بخشی از مقاله
چکیده
در استفاده از الگوریتم استراتژی تکامل جهت براورد نقاط کمینه توابع ریاضی ابتدا یک جمعیت اولیه درفضای چند بعدی مسئله بصورت تصادفی و با شرط ارضای محدودیت های مسئله تولید وبکمک الگوریتم استراتژی تکاملی جواب بهینه تخمین زده میشود . در این پژوهش تعدادی جمعیت اولیه - بیش از یک جمعیت - در فضای مسئله بصورت تصادفی و با شرط ارضای محدودیت ها تولید و تخمین صورت میگیرد.برای بررسی کارایی الگوریتم جدید الگوریتم های دو روش در شبیه ساز متلب شبیه سازی و نتایج حاصل از اجرای آنها در دو بعد تعداد تکرار و زمان اجرا ثبت شد. با استفاده از آزمون آماری داده های جفت شده و بکمک نرم افزار آماری آزمون فرضیه ها صورت گرفت. نتایج حاصل کارایی رویکرد جدید نسبت به الگوریتم قبلی را تایید می کنند.
-1مقدمه
استراتژی تکامل - Evolution Strategy و به اختصار - ES یک روش بهینه سازی بر اساس ایده ی سازگاری و تکامل است که بخشی از الگوریتمهای تکاملی و محاسبات تکاملی به شمار می رود.[4] الگوریتمهای تکاملی بطور کلی برای حل مسائل بهینه سازی استفاده می شوند.این الگوریتم ها براساس مدلهای یک فرایند تکاملی طراحی واجرا میشوند .[1] بیشتر الگوریتم های تکاملی الگوریتم های بیولوژیکی ، مفاهیم انتخاب طبیعی ، جهش وتولید دوباره را پیشهاد میدهند با این حال الگوهای دیگری هم وجود دارند که میتوان از آنها برای خلق الگوریتمهای تکاملی جدید استفاده کرد یا الگوریتمهای قبلی را ارتقا داد.
یکی از ارتقاهای پیشنهاد شده بر روی الگوریتمهای تکاملی ، کاستن از تنظیمات آنهاست . در میان پارامترهایی که باید تنظیم شوند ، پارامترهای عملگرهای بازترکیبی و جهش نیز به چشم میخورند.این تنظیمات عملگرها معمولاَ در روند وفق دادن توجه زیادی میطلبد چرا که مجاری اصلی اکتشاف و وسعت بشمار میروند . ارتقای عملگرهای الگوریتم تکاملی ، کارایی را در هر دو زمینه کیفیت و راه حل پیدا شده با توجه به زمان مصرفی بالا میبرد در ادامه الگوریتمهای بهینه سازی مبتنی بر تکامل معرفی و عملکرد و کارایی رویکرد جدید در استفاده از استراتژی تکاملی و نتایج شبیه سازی آن بیان میشود.
-2 الگوریتم های تکاملی
الگوریتم های تکاملی در مقایسه با سایر الگوریتم های بهینه سازی برتری هایی نسبت به دیگر الگوریتم ها دارند که موجب شده به طور گسترده در مسائل بهینه سازی مورد استفاده قرار گیرند. این الگوریتمها، نیاز به معرفی کامل مسئله ندارند و تنها با داشتن اطلاعات چندی در مورد تعریف مسئله می توانند کار کنند. همچنین محدودیتی درمورد تابع شایستگی ندارند و لزومی ندارد که این تابع مثلاً مشتق پذیر باشد. تکامل در الگوریتم به عنوان فرایند تطبیق بیان می شود. به همین دلیل شایستگی به عنوان هدف اصلی که باید بهینه شود مطرح نیست، بلکه عبارتی است که نیازمندی کل محیط را بیان میکند، هرچه این نیازمندی ها بیشتر ارضا شوند، نتیجه در تعداد بیشتری از اعضای جمعیت خود را نشان می دهد. عمل تکامل باعث میشود که جمعیت با محیط خود بیشتر و بیشتر سازگار شود.
فلوچارت الگوریتم تکاملی
اکثر اجزای فرآیند تکامل اتفاقی هستند. در زمان انتخاب موجوداتی که شرایط مناسب تری1 دارند ، شانس انتخاب بیشتری دارند، گرچه در بیشتر اوقات، موجودات ضعیف تر هم شانس انتخاب شدن و زنده ماندن را دارند. در بسیاری از اوقات موجودات به طور تصادفی برای ترکیب از جمعیت خارج می شوند. این مطلب در مورد تغییرات نیز صدق میکند. ایده کلی از الگوریتم های تکاملی در شکل 1 نشان داده شده است.[8] گونه های مختلفی از الگوریتم های تکاملی وجود دارد، این الگوریتم ها به سه دسته کلی تقسیم می شوند:
1. الگوریتم های ژنتیکی - GA - ارایه شده توسط [10]Holland و مطالعه شده توسط Goldberg[9]
.2 استراتژی های تکاملی - ES - ارایه شده توسط [15] Rechenberg و Schwefel[11]
3. برنامه ریزی تکاملی - - EP ارائه شده توسط [11]L.J. Fogel et. Alواصلاح شده توسط [7]D.B. Fogel در هربک از سه روش بالا اثبات شده است که با داشتن فضای مسئله پیچیده، پیوسته و چند کیفیتی میتوانندبه جواب تقریباً بهینه برسند.
-3الگوریتم های فرا ابتکاری
یکی دیگر از روشهای دسته بندی الگوریتمهایی که در زمینه بهینهیابی ترکیباتی ارائه شده است، دستهبندی آنها به دو گروه الگوریتمهای کامل2 و الگوریتمهای تقریبی3 میباشد. الگوریتمهای کامل، متضمن یافتن یک جواب بهینه در زمان محدود برای همه مصادیق یک مسأله بهینهیابی در اندازه متناهی - محدود - هستند. روشهای تقریبی، عموماً مبتنی بر دو اصل پایهای هستند: تکنیکهای ابتکاری سازنده و روشهای جستجوی محلی ، تکنیکهای ابتکاری سازنده، مربوط به فرایند ساختن جوابهای اولیه قبل از انجام عملیات دیگری است. برخی منابع علمی، تکنیکهای ابتکاری را به دو خانواده ابتکاریهای خاص و فرا ابتکاریهاتقسیم کردهاند.
ابتکاریهای خاص برای حل یک مسأله خاص و یا یک مصداق از آن طراحی میشوند، در حالی که فرا ابتکاریها الگوریتمهای همه منظوره4 هستند که قابل استفاده در تقریباٌ همه مسائل بهینهیابی میباشند.مزیت اصلی استفاده از روشهای فرا ابتکاری، وجود مفروضات محدود در فرموله کردن مدل است، در حالی که این امر در برنامهریزی ریاضی مصداق ندارد. برخی از مسائل بهینهیابی را نمیتوان با نمادهای تحلیلی-ریاضی بدون ابهام فرموله کرد. در واقع، تابع هدف در این موارد، مانند یک جعبه سیاه5 است. در بهینهیابی جعبه سیاه، هیچ قاعده تحلیلی برای هدف وجود ندارد [6] - شکل . - 2
سناریوی جعبه سیاه برای تابع
الگوریتم های فرا ابتکاری بسیاری ارائه شدهاند. این الگوریتم ها کارایی بالاتری برای برخی مسائل دارند و در برخی مسائل با مشکلاتی در زمینه نزدیک شدن به جواب بهینه مواجه میشوند. در حقیقت، با توجه به ساختار مسأله و نوع پیچیدگی آن، یک فرد خبره در زمینه الگوریتمهای فرا ابتکاری، یک الگوریتم را برای حل برمیگزیند و پارامترهای مربوط به آن الگوریتم را با استفاده از روش علمی طراحی آزمایش ها6 یا روش آزمون و خطا تنظیم میکند.
-4 استراتژی های تکاملی
استراتژی تکامل - Evolution Strategy و به اختصار - ES یک روش بهینه سازی بر اساس ایده ی سازگاری و تکامل است که بخشی از الگوریتم های تکاملی و محاسبات تکاملی به شمار می رود.[4]استراتژی های تکاملی ارایه شده توسط Rechenberg، Schwefel از لحاظ تاریخی به منظور حل مسائل بهینه سازی پارامترها تعریف شدند. در نتیجه هر گونه در جمعیت به صورت لیستی از اعداد حقیقی تعریف می شد. علاوه بر این هر گونه شامل یک سری پارامترهای استراتژی نیز بود. این پارامترها برای کنترل رفتار عملگرهای جهش استفاده می شدند. [3]
-5مکانیزم استراتژی تکامل :
در استراتژی تکامل فرد به عنوان یک زوج مرکب بصورت زیر نشان داده میشود[4] - 1 - با توجه به مشاهده بیولوژیکی که فرزندان شبیه به والدهای خود میباشند، و انحراف کوچکتر از پدر و مادر رخ میدهد بیشتر از آنهایی که بزرگتر، فرزندان با اضافه کردن نویز گاوسی به شرح زیر ایجاد شده است. پارامترهای استراتژی بر اساس قانون 1/5 موفقیت توسط Rechenberg پیشنهاد شد ، اگر فراوانی نسبی جهش موفق یک دوره خاص بزرگتر از 1/5 باشد انحراف M افزایش، در غیر این صورت، انحراف کاهش داده میشود.[13] عملگر انتخاب بین والد و فرزند بهترین را انتخاب میکند که در آن تابع برازندگی مقدار کمتری داشته باشد. شبه کد الگوریتم استراتژی تکامل در شکل 3 نشان داده شده است. [4]
همانند برخی دیگر از الگوریتم های تکاملی ES تا زمانی که یکی از شروط خاتمه مسئله برقرار شود، اجرا میشود.در هر دوره از اجرای الگوریتم، فرزند تولید می شوند. اندازه جمعیت بود و معمولاً برابر 6 بود عملگر ترکیب به ازای تولید یک فرزند نیاز به دو والد داشت. همین دو والد برای تولید هر دو بخش فرزند - پارامترهای استراتژیک و متغیرهای شی - مورد استفاده قرار می گرفتند. انتخاب والدها به صورت تصادفی از جمعیت فعلی بود. گونههای مختلفی برای ترکیب وجود دارند ولی بهترین جواب برای نوع ترکیبی بود که متغیرهای شیء فرزند را همه از روی یکی از والدین برداشته و برای پارامترهای استراتژی نیز میانگین پارامترهای استراتژی والدین استفاده شود. [12]
عملگر اصلی در ES، جهش است و روی هر دو بخش گونه اعمال می شود. عملگر جهش ابتدا روی بخش پارامترهای استراتژی اعمال می-شود. بعد از آن متغیرهای شیء با استفاده از نتایجی که از اعمال جهش روی پارامترهای استراتژی حاصل شده است، جهش میکنند. این نوع جهش به ES این قابلیت را می دهد که خود را تطبیق دهد و سعی کند بهترین پارامترهای استراتژی را بدست آورد. [4] انتخاب در ES به طور قطعی انجام می شود. بهترین گونه از بین فرزند انتخاب می شوند. - انتخاب , - یا بهترین گونه از اجتماع دو جمعیت انتخاب می شوند - انتخاب - - - همانند برخی دیگر از الگوریتم های تکاملی ES تا زمانی که یکی از شروط خاتمه مسئله برقرار شود، اجرا می شود.[12]
-6روش جدید برای الگوریتم استراتژی تکامل
در قسمت قبل روندکلی الگوریتم استراتژی تکامل بیان شد در این قسمت روش پیشنهادی جدید برای استفاده از الگوریتم استراتژی تکامل در تخمین نقاط مینیمم توابع بیان میشود. در استفاده از استراتژی تکاملی جهت براورد نقاط کمینه توابع ریاضی ابتدا یک جمعیت درفضای n بعدی مسئله مانند x بصورت تصادفی و با شرط ارضای محدودیت های مسئله تولید میشود وبکمک الگوریتم استراتژی تکاملی جواب بهینه تخمین زده میشود .[13] در این پژوهش تعداد kجمعیت n بعدی در فضای مسئله بصورت تصادفی و با شرط ارضای محدودیت ها تولید میشوند و تخمین صورت میگیرد.
-7روش اجرای ارزیابی رویکرد جدید
برای بررسی کارایی الگوریتم جدید الگوریتمهای دو روش در شبیه ساز matlab شبیه سازی و نتایج حاصل از اجرای آنها در دو بعد تعداد تکرار و زمان اجرا ثبت شد با استفاده از آزمون آماری داده های جفت شده و بکمک نرم افزار spss آزمون فرضیه ها انجام می شود.
