文章基本信息

标题：SOLVING TRAVELING SALESMAN PROBLEM USING GENETIC ALGORITHM BASED ON EFFICIENT MUTATION OPERATOR
本地全文：下载
作者：AHMAD BANY DOUMI ; BASEL A ; MAHAFZAH 等
期刊名称：Journal of Theoretical and Applied Information Technology
印刷版ISSN：1992-8645
电子版ISSN：1817-3195
出版年度：2021
卷号：99
期号：15
语种：English
出版社：Journal of Theoretical and Applied
摘要：The Traveling Salesman Problem (TSP) is a Combinatorial Optimization Problem (COP), which belongs to NP-hard problems and is considered a typical problem for many real-world applications. Many researchers used the Genetic Algorithm (GA) for solving the TSP. However, using a suitable mutation was one of the main obstacles for GA. This paper proposes for GA an Efficient Mutation (GA-EM) for solving TSP. The efficient mutation can balance between deeply searching and preventing stuck on local optima to ensure a better convergence rate and diversity. Therefore, in this paper, a local search method based on three neighborhood structure operators; namely, transpose, shift-and-insert, and swap, is proposed to produce the efficient mutation for GA. The performance of the proposed algorithm is validated by three TSP datasets; including, TSPLIB, National TSPs, and VLSI Data Set. These datasets have different graphs� structures and sizes. The sizes of the datasets range from 150 to 18512 cities. For comparative evaluation, the results obtained from the proposed GA-EM are compared with those obtained by four relatively recent approaches using the same TSP instances. These approaches are the Modernised Genetic Algorithm for solving TSP (MGA-TSP), List-Based Simulated Annealing algorithm (LBSA), Symbiotic Organisms Search optimization algorithm based on Simulated Annealing (SOS-SA), and Multiagent Simulated Annealing algorithm with Instance-Based Sampling (MSA-IBS). The GA-EM outperformed these approaches in all used TSP instances in terms of accuracy.
关键词：Genetic Algorithm;Mutation Operator;Neighboring Operator;Simulated Annealing Algorithm;Traveling Salesman Probl