Optimización por el método del recocido simulado, el problema del ancho de banda
Profesor: Eduardo Dubuc
Puntaje: 1 punto (Lic. y Prof.)
Correlatividades: No hay
Carga horaria: 24 horas totales
Carreras: Licenciatura en Matemática (Or. Pura y Aplicada), Profesorado en Matemática, Doctorado en Matemática
Contenidos:
El Problema del ancho de Banda: Dado un grafo, se trata de enumerar sus nodos de manera tal que se minimice la diferencia entre los índices de nodos adyacentes. Ello corresponde a que los 1 en la correspondiente matriz de incidencia se encuentren alrededor de la diagonal principal dentro de una banda de ancho mínimo.
El Recocido Simulado: se trata de un conocido proceso para llevar un fluido a un estado de energía bajo: Consiste en derretirlo (por calentamiento), y luego enfriarlo muy desacio hasta que se solidifique (por ejemplo, la fabricación de botellas de vidrio: si se enfrían bruscamente pueden quedar coin alta energía y estallan). Por analogía para minimizar una función h definida en un conjunto S, se considera un método Monte Carlo. Se simula un recocido que termina en un estado que (con suerte) minimiza h.
BIBLIOGRAFIA:
E. Dubuc: Bandwith reduction by Simulated Annealing. It. J. for Num. Methods in Eng. Vol. 37, 1994
S. Kirkpatrick, C. Gelatt & M. Vecchi: Optimization by Simulated Annealing. Science, Vol. 220, 1983
