روش‌های ابتکاری (جستجوی تصادفی)

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

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

برای روش‌های ابتکاری نمی‌توان تعریفی جامع ارائه کرد. با وجود  این، در  اینجا کوشش می‌شود تعریفی تا حد امکان مناسب برای آن عنوان شود: روش جستجوی ابتکاری، روشی است که می‌تواند جوابی خوب (نزدیک به بهینه) در زمانی محدود برای یک مسأله ارائه کند. هیچ تضمینی برای بهینه بودن جواب وجود ندارد و متأسفانه نمی‌توان میزان نزدیکی جواب به دست آمده به جواب بهینه را تعیین کرد.

Heuristic

Metaheuristic

Random Method

روش های فرا ابتکاری

  یکی از روش­های حل مسائل بهینه سازی و به خصوص مسائل بهینه سازی ترکیبی، استفاده از الگوریتم های فراابتکاری است. به طور کلی الگوریتم های فراابتکاری را این گونه می­توان تعریف کرد:

«الگوریتم­های فراابتکاری، روش­های حلی هستند که بین- های بهبود محلی و استراتژی­ های سطح بالاتر، جهت ایجاد فرآیندی که قابلیت فرار از بهینه محلی و اجرای یک جستجوی پایدار را داشته باشد، هماهنگی ایجاد می­ کنند». [49]

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

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

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

Robust

الگوریتم شبیه سازی تبریدی (SA)

الگوریتم تبرید شبیه‌سازی شده (SA)، یک الگوریتم بهینه‌سازی فراابتکاری ساده و اثربخش در حل مسائل بهینه‌سازی است. منشأ الگوریتم تبرید شبیه‌سازی شده، کارهای کریک پاتریک و کرنی و همکارانشان در سال‌های ۱۹۸۳ و ۱۹۸۵ است. کریک پاتریک و همکارانش، متخصصانی در زمینه فیزیک آماری بودند. آنها برای حل مسائل سخت بهینه‌سازی، روشی مبتنی بر تکنیک تبرید تدریجی پیشنهاد نمودند. تکنیک تبرید تدریجی، به وسیله متالورژیست‌ها برای رسیدن به حالتی که در آن ماده جامد، به خوبی مرتب و انرژی آن کمینه شده باشد، استفاده می‌شود. این تکنیک شامل قرار دادن ماده در دمای بالا و سپس کم کردن تدریجی این دماست. الگوریتم تبرید شبیه‌سازی شده  به علت تشابهش و الگو گیری آن از مکانیک آماری و فرایند پخت فلزات که در آن کریستال یک جامد حرارت داده و به آرامی سرد می­ شود تا بهترین شکل جایابی بلوری را پیدا کند، به این نام شناخته می­ شود. روش بهینه سازی SA به این ترتیب است که با شروع از یک جواب اولیه تصادفی برای متغیرهای تصمیم‌گیری، جواب جدید در مجاورت جواب قبلی با بهره گرفتن از یک ساختار همسایگی مناسب به طور تصادفی تولید می‌شود. بنابراین، یکی از مسائل مهم در SA روش تولید همسایگی است. الگوریتم در هر گام، دو مقدار را برای پاسخ­ها به دست می­دهد (پاسخ فعلی و پاسخ انتخابی جدید) و آنها را با هم مقایسه می­ کند. پاسخ­های بهتر همیشه پذیرفته ­شود، اما پاسخهای بدتر با احتمالی برای فرار از بهینه محلی پذیرفته می­شوند.

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

SAبا یک پاسخ اولیه  شروع می­ کند. سپس یک پاسخ همسایه  تولید می­ کند. جواب  که همسایه  است، بر اساس احتمال زیر پذیرفته می­ شود.

Simulated Annealing

Kirkpatrick

Cerny

الگوریتم جستجوی ممنوعه (TS)

جستجوی ممنوع (TS) در سال 1986 توسط فرد گلاور به عنوان یک الگوریتم فراابتکاری برای حل مسائل بهینه سازی ترکیبی معرفی شد [52]. TS در اصل روشی بود که برای فائق آمدن بر ضعف روش­های جستجوی محلی (LS) و الگوریتم های ابتکاری طراحی شد و می­توان آن را به نوعی ادامه و تعمیم الگوریتم­های LS به شمار آورد[53] . پایه­ای ترین و مهم ترین مفاهیم TS شامل دو عنصر «فضای جستجو»و «ساختار همسایگی» می­ شود.

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

با این اوصاف می­توان گفت که برای یک مسئله خاص این قابلیت وجود دارد که چندین ساختار همسایگی داشته باشیم (هر ساختار همسایگی متناظر با یک نوع حرکت یا تغییر  برروی پاسخ های شدنی است). معروف ترین حرکاتی که در TS به کار می رود و به کمک آن ها ساختار همسایگی تعریف می شود شامل «قرار دادن» و «جابجایی» است. در حرکت قرار دادن، یکی از عناصر پاسخ انتخاب و در جایی بین باقی عناصر قرار می گیرد و به این شکل یک پاسخ جدید ساخته می شود. در جابه جایی، مکان قرار گرفتن دو عنصر در پاسخ فعلی با یکدیگر تعویض می شود.

یکی دیگر از نکاتی که TS را از LS متمایز می­ کند، «لیست حرکت های غیر مجاز» (TL) است. TL در واقع یک آرایه با طول مشخص  است که در آن تمام  حرکت اخیری که در جریان جستجو انجام شده اند ذخیره شده است و در صورت تکراری بودن یک حرکت (وجود آن در TL) از انجام آن جلوگیری می­ شود. در صورتی که حرکت تکراری نباشد، پس از انجام آن، حرکت انجام شده وارد TL می­ شود و اولین حرکتی که در TL وجود دارد از لیست خارج    می­ شود. از TL با عنوان «حافظه کوتاه مدت» نیز یاد می­ شود. عناصر یا حرکت هایی که در TL ذخیره شده اند تا انجام تعداد مشخصی از حرکات (طول TL) قابلیت بازیابی و انجام مجدد ندارند مگر اینکه انجام آنها به مقدار قابل توجهی و به اندازه یک معیار از پیش تعیین شده تابع هدف را بهبود دهد. در واقع ما تنها در صورتی که معیار پیش گفته دیده شد می­توانیم یکی از عناصر TL را مورد استفاده قرار دهیم. این معیار با عنوان Aspiration Criteria شناخته می­ شود.

علاوه بر حافظه کوتاه مدت، دو نوع حافظه «میان مدت» و «بلند مدت» نیز در TS کاربرد دارد. این دو نوع حافظه در جریان جستجو این امکان را فراهم می­آورند که پاسخ­های بهتر امکان بیشتری جهت بروز داشته باشند و به همین نسبت پاسخ­های بدتر تاثیر کمتری در فرایند جستجو داشته باشند.

به طور کلی چهار چوب TS را به شکل زیر می ­وان نشان داد. (  مقدار فعلی،  بهترین پاسخ شناخته شده،  مقدار تابع هدف به ازای ،  همسایگی  و  مقدار غیر تابو یا اجازه داده شده توسط Aspiration Criteria است.)

Tabu Search

Local Search

Search Space

Neighborhood Structure

Insertion

Swap

Tabu List

Short Term Memory

Medium Term Memory

Long Term Memory

الگوریتم جستجوی پرندگان (PSO)

روش بهینه سازی جستجوی پرندگان (PSO) بر مبنای الگوی رفتار جمعی حیوانات کار می­ کند. این الگوریتم برای اولین بار در سال 1995 توسط کندی و ابرهارت معرفی شد. هر پاسخ شدنی در این الگوریتم به مثابه یک عضو از جامعه پرندگان (حیوانات) است که اطلاعات محدودی مانند سرعت نزدیکترین همسایه اش و وضعیت خود دارد و مجموعه این اعضا رفتار مشخصی را در شرایط مختلف مانند، هنگامیکه یک خطر آنها را تهدید می­ کند از خود بروز می­دهد. به طور مثال، هنگام حمله یک کوسه به دسته­ای از ماهی­ها می­توان مشاهده کرد که آنها به دو دسته تقسیم می­شوند و پس از رفع خطر به حالت اولیه باز می­گردند.

به طور خلاصه هر کدام از افراد، اطلاعات محلی که شامل جایابی نزدیکترین همسایه اش است و توسط او قابل دسترسی است را برای تصمیم گیری در مورد مکان خودش بکار می­برد.

در این الگوریتم هر ذره  توسط پارامتر وضعیتش که با  و یک بردار ، که بردار سرعت آن است، نشان داده می شود. در هر گام حرکت ذره به کمک معادله زیر :

تبیین می­ شود. هسته اصلی روش شامل روشی است که طبق آن v_i بعد از هر گام انتخاب می­ شود. به روز رسانی موقعیت ذرات بستگی به جهت حرکت، سرعت، بهترین پاسخ بدست آمده در مرحله قبل و مناسب ترین موقعیت میان همسایگان دارد.

2-6. مروری بر الگوریتم حل

   هدف اصلی روش‌های هوشمند به کار گرفته شده در هوش مصنوعی، یافتن پاسخ بهینه مسائل مهندسی است. بعنوان مثال اینکه چگونه یک موتور را طراحی کنیم تا بهترین بازدهی را داشته باشد یا چگونه بازوهای یک ربات را متحرک کنیم تا کوتاه‌ترین مسیر را تا مقصد طی کند (دقت کنید که در صورت وجود مانع یافتن کوتاه‌ترین مسیر دیگر به سادگی کشیدن یک خط راست بین مبدأ و مقصد نیست) همگی مسائل بهینه‌سازی هستند.

روش‌ها و الگوریتم‌های بهینه‌سازی به دو دسته الگوریتم های دقیق و الگوریتم‌های تقریبی تقسیم‌بندی می‌شوند. الگوریتم‌های دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه سازی سخت کارایی ندارند و زمان حل آنها در این مسائل به صورت نمایی افزایش می‌یابد. الگوریتم‌های تقریبی قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینه‌سازی سخت هستند. الگوریتم‌های تقریبی نیز به سه دسته الگوریتم‌های ابتکاری (heuristic) و فراابتکاری (meta-heuristic) و فوق ابتکاری (hyper heuristic) بخش بندی می شوند. دو مشکل اصلی الگوریتم‌های ابتکاری، قرار گرفتن آنها در بهینه‌های محلی،          و ناتوانی آنها برای کاربرد در مسائل گوناگون است. الگوریتم‌های فراابتکاری برای حل این مشکلات الگوریتم‌های ابتکاری ارائه شده‌اند. در واقع الگوریتم‌های فراابتکاری، یکی از انواع الگوریتم‌های بهینه‌سازی تقریبی هستند که دارای راهکارهای برون رفت از بهینه محلی می‌باشند و قابل کاربرد در طیف گسترده ای از مسائل هستند.

Particle Swarm Optimization