Análisis de Metaheurísticas Poblacionales para su Aplicación en Métodos de Reducción de Incertidumbre

Séptimo Encuentro de Investigadores y Docentes de Ingeniería
EnIDI 2013, Los Reyunos, San Rafael. Mendoza, Argentina

Análisis de Metaheurísticas Poblacionales para su
Aplicación en Métodos de Reducción de Incertidumbre*
Miguel Méndez-Garabetti1,2, Germán Bianchini1, María Laura Tardivo1,2,3
y Paola Caymes-Scutari1,2
1

Laboratorio de Investigación en Cómputo Paralelo/Distribuido(LICPaD)
Departamento de Ingeniería en Sistemas de Información, Facultad Regional Mendoza
Universidad Tecnológica Nacional. (M5502AJE) Mendoza, Argentina
miguelmendezgarabetti@gmail.com, {gbianchini,pcaymesscutari}@frm.utn.edu.ar
2

Consejo Nacional de Investigaciones Científicas y Técnicas (CONICET)
3
Departamento de Computación, Universidad Nacional de Río Cuarto.
(X5804BYA) Río Cuarto,Córdoba, Argentina
lauratardivo@dc.exa.unrc.edu.ar

Resumen. Las metaheurísticas poblacionales –como Algoritmos Genéticos (GA), Evolución
Diferencial (DE) y Optimización por Cúmulo de Partículas (PSO)– se utilizan de manera
eficiente en diferentes problemas complejos de optimización en ámbitos variados. En este
trabajo se realiza una comparación de estos algoritmos, utilizando como benchmark cuatrofunciones del CEC 2005, con el objetivo de poder determinar cuál de estas metaheurísticas
incluir en una nueva implementación del sistema de reducción de incertidumbre ESS, que
actualmente opera combinando Algoritmos Evolutivos (EAs), Cómputo de Alto Rendimiento y
Análisis Estadístico. En el análisis desarrollado se ha podido determinar que DE presenta mejor
desempeño que GA y PSOrespectivamente.
Palabras Clave: Metaheurísticas Poblacionales, Evolución Diferencial, Algoritmos Genéticos,
Optimización por Cúmulo de Partículas.

1 Introducción
La gran mayoría de los problemas de optimización poseen un grado de complejidad
tal que no pueden ser resueltos de manera exacta sin hacer uso de grandes cantidades
de tiempo. Sin embargo, en algunos problemas o situaciones particulares,no es
estrictamente necesario alcanzar una solución exacta, pudiendo ser éstos resueltos
haciendo uso de técnicas de optimización aproximadas, lo que permite solucionar el
problema en cuestión en períodos considerablemente menores de tiempo.
Los métodos de optimización aproximados brindan soluciones de alta calidad pero
no garantizan obtener una solución óptima global, en contraste con losmétodos de
*

Este trabajo ha sido financiado por Conicet mediante el proyecto PIP 11220090100709, por la
UTN a través del proyecto UTN1194 y por la ANPCyT mediante el proyecto PRH PICT2008-00242.

optimización exactos los cuales sí aseguran encontrar soluciones óptimas a cambio de
un alto costo computacional [1]. De los métodos de optimización aproximados las
metaheurísticas han cobrado unadestacada importancia en los últimos veinte años
debido a su capacidad de brindar soluciones satisfactorias aplicadas a problemas de
gran tamaño en plazos razonables de tiempo.
La clasificación de las metaheurísticas puede entenderse en función de distintos
criterios como ser: la cantidad de soluciones procesadas en cada ciclo de ejecución, la
forma en que se generan nuevas soluciones en elespacio de búsqueda, o el origen de
inspiración del algoritmo. Sin embargo, la primera de éstas es la que denota
diferencias de mayor relevancia por lo que se adopta como clasificación general.
Entonces, en función de la cantidad de soluciones utilizadas se clasifican en
metaheurísticas basadas en una única solución y metaheurísticas poblacionales. La
primera, tiene la característica demejorar de forma continua una única solución para
explorar el espacio de búsqueda del problema, este tipo de metaheurísticas también se
conoce como de trayectoria debido a que el proceso puede ser descrito como una
trayectoria de búsqueda a través del dominio de la solución del problema [2], mientras
que las metaheurísticas poblacionales o basadas en población, operan mejorando de
forma...