An Improved NSGA-II Algorithm for Multi-objective Traveling Salesman Problem

Yabo Luo, Min Liu, Zhongxiao Hao, Dongbo Liu

Abstract


Multi-objective traveling salesman problem (MOTSP) is an extended instance of traveling salesman problem (TSP), which is a well-known NP hard problem. In this paper, an improved NSGA-II algorithm (denoted by INSGA-II-MOTSP) is proposed to solve the MOTSP. Specifically, a layer strategy according to need is proposed to avoid generating unnecessary non-dominated fronts. The arena’s principle is also adopted to construct non-dominated set, so as to reduce the count of dominance comparison. In addition, an order crossover like operator and an inversion mutation operator are adopted for MOTSP. The experiment results show that the proposed INSGA-II-MOTSP algorithm is able to find better spread of solutions compared to other three algorithms.

 

DOI : http://dx.doi.org/10.11591/telkomnika.v12i6.5476


Full Text:

PDF

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Indonesian Journal of Electrical Engineering and Computer Science (IJEECS)
p-ISSN: 2502-4752, e-ISSN: 2502-4760
This journal is published by the Institute of Advanced Engineering and Science (IAES) in collaboration with Intelektual Pustaka Media Utama (IPMU).

shopify stats IJEECS visitor statistics