Departamento de Computación

Al buscar solucionar un problema de optimización, existen múltiples herramientas matemáticas que nos ayudan a lograr este objetivo. No obstante, en el mundo real existen problemas de optimización para los cuales es difícil o incluso imposible, aplicar métodos de programación matemática con Éxito. En estos problemas, las heurísticas se vuelven una alternativa viable. Los algoritmos evolutivos han sido ampliamente utilizados en optimización multi-objetivo debido a su naturaleza basada en la evolución de una población (o conjunto de soluciones), que permite la generación de diversos elementos del conjunto de óptimos de Pareto en una sola ejecución. Sin embargo, en un gran número de problemas de la vida real, las evaluaciones de las funciones objetivo a optimizar son muy costosas, en el sentido económico y/o computacional, lo cual puede volver impráctico el uso de algún algoritmo evolutivo. En esta tesis se propone una forma de reducir el número de evaluaciones de la función objetivo en el NSGA-II, que es un algoritmo evolutivo multi-objetivo del estado del arte mediante la implementación de métodos de aproximación de funciones, para aprovechar así los beneficios ofrecidos por los algoritmos evolutivos reduciendo su principal desventaja. Mediante el uso métodos de aproximación de funciones es posible construir un modelo similar al real, con la ventaja de poder acceder a él las veces que sean necesarias sin los inconvenientes relacionados con la función real. Al implementar dichos métodos al NSGA-II, fue posible obtener valores óptimos (o cercanos a éstos) en problemas de prueba estándar sin necesidad de realizar un número excesivo de evaluaciones a la función objetivo real.

Abstract

In the task of searching solutions for an optimization problem, there are many mathematical tools which help us to achieve this objective. Nevertheless, in the real world there exist optimization problems for which it is dificult or even impossible to apply mathematical programming methods successfully. In this type of problems, heuristics become a viable alternative. Evolutionary algorithms have been wide ly used in multi-objective optimization due to their population (or solutions set)-based nature which allows them to generate several Pareto optimal elements in a single run. Nevertheless, in a large amount of problems in real life, the evaluation of the functions to be optimized are costly in an economic and/or a computational sense, and may turn impractical the use of an evolutionary algorithm. In this thesis, we propose a method to reduce the number of the objective functions evaluations in the NSGA-II, which is a multi-objective evolutionary algorithm representative of the state-of-the-art hybridized with an implementation of functions aproximation methods. The aim is to exploit the good characteristics of evolutionary algorithms while overcoming their main disadvantage. The use of functions approximation methods makes possible to build a model similar to the real one, with the advantage of being able to access it the times required by the problem without the disadvantages of evaluating the real function. When this type of methods were implemented into the NSGA-II, it was possible to obtain optimal values (or near optimal) in standard test problems without the need of performing a large number of evaluations to the real (and presumably costly) function.