Name
Abstract | ||
|---|---|---|
Genetic Algorithms (GAs) have traditionally been designed to work on bitstrings. More recently interest has shifted to the application of GAs to constraint optimization and combinatorial optimization problems. Important for an effective and efficient search is the use of a suitable crossover operator. This paper analyses the performance of six existing crossover operators in the traveling salesman domain. While the edge recombination operator was reported to be the most suitable operator in the TSP domain, our results suggest that this is only true for symmetric TSPs. The problem with edge recombination is that it inverts edges found in the parents. This has no negative effect for the symmetric TSP but can have a substantial effect if the TSP is asymmetric. We propose an edge based crossover operator for the asymmetric TSP and demonstrate its superiority over the traditional edge recombination. Another interesting finding is that order crossover (OX) which has an average performance for symmetric problems, performs very well on asymmetric problems. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1007/3-540-45486-1_17 | Canadian Conference on AI |
Keywords | Field | DocType |
genetic algorithm,constraint optimization,genetics,traveling salesman | Crossover,Evolutionary algorithm,Computer science,Algorithm,Evolutionary computation,Combinatorial optimization,Travelling salesman problem,Edge recombination operator,Operator (computer programming),Genetic algorithm | Conference |
Volume | ISSN | ISBN |
1822 | 0302-9743 | 3-540-67557-4 |
Citations | PageRank | References |
3 | 0.47 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kay C. Wiese | 1 | 164 | 19.10 |
| Scott D. Goodwin | 2 | 148 | 21.04 |
| Sivakumar Nagarajan | 3 | 14 | 2.57 |