On the Computational Power of Adaptive Systems

Recent research has demonstrated that no search algorithm is better than any other one when performance is averaged over all possible discrete problems. Hybridization (incorporation of problem-knowledge) is required to produce adequate problem-specific algorithms. This work explores the power of hybridization in the context of evolutionary algorithms. For this purpose, a framework for describing adaptive systems is presented. It is shown that, when hybridized, adaptive techniques are computationally complete systems with Turing capabilities. Moreover, evolutionary algorithms can be regarded as a kind of nondeterministic Turing machines