Illinois Genetic Algorithms Laboratory

Tsutsui, S., Pelikan, M., Goldberg, D. E. (2003)
TR No.: 2003022 | Download PDF | Download PS

Abstract:
Recently, there has been a growing interest in probabilistic model-building genetic algorithms (PMBGAs), which replace traditional variation operators of genetic and evolutionary algorithms by building and sampling a probabilistic model of promising solutions. In this paper we propose a PMBGA that uses edge histogram based sampling algorithms (EHBSAs) to solve problems with candidate solutions represented by
permutations. Two sampling algorithms?the sampling without template
(EHBSA/WO) and the sampling with template (EHBSA/WT)?are presented. The
proposed algorithms are tested on several instances of the traveling
sales-man problem (TSP). The results show that EHBSA/WT works fairly
well even with a small population size on all tested problem instances
and that it outperforms popular two-parent recombination operators for
permuta-tions and other PMBGAs for permutation problems. Combining EHBSA
with a simple local heuristic for solving TSP called 2-OPT improves the
performance of the algorithm, enabling efficient solution to problems of
hundreds of cities. Nonetheless, unlike most other TSP solvers, EHBSA is
not limited to solving TSP in-stances, but it can be applied to any problem defined on permutations.