FITNESS LANDSCAPES AND THE ANDREWS–CURTIS CONJECTURE
Jerry Swan, Gabriela V. Ochoa, Graham Kendall, Martin Edjvet · International Journal of Algebra and Computation · 2011
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.