Computación evolutiva

La computación evolutiva es una rama de la inteligencia artificial que involucra problemas de optimización combinatoria. Se inspira en los mecanismos de la Evolución biológica.

Historia

Durante los años 50 se comenzó a aplicar los principios de Charles Darwin en la resolución de problemas. Durante los años 60 y 70, varias corrientes de investigación independientes comenzaron a formar lo que ahora se conoce como computación evolutiva:

• Programación evolutiva
• Estrategias Evolutivas
• Algoritmos genéticos

La programación evolutiva nació en la década de 1960 y su creador fue Lawrence J. Fogel. Este desarrollo comenzó como un esfuerzo encaminado a crear inteligencia artificial basado en la evolución de máquinas de estado finitas.

Las estrategias evolutivas fueron propuestas por Ingo Rechenberg y Hans-Paul Schwefel en la década de 1970. Su principal objetivo era el de optimizar de parámetros.

Los algoritmos genéticos fueron propuestos por John H. Holland en 1975 y su motivación inicial fue la de proponer un modelo general de proceso adaptable.

Algoritmos evolutivos

De manera general la computación evolutiva toma como base las ideas de la evolución propuestas por Charles Darwin y en los descubrimientos realizados por Gregor Mendel en el campo de la genética. A continuación se muestra el pseudocódigo de un algoritmo evolutivo genérico.

t:= 0

Inicialización P(t)

Evaluación P(t)

Hacer

P'(t):= variación[P(t)]

Evaluación[P'(t)]

P(t+1):= selección[P'(t) U Q]

t:= t+1

Mientras no se cumpla condición de término

Donde:

• La inicialización es la creación de la población inicial (P(0)), usualmente asignando valores aleatorios a cada individuo.

• P(t) representa una población de μ individuos en la generación t.

• La evaluación es la asignación de un indicador de aptitud (o capacidad para resolver el problema propuesto), para cada individuo de la población P(t), mediante la aplicación de una función de desempeño.

• P'(t) es una población construida a partir de la aplicación de operadores como recombinación y mutación, sobre la población P(t).

• Q es un conjunto especial de individuos que pueden ser considerados para la selección. Este conjunto puede ser vacío. Además, su utilización varia dependiendo del método de selección que se utilice.

• La población de la generación siguiente (P(t + 1)) se obtiene a partir de la selección a partir de la unión de la población modificada, P'(t) y los individuos eligibles, Q; considerando la función de desempeño utilizada.

• La condición de término es un criterio que indica cuándo se debe poner fin a la búsqueda. Este criterio puede ser un nivel de convergencia, un número de generaciones máximo, o un tiempo de ejecución máximo, entre otros

Cabe hacer notar que los operadores de variación, la selección y la manera en que son utilizados dependen del enfoque que se esté ocupando. Por ejemplo, la aplicación de la mutación no es la misma en los Algoritmos genético que en las Estrategias evolutivas.

Aspectos a considerar

Entre los principales aspectos a considerar en el diseño de algoritmos evolutivos se encuentran los siguientes:

• La elección de una codificación (representación de las variables del problema en el algoritmo evolutivo) tiene un gran efecto en el tamaño del Espacio de búsqueda y por ende, en el tiempo y dificultad de resolución.
• La función de desempeño (fitness function), la cual considera en la función objetivo o función de la cual se desea obtener el valor óptimo.
• Los algoritmos evolutivos poseen diversos parámetros los cuales deben ser cuidadosamente elegidos para obtener un buen desempeño y evitar problemas tales como la Convergencia prematura.

Enlaces externos

• http://algoritmoevolutivo.blogspot.com/2011/10/computacion-evolutiva-ejemplo-i.html Blog con ejemplos prácticos sobre computación evolutiva escritos en Java y de licencia GPL.