[인공지능] 4. Beyond Classical Search - 1

1. Local Search algorithm

 : Local Search algoritms은 single current node와 일반적으로 그 노드의 neighbors node로 움직이는 operation을 사용한다. 전형적으로 search에 의해 따라오는 path는 유지되지 않는다.

  -> 그래서 little memory만 사용 (보통 constant amount)

  -> 아주 크거나 infinite(continuous)한 state space에서 납득할만한 solution을 찾을 수 있다. (systematic algorithms은 적합하지 않걸랑)

  -> 또한 local search algorithm은 optimization problem(objective funtion에 따라 가장 best state를 찾는 것이 목표인 문제)을 푸는데 유용하다. 

 

  1) Hill-climbing search

 : objective function에 의해 현재 state가 얼마나 좋은지 판단해서, 더 값이 큰 곳으로 이동해 maximum을 찾는다.

알고리즘도 단순하다. neighbor 에 current의 successor중 가장 높은 valu를 가진 아이를 넣고, 현재 value보다 높으면 neighbor로 이동

HillClimbing search로 8-queens문제를 해결한다고 해보자.

8-queens 문제는 같은 행/ 열/ 대각선끼리 공격이 가능하다고 할 때, 서로 공격하지 않게 배치하는 문제이다.

한 개의 퀸을 이동하는 것이 action이고 공격 가능한 set의 개수를 object function value라고 했을 때, 우리의 목표는 이 값을 descent, 즉 내려와야 하는 것이다. 즉 앞선 설명과 달리 minimum 값을 찾아야 한다.

 

- hill-climbing search 알고리즘은 value가 증가하는 방향으로 계속 움직이는 아주 단순한 반복문이다. 

- 아무런 neighbor도 더 higher value를 갖지 않는 "peak"에 도달했을 때 알고리즘은 끝이 난다.

- search tree를 포함하고 있지 않아, current node의 data structure에는 오직 state와 objective function의 value 값만 필요하다. 

- hill-climbing은 때론 greedy local search라고 불린다. 어디로 가야할지 미리 생각하지 않고 그저 good neighbor state만 찾아다니거든. 즉 현재상태만이 중요하지, 과거와 미래는 신경쓰지 않음.

 

-그러나 불행히도, hill climbing은 "Local maxima, Plateaux, Rridges" 와 같은 이유로 문제가 생기곤 한다. 

 - Local maxima의 경우, 전체적으로 봤을 때 max값이 아닌데, 그 국소 지역에서의 max값에 갇혀 local밖에 보지 못하는 것

 - plateaux는 고원이라는 뜻으로, 평평한 지점에서 조금만 더 가면 더 높은 값을 찾을 수 있는데 그 평평한 구간에 갇혀버리는 것

- ridges는 어떤 state에서 취할 수 있는 모든 action을 다 취해도 더 높은 곳으로 가지 못하는 경우. 즉 local maxima가 서로 직접 연결되어있지 않은 경우. 낮은 곳을 들렀다가 가면 갈 수 있는데 낮은 곳은 애초에 안 감.

 

 1-2 ) Various Hill-Climbing Search Strategies

 

  i. Stochastic hill climbing : 가장 가파른 곳만 선택하는 것이 아니라 확률적으로 선택한다. 가파른 곳을 갈 확률이 더 높고, 완만한 곳 확률이 더 낮다. 그냥 steepest ascent보다는 느리겠지만, 더 나은 solution을 발견할 수도 있다.

 

 ii. First-choice hill climbing : 현재 state에서 가능한 모든 다음 state를 만들고서 그중에서 어디 갈지 고르는게 아니라, 다음 state를 랜덤으로 하나하나씩 만들어 나간다. 그래서 현재 state보다 value가 좋은 다음 state가 발견되면 그곳으로 바로 이동한다. 만약 state가 매우 많은 successor를 가지고 있을 경우 좋은 전략이 된다.

 

 iii. Random-restart hill climbing : goal을 찾을 때까지 랜덤하게 생성되는 initial state에서 hill climbing search를 수행한다. 시간이 무한할 경우 무조건 goal을 찾을 수 밖에 없어서 complete하다. (initial state처럼 goal state도 사실 생성해내는거나 마찬가지)

 

 - hill-climing algorithm은 절대 내려가는 방향으로는 움직이지 않아서 incomplete하다. 만약 local maximum에 갇혀버리면 global solution은 찾을 수가 없기 때문이다.

 

 

 

 

 2) Simulated Annealing 

 : hill climbing과 random walk를 합친 형태로, efficiency와 completeness를 둘다 잡은 알고리즘. 항상 올라가는 것만 아니라, 가끔 내려가기도 하는데, 탐색 초기에는 그 행동을 자주 shaking하다가 점차 그 intensity를 줄여나간다. 이 방법을 사용하면 local maxima에서 벗어날 수 있다. 

 

예를 들어 가장 작은 값을 구하기 위해 공을 굴린다고 생각하자. 그러면 local minima에 빠질 수 밖에 없는데, 이 때 이 통을 흔들어줘 그 local minima에서 벗어나 global minima 값을 찾을 수 있게 해주는 것이다.

 

 먼저 initial state를 current node에 넣어주고 시작한다. schedule(t)는 큰수에서 작은수까지 역순으로 정렬하게 해주는 코드이다. 즉 T에는 무한대부터 1의 값이 순서대로 들어간다. 만약 T가 0이라면 for문을 탈출한다. 

current의 successor중에서 랜덤하게 하나를 선택하여 next에 넣고, △E의 값에 next value 와 current value의 차를 넣어준다. △E가 양수라면 next value가 더 좋은것이므로 current에 next를 넣어준다. 만약 음수라면 e^△E/T 의 확률로 current에 next를 넣어준다. 즉 값이 더 안좋더라도 일정 확률에 따라 내려가기도 하는 것이다.

 

참고로 내려갈 때의 확률에서 △E는 당연히 음수이고(음수이니까 else문에 들어왔겠죠), e의 △E/T제곱이므로 T값이 작아질수록 확률의 값도 작아진다.

 

 

 

 

 3) Local Beam Search

   : Local Beam Search algorithm은 노드를 하나가 아니라 k개의 states를 가지고 있는다.

    - K개의 랜덤하게 생성된 states에서 시작해서, 각 step마다 모든 k states의 successor들이 생성된다. 그 중 하나가 goal이라면 알고리즘이 정지한다. 만약 아니라면, k x n 개의 노드 중에서 best successor k개를 선택하여 위 작업을 반복한다. 

    -랜덤하게 다시 시작할 때, 각 search process가 독립적으로 실행된다. 또한 유용한 정보가 있다면 병렬적으로 검색 thread간에 전달이 된다. 왜? best k개에서 다시 시작, 또 다시 시작 하다보면 best한 위치를 중심으로 검색이 이뤄질거니까! 

    - 하지만 이렇듯 local beam search는 좋은 쪽으로만 가기 때문에 탐색 공간의 lack of diversity의 문제가 생길 수 있다. 국소지역에 집중하게 되어버려 오히려 hill climbing보다도 더 많은 탐색을 하게 되어버릴 수도 있다. 

    - stochastic beam search는 k successor을 랜덤으로 뽑는다. (완전 랜덤은 아니고, value가 좋아질 수록 뽑을 확률도 높아지는) 이걸 통해서 앞서 말한 lack of diversity 문제를 어느정도 해결할 수 있다.

 

 

 

  4) Genetic Algorithm(유전 알고리즘)

    : genetic algorithm(=GA)는 successor state가 두 개의 parent states를 합쳐서 만들어지는 stochastic beam search의 변형판이라고 할 수 있다. 

 - 각 state(=individual)은 유한한 알파벳으로 이루어진 string으로 이루어지는데, 보통은 0또는 1이다.

 - 각 state는 objective function (=fitness function, 적합도) 를 기준으로 평가된다.

 - beam search처럼 GA도 처음에 k개의 랜덤 생성된 state로 시작한다. 이 initial state를 poopulation이라고 부른다.

 - reproduction을 위해서 랜덤으로 2개를 고른다. (확률을 반영한다)

 - 이 두개를 섞어서 새로운 state를 만들어낸다. 어떻게 crossover하냐? 두 개의 string에서 crossover point를 랜덤하게 고른다. 그리고 그 point를 기준으로 string을 잘라서 둘이 합친다. 

 - 낮은 확률로 한 자리 골라서 값을 바꿔버리는 mutation, 즉 돌연변이를 일으킨다. 

 

new_population에 빈 set을 집어 넣고 알고리즘이 시작된다.

반복을 총 population의 크기만큼 돌릴 거다.

population 중에서 fitness 함수 값을 반영하여 값을 골라 x와 y에 각각 대입한다. 그리고 x와 y를 reproduce하여 child node를 생성한다. 그리고 낮은 확률로 child에 mutate, 돌연변이를 시켜준다. 그리고 최종적으로 만들어진 child를 new_population에 넣어준다. 그리고 이 과정을 population의 크기만큼 반복하여 new_population을 population의 크기만큼 만들어준 다음에 반복이 끝나면 new_population set들을 population에 대입해준다. 그러면 이제 population이 자손 노드들로 다 바뀌었고, new_population을 empty set으로 초기화 한 후 또 반복한다. 

 

이 과정을 충분히 fit한 individual이 나오거나 시간이 이미 너무 많이 지나버릴 때까지 반복한다. 그리고 반복이 끝나면, population 안에 있는 individual중 가장 fit한 것을 return해준다.

 

 

그렇다면 reproduce는 어떻게 할까?

x와 y를 매개변수로 받았다. n에는 x의 길이를, c에는 1부터 n까지의 랜덤한 숫자를 넣어준다. 

그래서 x에서는 1부터 c까지의 값을, y에서는 c+1부터 n까지의 값을 가져와 합쳐서 return해준다. 

즉 crosspoint가 c인 것!

 

여기서는 공격할 수 없는 pair 의 개수는 fitness function으로 두었다. 즉 두번째 32752411은 1열에는 3행, 2열에는 2행.... 마지막 열에는 1행에 말이 존재하는 것이고, 이 때 fitness function은 전체 경우의 수인 8C2에서 공격할 수 있는 경우의 수인 5를 빼줘야 한다. 그래서 fitness function 값이 23이 된다. 

 

이런 식으로 4가지 경우에 대해 fitness function을 계산하면 선택할 확률도 도출이 된다. (값이 높을 수록 확률도 높아짐) 그 확률을 기반으로 2개의 individual을 선택하고, c의 값을 랜덤으로 골라 string을 합쳐준다. 그리고 보면 변이도 중간중간 일어났음을 볼 수 있다. 

 

 

 - 이 방법은 stochastic beam search처럼 좋은 노드가 선택될 확률이 높지만, 나쁜 노드도 선택될 수 있다. (uphill tendency with random exploration)

 - 그리고 각 parallel search thread간에 정보 교환이 일어나는 것도 동일하다.

 - 하나의 노드가 하나의 다음 노드를 생성하는 stochastic beam search와는 달리, 두 개의 노드를 조합하여 다음 노드를 만들어낸다. 이게 가장 큰!!! 어드벤티지다!!!