A Genetic Algorithm for a Hamiltonian Path Problem

Download: PDF.

A Genetic Algorithm for a Hamiltonian Path Problem” by E. Ponce de León, A. Ochoa, and R. Santana. In Proceedings of the X International Conference on Industrial and Engineering Applications of AI and Expert Systems, (Atlanta. USA), 1997, pp. 13-19.

Abstract

The genetic algorithm (GA) is one of the stochastic search techniques with application to a wide variety of combinatorial optimization problems. A conjecture of I. Havel, also attributed to P. Erdos, asserts that the simple graph G(k+1) (k>0), whose vertices are the subsets of cardinalities k and k+1 of the set 0,...,2k and whose adjacency is given by subset inclusion, is Hamiltonian. The search of a Hamiltonian cycle in this graph is reduced to find a Hamiltonian path in the multi-level graph. In this paper we describe a GA approach to this conjecture. We present theoretical and computational results which show that this GA approach finds the optimal solutions when we search path for each level of the graph. We introduce an evolutive fitness function, and discuss the impact of using non standard crossover operators. Seeding and adaptive mutation rate are used. Hamiltonian cycle in G(6) and G(7) are constructed.

Download: PDF.

BibTeX entry:

@inproceedings{Ponce_et_al:1997d,
   author = {E. Ponce de Le{\'o}n and A. Ochoa and R. Santana},
   title = {A Genetic Algorithm for a {H}amiltonian Path Problem},
   booktitle = {Proceedings of the X International Conference on
	Industrial and Engineering Applications of AI and Expert Systems},
   pages = {13--19},
   address = {Atlanta. USA},
   year = {1997},
   url =
	{http://books.google.es/books?hl=en&lr=&id=48FMFE2VwPkC&oi=fnd&pg=PA13&dq=info:otJvizwCRqsJ:scholar.google.com&ots=ubH-ZHpGno&sig=CGpqtfPgODzPRVIrwx2YkdG92yU&redir_esc=y#v=onepage&q&f=false}
}

(This webpage was created with bibtex2web.)

Back to Roberto Santana publications.