# 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.