Departamento de Computación

En 1995, Rainer Storn y Kenneth V. Price desarrollaron un algoritmo evolutivo para optimización global sobre espacios continuos llamado Evolución Diferencial. Este algoritmo realiza una cruza entre tres padres y suele converger rápidamente al óptimo (o a su vecindad) en problemas con una sola función objetivo y sin restricciones. Además, el desempeño de este algoritmo depende del control de pocos parámetros, lo cual facilita su uso en diversos problemas. Estas características hacen de la evolución diferencial un candidato idóneo para resolver problemas multiobjetivo. En los problemas multiobjetivo se busca optimizar dos o más funciones las cuales se encuentran en conflicto unas con otras, es decir, el mejorar una función significa empeorar el desempeño de las otras. Este trabajo presenta el diseño de un algoritmo (en dos distintas versiones) que resuelve problemas de optimización multiobjetivo utilizando la evolución diferencial en la generación de nuevas soluciones. El algoritmo propuesto utiliza el esquema de la evolución diferencial para cruzar tres padres y obtener un solo hijo el cual compite con un padre para saber quién pasa a la siguiente generación. Además, el algoritmo mantiene dos poblaciones distintas: la población principal (que sirve para la selección de los padres) y una población secundaria. La primera versión del algoritmo maneja una malla adaptativa para retener las mejores soluciones obtenidas y distribuirlas uniformemente, y la segunda versión adopta el concepto de dominancia- para los mismos fines. Es importante mencionar que el algoritmo propuesto también contempla un esquema distinto en cuanto al manejo de restricciones permitiendo que algunas soluciones no factibles intervengan en la cruza ayudando a resolver eficientemente problemas multiobjetivo con restricciones (los cuales suelen ser más difíciles). Para medir el desempeño del algoritmo, se implementaron una serie de métricas llamadas medidas de desempeño, las cuales ayudan a determinar la cercanía de los individuos obtenidos con respecto al verdadero frente, así como su la bondad de su distribución. Esto permite realizar una comparación cuantitativa directa con algoritmos representativos del estado del arte, tales como: PAES, NSGA-II y PDE. La comparación se realizó en un conjunto de funciones de prueba estándar, encontrándose que el algoritmo propuesto en este trabajo resulta muy competitivo en su desempeño promedio.