[AI] 4. CSP (Constraint Satisfaction Problems) - Local Search

 

앞서 CSP를 Backtracking Search 알고리즘 활용해 문제를 풀었는데, Backtracking Search는 Initial 조건 (ex. {WA = '', T = "" ...})에서 variable의 assignment를 하나하나 한달해서 솔루션을 찾는 방법이었다. (ex. {WA = red, T = ""} → {WA = red, T = green ...})

이번에는 관점을 바꾸어서, Initial 조건을 아무것도 할당하지 않은 상태가 아니라, 어떤 Domain으로 (random하게) assign이 되어있다고 가정하고, 잘못된 assignment를 하나하나 반복해서 고쳐나가는 방식으로 문제를 풀어보자. 위 그림을 예로 들면, Backtracking Search 처럼 초기값이 Non이 아닌 {red}로 모두 초기화를 하고 (complete assignment) constraint를 만족 못하는 variable을 하나하나 찾아나가는 것이다. 

이런 문제 해결법을 Iterative Improvement라 한다. Iterative Improvement는 문제가 풀릴때까지 위 과정을 반복하는데, assign할 variable은 random하게 선택되며, value ordering은 Heuristics를 활용한다. 예를 들어 남은 Domain의 수를 Heuristic으로 활용하면 남은 Domain의 수가 적은 Value로 assign 된다. (Min-Conflicts, 이 경우 LCV와 같은 개념) 한가지 예를 살펴보자.

이제는 제법 익숙한 N-Queens 문제이다. 앞서 설명한 절차에 빗대어 표현하면, 초기에는 Queen들이 random 하게 배치되어 있다. 이때 Heuristics는 5이다. (충족되지 않은 constraint 수) 다음으로 random한 Queen을 선택하여 Heuristics가 작아지는 방향으로(Min-Conflicts) 이동시키고, 이를 반복하면 단 3턴만에 N-Queens 문제를 해결 할 수 있게 된다.

다만, 위와 같이 Min-Conflicts 하도록 Iterative Improvement를 수행했을 때 주의해야 할 점은 critical ration에 따라 급격한 성능 저하를 일으킬 수 있음으로 주의해야 한다.

Local Search

이렇게 지나온 경로에 상관없이 현재 노드를 기준으로 주변 노드를 확인하여 조금이라도 더 좋은 해답을 찾는 기술을 통칭하여 Local Search라 하며, Iterative Improvement는 사실 CSP를 Local Search Problem으로 표현한 것에 불과하다.

Local Search는 지나온 경로를 기억할 필요도, 되돌아갈 필요도 없기 때문에 메모리나 속도에서 큰 이득을 가진다. 다만, 이런 시행착오를 겪으면서 해답을 찾는 과정은 Global optimal solution을 보장할 수 없다는 단점을 가진다. 이런 단점을 보안 하기 위해 다음 Variable이나 Value를 선택하는 전략을 잘 짜는 것이 중요하다. 아래는 Local Search의 대표적인 전략을 소개한다.

1. Hill Climbing

최근 인공신경망(ANN : Artificial Neural Network)이 관심을 받으면서, 알고리즘이나 고전 인공지능 등을 공부하지 않고 바로 인공신경망을 공부한 사람은 경사하강법(Gradient Decent)알고리즘이 익숙할 수 있다. 경사하강법은 x축으로 아주 극소량 반복 이동하면서 y의 최소점을 찾는 Optimize 알고리즘인데, Hill Climbing은 반대로 최대점을 찾는 알고리즘이다. 사실 최소점을 찾느냐 최대점을 찾느냐는 크게 의미가 없고, 이렇게 Iterative Improving 하는 방향으로 반복 이동하는 알고리즘을 흔히 Greedy Local Search라 부른다는 것 정도만 기억하면 되겠다. 그럼 그 원리를 간단히 살펴보자.

위 그림으로 Hill Climbing의 원리와 장단점을 모두 표현된다. 

먼저 Hill Climbing의 원리는 현재 state의 미분값(기울기)가 양수이면 (+) 방향으로 이동하고, 음수이면 (-) 방향으로 이동한다. 쉽게 말해 더 높은 곳으로 이동한다는 뜻이다. 그렇기 때문에 Hill Climbing은 기울기가 0인 곳, 산으로 치면 정상이나 Flat한 곳에서 알고리즘이 중단되게 된다. 여기서 중요한 문제점이 나오는데, 중단된 지점이 Global maximum이 아닐 수 있다는 것이다. 다만 직관적이고 빠르게 적당한 해(Local maximum)라도 찾는 데는 유용할 것이며, 이런 단점을 보완하기 위한 다양한 알고리즘들이 있다. 

(ex. Random-Restart Hill Climbing : Initial state를 random하게 배치하여 여러번 실행한 후 제일 좋은 해를 선택하는 방법)

2. Simulated Annealing

이런 Hill Climbing의 단점을 해결하기 위해 나온 알고리즘 중 하나가 Simulated Annealing이다. Hill Climbing의 경우 무조건 Goal (maximize)을 향해 가다가 Local maximum에 수렴할 수 있는데, Simulated Annealing은 아주 '가끔' 안 좋은 방향으로도 가게끔 하는 원리를 가진다. 이런 원리는 금속을 가열한 후 냉각시키면서 금속의 최대 가치를 창출하는 풀링(Annealing)을 모방했다고 한다. 그런데 왜 Simulated Annealing을 담금질 알고리즘이라고 부르는지는 모르겠다. 담금질은 Quenching인데...

어쨌든 그럼 이제 중요한 것은 얼마나 '가끔', 그리고 '얼만큼' 반대 방향으로 가게 할 것이냐가 남았다. 아래 Pseudo Code를 보자.

Hill-climbing 이라면 VALUE[next]가 VALUE[current] 보다 크면 상승방향이기 때문에 next 로 이동하고, 그렇지 않으면 무시했을 것이다. (아래에서 2번째줄) 

하지만 Simulated Annealing 알고리즘은 VALUE[next]가 VALUE[current]보다 작은, 즉 하강하는 경우를 무시하지 않고 특정 확률에 따라 next 방향으로 따라간다. (가장 아랫줄) 다시한번 조금 더 자세히 Simulation 해보자.

온도 T는 초기엔 충분히 큰 값을 가지다가 시간이 지날수록 0 으로 낮아진다고 하자. (마치 금속을 달궜다가 식히는 것 처럼) 그리고 VALUE는 Maximize 하고자하는 대상(금속의 가치)라고 했을 때, next state가 VALUE를 상승시킨다면 next state로 이동한다. 여기까지는 Hill Climbing과 같다.

반면 VALUE[next]가 VALUE[current]보다 더 작다면, 무시하지 않고 일정 확률에 따라 하강을 허용하기도 하는데 그 확률이 exp(E/T)이다. exp(x) 함수는 x가 음수일 때 0~1사이의 값을 갖는데 E ≤ 0 이기 때문에 0과 1사이의 확률로 사용할 수 있다. 이 확률 조건을 살펴보면,

 1) T가 작은경우(시간이 충분히 흐른 경우)에는 매우 낮은 확률을 가짐으로 현재 상태를 유지하려 할 것이다. 

 2) 반면 T가 매우 높은 경우(초창기)에는 매우 높은 확률로 next state를 반영하여 하강할 확률이 높다. 

 3) 그리고 E는 next와 current VALUE의 차인데, 그 차이가 클 수록 작은 확률을 가진다.

위 3가지 경우를 정리하면, Annealing의 초창기에는 하강 곡선을 만나도 높은 확률로 반영하면서 만약 그 곳이 local maxima의 비탈길이 었다면 탈출하여 다른 언덕을 탈 수 있게 해 준다. 반면 시간이 흘러 T가 작아지면 매우 보수적으로 next state를 허용함으로써 점차 VALUE가 수렴하게 되고, 이론적으로 이와 같은 방법으로 Global maxima를 찾을 수 있다고 한다. 다만 Hill Climbing의 경우 산넘어 산넘는 과정을 구현했듯 Local maxima가 많을 수록 Global maxima를 찾기가 점점 어려워지고 시간도 많이 걸린다. 

3. Genetic Algorithm

Simulated Annealing이 금속의 뜨임에서 영감을 얻었다면, 인간의 유전자 진화에서 영감을 얻은 Genetic Algorithm 또한 매우 강력한 Local search 알고리즘으로 평가 받는다.

Genetic Algorithm은 평가(Fitness)와 선택(Selection) 그리고 교배(Cross-Over)와 돌연변이(Mutation)과 같은 변화 과정을 반복하여 Global solution을 찾는 방법이다.

위 그림은 Feature가 8개인 sample 데이터 4개가 Genetic Algorithm을 만났을 때 1-iteration동안 일어나는 일이다. 

 1) sample은 아마 수 많은 데이터 중 가장 상위 Rank에 놓여진 Top 4 sample (Gene)일 것이며 

 2) 각 sample은 자체적으로 평가되는 적합도(Fitness)가 있다. 

 3) 이제 4개 샘플을 교배 시켜야하는데, 가장 좋은 2개의 유전자를 선택할 수도 있지만 염색체(Gene)의 다양성을 해치기 때문에 마치 룰렛을 돌려 찍는 것 처럼 Roulette Wheel Selection 확률을 통해 선택(Selection) 된다. 

 4) 선택된 염색체는 random하게 division point가 결정된 후 Cross-Over연산자를 통해 자손을 생산해 낸다.

 5) 그리고 생성된 자손은 낮은 확률로 돌연변이(Mutation)연산을 통해 변형된다.

위 1~5)과정을 반복하는 것을 다시 표현하면

우수한 유전자를 뽑아 각 유전자의 장점을 취하는 개체를 반복 생산하여, 적합도(Fitness)가 더 높은 새로운 개체를 생성하는 것이다. 이렇게 사람의 유전자의 진화 과정을 모방한 알고리즘이 Genetic Algorithm이며, 당사 에서도 금속의 합금성분을 Feature로한 sample에 대해 Genetic Algorithm을 적용하여 신강종 합금성분비를 도출한 사례가 있다.