X
تبلیغات
وکیل جرایم سایبری

SIA: Swarm Intelligence Algorithms

مقاله: بهینه سازی ازدحام ذرات ممتیکی (Memetic-PSO)

مقاله: بهینه سازی ازدحام ذرات ممتیکی (Memetic-PSO)

این مقاله توسط  Y.G. Petalas · K.E. Parsopoulos · M.N. Vrahatis  در سال 2007 در Springer به چاپ رسیده است. در این مقاله یک بهینه سازی ازدحام ذرات ممتیکی پیشنهاد شده است که ترکیبی از الگوریتم های جستجوی محلی با الگوریتم بهینه سازی ازدحام ذرات استاندارد می باشد. به همین دلیل یک روش بهینه سازی کارآمد و موثر خواهد بود که البته از نظر عملی مورد تحلیل قرار می گیرد.

کارائی الگوریتم های مبتنی بر جمعیت وابسته به قابلیت جستجوی سراسری (Exploration) به خوبی جستجوی محلی بهبود یافته (Exploitation) در فضای جستجو می باشد. تعادل در این دو ویژگی باعث افزایش کارائی می شود. در نوع سراسری PSO ، همه ذرات به وسیله بهترین موقعیت سراسری جذب می شوند. و نسبت به نقاط خاص همگرا می شوند. بنابراین این نوع از PSOبه بهره برداری روی اکتشاف اهمیت می دهد. از سوی دیگر، در نوع محلی PSO ، اطلاعات بهترین موقعیت هر همسایه به آرامی به ذرات دیگر جمعیت از طریق همسایگانشان فرستاده می شود. بنابراین، احتمال اینکه به بهترین موقعیت خاصی جذب شود ضعیف تر می باشد.از این طریق از گیر افتادن در بهینه محلی جلوگیری می شود. بنابراین، نوع PSO محلی به اکتشاف (Exploration) روی بهره برداری  (Exploitation) اهمیت می دهد.

انتخاب مناسب اندازه همسایگی روی تعادل بین بهره برداری و اکتشاف تاثیر می گذارد. که این مقدار یک مسئله باز می باشد و براساس تجربه مقدار دهی می شود.

در PSO مقدار دهی اولیه برای اندازه جمعیت (ازدحام) و سرعت به طور تصادفی انجام می شود. 

 

در برخی از انواع PSO به منظور عملکرد بهتر در جستجوی های محلی شان عملگرهای شان را تغییر و بهبود می دهند. ضعف در این بخش از الگوریتم PSO استاندارد باعث می شود که در این مقاله این الگوریتم به شکل ممتیکی ارائه شود. که در آن الگوریتم بهینه سازی ازدحام ذرات با الگوریتم های جستجوی محلی ترکیب می شوند.

الگوریتم ممتیک:

شبه کد الگوریتم های ممتیکی در شکل 1 آورده شده است. که در آن علاوه بر عملگرهای ترکیب جدید و جهش حستجوهای محلی نیز دخالت داده شده است.

شکل 1: شبه کد الگوریتم های ممتیکی

 

الگوریتم پیشنهادی در مقاله:

از جمله از طرح های مختلف بهینه سازی ازدحام ذرات ممتیکی عبارت است از:

طرح 1: جستجوی محلی روی بهترین موقعیت سراسری جمعیت بکابرده شود که pgنامیده می شود که منظور از g اندیسی است که نشان دهنده بهترین ذره می باشد.

طرح 2: برای هر بهترین موقعیت piکه i=1,2,..,N می باشد یک عدد تصادفی r تولید شده که اگر r<Ɛو جائی که Ɛ>0  به عنوان آستانه تعیین شده است آنگاه جستجوی محلی روی pi بکار برده می شود.

طرح 3-1:جستجوی محلی هم روی بهترین موقعیت pgبرای کل جمعیت بکاربرده می شود و هم روی بهترین موقعیت تصادفی انتخاب شده یعنی pi که i є {1,2,…,N} می باشد.

طرح 3-2:جستجوی محلی هم روی بهترین موقعیت pg برای کل جمعیت بکاربرده می شود و هم رویبهترین موقعیت تصادفی انتخاب شده یعنی pi که i є {1,2,…,N} می باشد بطوری که |pg-pi|> c Δ (s) که c є (0,1) و Δ (s) قطر (diameter) فضای جستجوی S می باشد.

هر کدام از این سه طرح می توانند با هم در هر تکرار یا در کل تکرار های الگوریتم مورد استفاده قرار گیرد.

شبه کد الگوریتم پیشنهادی در شکل 2 آورده شده است.

شکل2: شبه کد الگوریتم پیشنهادی MPSO

در ادامه مقاله به اثبات همگرائی طرح الگوریتم MPSO پرداخته شده است که در آن فرض بر این است که که روش جستجوی محلی تصادفی روی بهترین ذره جمعیت در هر تکرار الگوریتم بکاربرده شود.

تحلیل و مقایسه نتایج الگوریتم پیشنهادی:

در جدول 1 مقایسه نتایج بین الگوریتم های RWMPSOg,RWMPSOl,PSOg,PSOl نشان داده شده است. منظور از الگوریتم RWDE(Random Walk Direction Exploitation ) گام های تصادفی با جهت گیری بهره وری می باشد که به عنوان جستجوی محلی می تواند در کنار PSO استفاده شود که در آن صورت با RWMPSO نشان داده می شود. که خود این الگوریتم هم بر دو نوع سراسری RWMPSOg  و نوع محلی RWMPSOl تقسیم می شود. همچنین PSO های سراسری و محلی به ترتیب با PSOg و PSOl نشان داده شده اند.

در این جدول مقادیر min,max,mean نشان دهنده کمترین وماکزیمم و میانگین برازندگی می باشد. همچنین StD و Suc به ترتیب نشان دهنده انحراف معیار و تعداد موفقیت می باشد. یک جواب موفق است اگر مینیمم سراسری آن با دقت 10-6  اتفاق بی افتد.

جدول 1: مقایسه نتایج الگوریتم پیشنهادی و الگوریتم های دیگر برای مسائل مختلف Benchmark

نتایج حاکی از عملکرد بهتر الگوریتم پیشنهادی نسبت به الگوریتم های دیگر برای حل مسائل Benchmark می باشد. هر دو نوع پیشنهادی نوع محلی و سراسری PSO با انواع مختلف PSO مورد مقایسه قرار گرفته است. تقریباً در همه الگوریتم های ممتیکی روی مسائل مختلف بهبود کارائی و اثربخشی را نشان می دهد.

[1].  Y.G. Petalas · K.E. Parsopoulos · M.N. Vrahatis, “  Memetic particle swarm optimization”, springer, DOI 10.1007/s10479-007-0224-y, August 2007.

مقاله: یک الگوریتم ممتیک تکاملی تفاضلی موثر مبتنی بر جستجوی محلی آشوب

 

این مقاله توسط دنگلی و همکارانش در سال 2011 در Information Sciences چاپ گردیده است. این مقاله یک الگوریتم تکامل تفاضلی (DE) موثر ممتیکی بنام DECLS پیشنهاد داده است. که در آن جستجوی محلی آشوب را به همراه استراتژی Shrinking  بکار برده است. جستجوی محلی آشوب روی کاندیدهای تکامل تفاضلی روی یک فضای جستجوی بزرگ اعمال می شود تا باعث افزایش اکتشاف در الگوریتم شده و از همگرائی زودرس جلوگیری کند. همچنین با اعمال روی نواحی کوچک باعث افزایش بهره وری راه حل الگوریتم می شود. با تنظیم پارامترهای DECLS می توان قابلیت جستجو را افزایش داد. برای ارزیابی نتایج از 20 تابع Benchmark استفاده شده و با روش های پیشرفته تکامل تفاضلی دیگر مقایسه شده است که نتایج حاکی از عملکرد بهتر روش پیشنهادی نسبت به بقیه روش ها می باشد. همچنین الگوریتم پیشنهادی برای حل مسائل با ابعاد بزرگ نتایج امیدوارکننده ای از خود نشان داده است. در ادامه به بررسی موارد مطرح شده در بالا پرداخته می شود. در ادامه به هر یک از موارد مطرح شده در بالا پرداخته می شود.

الگوریتم تکامل تفاضلی استاندارد (DE):

در تکامل تفاضلی استاندارد، هر فرد یک راه حل f(x) در فضای جستجو را ارائه می دهد. در هر نسل، تابع هدف برای هر فرد ارزیابی می شود. مقدار شایستگی بدست آمده، برای تشخیص کیفیت افراد بکار برده می شود. و بهترین عضو  که در طول فرآیند بهینه سازی ساخته می شود، به منظور حفظ مسیر پیشرفت برجسته می شود. تکامل تفاضلی شامل مراحل زیر می باشد:

  1. جمعیت اولیه: افراد در الگوریتم تکامل تفاضلی از فرمول زیر بدست می آیند:

که در آن  نشان دهنده j امین پارامتر کاندید فرد i در نسل g ام برای تابع هدف f(x) می باشد.NP اندازه جمعیت می باشد. D ابعاد تابع هدف می باشد. همه افراد به صورت تصادفی با توزیع احتمال یکنواخت مقدار دهی اولیه می شوند.

  1. جهش: اولین تفاوت تکامل تفاضلی با الگوریتم ژنتیک در عملگر جهش می باشد. که ساده ترین روش جهش در الگوریتم تکامل تفاضلی برای هر فرد در بردار  ، تکامل تفاضلی یک بردار جهش یافته  را براساس افرادی که به طور تصادفی انتخاب شده اند، تولید می کند.
  2. تقاطع: در تقاطع بردار فرزند کاندید، به وسیله فرمول زیر تولید می شود:

که  یک پارامتری از فرزند کاندید  می باشد. و  یک پارامتری از  می باشد. CR فاکتور تقاطع نامیده می شود که در بازه [0,1] محدود شده است. دو طرح متفاوت از تقاطع به نام های نمائی (Exponential) و دو جمله ای (Binomial) وجود دارد. تفاوت بین آنها در روش چگونگی تولید بردار    می باشد. در تکامل تفاضلی استاندارد مقدار CR ثابتی برای همه افراد تخصیص داده می شود. در الگوریتم های تکامل تفاضلی، CR با فرآیند ارزیابی تغییر می کند.

  1. انتخاب: فرزند کاندید    با فرد قدیمی  براساس شایستگی یشان رقابت می کنند. فرد پیروز می خواهد شانسی برای زنده ماندن در نسل بعد را داشته باشد. این رقابت در فرمول زیر محاسبه شده است.

 

جستجوی آشوب

یکی از ویژگی های سیستم های آشوب، در عین بی نظمی منظم بودنشان می باشد. و در واقع در نهایت یک جواب قطعی ارائه می دهد. این ویژگی باعث می شود که بتوان برای ساخت عملگر جستجو برای توابع هدف بهینه سازی از آن استفاده نمود. از طرفی بهینه سازی آشوب برای فضای جستجوی کوچک به خوبی کار می کند ولی برای فضای جستجوی بزرگ زمان جستجو طولانی و غیرقابل قبول می باشد. بنابراین جستجوی آشوب با دیگر جستجوهای سراسری مانند الگوریتم ژنتیک یا بهینه سازی ازدحام ذرات برای افزایش قابلیت جستجو ترکیب می شود. 

ادامه مطلب

مقاله: الگوریتم ممتیک مبتنی بر کرم شب تاب و تئوری آشوب

 

این مقاله توسط مرضیه کامران پور، دکتر مهدی یعقوبی، دکتر پیمان کشاورزیان تدوین شده و در سال 1391 در یازدهمین کىفرانس سیستم های هوشمند ایران پذیرفته شده است.

به منظور گیر نه افتادن در بهینه محلی و همچنین پایداری بهتر نتایج در الگوریتم های هوش جمعی مانند کرم شب تاب از الگوریتم ممتیک کرم شب تاب و مفهوم تئوری آشوب استفاده نموده است. به منظور بررسی و مقایسه نتایج از توابعی که بهینه محلی زیادی دارند مانند تابع Rastrigin,Goldeprice,Exponential استفاده شده است. نتایج حاکی از عملکرد بهتر الگوریتم ممتیکی پیشنهادی نسبت به الگوریتم کرم شب تاب تنها می باشد. در ادامه به تشریح هر کدام از موارد مطرح شده پرداخته شده است.

الگوریتم کرم شب تاب:

این الگوریتم برای اولین بار توسط یانگ در سال 2008 مطرح شده است. این الگوریتم از ویژگی نور چشمک زن کرم شب تاب الهام گرفته است. در الگوریتم برای سادگی سه قانون زیر در نظر گرفته می شود:

  • همه کرم شب تاب ها تک جنسیتی می باشند و یک شب پره بدون در نظر گرفتن جنسیت جذب کر شب پره دیگر می شود.
  • جاذبه متناسب با درخشش است. و اگر هیچ نوری نباشد شب پره به صورت تصادفی حرکت می کند.
  • درخشندگی یک کرم شب تاب یا ساختگی است یا توسط تابع هدف ایجاد می گردد.

در الگوریتم کرم شب تاب دو مسئله برای فرمول سازی آن وجود دارد:

  1. تفاوت در شدت نور: این کار به وسیله فرمول I(r)=Is/r2 که در آن Is شدت نور در منبع و r فاصله بین دو کرم شب تاب i,j می باشد.
  2. فرموله کردن میزان جاذبه:  

از فرمول بالا برای حرکت کرم شب تاب i به سمت کرم شب تاب قوی تر j را نشان می دهد که در آن بخش اول فرمول نشان دهنده فاصله بین دو کرم شب تاب می باشد، بخش دوم فرمول نشان دهنده میزان جذب و بخش سوم میزان رندوم سازی با پارامتر  می باشد.

الگوریتم ممتیک و تئوری آشوب:

الگوریتم های هوش جمعی مانند کرم شب تاب معمولاً در بهینه محلی گیر می افتند. برای حل این مشکل از الگوریتم ممتیک استفاده می کنند. در الگوریتم های ممتیکی از جستجوی محلی سنتی مانند تپه نوردی، شبیه سازی تبرید یا جستجوی ممنوعه استفاده می شود. که در این مقاله برای یافتن جستجوی محلی به منظور افزایش کارائی از تئوری آشوب استفاده کرده است. در جستجوی محلی های سنتی یک شعاع همسایگی از نقطه فعلی در نظر گرفته می شود و بهترین همسایه جایگزین می گردد. که این شعاع همسایگی به دلیل اینکه فقط همسایگان نقطه فعلی هستند چندان تغییری از نظر بهینگی ندارند و در واقع میزان تنوع جواب ها در یک همسایگی کمتر است. تئوری آشوب با بکارگیری همسایگان با تنوع بیشتر و انتخاب کلی تر از فضای جستجو باعث می گردد نقاط بهینه بهتر برای جایگزینی با نقطه فعلی انتخاب شوند. این تئوری صرفاً به استفاده از همسایگان از نظر فاصله و مسافت اکتفا نکرده و به کمک نگاشت لجستیک همسایگانی با تنوع بیشتر را برای کاندید شدن برای جایگزینی با نقطه فعلی انتخاب می کند. این تنوع در نگاشت لجستیک ناشی از ضریب لجستیک می باشد که باعث اثر پروانه ای می شود.  

ادامه مطلب
1 2 >>