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

روش‌های فراابتکاری ابزاری قدرتمند برای حل مسائل بهینه‌سازی به شمار می‌روند. حسن این روش‌ها در مقایسه با روش‌های ابتکاری اینست که فضای جواب بهتر مورد جستجو قرار می‌گیرد و احتمال توقف در بهینه‌های موضعی کاهش می‌یابد. این روش‌ها به سه دسته عمده تقسیم می‌شوند: روش‌های فراابتکاری بر اساس جستجوی همسایگی، روش‌های فراابتکاری براساس جستجوی جمعیت، و روش‌های فراابتکاری براساس شبکه‌های عصبی.

الگوریتم‌های جستجوی همسایگی به صورت متناوب اقدام به جستجوی در فضای جواب می‌کنند تا شرط خاتمه رخ دهد. در دهه گذشته تلاش‌های بسیاری در زمینه استفاده از نگرش جستجوی همسایگی برای حل VRP صورت گرفته است و الگوریتم‌های متنوعی ارائه گردیده است.

اولین الگوریتم‌های ارائه شده، الگوریتم شبیه‌سازی ذوب[1] است. استفاده از این الگوریتم در ابتدای دهه 90 بسیار رایج بود. معروفترین روش شبیه‌سازی ذوب توسط عثمان در سال 1993 توسعه یافت. عثمان در الگوریتم خود از الگوریتم ذخیره که توسط کلارک و رایت معرفی شد، برای تولید جواب ‌های اولیه استفاده نمود. این الگوریتم جواب‌های خوبی تولید می‌کرد ولی جواب‌های بدست‌آمده قابل رقابت با جواب‌های حاصله از روش جستجوی ممنوعه[2] که در همان زمان ارائه شده بود نبود. الگوریتم شبیه‌سازی ذوب معین توسط گلدن در سال 1998براساس توسعه الگوریتم پیشنهاد شده توسط دوئک در سال 1993 که براساس روش ابتکاری مسافرت رکورد به رکورد[3] بود، ارائه گردید. تاث و ویگو نیز اقدام به ارائه قوانین برای تعریف عملگرها در روش شبیه‌سازی ذوب نمودند (قصیری،2007) و(ظهره‌وند،2011).

جستجوی ممنوعه از دیگر روش‌های جستجوی همسایگی به شمار می‌رود. ویلارد اولین تلاش‌ها را برای استفاده از روش جستجوی ممنوع برای حل مسائل VRP انجام داد. یکی از موفقترین روش‌های جستجوی ممنوعه در سال 1993 توسط تایلارد ارائه شد. ریگو و روکایرول در سال 1996 با استفاده از زنجیره‌ی خروج یک الگوریتم جستجوی ممنوعه را ارئه دادند. توسعه این روش توسط ژو و کلی در همان سال اتفاق افتاد. روش جستجوی ممنوعه دانه بندی شده[4] (GTS)، قابلیت استحصال جواب بهینه را افزایش داد. این روش توسط تاث و ویگو در سال 2003 مطرح گردید. ایده اصلی این الگوریتم، حذف دائمی یال‌های طولانی که شباهت نزدیک به مجموعه جواب را ندارند، بود (قصیری،2007) و(ظهره‌وند،2011).

روش‌های فراابتکاری بر اساس جستجوی جمعیت با الهام از پدیده‌های طبیعی ایجاد شده و توسعه یافتند. منطق این روش مشتمل بر عناصری نظیر بازآفرینی، پدیده‌های تصادفی، رقابت، و انتخاب است. اولین نوع این روش‌ها، الگوریتم‌های ژنتیک[5] هستند. الگوریتم‌های ژنتیک از پدیده‌های طبیعی الهام گرفته شده‌اند. هالند این الگوریتم را اولین بار معرفی نمود. در سال 2004 پرینس با استفاده از عملگرهای تقاطعی و جهشی، یک الگوریتم کارآمد برای حل مدل CVRP توسعه داد. در الگوریتم مزبور جواب‌ها به صورت تورهای بزرگ در نظر گرفته شده‌اند. برای تولید یک فرزند از دو والد ابتدا یک زنجیره از راه‌ها را به عنوان والد اول و رئوس را به عنوان والد دوم در نظرگرفته شده است. فرزند دوم به همین صورت تولید می‌شود، فقط این عمل با معکوس کردن والد اول و دوم ایجاد می‌شود. با به کارگیری ترکیب‌های مختلف از گره‌ها و یال‌ها، فرزندها (جواب‌ها) بهبود می‌یابند. (ظهره‌وند،2011).

دومین نوع الگوریتم‌های جستجوی جمعیت، بهینه‌سازی مورچگان[6] است.در سال2002 ریمان اولین فرم جامع به کارگیری الگوریتم مورچگان را برای حل مسائل CVRP مطرح نمود. این الگوریتم براساس تبدیل همزمان مکانیزم ایجاد تور که در سال 1964 توسط کلارک و رایت معرفی شده بود به الگوریتم مورچگان رتبه‌دار[7] معروف است. اولین گام این الگوریتم، با ایجاد یک لیست مقادیر جذابیت که به صورت نزولی مرتب شده است، شروع می‌گردد. پس از آن احتمال ملاقات گره  بعد از گره  بر اساس مقادیر جذابیت محاسبه می‌گردد. سپس هر جواب به صورت مجزا برای هر مسیر ایجاد شده توسط مورچه‌ها، با استفاده از 2-opt بهبود می‌یابد. ریمان و همکاران در سال 2004 با توسعه الگوریتمی که خودشان در سال 2002 ارائه نموده بودند، اقدام به ارائه الگوریتمی تحت عنوان D-ant نمودند. شاخص‌ترین ویژگی این الگوریتم، مفهوم تجزیه و غلبه بود که بر اساس آن تفکیک مجموعه تورها به تعداد کوچکتر مجموعه تورها که CVRP مورد نظر را می‌ساخت. سپس هر یک از این مجموعه‌ها با استفاده از الگوریتم اولیه ریمان، قابل حل بود(ظهره‌وند،2011).

آخرین نوع از روش‌های فراابتکاری که در این بخش بررسی خواهد شد شبکه‌های عصبی[8] است. شبکه‌های عصبی از تعامل نورون‌های مصنوعی ایجاد می‌گردد. شبکه‌های مصنوعی عصبی ممکن است برای دریافت درکی از شبکه نورون‌های زیستی، و یا برای حل مسائل هوش مصنوعی بدون نیاز به ایجاد یک مدل از سیستم زیستی حقیقی مورد استفاده قرار گیرند. در حقیقت، سیستم عصبی موجودات زنده بشدت پیچیده است و ممکن است که ویژگی‌های را در برگیرد که بر مبنای درک ما از شبکه‌های عصبی کاملا زاید باشند. در بحث VRP شبکه‌های عصبی بر مبنای یکسری از الگوهای قابل تغییر که در واقع حلقه‌هایی تشکیل دهنده مسیرهایی ممکن وسایل نقلیه، می‌باشند. حلقه‌ها بر رسیدن به رئوس بر مبنای یک روش تصادفی که در آن احتمال تخصیص یک رأس به یک حلقه ناشی از یک فرآیند یادگیرنده است، با یکدیگر رقابت می‌کنند. البته می‌بایست یادآوری کرد که شبکه های عصبی توانایی رقابت با سایر روش‌های ابتکاری VRP را ندارند (رناد و باکتور،2002)

 

.دانلود پایان نامه حل مسئله مسیریابی وسایل نقلیه چند انبار با پنجره زمانی با استفاده از یک الگوریتم فرابتکاری کارآمد

[1] Simulated Annealing

[2] Tabu Search

[3] Record-to-Record Travel Method

[4] Geranular Tabu Search

[5] Genetic Algorithm

[6] Ant Colony

[7] Rank-Based ACO algorithm

[8] Neural Networks