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

یکی از مسائل مهم در تئوری گرافها مساله فروشنده دوره گردی می باشد که یک مساله NP-COMPLETE است اکثر مسائلی که می توان آنها را با مساله فروشنده دوره گرد مدل کرد دارای مقیاس خیلی بزرگ هستند که الگوریتمهای موجود قادر به حل آنها در یک زمان قابل قبول نیستند الگوریتم رقابت استعماری و الگوریتم ژنتیک هر دو از الگوریتم های تکاملی هستند که برای حل مسائل NP-COMPLETE به کاربرده می شوند دراین مقاله یک روش ترکیبی از الگوریتم ژنتیک و الگوریتم رقابت استعماری برای حل مسئله فروشنده دوره گرد درمقیاس بزرگ پیشنهاد شده است دراین روش ابتدا مساله اصلی را به چند خوشه با مقیاس کوچک تقسیم کرده و سپس هریک از خوشه ها را از طریق الگوریتم ژنتیک حل می کنیم هر خوشه یک گره اصلی استعمارگر و تعداد گره عضو مستعمره داردکه گره اصلی مناسبترین عضو برای هر خوشه می باشد سپس خوشه ها برای تصاحب گره های فرعی با همدیگر رقابت می کنندو د رنهایت خوشه ای که ضعیف تر است به صورت تدریجی گره های فرعی خود را از دست خواهد داد و حذف خواهند شد و خوشه های قویتر با جذب این گره ها بر قدرت خود خواهند افزود و درنهایت یک خوشه واحد بوجود خواهد امد که گره اصلی مناسبترین جواب مساله خواهد شد نشان داده شده است که با استفاده ازا ین روش در مقیاسهای بزرگ سرعت رسیدن به جواب افزایش پیدا می کند.

کلیدواژه ها:

الگوریتم ژنتیک ، الگوریتم رقابت استعماری ، خوشه بندی ، مساله فروشنده دوره گرد