# A genetic algorithm and a local search procedure for a Hamiltonian path problem

**Download:**
PDF.

“A genetic algorithm and a local search procedure for a Hamiltonian
path problem”
by
E. Ponce de León
and
R. Santana.
In *Memorias del Encuentro Latino Iberoamericano de
Optimización, I ELIO. Congreso Chileno de Investigación
Operativa OPTIMA 97.*, (University of Conception, Chile), November 3-6
1997, pp. 226-232.

## Abstract

This paper deals with Hávels 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 make 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ávels 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 path are
constructed with this method.

**Download:**
PDF.

**BibTeX entry:**

@inproceedings{Ponce_and_Santana:1997,
author = {E. Ponce de Le{\'o}n and R. Santana},
title = {A genetic algorithm and a local search procedure for a
{H}amiltonian path problem},
booktitle = {Memorias del Encuentro Latino Iberoamericano de
Optimizaci{\'o}n, I ELIO. Congreso Chileno de Investigaci{\'o}n
Operativa OPTIMA 97.},
pages = {226-232},
address = {University of Conception, Chile},
month = {November 3-6},
year = {1997}
}

(This webpage was created with
bibtex2web.)

Back to Roberto Santana publications.