WS23_AKIDS1: Genetic Algorithm Selection

Hallo,

ich bräuchte kurz Hilfe beim Genetic Algorithmus für DCO. Wie genau würden wir die Roulette Wheel Strategy anwenden bei unserem Pseudocode?

Wir haben 2 Populationen nach dem Pseudocode p und p'. Mit Selection wollen wir eine neue Population erstellen, z.B q.
Müssten wir ein großes Roulette Wheel erstellen, wo sowohl p als auch p' Chromosome repräsentiert werden, oder wählen wir Chromosome aus p z.B p1, p5 und die restlichen entnehmen wir dann aus der Population p' (p'2, p'3, p'4 entsprechend)? Oder verfolgen wir eine andere Strategie?
Die Quellen, die ich gefunden habe, wenden Roulette Wheel vor recombination an, sodass wir p halbieren und dann die fehlende Hälfte erzeugen und mutieren. Sind da beide Herangehensweisen gleichwertig, oder gibt es einen bestimmten Grund, warum in der Vorlesung die Selection aus p und p' bevorzugt wird.

Danke und schönes Wochenende noch.

image%20%281%29.png

Re: Genetic Algorithm Selection

от Goran Glavaš - вторник, 6 февраля 2024, 14:26

Hi Antoni,

Grundsätzlich gibt es verschiedene Varianten der Selektionsstrategie und unterschiedliche Wege, wie diese tatsächlich umgesetzt werden kann.

Aber so wie unser Pseudocode geschrieben ist, gehen wir von Folgendem aus:

> In einer Iteration beginnen wir mit der Population p mit N Chromosomen

> Wir führen die Rekombination (die "recombine" Funktion) durch und erzeugen neue Chromosomen p' (nicht genau spezifiziert, aber wir nehmen auch N an). Für die Rekombination müssen wir die Eltern "auswählen", d.h. hier würde man eigentlich das Rhoulette-Rad oder die Turnierauswahl anwenden.

> Im letzten Schritt müssen wir die Population (p U p'), die 2N Chromosomen hat, auf N Chromosomen zurückführen (die "select" Funktion). Dazu können wir z.B. auch die Rhoulette-Rad-Auswahl verwenden (N-mal, um N aus 2N Chromosomen für die nächste Iteration auszuwählen).

Die von Ihnen erwähnte Variante, bei der N/2 der Population entfernt wird (z. B. über die Rhoulette-Rad-Auswahl) und dann das neue N/2 durch Rekombination der verbleibenden N/2 Chromosomen erhalten wird, ist ebenfalls üblich und gültig. Wie gesagt, es gibt viele mögliche Varianten: Wichtig ist, dass es eine Abfolge von Schritten gibt, die im Allgemeinen dazu führt, dass die nachfolgenden Populationen "besser" sind (eine bessere durchschnittliche Fitness haben) als die vorherigen.

VG,

Goran