유전자 알고리즘 토너먼트 선택

Question

유전자 알고리즘을 쓰고 있는데, 룰렛 휠 선택에서 토너먼트 선택으로 옮길 계획이지만, 내 이해에 결함이있을 수 있습니다.

인구 중 최고의 솔루션을 선택하는 경우 확실히 인구가 부족합니다. 알고리즘의

나의 이해는 다음과 같습니다

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 이상이어야하며 크로스 오버의 경우 크기가 최소 2 인 상태에서 최소 3 이상이어야합니다 (또는 각 부모를 크로스 오버 대상으로 선택하기 위해 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) 선택은 무작위 선택과 동일합니다.선택한 개인은 원하는 경우 선택이 이루어진 집단에서 삭제 될 수 있습니다. 그렇지 않으면 다음 세대에 대해 개인을 두 번 이상 선택할 수 있습니다. (확률 론적) 적합성 비례 선택 방법과 비교할 때, 토너먼트 선택은 확률 론적 잡음이 부족하기 때문에 실제로 구현됩니다.

매트랩에서 토너먼트 선택 :

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