유전 알고리즘-부모 선택
부모 선택은 다음 세대를위한 자손을 만들기 위해 짝짓기하고 재결합 할 부모를 선택하는 과정입니다. 좋은 부모가 개인을 더 나은 솔루션으로 이끌 기 때문에 부모 선택은 GA의 수렴 률에 매우 중요합니다.
그러나 매우 적합한 솔루션 하나가 몇 세대 동안 전체 인구를 차지하지 않도록주의해야합니다. 이로 인해 솔루션 공간에서 솔루션이 서로 가깝게되어 다양성이 손실되기 때문입니다. Maintaining good diversityGA의 성공을 위해서는 인구가 매우 중요합니다. 하나의 매우 적합한 솔루션으로 전체 모집단을 차지하는 것은 다음과 같이 알려져 있습니다.premature convergence GA에서 바람직하지 않은 조건입니다.
피트니스 비례 선택
피트니스 비례 선택은 부모 선택의 가장 인기있는 방법 중 하나입니다. 이것에서 모든 개인은 자신의 적합성에 비례하는 확률로 부모가 될 수 있습니다. 따라서 건강한 개인은 짝짓기하고 자신의 기능을 다음 세대로 전파 할 가능성이 더 높습니다. 따라서 이러한 선택 전략은 인구에서 더 적합한 개인에게 선택 압력을 적용하여 시간이 지남에 따라 더 나은 개인으로 진화합니다.
원형 바퀴를 고려하십시오. 바퀴는n pies, 여기서 n은 모집단의 개인 수입니다. 각 개인은 체력 값에 비례하는 원의 일부를 얻습니다.
피트니스 비례 선택의 두 가지 구현이 가능합니다.
룰렛 휠 선택
룰렛 휠 선택에서 원형 휠은 앞에서 설명한대로 분할됩니다. 그림과 같이 휠 원주에서 고정 점이 선택되고 휠이 회전합니다. 고정 점 앞에 오는 바퀴의 영역이 부모로 선택됩니다. 두 번째 부모의 경우 동일한 프로세스가 반복됩니다.
피터 개인은 바퀴에 더 큰 파이를 가지고 있으므로 바퀴가 회전 할 때 고정 지점 앞에 착륙 할 가능성이 더 큽니다. 따라서 개인을 선택할 확률은 적합성에 직접적으로 달려 있습니다.
구현 현명한, 우리는 다음 단계를 사용합니다-
S = 기교의 합을 계산합니다.
0과 S 사이의 난수를 생성합니다.
인구의 맨 위에서 시작하여 P <S가 될 때까지 부분 합계 P에 벌금을 계속 추가합니다.
P가 S를 초과하는 개인이 선택된 개인입니다.
확률 적 범용 샘플링 (SUS)
Stochastic Universal Sampling은 Roulette wheel 선택과 매우 유사하지만, 다음 이미지와 같이 고정 포인트가 하나만있는 대신 여러 고정 포인트가 있습니다. 따라서 모든 부모는 바퀴를 한 번만 돌리면 선택됩니다. 또한 이러한 설정은 매우 적합한 개인이 적어도 한 번 선택되도록 장려합니다.
피트니스 비례 선택 방법은 피트니스가 음수 값을 취할 수있는 경우에는 작동하지 않습니다.
토너먼트 선택
K-Way 토너먼트 선발에서는 모집단에서 무작위로 K 명의 개인을 선택하고 이들 중 가장 좋은 것을 선택하여 부모가됩니다. 다음 부모를 선택하기 위해 동일한 프로세스가 반복됩니다. 토너먼트 선택은 부정적인 피트니스 값으로도 작동 할 수 있기 때문에 문학에서 매우 인기가 있습니다.
순위 선택
순위 선택은 음의 피트니스 값으로도 작동하며 모집단의 개인이 매우 가까운 피트니스 값을 가질 때 주로 사용됩니다 (일반적으로 실행이 끝날 때 발생 함). 이것은 다음 이미지에 표시된 것처럼 각 개인이 (피트니스 비례 선택의 경우와 같이) 파이의 거의 동일한 몫을 가지므로 서로 상대적으로 얼마나 적합하더라도 각 개인은 a로 선택 될 확률이 거의 같습니다. 부모의. 이것은 결과적으로 건강한 개인에 대한 선택 압력의 손실로 이어지고 GA가 그러한 상황에서 가난한 부모 선택을하도록 만듭니다.
여기에서 우리는 부모를 선택하면서 피트니스 가치의 개념을 제거합니다. 그러나 인구의 모든 개인은 체력에 따라 순위가 매겨집니다. 부모의 선택은 적합성이 아니라 각 개인의 순위에 따라 다릅니다. 높은 순위의 개인이 낮은 순위의 개인보다 더 선호됩니다.
염색체 | 피트니스 가치 | 계급 |
---|---|---|
ㅏ | 8.1 | 1 |
비 | 8.0 | 4 |
씨 | 8.05 | 2 |
디 | 7.95 | 6 |
이자형 | 8.02 | 삼 |
에프 | 7.99 | 5 |
무작위 선택
이 전략에서 우리는 기존 모집단에서 무작위로 부모를 선택합니다. 더 건강한 개인에 대한 선택 압력이 없으므로이 전략은 일반적으로 피합니다.