모의 담금질

모의 담금질은 조합 문제를 푸는 데 사용할 수 있다. 여기서는 모든 125개 지점을 연결하는 경로의 길이를 최소화하기 위해 외판원 문제에 적용되었다.

모의 담금질로 해결한 120개 지점의 3차원 외판원 문제.

모의 담금질(SA)은 주어진 함수의 전역 최적해를 근사하는 확률적 기법이다. 구체적으로 이는 최적화 문제를 위한 큰 탐색 공간에서 전역 최적화를 근사하는 메타휴리스틱이다. 국소 최적해가 매우 많을 때 SA는 전역 최적해를 찾을 수 있다.[1] 이는 탐색 공간이 이산적일 때 흔히 사용된다(예: 외판원 문제, 불리언 만족도 문제, 단백질 구조 예측, 작업장 일정 계획). 사용할 수 있는 계산 자원이 정해진 문제에서는 정확한 국소 최적해를 찾으려 하기보다 근사 전역 최적해를 찾는 일이 더 중요할 수 있다. 이런 경우 SA는 경사 하강법이나 분기 한정법 같은 정확 알고리즘보다 더 적합할 수 있다. 현재 SA로 푸는 문제들은 여러 수학적 제약을 받는 다변수 목적 함수로 정식화된다. 실제로는 제약 위반을 목적 함수의 일부로서 벌점 처리할 수 있다.

유사한 기법은 Pincus (1970),[2] Khachaturyan 등(1979,[3] 1981[4]), Kirkpatrick, Gelatt 및 Vecchi (1983), Cerny (1985)를 포함하여 여러 차례 독립적으로 도입되었다.[5] 1983년에 Kirkpatrick, Gelatt Jr. 및 Vecchi는 외판원 문제의 해법에 이 접근법을 사용했다.[6] 이들은 현재의 이름인 모의 담금질도 제안했다.[7]

알고리즘의 이름은 재료를 가열하고 제어된 방식으로 냉각하여 물리적 성질을 바꾸는 기법인 금속학의 담금질에서 유래한다. 모의 담금질 알고리즘에서 구현된 이 느린 냉각 개념은 해 공간을 탐색함에 따라 더 나쁜 해를 받아들일 확률을 천천히 낮추는 것으로 해석된다. 더 나쁜 해를 받아들이면 전역 최적해를 더 광범위하게 탐색할 수 있다. 모의 담금질 알고리즘은 초기의 양의 값에서 온도를 0까지 점진적으로 낮추어 작동한다. 각 시간 단계에서 알고리즘은 현재 해에 가까운 해를 무작위로 선택하고, 그 품질을 측정하며, 더 좋은 해 또는 더 나쁜 해를 선택하는 온도 의존 확률에 따라 그 해로 이동한다.

시뮬레이션은 확률 밀도 함수에 대한 운동 방정식의 해로 수행하거나,[8][9] 확률적 표본추출 방법을 사용하여 수행할 수 있다.[6][10] 이 방법은 1953년에 N. Metropolis 등이 발표한, 열역학계의 표본 상태를 생성하는 몬테카를로 방법인 Metropolis–Hastings 알고리즘을 변형한 것이다.[11]

최댓값을 탐색하는 모의 담금질. 여기서 목표는 가장 높은 지점에 도달하는 것이다. 이 예에서는 국소 최댓값이 많으므로 단순한 언덕 오르기 알고리즘만으로는 충분하지 않다. 온도를 천천히 냉각하면 전역 최댓값을 찾는다.

일부 물리계의 상태 _s_와 최소화할 함수 E(s)는 그 상태에서 계의 내부 에너지에 비유된다. 목표는 임의의 _초기 상태_에서 계를 가능한 최소 에너지를 갖는 상태로 이끄는 것이다.

기본 반복

[편집]

각 단계에서 모의 담금질 휴리스틱은 현재 상태 _s_의 어떤 이웃 상태 _s_를 고려하고, 계를 상태 _s_로 옮길지 상태 _s_에 머무를지를 확률적으로 결정한다. 이 확률들은 궁극적으로 계가 더 낮은 에너지 상태로 이동하게 한다. 일반적으로 이 단계는 계가 응용에 충분히 좋은 상태에 도달하거나 주어진 계산 예산이 소진될 때까지 반복된다.

상태의 이웃

[편집]

해의 최적화에는 현재 상태를 보수적으로 변경하여 생성한 새 상태인 이웃 상태를 평가하는 일이 포함된다. 예를 들어 외판원 문제에서는 각 상태가 보통 방문할 도시의 순열로 정의되며, 어떤 상태의 이웃은 이 도시 중 임의의 두 개를 맞바꾸어 생성되는 순열들의 집합이다. 이웃 상태를 생성하도록 상태를 변경하는 잘 정의된 방식을 _이동_이라 하며, 서로 다른 이동은 서로 다른 이웃 상태 집합을 제공한다. 이러한 이동은 보통 현재 상태를 최소한으로 변경하며, 그 부분들(외판원 문제의 도시 연결 등)을 반복적으로 개선함으로써 해를 점진적으로 개선하려는 시도이다.

더 좋은 이웃을 계속 찾아 이동하고 더 좋은 이웃이 없는 해에 도달하면 멈추는 언덕 오르기 같은 단순 휴리스틱은 존재하는 더 나은 해들 가운데 어느 하나로 이어진다는 보장이 없다. 그 결과는 실제 최선의 해인 전역 최적해와 다를 수 있는 국소 최적해에 그치기 쉽다. 메타휴리스틱은 해의 이웃을 해 공간 탐색 수단으로 사용하며, 더 좋은 이웃을 선호하지만 국소 최적해에 갇히는 것을 피하기 위해 더 나쁜 이웃도 확률적으로 받아들인다. 충분한 시간이 주어지면 전역 최적해를 찾을 수 있다.

수용 확률

[편집]

현재 상태 $s$에서 후보 새 상태 $s_{\mathrm {new} }$로 전이할 확률은 두 상태의 에너지 $e=E(s)$ 및 $e_{\mathrm {new} }=E(s_{\mathrm {new} })$와 온도라 부르는 전역적 시간 변화 매개변수 $T$에 의존하는 수용 확률 함수 $P(e,e_{\mathrm {new} },T)$로 지정된다. 에너지가 더 작은 상태가 에너지가 더 큰 상태보다 좋다. $e_{\mathrm {new} }$가 $e$보다 클 때에도 확률 함수 $P$는 양수여야 한다. 이 특성은 이 방법이 전역 최솟값보다 나쁜 국소 최솟값에 갇히는 것을 막는다.

$T$가 0으로 수렴할 때, $e_{\mathrm {new} }>e$이면 확률 $P(e,e_{\mathrm {new} },T)$는 0으로 수렴해야 하며, 그렇지 않으면 양의 값으로 수렴해야 한다. $T$가 충분히 작으면 계는 점점 더 내리막(즉, 더 낮은 에너지값)으로 가는 이동을 선호하고 _오르막_으로 가는 이동을 피한다. $T=0$이면 절차는 내리막 전이만 수행하는 탐욕 알고리즘으로 축소된다.

모의 담금질의 원래 설명에서 확률 $P(e,e_{\mathrm {new} },T)$는 $e_{\mathrm {new} }<e$일 때 1이었다. 즉, 온도와 무관하게 내리막으로 갈 방법을 찾으면 절차는 항상 내리막으로 이동했다. 모의 담금질에 관한 많은 설명과 구현은 여전히 이 조건을 방법 정의의 일부로 취급한다. 그러나 이 조건은 방법이 작동하는 데 필수적이지 않다.

$P$ 함수는 보통 차이 $e_{\mathrm {new} }-e$가 커질수록 이동을 수용할 확률이 감소하도록 선택된다. 즉, 작은 오르막 이동이 큰 오르막 이동보다 가능성이 높다. 하지만 위 요구 사항이 충족되는 한 이 요구 사항은 엄격히 필수는 아니다.

이러한 성질에 따라 온도 $T$는 계 에너지 변화에 대한 민감도와 관련하여 계 상태 $s$의 진화를 제어하는 데 결정적 역할을 한다. 정확히 말하면 $T$가 크면 $s$의 진화는 더 거친 에너지 변화에 민감하고, $T$가 작으면 더 미세한 에너지 변화에 민감하다.

담금질 일정

[편집]

빠름

느림

냉각 일정이 모의 담금질 성능에 미치는 효과를 보여 주는 예이다. 문제는 이미지의 픽셀을 재배열하여 특정 퍼텐셜 에너지 함수를 최소화하는 것이다. 이 함수는 유사한 색이 가까운 거리에서는 서로 끌어당기고 약간 더 먼 거리에서는 서로 밀어내게 한다. 기본 이동은 인접한 두 픽셀을 교환한다. 이 이미지들은 빠른 냉각 일정(왼쪽)과 느린 냉각 일정(오른쪽)으로 얻었으며, 각각 비정질 및 결정질 고체와 유사한 결과를 낸다.

알고리즘의 명칭과 영감은 제어된 온도 변화를 요구한다. 따라서 시뮬레이션이 진행됨에 따라 온도를 점진적으로 낮춰야 한다. 알고리즘은 처음에 $T$를 높은 값으로 설정한 뒤, 사용자가 지정할 수 있지만 할당된 시간 예산의 끝 무렵에는 반드시 $T=0$으로 끝나야 하는 어떤 _담금질 일정_에 따라 각 단계에서 이를 낮춘다. 이렇게 계는 처음에는 에너지 함수의 작은 특징을 무시하면서 좋은 해를 포함하는 탐색 공간의 넓은 영역을 배회하고, 이후 더 좁아지는 저에너지 영역으로 이동하며, 마지막으로 최급강하 휴리스틱에 따라 내리막으로 이동할 것으로 기대된다.

주어진 유한 문제에서 담금질 일정을 연장하면 모의 담금질 알고리즘이 전역 최적 해와 함께 종료할 확률은 1에 접근한다.[12] 그러나 이 이론적 결과는 특별히 유용하지 않은데, 유의미한 성공 확률을 보장하는 데 필요한 시간은 보통 해 공간의 완전 탐색에 필요한 시간을 초과하기 때문이다.[13]

다음 의사코드는 위에서 설명한 모의 담금질 휴리스틱을 제시한다. 상태 s 0에서 시작하여 최대 k max 단계가 수행될 때까지 계속한다. 이 과정에서 neighbour(s) 호출은 주어진 상태 s의 무작위 선택 이웃을 생성해야 한다. random(0, 1) 호출은 [0, 1] 범위의 값을 균등 무작위로 선택하여 반환해야 한다. 담금질 일정은 temperature(r) 호출로 정의되며, 지금까지 소진된 시간 예산의 비율 r이 주어졌을 때 사용할 온도를 산출해야 한다.

• s = s 0으로 둔다

• k = 0부터 k max까지(제외):

  • T ← temperature( 1 - (k+ 1 )/k max )
  • 무작위 이웃을 선택한다. s new ← neighbour(s)
  • P(E(s), E(s new), T) ≥ random(0, 1)이면:
    • s ← s new

• 출력: 최종 상태 s

매개변수 선택

[편집]

모의 담금질 방법을 특정 문제에 적용하려면 상태 공간, 에너지(목표) 함수 E(), 후보 생성 절차 neighbour(), 수용 확률 함수 P(), 초기 온도 init_temp를 포함하는 담금질 일정 temperature()라는 매개변수를 지정해야 한다. 이 선택들은 방법의 효과에 큰 영향을 줄 수 있다. 불행히도 모든 문제에 좋은 이러한 매개변수 선택은 없으며, 주어진 문제에 대한 최선의 선택을 찾는 일반적 방법도 없다. 다음 절에서는 몇 가지 일반 지침을 제시한다.

충분히 가까운 이웃

[편집]

모의 담금질은 꼭짓점이 가능한 모든 상태이고 꼭짓점을 연결하는 간선이 후보 이동인 탐색 그래프 위의 무작위 보행으로 모델링할 수 있다. neighbour() 함수의 필수 요건은 초기 상태에서 전역 최적해일 수 있는 임의 상태까지 이 그래프상에서 충분히 짧은 경로를 제공해야 한다는 것이다. 탐색 그래프의 지름은 작아야 한다. 예를 들어 위 외판원 예에서 n= 20개 도시의 탐색 공간은 n!= 2,432,902,008,176,640,000 (2.4퀸틸리언)개 상태를 갖는다. 하지만 각 꼭짓점의 이웃 수는 \sum _{k=1}^{n-1}k={\frac {n(n-1)}{2}}=190}개 간선($n \choose 2$에서 유래)이고, 그래프의 지름은 $n-1$이다.

전이 확률

[편집]

특정 문제에서 모의 담금질의 동작을 조사하려면 알고리즘 구현에서 이루어진 다양한 설계 선택으로부터 생기는 _전이 확률_을 고려하는 것이 유용할 수 있다. 탐색 그래프의 각 간선 $(s,s')$에 대해, 전이 확률은 현재 상태가 $s$일 때 모의 담금질 알고리즘이 상태 $s'$로 이동할 확률로 정의된다. 이 확률은 temperature()로 지정되는 현재 온도, neighbour() 함수가 후보 이동을 생성하는 순서, 수용 확률 함수 P()에 의존한다. 후보들은 순차적으로 검사되므로 전이 확률은 단순히 $P(e,e',T)$가 아님에 유의해야 한다.

수용 확률

[편집]

neighbour(), P(), temperature()의 명세는 일부 중복된다. 실제로는 많은 문제에 같은 수용 함수 P()를 사용하고, 특정 문제에 따라 다른 두 함수를 조정하는 것이 일반적이다.

Kirkpatrick 등의 방법 정식화에서 수용 확률 함수 P(e, e', T)는 e' < e이면 1, 그렇지 않으면 $\exp(-(e'-e)/T)$로 정의되었다. 이 공식은 물리계의 전이와의 유추로 피상적으로 정당화되었다. 이는 T=1이고 Metropolis–Hastings의 제안 분포가 대칭인 경우의 Metropolis–Hastings 알고리즘에 해당한다. 하지만 Metropolis–Hastings에서 제안 분포와 유사한 neighbour() 함수가 대칭이 아니거나 전혀 확률적이지 않을 때에도 이 수용 확률은 모의 담금질에 흔히 쓰인다. 그 결과 모의 담금질 알고리즘의 전이 확률은 유사한 물리계의 전이와 일치하지 않으며, 일정한 온도 T에서 장기 상태 분포는 어떤 온도에서든 그 물리계 상태에 대한 열역학적 평형 분포와 닮을 필요가 없다. 그럼에도 모의 담금질에 대한 대부분의 설명은 원래 수용 함수를 가정하며, 이는 아마도 많은 구현에 하드코딩되어 있을 것이다.

1990년에 Moscato와 Fontanari[14], 그리고 독립적으로 Dueck와 Scheuer[15]는 확률적 수용 규칙에 기초하지 않는 결정론적 갱신이 최종 품질에 영향을 주지 않으면서 최적화 과정을 가속할 수 있다고 제안했다. Moscato와 Fontanari는 연구에서 임계값 갱신 담금질의 “비열” 곡선과 유사한 것을 관찰하여, “모의 담금질 알고리즘에서 Metropolis 갱신의 확률성은 준최적 최솟값 탐색에서 중요한 역할을 하지 않는다”고 결론지었다. 대신 이들은 “고온에서 비용 함수 지형의 평활화와 냉각 과정 중 최솟값의 점진적 정의가 모의 담금질 성공의 핵심 요소”라고 제안했다. 이 방법은 이후 Dueck와 Scheuer의 명칭에 따라 “임계값 수용”이라는 이름으로 널리 알려졌다. 2001년에 Franz, Hoffmann 및 Salamon은 비용 또는 에너지 지형 위의 무작위 보행을 시뮬레이션하는 큰 알고리즘 부류 안에서 결정론적 갱신 전략이 실제로 최적임을 보였다.[16]

효율적인 후보 생성

[편집]

후보 생성기 neighbour()를 선택할 때는 모의 담금질 알고리즘의 몇 번 반복 후 현재 상태가 무작위 상태보다 훨씬 낮은 에너지를 가질 것으로 예상된다는 점을 고려해야 한다. 따라서 일반적으로 목적지 상태 $s'$의 에너지가 현재 상태의 에너지와 비슷할 법한 후보 이동 쪽으로 생성기를 편향해야 한다. 이 휴리스틱은 Metropolis–Hastings 알고리즘의 주원리로서, 매우 좋은 후보 이동과 매우 나쁜 후보 이동을 모두 배제하는 경향이 있다. 그러나 전자는 보통 후자보다 훨씬 드물므로, 이 휴리스틱은 일반적으로 매우 효과적이다.

예를 들어 위 외판원 문제에서 저에너지 순회의 연속된 두 도시를 교환하면 에너지(길이)에 미치는 영향은 작을 것으로 예상된다. 반면 임의의 두 도시를 교환하면 길이가 줄어들기보다 늘어날 가능성이 훨씬 높다. 따라서 후자는 최적해까지 다소 더 짧은 경로를 제공할 수 있음에도($n-1$회 교환, $n(n-1)/2$회 대신), 연속 교환 이웃 생성기가 임의 교환 생성기보다 더 좋은 성능을 낼 것으로 예상된다.

이 휴리스틱을 더 정확히 말하면, $P(E(s),E(s'),T)$가 큰 첫 후보 상태 $s'$를 시도해야 한다는 것이다. 위의 “표준” 수용 함수 $P$에서는 $E(s')-E(s)$가 $T$ 정도 또는 그보다 작다는 뜻이다. 따라서 위 외판원 예에서는 무작위 두 도시를 교환하되, 도시 쌍을 선택할 확률이 두 도시 사이 거리가 $T$를 넘어서 증가함에 따라 사라지는 neighbour() 함수를 사용할 수 있다.

후보 생성기 neighbour()를 선택할 때는 “깊은” 국소 최솟값, 즉 모든 이웃 상태보다 훨씬 낮은 에너지를 갖는 상태(또는 연결된 상태 집합)의 수도 줄이려 해야 한다. 에너지 함수의 이러한 폐쇄된 집수 분지는 모의 담금질 알고리즘을 높은 확률로(대략 분지 안 상태 수에 비례) 매우 긴 시간 동안(대략 주변 상태와 분지 바닥 사이 에너지 차이에 지수적으로 비례) 가둘 수 있다.

일반적으로 이 목표를 만족하면서 비슷한 에너지를 가진 후보를 우선하는 후보 생성기를 설계하는 것은 불가능하다. 한편 생성기를 비교적 간단히 변경하여 모의 담금질의 효율을 크게 개선할 수 있는 경우가 많다. 예를 들어 외판원 문제에서는 길이가 거의 같은 두 순회 $A$, $B$를 쉽게 보일 수 있다. 이때 (1) $A$는 최적이고, (2) $A$를 $B$로 변환하는 모든 도시 쌍 교환 순서는 둘보다 훨씬 긴 순회를 거치며, (3) $A$는 연속된 도시 집합을 뒤집어(순서를 역전하여) $B$로 변환할 수 있다. 이 예에서 생성기가 무작위 쌍 교환만 수행하면 $A$와 $B$는 서로 다른 “깊은 분지”에 놓이지만, 생성기가 무작위 구간 뒤집기를 수행하면 같은 분지에 놓인다.

모의 담금질을 정당화하는 데 쓰이는 물리적 유추는 냉각 속도가 충분히 낮아 현재 상태의 확률 분포가 항상 열역학적 평형에 가까움을 가정한다. 불행히도 온도 변화 후 평형이 회복될 때까지 기다려야 하는 시간인 _이완 시간_은 에너지 함수의 “지형”과 현재 온도에 크게 의존한다. 모의 담금질 알고리즘에서 이완 시간은 후보 생성기에도 매우 복잡한 방식으로 의존한다. 이 모든 매개변수는 보통 모의 담금질 알고리즘에 블랙박스 함수로 제공된다는 점에 유의하라. 그러므로 이상적 냉각 속도는 미리 결정할 수 없으며 문제별로 경험적으로 조정해야 한다. 적응형 모의 담금질 알고리즘은 냉각 일정을 탐색 진행 상황에 연결하여 이 문제를 다룬다. 열역학적 모의 담금질 같은 다른 적응형 접근법은 [17] 열역학 법칙에 따라 두 상태 간 에너지 차이에 기초하여 각 단계의 온도를 자동으로 조정한다.

항상 현재 상태에서 이동하기보다 상당히 더 좋았던 해로 되돌아가는 것이 더 나을 때도 있다. 이 과정을 모의 담금질의 _재시작_이라 한다. 이를 위해 $s$와 $e$를 $\text{sbest}$ 및 $\text{ebest}$로 설정하고, 필요하면 담금질 일정도 재시작한다. 재시작 결정은 여러 기준에 기초할 수 있다. 대표적으로 고정된 단계 수에 따른 재시작, 현재 에너지가 지금까지 얻은 최선 에너지와 비교하여 지나치게 높은지에 따른 재시작, 무작위 재시작 등이 있다.

• 상호작용 Metropolis–Hasting 알고리즘(순차 몬테카를로라고도 함[18])은 모의 담금질 이동을 상호작용 재활용 메커니즘을 갖춘 가장 적합한 개체의 수용-거부와 결합한다.

• 양자 담금질은 목표 함수의 높지만 얇은 장벽을 통과하기 위해 열적 요동 대신 “양자 요동”을 사용한다.

• 확률적 터널링은 온도가 낮아짐에 따라 모의 담금질이 국소 최솟값에서 탈출하기 어려워지는 문제를 장벽을 ‘터널링’하여 극복하려 한다.

• 타부 탐색은 보통 더 낮은 에너지의 이웃 상태로 이동하지만, 국소 최솟값에 갇히면 오르막 이동을 수행하고 이미 본 해의 “금지 목록”을 유지하여 순환을 피한다.

• 이중상 진화는 탐색 공간의 상변화를 활용하여 국소 탐색과 전역 탐색 사이를 매개하는 알고리즘과 과정의 계열이며, 모의 담금질도 여기에 속한다.

• 반응형 탐색 최적화는 알고리즘의 자유 매개변수를 문제, 인스턴스, 현재 해 주변의 국소 상황 특성에 맞춰 자체 조정하는 내부 피드백 고리를 추가하여 기계 학습과 최적화를 결합하는 데 초점을 둔다.

• 유전 알고리즘은 하나의 해만이 아니라 해의 풀을 유지한다. 새 후보 해는 SA처럼 “돌연변이”로만 생성되는 것이 아니라 풀에서 나온 두 해의 “재조합”으로도 생성된다. SA에서 쓰이는 것과 유사한 확률 기준은 돌연변이 또는 결합 후보를 선택하고 풀에서 초과 해를 버리는 데 사용된다.

• 밈 알고리즘은 협력과 경쟁을 모두 수행하는 에이전트 집합을 활용하여 해를 탐색한다. 때로 에이전트의 전략은 재조합 전에 고품질 해를 얻기 위한 모의 담금질 절차를 포함한다.[19] 담금질은 탐색의 다양성을 높이는 메커니즘으로도 제안되었다.[20]

• 점진적 최적화는 최적화하면서 목표 함수를 점진적으로 “평활화”한다.

• 개미 군집 최적화(ACO)는 많은 개미(또는 에이전트)를 사용해 해 공간을 가로지르고 국소적으로 생산적인 영역을 찾는다.

• 교차 엔트로피 방법(CE)은 매개변수화된 확률 분포를 통해 후보 해를 생성한다. 다음 반복에서 더 좋은 표본을 생성하도록 교차 엔트로피 최소화를 통해 매개변수를 갱신한다.

• 하모니 탐색은 각 음악가가 함께 최선의 화음을 찾기 위해 음을 연주하는 즉흥 연주 음악가를 모방한다.

• 확률적 최적화는 모의 담금질과 수많은 다른 접근법을 포함하는 포괄적 방법 집합이다.

• 입자 군집 최적화는 군집 지능을 본뜬 알고리즘으로, 탐색 공간에서 최적화 문제의 해를 찾거나 목표가 있을 때의 사회적 행동을 모델링하고 예측한다.

• 주자-뿌리 알고리즘(RRA)은 자연 속 식물의 주자와 뿌리에서 영감을 받아 단봉 및 다봉 문제를 해결하는 메타휴리스틱 최적화 알고리즘이다.

• 지능형 물방울 알고리즘(IWD)은 자연 물방울의 행동을 모방하여 최적화 문제를 푼다.

• 병렬 템퍼링은 잠재 장벽을 극복하기 위해 서로 다른 온도(또는 해밀토니언)에서 모델 복사본을 시뮬레이션한다.

• 다목적 모의 담금질 알고리즘은 다목적 최적화에 사용되어 왔다.[21]

• 적응형 모의 담금질

• 자동 레이블 배치

• 조합 최적화

• 이중상 진화

• 컴퓨터 비전의 그래프 절단

• 지능형 물방울 알고리즘

• 마르코프 연쇄

• 분자 동역학

• 다학제 최적화

• 입자 군집 최적화

• 배치 및 배선

• 양자 담금질

• 외판원 문제

1. ↑"What is Simulated Annealing?". www.cs.cmu.edu. 2023-05-13에 확인함.
2. ↑Pincus, Martin (Nov–Dec 1970). "A Monte-Carlo Method for the Approximate Solution of Certain Types of Constrained Optimization Problems". Journal of the Operations Research Society of America. 18 (6): 967–1235. doi:10.1287/opre.18.6.1225.
3. ↑Khachaturyan, A.: Semenovskaya, S.: Vainshtein B., Armen (1979). "Statistical-Thermodynamic Approach to Determination of Structure Amplitude Phases". Soviet Physics Crystallography. 24 (5): 519–524.{{cite journal}}: CS1 유지 관리: 저자 목록에 여러 이름(링크)
4. ↑Khachaturyan, A.; Semenovskaya, S.; Vainshtein, B. (1981). "The Thermodynamic Approach to the Structure Analysis of Crystals". Acta Crystallographica. A37 (5): 742–754. Bibcode:1981AcCrA..37..742K. doi:10.1107/S0567739481001630.{{cite journal}}: CS1 유지 관리: 저자 목록에 여러 이름(링크)
5. ↑Laarhoven, P. J. M. van (Peter J. M.) (1987). Simulated annealing: theory and applications. Aarts, E. H. L. (Emile H. L.). Dordrecht: D. Reidel. ISBN90-277-2513-6. OCLC15548651.
6. 12Kirkpatrick, S.; Gelatt Jr, C. D.; Vecchi, M. P. (1983). "Optimization by Simulated Annealing". Science. 220 (4598): 671–680. Bibcode:1983Sci...220..671K. CiteSeerX10.1.1.123.7607. doi:10.1126/science.220.4598.671. JSTOR1690046. PMID17813860. S2CID205939.
7. ↑Kirkpatrick, S. (1984). "Optimization by simulated annealing: Quantitative studies." Journal of Statistical Physics, 34(5-6), 975-986.
8. ↑Khachaturyan, A.; Semenovskaya, S.; Vainshtein, B. (1979). "Statistical-Thermodynamic Approach to Determination of Structure Amplitude Phases". Sov.Phys. Crystallography. 24 (5): 519–524.
9. ↑Khachaturyan, A.; Semenovskaya, S.; Vainshtein, B. (1981). "The Thermodynamic Approach to the Structure Analysis of Crystals". Acta Crystallographica. 37 (A37): 742–754. Bibcode:1981AcCrA..37..742K. doi:10.1107/S0567739481001630.
10. ↑Černý, V. (1985). "Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm". Journal of Optimization Theory and Applications. 45: 41–51. doi:10.1007/BF00940812. S2CID122729427.
11. ↑Metropolis, Nicholas; Rosenbluth, Arianna W.; Rosenbluth, Marshall N.; Teller, Augusta H.; Teller, Edward (1953). "Equation of State Calculations by Fast Computing Machines". The Journal of Chemical Physics. 21 (6): 1087. Bibcode:1953JChPh..21.1087M. doi:10.1063/1.1699114. OSTI4390578. S2CID1046577.
12. ↑Granville, V.; Krivanek, M.; Rasson, J.-P. (1994). "Simulated annealing: A proof of convergence". IEEE Transactions on Pattern Analysis and Machine Intelligence. 16 (6): 652–656. Bibcode:1994ITPAM..16..652G. doi:10.1109/34.295910.
13. ↑Nolte, Andreas; Schrader, Rainer (1997), "A Note on the Finite Time Behaviour of Simulated Annealing", Operations Research Proceedings 1996, vol.1996, Berlin, Heidelberg: Springer Berlin Heidelberg, pp.175–180, doi:10.1007/978-3-642-60744-8_32, ISBN978-3-540-62630-5, 2023-02-06에 확인함
14. ↑Moscato, P.; Fontanari, J.F. (1990), "Stochastic versus deterministic update in simulated annealing", Physics Letters A, 146 (4): 204–208, Bibcode:1990PhLA..146..204M, doi:10.1016/0375-9601(90)90166-L
15. ↑Dueck, G.; Scheuer, T. (1990), "Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing", Journal of Computational Physics, 90 (1): 161–175, Bibcode:1990JCoPh..90..161D, doi:10.1016/0021-9991(90)90201-B, ISSN0021-9991
16. ↑Franz, A.; Hoffmann, K.H.; Salamon, P (2001), "Best optimal strategy for finding ground states", Physical Review Letters, 86 (3): 5219–5222, doi:10.1103/PhysRevLett.86.5219, PMID11384462
17. ↑De Vicente, Juan; Lanchares, Juan; Hermida, Román (2003). "Placement by thermodynamic simulated annealing". Physics Letters A. 317 (5–6): 415–423. Bibcode:2003PhLA..317..415D. doi:10.1016/j.physleta.2003.08.070.
18. ↑Del Moral, Pierre; Doucet, Arnaud; Jasra, Ajay (2006). "Sequential Monte Carlo samplers". Journal of the Royal Statistical Society, Series B. 68 (3): 411–436. arXiv:cond-mat/0212648. doi:10.1111/j.1467-9868.2006.00553.x. S2CID12074789.
19. ↑Moscato, Pablo (June 1993). "An introduction to population approaches for optimization and hierarchical objective functions: A discussion on the role of tabu search". Annals of Operations Research. 41 (2): 85–121. doi:10.1007/BF02022564. S2CID35382644.
20. ↑Moscato, P. (1989). "On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms". Caltech Concurrent Computation Program (보고서 826).
21. ↑Deb, Bandyopadhyay (June 2008). "A Simulated Annealing-Based Multiobjective Optimization Algorithm: AMOSA". IEEE Transactions on Evolutionary Computation. 12 (3): 269–283. Bibcode:2008ITEC...12..269B. doi:10.1109/TEVC.2007.900837. S2CID12107321.

• A. Das and B. K. Chakrabarti (편), Quantum Annealing and Related Optimization Methods, Lecture Note in Physics, Vol. 679, Springer, Heidelberg (2005)

• Weinberger, E. (1990). "Correlated and uncorrelated fitness landscapes and how to tell the difference". Biological Cybernetics. 63 (5): 325–336. doi:10.1007/BF00202749. S2CID851736.

• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 10.12. Simulated Annealing Methods". Numerical Recipes: The Art of Scientific Computing (제3판). New York: Cambridge University Press. ISBN978-0-521-88068-8. 원본에서 2011-08-11에 보관됨. 2011-08-13에 확인함.

• Strobl, M.A.R.; Barker, D. (2016). "On simulated annealing phase transitions in phylogeny reconstruction". Molecular Phylogenetics and Evolution. 101: 46–55. Bibcode:2016MolPE.101...46S. doi:10.1016/j.ympev.2016.05.001. PMC4912009. PMID27150349.

• V.Vassilev, A.Prahova: "The Use of Simulated Annealing in the Control of Flexible Manufacturing Systems", International Journal Information Theories & Applications, VOLUME 6/1999

• D. Thiel, "Simulated Annealing: From Statistical Thermodynamics to Combinatory Problems Solving", Encyclopedia of Life Support Systems UNESCO – EOLSS, Chapter Systems Science and Cybernetics – Vol. III

• Simulated Annealing 모의 담금질을 실험할 수 있는 JavaScript 앱. 소스 코드 포함.

• "General Simulated Annealing Algorithm"보관됨 2008-09-23 Wayback Machine에서. 일반 모의 담금질 연습을 위한 오픈 소스 MATLAB 프로그램.

• Self-Guided Lesson on Simulated Annealing Wikiversity 프로젝트.

• Google in superposition of using, not using quantum computer Ars Technica는 Google이 사용하는 D-Wave 컴퓨터가 실제로는 효율적인 모의 담금질 보조 프로세서일 가능성을 논한다.

• 모의 담금질 기반 다목적 최적화 알고리즘: AMOSA.