Solving TSP with Novel Local Search Heuristic Genetic Algorithms

The standard genetic algorithm often meets the occurrences of slow convergence for solving combinatorial optimization. In this study, we present a hybrid genetic algorithm (LSHGA) for symmetric traveling salesman problem. In the algorithm, a modified local search method based on new neighborhood model was contrived as crossover operation. And a MUT3 operator was introduced as mutation operation. For evading plunge into local extremum, some new ideas are incorporated in our algorithm. The strategy that unites stochastic tournament and elite reservation was used in the process of selection. An idea of reservation ratio was put forward, and the theory of self-adaptive was employed for conforming parameters of LSHGA at the same time. As a result, the population diversity of LSHGA was preserved, and can accomplish convergence quickly. Eight example problems in TSPLIB were showed in the paper to demonstrate the capabilities of the proposed algorithm.