遗传算法锦标赛选择

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，而对于交叉，大小必须至少为3且最佳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时）。单向锦标赛（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