Instituto Polit�cnico Nacional
Instituto Politécnico Nacional
"La Técnica al Servicio de la Patria"
Error
  • JUser: :_load: No se ha podido cargar al usuario con 'ID': 79

Boletín No. 64
1o. de enero de 2018




COMPARATIVA ENTRE ALGORITMOS EVOLUTIVOS EN PROBLEMAS DE MINIMIZACIÓN

 

ISC. Rául Fernando Galván Correa
Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Dr. Mauricio Olguín Carbajal
Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Dr. Juan Carlos Herrera Lozada
Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.

Instituto Politécnico Nacional
Centro de Innovación y Desarrollo Tecnológico en Cómputo

 

Resumen

Se realizará una comparación entre 3 algoritmos evolutivos (Estrategias evolutivas, Evolución diferencial y Optimización por cúmulo de partículas-PSO) para observar su comportamiento en distintas funciones de prueba, obteniendo resultados que permitirán realizar una aproximación de cuáles algoritmos se desempeñan mejor en ciertos problemas de optimización.

 

I. Introducción

Los algoritmos evolutivos (también conocidos como bio-inspirados) son algoritmos heurísticos que están basados en el principio de la evolución a través de la supervivencia del más apto. El uso principal de este tipo de algoritmos es resolver problemas complejos de búsqueda, principalmente en problemas de optimización. En la mayoría de los trabajos de investigación se utilizan los algoritmos evolutivos para la resolución y optimización en problemas de la vida real a través de una función de adaptación (fitness), los cuales tienen restricciones al determinar el modelo matemático, adaptando los algoritmos para el correcto manejo de las restricciones. Entre los algoritmos evolutivos más conocidos se incluyen los algoritmos genéticos, estrategias evolutivas y programación genética. En conjunto todas las técnicas se conocen con el nombre de cómputo evolutivo. [1]

Estos algoritmos trabajan con una población de individuos P(t)={x1,x2,x3,…xn} para la iteración t, donde cada uno de los individuos x representa un punto de búsqueda en el espacio de soluciones de un problema en específico. Posteriormente el desempeño de un individuo xi se evalua en la función de adaptación (fitness). En los algoritmos evolutivos la población inicial evoluciona hacia mejores regiones del espacio de búsqueda a través de distintos procesos probabilísticos: 1) Elitismo: selección de los individuos más adaptados en la población, es decir los que obtienen mejores valores de minimización en la función de adaptación. 2) Modificación utilizando recombinación y/o mutación de individuos seleccionados. [2]

Las diferencias principales de los algoritmos evolutivos contra los tradicionales de búsqueda exhaustiva, aleatorios entre otros, son los siguientes: a) codificación de parámetros, b) búsquedas en paralelo con una población, c) Uso de una función de fitness sin necesidad de utilizar derivadas, d) reglas de transición probabilísticas entre una iteración y otra.

Para que los algoritmos evolutivos encuentren óptimos locales, utilizan básicamente dos técnicas : 1) Explorar áreas desconocidas en el espacio de búsqueda utilizando procesos y datos aleatorios para incrementar el espacio de exploración, 2) Explotar el conocimiento de los puntos previamente obtenidos. En los últimos años se han propuesto nuevas heurísticas como Evolución Diferencial (ED) y Particle Swarm Optimization (PSO) para poder resolver problemas de optimización con restricciones. El objetivo del presente trabajo es analizar el comportamiento de diferentes algoritmos (Estrategia evolutiva (EE), Evolución Diferencial (ED), Optimización por cúmulo de partículas (PSO)) y determinar el desempeño de cada uno de los algoritmos con las mismas características del problema a resolver.[3]

II. Descripción del experimento

En el experimento se utilizan 10 funciones de prueba. Las características de cada uno de los problemas se presentan en la Tabla 1. Cabe mencionar que en la mayoría de los algoritmos evolutivos se tienen como condición de paro un número determinado de generaciones/iteraciones establecidas por el usuario o si la función fitness obtiene el valor de minimización que se está buscando. Sin embargo en el presente trabajo se tomó como condición de paro 10,000 llamadas a la función fitness, independientemente del número de iteraciones que represente debido a que algunos algoritmos realizan más de una evaluación por individuo de la función fitness por generación. De esta manera, se obtendrán valores tomando un parámetro en común con todos los algoritmos, de otra manera no es tan sencillo debido a que cada uno de los algoritmos definen variables de restricciones de manera distinta.

 

Figura 1. Funciones a evaluar.

III. Análisis del experimento

Como se mencionó anteriormente, se realizó la ejecución de cada uno de los algoritmos. En Figura 2 se puede observar un ejemplo del comportamiento de PSO, donde todas las partículas tienden hacia un mismo valor.

Figura 2. Tendencia de partículas del algoritmo PSO.

Como se mencionó anteriormente, se realizó la ejecución de los tres algoritmos tomando como criterio de parada 10,000 llamadas a la función objetivo. En la Tabla 3 se muestran los resultados obtenidos.

Tabla 1. Resultados algoritmos.

De acuerdo a los resultados obtenidos en las Tabla1 se puede observar  que se en la mayoría de los casos PSO obtiene mejores óptimos, mientras que Estrategias evolutivas es el que tiene los valores más lejanos del mínimo.

Los valores utilizados para el control de las restricciones en los algoritmos son los siguientes: Para el caso de Estrategias evolutivas: número de individuos=100, porcentaje de mutación=0.8; Evolución diferencial: número de individuos=100, porcentaje de cruza= 0.2, porcentaje de mutación= 1/5; PSO: Número de partículas=50, w(inercia) = 0.729, C1 (cognitive particle)= 1.49445, C2(social)= 1.49445.

IV. Modelo

En la Figura 3, Figura 4 y Figura 5 se presentan los pseudocódigos de los modelos que representan a cada uno de los algoritmos.

Figura 3. Pseudo-código Evolución Diferencial.

 

Figura 4. Pseudo-código Estrategias Evolutivas.

 

Figura 5. Pseudo-código PSO

Una vez realizados los algoritmos se graficaron cada uno de los resultados para observar los comportamientos. En la Figura 6 se muestra un ejemplo de comparación entre los 3 algoritmos de la función 8.

 

Figura 6. Comparación Estrategias Evolutivas (azul), Evolución diferencial (rojo) y PSO (verde)

V. Análisis

Como se puede observar en la Tabla 1 y Figura 5, los mejores óptimos los obtuvo PSO, mientras que los resultados más lejanos del mínimo fueron de Estrategias Evolutivas. Este comportamiento se repite en todas las funciones. Cabe mencionar que Evolución diferencial tuvo resultados muy cercanos a PSO, siendo igual de eficaces para las funciones presentadas.

VI. Conclusiones

Las conclusiones principales se mencionan  a continuación:

  1. PSO mostró los resultados de calidad de manera consistente y más cercanos a los mínimos.
  2. Evolución Diferencial obtuvo resultados competitivos.
  3. Estrategias evolutivas mostró los resultados más pobres y en varios problemas se quedó lejos de los valores óptimos.

Como trabajo a futuro se busca realizar la comparación de los algoritmos con otras funciones de prueba y observar su funcionamiento, debido a que para ciertos problemas de optimización un algoritmo puede dar mejores soluciones que el resto.

Referencias

  1. Lucken C, Hermosilla A. y Barán B. (2004) Algoritmos Evolutivos para Optimización Multiobjetivo: un Estudio Comparativo en un Ambiente Paralelo Asíncrono. Campus Universitario de San Lorenzo. Pages 1-9.

  2. Estevez P. (2007) Optimización Mediante Algoritmos Genéticos. Pages 83-92.

  3. López-Ramírez B. y Mezura-Montes E. Comparación de algoritmos evolutivos y bio-inspirados en problemas de optimización con restricciones. Centro de Investigaciones en Óptica CIATEC. Pages 2-5.