Einführung in das Verfahren

Nachdem wir das Problem des Handlungsreisenden kennengelernt haben, wollen wir nun genetische Algorithmen als allgemeine Lösungsverfahren vorstellen. Dabei werden wir bewusst stets das Problem des Handlungsreisenden als Beispiel verwenden.

Grundsätzlich handelt es sich bei genetischen Algorithmen um spezielle Optimierungsverfahren, bei denen auch der Zufall eine zentrale Rolle spielt. Die Funktionsweise der Verfahren orientiert sich dabei an der Evolutionstheorie.

Populationen

Bei genetischen Verfahren wird stets eine sogenannte Population betrachtet: Dabei handelt es sich um eine gewisse Anzahl an Lösungskandidaten, also beim Beispiel des Handlungsreisenden um eine gewisse Anzahl an Permutationen. Allen Permutationen bzw. Lösungskandidaten kann eine gewisse Güte bzw. Qualität zugewiesen werden, nämlich genau die Länge der zugehörigen Rundtour.

In Anlehnung an die Evolutionstheorie spricht man bei Lösungskandidaten genetischer Verfahren auch von Individuen sowie bei der zugehörigen Güte bzw. Qualität von der Fitness. Die folgende Tabelle zeigt eine Population bestehend aus sechs Individuen bezüglich eines Handlungsreisenden mit acht Orten:

IndividuumFitness
(5, 2, 6, 4, 3, 7, 1, 8)123,4
(5, 8, 3, 4, 7, 2, 1, 6)198,0
(8, 6, 4, 7, 3, 2, 1, 5)153,8
(2, 1, 3, 7, 8, 6, 5, 4)164,3
(2, 5, 7, 6, 4, 3, 8, 1)112,4
(6, 7, 4, 3, 5, 8, 1, 2)175,1

Wir führen damit direkt einen ersten Parameter genetische Verfahren ein:

Populationsgröße, d.h. Anzahl der Individuen pro Generation

Die Vorgehensweise, die wir in den nächsten Abschnitten genauer vorstellen werden, ist folgende: Aus den Individuen einer Population (bzw. Generation) werden Kinder erzeugt und die zugehörige Fitness bestimmt. Schließlich überleben die Individuen mit der besten Fitness, wobei die Populationsgröße von Schritt zu Schritt bzw. Generation zu Generation stets identisch bleibt.

Quiz

In dieser Aufgabe untersuchen wir das Problem des Handlungsreisenden, wobei die folgenden acht Orte zu besuchen sind:

Hinweis zur Skalierung: Der Abstand zwischen den Orten 4 und 6 ist exakt 2 und der Abstand zwischen den Orten 2 und 7 ist exakt 5.

Was ist die Fitness des Individuums (7, 5, 8, 2, 1, 4, 6, 3)?
8
10
16
18
26
28
36
Was ist die Fitness des Individuums (4, 2, 7, 3, 1, 5, 8, 6)?
8
10
16
18
26
28
36
Nachfolgende Generationen