Temperatura inicial no algoritmo de recozimento simulado

14

Fiz alguns testes de diferentes temperaturas iniciais no meu algoritmo de recozimento de simulação e notei que a temperatura inicial afeta o desempenho do algoritmo.

Existe alguma maneira de calcular uma boa temperatura inicial?

Indefinido
fonte
2
A temperatura inicial tem muito a ver com o domínio do problema e outros parâmetros que você está usando para a parte de descida do gradiente do algoritmo. Você pode dar mais contexto?
dhj

Respostas:

9

0,8tmin t δ t E max t - E min t π min t 1maxtmintδtEmaxt-Eminttπmint1|N(mint)|t

πEu=|N(Eu)|exp(-EEu/T)j|N(j)|exp(-Ej/T)
, em que denota o conjunto de vizinhos de .iN(Eu)Eu

Finalmente, é a probabilidade de aceitar uma transição positiva . Agora, podemos ter uma estimativa da probabilidade de aceitação base em um conjunto "aleatório" de transições positivas:t × × ( t ) Sexp(-δt/T)tχ^χ(T)S

χ^(T)=tSπmint1|N(mint)|exp(-δt/T)tSπmint1|N(mint)|=tSexp(-Emaxt/T)tSexp(-Emint/T).

Queremos encontrar uma temperatura tal que , onde χ ( T 0 ) = χ 0 χ 0] 0 , 1 [T0 0χ(T0 0)=χ0 0χ0 0]0 0,1[ seja a probabilidade de aceitação que desejamos.

S E max t E min t S T 1 T 0T0 0 é calculado por um método iterativo. Alguns estados e um vizinho para cada estado são gerados. Isto dá-nos um conjunto de transições . As energias e correspondentes aos estados do subconjunto são armazenadas. Em seguida, é escolhido um valor para , que pode ser qualquer valor positivo. SEmaxtEmintST1T0 é então encontrado com a fórmula recursiva

Tn+1=Tnln(χ^(Tn))ln(χ0)1/p
, em quep é um número real .1

Quando se aproxima de , podemos parar. agora é uma boa aproximação da temperatura inicial desejadaχ^(Tn)χ0 0TnT0 0 . Para mais explicações, provas e discussão, consulte a primeira seção do artigo original [1].


[1] Ben-Ameur, Walid. "Computando a temperatura inicial do recozimento simulado". Otimização e aplicações computacionais 29, no. 3 (2004): 369-385.

Juho
fonte
3

este é um tópico muito avançado relacionado à obtenção de ótimos indicadores muito rígidos. Pelo que entendi, a temperatura inicial é geralmente considerada parte de uma estratégia de "cronograma de temperatura" para a qual há alguma pesquisa profunda. em outras palavras, a condição inicial de temperatura e o algoritmo de redução de temperatura (que você não mencionou) afetam os resultados gerais da otimização. estratégias ou heurísticas simples para ambos geralmente produzem resultados bons ou "bons o suficiente".

há, no entanto, pelo menos um artigo que estuda a temperatura inicial sozinha. [1] o ponto principal é que, a menos que você esteja fazendo um trabalho muito avançado, tratar a temperatura inicial como um parâmetro do problema e iterar em diferentes temperaturas iniciais como parte da otimização geral [depois de descobrir que isso realmente afeta os resultados] é muito razoável e uma prática provavelmente generalizada.

ou mesmo escolher apenas uma temperatura inicial que produza bons resultados também é comum (parece surpreendente e não é frequente que os resultados da otimização da instância do problema variem substancialmente de um parâmetro de temperatura inicial "melhor" encontrado por tentativa e erro) . Como o dhj apontou, alguns problemas serão mais sensíveis do que outros à temperatura inicial.

[1] Computando a temperatura inicial do recozimento simulado Ben-Ameur 2004

[2] Um cronograma eficiente de recozimento simulado: derivação Lam & Delosme

[3] Controle de temperatura para recozimento simulado Munakata & Nakamura

vzn
fonte