Skuteczna implementacja doboru proporcjonalnego „ruletki”
Obecnie piszę algorytm optymalizacji układu klawiatury w C (taki jak ten zaprojektowany przez Petera Klauslera) i chcę zaimplementować wybór proporcjonalny do sprawności, jak opisano tutaj (Link PDF):
W przypadku wyboru ruletki wybiera się członków populacji na podstawie modelu koła rolkowego. Utwórz wykres kołowy, gdzie obszar wycinka członka do całego okręgu jest stosunkiem dopasowania członków do całkowitej populacji. Jak widzisz, jeśli punkt na obwodzie okręgu zostanie wybrany losowo, członkowie populacji o wyższej elastyczności będą mieli większe prawdopodobieństwo, że zostaną wybrani. Zapewnia to dobór naturalny.
Problem polega na tym, że nie widzę, jak go skutecznie wdrożyć. Pomyślałem o dwóch metodach: jedna jest zawodna, a druga powolna.
Po pierwsze, powolny:
W przypadku puli klawiatury o długości N utwórz tablicę o długości N, w której każdy element tablicy zawiera dwa elementy, wartość minimalną i maksymalną. Każda klawiatura ma odpowiednią wartość minimalną i maksymalną, a zakres zależy od kondycji klawiatury. Na przykład, jeśli zero klawiatury ma sprawność 10, klawiatura ma sprawność 20, a klawiatura 2 ma sprawność 25, wyglądałoby to tak: Kod:
array[0][0] = 0; // minimum
array[0][1] = 9; // maximum
array[1][0] = 10;
array[1][1] = 30;
array[2][0] = 31;
array[2][1] = 55;
(W tym przypadku niższa sprawność jest lepsza, ponieważ wymaga mniej wysiłku.)
Następnie wygeneruj liczbę losową. W zależności od zakresu, w którym liczba ta się mieści, odpowiednia klawiatura jest „zabijana” i zastępowana potomstwem innej klawiatury. Powtórz to tyle razy, ile chcesz.
Problem polega na tym, że jest bardzo powolny. Do zakończenia operacji O (N ^ 2).
Następny szybki:
Najpierw dowiedz się, jakie są najniższe i najwyższe dopasowania dla klawiatur. Następnie wygeneruj losową liczbę między (najniższa sprawność) a (najwyższa sprawność) i zabij wszystkie klawiatury o sprawności wyższej niż wygenerowana liczba. Jest to wydajne, ale nie ma gwarancji, że zabije tylko połowę klawiatur. Ma też nieco inną mechanikę niż wybór „koła ruletki”, więc może nawet nie mieć zastosowania.
Pytanie brzmi: co to jest efektywna implementacja?
Na stronie 36 tej książki istnieje dość wydajny algorytm (Połączyć), ale problem polega na tym, że jest skuteczny tylko wtedy, gdy wybierzesz ruletkę tylko raz lub kilka razy. Czy jest jakiś skuteczny sposób na równoległe wybieranie wielu ruletek?