The efficiency of hybrid mutation genetic algorithm for the travelling salesman problem

✍ Scribed by K Katayama; H Sakamoto; H Narihisa

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 519 KB
• Volume: 31
• Category: Article
• ISSN: 0895-7177
• DOI: 10.1016/s0895-7177(00)00088-1

✦ Synopsis

In this paper, we present an efficient genetic algorithm (GA) for solving the travelling salesman problem (TSP) as a combinatorial optimization problem. In our computational model, we propose a complete subtour exchange crossover that does not break as some good subtours as possible, because the good subtoum are worth preserving for descendants. Generally speaking, global search GA is considered to be better approaches than local searches. However, it is necessary to strengthen the ability of local search as well as global ones in order to increase a GA total efficiency. In this study, our GA applies a stochastic hill climbing procedure in the mutation process of the GA. Experimental results showed that the GA leads good convergence as high as 99 percent even for 500 cities TSP.