Multi-parent extension of sequential constructive crossover for the travelling salesman problem

摘要

Crossover operator plays a vital role in genetic algorithms. This paper proposes the multi-parent sequential constructive crossover (MPSCX), which generalises the two-parent sequential constructive crossover (SCX) to a multi-parent crossover for the travelling salesman problem (TSP). Experimental results on five TSPLIB instances show that MPSCX significantly improves SCX by up to 4.60% in average tour value with maximum 4.01% away from the exact optimal solution. Finally, the efficiency of the MPSCX is compared as against multi-parent partially mapped crossover (MPPMX). Experimental results show that the MPSCX is better than the MPPMX.