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

امروزه تعداد زیادی از مسائل بهینه سازی دردنیای ما وجود دارد که به روش دقیق قابل حل نیستند. چنین مسائلی را مسئله NP کامل می گویند. روشهای بهینه یابی موجود برای حل مسائل NP کامل بطور عمده شامل تعداد زیادی متغیر و محدودیت می باشند که از کارایی عملی آنها در حل مسائل با ابعاد واقعی می کاهد. یکی از مسائل NP کامل که زمینه های کاربردی بسیاری در دنیای واقع دارد مسئله فروشنده دورگرد Travelling Salesman Problem)) می باشد که از مسائل بسیار مهم در تئوری گراف ها است. اکثر مسائلی که می توان آن ها را با مسئله فروشنده دورگرد مدل کرد دارای مقیاس خیلی بزرگ هستند. بطوری که الگوریتم های موجود قادر به حل آن ها در یک زمان قابل قبول نیستند. در حال حاضر بهترین روش برای حل این نوع مسائل استفاده از الگوریتم های فرا ابتکاری بعنوان ابزار جستجو می باشد. در این مقاله مسئله فروشنده دوره گرد با استفاده از الگوریتم کرم شب تاب بهبود یافته حل و نتایج ان با نتایج حاصل از چند الگوریتم بهینه سازی دیگر مقایسه شده است. نتایج حاصل از این مقاله بیانگر توانایی کارایی الگوریتم پیشنهادی در بهینه یابی مساله فروشنده دوره گرد می باشد

کلیدواژه ها:

فروشنده دوره گرد ، الگوریتم کرم شب تاب ، مسئله NP-Hard ، جهشK-Opt