Algoritmos evolutivos con estimación de distribuciones

Algoritmos Evolutivos de Estimación

Algoritmos Evolutivos de Estimación.Son algoritmos basados en poblaciones que realizan su búsqueda en el carácter estocástico de la generación. No utilizan los operadores de cruce y mutación.

El comportamiento de los Algoritmos Genéticos dependen en gran parte de los operadores de cruce y mutación , las probabilidades de cruce y mutación, el tamaño de la población , la tasa de reproducción generacional, el número de generaciones, etc.

La determinación de valores adecuados para dichos parámetros constituye por sí mismo un verdadero problema de optimización. Por otra parte una mala elección de los valores de los parámetros puede llevar a que el algoritmo obtenga soluciones alejadas del óptimo.

Este es uno de los motivos por los que desde hace varios años se han venido estudiando alternativas a los métodos heurísticos estocásticos existentes que no necesitasen el ajustar un número alto de parámetros. Otro motivo básico por el que se ha desarrollado la búsqueda de nuevos métodos heurísticos de optimización es por la necesidad de identificar las interrelaciones entre las variables utilizadas para representar a los individuos con la codificación utilizada.

Nueva familia

Todo ello ha motivado al nacimiento de una nueva familia de algoritmos evolutivos llamados Algoritmos Evolutivos con estimación de distribuciones (EDAs). Estos son algoritmos basados en poblaciones al igual que los algoritmos genéticos en los que la transición de una generación a otra ha sido modificada, y basan su búsqueda en el carácter estocástico de la misma, sin embrago a diferencia de los AGs, en los EDAs no existen los operadores de cruce y mutación.

En su lugar la población de individuos se regenera mediante una distribución de probabilidad, que se estima a partir de una base de datos formada por individuos de generaciones anteriores, es decir se sustituyen los operadores de cruce y mutación, por operadores que estiman o “aprenden” la distribución de probabilidad de los puntos seleccionados en la generación anterior. Se utilizan para resolver problemas de optimización en los cuales las variables de decisión son reales (xi€R), en una generación la población se construye realizando un muestreo probabilístico de la población anterior y escogiendo los mejores individuos.

Mientras que en los algoritmos genéticos las interrelaciones entre las variables representando a los individuos se tienen en cuenta de manera implícita, en los EDAs dichas interrelaciones se expresan de manera explícita a través de la distribución de probabilidad asociada con los individuos seleccionados en cada generación.

Pasos que siguen los algoritmos evolutivos

1. En primer lugar, se genera la población inicial formada por N puntos, que frecuentemente se realiza asumiendo una distribución uniforme de cada variable. Tras generar los puntos, estos se evalúan mediante la aplicación de la función de adaptabilidad o de costo (función objetivo).
2. Segundo, en cada generación se seleccionan M puntos (M ≤N) siguiendo un criterio de selección.
3. Tercero, se induce el modelo probabilístico n-dimensional que mejor representa las interdependencias entre las n variables. Este paso es conocido como el de aprendizaje, y es el más crucial en los EDAs debido a la importancia de tener en cuenta todas las dependencias entre las variables para asegurar mejoras sucesivas de los puntos.
4. Finalmente, la nueva población se conforma con N nuevos puntos obtenidos tras simular o muestrear la distribución de probabilidad aprendida en el paso previo. Es frecuente en este paso utilizar una aproximación elitista, que mantiene el mejor o los mejores puntos de la población t–1 en la nueva población. En este caso, se crean en cada generación un total de N – E puntos, donde E representa el número de puntos élites.

Los pasos 2, 3 y 4 se repiten mientras no se cumple una condición de parada en concreto. Ejemplos de criterios de parada son: llegar a un número máximo de generaciones, uniformidad de la población generada, no mejora con respecto al mejor de los puntos obtenido en las generaciones previas, etc. A continuación se muestra el pseudocódigo de un EDAs.

Pseudocódigo.JPG

Estructura general de un Algoritmo de Estimación de distribuciones

Estructura.JPG

Como se puede observar al igual que en la mayoría de los algoritmos generacionales, se parte de una población inicial con m individuos, generada (en la mayoría de los casos) aleatoriamente. En el segundo paso se selecciona un número n (n<=m) de individuos, se selecciona normalmente aquellos con los mejores valores en la función de evaluación) como base de datos para la estimación del modelo . A continuación se introduce el modelo probabilístico n-dimensional que mejor refleja las interdependencias entre las n variables. A partir del modelo inducido se genera una población auxiliar mediante muestreo. Por último la nueva población D_k se obtiene a partir de la población anterior D_ {k-1} y de la población auxiliar. Normalmente esta selección se realiza de forma elitista. A continuación se muestra como proceden los EDAs para arrojar las nuevas generaciones.

Fig # 3. Diagrama ejemplificando la operativa de un EDA.

Como se puede observar, partimos de una población inicial de individuos a la cual aplicamos un proceso de selección, en este paso decantamos aquellos individuos menos prometedores a mejorar nuestra función objetivo, posteriormente utilizando los individuos seleccionados determinamos el modelo que caracteriza las relaciones existentes entre las variables, este modelo permite luego aplicando un muestreo estocástico seleccionar la nueva generación.
El principal problema que se presenta es la estimación del modelo M, ya que cuanto más complejo sea el modelo mejor recogerá las dependencias entre las variables, pero más compleja/costosa será su estimación, puesto que en cada generación un nuevo modelo puede ser construido.

Formas fundamentales de realizar el modelado

• Análisis univariado: este es el modelo más simple, no considera relaciones entre las variables y las probabilidades conjuntas se factorizan como producto de distribuciones (marginales) univariadas e independientes.
• Análisis bivariados: permite la dependencia entre las variables, sin embargo la dependencia se restringe a dos variables, ej: xj depende de xi y solo de xi. En este caso es necesario realizar dos tareas: hallar el grafo de dependencia y calcular las probabilidades condicionales P (xj|xi). Se puede decir que existen heurísticas específicas para determinar el grafo de dependencia.
• Análisis multivariado: es el enfoque más completo, pero también el más complejo de implementar, los modelos estadísticos utilizados son de orden n, típicamente se modelan mediante redes bayesianas. Para obtener la población en t+1 se realiza el muestreo de M, habitualmente mediante la utilización de modelos lógicos probabilísticos.
  Las diferencias consisten en el tipo de relaciones que son consideradas para la construcción del modelo.

Fuente

• Tesis de Isabel María Higuera Igarza.