SIMULATED ANNEALING

Método de busca local ou global, dependendo de certos parâmetros;

o Resfriamento lento conduz a produtos mais estáveis, estruturalmente

fortes, de menor energia;

o Durante o recozimento o material passa por vários estados possíveis

que podem significar soluções do espaço de busca;

o A energia em cada estado corresponde ao valor da função objetivo;

o A baixas temperaturas, somente estados com baixa energia têm alta

probabilidade de se tornar o estado corrente

o Global: aceita movimentos piores

o Requer codificação, métricas de vizinhança, função custo adequada;

procedimento SA

1. Seja s0 uma solução inicial, T0 a temperatura inicial, α a taxa de

resfriamento e SAmax o número máximo de iterações para se atingir o

equilíbrio térmico;

2. s ← s0; {Solução corrente}

3. s' ← s; {Melhor solução obtida até então}

4. T ← T0; {Temperatura corrente}

5. IterT ← 0; {Número de iterações na temperatura T}

6. enquanto (T > 0) faça

7. enquanto (IterT < SAmax) faça

8. IterT ← IterT + 1;

9. Gere um vizinho qualquer s’ ∈ N (s);

10. ∆ = f(s’) – f(s);

11. se (∆ < 0)

12. então

13. s ← s’;

14. se f(s’) < f(s

*

) então s

* ← s’;

15. senão

16. Tome x ∈ [0,1];

17. se x < e

-∆/(cT) então s ← s’;

18. fim-se;

19. fim-enquanto;

20. T ← α ×T;

21. IterT ← 0;

22. fim-enquanto;

23. Retorne s

*

;

fim SA;

...