Cross Entropy Acelerado y una
aplicación al problema del
Máximo Corte
Manuel Laguna
Abraham Duarte
Rafael Marti
Publicado en Diciembre 2006
Manuel Benjamin
Presentación:
•
•
•
•
Introducción.
El metodo de Cross Entropy (CE).
Método Acelerado de Cross Entropy (ACE).
El problema de Max Cut y la implementación del ACE
para resolverlo.
• Experimentos Computacionales.
• Conclusiones.
Desarrollo y méritos:
• Fue concebido por Rubinstein (1997) como una forma de estimar
probabilidades para “rare events” en redes estocásticas complejas.
• El método fue adaptado rápidamente para resolver problemas de
optimización combinatoria. (Rubenstein 1999 y 2001).
• En el 2005 El Annals of Operations Research le dedico un volumen
al método.
Problemas a los que se les ha
aplicado el método:
• Ruteo de vehículos.
• Ruteo de vehículos con demandas
estocásticas.
• Viajante de comercio
• Buffer allocation.
• Máximo Corte.
Ideas Básicas:
• 1. Generar una muestra aleatoria con una distribución
de probabilidad pre-especificada.
• 2.Utilizar la muestra obtenida para modificar los
parámetros de la función de probabilidad en orden de
obtener una “mejor” muestra en la próxima iteración.
El método basico de CE es intuitivo y muy fácil de implementar. En particular
cuando se trata de problemas combinatorios en los que la representación natural
de la solución es un vector binario.
Para la claridad del método trabajamos con problemas
combinatorios sin restricciones y que la representación
de sus soluciones sea un vector binario.
S=“conjunto de soluciones”
x=(x1,x2,…,xn) donde xi= 0 ó 1
x esta en S  x es binario
El objetivo es maximizar una función f(x) sobre el espacio
de soluciones
Parametros:
• Se define un vector p=(p1,…,pn) de probabilidades
correspondientes a los parametros de “n” bernulli independientes.
• La distribución bernulli se ha probado efectiva en el contexto de
vectores binarios. Ante la falta de información a priori el vector se
inicializa con valor 0.5 para todo pi.
CE usa 5 parametros:
N=
ρ=
α=
k=
K=
Tamaño de la muestra
porcentaje de corte para soluciones de calidad
Constante “suavisadora” para la actualizacion del vector p
Límite de iteraciones sin mejora
Límite máximo de iteraciones
Pseudo-Codigo:
•La metodología CE se concentra en problemas de optimización
combinatoria que pueden ser representados como grafos con peso y los
clasifica en dos grupos:
1) Aquellos problemas que las variables de decision estan
asociados a las ramas del grafo. (Problemas de ramas)
ie: TSP
2) Los problemas que las variables están asociados a los nodos
del grafo. (Problemas de nodos)
ie: Max-Cut
•El tamaño N de la muestra y el valor de ρ son cruciales para la performance
del CE.
•Boer sugiere que para problemas de ramas el tamaño de la muestra debe ser
una funciones de k*n2 con k>1 y para problemas de nodos el N debe ser una
funcion lineal de n. N=k*n con k>1
(Estos valores asumen que hay un solo parametro que estimar para la función de distribucion
asociada. Como es el caso de la Bernulli. Aunque esto no es cierto para distribuciones Normales o
Betas.)
•La literatura de CE tambien tiene guias para ajustar ρ. Y debería decrecer a
medida que N crece. Si N>=100 ρ=.01 o ρ=ln(N)/N si N<100
Problemas del CE
El método presenta algunas limitaciones:
•Requiere muestras muy grandes para obtener resultados de alta calidad.
•Las muestras grandes hacen lento al método.
•Los mecanismos de diversificación se apoyan solamente en la aleatoriedad de
las muestras, lo que hace los resultados impredecibles
•Los parámetros de búsqueda son difíciles de ajustar a pesar de lo que sugiere
la bibliografía del método.
•Es necesario el K como mecanismo de precacución. Aunque teóricamente el
método debería converger. Que en este contexto significa que todos los
elementos de la muestra sean iguales o que no haya habido mejoras en k
iteraciones.
Propuestas del ACE
• Ayudar la convergencia del metodo y reducir el tamaño
de la muestra mediante la inclusión de optimización
local.
• Esta es aplicado a un porcentaje δ de soluciones en la
muestra.
Optimización local:
•
Asumiendo la muestra ordenada:
Consideraciones :
•Haciendo subjetivo el concepto de “mejores soluciones” para la eleccion de los
elementos a quienes aplicar optimizacion local se acelera la convergencia del
metodo tendiendo a soluciones de mejor calidad.
•La optimización local sobre un conjunto diverso de soluciones (no las mejores sino
las mas “diversas”) expande la exploracion del espacio de soluciones en busca de
más optimos locales.
•En cambio la busqueda local sobre las mejores
temprana convergencia y peores resultados.
soluciones deriva en una
•Como criterio, si la mejor solución no cambia de una iteración a la siguiente. No se
vuelve a hacer búsqueda local sobre la nueva mejor.
•El agregado de la Búsqueda local tiene el efecto de reducir el tamaño de la
muestra necesaria para encontrar soluciones de Calidad.
Método ACE
Diferencias:
•No hay parametro k.
•Se quita el parametro ρ. El vector V se genera con el promedio de toda la
muestra. Que es lo mismo que fijarlo en 1
•Se agrega el parametro δ para decidir el porcentaje de la muestra al que se
le hace busqueda local.
•En los experientos se ve que la relación N=k*n sigue siendo válida pero con
0.01<k<0.05 (antes k>1)
ACE para el Problema del Máximo Corte:
Max-Cut:
“Dado un grafo completo G=(V,E) con pesos en sus ramas. El
problema es hallar una partición de V en dos subconjuntos V1 y V2
de manera que la suma de los pesos de los ejes con vertices en
V1 y V2 sea máxima.”
Usando programación semidefinida, Goemans and Williamson
hicieron un algoritmo aproximado del problema con un factor de
0.878..
Si se acepta la conjetura de “unicidad de los juegos”. Se sabe que
es la mejor aproximación posible salvo que P=NP.
Formulación de Max-Cut
La aplicación del ACE
es directa si:
Donde
= peso de (i,j)
Busqueda Local:
Llamamos:
Se define la noción de vecindad mediante un cambio de una bit.
Para la búsqueda local se ordenan los nodos aleatoriamente.
Para i (2,3,…,n):
En el orden aleatorio.
Distancia:
Experimentos:
Varias metas de la exprimentación:
•Encontrar parámetros para el CE para igualar los resultados por
Rubinstein (2002)
•Ajustar parámetros de ACE para aplicar a las instancias de
Rubinstein (2002) que son consideradas chicas.
•Comparar con otras Heurísticas especialmente diseñadas para el
problema del máximo corte
Se experimentó sobre 4 conjuntos de problemas:
•G1: Rubinstein con 200 vértices y pesos entre 1 y 5.
•G2: DIMACS de 512 a 3375 vértices y desde 1536 a 10125
ramas
•G3:Helmberg and Rendl. 24 instancias con grafos Toroidales,
planares y aleatorios. Pesos 1, 0 o -1. de 800 a 3000 nodos y
con densidades del 0.17% a 6.12%
•G4 de Festa (2002) con 20 instancias. 1000 y 2744 vertices.
Densidades 0.6% y .22%. Pesos 1, 0 o -1.
Resultados:
•
No se pudo obtener los resultados de Rubinstein con sus parametros
indicados en su trabajo.
•
Se procedio a buscar mejores parametros con el “fine-tuning system”
conocido como Calibra (Aldenso-Diaz and Laguna, 2006)
•
Se busco dentro del siguiente rango de parametros:
Fijando previamente k=10 (cantidad de iteraciones sin mejora)
Se hallaron los mejores resultados con los siguientes parametros:
Busqueda de parametros para ACE
•
Se procedió a encontrar los parámetros con Calibra en el siguiente rango:
•
Obteniendo los siguientes resultados:
Comparación entre CE y ACE
En G2 se puede ver que CE no aporta buenas soluciones.
El ACE es superior en términos de Calidad y tiempo.
A saber:
CE: Cross Entropy
ACE: Cross Entropy Acelerado
CirCut: Heuristica Circut debida A Burer (2001) Hecha para
resolver “binary quadratic programs” en especial Max-Cut.
Grasp; Grasp
GPR: Grasp con Path Relinking
VNSPR: Busqueda de varios vcindarios con Path Relinking de
Festa
SDP: Programacion Semidefinida (que da la cota superior del
problema)
Para el G3 y G4 se compara con otras heurísticas especificamente diseñadas
al problema en tiempo y calidad.
Conclusiones:
• ACE produce souciones de calidad razonable, pero no
puede competir con medio altamente diseñados para el
problema. Esto es porque CE no usa ningun
conocimento específico del problema y ACE solo tiene la
busqueda local.
• ACE es una alternativa interesante por la facil
implementación y buenos tiempos computacionales.
• ACE logra superar los problemas encontrados en CE
FIN
• PD: preguntas?
Descargar

Cross Entropy Acelerado y una aplicación al problema del Máximo