میر محمد علیپور

امروزه صنایع فراوانی با مساله پیدا کردن کوتاه ترین مدار هامیلتونی (مساله فروشنده دوره گرد)، درگیر می باشند و با توجه به اینکه این مساله جزو مسائل Complete-NP بوده و راه حل قطعی که تابحال برای آن ارائه شده، دارای مرتبه زمانی نمایی است، بهمین دلیل الگوریتمهای تقریبی متعددی از جمله الگوریتم های مبتنی بر شبکه های عصبی، کولونی مورچه ها، الگوریتم های ژنتیکی و غیره برای حل آن گزارش شده است. در این مقاله با استفاده از اتوماتای یادگیر توزیع شده که یک ابزار جستجوی عمومی بوده و برای حل تعدادی از مسائل Complete-NP بکار برده شده است، یک الگوریتم جدید برای حل مساله فروشنده دورهگرد معرفی خواهیم کرد که کارایی آن را با استفاده از هیوریستیک جستجوی محلی opt-2 افزایش داده ایم و در نهایت کارایی الگوریتم تلفیقی ارائه شده را بر روی نمونه مسائل استاندارد مساله فروشنده دوره گرد بررسی کرده و نتایج بدست آمده را با الگوریتم قبلی که از هیوریستیک opt-2 استفاده نمی نماید و نیز با برخی از الگوریتمهای تقریبی موجود، مقایسه می کنیم. آزمایشهای انجام گرفته نشان میدهد که الگوریتم پیشنهادی در مقایسه با الگوریتمهای بررسی شده از کارایی بهتری بر خوردار است.