Improved Evolutionary Approximation Algorithms for TSP
Ru Huang · Microelectronics & Computer · 2004
Traveling Salesman Problem (TSP) is a typical combinatorial optimization problem. It has been proved that TSP is of NPC complexity. Therefore, it has significant meaning to solve this problem. We present a kind of approximation algorithm for TSP based on evolutionary algorithms which is defined as IEAA(Improved Evolutionary Approximation Algorithms).In the evolutionary process, IEAA conserves a group of better individuals instead of the best one in every cycle. Meanwhile, it uses only mutation operator meaning an asexual reproduction and only individuals with better performance have the chance to reproduce. All these characteristics speed up algorithms convergence. We use IEAA to resolve Chinese-TSP and get the encouraging result comparing with simple evolutionary algorithms.