بهینه‌سازی انبوه ذره

بهینه‌سازی ازدحام ذره (حرکت ذرات) بهینه‌سازی ازدحام ذره:
در علم کامپیوتر، بهینه‌سازی ازدحام ذره (pso) روشی محاسباتی است که یک مسئله را با تکرارهای متوالی از طریق بهبود دادن یک جواب انتخابی با توجه به یک معیار کیفیتی مشخص، بهینه‌سازی می‌کند. pso با داشتن جمعیتی از راه حل‌های انتخابی، در این‌جا ذرات دوبله شده، و حرکت دادن این ذرات در فضای جستجو بر اساس یک فرمول ساده ریاضی برای موقعیت ذره و سرعت آن، مسئله را بهینه‌سازی و حل می‌کند.
هر حرکت ذره تحت تاثیر بهترین موقعیت محلی شناخته شده آن است و همچنین در فضای جستجو به سوی بهترین موقعیت‌های شناخته شده راهنمایی می‌شود، به طوری که این موقعیت‌ها هنگامی که موقعیت‌های بهتری که به وسیله ذرات دیگر پیدا می‌شود به روزآوری می‌شوند. در اینجا انتظار می‌رود که ذره به سوی بهترین راه حل‌ها حرکت داده شود.
Pso به‌طور کلی به کندی (kennedy، ایبرهارت (Eberhart) و شی (shi) نسبت داده می‌شود و اولین بار برای شبیه‌سازی رفتار اجتماعی، مانند بازنمایی خاصی از حرکت ارگانیسم‌ها در دسته پرندگان یا اجتماع ماهی‌ها ابه کار گرفته شد. این الگوریتم به منظور بهینه‌سازی مورد بررسی و ساده‌سازی قرار گرفت
کتاب کندی و ایبرهارت بسیاری از جنبه‌های فلسفی pso و هوش ذره راای توصیف می‌کند. پولی (poli) مطالعات گسترده‌ای بر روی استفاده‌های pso انجام داده‌است. به‌تازگی، بنیادی (Bonyadi) و Michalewicz بازنگری جامعی بر مسائل تئوریکی و تجربی PSO منتشر کرده‌اند.
PSO یک روش فراابتکاری است به گونه‌ای که فرضیه‌های بسیار اندکی در مورد مسئله‌ای که بهینه‌سازی می‌شود در نظر می‌گیرد و می‌تواند فضاهای خیلی بزرگی از راه حل‌های انتخابی را جستجو کند. گرچه، روش فراابتکاری‌ای همچون pso جواب بهینه‌ای که یافته می‌شود را تضمین نمی‌کند. PSO به ویژه از گرادیان مسئله بهینه‌سازی استفاده نمی‌کند و این به معنای آن است که PSO نیازی ندارد که مسئله مورد بهینه‌سازی، مشتق پذیر باشد آنچنان که در روش‌های کلاسیک بهینه‌سازی همچون روش‌های quasi-newton method وgradient descent نیاز است؛ بنابراین PSOهمچنین می‌تواند برای بهینه‌سازی مسایلی مورد استفاده قرار گیرد که نسبتا نامنظم، شلوغ هستند و در طی زمان تغییر می‌کنند.
مفاد
۱الگوریتم
۲انتخاب پارامتر
۳همسایگان و توپولوزی
۴کارهای داخلی
۱–۴همگرایی
۲–۴پیش داوری
۵گونه‌های متفاوت
۱–۵ساده‌سازی
۲–۵بهینه‌سازی چند منظوره
۳–۵ PSOترکیبی، گسسته، باینری
۶موارد ملاحظه کردنی
۷مراجع
۸خطوط خارجی
الگوریتم:گونه‌های اصلی الگوریتم PSOبا داشتن جمعیتی (که انبوه نامیده می‌شود) از راه حل‌های انتخابی (که ذرات نامیده می‌شوند) کار می‌کند. این ذرات بر اساس تعدادی فرمول ساده حول فضای جستجو حرکت می‌کنند. حرکات ذرات به وسیله بهترین موقعیت شناخته شده؟ در فضای جستجو همچنین بهترین موقعیت شناخته شده کل انبوه راهنمایی می‌شود. وقتی که موقعیت‌های اصلاح شده این را کشف می‌کنند سپس می‌آیند تا حرکات انبوه را هدایت کنند. فرایند تکرار می‌شود و با انجام چنین چیزی می‌پرد، اما تضمین نمی‌شود که راه حل رضایت بخش سرانجام حل خواهد شد. منظما اجازه دهید
f:Rn
R تابع هزینه‌ای باشد که باید به حداقل برسد. تابع راه حل انتخابی را می‌گیرند همچون توافق به شکل بردار عدد واقعی و یک بردار واقعی همچون خروجی ایجاد می‌شود که نشان می‌دهدمقدار تابع هدف از راه حل انتخابی داده شده را نشان می‌دهد. عنصر fشناخته شده نمی‌باشد. هدف ان است تا راه حل aرا برایf(b) ≥ f(a)برای تمام bدر فضای جستجو پیدا کنیم، که به معنای آن است aحداقل جهانی است. حداکثر می‌تواند با بررسی به جای f- =تابعhانجام شود. اجازه دهید که s تعداد ذرات در انبوه باشد، هر کدام دارای موقعیت Xi € Rn در فضای پژوهشی ri € Rnهستند. اجازه دهید pi بهترین موقعیت شناخته شده ذره iباشد و اجازه دهید gبهترین موقعیت شناخته شده کل انبوه باشد. الگوریتم PSOاصلی سپس به صورت زیر است:
برای هر ذره i=۱,…,sبه ترتیب زیر عمل کنید:
موقعیت ذره با بردار تصادفی یکپارچه توزیع شده ایجاد می‌شود:xi~U(bi,bup) جاییکه biو bupمحدوده‌های پایین‌تر و بالاتر فضای جستجو هستند.
بهترین موقعیت ذره شناخته شده برای موقعیت ابتدایی آن را ایجاد کنید pi←xi
اگرf(pi)<f(g)) (بهترین موقعیت شناخته شده انبوه را بروز درمی‌آورد i← piد:g
سرعت ذره را ایجاد کنیدri~U(-|bup- bi|,|bup- bi|)
تا اینکه یک ضابطه انقضا دیده می‌شود (برای مثال، تعداد iterationهای ایجاد شده، یا یک راه حل با مقدار تابع واقعی کافی پیدا می‌شود)، تکرار کنید:
برای هر ذره i=۱,…,sانجام دهید
برای هر بعدd=۱,…,.nانجام دهید
اعداد تصادفی را انتخاب کنیدrg~U(0 ۱)  rp
سرعت ذره را به روز درآورید:
Vi,d←???Vi,d+prp(pi,d+Xi,d)+ grg(gd-Xi,d)
موقعیت ذره را به روز درآورید Xi← Xi+Vi
اگر (f(Xi)<f(pi))انجام دهید
بهترین موقعیت شناخته شده ذره را بروز درآورید:pi←Xi
اگر) (f(pi)<f(g) بهترین موقعیت شناخته شده انبوه بروز در می‌آید:g←pi
هم‌اکنون gبهترین راه حل را حفظ می‌کند.
تقسیم‌کننده پارامترهای؟ ،p،gرا انتخاب می‌کند و عملکرد و خاصیت روش PSOرا کنترل می‌کند، قسمت زیر را ملاحظه کنید.
انتخاب پارامتر:
انتخاب پارامترهای PSOمی‌تواند تاثیر زیادی برروی عملکرد بهینه‌سازی داشته باشد. انتخاب پارامترهای PSOکه بهترین عملکرد را به همراه دارد بنابراین هدف بسیاری از پروزه هااست. پارامترهای PSOهمچنین می‌تواند با استفاده از روی هم قرار دادن بهینه‌ساز دیگر تدوین شود همچون بهینه‌ساز متا. پارامترها همچنین برای انواع حس گرهای بهینه‌سازی تدوین شده‌است.
همسایگان و توپولوژی:
PSOاصلی در حداقل مرکزی نگه داشته می‌شود. نه با استفاده از بهترین موقعیت شناخته شده کل انبوه g، بلکه فقط با بهترین موقعیت شناخته شده؟ از ذره «حول» زیر مجموعه انبوه در حال حرکت، اجتناب می‌شود. چنین زیر مجموعه –انبوهی می‌تواند یک نمونه جغرافیایی باشد، برای مثال، «mنزدیک‌ترین ذرات» یا اغلب یک نمونه اجتمتعی برای مثال یک سری از ذرات که به هیچ فاصله‌ای بستگی ندارد. در چنین موارد، گفته می‌شود تنوع PSOبهترین مرکز باشد (در مقابل بهترین کلی برای PSOمرکزی). اگر فرض کنیم یک مسیر اطلاعاتی بین هر ذره و همسایگان آن وجود دارد، سری این خط‌ها یک گراف، یک شبکه ارتباطی می‌سازد که به اصطلاح توپولوژی تنوع PSOنامیده می‌شود. یک توپولوژی اجتماعی در حلقه که در هر ذره فقط دو همسایه داردفاما در این‌جا بیشتر است. توپولوژیضرورتا ثابت نیست و می‌تواند سازگاری(SPSO،Star،Stochastic،TRIBES،Swarm،Cyber)
جای تصویر صفحه۳
کارهای درونی:
در اینجا چندین مکتب فکری وجود دارد مبنی بر اینکه چرا و چگونه الگوریتم PSOمی‌تواند بهینه‌سازی را اجرا کند. باور معمول در بین پژوهشگران آن است که رفتار انبوه در بین رفتار اکتشافی متفاوت است، چرا که بررسی حوزه وسیع‌تری از فضای جستجو و رفتار بهره‌کشی به عنوان جستجوی مرکزی قلوداد می‌شود برای این منظور به بهینه‌سازی (احتمالا مرکز) نزدیک می‌شود. این مکتب فکری از آغازPSOمتداول شده‌است. این مکتب فکری اظهار دارد که الگوریتمPSO و پارامترهای آن باید انتخاب شوند برای این منظور احتمالا تعادل بین اکتشافی و بهره‌کشی از همگرایی زودرس به مناسبمرکز اجتناب می‌شود همچنین باز هم از سرعت مناسب همگرایی به مناسب‌ترین حد جلوگیری می‌کند. این باور آغازگر بسیاریPSOمتفاوت است، قسمت زیر را ملاحظه کنیدمکتب فکری دیگر رفتار انبوه PSOاست که به اصطلاح به خوبی درک نمی‌شود که چگونه بر روی عملکرد واقعی بهینه‌سازی، بخصوص برای فضاهای جستجوی بعدی و مسایل بهینه‌سازی احتمالا گسسته، شلوغ و وقت گیر تاثیر می‌گذارد. این مکتب فکری صرفا سعی می‌کند تا الگوریتم‌های PSOو پارامترهایی را پیدا کند که باعث عملکرد صحیح می‌شود صرف نظر از اینکه چگونه رفتار انبوه می‌تواند در رابطه با برای مثال بهره‌کشی و اکتشاف تفسیرشود. چنین مطالعاتی منجر به سادگی الگوریتم PSOشده‌اند، قسمت زیر را ملاحظه کنید.
همگرایی:
در رابطه با همگرایی PSOبه خصوص به معنای یک یا دو چیز است، اگر چه اغلب روشن نمی‌شود که تعریف معنادار است و گاهی اوقات به اشتباه تصور می‌شود آنها مشابه هستند.
همگرایی ممکن است به بهترین موقعیت شناخته شده انبوه gاشاره داشته باشد که بهترین مسئله را تنظیم (همگرا) می‌کند، صرف نظر از اینکه انبوه چگونه رفتار می‌کند.
همگرایی ممکن است به فروپاشی انبوهی اشاره داشته باشد که تمام ذرات به نقطه‌ای در فضای جستجو تلاقی پیدا کرده‌اند، که ممکن است یا ممکن نیست که بهتر باشد.
چندین فعالیت در زمینه تحلیل و بررسی محاسباتی همگرایی PSOدر مقاله وجود دارد. این تحلیل هادستورالعمل‌هایی برای انتخاب پارامترهای PSOارائه می‌دهد که اعتقاد بر آن است باعث همگرایی، واگرایی یا نوسان ذرات انبوه می‌شود و تحلیل و بررسی‌ها همچنین چندین PSOمتفاوت به دست داده‌است. به هر حال پی در سن(Pedersen)برای سادگی و سهولت کار انتقاداتی بر این تحلیل و بررسی کرده‌است همچنین آنها تصور می‌کنند انبوه فقط یک ذره دارد، که از متغیرهایStochasticاستفاده نمی‌کند و همین نقاط جذب که بهترین موقعیت شناخته شده ذره pو بهترین موقعیت شناخته شده انبوه gاست که در طی فرایند بهینه‌سازی ثابت باقی می‌ماند. علاوه بر این، بعضی تحلیل و بررسی‌ها موجب تعداد نامحدودiterationهای بهینه‌سازی می‌شود که احتمالا واقعی نیستند. این به معنای آن است که تعیین قابلیت‌های همگرایی الگوریتم‌های مختلف PSOو پارامترهابنابراین هنوز به نتایج تجربی بستگی دارند.
پیش داوری‌ها:
همان‌طور که PSOاصلی بعد به بعد کار می‌کند، نقطه راه حل هنگامی که برروی بردار فضای جستجو قرار دارد آسان‌تر پیدا می‌شود، برروی قطر، و حتی بر روی مرکز قرار دارد آسان‌تر پیدا می‌شود. روش اول از این پیش داوری جلوگیری می‌کند، و برای مقایسه‌های رضایت بخش است که دقیقا از ماسیل benchmark پیش داوری نشده‌ای استفاده می‌کند که جابه‌جا می‌شوندیا می‌چرخند. روش دیگر آن است که خود الگوریتم را توصیف می‌کند بنابراین به سیستم هماهنگ سازی هیچ گونه حساسیت بیشتری ندارد.
گونه‌های متفاوت: گونه‌های متفاوت بی‌شمار حتی یک الگوریتم اصلی PSOاحتمال دارد. برای مثال، در این‌جا روش‌های مختلفی وجود دارد که ذرات و سرعت‌ها را به راه می‌اندازد (برای مثال در عوض شروع با سرعت صفر)، چگونه از سرعت می‌کاهد، و بعد از اینکه تمام انبوه بروز درآمده است piوgبروز در می‌آید. بعضی از این انتخاب‌ها و تاثیر احتمالی عملکرد آنها در مقاله بحث و گفتگو شده‌است. گونه‌های متفاوت PSOجدید و مناسب‌تر همچنین پیوسته در تلاشی معرفی می‌شوند تا عملکردبهینه سازی را بهبود بخشند. در این‌جا گرایش‌های خاصی در پژوهش وجود دارد، یک گرایش است که با استفاده از PSOمرکب با بهینه‌سازهای دیگر از روش بهینه‌سازی ترکیبی استفاده می‌کند، گرایش پژوهشی دیگر است که سعی می‌کند از میزان همگرایی زودرس جلوگیری کند (که کسادی بهینه‌سازی است) برای مثال با معکوس کردن یا آشفتگی حرکت ذراتPSO، روش دیگر که با همگرایی زودرس روبرواست از انبوه‌های چندگانه استفاده می‌کند (بهینه‌سازی چند ذره) و سپس در تنظیم پارامترهای رفتاری PSOدر طی بهینه‌سازی تلاش می‌شود.
آسان سازی:مکتب فکری دیگر همین PSOاست که باید تا حد ممکن بدون تضعیف عملکرد آن ساده شود، یک مفهوم کلی که اغلب به تیغ اوکام(Occum)اشاره دارد. کی نری در ابتدا ساده‌سازی PSOرا پیشنهاد داد و بیشتربه طور گسترده بر روی آن مطالعه کرده‌است، در حالیکه به نظر می‌رسد عملکرد بهینه سازیاصلاح شد و پارامترها آسان‌تر تدوین می‌شوند و آنها به‌طور منسجم‌تر در بین مسایل مختلف بهینه‌سازی عمل می‌کنند. روش دیگر در رابطه با ساده‌سازی psoهمین متاهیوریستیک است که فقط خاصیت خود را به‌طور تجربی با انجام آزمایش‌های محاسباتی بر روی تعداد محدودی از مسایل بهینه‌سازی نشان داده‌است. این به معنای آن است یک متاهیوریستیک همچون psoتواند صحیح و دقیق اثبات شود و این موجب افزایش خطر اشتباه در شرح و انجام آن باشد. نمونه صحیح این گونه‌های متفاوت الگوریتم تکوینی (الگوریتم ژنتیک:متاهیوریستیک قابل قبول دیگر) را نمایش داد اما بعدا معلوم گردیدکه ناقص باشد بر همین اساس در جستجوی بهینه‌سازی آن به سوی مقادیر مشابه برای ابعاد مختلف در فضای جستجو پیش داوری می‌شود، که به نظر رسید بهترین مسایل benchmarkباشد که ملاحظه می‌شود. این پیش داوری به خاطر خطای برنامه‌ریزی است و هماکنون ثابت گردیده‌است. شروع سرعت‌ها ممکن است نیاز به ورودی‌های فوق‌العاده‌ای داشته باشد. یک نوع مشابه بهینه‌سازی انبوه ذره شتاب یافته (APSO)استنیازی نیست اصلا از سرعت استفاده کند و می‌تواند در بسیاری موارد کاربردی موجب تسریع همگرایی شود. یک کد نمایشی ساده ازAPSOموجود است.
بهینه‌سازی چند منظوره:PSO همچنین برای مسایل چندمنظوره‌ای انجام شده‌است که در مقایسه تابع هدف هنگام حرکت ذرات PSOسلطه پیدا می‌کند و راه حل‌هایی که در سلطه نیستند برای همینمنظور تقریبی حوزه پاریتو ذخیره‌سازی می‌شوند.
PSOترکیبی، مجزا، دوتایی:همان‌طور که معادلات PSOدر کار بالا با اعداد و ارقام واقعی داده شدند، یک روش معمول به کار رفته برای حل مسایل مجزا آن است تا فضای جستجوی جداگانه تا محدوده پیوسته نقشه‌کشی شود، یک PSOکلاسیک اجرا شود و سپس نتیجه از حالت نقشه‌کشی خارج می‌شود. چنین نقشه‌کشی می‌تواند خیلی ساده (برای مثال فقط با استفاده از مقادیر گرد شده) یا مناسب‌تر باشد. به هر حال می‌توان یادآور شد که معادلات حرکت از اپراتورهایی استفاده می‌کنند که چهار عمل را انجام می‌دهند:
محاسبه تفاوتدو موقعیت.نتیجه سرعت است (دقیقا یک جابجایی)
چندگانه بودن سرعت به وسیله ضریب عددی
اضافه کردن دو سرعت
اجرای سرعت به موقعیت
معمولا یک موقعیت و سرعت به وسیله nشماره واقعی نمایش داده می‌شوند و این اپراتورها به راحتی –و+و*و دوباره+هستند. اما تمام این اهداف محاسباتی می‌توانند به شیوه کاملا متفاوت تعیین شوند تا از پس مسایل باینری (دوتایی) یا به‌طور کلی‌تر مسایل جداگانهیا حتی مسایل ترکیبی برآیند. یک روش آن است که اپراتورها بر اساس سری‌ها دوباره تعیین شوند. همچنین
هوش انبوه
بهینه‌سازی چند ذره‌ای
الگوریتم زنبورها/الگوریتم ساختگی مستعمره زنبور
فیلتر ذره را ملاحظه کنید