بررسی pso در محیطهای پویا - Artificial Intelligence

**Astaraki** · ۰۷-۱۳-۱۳۸۸, ۰۳:۵۹ بعد از ظهر

در این مقاله عملکرد PSO در محیطهای پویا (پیوسته و گسسته) را مورد بررسی قرار خواهم داد.
فايل مثال کاربردي انجام شده در اين مقاله، از ضميمه قابل دريافت مي باشد

مقدمه :
در اين مقاله موارد زير مورد بررسي قرار خواهد گرفت :
1-پياده سازي PSO در محيط هاي پيوسته و پويا
Full Model (a
Social Only Model (b
2-پياده سازي PSO در محيط هاي گسسته و پويا
Full Model (a
Social Only Model (b
3-پياده سازي PSO در محيط هاي پيوسته و پويا همراه با local maxima زياد

کلمات کليدي :
Particle Swarm Optimization,PSO,Discrete، گسسته ، پويا ، Dynamic

.................................................. ...............
1-پياده سازي PSO در محيط هاي پيوسته و پويا

Full Model (a

پيدا کردن مينيمم تابع زير :

براي پياده سازي از يک نگهبان استفاده شده که در ابتدا به صورت رندوم انتخاب ميشود.

هنگامي که تغيير توسط نگهبان تشخيص داده ميشود کارهاي زير انجام مي شود:

Inertia Weight به يک مقدار دهي ميشود و مجددا با استفاده از يک تابع نزولي در طي انجام فرايندها در iteration هاي متوالي اين مقدار مرتبا کاهش ميابد .

يک سوم از جمعيتي که نسبت به Global Best در فاصله دورتري هستند مجددا مقدار دهي ميشوند( روش Partial Reinitialization ) .

Personal Best و Global Best ها مجددا بررسي ميشوند.

و به جهت به روز رساني swarm ها از Full Model استفاده کرده ايم يعني هم Personal Best و هم Global Best را به منظور تعيين جهت حرکت swarm ها در نظر گرفتيم .

توضيح توابع :

كد:

function f=fitness(particle,w1,w2)
f=((particle(1)-w1)^2+w2)+((particle(2)-w2)^2+w2);

اين تابع fitness را محاسبه مي کند .

كد:

function [min1,gbest]=global_best(swarm,w1,w2)
min1=fitness(swarm(1,:),w1,w2);
gbest=swarm(1,:);
dim=size(swarm);
for i=1:dim(1)
     min2=fitness(swarm(I,:),w1,w2);   
     if min2<min1
         min1=min2;
         gbest=swarm(I,:);
     end;
end;

اين تابع global best را همراه با Particle مربوطه ميابد و بعنوان خروجي برمي گرداند .

كد:

func function  [swarm,pbest]=REInitialize_Swarms(swarms,f,pbest,DETECTOR_SELECTED_index)
dim=size(swarms);
 index=[1:dim(1)];
 for i=1:(dim(1)-1)
     for j=(i+1):dim(1)
       if f(i)>f(j)
           temp=index(i);
           index(i)=index(j);
           index(j)=temp;
       end;
     end;
 end;
 for i=floor(dim(1)/4):dim(1)
 if index(i)~=DETECTOR_SELECTED_index
  swarms(index(i),:)=10*rand(1,2)+swarms(index(1),:)-5 ;
 end;
 end;
 swarm=swarms;

اين تابع يک سوم جمعيت را که در موقعيت بدتري نسبت به global best قرار دارند را مجددا مقدار دهي ميکند . البته ذره نگهبان را دست نمي زند.

كد:

function DynamicPSO_With_OneDetectionNOTChanged

تابع اصلي است .

در اين function به منظور دايناميک کردن تابع پياده سازي شده از کد زير استفاده کرده ايم :

كد:

if(rnd<.1) 
  w1=rand*10;
  w2=rand*30;
end;

در اين قسمت مقدار ذره نگهبان چک ميشود :

كد:

if (Detector_Fitness_last ~=  Detector_Fitness_now)
       % IT means chenges accoured
       D=1;
       for fcount=1:dim(1)
           f(fcount)=fitness(swarm(fcount,:),w1,w2);
       end;
        [swarm,pbest]=REInitialize_Swarms(swarm,f,pbest,DETECTOR_SELECTED_index);
       [min1,gbest]=global_best(swarm,w1,w2);
       Q=1;
       k=1;
 end;

به منظور اجراي برنامه DYNAMIC_FINAL_PROJECT.m را اجرا کنيد فرم زير را پس از اجرا مشاهده خواهيد کرد .

و پس از تنظيم مقادير C1 و C2 و Iteration و Number Of Swarm ، بر روي دکمه Continues Dynamic PSO(Full Model) کليک کنيد .

اجراي برنامه به فرم زير خواهد بود :

مشاهده خواهيد کرد که پس از هر تغيير تعدادي از Swarm ها مجددا به صورت رندوم مقدار دهي مي شوند و سرعت حرکت آنها مجددا زياد مي شود .

Social Only Model (b

مدل فقط اجتماعي کارآيي خوبي دارد اگر در محيط بهينه محلي با قدرت جذب زياد نداشته باشيم.
بخاطر اينکه در اين مورد به بهترين گذشته ذرات نگاهي نداريم اگر بهترين ذره به سمت بهينه محلي تمايل پيدا کند قادر به گريز از آن نخواهد بود.
در اين پياده سازي از مدل فقط اجتماعي استفاده کرديم که در اين تابع چون مينيمم محلي وجود ندارد در نتيجه نسبت به Full Model تغييري مشاهده نخواهيم کرد .
محاسبه سرعت در هر مرحله در اين روش با Full Model تفاوت دارد و بصورت زير است :

به منظور اجراي برنامه DYNAMIC_FINAL_PROJECT.m را اجرا کنيد فرم زير را پس از اجرا مشاهده خواهيد کرد :

سپس بر روي دکمه Continues Social Only PSO کليک کنيد . اجراي برنامه به شکل زير خواهد بود :

در اين نمودار حرکت ذرات (Swarm) بر روي منحني مشهود است .

2-پياده سازي PSO در محيط هاي گسسته و پويا

تا بحال PSO را در محيط پيوسته مورد بررسي قرار داديم در اين قسمت به نحوه عملکرد PSO در محيط گسسته مي پردازيم .
در اين نوع محيطها Partcle ها ديگر نمي توانند هر مقداري به خود بگيرند ، يکسري مقادير خواص برايشان تعريف شده است ، از اينرو گسسته هستند .
به منظور پياده سازي ، يک شبکه را شبيه سازي کرديم که حجم Packet هايي که بين نودها در حال حرکت هستند به عنوان وزن آن يال در يک گراف مش نمايش داده مي شود ، و به منظور شبيه سازي Packet هاي در حال انتقال به صورت رندوم از وزن آن يال کم يا به آن اضافه مي کنيم
در اين حالت Swarm ها انواع مسير هاي ممکن از مبدا به مقصد را شامل مي شوند که به اين منظور در ابتدا به صورت تصادفي مقدار مي گيرند و در طي مراحل اجرا به سمت مسير بهينه همگرا مي شوند .
در محيط پويا همگرايي به سمت بهترين مسير تا زماني رخ مي دهد که ذره نگهبان تغييري حس نکرده باشد به محض اينکه ذره نگهبان تغيير محيط را درک کند مجددا ضريب اينرسي را يک مي کند و تعدادي از ذرات مجددا مقدار دهي مي شوند و بنابراين توانايي جهت يافتن مسير بهينه جديد را مجددا پيدا مي کند .
به منظور توليد Swarm ها از روش زير استفاده کرديم

كد:

swarm=rand(counterOFswarms,(NodeCounter^2));
dim=size(swarm);
DETECTOR_SELECTED_index=floor(rand*dim(1)+1); %initialize
for i=1:dim(1)
swarm(i,:)=set_Particle2(swarm(i,:),NodeCounter,destination,from);
end;
function Particle=set_Particle2(particle,node_count,destination,from)
  dim=size(particle);
  distance=1/node_count;
 particle(1)=from;
 particle(dim(2))=destination;
  for j=2:(dim(2)-1)
      sum=0;
   for i=1:node_count
      if particle(1,j)>sum && particle(1,j)<=(sum+distance)
          particle(1,j)=i;
          break;
      end;
      sum=sum+distance;
   end;
  end;
  Particle=particle;

جهت اجراي برنامه DYNAMIC_FINAL_PROJECT.m را اجرا کنيد فرم زير را پس از اجرا مشاهده خواهيد کرد .

و پس از تنظيم مقادير C1 و C2 و Iteration و Number Of Swarm و مبدا و مقصد Packet بر روي دکمه Dynamic PSO(Full Model) Discreteکليک کنيد .

اجراي برنامه به فرم زير خواهد بود :

3-پياده سازي PSO در محيط هاي پيوسته و پويا همراه با local maxima زياد :

براي پياده سازي از تابع زير استفاده کرديم :

که به جهت دايناميک کردن آن w1و w2 در هر مرحله بصورت تصادفي مقدار دهي مي شوند .
فرم تابع را با تغيير w ها شکلهاي زير را بخود مي گيرد :

در اينگونه محيطها انتخاب ذره نگهبان بسيار مهم مي باشد . و همچنين نوع مدل که Social يا Full مهم مي باشد .
انتخاب مدل Social امکان گرفتار شدن Swarm ها را در ماکزيمم محلي افزايش مي دهد .
به منظور اجراي برنامه تابع DynamicPSO_With_OneDetectionChanged_with_localmini ma را باز کنيد و پارامترهاي(c1,c2,iteration,counterOFswar ms) را به عنوان ورودي به تابع ارسال کنيد.
نمودار اجراي برنامه به شکل زير است :

فايل مثال کاربردي انجام شده در اين مقاله، از لينک زير قابل دريافت مي باشد