Departamento de Computación

La mayoría de los problemas de mundo real son multiobjetivo. Generalmente las técnicas tradicionales de optimización no-lineal multiobjetivo son computacionalmente costosas. Consecuentemente, es difícil obtener soluciones en tiempo polinomial, si se incrementa la complejidad del problema. Además, las técnicas tradicionales de programación matemática son normalmente altamente susceptibles a la forma o continuidad del frente de Pareto. Por lo tanto, se necesitan nuevas herramientas alternativas para abordar dichos problemas. Una de ellas es la computación evolutiva. La “optimización mediante cúmulos de partículas” (PSO1 ) es una heurística evolutiva relativamente nueva que ha sido usada para resolver exitosamente una amplia variedad de tareas de optimización. Su alta velocidad de convergencia y su relativa simplicidad hacen al PSO un candidato altamente viable para utilizarlo en la resolución de problemas multiobjetivo. Sin embargo, el PSO carece de un mecanismo explícito para manejar objetivos múltiples. En esta tesis, analizamos y extendemos el PSO para resolver “eficientemente” problemas de optimización multiobjetivo. Nuestra investigación está dividida en tres partes principales: 1) una propuesta para habilitar al PSO para que pueda manejar objetivos múltiples. La principal novedad del enfoque consiste en el uso de una técnica de clustering para dividir la población en diferentes sub-cúmulos (en el espacio de las variables de decisión). Dicha modificación mejora significativamente la calidad del frente de Pareto producido, en parte, debido a que hace emerger una búsqueda local en cada sub-cúmulo. También, para reducir el conjunto de soluciones no-dominadas, proponemos un enfoque adicional para aceptar soluciones. 2) Presentamos un mecanismo para manejar restricciones usando el PSO. Nuestra propuesta usa un criterio de selección de líderes basado en la cercanía de una partícula a la región factible. Los resultados nos indican que el algoritmo propuesto es altamente como petitivo con respecto a tres técnicas de manejo de restricciones representativas del estado del arte en el área. Nuestra técnica fue también implentada en nuestro PSO multiobjetivo (MOPSO). 3) Finalmente, para mejorar el desempeño general del algoritmo, realizamos un estudio sobre los parámetros del MOPSO. Proponemos un esquema de auto-adaptación para seleccionar los mejores valores de los parámetros; nuestra propuesta fue validada usando varias funciones de prueba y métricas tomadas de la literatura especializada. Los resultados indican que nuestro algoritmo final es una alternativa viable, ya que supera el desempeño algunos de los mejores algoritmos multiobjetivos que se conocen a la fecha.