Soporte para el elitismo en algoritmos evolutivos multiobjetivo paralelos
2014Profesores: Dr. Antonio López Jaimes (UAM Cuajimalpa) y Dra. Elizabeth Pérez Cortés
Resumen: La mayoría de los problemas de optimización del mundo real involucran dos o más objetivos que se tienen que optimizar simultáneamente y que se encuentran en conflicto. Como resultado, a diferencia de la optimización de un solo objetivo, en la optimización multiobjetivo no hay una solución óptima sino un conjunto de soluciones compromiso óptimas (llamadas frente de Pareto). Estas soluciones son óptimas en el sentido que no es posible mejorar un objetivo sin deteriorar otro. Los algoritmos evolutivos (AEs) fueron diseñados para resolver problemas de optimización del mundo real en los que las técnicas clásicas de programación matemática tienen un desempeño pobre o incluso no pueden aplicarse. Los algoritmos evolutivos son particularmente adecuados para resolver problemas multiobjetivo ya que mantienen simultáneamente un conjunto de soluciones para obtener una muestra del frente de Pareto.
El elitismo es el mecanismo para evitar perder las mejores soluciones encontradas durante la ejecución de un AE debido a efectos estocásticos. Este concepto juega un papel importante en AE modernos ya que junto con la mutación, garantiza convergencia global. Existen dos enfoques principales para implementar el elitismo. Uno de ellos combina la población anterior y la nueva, y posteriormente utiliza una selección determinista para mantener a las mejores soluciones en la siguiente generación. En el otro enfoque se mantiene un conjunto externo de soluciones llamado “archivo” que mantiene las mejores soluciones encontradas durante la búsqueda. Existen múltiples esfuerzos para encontrar una estructura de datos que permita el mantenimiento eficiente del archivo en un entorno centralizado y, en este proyecto, estamos interesados en hacer lo propio par a un entorno paralelo. En otras palabras, estamos interesados en diseñar un algoritmo de archivado paralelo de manera que pueda contener un gran número de soluciones (> 5× 10⁵).
Objetivo general
- Diseñar un algoritmo paralelo de archivado capaz de mantener de manera eficiente un gran número de soluciones (> 5 x 10⁵).
Objetivos específicos
- Identificar los algoritmos de archivado propuestos actualmente que puedan implementarse en paralelo directamente.
- Conocer la eficiencia relativa de los algoritmos de archivado identificados.
- Proponer un algoritmo de archivado paralelo (posiblemente basado en una versión secuencial existente) para ejecutarse en un multiprocesador débilmente acoplado (e.g., un cluster).
- Poner el algoritmo implementado a disposición de la comunidad de computación evolutiva.
Ultima actualización 14/08/2022 por pcyti