遺伝的アルゴリズムにおけるルーレット選択

Question

ルーレット選択機能用の擬似コードを誰でも提供できますか？これをどのように実装しますか：

この数学表記の読み方はよくわかりません。確率や統計をとったことはありません。

Answer 1

自分でこれを行ってから数年が経ちましたが、次の擬似コードはGoogleで簡単に見つかりました。

for all members of population
    sum += fitness of this individual
end for

for all members of population
    probability = sum of probabilities + (fitness / sum)
    sum of probabilities += probability
end for

loop until new population is full
    do this twice
        number = Random between 0 and 1
        for all members of population
            if number > probability but less than next probability 
                then you have been selected
        end for
    end
    create offspring
end loop

これが由来するサイトは、こちらで見つけることができます。詳細。

Answer 2

すでに正しい解決策がたくさんありますが、このコードはより明確だと思います。

def select(fs):
    p = random.uniform(0, sum(fs))
    for i, f in enumerate(fs):
        if p <= 0:
            break
        p -= f
    return i

さらに、fsを蓄積すると、より効率的なソリューションを作成できます。

cfs = [sum(fs[:i+1]) for i in xrange(len(fs))]

def select(cfs):
    return bisect.bisect_left(cfs, random.uniform(0, cfs[-1]))

これは高速であり、非常に簡潔なコードです。 C ++のSTLには、使用している言語であれば、同様の二分法アルゴリズムがあります。

Answer 3

投稿された擬似コードには不明確な要素が含まれていたため、純粋な選択を実行する代わりに、子孫を生成する複雑さが追加されました。以下は、その擬似コードの単純なpython実装です。

def roulette_select(population, fitnesses, num):
    """ Roulette selection, implemented according to:
        <http://stackoverflow.com/questions/177271/roulette
        -selection-in-genetic-algorithms/177278#177278>
    """
    total_fitness = float(sum(fitnesses))
    rel_fitness = [f/total_fitness for f in fitnesses]
    # Generate probability intervals for each individual
    probs = [sum(rel_fitness[:i+1]) for i in range(len(rel_fitness))]
    # Draw new population
    new_population = []
    for n in xrange(num):
        r = rand()
        for (i, individual) in enumerate(population):
            if r <= probs[i]:
                new_population.append(individual)
                break
    return new_population

Answer 4

これは確率的受け入れによるルーレットホイール選択と呼ばれます：

/// \param[in] f_max maximum fitness of the population
///
/// \return index of the selected individual
///
/// \note Assuming positive fitness. Greater is better.

unsigned rw_selection(double f_max)
{
  for (;;)
  {
    // Select randomly one of the individuals
    unsigned i(random_individual());

    // The selection is accepted with probability fitness(i) / f_max
    if (uniform_random_01() < fitness(i) / f_max)
      return i;
  }   
}

1回の選択に必要な平均試行回数は次のとおりです。

<！>＃964; = f _max / avg（f）

• f _max は母集団の最大適合度です
• avg（f）は平均フィットネスです

<！>＃964;母集団内の個人の数（N）に明示的に依存しませんが、比率はNによって変化します。

ただし、多くのアプリケーション（フィットネスが制限されたままで、Nを増やしても平均フィットネスが0に減少しない場合）<！>＃964; Nで無制限に増加しないため、このアルゴリズムの典型的な複雑さはO（1）です（検索アルゴリズムを使用したルーレットホイールの選択にはO（N）またはO（log N）の複雑さがあります）

この手順の確率分布は、実際には古典的なルーレットホイールの選択と同じです。

詳細については、次を参照してください：

• 確率的受け入れによるルーレットホイールの選択（Adam Liposki、Dorota Lipowska-2011）

Answer 5

Cのコードは次のとおりです。

// Find the sum of fitnesses. The function fitness(i) should 
//return the fitness value   for member i**

float sumFitness = 0.0f;
for (int i=0; i < nmembers; i++)
    sumFitness += fitness(i);

// Get a floating point number in the interval 0.0 ... sumFitness**
float randomNumber = (float(rand() % 10000) / 9999.0f) * sumFitness;

// Translate this number to the corresponding member**
int memberID=0;
float partialSum=0.0f;

while (randomNumber > partialSum)
{
   partialSum += fitness(memberID);
   memberID++;
} 

**// We have just found the member of the population using the roulette algorithm**
**// It is stored in the "memberID" variable**
**// Repeat this procedure as many times to find random members of the population**

Answer 6

上記の回答から、次のことがわかりました。これは回答自体よりも明確でした。

例を挙げます：

ランダム（合計）::ランダム（12） 母集団を反復処理して、以下をチェックします。random <！> lt;合計

乱数として7を選択しましょう。

Index   |   Fitness |   Sum |   7 < Sum
0       |   2   |   2       |   false
1       |   3   |   5       |   false
2       |   1   |   6       |   false
3       |   4   |   10      |   true
4       |   2   |   12      |   ...

この例では、最適なインデックス（インデックス3）が選択される割合が最も高くなります（33％）。乱数は6-<！> gt; 10以内に収まる必要があるため、選択されます。

    for (unsigned int i=0;i<sets.size();i++) {
        sum += sets[i].eval();
    }       
    double rand = (((double)rand() / (double)RAND_MAX) * sum);
    sum = 0;
    for (unsigned int i=0;i<sets.size();i++) {
        sum += sets[i].eval();
        if (rand < sum) {
            //breed i
            break;
        }
    }

Answer 7

教授。スタンフォードのAIラボのThrunは、UdacityのCS373でPythonの高速（er？）再サンプリングコードも提示しました。 Googleの検索結果から次のリンクが表示されました：

http://www.udacity-forums.com/ cs373 / questions / 20194 / fast-resampling-algorithm

これが役立つことを願って

Answer 8

これは、ルーレット選択のために最近書いたコンパクトなJava実装です。うまくいけば使用できます。

public static gene rouletteSelection()
{
    float totalScore = 0;
    float runningScore = 0;
    for (gene g : genes)
    {
        totalScore += g.score;
    }

    float rnd = (float) (Math.random() * totalScore);

    for (gene g : genes)
    {   
        if (    rnd>=runningScore &&
                rnd<=runningScore+g.score)
        {
            return g;
        }
        runningScore+=g.score;
    }

    return null;
}

Answer 9

MatLabでのルーレットホイールの選択：

TotalFitness=sum(Fitness);
    ProbSelection=zeros(PopLength,1);
    CumProb=zeros(PopLength,1);

    for i=1:PopLength
        ProbSelection(i)=Fitness(i)/TotalFitness;
        if i==1
            CumProb(i)=ProbSelection(i);
        else
            CumProb(i)=CumProb(i-1)+ProbSelection(i);
        end
    end

    SelectInd=rand(PopLength,1);

    for i=1:PopLength
        flag=0;
        for j=1:PopLength
            if(CumProb(j)<SelectInd(i) && CumProb(j+1)>=SelectInd(i))
                SelectedPop(i,1:IndLength)=CurrentPop(j+1,1:IndLength);
                flag=1;
                break;
            end
        end
        if(flag==0)
            SelectedPop(i,1:IndLength)=CurrentPop(1,1:IndLength);
        end
    end

Answer 10

Based on my research ,Here is another implementation in C# if there is a need for it:


//those with higher fitness get selected wit a large probability 
//return-->individuals with highest fitness
        private int RouletteSelection()
        {
            double randomFitness = m_random.NextDouble() * m_totalFitness;
            int idx = -1;
            int mid;
            int first = 0;
            int last = m_populationSize -1;
            mid = (last - first)/2;

            //  ArrayList's BinarySearch is for exact values only
            //  so do this by hand.
            while (idx == -1 && first <= last)
            {
                if (randomFitness < (double)m_fitnessTable[mid])
                {
                    last = mid;
                }
                else if (randomFitness > (double)m_fitnessTable[mid])
                {
                    first = mid;
                }
                mid = (first + last)/2;
                //  lies between i and i+1
                if ((last - first) == 1)
                    idx = last;
            }
            return idx;
        }

Answer 11

さて、ルーレットホイールの選択の実装には、通常と確率的受け入れの2つの方法があります。

通常アルゴリズム：

# there will be some amount of repeating organisms here.
mating_pool = []

all_organisms_in_population.each do |organism|
  organism.fitness.times { mating_pool.push(organism) }
end

# [very_fit_organism, very_fit_organism, very_fit_organism, not_so_fit_organism]
return mating_pool.sample #=> random, likely fit, parent!

確率的受け入れアルゴリズム：

max_fitness_in_population = all_organisms_in_population.sort_by(:fitness)[0]
loop do
  random_parent = all_organisms_in_population.sample
  probability = random_parent.fitness/max_fitness_in_population * 100
  # if random_parent's fitness is 90%,
  # it's very likely that rand(100) is smaller than it.
  if rand(100) < probability
    return random_parent #=> random, likely fit, parent!
  else
    next #=> or let's keep on searching for one.
  end
end

どちらかを選択できますが、同じ結果が返されます。

---

有用なリソース：

http://natureofcode.com/book/chapter-9 -the-evolution-of-code -遺伝的アルゴリズムに関する初心者向けのわかりやすい章。 ルーレットホイールの選択を木製の手紙のバケツとして説明しています（入力するほど、A、通常アルゴリズムを選択できる可能性が高くなります）。

https://en.wikipedia.org/wiki/Fitness_proportionate_selection -確率的受け入れアルゴリズム。

Answer 12

この Swift 4 配列拡張機能は、要素からのルーレット選択としての重み付きランダム選択を実装しています。

public extension Array where Element == Double {

    /// Consider the elements as weight values and return a weighted random selection by index.
    /// a.k.a Roulette wheel selection.
    func weightedRandomIndex() -> Int {
        var selected: Int = 0
        var total: Double = self[0]

        for i in 1..<self.count { // start at 1
            total += self[i]
            if( Double.random(in: 0...1) <= (self[i] / total)) { selected = i }
        }

        return selected
    }
}

たとえば、2つの要素の配列がある場合：

[0.9, 0.1]

weightedRandomIndex()は、時間の90％をゼロ、時間の10％を1つ返します。

より完全なテストを次に示します。

let weights = [0.1, 0.7, 0.1, 0.1]
var results = [Int:Int]()
let n = 100000
for _ in 0..<n {
    let index = weights.weightedRandomIndex()
    results[index] = results[index, default:0] + 1
}
for (key,val) in results.sorted(by: { a,b in weights[a.key] < weights[b.key] }) {
    print(weights[key], Double(val)/Double(n))
}

出力：

0.1 0.09906
0.1 0.10126
0.1 0.09876
0.7 0.70092

この回答は、Andrew Maoの回答と基本的に同じです。 https://stackoverflow.com/a/15582983/74975

Answer 13

C＃でバージョンを作成し、実際にそれが正しいことの確認を探しています：

（roulette_selectorは、0.0〜1.0の範囲の乱数です）

private Individual Select_Roulette(double sum_fitness)
    {
        Individual ret = new Individual();
        bool loop = true;

        while (loop)
        {
            //this will give us a double within the range 0.0 to total fitness
            double slice = roulette_selector.NextDouble() * sum_fitness;

            double curFitness = 0.0;

            foreach (Individual ind in _generation)
            {
                curFitness += ind.Fitness;
                if (curFitness >= slice)
                {
                    loop = false;
                    ret = ind;
                    break;
                }
            }
        }
        return ret;

    }