TY - JOUR
T1 - A New Evolutionary Multiobjective Model for Traveling Salesman Problem
AU - Chen, Xuejiao
AU - Liu, Yuxin
AU - Li, Xianghua
AU - Wang, Zhen
AU - Wang, Songxin
AU - Gao, Chao
N1 - Publisher Copyright:
© 2013 IEEE.
PY - 2019
Y1 - 2019
N2 - The traveling salesman problem (TSP) is one of the most classical NP-hard problems in the combinatorial optimization, as many practical problems, such as scheduling problems and vehicle-routing cost allocation problems can be abstracted. The introduction of multiobjective in the TSP is a very important research topic, which brings serious challenges to the TSP. Currently, genetic algorithms (GAs) are one of the most effective methods to solve the multiobjective traveling salesman problem (MOTSP). However, GA-based algorithms suffer the premature convergence, the insufficient diversity, and nonuniform distribution of solutions when solving the MOTSP, which further restrict the wide application of GA-based algorithms. In order to overcome these problems, this paper proposes an improved method for GAs based on a novel evolutionary computational model, named the Physarum-inspired computational model (PCM). Based on the prior knowledge of the PCM, the initialization of the population in the proposed method is first optimized to enhance the distribution of solutions. Then, the hill climbing (HC) method is used to improve the diversity of individuals and avert running into the local optimum. Compared to the other MOTSP solving algorithms, a series of experimental results demonstrate that our proposed method achieves a better performance.
AB - The traveling salesman problem (TSP) is one of the most classical NP-hard problems in the combinatorial optimization, as many practical problems, such as scheduling problems and vehicle-routing cost allocation problems can be abstracted. The introduction of multiobjective in the TSP is a very important research topic, which brings serious challenges to the TSP. Currently, genetic algorithms (GAs) are one of the most effective methods to solve the multiobjective traveling salesman problem (MOTSP). However, GA-based algorithms suffer the premature convergence, the insufficient diversity, and nonuniform distribution of solutions when solving the MOTSP, which further restrict the wide application of GA-based algorithms. In order to overcome these problems, this paper proposes an improved method for GAs based on a novel evolutionary computational model, named the Physarum-inspired computational model (PCM). Based on the prior knowledge of the PCM, the initialization of the population in the proposed method is first optimized to enhance the distribution of solutions. Then, the hill climbing (HC) method is used to improve the diversity of individuals and avert running into the local optimum. Compared to the other MOTSP solving algorithms, a series of experimental results demonstrate that our proposed method achieves a better performance.
KW - Bi-objective traveling salesman problem
KW - hill climbing
KW - NSGA-II
KW - Physarum
UR - http://www.scopus.com/inward/record.url?scp=85067255790&partnerID=8YFLogxK
U2 - 10.1109/ACCESS.2019.2917838
DO - 10.1109/ACCESS.2019.2917838
M3 - 文章
AN - SCOPUS:85067255790
SN - 2169-3536
VL - 7
SP - 66964
EP - 66979
JO - IEEE Access
JF - IEEE Access
M1 - 8718296
ER -