Selection Options

Parent Selection은 다음 세대를 위한 자손(off-springs)을 만들기 위해 교미하고 재결합하는 부모를 선택하는 과정입니다. 좋은 부모가 개인을보다 훌륭하고 훌륭한 해결책으로 유도 할 때 학부모 선발은 GA의 수렴 속도에 매우 중요합니다.

https://slidetodoc.com/optimization-techniques-genetic-algorithms-and-other-approaches-for/

 

인구의 다양성(즉 refrence points가 여러 곳) 을 유지하는 것은 GA의 성공을 위해 매우 중요합니다. 매우 적합한 솔루션으로 전체 인구를 감당하는 것은 조기 컨버전스로 알려져 있으며 GA에서 바람직하지 않은 조건입니다.

 

Fitness Proportionate Selection (Fitness 비율 기반 선택)

메인아이디어 

- 개인은 적합성에 비례하는 확률로 부모가 될 수 있다.

- 적합 점수가 높을 수록 개인은 다음 세대로 그들의 특징을 교배하고 전파 할 기회가 더 많다.

- 따라서 그러한 선택 전략은 인구에 맞는 개인에게 선택 압력을 적용하여 시간이 지남에 따라 더 나은 개인을 발전시킨다.

 

파이를 어떻게 분할할지,

고정점을 몇개로 할지

 

 

Roulette Wheel Selection

원형 휠은 chromsome 개의 파이로 나뉜다.

그림과 같이 휠에서 고정 점이 선택되고 휠이 회전된다.

고정 점 앞에 오는 휠의 영역이 부모로 선택됩니다.

두 번째 부모에게는 동일한 과정이 반복됩니다.

(Q. 부모를 두 명 선택하는 이유는? -일부 다처제면 안되나?)

회전 할 때 휠체어에 더 큰 파이가있어서 고정 점 앞에 착륙 할 확률이 높아집니다. 따라서 개인을 선택할 확률은 적합성에 직접적으로 달려 있습니다.

Stochastic Universal Sampling

 

룰렛 휠선택과 차이점: 고정 점이 하나가 아니라 여러 개.

 

Tournament Selection

K-Way 토너먼트 선택에서 우리는 무작위로 K 명의 개인을 선택하고 이들 중 최고를 선택하여 부모가됩니다. 동일한 프로세스가 두 번째 부모를 선택하기 위해 반복됩니다.

 

Rank Selection

 

 

랜덤이 아닌 그냥 랭크기반으로 1위2위 선택?

Scaling 왜 하는지?

우성인자 열성인자 fitness 값이 차이가 나면, 계속해서 우성인자가 선택에서 압도적으로 살아남게 됨. 그러면 다양한 지역탐색 X. (선결지식: 꼭 처음에 population은 refrence point가 여러 군데인 점을 설명해야함)

 

Q. Scaling이후에 룰렛 휠을 적용가능?

 

정착 대신 탐험을 많이하는 전략

Often the objective scores must be transformed in order to help the genetic algorithm maintain diversity or differentiate between very similar individuals. The transformation from raw objective scores to scaled fitness scores is called scaling.

 

There are many different scaling algorithms. Some of the most common are linear (fitness proportionate) scaling, sigma truncation scaling, and sharing. Linear scaling transforms the objective score based on a linear relationship using the maximum and minimum scores in the population as the transformation metric. Sigma truncation scaling uses the population's standard deviation to do a similar transformation, but it truncates to zero the poor performers. Sharing derates the score of individuals that are similar to other individuals in the population.

For a complete description of each of these methods, see Goldberg's book.