کاربرد یک الگوریتم اصلاحی رقابت استعماری برای حل مسأله ی فروشنده دوره‌گرد

نوع مقاله: اصیل

نویسندگان

1 باشگاه پژوهشگران جوان، دانشگاه آزاد اسلامی، واحد همدان

2 دانشکده ریاضی و علوم کامپیوتر، دانشگاه صنعتی امیرکبیر تهران

چکیده

این مقاله یک روش رقابت استعماری اصلاح‌شده را برای حل مسأله فروشنده دوره‌گرد ارائه می کند که در تابع جذب بین کشورهای استعمارگر و استعمار شده و هم چنین انقلاب کشورهای مستعمره، با حالت معمولی خود تفاوت دارد. به علاوه برای افزایش کارایی الگوریتم از روش بهبود دهنده ی سه‌گانه استفاده می‌شود. الگوریتم جدید روی 19 مثال استاندارد مسأله فروشنده دوره‌گرد از کتابخانه TSPLIBمورد آزمایش و با الگوریتم‌های رقابت استعماری، ژنتیک، پرندگان، تکاملی و کلونی زنبور مورد مقایسه قرار گرفت. نتایج محاسباتی نشان می‌دهد که الگوریتم پیشنهادی دارای کارایی مناسبی می‌باشد.

کلیدواژه‌ها


عنوان مقاله [English]

Application a Modified Imperialist Competitive Algorithm for Solving the Traveling Salesman Problem

نویسندگان [English]

  • Majid Yousefikhoshbakht 1
  • Farzad didehvar 2
  • Farhad Rahmati 2
1 Young Researchers Club, Hamedan Branch, Islamic Azad University, Hamedan, Iran
2 College of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran
چکیده [English]

This paper proposes a modified Imperialist Competitive Algorithm (MICA) for solving the Traveling Salesman Problem (TSP) that is different with common Imperialist Competitive Algorithm (ICA) in assimilation policy between Imperialist and colonies countries and revolution of colonies. Furthermore, the 3-opt local search is used for increasing performance of the algorithm. The new ICA algorithm is  tested on nineteen instances of TSBLIB and its performance is compared with  ICA, Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Evolutionary Algorithm (EA) and Bee Colony Optimization (BCO). Extensive computational tests confirm the effectiveness of the proposed approach.