담금질 기법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사
3. 원리
- 3.1. 상태 전이
- 3.2. 냉각 스케줄
4. 알고리즘
- 4.1. 의사 코드
- 4.2. 매개변수 선택
5. 응용 분야
6. 변형 및 관련 기법
7. 한계
참조

1. 개요

담금질 기법은 주어진 문제의 최적해를 찾기 위한 확률적 탐색 기법이다. 이 방법은 고체의 냉각 과정, 즉 온도를 점차 낮추면서 에너지가 낮은 상태로 수렴하는 현상에서 영감을 얻었다.

담금질 기법은 현재 상태의 에너지와 새로운 상태 후보의 에너지, 그리고 '온도' 매개변수에 의해 결정되는 수용 확률 함수를 사용하여 해를 탐색한다. 온도가 높을 때는 넓은 영역을 탐색하며, 점차 낮아지면서 최적해에 가까워진다. 알고리즘은 초기 온도 설정, 냉각 스케줄, 상태 전이, 그리고 매개변수 선택에 따라 성능이 달라지며, 다양한 변형 기법과 관련 알고리즘이 존재한다.

더 읽어볼만한 페이지

몬테카를로 방법 - 메트로폴리스-헤이스팅스 알고리즘
메트로폴리스-헤이스팅스 알고리즘은 마르코프 연쇄 몬테카를로 방법으로, 확률 밀도 함수에 비례하는 함수를 알 때 원하는 확률 분포에서 난수열을 생성하며 통계 모델링, 데이터 분석 등에 응용된다.
몬테카를로 방법 - 피셔-예이츠 셔플
피셔-예이츠 셔플은 유한 집합에서 임의의 순열을 생성하는 알고리즘으로, 피셔와 예이츠가 처음 소개한 후 더스텐펠트에 의해 컴퓨터에 최적화되었으며, 구현 시 편향 요인을 주의해야 한다.
최적화 알고리즘 - 기댓값 최대화 알고리즘
최적화 알고리즘 - 유전 알고리즘
유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다.

담금질 기법
개요
열처리 과정 모식도.
정의	금속 공학에서, 재료의 물리적, 때로는 화학적 특성을 변화시키기 위해 제어된 가열 및 냉각 과정을 포함하는 열처리 기술
상세 정보
목적	경도를 증가시키고, 연성을 증가시키고, 취성을 감소시키고, 잔류 응력을 제거하고, 투자율을 향상시키는 것
적용 재료	강철 기타 금속 유리
공정
가열	재료를 특정 온도까지 가열
유지	해당 온도에서 일정 시간 유지
냉각	제어된 속도로 냉각
온도 및 시간	재료의 종류와 원하는 특성에 따라 조절
기술적 측면
야금학적 원리	원자들의 열적 운동을 이용하여 에너지적으로 더 안정된 상태로 만드는 과정
결정 구조 변화	담금질을 통해 준안정 상태가 된 금속의 결정 구조를 안정화
응용 분야
금속 가공	강철의 강도와 연성 향상
유리 제조	유리의 내구성 강화
반도체 제조	반도체 웨이퍼의 결함 감소
관련 기술
담금질 (Quenching)	급랭을 통해 재료를 경화시키는 기술
풀림 (Annealing)	서냉을 통해 재료의 연성을 높이는 기술
노멀라이징 (Normalizing)	공랭을 통해 재료의 결정립을 미세화하는 기술
알고리즘 (컴퓨터 과학)
특징	전역 최적해 탐색: 넓은 탐색 공간에서 최적의 해를 찾음 지역 최적해 탈출: 확률적인 탐색으로 지역 최적해에 갇히지 않음 파라미터 조정: 온도 스케줄링, 이웃 해 생성 방식 등
활용	조합 최적화 문제: 외판원 문제, 그래프 색칠 문제 함수 최적화 문제: 복잡한 함수의 최적값 탐색 머신러닝: 신경망 학습, 특징 선택
역사
기원	금속의 열처리에서 유래
알고리즘 개발	1983년 Kirkpatrick 등이 제안
장점 및 단점
장점	구현 용이성: 비교적 간단한 알고리즘 구조 전역 최적해 보장: 충분한 시간과 적절한 파라미터 설정 시 다양한 문제 적용: 조합 최적화, 함수 최적화 등
단점	파라미터 의존성: 성능이 파라미터 설정에 민감 계산 비용: 탐색 공간이 넓을 경우 많은 계산 시간 소요
구현 예시
의사 코드	알고리즘의 핵심 단계를 간략하게 표현
프로그래밍 언어	다양한 언어로 구현 가능 (Python, C++, Java 등)

2. 역사

담금질 기법이라는 이름은 금속 공학의 담금질(annealing) 과정에서 유래했다. 실제 금속을 높은 온도로 가열했다가 서서히 식히면서 내부 결정 구조를 안정화하고 에너지 상태를 낮추는 과정과 유사하게, 이 알고리즘은 최적화 문제에서 점진적으로 더 나은 해를 찾아가는 방식을 모방한다.

알고리즘 설명에서 자주 등장하는 '온도(Temperature)'나 '냉각(Frozen)'과 같은 용어는 실제 물리적인 온도를 의미하는 것이 아니라, 알고리즘의 상태를 설명하기 위한 비유적 표현이다. 탐색 과정에서 현재 해보다 좋지 않은 해(더 높은 비용 또는 비효율적인 상태)를 받아들일 가능성을 '온도'로 표현하며, 온도가 높을수록 더 좋지 않은 해를 수용할 확률이 커진다. 반대로, 더 좋은 해(더 낮은 비용 또는 효율적인 상태)를 찾으면 '온도가 내려간다(Downhill)'고 표현한다. 알고리즘이 진행됨에 따라 이 가상의 '온도'는 점차 낮아지고, '냉각' 상태, 즉 온도가 완전히 떨어진 상태에 도달하면 알고리즘은 최적의 해 또는 그에 매우 가까운 해(전역 최적해)를 찾은 것으로 간주하고 종료된다. 이는 금속이 서서히 식으면서 안정적인 에너지 최저 상태에 도달하는 과정과 유사하며, 수많은 가능한 해의 조합 중에서 가장 최적화된 해(예: 주어진 공간에 여러 물체를 가장 효율적으로 배치하는 방법)를 찾는 것이 이 기법의 목표이다.

3. 원리

담금질 기법은 최적화 문제를 해결하기 위한 확률적 휴리스틱 알고리즘 중 하나로, 물리 시스템의 담금질(annealing) 과정에서 영감을 얻었다. 금속공학에서 담금질은 금속을 높은 온도로 가열했다가 서서히 냉각시켜 결함을 줄이고 안정적인 결정 구조를 만드는 공정이다. 이와 유사하게, 담금질 기법은 어떤 문제의 해결책(해)을 물리 시스템의 열역학적 상태 ''s''로 간주하고, 최소화하려는 목적 함수 ''E''(''s'')를 해당 상태의 내부 에너지로 본다. 알고리즘의 목표는 임의의 초기 상태에서 시작하여 시스템 에너지가 가능한 가장 낮은 상태, 즉 전역 최적해를 찾는 것이다.^[11]

알고리즘은 현재 상태 ''s''에서 시작하여, 이웃한 상태 ''s' ''를 탐색한다. 이웃 상태는 현재 상태를 약간 변경하여 생성된다. 예를 들어, 외판원 문제에서는 현재 경로에서 두 도시의 방문 순서를 바꾸는 방식으로 이웃 상태를 만들 수 있다.

탐색 과정에서 새로운 이웃 상태 ''s' ''가 현재 상태 ''s''보다 더 좋으면(즉, 에너지 ''E''(''s' '')가 ''E''(''s'')보다 낮으면) 항상 그 상태로 이동한다. 이는 마치 언덕을 내려가는 것과 같아서, 더 나은 해를 향해 직접 나아가는 방식이다.

하지만 담금질 기법의 핵심적인 특징은, 새로운 이웃 상태 ''s' ''가 현재 상태 ''s''보다 더 나쁘더라도(즉, 에너지 ''E''(''s' '')가 ''E''(''s'')보다 높더라도) 무조건 거부하지 않고 특정 확률에 따라 이동을 허용한다는 점이다. 이 확률은 온도(Temperature)라고 불리는 매개변수 ''T''와 두 상태의 에너지 차이(''E''(''s' '') - ''E''(''s''))에 따라 결정된다. 온도가 높을 때는 에너지 차이가 크더라도 나쁜 상태로 이동할 확률이 비교적 높지만, 온도가 낮아질수록 이 확률은 급격히 감소한다.

이러한 확률적 이동은 알고리즘이 지역 최적해에 갇히는 것을 방지하는 중요한 역할을 한다. 단순한 언덕 오르기 알고리즘은 더 좋은 이웃 상태가 없을 때 탐색을 멈추기 때문에, 실제 최적해보다 못한 지역 최적해에 머무를 수 있다. 반면 담금질 기법은 때로는 나쁜 상태로 이동함으로써 현재의 지역 최적 상태를 벗어나 더 넓은 탐색 공간을 탐험하고 전역 최적해를 찾을 가능성을 높인다.

'온도' ''T''는 알고리즘이 진행됨에 따라 점차 낮아진다. 이를 냉각(cooling)이라고 하며, 이 과정을 조절하는 계획을 냉각 스케줄이라고 부른다. 초기에는 높은 온도로 설정하여 나쁜 상태로의 이동을 비교적 자유롭게 허용하며 탐색 공간의 넓은 영역을 탐험한다. 시간이 지나면서 온도를 점차 낮추면, 알고리즘은 점차 에너지(목적 함수 값)가 낮은 방향으로 이동하는 것을 선호하게 되고, 나쁜 상태로 이동할 확률은 줄어든다. 온도가 0에 가까워지면 알고리즘은 거의 탐욕 알고리즘처럼 작동하여 가장 좋은 이웃 상태만을 선택하게 된다. 이 과정을 통해 알고리즘은 점진적으로 최적해에 수렴하게 된다.

여기서 '온도'와 '냉각'은 실제 물리적 현상을 의미하는 것이 아니라, 알고리즘이 얼마나 자유롭게 나쁜 상태를 받아들일지를 조절하는 매개변수를 설명하기 위한 비유이다. 온도가 높다는 것은 더 다양한 가능성을 탐색하며 때로는 더 안 좋은 결과를 받아들이는 유연한 상태를 의미하고, 온도가 낮아진다는 것은 점차 좋은 결과를 향해 안정화되는 과정을 의미한다. 온도가 완전히 떨어져 더 이상 상태 변화가 없는 지점이 우리가 찾는 최적의 조합이 될 수 있다.

담금질 기법의 성능은 이웃 상태를 어떻게 정의하고 탐색하는지(예: Step 사이즈), 초기 온도를 얼마로 설정하는지, 그리고 온도를 어떤 속도와 방식으로 낮추는지(냉각 스케줄)에 크게 의존한다. 예를 들어, 이웃 상태를 탐색하는 단계(Step)의 크기가 너무 크면 최적해를 지나칠 수 있고, 너무 작으면 모든 경우의 수를 탐색하는 것과 비슷해져 비효율적일 수 있다. 이러한 매개변수를 문제의 특성에 맞게 적절히 설정하는 것이 중요하며, 하위 섹션에서는 상태 전이 확률과 냉각 스케줄에 대해 더 자세히 다룬다.

3. 1. 상태 전이

현재 상태

s

에서 새로운 후보 상태

s_\mathrm{new}

로의 상태 전이 확률은 두 상태의 에너지

e = E(s)

와

e_\mathrm{new}= E(s_\mathrm{new})

, 그리고 '온도'라고 불리는 전역 매개변수

T

에 의존하는 수용 확률 함수

P(e, e_\mathrm{new}, T)

에 의해 결정된다. 여기서 에너지는 문제에 따라 최소화하려는 값(예: 비용, 거리, 오류 등)을 나타내며, 에너지가 낮은 상태가 더 좋은(바람직한) 상태로 간주된다.

핵심은 확률 함수

P

가

e_\mathrm{new} > e

인 경우, 즉 새로운 상태의 에너지가 현재 상태보다 높더라도 0이 아닌 양수 값을 가져야 한다는 점이다. 이는 알고리즘이 지역 최적해(local minimum)에 빠지지 않고 더 좋은 전역 최적해(global minimum)를 찾기 위해 때로는 더 나쁜 상태로 이동하는 것을 허용하기 위함이다. 마치 언덕을 내려가다가 더 높은 봉우리를 발견하기 위해 잠시 다른 언덕을 오르는 것과 같다.

온도

T

는 상태 전이를 제어하는 중요한 역할을 한다.

T

가 높을 때는 에너지 차이(

e_\mathrm{new} - e

)가 큰 상태 변화도 비교적 높은 확률로 받아들여져 탐색 공간을 넓게 탐험한다. 반면,

T

가 0에 가까워질수록

e_\mathrm{new} > e

일 때의 확률

P(e, e_\mathrm{new}, T)

는 0에 가까워지고,

e_\mathrm{new} < e

(에너지가 낮아지는 이동)일 때는 확률이 1에 가까워지거나 1이 된다. 즉, 점차 에너지 최소점을 향해 안정화되며 나쁜 상태로의 이동은 거의 일어나지 않는다.

T=0

이 되면, 에너지를 낮추는 방향으로만 이동하는 탐욕 알고리즘(Greedy algorithm)과 유사해진다.

일반적으로 수용 확률 함수

P

는 에너지 차이

e_\mathrm{new}-e

가 클수록 이동을 수용할 확률이 감소하도록 설계된다. 즉, 작은 폭의 에너지 증가는 허용될 가능성이 높지만, 큰 폭의 에너지 증가는 허용될 가능성이 낮다.

Kirkpatrick 등이 제안한 초기 담금질 기법에서는 수용 확률 함수를 다음과 같이 정의했다.^[13]^[14]

$e_\mathrm{new} < e$ (에너지가 감소하는 경우): $P(e, e_\mathrm{new}, T) = 1$ (항상 이동)
$e_\mathrm{new} \ge e$ (에너지가 증가하거나 같은 경우): $P(e, e_\mathrm{new}, T) = \exp(-(e_\mathrm{new}-e)/T)$

이 형태는 물리 시스템에서 입자들이 특정 에너지 상태를 가질 확률 분포(맥스웰-볼츠만 분포)를 따르도록 상태를 전이시키는 메트로폴리스-헤이스팅스 알고리즘에서 영감을 얻었다. 그러나 담금질 기법은 실제 물리적 담금질 과정이나 메트로폴리스 알고리즘과 완전히 동일하지는 않다. 예를 들어, 담금질 기법에서 다음 상태 후보를 어떻게 생성하는지(알고리즘의 ''neighbour()'' 함수)에 따라 실제 전이 확률은 위 수식과 달라질 수 있다. 따라서 물리적 유추는 알고리즘의 작동 방식을 이해하는 데 도움을 주는 개념적인 설명으로 받아들이는 것이 좋다.^[15] 특정 문제에 대한 담금질 기법의 동작을 이해하기 위해서는 현재 온도(''temperature()''), 후보 이동 생성 방식(''neighbour()'') 및 수용 확률 함수(''P()'')를 포함한 전이 확률을 고려하는 것이 유용하다.

1990년대에는 메트로폴리스 업데이트의 확률적 요소 대신 결정론적 규칙(예: 특정 임계값 이하의 에너지 증가는 항상 허용)을 사용하는 "Threshold Accepting"과 같은 변형 기법도 제안되었다.^[13]^[14] 이는 확률적 요소 없이도 담금질 기법의 핵심 아이디어인 '온도 조절을 통한 탐색 범위 조절'이 효과적일 수 있음을 보여준다.^[15]

3. 2. 냉각 스케줄

담금질 기법의 이름과 작동 원리는 알고리즘의 핵심 특징인 온도 변화와 관련이 깊다. 이는 시뮬레이션이 진행됨에 따라 온도를 점진적으로 감소시켜야 함을 의미한다. 알고리즘은 처음에 온도 ''T''를 높은 값(또는 무한대)으로 설정하고, 사용자가 지정할 수 있는 냉각 스케줄(annealing schedule)에 따라 각 단계에서 온도를 낮춘다. 이 스케줄은 정해진 시간이 끝나면 ''T'' = 0에 도달하도록 설계된다. 이러한 온도 조절을 통해, 시스템은 초기에는 에너지 함수의 미세한 변화를 무시하고 좋은 해가 있을 가능성이 높은 탐색 공간의 넓은 영역을 탐색하게 된다. 이후 온도가 낮아짐에 따라 점차 에너지가 낮은 영역으로 탐색 범위를 좁혀가며, 최종적으로는 최급강하법 휴리스틱과 유사하게 가장 낮은 에너지 상태를 찾아 내려간다.

냉각 스케줄은 신중하게 선택해야 한다. 초기 온도는 오르막 이동(uphill move, 더 나쁜 해를 선택할 확률)과 내리막 이동(downhill move, 더 좋은 해를 선택할 확률)의 전이 확률이 거의 같아질 정도로 충분히 높게 설정해야 한다. 이를 위해서는 탐색 과정에서 나타날 수 있는 상태 간의 에너지 차이(''e' ''−''e'')를 미리 예측해볼 필요가 있다. 온도는 이후 최종적으로 0이 될 때까지 점진적으로 감소시키는데, 일반적으로 온도를 지수 함수적으로 감소시키는 스케줄을 사용한다. 이는 각 단계마다 온도를 1보다 작은 고정된 상수 α를 곱하여 낮추는 방식이다.

빠른 냉각 스케줄 결과. 이미지의 픽셀을 재배열하여 특정 포텐셜 에너지 함수를 최소화하는 문제에서, 빠른 냉각은 비정질 고체와 유사한 결과를 생성한다.

느린 냉각 스케줄 결과. 동일한 문제에서 느린 냉각은 결정질 고체와 유사한, 더 정돈된 결과를 생성한다. 느린 냉각이 더 좋은 최적해를 찾을 가능성이 높음을 보여준다.

어떤 유한한 문제에 대해, 담금질 기법 알고리즘이 전역 최적해를 찾을 확률은 냉각 스케줄을 충분히 길게(느리게) 하면 1에 가까워진다.^[11] 그러나 이 이론적인 결과는 실제 적용에 있어 한계가 있다. 상당한 성공 확률을 보장하기 위해 필요한 시간(매우 느린 냉각)이 해 공간 전체를 전수 조사하는 데 필요한 시간보다 길어질 수 있기 때문이다.^[12]

담금질 기법의 물리적 비유는 냉각 속도가 충분히 느려서 시스템의 확률 분포가 항상 열역학적 평형 상태에 가깝다고 가정한다. 하지만 실제로는 온도가 변한 후 시스템이 다시 평형 상태를 회복하는 데 걸리는 시간, 즉 '완화 시간'(relaxation time)이 에너지 함수의 형태와 현재 온도에 따라 크게 달라진다. 시뮬레이티드 어닐링 알고리즘에서는 이 완화 시간이 후보 해를 생성하는 방식에도 복잡하게 영향을 받는다. 이러한 요소들은 보통 알고리즘 사용자에게는 내부적으로 처리되는 블랙 박스와 같아서, 이상적인 냉각 속도를 미리 결정하기는 어렵다. 따라서 각 문제에 맞게 경험적으로 냉각 스케줄을 조정해야 하는 경우가 많다. 적응형 시뮬레이티드 어닐링과 같은 기법들은 탐색 진행 상황에 따라 냉각 스케줄을 자동으로 조절하여 이러한 문제를 해결하려고 시도한다. 예를 들어, 열역학적 시뮬레이티드 어닐링은^[16] 열역학 법칙에 따라 두 상태 간의 에너지 차이를 기반으로 각 단계에서 온도를 자동으로 조정한다.

4. 알고리즘

담금질 기법은 초기 해(상태 `s`)에서 시작하여 이웃한 해(`s'`)를 탐색하며 최적해를 찾아가는 최적화 알고리즘이다. 이 과정은 금속을 뜨겁게 달궜다가 서서히 식히는 '담금질' 과정에 비유된다.

알고리즘의 핵심은 현재 해보다 더 좋은 해(비용 또는 에너지가 낮은 해)는 항상 받아들이지만, 더 나쁜 해(비용 또는 에너지가 높은 해)라도 특정 확률에 따라 받아들일 수 있다는 점이다. 이 확률은 '온도(`T`)'라는 매개변수에 의해 조절된다. 초기에는 높은 온도로 설정하여 나쁜 해를 받아들일 확률을 높여 탐색 공간을 넓게 탐색하고 지역 최적해에 빠지는 것을 방지한다. 이후 온도를 점진적으로 낮추는 '냉각' 과정을 통해 나쁜 해를 받아들일 확률을 줄여나가면서 점차 최적해로 수렴하도록 유도한다.

여기서 '온도'나 '냉각'은 실제 물리적인 온도가 아니라, 알고리즘이 더 나쁜 해를 수용할 가능성 및 그 가능성을 줄여나가는 과정을 설명하기 위한 비유적인 표현이다.^[1] 온도가 높다는 것은 더 안 좋은 결과(높은 비용)가 나올 수 있는 탐색을 허용하는 것을 의미하고, 온도가 낮아진다는 것은 점차 좋은 결과(낮은 비용)를 내는 방향으로 탐색을 집중하는 것을 의미한다. 온도가 충분히 낮아져 더 이상 상태 변화가 거의 없을 때(이를 'frozen' 상태라고도 한다) 알고리즘은 종료되고, 이때의 해가 최종적인 최적해 후보가 된다.^[1]

알고리즘의 성능은 여러 요소에 영향을 받는데, 특히 한 온도에서 얼마나 많은 이웃 해를 탐색할지 결정하는 '스텝(Step) 크기'(소스에서는 `P`로 표현됨) 설정이 중요하다.^[1] 스텝 크기가 너무 크면 최적해를 지나칠 수 있고, 너무 작으면 탐색 시간이 과도하게 길어져 모든 경우를 탐색하는 것과 비슷해질 수 있다. 적절한 스텝 크기를 결정하는 것은 담금질 기법 적용의 어려운 점 중 하나이다.^[1]

각 단계에서 알고리즘은 현재 상태 `s`의 이웃 상태 `s*`를 고려하고, 상태 `s*`로 이동할지 아니면 상태 `s`에 머무를지를 확률으로 결정한다.^[1] 이러한 확률적 결정 과정은 시스템이 점차 더 낮은 에너지(비용) 상태로 이동하도록 유도한다.^[1] 이 과정은 시스템이 충분히 좋은 상태에 도달하거나 주어진 계산 시간이 소진될 때까지 반복된다.^[1]

담금질 기법은 초기 해에서 시작하여 전역 최적해에 도달하는 것을 목표로 하지만, 항상 전역 최적해를 보장하지는 않는다. 그럼에도 불구하고, 복잡한 문제에서 모든 경우의 수를 탐색하지 않고 비교적 짧은 시간에 좋은 해를 찾는 데 유용하게 사용된다.^[1] 초기 알고리즘의 성능 문제를 개선하기 위한 다양한 변형 기법들도 연구되고 있다.^[1]

4. 1. 의사 코드

다음은 담금질 기법을 설명하는 여러 형태의 의사 코드이다.

=== 기본 의사 코드 ===

가장 기본적인 담금질 기법의 작동 방식을 나타내는 의사 코드 예시는 다음과 같다.^[1]

```text
begin // 초기 해와 에너지를 설정한다.

s ← s0;

e ← E(s);

// 초기 온도를 설정한다. (예: T = 1000)

초기 온도 T > 0 설정;

// 온도가 충분히 낮아질 때까지 반복한다 ("frozen" 상태가 될 때까지).

while (아직 "frozen" 상태가 아님) do // 정해진 횟수(P)만큼 반복하여 해 공간을 탐색한다. P는 문제의 크기(n)와 관련하여 결정된다 (예: P = nk).

for 1 부터 P 까지 do // 현재 해(s)의 이웃 해(s')를 임의로 선택한다.

s' ← s의 임의의 이웃 선택;

// 새로운 해와 현재 해의 비용(에너지) 차이를 계산한다.

∆ ← cost(s') - cost(s);

// 만약 새로운 해가 더 좋거나 같은 비용을 가지면 (∆ <= 0, "downhill move"),

// 새로운 해를 현재 해로 받아들인다.

if ∆ <= 0 then s ← s';

e ← E(s');

// 만약 새로운 해가 더 나쁜 비용을 가지면 (∆ > 0, "uphill move"),

// 특정 확률에 따라 새로운 해를 받아들일지 결정한다. (아래 의사 코드에서는 이 부분이 생략되었으나, 일반적인 담금질 기법에서는 확률적으로 받아들인다.)

// 원본 코드 예시에서는 ∆ > 0일 때도 s ← s' 로 되어 있으나, 이는 확률적 수용 과정을 단순화한 표현일 수 있다.

// 일반적으로는 exp(-∆/T)와 같은 확률로 수용한다.

if ∆ > 0 then // 확률적 수용 여부 결정 (예: if random(0,1) < exp(-∆/T) then s ← s')

// 아래는 원본 코드의 표현

s ← s'; // 원본 코드에서는 확률 없이 받아들이는 것으로 표현됨. 주석 참고.

e ← E(s');

// 온도를 점진적으로 낮춘다 (냉각 스케줄). r은 냉각 계수 (0 < r < 1).

T ← r * T;

// 최종적으로 찾은 해(s)를 반환한다.

return s;
end```

이 의사 코드에서 `P` 값(내부 반복 횟수) 설정이 중요하다. `P`가 너무 크면 계산 시간이 오래 걸리고, 너무 작으면 최적해를 찾기 전에 탐색이 끝날 수 있다. '온도'와 '냉각'이라는 용어는 실제 온도가 아니라, 더 나쁜 해를 받아들일 확률(온도가 높을수록 확률 증가)과 그 확률을 점차 줄여나가는 과정(냉각)을 비유적으로 나타낸다.^[1]

=== 확률적 수용을 포함한 의사 코드 ===

다음은 최대 반복 횟수(`k_max`)와 명시적인 전이 확률 함수 `P`를 사용하는 의사 코드이다.^[1]

`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)`: (전이 확률 `P`에 따라 수용 여부 결정)
** `s ← s_new` (새로운 상태로 업데이트)
출력: 최종 상태 `s`

여기서 전이 확률 `P`는 현재 상태의 에너지 `e` (즉, `E(s)`), 새로운 상태의 에너지 `e'` (즉, `E(s_new)`), 그리고 현재 온도 `T`에 따라 결정된다. 중요한 점은 `e' > e` (즉, 더 나쁜 상태)일 때도 `P`가 0이 아닌 값을 가질 수 있다는 것이다. 이는 알고리즘이 국소 최적해에 빠지지 않고 더 넓은 해 공간을 탐색하여 전역 최적해에 도달할 가능성을 높인다. 온도가 0에 가까워짐에 따라, 더 나쁜 상태로 이동할 확률(`e' > e`일 때의 `P`)은 0에 가까워지고, 더 좋은 상태로 이동할 확률(`e' < e`일 때의 `P`)은 커진다. 온도가 0이 되면, 이 알고리즘은 언덕 오르기 알고리즘처럼 가장 좋은 이웃으로만 이동하게 될 수 있다.^[1]

=== 함수 형태 의사 코드 ===

다음은 담금질 기법을 함수 형태로 구현한 의사 코드와 관련 함수의 정의이다.^[1]

주요 함수 정의
EVAL(state): 상태 `state`의 평가값(에너지)을 반환한다.
NEIGHBOUR(state): 상태 `state`의 주변 상태 중 하나를 무작위로 생성하여 반환한다.
TEMPERATURE(r): 냉각 스케줄 함수. 진행률 `r` (0에서 1 사이)에 따른 현재 온도를 반환한다. 예시에서는 α^r (단, 0 < α < 1) 형태를 사용한다.
PROBABILITY(e1, e2, t): 현재 에너지 `e1`, 새로운 에너지 `e2`, 온도 `t`가 주어졌을 때 `e1`에서 `e2`로 전이할 확률을 반환한다.
random(): 0 이상 1 이하의 균등 분포 난수를 반환한다.

담금질 기법 함수

```text
function 담금질 기법(startState, maxIter, goalE)

state = startState // 현재 상태 초기화

e = EVAL(state) // 현재 상태의 에너지 계산

bestState = state // 지금까지 찾은 최적 해 초기화

bestE = e // 지금까지 찾은 최적 에너지 초기화

for (iter = 0; iter < maxIter; iter++) // 최대 반복 횟수만큼 반복

nextState = NEIGHBOUR(state) // 이웃 상태 생성

nextE = EVAL(nextState) // 이웃 상태의 에너지 계산

// 만약 이웃 상태가 지금까지 찾은 최적 해보다 좋으면 업데이트

if nextE < bestE then bestState = nextState

bestE = nextE

// 만약 목표 에너지 이하의 해를 찾으면 즉시 종료

if bestE <= goalE then return bestState

// 확률적으로 이웃 상태를 다음 상태로 받아들일지 결정

if random() <= PROBABILITY(e, nextE, TEMPERATURE(iter / maxIter)) then state = nextState

e = nextE

// 반복이 끝나면 지금까지 찾은 최적 해를 반환

return bestState

```

전이 확률 함수 예시 (메트로폴리스 기준)

```text
function PROBABILITY(e1, e2, t)

if e1 >= e2 then // 새로운 상태가 더 좋거나 같으면

return 1 // 항상 전이 (확률 1)

else // 새로운 상태가 더 나쁘면

return e^{(e1 - e2)/t} // 온도(t)와 에너지 차이(e1-e2)에 따라 확률적으로 전이

```

온도 함수 예시 (지수적 냉각)

```text
function TEMPERATURE(r) // r은 진행률 (iter / maxIter)

return α^r // α는 0과 1 사이의 상수 (예: 0.99)

4. 2. 매개변수 선택

담금질 기법을 특정 문제에 적용하기 위해서는 상태 공간, 에너지(목표) 함수 `E()`, 후보 생성 절차 `neighbor()`, 수용 확률 함수 `P()`, 냉각 스케줄 `temperature()`, 그리고 초기 온도 `init_temp`와 같은 매개변수들을 지정해야 한다. 이러한 매개변수들의 선택은 알고리즘의 효과에 상당한 영향을 미치므로 신중하게 결정해야 한다.^[11] 하지만 모든 문제에 적용 가능한 최적의 매개변수 조합은 없으며, 특정 문제에 대한 최상의 선택을 찾는 일반적인 방법론 또한 존재하지 않는다. 이는 무료 점심 정리로도 알려져 있으며, 담금질 기법 적용이 과학이라기보다는 경험적 기술에 가깝다고 여겨지는 이유이다.

=== 상태 공간과 후보 생성 절차 (neighbor()) ===

담금질 기법은 상태 공간을 탐색하는 과정으로, 이를 탐색 그래프로 모델링할 수 있다. 이 그래프에서 각 정점은 가능한 상태를, 간선은 한 상태에서 다른 상태로 이동할 수 있는 후보 이동을 나타낸다. 후보 생성 절차 `neighbor()`는 현재 상태에서 다음 상태 후보들을 어떻게 열거할지를 정의한다. 이 절차는 초기 상태에서 시작하여 전역 최적 상태에 도달할 수 있는 충분히 짧은 경로를 그래프 상에 제공해야 한다. 즉, 탐색 그래프의 지름이 작아야 한다. 예를 들어, 외판원 문제에서 각 상태는 도시 방문 순열이며, 이웃 상태는 두 도시의 방문 순서를 바꾼 순열로 정의될 수 있다.

후보 생성기를 선택할 때는 알고리즘이 진행됨에 따라 현재 상태의 에너지가 임의의 상태보다 훨씬 낮아질 가능성이 높다는 점을 고려해야 한다. 따라서 일반적으로 에너지 변화가 크지 않은, 즉 현재 상태와 에너지가 유사한 후보 상태를 생성하도록 편향시키는 것이 효과적이다. 이는 메트로폴리스-헤이스팅스 알고리즘의 기본 원리와 유사하며, 에너지 변화가 매우 큰 이동(매우 좋은 이동과 매우 나쁜 이동 모두)을 배제하는 경향이 있다. 예를 들어 외판원 문제에서 인접한 두 도시를 교환하는 것은 임의의 두 도시를 교환하는 것보다 에너지(경로 길이) 변화가 작을 가능성이 높아 일반적으로 더 나은 성능을 보인다.

=== 에너지(목표) 함수 (E()) ===

최소화하려는 함수 `E(s)`는 특정 상태 ''s''에서의 시스템 내부 에너지와 유사하게 취급된다. 알고리즘의 목표는 임의의 초기 상태에서 시작하여 에너지가 가장 낮은 상태, 즉 전역 최적 상태를 찾는 것이다.

=== 수용 확률 함수 (P()) ===

수용 확률 함수 `P(e, e_new, T)`는 현재 상태 ''s''(에너지 ''e'')에서 후보 새 상태 ''s_new''(에너지 ''e_new'')로의 전이 확률을 결정한다. 이 확률은 두 상태의 에너지와 전역적인 시간 가변 매개변수인 온도 ''T''에 의존한다. 에너지가 낮은 상태(''e_new'' < ''e'')가 선호되지만, 지역 최적 상태에 갇히는 것을 방지하기 위해 에너지가 더 높은 상태(''e_new'' > ''e'')로 이동할 확률 ''P''도 양수여야 한다. 일반적으로 ''P'' 함수는 에너지 차이

e_\mathrm{new}-e

가 증가할수록 이동을 수용할 확률이 감소하도록, 즉 작은 에너지 증가(오르막 이동)가 큰 증가보다 더 가능성이 높도록 선택된다.

=== 냉각 스케줄 (temperature()) 및 초기 온도 (init_temp) ===

온도 ''T''는 시스템 진화에서 에너지 변화에 대한 민감도를 조절하는 핵심 요소이다. ''T''가 높으면 시스템은 큰 에너지 변화에도 민감하게 반응하며 탐색 공간의 넓은 영역을 탐색하고, ''T''가 낮아지면 작은 에너지 변화에 더 민감해져 점차 낮은 에너지 영역으로 수렴한다. ''T''가 0에 가까워지면, 에너지를 높이는 이동의 확률 ''P''는 0에 수렴해야 하며, 에너지를 낮추는 이동만 허용하는 탐욕 알고리즘처럼 작동하게 된다.

알고리즘의 핵심 특징은 시뮬레이션이 진행됨에 따라 온도를 점진적으로 감소시키는 '냉각 스케줄'이다. 초기 온도 `init_temp`는 오르막 이동과 내리막 이동의 확률이 거의 비슷하도록 충분히 높게 설정해야 한다. 이후 온도는 사용자가 지정한 냉각 스케줄에 따라 감소하여 결국 ''T''=0에 도달해야 한다. 일반적으로 온도는 각 단계마다 1보다 작은 고정된 값 α를 곱하여 지수 함수적으로 감소시킨다.

이상적인 냉각 속도는 에너지 함수의 "지형", 현재 온도, 후보 생성기 등 여러 요인에 복잡하게 의존하며, 평형 상태를 유지하기 위해 필요한 '완화 시간'도 고려해야 한다. 이러한 이유로 최적의 냉각 스케줄은 사전에 결정하기 어렵고 각 문제에 맞게 경험적으로 조정해야 한다.^[12] 적응형 시뮬레이티드 어닐링과 같은 기법들은 검색 진행 상황에 따라 냉각 일정을 조정하거나,^[16] 열역학 법칙에 따라 온도를 자동으로 조절하여 이 문제를 해결하려고 시도한다.

5. 응용 분야

담금질 기법의 기본 아이디어는 다양한 분야의 문제 해결에 적용될 수 있다. 특히, 고려해야 할 경우의 수가 매우 많고 정해진 조건 안에서 최적화된 해답을 찾아야 하는 조합 최적화 문제에 효과적으로 사용될 수 있다. 예를 들어, 여러 개의 물건을 최소한의 공간에 배치하는 방법이나 복잡한 경로 중 가장 효율적인 경로를 찾는 문제 등이 이에 해당한다. 모든 가능한 경우의 수를 탐색하는 것은 비효율적이거나 불가능할 수 있으므로, 담금질 기법과 같은 메타 휴리스틱 알고리즘이 유용하게 활용된다.

6. 변형 및 관련 기법

상호작용 메트로폴리스-헤이스팅스 알고리즘: 순차 몬테카를로 방법^[17]이라고도 하며, 담금질 기법의 이동 방식과 상호작용 재활용 메커니즘을 결합하여 최적해를 탐색한다.
양자 어닐링: 열적 변동 대신 "양자 변동"을 이용하여 목적 함수의 높지만 얇은 장벽을 통과하는 방식으로 최적해를 찾는다.
확률적 터널링: 담금질 기법이 온도가 낮아짐에 따라 지역 최적해(local minimum)에서 벗어나기 어려워지는 단점을 극복하기 위해, 에너지 장벽을 '터널링'하여 통과하려는 시도를 한다.
타부 탐색(TS): 일반적으로 더 낮은 에너지 상태로 이동하지만, 지역 최적해에 갇혔을 경우 일시적으로 더 높은 에너지 상태로 이동(오르막 이동)하기도 한다. 이미 방문했던 해를 "타부 목록"으로 관리하여 탐색 과정이 특정 상태에 머무는 순환(cycling)을 방지한다. 담금질 기법과 유사하게 현재 해의 주변을 탐색하는 기법이다.^[20]
듀얼 위상 진화: 탐색 공간의 위상 변화를 활용하여 지역 탐색과 전역 탐색 사이의 균형을 맞추는 알고리즘 군에 속하며, 담금질 기법도 여기에 포함될 수 있다.
반응 탐색 최적화(Reactive Search Optimization, RSO): 기계 학습과 최적화를 결합하는 데 중점을 둔다. 알고리즘 내부의 피드백 루프를 통해 문제의 특성, 주어진 인스턴스, 현재 해 주변의 지역적 상황에 맞게 알고리즘의 매개변수를 스스로 조정한다.
유전 알고리즘(GA): 단일 해가 아닌 여러 해의 집합(풀)을 유지하며 탐색을 진행한다. 새로운 후보 해는 기존 해의 일부를 변경하는 "돌연변이"나 두 해의 정보를 조합하는 "교차(재조합)"를 통해 생성된다. 담금질 기법에서 사용되는 것과 유사한 확률적 기준(선택)을 사용하여 돌연변이나 교차를 위한 후보를 선택하고, 풀에서 성능이 낮은 해를 제거한다.
밈 알고리즘: 여러 에이전트(agent)가 서로 협력하고 경쟁하며 해를 탐색한다. 때로는 에이전트의 전략에 담금질 기법 절차를 포함시켜 해를 재조합하기 전에 고품질의 해를 얻으려고 시도하기도 한다.^[18] 담금질 기법은 탐색의 다양성을 높이는 메커니즘으로 제안되기도 했다.^[19]
점진적 최적화: 최적화 과정 동안 목적 함수를 점진적으로 "부드럽게(smoothing)" 만들어 탐색을 용이하게 한다.
개미 군집 최적화(ACO): 여러 마리의 개미(또는 에이전트)가 해 공간을 이동하며 지역적으로 생산적인 영역을 찾는 방식으로 최적해를 탐색한다.
교차 엔트로피 방법(CE): 매개변수를 가진 확률 분포를 통해 후보 해를 생성한다. 매개변수는 교차 엔트로피 최소화를 통해 업데이트되어 다음 반복에서 더 나은 샘플을 생성하도록 유도한다.
하모니 탐색: 여러 음악가가 함께 최고의 화음(하모니)을 찾기 위해 각자 음을 연주하는 즉흥 연주 과정을 모방한 알고리즘이다.
확률적 최적화: 담금질 기법을 포함하여 다양한 확률 기반 접근법을 포괄하는 광범위한 최적화 방법론이다.
입자 군집 최적화(PSO): 탐색 공간에서 여러 입자(particle)가 이동하며 최적해를 찾거나, 목표가 있는 경우 사회적 행동을 모방하고 예측하는 군집 지능을 모델링한 알고리즘이다.
러너-루트 알고리즘(RRA): 자연에서 식물의 기는줄기(러너)와 뿌리에서 영감을 받아 개발된 메타휴리스틱 최적화 알고리즘으로, 단일 또는 다중 봉우리(modal) 문제를 해결하는 데 사용된다.
지능형 물방울 알고리즘(IWD): 자연계 물방울의 움직임을 모방하여 최적화 문제를 해결하려는 알고리즘이다.
병렬 템퍼링: 서로 다른 온도(또는 해밀토니안)를 가진 여러 개의 모델 복사본을 동시에 시뮬레이션하여, 탐색 과정에서 마주칠 수 있는 에너지 장벽을 효과적으로 극복하려는 기법이다.
다중 목적 담금질 기법: 다중 목적 최적화 문제에 담금질 기법을 적용한 변형 알고리즘이다.^[20]

7. 한계

담금질 기법은 전역 최적 해를 찾는 강력한 방법이지만 몇 가지 한계를 가진다.

가장 큰 한계 중 하나는 전역 최적해를 항상 보장하지는 않는다는 점이다. 이론적으로는 담금질 스케줄(온도를 낮추는 계획)을 충분히 길게 설정하면 전역 최적해에 도달할 확률이 1에 가까워진다.^[11] 하지만 실제 문제에서 전역 최적해를 보장할 만큼 충분한 시간을 투자하는 것은 완전 탐색만큼의 시간이 필요할 수 있어 비현실적일 때가 많다.^[12] 따라서 실제 적용 시에는 매우 좋은 지역 최적해를 찾는 선에서 만족해야 할 수도 있다.

또한, 담금질 기법은 에너지 함수 상에서 주변의 다른 상태들보다 훨씬 낮은 에너지를 갖는 "깊은" 지역 최적 상태(닫힌 유역)에 빠질 위험이 있다. 알고리즘이 이러한 상태에 한번 빠지면 벗어나기 위해 매우 오랜 시간이 걸릴 수 있다. 이는 유역 내 상태 수에 비례하고 주변 상태와 유역 바닥 사이의 에너지 차이에 대해 지수적으로 증가하는 시간이다. 어떤 후보 생성기(이웃 함수)를 사용하느냐에 따라 이러한 지역 최적 상태에 빠질 가능성이 달라질 수 있다.

담금질 기법의 성능은 여러 매개변수 설정에 크게 의존하며, 이를 적절히 설정하기 어렵다는 문제점도 있다.

탐색 단계(Step) 크기: 한 번에 탐색하는 이웃 해의 범위(Step 크기, P=nk)를 결정하는 것이 중요하다. Step 크기가 너무 크면 최적해를 건너뛸 수 있고, 너무 작으면 탐색 속도가 느려져 완전 탐색과 유사해질 수 있다.
냉각 스케줄(Annealing Schedule): 초기 온도 설정, 온도를 낮추는 속도와 방식(냉각 스케줄)은 알고리즘의 성능에 결정적인 영향을 미친다.

냉각이 너무 빠르면 지역 최적해에 쉽게 빠지고, 너무 느리면 계산 시간이 과도하게 길어진다. 이상적인 냉각 속도는 문제의 특성, 에너지 함수의 형태, 현재 온도, 후보 생성 방식 등 여러 요인에 복잡하게 의존하며, 사전에 결정하기 어렵다. 따라서 대부분의 경우 경험적으로 최적의 냉각 스케줄을 찾아 조정해야 한다. 적응형 시뮬레이티드 어닐링과 같은 기법은 이러한 문제를 해결하기 위해 냉각 스케줄을 탐색 진행 상황에 따라 자동으로 조절하기도 한다.^[16]

결과적으로 담금질 기법은 의미 있는 해를 찾기 위해 충분한 계산 시간을 필요로 한다. 문제의 복잡도나 요구되는 해의 정확도에 따라 상당한 시간이 소요될 수 있다. 초기 담금질 기법(Generic Simulated Annealing Algorithm)은 속도나 메모리 사용 측면에서 문제점이 지적되어, 이를 개선하기 위한 다양한 변형 알고리즘들이 연구되고 있다.

참조

_[1] 웹사이트 What is Simulated Annealing? https://www.cs.cmu.e[...] 2023-05-13
_[2] 논문 A Monte-Carlo Method for the Approximate Solution of Certain Types of Constrained Optimization Problems 1970-11
_[3] 논문 Statistical-Thermodynamic Approach to Determination of Structure Amplitude Phases 1979
_[4] 논문 The Thermodynamic Approach to the Structure Analysis of Crystals http://scripts.iucr.[...] 1981
_[5] 서적 Simulated annealing : theory and applications https://www.worldcat[...] D. Reidel 1987
_[6] 논문 Statistical-Thermodynamic Approach to Determination of Structure Amplitude Phases
_[7] 논문 The Thermodynamic Approach to the Structure Analysis of Crystals
_[8] 논문 Optimization by Simulated Annealing
_[9] 논문 Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm
_[10] 논문 Equation of State Calculations by Fast Computing Machines
_[11] 논문 Simulated annealing: A proof of convergence
_[12] 간행물 A Note on the Finite Time Behaviour of Simulated Annealing http://link.springer[...] Springer Berlin Heidelberg 2023-02-06
_[13] 논문 Stochastic versus deterministic update in simulated annealing
_[14] 논문 Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing
_[15] 논문 Best optimal strategy for finding ground states
_[16] 논문 Placement by thermodynamic simulated annealing
_[17] 논문 Sequential Monte Carlo samplers
_[18] 논문 An introduction to population approaches for optimization and hierarchical objective functions: A discussion on the role of tabu search 1993-06
_[19] 논문 On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms
_[20] 논문 A Simulated Annealing-Based Multiobjective Optimization Algorithm: AMOSA 2008-06
_[21] 논문 Optimization by Simulated Annealing
_[22] 논문 Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com