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. Hàvel, also attributed to P. Erdös, 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 cycles in G(6) and G(7) are constructed.
