numero 3 articulo2

OPTIMIZACION CON RECOCIDO SIMULADO PARA EL PROBLEMA DE CONJUNTO INDEPENDIENTE


3. RECOCIDO SIMULADO

3.1 El Proceso de Recocido de un Sólido

El algoritmo de recocido simulado está basado en una analogía entre la simulación de recocido de sólidos y la problemática de resolver problemas de optimización combinatoria de gran escala. Por esta razón el algoritmo se conoce como recocido simulado. Recocido denota un proceso de calentamiento de un sólido a una temperatura en la que sus granos deformados recristalizan para producir nuevos granos. La temperatura de recocido o de recristalización, depende del tipo de material, del grado de deformación del mismo, además de su uso futuro. Seguida a la fase de calentamiento, viene un proceso de enfriamiento en donde la temperatura se baja poco a poco. De esta manera, cada vez que se baja la temperatura, las partículas se reacomodan en estados de más baja energía hasta que se obtiene un sólido con sus partículas acomodadas conforme a una estructura de cristal. Si se comienza con un valor máximo de la temperatura, en la fase de enfriamiento del proceso de recocido, para cada valor de la temperatura T debe permitirse que se alcance su equilibrio térmico. Sin embargo, si el proceso de enfriamiento es demasiado rápido y no se alcanza en cada etapa el equilibrio térmico, el sólido congelará en un estado cuya estructura será amorfa en lugar de la estructura cristalina de más baja energía. La estructura amorfa está caracterizada por una imperfecta cristalización del sólido.

El equilibrio térmico está caracterizado por la distribución de Boltzmann [TOD83]. De acuerdo a esta distribución, la probabilidad de que el sólido esté en un estado i con energía Ei a la temperatura T, viene dada por

(12)

donde X es tina variable aleatoria que denota el estado actual del sólido. Z(T) es una constante de nomalización llamada la función partición, que está definida como

(13)

donde la sumatoria se extiende sobre todos los posibles estados y kB es una constante física conocida como la constante de Boltzmann. El factor exp se conoce como el factor de Boltzmann. Obviamente (12) es una función de densidad de probabilidad ya que siempre es mayor o igual a cero y la suma sobre todos los valores es igual a la unidad. Se puede observar en (12) que cuando el valor de T disminuye, la distribución de Boltzmann se concentra en los estados de menor energía mientras que si la temperatura se aproxima a cero, únicamente los estados con mínima energía tienen una probabilidad de ocurrencia diferente de cero.

Por lo dicho anteriormente, el proceso de recocido consta de dos pasos fundamentales que son:

Incrementar la temperatura del barro térmico a un valor máximo.

Decrementar cuidadosamente la temperatura del barro térmico hasta que las partículas se reacomoden por sí mismas en un estado de mínima energía, denominado el estado fundamental del sólido.

El proceso físico de recocido puede moderarse exitosamente usando métodos de simulación (vea [BlN78] o [MET53]), el algoritmo introducido para tal propósito se basa en técnicas Monte Carlo y genera una sucesión de estados del sólido de la siguiente manera. Dado un estado i del sólido con energía Ei, se genera un estado subsecuente j aplicando un mecanismo de perturbación que transforma el estado actual en el siguiente estado por medio de una pequeña distorsión, por ejemplo, por el desplazamiento de una partícula. La energía del siguiente estado es Ej. Si la diferencia de energía, Ej - Ei, es menor o igual a cero, el estado j se acepta como el estado actual. Si la diferencia de energía, es mayor que cero, el estado j se acepta con una probabilidad que está dada por

exp(14)

donde T denota la temperatura del baño térmico y kB es la constante de Boltzman. La regla de decisión descrita arriba se conoce como el criterio de Metropolis y al algoritmo se le conoce como algoritmo de Metropolis.

Si la temperatura se baja poco a poco, el sólido puede alcanzar su equilibrio térmico en cada temperatura. En el algoritmo de Metropolis esto se lleva a cabo generando un número grande de transiciones para un valor dado de la temperatura.

 

3.2 El Algoritmo de Recocido Simulado

La simulación del proceso de recocido puede usarse para describir un proceso de generación de una sucesión de soluciones de un problema de optimización combinatoria, en donde se vayan obteniendo, conforme el proceso avanza, mejores soluciones al misimo. Para este propósito, se puede observar una analogía entre el sistema físico y un problema de optimización combinatoria en donde cada solución del problema puede verse como un estado del sólido y el valor de la función objetivo para la el nivel de energía del sólido. En resumen, se puede pensar en las siguientes equivalencias.

Las soluciones de un problema de optimización combinatoria son equivalentes a los estados de un sistema físico.

El costo de una soltución es equivalente a la energía de un estado.

Además, se introdtroduce un parámetro que juega el papel equivalente de la temperatura. Este parámetro se llama el parámetro de control. El algoritmo de recocido simulado puede verse como una iteración del algoritmo de Metropolis, evaluado en valores decrecientes del parámetro de control.

A continuación se introducen las siguientes definiciones.

Definición 5 Sea (S,) una Instancia de un problema de optmziación combinatoria, y denote por i y j dos soluciones con costo (i) y (j), respectivamente. Entonces el criterio de aceptación determina si j se acepta de i a parir de aplicar la siguiente probabilidad de aceptación:

(15 )

donde c R+ denota el parámetro de control.

Claramente, el mecanismo de generación corresponde al mecanismo de perturbación en el algoritmo de Metropolis, mientras que el criterio de aceptación corresponde al criterio de Metropolis.

 

Definición 6 Una transición es una acción combinada que transforma la solución actual en una subsecuente. Esta acción consiste de los siguientes dos pasos: (i) aplicación del mecanismo de gcneración, (ii) aplicación del criterio de aceptación.

Sea Ck el valor del parámetro de control y Lk el número de transiciones generadas en la k-ésima iteración del algoritmo de Metropolis. Entonces el algoritmo de recocido simulado puede describirse en pseudo-código como se muestra en la Figura 2.

El algoritmo de la Figura 2 comienza llamando a un procedimiento de inicialización donde se definen la solución inicial, la temperatura inicial y el número inicial de generaciones necesarias para alcanzar el equilibrio térmico para la temperatura inicial. La parte modular del algoritmo consta de dos ciclos. El externo Repite ... hasta y el interno para ...finpara. El ciclo interno mantiene fijo el parámetro de control hasta que se generan Lk soluciones y se acepta o se rechaza la solución generada conforme los criterios de aceptación ya discutidos. El ciclo externo disminuye el valor de la temperatura mediante el procedimiento CALCULA-CONTROL y calcula el número de soluciones a generar para alcanzar equilibrio térmico mediante el procedimiento CALCULA-LONGITUD. Este ciclo finaliza cuando la condición de paro se cumple.

Un rasgo característico del algoritmo de recocido simulado es que, además de aceptar mejoramientos en el costo, también acepta soluciones más malas en costo. Inicialmente. para valores grandes donde c, puede aceptar soluciones con un valor objetivo mucho mayor a la solución actual; cuando c decrece, únicamente pequeñas desviaciones serán aceptadas y finalmente, cuando el valor de c se aproxima a cero, no se aceptarán desviaciones. Este hecho significa que el algoritmo de recocido simulado, en contraste con el algoritmo de búsqueda local, puede escapar de mínimos locales además de exhibir los rasgos favorables de los algoritmos de búsqueda local; es decir, simplicidad y aplicabilidad general.

Comienza

INICIALIZA ( i inicial, C0, L0)

k: = 0

i: = i inicial

Repite

para l : = 1 a Lk haz

Comienza

GENERA ( J de Si )

sientonces i := j

sino

si expnúmero aleatorio en [0,1) entonces i := j

fin para

k := k+1

CALCULA-LONGITUD (Lk)

CALCULA- CONTROL (Ck)

hasta criterio de paro

fin

 

Figura 2. Algoritmo de Recocido Simulado en pseudo-código

 

Note que la probabilidad de aceptar desviaciones está implementada al comparar el valor de exp

(((i) - (j) )/ c) con un número aleatorio generado de una distribución uniforme en el intervalo [0, l). Además, debe ser obvio que la velocidad de convergencia del algoritmo está determinada al escoger los parámetros Lk y ck, k=0,l..... Si los valores Ck decrecen rápidamente o los valores de Lk no son grandes, se tendrá una convergencia más rápida que cuando los valores de ck decrecen lentamente o los valores de Lk son grandes.

Comparando el algoritmo de recocido simulado con el algoritmo de búsqueda local, resulta evidente que recocido simulado puede verse como una generalización de búsqueda local y viene a ser idéntico a búsqueda local, en el caso que el parámetro de control c se tome igual a cero. En lo que respecta a la ejecución de ambos algorltmos, generalmente el algoritmo de recocido simulado obtiene soluciones de menor calidad que el algoritmo de búsqueda local.

atrasnumeroscomenzo