Algoritmos genéticos en optimización multiobjetivo

En la tesis de maestría de Von Lücken, publicada el año 2003 con el título “Algoritmos evolutivos para optimización multiobjetivo: Un estudio comparativo en un ambiente paralelo asíncrono”, se menciona que la falta de métodos determinísticos eficientes y eficaces para la resolución de problemas con objetivos múltiples, motivó la búsqueda de métodos alternativos. El notable éxito obtenido por los algoritmos evolutivos en optimización monobjetivo y las características propias de los mismos despertaron el interés de los investigadores en utilizarlos en optimización multiobjetivo. La optimización evolutiva multiobjetivo es un área de investigación muy importante tanto para científicos como para ingenieros, no sólo por que la mayor parte de los problemas consideren por naturaleza objetivos múltiples, sino también porque aún quedan por resolver un sin número de interrogantes en esta disciplina.

Si bien la noción de búsqueda genética para la exploración de soluciones óptimas en problemas con varios objetivos se remonta a fines de la década de los años sesenta, los primeros algoritmos evolutivos que consideraban de forma simultánea objetivos múltiples se desarrollaron recién a inicios de los años noventa. Como una muestra de lo incipiente del área, el primer congreso internacional de optimización evolutiva multiobjetivo se realizó en marzo del año 2001, reportado en las actas de la “Primera Conferencia sobre Algoritmos Evolutivos en Optimización Monobjetivo”. Zitzler y sus colegas, en el artículo publicado el año 2001 con el título “Comparación de algoritmos evolutivos multiobjetivo: Resultados empíricos”, mencionan que a pesar de esto, en poco tiempo, la computación evolutiva multiobjetivo, se ha establecido como el método para aproximar el frente Pareto-óptimo en problemas de este tipo. Esto se debe fundamentalmente al paralelismo intrínseco de los algoritmos evolutivos que les permite explorar similaridades entre las soluciones de forma eficiente y a la capacidad de capturar varias soluciones Pareto-óptimas en una única corrida de optimización. Los diferentes métodos para trabajar con objetivos múltiples utilizando algoritmos evolutivos se pueden clasificar, en forma sencilla, en técnicas de primera y segunda generación. Pertenecen a la primera generación las propuestas iniciales que no consideran conceptos de Pareto. Así mismo, ésta generación abarca a los primeros algoritmos evolutivos multiobjetivo basados en Pareto que no incluyen mecanismos para la preservación de las buenas soluciones encontradas durante el proceso evolutivo, tal como el elitismo. La segunda generación está caracterizada básicamente por algoritmos basados en Pareto y que incorporan alguna forma de elitismo.

Coello, en el artículo publicado el año 2000 con el título “Estudio actualizado de técnicas de optimización multiobjetivo basadas en algoritmos genéticos”, se menciona que puesto que los algoritmos genéticos requieren información escalar sobre el valor de adaptabilidad de los individuos, no es extraño que los primeros enfoques evolutivos para lidiar con objetivos múltiples se basen en la idea de combinar un algoritmo genético simple con métodos de escalarización de la función objetivo. Así, estos primeros enfoques se encargaban de optimizar la función agregada en vez de optimizar la verdadera función multiobjetivo. Schaffer, en la tesis doctoral publicada el año 1984 con el título “Optimización de objetivos múltiples con algoritmos genéticos evaluados por vector”, presentó el primer algoritmo evolutivo que no utiliza funciones de agregación para resolver problemas multiobjetivo, al que llamó “Algoritmo genético evaluado por vector”. Fonseca y Fleming, en el reporte técnico publicado el año 1994 con el título “Una vista de algoritmos evolutivos en optimización multiobjetivo”, mencionan que este algoritmo utiliza un procedimiento evolutivo que básicamente divide una población genética en subpoblaciones, en las que se considera el valor de adaptación de los individuos de acuerdo a un objetivo distinto para cada subpoblación y realiza el cruzamiento mezclando individuos de distintas subpoblaciones. El resultado final del procedimiento de selección del algoritmo genético evaluado por vector corresponde al promedio de los valores de cada uno de los objetivos.

A pesar que Schaffer y Grefenstette tuvieron algún éxito, especialmente para la resolución de problemas en aprendizaje automático, reportadas en el artículo publicado el año 1985 con el título “Aprendizaje multiobjetivo mediante algoritmos genéticos”, el método propuesto resultó ineficiente para explorar espacios de objetivos no convexos comportándose bien sólo en una dimensión. Von Lücken, en la tesis de maestría citada, señala que muchos problemas del mundo real implican la optimización simultánea de objetivos diferentes, en ocasiones laboriosos de evaluar, y que a menudo resultan contradictorios entre sí. Mientras que en problemas con un único objetivo la solución óptima habitualmente está bien definida, no sucede lo mismo en los problemas de optimización con múltiples objetivos. En vez de un único óptimo, existe un conjunto de soluciones equiparables, que recibe el nombre de conjunto óptimo de Pareto. La mayoría de los problemas que se plantean en el mundo real presentan múltiples objetivos contrapuestos. Por tanto, uno de los objetivos que persigue la industria es desarrollar algoritmos de optimización multiobjetivo capaces de enfrentarse a este tipo de problemas. En este sentido, las técnicas heurísticas están alcanzando cada vez mayor auge. De entre todas las técnicas heurísticas, los algoritmos evolutivos han experimentado un gran desarrollo, por su capacidad para encontrar soluciones a problemas muy complejos en un tiempo razonable.