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

یکی از اساسی ترین مسائل الگوریتمی گراف، مسئله فروشنده دوره گرد (TSP) می باشد. این مسئله یکی از مسائل بهینه سازی ترکیبی سخت است که راه حل محاسباتی برای آنها وجود ندارد و برای آن در زمان چندجمله ای ممکن است جوابی قطعی وجود نداشته باشد. هدف از مسأله فروشنده دوره گرد، به دست آوردن کوتاه ترین مسیر بین مجموعه ای ازشهرها است، به گونه ای که هر شهر، فقط یک بار در مسیر، قرار گرفته و مسیر ساخته شده، به شهر اول، منتهی می شود. دراین مقاله به ترکیب دو الگوریتم تکاملی ژنتیک (GA) و کلونی زنبور عسل مصنوعی (ABC)، جهت حل مسئله فروشنده دوره گرد پرداخته، آن را با هر یک از الگوریتم های GA و ABC ، مقایسه نموده ایم. نتایج، نشان دهنده برتری روش ترکیبی به کارگرفته شده است.

Keywords:

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