Performance analysis for crossover operators of genetic algorithm

✍ Scribed by Kengo Katayama; Hisayuki Hirabayashi; Hiroyuki Narihisa

• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 717 KB
• Volume: 30
• Category: Article
• ISSN: 0882-1666
• DOI: 10.1002/(sici)1520-684x(199902)30:2<20::aid-scj3>3.0.co;2-m

✦ Synopsis

In this paper, we deal with promising crossover operators developed in the genetic algorithm (GA) and analyze the performance of these crossovers on the traveling salesman problem (TSP) which is one of the most popular NP-hard problems. Many crossovers that efficiently generate good solutions have been proposed, and the performance of each crossover was evaluated using the framework of the simple GA. Therefore, for practical use, we propose a framework based on the GA combined with a local search algorithm, and analyze three crossovers for the TSP, the maximal preservative crossover of Mühlenbein et al., the improved edge recombination crossover of Starkweather et al., and the complete subtour exchange crossover recently proposed by us. From our results, we show that our crossover obtains better-quality solutions than the others and that the solutions obtained using the framework were little influenced by the probability of the mutational operator.