Solving Large Travelling Salesman Problems with Small Populations
Rong Yang
Abstract:
A new genetic algorithm for the solution of the travelling salesman problem is presented in this paper. The approach is to introduce several knowledge-augmented genetic operators which guide the genetic algorithm more directly towards better quality of the populationbut are not trapped in local optima prematurely. The algorithm applies a greedy crossover and two advanced mutation operations based on the 2-opt and 3-opt heuristics. One of our particular interests is to investigate whether small populations are adequate for solving large problems. We also want to see how the quality of the initial population and the quality of the final solution are related, especially when the population is small. For this purpose, we designed a selective initialization scheme to generate a better initial population. The algorithm has been implemented in C and tested on several sets of data. The largest data instance used is 2392 cities (i.e., pr2392). The actual population size used is only 32. ...
Bibliographical:
@Misc{yang98, title = "Solving Large Travelling Salesman Problems with Small Populations", author = "Rong Yang", year = "1998", month = aug # "~25", abstract = "A new genetic algorithm for the solution of the travelling salesman problem is presented in this paper. The approach is to introduce several knowledge-augmented genetic operators which guide the genetic algorithm more directly towards better quality of the populationbut are not trapped in local optima prematurely. The algorithm applies a greedy crossover and two advanced mutation operations based on the 2-opt and 3-opt heuristics. One of our particular interests is to investigate whether small populations are adequate for solving large problems. We also want to see how the quality of the initial population and the quality of the final solution are related, especially when the population is small. For this purpose, we designed a selective initialization scheme to generate a better initial population. The algorithm has been implemented in C and tested on several sets of data. The largest data instance used is 2392 cities (i.e., pr2392). The actual population size used is only 32. For sma...", citeseer-references = "oai:CiteSeerPSU:193219; oai:CiteSeerPSU:527216; oai:CiteSeerPSU:531138", annote = "Author: Rong Yang (Affiliation: Department of Computer Science, University of Bristol; Address: Bristol BS8 1UB, U.K; ); The Pennsylvania State University CiteSeer Archives", language = "en", oai = "oai:CiteSeerPSU:145347", rights = "unrestricted", subject = "Rong Yang Solving Large Travelling Salesman Problems with Small Populations", URL = "http://citeseer.ist.psu.edu/145347.html; http://www.cs.bris.ac.uk/~rong/gzipped/tsp.ps.gz", }
URL:
http://citeseer.ist.psu.edu/145347.html
http://liinwww.ira.uka.de/cgi-bin/bibshow?e=Njtd0DjufTffs02::9%6019/vojrvf%7d24597761&r=bibtex