Simulated Annealing, Local Beam Search, Stochastic Beam Search, Genetic Algorithms

- Hill-climbing search 는 landscape 에 따라 Incomplete 하다. -> greedy

- Random walk 는 더 좋은 곳이 아니라 무작위로 이동을 한다. 그러나 landscape 를 거의 무한으로 이동해야 solution 을 찾을 수 있으므로 매우 비효율적이다.

- Annealing 은 금속을 뜨겁게 가열한 다음에 천천히 식히는 과정을 말한다. 이는 금속을 부드럽게 하기 위해 사용된다.

 

 

Simulated Annealing

t = 1부터 무한까지 반복문을 도는데,

T <- schedule(t) 에서 인자로 받는 t는 반복문의 인덱스를 의미하고, T는 temperature 온도의 약자이다.

즉, t를 인자로 받아서 그에 대응하는 온도를 리턴해주는 것이 schedule 이다.

이때 온도가 0이 되는 경우 loop 를 빠져나간다.

T는 높다가 loop 를 돌 수록 낮아진다.

 

next 는 current 의 successor 중 무작위로 선택된 것이다.

델타 E는 next.VALUE - current.VALUE 의 값으로, next 와 current 를 비교하는 값이 된다.

만약 델타 E가 0보다 좋은 경우 (이 알고리즘의 경우 값이 클 수록 좋은 것 -> next가 더 좋은 경우), next 로 이동한다.

그러나 next 가 current 보다 좋지 않은 경우, 확률적으로 next 로 이동한다.

 

확률은 e^(델타E / T) 가 되는데, 초반에 T가 클 때에는 델타E/T 가 0 에 가까워서 확률은 1에 가깝게 된다. 

따라서 높은 확률로 next 로 움직이게 된다.

반면, loop 를 돌 수록 T가 작아지는데, 이때는 델타 E / t 가 커지므로 확률은 0에 가깝게 된다. 이때는 random 에 의해 움직이기 보단 hill-climbing 에 가깝게 움직이게 된다.

 

 

Local Beam Search

- local search 는 path 를 기억하고 있을 필요가 없는데, Local Beam 에서는 하나의 state 만 알고 있기 보단 set of node 를 유지한다.

- initial state 를 k만큼 랜덤하게 생성하고, current state 를 k개 설정한다.

- loop 를 도는데, 각 current 에서 k개의 successor 를 설정하고, 또 반복해서 successor 를 설정하는 방식이다.

random-restart hill-climbing search 와 다른점은 random-restart 에서는 hill climbing 을 k번 반복하고, k개의 solution 중에 가장 좋은 것을 택하는 방식이다. 그러나 Local Beam 에서는 한 번의 반복문을 돌 때마다 sucessor 가 없는 state 를 제거할 수 있다. 둘 중 어느것이 더 낫다고 말할 순 없다. 상황에 따라 쓰임새가 다르기 때문이다.

 

 

Stochastic Beam Search

local beam search 를 변형한 것으로, successor 들 중 확률적으로 k개의 successor 을 선택하는 방법이다.

 

 

Genetic Algorithms (유전 알고리즘)

stochastic beam search 를 변형한 알고리즘이다.

stochastic beam 에서는 current 에서 갈 수 있는 single action 에 의해 successor 들이 만들어졌다.

그러나, 유전 알고리즘에서는 두 개의 state 를 결합하여 successor 를 생성하게 된다.

- k개의 state 를 무작위로 만들어서 시작한다. -> Population(집단)

- 각 state (individual - 개체) 은 string(문자열) 로 표현이 된다.

 

- 8-queen 문제에서의 예제

initial population 은 문자열로 구성이 되어있는데, 각 state는 열에서 queen 의 위치를 의미한다.

Fitness function 은 heuristic 과 반대되는데, 서로 공격을 하지 못하는 queen 쌍의 개수를 의미한다. 따라서 goal state 는 28이 된다.

각 Initial Population 에 대한 Fitness function 으로, 각 집단을 고를 확률을 계산한다.

그리고, 확률에 의해 Parent 가 될 집단이 선택된다. 이때 중복되어 선택될 수도 있다.

Parent 두 쌍을 점선에 따라 Crossover 하여 Offsprint (자손)을 생성한다. 이때 crossover 가 일어나는 위치는 무작위로 결정된다.

또한, 생성된 Offspring 에 무작위 확률로 Mutation 이 일어나게 된다.

 

 

 

-지금까지의 알고리즘에서는 successor 를 생성할 때 current state 에서 action 을 하나만 취하였는데,

genetic 알고리즘에서는 여러 action 을 결합한다. -> Crossover

- 8-queen 문제에서 state 는 '16257483' 과 같은 문자열로 표현이 되었다. 이는 bit string 으로 나타낸다면 24 bit 를 필요로 하게 된다. 이때는 3자리씩 건너서 crossover 을 실행하는 것을 고려해야 한다.