[인공지능] Local Search - 2
Hill-climbing on the 8-Queens Problem
8-Queens 문제는 8x8 체스판에 8개의 퀸을 서로 공격할 수 없는 위치에 배치하는 문제이다. Hill-climbing 알고리즘은 이 문제의 해결책을 찾기 위해 사용될 수 있다.
- No sideways moves:
- sideways move를 허용하지 않는 경우를 의미한다. 즉, 현재 상태보다 더 나은 상태로만 움직인다.
- Succeeds w/ prob. 0.14 : 이 방법으로 문제를 성공적으로 해결할 확률은 0.14이다.
- Average number of moves per trial : 시도당 평균 움직임 횟수는 성공할 때 4번, 막힐 때 3번입니다.
- Expected total number of moves needed : 필요한 총 움직임 횟수의 기대값은 3(1−𝑝)/𝑝 + 4로, 약 22번의 움직임이라고 계산된다.
- Allowing 100 sideways moves:
- 100번의 sideways move를 허용하는 경우를 의미한다. 즉, 현재 상태와 같은 값을 가진 상태로도 움직일 수 있다.
- Succeeds w/ prob. 0.94 : 이 방법으로 문제를 성공적으로 해결할 확률은 0.94이다.
- Average number of moves per trial : 시도당 평균 움직임 횟수는 성공할 때 21번, 막힐 때 65번이다.
- Expected total number of moves needed: 필요한 총 움직임 횟수의 기대값은 65(1−𝑝)/𝑝 + 21로, 약 25번의 움직임이라고 계산된다.
8-queen 문제의 경우 86% 확률로 정답을 찾지 못한다.
goal 을 찾으면 평균 4번, 찾지 못하는 경우(Local maximum) 3번만에 알고리즘이 끝난다.
shoulder 에서도 움직일 수 있는 Sideway moves 를 허용한 8-queen 은 6%확률로 정답을 찾지 못한다.
goal 을 찾으면 21번, 찾지 못하는 경우에는 65번만에 알고리즘이 끝난다.
단 sideway moves 를 할 때 shoulder 에서만 무한으로 왔다갔다 할 수 있으므로 이동 횟수를 제한해야한다.
이 결과를 통해, sideway move를 허용하면 문제를 성공적으로 해결할 확률이 크게 증가하지만, 필요한 총 움직임 횟수도 약간 증가한다는 것을 알 수 있다. 따라서, 어떤 방법을 선택할지는 문제의 요구 사항과 상황에 따라 결정해야 한다.
Moral: algorithms with knobs to twiddle are irritating
"knobs to twiddle"는 알고리즘의 동작을 조절하거나 최적화하기 위해 미세하게 조정해야하는 매개변수나 설정을 의미한다. 최적의 성능을 위해 알고리즘의 매개변수를 반복적으로 조절하고 테스트하는 과정은 복잡하고 시간이 많이 소요될 수 있기 때문에 매개변수를 조절해야 하는 알고리즘은 사용하거나 구현하는 데 있어 불편함을 줄 수 있다(irritating).
Simulated Annealing
"Simulated Annealing"은 최적화 문제를 해결하기 위한 확률적 알고리즘 중 하나이다. 이 알고리즘은 금속을 천천히 냉각하여 주문된 (저에너지) 상태 (ordered (low-energy) state) 에 도달하도록 하는 금속의 담금질(annealing) 과정을 모방한다.
기본적인 개념은 다음과 같다 :
- Allow “bad” moves occasionally, depending on “temperature” : 일반적인 로컬 검색 알고리즘은 항상 좋은 상태로만 이동한다. 그러나 Simulated Annealing은 "온도"(temperature)에 따라 가끔 "나쁜"(bad) 움직임을 허용한다.
- High temperature => more bad moves allowed, shake the system out of its local minimum. : 높은 온도에서는 더 많은 나쁜 움직임이 허용된다. 이는 시스템을 지역 최소값(local minimum)에서 벗어나게 하기 위한 것이다.
- Gradually reduce the temperature according to some schedule. : 알고리즘의 실행 과정에서 온도는 점차적으로 감소한다.
Simulated Annealing은 지역 최적해에 갇히는 문제를 극복하기 위해 설계된 알고리즘이다. 온도가 높을 때는 다양한 상태를 탐색하고, 온도가 낮아질수록 좋은 상태로만 이동하게 된다. 이러한 방식으로 전역 최적해에 접근하게 된다.
Simulated Annealing의 개념은 처음 듣기에는 다소 복잡하고 불확실하게(flaky) 느껴질 수 있다. 그러나 실제로 이 알고리즘은 많은 최적화 문제에서 효과적으로 작동하며, 전역 최적해에 가까운 해를 찾는 데 성공적이다.
Simulated Annealing Algorithm
function SIMULATED-ANNEALING(problem,schedule) returns a state
current ← problem.initial-state
for t = 1 to ∞ do
T ←schedule(t)
if T = 0 then return current
next ← a randomly selected successor of current
∆E ← next.value – current.value
if ∆E > 0 then current ← next
else current ← next only with probability e^(∆E/T)
function SIMULATED-ANNEALING(problem,schedule) returns a state
- `SIMULATED-ANNEALING`이라는 함수가 정의되어 있으며, 입력으로 `problem`과 `schedule`을 받아 결과로 상태(state)를 반환한다.
current ← problem.initial-state
- 초기 상태를 `current`로 설정한다.
for t = 1 to ∞ do
- 시간 변수 t를 1부터 시작하여 무한 루프를 시작한다.
T ←schedule(t)
- `schedule` 함수를 사용하여 현재의 온도 `𝑇`를 결정한다.
if T = 0 then return current
- 온도 `𝑇` 가 0이 되면 현재 상태 `current`를 반환하고 알고리즘을 종료한다.
next ← a randomly selected successor of current
- 온도 `𝑇` 가 0이 아니라면 알고리즘을 종료하지 않고 진행한다. 현재 상태 `current`의 무작위로 선택된 후속 상태(이웃 상태)를 `next`로 설정한다.
∆E ← next.value – current.value
- `next` 상태와 `current` 상태의 값 차이를 계산하여 `∆𝐸`로 설정한다.
if ∆E > 0 then current ← next
- 만약 `∆𝐸`가 양수라면 (즉, `next` 상태가 `current` 상태보다 더 좋다면), `current`를 `next`로 업데이트한다.
else current ← next only with probability e^(∆E/T)
- 그렇지 않다면( 즉, `next` 상태가 `current` 상태보다 나쁘다면), `𝑒^(∆𝐸/𝑇)`의 확률로 `current`를 `next`로 업데이트한다. => bad moves 허용
- 이 확률은 `∆𝐸`와 온도 `𝑇`에 따라 결정된다.
이 알고리즘의 핵심은 높은 온도에서는 나쁜 움직임 (즉, 현재 상태보다 나쁜 상태로의 이동)을 허용하면서 전체 상태 공간을 탐색하고, 온도가 점차 감소함에 따라 좋은 움직임만을 허용하여 전역 최적해에 접근하는 것이다.
Simulated Annealing
이론적 보장(Theoretical guarantee) :
- Stationary distribution (Boltzmann): 𝑃(𝑥)∝𝑒^(𝐸(𝑥)/𝑇):
- Boltzmann 분포는 물리학에서 에너지 상태의 확률 분포를 설명하는 데 사용된다. 이 알고리즘에서는 고정 분포로 볼츠만 분포를 사용해 𝑥 에 대한 시스템의 상태 확률 P가 에너지 E와 온도 T에 따라 결정된다는 것을 나타낸다.
- If 𝑇 decreased slowly enough, will converge to optimal state! : 온도 𝑇가 충분히 천천히 감소하면, 알고리즘은 최적 상태에 수렴하게 된다.
이론적 보장 증명 개요 (Proof sketch) :
- Consider two adjacent states 𝑥, 𝑦 with 𝐸(𝑦)>𝐸(𝑥) [high is good]
- 두 인접한 상태 𝑥와 𝑦를 고려하며, 𝐸(𝑦)가 𝐸(𝑥)보다 큰 경우를 생각한다. 여기서 "high is good"은 높은 에너지 값이 더 좋은 상태라는 것을 의미한다. ( 𝐸(𝑦)가 𝐸(𝑥)보다 좋은 상태이다 )
- Assume 𝑥→𝑦 and 𝑦→𝑥 and outdegrees 𝐷(𝑥)=𝐷(𝑦)=𝐷
- 상태 𝑥에서 𝑦로의 전이와 𝑦에서 𝑥로의 전이를 가정한다. 또한 두 상태의 진출 차수 𝐷 (outdegree)가 동일하다고 가정한다.
- Let 𝑃(𝑥), 𝑃(𝑦) be the equilibrium occupancy probabilities at 𝑇
- 온도 𝑇에서의 균형 점유 확률( equilibrium occupancy probabilities )을 𝑃(𝑥)와 𝑃(𝑦)로 나타낸다.
- Let 𝑃(𝑥→𝑦) be the probability that state 𝑥 transitions to state 𝑦
- 상태 𝑥에서 상태 𝑦로 전이될 확률을 𝑃(𝑥→𝑦)로 나타낸다.
𝑃(𝑥)𝑃(𝑥→𝑦) = 𝑃(𝑦)𝑃(𝑦→𝑥)
(1/𝐷)e^((E(x)-E(y))/T)
P(x)/P(y) = e^(E(x)/T) / e^(E(y)/T)
이 부분은 필기를 보면서 그 증명을 알아야할 거 같음
Occupation Probability as a Function of 𝑇
"Occupation Probability as a Function of 𝑇"는 Simulated Annealing 알고리즘에서 중요한 개념이다. 여기서 "Occupation Probability"는 시스템이 특정 상태에 있을 확률을 나타내며, 𝑇는 온도를 나타낸다.
Simulated Annealing에서, 온도 𝑇는 알고리즘의 "탐색성"을 조절하는 매개변수이다. 높은 온도에서는 시스템이 다양한 상태를 탐색하게 되며, 낮은 온도에서는 좋은 상태로만 이동하려는 경향이 있다.
"Occupation Probability"는 다음과 같은 특성을 가진다:
1. 높은 온도일 때 : 시스템은 다양한 상태를 탐색하므로, 모든 상태에 대한 점유 확률은 거의 동일하게 된다.. 즉, 시스템은 어떤 상태에 있을 확률이 거의 동일하다.
2. 낮은 온도일 때 : 시스템은 에너지가 낮은 (또는 높은, 문제에 따라 다름) 상태로 이동하려는 경향이 있다. 따라서, 좋은 상태의 점유 확률이 높아지고, 나쁜 상태의 점유 확률이 낮아진다.
3. 온도가 0에 가까워질 때 : 시스템은 가장 좋은 상태에만 있을 확률이 가장 높아진다.
Simulated Annealing
- Simulated Annealing 알고리즘이 최적 상태에 수렴(convergence)한다는 것은 중요한 보장이다. 온도가 충분히 천천히 감소하면 알고리즘이 전역 최적해에 수렴할 것이다.
- Simulated Annealing의 원리는 실제로는 몇 가지 중요한 사실에 기반한다. :
- 지역 최적해에서 벗어나기 위해 필요한 하향 단계(downhill step)가 많을수록, 그 모든 단계를 연속으로 (in a row) 수행할 확률은 줄어든다.
- "충분히 천천히"(Slow enough)라는 표현은 온도를 지수적으로(exponentially) 천천히 감소시키는 것을 의미할 수 있다.
- Random restart hillclimbing 알고리즘도 최적 상태(optimal state)에 수렴(converge)한다. 이는 Simulated Annealing과 비교하여 다른 접근 방식을 사용하는 알고리즘의 예이다.
- Simulated Annealing과 그와 관련된 알고리즘들은 VLSI 레이아웃(반도체 칩의 설계와 제조 과정에서 최적 위치에 배치하는 공정) 및 기타 최적 구성 문제에서 핵심 도구로 사용된다.