Departamento de Computación

La optimización multiobjetivo tiene amplias aplicaciones en distintas áreas de la ingeniería y las ciencias computacionales. Muchos de estos problemas tienen espacios de búsqueda muy grandes por lo que, en algunos casos, no pueden ser resueltos mediante técnicas exactas en un tiempo razonable. Para resolver este tipo de problemas suelen utilizarse metaheurísticas. Dentro de las metaheurísticas destacan los algoritmos basados en computación evolutiva, los cuales simulan el proceso de selección del \más apto" en una computadora, aún de resolver problemas (por ejemplo de optimización y clasificación). En los algoritmos evolutivos, las soluciones de un problema son modeladas como individuos de una población, a las cuales se le aplican operadores inspirados en la evolución biológica. Este tipo de algoritmos han sido capaces de obtener muy buenos resultados en diversos problemas del mundo real, de alta complejidad. Una técnica de computación evolutiva son los algoritmos culturales. Esta clase de algoritmo incorpora, además del espacio de población, un espacio de creencias. El espacio de creencias es un repositorio de información extraída durante el proceso de optimización y utilizada para hacer la búsqueda más eficiente. En esta tesis se diseño e implementó un algoritmo cultural para resolver problemas de optimización multiobjetivo. El algoritmo propuesto utiliza el algoritmo llamado NSGA-II como su espacio de población. La propuesta consiste en incorporar un espacio de creencias a NSGA-II y utilizarlo como guía en la selección. Además, se incorpora un procedimiento de búsqueda local basado en la información contenida en el espacio de creencias. El algoritmo propuesto fue evaluado utilizando problemas de prueba y medidas de desempeño estándar, reportados en la literatura especializada. Los resultados del algoritmo cultural multiobjetivo propuesto fueron comparados contra los obtenidos por el NSGA-II. Los resultados indicaron que el algoritmo cultural propuesto logró un mejor desempe~no en la mayor parte de los problemas de prueba adoptados, indicando el potencial de este tipo de técnicas para resolver problemas con funciones objetivo computacionalmente costosas.

Abstract

Multiobjective optimization has wide applicability in diferent areas within engineering and computer science. Many of these problems have very large search spaces and, therefore, in some cases, cannot be solved using exact techniques, within a reasonable time. For solving these types of problems, it is common to adopt metaheuristics. Within metaheuristics, algorithms based on evolutionary computation are a popular choice. Evolutionary algorithms simulate the \selection of the ttest" principle in a computer, with the aim of solving (for example, optimization and classification) problems. When using evolutionary algorithms, the solutions of a problem are modeled using individuals in a population, to which several operators inspired on biological evolution are applied. This type of approach has been able to obtain very good results in a variety of highly complex real-world problems. A particular evolutionary computation technique are the so-called cultural algorithms. This type of algorithm incorporates, besides the population space, a belief space. The belief space is a repository of information which is extracted during the optimization process, and which is adopted to perform a more eficient search. In this thesis, a cultural algorithm for solving multiobjective optimization problems is designed and implemented. The proposed approach adopts NSGA-II as its population space. This work incorporates a belief space into NSGA-II to guide the selection. Furthermore, it incorporates a local search procedure which is based on information contained in the belief space. The proposed approach was assessed using several standard test problems and performance measures reported in the specialized literature. The results of the proposed multiobjective cultural algorithm were compared with respect to those obtained by NSGA-II. Our results indicate that the proposed approach had a better performance in most of the test problems adopted, which indicates the potential of this sort of approach for dealing with computationally expensive objective functions.