Simulated Annealing - 모의 담금질
3, 4차시
@ 강의실 어딘지 너무 헷갈려~
💫 Simulated Annealing - 모의 담금질
Simulated Annealing - 모의/유사 담금질
최적화 → 검색 → 모의 담금질
담금질 :
금속을 가열하고 급냉시켜 경도를 높히는 작업
고체 → 액체 → 기체
고체 ← 액체 ← 기체
안정 → 불안정 (변화 가능한)
0 - 지금보다 더 나은 상태 요구
1 - 지금 그대로가 아니라, 변화가 있어야
→ 변화가 일어나기 쉬운 상태로
2 - 계속해서 변화만 하면 안됨
→ 다시 안정한 상태로
💫 과정
임의의 조건/가중치 계산, 결과 A
임의의 변형, 새로운 결과 B
이전 결과 A 와 새로운 결과 B 비교
Loop하여 답을 찾는 것
지금보다 좋은 상황만 찾음
→ Greedy Algorithm - 맹목적 알고리듬
→ Hill Climbing Algorithm
지금 상태가 정말 가장 좋은 상태인가?
Local Max, Global Max
현재 위치에서 한 발자국 씩 옮겨서 더 높은 곳으로 이동
→ Hill Climbing Algorithm
문제
→ 평면이나 Local M을 만난다면?
→ 과적합
→ 여러 군데에서 시작하면 될까?
제일 좋은 곳을 가기위해서는
좋은 곳만 찾지 말고, 욕심을 버리고 아래로 내려가야 한다
→ 정착을 못함
언제 정착 ?
→ 시간이 지날수록 조건을 까다롭게
Sample Problem - N-Queen
초기 soln를 대충 만들어두고, soln를 평가
답(최정상)은 모르니까 대강 어느정도 좋다
핵심 두 가지
- 지금보다 더 좋지 않은 솔루션을 찾은 경우에도 이전 것을 버리고 나쁜 것을 받아들일 수 있다는 것
- 나쁜 것을 받을 때 심사를 하는데 심사기준을 처음에는 루즈하게(많이 나빠도 OK), 점점 까다롭게(탐색 후반부에서는 허용 X)
기체/액체/고체 상변화에서도,
그걸 비유적으로 이야기 할 수 있는
Loss (책에서는 Energy)
현재 상황이 좋은가? 에 대한 기준
얼마나 나쁜가 (클수록 나쁜 것, 에너지가 높을 수록 변화가 많음)
Loss가 낮아야 좋은 것
교체 확률 (0 ~ 1) :
→ 그래프에서 Y축
→ 1이면 무조건 바꾸겠다는 것
Delta Energy - 평가 결과 = 에너지 E
I.E. 0~20, N-Queen 겹치는 경로 수
교체 확률, 평가 결과 그래프에 대해,
→ 평가 결과가 작을 수록 교체 확률이 크다
→ 평가 결과가 최대까지 가더라도 교체 확률이 존재하긴 하는데 작다
→ 덜 나쁠수록 더 많은 기회를
Temperature 온도 (상수)
→ 온도가 높다 = 시작 단계
→ 온도가 낮다 = 끝 단계
자연에서도
→ 온도가 높다 = 무질서하다 (Like 고체-액체-기체)
→ 온도를 낮출 수록 안정적인 상태가 된다
평가 결과가 최대더라도, 온도가 높으면 (즉 시작 단계면)
교체 확률이 높다
같은 온도에서는 (다시말해 온도 상관없이는)
평과 결과가 낮을수록 교체 확률이 높다
@ U 중간고사 출제 : 두 가지 (조건, 식)을 가지고 모의담글질을 설명하시오. (각각 온도 50, 2 ~)
욕심쟁이 알고리듬과 그 문제점
→ 좋은 상태만 찾음, 로컬 Max에 머무를 수 있다
반면 모의 담금질
→ 핵심은 온도(불안정 수치)라는 개념을 도입해서,
→ 탐색 초기에는 현재 상태보다 많이 나쁜 상태여도 채택하는 확률을 높게 설정하고,
→ 시간이 지날 수록 현재 상태보다 많이 좋은 상태여도 채택하는 확률을 낮게
→ (불안정한 온도 안정시키기, 초기 높게 설정된 온도를 점차 낮추기)