2009 WRI World Congress on Computer Science and Information Engineering Introducing Gene Clusters into a P2P Based TSP Solving Algorithm Los Angeles, California USA March 31-April 02 ISBN: 978-0-7695-3507-4
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CSIE.2009.468
The TSP (Traveling Salesman Problem) genetic algorithm is very possible of destroying ever found pieces of a path. To prevent the found pieces from being destroyed, a P2P based TSP genetic algorithm P2PTSPGA which make use of gene clusters is presented. The gene cluster which stands for a series of cities is past down in whole to the offspring from their parent individuals, and is smashed after the first optimum is found to prevent the algorithm from falling into a local optimum. Experiments on CHN144 and instances of TSPLIB show that the optimal solutions are the same as the published results, except the solution 3859 for TSP225 is better than the result 3916 published up-to-date. Our experiments also show that the P2PTSPGA has a high performance in solving such TSPs that number of cities is less than 5000.
Index Terms:
Traveling Salesman Problem, Gene Cluster, Peer to Peer, Genetic Algorithm
Citation:
Ma Guangzhi, Lu Yansheng, Song Enmin, Zhang Wei, "Introducing Gene Clusters into a P2P Based TSP Solving Algorithm," csie, vol. 4, pp.795-799, 2009 WRI World Congress on Computer Science and Information Engineering, 2009 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb