체력비례선택

룰렛 휠 선택이라고도 알려진 피트니스 비례 선택은 재조합을 위해 잠재적으로 유용한 해결책을 선택하기 위해 유전 알고리즘에 사용되는 유전적 연산자다.

피트니스 비례 선택에서, 모든 선택 방법에서와 같이, 피트니스 함수는 가능한 해결책이나 염색체에 적합성을 할당한다.이 피트니스 수준은 선택 확률을 각 개별 염색체와 연관시키기 위해 사용된다.$f{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$가 모집단에서 개별 $i{\displaystyle }$ ${\displaystyle i}$의 적합성인 경우, 선택될 확률은 다음과 같다.

${\displaystyle p_{i}={\frac {f_{i}}{\Sigma _{j=1}^{N}f_{j}}}},$

여기서 $N{\displaystyle }$ ${\displaystyle N}$은 모집단의 개인 수입니다.

이것은 카지노의 룰렛 휠과 비슷한 상상을 할 수 있었다.일반적으로 휠의 비율은 피트니스 값에 기초하여 가능한 각 선택 항목에 할당된다.이는 선택 항목의 적합성을 모든 선택 항목의 전체 적합성으로 나눈 다음 1로 정상화함으로써 달성될 수 있다.그런 다음 룰렛 휠이 회전하는 방법과 비슷하게 무작위로 선택한다.

적합성이 높은 후보 솔루션은 탈락 가능성은 적겠지만 선택 확률은 1(또는 100%) 미만이기 때문에 탈락할 가능성도 여전히 있다.이를 가장 약한 후보의 고정 비율을 제거하는 잘림 선택과 같은 덜 정교한 선택 알고리즘과 대조하십시오.피트니스 비례 선택으로 일부 약한 해결책이 선택 과정에서 살아남을 가능성이 있다.이것은 약한 해결책이 살아남을 확률은 낮지만, 0이 아니라는 것은 그것이 생존할 가능성이 있다는 것을 의미하기 때문이다; 이것은 약한 해결책이라도 재조합 과정 후에 유용하다고 증명될 수 있는 몇몇 특징이나 특성을 가질 가능성이 있기 때문에 장점이다.

룰렛 휠에 대한 유사점은 각 후보 솔루션이 바퀴 위의 포켓을 나타내는 룰렛 휠을 상상함으로써 예측할 수 있다; 포켓의 크기는 솔루션 선택 확률에 비례한다.^{[citation needed]}모집단에서 N개 염색체를 선택하는 것은 각 후보가 독자적으로 그려지기 때문에 룰렛 휠에서 N개 게임을 하는 것과 같다.

확률적인 유니버설 샘플링이나^[1] 토너먼트 선택과 같은 다른 선택 기법이 종종 연습에 사용된다.확률적 소음이 적거나 빠르고 구현이 용이하며 선택 압력이 일정하기 때문이다.^[2]

순진한 실행은 우선 개인의 적합성에 비례하는 확률을 이용하여 개인의 리스트에 걸쳐 누적 확률분포(CDF)를 발생시킴으로써 이루어진다.[0,1) 범위의 균일한 무작위 숫자를 선택하고 그 숫자에 대한 CDF의 역수는 개인에게 주어진다.이것은 너비에 비례하는 확률로 개인의 빈에 떨어지는 룰렛 공에 해당한다.균일한 난수의 역에 해당하는 "bin"은 CDF의 요소들을 통한 이진 검색을 사용하면 가장 빨리 찾을 수 있다.개인을 선택하는 데는 O(log n) 시간이 걸린다.O(1) 시간 내에 개인을 생성하는 더 빠른 대안은 가명법을 사용하는 것이다.

최근에는 「스토크리스틱 수용」을 기본으로 하는 매우 간단한 알고리즘이 도입되었다.^[3]알고리즘은 임의로 개인(say $i{\displaystyle }$ ${\displaystyle$ i$\})$을 선택하고 확률 f ${\displaystyle i_{}{f}_{}}$ M ${\$을(를) 사용하여 선택을 허용하며$,$ 여기서 ${\displaystyle f_{}}$ ${\$은 모집단의 최대 적합성이다$$.특정 분석은 특히 실행 중에 피트니스 값이 변경될 수 있는 애플리케이션에서 확률적 허용 버전이 선형 또는 이진 검색에 기반한 버전보다 상당히 더 나은 성능을 가지고 있음을 나타낸다.^[4]이 알고리즘의 동작은 일반적으로 빠르지만, 일부 피트니스 분포(예: 지수 분포)는 $최악$의 경우 O${\displaystyle }$( ${\displaystyle n}$) ${\displaystyle O(n)}$번 반복이$$ 필요할 수 있다.또한 이 알고리즘은 2진수 검색보다 더 많은 임의의 숫자를 요구한다.

가성음

예를 들어, [1, 2, 3, 4]의 피트니스를 가진 모집단이 있는 경우, 합계는 (1 + 2 + 3 + 4 = 10)이다.따라서 확률이나 확률은 [1/10, 2/10, 3/10, 4/10] 또는 [0.1, 0.2, 0.3, 0.4]가 될 것이다.0.0과 1.0 사이에서 이 문제를 시각적으로 정규화하려면 다음과 같이 [빨간색 = 1/10, 녹색 = 2/10, 파란색 = 3/10, 검은색 = 4/10]으로 그룹화하십시오.

0.1 ] 0.2 \ 0.3 / 0.4 \ 0.5   0.6 / 0.7 \ 0.8   0.9   1.0 / 

위의 예제 숫자를 사용하여 확률을 결정하는 방법:

sum_of_fitness = 10 previous_probability = 0.0  [1] = previous_probability + (fitness / sum_of_fitness) = 0.0 + (1 / 10) = 0.1 previous_probability = 0.1  [2] = previous_probability + (fitness / sum_of_fitness) = 0.1 + (2 / 10) = 0.3 previous_probability = 0.3  [3] = previous_probability + (fitness / sum_of_fitness) = 0.3 + (3 / 10) = 0.6 previous_확률 = 0.6 [4] = 이전_sum + (sum_of_sum) = 0.6 + (4 / 10) = 1.0

마지막 지수는 항상 1.0이거나 그것에 근접해야 한다.그런 다음 개인을 임의로 선택하는 방법이다.

random_number # random_number < 0.1>인 경우 0.0에서 1.0 사이, 1.0에서 1.0 사이, 0.3 - 0.1 = 0.2 확률인 경우 1을 선택하고, 0.6 - 0.3 = 0.3 확률인 경우 2를 선택하고, random_number < 0.0 - 0.6 = 0.3 확률인 경우 3을 선택하고, random_number < 1.0 - 0.6 = 0.4 확률인 경우 4를 선택한다.

참고 항목

• 포상기준선정
• 확률적 유니버설 샘플링
• 토너먼트 선택

참조

외부 링크

• C 구현(.tar.gz; selector.cxx 참조) WBL
• 룰렛 휠 선택 예
• O(1) 버전의 구현 개요