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. ...
@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",
}
http://citeseer.ist.psu.edu/145347.html
http://liinwww.ira.uka.de/cgi-bin/bibshow?e=Njtd0DjufTffs02::9%6019/vojrvf%7d24597761&r=bibtex