COMPUTACIÓN EVOLUTIVA- resumen

¿Que es la Computación Evolutiva?

La computación evolutiva (en adelante CE) es una de las ramas de la Inteligencia Artificial que se aplica para la resolución de problemas de optimización combinatoria. La CE está inspirada en los mecanismos de evolución biológica propuestos por Darwin, Medel y Lamark. Sin entrar mucho en detalle sobre los estudios que hicieron estos científicos, solo vamos a mencionar brevemente lo que propusieron. Darwin propuso la "Selección natural de los más adaptados", Medel propuso la "Teoría corpuscular de la herencia" y Lamark propuso la "Herencia de caracteres adquiridos".

Como debéis saber muchos de vosotros, el principal problema de la inteligencia artificial es que no tiene una definición fácil o formal, pero para entendernos podemos decir que la inteligencia artificial es una rama que trata de "imitar" a la inteligencia natural y por tanto la computación evolutiva se basa en imitar la evolución biológica tal y como la entendemos hoy en dia. Como podeis suponer la CE trata de resolver problemas de optimización combinatoria, con el fin de encontrar el mejor resultado al problema, es decir tal y como pasa en la naturaleza, ya que el gran problema que hay, sobre todo en el entorno animal; es la supervivencia y solo los más fuertes y mejor adaptados al entorno son capaces de sobrevivir y reproducirse; en otras palabras, son los mejores individuos posibles o la mejor solución al problema.

Aunque podemos "rizar mucho el rizo" la computación evolutiva se basa en la siguiente metáfora, denominada como metáfora evolutiva:

Una población de individuos coexiste en un determinado entorno con recursos limitados.

La competición por los recursos provoca la selección de aquellos individuos que están mejor adaptados al entorno.

Estos individuos se convierten en los progenitores de nuevos individuos a través de procesos de mutación y recombinación.

Los nuevos individuos pasan a competir por su supervivencia.

Con el paso del tiempo, esta selección natural provoca el incremento en la “calidad” de los individuos de la población.

Enlace. para más información 

• Orígenes de la computación evolutiva

Composición y funcionamiento de un algoritmo evolutivo (AE)

Sin duda, el mejor recurso bibliográfico para iniciarse en el mundo de la CE -compuactión evolutiva- es el magnífico libro Introduction to Evolutionary Computing, de los autores Agoston E. Eiben, y J.E. Smith.

Hemos dicho que la computación evolutiva es una ciencia computacional en la que sus algoritmos imitan el proceso evolutivo de la naturaleza. Veamos de qué partes consta, y cómo funcionan:

Cualquier AE seguirá el siguiente pseudocódigo:

Existe una población de n individuos, los cuales expresan una posible solución. La población es pues, un multiconjunto de genotipos, y forman la unidad de evolución.

Los individuos de la población se van renovando en sucesivas generaciones, que van convergiendo evolutivamente hacia la meta deseada, que no es otra que encontrar una solución a un problema determinado. La evolución se produce durante el paso de las generaciones, y cada generación cumple con el siguiente procedimiento:

La primera generación es especial, y sólo consiste en la generación (y evaluación) de una población inicial de nindividuos, normalmente generados aleatoriamente.

El resto de generaciones comienzan con la selección de los individuos que se van a reproducir. Es decir, se seleccionan los padres que conformarán la descendencia.

Y dicha descendencia, será el resultado de un proceso de recombinación y mutación de esos padres previamente seleccionados. Tras la creación de la descendencia, se procede a evaluar su adaptabilidad. Es decir; se calcula, lo bien o mal que se adapta el nuevo individuo a las condiciones del medio ambiente. Este proceso se suele realizar, mediante el uso de una funcion de desempeño (fitness function). Dicha función representará la adaptabilidad del fenotivo expresado por el genotipo en cuestión. Una vez evaluada la progenie, se procede a seleccionar los individuos que finalmente prevalecerán para formar la siguiente generación.

Todo este proceso generacional, se repetirá mientras no se cumpla una condición de parada. La condición de parada normalmente será, o bien que uno o varios genomas expresan un fenotipo que es solución óptima del problema a resolver, o que se alcanzó el máximo de generaciones previstos programáticamente.

Técnicas de Computación Evolutiva 

La expresión genérica computación evolutiva designa a un amplio conjunto de técnicas heurísticas de resolución de problemas complejos que basan su funcionamiento en un mecanismo análogo a los procesos de la evolución natural. Trabajando sobre un conjunto de soluciones a un problema determinado, la metodología utilizada por estas técnicas se fundamenta en el uso de mecanismos de selección de las mejores soluciones potenciales y de construcción de nuevas soluciones candidatas mediante recombinación de características de las soluciones seleccionadas.

El algoritmo evolutivo trabaja sobre individuos que representan potenciales soluciones al problema, codificados de acuerdo a un mecanismo prefijado. Los individuos son evaluados de acuerdo a una función de fitness que toma en cuenta la adecuación de cada solución al problema que se intenta resolver.

La operativa del algoritmo evolutivo comienza con una etapa de inicialización de los individuos, que puede ser completamente aleatoria, muestreando al azar diferentes secciones del espacio de soluciones, o guiada de acuerdo a características del problema a resolver. El algoritmo evolutivo podría inclusive tomar como población inicial individuos resultantes como salida de algún otro algoritmo heurístico de resolución que permitiera calcular buenas soluciones iniciales aproximadas para el problema.

La evolución propiamente dicha se lleva a cabo en el ciclo que genera nuevos individuos a partir de la población actual mediante un procedimiento de aplicación de operadores estocásticos. En este ciclo se distinguen cuatro etapas:

• Evaluación: etapa que consiste en asignar un valor de adecuación (fitness) a cada individuo en la población. Este valor evalúa que tan bien resuelve cada individuo el problema en cuestión, y es utilizado para guiar el mecanismo evolutivo. 
• Selección: proceso que determina candidatos adecuados, de acuerdo a sus valores de fitness, para la aplicación de los operadores evolutivos con el objetivo de engendrar la siguiente generación de individuos. 
• Aplicación de los operadores evolutivos: etapa que genera un conjunto de descendientes a partir de los individuos seleccionados en la etapa anterior. 
• Reemplazo: mecanismo que realiza el recambio generacional, sustituyendo individuos de la generación anterior por descendientes creados en la etapa anterior.

Programación Evolutiva 

Las técnicas de programación evolutiva fueron propuestas por Fogel, Owens y Walsh en 1966 como un método para evolucionar comportamientos de autómatas de estado finito utilizados para la predicción de series temporales (Fogel et al, 1966). El enfoque presentado en el artículo referido ha sido considerado “moderno”, en el sentido de que sigue la línea de trabajo actual de la computación evolutiva. Introduce el concepto de población y dimensiona adecuadamente la importancia del mecanismo de selección en el proceso evolutivo, tomando en cuenta el “entorno” al cual se encuentran expuestos los individuos. El método fue aplicado con éxito para la resolución de problemas sencillos, aunque no faltó la crítica habitual sobre que la técnica propuesta no era superior que una búsqueda completamente aleatoria. 

En 1975, Holland sugirió que un algoritmo evolutivo podría ser utilizado con una codificación que representara un programa (Holland, 1975). Luego de una década en el silencio, la programación evolutiva se renovó a mediados de 1980, modificando su planteo para permitir representaciones que extendieron su aplicabilidad para la resolución de variados problemas de optimización. En la década de 1980, algunos investigadores retomaron la sugerencia de Holland y realizaron implementaciones de programas evolutivos aplicados a heurísticas de optimización (Smith, 1985), al dilema del prisionero (Fujicki, 1986), y a la evolución de expresiones LISP para programas capaces de resolver juegos sencillos (Hicklin, 1986). Estos trabajos y otras aplicaciones de la programación evolutiva se presentan en el artículo de P. Angeline (1998), que ofrece una perspectiva histórica de las propuestas de estructuras ejecutables evolutivas.

La principal línea de trabajo de programas evolutivos se basa en el trabajo de John Koza, quien le dio el nombre de programación genética. Koza propuso un mecanismo evolutivo para la generación de programas, extendiendo las ideas previas de Cramer respecto al uso de árboles de parsing para representar programas (Koza, 1996). A partir de la propuesta de Koza, diversos investigadores han estudiado sobre temas relacionados con la programación genética, incluyendo la aplicabilidad de la técnica a un amplio conjunto de problemas, fundamentos teóricos del mecanismo, diseño de operadores evolutivos adecuados y aplicación de técnicas de procesamiento paralelo, entre otros (O' Reilly, 1995).

En los últimos años, las líneas de trabajo en el área de la programación evolutiva se han concentrado principalmente en aplicaciones como el entrenamiento de redes neuronales y la evolución de sistemas difusos. Algunos nuevos fundamentos matemáticos han sido presentados por parte del creador de las técnicas (Fogel, 1995). 

Referencias:

• FRANCIS CRICK. (D. Dennett, 1984). TÉCNICAS DE COMPUTACIÓN EVOLUTIVA . septiembre 2017, de Elbow Room: the varieties of free will worth wanting, ascedido en: http://recursos.salonesvirtuales.com/assets/bloques//francis_crick.pdf

• Ricardo Mayo . (18-mayo-2013). ¿Que es la Computación Evolutiva?. septiembre-2017, de Jorroba.com; ascedido en: https://jarroba.com/computacion-evolutiva-ejemplo-con-un-algoritmo-genetico/