مقاله: تکامل تدریجی رفتار در الگوریتم های ممتیک با استفاده از سازگاری در تقلید افراد جامعه

این مقاله در سال 2007 که توسط رامین اعیان زاده و دکتر محمد تشنه لب تدوین شده است در هشتمین کنفرانس سیستم های هوشمند که در دانشگاه فردوسی مشهد برگزار شده، پذیرفته شده است.

در این مقاله معماری جدیدی برای الگوریتم های ممتیک ارائه شده است که نسبت به بقیه ممتیک های دیگر عملکرد بهتری دارد. همچنین در این مقاله روی پایداری روش کار شده است.

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

در معماری جدید برای الگوریتم ممتیک به منظور مدیریت شعاع همسایگی همان طور که در نظریه بالدوینی مطرح شده است نرخ تقلید ثابت نمی باشد و با گذشت زمان می تواند میزان یادگیری و تقلید به یک موضوع به مرور زمان کاهش پیدا کند. بدین منظور در معماری جدید برای الگوریتم ممتیک پیشنهادی  از این مفهوم استفاده کرده و نرخ تقلید متناسب با فرمول زیر با افزایش تعداد تکرارها در هر مرحله این نرخ کاهش می یابد:

در فرمول بالا t شماره نسل فعلی می باشد، T حداکثر نسل های مجاز می باشد، a نرخ کاهش تقلید می باشد.

در شکل 1 منحنی تغییرات نرخ تقلید به ازاء مقادیر مختلف a در الگوریتم های ممتیک نشان داده شده است.

شکل1 : تغییرات نرخ تقلید به ازاء مقادیر مختلف a

در این مقاله به طور تجربی مقدار a=3 در نظر گرفته شده است. برای مقایسه کارائی الگوریتم ممتیک در این مقاله از سه شاخص آماری بهترین جواب از اجراهای متعدد بدست آمده، میانگین 30 بار اجرای الگوریتم و واریانس جواب هایی که در میانگین شرکت کرده اند، استفاده شده است. با توجه به تصادفی بودن الگوریتم های تکاملی بهترین جواب خیلی ملاک مناسبی نمی باشد به همین منظور میانگین جواب ها مناسب تر می باشد. و از شاخص سوم هم برای مقایسه میزان پایداری الگوریتم های مختلف می توان استفاده کرد.

همان طور که در جدول 1 نشان داده شده است نتایج روی یک مسئله Benchmark برای سه روش الگوریتم ژنتیک، الگوریتم ممتیک استاندارد با تپه نوردی(SMA) و الگوریتم ممتیک با جستجوی تپه نوردی و سازگاری تقلید (AMA) مورد مقایسه قرار گرفتند که نتایج حاکی از عملکرد بهتر الگوریتم پیشنهادی از نظر کارائی و پایداری نسبت به دو روش دیگر می باشد.

جدول 1: مقایسه نتایج سه روش الگوریتم ژنتیک،SMA و AMA روی یک مسئله Benchmark

منابع:

[1]. رامین اعیان زاده، محمد تشنه لب،" تکامل تدریجی رفتار در الگوریتم های ممتیک با استفاده از سازگاری در تقلید افراد جامعه "، هشتمین کنفرانس سیستم های هوشمند،دانشگاه فردوسی مشهد،شهریورماه 86.