遺伝的アルゴリズムトーナメントの選択

Question

私は遺伝的アルゴリズムを書いています。ルーレットホイールの選択からトーナメントの選択に移行する予定ですが、私の理解には欠陥があると思われます。

人口でn/2のベストソリューションを選択している場合は、確かに人口が非常に不足していますか？

アルゴリズムの私の理解では、次のとおりです。

for(Member m in currentPopulation){ 
    Member randomMember1 = random member of currentPopulation which is then removed from currentPopulation 
    Member randomMember2 = as above; 
    //Mutate and crossover 

    if(randomMember1.getScore() > randomMember2.getScore()){ 
     nextGeneration.add(randomMember1); 
    } else { 
     nextGeneration.add(randomMember2); 
    } 
} 

私はこれを正しく理解していますか？

Answer 1

トーナメントの選択では、選択した個体は母集団から削除されません。複数のトーナメントに参加するには、同じ個人を選択することができます。

あなたのコードをもう少し近く見て、別の誤解があるのを見ます。あなたは通常、トーナメントのすべてのメンバーを突然変異させたり、クロスオーバーさせたりしません。代わりに、トーナメントを行い、そのトーナメントの勝者が突然変異/クロスオーバーを受ける個体として選択されます。これは、突然変異のためにはトーナメントのサイズが2以上でなければならないことを意味します。クロスオーバーの場合、サイズは少なくとも2でなければなりません（または、2つのトーナメントを2つずつ実行して各ペアレントをクロスオーバーにすることができます）。

いくつかの擬似コードは役立つかもしれない：

while (nextPopulation too small) { 
    Members tournament = randomly choose x members from currentPopulation 

    if(crossover){ 
     Member parents = select best two members from tournament 
     Member children = crossover(parents) 
     nextPopulation.add(children); 
    } else { 
     Member parent = select best one member from tournament 
     Member child = mutate(parent) 
     nextPopulation.add(child); 
    } 
} 

Answer 2

を使用すると、すべての世代であなたの集団からN/2人を選択している場合、あなたは最終的にあなたは何の1の人口を持っている点に到達します選択に加えて、次の世代のために、トーナメントで勝者であったメンバーに、突然変異またはクロスオーバを使用して新しいメンバーを作成することです。

したがって、世代ごとに、サイズnの人口があります。これを選択することでn/2に減らした後、n/2メンバーが再生したり突然変異して約n/2人のメンバーを追加しますあなたの次世代（これは、平均して、前世代から進歩しなかったものよりも「手間がかかります」）でしょう。

Answer 3

トーナメント選択：

• トーナメントの選択は、個人の集団から個体を選択する方法です。
• トーナメントの選択には、人口から無作為に選ばれた少数の個人の中でいくつかの「トーナメント」を実行する必要があります。
• 各トーナメントの勝者（最高の適合度を持つ選手）がクロスオーバーのために選択されます。
• トーナメントのサイズが小さい場合、トーナメントの選択もすべての個人に選択される可能性があり、多様性を維持するとコンバージェンス速度が低下する可能性がありますが、多様性は維持されます。
• しかし、トーナメントのサイズが大きければ、弱い人が選択される可能性が低くなり、多様性が失われます。

擬似コード：

choose k (the tournament size) individuals from the population at random 
choose the best individual from pool/tournament with probability p 
choose the second best individual with probability p*(1-p) 
choose the third best individual with probability p*((1-p)^2) 
and so on... 

確定トーナメント選択は、任意のトーナメントで最高の個々の（場合P = 1）を選択します。 1-wayトーナメント（k = 1）の選択はランダム選択と同じです。選択された個体は、必要に応じて選択された個体群から除去することができ、そうでなければ次世代の個体を複数回選択することができる。 （確率的な）フィットネス比例選択法と比較して、トーナメント選択は、確率的ノイズの欠如のために、しばしば実際に実施される。 MATLABで

トーナメント選択：

Matepool=randi(PopLength,PopLength,2);%%select two individuals randomly for tournament and chooose the one with best fitness value 
%% number of tournament is equal to the number of population size 
for i=1:PopLength 
    if Fitness(Matepool(i,1))>= Fitness(Matepool(i,2)) 
     SelectedPop(i,1:IndLength)=CurrentPop(Matepool(i,1),1:IndLength); 
    else 
     SelectedPop(i,1:IndLength)=CurrentPop(Matepool(i,2),1:IndLength); 
    end 
end