بخشی از مقاله
خلاصه
یکی از اساسیترین مسائل الگوریتمی گراف، مسئله فروشنده دورهگرد - TSP - 2 میباشد. این مسئله یکی از مسائل بهینهسازی ترکیبی سخت است که راهحل محاسباتی برای آنها وجود ندارد و برای آن در زمان چندجملهای ممکن است جوابی قطعی وجود نداشته باشد. هدف از مسأله فروشنده دورهگرد، بهدستآوردن کوتاهترین مسیر بین مجموعهای از شهرها است، بهگونهای که هر شهر، فقط یک بار در مسیر، قرار گرفته و مسیر ساختهشده، به شهر اول، منتهی میشود. در این مقاله به ترکیب دو الگوریتم تکاملی ژنتیک - GA - 3 و کلونی زنبور عسل مصنوعی - ABC - 4، جهت حل مسئله فروشنده دورهگرد پرداخته، آن را با هر یک از الگوریتمهای GA و ABC، مقایسه نمودهایم. نتایج، نشاندهنده برتری روش ترکیبی بهکارگرفته شده است.
.1 مقدمه
مسائل بهینهسازی جزء اصلیترین زمینههای تحقیقاتی در علوم مختلف بهشمار میآید. بسیاری از مسائل بهینهسازی در مهندسی، طبیعتاً پیچیدهتر و مشکلتر از آن هستند که با روشهای مرسوم بهینهسازی نظیر روش برنامهریزی ریاضی و مانند آن قابل حل باشند از اینرو برای حل این دسته مسائل سراغ روشهای هوشمند یا طبیعی میرویم .[1] مسأله فروشنده دورهگرد از n شهر تشکیل شده که بین هر دو شهر آن یک مسیر میتواند وجود داشته باشد و هر کدام از این مسیرها، فاصله یا هزینه مشخص دارد.
در این مسأله که مسأله کوتاهترین مسیر هامیلتونی نیز نام دارد، فروشنده دورهگرد میخواهد از یکی از این شهرها، مسیر خود را شروع کرده و سپس به کلیه شهرها مسافرت کند و از هر یک از شهرها فقط یک بار بگذرد و در نهایت به شهر مبدأ بازگردد. در این مسأله، هدف پیداکردن ترتیبی از شهرهاست که فروشنده دورهگرد از آنها عبور نماید، به نحوی که مجموع مسافت طی شده توسط فروشنده، حداقل شود. مسأله فروشنده دورهگرد، یکی از مسائل سخت1 میباشد که بسیار مهم و پرکاربرد در علوم کامپیوتر و تحقیق در عملیات بهشمار میرود. سه روش کلی برای کدکردن راهحلهای این مسأله در الگوریتمهای مختلف ارائه شده است که عبارتند از:
الف - نمایش جواب بهصورت رشته گسسته جایگشتی
ب - نمایش جواب بهصورت کلیدهای تصادفی
ج - نمایش جواب بهصورت ماتریسهای شبه فرومون در این مقاله قصد داریم با استفاده از ترکیب الگوریتمهای GA و ABC به حل مسأله کوتاهترین مسیر هامیلتونی2 یا فروشنده دورهگرد بپردازیم.
.2 الگوریتم زنبور عسل مصنوعی - ABC -
الگوریتم زنبور عسل مصنوعی یکی از جدیدترین الگوریتمهای بهینهسازی3 است و شبیهسازی رفتار جستجوی غذای گروههای زنبور عسل است .[2] این الگوریتم در سال 2005 توسط کارابوگا و باشتورک 4 مطرح شد [3] که آن را برای حل مسائل بهینهسازی بهکار بردند. یک کلونی زنبور عسل شامل سه گروه از زنبورها است: زنبورهای کارگر5 ، ناظر6 و پیشاهنگ 7 که در ابتدا یک جمعیت تصادفی از آنها در کلونی توزیع میشود.
[4] موقعیت هر منبع غذایی، یک راهحل ممکن از فضای مسأله را نشان میدهد و مقدار شهد هر منبع غذایی، کیفیت و شایستگی راهحل یافتشده را مشخص میسازد و تعداد زنبورهای کارگر در کندو برابر با تعداد منابع غذایی اطراف کندو یا همان تعداد راهحلها است. بهطورکلی قطعه زمینهای گلدار با میزان شهد فراوان، باید توسط زنبورهای بیشتری ملاقات شوند، درحالیکه قطعه زمینهای گلدار با شهد کمتر باید زنبورهای کمتری را دریافت کنند. مراحل کلی این الگوریتم در زیر بیان شده است:
- 1 انتخاب راهحل اولیه توسط زنبورهای کارگر: در مرحله آغازین زنبورهای موجود در کلونی به دو دسته تقسیم میشوند: زنبورهای کارگر و زنبورهای ناظر. زنبورهای کارگر ابتدا بدون هیچگونه شناختی از فضای اطراف کندو شروع به جستجو نموده و راهحلهای اولیه را تصادفی انتخاب مینمایند و هر منبع غذایی و موقعیت مکانی آن را در حافظه خود نگه میدارند.
- 2 ارزیابی راهحلهای اولیه و انتخاب زنبورهای پیشاهنگ: پس از اتمام فرآیند جستجو زنبورهای کارگر به کندو باز گشته و اطلاعات خود را درباره کیفیت منابع غذایی با زنبورهای مراقب به اشتراک میگذارند. زنبورهای ناظر در نقش تابع هدف هستند که کیفیت شهد منابعی که زنبوران کارگر یافتهاند را ارزیابی مینمایند.
