Hoy en día, en muchas aplicaciones del mundo real relacionadas con la industria, finanzas y otras ramas se requiere el optimizar múltiples objetivos al mismo tiempo. Los problemas de optimización multi-objetivo(POM) representan tales problemas donde múltiples objetivos deben optimizarse de forma concurrente. Además, existen ciertos tipos de problemas relacionados con aplicaciones del mundo real donde además de optimizar múltiples objetivos se requiere considerar el efecto de parámetros externos dentro del proceso de optimización. Estos parámetros externos pueden representar por ejemplo las condiciones del ambiente como el clima, temperatura o viento. Para este caso en particular la condiciones ambientales no pueden ser optimizadas ni tampoco ignoradas dado que pueden afectar a los objetivos si un cambio se llega a presentar. Un problema de optimización multi-objetivo dependiente de parámetros (POMP) consiste en un POM donde adicionalmente algunos parámetros externos 2 Rl no pueden ser incluidos dentro del diseño de un objeto (por ejemplo, el viento no puede ser incluido dentro del diseño de un carro óptimo). Durante la última década los algoritmos evolutivos multi-objetivo (AEMOs) se volvieron populares para el tratamiento de POMs. Entre los diversos AEMOs, hay una tendencia reciente dentro del diseño de estos algoritmos de incluir indicadores de desempeño dentro del mecanismo de selección o como estimadores de densidad. Estos indicadores de desempeño son herramientas que miden la calidad de un aproximación producida por un AEMO, por lo tanto, al incluir los indicadores de desempeño dentro del proceso de optimización se mejora la calidad de la aproximación generada de acuerdo al indicador seleccionado. Varias ventajas de estos algoritmos incentivan su uso para el tratamiento de POMs, sin embargo, también existen ciertas desventajas al utilizarlos. Por ejemplo, generalmente los AEMOs tienden a converger lentamente, lo que es una desventaja severa para este tipo de algoritmos.
Este problema provoca el uso de un alto número de evaluaciones de función del POM para obtener una representación adecuada del conjunto de interés. Como posible solución a este problema, se propuso el uso de estrategias meméticas donde un AEMO es combinado con una técnica de vi búsqueda local para mejorar su desempeño. Finalmente, como se menciono anteriormente, existen una gran variedad de AEMOs para el tratamiento de POMs, sin embargo, para el caso de los POMPs existe una escasez de técnicas especializadas diseñadas para obtener un conjunto de soluciones del problema completo. A lo largo de este trabajo de tesis, nos enfocaremos en el tratamiento numérico de POMs y POMPs. Primeramente, presentaremos dos técnicas de búsqueda local el método de búsqueda dirigida basado en hypervolumen (MBDH) y el método de Newton basado en hypervolumen (MNH). Ambas técnicas incorporán el uso del indicador del indicador de desempeño hypervolumen para mejorar la convergencia y la calidad de las aproximaciones generadas bajo este indicador. Una característica importante de ambas técnicas es que fueron diseñadas para conjuntos y no solamente para un mejorar un solo punto. Dicha característica convierte ambas técnicas en candidatos perfectos para ser combinados junto con un AEMO. Posteriormente, presentaremos dos estrategias meméticas las cuales integran tanto al MBDH como al MNH. Las estrategias meméticas desarrolladas muestran alcanzar de forma más rápida el conjunto solución y de igual formar mejorar el valor del indicador hypervolume de la aproximación final. Lo anterior incluso es realizado utilizando un número menor de evaluaciones de función. Por último, para contribuir a reducir la falta de técnicas para el tratamiento de POMPs, presentaremos un algoritmo evolutivo basado en descomposición. Esta técnica incluirá observaciones hechas en un estudio presentado dentro de esta tesis sobre el comportamiento de la búsqueda local estocástica dentro de los POMPs. El algoritmo demuestra ser capaz de obtener una aproximación del conjunto de solución completo explotando la interacción existente entre los elementos de la población actual inclusive si ellos pertenecen a un valor de diferente.
Abstract
Nowadays, many real world applications related to industry, medicine, finance, among others require optimizing multiple objectives at the same time. A multiobjective optimization problem (MOP) represents such a problem of optimizing not only one but multiple objectives concurrently. Even more, there is a certain type of problems related also to real world applications in which furthermore of optimizing multiple objectives one has to consider the effect of external parameters on the optimization process. These external parameters can represent for instance environment conditions such as weather, temperature or side wind. In this case, environment conditions cannot be optimized nor neglected since they can affect the objectives if a change is presented. A parameter dependent multi-objective optimization problem (PMOP) consists of a MOP where in addition several external parameters 2 Rl cannot be influenced for the design of an object (e.g., the side wind in the design of an ‘optimal’ car). During the last decade, multi-objective evolutionary algorithms (MOEAs) has become very popular for the treatment of MOPs. Among them, there is a recent trend in the design of algorithms which consist in including performance indicators into the selection mechanism or as a density estimator. These performance indicators are tools to measure the quality of the approximation set produced by a MOEA, then by including them into the optimization process one, can improve the quality of our approximation according to the selected indicator. Many advantages of these algorithms encourage their use for the treatment of MOPs, however, they still have drawbacks. For instance in general, MOEAs tend to converge slowly, what is a severe drawback of this kind of algorithms. This drawback leads to use a relatively high number of function evaluations to obtain a suitable representation of the set of interest. As a possible remedy, researchers have proposed the use of memetic strategies where a MOEA is hybridized with a local search technique in order to improve its performance. Finally, as we mentioned before, there is a big variety of MOEAs which address the treatment of MOPs, nevertheless, in the case of PMOPs, there is still a lack of specialized techniques designed for solving them as a whole.
Throughout this thesis work, we aim for the numerical treatment of both multiobjective and parameter dependent multi-objective optimization problems. First, we present two different local search techniques the hypervolume based directed search (HVDS) and the hypervolume Newton method (HNM). Both techniques incorporate the use of the hypervolume performance indicator to improve the convergence and also the quality of the approximation according to this indicator. A remarkable property of both techniques is that they are designed for sets and not exclusively for a single point which makes them the perfect candidates to be coupled with a MOEA. Next, two memetic strategies are presented which integrate HVDS and HNM, respectively. The presented memetic strategies show to reach faster the solution set of a MOP and also to improve the hypervolume indicator value of the produced approximation, even using fewer function evaluations. Finally, in order to fill the gap of evolutionary algorithms to tackle PMOPs as a whole, we present the PMOEA/D. This technique incorporates observations made over stochastic local search within PMOPs presented in this thesis work. The algorithm shows to be able to compute an approximation of the whole solution set by exploiting the interactions between all the elements in the current population even if they belong to a different value.
