Mejorando la Optimización con Algoritmos Asistidos por Suplantación

Cuando tratamos de encontrar las mejores soluciones a problemas complejos, muchas veces nos topamos con lo que llamamos problemas de optimización costosos. Estos problemas requieren mucho tiempo y recursos para evaluar cada posible solución a fondo. Los Algoritmos Evolutivos asistidos por sustitutos (SAEAs) han surgido como herramientas útiles para enfrentar estos desafíos. Combinan las fortalezas de los algoritmos evolutivos tradicionales con modelos rentables que pueden predecir resultados sin hacer todos los cálculos.

Este estudio se centra en mejorar los SAEAs utilizando soluciones que todavía no se han evaluado. La idea principal es mejorar la manera en que seleccionamos nuevas soluciones en el Proceso de Optimización. El método tradicional evalúa solo un número limitado de soluciones, lo que puede reducir la calidad general de las soluciones obtenidas. Este documento sugiere un método para utilizar de manera eficiente las soluciones no evaluadas con el fin de mejorar el proceso de optimización.

#Contexto

#Problemas de Optimización Costosos

Los problemas de optimización costosos surgen en muchos campos, como la ingeniería, las finanzas y la investigación científica. Estos problemas a menudo implican funciones complejas que son difíciles de evaluar rápidamente. Por ejemplo, una función puede requerir simulaciones extensas o pruebas de laboratorio, lo que hace impracticable evaluar cada solución posible. Por lo tanto, se necesita un mejor enfoque para navegar estos desafíos.

#Algoritmos Evolutivos

Los algoritmos evolutivos se usan comúnmente para encontrar soluciones óptimas a problemas difíciles. Imitan el proceso de selección natural, utilizando técnicas como reproducción, mutación y selección para evolucionar soluciones con el tiempo. Aunque son herramientas poderosas, tienen sus limitaciones cuando se aplican a problemas de optimización costosos. Un problema importante es que a menudo no pueden permitirse evaluar cada solución candidata a fondo.

#Modelos Sustitutos

Para sortear los altos costos de evaluar soluciones directamente, se utilizan modelos sustitutos. Estos modelos aproximan la función real que necesita ser optimizada, permitiendo evaluaciones más rápidas. Pueden ser entrenados utilizando datos de soluciones previamente evaluadas para predecir el rendimiento de soluciones no evaluadas. Al hacer esto, los modelos sustitutos pueden ayudar a guiar la búsqueda de mejores soluciones sin necesidad de evaluar cada una en detalle.

#Declaración del Problema

Uno de los principales desafíos con los SAEAs actuales es la falta de Diversidad en la población de soluciones. Cuando solo se evalúa un número pequeño de soluciones por generación, la población puede volverse similar, lo que lleva a un rendimiento deficiente. Esto resulta en soluciones descendientes que no exploran el espacio de búsqueda de manera efectiva.

Este documento aborda este problema proponiendo un marco que integra soluciones no evaluadas en el proceso de selección. Al usar modelos sustitutos, podemos identificar soluciones prometedoras sin necesidad de evaluar cada una de ellas. Este enfoque no solo ahorra recursos computacionales, sino que también aumenta la diversidad de la población, lo cual es crucial para una optimización efectiva.

#Metodología

#Marco Propuesto

El marco propuesto utiliza soluciones no evaluadas junto con soluciones evaluadas para generar nuevas soluciones descendientes. En cada generación, se selecciona la mejor solución evaluada para una evaluación real. Junto con esto, algunas soluciones no evaluadas de alto potencial se utilizan directamente para producir nuevas soluciones sin necesidad de evaluación. Este enfoque dual mejora la exploración del espacio de búsqueda mientras mantiene la eficiencia.

#Modelos Sustitutos

Para asegurar una selección efectiva tanto de soluciones evaluadas como no evaluadas, se introducen dos tipos de modelos sustitutos. Estos modelos se centran en entender la relación entre soluciones en lugar de evaluarlas de forma aislada.

1. Criterio Basado en Fitness: Este modelo evalúa pares de soluciones basándose en sus valores de fitness. Ayuda a identificar qué soluciones son superiores unas respecto a otras.

2. Criterio Basado en Categorías: Este modelo categoriza las soluciones según sus niveles de fitness y asigna etiquetas a las relaciones entre soluciones. Proporciona una visión más amplia al entender cómo se comparan las soluciones entre diferentes grupos.

Ambos modelos están diseñados para trabajar en conjunto, permitiendo que el algoritmo tome decisiones más informadas al seleccionar soluciones para la optimización.

#Integración de Soluciones No Evaluadas

El marco emplea soluciones no evaluadas para potenciar la generación de nuevas soluciones descendientes. Después de las evaluaciones iniciales, se incluye un segmento de la población que no ha sido evaluado formalmente. Luego, los modelos sustitutos ayudan a crear soluciones descendientes aprovechando tanto los datos evaluados como los no evaluados. Esta integración asegura que el algoritmo no dependa únicamente de unas pocas soluciones evaluadas, sino que se beneficie de un grupo más amplio de candidatos potenciales.

#Proceso de Selección

El proceso de selección implica generar un conjunto de soluciones de prueba usando varias heurísticas. Una vez generadas, se aplican los modelos sustitutos para evaluar la calidad de estas soluciones. Se selecciona la mejor solución para una evaluación real, y ciertas soluciones no evaluadas se eligen para contribuir directamente a la próxima generación de soluciones. Esta combinación tiene como objetivo mejorar la diversidad de la población y acelerar la convergencia hacia soluciones óptimas.

#Estudio Experimental

#Conjuntos de Prueba

Para validar el marco propuesto, se llevaron a cabo experimentos utilizando dos conjuntos de prueba bien conocidos. Estos conjuntos de prueba constan de una variedad de funciones con diferentes características, permitiendo una evaluación integral del rendimiento del algoritmo en diversos escenarios.

1. Conjunto de Prueba LZG: Incluye funciones que presentan una mezcla de paisajes, desde unimodales hasta multimodales.

2. Conjunto de Prueba YLL: Contiene funciones con diversas características, incluyendo paisajes escalonados y funciones con ruido aleatorio.

#Algoritmos para Comparación

El rendimiento del marco propuesto se comparó con varios algoritmos establecidos, que caen en tres categorías principales:

1. Algoritmos Evolutivos Básicos: Como CMA-ES y EDA/LS. Estos algoritmos no están diseñados específicamente para la optimización costosa, pero sirven como base.

2. Algoritmos de Optimización Bayesiana: Como Skopt, que utilizan modelos probabilísticos para mejorar el proceso de búsqueda.

3. Algoritmos Evolutivos Asistidos por Sustitutos: Incluyendo FCPS-CoDE y GPEME, conocidos por su integración de modelos sustitutos en la evaluación de soluciones candidatas.

Cada algoritmo se ejecutó varias veces para tener en cuenta la variación en los resultados, asegurando un análisis robusto.

#Resultados

Los resultados de los experimentos mostraron que el enfoque propuesto superó a los otros algoritmos en la mayoría de los escenarios. Por ejemplo, consistentemente logró valores de función objetivo más bajos en las funciones de prueba, lo que indica un rendimiento superior. Un análisis estadístico, incluyendo la prueba de Friedman y la prueba de suma de rangos de Wilcoxon, confirmó estos hallazgos, demostrando la efectividad de usar soluciones no evaluadas en el proceso de optimización.

#Importancia de la Diversidad

Los experimentos destacaron la importancia de mantener la diversidad dentro de la población de soluciones. Cuando solo se selecciona una o unas pocas soluciones para evaluación, el algoritmo tiende a perder variedad, lo que lleva a la estancación. Al incorporar soluciones no evaluadas, el algoritmo puede explorar un espacio de búsqueda más amplio, reduciendo las posibilidades de quedarse atrapado en óptimos locales.

Además, la capacidad de aprovechar modelos sustitutos para evaluar la aptitud y categorización de soluciones mejora el proceso de toma de decisiones. Esta estrategia permite que el algoritmo haga selecciones informadas que guían mejor la búsqueda de soluciones óptimas.

#Conclusión

En conclusión, el método propuesto de integrar soluciones no evaluadas en el marco del algoritmo evolutivo asistido por sustitutos presenta una mejora significativa sobre los métodos tradicionales. Al centrarse en las relaciones entre soluciones en lugar de evaluar cada una de forma aislada, el algoritmo puede mantener la diversidad en la población mientras optimiza el uso de recursos. El uso de modelos sustitutos permite hacer predicciones efectivas, mejorando aún más la capacidad del algoritmo para encontrar soluciones óptimas en problemas de optimización costosos.

Investigaciones futuras pueden ampliar este trabajo explorando estrategias adicionales para utilizar eficazmente soluciones no evaluadas. También hay potencial para aplicar el marco propuesto a otros tipos de algoritmos y dominios de problemas, lo que podría llevar a más avances en técnicas de optimización.