یک روش مبتنی بر خوشه بندی با ترکیب الگوریتم ژنتیک و الگوریتم رقابت استعماری برای حل مسئله فروشنده دوره گرد با مقیاس بزرگ
چکیده
یکی از مسائل مهم در تئوری گراف‌ها مساله فروشنده دوره گرد می‌باشد که یک مساله NP-COMPLETE است اکثر مسائلی که می‌توان آن‌ها را با مساله فروشنده دوره گرد مدل کرد دارای مقیاس خیلی بزرگ هستند که الگوریتم‌های موجود قادر به حل آن‌ها در یک زمان قابل قبول نیستند. الگوریتم رقابت استعماری و الگوریتم ژنتیک هر دو از الگوریتم‌های تکاملی هستند که برای حل مسائل NP-COMPLETE به کار برده می‌شوند. در این مقاله یک روش ترکیبی از الگوریتم ژنتیک و الگوریتم رقابت استعماری برای حل مساله فروشنده دوره گرد در مقیاس بزرگ پیشنهاد شده است. در این روش ابتدا مساله اصلی را به چند خوشه با مقیاس کوچک تقسیم کرده و سپس هر یک از خوشه‌ها را از طریق الگوریتم ژنتیک حل می‌کنیم. هر خوشه یک گره اصلی (استعمارگر) و تعدادی گره عضو (مستعمره) دارد که گره اصلی مناسب‌ترین عضو برای هر خوشه می‌باشد. سپس خوشه‌ها برای تصاحب گره‌های فرعی با همدیگر رقابت می‌کنند و در نهایت خوشه‌ای که ضعیف‌تر است به صورت تدریجی گره‌های فرعی خود را از دست خواهد داد و حذف خواهند شد و خوشه‌های قوی‌تر با جذب این گره‌ها بر قدرت خود خواهند افزود و در نهایت یک خوشه واحد بوجود خواهد آمد که گره اصلی مناسب‌ترین جواب مساله خواهد شد. نشان داده شده است که با استفاده از این روش در مقیاس‌های بزرگ، سرعت رسیدن به جواب افزایش پیدا می‌کند.
نویسنده : محمد صادق گرشاسبی، مریم گرشاسبی
تعداد صفحه : 5
مشخصات فایل : 437KB / PDF
قیمت : رایگان
