Departamento de Computación

En un problema de optimización multiobjetivo (POM) la tarea es optimizar varios objetivos concurrentemente que usualmente están en conflicto. Dado que la solución P de tales POMs está dada por un conjunto de k-1 dimensiones en donde k es el número de objetivos involucrados, la aproximación de P no es siempre deseada o incluso posible, particularmente en problemas de muchos objetivos, i.e., problemas con tres o más objetivos. En cambio, tiene sentido concentrarse en puntos particulares o regiones del conjunto solución. En caso de que el tomador de decisiones tenga una cierta idea sobre el desempeño esperado de su producto, se pueden usar los problemas de punto de referencia para encontrar soluciones que se parezcan lo más posible a sus preferencias (dadas por los puntos de referencia). Las técnicas de programación matemática (PM) actuales para puntos de referencia (e.g. el problema de las métricas ponderadas) trabajan sólo con un punto de referencia a la vez. Más aún, pueden garantizar soluciones óptimas, pero sólo localmente. Por otro lado, los algoritmos evolutivos (AE) (e.g. RNSGA-II) son beneficiosos para el tratamiento de tales problemas en particular si hay múltiples puntos de referencia y/o si los objetivos son altamente multimodales, sin embargo, sufren de la desventaja general de velocidad de convergencia lenta. Por tanto, se vuelve un paso natural hibridar un AE con una técnica de PM para tomar ventaja de ambos enfoques. En este trabajo, investigamos el método de Búsqueda Dirigida (Directed Search) para problemas de punto de referencia y discutimos su integración como motor de búsqueda local dentro de algoritmos evolutivos, concretamente, del algoritmo estado del arte RNSGA-II. Resultados numéricos en varios problemas estándar y de ingeniería (con y sin restricciones, unimodales y multimodales) indican que el nuevo algoritmo memético incrementa significativamente el desempeño de su algoritmo base.

Abstract

The task in a multi objective optimization problem (MOP) is to optimize several objectives concurrently which are usually in conflict. Since the solution P of such MOPs is typically given by an entire set of dimension k-1, where k is the number of objectives involved, the entire approximation of P is not always desired or even possible, particularly in many objective problems, i.e., problems with three or more objectives. Instead, it makes sense to concentrate on particular points or regions of the solution set. In case the decision maker has a certain idea about the expected performance of his/her product, reference point problems can be used to find solutions that more closely resemble their preferences (given by reference points). Current mathematical programming (MP) techniques for reference point problems (e.g. the weighted metrics problem) work with only one reference point at a time. Further, they can guarantee optimal solutions, but only locally. On the other hand, evolutionary algorithms (EAs) (e.g., RNSGA-II) are advantageous for the treatment of such problems in particular if there are multiple reference points and/or the objectives are highly multimodal. However, they suffer the general drawback of relative slow convergence rates. Hence, it becomes a natural step to hybridize an EA with MP techniques to take advantage of both approaches. In this work, we investigate the Directed Search method for reference point problems and discuss its integration as a local search engine into evolutionary algorithms, namely, the state-of-the-art RNSGA-II. Numerical results on several benchmark and engineering problems (constrained and unconstrained, unimodal and multimodal) indicate that the novel memetic algorithm significantly increases the performance of its base algorithm