시뮬레이션 어닐링 알고리즘은 어떤 알고리즘인가요?

SAA(Simulated Anneal Arithmetic)는 대규모 검색 공간에서 명제에 대한 최적의 솔루션을 찾는 데 사용되는 일반적인 확률 알고리즘입니다. 모의 어닐링은 1983년 S.Kirkpatrick, C.D.Gelatt 및 M.P.Vecchi에 의해 발명되었습니다. V.ern & yacute도 1985년에 이 알고리즘을 독립적으로 발명했습니다. 시뮬레이션 어닐링 알고리즘은 TSP 문제를 해결하는 효과적인 방법 중 하나입니다.

문제에 대한 최적의 솔루션을 찾을 때 먼저 초기 솔루션을 제공할 수 있습니다. 이때, 온도가 높고, 초기 해가 변할 확률이 높고, 온도가 낮아질수록 해가 변할 확률이 점차 감소한다. 함수 f(x)의 최소값을 풀어야 한다고 가정하면 시뮬레이션된 어닐링 알고리즘의 프로세스는 다음과 같이 설명됩니다.

새로운 솔루션을 생성하는 방법에는 여러 가지가 있습니다. 예를 들어, 솔루션이 01001101인 경우 무효화할 비트 하나를 무작위로 선택할 수 있습니다. 세 번째 비트를 선택하면 세 번째 비트가 비트 단위로 반전되어 새로운 해는 01101101이 됩니다. 이 과정은 유전자 알고리즘의 유전자 돌연변이와 다소 유사합니다. 위의 알고리즘 설명에서 각 온도 값은 새로운 솔루션을 한 번만 생성하지만 실제 문제에서는 여러 번 생성될 수 있습니다.

알고리즘의 핵심은 메트로폴리스 기준에 있습니다. 새 해의 함수 값이 작으면 새 해를 현재 해로 간주하는 것이 당연하고, 새 해의 함수 값이 크면 여전히 현재 해로 선택될 확률이 있습니다. 이 확률은 df와 관련이 있습니다. df가 클수록 새 솔루션이 더 나빠지고 현재 솔루션으로 선택될 확률이 작아집니다. 또한 이 확률은 현재 온도가 높을수록 관련이 있습니다. 온도가 높을수록 확률이 높아집니다(분자와 유사하며 열 운동이 더욱 강렬해집니다).