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

SIA: Swarm Intelligence Algorithms

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

 

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

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

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

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

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

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

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

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

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

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

 

معرفی توابع استفاده شده برای مقایسه نتایج:

تابع راستریجین (Rastrigin):

معادله این تابع   f(x)= +  –cos(18x1)-cos(18x2) می باشد. تابع در فضای دو بعدی در بازه (-1,1) دارای مینیمم 2- می باشد. علت اینکه این تابع انتخاب شده است این است که همان طور که در شکل 1 نشان داده شده است دارای مینیمم های محلی زیادی می باشد و برای تست عملکرد الگوریتم ممتیکی جدید و نحوه عملکرد آن برای فرار از بهینه محلی مناسب می باشد.

شکل 1 : تابع راستریجین

تابع گلدپرایس (Goldeprice):

تابع F(x)=(1+(x+y+2)2.(19-14x+3x2-14y+6xy+3y2))(30+(2x-3y)2(18-32x+12x2+48y-36xy+27y2 نشان دهنده گلدپرایس می باشد. این تابع در بازه (-2,2) دارای مقدار 3 می باشد.

تابع Exponential :

این تابع در بازه (-1,1) برای ابعاد 2,4,16,32,64  دارای مینیمم صفر می باشد.

همان طور که در شکل 2 نشان داده شده است الگوریتم کرم شب تاب روی تابع Rastrigin اعمال شده است که در نسل بیست و پنجم در بهینه محلی گیر افتاده است. ولی همان طور که در شکل 3 نشان داده شده است در بکارگیری الگوریتم ممتیکی کرم شب تاب و تئوری آشوب در نسل بیست و پنجم باعث یافتن بهینه سراسری شده است.

شکل 2 : الگوریتم کرم شب تاب برای حل تابع Rastrigin