Computo Evolutivo

Computación Evolutiva

Definición: El computo evolutivo es una área de la inteligencia que implementa diversos algoritmos heurísticos (ósea que no se garantiza que de la solución verdadera, pero se acerca lo suficiente) basado en la teoría de la evolución natural para poder resolver problemas de optimización y búsqueda.

El cómputo evolutivo se utiliza para resolver una amplia variedad de problemas computacionales de cualquier área del conocimiento, incluyendo problemas NP.

 Computación Evolutiva y Optimización

Un problema de optimización requiere hallar un conjunto de parámetros de forma que se cumpla un cierto criterio de calidad que se quiere optimizar, es decir, maximizando o minimizando una cierta función de evaluación f(x) dada.

Los algoritmos evolutivos son especialmente útiles cuando nos encontramos con problemas difíciles o altamente irresolubles, como lo son aquellos caracterizados por una alta dimensionalidad, multimodalidad, fuerte no linealidad, no diferenciabilidad, presencia de ruido y cuando se trata con funciones dependientes del tiempo.

ALGORITMOS GENÉTICOS

Modelan el proceso de evolución como una sucesión de frecuentes cambios en los genes, con soluciones análogas a cromosomas. Trabajan con una población de cadenas binarias para la representación del problema, y el espacio de soluciones posibles es explorado aplicando transformaciones a éstas soluciones candidatas tal y como se observa en los organismos vivientes: cruce, inversión y mutación. Como método de selección emplean en mecanismo de la ruleta (a veces con elitismo). Constituyen el paradigma más completo de la computación evolutiva ya que resumen de modo natural todas las ideas fundamentales de dicho enfoque.

Son muy flexibles ya que pueden adoptar con facilidad nuevas ideas, generales o específicas, que surjan dentro del campo de la computación evolutiva. Además, se pueden hibridar fácilmente con otros paradigmas y enfoques, aunque no tengan ninguna relación con la computación evolutiva. Se trata del paradigma con mayor base teórica.

CLASES DE ALGORITMOS GENÉTICOS

Algoritmos Genéticos Generacionales

Se asemejan a la forma de reproducción de los insectos, donde una generación pone huevos, se aleja geográficamente o muere y es substituida por una nueva. En este momento se realizan cruces en una piscina de individuos, los descendientes son puestos en otra, al final de la fase reproductiva se elimina la generación anterior y se pasa a utilizar la nueva. Este modelo también es conocido como Algoritmo Genético Canónico.

Algoritmos Genéticos de estado Fijo.

Utilizan el esquema generacional de los mamíferos y otros animales de vida larga, donde coexisten padres y sus descendientes, permitiendo que los hijos sean educados por sus progenitores, pero también que a la larga se genere competencia entre ellos. En este modelo, no solo se deben seleccionar los dos individuos a ser padres, si no también cuales de la población anterior serán eliminados, para dar espacio a los descendientes. La diferencia esencial entre el reemplazo generacional y el modelo de estado fijo es que las estadísticas de la población son recalculadas luego de cada cruce y los nuevos descendientes están disponibles inmediatamente para la reproducción. Esto permite al modelo utilizar las características de un individuo prometedor tan pronto como es creado.
Algoritmos Genéticos Paralelos.

Parte de la metáfora biológica que motivo a utilizar la búsqueda genética consiste en que es inherentemente paralela, donde al evolucionar se recorren simultáneamente muchas soluciones, cada una representada por un individuo de la población. Sin embargo, es muy común en la naturaleza que no solo sea una población evolucionando, si no varias poblaciones, normalmente aisladas geográficamente, que originan respuestas diferentes a la presión evolutiva. Esto origina dos modelos que toman en cuenta esta variación, y utilizan no una población como los anteriores si no múltiples concurrentemente.

Modelos de Islas.

Si se tiene una población de individuos, esta se divide en subpoblaciones que evolucionan independientemente como un Algoritmo Genético normal. Ocasionalmente, se producen migraciones entre ellas, permitiéndoles intercambiar material genético. Con la utilización de la migración, este modelo puede explotar las diferencias en las subpoblaciones; esta variación representa una fuente de diversidad genética. Sin embargo, si un número de individuos emigran en cada generación, ocurre una mezcla global y se eliminan las diferencias locales, y si la migración es infrecuente, es probable que se produzca convergencia prematura en las subpoblaciones.

Modelo Celular

Coloca cada individuo en una matriz, donde cada uno sólo podrá buscar reproducirse con los individuos que tenga a su alrededor (más cerca de casa) escogiendo al azar o al mejor adaptado. El descendiente pasara a ocupar una posición cercana. No hay islas en este modelo, pero hay efectos potenciales similares. Asumiendo que el cruce está restringido a individuos adyacentes, dos individuos separados por 20 espacios están tan aislados como si estuvieran en dos islas, este tipo de separación es conocido como aislamiento por distancia.

ESTRATEGIAS EVOLUTIVAS (EE)

Esta técnica está básicamente enfocada hacia la optimización paramétrica. En esencia son métodos estocásticos con paso adaptativo, que permiten resolver problemas de optimización paramétrica. A este método se le han agregado procedimientos propios de la computación evolutiva, que lo han convertido en un paradigma más de dicha metodología. Con tal mezcla, las EEs pueden definirse como algoritmos evolutivos enfocados hacia la optimización paramétrica, teniendo como características principales que utilizan una representación a través de vectores reales, una selección determinística y operadores genéticos específicos de cruce y mutación. Además, su objetivo fundamental consiste en encontrar el valor real de un vector de N dimensiones.

Las EEs pueden dividirse en dos tipos: Estrategias Evolutivas Simples y Estrategias Evolutivas Múltiples.

EEs Simples

Son consideradas como procedimientos estocásticos de optimización paramétrica con paso adaptativo, esta característica las hace similares al temple simulado. En este caso, se hace evolucionar un solo individuo usando únicamente a la mutación como operador genético. Son relativamente sencillas, y se denominan también EEs de dos miembros. Debido a que evoluciona un solo individuo a la vez, no son consideradas estrictamente como métodos evolutivos. A pesar de ser muy sencillas, son de gran utilidad práctica y han sido utilizadas, con algunas mejoras, para resolver problemas reales en diversas áreas.

EEs Múltiples

Surgen como respuesta a las debilidades de las EEs simples, las cuales tienden a converger hacia subóptimos. En las EEs múltiples existen múltiples individuos (población), y se producen en cada generación varios nuevos individuos, usando tanto mutación como cruce (también puede usarse cualquier otro operador). Se usa normalmente e cruce promedio, el cual genera un único descendiente de dos padres, promediando los valores de estos. En cuanto a los criterios de reemplazo, siempre se usa un esquema determinístico pudiéndose utilizar una estrategia de inserción o de inclusión.

Algunas aplicaciones de las estrategias evolutivas son:

• Problemas de ruteo y redes

• Bioquímica

•  Óptica

• Diseño en ingeniería

• Magnetismo