A Partheno Genetic Algorithm Based on Gene Pool for TSP
Xiyu Liu · Jisuanji fangzhen · 2010
Traveling Salesman Problem(TSP) is a typical representative of combinatorial optimization problems.An improved Genetic algorithm is proposed for solving TSP.This Partheno-genetic algorithm employs only mutation and selection operators to produce the offspring.A new combinatory operator is designed by combining the gene pool operator with inversion operator which ensures its strong searching capability.The gene pool directs the single-parent evolution and enhances the evolutionary speed.This algorithm simulates the recurrence of nature evolution process.Experiments based on 4 instances selected from TSPLIB are used to test the performance of this algorithm.They prove that it can reach the satisfying optimization at a faster speed.Especially,for the KroA100,the best path it found is better than any other available one.