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

در این مقاله به حل مسئله فروشنده دوره گرد با استفاده از الگوریتمهای بهینه سازی انبوه ذرات و ژنتیک پرداخته شده است. الگوریتم بهینه سازی انبوه ذرات یک الگوریتم پیوسته میباشد و مسئله فروشنده دوره گرد به طور ذاتی یک مسئله گسسته می باشد. با توسعه الگوریتم بهینه سازی انبوه ذرات این مسئله سریعتر به جواب بهینه همگرا میشود و در مدت زمان کمتری جواب بهینه را می یابد. در این مطالعه الگوریتم بهینه سازی انبوه ذرات با انجام اصلاحاتی به حالت گسسته تعمیم داده شده است. مسئله فروشنده دوره گرد توسط دو الگوریتم بهینه سازی انبوه ذرات گسسته و ژنتیک پیاده سازی شده است، تا کوتاهترین دور مسیر با گذر از تمام شهرها بدست آید. ۳۱ مرکز استان ایران به عنوان شهرهای مسئله درنظر گرفته شده است و در نهایت نتایج بدست آمده از الگوریتم بهینه سازی انبوه ذرات تعمیم یافته با الگوریتم ژنتیک مقایسه و ارزیابی شده است. طبق نتایج الگوریتم بهینه سازی انبوه ذرات در تعداد اجرا و زمان کمتری همگرا میشود. همچنین الگوریتم بهینه سازی انبوه ذرات تعمیم یافته جواب بهتری را نسبت به الگوریتم ژنتیک در نهایت پیدا میکند. الگوریتم بهینه سازی انبوه ذرات تعمیم یافته با مقدار تابع بهینگی ۷۰,۶۵۹ و الگوریتم ژنتیک با مقدار تابع بهینگی ۷۳,۱۶۱۵ میباشد؛ این مقدار بیانگر طول مسیر یافت شده توسط دو الگوریتم است که هدف کمینه کردن مقدار تابع بهینگی میباشد؛ و الگوریتم بهینه سازی انبوه ذرات تعمیم یافته عملکرد بهتری برای کمینه کردن مقدار تابع بهینگی نسبت به الگوریتم ژنتیک داشته است.

کلیدواژه ها:

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