8

我正在编写一个遗传算法，我计划从轮盘赌选择转向锦标赛选择，但我怀疑我的理解可能存在缺陷。

如果我只选择人口中的 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);
    }
}

我是否正确理解这一点？

4

3 回答 3

9

在锦标赛选择中，选定的个体不会从群体中移除。您可以选择同一个人参加多个锦标赛。

仔细查看您的代码后，我发现您确实有另一个误解。您通常不会变异/交叉比赛的所有成员。取而代之的是，您进行了一场锦标赛，该锦标赛的获胜者被选为个人进行突变/交叉。这意味着对于突变，您的锦标赛规模必须至少为 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);
    }
}
于 2011-02-02T10:26:39.913 回答
1

如果您在每一代的人口中选择 n/2 个个体，您最终将达到人口为 1 的点。除了选择之外，您还想做的是使用突变或交叉，通常是那些在比赛中获胜的人。

因此，对于每一代，您都有一个大小为 n 的人口 - 您通过您的选择将其减少到 n/2，然后这些 n/2 成员复制和/或变异为您的下一代产生大约 n/2 更多成员（平均而言，这将比上一代没有进步的那些“更健康”）。

于 2011-02-02T10:40:16.637 回答
-1

赛事选择：

  • 比赛选择是一种从个体群体中选择个体的方法。
  • 比赛选择涉及在从人群中随机选择的几个人中运行几个“比赛”。
  • 每场比赛的获胜者（体能最好的那个）被选为交叉赛。
  • 当锦标赛规模较小时，锦标赛选择也给了所有个体被选择的机会，因此它保留了多样性，尽管保持多样性可能会降低收敛速度。
  • 但如果比赛规模较大，弱个体被选中的机会较小，导致多样性损失。

伪代码：

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
于 2018-03-04T03:06:25.140 回答