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 resu...

Full description

Saved in:
Bibliographic Details
Published in:Expert systems with applications 2010-03, Vol.37 (3), p.1879-1886
Main Authors: Ting, Chuan-Kang, Su, Chien-Hao, Lee, Chung-Nan
Format: Article
Language:English
Subjects:
Combinatorial optimization
Genetic algorithms
Multi-parent crossover
Partially mapped crossover (PMX)
Traveling salesman problem (TSP)
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0957-4174
1873-6793
DOI:10.1016/j.eswa.2009.07.082