Abstrato

Enhanced Order Crossover for Permutation Problems

Girdhar Gopal, Rakesh Kumar, Ishan Jawa, Naveen Kumar

This paper proposes a modified Order crossover operator for genetic algorithm that generates high quality solutions to the Traveling Salesman Problem (TSP) effectively. As the main time consuming process of crossover operator and schemata preserving process in crossover is the hole filling done in Order Crossover operator, so if the swath size is not to be too long and also depending on the problem size then it might be proven to find near optimum solutions in effective and efficient manner. The Modified Order Crossover operator constructs an offspring from a pair of parents using the existing Order Crossover operator with the enhancement on swath length (the size of a chromosome which is between two crossover sites). The efficiency of the Modified Order Crossover is compared as against some of the existing crossover operators; namely, Partially Mapped Crossover (PMX), Order Crossover (OX) & Cyclic Crossover (CX) for some benchmark TSPLIB instances. Experimental results suggest that the new crossover operator enabled improved results compared to the PMX, OX and CX for the five Travelling salesman problems tested