Y@SiN
02-11-2010, 06:58 PM
در این مقاله عملکرد 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
پيدا کردن مينيمم تابع زير :
http://pnu-club.com/imported/2010/02/783.jpg
http://pnu-club.com/imported/2010/02/784.jpg
براي پياده سازي از يک نگهبان استفاده شده که در ابتدا به صورت رندوم انتخاب ميشود.
هنگامي که تغيير توسط نگهبان تشخيص داده ميشود کارهاي زير انجام مي شود:
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_SELEC TED_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_SELECT ED_index);
[min1,gbest]=global_best(swarm,w1,w2);
Q=1;
k=1;
end;
به منظور اجراي برنامه DYNAMIC_FINAL_PROJECT.m را اجرا کنيد فرم زير را پس از اجرا مشاهده خواهيد کرد .
http://pnu-club.com/imported/2010/02/785.jpg
و پس از تنظيم مقادير C1 و C2 و Iteration و Number Of Swarm ، بر روي دکمه Continues Dynamic PSO(Full Model) کليک کنيد .
اجراي برنامه به فرم زير خواهد بود :
http://pnu-club.com/imported/2010/02/786.jpg
مشاهده خواهيد کرد که پس از هر تغيير تعدادي از Swarm ها مجددا به صورت رندوم مقدار دهي مي شوند و سرعت حرکت آنها مجددا زياد مي شود .
Social Only Model (b
مدل فقط اجتماعي کارآيي خوبي دارد اگر در محيط بهينه محلي با قدرت جذب زياد نداشته باشيم.
بخاطر اينکه در اين مورد به بهترين گذشته ذرات نگاهي نداريم اگر بهترين ذره به سمت بهينه محلي تمايل پيدا کند قادر به گريز از آن نخواهد بود.
در اين پياده سازي از مدل فقط اجتماعي استفاده کرديم که در اين تابع چون مينيمم محلي وجود ندارد در نتيجه نسبت به Full Model تغييري مشاهده نخواهيم کرد .
محاسبه سرعت در هر مرحله در اين روش با Full Model تفاوت دارد و بصورت زير است :
http://pnu-club.com/imported/2010/02/787.jpg
به منظور اجراي برنامه DYNAMIC_FINAL_PROJECT.m را اجرا کنيد فرم زير را پس از اجرا مشاهده خواهيد کرد :
http://pnu-club.com/imported/2010/02/788.jpg
سپس بر روي دکمه Continues Social Only PSO کليک کنيد . اجراي برنامه به شکل زير خواهد بود :
http://pnu-club.com/imported/2010/02/789.jpg
در اين نمودار حرکت ذرات (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,de stination,from);
end;
function Particle=set_Particle2(particle,node_count,destina tion,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 را اجرا کنيد فرم زير را پس از اجرا مشاهده خواهيد کرد .
http://pnu-club.com/imported/2010/02/790.jpg
و پس از تنظيم مقادير C1 و C2 و Iteration و Number Of Swarm و مبدا و مقصد Packet بر روي دکمه Dynamic PSO(Full Model) Discreteکليک کنيد .
اجراي برنامه به فرم زير خواهد بود :
http://pnu-club.com/imported/2010/02/791.jpg
3-پياده سازي PSO در محيط هاي پيوسته و پويا همراه با local maxima زياد :
براي پياده سازي از تابع زير استفاده کرديم :
http://pnu-club.com/imported/2010/02/792.jpg
که به جهت دايناميک کردن آن w1و w2 در هر مرحله بصورت تصادفي مقدار دهي مي شوند .
فرم تابع را با تغيير w ها شکلهاي زير را بخود مي گيرد :
http://pnu-club.com/imported/2010/02/793.jpg
http://pnu-club.com/imported/2010/02/794.jpg
http://pnu-club.com/imported/2010/02/795.jpg
در اينگونه محيطها انتخاب ذره نگهبان بسيار مهم مي باشد . و همچنين نوع مدل که Social يا Full مهم مي باشد .
انتخاب مدل Social امکان گرفتار شدن Swarm ها را در ماکزيمم محلي افزايش مي دهد .
به منظور اجراي برنامه تابع DynamicPSO_With_OneDetectionChanged_with_localmini ma را باز کنيد و پارامترهاي(c1,c2,iteration,counterOFswar ms) را به عنوان ورودي به تابع ارسال کنيد.
نمودار اجراي برنامه به شکل زير است :
http://pnu-club.com/imported/2010/02/796.jpg
فايل مثال کاربردي انجام شده در اين مقاله، از لينک زير قابل دريافت مي باشد
فايل مثال کاربردي انجام شده در اين مقاله، از ضميمه قابل دريافت مي باشد
مقدمه :
در اين مقاله موارد زير مورد بررسي قرار خواهد گرفت :
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
پيدا کردن مينيمم تابع زير :
http://pnu-club.com/imported/2010/02/783.jpg
http://pnu-club.com/imported/2010/02/784.jpg
براي پياده سازي از يک نگهبان استفاده شده که در ابتدا به صورت رندوم انتخاب ميشود.
هنگامي که تغيير توسط نگهبان تشخيص داده ميشود کارهاي زير انجام مي شود:
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_SELEC TED_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_SELECT ED_index);
[min1,gbest]=global_best(swarm,w1,w2);
Q=1;
k=1;
end;
به منظور اجراي برنامه DYNAMIC_FINAL_PROJECT.m را اجرا کنيد فرم زير را پس از اجرا مشاهده خواهيد کرد .
http://pnu-club.com/imported/2010/02/785.jpg
و پس از تنظيم مقادير C1 و C2 و Iteration و Number Of Swarm ، بر روي دکمه Continues Dynamic PSO(Full Model) کليک کنيد .
اجراي برنامه به فرم زير خواهد بود :
http://pnu-club.com/imported/2010/02/786.jpg
مشاهده خواهيد کرد که پس از هر تغيير تعدادي از Swarm ها مجددا به صورت رندوم مقدار دهي مي شوند و سرعت حرکت آنها مجددا زياد مي شود .
Social Only Model (b
مدل فقط اجتماعي کارآيي خوبي دارد اگر در محيط بهينه محلي با قدرت جذب زياد نداشته باشيم.
بخاطر اينکه در اين مورد به بهترين گذشته ذرات نگاهي نداريم اگر بهترين ذره به سمت بهينه محلي تمايل پيدا کند قادر به گريز از آن نخواهد بود.
در اين پياده سازي از مدل فقط اجتماعي استفاده کرديم که در اين تابع چون مينيمم محلي وجود ندارد در نتيجه نسبت به Full Model تغييري مشاهده نخواهيم کرد .
محاسبه سرعت در هر مرحله در اين روش با Full Model تفاوت دارد و بصورت زير است :
http://pnu-club.com/imported/2010/02/787.jpg
به منظور اجراي برنامه DYNAMIC_FINAL_PROJECT.m را اجرا کنيد فرم زير را پس از اجرا مشاهده خواهيد کرد :
http://pnu-club.com/imported/2010/02/788.jpg
سپس بر روي دکمه Continues Social Only PSO کليک کنيد . اجراي برنامه به شکل زير خواهد بود :
http://pnu-club.com/imported/2010/02/789.jpg
در اين نمودار حرکت ذرات (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,de stination,from);
end;
function Particle=set_Particle2(particle,node_count,destina tion,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 را اجرا کنيد فرم زير را پس از اجرا مشاهده خواهيد کرد .
http://pnu-club.com/imported/2010/02/790.jpg
و پس از تنظيم مقادير C1 و C2 و Iteration و Number Of Swarm و مبدا و مقصد Packet بر روي دکمه Dynamic PSO(Full Model) Discreteکليک کنيد .
اجراي برنامه به فرم زير خواهد بود :
http://pnu-club.com/imported/2010/02/791.jpg
3-پياده سازي PSO در محيط هاي پيوسته و پويا همراه با local maxima زياد :
براي پياده سازي از تابع زير استفاده کرديم :
http://pnu-club.com/imported/2010/02/792.jpg
که به جهت دايناميک کردن آن w1و w2 در هر مرحله بصورت تصادفي مقدار دهي مي شوند .
فرم تابع را با تغيير w ها شکلهاي زير را بخود مي گيرد :
http://pnu-club.com/imported/2010/02/793.jpg
http://pnu-club.com/imported/2010/02/794.jpg
http://pnu-club.com/imported/2010/02/795.jpg
در اينگونه محيطها انتخاب ذره نگهبان بسيار مهم مي باشد . و همچنين نوع مدل که Social يا Full مهم مي باشد .
انتخاب مدل Social امکان گرفتار شدن Swarm ها را در ماکزيمم محلي افزايش مي دهد .
به منظور اجراي برنامه تابع DynamicPSO_With_OneDetectionChanged_with_localmini ma را باز کنيد و پارامترهاي(c1,c2,iteration,counterOFswar ms) را به عنوان ورودي به تابع ارسال کنيد.
نمودار اجراي برنامه به شکل زير است :
http://pnu-club.com/imported/2010/02/796.jpg
فايل مثال کاربردي انجام شده در اين مقاله، از لينک زير قابل دريافت مي باشد