確率的普遍サンプリング

確率的普遍サンプリング（SUS ）は、遺伝的アルゴリズムで再結合に潜在的に有用な解決策を選択するために使用される手法です。これはジェームズ・ベイカーによって導入されました。^[1]

SUS は、偏りがなく、広がりが最小限である適応度比例選択(FPS)の発展形です。FPS では、ランダム サンプリングを繰り返して母集団から複数のソリューションを選択しますが、SUS では、単一のランダム値を使用して、均等間隔でソリューションを選択することで、すべてのソリューションをサンプリングします。これにより、母集団の弱いメンバー (適応度に応じて) に選択される機会が与えられます。

集団のメンバーが他のメンバーと比較して非常に大きな適応度を持つ場合、FPS のパフォーマンスは悪くなる可能性があります。SUS は櫛のような定規を使用して、小さな乱数から開始し、残りの集団から次の候補を選択します。これにより、最も適応度の高いメンバーが候補空間を飽和させることがなくなります。

アルゴリズムとして説明すると、SUS の疑似コードは次のようになります。

SUS( Population , N )
     F  := Populationの総適応度
    N  := 保持する子孫の数
    P  := ポインタ間の距離 ( F / N )
     Start := 0 からP
     の間の乱数Pointers  := [ Start + i * P | i  in [0..( N -1)]]
     return RWS( Population , Pointers )

RWS( Population , Points )
     = []
    を維持し、Pが Points I  := 0
        の場合、Population [0.. I ]の適応度の合計< P I ++  
        
            Population [ I ]をKeep
    に
        追加するKeepを返す 

配列インデックス 0 からIまでの個体の集合はどこでしょうか。 Population[0..I]

ここで、 RWS() は適応度比例選択 (「ルーレットホイール選択」とも呼ばれる) の大部分を記述します。実際の適応度比例選択では、パラメーターPoints は常に 0 からFまでの乱数の (ソートされた) リストです。上記のアルゴリズムは、標準的というよりも説明を目的としています。

• 適応度比例選択
• 報酬に基づく選択