遗传算法锦标赛选择

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);
    }
}

我理解得对吗？

- Reu

---

请适当格式化您的代码。http://stackoverflow.com/editing-help - bdhar

哦，抱歉！看起来已经有人做了，下次我会记住的。 - Reu

Answer 1

在锦标赛选择中，被选中的个体不会从种群中删除。您可以选择相同的个体参加多次锦标赛。

仔细查看您的代码后，我发现您还有一个误解。通常情况下，您不会对所有锦标赛成员进行变异/交叉。相反，您执行一场锦标赛，获胜者将被选为进行变异/交叉的个体。这意味着，对于变异，您的锦标赛规模必须至少为2，而对于交叉，规模必须至少为3，并且最好的两个获胜者（或者您可以执行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);
    }
}

- Tom Castle

---

它如何比轮盘赌等选择方法得出更好的解决方案呢？ - Reu

只有锦标赛的获胜者才会进行基因变异/交叉，并进入下一代人口。 - Tom Castle

平均而言（如果我没记错的话），如果您比较3个，那么约66％的人口将经历突变/交叉。 - deceleratedcaviar

Answer 2

如果你在每一代中从人口中选择n/2个个体，最终你将达到一个只有一个个体的人口。除了选择外，你还要通过变异或交叉产生新的成员，通常是那些在锦标赛中获胜的成员。

因此，对于每一代，你都有大小为n的人口-通过选择，你将其缩小到n/2，然后这n/2个成员繁殖和/或突变，为下一代大约产生n/2个成员（平均而言，这些成员比上一代中未进步的成员“更适合”）。

- Anthony Grist

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

- Setu Kumar Basak