Lösung mit einem genetischen Algorithmus

Der Natur eine Lösungsstrategie abschauen

Wie optimiert die Natur die Anpassung von Lebewesen an Umweltbedingungen? Evolution spielt in den Erklärungsmodellen der Biologen eine wesentliche Rolle. Was Evolution ist, wird im folgenden kurzen Auszug aus dem Wikipedia-Artikel (vgl. Wikipedia - Evolution) erklärt:

Evolution ist die Veränderung der vererbbaren Merkmale einer Population von Lebewesen von Generation zu Generation. Diese Merkmale sind in Form von Genen kodiert, die bei der Fortpflanzung kopiert und an den Nachwuchs weitergegeben werden. Durch Mutationen entstehen unterschiedliche Varianten (Allele) dieser Gene, die veränderte oder neue Merkmale verursachen können. Diese Varianten sowie Rekombinationen führen zu erblich bedingten Unterschieden (Genetische Variabilität) zwischen Individuen. Evolution findet statt, wenn sich die Häufigkeit dieser Allele in einer Population (die Allelfrequenz) ändert, diese Merkmale in einer Population also seltener oder häufiger werden. Dies geschieht entweder durch Natürliche Selektion (unterschiedliche Überlebens- und Reproduktionsrate aufgrund dieser Merkmale) oder zufällig durch Gendrift.

In der Informatik werden Elemente der Evolution übernommen und zu einer Strategie zum näherungsweisen Lösen von Optimierungsproblemen ausgebaut. Wir werden diese Strategie im Folgenden zur Lösung des Rucksackproblems erläutern.

Die Population und ihre Individuen

Zur Lösung des Rucksackproblems kommen eine Vielzahl an Lösungskandidaten in Frage.

In dem durch die Abbildung gezeigten konkreten Fall wird ein möglicher Lösungskandidat durch eine Auswahl an Gegenständen gegeben, z.B. durch die Gegenstände 0, 2, 3, 4, 5, 8.

Wir stellen Lösungskandidaten durch 0-1-Zeichenketten dar. Der Lösungskandidat, der durch die Gegenstände 0, 2, 3, 4, 5, 8 festgelegt wird, wird beispielsweise in der Form '1011110010' dargestellt.

Lösungskandidaten sind die Individuen der Population. Eine Population zum Rucksackproblem besteht demnach aus einer Menge von Lösungskandidaten. In der Regel gibt man die Größe der Population (d.h. die Anzahl der Individuen) fest vor.

Die Nullen und Einsen in einer 0-1-Zeichenkette zur Darstellung eines Individuum / Lösungskandidaten (wie z.B. '1011110010') interpretieren wir als Gene, die 0-1-Zeichenfolge als Gencode des Individuum.

Die folgende Population zum Rucksackproblem besteht aus 8 Individuen, die alle über ihre Gene eine bestimmte Kombination möglicher Gegenstände beschreiben. Beachte, dass zwei Individuen auch dieselben Gene haben können und somit auch dieselbe Kombination an Gegenständen erfassen können.

'1011110010'
'0000110010'
'1011010111'
'1000010010'
'1010010010'
'1011110111'
'1011110010'
'1010111000'

Fitness von Individuen

Wie im wirklichen Leben sind in der Regel nicht alle Individuen gleich gut an die Umweltsituation angepasst: Manche sind fitter in dem Sinne, dass sie mit den Umweltbedingungen besser zu Rande kommen als andere Individuen. Die Fitness hat Auswikungen auf die Weitergabe von Merkmalen an folgende Generationen der Population.

Die Fitness von Lösungskandidaten beim Rucksackproblem wird so modelliert, das sie die Qualität der Lösung beschreibt. Die Qualität eines Lösungskandidaten wird durch die Summe der Werte der Gegenstände gegeben. Je höher dieser Gesamtwert der Gegenstände, desto größer ist die Qualität des Lösungskandidaten, vorausgesetzt, der Gesamtwert bleibt unter der Kapazitätsgrenze des Rucksacks.

Wir legen daher die Fitness eines Lösungskandidaten beim Rucksackproblem wie folgt fest. Wenn die Summe der Werte der ausgewählten Gegenstände die Kapazitätsgrenze des Rucksacks nicht übertrifft, so wird dieser Gesamtwert als Fitnesswert des Lösungskandidaten angesehen. Ansonsten soll der Fitnesswert des Lösungskandidaten 0 betragen.

Aufgabe 1

Bestimme die Fitness der Individuen der folgenden Population unter Berücksichtigung der Vorgaben, die durch das konkrete Rucksackproblem (siehe Abbildung oben) gegeben sind. Welches Individuum ist am fitesten?

'1011110010'
'0000110010'
'1011010111'
'1000010010'
'1010010010'
'1011110111'
'1011110010'
'1010111000'

Fortpflanzung der Population

Eine Population ist ein dynamisches System, die durch immer wieder neue Generationen von Individuen gebildet wird.

Bei der Suche nach möglichst guten Näherungslösungen für ein Optimierungsproblem mit Evolutionsstrategien spielt die Fortpflanzung der Population eine entscheidende Rolle. Ziel ist es, die Population so weiterzuentwickeln, dass die Fitness der Individuen bzw. die Qualität der Lösungskandidaten zunimmt, so dass eine möglichst gute Näherungslösung zum Optimierungsproblem erzielt wird.

Wir werden die Fortpflanzung so realisieren, dass in jedem Schritt eine Population komplett ersetzt wird durch die Nachkommen der Individuen der Population.

Kreuzung

Die Fortpflanzung von Individiuen soll durch Kreuzung von zwei Lösungskandidaten realisiert werden. Hierzu wird zunächst eine zufällige Stelle im Gencode bestimmt (z.B. die Stelle 7). Die Genabschnitte der beiden Individuen werden jetzt (über Kreuz) neu kombiniert. Der 1. Abschnitt des ersten Individuums wird mit dem 2. Abschnitt des zweiten Individuums zusammengesetzt, ebenso der 2. Abschnitt des ersten Individuums mit dem 1. Abschnitt des zweiten Individuums:

'1011110|010'   '0000110|000'

'1011110|000'   '0000110|010'

Auf diese Weise entstehen aus zwei gegebenen Individuen zwei neue Individuen.

Selektion

Welche Individuen sollen zur Fortpflanzung beitragen? Selektion führt dazu, dass eine Bevorzugung bestimmter Individuen bei der Fortpflanzung durch die Berücksichtigung der Fitness der Individuen stattfinden.

Wir realisieren eine Fortpflanzung mit Selektion wie folgt: Aus der Population sollen zwei Eltern-Individuen ermittelt werden. Für jedes Elternteil werden zwei Kandidaten per Zufall aus der Population ausgewählt. Jetzt kommt die Fitness ins Spiel: Der fitere der beiden Kandidaten kommt zum Zug, der andere hat das Nachsehen. Aus den beiden fiteren Kandidaten werden jetzt durch Kreuzung die beiden Nachkommen erzeugt.

Aufgabe 2

Die folgende Population (zum konkreten Rucksackproblem oben) dient als Ausgangspopulation.

'1011110010'
'0000110010'
'1011010111'
'1000010010'
'1010010010'
'1011110111'
'1011110010'
'1010111000'

(a) Ermittle mit einem geeigneten Zufallsgenerator (z.B. Python) die nächste Generation der Population: Es sollen also solange Eltern per Zufall und mit Selektion ausgewählt und deren Nachkommen per Kreuzung erzeugt werden, bis die Populationsgröße der Nachkommen der Populationsgröße der Eltern entspricht (also insgesamt 4 mal).

(b) Bestimme die Fitness der Individuen der neuen Generation. Hat sich eine Qualitätssteigerung ergeben?

Mutation

Eine Mutation ist eine Veränderung des Gencodes eines Individuums. Sie kann positive, negative oder auch gar keine Auswirkungen auf die Eigenschaften des Individuum haben. Sie kommt spontan oder auch durch äußere Einflüsse zustande.

Ohne Mutation würden die Individuen durch Kreuzung immer nur ihre Anfangs- und Endabschnitte austauschen. Auf diese Weise könnte es vorkommen, dass bestimmte gute Näherungslösungen gar nicht erzeugt werden können. Mutation bringt hier Bewegung ins Spiel. Indem einzelne Gene per Zufall abgeändert werden, können völlig neue Lösungskandidaten erzeugt werden. Das kann sich positiv, aber natürlich auch negativ auf die Qualität der Lösung auswirken.

Wir realisieren Mutation, indem ein Gen per Zufall ausgewählt und abgeändert wird.

'1011110|0|10'

'1011110|1|10'

Diesen Vorgang führen wir nur ab und zu (mit einer bestimmten Mutationswahrscheinlichkeit) bei einem neu generierten Individuum aus.

Algorithmus

Das gesamte Verfahren lässt sich mit dem folgenden Algorithmus beschreiben.

ALGORITHMUS loesung mit genetischem Algorithmus 
    erzeuge eine initiale Population
    SOLANGE das Abbruchkriterium nicht erfüllt ist:
        lege eine neue Population an
        SOLANGE die Populationsgröße nicht erreicht ist:
            wähle durch Selektion 2 Individuen aus
            erzeuge 2 neue Individuen durch Kreuzung der Individuen
            verändere die Gensequenz der neuen Individuen durch Mutation
            nimm die neuen Individuen in die neue Population auf
        ersetze die alte durch die neue Population
    bestimme das Individuum mit maximaler Fitness

Beachte, dass der Algorithmus keinen Bezug auf das Rucksackproblem nimmt. Er kann also auch bei anderen Optimierungsproblemen benutzt werden, sofern geeignete Realisierungen der Gen-Codierung, Selektion, Kreuzung und Mutation gefunden werden.