موضوع مقاله: روش بهینه‌سازی ازدحام ذرات | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # روش بهینه‌سازی ازدحام ذرات | مقدمه: در اینچنین فضایی، فرضیاتی مطرح می‌شود و یک سرعت ابتدایی به آن‌ها اختصاص داده می‌شود، همچنین کانال‌های ارتباطی بین ذرات در نظر گرفته می‌شود. | ## بخش 1: روش بهینه‌سازی ازدحام ذرات | سپس این ذرات در فضای پاسخ حرکت می‌کنند و نتایج حاصله بر مبنای یک «ملاک شایستگی» پس از هر بازهٔ زمانی محاسبه می‌شود. با گذشت زمان، ذرات به سمت ذراتی که دارای ملاک شایستگی بالاتری هستند و در گروه ارتباطی یکسانی قرار دارند که در این راسستا شتاب می‌گیرند. علی‌رغم اینکه هر روش در محدوده‌ای از مسائل به خوبی کار می‌کند، این روش در حل مسائل بهینه‌سازی پیوسته موفقیت بسیاری از خود نشان داده‌است. انواع الگوریتم ازدحام ذرات الگوریتم ازدحام ذرات پیوسته مقدمه الگوریتم PSO یک الگوریتم جستجوی جمعی است که از روی رفتار اجتماعی دسته‌های پرندگان مدل شده‌است. در ابتدا این الگوریتم به منظور کشف الگوهای حاکم بر پرواز هم‌زمان پرندگان و تغییر ناگهانی مسیر آن‌ها و تغییر شکل بهینهٔ دسته به کار گرفته شد. تغییر مکان ذرات در فضای جستجو تحت تأثیر تجربه و دانش خودشان و همسایگانشان است؛ بنابراین موقعیت دیگر توده ذرات روی چگونگی جستجوی یک ذره اثر می‌گذارد. نتیجهٔ مدل‌سازی این رفتار اجتماعی فرایند جستجویی است که ذرات به سمت نواحی موفق میل می‌کنند. ذرات از یکدیگر می‌آموزند و بر مبنای دانش بدست آمده به سمت بهترین همسایگان خود می‌روند اساس کار PSO بر این اصل استوار است که در هر لحظه هر ذره مکان خود را در فضای جستجو با توجه به بهترین مکانی که تاکنون در آن قرار گرفته‌است و بهترین مکانی که در کل همسایگی‌اش وجود دارد، تنظیم می‌کند. راه حل یک مسأله یک فرد در نظر گرفته می‌شود، یک انسانی که بال دارد و می‌تواند پرواز کند. یک انسان بال‌دار که در فضای مسئله، فضایی که در آن کلی راه‌حل وجود دارد از راه‌حل خوب خوب هست تا راه‌حل بد بد می‌تواند پرواز کند. هوش جمعی هوش جمعی خاصیتی است سیستماتیک که در این سیستم، عامل‌ها به‌طور محلی با هم همکاری می‌نمایند و رفتار جمعی تمام عامل‌ها باعث یک همگرایی در نقطهای نزدیک به جواب بهینه سراسری می‌شود نقطه قوت این الگوریتم‌ها عدم نیاز آن‌ها به یک کنترل سراسری می‌باشد. هر ذره) عامل) در این الگوریتم‌ها خود مختاری نسبی دارد که می‌تواند در سراسر فضای جواب‌ها حرکت کند و می‌بایست با سایر ذرات (عامل‌ها) همکاری داشته باشد. دو الگوریتم مشهور هوش جمعی، بهینه‌سازی لانه مورچگان و بهینه‌سازی توده ذرات می‌باشند. اولین الگوریتم ازدحام ذرات در سال ۱۹۹۵ ابرهارت و کندی برای اولین بار PSO به عنوان یک روش جستجوی غیر قطعی برای بهینه‌سازی تابعی مطرح گشت این الگوریتم از حرکت دسته جمعی پرندگانی که به دنبال غذا می‌باشند، الهام گرفته شده‌است. هر راه حل که به آن یک ذره گفته می‌شود، PSO در الگوریتم معادل یک پرنده در الگوریتم حرکت جمعی پرندگان می‌باشد. هر چه ذره در فضای جستجو به هدف (غذا در مدل حرکت پرندگان) نزدیکتر باشد، شایستگی بیشتری دارد. هر ذره با دنبال کردن ذرات بهینه در حالت فعلی، به حرکت خود در فضای مسئله ادامه می‌دهد. | ## بخش 2: روش بهینه‌سازی ازدحام ذرات | به ا ین شکل است که گروهٔ از ذرات در آغاز کار به صورت تصادفی به وجود می‌آیند و با به روز کردن نسل‌ها سعی در یافتن راه‌حل بهینه می‌نمایند. موقعیت مذکور شناخته و نگهداری می‌شود که این بهترین مقدار نوستالژی آن ذره نیز گفته می‌شود که آن را با pbest نمایش می‌دهیم. بهترین مقدار دیگری که توسط الگوریتم مورد استفاده قرار می‌گیرد، بهترین موقعیتی است که تاکنون توسط جمعیت ذرات بدست آمده‌است که آن را gbest می‌گوییم (هوش جمعی). پس از یافتن بهترین مقادیر، سرعت و مکان هر ذره با استفاده از رابطه ۶ و ۷به روز می‌شود. رابطه 6 رابطه 7 سمت راست معادله ۶ از سه قسمت تشکیل شده‌است که قسمت اول، سرعت فعلی ذره است و قسمت‌های دوم و سوم میزان تغییر سرعت ذره و جهت آن به سمت بهترین تجربه شخصی (نوستالژی) و بهترین تجربه گروه (هوش جمعی) را به عهده دارند. اگر قسمت اول را در این معادله در نظر نگیریم ، آنگاه سرعت ذرات تنها با توجه به موقعیت فعلی و بهترین تجربه ذره و بهترین تجربه جمع تعیین می‌شود و عملاً تأثیر سرعت کنونی و لختی آن حذف می‌شود. به این ترتیب، بهترین ذره گروه، در جای خود ثابت می‌ماند و سایرین به سمت آن ذره حرکت می‌کنند. در واقع حرکت دسته جمعی ذرات بدون قسمت اول معادله ۶، پروسه ای خواهد بود که طی آن فضای جستجو به تدریج کوچک می‌شود و جستجویی محلی حول بهترین ذره شکل می‌گیرد. در مقابل اگر فقط قسمت اول معادله ۶ را در نظر بگیریم، ذرات راه عادی خود را می‌روند تا به دیواره محدوده برسند و به نوعی جستجویی سراسری را انجام می‌دهند. پارامترهای c1 و c2 (مقدار آن حدود ۲ است) میزان اهمیت و وزن هوش جمعی و نوستالژی را مشخص می‌کنند. پارامتر با صفر قرار دادن یا ندادن پارامترهای c1 و c2 سه حالت مختلف زیر به وجود می‌آید: هیچ‌کدام از این دو پارامتر را صفر نگذاریم که می‌شود pso با لختی سرعت، هوش جمعی و نوستالژی. به این صورت که می‌گوییم اگر ۸۰ درصد ذرات در فاصل‌های کمتر از ۲۰ درصد بیشترین فاصله نسبت به بهترین جواب قرار داشتند، الگوریتم باید متوقف شود. همان‌طور که گفته شد یک مقدار بین ۰ و ۱ است و همین‌طور F بیشترین فاصله بین دو ذره در حالت کنونی است. رابطه 10 مشکل اساسی اولین الگوریتم ازدحام ذرات یک مشکل اساسی فرمول ارائه شده برای الگوریتم ازدحام ذرات اولیه اینست که دائماً سرعت افزایش می‌یابد و هیچ برنامه‌ای برای کاهش آن ارائه نشده‌است، درصورتیکه لازم است هر چه به بهینه سراسری نزدیک می‌شویم سرعت کمتر شود تا ذره ما از بهینه سراسری عبور نکند. استفاده از سرعت بیشینه برشی در این روش برای جلوگیری از زیاد شدن بیش از اندازه سرعت، یک سرعت بیشینه تعریف می‌شود تا هرگاه سرعت به بیش از آن رسید برش داده شود. استفاده از سرعت بیشینه تانژانت هایپربولیکی در این روش از یک تابع تانژانت هیپربولیک برای محدود کردن سرعت به یک مقدار خاص استفاده می‌شود. تفاوت این حالت با حالت برشی اینست که در این حالت تابع ما مشتق پذیر در همهٔ نقاط است درحالیکه در حالت برشی مشتق پذیری از بین می‌رود. | ## بخش 3: روش بهینه‌سازی ازدحام ذرات | در حالت برشی در نقطه برش مشتق پذیری از بین می‌رود؛ ولی در تانژانت هیپربولیک این مشکل وجود ندارد. استفاده از ضریب کاهنده سرعت در این روش از یک ضریب که باید بین ۰ و ۱ باشد، استفاده می‌شود. روش چهارم: در این روش براساس مقدار شایستگی تغییر می‌کند که این روش مناسب تری از روش‌های بالا است. روش پنجم: در این روش که جدیدترین روش است یک پارامتر X خی که در کل سرعت ضرب می‌شود. ۲۰ ۲۱+ , ۲۲; k ∈[۰٬۱] استفاده از تابعی برحسب تکرار برای سرعت بیشینه در این روش سعی می‌شود تا از یک سرعت بیشینه به صورت تابعی از تکرار استفاده شود. [null 13] این قابلیت باعث می‌شود که سرعت بیشینه با توجه به نیاز ما برای تنظیم وزن کاوش و انتفاع در هر تکرار مربوطه تعیین شود. الگوریتم ازدحام ذرات آسنکرون الگوریتم ازدحام ذرات گفته شده نوع سنکرون بود، یک نوع دیگری از این الگوریتم وجود دارد که به آن آسنکرون گویند. در این حالت پس از محاسبه شایستگی هریک از ذرات اگر بهینه سراسری عوض شد بلافاصله به‌روزرسانی می‌شود. این کار باعث می‌شود که سرعت همگرایی تا حدودی افزایش یابد؛ ولی امکان پیاده‌سازی موازی را می‌گیرد. الگوریتم ازدحام ذرات تمام آگاه ذرات با اطلاع هم و با هماهنگی حرکت می‌کنند و یک ذره حرکت بقیه را نیز در حرکت خودش دخالت می‌دهد. در این حالت طبق رابطه هر ذره کاملاً کورکورانه بردار حرکت سایر ذرات را مد نظر قرار می‌دهد و با گرفتن برآیندی از جهت و اندازه حرکت همه، جهت و اندازه خود را بدست می‌آورد. الگوریتم ازدحام ذرات استخوان خالی این الگوریتم نسبت به الگوریتم‌های قبلی خیلی سریع تر همگرا می‌شود و دارای دو نسخه است که در نسخه اول سرعت به شیوه زیر محاسبه می‌شود. نسخه اول: ۲۴ ۲۵ ۲۶ نسخه دوم: در این حالت در نیمی از حالات از روش استخوان خالی و در نیمی از الگوریتم ازدحام ذرات معمول استفاده می‌شود. ۲۷ الگوریتم ازدحام ذرات پیش کشیدن و پس زدن در این الگوریتم ذره به سمت بهینه سراسری جذب می‌شود وقتی که به مقدار آستانه اول برسد، دفع می‌شود تا به جستجوی بیشتری بپردازد و این دفع شدن تا جایی ادامه پیدا می‌کند که به آستانه دوم برسد. [null 32] [null 33] الگوریتم ازدحام ذرات شکار و شکارچی هنگامی که ذرات همگرا شوند یک پارامتر ترس اعمال می‌کنیم با احتمال که باعث دور شدن ذرات از بهینه سراسری می‌شود و در نتیجه جستجو بیشتر می‌شود. جمع‌بندی الگوریتم ازدحام ذرات دودویی الگوریتم ازدحام ذرات دودویی یکی از الگوریتم‌هایی است که برای مسائل جایگذاری یا عدم جایگذاری استفاده می‌شود. جهت پیاده سازی و برای انجام این کار باید از یک نگاشت برای تبدیل از پیوسته به دودویی استفاده شود. | ## جمع‌بندی | ۳۶ ۳۷ الگوریتم ازدحام ذرات جایگشتی برای مطالعه بیشتر الگوریتم پرندگان یا اجتماع ذرات چیست؟