Ich schreibe gerade einen Algorithmus zur Optimierung des Tastaturlayouts in C (wie den von Peter Klausler entworfenen) und möchte eine fitnessproportionale Auswahl wie hier beschrieben implementieren (PDF Link):

Bei der Roulette-Auswahl wählen Sie Mitglieder der Bevölkerung anhand eines Roullete-Rad-Modells aus. Erstellen Sie ein Kreisdiagramm, in dem die Fläche des Schnitts eines Mitglieds zum gesamten Kreis das Verhältnis der Fitness des Mitglieds zur Gesamtbevölkerung ist. Wie Sie sehen können, ist die Wahrscheinlichkeit, dass ein Punkt auf dem Umkreis des Kreises zufällig ausgewählt wird, für die Bevölkerungsmitglieder mit höherer Fitness höher. Dies stellt sicher, dass eine natürliche Selektion stattfindet.

Das Problem ist, dass ich nicht sehe, wie ich es effizient umsetzen kann. Ich habe mir zwei Methoden überlegt: Eine ist unzuverlässig und die andere ist langsam.

Erstens die langsame:

Erstellen Sie für einen Tastaturpool der Länge N ein Array der Länge N, wobei jedes Element des Arrays tatsächlich zwei Elemente enthält, einen minimalen und einen maximalen Wert. Jede Tastatur hat einen entsprechenden Minimal- und Maximalwert, und der Bereich basiert auf der Fitness der Tastatur. Wenn Tastatur Null beispielsweise eine Fitness von 10 hat, Tastatur Eins eine Fitness von 20 hat und Tastatur Zwei eine Fitness von 25 hat, sieht das folgendermaßen aus: Code:

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;

(In diesem Fall ist eine geringere Fitness besser, da weniger Kraftaufwand erforderlich ist.)

Dann generiere eine Zufallszahl. Für jeden Bereich, in den diese Nummer fällt, wird die entsprechende Tastatur "getötet" und durch die Nachkommen einer anderen Tastatur ersetzt. Wiederholen Sie dies so oft wie gewünscht.

Das Problem dabei ist, dass es sehr langsam ist. Es dauert O (N ^ 2) Operationen, um zu beenden.

Als nächstes die Schnelle:

Ermitteln Sie zunächst die niedrigsten und höchsten Fitnesswerte für die Tastaturen. Generieren Sie dann eine Zufallszahl zwischen (niedrigste Fitness) und (höchste Fitness) und töten Sie alle Tastaturen mit einer Fitness, die höher als die generierte Zahl ist. Dies ist effizient, aber es kann nicht garantiert werden, dass nur die Hälfte der Tastaturen zerstört wird. Es hat auch eine etwas andere Mechanik als ein "Roulette-Rad", so dass es möglicherweise nicht einmal anwendbar ist.

Die Frage ist also, was ist eine effiziente Implementierung?

Es gibt einen ziemlich effizienten Algorithmus auf Seite 36 dieses Buches (Verknüpfung), aber das Problem ist, dass es nur dann effizient ist, wenn Sie die Roulette-Auswahl nur ein oder mehrere Male durchführen. Gibt es eine effiziente Möglichkeit, viele Roulette-Auswahlen gleichzeitig durchzuführen?