Método de entropía cruzada
El método de entropía cruzada fue desarrollado como una técnica de estimación eficiente para probabilidades de eventos raros en sistemas de simulación de eventos discretos y ha sido adaptado para su uso en optimización. El nombre de la técnica proviene del método de entropía cruzada de Kullback-Leibler para medir la cantidad de información (bits) necesaria para identificar un evento a partir de un conjunto de probabilidades.
La estrategia de procesamiento de información del algoritmo es muestrear el espacio del problema y aproximar la distribución de buenas soluciones. Esto se logra asumiendo una distribución del espacio del problema (como Gaussian), muestreando el dominio del problema, generando soluciones candidatas utilizando la distribución y actualizando la distribución en función de las mejores soluciones candidatas descubiertas. Las muestras se construyen en etapas (un componente a la vez) en función de la distribución resumida de buenas soluciones. A medida que avanza el algoritmo, la distribución se vuelve más refinada hasta que se enfoca en el dominio o rango de soluciones óptimas en el dominio.
El siguiente algoritmo describe el método de entropía cruzada para minimizar una función de costo.
El método de entropía cruzada se ha adaptado a problemas de optimización combinatoria, aunque se ha aplicado a la optimización de funciones continuas así como a problemas de simulación que contienen mucho ruido.
Un parámetro alfa (a) o una tasa de aprendizaje en [0; 1] generalmente se establece alto, como 0.7. Se puede utilizar una función de suavizado para controlar aún más las actualizaciones de las distribuciones de muestra del espacio de definición. Por ejemplo, en la optimización de una función continua, un parámetro puede reemplazar (a) por la actualización de la desviación estándar, calculada en el tiempo t como BB(1-1/t)^q, donde B se establece inicialmente en [0,8 ; 0.99] yq es un entero pequeño en [5; 10].
