بخشی از مقاله
مروری بر الگوریتمهای فراابتکاری و بررسی قابلیتهای آنها
چکیده
یک الگوریتم بهینهسازی فراابتکاری، یک روش ابتکاری است که میتواند با تغییرهایی کم برای مسائل مختلف بهینهسازی به کار رود. الگوریتمهای فراابتکاری، به طور قابل ملاحظهای توانایی یافتن جوابهای با کیفیت بالا را برای مسائل بهینهسازی سخت، افزایش میدهد. ویژگی مشترک این الگوریتمها، استفاده از مکانیزمهای خروج از بهینهسازی محلی است. الگوریتمهای فراابتکاری، به دو گروه کلی، به دو گروه روشهای مبتنی بر یک جواب و مبتنی بر جمعیت تقسیم میشوند. الگوریتم-های مبتنی بر یک جواب، در حین فرایند جستجو، یک جواب را تغییر میدهند، در حالی که الگوریتمهای مبتنی بر جمعیت، در حین جستجو، یک جمعیت از جوابها را در نظر میگیرند. الگوریتمهای مبتنی بر یک جواب، بر روی مناطق محلی جستجو تمرکز دارند؛ در مقابل، الگوریتم-های مبتنی بر جمعیت، میتوانند جستجو را به طور همزمان در مناطق مختلفی از فضای جواب انجام دهند.
در این مقاله بـه مروری بر انواع الگوریتمهای بهینهسازی فراابتکاری پرداخته است. آنچه کـه در این مقاله آمده، توضیحات کلی درباره انواع الگوریتمهای فراابتکاری می باشد. و بـه برخی کاربردهای آن نیز اشاره شده است.
کلمات کلیدی:
الگوریتمهای فرا ابتکاری، الگوریتمهای مبتنی بر جواب، الگوریتمهای مبتنی بر جمعیت
1
مقدمه
مهندسان و تصمیمگیرندگان، با مسائلی روبرو هستند که پیچیدگی آنها روزبهروز افزایش پیدا میکند. این مسائل در زمینههای مختلفی نظیر تحقیق در عملیات، طراحی سیستمهای مکانیکی، پردازش تصویر و الکترونیک ایجاد میشوند. در تمامی این زمینهها، میتوان مساله را به صورت یک مساله بهینهسازی بیان کرد. در مسائل بهینه-سازی، یک یا چند تابع هدف تعریف میشود که باید در عین حال که تمامی پارامترها مورد توجه قرار می-گیرند، کمینه یا بیشینه شود.
روشهای ابتکاری و فراابتکاری از روشهـای تقریبی در بهینهسـازی ترکیبی میبـاشند. الگوریتمهـای ابتکاری، معمولا به دنبال رسیدن به جوابهای خوب، یعنی جوابهای نزدیک بـه بهینه، در زمـان محاسباتی قابـل قبول هستند ولی قـادر بـه تضمین بهینهبودن جوابهای بـه دست آمده نیستند.[2] یکی از عیبهای الگوریتمهـای ابتکاری، تولید یک جواب یـا تعداد محدودی از جوابها و توقف آنها در بهینهی محلی بـا کیفیت پایین است. الگوریتمهای فراابتکاری، بـرای حل این مشکلات و عیبهای روشهـای ابتکاری پیشنهاد شدهاند. الگوریتم-های فراابتکاری، بـا معرفی اصـول سیستماتیک برای خـارجشدن از بهینههـای محلی یا جلوگیری از قـرارگرفتن در بهینههای محلی با این مشکل برخورد میکنند. ویژگی مشترک الگوریتمهای فراابتکاری، استفاده از مکانیزمهای خروج از بهینهی محلی است.
الگوریتمهای فراابتکاری:
یک الگوریتم فراابتکاری، یک چارچوب الگوریتمی است که میتواند با تغییرهایی کم، برای مسائل بهینهسازی مختلف به کار رود. استفاده از الگوریتمهای فراابتکاری، بهطور قابل ملاحظهای توانایی یافتن جوابهای با کیفیت بالا را برای مسائل بهینهسازی ترکیبی افزایش میدهد. بهعبارت دیگر، یک الگوریتم فراابتکاری یک روش ابتکاری است که قادر به جستجوی فضای جواب، برای یافتن جوابهای با کیفیت بالاست. هدف مشترک تمامی الگوریتمهای فراابتکاری، حل مسائل بهینهسازی سخت مشهور هستند.[1]
روشهای فراابتکاری، دارای ویژگیهای زیر هستند:[2]
· این روشها، همگی تا حدودی احتمالی هستند، چنین رویکردی، این امکان را میدهد که از قرار گرفتن الگوریتم در دام بهینهی محلی جلوگیری شود.
· این روشها معمولا برای حل مسائل گسسته ارائه شدهاند، اما امکان کاربرد درمسائل پیوسته را نیز دارند.
· این روشها معمولا از مفاهیم زیستشناسی، رفتارشناسی جانوری و فیزیک الهام گرفته شدهاند.
· یکی از عیبهای مشترک در این روشها، دشواربودن تنظیم و تطبیق پارامترهاست.
2
همانطور که گفته شد، الگوریتمهای فراابتکاری، به دو گروه کلی، الگوریتمهای مبتنیبریک جواب و الگوریتم-های مبتنی بر جمعیت تقسیم میشوند، که به اختصار به تشریح انواع مختلف آنها می پردازیم.
الگوریتمهای مبتنی بر یک جواب
(1-1 الگوریتم تبرید شبیهسازی شده(:(SA
منشا الگوریتم تبرید شبیهسازی شده((SA، کارهای کریک پاتریک و کرنی و همکارانشان در سالهای 1983 و 1985 است[2] و .[3] کریک پاتریک و همکارانش، متخصصانی در زمینهی فیزیک آماری بودند. آنها برای حل مسائل سخت بهینهسازی، روشی مبتنی بر تکنیک تبرید تدریجی پیشنهاد نمودند. تکنیک تبرید تدریجی، به وسیلهی متالوژیستها برای رسیدن به حالتی که در آن ماده جامد، به خوبی مرتب و انرژی آن کمینهشده باشد، استفاده میشود. این تکنیک شامل قراردادن ماده در دمای بالا و سپس کمکردن تدریجی این دماست.[4]
الگوریتم SA، یک الگوریتم احتمالی است، که در آن، مکانیزمی جهت خروج از بهینههای محلی ارائه شده است. مشکل اصلی تبرید شبیهسازی شده، سختبودن تنظیم پارامترهای این الگوریتم، نظیر دمای اولیه و نرخ کاهش دما است؛ همچنین زمان محاسباتی میتواند بسیار مهم باشد، که برای کاهش آن میتوان از پیادهسازی موازی الگوریتم استفاده کرد. از طرف دیگر، تبرید شبیهسازی شده دارای مزیت انعطافپذیری نسبت به تغییر مساله و پیادهسازی ساده است. تبرید شبیهسازی شده کاربردهای فراوانی دارد که برخی از این کاربردها عبارتند از:
مسیریابی: فروشنده دورهگرد-مسیریابی وسیله نقلیه، مکانیابی: جایابی تسهیلات، ساخت و تولید: تولید سلولی - ماشینهای موازی - زمانبندی کارگاهی - زمانبندی پروژه، یادگیری ماشین: دادهکاوی، طراحی: طراحی شبکه
(2-1 جستجوی ﳑنوعه(:(TS
جستجوی ممنوعه((TS، برای اولینبار در سال 1986توسط گلووِر[5] معرفی شد، البته الگوریتمی کـه وی ارائه کرد، برگرفته از ایدههای مطرح شدهی قبلی دردههی 60 بود. رواج و مقبولیت جستجوی ممنوعه، قطعا به دلیل کارهای انجام شده توسط دکتر دیورا در موسسهی صنعتی فدرال سوئیس در اواخر دههی 80 است. کارهای دکتر دیورا در رواج روش ارائه شده توسط گلووِر نقش به سزایی را ایفا کرده است.
3
همچنین، در همین زمان مقایسههایی میان الگوریتم تبرید شبیهسازی شده و جستجوی ممنوعه صورت گرفت. در بسیاری از کاربردها، الگوریتمهای ابتکاری مبتنی بر TS، نتایج اثربخشتری را نشان دادند، که این امر جذابیت TS را در جوامع علمی افزایش داد.[6]
استراتژیهای تقویت و تنوعبخشی، دو جزء بسیار مهم جستجوی ممنوعه هستند. استراتژیهای تقویت، یعنی تعدیل و تغییر قوانین انتخاب همسایه، بـرای جوابهایی کـه دارای کیفیت خوبـی هستند. این استراتژیهـا میتوانند یک بازگشت بـه سمت نواحی جذاب را ایجاد کنند تـا آن مناطق کاملتر جستجو شوند. جستجوی ممنوعه را میتوان بـه طور مستقیم برای بسیاری از انواع مسائل تصمیمگیری بـه کار برد.
کاربردهای جستجوی ممنوعه
جستجوی ممنوعه، به طور قابل ملاحظهای توانایی ما را در حل مسائل عملی افزایش میدهد. کاربردهای کنونی TS در زمینههای برنامهریزی منابع، ارتباطات مخابراتی، طراحی VLSI، تحلیل مالی، زمانبندی، توزیع انرژی، مهندسی مولکولی، لجستیک، دستهبندی الگوها، برنامهریزی تولید، مدیریت مواد زائد، اکتشاف مواد معدنی، تحلیل داروهای طبیعی، حفاظت زیست محیطی و بسیاری از موارد دیگر است.
(3-1 الگوریتم جستجوی محلی تکرارشونده(:(ILS
کیفیت بهینهی محلی بهدستآمده بهوسیلهی یک جستجوی محلی، بستگی به جواب اولیه دارد، بنابراین باتوجه به اینکه ما میتوانیم بهینههای مختلفی تولید کنیم، الگوریتم جستجوی محلی تکرارشونده((ILS، میتواند بهکار برده شود تا کیفیت بهینههای محلی متوالی را بهبود بخشد. این نوع استراتژی، برای اولین بار در مقالهی مارتین و همکارانش در سال 1991ارائه شد[5] و درپژوهشهای افرادی چون لورنکو و همکارانش [7] 2002 و استوتزل [8] 1994گسترش یافت.
در جستجوی محلی چند شروعی(تکرار شونده)، جـواب اولیه همواره بـه صورت تصادفی و مستقل از بهینهی محلی تولید می شود. الگوریتم ILS، جستجوی محلی چند شروعی را به وسیله ایجاد بـههم ریختگی در بهینه-ی محلی به دست آمده و در نظر گرفتن آن به عنوان جواب اولیهی جدید، بهبود میبخشد.[6]
الگوریتمILS، مبتنی بر اصول سادهای است که در بسیاری از الگوریتمهای ابتکاری مورداستفاده قرار گرفته است. در ابتدا، برای پیداکردن یک بهینهی محلی، یک جستجوی محلی بر روی یک جواب اولیه، به کار برده میشود. سپس در هر تکرار، یک بههم ریختگی بر روی بهینهی محلی به دست آمده، انجام میگیرد. در نهایت،
4
یک جستجوی محلی بر روی این جواب به کار برده میشود. جواب تولید شده، تحت شرایطی خاص به عنوان جواب فعلی پذیرفته میشود. این فرآیند ادامه مییابد تا شرط خاتمهی مفروض، تحقیق یابد.
عناصر اصلی زیر، الگوریتم ILS را می سازند:[6]
• جستجوی محلی: در یک الگوریتم ILS، باید یک جستحوی محلی برای یافتن بهینههای محلی مورد استفاده قرار بگیرد.
• روش ایجاد بههم ریختگی: عملگر ایجاد بههم ریختگی، باید یک قسمت از جواب را ثابت نگه داشته و قسمت دیگر را تغییر دهد تا جواب را به بخش جذابتری از فضای حل، حرکت دهد.
• معیار پذیرش: معیار پذیرش شرایطی است که طبق آن یک بهینهی محلی جدید، به عنوان جواب فعلی پذیرفته میشود و طراحی یک ILS، به میزان زیادی به روش ایجاد بههم ریختگی و معیار پذیرش بستگی دارد، بنابراین با توجه به این که چه روشی برای ایجاد بههم ریختگی و معیار پذیرشی انتخاب شود، الگوریتمهای جستجوی محلی مختلفی را میتوان طراحی کرد.
(4-1 الگوریتم جستجوی همسایگی متغیر(:(VNS
الگوریتم جستجوی همسایگی متغیر((VNS، در سال 1997 توسط هانسن و ملادوینوویچ ارائه شد.[9] ایدهی اصلی در VNS، اکتشاف متوالی همسایگیهای از پیش تعیین شده است تا از این طریق، یک جواب بهتر تولید شود. اکتشاف همسایگیها در VNS، به صورت تصادفی یا سیستماتیک صورت میگیرد. VNS، با اکتشاف همسایگیها، به بهینههای محلی مختلف دست یافته و از بهینهی محلی خارج میشود. درواقع، با استفاده از همسایگیهای متفاوت در جستجوی محلی، میتوان بهینههای محلی متفاوتی را تولید کرد. در نتیجه، میتوان امیدداشت که یکی از بهینههای محلی به دست آمده از این روش، بهینهی سراسری باشد. در حقیقت، همسایگی های مختلف، سطوح مختلف جستجو را ایجاد میکنند.[4]
جستجوی همسایگی متغیر، مبتنی بر روش نزولی همسایگی متغیر((VND است. این روش، در واقع یک VNS قطعی است. الگوریتم VND از همسایگیهای متوالی برای رسیدن به یک بهینهی محلی استفاده میکند، به این صورت که ابتدا باید یک مجموعه از ساختارهای همسایگی Nl که در آن O 1'…'Omax است، تعریف شود. Nl ، اولین همسایگی برای ساختن جواب اولیهی x است. اگر هیچ بهبودی در یک جواب x در همسایگی فعلی Nl(x)، امکان پذیر نباشد، آنگاه ساختار همسایگی از Nl به Nl+1 تغییر مییابد. اگر در جواب فعلیx، بهبودی یافت شود، ساختار همسایگی به اولین ساختار Nl(x) باز میگردد تا جستجو را از آن نقطه
5
شروع کند. طراحی الگوریتمVND، به میزان زیادی به انتخاب ساختارهای همسایگی و ترتیب به کارگیری آنها بستگی دارد، همچنین، پیچیدگی همسایگیها، براساس اکتشاف و ارزیابی جوابهای آنها نیز باید مورد توجه قرار گیرد. هرچـه همسایگیها بزرگتر باشند، VND زمـان بیشتری بـرای جستجو صرف میکنـد. یکی از استراتژی رایـج در VND، رتبهبنـدی همسایگیها بـراساس پیچیدگی(اندازهی همسایگی) آنهاست، تـا براسـاس این رتبهبنـدی، ترتیب بـه کارگیـری همسایگیها مشخص شود.[4]
(5-1 الگوریتم جستجوی محلی هدایتشده(:(GLS
الگوریتم جستجوی محلی هدایتشده((GLS، یک الگوریتم مبتنی بر جواب قطعی است. این رویکرد، برای اولین بار توسط وودوریس در سال [6]1995 ارائه شد و در مطالعههای وودوریس و همکارانش در سال [7]1998، گسترش یافت. این الگوریتم، کاربرد زیادی در بهینهسازی ترکیبی داشته است و تبدیل آن برای استفاده در مسایل بهینهسازی پیوسته نیز آسان است. کاربردهای فراوانGLS در مسایل گسسته و پیوسته، آن را تبدیل به یکی از رایجترین الگوریتمهای مبتنی بر جستجوی محلی کرده است. اصول اصلیGLS، براساس تغییر دینامیکی تابع هدف، با توجه به بهینههای محلی تولید شده است. ویژگیهای بهینههای محلی به دست آمده، برای تغییر تابع هدف مورد استفاده قرار میگیرند. با این کار میتوان ساختار سطح جستجو را تغییر داد و از بهینهی محلی خارج شد.[4]
در GLS، یک مجموعه از ویژگی fti;( L 1' … 'P) برای یک جواب تعریف میشود. یک ویژگی از جواب، یک خصوصیت از یک جواب را با توجه به مسالهی در دست حل، تعریف میکند. هزینه Ci به هر ویژگی اختصاص مییابد. هنگامی که الگوریتم به یک بهینهی محلی رسید، الگوریتم با توجه به هر یک از ویژگیها، به جوابها جریمه اختصاص میدهد. به صورتی که برای هر ویژگی i، یک جریمهی Pi اختصاص داده میشود. مقادیر اولیهی تمامی جریمهها صفر است. این جریمهها نشان دهندهی اهمیت ویژگیها هستند. تابع هدف F، متعلق به جواب S، به صورت زیر جریمهدهی میشود:[4]
(s)iIiP F'(s)=F(s) +
که در آن، نشان دهندهی وزنهای اختصاص یافته به جریمههای مختلف و Ii(s) یک تابع مشخصه است که تعیین میکند ویژگی fti در جواب s وجود دارد یا خیر؟
if the feature fti s 1
Ii(s)=
otherwise 0
