Unidad de Comunicación

El desarrollo de algoritmos metaheurísticos y la optimización evolutiva multiobjetivo fue el tema de la charla a cargo del doctor Carlos Artemio Coello Coello, investigador titular en el Centro de Investigaciones y Estudios Avanzados (CINVESTAV) del Instituto Politécnico Nacional (IPN), como parte del seminario Marcos Moshinksy, que conmemora una década desde el inicio de la entrega de las cátedras del mismo nombre y el centenario del nacimiento de dicho investigador.

Con la presentación titulada “Avances recientes en optimización evolutiva multiobjetivo”, el doctor Cátedra Marcos Moshinsky 2013-2014 habló sobre el área en la que ha trabajado, “desde 1994, cuando era estudiante de doctorado, que es la optimización evolutivamente objetivo”, como lo comentó.

El investigador con estudios de doctorado en ciencias de la computación por la Universidad de Tulane, en Estados Unidos, comenzó su charla con generalidades sobre la optimización multiobjetivo. “Probablemente sepamos que la optimización global implica encontrar la mejor solución posible en todo el espacio de búsqueda, sujeta a ciertas restricciones. En el caso multiobjetivo no tenemos una función objetivo, sino que tenemos dos o más que, además, están en conflicto entre sí en al menos algunas de ellas”, como definió el doctor Coello Coello. Por ejemplo, la optimización del diseño de un puente puede considerar reducir el costo y maximizar la seguridad de la estructura, dos objetivos que se contraponen.

Posteriormente, el doctor Coello Coello mencionó que existe más de una noción de optimalidad debido a que, al tener varias funciones objetivo en conflicto, no es posible usar la noción de óptimo en la optimización global. La más usada es la que propuso Francis Ysidro Edgeworth en 1881, en la que define el mejor compromiso posible entre dos objetivos en conflicto. Por otro lado, Vilfredo Pareto publicó en 1896 un curso de economía política en donde usa el término “ophelimity” que, a diferencia de Edgeworth, se refiere a cualquier cantidad de objetivos en conflicto. “Con el tiempo hubo algunas personas que comenzaron a llamarle <>, pero luego quitaron a Edgeworth a pesar de haber sido el primero en haber llegado a una definición”, comentó el investigador. “La definición es muy sencilla: si yo supongo que todos los objetivos se van a optimizar, esto siempre es posible, porque un objetivo que yo quiera maximizar lo puedo convertir a minimización; un vector de variables de decisión factible, es decir que cumpla con todas las restricciones, es un óptimo en el sentido de Pareto si no existe otro vector de variables de decisión factible tal que se cumplan estas dos condiciones: que sea menor o igual en todos los objetivos y estrictamente menor en al menos uno”, definió quien en 2017 fue listado como uno de los 300 científicos más citados en el mundo por la editorial Elsevier.

Una solución es un óptimo de Pareto si no puedo mejorar un objetivo sin empeorar otro. Si hay conflicto, se generarán un conjunto de soluciones. Ese conjunto, en el espacio de las variables, se conoce como el conjunto de óptimos de Pareto. Los vectores de esas soluciones contenidos en el conjunto se dice que son no dominados, para hacer referencia a las soluciones en el conjunto de óptimos de Pareto. Además, los valores de las funciones objetivo que corresponden al conjunto de óptimos de Pareto, constituyen el frente de Pareto.

Posterior al planteamiento de los antecedentes, su charla dio paso a la definición de los algoritmos evolutivos aplicados a los problemas multiobjetivo (AEMO). “Los algoritmos evolutivos son técnicas de búsqueda que adoptan un mecanismo de selección inspirado en el principio de la supervivencia del más apto de la teoría evolutiva de Darwin. Estos algoritmos son adecuados para resolver problemas de optimización multiobjetivo, pues pueden lidiar simultáneamente con un conjunto de soluciones posibles”, describió el doctor Coello Coello.

Esto permite encontrar varios miembros del conjunto de óptimos de Pareto en una sola ejecución del algoritmo, en vez de tener que realizar una serie de ejecuciones independientes, como en el caso de técnicas de programación matemática. Además, son menos susceptibles a la forma o continuidad del frente de Pareto.

Una vez esto, el investigador detalló el proceso de desarrollo de los AEMOs. Comenzó con la primera implementación de uno, que hizo David Schaffer en 1984, a pesar de que fue destacado en 1967 por Richard S. Rosenberg. Posteriormente, habló del trabajo desarrollado en los años siguientes y hasta nuestros días, haciendo mención de los algoritmos representantes de cada etapa, que incluye los recientes: MOEA/D (y sus variantes), algoritmos basados en indicadores de desempeño; IBEA, SMS-EMOA, HyPE; NSGA-III (y sus variantes). “En general, los AEMOs modernos consisten de dos componentes: un mecanismo de selección que normalmente, aunque no necesariamente, incorpora la optimalidad de Pareto; y un estimador de densidad, el cual es responsable de mantener diversidad en la población, a fin de evitar que el AEMO converja a una solución única”, comentó el doctor.

Luego de dar una definición de los tres tipos de AEMOs en uso común en la actualidad -que son los basados en optimalidad de Pareto, los basados en descomposición y los basados en indicadores-, el doctor habló de elementos como el estimador de densidad, la escalabilidad y el paralelismo para optimización multiobjetivo, estos dos últimos relevantes para la obtención de la Cátedra Marcos Moshinsky.

El doctor Coello Coello también habló de algunas aplicaciones, como la que se hizo en 2017 con la propuesta de esquemas que combinan técnicas de aprendizaje de máquina y optimización multiobjetivo para resolver problemas industriales de programación de horarios; o la que se propuso en 2018, con una extensión del MOEA/D, que se basa en distancias de referencia, para resolver problemas de optimización de portafolios de proyectos de software. De este último, explicó que, “el objetivo es que una empresa grande de software seleccione los portafolios de proyectos que obtengan el máximo retorno posible, con recursos limitados y en la presencia de muchas restricciones”.

Para finalizar, el investigador del CINVESTAV habló de las tendencias actuales, como el uso de esquemas subrogados para manejar funciones objetivo muy costosas o la hibridación de algoritmos evolutivos multiobjetivo con métodos de gradiente y métodos de búsqueda directos. Asimismo, enumeró algunos retos a futuro, como la necesidad de trabajar en la configuración automática de parámetros para algoritmos evolutivos multiobjetivo o la creación de nuevos AEMOs usando herramientas automatizadas.

La directora del Instituto, la doctora Cecilia Noguez Garrido, estuvo a cargo de la sesión, que contó con la presencia de distintos miembros de la Fundación Marcos Moshinsky.