SAC Model Based Improved Genetic Algorithm for Solving TSP

Abstract

Genetic algorithm (GA) has strong global searching ability and is easy to operate, but its disadvantages such as poor convergence speed, unstable and easy to fall into local optimal value restrict its application. In order to overcome these disadvantages, an improved genetic algorithm based on the deep reinforcement learning model SAC (soft actor-critic) is proposed in this paper, which is applied to the resolution of traveling salesman problem (TSP). The improved algorithm regards the population as agent's interaction environment, meanwhile greedy algorithm is used to initialize this environment for improving the quality of initial populations. For controlling the evolution of the population, the improved crossover and mutation operations are used as agent's action space. With the goal of maximizing the cumulative rewards of population evolution, the improved algorithm treats the evolution of the population as a whole and uses a policy gradient algorithm based on SAC to generate evolution controlling action strategy combined with the current individual fitness of the population. The action strategy reasonably uses the global and local search ability of genetic algorithm by agent's actions, optimizing the evolutionary process of the population while balancing relationship between the population convergence rate and the times of genetic operation. The experimental results of TSPLIB indicate that the improved genetic algorithm can effectively avoid falling into the local optimal solution and reduce the number of iteration in the optimization process while improving the convergence rate of the population.

Keywords

• reinforcement learning
• genetic algorithm (ga)
• traveling salesman problem (tsp)
• deep policy gradient
• soft actor-critic (sac) model