Propuesta de algoritmos de estimación de distribución para problemas de optimización continua

Abstract

Los algoritmos de optimización se presentan en la industria y la academia de manera cotidiana. Existen una gran cantidad de problemas de interés y no existe un algoritmo o un grupo de algoritmos que puedan resolver toda la variedad de problemas de manera eficiente y cierta. En particular, los problemas con múltiples mínimos y máximos, no derivables, o incluso sin conocimiento explícito de la función a optimizar, se presentan de forma cotidiana en diferentes campos, y no existe un algoritmo de optimización eficiente (de orden polinomio) que garantice la solución óptima. Estos problemas han sido ampliamente estudiados y se han propuesto muchos algoritmos para aproximar su solución, pero es un campo de estudio que continua como un reto abierto a la comunidad académica. Dado lo anterior, en esta tesis se estudian y presentan propuestas de algoritmos, que atacan problemas como los mencionados, dentro de una familia denominada: algoritmos de estimación de distribución. En estos algoritmos se estima una distribución de probabilidad de un subconjunto de la población de soluciones y se toman muestras para generar la siguiente población. Los algoritmos de estimación de distribución siguen los siguientes pasos: 1) Generar una población inicial P , 2) seleccionar un subconjunto D de la población P , 3) estimar la función de probabilidad p(X = x) a partir del subconjunto D, 4) muestrear p(X = x) para generar descendientes y 5) ir al paso 2 hasta que el criterio de paro se cumpla. Las contribuciones de esta tesis se centran en 3 propuestas: el uso de direcciones de la búsqueda, los algoritmos de estado estable, y una aplicación de detección de una parábola en imágenes de la retina del ojo humano, usando el algoritmo propuesto de estado semi estable con estimadores pesados.