java 遗传算法锦标赛选择

Genetic Algorithm Tournament Selection

提问by Reu

I'm writing a genetic algorithm and I plan to move from roulette wheel selection to tournament selection, but I suspect my understanding may be flawed.

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

If I'm only selecting the n/2 best solutions in the population, surely I run out of population quite quickly?

如果我只选择总体中的 n/2 个最佳解决方案，我肯定很快就会用完人口吗？

My understanding of the algorithm is:

我对算法的理解是：

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

Am I understanding this correctly?

我理解正确吗？

回答by Tom Castle

In tournament selection the selected individuals are not removed from the population. You may select the same individuals to take part in multiple tournaments.

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

Having looked at your code a little closer, I see you do have another misunderstanding. You would not typically mutate/crossover all members of the tournament. Instead, you perform a tournament, with the winner of that tournament being select as an individual to undergo mutation/crossover. This means that for mutation your tournament size must be at least 2, and for crossover the size must be at least 3 with the best 2 winning (or you can perform 2 separate tournaments to choose each of the parents to crossover).

仔细查看您的代码后，我发现您确实有另一个误解。您通常不会变异/交叉锦标赛的所有成员。取而代之的是，您进行一场比赛，该比赛的获胜者将被选为个人进行变异/交叉。这意味着对于变异，您的锦标赛规模必须至少为 2，而对于交叉，规模必须至少为 3，并且最好的 2 获胜（或者您可以进行 2 个单独的锦标赛以选择每个父母进行交叉）。

Some pseudo-code might help:

一些伪代码可能会有所帮助：

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

回答by Anthony Grist

If you're selecting n/2 individuals from your population in every generation, you will eventually reach a point where you have a population of 1. What you want to do in addition to selection is create new members for your next generation using mutation or crossover, generally on those that were victors in the tournament.

如果你在每一代中从你的种群中选择 n/2 个个体，你最终会达到种群为 1 的点。除了选择之外，你还想做的是使用变异或变异为下一代创建新成员交叉，通常是那些在比赛中获胜的人。

So, for each generation, you have a population of size n - you reduce this to n/2 through your selection, and then those n/2 members reproduce and/or mutate to produce roughly n/2 more members for your next generation (which, on average, will be 'fitter' than those that didn't progress from the previous generation).

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

回答by Setu Kumar Basak

Tournament Selection:

赛事选择：

• Tournament selection is a method of selecting an individual from a population of individuals.
• Tournament selection involves running several "tournaments" among a few individuals chosen at random from the population.
• The winner of each tournament (the one with the best fitness) is selected for crossover.
• When the tournament size is smaller, Tournament selection also gives a chance to all individuals to be selected and thus it preserves diversity, although keeping diversity may degrade the convergence speed.
• But if the tournament size is larger, weak individuals have a smaller chance to be selected causes loss of diversity .

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

PseudoCode:

伪代码：

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...

Deterministic tournament selection selects the best individual (when p = 1) in any tournament. A 1-way tournament (k = 1) selection is equivalent to random selection. The chosen individual can be removed from the population that the selection is made from if desired, otherwise individuals can be selected more than once for the next generation. In comparison with the (stochastic) fitness proportionate selection method, tournament selection is often implemented in practice due to its lack of stochastic noise.

确定性锦标赛选择在任何锦标赛中选择最佳个人（当 p = 1 时）。单向锦标赛 (k = 1) 选择等效于随机选择。如果需要，可以从进行选择的群体中移除所选择的个体，否则可以多次为下一代选择个体。与（随机）适应度比例选择方法相比，锦标赛选择由于缺乏随机噪声而在实践中经常被实施。

Tournament Selection in MatLab:

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