Swan J, Ochoa G, Kendall G & Edjvet M (2012) Fitness landscapes and the Andrews-Curtis conjecture. International Journal of Algebra and Computation, 22 (2), p. 1250009. https://doi.org/10.1142/S0218196711006753
Attempts have been made to eliminate some potential counterexamples to the Andrews-Curtis conjecture using the combinatorial optimization methods of blind-search and the genetic algorithms meta-heuristic. Breadth-first search with secondary storage is currently the most successful method, which raises questions regarding the inferior performance of heuristic search. In order to understand the underlying reasons we obtain fitness landscape metrics for a number of balanced presentations and draw conclusions regarding the likely effectiveness of other meta-heuristics.
Andrews–Curtis conjecture; fitness landscapes; combinatorial optimization
International Journal of Algebra and Computation: Volume 22, Issue 2