ترکیب موثر الگوریتم نمونه مورچگان و الگوریتم ژنتیکت برای مساله چندین فروشنده دوره گرد

مسیله چندین فروشنده دوره گرد یکی از مهمترین گسترش های مساله فروشنده دوره گرد است، که برخلاف این مساله کمتر مورد توجه قرار گرفته است. در این مساله چندین فروشنده دوره گرد از یک گره خاص به نام نبار شروع به حرکت کرده و بعد از ملاقات کردن بقیه گرهها به گره مربوطه بازمیگردند. هدف یافتن مسیری برای هر فروشنده دوره گرد است بطوریکه هر گره فقط و تنها فقط بوسیله یک فروشنده مورد ملاقات قرار گیرد : هزینه کل مینیمم گردد. در این مقاله ترکیبی از الگوریتم های نمونه مورچگان و ژنتیک برای حل مساله ارایه شده است، که در آن ابتدا روش نمونه مورچگان برای یافتن جواب های شدنی با کیفیت استفاده می شود و سپس الگوریتم ژنتیک برای بهبود بیشتر جواب ها بکار گرفته می شود. این ترکیب سبب میشود که نقاط قوت هر الگوریتم مورد استفاده قرار گیرد و الگوریتم تا حل امکان از بهینه های محلی فرار کند و به جواب های با کیفیت تری دست یابد. مقایسه این الگوریتم با روش های نمونه مورچگان و ژنتیک کارایی الگوریتم را اثبات می کند.

Keywords:

الگوریتم مورچگان , الگوریتم ژنتیک , مسیله چندین فروشنده دوره گرد , مسایل NP-سخت