Algoritmos evolutivos
| ||||||||
Algoritmos evolutivos. Los algoritmos evolutivos son inspirados en la Teoría de evolución de Darwin y en el desarrollo de la informática evolutiva estos algoritmos permiten abordar problemas complejos que surgen en las ingenierías y los campos científicos.
Sumario
Origen
Tuvieron su origen en el año 1960 introducido por John Holland quien incorporo los métodos de selección natural y supervivencia a la resolución de problemas de IA. Los algoritmos evolutivos surgieron por la simulación de procesos de la evolución natural como resultado de esto es la optimización estocástica (Algoritmos evolutivos).
Funcionamiento y aplicación
Una rama de la inteligencia artificial son los algoritmos evolutivos (AE), estos son métodos de optimización y búsqueda estocásticos que se inspiran en la genética y en los principios establecidos por Darwin en 1859 sobre la evolución de las especies en el mundo biológico.
Estos algoritmos se modelan computacionalmente simulando la selección natural y el entrecruzamiento de las especies por medio de la recombinación genética y la mutación. En ellos se mantienen un conjunto de entidades que representan posibles soluciones, las cuales se mezclan y compiten entre sí, de manera que las más aptas son capaces de prevalecer a lo largo del tiempo, evolucionando hacia mejores soluciones cada vez.
En la naturaleza lo único que hay que optimizar es la supervivencia, y eso significa a su vez maximizar diversos factores y minimizar otros. Un algoritmo evolutivo, sin embargo, se usará habitualmente para optimizar sólo una función, no diversas funciones relacionadas entre sí simultáneamente. Se han aplicado con éxito en problemas de optimización, búsqueda, aprendizaje y simulación de sistemas dinámicos, en problemas con espacios de búsqueda extensos y no lineales donde otros métodos no son capaces de encontrar soluciones en un tiempo razonable.
Esta gran familia de algoritmos está compuesta por distintos métodos de búsqueda entre los que se pueden mencionar, la Programación Genética, que consiste en la evolución automática de se programa usando ideas basadas en la selección natural, se busca que poblaciones de programas evolucionen transmitiendo su herencia de manera que se adapten mejor al medio, los individuos tienen mayores probabilidades de reproducirse, la medida de la calidad del individuo dependerá del tipo de problema.
La Programación Evolutiva que se basa en la optimización de funciones y es una abstracción de la evolución al nivel de las especies, por lo que no se requiere el uso de un operador de recombinación (diferentes especies no se pueden cruzar entre sí). Los algoritmos evolutivos presentan una estructura que puede aplicarse en distintos problemas, favoreciendo así grandemente las tareas de diseño e implementación. Como único requisito del usuario que desee aplicar esta técnica para resolver un problema concreto es saber programar en cualquier lenguaje de propósito general en el que codificaría el algoritmo evolutivo.
Exigencias
Para obtener buenos resultados con estos algoritmos es necesario conocerlos en el más mínimo detalle, ya que dentro del esquema general de un algoritmo evolutivo hay que elegir múltiples componentes y parámetros, de los que va a depender la calidad del resultado y la eficiencia del algoritmo.Asimismo, utiliza selección probabilística. También se encuentran las estrategias evolutivas, son métodos computacionales que trabajan con una población de individuos que pertenecen al dominio de los números reales, que mediante los procesos de mutación y de recombinación evolucionan para alcanzar el óptimo de la función objetivo.
Los Algoritmos Genéticos usados fundamentalmente en la optimización de problemas combinatorios, en ellos cada cromosoma es una estructura de datos que representa una de las posibles soluciones del espacio de búsqueda del problema.
Los Cromosomas son sometidos a un proceso de evolución que envuelve evaluación, selección, crossover y mutación. Después de varios ciclos de evolución la población deberá contener individuos más aptos. También forman parte de los algoritmos evolutivos los algoritmos de estimación de distribuciones y otros métodos.
Un algoritmo evolutivo consiste en: hallar de qué parámetros depende el problema, codificarlos en un cromosoma , y aplicar los métodos de la evolución: selección y reproducción sexual con intercambio de información y alteraciones que generan diversidad.
Fases de un algoritmo evolutivo
Un algoritmo evolutivo sigue generalmente los siguientes pasos:
- Generar una POBLACIÓN aleatoria de N individuos.
- Evaluar los individuos de la POBLACIÓN de acuerdo a la función objetivo.
- Repetir durante GENERACIONES iteraciones:
- Aplicar el operador de selección para elegir k individuos de la POBLACIÓN
- Aplicar los operadores genéticos a esos k individuos para generar la descendencia
- Evaluar los nuevos individuos de acuerdo a la función objetivo
- Reemplazar los peores individuos en POBLACIÓN por los individuos recién creados.
Fuente
