Bewertungsproportionale Zufallsauswahl von Objekten aus Listen

Zufällige Auswahl von Kandidaten anhand ihrer Bewertung, z.B. bei Roulette-Wheel-Selection.

Ausgangslage

Bei vielen zufallsbasierten Algorithmen werden Entscheidungen auf Basis der Qualität von beispielsweise Teillösungen getroffen. Hierbei wird nicht zwingend die beste Option aus einer Menge von Optionen ausgewählt. Oftmals werden Optionen zufällig ausgesucht, je “besser” diese Optionen sind, desto höher ist jedoch die Chance sie zu wählen.

Beispiele

Zufällige Auswahl von

• Individuen in einem genetischen Algorithmus auf Basis ihrer Fitness (Link)
• Einträgen in einem Memory beim Adaptive Memory Programming (Link)
• nächstbesten Kandidaten in einer Greedy Randomized Adaptive Search Procedure (Link)
• Desktruktoren / Reparatoren anhand ihres Scores in einer Adaptive Large Neighborhood Search (Link)

Vorgehen

In allen zuvor genannten Fällen möchten wir anhand von zwei Kriterien auswählen

• Die Auswahl erfolgt zufällig
• Kandidaten / Optionen mit einer höheren Bewertung sollen eine höhere Chance haben, ausgewählt zu werden

Wir realisieren die Anforderungen, indem wir den relativen Bewertungsanteil jeder Option an der Summe aller Bewertungen ermitteln. Anschließend ziehen wir eine Zufallszahl zwischen 0 und 1 und iterieren so lange durch die verfügbaren Optionen, bis der kumulierte Wert der relativen Anteile erstmals größer ist als die Zufallszahl.

Beispielimplementierung: Zufallsauswahl auf Basis von Bewertungen

Zunächst legen wir eine simple Klasse an, die beispielhaft eins der eingangs genannten Objekte repräsentieren soll (Individuum eines GA, Memoryeintrag, Destruktor, …).

from dataclasses import dataclass
@dataclass
class BeispielObjekt:
    nr : int # ID des Objekts
    bewertung : float # Bewertung (z.B. Fitness, Score,...)

Für diese Art von Objekt wird dann die bewertungsproportionale Zufallsauswahl wie folgt implementiert:

import random
def select_random(beispiel_objekte : list[BeispielObjekt], minimize=False):
    """
        Wählt fitnessproportional ein Element aus der Liste.
        Wenn Objekte mit kleinerer Bewertung besser sind als Objekte mit
        größerer Bewertung, dann arbeitet der Algorithmus mit 1/Bewertung.
        (Kann problematisch werden, bei großen Zielfunktionswerten)
    """

    summe_bewertung = 0
    for o in beispiel_objekte:
        fitness = 1/o.bewertung if minimize else o.bewertung
        summe_bewertung += fitness

    # Zufallszahl zw. 0 und 1
    zufallszahl = random.random()

    sum_rel_bewertung = 0
    for o in beispiel_objekte:

        # Bestimmt Anteil vom Objekte an Gesamtbewertung
        fitness = 1/o.bewertung if minimize else o.bewertung
        anteil = fitness/summe_bewertung

        # Addiert Anteil zur Summe hinzu
        sum_rel_bewertung += anteil
        if zufallszahl <= sum_rel_bewertung:
            # Summe der rel. Bewertungen erstmals kleiner
            # als gezogene Zufallszahl --> das ist das nächste Objekt
            return o

Hierbei kann es bei einer großen Anzahl von Objekten sinnvoll sein, die Summe der Bewertungen (sofern möglich) abzuspeichern. Hierdurch spart man sich die erste Iteration mit einer Komplexität von O(n). Nachfolgend prüfen wir, ob die Funktion genau das tut, was erwartet wird. Wir erzeugen drei Objekte deren Bewertungen sich zufällig zu 1 addieren. Anschließend ziehen wir mehrere tausend mal zufällig anhand der Funktion Objekte.

random.seed(1)
beispiel_objekte = []
beispiel_objekte.append(BeispielObjekt(nr=1,bewertung=0.20))
beispiel_objekte.append(BeispielObjekt(nr=2,bewertung=0.30))
beispiel_objekte.append(BeispielObjekt(nr=3,bewertung=0.50))
counter = { 1 : 0, 2 : 0, 3 : 0}
for _ in range(10000):
    naechstes_objekt = select_random(beispiel_objekte)
    # Aktualisiert: Wie oft wurde das Objekt gezogen?
    counter[naechstes_objekt.nr] += 1
print(counter)

Wie erwartet stimmt das Ergebnis zur Annahme. Von 10.000 Ziehungen wurde Objekt 1 in knapp 20% der Fälle, Objekt 2 in etwa 30% der Fälle und Objekt 3 in rund 50% der Fälle ausgewählt.

{1: 2058, 2: 2965, 3: 4977}