Step 3: Reproduction & Step 4: Generating Offspring

앞서 reproduce(번식)할 parents를 선택하였다.

이번 섹션에서는 어떻게 reproduce하는지 알아보자.

reproduction은 크게 cross over, mutation 두 단계로 이루어졌다.

 

 

1) Cross Over opeartion

 

- single point corssover : 임의로 점 한 군데 선정해서 좌, 우 crossover 

- double point : 임의로 점 두 군대 선정. 

 

그냥 무작정 아무 개체나 crossover하지 않고 확률을 기반으로 crossover를 할 수 있다.

확률 threshold를 crossover probability (rate)라고 한다. 

2) Mutation

- Q. Crossover vs. Mutation 차이가 무엇인지?

 local search vs. global serach

- 어떻게 mutation이 수행되는지? 그냥 부모의 임의의 bit하나 잡아서 바꿔줌. 

 

 

Mutation도 모든 bit가 수행하는 것이 아니라, 임의의 bit를 확률적으로 선택해서 수행한다.

mutation probabbility (rate)가 그 확률적 선택 기준 thrshold 역할 한다.

 

그래서 mutation probability, cross over probability를 알고리즘 디자이너가 잘 경험을 토대로 결정해주어야 한다.

혹은, Hill climbing, Simulated Annealing 같은 방법을 적용해서 adaptive하게 순간순간 가변적으로 결정할 수 도 있다.

 

Reproduction 연산을 통해서  생성해낸 offspring 중에서 fitness value가 높은 우성인자만 생존시키고, 그렇지 않은 열성인자는 도태시킨다.

 

잠깐, 

근데 왜 세대마다 population의 사이즈는 동일할까? 가변적으로 할 수 없을까?

크면, 작으면 어떤 효과가 있을까?  파라미터 관련해서는 나중에 살펴보겠다.

 

그래서 이게 알고리즘의 전체 슈도 코드가 된다. 

 

 

Stopping Criteria

https://slidetodoc.com/genetic-algorithms-genetic-algorithms-l-components-of-a/