On the computational power of adaptive systems
Carlos Cotta, Enrique Alba, José M. Troya · 2000
Recent research has demonstrated that no search algorithin is better than any other one when performance is averaged over all possible discrete prob lems. Hybridization (incorporation of problem-knowiedge) 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 lecinmiques are computationally complete systeins with Turing capabilities. Moreover, evolutionary algorithms can be regarded as a kind of nondeterministie Turing machines.