선택(유전자 알고리즘)

다음 시리즈의 일부
진화 알고리즘
인공발달성 인공생명체 세포진화 알고리즘 문화 알고리즘 미분진화 효과적인 피트니스 진화 연산 진화전략 가우스 적응 진화적 다중모드 최적화 입자 군집 최적화 메미틱 알고리즘 자연 진화 전략 신경진화 프로모터 기반 유전 알고리즘 나선 최적화 알고리즘 자체수정코드 다형 코드
유전 알고리즘
염색체 클론 선택 알고리즘 크로스오버 돌연변이 유전적 기억력 유전 퍼지 시스템 선택 플라이 알고리즘
유전자 프로그래밍
데카르트 유전 프로그래밍 선형유전자프로그래밍 문법적 진화 다중 표현식 프로그래밍 유전적 개선 스키마 유리스코 패리티 벤치마크
v t

선택이란 개체군 중에서 개별 게놈을 선택해서 나중에 번식을 하는 유전자 알고리즘의 단계다(크로스오버 연산자 사용).

일반적 선택 절차는 다음과 같이 시행할 수 있다.

1. 피트니스 기능은 각 개인에 대해 평가되어 피트니스 가치를 제공하며, 그 후 정상화된다. 정상화는 각 개인의 건강 가치를 모든 건강 가치의 합으로 나누는 것을 의미하며, 결과적인 건강 가치의 합이 1이 되도록 한다.
2. 누적된 정규화된 체력 값은 계산된다. 개인의 누적 체력 값은 자신의 체력 가치와 이전 모든 개인의 체력 가치를 합한 값이다. 마지막 개인의 누적 체력 값은 1이어야 한다. 그렇지 않으면 표준화 단계에서 무언가 잘못되었다.
3. 0과 1 사이의 임의의 숫자 R을 선택한다.
4. 선택한 개인은 누적 정규화 값이 R보다 크거나 같은 첫 번째 개인이다.

많은 문제에서 위의 알고리즘은 계산적으로 요구될 수 있다. 더 간단하고 빠른 대안은 소위 확률적 수용을 사용한다.

만약 이 절차를 선택한 사람이 충분히 있을 때까지 반복한다면, 이 선택 방법을 피트니스 비례 선택 또는 룰렛 휠 선택이라고 한다. 한 개의 포인터가 여러 번 회전하는 대신, 한 번 회전하는 바퀴에 동일한 간격으로 여러 개의 포인터가 있다면, 그것은 확률적 유니버설 샘플링이라고 불린다. 무작위로 선택한 서브셋 중 최고의 개인을 반복적으로 선택하는 것은 토너먼트 선택이다. 개인 중 가장 좋은 절반, 세 번째 또는 다른 비율을 차지하는 것은 잘림 선택이다.

모든 개인을 선택 대상으로 고려하지 않고 주어진 (임의) 상수보다 더 높은 피트니스 가치를 가진 사람만 선택하는 선택 알고리즘이 있다. 다른 알고리즘은 개인의 특정 비율만 허용되는 제한된 풀에서 피트니스 값에 기초하여 선택한다.

다음 세대에도 변하지 않는 한 세대의 최고의 개인을 유지하는 것을 엘리트주의 또는 엘리트주의 선택이라고 한다. 그것은 새로운 인구를 건설하는 일반적인 과정의 성공적인 변종이다.

선택 방법(유전자 알고리즘)

룰렛 휠 선택

룰렛 휠 선택에서, 다음 세대의 번식을 위해 개인을 선택할 확률은 그 적합성에 비례하고, 적합성이 높을수록 그 개인을 선택할 확률은 높아진다. 개인을 선택하는 것은 현 세대의 개인들만큼 주머니가 많은 룰렛을 회전시키는 것으로 묘사할 수 있으며, 그 확률에 따라 크기가 달라진다. Probability of choosing individual ${\displaystyle i}$ is equal to ${\displaystyle p_{i}={\frac {f_{i}}{\Sigma _{j=1}^{N}f_{j}}}}$, where ${\displaystyle f_{i}}$ is the fitness of ${\displaystyle i}$ and ${\displaystyle N}$ is the size of current generation (이 방법에서 한 개인을 여러 번 그릴 수 있다는 점에 유의하십시오.)

순위 선택

순위 선택도 음의 피트니스 값으로 작동하며 모집단의 개인이 매우 가까운 피트니스 값을 가질 때 주로 사용된다(이는 대개 실행이 끝날 때 발생한다). 이것은 각 개인이 거의 동일한 파이를 갖게 하고(예: 피트니스 비례 선택의 경우) 따라서 각 개인은 아무리 서로 상대적인 적합성이 있더라도 거의 동일한 부모로 선택될 확률을 갖게 한다. 이는 결과적으로 더 건강한 개인에 대한 선택 압력의 상실로 이어져 GA가 그러한 상황에서 부모 선택을 제대로 하지 못하게 한다.

안정화 상태 선택

모든 세대에서 새로운 자손의 생성을 위해 선택된 염색체는 거의 없다. 그런 다음 일부(체력이 낮은 나쁜) 염색체를 제거하고 새로운 자손이 그 자리에 배치된다. 나머지 인구는 신세대까지 살아남는다.

토너먼트 선택

토너먼트 셀렉션은 개인 세트 중에서 개인을 선택하는 방식이다. 각 토너먼트 우승자를 선정하여 크로스오버를 실시한다.

엘리트주의 선택

종종 더 나은 매개변수를 얻기 위해 부분적 재현을 가진 전략이 사용된다. 그 중 하나가 엘리트주의인데, 마지막 세대의 가장 우수한 개인들 중 작은 부분이 다음 세대로 넘어가는 것이다.

볼츠만 선택

볼츠만 선택에서 지속적으로 변화하는 온도는 사전 설정된 일정에 따른 선택 속도를 제어한다. 온도가 높게 출발하기 때문에 선택 압력이 낮다는 뜻이다. 온도가 점차 낮아져 선택 압력이 점차 증가하므로 적절한 다양성을 유지하면서 GA가 검색 공간의 가장 좋은 부분까지 더욱 가깝게 좁혀질 수 있다.^[1]

참고 항목

• 체력비례선택
• 토너먼트 선택
• 확률적 유니버설 샘플링
• 포상기준선정
• 잘라내기 선택

참조

외부 링크

• 유전 알고리즘 소개
• 확률적 수용성 버전의 구현 개요