MCPC and MCMP Evolutionary Algorithms for the TSP

CARBALLIDO JESSICA A.; PONZONI IGNACIO; BRIGNOLE NÉLIDA B.

Buenos Aires, Argentina.

Simposio; ASAI 2003, (Argentine Symposium on Artificial Intelligence, XXXII Jornadas Argentinas de Informática e Investigación Operativa (XXXII JAIIO)); 2003

Sociedad Argentina de Informática e Investigación Operativa.

The Travelling Salesman Problem (TSP) is an NP-complete problem that has to be solved with optimisation tools, such as the evolutionary algorithms (EA). There are various ways of representing the TSP tours through EAs.  Two of the most often employed genetic representations are the ordinal and path representations. In this work we present several EAs based on those representations combined with different crossover operators, namely Single Crossover Per Couple (SCPC), Multiple Crossover Per Couple (MCPC) and Multiple Crossover with Multiple Parents (MCMP). The implementations were tested for several academic case studies generated at random. The EAs with MCPC exhibited the best performance, while the MCMP variants yielded premature convergence problems.