適応度比例選択
Selection technique used in evolutionary algorithms
単一の個体の選択の例

適応度比例選択はルーレットホイール選択やスピニングホイール選択とも呼ばれ、進化アルゴリズムにおいて組み換えに有用な解決策を選択するために使用される選択手法です。[1]

方法

適応度比例選択においては、他の選択手法と同様に、適応度関数は可能な解、すなわち染色体に適応度を割り当てます。この適応度レベルは、個々の染色体に選択確率を関連付けるために使用されます。個体の集団における適応度が である場合、その個体が選択される確率は です。 f i {\displaystyle f_{i}} i {\displaystyle i}

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

ここで、人口内の個体数です。 N {\displaystyle N}

これはカジノのルーレットホイールに似ていると想像できます。通常、各選択肢の適応度に基づいて、ホイールの一定の割合が割り当てられます。これは、ある選択肢の適応度を全ての選択肢の合計適応度で割り、1に正規化することで実現できます。そして、ルーレットホイールの回転と同様に、ランダムに選択が行われます。

適応度の高い候補解が排除される可能性は低くなりますが、選択される確率が 1 (または 100%) 未満であるため、排除される可能性は依然としてあります。これを、最も弱い候補の一定の割合を排除する、切り捨て選択などのそれほど洗練されていない選択アルゴリズムと比較してください。適応度比例選択では、一部の弱い解が選択プロセスを生き残る可能性があります。これは、弱い解が生き残る確率は低いものの、生き残る可能性がまだあることを意味するゼロではないためです。これは、弱い解であっても、再結合プロセスの後に有用であると判明する可能性のある機能や特性を持っている可能性があるため、利点となります。

ルーレットとの類似性は、各候補解決策がホイール上のポケットを表すルーレットホイールを想像することで思い描くことができます。ポケットのサイズは、解決策が選択される確率に比例します。[要出典] 集団から N 個の染色体を選択することは、各候補が個別に抽選されるため、ルーレットホイールで N 回ゲームをプレイすることと同じです。

単純な実装では、まず個体の適応度に比例する確率を用いて、個体リスト全体にわたる累積確率分布（CDF）を生成します。範囲[0,1)から一様乱数が選択され、その乱数のCDFの逆数が個体となります。これは、ルーレットの玉が個体のビンにその幅に比例する確率で落ちることに相当します。一様乱数の逆数に対応する「ビン」は、CDFの要素に対して二分探索を行うことで最も速く見つけることができます。個体の選択にはO(log n)の時間がかかります。個体をO(1)の時間で生成するより高速な方法は、エイリアス法を使用することです。

2011年には、「確率的受容」に基づく非常にシンプルなアルゴリズムが導入されました。[2]このアルゴリズムは、個体（例えば）をランダムに選択し、その選択を確率 （ は集団における最大の適応度）で受容します。ある分析によると、確率的受容バージョンは、線形探索や二分探索に基づくバージョンよりも大幅に優れた性能を示し、特に実行中に適応度が変化する可能性があるアプリケーションでは顕著です。[3]このアルゴリズムの動作は通常高速ですが、一部の適応度分布（指数分布など）では、最悪の場合、反復処理が必要になることがあります。また、このアルゴリズムは二分探索よりも多くの乱数を必要とします。 i {\displaystyle i} f i / f M {\displaystyle f_{i}/f_{M}} f M {\displaystyle f_{M}} O ( n ) {\displaystyle O(n)}

擬似コード

例えば、適応度が[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 /

上記の例の数値を使用して、確率を決定する方法は次のとおりです。 

適応度の合計 = 10
前回の確率 = 0.0

[1] = 前回の確率 + (適応度 / 適応度の合計) = 0.0 + (1 / 10) = 0.1
前回の確率 = 0.1

[2] = 前回の確率 + (適応度 / 適応度の合計) = 0.1 + (2 / 10) = 0.3
前回の確率 = 0.3

[3] = 前回の確率 + (適応度 / 適応度の合計) = 0.3 + (3 / 10) = 0.6
前回の確率 = 0.6

[4] = 前回の確率 + (適応度 / 適応度の合計) = 0.6 + (4 / 10) = 1.0

最後のインデックスは常に1.0かそれに近い値である必要があります。次に、個体をランダムに選択する方法を示します。 

random_number # 0.0から1.0の間

乱数 < 0.1 の場合1を

    選択、そうでない場合はrandom_number < 0.3 の場合# 0.3 − 0.1 = 0.2 の確率2を

    選択、そうでなければrandom_number < 0.6の場合# 0.6 − 0.3 = 0.3の確率3を

    選択、そうでなければrandom_number < 1.0の場合# 1.0 − 0.6 = 0.4の確率
    選択4
終了の場合

その他の方法

確率的ユニバーサルサンプリング[4]やトーナメント選択などの他の選択手法は、実際にはしばしば用いられます。これは、これらの手法が確率的ノイズが少ない、あるいは高速で実装が容易であり、選択圧が一定であるためです[5] 。

参照

参考文献

  1. ^ Eremeev, Anton V. (2020年7月). 「ロイヤルロード関数における適応度比例淘汰を用いた非エリート主義的進化アルゴリズムの実行時間分析」. 2020 Cognitive Sciences, Genomics and Bioinformatics (CSGB) . pp.  228– 232. doi :10.1109/CSGB51356.2020.9214612. ISBN 978-1-7281-9597-1。
  2. ^ A. リポウスキー「確率的受容によるルーレットホイール選択」（arXiv:1109.3627）[1]
  3. ^ 高速比例選択
  4. ^ バック、トーマス、「進化アルゴリズムの理論と実践」（1996年）、p. 120、オックスフォード大学出版局
  5. ^ Blickle, Tobias; Thiele, Lothar (1996). 「進化アルゴリズムにおける選択スキームの比較」.進化計算. 4 (4): 361– 394. doi :10.1162/evco.1996.4.4.361. ISSN  1063-6560. S2CID  42718510.
  • C実装（.tar.gz; selector.cxxを参照）WBL
  • ルーレットホイールの選択例
  • O(1)版の実装の概要
Retrieved from "https://en.wikipedia.org/w/index.php?title=Fitness_proportionate_selection&oldid=1293984692"