بهینه‌سازی انبوه ذره
بهینه‌سازی ازدحام ذره (حرکت ذرات) بهینه‌سازی ازدحام ذره:
در علم کامپیوتر، بهینه‌سازی ازدحام ذره (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محدوده‌های پایین‌تر و بالاتر فضای جستجو هستند. Vi,d←???Vi,d+Фprp(pi,d+Xi,d)+ Фgrg(gd-Xi,d) تقسیم‌کننده پارامترهای؟ ،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به خصوص به معنای یک یا دو چیز است، اگر چه اغلب روشن نمی‌شود که تعریف معنادار است و گاهی اوقات به اشتباه تصور می‌شود آنها مشابه هستند. چندین فعالیت در زمینه تحلیل و بررسی محاسباتی همگرایی 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شماره واقعی نمایش داده می‌شوند و این اپراتورها به راحتی –و+و*و دوباره+هستند. اما تمام این اهداف محاسباتی می‌توانند به شیوه کاملاً متفاوت تعیین شوند تا از پس مسایل باینری (دوتایی) [یا به‌طور کلی تر مسایل جداگانه]یا حتی مسایل ترکیبی برآیند. یک روش آن است که اپراتورها بر اساس سری‌ها دوباره تعیین شوند. همچنین