Departamento de Computación

Una amplia variedad de problemas complejos del mundo real son de naturaleza multiobjetivo y su solución implica encontrar un conjunto de variables de decisión que representen los mejores compromisos entre todos sus objetivos. Los Algoritmos Evolutivos Multi-Objetivo (AEMOs) son técnicas poderosas de búsqueda, inspiradas en ideas derivadas de procesos biológicos, que son adecuadas para encontrar soluciones casi óptimas para este tipo de problemas. Usualmente, los AEMOs dirigen su búsqueda por medio de una única heurística, que puede ser una regla, componente o proceso. Un fenómeno común es que los AEMOs son exitosos en la resolución de un tipo particular de problema. Sin embargo, al aplicarlos a nuevos problemas o instancias ligeramente diferentes, los AEMOs pueden ver degradado su desempeño. Por esta razón, una nueva tendencia es que los AEMOs seleccionen la heurística más apropiada de un conjunto de heurísticas disponibles. Este paradigma se conoce como hiper-heurística y se ha promovido con el objetivo de proporcionar metodologías de búsqueda de aplicación general. Sin embargo, al usar hiper-heurísticas surge la problemática de que éstas pueden requerir mucho tiempo de ejecución para ciertas aplicaciones y por lo tanto surge la necesidad de utilizar paralelismo. En esta tesis, proponemos diferentes hiper-heurísticas paralelas multi-objectivo, así como un marco de software para su desarrollo. Los enfoques propuestos se comparan con respecto a los AEMOs de última generación que adoptan varios problemas de referencia y medidas de rendimiento que normalmente se utilizan en la literatura especializada. Nuestros resultados experimentales indican que nuestras propuestas obtienen mejores resultados en la mayoría de los casos, siendo aplicables para una amplia gama de problemas complicados y también para problemas que tienen cuatro o más objetivos (es decir, los denominados problemas de optimización con muchos objetivos).

Abstract

A wide variety of complex real-world problems are multi-objective in nature, and their solution involves finding a set of decision variables that represent the best possible trade-offs among all their objectives. Multi-Objective Evolutionary Algorithms (MOEAs) are powerful search techniques, which are inspired by ideas derived from biological science, being suitable for finding near-optimal solutions for such types of problems. Usually, MOEAs rely on the guidance of a single heuristic, which can be a rule, component or process. A common phenomenon is that MOEAs are successful in solving a particular kind of problem. However, when applying them to new problems or slightly modified instances, MOEAs may face difficulties in their performance. For this reason, a new trend is to leave MOEAs the task of selecting the most appropriate heuristic from a pool of available heuristics. This paradigm is known as hyper-heuristic and has been promoted with the aim to provide generally applicable search methodologies. Another issue is that using hyper-heuristics can be very time-consuming for certain applications and therefore the need of parallelism. In this thesis, we propose different parallel hyper-heuristics for multi-objective optimization, and a software framework for their development. The proposed approaches are compared with respect to state-of-the-art MOEAs adopting several benchmark problems and performance measures normally used in the specialized literature. Our experimental results indicate that our proposals obtain better results in most cases, being applicable for a wide range of complicated problems, and also for problems having four or more objectives (i.e., the so-called many-objective optimization problems).