Multi-parent extension of partially mapped crossover for combinatorial optimization problems

摘要

This paper proposes the multi-parent partially mapped crossover (MPPMX), which generalizes the partially mapped crossover (PMX) to a multi-parent crossover. The mapping list and legalization of PMX are modified to deal with the issues that arise from the increase of parents in PMX. Experimental results on five traveling salesman problems show that MPPMX significantly improves PMX by up to 13.95% in mean tour length. These preferable results not only demonstrate the advantage of the proposed MPPMX over PMX, but also confirm the merit of using more than two parents in crossover.