Multiobjective Optimization Using a Micro-Genetic Algorithm

Year
2001
Type(s)
Author(s)
Gregorio Toscano Pulido
Source
(In Spanish), Universidad Veracruzana, Xalapa, Veracruz, Mexico, 2001

Los problemas del mundo real, en su gran mayoría presentan diferentes objetivos a optimizarse (los cuales generalmente se expresan en unidades diferentes y están en conflicto entre sí) y un espacio de búsqueda grande y complejo (p.ej., no diferenciable, accidentado, etc.). Estas dos características son suficientes para que los métodos tradicionales de optimización resulten inoperantes o simplemente re- quieran un costo computacional prohibitivo. Por lo tanto, este tipo de problemas requieren de técnicas alternativas de solución. La computación evolutiva ha sido utilizada satisfactoriamente para resolver los denominados problemas multiobjetivo (o sea, con más de una función objetivo). Sin embargo, no fue sino hasta recientemente que se ha comenzado a enfatizar el desarrollo de algoritmos que sean no sólo efectivos, sino también eficientes (en términos computacionales). Como resultado de estos estudios, esta disciplina conocida como optimización evolutiva multiobjetivo, ha originado nuevas metodologías para el desarrollo de algoritmos eficientes. Se sabe que las dos fuentes principales de ineficiencia de un algoritmo evolutivo multiobjetivo son: (a) el proceso de jerarquización para clasificar a los individuos usando el concepto de dominancia de Pareto, y (b) el mecanismo utilizado para preservar la diversidad en la población. Con esto en mente, se han propuesto recientemente algunas formas en que resulta posible disminuir los costos asociados con estas dos operaciones.
El objetivo principal de esta tesis fue el de construir un algoritmo eficiente, basado en tendencias novedosas del área que permiten el desarrollo de técnicas eficientes para solventar problemas de optimización multiobjetivo. Como consecuencia, se decidió desarrollar una aplicación en la cual se usaría un algoritmo genético con una población de tamaño muy pequeño y un proceso de reinicialización combinado con un archivo externo para guardar los vectores no-dominados encontrados previamente y un mecanismo para mantener diversidad basado en distribución geográfica, para resolver problemas de optimización multiobjetivo de diferentes grados de complejidad. Para validar el desempeño del algoritmo propuesto, se evaluó su comportamiento en seis funciones de prueba tomadas de la literatura especializada y se compararon los resultados obtenidos contra los producidos por dos técnicas recientes.