Генетический алгоритм отбора турниров

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