The Efficiency of a Genetic Algorithm with a SHC Mutation

Recently, Genetic Algorithms (GAs) have been investigated as a technique for solving combinatorial optimization problems and have been shown to be effective at searching solutions among a large and complex space in an adaptable way, guided by the equivalent biological evolutionary mechanisms of reproduction, crossover and mutation. In this paper, we propose an efficient Genetic Algorithm (GA) for solving the traveling salesman problem (TSP) as a combinatorial optimization problem. In our computational model, we propose a complete subtour exchange crossover that breaks as few good subtours as possible, because good subtours are worth preserving for descendants. Generally speaking, global search GAs are considered to be better approaches than local searches. However, it is necessary to strengthen local searches as well as global ones in order to increase a GAs total efficiency. In this study, we propose a new GA which applies a stochastic hill climbing (SHC) procedure in the mutation process of the GA. Experimental results have shown an efficiency convergence as high as 99 percent even for 500 cities TSP