A Genetic Algorithm Based on Stochastic Crossover for DHCP
Marco Carpentieri · 2007
We introduce a genetic model based on stochastic crossover to solve the Hamiltonian cycle problem (DHCP) for random digraphs containing a random Hamiltonian cycle. The genetic model represents a new decision computational method inspired by the remark that DHCP can be formulated as determining the compatibility of a quadratic system over the finite field GF(2). A (simple) genetic algorithm based on the stochastic crossover is experimentally compared with a randomized algorithm based on the Angulin and Valiant classic technique designed to find Hamiltonian cycles in random digraphs