Wir sind jetzt dabei, einen Sortieralgorithmus uns anzugucken, der schon ein bisschen exotisch ist.

Nämlich, wir wollen sortieren mit Hilfe eines evolutionären Algorithmus.

Wir haben beim letzten Mal ja schon die beiden, nicht nur beide,

eine ganze Reihe von Tiefunktionen, die man damit angehen kann, betrachtet.

Das war, wir zählen die Anzahl der Inversionen, oder wenn man es genau nennt,

die Anzahl der Nichtinversionen oder die Anzahl der Zahlen, die schon an der richtigen Stelle steht.

Das waren diese beiden Maße, inf und ham.

Wir hatten dann noch ein paar andere auch noch, wir werden jetzt gleich inf und ham,

also für Hemmingenabstand, uns anschauen.

Der Mutationsoperator ist ganz einfach.

Wir haben dann eben, dass wir eine Anzahl an Schritten wählen,

die bezüglich so einer Poissonverteilung ausgewürfelt werden.

Also S ist jetzt die Anzahl der Schritte, ganz genau, weil wir auch noch die Null mit dabei haben.

Wir würfeln da oben so eine Zahl aus und machen dann S plus eins viele Schritte.

Ich hatte Ihnen ja schon beim letzten Mal erklärt, warum man da nicht nur einen Schritt macht, sondern mehrere.

Weil wir nehmen ja nur, hier an dieser Stelle ist das, wir nehmen nur dann die neue Permutation,

wenn sie eine Verbesserung gegenüber der alten Permutation darstellt.

Und man kann sich das dann so vorstellen, dass man dann irgendwie auf so einem lokalen Berg steht.

Und wie ich das ja dann schon gesagt habe, man muss, das hier ist ein Hillclimber,

man steht auf einem lokalen Berg und der nächste Schritt, egal wohin man geht,

würde halt immer erstmal eine Verschlechterung bringen.

Deswegen müssen wir mehrere Schritte machen.

Also wir dürfen runtergehen und dann müssen wir auf der anderen Seite wieder hochgehen.

Und deswegen brauchen wir mehr als einen Schritt.

Und das lassen wir halt zu.

Aber eben, die Verteilung ist eben, dass man da nicht mehr als zwei Schritte so im Erwartungswert macht.

Aber jede Schrittzahl ist möglich.

Aber Sie sehen da oben, die Anzahl der Schritte ist natürlich, also dass die Anzahl der Schritte groß ist,

ist sehr unwahrscheinlich.

Also zehn Schritte ist eins durch E mal zehn Fakultät.

Dafür ist die Wahrscheinlichkeit eins durch E mal zehn Fakultät.

Das ist eine winzige Zahl.

Nur es ist nicht ausgeschlossen.

Das ist immer das, was das mit den Wahrscheinlichkeiten so interessant macht.

Man schließt halt nicht aus, sondern das, was man nicht haben will, das macht man sehr unwahrscheinlich.

Aber es ist halt hin und wieder so, dass das, was man nicht haben will, das Gute ist.

Und dadurch, dass man es nicht ausschließt, wird es dann auch irgendwann mal eintreten.

Deswegen ist das halt das Gute.

Wir machen halt insgesamt S plus eins von diesen Operationen.

Und für jede Operation wählen wir jetzt dann zwei Indizes aus,

auf die wir dann entweder einen Exchange anwenden oder einen Jump.

Und da an den Stellen wird auch nochmal gewürfelt.

Und das Verfahren selbst ist jetzt, hier haben wir, das ist jetzt abgespeckt unser evolutionärer Zyklus.

Wir initialisieren, wir bewerten, wir brauchen keine Nachkommen zu erzeugen,

sondern wir haben immer nur eine Permutation.

Und aus dieser einen Permutation erzeugen wir durch Mutation eine neue Permutation.

Und wenn die besser ist, dann nehmen wir die, wenn nicht, wird die halt verworfen.

Und wir wiederholen das Ganze nochmal.

Also wir wiederholen das und das machen wir so lange, bis wir entweder bei Ham haben wir dann ja die Anzahl der Übereinstimmungen ist N.

Beziehungsweise wenn wir Inf nehmen, dann ist die Anzahl der Inversion eben 0.