Kurs:Genetische Algorithmen/Kapitel 1

Dieses Kapitel gehört zum Kurs Genetische Algorithmen des Fachbereichs Informatik.

Übersicht

In diesem ersten Kapitel führen wir das Konzept eines Optimierungsproblems ein. Obwohl es vom Namen her wie etwas Neues aussieht, ist es etwas, was uns schon mehrmals im Leben über den Weg gelaufen ist. Anhand dieser Beispiele aus dem Alltag zeigen wir, was wir unter einem Optimierungsproblem verstehen. Im Laufe des Kapitels werden wir uns einige klassische Optimierungsprobleme anschauen und uns mit den gängigen Begriffen bekannt machen.

Lernziele

• Sie können Ihren Freunden erklären, was ein Optimierungsproblem ist.
• Sie wissen, was eine Zielfunktion ist und was sie bei Optimierungsproblemen für eine Rolle spielt.
• Sie bekommen ein neues Konzept der Definition einer Lösung, welche die klassische Definition aus der Mathematik ergänzt.
• Sie können sowohl Lösungen als auch ihre Repräsentation für Optimierungsprobleme formulieren.

Einleitung

Eigentlich will jeder/jede am Morgen so lange wie nur möglich ausschlafen. Wie lange man schlafen kann hängt, zu einem grossen Teil, von der Dauer des Arbeitsweges (in unserem Falle des Schulweges) ab -- je kürzer der Weg, desto länger kann man im Bett bleiben.

Die Menge der möglichen Schulwege ist schier unbegrenzt. Abgesehen von der scheinbar unendlich grossen Anzahl Kombinationen von Straßen und Fußwegen, die man nehmen könnte, um zur Schule zu gelangen, kommt noch hinzu, dass wir auch für gewisse Strecken das Verkehrsmittel wechseln können. So können wir mit dem Fahrrad zum Bahnhof radeln, vom Bahnhof in die Stadt den Zug nehmen, um dann von dort aus mit dem Tram zur Schule zu fahren. Die gleiche Strecke könnten wir auch nur zu Fuss oder nur mit dem Fahrrad absolvieren, wobei das schnellere Fahrzeug nicht unbedingt die kürzere Reisezeit garantiert: Züge, Busse und Trams fahren nach vorgegebenen Fahrplänen und nach vorgegebenen Destinationen, die nicht unbedingt genau dort liegen, wo man eigentlich hin will. Bei persönlichen Motorfahrzeugen (Auto, Töff, etc...) hängt die Reisezeit von der Verkehrslage ab, welche wiederum von der Tageszeit abhängig ist. Das schnellere Verkehrsmittel ist also nicht unbedingt das Beste, was die Bestimmung des schnellsten Weges bedeutend erschwert.

Dieses Problem nennt man ein Optimierungsproblem.

Genetische Algorithmen/Kapitel 1

Bei einem Optimierungsproblem geht es darum, die beste Lösung zu finden. Diese Lösung unterscheidet sich von der klassischen Definition einer Lösung, die wir aus der Mathematik kennen. Für Optimierungsprobleme ist eine Lösung ein Satz von Werten, welche das Problem erfüllen (zum Beispiel bilden sie einen Weg von Zuhause zur Schule und nicht zum Zoo). Wir suchen nun nicht einfach eine Lösung, sondern die beste Lösung.

Aufgabe:

Diskutieren Sie mit Ihrem Nachbarn und überlegen Sie sich, worin sich die Lösungen eines Optimierungsproblems -- zum Beispiel die verschiedene Schulwege -- von Lösungen mathematischer Probleme unterscheiden. Gibt es in der Mathematik auch Probleme, die mehrere, unterschiedliche Lösungen haben können?

Die Güte einer Lösung wird durch die sogenannte Zielfunktion gegeben.

Definition:

Die Zielfunktion drückt die Güte der Lösung in einer Zahl aus. Ist eine Lösung besser als eine andere, so unterscheiden sich auch deren Bewertungen durch die Zielfunktion.

Je nach Aufgabe werden Lösungen gesucht, welche die Zielfunktion minimieren oder maximieren.

Genetische Algorithmen/Kapitel 1

Definition:

Eine Lösung ist eine Menge von Werten, welche den Unbekannten eines Problems (oder dessen Zielfunktion) zugewiesen werden.

Diese Werte können ganze oder reelle Zahlen, Buchstaben eines bestimmten Alphabets oder auch abstraktere Sachen wie Reihenfolgen sein.

Allgemein sagt man für die Lösung eines Optimierungsproblems, dass die Zielfunktion über die Unbekannten optimiert (sprich minimiert oder maximiert) wird.

In unserem Beispiel ist eine Lösung eine Kombination von Strecken und Verkehrsmitteln, die zur Schule führen. Die zu optimierende (sprich minimierende) Zielfunktion ist die Zeit, welche für den Weg nötig ist.

Beispiel:

Die unterschiedlichen Lösungen können wir als Liste von Teilstrecken systematisch darstellen, wie zum Beispiel:

1. Von Zuhause bis zum Bahnhof mit dem Fahrrad.
2. Vom Bahnhof bis zum Hauptbahnhof mit der S-Bahn.
3. Vom Hauptbahnhof bis zum Schulhaus mit dem Tram.

Im Folgenden werden wir drei weitere Beispiele von Optimierungsproblemen anschauen:

Problem des Handlungsreisenden

Ein Handelsreisender muss, seines Geschäftes wegen, 6 Städte besuchen. Die sechs Städte, Aarau, Bern, Chur, Dübendorf, Emmen und Fribourg, haben verschiedene Distanzen zueinander, die auf der folgenden Tabelle abgelesen werden können.

von/nach	A	B	C	D	E	F
A	0	65	127	43	38	94
B	65	0	157	100	62	29
C	127	157	0	92	98	181
D	43	100	92	0	31	117
E	38	62	98	31	0	90
F	94	29	181	117	90	0

Aus Kostengründen muss unser Handelsreisende den kürzesten Weg finden, der alle 6 Städte verbindet und ihn zu seinem Anfangsort zurückführt. Zudem darf er jede Stadt nur einmal durchreisen.

Es gibt nur 60 unterschiedliche Wege, die 6 Städte zu durchreisen. Bei 10 Städten sind es jedoch schon 181'440, bei 100 Städten gar $4.66\times 10^{155}$. Es ist also nicht immer möglich, alle Wege auszuwerten und den besten herauszupicken.

	$ABCDEF$:	$65+157+92+31+90+94=529$
	$AEDCFB$:	$38+31+92+181+29+65=436$
	$AFBECD$:	$94+29+62+98+92+43=418$

Das Problem, die kürzeste Strecke zu finden, lässt sich als Optimierungsproblem formulieren. Die Zielfunktion, die es zu minimieren gilt, ist die Gesamtstrecke zwischen den sechs Städten, die anhand der Tabelle errechnet werden kann. Die verschiedenen Lösungen sind die verschiedenen Reihenfolgen, in denen die Städte besucht werden können (vgl. Abbildung oben).

Aufgabe:

Als Darstellung der Lösungen wählen wir eine Liste mit den Anfangsbuchstaben jeder Stadt. Gegeben der Distanztabelle weiter oben im Text, berechnen Sie die Länge folgender Wege durch alle Städte und zurück zum Ausgangsort:

1. BCAFED
2. FEDCBA
3. AFBECD
4. DCBAFE

Das Problem des Handlungsreisenden wurde schon Mitte 1800 vom berühmten Mathematiker William Rowan Hamilton beschrieben und 1930 von Karl Menger formalisiert. Seitdem erfreut es sich grosser Beliebtheit als Musterproblem für Optimierungsverfahren, da es bisher unmöglich ist, die beste Lösung zu finden, ohne alle möglichen Lösungen auszuprobieren. In der Praxis können Probleme mit bis zu 25'000 Städten exakt gelöst werden, der dafür erforderliche Rechenaufwand ist jedoch enorm. In der Praxis ist die Lösung solcher Probleme nicht nur für Handelsreisende interessant, sondern auch für den Entwurf von Schaltkreisen oder Computernetzwerken von Bedeutung.

Das Klassifikationsproblem

Können wir anhand von Grösse und Gewicht entscheiden, ob jemand eher ein Mann oder eine Frau ist? Zeichnen Sie die Körpergrösse und das Gewicht aller Männer und Frauen ihrer Klasse auf. Welche Gerade

$g(x)=ax+b$

teilt die Punktmenge am besten?

Klassifikation mit der Lösung $g(x)=0.2x+35$ und 3 Fehlern.

Eine Lösung ist ein Wertepaar für $a$ und $b$, die Unbekannten der Funktion $g(x)$.

Die Zielfunktion ist die Anzahl Punkte (Personen), die durch die Funktion $g(x)$ falsch eingeteilt wurden (vgl. Abbildung oben).

Aufgabe:

Wie können wir erkennen, ob ein Punkt $(x,y)$ oberhalb oder unterhalb der Geraden $g(x)=0.2x+35$ liegt? Wie würden Sie eine Person mit 60 kg und 140 cm klassifizieren? Auf welcher Seite der Geraden liegt jemand mit 50 kg und 170 cm?

Eine solche Klassifikation kann von Nutzen sein, wenn zum Beispiel ein neuer Mitschüler oder eine neue Mitschülerin der Klasse beitritt, dessen Grösse und Gewicht, nicht aber dessen Geschlecht, bekannt sind. Trägt man besagten Mitschüler oder Mitschülerin in den Grafen ein, kann man anhand dessen Position relativ zur Geraden $g(x)$ schätzen, ob es sich um einen Kommilitonen männlichen oder weiblichen Geschlechts handelt.

Derartige Klassifikationen sind in der Biologie von sehr grosser Bedeutung, wenn es darum geht, Tier- oder Zellarten anhand von bestimmten erfassten Kriterien zu unterscheiden. Zum Beispiel können wir so verschiedene Zelltypen oder Mikroorganismen anhand ihrer Geschwindigkeit und Wendigkeit voneinander unterscheiden, ohne sie unter einem Mikroskop genauer anzuschauen. So lassen sich auch auf Satellitenbildern verschiedene Erntetypen auf Feldern anhand von Farbe, Dichte und Stärke des Bildrauschens unterscheiden.

Das Damenproblem

Können sechs Damen auf einem $6\times 6$ grossen Schachbrett so positioniert werden, dass sie sich gegenseitig nicht schlagen können? Laut den Schachregeln kann eine Dame jede Figur schlagen, die sich auf der gleichen Höhe, Breite oder Diagonale befindet.

Eine mögliche Lösung des Damenproblems mit 3 Kollisionen.

Für unser $6\times 6$ Feld existieren, wenn in jeder Spalte genau eine Dame steht, 46'656 verschiedene Lösungen, wobei nur 4 davon 0 Kollisionen haben. Auf einem normalen $8\times 8$ grossen Schachbrett existieren 16'777'216 Lösungen, wobei nur gerade mal 92 keine Kollisionen enthalten. Auf einem $12\times 12$ grossen Feld gibt es zwar 14'200 kollisionsfreie Lösungen, die müssen jedoch aus 8'916'100'448'256 möglichen anderen Lösungen gefunden werden.

Wir formulieren die Zielfunktion als die Anzahl Kollisionen zwischen den Damen. Da diese möglichst null sein sollte, handelt es sich um eine Minimierung. Die Lösungen der Zielfunktion sind die Positionen der sechs Damen (vgl. Abbildung oben). Um zu vermeiden, dass sich die Damen gegenseitig auf die Schuhe stehen, platzieren wir jede in einer Spalte. Die Unbekannten sind dann die Reihen jeder Dame.

Beispiel:

Die Lösung in der Abbildung oben können wir also wie folgt darstellen:

$[1,3,5,4,2,5]$

Die Dame in der ersten Spalte steht auf dem ersten Feld, die Dame in der zweiten Spalte auf dem dritten Feld, die Dame in der dritten Spalte auf dem fünften Feld, usw...

Wir beachten bei diesem Optimierungsproblem, dass wir im Gegensatz zu den zwei vorhergehenden Beispielen nun eine Fragestellung mit nur einer Lösung ("Können sechs Damen auf einem $6\times 6$ grossen Schachbrett...") haben. Wir können es aber trotzdem als Optimierungsproblem formulieren, indem wir eine Zielfunktion wählen, die falsche Lösungen nach ihrer Falschheit unterscheidet. Auf diese Art und Weise lassen sich viele Probleme als Optimierungsprobleme formulieren.

Erstmals formuliert wurde das Damenproblem von dem bayrischen Schachmeister Max Bezzel Mitte 1800 -- in der Berliner Schachzeitung fragte er 1848 nach der Anzahl der möglichen Lösungen auf einem $8\times 8$ Brett. Auch Carl Friedrich Gauss, der berühmte Mathematiker, zeigte Interesse an dem Problem, weshalb es irrtümlich häufig auf ihn zurückgeführt wird. Als erster nannte 1850 Dr. Franz Nauck die korrekte Zahl 92. 1874 bewies der englische Mathematiker James Whitbread Lee Glaisher, dass es nicht mehr Lösungen geben konnte. Damit war das Problem vollständig gelöst. Nauck verallgemeinerte die Problemstellung für ein beliebiges $n\times n$-Schachbrett und erst 1991 wurde von B. Bernhardsson eine explizite Lösung des N-Damenproblems für jede beliebige Brettgrösse angegeben.

Lernkontrolle

1. Was sucht man bei einem Optimierungsproblem?
2. Wie bewertet man die Güte einer Lösung?
3. Ein GPS-System löst das Optimierungsproblem, die kürzeste Strecke im Straßennetz zwischen zwei Orten zu finden. Machen Sie einen Vorschlag, wie die verschiedenen Lösungen dieses Problems dargestellt werden können.
4. Bei allen bis jetzt vorgestellten Beispielen handelt es sich um Minimierungen. Was müssen Sie beachten, wenn Sie anstatt etwas zu minimieren etwas maximieren wollen?

Kapiteltest

Die schulische Leistung eines jeden Schülers und einer jeden Schülerin hängt von vielen Faktoren ab, nicht zuletzt von der eigenen Freizeitplanung. Je mehr Zeit man mit Lernen verbringt, desto besser wirkt sich dies auf die schulische Leistung aus. Dies geht natürlich auf Kosten von Sport und Schlaf. Verbringt man zu wenig Zeit mit dem Schlafen, so hat dies oft negative Auswirkungen auf die Konzentration und darum auch auf die Leistung. Ähnlich ergeht es denjenigen, die zu wenig Zeit in die sportliche Betätigung investieren: Vor lauter Lernen und Schlafen leidet die Gesundheit und vermindert somit die Leistungsfähigkeit.

Formulieren Sie ein Optimierungsproblem, in dem die schulische Leistung über die Zeiteinteilung optimiert wird. Was wäre dabei die Zielfunktion? Was wäre eine Lösung?

Lösungen

Lernkontrolle

1. Wir suchen die beste Lösung, d.h.~die Lösung, welche für die Zielfunktion den höchsten oder tiefsten Wert liefert.
2. Die Güte bewerten wir mittels der Zielfunktion.
3. Das GPS-System könnte eine Liste von Kreuzungen, welche auf dem Weg durchfahren werden, erzeugen und bei jeder anmerken, wo man abbiegen muss.
4. Wir suchen nicht die Lösung, welche den tiefsten Wert der Zielfunktion ergibt, sondern deren höchsten Wert.

Kapiteltest

Wir definieren die Zielfunktion als den Notendurchschnitt des Schülers oder der Schülerin. Diese Zielfunktion gilt es zu maximieren. Eine Lösung ist eine Aufteilung der 24 Stunden eines Tages in Lernen, Sport und Schlaf.