遗传算法比赛选择

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 时）。 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