Hybridization of Evolutionary Techniques for the TSP with a Genotypic Termination Criterion

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

WSEAS Transactions on Information Science and Applications

WSEAS Press (The World Scientific and Engineering Academy and Society Press)

Lugar: Atenas; Año: 2004 vol. 1 p. 67 - 72

1790-0832

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.