A hybrid genetic algorithm for a Hamiltonian path problem

Download: PDF.

“A hybrid genetic algorithm for a Hamiltonian path problem” by E. Ponce de León and R. Santana. Revista Investigación Operacional, vol. 20, no. 1, 1999, pp. 20-29, Universidad de la Habana.

Abstract

This paper deals with Hável and Erdös conjecture that asserts that all bipartite graph formed with the middle levels of n-dimensional cube is Hamiltonian, when n is odd. This means that at least one Hamiltonian cycle should be found in the graph. We use a circular representation of the vertices of n-dimensional cube which makes it possible to introduce two group actions in order to reduce the problem to find out a Hamiltonian path in multi - level quotient graphs. We report on a hybrid genetic algorithm for the Hável and Erdös conjecture problem. We present interesting results which show that this GA approach gives optimal solutions in multi-level quotient graph. We use bitstring representation, an evolutionary fitness function, restricted edge crossover operator, intelligent mutation, seeding and adaptive mutation rate. Three Hamiltonian paths are constructed with this method.

Download: PDF.

BibTeX entry:

@article{Ponce_and_Santana:1999,
   author = {E. Ponce de Le{\'o}n and R. Santana},
   title = {A hybrid genetic algorithm for a {H}amiltonian path problem},
   journal = {Revista Investigaci{\'o}n Operacional},
   volume = {20},
   number = {1},
   pages = {20--29},
   publisher = {Universidad de la Habana},
   year = {1999}
}

(This webpage was created with bibtex2web.)

Back to Roberto Santana publications.