Выбор турнира по генетическому алгоритму

Я пишу генетический алгоритм и планирую перейти от выбора колеса рулетки к выбору турнира, но я подозреваю, что мое понимание может быть ошибочным.

Если я выбираю только 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);
    }
}

Я правильно это понимаю?


java genetic-algorithm evolutionary-algorithm
person Reu    schedule 02.02.2011    source источник
comment
Пожалуйста, отформатируйте код соответствующим образом. stackoverflow.com/editing-help   -  person bdhar    schedule 02.02.2011
comment
Ой, извини! Похоже, у кого-то уже было, я вспомню об этом в следующий раз.   -  person Reu    schedule 02.02.2011

Ответы (3)


arrow_upward
9
arrow_downward

При турнирном отборе выбранные особи не удаляются из популяции. Вы можете выбрать одних и тех же лиц для участия в нескольких турнирах.

Посмотрев на ваш код немного ближе, я вижу, что у вас есть еще одно недоразумение. Обычно вы не мутируете/пересекаете всех участников турнира. Вместо этого вы проводите турнир, в котором победитель этого турнира выбирается как личность для прохождения мутации/кроссовера. Это означает, что для мутации размер вашего турнира должен быть не менее 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);
    }
}
person Tom Castle    schedule 02.02.2011
comment
Как же тогда получить лучшее решение, чем метод выбора, такой как колесо рулетки? - person Reu; 02.02.2011
comment
Смотрите мою правку. Только победители турнира подвергаются мутации/скрещиванию и попадают в следующую популяцию. - person Tom Castle; 02.02.2011
comment
Т.е. в среднем (если не ошибаюсь) 66% популяции подвергнется мутации/кроссинговеру, если вы проводите сравнение 3. - person deceleratedcaviar; 02.02.2011
comment
Большое спасибо, это было именно то, что я искал. - person Reu; 02.02.2011

arrow_upward
1
arrow_downward

Если вы выбираете n/2 особей из своей популяции в каждом поколении, вы в конечном итоге достигнете точки, когда ваша популяция будет равна 1. Что вы хотите сделать в дополнение к отбору, так это создать новых членов для вашего следующего поколения, используя мутацию или кроссовер, как правило, на тех, кто был победителем в турнире.

Таким образом, для каждого поколения у вас есть популяция размером n — вы уменьшаете ее до n/2 посредством своего отбора, а затем эти n/2 членов воспроизводятся и/или мутируют, чтобы произвести примерно n/2 дополнительных членов для вашего следующего поколения ( которые, в среднем, будут «лучше приспособлены», чем те, которые не произошли от предыдущего поколения).

person Anthony Grist    schedule 02.02.2011

arrow_upward
-1
arrow_downward

Выбор турнира:

  • Турнирный отбор - это метод выбора индивидуума из популяции индивидуумов.
  • Выбор турнира включает в себя проведение нескольких «турниров» среди нескольких человек, выбранных случайным образом из населения.
  • Победитель каждого турнира (тот, у кого лучшая физическая форма) выбирается для кроссовера.
  • Когда размер турнира меньше, выбор турнира также дает возможность быть выбранным всем участникам и, таким образом, сохраняет разнообразие, хотя сохранение разнообразия может снизить скорость сходимости.
  • Но если размер турнира больше, слабые люди имеют меньше шансов быть выбранными, что приводит к потере разнообразия.

Псевдокод:

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
person Setu Kumar Basak    schedule 04.03.2018