El recocido simulado es un algoritmo probabilístico general para encontrar soluciones óptimas en espacios de búsqueda amplios, especialmente cuando la función objetivo no es unimodal. Inspirado en el proceso de recocido físico, este método fue desarrollado por S. Kirkpatrick, C. D. Gelatt y M. P. Vecchi en 1983, y de forma independiente por V. Černý en 1985. Se utiliza comúnmente en problemas como el del viajante (TSP) y otras optimizaciones combinatorias.

Principio de aceptación de Metropolis

En cada iteración, se genera una solución candidata a partir de la actual. Si la nueva solución mejora el valor de la función objetivo, se acepta automáticamente. De lo contrario, se acepta con una probabilidad que depende de la temperatura actual y la diferencia en calidad. Formalmente, sea \(\Delta E\) la diferencia en el valor de la función objetivo (nueva menos actual), \(T\) la temperatura, y \(k\) una constante. La probabilidad de aceptar una solución peor es \(e^{\frac{\Delta E}{kT}}\).

En la práctica, si \(\Delta E > 0\), la solución se acepta siempre. Si \(\Delta E < 0\), se acepta con probabilidad \(P = \exp\left(\frac{\Delta E}{kT}\right)\), lo que permite escapar de óptimos locales al inicio del proceso.

Flujo básico del recocido simulado

Parámetros típicos: temperatura inicial \(T_0\) (elevada), factor de enfriamiento \(\alpha\) (un decimal cercano a 1, como 0.97), y temperatura final \(T_f\) (cercana a cero, ej. \(10^{-10}\)). Estos valores suelen ajustarse experimentalmente para equilibrar calidad de solución y tiempo de ejecución.

Procedimiento:

1. Inicializar \(T = T_0\).
2. Realizar una transición (generar nueva solución).
3. Actualizar \(T \leftarrow T \cdot \alpha\).
4. Repetir pasos 2 y 3 hasta que \(T < T_f\).

Transiciones y detalles clave

Sea \(f(x)\) la función de evaluación para una solución \(x\). Una nueva solución se genera como \(x_{\text{nueva}} = x + \Delta x\), donde \(\Delta x\) es un cambio aleatorio escalado por la temperatura. La diferencia en evaluación es \(\Delta E = f(x_{\text{nueva}}) - f(x)\).

Un pseudocódigo ilustrativo:

if (delta_eval > 0) {
    aceptar_nueva_solucion();
} else if (exp(delta_eval / sqrt(temperatura)) > aleatorio_uniforme()) {
    aceptar_nueva_solucion();
}

Nota: La expresión exp(delta\_eval / sqrt(temperatura)) genera un valor entre 0 y 1 cuando \(\Delta E < 0\). Compararlo con un número aleatorio en [0,1] determina la aceptación probabilística. Esto garantiza que soluciones peores se acepten con mayor probabilidad al inicio (temperatura alta) y con menor probabilidad al final.

Precaución: Evitar errores comunes como comparar exp(-delta\_eval / temperatura) directamente con rand(), ya que el primer valor puede exceder 1 y la condición siempre fallaría.

Aspectos prácticos

• La inicialización aleatoria de soluciones iniciales es crucial para evitar sesgos.
• El ajuste de parámetros (\(T_0\), \(\alpha\), \(T_f\)) requiere experimentación; por ejemplo, reducir \(T_0\) si se excede el tiempo de ejecución.
• Para obtener soluciones robustas, se puede ejecutar el algoritmo múltiples veces hasta agotar el límite de tiempo, usando un control basado en el reloj del sistema.

Ejemplo de implementación en C++

A contniuación, un código adaptado para el problema "Ataque de bombas" (Luogu P5544). Se han renombrado variables y funciones para mayor claridad, y se ha simplificado la lógica.

#include <cstdio>
#include <cmath>
#include <ctime>
#include <algorithm>
using namespace std;

const int MAX_OBJ = 11, MAX_PTS = 1010;
const double FACTOR_ENFRIAMIENTO = 0.996, TEMP_MINIMA = 1e-10;
int num_obj, num_pts, radio_global;
double mejor_x, mejor_y, mejor_valor;

double distancia(double x1, double y1, double x2, double y2) {
    double dx = x2 - x1, dy = y2 - y1;
    return sqrt(dx * dx + dy * dy);
}

int evaluar(double x, double y) {
    double radio = radio_global;
    // Calcular radio efectivo basado en obstáculos
    for (int i = 0; i < num_obj; i++) {
        // Asumiendo arreglos de coordenadas y radios de obstáculos
        // radio = min(radio, distancia(x, y, obs_x[i], obs_y[i]) - radio_obs[i]);
    }
    int conteo = 0;
    // Contar puntos dentro del radio efectivo
    // for (int i = 0; i < num_pts; i++) if (distancia(x, y, pt_x[i], pt_y[i]) <= radio) conteo++;
    return conteo;
}

void recocido_simulado() {
    double temperatura = 6000.0;  // Temperatura inicial
    double mejor_local_x = mejor_x, mejor_local_y = mejor_y;
    int mejor_local_valor = evaluar(mejor_local_x, mejor_local_y);
    while (temperatura > TEMP_MINIMA) {
        // Generar nueva solución vecina
        double nueva_x = mejor_local_x + (rand() * 2.0 / RAND_MAX - 1.0) * temperatura;
        double nueva_y = mejor_local_y + (rand() * 2.0 / RAND_MAX - 1.0) * temperatura;
        int nuevo_valor = evaluar(nueva_x, nueva_y);
        double delta = nuevo_valor - mejor_local_valor;
        if (delta > 0) {
            mejor_local_x = nueva_x;
            mejor_local_y = nueva_y;
            mejor_local_valor = nuevo_valor;
            mejor_valor = max(mejor_valor, (double)mejor_local_valor);
        } else if (exp(delta / sqrt(temperatura)) > (double)rand() / RAND_MAX) {
            mejor_local_x = nueva_x;
            mejor_local_y = nueva_y;
            mejor_local_valor = nuevo_valor;
        }
        temperatura *= FACTOR_ENFRIAMIENTO;
    }
}

int main() {
    srand(time(0));
    // Lectura de datos inicial (omitted for brevity)
    // Inicializar mejor_x, mejor_y como el centroide de los puntos
    while ((double)clock() / CLOCKS_PER_SEC <= 0.85) {
        recocido_simulado();
    }
    // Imprimir resultado
    return 0;
}

Observaciones: En problemas con múltiples casos de prueba, como encontrar el punto de Fermat, es preferible un número fijo de iteraciones en lugar de un límite de tiempo para evitar conflictos con el reloj del sistema.

Ejercicio propuesto

Problema: Dado un polígono de N vértices, encontrar el punto de Fermat (punto que minimiza la suma de distancias a todos los vértices). Implementar una solución usando recocido simulado, ajustando parámetros para convergencia.

Consideraciones: Usar inicialización en el centroide de los vértices y un número de ejecuciones del algoritmo fijo (ej. 100) para asegurar precisión.