El método de entropía cruzada ( CE ) es un método de Monte Carlo para el muestreo y la optimización de importancia . Es aplicable tanto a problemas combinatorios como continuos , con un objetivo estático o ruidoso.
El método se aproxima al estimador de muestreo de importancia óptima repitiendo dos fases: [1]
- Extrae una muestra de una distribución de probabilidad.
- Minimice la entropía cruzada entre esta distribución y una distribución de destino para producir una mejor muestra en la siguiente iteración.
Reuven Rubinstein desarrolló el método en el contexto de la simulación de eventos raros , donde se deben estimar pequeñas probabilidades, por ejemplo, en análisis de confiabilidad de red, modelos de cola o análisis de rendimiento de sistemas de telecomunicaciones. El método también se ha aplicado al vendedor ambulante , la asignación cuadrática , la alineación de la secuencia de ADN , el corte máximo y los problemas de asignación de búfer.
Estimación mediante muestreo de importancia
Considere el problema general de estimar la cantidad
,
dónde es alguna función de rendimiento yes un miembro de alguna familia de distribuciones paramétricas . Utilizando un muestreo de importancia, esta cantidad se puede estimar como
,
dónde es una muestra aleatoria de . Por positivo, la densidad de muestreo de importancia teóricamente óptima (PDF) viene dada por
.
Esto, sin embargo, depende de lo desconocido . El método CE tiene como objetivo aproximar la PDF óptima mediante la selección adaptativa de los miembros de la familia paramétrica que están más cerca (en el sentido de Kullback-Leibler ) a la PDF óptima.
Algoritmo genérico de CE
- Elija el vector de parámetro inicial ; establecer t = 1.
- Genera una muestra aleatoria de
- Resolver , dónde
- Si se alcanza la convergencia, deténgase ; de lo contrario, aumente t en 1 y repita desde el paso 2.
En varios casos, la solución al paso 3 se puede encontrar analíticamente . Las situaciones en las que esto ocurre son
- Cuándo pertenece a la familia exponencial natural
- Cuándo es discreto con soporte finito
- Cuándo y , luego corresponde al estimador de máxima verosimilitud basado en aquellos.
Optimización continua: ejemplo
El mismo algoritmo CE se puede utilizar para la optimización, en lugar de la estimación. Suponga que el problema es maximizar alguna función, por ejemplo, . Para aplicar CE, se considera primero el problema estocástico asociado de estimarpara un nivel dado y familia paramétrica , por ejemplo la distribución gaussiana unidimensional , parametrizada por su media y varianza (entonces aquí). Por lo tanto, para un, el objetivo es encontrar así que eso se minimiza. Esto se hace resolviendo la versión de muestra (contraparte estocástica) del problema de minimización de divergencia KL, como en el paso 3 anterior. Resulta que los parámetros que minimizan la contraparte estocástica para esta elección de distribución objetivo y familia paramétrica son la media muestral y la varianza muestral correspondientes a las muestras élite , que son aquellas muestras que tienen un valor de función objetivo.. La peor de las muestras de élite se utiliza luego como parámetro de nivel para la siguiente iteración. Esto produce el siguiente algoritmo aleatorio que coincide con la llamada Estimación del algoritmo normal multivariante (EMNA), un algoritmo de estimación de distribución .
Pseudocódigo
// Inicializar parámetrosμ: = −6σ2: = 100t: = 0maxits: = 100N: = 100Ne: = 10// Mientras que los máximos no se excedieron y no convergieron mientras táximos>y σ2> ε sí // Obtenga N muestras de la distribución de muestreo actual X: = SampleGaussian (μ, σ2, N) // Evaluar la función objetivo en los puntos muestreados S: = exp (- (X - 2) ^ 2) + 0.8 exp (- (X + 2) ^ 2) // Ordenar X por valores de función objetivo en orden descendente X: = ordenar (X, S) // Actualizar los parámetros de la distribución de la muestra μ: = media (X (1: Ne)) σ2: = var (X (1: Ne)) t: = t + 1// Devuelve la media de la distribución final del muestreo como solución devuelve μ
Métodos relacionados
Ver también
Artículos de revistas
- De Boer, PT., Kroese, DP, Mannor, S. y Rubinstein, RY (2005). Un tutorial sobre el método de la entropía cruzada. Annals of Operations Research , 134 (1), 19–67. [1]
- Rubinstein, RY (1997). Optimización de modelos de simulación por computadora con eventos raros, European Journal of Operational Research , 99 , 89–112.