He realizado algunas pruebas de diferentes temperaturas iniciales en mi algoritmo de recocido de simulación y noté que la temperatura inicial tiene un efecto en el rendimiento del algoritmo.
¿Hay alguna forma de calcular una buena temperatura inicial?
optimization
artificial-intelligence
heuristics
Indefinido
fuente
fuente
Respuestas:
Como señaló Thomas Klimpel en los comentarios, a menudo se usa una cierta probabilidad de aceptación, que es igual a0.8 . El siguiente es un método iterativo simple para encontrar una temperatura inicial adecuada, propuesto por Ben-Ameur en 2004 [1]. A continuación, t es una transición estrictamente positiva, maxt y mint son los estados después y antes de la transición, δt la diferencia de costo mimaxt- Emint y La probabilidad de generar una transicióncuando los estados de energía se distribuyen de conformidad con la distribución estacionariaπmint1El | norte( mint) | t
Finalmente, es la probabilidad de aceptar una transición positiva . Ahora, podemos tener una estimación de la probabilidad de aceptación basada en un conjunto "aleatorio" de transiciones positivas:t chi chi ( T ) Sexp ( - δt/ T) t χ^ χ ( T) S
Queremos encontrar una temperatura tal que , donde es la probabilidad de aceptación que deseamos. χ ( T 0 ) = χ 0 χ 0 ∈ ] 0 , 1 [T0 χ(T0)=χ0 χ0∈]0,1[
, dondepes un número real≥1.
[1] Ben-Ameur, Walid. "Calcular la temperatura inicial del recocido simulado". Optimización computacional y aplicaciones 29, no. 3 (2004): 369-385.
fuente
Este es un tema muy avanzado relacionado con obtener optimismos muy ajustados. Según tengo entendido, la temperatura inicial generalmente se considera parte de una estrategia de "programa de temperatura" para la cual hay una investigación profunda. en otras palabras, tanto la condición de temperatura inicial como el algoritmo de disminución de temperatura (que no menciona) afectan los resultados generales de optimización. Las estrategias simples o la heurística para ambos a menudo producen resultados buenos o "suficientemente buenos".
Sin embargo, hay al menos un documento que estudia la temperatura inicial solo. [1] La conclusión es que, a menos que esté haciendo un trabajo muy avanzado, tratar la temperatura inicial como un parámetro del problema e iterar sobre diferentes temperaturas iniciales como parte de la optimización general [después de descubrir que sí afecta los resultados] es muy razonable y Una práctica probablemente extendida.
o, incluso, simplemente elegir una temperatura inicial que dé buenos resultados también es común (parecería algo sorprendente y no es frecuente que los resultados de optimización de la instancia del problema varíen sustancialmente de un "mejor" parámetro de temperatura inicial encontrado por prueba y error) . como señaló dhj, algunos problemas serán más sensibles que otros a la temperatura inicial.
[1] Cálculo de la temperatura inicial de recocido simulado Ben-Ameur 2004
[2] Un programa de recocido simulado eficiente: Derivation Lam & Delosme
[3] Control de temperatura para recocido simulado Munakata y Nakamura
fuente