[인공지능 : AI, Artificial Intelligence] Lecture 8 : Local Search

Lecture 8

Local Search 다시 보기

매우 큰 state space -> exhausive는 불가능하다.
그래서 일부, 즉 Local만 Search를 해본다.

Local Beam Search

정해진 시간동안 search를 해서 각자 다른 local maxima를 찾았다고 해보자.
이걸 전부 모아서 best인 k개를 솎아내서 tracking한다(이걸 교수님은 '협력했다, 정보가 각 k search에서 서로 공유되었다'고 하더라..).
중요한 점은 k개의 successor가 good ones에 bias되게 만든다는 점이다.

diversity가 부족할 수 있다.
이를 위해서 Stochastic beam search : state quality에 비례한 확률로 k successors를 선정하는 방식을 택할 수도 있다.

Local Beam Search와 Hill Climbing의 비교

• random k restart를 한다는 점까지는 같다.
• useful information이 각 search thread에 공유된다.
  • 그 결과 semi optimal solution을 얻는다.
• 소득없는 search를 빠르게 중단한다.
• 하지만, 모든 k state가 작은 지역에 집중되어있을 수 있다. 이 경우, stochastic local beam search를 통해서 k successors를 선택해 문제를 해결할 수 있다.

그 k개에서 또 search를하고, 거기서 또 k개를 고른다!

형광표시는 경로가 진행된 것을 의미한다.

Local Beam Search 알고리즘은 워크북에서 확인한다.

Genetic Algorithm

Local Beam Search 기반의 알고리즘.
Genetic Algorithm을 정의하려면 다음과 같은 것을 정해야한다.

1. fitness function(적합도. 환경에 대한 적합도.)
2. state
3. generation shitf strategy를 정의
   • crossover, mutation, selection(누구를 crossover 시킬것인가)

순서는 다음과 같다.

1. k개의 랜덤 generated state로 시작한다.
   • 이를 population이라하고, 각 state를 individual이라고 한다.
   • 각 individual은 0과 1의 string으로 구성(더 큰 정수로 표현할 수도 있다.)
   • obj function = fitness function : 좋은 state일 수록 high
2. selection을 거친다.
3. crossover한다. (짝을 짓고 교배) : individual이 2배가 된다.
4. mutation을 한다. (돌연변이)
5. 다음 세대 완성! 2번부터 반복

selection 방법 : 누구를 crossover 시킬 것인가?에 대한 방법이다.

1. elite 방법
2. stochastic
3. crossover를 여러번 가능

• Search space
  • 각 individual, 즉, candidate solution의 집합
• Fitness landscape(Fitness function)
  • j bit로 구성된 chromosome을 이용해서 정의한 obj function, 높을수록 좋도록 설계한다.
  • j+1 차원으로 plot이 가능하다. j개의 차원의 입력이 j+1의 출력으로 나오는 방식.
  • crossover와 mutation은 이 landscape를 따라서 population을 이동시키는 것이다.
  • adaption은 local peak로 이동하는 것이다.
• Selection : fitness에 따라서 chromosomes를 선택한다.
  • fitness proportionate, tournament 두가지 방법이 있다.
  • stochastic 혹은 Elite한 방법도 있다.
• Crossover
  • 각 individual의 chromosome을 절반씩(조정 가능) 섞는다.
  • 두 개의 offspring이 만들어진다.
  • 11000001과 00011111은 4번째를 기준으로 crossover를 하면, 11001111과 00010001을 만든다.
  • 서로 정보를 교환한다는 것이 중요한 부분
• Mutation
  • chromosome bit를 약간 마음대로 변경(flip)한다.
  • 11000001을 10000001로 바꾸는 등

Genetic Algorithm의 전체적인 과정

1. Fitness를 구하고, 이를 기반으로 selection을 진행한다.
2. selection된 것을 기반으로 crossover를 한다.
3. 낮은 확률로 mutation을 한다.

위의 그림처럼, selection의 stochastic함을 Fitness값의 비율로 정할 수도 있다.

알고리즘은 다음과 같다.

예시

8 queens에서는 이렇게 표현할 수 있을 것이다.

fitness function을 number of non attacking pairs of queens로 둔다. solution을 구했다면 28이 나온다고 한다.

이 경우 crossover는 다음과 같이 처리될 것이다.

예시 2

hyperparameter를 다음과 같이 설정한다.

초기 generation의 population은 다음과 같다.
fitness는 1의 개수.

아래는 fitness proportionate selection을 사용한다.
selection의 회수가 fitness를 평균 fitness 값으로 나눈 값이다.

여기서 룰렛을 만든다는 느낌으로, 비율을 각자 정해서 랜덤하게 selection을 한다.

확률 $p_c$를 기반으로 first locus뒤에서 crossover를 할 위치를 선정한다.
crossover를 한다.
crossover가 안된다면 그대로 copy 2개를 만든다.

그 후, 각 locus에 대해서 확률 $p_m$로 mutation을 한다.

그 결과, 새로운 population이 만들어진다.

플로우차트는 다음과 같다.

이후는 참고

simple genetic algorithm

• n개의 j bit chromosome을 생성한다.
• 각 chromosome의 fitness를 측정한다.
• 다음 과정을 n개의 offspring이 만들어질 때까지 반복한다. (population을 2배로):
  • fitness를 기반으로 두가지 chromosome을 Selection을 한다.
  • crossover rate $p_c$를 기반으로, crossover를 한다. 두개의 offspring을 만든다. crossover가 없다면 두 개의 offspring은 두 parent를 그대로 복사한 것이다.
  • mutation rate $p_m$를 기반으로, 각 locus에 mutation 확률을 가해서 mutation을 시도하고, 그 chromosome을 population에서 대체한다.
• 여기서, n이 홀수라면, 하나의 individual을 랜덤하게 삭제한다.
• 현대의 population을 새로운 population으로 교체한다.
• Go to step 2.

각 iteration을 generation이라고한다.
보통 하나의 GA에서 50 ~ 500 정도의 generation을 거친다.
각 run은 랜덤함에 영향을 크게 받기 때문에, 각 실행마다 그 결과가 다르며, 각 실행의 결과물의 fitness가 다르다.

Continuous State Space

Discretization 되어있다면

• hill climbing 기반 방법을 사용

Continuous 하다면

• Gradient Descent를 사용
• x := x - lr * grad(f by x)
• lr는 낮게 시작해서 f가 상승할 때까지 증가시킨다.