A New Mutation for Traveling Salesman Problem by Physarum Polycephalum
Yang Liu, Jingfei Zhang, Fuyuan Xiao and Yong Deng
We propose a mutation of a genetic algorithm solver for the traveling salesman problem (TSP) inspired path-forming and foraging behaviour of acellular slime mould Physarum polycephalum. Based on Physarum polycephalum model, a mutation operator, Physarum-type mutation (PTM), is developed to improve genetic algorithm (GA) for TSP. Inspired by adaptability of Physarum protoplasmic networks integrated in global features of GA the PTM allows for decreasing the probability of stacking in a local optimal solution and increasing the probability of reaching the global optimal solution. To test the performance of PTM, we conduct the experiments on 18 different TSP examples selected from TSPLIB. The results show that the proposed method outperforms the existing mutations of GA TSP solvers.
Keywords: Genetic algorithm; physarum polycephalum; mutation operator; traveling salesman problem; optimization.