어닐링 시뮬레이션

이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 : '시뮬레이션 어닐링'– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2009년 12월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인)

시뮬레이션 어닐링(SA)은 주어진 함수의 전역 최적화를 근사하기 위한 확률론적 기법이다.구체적으로는 최적화 문제에 대해 대규모 검색 공간에서 글로벌 최적화를 근사화하는 메타 휴리스틱입니다.검색 공간이 분리된 경우(예: 출장 세일즈맨 문제, 부울 만족도 문제, 단백질 구조 예측 및 잡샵 스케줄링)에 자주 사용됩니다.대략적인 글로벌 최적화를 찾는 것이 일정한 시간 내에 정확한 국소 최적화를 찾는 것보다 더 중요한 문제의 경우, 경사 하강 또는 분기 및 경계와 같은 정확한 알고리즘보다 시뮬레이션 어닐링이 선호될 수 있다.

알고리즘의 이름은 물질의 물리적 특성을 변경하기 위해 가열 및 제어된 냉각을 포함하는 기술인 야금학의 아닐링에서 유래했습니다.둘 다 열역학적 자유 에너지에 의존하는 물질의 속성입니다.재료의 가열과 냉각은 온도와 열역학적 자유 에너지 또는 깁스 에너지 모두에 영향을 미칩니다.시뮬레이트 어닐링은 정확한 알고리즘이 실패하는 매우 어려운 계산 최적화 문제에 사용할 수 있습니다.일반적으로 글로벌 최소값에 대한 대략적인 해결책을 달성하지만 많은 실제 문제에 충분할 수 있습니다.

SA에 의해 해결된 문제들은 현재 여러 변수의 객관적 함수에 의해 공식화되어 있으며, 몇 가지 제약이 따른다.실제로, 제약조건은 목적 함수의 일부로서 불이익을 줄 수 있다.

유사한 기술은 핀커스(1970),^[1] 하차투리안 외 연구진(1979,^[2] 1981^[3]), 커크패트릭, 겔라트와 베치(1983), 체르니(1985)^[4]를 포함한 여러 경우에 독립적으로 도입되었다.1983년, 이 접근방식은 출장 세일즈맨 문제를 해결하기 위해 Kirkpatrick,^[5] Gelatt Jr., Vecchi에 의해 사용되었습니다.그들은 또한 그것의 현재 이름인 모의 어닐링을 제안했다.

시뮬레이션 어닐링 알고리즘에서 구현된 느린 냉각의 개념은 솔루션 공간이 탐색될수록 더 나쁜 솔루션을 받아들일 확률이 느리게 감소하는 것으로 해석됩니다.더 나쁜 솔루션을 받아들이면 글로벌 최적 솔루션을 더 폭넓게 검색할 수 있습니다.일반적으로 시뮬레이트된 어닐링 알고리즘은 다음과 같이 동작합니다.온도는 초기 양의 값에서 점차 0으로 감소합니다.각 단계에서 알고리즘은 현재 솔루션에 가까운 솔루션을 랜덤하게 선택하고 품질을 측정하여 검색 중에 각각 1(또는 양의)으로 유지되며 0으로 감소하는 더 나은 솔루션 또는 더 나쁜 솔루션을 선택하는 온도의존 확률에 따라 이동한다.

시뮬레이션은 밀도^[6][7] 함수에 대한 운동 방정식의 해법 또는 확률적 샘플링 ^[5][8]방법을 사용하여 수행할 수 있습니다.이 방법은 1953년 ^[9]N. Metropolis 등에 의해 발표된 열역학 시스템의 표본 상태를 생성하기 위한 몬테카를로 방법인 메트로폴리스-헤스팅스 알고리즘을 채택한 것이다.

개요

일부 물리적 시스템의 상태와 최소화해야 할 기능 E는 해당 상태의 시스템 내부 에너지와 유사합니다.목표는 시스템을 임의의 초기 상태에서 가능한 최소한의 에너지를 가진 상태로 만드는 것입니다.

기본 반복

각 단계에서 시뮬레이트된 아닐 휴리스틱은 현재 상태 s의 몇 가지 인접 상태 s*를 고려하여 시스템을 상태 s*로 이행할 것인지 또는 상태 s로 유지할 것인지를 확률적으로 결정한다.이러한 가능성은 궁극적으로 시스템을 낮은 에너지 상태로 이동시킵니다.통상, 이 순서는, 시스템이 애플리케이션에 충분한 상태가 될 때까지, 또는 소정의 계산 버젯이 다 될 때까지 반복됩니다.

한 나라의 이웃나라

해결책의 최적화는 주어진 상태를 보수적으로 변경함으로써 생성되는 새로운 상태인 문제 상태의 인접 상태를 평가하는 것을 포함한다.예를 들어, 여행 세일즈맨 문제에서 각 주는 일반적으로 방문할 도시의 순열로 정의되며, 모든 주의 이웃은 이러한 두 도시를 교환함으로써 생성된 순열 집합이다.인접 상태를 생성하기 위해 상태가 변경되는 잘 정의된 방식을 "이동"이라고 하며, 서로 다른 움직임은 서로 다른 일련의 인접 상태를 제공합니다.이러한 움직임에 의해, 통상, 마지막 상태의 변경이 최소한으로 억제되어, 그 부분(여행 세일즈맨의 도시 접속 등)을 반복해 개선해 나가려고 합니다.

더 나은 이웃을 찾아 더 나은 이웃이 없는 솔루션에 도달했을 때 멈추는 힐 클라이밍과 같은 단순한 휴리스틱스에서는 기존의 더 나은 솔루션 중 어느 것도 얻을 수 없다고 보장할 수 없습니다.그 결과는 쉽게 국지적인 최적일 수 있지만, 실제 최선의 솔루션은 다음과 같습니다.e는 다를 수 있는 글로벌 최적치입니다.메타휴리스틱은 솔루션 공간을 탐색하기 위한 방법으로 솔루션의 인접을 사용하고 더 나은 인접 관계를 선호하지만 로컬 최적 상태에 갇히지 않기 위해 더 나쁜 인접 관계를 수용합니다. 충분한 시간 동안 실행하면 글로벌 최적 상태를 찾을 수 있습니다.

합격 확률

현재 $상태{\displaystyle }$s(\$displaystyle s$$)$에서 후보 새 $상태{\displaystyle {}_{}}$ ${\displaystyle {\mathrm{sn}}_{}}$ e$(\$displaystyle s_{\$mathrm {new}})$로 이행할 확률은 허용 확률 $함수{\displaystyle }$ P${\displaystyle ({}_{},}$ ${\displaystyle {e\mathrm{}}_{}}$ ${\displaystyle {\mathrm{n}}_{}}$ w$)(\displaystyle$ P$(e, e_{\mathrm {new}$} $\})$에 의해 지정되며, $E$${\displaystyle (\mathrm{에너지})}$에 의존합니다.$({displaystyle$ e$=$${\displaystyle E}$$(s)}$ $및$ ${\displaystyle {e\mathrm{}}_{}}$ ${\displaystyle {\mathrm{n}}_{}}$ ${\displaystyle {\mathrm{w}}_{}}$ $=$E(${\displaystyle {\mathrm{sn}}_{}}$ e $)$ {$displaystyle e_{\mathrm {new}$ }) = $E(s_{\mathrm$ {new$}$}}) $및$ 온도라고 불리는 글로벌 시간 지연 $매개{\displaystyle }$ 변수$$T({$displaystyle$ T$)$에 따라 결정됩니다.에너지가 작은 국가가 에너지가 큰 국가보다 낫다.${\displaystyle {\mathrm{확률}}_{}}$ $함수{\displaystyle }$P(\$displaystyle$ P$)$는 e$(\$가 e$(\displaystyle$e$\})$보다 큰 $경우$에도 양의 값이어야 합니다.이 기능을 통해 메서드가 글로벌보다 나쁜 로컬 최소값에서 고착되는 것을 방지할 수 있습니다.

T$(\displaystyle$ T$)$가 0이 되는 경향이 있는 $경우{\displaystyle }$, $확률{\displaystyle }$ P$(e$ ${\displaystyle {e\mathrm{}}_{}}$ ${\displaystyle {\mathrm{n}}_{}}$ ${\displaystyle {\mathrm{w},}_{}T}$ $)(e, e_{\mathrm$ ${$$new}$},$$T)는 e n $>$ e {\$displaystyle$e_{\$mathrm$ {new$}$} >$e}$이면 0이 되는 경향이 있습니다.T$(\style$ T$)$의 값이 충분히 작을 경우 시스템은 "다운힐"(즉, 에너지 값을 낮추기 위해) 이동하는 것을 선호하고 "업힐"되는 것을 피하게 됩니다.T ${\displaystyle =}$ {$displaystyle$ T$=0}$일 때 절차는 내리막길 전환만 하는 그리디 알고리즘으로 감소합니다.

시뮬레이션 어닐링의 원래 설명에서는 e ${\displaystyle {}_{}}$$<\displaystyle e_$${\mathrm {new}},T)$의 $확률{\displaystyle }$ P$(e$$,$ ${\displaystyle {e\mathrm{}}_{}}$ $n$ ${\displaystyle {\mathrm{w}}_{}}$ {\displaystyle e_${\mathrm {new}},T$가 1로 되어 있었습니다.즉, 이 순서는 그 방법에 관계없이 항상 하향으로 이동했습니다.시뮬레이션 어닐링의 많은 설명과 구현은 여전히 이 조건을 방법의 정의의 일부로 받아들인다.단, 이 조건은 메서드가 동작하기 위해 반드시 필요한 것은 아닙니다.

$일반적$으로$$P\$displaystyle$P 함수는$$ ${\displaystyle e_{}}$-$$ \$displaystyle e_{\mathrm {new}-e}$ 차이가 $커질$ 때 이동 허용 확률이 감소하도록 선택됩니다. 즉, 작은 오르막 이동은 큰 이동보다 더 높습니다.단, 상기 요건이 충족될 경우 이 요건은 엄밀하게 필요하지 않습니다.

이러한 특성을 고려할 때 $T$는 시스템 에너지 변화에 대한 민감도와 관련하여 시스템 $상태의$$$진화를 제어하는 데 중요한 역할을 합니다$.$정확히 말하면, $T$의$$경우$, S$의 진화는 거친 에너지 변화에 민감하지만$,$ 소형 $T의$$$경우 $미세$한 에너지 변화에 민감합니다.

어닐링 스케줄

알고리즘의 이름과 영감을 얻으려면 알고리즘의 동작 특성에 온도 변동과 관련된 흥미로운 기능이 포함되어야 합니다.따라서 시뮬레이션이 진행됨에 따라 온도를 점진적으로 낮출 필요가 있습니다.알고리즘은 처음에$$T {\$displaystyle$ T$}$가 높은 값(또는 무한대)으로 설정된 $상태$에서 시작하여 사용자가 지정할 수 있는 일부 아닐 일정에 따라 각 단계에서 감소하지만 할당된 시간 버젯의 마지막에 T ${\displaystyle =}$ $(\displaystyle$ T$=0)$으로 끝나야 합니다.이와 같이 시스템은 처음에는 에너지 함수의 작은 특징을 무시하고 좋은 솔루션을 포함하는 탐색 공간의 넓은 영역을 향해 돌아다니다가 점점 좁아지는 저에너지 영역으로 표류하여 마침내 가장 가파른 하강 휴리스틱에 따라 하강할 것으로 예상된다.

임의의 유한한 문제에 대해서, 애니링 스케줄이 ^[10]연장됨에 따라 시뮬레이션된 애니링 알고리즘이 글로벌 최적 해법으로 종료할 확률은 1에 가까워진다.그러나 이 이론적인 결과는 그다지 도움이 되지 않습니다.이는 상당한 성공 가능성을 보증하는 데 필요한 시간이 솔루션 ^{[citation needed]}공간을 완전히 탐색하는 데 필요한 시간을 초과하기 때문입니다.

유사 코드

다음 의사 코드는 위에서 설명한 것과 같은 시뮬레이트된 어닐링 휴리스틱을 나타냅니다.상태부터₀ 시작하여 최대 k개의_max 스텝이 실행될 때까지 계속됩니다.이 프로세스에서 콜 네이버는 임의의 상태로 무작위로 선택된 네이버를 생성해야 합니다.콜 랜덤(0, 1)은 랜덤으로 균일하게 [0, 1] 범위의 값을 선택하여 반환해야 합니다.어닐링 스케줄은 콜온도(r)에 의해 정의됩니다.콜온도(r)는 지금까지 소비된 시간 버젯의 비율r을 고려하여 사용할 온도를 산출합니다.

파라미터 선택

시뮬레이션된 어닐링 방법을 특정 문제에 적용하려면 상태 공간, 에너지(골) 기능을 지정해야 합니다.E(), 후보 제너레이터 절차neighbour(), 합격 확률 함수P(), 및 어닐링 스케줄temperature()그리고 초기 온도 <init temp>.이러한 선택은 방법의 효율성에 큰 영향을 미칠 수 있습니다.유감스럽게도 모든 문제에 적합한 이들 파라미터의 선택지가 없습니다.또한 특정 문제에 대해 최적의 선택지를 찾을 수 있는 일반적인 방법도 없습니다.여기에서는 일반적인 가이드라인을 몇 가지 설명하겠습니다.

충분히 가까운 이웃

시뮬레이션 어닐링은 검색 그래프에서 랜덤 워크로 모델링할 수 있으며, 그 정점은 모두 가능한 상태이며, 가장자리는 후보 이동이다.의 필수 요건neighbour()함수는 초기 상태에서 전역 최적 상태까지 이 그래프에 충분히 짧은 경로를 제공해야 한다는 것입니다. 검색 그래프의 직경은 작아야 합니다.예를 들어, 위의 순회 세일즈맨 예에서 n = 20개 도시의 검색 공간은 n! = 2,432,902,008,190,000(2.4조) 상태를 가지지만, 각 정점의 이웃 수는${\displaystyle \underset{of}{\overset{}{}}}$ k ${\displaystyle \underset{}{\overset{}{=}}}$ ${\displaystyle \underset{}{\overset{}{1}}}$ ${\displaystyle \underset{}{\overset{}{}}}$- ${\displaystyle \underset{}{\overset{}{1}}}$ ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle =\frac{}{}n\frac{}{}}$ (${\displaystyle \frac{n}{}}$ -${\displaystyle \frac{1}{}}$) ${\displaystyle \frac{\mathrm{}}{}}$ ${\displaystyle =}$ ${\displaystyle 190}$ ${style \sum$ _${k = 1$ ~1-n$}^{$n}입니다.그래프의 직경은 n${\displaystyle }$-$$(\$style n-1$입니다.

이행 확률

특정 문제에 대한 시뮬레이트된 어닐링의 동작을 조사하려면 알고리즘 구현에서 이루어진 다양한 설계 선택에서 발생하는 전이 확률을 고려하는 것이 유용할 수 있습니다.검색 그래프의 각${\displaystyle \mathrm{엣지}(}$ ${\displaystyle {}^{}}$ , s${\displaystyle {}^{})}$ )$${ $displaystyle ($ s , s , s )$$} of$$$$、 이행확률은 현재 상태가$s{\displaystyle }$ { $displaystyle$ s$$}일$$ 때 시뮬레이트된 어닐링 알고리즘이 s${\displaystyle {}^{}}${ $displaystyle$ s$` 상태$로 이행할 확률로 정의됩니다.이 확률은 다음 조건에 따라 현재 온도에 따라 달라집니다.temperature()후보자가 이동하는 순서에 따라neighbour()함수 및 합격 확률 함수P()(후보자가 연속적으로 테스트되기 때문에 이행 확률은 $단순히{\displaystyle }$ P${\displaystyle (e,}$ ${\displaystyle {}^{}}$,, $)$가 아닙니다.{ $displaystyle$ P$(e, e', T)$} 。

합격 확률

의 사양neighbour(),P(),그리고.temperature()는 부분적으로 용장합니다.실제로 동일한 수용 함수를 사용하는 것이 일반적입니다.P()다른 두 가지 기능은 특정 문제에 따라 조정합니다.

Kirkpatrick 등에 의한 방법의 공식에서 $합격확률함수{\displaystyle }$P (${\displaystyle e}$ , ${\displaystyle {}^{},}$ ,${\displaystyle T}$) { $display P ( e$ , e , e ' , $T$${\displaystyle }$) }는$$ e < \ $display style$ e' <${\displaystyle e}$ ${\displaystyle 및}$ exp${\displaystyle ,}$ (${\displaystyle }$-${\displaystyle {}^{}}$( ${\displaystyle e,}$ - ${\displaystyle {}^{}}$ ) \$exp$- e ( ) （ e ）$$。이 공식은 물리적 시스템의 전이와 유추하여 표면적으로 정당화되었으며, T=1과 Metropolis-Hastings 제안 분포가 대칭인 경우 Metropolis-Hastings 알고리즘에 해당한다.그러나, 이 허용 확률은 종종 시뮬레이션 어닐링에 사용됩니다.neighbour()Metropolis-Hastings의 제안 분포와 유사한 함수는 대칭적이지 않거나 전혀 확률적이지 않다.그 결과, 시뮬레이션된 아닐링 알고리즘의 전이 확률은 유사한 물리적 시스템의 전환에 해당하지 않으며$,$ $일정$한 온도에서 상태의 장기 분포 T(\$displaystyle$ T$)$는 물리적 상태에 대한 열역학적 평형 분포와 유사할 필요가 없습니다.모든 온도에서 시스템을 사용할 수 있습니다.그럼에도 불구하고, 시뮬레이션 어닐링에 대한 대부분의 설명은 아마도 SA의 많은 구현에서 하드 코딩된 원래의 수용 함수를 가정합니다.

1990년에 Moscato와 Fontanari,^[11] 그리고 독립적으로 Dueck와 Scheuer는 ^[12]결정론적 업데이트(즉, 확률론적 수용 규칙에 기초하지 않은 업데이트)가 최종 품질에 영향을 미치지 않고 최적화 과정을 가속화할 수 있다고 제안했다.Moscato와 Fontanari는 연구에서 유래한 "임계값 업데이트" 아닐링의 "특정 열" 곡선의 유사성을 관찰한 결과, "시뮬레이션된 아닐링 알고리즘에서 메트로폴리스 업데이트의 확률성은 거의 최적 최소값을 찾는데 주요한 역할을 하지 않는다"고 결론지었다.대신, 그들은 "고온에서 비용 함수 경관을 부드럽게 하고 냉각 과정 동안 최소의 점진적인 정의가 시뮬레이션 어닐링의 성공을 위한 기본 요소"라고 제안했다.이 방법은 Dueck와 Scheuer의 교파 때문에 "임계 수용"이라는 명칭으로 대중화되었습니다.2001년에 Franz, Hoffmann 및 Salamon은 결정론적 업데이트 전략이 비용/에너지 ^[13]지형에서 무작위 보행을 시뮬레이션하는 알고리즘의 큰 클래스 내에서 실제로 최적의 것임을 보여주었다.

효율적인 후보 생성

후보 제너레이터 선택 시neighbour()시뮬레이션 어닐링 알고리즘을 몇 번 반복한 후 현재 상태는 랜덤 상태보다 훨씬 낮은 에너지를 가질 것으로 예상된다는 점을 고려해야 한다.$따라서$ 일반적으로 목적지 $상태$의${\displaystyle {}^{}}$에너지가$$ 현재 상태와 비슷할 가능성이 높은 후보 이동 방향으로 발전기를 기울여야 합니다$.$이 휴리스틱(Metropolis-Hastings 알고리즘의 주요 원리)은 "매우 좋은" 후보 이동과 "매우 나쁜" 후보 이동을 배제하는 경향이 있습니다. 그러나 전자는 보통 후자에 비해 훨씬 덜 일반적이므로 휴리스틱은 일반적으로 상당히 효과적입니다.

예를 들어, 위의 여행 세일즈맨 문제에서 저에너지 투어의 연속된 두 도시를 교환하는 것은 에너지(길이)에 약간의 영향을 미칠 것으로 예상되지만, 반면 두 개의 임의의 도시를 교환하는 것은 길이를 줄이는 것보다 길이를 늘리는 것이 훨씬 더 쉽다.따라서 (n (n${\displaystyle }$-${\displaystyle 1}$)${\displaystyle }$/ ${\displaystyle 2\mathrm{}}$($n$ $display$ $style$n ($n-1$)/$2)$가 아닌${\displaystyle }$n -$$ (display $style$ n-1$)$스왑을$$ $사용$하여) 최적화에 대한 경로가 다소 짧은 경우에도 연속 스왑 인접 라우터 제너레이터는 임의 스왑보다 성능이 향상될 것으로 예상됩니다.

휴리스틱의 보다 정확한 설명은 $P{\displaystyle }$(${\displaystyle s}$) ,${\displaystyle \mathrm{E<img\; alt="s\text{'}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/5136680c63706cfd17ceddb4acddbfdd0ba5ef2d"\; style="vertical-align:\; -0.338ex;\; width:1.775ex;\; height:2.509ex;">}}$ ( ${\displaystyle {}^{})}$) ,${\displaystyle T}$) ( \ $displaystyle$P$$ ($E$( s ) , E ( s ) , E ( s ) , T ) ( \ $displaystyle{\displaystyle {}^{}}$P ( s ) , E ( s ) , E ( s ) , $T$) $。$위의 "표준" 수용 $함수{\displaystyle }$P {\$displaystyle$ P$}$의 경우${\displaystyle ,}$ ${\displaystyle {}^{}}$ (${\displaystyle }$s )${\displaystyle }$-$E$ ( ${\displaystyle s}$) {$displaystyle$E ($s )-E$( s )}가 T $(\displaystyle$ T$)$ $이하임$을 의미합니다.따라서, 위의 순회 세일즈맨 예에서, 사람은 다음을 사용할 수 있습니다.neighbour()function that swaps two random cities, where the probability of choosing a city-pair vanishes as their distance increases beyond ${\displaystyle T}$.

장벽 회피

후보 제너레이터 선택 시neighbour()또한 모든 인접 상태보다 훨씬 낮은 에너지를 가진 "깊은" 국소 최소 상태(또는 일련의 연결 상태)의 수를 줄이기 위해 노력해야 한다.에너지 함수의 이러한 "폐쇄 유역"은 높은 확률(분지의 상태 수에 거의 비례함)과 매우 오랜 시간(주변 상태와 분지의 바닥 사이의 에너지 차이에 대해 거의 지수함수)로 시뮬레이션 어닐링 알고리즘을 트랩할 수 있다.

원칙적으로 이 목표를 충족시킬 수 있는 발전기 후보 설계는 불가능하며, 이와 유사한 에너지를 가진 발전기 후보를 우선시하는 것도 불가능하다.한편, 발전기에 대한 비교적 간단한 변경으로 시뮬레이션 어닐링의 효율을 크게 향상시킬 수 있습니다.예를 들어, 출장 세일즈맨 문제에서는 길이가 거의 같은 A($디스플레이 스타일)$와 B$(디스플레이 스타일$ B$)$의 두 개의 $투어$를 전시하는 것이 어렵지 않습니다. (1) $(디스플레이$ 스타일 A$)$가 최적이고 (2) A$(디스플레이 스타일$ A$)$를 B$(디스플레이 스타일$ B$)$로 $변환$하는 모든 일련의 시티-페어 스왑이 t를 거칩니다.$두$ 도시보다 훨씬 긴 길이와 (3) $연속$된 도시를 반전시켜 A를$B$로 $변환$할 수 있습니다.이 예에서는 제너레이터가 랜덤페어 스왑만 실행하는 경우 A$(\displaystyle$ A$)$와 B$(\displaystyle$ B$)$는 $서로{\displaystyle }$ 다른 "딥 분지"에 존재하지만 제너레이터가 랜덤세그먼트 플립을 실행하는 경우에는 같은 분지에 있습니다.

냉각 스케줄

시뮬레이션 어닐링을 정당화하기 위해 사용되는 물리적 유추는 냉각 속도가 현재 상태의 확률 분포가 항상 열역학적 평형에 근접할 정도로 충분히 낮다고 가정한다.불행히도 완화 시간(온도 변화 후 평형이 회복되기를 기다려야 하는 시간)은 에너지 함수의 "지형"과 현재 온도에 크게 좌우된다.시뮬레이션 어닐링 알고리즘에서는 완화 시간도 후보 발전기에 따라 매우 복잡한 방식으로 달라집니다.이러한 모든 파라미터는 보통 시뮬레이트된 어닐링 알고리즘에 블랙박스 함수로 제공됩니다.따라서 이상적인 냉각 속도는 사전에 결정할 수 없으며 각 문제에 대해 경험적으로 조정해야 한다.적응형 어닐링 알고리즘은 냉각 일정을 검색 진행률에 연결하여 이 문제를 해결합니다.열역학적 시뮬레이션 어닐링(^[14]Thermodynamic Simulated Annealing)이라는 다른 적응적 접근법은 열역학의 법칙에 따라 두 상태 간의 에너지 차이를 기반으로 각 단계의 온도를 자동으로 조정합니다.

재기동

항상 현재 상태에서 이동하는 것보다 훨씬 더 나은 솔루션으로 다시 전환하는 것이 더 나을 수 있습니다.이 프로세스를 시뮬레이트된 어닐링 재시작이라고 합니다.이를 위해 우리는s그리고.e로.sbest그리고.ebest아닐 일정을 다시 시작할 수도 있습니다.재기동 여부는 몇 가지 기준에 따라 결정할 수 있습니다.그 중에서도 주목되는 것은, 지금까지 얻은 베스트 에너지에 비해 현재의 에너지가 너무 높은지 아닌지에 근거해, 일정수의 스텝에 근거해 재기동하는 것, 랜덤으로 재기동하는 것 등이다.

관련 방법

• 인터랙티브 메트로폴리스-헤이스팅 알고리즘(일명^[15] 순차 몬테카를로)은 시뮬레이션된 아닐링 움직임과 인터랙티브 재활용 메커니즘을 갖춘 최적의 개인에 대한 수용-거부를 결합한다.
• 양자 어닐링은 열변동 대신 양자변동(quantum follations)을 이용해 목표 함수의 높고 얇은 장벽을 뚫는다.
• 확률적 터널링은 시뮬레이션된 아닐링 실행의 난이도를 극복하기 위한 시도이며, 온도가 낮아짐에 따라 장벽을 통해 '터널링'함으로써 국소 최소값에서 탈출합니다.
• Tabu 검색은 일반적으로 에너지가 낮은 인근 상태로 이동하지만 로컬 최소값에 갇힌 경우 오르막으로 이동하며 이미 표시된 솔루션의 "taboo 목록"을 유지함으로써 사이클을 회피합니다.
• 이중 위상 진화는 검색 공간의 위상 변화를 이용하여 로컬 검색과 글로벌 검색을 중재하는 알고리즘 및 프로세스(시뮬레이션 해제) 패밀리입니다.
• 사후적 검색 최적화는 알고리즘의 자유 매개변수를 문제, 인스턴스 및 현재 솔루션 주변의 로컬 상황에 자가 조정하기 위한 내부 피드백 루프를 추가하여 기계 학습과 최적화를 결합하는 데 초점을 맞춥니다.
• 유전 알고리즘은 하나의 해결책이 아니라 하나의 해결책의 풀을 유지합니다.새로운 후보 솔루션은 (SA와 마찬가지로) "변환"뿐만 아니라 풀에서 두 솔루션을 "재결합"함으로써 생성됩니다.SA에 사용된 것과 유사한 확률론적 기준은 돌연변이 또는 결합의 후보 선택 및 풀에서 초과 용액의 폐기에 사용된다.
• 메메틱 알고리즘은 프로세스에서 협력하고 경쟁하는 에이전트 세트를 사용하여 솔루션을 찾습니다.때로는 에이전트의 전략이 ^[16]재결합하기 전에 고품질 솔루션을 얻기 위한 시뮬레이션된 어닐링 절차를 수반합니다.어닐링은 ^[17]검색의 다양성을 높이기 위한 메커니즘으로도 제안되고 있습니다.
• 단계별 최적화는 최적화하는 동안 대상 함수를 "평활하게" 전환합니다.
• 개미 군집 최적화(ACO)는 많은 개미(또는 에이전트)를 사용하여 솔루션 공간을 이동하고 국소적으로 생산성이 높은 영역을 찾습니다.
• 교차 엔트로피 방법(CE)은 모수화된 확률 분포를 통해 후보 솔루션을 생성합니다.매개 변수는 다음 반복에서 더 나은 샘플을 생성하기 위해 교차 엔트로피 최소화를 통해 업데이트됩니다.
• 하모니 검색은 즉흥연주 과정에서 각 뮤지션들이 함께 최고의 하모니를 찾기 위해 음을 내는 것을 모방한다.
• 확률적 최적화는 시뮬레이션 어닐링 및 기타 수많은 접근방식을 포함하는 포괄적인 방법 세트이다.
• 파티클 군집 최적화는 탐색 공간에서 최적화 문제에 대한 해결책을 찾거나 목표가 존재하는 상황에서 사회적 행동을 모델링하고 예측하는 군집 지능을 모델로 한 알고리즘입니다.
• Runner-root algorithm(RRA; 러너 루트 알고리즘)은 자연에 있는 식물의 러너와 뿌리에서 영감을 받은 단일모달 및 다중모달 문제를 해결하기 위한 메타 휴리스틱 최적화 알고리즘입니다.
• 자연 물방울 동작을 모방하여 최적화 문제를 해결하는 인텔리전트 물방울 알고리즘(IWD)
• 병렬 감쇠는 잠재적인 장벽을 극복하기 위해 다양한 온도(또는 해밀턴식)에서 모델을 복사하는 시뮬레이션입니다.
• 다목적 최적화에 ^[18]다목적 시뮬레이션 어닐링 알고리즘이 사용되었습니다.

「 」를 참조해 주세요.

레퍼런스

추가 정보

• A. Das and B. K. Chakrabarti (Eds), 양자 아닐링 및 관련 최적화 방법, 물리학 강의 노트, 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. S2CID 851736.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 10.12. Simulated Annealing Methods". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
• Strobl, M.A.R.; Barker, D. (2016). "On simulated annealing phase transitions in phylogeny reconstruction". Molecular Phylogenetics and Evolution. 101: 46–55. doi:10.1016/j.ympev.2016.05.001. PMC 4912009. PMID 27150349.
• V.Vassilev, A.Prahova: "유연한 제조 시스템의 제어에 대한 모의 풀림 사용", 국제 저널 정보 이론 및 응용 프로그램, 제6권/1999년

외부 링크

• 모의 아닐링 모의 아닐링을 실험할 수 있는 Javascript 앱입니다.소스 코드 포함.
• "일반 어닐링 알고리즘" 일반 어닐링 연습을 위한 오픈 소스 MATLAB 프로그램.
• 위키 다양성 프로젝트 시뮬레이트 해제에 대한 셀프 가이드 수업.
• 구글은 양자 컴퓨터 Ars Technica가 아닌 사용의 중첩에 있는 D-Wave 컴퓨터가 실제로 효율적인 모의 해제 공동 프로세서일 가능성에 대해 논의한다.
• [1] 어닐링 기반의 다목적 최적화 알고리즘: AMOSA.