Wybór turniejów algorytmów genetycznych

Question

Piszę algorytm genetyczny i planuję przejść od wyboru koła ruletki do wyboru turnieju, ale podejrzewam, że moje zrozumienie może być wadliwe.

Jeśli wybieram tylko najlepsze rozwiązania n/2 w populacji, z pewnością dość szybko zabraknie mi populacji?

Moje zrozumienie algorytmu jest:

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

jestem rozumiejąc to prawidłowo?

Answer 1

W wyborze turnieju wybrane osoby nie są usuwane z populacji. Możesz wybrać te same osoby, aby wziąć udział w wielu turniejach.

Po przyjrzeniu się kodowi trochę bliżej, widzę, że masz kolejne nieporozumienie. Zazwyczaj nie mutowałbyś/nie krosował wszystkich członków turnieju. Zamiast tego, wykonujesz turniej, w którym zwycięzca tego turnieju jest wybierany indywidualnie, aby przejść mutację/crossover. Oznacza to, że w przypadku mutacji rozmiar twojego turnieju musi wynosić co najmniej 2, a dla crossovera rozmiar musi wynosić co najmniej 3, z najlepszym 2 wygranym (lub możesz wykonać 2 oddzielne turnieje, aby wybrać każdego z rodziców do przejścia).

Niektóre pseudo-kod może pomóc:

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

Jeśli wybierając N/2 osoby ze swojej populacji w każdym pokoleniu, w końcu dotrzeć do punktu, gdzie trzeba populację 1. Co ty oprócz selekcji chcesz stworzyć nowych członków dla następnej generacji, używając mutacji lub crossovera, ogólnie tych, którzy byli zwycięzcami w turnieju.

Tak więc, dla każdego pokolenia, masz populację wielkości n - redukujesz to do n/2 poprzez swój wybór, a następnie ci n/2 członkowie rozmnażają się i/lub mutują, aby wyprodukować około n/2 dodatkowych członków dla następne pokolenie (które średnio będzie "sprawniejsze" niż te, które nie rozwijały się z poprzedniego pokolenia).

Answer 3

Wybór turnieju:

• wybór Turniej jest metodą wyboru osobnika z populacji osobników.
• Wybór turnieju polega na przeprowadzeniu kilku "turniejów" wśród kilku wybranych losowo osób z populacji.
• Zwycięzca każdego turnieju (ten o najlepszej kondycji) jest wybierany do crossovera.
• Gdy rozmiar turnieju jest mniejszy, wybór Turnieju daje także szansę wszystkim wybranym osobom, a tym samym zachowuje różnorodność, chociaż zachowanie różnorodności może pogorszyć prędkość zbieżności.
• Ale jeśli rozmiar turnieju jest większy, słabe osoby mają mniejszą szansę na wybranie powodują utratę różnorodności.

pseudokodzie:

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

deterministyczny wybór turnieju wybiera najlepszą fizyczną (gdy p = 1), w każdym turnieju. Wybór 1-drożnego turnieju (k = 1) jest równoważny doborowi losowemu.Wybraną osobę można usunąć z populacji, z której dokonano selekcji, jeśli jest to pożądane, w przeciwnym razie można wybrać osobniki więcej niż raz dla następnej generacji. W porównaniu do metody doboru proporcjonalnego (stochastycznego), wybór turniejów jest często wdrażany w praktyce ze względu na brak hałasu stochastycznego.

Wybór turnieju w 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