인공지능 탐색 알고리즘 4-Local Search

이제부터는 현실적인 문제를 해결하는 알고리즘입니다.

Local Search는 반복적인 개선알고리즘입니다.

탐색경로가 아닌 최적화 문제의 경우 쓰입니다.

우선 한가지 상태를 나열해 놓고 조금씩 수정하면서 최적의 해를 찾는 알고리즘입니다.

예를 들어 A, B, C, D, E 5개의 도시를 한번씩 최단거리로 방문하는 경우를 찾는 예에서

임의로 순서를 정해 놓습니다.

그리고 인접한 도시들의 순서를 바꿔가며 최적의 해를 찾는 방법입니다.

n-queens 문제의 경우에도 쓰입니다.

아래 그래프를 보시면 어떻게 상태를 바꾸느냐에 따라 최적의 해를 풀수도 있지만 정체에 빠지기도 합니다.

1. Hill-climbing Search

Hill-climbing Search는 최적의 해를 찾아 값이 증가하는 방향이나 감소하는 방향으로 계속 이동하는 알고리즘입니다.

8-queens 문제입니다.

왼쪽 그림이 임의로 queen을 배치한 것이고, 숫자는 그 열의 queen을 옮겼을때 공격가능 수를

나타낸 것입니다.

공격가능성이 제일 낮은 곳으로 queen들을 이동한 것이 오른쪽의 그림입니다.

자세히 보시면 문제가 완전히 해결이되지는 않았지만, 더이상 이동을 할 수 없습니다.

이 경우가 위쪽에 나오는 그래프의 local maximum(또는 local minimum)상태입니다.

이런 경우 초기상태를 다시 restart 하여 다시 진행해야 합니다.

실제로 3백만-queens 문제를 1분이내로 해결가능합니다.

Hill-climbing에는 3가지가 있습니다.

Stochastic hill climbing : 위 그래프에서 여러 오르막 방향중 기울기에 비례하는 확률로 선택하는 방법입니다.

First-choice hill climbing : 현재상태보다 나은 것이 발견될 때까지 무작위로 successor들을 생성하는 방법입니다.

Random-restart hill climbing : 초기상태를 무작위로 생성해가며 hill-climbing search를 수행합니다.

2. Simulated Annealing Search

Hill-climbing Search 처럼 최상의 상태로만 이동하는 것이 아닌, 

상태가 개선되는 경우는 무조건 받아들이는 알고리즘입니다.

Best가 아닌 Random을 선택하여, 너무 나쁘지만 않으면 움직임을 허용하여 문제를 해결해 가는 알고리즘입니다.

3. Local Beam Search

초기 하나의 상태가 아닌 k개의 상태를 생성하여 각각의 successor들을 생성합니다.

이중에 최상의 n개의 successor들을 선택하여 목표상태를 찾을때까지 반복하는 알고리즘입니다.

4. Genetic Algorithms

일종의 유전법칙을 이용한 방법입니다.

순서는 아래와 같습니다.

 Chromosome design->initialization->Fitness evaluation

->Selection->Crossover->Mutation->Update generation

Local Beam Search처럼 초기 몇개의 상태를 만듭니다.

1) 먼저 형태(염색체)를 디자인 합니다.

2) 그리고 이걸 기반으로 몇몇개의 초기 상태들을 만듭니다.

3) 그리고 평가를 합니다.

4)임의로 좋은것들을 둘씩 고릅니다.

5)일정 부분을 나누어 두개의 샘플을 합쳐줍니다.

6)임의로 선택하여 염색체의 일부분을 변형시킵니다.

7)진화했습니다.

다시 3)부터 반복하다보면 최적의 상태를 찾게됩니다.

Genetic Algorithms의 경우 시간에 따라 최적의 해를 찾아갑니다.

중간에 멈추어도 이전보다 최적의 값을 찾습니다.