Computación evolutiva
De Wikipedia, la enciclopedia libre
La computación evolutiva nace en el año de 1993 y retoma conceptos de la evolución y la genética para resolver principalmente problemas de optimización. Esta rama de la inteligencia artificial tiene sus raíces en tres desarrollos relacionados pero independientes entre sí:
Los algoritmos genéticos fueron desarrollas por John H. Holland en la década de 1960 y su motivación inicial fue la de proponer un modelo general de proceso adaptable.
La programación evolutiva fue creada en la década de 1960 y su creador fue L. 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 resolver problemas de optimización de parámetros.
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 algoritmo evolutivo genérico.
- t:= 0
- Inicialización P(t)
- Evaluación P(t)
- While not terminado do
- P'(t) := variación[P(t)]
- Evaluación[P'(t)]
- P(t+1) := selección[P'(t) U Q]
- terminado := Criterio de convergencia[P(t+1)]
- t := t+1
- End do
Donde:
P(t) representa una población de mu individuos en la generación t.
Q es un conjunto especial de individuos que pueden ser considerados para la selección. Este conjunto puede ser vacío, además que su utilización está en función del método de selección que se utilice.
P'(t) es una población descendiente de mu individuos generada a partir de la aplicación de los operadores como la recombinación y la mutación, sobre la población P(t).
La inicialización es la creación de la población inicial, que se lleva cabo con la asignación de valores aleatorios a cada individuos.
La evaluación es la obtención de un indicador de aptitud (o capacidad del individuo 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.
La selección que es la obtención de una población de lambda individuos de P'(t) en función del indicador de aptitud y de Q.
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.
El criterio de convergencia se encarga de determinar en que momento el proceso iterativo debe de terminar, en función de los indicadores de aptitud asignados a los individuos de P(t+1). Otro punto importante es la función que genera el indicador de aptitud, a esta función, dentro de la computación evolutiva, se le conoce como función de desempeño (función de fitness en inglés). La función de desempeño se basa en la función objetivo o función de la cual se desea obtener el valor óptimo.
