Genetic Algorithm

문제 풀이 난이도 :

optimize 루트를 계산하는 시간이 오래 걸릴수록 + optimize 하다는 확신이 없을수록 어려운 문제이다.

 

(1) Traveling salesman problem

TSP 의 해결 시간은.... O(N!) complexity

 

(2) Search space and global optimum

binary search tree 는 이미 최적의 경로가 define 되어 있다.

반면 path가 정의되어 있지 않은 거대한 N 사이즈의 데이터에서 global optimum 을 찾아야 한다면 최적의 경로를 확신할 수 없고, 도달한 곳이 Local optimum 일수도 있어 어려운 문제가 될 것이다.

 

이때 필요한 것이 Heuristic!

 

Heuristic

Algorithm : 구조나 규칙이 있어 해를 찾을 수 있다는 보장이 있음.

Heuristic : 경험해가며 해를 찾아가는 것. 해를 찾을 수 있다는 보장은 없음.

 

(2) 에서 말한 Search space and global optimum 을 heuristic으로 풀 수 있다. 

"Hill-climbing heuristics" or "gradient-ascent heuristics"라고 부르는데, 문제는...

Local optimum에 빠질 수 있다!!

 

그럼 어떤 heuristic 기법을 써야 할까..?

Genetic Algorithm!

 

Genetic Algorithm

알고리즘이라고는 하나 heuristic 기법임

예시) Search space and global optimum을 한다고 할 때,

(1) Gene : 유전자 조각. genotype 을 구성하는 원소 하나

ex) 10.7, 12.3

(2) Genotype : 유전자 특성.

ex) 위치: (10.7,12.3)

(3) Phenotype : genotype으로 인해 발현된 결과!

ex) 고도: 30 m

그래서 최적의 phenotype : Optimal value이고, 최적의 genotype은 Optimal solution이 된다.

 

 

Terminology of genetic algorithm

 

A problem to solve	GA로 풀어야 할 문제	Traveling Salesman Problem
Gene	솔루션의 요소	Seoul or Kwangju or Daejeon...
Genotype	솔루션	[Seoul,Kwangju, Daejeon...]
Encoding	솔루션 표기 규칙	[1,2,3...] assuming Seoul is 1 ...
Phenotype	솔루션의 가치	Trip Cost of {Genotype}
Population	솔루션들의 모음 ( N!개 )	[Seoul, Kwangju, Daejeon...], [Kwangju, Seoul, Daejeon...],[Seoul,Daejeon, Kwangju ...]
Initialization	처음에 몇 개의 solutions (sub-population) 중에서 비교해서 더 좋은 solution을 찾을지 정해놓는 과정
Selection	sub-population 중에서 적자를 찾아내는 과정	top k minimum solution을 찾아내겠다
Offspring production	selection 으로 찾아낸 solution을 섞어 새로운 solution인 derived solution을 만든다
Environment	solution에 대한 evaluation!

 

Structure of Genetic Algorithm

(1) Initial sub- population set

(2) 진화의 루프: 진화 단계 수는 적절히 선택한다!

(3) 자손해를 만든다: 자손해는 한 번에 몇 명이나 만들지 수 선택

자손이 많이 생기면 다양한 경험 가능. 수렴 느림

자손이 적으면  빨리 수렴할 수 있다.

-> 처음엔 자손 많이 만들고 어느정도 안정 되면 그때부터 적게 만들어야 함.

(4)selection -> crossover -> muattion

(5) 그렇게 만들어진 자손을 기존의 populatio에 대체!

(6) 가장 적절한 solution을 찾아낸다!

 

 

Encoding

문제를 풀기 위해 표현하는 것.

(1) K-ary coding : [0,1,2]

일반적인 표현법

 

(2) binary coding : [00 01 10 ]

mutation crossover 할 때 0,1 만 있기 때문에 더 쉽게 바꿀 수 있음 ( 속도 빠름)

 

(3) adaptation to the problem :

 [0] 서울 시작, [1] 광주시작 , [2] 대전시작  일 때, [1,2,0]  ==> which means ::: [서울->광주 , 광주->대전, 대전->서울 ]

 

(1)과 (3) 의 차이점:

(3)을 사용하면 vaild 여부를 더 빨리 확인할 수 있음 (ex. (3)번 encoding에서 [0,1,2]는 (서울->서울은 낭비!) invaild하다!) -> solution 후보를 줄여준다. -> 더 빨리 optimum 탐색이 가능함!

 

Selection step

Global optimum을 찾기 위해서는 당장의 optimum way만 봐선 global optimum으로 가지 못할 수도 있음.

따라서 안좋은 solution도 어느정도 수용해가며 selection해야 함.

(1)Roulette wheel based

그림넣기

 

K 가 작을수록 worst 에서도 선택될 확률 커짐! 전체 portion이 비슷해짐.

K 가 클수록 worst 에서 선택될 확률은 작아짐.

 

 

Crossover step

부모 genes를 서로 바꿔 새로운 자손을 만드는 것!

그런데 crossover 하면 invalid 한 solution이 나오는 경우가 있다.

이를 해결하기 위해 (1) 마지막에 수정하거나, (2) 조심스럽게 crossover 하게 된다.

 

Mutation step

random and swap!

대부분 안좋은 solution이 만들어지지만 가끔 아주 좋은 solution이 만들어지기도 함!

(1) Random mutation

임의로 하나의 gene을 골라서 gene의 범주 내에서 랜덤하게 다른 gene으로 덮어쓴다.

 

(2) Swap mutation

두개의 gene을 골라서 서로 위치를 바꾼다.

 

마지막 step! invalid solution이 만들어지지 않음!

 

 

Substitution step

새로 만들어진 솔루션을 population에 넣어주는 과정

N =size of population

K = size of offspring

 

(1) Generational GA : 기존의 population을 대부분 offspring으로 대체함

K/N -> 1

(2) Steady-state GA : 기존의 lpopulation중에서 조금만 offspring 으로 대체함

K/N -> 1/N

 

population 중에서 누구를 replace?

-Inferior solution? 빠르게 convergence 하겠지만 다양성이 적어짐.

-Parent? 좋은 성능의 해를 버리게 됨. convergence 는 느리지만 다양성은 많아짐.

 

Heuristic 이므로 우리가 정해야 하는 parameter가 많다!

(1) number of iterations

(2) size of population : 크면) 다양성, 느림 작으면) 빠름

(3) initial population 방법