Recocido Simulado

Conceptos Básicos

El algoritmo de recocido simulado se utiliza para resolver problemas que pueden modelarse como una función y donde se busca un valor extremo (máximo o mínimo). Por ejemplo:

1. Dado un conjunto de puntos en un plano bidimensional, encontrar un punto que minimize o maximice alguna métrica, como la suma de distancias a todos los puntos.
2. Dada una secuencia, determinar un ordenamiento que cumpla con restricciones específicas o optimice un valor objetivo.

Para abordar estos problemas, el recocido simulado es una técnica eficaz. A continuación, se presenta una guía técnica.

Fudnamento Teórico

El algoritmo se inspira en el proceso de recocido en metalurgia, donde un maetrial se calienta y luego se enfría lentamente para reducir defectos. En términos computacionales:

• Se define un estado inicial, que puede ser un punto en el plano o un ordenamiento de secuencia, denotado como \(x\).
• Se calcula un valor objetivo \(y\) para este estado.
• Se establece una temperatura inicial alta \(T\) que controla la exploración del espacio de soluciones.
• En cada iteración, se genera un nuevo estado vecino aleatorio, típicamente dentro de un rango que depende de \(T\).
• Si el nuevo estado mejora el valor objetivo, se acepta inmediatamente. Si no, se acepta con una probabilidad que disminuye a medida que \(T\) baja, lo que permite escapar de óptimos locales.

Mecanismo de Aceptación de Soluciones Peores

La probabilidad de aceptar una solución peor se calcula usando la función exponencial. En código, esto se implementa comúnmente así:

if (exp(delta / temperatura) * RAND_MAX > rand()) {
    // Aceptar solución peor
}

Aquí, RAND_MAX es una constante que define el valor máximo de rand() (generalmente 32767). El parámetro delta es la diferencia entre el valor de la solución actual y la mejor encontrada hasta ahora. Para problemas de minimización, delta se toma negativo para que la expresión dentro de exp sea negativa, asegurando que la probabilidad esté entre 0 y 1. Para maximización, delta ya es negativo.

Proceso de Enfriamiento

El algoritmo itera mientras la temperatura se reduce gradualmente. Se definen tres parámetros clave:

• Temperatura inicial \(T_0\), un valor alto para permitir exploración amplia.
• Factor de enfriamiento \(d\), un número ligeramente menor que 1 (e.g., 0.996) que reduce \(T\) en cada paso.
• Temperatura final \(T_k\), un valor cercano a cero donde el algoritmo se detiene.

En cada iteración, se actualiza la temperatura como \(T = d \times T\). Cuando \(T < T_k\), se termina el proceso y la mejor solución encontrada es el resultado.

Ejemplo de Implementación

El siguiente código ilustra una implementación básica en C++. Se han modificado nombres de variables y estructura para mayor claridad, manteniendo la lógica esencial.

void recocidoSimulado() {
    double temperaturaActual = 1111.0;
    double factorEnfriamiento = 0.998;
    while (temperaturaActual > 1e-9) {
        // Generar nuevo estado aleatorio
        int nuevaPosX = posX + (rand() * 2 - RAND_MAX) * temperaturaActual;
        int nuevaPosY = posY + (rand() * 2 - RAND_MAX) * temperaturaActual;
        
        // Calcular valor objetivo para el nuevo estado
        int valorActual = calcularValorObjetivo(nuevaPosX, nuevaPosY);
        int delta = valorActual - mejorValor;
        
        // Actualizar mejor solución si hay mejora
        if (delta >= 0) {
            posXMejor = nuevaPosX;
            posYMejor = nuevaPosY;
            mejorValor = valorActual;
        } else if (exp(-delta / temperaturaActual) * RAND_MAX > rand()) {
            posX = nuevaPosX;
            posY = nuevaPosY;
        }
        
        // Reducir temperatura
        temperaturaActual *= factorEnfriamiento;
    }
}

Ejemplos de Aplicación

El recocido simulado se aplica a diversos problemas. Algunos ejemplos incluyen:

• Distribución de monedas: Optimizar la asignación aleatoria de recursos.
• Búsqueda de rutas: Minimizar distancias en problemas como el viajante.
• Ataques con explosivos: Mover puntos aleatoriamente para cubrir objetivos.
• Árbol estelar: Buscar un punto óptimo en un plano.
• Cableado eléctrico: Intercambiar pares de elementos para reducir costos.
• Punto de equilibrio: Mover puntos en un sistema físico.
• Coloreado de grafos: Intercambiar colores en celdas adyacentes.

En algunos casos, se recomienda usar permutaciones aleatorias (shuffle) cuando el tamaño del problema es grande o las soluciones son factibles pero no necesariamente óptimas.

Variantes del Algoritmo

Versión 1: Comparación con la Mejor Solución Global

En esta variante, se compara el nuevo estado con la mejor solución encontrada hasta ahora, como se muestra en el código anterior.

Versión 2: Comparación con la Solución Actual

Aquí, se compara con la solución aceptada en el paso actual, lo que puede ayudar a escapar de óptimos locales pero puede desviar la búsqueda.

void recocidoSimuladoVariante() {
    double temperaturaActual = 1111.0;
    while (temperaturaActual > 1e-9) {
        int nuevaPosX = posX + (rand() * 2 - RAND_MAX) * temperaturaActual;
        int nuevaPosY = posY + (rand() * 2 - RAND_MAX) * temperaturaActual;
        int valorActual = calcularValorObjetivo(nuevaPosX, nuevaPosY);
        int delta = valorActual - valorActualMejorLocal;
        
        if (delta < 0 || exp(-delta / temperaturaActual) * RAND_MAX > rand()) {
            posX = nuevaPosX;
            posY = nuevaPosY;
        }
        mejorValorGlobal = min(mejorValorGlobal, valorActual);
        temperaturaActual *= factorEnfriamiento;
    }
}

Recomendaciones para Parámetros y Ajuste

La selección de parámetros es crucial para el rendimiento. Basado en experiencias prácticas:

• Temperatura final: Para problemas con variables reales, usar \(1e-11\); para variables enteras, \(1e-7\).
• Temperatura inicial: Elegir un valor que cubra el rango de estados posibles (e.g., miles o decenas de miles). Si los deltas son grandes, considerar escalar la temperatura.
• Factor de enfriamiento: Para variables reales, valores entre 0.996 y 0.998; para enteras, entre 0.99 y 0.998. Ajustar según la complejidad del problema.

El ajuste de parámetros depende de factores como el rango de exploración (controlado por \(T\)), la precisión de la solución (controlada por \(T_k\)) y el número de iteraciones (controlado por el factor de enfriamiento).

Cuándo Usar Permutaciones Aleatorias

El uso de shuffle es adecuado cuando:

• El problema involucra secuencias con restricciones de orden.
• Se buscan soluciones factibles, no necesariamente óptimas.
• El tamaño del problema es grande, para evitar sesgos en el recocido.
• No es posible evaluar la calidad relativa de soluciones.

El algoritmo de recocido simulado no es eficaz para funciones discontinuas o problemas donde no se pueden ganerar estados vecinos de manera significativa.