ارزیابی الگوریتم فراابتکاری سنجاقک (DA) در حل مسئله فروشنده دوره گرد(TSP)

مسئله فروشنده دوره گرد (TSP) به عنوان یک مسئله سخت چند جمله ای غیر قطعی (NP-hard) در نظر گرفته میشود. در مسئله فروشنده دوره گرد، یک فروشنده باید کوتاهترین مسیر بین شهر ها را طی نموده، از همه شهر ها یکبار عبور کرده و سپس به شهر مبدأ برگردد. روش های متفاوتی برای مقابله با این مسئله وجود دارد که متداول ترین روش استفاده از الگوریتم های فراابتکاری است. در این مقاله مسئله فروشنده دوره گرد توسط الگوریتم جدید فراابتکاری سنجاقک حل و بررسی شده است. ایده الگوریتم سنجاقک از هوش جمعی سنجاقکها الهام گرفته شده است . برای ارزیابی کیفیت روش پیشنهادی مقایسه آن با دو الگوریتم ازدحام ذرات و ژنتیک انجام شده است. با توجه به نتایج نهایی روش پیشنهادی سنجاقک برای حل مسئله فروشنده دوره گرد مؤثر گزارش شده و نتایج قابل قبولی نشان میدهد.

کلیدواژه ها:

الگوریتم سنجاقک ، الگوریتم ازدحام ذرات ، الگوریتم ژنتیک ، مسئله فروشنده دوره گرد