適応度比例選択

適応度比例選択はルーレットホイール選択とも呼ばれ、組み換えに潜在的に有用なソリューションを選択するために遺伝的アルゴリズムで使用される遺伝的演算子です。

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

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

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

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

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

ルーレットホイールとの類似性は、各候補ソリューションがホイール上のポケットを表すルーレットホイールを想像することで想定できます。ポケットのサイズは、ソリューションが選択される確率に比例します。^[要出典] 集団から N 個の染色体を選択することは、各候補が独立して抽選されるため、ルーレットホイールで N 回のゲームをプレイすることと同じです。

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

2011 年に、「確率的受容」に基づく非常に単純なアルゴリズムが導入されました。^[1]このアルゴリズムは、個体 (たとえば) をランダムに選択し、その選択を確率 で受容します。ここで は、集団の最大適応度です。特定の分析によると、確率的受容バージョンは、特に実行中に適応度値が変化する可能性があるアプリケーションでは、線形探索または二分探索に基づくバージョンよりも大幅に優れたパフォーマンスを発揮します。^[2]このアルゴリズムの動作は通常高速ですが、一部の適応度分布 (指数分布など) では、最悪の場合、反復が必要になることがあります。また、このアルゴリズムでは、二分探索よりも多くの乱数が必要になります。 ${\displaystyle i}$${\displaystyle f_{i}/f_{M}}$${\displaystyle f_{M}}$${\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
終了

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

• 報酬に基づく選択
• 確率的普遍サンプリング

• C 実装 (.tar.gz; selector.cxx を参照) WBL
• ルーレットホイールの選択例
• O(1)バージョンの実装の概要