michael.eichberg@dhbw.de, Raum 149B
1.0
Davic Kopec, Algorithmen in Python, Rheinwerk Computing
werden eingesetzt, wenn traditionelle Algorithmen nicht geeignet sind oder keine offensichtlichen Algorithmen existieren
Z. B. im Bereich des Wirkstoffdesigns oder der Optimierung von Produktionsprozessen.
benötigen im Prinzip nur eine Definition des Aufgabenziels
(Implementierungen) sind in der Regel hochgradig spezialisiert; hier diskutieren wir eine allgemeine/generische Implementierung
Genetische Algorithmen basieren auf der Evolutionstheorie:
die besten Individuen überleben
zufällige Veränderungen
Kreuzung von Individuen
Terminologie:
Menge von Individuen, die auch Chromosomen genannt werden und Lösungskandidaten repräsentieren
Lösungskandidaten oder auch Individuen, die aus Genen bestehen
Eigenschaften eines Lösungskandidaten
Bewertung eines Chromosoms ( Lösungskandidaten)
D. h. auf der natürlichen Auslese und der Vererbung von Eigenschaften. Ein Individuum, das besser an die Umwelt angepasst ist, hat eine höhere Wahrscheinlichkeit, sich fortzupflanzen und seine Gene weiterzugeben. Schlechter angepasste Individuen sterben aus.
Klassisches Beispiel ist die Entwicklung von Resistenzen gegen Antibiotika bei Bakterien.
ein genetischer Algorithmus durchläuft Generationen
In jeder Generation werden die Individuen/Chromosomen bewertet und die besser angepassten Individuen (solche die fitter sind) mit einer höheren Wahrscheinlichkeit zum Überleben und zur Fortpflanzung ausgewählt
in jeder Generation werden die Individuen mit gewissen Wahrscheinlichkeiten:
rekombiniert (crossover von zwei Chromosomen) und
mutiert (mutate)
Genetische Algorithmen sind eine gute Wahl, wenn es keinen schnellen deterministischen Algorithmus gibt.
1class Chromosome(ABC):2@abstractmethod3def fitness(self) -> float:4raise NotImplementedError56@classmethod7@abstractmethod8def random_instance(cls: Type[T]) -> T:9raise NotImplementedError1011@abstractmethod12def crossover(self: T, other: T) -> tuple[T, T]:13raise NotImplementedError1415@abstractmethod16def mutate(self) -> None:17raise NotImplementedError
Die Basisklasse für Chromosomen (https://delors.github.io/theo-algo-genetic_algorithms/code/lib/chromosome.py) definiert die Methoden, die jedes Chromosom implementieren muss: Eine Klassenmethode zum Erzeugen einer zufälligen Instanz (random_instance), und Instanzmethoden zum Mutieren einer Instanz (mutate), zum Kreuzen einer Instanz mit einer anderen (crossover) und schließlich zur Bewertung eines Chromosoms (fitness).
mutate:führt eine kleine zufällige Änderung (an den Genen) durch
crossover:kombiniert zwei Chromosomen zu einem neuen Chromosom; d. h. mischt zwei Lösungen
fitness:bewertet die eigene Fitness
random_instance:erzeugt eine zufällige Instanz; wird nur einmal am Anfang benötigt, um die Population zu initialisieren
Erzeugen einer zufälligen Population
Miss die Fitness der Individuen, wenn einer den Zielwert erreicht, beende den Algorithmus und gib das Individuum zurück
Wähle einige Individuen aus, die sich fortpflanzen - bevorzuge die Fitteren mit einer höheren Wahrscheinlichkeit
Kombiniere die ausgewählten Individuen, um neue Individuen zu erzeugen
Mutiere einige Individuen, um die neue Generation zu vervollständigen
Wiederhole die Schritte 2-5 für eine bestimmte Anzahl von Generationen
Größe der Population
Design der ersten Population (rein zufällig oder basierend auf einer Heuristik)
Wahl des Schwellenwertes, der angibt, wann der Algorithmus beendet wird
Auswahl der Chromosomen, die sich fortpflanzen
Wie und mit welcher Wahrscheinlichkeit die Rekombination erfolgt (crossover)
Wie und mit welcher Wahrscheinlichkeit eine Mutation erfolgt (mutate)
Wie viele Generationen max. durchlaufen werden
Es gibt zwei typische Strategien zur Auswahl der Chromosomen, die sich fortpflanzen: die Tournament Selection und die Roulette Wheel Selection.
Bestimmung der Chromosomen, die überleben und sich ggf. fortpflanzen.
Auswahlstrategien
Wähle zufällig einige Chromosomen aus und wähle das beste(/die besten) Chromosom(en) aus dieser Gruppe:
1def _pick_tournament(2self, num_participants: int) -> tuple[C, C]:3participants: list[C] = \4choices(self._population, k=num_participants)5return tuple(6nlargest(72,8participants, key=self._fitness_key))
Jedes Chromosom wird mit einer Wahrscheinlichkeit ausgewählt, die proportional zu seiner Fitness ist (die Fitness wird in eine Wahrscheinlichkeit umgerechnet).
1def _pick_roulette(2self, wheel: list[float]) -> tuple[C, C]:3c: tuple[C, C] = \4tuple(choices(5self._population,6weights=wheel, k=2))7return c
Vorgehen
Für jedes gewählte Chromosomenpaar bestimme, ob diese rekombiniert werden sollen. Wenn ja, führe die Rekombination durch. Wenn nicht, kopiere die Chromosomen einfach in die neue Generation.
Wiederhole die Selektion und ggf. Rekombination, bis die gewünschte Anzahl von Chromosomen ausgewählt wurde.
1C = TypeVar("C", bound=Chromosome) # type of the chromosomes234class GeneticAlgorithm(Generic[C]):5SelectionType = Enum("SelectionType", "ROULETTE TOURNAMENT")67def __init__(8self,9initial_population: list[C],10threshold: float,11max_generations: int = 100,12mutation_chance: float = 0.01,13crossover_chance: float = 0.7,14selection_type: SelectionType = SelectionType.TOURNAMENT,15)
1def run(self) -> C:2best: C = max(self._population, key=self._fitness_key)3for generation in range(self._max_generations):4# early exit if we beat threshold5if best.fitness() >= self._threshold:6return best7print(8f"Generation {generation} Best {best.fitness()} Avg {9mean(map(self._fitness_key, self._population))10}")11self._reproduce_and_replace() # selection and crossover12self._mutate()13highest: C = max(self._population, key=self._fitness_key)14if highest.fitness() > best.fitness():15best = highest # found a new best16return best # best we found in _max_generations
fitness_key ist eine Referenz auf die Methode, die die Fitness eines Chromosoms berechnet.
94def _mutate(self) -> None:95for individual in self._population:96if random() < self._mutation_chance:97individual.mutate()
69def _reproduce_and_replace(self) -> None:70new_population: list[C] = []71# Selektiere und Kreuze Individuen, bis die neue Population steht72while len(new_population) < len(self._population):73# Wahl der zwei Eltern gemäß Selektionsmethode74# (Roulette oder Turnier)
82# Kreuze ggf. die Eltern83if random() < self._crossover_chance:84new_population.extend(parents[0].crossover(parents[1]))85else:86new_population.extend(parents)87# Falls die Populationsgröße ungerade ist,88# entferne das letzte Individuum89if len(new_population) > len(self._population):90new_population.pop()91self._population = new_population # replace reference
73# Wahl der zwei Eltern gemäß Selektionsmethode74# (Roulette oder Turnier)75if self._selection_type == \76GeneticAlgorithm.SelectionType.ROULETTE:77parents: tuple[C, C] = self._pick_roulette(78[x.fitness() for x in self._population]79)80else:81parents = \82self._pick_tournament(len(self._population) // 2)
Die Herausforderung bei der Entwicklung von genetischen Algorithmen ist somit zweigeteilt:
eine passende Formulierung für das Problem zu entwickeln und
danach die Parameter so zu wählen, dass der Algorithmus in einer akzeptablen Zeit eine gute Lösung findet.
Klassisches Problem der Kryptographie
Jeder Buchstabe repräsentiert eine Ziffer von 0 bis 9
Keine Ziffer darf doppelt vorkommen
S E N D + M O R E --------- M O N E Y
Welcher Buchstabe steht für welchen Wert?
Chromosomen ermöglichen Zuordnung von Buchstaben zu Ziffern
Idee: Verwendung von Listenindizes zur Repräsentation der Ziffern: [0,...,9]. Die Werte in der Liste entsprechen den Buchstaben; Beispiel:
Zuordnung von Ziffern zu Buchstaben:
Index: |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|---|---|---|---|---|---|---|---|---|---|---|---|
letters = [ |
O, |
M, |
Y, |
␣, |
␣, |
E, |
N, |
D, |
R, |
S |
] |
Für die Lösung würde sich ergeben:
S |
E |
N |
D |
M |
O |
R |
Y |
␣ |
␣ |
|---|---|---|---|---|---|---|---|---|---|
9 |
5 |
6 |
7 |
1 |
0 |
8 |
2 |
3 |
4 |
Somit kann durch die Verschiebung der Buchstaben in der Liste der assoziierte Wert geändert werden.
Klasse für Chromosomen
1class SendMoreMoney(Chromosome):2def __init__(self, letters: list[str]) -> None:3self.letters: list[str] = letters
Erzeugen von Individuen bzw. Chromosomen
Idee: beliebige Verwürfelung der Buchstaben in der Liste.
1def random_instance(cls) -> Self:2letters = [3"S", "E", "N", "D", "M", "O", "R", "Y",4" ", " "]5shuffle(letters)6return SendMoreMoney(letters)
Mutation eines Chromosoms
Idee: zufälliger paarweiser Austausch von zwei Buchstaben in der Liste.
1def mutate(self) -> None: # swap two letters' locations2idx1, idx2 = sample(range(len(self.letters)), k=2)3self.letters[idx1], self.letters[idx2] = \4self.letters[idx2], self.letters[idx1]
Vererbung
Idee: pro Nachkommen sicherstellen, dass einige Buchstaben Indizes (d. h. Wertzuordnungen) von einem Elternteil und einige vom anderen Elternteil stammen.
Beispiel (verkürzt):
Elternteil 1 = [a,b,c,d,e] # d.h. ein Chromosom Elternteil 2 = [c,a,b,e,d] # d.h. ein Chromosom
gewählte Indizes seien: 0 und 2
Nachkomme 1 = [a,c,b,d,e] # im Wesentlichen Elternteil 1,
aber Position von "b" vom 2ten übernommen
(dadurch Anpassung der Pos. von "c" notw.)
Nachkomme 2 = [a,c,b,e,d] # im Wesentlichen Elternteil 2,
aber Position von "a" vom 1ten übernommen
(dadurch Anpassung der Pos. von "c" notw.)
Vererbung - Implementierung
1def crossover(self, other: Self) -> tuple[Self, Self]:2child1: SendMoreMoney = deepcopy(self)3child2: SendMoreMoney = deepcopy(other)4idx1, idx2 = sample(range(len(self.letters)), k=2)5l1, l2 = child1.letters[idx1], child2.letters[idx2]6child1.letters[child1.letters.index(l2)], \7child1.letters[idx2] = \8child1.letters[idx2], l2910child2.letters[child2.letters.index(l1)], \11child2.letters[idx1] = \12child2.letters[idx1], l11314return child1, child2
Fitness-Funktion
Idee: Eine Lösung ist besser, je näher die Summe der Ziffern von SEND und MORE an MONEY ist. D. h.:
Feststellung: Das Ziel des generischen genetischen Algorithmus ist es, die Fitness-Funktion zu maximieren. Wir müssen somit unser Minimierungsproblem in ein Maximierungsproblem umwandeln:
Beispiel: Sei die Differenz \(1\), dann ist die Fitness \(1/2\); bei einer Differenz von \(0\) ist die Fitness \(1\) und somit maximal.
Fitness-Funktion - Implementierung
1def fitness(self) -> float:2s: int = self.letters.index("S")3e: int = self.letters.index("E")4n: int = self.letters.index("N")5d: int = self.letters.index("D")6m: int = self.letters.index("M")7o: int = self.letters.index("O")8r: int = self.letters.index("R")9y: int = self.letters.index("Y")10send: int = s * 1000 + e * 100 + n * 10 + d11more: int = m * 1000 + o * 100 + r * 10 + e12money: int = m * 10000 + o * 1000 + n * 100 + e * 10 + y13return 1 / (abs(money - (send + more)) + 1)
Initialisierung
1initial_population: list[SendMoreMoney] = \2[SendMoreMoney.random_instance() for _ in range(1000)]3ga: GeneticAlgorithm[SendMoreMoney] = \4GeneticAlgorithm(5initial_population=initial_population,6threshold=1.0,7max_generations = 1000,8mutation_chance = 0.2,9crossover_chance = 0.7,10selection_type= \11GeneticAlgorithm.SelectionType.ROULETTE)12result: SendMoreMoney = ga.run()13print(result)
Exemplarische Ausführungen zeigt stochastische Natur
1. Lauf (237 Generationen)
Generation 0 Best 0.03333333333333333 Avg 0.0001322689088530895 ︙ Generation 236 Best 0.5 Avg 0.26552306542712417 9567 + 1085 = 10652 Difference: 0
2. Lauf (2 Generationen)
Generation 0 Best 0.025 Avg 0.0001658511923601707 Generation 1 Best 0.3333333333333333 Avg 0.003446183841665406 7429 + 814 = 8243 Difference: 0
3. Lauf (4 Generationen)
Generation 0 Best 0.006896551724137931 Avg 0.00012684576568285674 ︙ Generation 3 Best 0.5 Avg 0.01426133638316889 5731 + 647 = 6378 Difference: 0
Gruppenzuteilung
Entwickeln Sie einen genetischen Algorithmus, der eine sehr gute Aufteilung von Personen (Studierenden) auf eine feste Anzahl an Gruppen findet, basierend auf den Präferenzen der Personen.
Im Template ist eine initiale Aufgabenstellung hinterlegt, die es zu lösen gilt: Verteilung von 16 Studierenden auf 4 Gruppen inkl. Bewertungsmatrix (jeder Studierende hat jeden anderen mit Werten von 1 bis 10 bewertet).
Basis (Achten Sie auf die Verzeichnisse)
https://delors.github.io/theo-algo-genetic_algorithms/code/lib/chromosome.py
https://delors.github.io/theo-algo-genetic_algorithms/code/lib/genetic_algorithm.py
https://delors.github.io/theo-algo-genetic_algorithms/code/group_assignment_template.py
Denken Sie daran, dass Sie die Parameter bzgl. mutation_chance, crossover_chance, selection_type, initial_population und max_generations anpassen können.
Sie können für die Darstellung der Mitglieder einer Gruppe auch eine andere Darstellung als eine Liste von Listen verwenden. Sie müssen dann nur ggf. auch die __str__ Methode anpassen. Es steht Ihnen natürlich auch frei Konzepte wie Memoization zu verwenden, um die Fitness-Funktion zu beschleunigen.
Sieger ist, wer in einem akzeptablen Zeitrahmen (3 Minuten) die beste Lösung findet.
Ausgeglichene Gruppenzuteilung
Passen Sie Ihren genetischen Algorithmus aus der vorherigen Übung so an, dass die Gruppen alle in etwa die gleiche Glücklichkeit aufweisen. D. h. eine Zuteilung, bei der die Gruppenglücklichkeiten z. B. 92 + 91 + 73 + 89 = 345 sind, die aber größere Unterschiede zwischen den Gruppen hat, sollte vermieden werden. Eine Verteilung z. B. mit den Gruppenglücklichkeiten: 80, 84, 80, 80 = 324 sollte bevorzugt werden.