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

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

 

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

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

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

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

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

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

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

 

جستجوی آشوب

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

تکرار آشوب:

در این مقاله تابع آشوب لجستیک برای ساختن یک تکامل تفاضلی آشوبناک به شکل زیر استفاده شده است:

که  برابراست با k امین نسل و  ، j امین متغیر آشوب می باشد. وقتی  باشد تابع آشوب در وضعیت آشوب کامل قرار می گیرد.شکل 1 ویژگی ergodic و توزیع احتمال وقتی تابع لجستیک برابر  و Iteration=1000 می باشد را نشان می دهد. از این شکل می توان برداشت کرد که تکرار آشوب دارای جستجوی با احتمال بالاتر در فیلدهای مرزی دارد که به نوبه خود یک مزیت است همانند یک عملگری عمل می کند که از همگرائی زودرس برخی از نواحی جلوگیری می کند. 

شکل 1: ویژگی ergodic توزیع احتمال برای تابع لجستیک

جستجوی آشوب با استراتژی shrinking:

یک جستجوی محلی معمولاً برای بازسازی تابع هدف بکار برده می شود. با این حال ممکن است باعث همگرائی زودرس شود از این رو نتایج فرآیند ارزیابی کلی در بهینه محلی گیر می افتند. مزیت CLS جلوگیری از همگرائی زودرس در فرآیند جستجو می باشد. برای افزایش ویژگی بهره وری CLS و بازسازی راه حل در فاز بعدی، فضای جستجو را به کمک افزایش تابع ارزیابی ها،  کوچک (Shrink) می کند.

فرمول جستجوی محلی آشوب عبارت است از:

که  یک بردار جدید از فرد  در g امین نسل تولید شده به وسیله جستجوی محلی آشوب می باشد.  به وسیله فرمول زیر تولید می شود:

که در آن  از تکرار آشوب بدست می آید ( از بازه [0,1] به طور تصادفی انتخاب می شود )و سپس در درون فضای جستجو [A,B] از فرد نگاشت می شود. ℷ مقیاس کوچک سازی است که از فرمول زیر بدست می آید:

FEs برابر ارزیابی های تابع فعلی می باشد.  m سرعت کوچک سازی را کنترل می کند. مقدار m بزرگتر باعث می شود سرعت کوچک سازی کمتر شود.

طول جستجو CLS:

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

کنترل پارامترهای DE به روش تطبیقی

در الگوریتم پیشنهادی یک روش تطبیقی پارامتر پیاده سازی شده است. در ابتدا به هر فرد از جمعیت کل به طور مستقل یک F و یک CR در بازه [0,1] اختصاص داده می شود. سپس در هر نسل، درصدی از افراد جمعیت به طور تصادفی مقدار F,CR شان را به ترتیب در بازه  [0.1,0.9],[0,1] تغییر می دهند. در فاز انتخاب، افرادی که پیروز شده اند مقادیر F,CR شان به نسل بعد منتقل می شود.

بهبود DE به کمک CLS:

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

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

با توجه به مباحث مطرح شده در بالا، الگوریتم تکامل تفاضلی و جستجوی محلی آشوب ترکیب شده و الگوریتم جدیدی بنام DECLS توسط نویسندگان ارائه شده است. چهار مرحله این الگوریتم پیشنهادی عبارت است از:

1. مقداردهی اولیه

1.1 اندازه جمعیت NP و حداکثر FE را مقداردهی کن.

1.2 همه افراد  را با F,CR های مستقل در درون فضای جستجو مقدار دهی کن.

1.3تابع f(X) را روی همه افراد ارزیابی کن.

2. مرحله تکرار

2.1 عملگر جهش را براساس معادله 3 اجرا کن و برای F,CR تنظیم کن.

2.2 عملگر تقاطع را براساس معادله 4 اجرا کن.

2.3 عملگر انتخاب را براساس معادله 5 اجرا کن.

3. بکاربردن CLS روی بهترین فرد یا کروموزومی که تاکنون بدست آمده است.
4. اگر به معیار توقف رسیده است بهترین راه حل را چاپ کن در غیر این صورت به مرحله 2 برو.

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

شکل 2: مقایسه میزان همگرائی الگوریتم پیشنهادی با دیگر الگوریتم ها

در شکل 3 میزان مقیاس پذیری الگوریتم پیشنهادی با الگوریتم های دیگر را نشان می دهد که نشان از مقیاس پذیرتر بودن الگوریتم پیشنهادی را دارد.

شکل 3: مقایسه مقیاس پذیری الگوریتم پیشنهادی با دیگر الگوریتم ها

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

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

نتیجه گیری:

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

منابع:

[1]. Dongli Jia , Guoxin Zheng , Muhammad Khurram Khan ,“An effective memeticdifferential evolution algorithm based on chaotic local search”, Information Sciences 181 (2011) 3175–3187,2011.