A hybrid genetic algorithm for solving bi-objective traveling salesman problems

2nd Annual International Conference on Information System and Artificial Intelligence

物理学;计算机科学

Ma, Mei^1 ; Li, Hecheng^1

School of Mathematics and Statistics, Qinghai Normal University, Xining

810008, China^1

关键词: Algorithm framework;    Bi-objective traveling salesman problems;    Combinatorial optimization problems;    Hybrid genetic algorithms;    Iteration process;    Multi objective;    Satisfaction degrees;   

Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/887/1/012065/pdf
DOI  :  10.1088/1742-6596/887/1/012065

学科分类：计算机科学（综合）

来源: IOP

【 摘 要 】

The traveling salesman problem (TSP) is a typical combinatorial optimization problem, in a traditional TSP only tour distance is taken as a unique objective to be minimized. When more than one optimization objective arises, the problem is known as a multi-objective TSP. In the present paper, a bi-objective traveling salesman problem (BOTSP) is taken into account, where both the distance and the cost are taken as optimization objectives. In order to efficiently solve the problem, a hybrid genetic algorithm is proposed. Firstly, two satisfaction degree indices are provided for each edge by considering the influences of the distance and the cost weight. The first satisfaction degree is used to select edges in a "rough" way, while the second satisfaction degree is executed for a more "refined" choice. Secondly, two satisfaction degrees are also applied to generate new individuals in the iteration process. Finally, based on genetic algorithm framework as well as 2-opt selection strategy, a hybrid genetic algorithm is proposed. The simulation illustrates the efficiency of the proposed algorithm.