Overcoming Complexity Catastrophe: An Algorithm for Beneficial Far-Reaching Adaptation under High Complexity
This addresses a foundational issue in evolutionary algorithms and optimization for researchers and practitioners, showing that complexity catastrophe can be overcome with incremental changes.
The paper tackles the problem of complexity catastrophe in NK landscapes, where high complexity hinders adaptation, and presents the ICTT algorithm that achieves superior fitness outcomes compared to existing research.
In his seminal work with NK algorithms, Kauffman noted that fitness outcomes from algorithms navigating an NK landscape show a sharp decline at high complexity arising from pervasive interdependence among problem dimensions. This phenomenon - where complexity effects dominate (Darwinian) adaptation efforts - is called complexity catastrophe. We present an algorithm - incremental change taking turns (ICTT) - that finds distant configurations having fitness superior to that reported in extant research, under high complexity. Thus, complexity catastrophe is not inevitable: a series of incremental changes can lead to excellent outcomes.