En el mundo real existen muchos problemas de optimización en diversas disciplinas dentro de las ciencias, la ingeniería y la industria. Muchos de estos problemas requieren de la optimización simultánea de varias funciones objetivo las cuales suelen estar en conflicto entre sí. A éstos se les conoce como Problemas de Optimización Multi-Objetivo y no tienen una solución única, sino un conjunto de ellas, las cuales representan los mejores compromisos posibles entre todos los objetivos (es decir, soluciones en las cuales no es posible mejorar un objetivo sin empeorar otro). A dicho conjunto se le denomina óptimos de Pareto y su imagen en el espacio de las funciones objetivo se conoce como frente de Pareto. Aunque existen diversas técnicas de programación matemática para resolver problemas multi-objetivo, éstas presentan varias limitantes, de entre las que destacan su sensibilidad a la forma y continuidad del frente de Pareto. Adicionalmente, la mayoría de estas técnicas suelen generar un elemento del conjunto de óptimos de Pareto por ejecución. Estas limitantes han motivado el uso de algoritmos evolutivos para resolver problemas multi-objetivo, pues presentan mayor generalidad y requieren poca información del problema. En años recientes, la incorporación de buscadores locales a algoritmos evolutivos multi-objetivo se ha vuelto un área atractiva para varios investigadores, dando pie a los denominados algoritmos meméticos multi-objetivo. Sin embargo, la mayor parte de este trabajo se ha enfocado a problemas discretos y a la fecha existe muy poca investigación en torno a la solución de problemas continuos. La motivación principal para desarrollar algoritmos meméticos multi-objetivo es acelerar la convergencia hacia el frente de Pareto verdadero. No obstante, el diseño de estos algoritmos dista de lo trivial, pues es importante diseñar buenos buscadores locales y saber equilibrar su uso con respecto al buscador global. Adicionalmente, muchos problemas del mundo real tienen funciones objetivo costosas, las cuales pueden resolverse más eficazmente utilizado Unidades de Procesamiento Gráfico (GPUs, por sus siglas en inglés), cuyo costo económico es mucho más bajo que el de otras tecnologías disponibles para implementar algoritmos paralelos. En esta tesis se utiliza el indicador de desempeño denominado Inverted Generational Distance plus (IGD+) para guiar el motor de búsqueda local de un algoritmo memético multi-objetivo, incorporando el uso de GPUs. Se proponen dos nuevos algoritmos basados en IGD+, los cuales se muestra que son competitivos con respecto a los algoritmos evolutivos multi-objetivo del estado del arte. El primero de ellos combina un optimizador global basado en el uso del hipervolumen y un motor de búsqueda local basado en IGD+. Esta primera propuesta se compara con respecto al S-Metric Selection Evolutionary Multiobjective Optimization Algorithm (SMS-EMOA), siendo capaz de superarlo. Debido a que el uso del hipervolumen resulta computacionalmente costoso, se propone realizar una implementación paralela de este algoritmo mediante el uso de GPUs. El segundo algoritmo propuesto en esta tesis consiste de una mejora del primero, de tal forma que puedan resolverse adecuadamente problemas multi-objetivo con frentes de Pareto complicados (p.ej., frentes de Pareto con geometrías irregulares). Esta segunda propuesta incorpora un mecanismo para guiar el proceso de optimización, el cual se adapta a cualquier forma geométrica del frente de Pareto. Este segundo algoritmo fue validado usando varios conjuntos de prueba, comparándose su desempeño con respecto al de nuestra primera propuesta. Adicionalmente, se le validó en un problema de diseño de vehículos en el que se busca maximizar la seguridad contra choques. El algoritmo propuesto no sólo es capaz de resolver éxitosamente una amplia variedad de problemas multi-objetivo, sino que también logra una aceleración significativa (de hasta 22 veces) mediante el uso de GPUs
Abstract
Many real-world optimization problems exist in a wide variety of disciplines within science, engineering and industry. Many of these problems require the simultaneous optimization of several objective functions which are normally in conflict with each other. These are the so-called Multi-Objective Optimization Problems and they do not have a single solution, but a set of them, representing the best possible trade-offs among all the objectives (i.e., solutions in which it is not possible to improve one objective without worsening another one). This is the so-called Pareto Optimal set, and its image in objective function space is known as the Pareto front. In spite of the existence of several mathematical programming techniques for solving multi-objective problems, they have several limitations, from which the main one is their sensitivity to the shape and continuity of the Pareto front. Additionally, most of these techniques generate a single element of the Pareto optimal set per run. These limitations have motivated the use of evolutionary algorithms for solving multi-objective problems, since they provide a greater generality and require little domain-specific information. In recent years, the incorporation of local search engines into multi-objective evolutionary algorithms has become an attractive area for several researchers, giving rise to the so-called multi-objective memetic algorithms. However, most of this work has focused on discrete problems and to date, there is very little research related to the solution of continuous problems. The main motivation to develop multiobjective memetic algorithms is to speed up convergence towards the true Pareto front. Nevertheless, the design of these algorithms is far from trivial, because it is important to design good local search engines and to know how to balance their use with respect to that of the global search engine. Additionally, many realworld problems can be solved in a more efficient manner using Graphics Processing Units (GPUs) which have a lower cost than that of other technologies available for implementing parallel algorithms. In this thesis, the performance indicator called Inverted Generational Distance plus (IGD+) is adopted to guide the local search engine of a multi-objective memetic algorithm, incorporating the use of GPUs. Two new algorithms based on IGD+ are proposed, both of which are found to be competitive with respect to state-of-the-art multi-objective evolutionary algorithms. The first algorithm combines a global search engine based on the use of the hypervolume and a local search engine based on IGD+. This first proposal is compared with respect to the S-Metric Selection Evolutionary Multi-objective Optimization Algorithm (SMS-EMOA), being able to outperform it. Since the use of the hypervolume involves a high computational cost, we propose a parallel implementation of this algorithm using GPUs. The second algorithm proposed in this thesis consists of an improved version of the first one, such that it can properly solve multi-objective problems with complicated Pareto fronts (e.g., Pareto fronts with irregular geometries). This second proposal incorporates a mechanism to guide the optimization process, which is able to adapt to any geometrical shape of the Pareto front. This second algorithm was validated using several test problems, comparing its performance with respect to that of our first proposed algorithm. Additionally, it was validated using a vehicle design problem in which the aim is to maximize safety against collisions. Our proposed algorithm is not only able to successfully solve a wide variety of multi-objective optimization problems, but it can also achieve a significant speed up (of up to 22 times) through the use of GPUs
