Departamento de Computación

En un problema `clásico' de optimización multi-objetivo (POM), la tarea principal es el optimizar varios objetivos al mismo tiempo. El conjunto solución de un POM, llamado conjunto de Pareto, típicamente forma un objeto de (k-1) dimensiones, donde k es el número de objetivos involucrados en el problema. Un problema de optimización multi-objetivo dependiente de parámetros (POMP) se constituye de un problema multi-objetivo donde algunos parámetros lambda en R^l$ son externos y no pueden ser influenciados por el diseño de un objeto (por ejemplo, la dirección del viento en el diseño de un carro `óptimo'). El conjunto solución de un POMP es en la mayoría de los casos de k-1+l dimensiones. Recientemente, los algoritmos evolutivos basados en indicadores (AEBIs) han capturado el interés de muchos investigadores para tratar POMs, esto es debido a que tales algoritmos entregan una buena aproximación del conjunto de soluciones y usualmente tienen un mejor desempeño comparado con algoritmos basados en dominancia de Pareto. Sin embargo, estos métodos continúan teniendo la desventaja de necesitar un alto número de evaluaciones de la función objetivo para obtener un representación adecuada del conjunto de soluciones. El alcance de este trabajo de tesis es el tratamiento numérico de POMs y POMPs utilizando búsqueda local y estrategias meméticas. Para llevar a cabo esto, el reciente desarrollado Método de Búsqueda Dirigida (MBD) (en inglés `Directed Search Method (DS)') será adaptado a cada contexto. En el caso de POMPs, se adaptará el MBD para realizar un movimiento sobre el espacio $\lambda$, contando o no con la información del gradiente. Finalmente para los POMs, el objetivo es adaptar el MBD dentro del contexto de aproximaciones utilizando el hipervolumen, y de esa manera solucionar el problema de la `lenta convergencia'. Se presentará un nuevo algoritmo de búsqueda local, el cual será integrado dentro de un algoritmo basado en el hipervolumen, para dar lugar a un nuevo algoritmo memético. Mostraremos que estas nuevas estrategias puede ser altamente competitivas considerando algoritmos del estado del arte sobre estos campos.

Abstract

In a `classical' multi-objective optimization problem (MOP) the task is to optimize several conflicting objectives concurrently. The solution set of a MOP, the so-called Pareto set, typically forms a (k-1)-dimensional manifold, where k is the number of objectives involved in the MOP. A parameter dependent multi-objective optimization problem (PMOP) consists of a MOP where in addition several parameters lambda in R^l are external and cannot be influenced for the design of an object (e.g., the side wind in the design of an `optimal' car). The solution set of a PMOP is typically k -1 + l dimensional. Recently, indicator based evolutionary algorithms (IBEAs) have caught the interest of many researchers for the treatment of MOPs, since they deliver the desired approximation of the solution set and due to a usually better performance compared to dominance based algorithms. Nevertheless, these methods still suffer the drawback that many function evaluations are required to obtain a suitable representation of the solution set. The scope of this thesis project is the numerical treatment of both MOPs and PMOPs by means of local search and memetic strategies. For this, the recently developed Directed Search method will be adapted to the given contexts. In the case of PMOPs, we adapt the DS to perform a movement over $\lambda$-space with and without gradient information. Finally, for MOPs we aim to adapt the DS for the context of hypervolume approximations to overcome the problem of `slow convergence'. We present a new local search algorithm and a new memetic algorithm using the SMS-EMOA. We will show that the novel local search strategies and the new memetic strategy will be highly competitive to state-of-the-art algorithms in these fields.