الگوریتم بهینه سازی pso

[moji5]

فرض کنید شما و گروهی از دوستانتان به دنبال گنج می‌گردید. هر یک از اعضای گروه یک فلزیاب و یک بی‌سیم دارد که می‌تواند مکان و وضعیت کار خود را به همسایگان نزدیک خود اطلاع بدهد. بنابراین شما می‌دانید آیا همسایگانتان از شما به گنج نزدیکترند یا نه؟ پس اگر همسایه‌ای به گنج نزدیکتر بود شما می‌توانید به طرف او حرکت کنید. با چنین کاری شانس شما برای رسیدن به گنج بیشتر می‌شود و همچنین گنج زودتر از زمانی که شما تنها باشید، پیدا می‌شود.

این یک مثال ساده از رفتار جمعی یا Swarm behavior است که افراد برای رسیدن به یک هدف نهایی همکاری می‌کنند. این روش مؤثرتر از زمانی است که افراد جداگانه عمل کنند. Swarm را می‌توان به صورت مجموعه‌ای سازمان یافته از موجوداتی تعریف کرد که با یکدیگر همکاری می‌کنند. در کاربردهای محاسباتی Swarm intelligence از موجوداتی مانند مورچه‌ها، زنبورها، موریانه‌ها، دسته‌های ماهیان و دسته‌ی پرندگان الگو برداری می‌شود. در این نوع اجتماعات هر یک از موجودات ساختار نستباً ساده‌ای دارند ولی رفتار جمعی آنها بی‌نهایت پیچیده است. برای مثال در کولونی مورچه‌ها هر یک از مورچه‌ها یک کار ساده‌ی مخصوص را انجام می‌دهد ولی به طور جمعی عمل و رفتار مورچه‌ها، ساختن بهینه‌ی لایه، محافظت ازملکه و نوزادان، تمیز کردن لانه، یافتن بهترین منابع غذایی و بهینه‌سازی استراتژی حمله را تضمین می‌کند. رفتار کلی، یک Swarm به صورت غیر خطی از آمیزش رفتارهای تک‌تک اجتماع بدست می‌آید. یا به عبارتی یک رابطه‌ی بسیار پیچیده بین رفتار جمعی و رفتار فردی یک اجتماع وجود دارد. رفتار جمعی فقط وابسته به رفتار فردی افراد اجتماع نیست بلکه به چگونگی تعامل میان افراد نیز وابسته است. تعامل بین افراد، تجربه‌ی افراد درباره‌ی محیط را افزایش می‌دهد و موجب پیشرفت اجتماع می‌شود. ساختار اجتماعی Swarm بین افراد مجموعه کانالهای ارتباطی ایجاد می‌کند که طی آن افراد می‌توانند به تبادل تجربه‌های شخصی بپردازند، مدل‌سازی محاسباتی Swarmها کاربردهای موفق و بسیاری را در پی داشته است مانند:

Function optimization, Finding optimal roots, scheduling, structural optimization, Image and data analysis

کاربردهای زیادی از مطالعه‌ی Swarmهای مختلف وجود دارد. از این دسته می‌توان به کولونی مورچه‌ها (Ant Colony) و دسته‌ی پرندگان (Bird Flocks) اشاره نمود.


(Particle Swarm Optimitation(PSO:

الگوریتم PSO یک الگوریتم جستجوی اجتماعی است که از روی رفتار اجتماعی دسته‌های پرندگان مدل شده است. در ابتدا این الگوریتم به منظور کشف الگوهای حاکم بر پرواز همزمان پرندگان و تغییر ناگهانی مسیر آنها و تغییر شکل بهینه‌ی دسته به کار گرفته شد.
در PSO، particleها در فضای جستجو جاری می‌شوند. تغییر مکان particleها در فضای جستجو تحت تأثیر تجربه و دانش خودشان و همسایگانشان است. بنابراین موقعیت دیگر particleهای Swarm روی چگونگی جستجوی یک particle اثر می‌گذارد.
نتیجه‌ی مدل‌سازی این رفتار اجتماعی فرایند جستجویی است که particleها به سمت نواحی موفق میل می‌کنند. Particleها در Swarm از یکدیگر می‌آموزند و بر مبنای دانش بدست آمده به سمت بهترین همسایگان خود می‌روند.

Particle swarm Optimitation Algorithm:

اساس کار PSO بر این اصل استوار است که در هر لحظه هر particle مکان خود را در فضای جستجو با توجه به بهترین مکانی که تاکنون در آن قرار گرفته است و بهترین مکانی که در کل همسایگی‌اش وجود دارد، تنظیم می‌کند.

فرض کنید می‌خواهیم زوج مرتب (x,y) را طوری بدست آوریم که تابع F(x,y)=x2+y2، مینیمم شود. ابتدا نقاطی را به صورت تصادفی در فضای جستجو، روی صفحه‌ی x-y انتخاب می‌کنیم. فرض کنید این Swarm را به 3 همسایگی تقسیم کنیم که در هر همسایگی نقاط موجود با یکدیگر تعامل دارند. در هر همسایگی هر یک از نقاط به سمت بهترین نقطه در آن همسایگی و بهترین مکانی که آن نقطه تاکنون در آن قرار داشته است، حرکت می‌کند. برای حل یک مسئله چند متغیر بهینه‌سازی می‌توان از چند Swarm استفاده کرد که هر یک از Swarmها کار مخصوصی را انجام می‌دهند. این همان ایده‌ای است که Ant colony از آن ریشه می‌گیرد. از آنجا که دانش Swarm intelligence بسیار جدید است در حال حاضر کاربردهای کمی از آن شناخته شده است. ولی صاحبنظران معتقدند با این رشد روزافزون، Swarm intelligence می‌تواند نقش مهمی را در علوم مختلف از جمله مهندسی نفت ایفا کند.

[moji5]

دانلود رایگان کد الگوریتم PSO یا الگوریتم پرندگان

لگوریتم بهینه سازی ازدحام ذرات یا PSO، که به نام الگوریتم پرندگان نیز شناخته می شود، یکی از الگوریتم های قدرتمند و پر طرفدار برای بهینه سازی است که بیشتر به خاطر سرعت همگرایی نسبتا بالایی که دارد، مورد استفاده قرار می گیرد. این الگوریتم با وجود عمر کمی که دارد، اما توانسته است در حوزه های کاربردی بسیاری، از الگوریتم های قدیمی تر، مانند الگوریتم ژنتیک، پیشی بگیرد و به عنوان انتخاب اول محسوب شود. گروه برنامه نویسان متلب سایت، کد الگوریتم کلاسیک PSO را تهیه نموده در برای دانلود در اختیار دوستان و مراجعین عزیز قرار داده است.

لینک دانلود کد الگوریتم PSO در ادامه قرار داده شده است:

http://uploading.com/files/1ecc4ecb/PSO.rar/

[moji5]

بررسی 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)
fparticle(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=1dim(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 را اجرا کنيد فرم زير را پس از اجرا مشاهده خواهيد کرد .
و پس از تنظيم مقادير 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,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=2dim(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) را به عنوان ورودي به تابع ارسال کنيد.
نمودار اجراي برنامه به شکل زير است :

دموی برنامه : دانلود

[moji5]

دانلود رایگان کد متلب الگوریتم پرندگان یا الگوریتم PSO دانلود رایگان کد متلب برای

الگوریتم پرندگان، الگوریتم بهینه سازی ازدحام ذرات یا الگوریتم PSO

Particle Swarm Optimization with Matlab

لینک دانلود این برنامه در ادامه قابل مشاهده است:

لینک دانلود رایگان کد متلب الگوریتم پرندگان یا الگوریتم PSO


پسورد فایل: matlabsite.com

[moji5]

الگوریتم Particle swarm Optimization یا PSO

PSO حالتی از هوش دسته جمعی مبتنی بر الگوریتم است. راه حلی برای مسئله بهینه سازی در فضای جستجو یا مدل سازی رفتار اجتماعی در هنگام وجود هدفهاست.

مرور

PSO یک الگوریتم کامپیوتری مبتنی بر جمعیت و کتره ای برای حل مسئله است. PSOیک نوع هوش جمعی مبتنی بر اصول روانشناسی اجتماعی و فراهم آوردن بینشی در رفتار اجتماعی و کمک کردن به کاربردهای مهندسی است.

الگوریتمPSO برای اولین بار در 1975 توسط James KennedyوRussell C.Eberhart توصیف شد.این تکنیک ها بسیار رشد کرده اند و نسخه اصلی این الگوریتم به طور واضحی در نسخه های امروزی قابل شناخت است.
تاثیر گذاری اجتماعی و یاد گیری اجتماعی یک شخص را قادر می سازد تا ثبات دانستنی هایش را برقرار سازد.
انسان ها مسائلشان را به کمک صحبت با دیگران و نیز به کمک برهم کنش با باورهایشان، گرایش هایشان و تغییر رفتارشان حل می کنند؛ این تغییرات را می توان به طور نمونه به شکل حرکت افراد به سوی یکدیگر در فضای آگاهی اجتماعی مجسم کرد.

ذرات جمعی شبیه سازی شده ، این نوع از بهینه سازی اجتماعی می باشند.مسئله داه شده و چند راه برای ارزیابی مسئله پیشنهادی به ..... در شکل کلی "تابع شایستگی"حضور دارند.ساختار ارتباطی یا شبکه اجتماعی برای واگذار کردن هر همسایگی به یک فرد تعریف شده تا آن فرد با آن همسایگی بر هم کنش داشته باشد.سپس گروه کارگزاران به عنوان مهمان های سرزده برای راه حل های مسئله تعریف می شوند که آنها را به نام "ذرات" نیز می شناسیم؛ از این رو آنها را "ذرات دسته جمعی" نام نهاده ایم.


یک فرایند تکراری برای بهبود کاندیدا ها در طی حرکت ذرات در نظر گرفته شده است. ذرات مکررا شایستگی راه حل های کاندیدا را ارزیابی می کنند و موقعیتی را که در آن بهترین موفقیت را داشته اند ، به خاطر می سپارند. بهره راه حل کارگزاران "بهترین ذره" یا "بهترین محل" نامیده می شود. هر ذره این اطلاعات را برای دیگر ذرات موجود در همسایگی قابل دسترسی می کند.

همچنین آنها نیز می توانند ببینند که دیگر ذرات موجود در همسایگی در کجا بهترین موفقیت را داشته اند.

رکت ها در فضای جستجو بوسیله ی موفقیت های قبلی ؛ با افرادی که بیشتر مواقع همگرایی دارند، سرانجام بهتر از حالتی است که نزدیک شدن به جواب بوسیله عواملی فاقد هوش جمعی ولی با همین روش صورت گیرد.

گروه به صورت نمونه بوسیله ذرات در فضای چند بعدی که مکان و سرعت دارد، مدل سازی می شود.


این ذرات در میان این ابر فضا(فضای دارای بیش از سه بعد) پرواز می کنند و دو توانایی ضرورری دارند:

1-حافظه ای برای ذخیره سازی بهترین مکان خود2-آگاهی در مورد بهترین موقعیت در همسایگی خود یا در کل فضای پاسخ ها اعضای دسته جمعی مکان های خوب را به یکدیگر از طریق ارتباط انتقال می دهند و موقعیت و سرعتشان را با مکان های خوب تنظیم می کنند.

هر ذره برای اعمال تغییری مناسب در مکان و سرعت خود اطلاعات زیر را دارا می باشد:

1-"بهترین عمومی" که برای همه شناخته شده است و هنگامی که هر ذره بهترین مکان جدیدی را شناسایی کند، فورا برای بقیه ذرات اطلاعات مربوطه را به روز رسانی می کند.

2-"بهترین همسایگی"که ذره از طریق ارتباط با زیر مجموعه های گروه ، آنرا بدست می آورد.

3-"بهترین محلی"که بهترین راه حلی است که ذره تا کنون تجربه کرده است.

همه ذرات شروع به تاثیر پذیری از "بهترین عمومی" می کنند تا سرانجام به آن نزدیک شوند.
ذرات در فضای جستجو در نزدیکی "بهترین عمومی" سیر می کنند و بقیه فضا را کاوش نمی کنند ، به این پدیده"همگرایی" گفته می شود.
اگر ضریب اینرسی سرعت را کوچک انتخاب کنیم، تمام ذرات می توانند سرعتشان را کاهش دهند تا اینکه در "بهترین عمومی" به سرعت صفر نزدیکتر شوند.
یک را خروج از وضعیت همگرایی اولیه(نامطلوب) این است که دوباره به موقعیت ذرات (پس از رخ دادن همگرایی )مقدار اولیه بدهیم.

[amirshar]

ميشه با يك مثال ساده رياضي توضيح بدي

[moji5]

نمیدونم درستیش رو اما مثال ساده تر از این به ذهنم نمیرسه
مثلا" داری تو یه سری عدد که به صورت نزولی سعودی مرتب شده دنبال یه عدد میگردی
به طور تصادفی یه عدد رو میخونی بعد با عددی که دنبالش میگردی مقایسه میکنی اگه از عددی که میخوای بزرگتر بود حالا از نیمه پایین انتخاب میکنی
اگه کوچیکتر بود از نیمه بالا انتخاب میکنی
تا جایی این انتخاب رو انجام میدی که به عدد مورد نظرت برسی
این الگوریتم میتونه کاره مرتب سازی داده ها و انتخاب سمت مناسب رو انجام بده

[AFROUZ_H]

سلام
Pso انواع مختلفي داره؟
و اينكه لينك دانلودتون كار نمي كرد

[moji5]

شاید بسته به نوع مرتب سازی یعنی صعودی یا نزولی
نوع عملکردش متفاوت باشه
اطلاعات بیشتری ندارم
با تشکر از سایت مطلب
http://uc-njavan.ir/file/do.php?id=42

[M.esmaeili]

سلام، من دارم روی این الگوریتم برای پایان نامه ام کار می کنم. یکی از مشکلات این الگوریتم زمانی پیش میاد که ذرات از فضای جستجو خارج میشن. در این حالت یکی از راه حل ها برگردوندن ذره به مرز و صفر کردن سرعت اونها است. در این حالت ذره تا آخر الگوریتم روی مرز باقی می مونه و ایجاد مشکل میکنه. کسی راه حلی براش سراغ داره؟