유전자 알고리즘 소개

 

최적화 문제를 풀 때 서칭 공간을 탐색하는 방식으로 해를 찾는다.

 

기존의 서칭 공간 탐색 방식 특징: 

1) 보조 지식을 활용한다. 예) 그래디언트 디센트

2) local 해에 빠지게 된다. (local 해 vs. global 해) 

3) population 단위로 서칭 (탐색점이 여러개이다.) 대신 보조지식 활용 X

 

Genetic Algorithm  탐색 방식 특징:

1) 탐색에 관련된 보조 지식을 활용하지 않는다.

2) 역시나 local해에 빠진다. 그래서 적당히 좋은 해만 찾으면 충분한 경우에 사용이 적합하다. 

(서칭 알고리즘에 여러가지 있지만 GA와 대조되는 알고리즘 위주로 설명)

 

Q. Gradient Descent는 추가(방향, 크기)적인 정보로 iteratively하게 스텝마다 더 좋은 솔루션을 찾아나간다.

그러면 Geneic Algorithm은 알고리즘적으로 더 좋은 방향으로 찾아나간다라는 보장을 어떻게 할 수 있을까? 다른 방향으로 샐 수도 있지 않을까?

 

A. 더 좋은 방향으로 굉장히 느린 속도로 해를 찾아갈 수 있고, 더이상 개선되지 않을 수도 있다.  각 문제 도메인에 맞게 Genetic Algorithm을 수정해주어야 한다. (Q. 어떤부분을?)

 

GA언제 유용?
- 적당히 좋은 해면 충분한 경우
- 문제를 해결하는 방법을 아무도 모를 때

GA
- 샘플링기반 서칭