[AI] Constraint Satisfaction Problems (2)
이 글은 포스텍 이근배 교수님의 CSED442 인공지능 수업의 강의 내용과 자료를 기반으로 하고 있습니다.
인공지능 3주차 두 번째 강의 요약이다.
믿었던 AI 과제마저도 날 괴롭히는 바람에 포스팅이 가면 갈수록 늦어지고 있다.
시험도 얼마 안남았는데, 더 힘내서 살아야겠다.
여하튼, 이번 포스트에서는 backtraking과는 다른 방식으로 CSP를 푸는 방법을 소개한다.
1. Iterative Improvement
우리가 이전에 배웠던 backtracking은 initial assignment에서 시작해서 적절한 assignment를 하나씩 찾아가는 방식이었다.
이 접근법을 완전히 뒤집어서, 하나씩 할당해보는게 아니라 이미 할당되어 있는 값을 바꿔보면서 올바른 답을 찾아나가면 어떨까?
다시 말해,
- Initial state: the complete assignment
- Successor function: reassign a value to an assigned variable
- Goal test: is consistent?
이런 식으로 search를 해보면 어떨까?
바로 이것이 iterative improvement다.
예를 들어, 2개의 variable로 이루어진 CSP가 있다고 해보자.
Backtracking은 {} → {red} → {red, red} → {red}(backtrack) → {red, blue} … 이런 식으로 하나씩 할당해가며 해를 찾겠지만,
Iterative improvement는 위의 그림처럼 {red, red} → {red, blue} … 이런 식으로 complete assignment의 value들을 조정해가며 해를 찾는다.
2. Local Search
사실 위에서 설명한 iterative improvement는 CSP를 local search problem으로 표현한 것에 불과하다.
그럼 local search란 무엇일까?
local search란 지나온 경로들에 관계 없이 현재 노드를 기준으로 이웃 노드를 확인하여 조금이라도 더 좋은 노드로 이동하는 방식을 말한다.
말 그대로 지역적인 탐색을 하는 것이다.
그럼 이게 어떤 이점을 가질까?
지나온 경로에 관심이 없으므로 fringe를 유지할 필요가 없어서 메모리 효율성이 상당히 좋고, 뒤로 돌아갈 필요도 없으므로 대체로 빠르다는 장점이 있다.
그러나 당연하게도 해를 찾아낸다는 보장이 없고, 해를 찾아낸다 하더라도 그것이 optimal하다는 보장 또한 없을 것이다.
이런 단점들을 보완하기 위해서는 이웃 노드로 이동하는 전략을 잘 짜야만 한다.
1. Hill Climbing
첫 번째 전략은 hill climbing으로, 무조건 현재 노드보다 좋은 노드로 이동하는 것이다.
흔히 greedy local search라고 부른다.
이해를 위해 5-Queens 문제를 iterative improvement with hill climbing로 풀어보자.
여기서 hill climbing을 한다는 말은 가장 constraints를 적게 위반하는 value를 고른다는 것이다. (PPT의 min-conflicts heuristic과 동일하다)
참고로 variable은 랜덤하게 선택한다!
Initial state는 위와 같다.
첫 번째로 4번 variable이 선택되었다.
이때 evaluation을 해보면, 5번째 column으로 옮기는 것이 가장 constraints를 적게 위반한다.
따라서 저기로 옮기자.
두 번째로는 3번 variable이 선택되었다.
역시 evlaluation을 해보고, 가장 적게 위반하는 column으로 옮기면 된다.
이 과정을 반복하다보면
이와 같은 solution을 얻을 수 있을 것이다.
Problem of Hill Climbing
hill climbing은 언제 멈출까?
주변에 더 이상 올라갈 공간이 없을 때 멈출 것이다.
문제는 그 멈춘 지점이 global maximum이 아니라 local maximum 또는 flat (shoulder, flat local maximum) 일 수 있다는 점이다.
심지어 agent는 멈춘 지점이 global인지 local인지 flat인지 판단할 수도 없다. 그냥 한 번 멈추면 끝인 것이다.
그래서 hill climbing은 complete하지도, optimal 하지도 않다고 하는 것이다.
이런게 언제 쓰이냐 싶겠지만, 정확한 해를 찾기보단 빠르게 적당한 해를 찾아야 하는 문제의 경우에는 유용하다.
이런 문제를 개선하기 위해서 나온게 Random-Restart Hill Climbing이다.
여러 번 돌려본 다음, 제일 잘 나온 값을 고르는 것이다.
2. Simulated Annealing
Hill climbing이든 random restart든 모두 올라가기만 하는 알고리즘이기에, 한번 maximum에 도착하면 탐색이 끝나버린다.
그럼 내려가는 알고리즘도 추가하면 global maximum에 도달할 확률이 높아지지 않을까?
이것이 Simulated Annealing의 접근법이다.
Simulated Annealing은 독특하게도 금속을 ‘가열 냉각’하는 과정을 본따 내려가는 알고리즘을 만들었다.
기존의 diagram을 뒤집어 보자.
그럼 maximum이 계곡이 된다.
계곡에 갇힌 agent의 온도가 높다면 (금속이 불안정하다면) 마구 튀어서 이 계곡을 빠져나와 다른 계곡에 들어갈 수도 있을 것이다.
그러다 점점 agent의 온도가 낮아지면 (금속이 안정해지면) 계곡에서 빠져나오지 못하고 해당 계곡에 정착해버릴 것이다.
이런 식으로 maximum을 결정하는 것이다.
이게 효율적인가 의문이 들 수도 있다. 잘못 튀면 오히려 더 안 좋은 상태에 갇혀버릴 수도 있으니까.
그런데 놀랍게도 온도가 충분히 천천히 감소한다면 optimal하다고 한다!
물론 그 감소하는 속도가 너-무 느려서 반드시 그 수준을 맞추기 보다는, 적절히 조절해서 쓰는 편이라고 한다.
아래는 수도코드이다.
수도코드에서 기억해야 할 부분은 $if\; \Delta E>0\; else$ 부분이다.
개선 되지 않는 노드를 찾아냈을 경우 Hill climbing 이라면 가차없이 버렸겠지만, simulated annealing은 확률적으로 해당 노드로 이동한다.
3. Genentic Algorithms
Simulated annealing은 분명 매력적인 알고리즘이지만, 현실은 그렇게 녹록치 않다.
Global maximum을 찾기 위해 건너야 하는 local maximum이 수십개나 있을 수 있다.
게다가, 다른 maximum 까지 가기 위해선 내려갔다가 다시 또 올라가야 하므로 정말 많은 시간이 걸릴 것이다.
그래서 나온 아이디어가 아예 다른 곳으로 점프해버리자는 것이다.
이를 적용한 대표적인 알고리즘이 Genetic algorithm 이다.
Genetic algorithm이란 자연의 상태학적 유전 알고리즘을 본따 만든 알고리즘이다.
State를 유전자로 생각해 마치 교배를 통해 유전자가 섞는 것처럼 state들의 내부 요소들을 섞는 것이다.
구체적으로는 다음 과정으로 진행된다.
- 여러 개체들에 대해서 적합성을 평가해서 각 개체들이 선택될 확률을 계산한다.
- 확률에 따라 개체들을 선택한다
- 선택된 개체들의 유전자를 교차로 적절히 섞는다.
- 만들어진 개체의 유전자에 임의로 돌연변이를 만든다.
- 원하는 솔루션을 찾을 때까지 반복한다.
예를 들어 N-Queens를 genetic algorithm으로 푼다고 해보자.
위 그림처럼, 여러 state 중 일부를 뽑고, 적절히 섞어 우측의 새로운 state를 탄생시킨 다음 local change를 통해 mutation을 일으키는 방식으로 탐색을 하게 된다.
3. 출처 및 참고자료
마프 조교님 블로그인데, 정리가 잘 되어있다.
좀 더 자세한 내용에 대해서 알고 싶다면 읽어보는 것을 추천한다.
댓글남기기