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.