Abstract
We use two evolutionary algorithms to make hard instances of the Hamiltonian cycle problem. Hardness (or ‘fitness’), is defined as the number of recursions required by Vandegriend–Culberson, the best known exact backtracking algorithm for the problem. The hardest instances, all non-Hamiltonian, display a high degree of regularity and scalability across graph sizes. These graphs are found multiple times through independent runs, and by both evolutionary algorithms, suggesting the search space might contain monotonic paths towards the global maximum. For Hamiltonian-bound evolution, some hard graphs were found, but convergence is much less consistent. In this extended paper, we survey the neighbourhoods of both the hardest yes- and no-instances produced by the evolutionary algorithms. Results show that the hardest no-instance resides on top of a steep cliff, while the hardest yes-instance turns out to be part of a plateau of 27 equally hard instances. While definitive answers are far away, the results provide a lot of insight in the Hamiltonian cycle problem’s state space.
Original language | English |
---|---|
Article number | 372 |
Pages (from-to) | 1-16 |
Number of pages | 16 |
Journal | SN Computer Science |
Volume | 3 |
Issue number | 5 |
Early online date | 15 Jul 2022 |
DOIs | |
Publication status | Published - Sept 2022 |
Bibliographical note
Funding Information:ECTA’s reviewers really made an effort to understand and thoroughly annotate the predecessor of this paper which led to this extended version. For the journal paper, two reviewers of Springer Nature Computer Science did an excellent job by not only reading, but recalculating, interpreting and discussing our findings. Thank you all, for adding your fruits of thought to our pie.
Publisher Copyright:
© 2022, The Author(s).
Keywords
- Evolutionary algorithms
- Hamiltonian cycle problem
- Instance hardness
- NP-complete
- Plant propagation algorithm