selekcja metodą ruletki

Mam tablicę np. double tab[10], gdzie przechowuję wartość funkcji przystosowania dla poszczególnych osobników. W tym wypadku im wartość mniejsza tym osobnik jest bardziej przystosowany. Jak zaimplementować w C++ funkcję dokonującą selekcję 10 osobników metodą ruletki ?

liczysz sumę stopnia przystosowania dla wszystkich osobników, obliczasz ta_suma* rand()/(double)RAND_MAX i od tej wartości po kolei odejmujesz stopień przystosowania kolejnego osobnika. Gdy dla danego osobnika osiągniesz wartość ujemną, to tego osobnika bierzesz do rozmnażania.

To jest tak popularny temat że dziwne że o to pytasz.

Ten algorytm to najmilsza część GA.

Odpowiedź od MarekR22 powinna wystarczyć.

Algorytm jaki podał @MarekR22 jest dobry i poprawny tylko że zakłada że największy element jest bardziej przystosowany. Więc przed jego użyciem trzeba do tego stanu doprowadzić.
Znajdujesz element o wartości maksymalnej MAX oraz minimalnej MIN.
f(i)=MAX+MIN-tab[i].
Sumę liczysz f(i) oraz odejmujesz f(i) wg powyższego algorytmu.

Można zrobić bez odejmowania - pseudo-kod:

a = suma elementów
b = wartość losowa od 0.0 do a włącznie
c = element[0]
i = 0

dopóki (c < b) oraz (i < liczba-elementów - 1)
{
   zwiększ i
   c = c + element[i];
}
 
i = nr wylosowany

@vpiotr, załóżmy że mamy tylko 3 elementy w tablice element[]={1,10,100};
wg podanego przez ciebie algorytmu losujemy wartość b w zakresie od 0 do 111
c=1;
i=0;
dopóki (c<b) // tu jedyną szansą na wylosowanie zerowego elementu jest warunek b=0;
czyli element 0 o wartości 1, najlepiej przystosowany wg założeń pytającego ma szanse na rozmnożenie z prawdopodobieństwem 1/112 !
No chyba że nie przeczytałeś uważnie pytania ani mojego postu.

_13th_Dragon napisał(a):

No chyba że nie przeczytałeś uważnie pytania ani mojego postu.

Dokładnie tak, mea culpa.
Trzeba to albo najpierw znormalizować albo zastosować inny algorytm.

_13th_Dragon napisał(a):

Znajdujesz element o wartości maksymalnej MAX oraz minimalnej MIN.
f(i)=MAX+MIN-tab[i].
Sumę liczysz f(i) oraz odejmujesz f(i) wg powyższego algorytmu.

Wracając do Twojego przykładu:
element[]={1,10,100};

MAX = 100
MIN = 1

element[0] = 100 + 1 - 1 = 100
element[1] = 101 - 10 = 91
element[2] = 101 - 100 = 1

po normalizacji wg sumy (192):

element[0] = 100/192 = 52% szans na wylosowanie
element[1] = 91/192 = 47% szans
element[2] = 1/192 = 1% szans

Pamiętając że "im wartość mniejsza tym osobnik jest bardziej przystosowany":

Osobnik nr 0 powinien mieć 10 razy większą szansę na wylosowanie (jest 10 razy lepszy) niż nr 1.
Czyli z grubsza licząc rozkład powinien być mniej więcej taki:

element[0] = 90 = 90% szans
element[1] = 9 = 9%
element[2] = 1 = 1%

A nie jest...

Moja propozycja do normalizacji poniżej.

Normalizacja nr 1:

f(i) = 1 / (element[i] + suma(element[k], k = 0..i-1))

Przy normalizacji:

1 / (1) = 1
1 / (1 + 10) = 0,09
1 / (11 + 100) = 0,009

Suma = 1,099

Po wykonaniu drugiej normalizacji:
g(i) = element[i] / suma

element[0] = 0,9 = 90%
element[1] = 0,081 = 8%
element[2] = 0,0082 = 1%

To jest rozkład niedokładnie taki jak oczekiwany, ale bardziej zbliżony.

@vpiotr, zamiast dwóch kroków normalizacji wystarczy wziąć moją addytywną normalizację:
f(i)=MAX+MIN-tab[i]
i przerobić ją na multiplikatywną:
f(i)=exp(ln(MAX)+ln(MIN)-ln(tab[i]))
co jest w zasadzie tym samym co:
f(i)=MAX*MIN/tab[i]
czyli:
1 => 100
10 => 10
100 => 1