مقاله حل مسئله فروشنده دوره گرد با الگوریتم نوین کلونی مورچه ها

بخشی از مقاله

چکیده

مسأله فروشنده دورهگرد یا Traveling Salesman Problem به اختصارTSP یکی از مسائل بسیار مهم و پرکاربرد در علوم کامپیوتر و تحقیق در عملیات است. بسیاري از فعالیتهاي علمی را میتوان به صورت مسئله فروشنده دورهگرد در آورد و سپس حل نمود به طوریکه این مسئله به یکی از مسائل بسیار مهم در تئوري گراف ها تبدیل شده است. روشهاي بهینهیابی موجود براي حل مسائل سخت همچون مسئله فروشنده دورهگرد بطور عمده شامل تعداد بسیار زیادي متغیر و محدودیت میباشند که از کارایی عملی آنها در حل مسائل با ابعاد واقعی میکاهد. بدین علت در دهههاي اخیراستفاده ازالگوریتمهاي ابتکاري و فوق ابتکاري مورد توجه قرار گرفته است.در این تحقیق از الگوریتم کلونی مورچهها براي کمینه کردن مس یر پیموده شده توسط فروشنده دورهگرد استفاده شده است که تور بهتري را حاصل دهد. پس از طراحی الگوریتم، تنظیم پارامترهاي آن با حل مسائل متعدد صورت گرفته است و نتایج بدست آمده نشان می دهد که این الگوریتم در اغلب مسائل قادر است جواب بهتري بدست آورد.

واژههاي کلیدي: فروشنده دورهگرد، الگوریتمهاي ابتکاري، الگوریتم کلونی مورچگان، بهینهسازي

-1 مقدمه

با گسترش روز افزون جوامع و رشد جمعیت، نیاز به صرفهجویی و یافتن روشهایی براي به حداقل رساندن زمان و هزینه در انجام امور صنعتی، عمرانی و غیره هر روز بیشتر ضرورت پیدا میکند. مساله فروشنده دورهگرد یکی از مسائل مشهور بهینهسازي است که بر اساس آن یک فروشنده دورهگرد میخواهد به N شهر رفته و کالاي خود را به فروش برساند، به طوري که تمام شهرها را رفته، از هر شهر فقط یک بار عبور کرده و در نهایت کمترین مسیر را طی کرده باشد. براي حل اینگونه مسائل میتوان از الگوریتمهاي هوشمند مانند الگوریتم ژنتیک استفاده نمود.
 الگوریتم نوار بندي یکی از الگوریتمهاي بهینه حل مسئله فروشنده دورهگرد است که در سال 1959 توسط بردوود و همکارانش ارائه شد.[1] این الگوریتم به عنوان یک ابزار در مورد رفتار طول تور بهینه معرفی شد.

یکی دیگر از قدیمیترین و کاراترین بررسیها در بکارگیري روش شاخه و کران براي حل مساله فروشنده دورهگرد توسط لیتل و همکارانش در سال 1963 ارائه گردید.[2] این روش بر اساس تمام مسیرهاي فروشنده دورهگرد روي یک درخت شمارش صورت میگیرد. الگوریتم ذخیرهسازي یک برداشت از مساله فروشنده دوره گرد متقارن بوسیله الگوریتم ابتکاري مسیر وسایل نقلیه میباشد که توسط کلارك و همکارش معرفی شد.[3] الگوریتمهاي ابتکاري1، جوابهاي نزدیک به جواب بهینه را در یک زمان قابل قبول یافت می کنند، با این حال، تضمینی براي پیدا شدن بهترین جواب وجود ندارد.[4]از جمله روشهاي مبتنی بر جستجوي ابتکاري میتوان الگوریتم وراثتی2، الگوریتم جمعیت مورچگان3 و الگوریتم ازدحام ذرات4 را نام برد.

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

-2 مروري بر روشهاي بهینهسازي

الف. بهینهسازيفمبتنیفبرفگرادیان

ب. بهینهسازيفهوشمند، کهفخودفشامل،
الگوریتمفژنتیک

الگوریتمفاجتماعفذرات

الگوریتمفکلونیفمورچهفها

الگوریتمفکلونیف زنبورها5

تکاملی فتفاضلی6

-3 مسئله فروشنده دورهگرد

مسئله فروشنده دوره گرد، مسئلهاي معروف است که ابتدا مسائل مربوط به آن توسط ویلیام همیلتون و توماس کرکمن در سده 18 مطرح شد و سپس در دهه 1930 شکل عمومی آن به وسیله ریاضیدانانی مثل کارل منگر از دانشگاه هاروارد و هاسلر ویتنی از دانشگاه پرینستون مورد توجه قرار گرفتل