Schönen guten Morgen. Nachdem wir jetzt beim letzten Mal das Hauptaugenmerk darauf gelegt hatten,

wie man was beweist bei genetischen Algorithmen, ist es heute so, dass wir eben nicht mal dem

Spielbeispiel des Sortierens uns genetische Algorithmen anschauen wollen, sondern halt

wirklich an einem ganz normalen kombinatorischen Problem, nämlich dem Rundreiseproblem.

Und das, was wir uns da bei uns anschauen wollen, ist eben jetzt, dass wir wirklich

mal so einen Evolutionsprozess nachahmen.

Wir hatten ja noch bei dem Sortieren nicht, dass wir eine Elternpopulation hatten, die

dann Nachkommen generiert hat, sondern wir haben halt ausschließlich ein Individuum

gehabt, das dann halt mutiert wurde.

Jetzt wird halt auch weiter geschaut, dass man halt sozusagen zwei Eltern nimmt, aus

den beiden Eltern ein neues Individuum kreiert und dann halt den besten von all denen nimmt.

Also das, was man da dann halt als Oberbegriff sieht, ist dann halt das Survival of the fittest.

Ja, das, was wir uns anschauen wollen, ist ja auch schon ein uns bekanntes Problem, nämlich

das Rundreiseproblem.

Da ist halt gegeben ein Graf, Sie sehen es hier, ein sehr komplizierter Graf, nur vier

Knoten.

Der Graf ist kantengewichtet und so, wie wir es jetzt an der Stelle uns vorstellen, ist

es so, dass alle mit allen verbunden sind.

Wir werden am Ende nochmal dann schauen, wie wir damit umgehen, wenn nicht alle mit allen

verbunden sind, sondern wir einen ganz normalen Graf nahmen, wo ein paar Knoten mit ein paar

anderen verbunden sind, die wieder mit ein paar anderen verbunden sind und so weiter.

Da ist es halt so, dass man dann halt sagt, ja, die sind auch wieder alle untereinander

verbunden, aber die, wo wir keine direkte Kante haben, die sind halt über den kürzesten

Weg über schon vorhandene Knoten verbunden und wenn wir jetzt dann eine Rundreise haben,

dann werden eben doch Knoten doppelt besucht, aber beim zweiten Mal fahren wir einfach auf

der Umgehungsstraße an dem Ort vorbei.

So haben wir dann eben doch wieder einen vollständigen Grafen und wir ignorieren dann, dass wir

dann Knoten nochmal besuchen, sondern wie gesagt, wir fahren einfach an der Stadt dann vorbei.

Also das ist das, was die Eingabe ist und gesucht ist eben, wie wir das bei den Ameisen

ja auch schon hatten, eine kürzeste Rundreise da drauf und ja, jetzt nehmen wir mal alles,

was wir schon gelernt haben.

Also wir müssen uns jetzt überlegen, wie wir eine Rundreise da drauf codieren.

Das hatten wir ja schon als Genotyp bezeichnet, also ein Genotyp für eine Rundreise ist jetzt,

wenn wir bei der Mutation hinschreiben und zwar so, da wo wir starten, wir starten jetzt

hier beim Knoten 1 und dann haben wir den Scham 1, 3, 4, 2, dann ist halt unsere Rundreise

1, 3, 4, 2 und dann müssen wir wieder zurück und das ist dann halt das, was wir ausgeben

und die Länge der Rundreise ist dann natürlich das, was an den Kanten steht, also 1, 3 hat

die Länge 2, dann 3, 4 hat die Länge 10, also bisher haben wir 12 zurückgelegt, wenn

wir dann nach oben gehen 14 und nochmal 2 sind dann 16.

Das wäre also eine Rundreise der Länge 16 und unser Ziel ist es, eine kürzeste Rundreise

zu machen.

An der Stelle sage ich auch immer ganz gerne, natürlich könnte man es genauso gut formulieren

als längste Rundreise, da ist dann eben das, was hier an den Kanten dran steht, nicht so

Kilometer, sondern da ist das dann Gewinn.

Also wenn ich zuerst nach da fahre und dann nach da, dann ist der Gewinn halt 10 und wenn

ich hier langfahre, ist dann der Gewinn nur 4, also auch das Problem an der längste Rundreise

zu finden ist ein interessantes Problem, aber es ist von der Komplexität her genauso

schwierig, also das Entscheidungsproblem dazu ist halt NP-vollständig, das heißt wir werden

ganz sicher keinen, ganz sicher sollte man nie sagen, wir werden vermutlich keinen Polynomenzeit-Algorithmus,

einen schnellen Algorithmus für das Rundreiseproblem angeben können, der auch wirklich die beste