A New Evolutionary Multiobjective Model for Traveling Salesman Problem
Open Access
- 20 May 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 7, 66964-66979
Abstract
The traveling salesman problem (TSP) is one of the most classical NP-hard problems in the combinatorial optimization, as which many practical problems, such as scheduling problems and vehicle-routing cost allocation problems, can be abstracted. The introduction of multiobjective in traveling salesman problem is a very important research topic which brings serious challenges to TSP. Currently, genetic algorithms (GA) are one of the most effective methods to solve multiobjective traveling salesman problem. However, GA-based algorithms suffer the premature convergence, the insufficient diversity and nonuniform distribution of solutions when solving MOTSP, which further restrict the wide application of GA-based algorithms. In order to overcome these problems, this paper proposes an improved method for genetic algorithms based on a novel evolutionary computational model, named as Physarum-inspired computational model (PCM). Based on the prior knowledge of PCM, the initialization of population in the proposed method is first optimized to enhance the distribution of solutions. Then the hill climbing method (HC) is used to improve the diversity of individuals and avert running into the local optimum. Compared to other MOTSP solving algorithms, a series of experiments results demonstrate that our proposed method achieve a better performance.Keywords
Funding Information
- National Natural Science Foundation of China (U1803263, 61762020)
- Natural Science Foundation of Chongqing Municipality (cstc2018jcyjAX0274)
This publication has 36 references indexed in Scilit:
- Multiobjective evolutionary algorithms: A survey of the state of the artSwarm and Evolutionary Computation, 2011
- Development a new mutation operator to solve the Traveling Salesman Problem by aid of Genetic AlgorithmsExpert Systems with Applications, 2011
- Multiobjective constructive heuristics for the 1/3 variant of the time and space assembly line balancing problem: ACO and random greedy searchInformation Sciences, 2010
- Rules for Biologically Inspired Adaptive Network DesignScience, 2010
- A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSPEuropean Journal of Operational Research, 2007
- A mathematical model for adaptive transport network in path finding by true slime moldJournal of Theoretical Biology, 2007
- Pareto Ant Colony Optimization: A Metaheuristic Approach to Multiobjective Portfolio SelectionAnnals of Operations Research, 2004
- A fast and elitist multiobjective genetic algorithm: NSGA-IIIEEE Transactions on Evolutionary Computation, 2002
- Bi-Criterion Optimization with Multi Colony Ant Algorithms2001
- Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approachIEEE Transactions on Evolutionary Computation, 1999