Publication: Scalable multi-objective optimization
Loading...
Identifiers
Publication date
2011
Defense date
2011-03-29
Authors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This thesis is concerned with the three open in multi-objective optimization: (i) the development of strategies for dealing with problems with many objective functions; (ii) the comprehension and solution of the model-building issues of current MOEDAs, and; (iii) the formulation of stopping criteria for multi-objective optimizers. We argue about what elements of MOEDAs should be modified in order to achieve a substantial improvement on their performance and scalability. However, in order to supply a solid ground for that discussion, some other elements are to be discussed as well. In particular, this thesis: sketches the supporting theoretical corpus and the fundamentals of MOEA and MOEDA algorithms; analyzes the scalability issue of MOEAs from both theoretical and experimental points of view; discusses the possible directions of improvement for MOEAs’ scalability, presenting the current trends of research; gives reasons of why EDAs can be used as a foundation for achieving a sizable improvement with regard to the scalability issue; examines the model-building issue in depth, hypothesizing on how it affects MOEDAs performance; proposes a novel model-building algorithm, the model-building growing neural gas (MBGNG), which fulfill the requirements for a new approach derived from the previous debate, and; introduces a novel MOEDA, the multi-objective neural EDA, that is constructed using MB-GNG as foundation. The formulation of an strategy for stopping multi-objective optimizers became obvious and necessary as this thesis was developed. The lack of an adequate stopping criterion made the rendered any experimentation that had to do with many objectives a rather cumbersome task. That is why it was compulsory to deal with this issue in order to proceed with further studies. In this regard, the thesis: provides an updated and exhaustive state-of-the-art of this matter; examines the properties and characteristics that a given stopping criterion should exhibit; puts forward a new stopping criterion, denominated MGBM, after the authors last names, that has a small computational footprint, and; experimentally validates MGBM in a set of experiments. Theoretical discussions and algorithm proposals are experimentally contrasted with current state-of-the-art approaches when required. --------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Muchas actividades humanas están relacionadas con la elaboraciĂłn de artefactos cuyas caracterĂsticas, organizaciĂłn y/o costes de producciĂłn, etc., se deben ajustar en la manera más eficiente posible. Este hecho ha creado la necesidad de tener herramientas matemáticas y computacionales capaces de tratar estos problemas, lo cual ha impulsado el desarrollo de distintas áreas de investigaciĂłn interrelacionadas, como, por ejemplo, la optimizaciĂłn, programaciĂłn matemática, investigaciĂłn de operaciones, etc. El concepto de optimizaciĂłn se puede formular en tĂ©rminos matemáticos como el proceso de buscar una o más soluciones factibles que se correspondan con los valores extremos de una o varias funciones. La mayor parte de los problemas de optimizaciĂłn reales implican la optimizaciĂłn de más de una funciĂłn a la vez. Esta clase de problemas se conoce como problemas de optimizaciĂłn multi-objetivo (POM). Existe una clase de POM que es particularmente atractivo debido a su complejidad inherente: los denominados problemas de muchos objetivos. Estos son problemas con un nĂşmero relativamente elevado de funciones objetivo. Numerosos experimentos han mostrado que los mĂ©todos “tradicionales” no logran un desempeño adecuado debido a la relaciĂłn intensamente exponencial entre la dimensiĂłn del conjunto objetivo y la cantidad de recursos requeridos para resolver el problema correctamente. Estos problemas tienen una naturaleza poco intuitiva y, en particular, sus soluciones son difĂciles de visualizar por un tomador de decisiones humano. Sin embargo, son bastante comunes en la práctica (Stewart et al., 2008). La optimizaciĂłn multi-objetivo ha recibido una importante atenciĂłn por parte de la comunidad dedicada a los algoritmos evolutivos (Coello Coello et al., 2007). Sin embargo, se ha hecho patente la necesidad de buscar alternativas para poder tratar con los problemas de muchos objetivos. Los algoritmos de estimaciĂłn de distribuciĂłn (EDAs, por sus siglas en inglĂ©s) (Lozano et al., 2006) son buenos candidatos para esa tarea. Estos algoritmos se han presentado como una revoluciĂłn en el campo de la computaciĂłn evolutiva. Ellos sustituyen la aplicaciĂłn de operadores inspirados en la selecciĂłn natural por la sĂntesis de un modelo estadĂstico. Este modelo es muestreado para generar nuevos elementos y asĂ proseguir con la bĂşsqueda de soluciones. Sin embargo, los EDAs multi-objetivo (MOEDAs) no han logrado cumplir las expectativas creadas a priori. El leit motif de esta tesis se puede resumir en que la causa principal del bajo rendimiento MOEDAs se debe a los algoritmos de aprendizaje automático que se aplican en la construcciĂłn de modelos estadĂsticos. Los trabajos existentes hasta el momento han tomado una aproximaciĂłn de “caja negra” al problema de la construcciĂłn de modelos. Por esa razĂłn, se aplican mĂ©todos de aprendizaje automático ya existentes sin modificaciĂłn alguna, sin percatarse que el problema de la construcciĂłn de modelos para EDAs tiene unos requisitos propios que en varios casos son contradictorios con el contexto original de aplicaciĂłn de los mencionados algoritmos. En particular, hay propiedades compartidas por la mayorĂa de los enfoques de aprendizaje automático que podrĂan evitar la obtenciĂłn de una mejora sustancial en el resultado de los MOEDAs. Ellas son: el tratamiento incorrecto de los valores atĂpicos (outliers) en el conjunto de datos; tendencia a la pĂ©rdida de la diversidad de la poblaciĂłn, y; exceso de esfuerzo computacional dedicado a la bĂşsqueda de un modelo Ăłptimo. Estos problemas, aunque ya están presentes en los EDAs de un solo objetivo, se hacen patentes al escalar a problemas de varios objetivos y, en particular, a muchos objetivos. Además, con el aumento de la cantidad de objetivos con frecuencia esta situaciĂłn se ve agravada por las consecuencias de la “maldiciĂłn de la dimensionalidad”. La cuestiĂłn de los valores atĂpicos en los datos es un buen ejemplo de como la comunidad no ha notado esta diferencia. En el contexto tradicional del aprendizaje automático los valores extremos son considerados como datos ruidosos o irrelevantes y, por tanto, deben ser evitados. Sin embargo, los valores atĂpicos en los datos de la construcciĂłn de modelos representan las regiones reciĂ©n descubiertas o soluciones candidatas del conjunto de decisiĂłn y por lo tanto deben ser explorados. En este caso, los casos aislados debe ser al menos igualmente representados por el modelo con respecto a los que están formando grupos. Sobre la base de estos razonamientos se estructuran los principales resultados obtenidos en el desarrollo de la tesis. A continuaciĂłn se enumeran brevemente los mismos mencionando las referencias principales de los mismos. ComprensiĂłn del problema de la construcciĂłn de modelos en MOEDAs (MartĂ et al., 2010a, 2008b, 2009c). Se analiza que los EDAs han asumido incorrectamente que la construcciĂłn de modelos es un problema tradicional de aprendizaje automático. En el trabajo se muestra experimentalmente la hipĂłtesis. Growing Neural Gas: una alternativa viable para construcciĂłn de modelos (MartĂ et al., 2008c). Se propone el Model-Building Growing Neural Gas network (MB-GNG), una modificaciĂłn de las redes neuronales tipo Growing Neural Gas. MB-GNG tiene las propiedades requeridas para tratar correctamente la construcciĂłn de modelos. MONEDA: mejorando el desempeño de los MOEDAs (MartĂ et al., 2008a, 2009b, 2010c). El Multi-objective Optimization Neural EDA (MONEDA) fue ideado con el fin de hacer frente a los problemas arriba descritos de los MOEDAs y, por lo tanto, mejorar la escalabilidad de los MOEDAs. MONEDA utiliza MB-GNG para la construcciĂłn de modelos. Gracias a su algoritmo especĂfico de construcciĂłn de modelos, la preservaciĂłn de las Ă©lites de individuos de la poblaciĂłn y su mecanismo de sustituciĂłn de individuos MONEDA es escalable capaz de resolver POMs continuos de muchos objetivos con un mejor desepeño que algoritmos similares a un coste computacional menor. Esta propuesta fue nominada a mejor trabajo en GECCO’2008. MONEDA en problemas de alta complejidad (MartĂ et al., 2009d). En este caso se lleva a cabo una amplia experimentaciĂłn para comprender como las caracterĂsticas de MONEDA provocan una mejora en el desempeño del algoritmo, y si sus resultados mejoran los obtenidos de otros enfoques. Se tratan problemas de alta complejidad. Estos experimentos demostraron que MONEDA produce resultados sustancialmente mejores que los algoritmos similares a una menor coste computacional. Nuevos paradigmas de aprendizaje: MARTEDA (MartĂ et al., 2010d). Si bien MB-GNG y MONEDA mostraron que la vĂa del tratamiento correcto de la construcciĂłn de modelos era una de las formas de obtener mejores resultados, ellos no evadĂan por completo el punto esencial: el paradigma de aprendizaje empleado. Al combinar un paradigma de aprendizaje automático alternativo, en particular, la TeorĂa de Resonancia Adaptativa, se trata a este asunto desde su raĂz. En este respecto se han obtenido algunos resultados preliminares alentadores. Criterios de parada y convergencia (MartĂ et al., 2007, 2009a, 2010e). Con la realizaciĂłn de los experimentos anteriores nos percatamos de la falta de de un criterio de parada adecuado y que esta es un área inexplorada en el ámbito de la investigaciĂłn en algoritmos evolutivos multi-objectivo. Abordamos esta cuestiĂłn proponiendo una serie de criterios de parada que se han demostrado efectivos en problemas sintĂ©ticos y del mundo real.
Muchas actividades humanas están relacionadas con la elaboraciĂłn de artefactos cuyas caracterĂsticas, organizaciĂłn y/o costes de producciĂłn, etc., se deben ajustar en la manera más eficiente posible. Este hecho ha creado la necesidad de tener herramientas matemáticas y computacionales capaces de tratar estos problemas, lo cual ha impulsado el desarrollo de distintas áreas de investigaciĂłn interrelacionadas, como, por ejemplo, la optimizaciĂłn, programaciĂłn matemática, investigaciĂłn de operaciones, etc. El concepto de optimizaciĂłn se puede formular en tĂ©rminos matemáticos como el proceso de buscar una o más soluciones factibles que se correspondan con los valores extremos de una o varias funciones. La mayor parte de los problemas de optimizaciĂłn reales implican la optimizaciĂłn de más de una funciĂłn a la vez. Esta clase de problemas se conoce como problemas de optimizaciĂłn multi-objetivo (POM). Existe una clase de POM que es particularmente atractivo debido a su complejidad inherente: los denominados problemas de muchos objetivos. Estos son problemas con un nĂşmero relativamente elevado de funciones objetivo. Numerosos experimentos han mostrado que los mĂ©todos “tradicionales” no logran un desempeño adecuado debido a la relaciĂłn intensamente exponencial entre la dimensiĂłn del conjunto objetivo y la cantidad de recursos requeridos para resolver el problema correctamente. Estos problemas tienen una naturaleza poco intuitiva y, en particular, sus soluciones son difĂciles de visualizar por un tomador de decisiones humano. Sin embargo, son bastante comunes en la práctica (Stewart et al., 2008). La optimizaciĂłn multi-objetivo ha recibido una importante atenciĂłn por parte de la comunidad dedicada a los algoritmos evolutivos (Coello Coello et al., 2007). Sin embargo, se ha hecho patente la necesidad de buscar alternativas para poder tratar con los problemas de muchos objetivos. Los algoritmos de estimaciĂłn de distribuciĂłn (EDAs, por sus siglas en inglĂ©s) (Lozano et al., 2006) son buenos candidatos para esa tarea. Estos algoritmos se han presentado como una revoluciĂłn en el campo de la computaciĂłn evolutiva. Ellos sustituyen la aplicaciĂłn de operadores inspirados en la selecciĂłn natural por la sĂntesis de un modelo estadĂstico. Este modelo es muestreado para generar nuevos elementos y asĂ proseguir con la bĂşsqueda de soluciones. Sin embargo, los EDAs multi-objetivo (MOEDAs) no han logrado cumplir las expectativas creadas a priori. El leit motif de esta tesis se puede resumir en que la causa principal del bajo rendimiento MOEDAs se debe a los algoritmos de aprendizaje automático que se aplican en la construcciĂłn de modelos estadĂsticos. Los trabajos existentes hasta el momento han tomado una aproximaciĂłn de “caja negra” al problema de la construcciĂłn de modelos. Por esa razĂłn, se aplican mĂ©todos de aprendizaje automático ya existentes sin modificaciĂłn alguna, sin percatarse que el problema de la construcciĂłn de modelos para EDAs tiene unos requisitos propios que en varios casos son contradictorios con el contexto original de aplicaciĂłn de los mencionados algoritmos. En particular, hay propiedades compartidas por la mayorĂa de los enfoques de aprendizaje automático que podrĂan evitar la obtenciĂłn de una mejora sustancial en el resultado de los MOEDAs. Ellas son: el tratamiento incorrecto de los valores atĂpicos (outliers) en el conjunto de datos; tendencia a la pĂ©rdida de la diversidad de la poblaciĂłn, y; exceso de esfuerzo computacional dedicado a la bĂşsqueda de un modelo Ăłptimo. Estos problemas, aunque ya están presentes en los EDAs de un solo objetivo, se hacen patentes al escalar a problemas de varios objetivos y, en particular, a muchos objetivos. Además, con el aumento de la cantidad de objetivos con frecuencia esta situaciĂłn se ve agravada por las consecuencias de la “maldiciĂłn de la dimensionalidad”. La cuestiĂłn de los valores atĂpicos en los datos es un buen ejemplo de como la comunidad no ha notado esta diferencia. En el contexto tradicional del aprendizaje automático los valores extremos son considerados como datos ruidosos o irrelevantes y, por tanto, deben ser evitados. Sin embargo, los valores atĂpicos en los datos de la construcciĂłn de modelos representan las regiones reciĂ©n descubiertas o soluciones candidatas del conjunto de decisiĂłn y por lo tanto deben ser explorados. En este caso, los casos aislados debe ser al menos igualmente representados por el modelo con respecto a los que están formando grupos. Sobre la base de estos razonamientos se estructuran los principales resultados obtenidos en el desarrollo de la tesis. A continuaciĂłn se enumeran brevemente los mismos mencionando las referencias principales de los mismos. ComprensiĂłn del problema de la construcciĂłn de modelos en MOEDAs (MartĂ et al., 2010a, 2008b, 2009c). Se analiza que los EDAs han asumido incorrectamente que la construcciĂłn de modelos es un problema tradicional de aprendizaje automático. En el trabajo se muestra experimentalmente la hipĂłtesis. Growing Neural Gas: una alternativa viable para construcciĂłn de modelos (MartĂ et al., 2008c). Se propone el Model-Building Growing Neural Gas network (MB-GNG), una modificaciĂłn de las redes neuronales tipo Growing Neural Gas. MB-GNG tiene las propiedades requeridas para tratar correctamente la construcciĂłn de modelos. MONEDA: mejorando el desempeño de los MOEDAs (MartĂ et al., 2008a, 2009b, 2010c). El Multi-objective Optimization Neural EDA (MONEDA) fue ideado con el fin de hacer frente a los problemas arriba descritos de los MOEDAs y, por lo tanto, mejorar la escalabilidad de los MOEDAs. MONEDA utiliza MB-GNG para la construcciĂłn de modelos. Gracias a su algoritmo especĂfico de construcciĂłn de modelos, la preservaciĂłn de las Ă©lites de individuos de la poblaciĂłn y su mecanismo de sustituciĂłn de individuos MONEDA es escalable capaz de resolver POMs continuos de muchos objetivos con un mejor desepeño que algoritmos similares a un coste computacional menor. Esta propuesta fue nominada a mejor trabajo en GECCO’2008. MONEDA en problemas de alta complejidad (MartĂ et al., 2009d). En este caso se lleva a cabo una amplia experimentaciĂłn para comprender como las caracterĂsticas de MONEDA provocan una mejora en el desempeño del algoritmo, y si sus resultados mejoran los obtenidos de otros enfoques. Se tratan problemas de alta complejidad. Estos experimentos demostraron que MONEDA produce resultados sustancialmente mejores que los algoritmos similares a una menor coste computacional. Nuevos paradigmas de aprendizaje: MARTEDA (MartĂ et al., 2010d). Si bien MB-GNG y MONEDA mostraron que la vĂa del tratamiento correcto de la construcciĂłn de modelos era una de las formas de obtener mejores resultados, ellos no evadĂan por completo el punto esencial: el paradigma de aprendizaje empleado. Al combinar un paradigma de aprendizaje automático alternativo, en particular, la TeorĂa de Resonancia Adaptativa, se trata a este asunto desde su raĂz. En este respecto se han obtenido algunos resultados preliminares alentadores. Criterios de parada y convergencia (MartĂ et al., 2007, 2009a, 2010e). Con la realizaciĂłn de los experimentos anteriores nos percatamos de la falta de de un criterio de parada adecuado y que esta es un área inexplorada en el ámbito de la investigaciĂłn en algoritmos evolutivos multi-objectivo. Abordamos esta cuestiĂłn proponiendo una serie de criterios de parada que se han demostrado efectivos en problemas sintĂ©ticos y del mundo real.
Description
Keywords
Multi-objective optimization, MOEDA