試驗基因演算法解旅行推銷員問題

Abstract

基因演算法（Genetic Algorithm）是一種模仿自然界生物演化過程的演算法，適合在巨大數量的可行解中，迅速找到最佳解的近似解。基因演算法利用交配與突變的作用，讓一群可行解自行演化出更好的解。此演算法很合適用來解旅行推銷員問題（Traveling Salesman Problem），這篇論文除了利用典型的基因演算法外，並設計了新的限制作用，並得到了更好的結果。The traveling salesman problem (TSP) is an NP-complete problem. These problems are considered to have no solution in polynomial time. However, there are ways of approximating the solutions to these problems. Genetic algorithm (GA) is a model of machine learning based on biological evolution of population, which uses crossover and mutation operators to solve optimization problems, evaluate individual by fitness function. They have been used successfully in different problems, including the TSP. In this paper, we design a restriction action to weed out some paths. It is a new idea. Restriction had better be a necessary condition of the optimal solution, but they also work even though they are not. Restriction itself is not an operator. This can be added to other operators to make them more efficient. We also compare with some studies of other researchers. We find that a suitable restriction can increase the efficacy of GAs. We can design other restrictions on GAs for TSP or other problems.