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

بهینه سازی مسأله ی فروشنده ی دوره گردTSP)چون با مسأله ی یافتن کوتاه ترین دور همیلتنی در گراف متناظر مرتبط می گردد، ازنوع NP-HARD می باشد. از این رو، حل آن با روش های بهینه سازی دقیق نظیر برنامه ریزی خطی یا شاخه و کران، به لحاظ زمانی، فقط در مورد اندازه های کوچک مقرون به صرفه است. برای حل مسائل با اندازه های بزرگ، به دلیل طولانی بودن راه حل های دقیق، یا در برخی موارد غیرممکن بودن به کارگیری آن ها، راه حل های ابتکاری و فراابتکاری مورد استفاده قرار می گیرد. الگوریتم هایی نظیر کلونی مورچگان، اجتماع ذرات، ژنتیک و شبکه ی عصبی تا کنون، برای حل مسائل مرتبط با فروشنده ی دوره گرد، بسیار مورداستفاده قرار گرفته اند. از طرفی، الگوریتم فراابتکاری قهرمانی در لیگ های ورزشیLCA)تا کنون فقط برای مسائل پیوسته به کاررفته است. در این مقالهLCAرا، نخستین بار و به صورت نوآورانه، برای مسأله ی گسسته یTSPاستفاده نموده که نتایج قابل قبولی را نیز به همراه داشته است. در این تحقیق با استفاده ازLCAچهار مثال مختلف ازTSPبا اندازه های کوچک، متوسط، تقریباً بزرگ و بزرگ حل شده و با نتایج قبلی آن مقایسه گشته است. نظر به مشابهت بسیار زیاد جواب های به دست آمده با بهترین جواب های قبلی، عملکرد LCA مناسب ارزیابی شد. جزئیات مربوط به نتایج آن در این مقاله مندرج گردیده و پیرامون آن بحث شده است

کلیدواژه ها:

مسأله ی فروشنده ی دوره گرد ، الگوریتم قهرمانی در لیگ های ورزشی ، بهینه سازی ترکیباتی ، الگوریتم های فراابتکاری