Introdução ao Recozimento Simulado

O Recozimento Simulado (Simulated Annealing - SA) é um algoritmo metaheurístico e probabilístico utilizado para aproximar a solução ótima global em espaços de busca vastos e complexos. Diferente de algoritmos de busca local tradicioanis que podem ficar presos em ótimos locais (especialmente em funções multimodais), o SA introduz uma componente estocástica que permite a exploração de soluções subótimas temporárias, facilitando a fuga de mínimos ou máximos locais.

Fundamentos Físicos e Mapeamento Computacional

A inspiração para este algoritmo provém da termodinâmica, especificamente do processo de recozimento de metais. Na metalurgia, um material é aquecido a uma temperatura elevada, aumentando a energia interna e a desordem de seus átomos. Em seguida, o resfriamento é realizado de forma lenta e controlada, permitindo que a estrutura atômica se reorganize em um estado de mínima energia (equilíbrio termodinâmico).

Na computação, esse processo é mapeado da seguinte forma:

• Temperatura: Controla a probabilidade de aceitar soluções piores. Inicia-se alta e decai gradualmente.
• Energia: Representa o valor da função objetivo que se deseja minimizar (ou maximizar).
• Estado: Uma configuração ou solução candidata no espaço de busca.

Mecanismo e Critério de Metropolis

A execução do algoritmo requer a definição de uma temperatura inicial T, tipicamente entre 103 e 105, e uma taxa de resfriamento α (ou fator de decaimento), geralmente entre 0.9 e 0.9995. A cada iteração, a temperatura é atualizada por T = T × α até atingir um limiar mínimo.

A transição entre estados segue o Critério de Metropolis. Seja ΔE a diferença de energia entre o novo estado e o estado atual (ΔE = Enovo - Eatual). Se o novo estado for melhor (ΔE < 0 para minimização), ele é aceito incondicionalmente. Caso contrário, ele é aceito com uma probabilidade P dada por:

P = e-ΔE / T

Um número aleatório r ∈ [0, 1) é gerado. Se P > r, a solução pior é aceita. Conforme a temperatura T diminui, a probabilidade de aceitar soluções piores decai exponencialmente, convergindo o algoritmo para uma busca puramente gulosa nas fases finais.

Estrutura Básica em Código

Abaixo está um modelo genérico da implementação do algoritmo em C++. As variáveis e a estrutura foram organizadas para clareza e reutilização.

#include <iostream>
#include <cmath>
#include <cstdlib>

// Gera um número pseudoaleatório no intervalo [0, 1)
double gerarProbabilidade() {
    return static_cast<double>(rand()) / RAND_MAX;
}

// Função objetivo: calcula a "energia" de um dado estado
double avaliarEnergia(double parametro1, double parametro2) {
    // Lógica de cálculo da função objetivo
    return 0.0; 
}

void recozimentoSimulado() {
    double temperatura = 10000.0;      // Temperatura inicial
    double temperaturaMinima = 1e-5;   // Critério de parada
    double taxaResfriamento = 0.995;   // Fator de decaimento
    
    double estadoAtual = 0.0;          // Solução inicial
    double melhorEnergia = avaliarEnergia(estadoAtual, 0.0);

    while (temperatura > temperaturaMinima) {
        // Gera um estado vizinho (a lógica depende do problema)
        double proximoEstado = estadoAtual + temperatura * (gerarProbabilidade() * 2 - 1);
        
        double energiaAtual = avaliarEnergia(estadoAtual, 0.0);
        double energiaProxima = avaliarEnergia(proximoEstado, 0.0);
        double deltaE = energiaProxima - energiaAtual;
        
        // Critério de Metropolis
        if (deltaE < 0 || exp(-deltaE / temperatura) > gerarProbabilidade()) {
            estadoAtual = proximoEstado;
            if (energiaProxima < melhorEnergia) {
                melhorEnergia = energiaProxima;
            }
        }
        
        temperatura *= taxaResfriamento;
    }
}

Estudo de Caso 1: Ponto de Equilíbrio de Toças

Considere um probleam onde n massas estão conectadas por cordas a um nó central sobre uma mesa, passando por orifícios. O objetivo é encontrar a posição de equilíbrio (x, y) do nó central que minimiza a energia potencial total do sistema. A energia do sistema é proporcional à soma das distâncias do nó até cada orifício, ponderada pela massa correspondente.

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

struct Massa {
    double x, y, peso;
};

int numMassas;
vector<Massa> objetos;
double melhorX, melhorY, menorEnergia;

double gerarAleatorio() {
    return static_cast<double>(rand()) / RAND_MAX;
}

double calcularEnergia(double cx, double cy) {
    double energiaTotal = 0.0;
    for (int i = 0; i < numMassas; ++i) {
        double dx = objetos[i].x - cx;
        double dy = objetos[i].y - cy;
        energiaTotal += sqrt(dx * dx + dy * dy) * objetos[i].peso;
    }
    if (energiaTotal < menorEnergia) {
        menorEnergia = energiaTotal;
        melhorX = cx;
        melhorY = cy;
    }
    return energiaTotal;
}

void executarSA() {
    double temp = 10000.0;
    double atualX = melhorX, atualY = melhorY;
    
    while (temp > 1e-6) {
        double novoX = atualX + temp * (gerarAleatorio() * 2 - 1);
        double novoY = atualY + temp * (gerarAleatorio() * 2 - 1);
        
        double delta = calcularEnergia(novoX, novoY) - calcularEnergia(atualX, atualY);
        
        if (exp(-delta / temp) > gerarAleatorio()) {
            atualX = novoX;
            atualY = novoY;
        }
        temp *= 0.9995;
    }
    
    // Refinamento final na vizinhança da melhor solução encontrada
    for (int i = 0; i < 5000; ++i) {
        double novoX = melhorX + temp * (gerarAleatorio() * 2 - 1);
        double novoY = melhorY + temp * (gerarAleatorio() * 2 - 1);
        calcularEnergia(novoX, novoY);
    }
}

int main() {
    srand(time(nullptr));
    cin >> numMassas;
    objetos.resize(numMassas);
    
    double somaX = 0, somaY = 0;
    for (int i = 0; i < numMassas; ++i) {
        cin >> objetos[i].x >> objetos[i].y >> objetos[i].peso;
        somaX += objetos[i].x;
        somaY += objetos[i].y;
    }
    
    melhorX = somaX / numMassas;
    melhorY = somaY / numMassas;
    menorEnergia = calcularEnergia(melhorX, melhorY);
    
    executarSA();
    
    printf("%.3f %.3f\n", melhorX, melhorY);
    return 0;
}

Estudo de Caso 2: Problema do Clique Máximo

Em um grafo não direcionado, o objetivo é encontrar o maior subconjunto de vértices onde todos são adjacentes entre si (Clique Máximo). Para aplicar o SA, o espaço de busca é definido como o conjunto de todas as permutações dos vértices. A função de avaliação percorre a permutação e adiciona vértices ao clique desde que sejam adjacentes a todos os já selecionados. A aleatoriedade na permutação permite explorar diferentes formações de cliques.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int numVertices;
bool matrizAdj[60][60];
int permutacaoAtual[60], melhorPermutacao[60];
int tamanhoMaximo = 0;

int gerarIndice(int limite) {
    return rand() % limite;
}

double gerarProbabilidade() {
    return static_cast<double>(rand()) / RAND_MAX;
}

int avaliarClique() {
    int tamanho = 0;
    vector<int> clique;
    
    for (int i = 0; i < numVertices; ++i) {
        int v = permutacaoAtual[i];
        bool podeAdicionar = true;
        for (int u : clique) {
            if (!matrizAdj[v][u]) {
                podeAdicionar = false;
                break;
            }
        }
        if (podeAdicionar) {
            clique.push_back(v);
            tamanho++;
        }
    }
    return tamanho;
}

void otimizarSA() {
    double temp = 1.0;
    for (int i = 0; i < numVertices; ++i) {
        permutacaoAtual[i] = melhorPermutacao[i];
    }
    
    while (temp > 1e-8) {
        int idx1 = gerarIndice(numVertices);
        int idx2 = gerarIndice(numVertices);
        swap(permutacaoAtual[idx1], permutacaoAtual[idx2]);
        
        int tamanhoAtual = avaliarClique();
        int delta = tamanhoAtual - tamanhoMaximo;
        
        if (delta > 0) {
            tamanhoMaximo = tamanhoAtual;
            for (int i = 0; i < numVertices; ++i) {
                melhorPermutacao[i] = permutacaoAtual[i];
            }
        } else if (exp(delta / temp) > gerarProbabilidade()) {
            // Mantém a mudança (não reverte)
        } else {
            swap(permutacaoAtual[idx1], permutacaoAtual[idx2]); // Reverte a mudança
        }
        temp *= 0.95;
    }
}

int main() {
    srand(time(nullptr));
    cin >> numVertices;
    
    int u, v;
    while (cin >> u >> v) {
        matrizAdj[u][v] = matrizAdj[v][u] = true;
    }
    
    for (int i = 0; i < numVertices; ++i) {
        melhorPermutacao[i] = i + 1;
    }
    
    // Execução contínua dentro do limite de tempo
    clock_t inicio = clock();
    while (clock() - inicio < 0.95 * CLOCKS_PER_SEC) {
        otimizarSA();
    }
    
    cout << tamanhoMaximo << endl;
    return 0;
}

Otimização Baseada em Tempo de Execução

Em problemas competitivos ou com restrições rígidas de tempo, executar o algoritmo uma única vez pode não ser suficiente para garantir a convergência para o ótimo global. Uma técnica eficaz é encapsular a execução do SA em um loop controlado por tempo. Utilizando a função clock(), o algoritmo é reiniciado múltiplas vezes até que o tempo limite (por exemplo, 95% do tempo total permitido) seja atingido. Isso maximiza o número de explorações do espaço de busca sem exceder o tempo limite da aplicação.