Abstract:

Based on theories of simulated annealing(SA)、genetic algorithm(GA)、parthenon-genetic algorithm(PGA) and simulated annealing genetic algorithm(SAGA), the major merits and shortcomings of SA、GA and PGA are analyzed. According to the merits complementary nature of SA and PGA, a new algorithm --Parthenon-Genetic simulated annealing algorithm is proposed. The synthesizing of the merits of the two algorithms, reconstruction operation of gene in every generation in PGA has been improved. The traditional cooling method has been improved too. Between the operations of two generations, the algorithm adds a process which sorts the chromosomes in according to fitness function. In experiments we three groups city data’s traveling salesman problem (TSP) problems with the five algorithms mentioned above are used. It shows that the SAPGA’s average optimal solution is the least, and the convergence time is the shortest.

Key words: traveling salesman problem , genetic algorithm , parthenon-genetic algorithm , simulated annealing, combinatorial optimization