 |
    |
New Subtour-Based Crossover Operator for the TSP
Sang-Moon Soak and Byung-Ha Ahn
Department of Mechatronics
Kwang-ju Institute of Science and Technology
Oryong-dong, Buk-gu, Gwangju 500-712, Republic of Korea
{soakbong,bayhay}@kjist.ac.kr
Abstract. Genetic algorithm (GA) is a very useful method for the global search of large search space and has been applied to various problems. It has two kinds of important search mechanisms, crossover and mutation. Because the performance of GA depends on these operators, a large number of operators have been developed for improving the performance of GA. Especially many researchers have more interested in crossover operator than mutation operator because crossover operator has charge of the responsibility of local search. We only deal with crossover operator.
In this paper we propose subtour preservation crossover (SPX), which uses a similar subtour enumeration method to other subtour-based crossovers but has an amount of difference in method that generates a valid tour. SPX generates offsprings as many as we wish by using genetic information of parents propagated over a lot of generations.
LNCS 2724, p. 1610 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003