[Todos] Seminario EMEA

[Mariela Sued]

Seminario de Estadistica, Modelizacion Estocastica y Aplicaciones (EMEA)

Proximo encuentro:  Miercoles 6 de Mayo

EXPOSITOR: Eduardo Dubuc, Departamento de Matematica, FCEyN.
 
TITULO:"El recocido simulado (Simulated Annealing) en optimizacion combinatoria,
dos ejemplos, fixtures condicionados y ancho de banda de matrices ralas"

LUGAR: INSTITUTO DE CALCULO, PAB II 2º piso.

HORA: 12 hs. 

RESUMEN: El recocido es un conocido metodo para llevar un fluido a un estado de
baja energia (por ejemplo, la fabricacion de botellas de vidrio). Consiste en
derretir el fluido y luego ir bajando lentamente la temperatura. Esta es una
situacion termodinamica que obedece la ley de Bolzano, y que se modela
matematicamente con un sistema finito cuya evolucion esta definida por una
cadena de Markov. Esta evolucion es entonces simulada por un metodo de Monte
Carlo. De acuerdo a la realidad fisica, el sistema evoluciona hasta un estado de
minima energia.
  La optimizacion combinatoria consiste en encontrar el minimo de una funcion
numerica definida en un conjunto finito. Por analogia, se supone que el conjunto
es el conjunto de "estados" de un sistema, y la funcion es la funcion que a un
estado le asigna su energia. La simulacion Monte Carlo, (comenzando a alta
temperatura y gradualmente disminuyendola en pasos pequennos) debe terminar en
un estado de (con suerte !) minima o casi minima energia.
  En practica, la aplicabilidad del metodo depende en cada problema de la
"velocidad de la convergencia". A veces funciona, y a veces no. Contrariamente a
importantes logros de la matematica en las aplicaciones, en este caso la
velocidad de la convergencia es el resultado (como su nombre en castellano
parece indicar) de "pura cocina". No existen resultados teoricos que sirvan. Sin
embargo, creo que las neuronas que se utilizan para hacer esta cocina son las
mismas que las que se utilizan para demostrar teoremas.
 Se enfoca el problema de los fixtures condicionados (facil por su tamanno, 20!)
y el del ancho de banda de matrices ralas (mucho mas dificil, hasta 2600!) como
sendos problemas de optimizacion combinatoria. Se desarrolla una receta exitosa
para resolverlos con el recocido simulado, y se analizan los resultados
obtenidos. Correremos un programa que muestra la evolucion montecarlo en el caso
del ancho de banda (una caja de fondo blanco con puntos negros en los lugares
donde la matriz (que va evolucionando) es no nula).

Quedan todos cordialmente invitados
  Pablo Groisman -  Mariela Sued
 
 
 
 
 Mas informacion: http://mate.dm.uba.ar/~drodrig/seminario/