Generalization and Completeness of Evolutionary Computation

Abstract

The need of a structured framework for evolutionary computation has been acknowledged. In order to achieve this we designed a set of operational semantics and defined a “general form” of evolutionary computation. Our second approach towards a generalization was to study the relationship between different algorithms and the problems they solve from a performance standpoint. Lastly, we tried to analyze the convergence and complexity of evolutionary algorithms. This led to a set of computability results, the main one being that evolutionary computation is Turing-complete.

Se ha reconocido la necesidad de crear un marco estructurado para la computación evolutiva. Para llegar a él diseñamos un conjunto de semánticas operacionales y definimos una “forma general” de la computación evolutiva. Nuestro segundo enfoque para llegar a una generalización fue estudiar la relación existente entre distintos algoritmos y los problemas que solucionan desde el punto de vista de su eficiencia. Finalmente, tratamos de analizar la convergencia y complejidad de los algoritmos evolutivos. Esto nos llevó a obtener una serie de resultados sobre su calculabilidad, siendo el más importante la Turing-completitud de la computación evolutiva.