Neighborhood-Based Approaches - Population-Based Approaches
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Part Number | 5 | |
| Number of Parts | 12 | |
| Author | ||
| License | CC Attribution - ShareAlike 3.0 Germany: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this | |
| Identifiers | 10.5446/21463 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
00:00
Radical (chemistry)Feasibility studyLocal ringPerturbation theoryFunction (mathematics)Mathematical optimizationTime evolutionSimilarity (geometry)Slide ruleSampling (statistics)String theoryTerm (mathematics)Travelling salesman problemPermutationMatrix (mathematics)Group representationGraph (mathematics)OptimumLösung <Mathematik>Moment (mathematics)Direction (geometry)String (computer science)Local ringConnected spaceSubsetPlane (geometry)Directed graphVector graphicsIndexGenetic programmingKanteSet (mathematics)Solution setStrategy gameComputer animation
09:48
Graph (mathematics)Slide ruleBinary fileString theoryFeasibility studyVertex (graph theory)Travelling salesman problemRule of inferenceString (computer science)Lösung <Mathematik>PositionAlgebraStrategy gameEuclidean vectorConnected spacePermutationMatrix (mathematics)IndexFormalismus <Mathematik>Object (grammar)LengthRoundingElement (mathematics)Permutation matrixChromosomal crossoverGraph (mathematics)LinieKanteGenetic programming
19:30
Degree (graph theory)Chromosomal crossoverFundamental theorem of algebraPositional notationSlide ruleSampling (statistics)Strategy gameConstraint (mathematics)Standard deviationGroup representationFeasibility studyPositionStrategy gameLösung <Mathematik>Chromosomal crossoverMilitary operationSolution setString (computer science)DepictionComputer animation
29:11
InfinityFunction (mathematics)Constraint (mathematics)Graph (mathematics)Mathematical optimizationTheoryLimit (category theory)Total S.A.Process (computing)Group representationZielfunktionFeasibility studyMaß <Mathematik>Sign (mathematics)Partial derivativeApproximationSummationSolution setPermutationMassLösung <Mathematik>String (computer science)Point cloudKanteReal number
38:52
Solution setEuclidean vectorLösung <Mathematik>Vector graphicsGreatest elementBerechnungNegative numberLengthKanteMaximum (disambiguation)Set (mathematics)Strategy gameState of matterModulformMaß <Mathematik>Connected spaceStress (mechanics)
48:33
IndexPositionSolution setRecursive languageRecursionConnected spaceDecision theoryLösung <Mathematik>Rekursiver AlgorithmusLoop (music)NumberComputer animation
58:04
PositionLoop (music)KantePermutationNumberIndexGraph (mathematics)Image resolutionMilitary operationRoundingMittelungsverfahren
01:07:19
Stress (mechanics)PositionMittelungsverfahrenPhysical quantityLogicPoint (geometry)Chromosomal crossoverChain complexStrategy gameLength of stayZifferComputer animation
01:16:34
Musical ensembleSimulationVelocityModulformPermutationLösung <Mathematik>Physical quantityGebiet <Mathematik>MathematicsMatching (graph theory)SakokuComputer animation
Transcript: German(auto-generated)
00:01
Präsentiert von Open Learnware, die Plattform für Lernmaterialien an der TU Darmstadt. So, hallo allerseits, dieser Punkt hatte ich letztes Mal kurz übersprungen, weil ich mir in dem Moment nicht sicher war, ob ich das richtig rüberbringen würde.
00:21
Ich habe es mir natürlich jetzt nochmal angesehen, hatte ich ja gesagt, dass ich das dann auf dieses Mal verschieben würde. Das ist jetzt auch keine besonders tief liegende Sache. Worum geht es? Sie erinnern sich, wir hatten Varianten von Local Search, bei denen wir auch in dem
00:41
Moment, wenn wir in ein lokales Optimum gekommen sind, dann auch etwas anders gemacht haben. Zum Beispiel bei Tabusuche, dass wir dann eben weitergegangen sind, sozusagen in dieselbe Richtung, auch wenn es Verschlechterungen gibt. Wir hatten auf der anderen Seite gesehen, die einfache Idee, dass man nicht eine lokale Suche macht, sondern beispielsweise eine Million lokale Suchen.
01:02
Von zufällig aus gewählten verschiedenen Startpunkten in der Hoffnung, wenn wir die wirklich ausreichend zufällig aussuchen, dann gibt es ausreichend viele Treffer unter den Millionen, wo wir schon in einem sehr guten Bereich des Lösungsraums sind. Und wenn wir dann von dort aus lokale Suche machen, dass wir dann schon zu
01:22
einem sehr guten lokalen Optimum kommen. Das ist die Hoffnung, die natürlich in der Praxis durchaus ihre Bestätigung findet. Nicht immer, aber immer öfter. Also nicht immer, aber sicherlich in vielen verschiedenen Situationen. Beziehungsweise wenn diese Bestätigung nicht da ist, wenn es doch nicht so gut funktioniert, sollte man sich vielleicht überlegen, ob man die diese zufällige
01:45
Auswahl, diese eine Million oder zehn Millionen oder wie viel auch immer Startlösung, ob man da an der nicht ein bisschen was rumbastelt. Denn irgendwo müssen ja die guten Lösungen liegen. So hier, das ist ein bisschen dazwischen. Wir machen im Prinzip machen wir eine lokale Suche.
02:12
Aber wenn wir einem lokalen Optimum gelandet sind, dann machen wir nicht nur einfach einen kleinen Schritt in der Nachbarschaft, sondern machen wir eine
02:22
größere Änderung. Zum Beispiel bei einer Rundtour, dass sie einfach eine größere Anzahl von Knoten hernehmen. Immer noch klein im Verhältnis zur Gesamtzahl der Knoten, aber eine größere Anzahl von Knoten hernehmen und die deren, zum Beispiel deren Platzierung beliebig umändern, sodass sie dann also eine neue Rundtour bekommen, mit
02:44
der sie dann wieder weitermachen in der Hoffnung, wenn sie da irgendwie willkürlich herum die Knoten herumgeschoben haben, dass sie dann zu einer Lösung kommen, die außerhalb dieses lokalen Optimums und seinem Einflussbereich ist, jenseits der nächsten Bergkette auf der anderen
03:01
Seite, sodass sie dann, so wie hier in dem Bild angedeutet, eine Chance haben, zu einem besseren lokalen Optimum zu kommen. Und das ist eigentlich alles, was dazu zu sagen ist. Mehr will ich auch dazu nicht sagen. Wir können dann zum eigentlichen Thema des heutigen Tages kommen.
03:21
Zum ersten Thema des heutigen Tages, genetische Algorithmen. Das ist eine sehr beliebte Vorgehensweise. Wir haben beim letzten Mal Evolutionsstrategien betrachtet, die in gewisser Weise eine Simulation der biologischen Evolution, der asexuellen
03:41
biologischen Evolution ist. Mutation und Selektion. Die einzelnen Individuen auf der Ebene der Gene der Erbanlagen mutieren in der Natur natürlich extrem langsam. Hier wollen wir es natürlich etwas schneller haben. Wir haben keine 5 Milliarden Jahre Zeit, bis wir zu Lösungen kommen, die
04:03
immer noch so schlecht sind wie der Homo sapiens, sondern wir wollen in kürzere Zeit zu besseren Lösungen kommen. Und einer der wesentlichen Punkte, warum es überhaupt oder vielleicht der entscheidende Punkt, warum es überhaupt in der biologischen Evolution zu einer solchen Explosion von Artenvielfalt, zu einer solchen
04:20
höheren Entwicklung von einfachsten Lebewesen bis zu so merkwürdigen Lebewesen wie uns gekommen ist, liegt daran, dass eben Mutation und Selektion, dass sich durch Mutation und Selektion im Laufe der Zeit eine neue Strategie herausgebildet hat.
04:41
Sexuelle Vererbung, Rekombination. Und genau das wird hier simuliert. Das heißt also, wir haben nicht mehr wie die Entwicklungsstrategien einzelne Individuen, die im Wettstreit miteinander liegen, die nicht gegeneinander kämpfen, sondern die, die alle sozusagen im selben Hamsterrad vorwärts laufen und die,
05:02
die in die richtige Richtung laufen, die gewinnen, die duplizieren und dann gehen zwei separate Individuen ihren Weg und die, die in die falsche Richtung laufen, die werden aus dem Spiel genommen. Hier geht es jetzt darum, wir nehmen uns zwei, wie in der Natur, wie in der Biologie zwei Individuen her und lassen von denen jetzt Nachkommen
05:25
entwickeln und zwar, weil das ein besonders einfaches Schema ist, immer auch gleich zwei Nachkommen, also immer Zwillinge. So, wir brauchen, wir brauchen allerdings dafür eine spezielle Rekodierung,
05:42
was allerdings auch kein großes Problem ist. Wir haben bisher zunächst einmal immer eine sehr abstrakte Struktur zugrunde gelegt, das ist die Nachbarschaftsbeziehung auf dem, auf den zulässigen Lösungen, was nichts anderes war als ein gerichteter Graph mit den Knoten als zulässigen Lösungen
06:04
und die Kanten definieren die Nachbarschaftsbeziehungen. Wir haben beim letzten Mal auch Algorithmen betrachtet, die eine stärkere Struktur benötigen, das waren die feature-based Algorithmen.
06:20
Das heißt, wenn Sie sich erinnern, es gibt eine Grundmenge von Features und jede zulässige Lösung ist eine bestimmte Teilmenge dieser Grundmenge. Hier brauchen wir auch wieder eine zusätzliche Struktur. Und zwar kodieren wir den Lösungsraum, die Elemente des Lösungsraums,
06:43
also die zulässigen Lösungen, als Strings über einem Alphabet. Und da folgen wir voll und ganz der Biologie. Sie erinnern sich vielleicht aus einem Biologieunterricht oder diejenigen von Ihnen, die bei mir Algorithmische Modellierung gehört haben, erinnern sich das vielleicht aus einem entsprechenden Modellierungsproblem.
07:01
Die Erbanlagen, das sind im Prinzip DNA-Sequenzen. Wenn man die ganzen biologischen Details weg abstrahiert und sich anschaut, was ist denn die Information oder wie ist die Information der Erbanlagen kodiert in den RNA-Sequenzen, dann kann man sagen, na ja, abstrakt gesehen ist das ein String über einem Alphabet von vier Buchstaben.
07:25
Diese vier Buchstaben, meistens ACGT, das sind die Anfangsbuchstaben der vier Säuren, die die tatsächliche Information in dieser Doppelhelix kodieren. Wobei wir natürlich als Informatiker immer zuerst nicht an ein Alphabet mit vier Buchstaben,
07:42
sondern an ein Alphabet mit zwei Buchstaben denken, 0 und 1, aber das ist nicht zwingend notwendig. Ich sollte dazu sagen, wenn Sie weiter lesen zu diesem Thema, also vor allem in Informatik auch weiter lesen, dann werden Sie feststellen, dass die Übertragung der biologischen Begriffe,
08:02
die in der Biologie natürlich alle ganz klare feste Bedeutung haben, aber die Übertragung in die Formatik ist nicht so wirklich standardisiert. Aber ich denke, es sollte in jedem Fall aus dem Kontext klar werden, was damit jeweils gemeint ist. So, bei Feature Based Problemen Definition.
08:21
Das ist eine ganz einfache Kiste. Was heißt noch mal Feature Based? Habe ich eben schon mal gesagt, Sie haben eine Grundmenge von Features, endlich. Sollte typischerweise endlich sein, ist nicht zwingend notwendig, aber sollte eigentlich endlich sein. Und die gewisse Teilmenge dieser Grundmenge sind zulässige Lösungen.
08:41
Sie wissen, Sie können jede Teilmenge einer Menge auch kodieren als 0,1-Vektor, als den charakteristischen Vektor dieser Teilmenge, indem Sie einen Vektor haben, der so lang ist, wie diese Gesamtmenge Elemente hat. Also eine Komponente für jedes einzelne Element dieser Grundmenge.
09:03
Und eine 1 an einer Komponente besagt, an einem Index besagt, dass dieses Element, dieses Feature in der Teilmenge drin ist und eine 0 besagt, dass sie nicht drin ist. Und schon haben Sie eine entsprechende Kodierung. TSP haben wir natürlich auch als Feature basiert modelliert,
09:25
nämlich für jede einzelne Kante zu sagen, ob sie drin ist oder nicht. Aber hier in diesem Kontext ist es durchaus sinnvoll oder sinnvoller, an eine andere Kodierung des TSP zu denken, die wir auch betrachtet haben, eine einfache Kodierung.
09:43
Was bedeutet denn eine TSP-Lösung? Das ist eine Reihenfolge der Städte, die Reihenfolge, in der Sie diese Städte besuchen wollen. Das ist einfach eine zulässige Lösung des TSP. Und das kann man natürlich auch entsprechend als eine Permutation kodieren.
10:02
Das heißt also, was ist eine Permutation? Eine Permutation von N Elementen, von N Objekten ist einfach ein String. Den können Sie als ein String über dem Alphabet auffassen, wo Sie jedem einzelnen Objekt dort seine Position zuweisen.
10:20
Sie schreiben, Sie haben N verschiedene Indizes, für jede Stadt eine. Und Sie schreiben da jeweils die Position hin in der Reihenfolge. Also Sie müssen natürlich festlegen, welche Stadt ist jetzt die Nummer 1. Bei einer Rundtour ist das ja eigentlich egal. Und dann ergibt sich automatisch aus der Rundtour, welche Stadt ist an Position 2, welche Stadt ist an Position 3 und so weiter.
10:50
So, oder auch so, wenn Sie 01-Vektoren haben wollen, wenn Sie 01-Strings haben wollen, können Sie auch eine andere Matrix definieren, wo Sie sagen,
11:09
der Wert, die Komponente an der Zeile i und der Spalte j ist entweder 01 und zwar 1 genau dann, wenn i, die Position von i in der Rundtour gerade j ist.
11:25
Ich weiß nicht, ob Sie das aus der Linie in Algebra mitgenommen haben. Das ist im Prinzip eine Permutationsmatrix. Was ist eine Permutationsmatrix? Sie nehmen sich die Einheitsmatrix her, diagonalen alles 1, alles andere 0. Und dann promethilen Sie die Zeilen oder die Spalten. Und alles, was Sie auf diese Art und Weise generieren können, nennt man naheliegenderweise Permutationsmatrix.
11:46
So, Graph Coloring ist noch ein Beispiel. Wir kommen gleich zum Algorithmus. Ich glaube, wenn ich mal kurz vorschauen darf, jawohl, letztes Beispiel. Keine Sorge. Graph Coloring, Sie erinnern sich, das war das Problem, was auf der einen Seite entstanden ist aus der Frage,
12:06
mit wie viel Farben braucht man, um eine Landkarte zu färben, wo wir dann jedes Land durch einen Knotenersatz repräsentiert haben. Und wenn zwei Länder benachbart sind, dann sind die beiden Knoten verbunden durch eine ungerichtete Kante.
12:20
Und die Aufgabe besteht darin, das ist genau das Graph Coloring-Problem, jedem einzelnen Knoten eine Farbe zuzuweisen, sodass zwei Knoten, die mit einer Kante verbunden sind, unterschiedliche Farben haben. Und natürlich, das Optimierungsziel dabei ist, die Anzahl der Farben, die Sie benutzt haben, dafür zu minimieren.
12:43
So, dass wir uns auch daran erinnern, natürlich haben wir immer eine triviale Möglichkeit einer Graph Coloring, indem wir jedem Knoten eine andere Farbe geben. Das heißt, wir wissen von vornherein, wir werden nicht mehr als n Farben brauchen, wenn wir n Knoten im Graphen haben.
13:00
Das heißt, wir können von vornherein die Länge des Strings oder des Alphabets begrenzen. Wir haben wieder dieselbe Situation wie eben beim TSP. Wir haben für jeden Knoten einen Index, die Farbe. Und dieser Index, die Farbe, wird natürlich ausgedrückt durch die Nummer dieser Farbe, die wir unabschränkter Allgemeinheit auf 1 bis n reduzieren können.
13:24
Auch hier wieder, ähnlich wie beim TSP, können Sie beispielsweise auch verschiedene, sehr analoge Kodierungen hier nehmen. Also ein wichtiger Punkt hierbei ist auch immer, was immer wieder mitschwingt, es gibt nicht die Problemstellung.
13:43
Ja, es gibt auf der einen Seite die abstrakte Problemstellung, wie sie in der Welt vorkommt, wie das TSP. Sie wollen bestimmte Punkte möglichst schnell hintereinander anlaufen. Und auf der anderen Seite gibt es dann die Kodierung dieser Problemstellung in einem Formalismus.
14:00
Und wie diese Kodierung ist, da haben Sie, wie Sie hier an diesem Beispiel noch sehen, da haben Sie eine gewisse Handlungsfreiheit. Wie diese Kodierung ist, davon hängt es natürlich ab, ob die Algorithmen, die Sie anwenden, dann später gute oder schlechte Ergebnisse liefern. Oder umgekehrt, von einem Algorithmen, die Sie anwenden wollen, hängt es dann ab, was eine gute oder was eine schlechte Kodierung ist.
14:23
Das sind Dinge, die man nicht so richtig gut verbalisieren kann, wo man Erfahrungswerte sammeln kann und wo man dann eben auch herumspielen kann. Sie haben ein Problem, wie dieses Kraft-Coding-Problem. Sie wählen eine Kodierung. Sie lassen darauf Algorithmen rumlaufen und sie kommen auf keinen grünen Zweig. Es funktioniert einfach nicht ordentlich.
14:43
Sie kommen zu keinen guten Lösungen. Sie können an den Algorithmen rumspielen, dass Sie einen anderen Algorithmus auswählen oder dass Sie an dem Algorithmus, den Sie ausgewählt haben, noch ein bisschen drehen und schrauben. Und oder Sie können sich auch überlegen, ob die Kodierung, die ich gewählt
15:00
habe, die vernünftig ist oder ob ich nicht eine bessere andere Kodierung wählen sollte. Und da kommt wieder ins Spiel das, was in der Übungsaufgabe auch sehr wichtig ist. Wenn Sie den Algorithmus so abstrakt formulieren, wie ich es vorderein in der Programmieraufgabe, dann ist es überhaupt kein Problem mehr,
15:20
darunter eine Kodierung rauszunehmen und eine andere Kodierung reinzustecken. Dann brauchen Sie von dem ganzen Algorithmus nichts, aber auch gar nichts nochmal neu programmieren. Die Abstraktion auf die Spitze zu treiben, wie wir das hier in der Programmieraufgabe machen, ist nicht einfach eine Schikane und ist auch nicht nur didaktisch zur Unterstützung des Vorlesungsstoffes, sondern hat handfeste Vorteile.
15:46
Und das ist eine Denkweise, die Ihnen sicherlich über die hier betrachtete Thematik Optimierungsalgorithmen weit hinaus helfen kann. Denken Sie an Datenbanksysteme, dass Sie das Datenbankschema ändern, ohne dass Sie die ganzen Applikationen darüber ändern müssen.
16:08
So, wieder mal das Wort zum Sonntag. Jetzt kommen wir wieder zurück zu den genetischen Algorithmen. Wie kann man sich das vorstellen? Also grundsätzlich sieht das so aus, wie ich das schon ebenmündlich angedeutet habe.
16:28
Ich mache mal noch einen kleinen Check, das hätte ich vielleicht vorher machen sollen, ob die Kamera das richtig gut... Ja, geht so. Wir nehmen uns zwei zulässige Lösungen her. Wir haben wieder, wie bei den Evolutionsstrategien, eine Population von Lösungen.
16:55
Aus dieser Population nehmen wir uns nicht mehr eine Lösung her und schmeißen die raus oder lassen die sich duplicieren,
17:03
sondern wir nehmen zwei her, die, wie in der Biologie auch, die sich möglichst deutlich unterscheiden sollten. Weil wir, wie in der Biologie auch, wollen wir hier keine Inzucht produzieren. Wir wollen keine Inzucht, das wissen Sie, ist die Erfahrung verstärkt, negative Erbmerkmale, die normalerweise durch diese Rekombination,
17:27
wenn die Erbanlagen der beiden Partner ausreichend weit auseinander sind, typischerweise nicht verstärkt würden. So, und die bilden zusammen wieder zwei neue. Und Sie sehen schon, vielleicht allein durch dieses Bild schon,
17:52
bekommen Sie eine Ahnung davon, wie wichtig es ist, dass wir da eine vernünftige Kodierung haben in Form von Strings, wie in der Biologie auch. Ich glaube, wenn die Biologie keine Strings erfunden hätte als Erbanlagen,
18:06
gäbe es uns wahrscheinlich nicht. Also gäbe es uns definitiv nicht, denn die Strings sind ja bei uns drin. Aber ob es zu einer solchen Explosion von Artenvielfalt hätte kommen können und von solcher Weiterentwicklung, das ist dann schon fraglich. So, ist ein bisschen anders natürlich. Wir müssen natürlich Abstriche machen.
18:30
Wir müssen Kompromisse schließen, wenn wir das Ganze als Computerprogramm laufen lassen. Dann, wie in der Evolutionsstrategie auch, läuft das immer in Runden ab. Das ist in der natürlichen Evolution natürlich nicht der Fall. Und wir haben immer Zwillinge,
18:45
immer Zwillingsgeburten. Und die typische Strategie, die wir uns gleich noch ansehen werden, sehen so aus, dass die beiden, das spielt Rolle A, das spielt Rolle B, um den zu produzieren.
19:02
Und das spielt Rolle A und das spielt Rolle B, um dann den zu produzieren. Das werden wir gleich sehen, was das heißt. Nur noch zur Terminologie. Da werde ich sicherlich auch auf das Mal rein verfallen, dass ich von Crossover spreche anstelle von Rekombination. Das ist eigentlich ein gängiger Ausdruck,
19:21
sowohl in der Informatik als auch in der Biologie. So, Qualität. Qualität einer solchen Rekombinationsstrategie. Na ja, wir wählen natürlich von vornherein, wie auch in der Biologie, vor allem Eltern aus,
19:43
die besonders gut sind. Also was bei uns bedeutet, deren Zielfunktionswert besonders gut ist. Eben in der Biologie eben die Fitness, was, wie ich ja gesagt hatte, Angepasstheit bedeutet. Im Gegensatz zu dem, was die Sozialterministen glauben.
20:03
So, das heißt, wir machen dasselbe im Prinzip wie in den Innovationstrategien. Wir lassen dem Zufall seinen Raum, aber diejenigen zulässigen Lösungen, die besonders gut sind, die haben eine sehr viel höhere Chance für die Rekombination ausgewählt zu werden als diejenigen zulässigen Lösungen,
20:25
die nicht besonders gut sind. Zum Beispiel. Und wenn wir jetzt so gute Lösungen haben, dann sollte auch möglichst viel an Gemeinsamkeiten von diesen Eltern durchaus übertragen werden.
20:45
Wenn sie zum Beispiel zwei an zwei Positionen denselben Wert haben bei beiden, dann sollte das eigentlich auch bei den beiden Offspring, bei den beiden Nachkommen ebenso jeweils diesen Wert haben.
21:01
Und wenn ein bestimmter Wert da nicht ist, dann sollte bei den Eltern, dann sollte er bei den Offspring, bei den Nachkommen auch nicht sein. Aber trotzdem, die Grundidee beziehungsweise das, was eben auch in der Biologie den Erfolg der Rekombination ausmacht, ist, dass wir eben im Gegensatz zu Mutation und Selektion nicht allzu große Ähnlichkeit zwischen den Eltern und den Nachkommen haben,
21:29
sondern dadurch, dass zwei sehr unterschiedlich, möglichst unterschiedliche Eltern gewählt werden, ergibt sich automatisch, dass auch die Nachkommen, wenn wir das mit einer vernünftigen Crossover-Strategie machen,
21:42
dass auch die Nachkommen dann sich untereinander stark unterscheiden und sich auch von den Eltern stark unterscheiden. Sodass wir nebenbei bemerkt auch noch einen viel größeren Bereich des Lösungsraums explorieren. Weil wir eben nicht immer nur kleine Schritte voran machen, sondern gleich große Sprünge.
22:03
So, wir gucken uns das jetzt an, nur die Notation. Wir haben also hier, das kann ich hier an die Tafel eintragen, diese Notation. Wir haben hier P1 und hier P2 und hier haben wir Offstring 1 und Offstring 2.
22:29
Und das ist schon die ganze Notation auf dieser Folie. So, das zeichne ich Ihnen lieber an, als dass ich versuche Ihnen die Folie zu erklären. One-Point-Crossover ist eine ganz primitive Sache.
22:48
Ich muss das Bild jetzt aber etwas variieren. Sie haben hier den Parent 1. Jetzt muss ich ja mal gucken, ob das nicht sowieso ein Bild davon dann da ist.
23:05
Nein, ist nicht da. Also mache ich das jetzt hier. Und den Parent 2. Und Sie haben jetzt hier irgendwo eine Nummer, eine Position P, irgendwo drin.
23:24
Dieselbe Position hier. So. Das schraffiere ich so und das schraffiere ich so. Und was wir jetzt rauskriegen, sind der Offstring 1 und der Offstring 2.
23:47
Das ist die Position P hier, auf der Seite. Und genauso hier. Die Position P auf der Seite. Und was wir jetzt rauskriegen, ist eine Rekombination, die bis dahin gleich dem Parent 1 ist.
24:08
Und umgekehrt, die bis dahin gleich dem Parent 2 ist. Und was letztendlich gemacht worden ist, ist, dass dieser Bereich nach P vertauscht worden ist.
24:22
Da sehen Sie, wie einfach die Sache wird, wenn wir tatsächlich solche zulässige Lösungen als Strings codieren. Weil wir dann einfach solche Operationen machen können, wie Substring hernehmen, aus einem String rausnehmen und woanders hin anhängen.
24:40
Two-Point-Crossover ist eine leichte Verkomplizierung des Ganzen.
25:27
Sie haben wieder zwei Parents, wie eben. Zwei Eltern. Vielleicht ein bisschen länger.
25:45
Und Sie haben jetzt zwei Positionen. L und R. Jetzt muss ich gucken, wie das ... Ja. Hier ist L auf der Seite, hier ist R auf der Seite. Und machen wir dasselbe Spielchen wieder.
26:03
Den schraffiere ich so. Und den schraffiere ich so zur Unterscheidung. Und was dabei jetzt herauskommt, ist ein Offspring 1 und ein Offspring 2 tragen wir dieselben zwei Positionen ab.
26:30
L und R. Und alles vor L bleibt so wie es ist. Also hinter R. Das war jetzt falsch. Das müsste jetzt eigentlich andersrum sein. So.
26:45
Alles hinter R bleibt so wie es ist. Und das zwischen L und R inklusive wird zwischen beiden hin und her getauscht. Die beiden sind ausgetauscht.
27:02
Dritte Möglichkeit. Uniform. Crossover. Das ist eine etwas andere Strategie, die man nicht so richtig gut zeichnen kann, denke ich, aber die man gut verbalisieren kann. Für jede einzelne Position würfeln wir. Also genau gesagt wir werfen eine Münze. Die Münze
27:24
ist aber nicht unbedingt 50-50, sondern die kann durchaus wieder zwei unterschiedliche Wahrscheinlichkeiten haben. Und mit einer gewissen Wahrscheinlichkeit werden die Werte an dieser Position ausgetauscht zwischen den beiden Strings. Und mit einer entsprechenden Restwahrscheinlichkeit bleiben die Werte so wie sie sind.
27:43
So wie ist das jetzt hier rum? Also der erste Spiegelstrich ist hier, dass die Werte so bleiben wie sie sind. Zweites Spiegelstrich ist, dass die Werte zwischen beiden ausgetauscht werden. Das sind so schon mal die gängigen grundlegenden Strategien für Crossover, die immer wieder gerne Anwendung finden und die durchaus viel bringen.
28:06
Jetzt ist aber das Problem dabei. So abstrakt wie wir das jetzt eben auf dieser Folie gesehen haben, habe ich das Problem, was dahinter ist, natürlich schön auch weg abstrahiert. Das Problem ist, wenn wir so eine Strategie anwenden, ob das dann, was dann am Ende herauskommt, immer noch eine zulässige Lösung ist.
28:26
Das ist ja erstmal nicht gesagt. Nicht alles, was ich als diese Strings kodiere, ist ja eine zulässige Lösung, sondern nur bestimmte davon sind zulässige Lösungen. Wenn ich jetzt anfange da so blind rumzuhandieren, Strings auszutauschen, wer sagt
28:43
denn, dass das, was dann am Ende herauskommt, tatsächlich zulässige Lösungen sind? Das ist natürlich witzlos, wenn sie das nicht sind. Eine Möglichkeit, die oft verwendet wird, ist, dass man sagt, okay, wir erlauben auch nicht zulässige Lösungen im Laufe des Algorithmus.
29:05
Ja, wir erlauben, dass wir erweitern sozusagen den Lösungsraum auf alle möglichen Strings, die vorkommen, nicht nur auf die Strings, die zulässige Lösungen darstellen. Aber natürlich nicht ersatzlos, denn sonst kommen wir mit Sicherheit am Ende bei einer unzulässigen Lösung raus.
29:21
Wir bestrafen das, dass das, was da ist, keine zulässige Lösung ist. Denken Sie beispielsweise ans TSP. Wenn wir jetzt anfangen, beliebig will, wir nehmen uns zwei Rundtouren her und tauschen da irgendwelche Kanteninformationen aus. Für bestimmte Kanten tauschen wir die Information aus. In dem einen ist sie drin, im anderen ist sie nicht drin.
29:43
Das, was dabei rauskommt, als die zwei aufspringen, sind nie und nimmer Rundtouren. Kann gar nicht sein. Also sehr unwahrscheinlich, dass das zwei Rundtouren sind. Extrem astronomisch unwahrscheinlich. Dass man aber dann sagt, dass sagt diese Strategie, okay, wir lassen das zu.
30:00
Uns ist es wichtiger, dass der Lösungsraum sehr einfach strukturiert ist, damit wir sehr, sehr schnell auf auf diesem Lösungsraum die Suche sich ausbreiten lassen können. Ohne große, ohne große Fils im Attenten. Aber die der Kostenwert einer solchen zulässigen oder unzulässigen Lösung ist nicht mehr einfach die Summe der Kantenlängen,
30:22
sondern die Summe der Kantenlängen plus ein Strafterm, der bestraft, wie weit weg das, was wir da in Händen haben, von einer Rundtour ist. Wie weit weg das von einer Rundtour ist, da kann man natürlich schauen, kann man versuchen, als Maß beispielsweise herzunehmen,
30:46
wie viele Knoten gibt es, die nicht genau eine reingehende und nicht genau eine rausgehende Kante haben oder solche Sachen. Kann man versuchen, als Strafterm zu definieren. Und Sie sehen auch hier, das ist auch wieder ein Beispiel.
31:02
Wenn Sie das TSP kodieren als Permutation und dann haben Sie dieses Problem nicht mehr so in dieser verschärften Form. Ein anderes Beispiel hier ist, da machen wir einen Ausflug.
31:21
Dieses Problemstellung haben wir noch nicht in den Beispielen eingeführt, ist aber auch eine sehr wichtige Problemstellung. Genau, nehmen wir dieses Beispiel her. Was Sie hier haben, stellen Sie sich vor, Sie haben ein großes Projekt zu organisieren, ein richtig großes Projekt, ein großes Bauprojekt oder so etwas.
31:42
Dieses riesengroße Bauprojekt besteht natürlich aus vielen, vielen, vielen Einzeljobs. Jobs ist der typische Begriff dabei in der englischen Literatur. Ich habe mir angewöhnt, hier von vornherein immer von Jobs zu sprechen. Jeder versucht das was anderes zu sagen. Aufgaben oder Teilprojekte oder sowas hat nicht funktioniert.
32:00
Ich habe dann doch am Ende von Jobs gesprochen. So, diese ganzen weiterhin unteilbaren Tas, Aufgaben, Jobs, Jobs, deshalb ein großes J als Abkürzung, die stehen natürlich in Beziehungen zueinander.
32:20
Ja, denken Sie an ein Bauprojekt. Sie können die Wände erst dann hochziehen, wenn der Keller gebaut ist. Sie können erst dann mit dem Dachgebelg anfangen, wenn die Wände hochgezogen sind. Sie können erst dann mit den Fenstern anfangen, wenn die Wände eingesetzt waren und so weiter und so fort. Das sind diese Pfeile hier in diesem Bildchen.
32:41
Diese einzelnen Jobs sind die Knoten. Hier D, Job D darf erst begonnen werden, wenn A schon beendet ist. Also vorher kann Job D nicht anfangen. Wir haben jeweils eine geschätzte Dauer, wie lange das dauern wird, diese einzelnen Jobs. Denken Sie beispielsweise an Tage bei einem Bauprojekt. Das können dann typischerweise Tage sein, wie das dauert.
33:05
Bei einem Ablauf in einer Fabrik wären es vielleicht eher Stunden oder Minuten, je nachdem, worum es geht. So, das ist das eine. Das sind die Precedence Constraints, dass bestimmte Jobs erst dann starten können, wenn andere fertig sind.
33:20
Und dann kommen natürlich noch Resource Constraints dazu. Denken Sie wieder an ein Bauprojekt. Sie haben zwei Kräne und Sie haben drei Aufgaben, die einen Kran benötigen. Sie können nicht diese drei Aufgaben zeitgleich machen. Also einen von den drei müssen sie, einer von den drei muss warten, muss eingeplant werden zu einem Zeitpunkt, wo mindestens einer von den anderen beiden fertig ist, damit dann wieder ein Kran zur Verfügung steht.
33:45
So, und was wir minimieren wollen hier ist die Gesamtdauer, das heißt vom Beginn des ersten Jobs bis zum Ende des letzten Jobs. Ja, vom ersten Spatenstich bis zur schlüsselfertigen Übergabe, wenn man so will.
34:01
So, die sind endbeschwer, die Problemstellungen sind auch in der Praxis schwer. Hier wäre hier wäre so ein Beispiel, wie man sich etwa so was vorstellen kann. Sie haben zwei Kräne oder zwei sonstige Maschinen M1, M2, Machine 1, Machine 2.
34:25
Und Sie können diese Grafen hernehmen und wenn jeder von denen eine von den beiden Maschinen braucht, die beiden Maschinen sind austauschbar. Ja, zwei Kräne beispielsweise, wenn jeder von denen eine Maschine braucht und es ist egal, auf welche
34:42
das ist, dann wären das hier, das hier wären zwei zulässige Lösungen, und zwar zwei recht gute. Natürlich packen Sie die Lösung so eng wie nur möglich, aber Sie sehen, es geht nicht überall so eng. H, dieses H bei P2, bei der zweiten Lösung, beim zweiten älter, können Sie nicht beliebig nach
35:02
links direkt ans D anhängen, weil H noch auf E zu warten hat und E ist hier platziert. Also kann H frühestens hier platziert sein. Sie können nicht einfach alles so weit nach links wie möglich platzieren. Ich habe eben von älter im Singular gesprochen, das mache ich öfter. Im Englischen ist es möglich, parent im Singular zu verwenden.
35:23
Im Deutschen eigentlich nicht, aber in der Informatik hat es sich inzwischen eingebürgert, tatsächlich von älter im Singular zu sprechen. Damit man jetzt nicht überlegen muss, ist das jetzt Vater oder ist das jetzt Mutter, dann kommt man in alle möglichen politischen Probleme rein. Mit älter hat man das Problem von vornherein gelöst.
35:43
So, das ist jetzt ein Beispiel für das, was ich eben gesagt habe, dass wir auch unzulässige Lösungen zulassen. Vielleicht nicht alle, aber wenigstens gewisse, nämlich, dass wir die Ressourcenbedingungen ignorieren.
36:07
Also to relax heißt, ja, was heißt das? Sich oder anderen das Leben einfacher machen, wird auch hier gerne verwendet in der Informatik und ist dann meist synonym zu verstehen mit,
36:23
dass wir diese Ressourcenbedingungen, also entweder abschwächen auf irgendeine Art und Weise, dass wir sagen, wir tun so, als ob wir noch eine Maschine mehr hätten, dann machen uns das Leben einfacher oder sogar ganz ignorieren. Aber nicht ohne Ersatz, denn wir bestrafen jetzt, wenn wir Lösungen, so wie hier, das waren zwei zulässige Lösungen.
36:48
Wir haben zwei Maschinen und sämtliche Jobs sind auf den beiden Maschinen platziert. Wenn wir jetzt sagen, wir lassen diese Bedingungen fallen, dass wir nur zwei Maschinen haben und dass alle Jobs auf diesen zwei Maschinen sind,
37:02
wir interessieren uns gar nicht für die Anzahl Maschinen, wir gehen davon aus, dass wir unendlich viele Maschinen haben. Ja, dann haben wir diese Ressource Constraints, die Bedingungen, dass wir nicht mehr Maschinen verwenden als wir haben, die haben wir dann ignoriert, aber wir bestrafen es, wenn eine Lösung mehr als zwei Maschinen braucht.
37:22
Zum Beispiel, indem Sie einfach zählen, wie viel Workload auf den nicht existierenden zusätzlichen Maschinen ist. Das wäre eine sinnvolle Bestrafung. So, aber die Reihenfolgebeziehungen, die lassen wir so, wie sie sind.
37:43
Und was wir jetzt als Repräsentierung sinnvollerweise hernehmen, ist, dass jeder Job eine reelle Zahl hat, die aber erklärungsbedürftig ist. Diese reelle Zahl hat eine Bedeutung, wenn Sie sich hier diese Formel ansehen, für jede Reihenfolgebeziehung,
38:08
für jedes Presidents Constraint, das haben wir hier irgendwo mit S ausgedrückt, diese Reihenfolgebeziehung, dass dieser Job JS starten darf, wenn I zu Ende ist.
38:22
Was bedeutet das? I ist zu Ende, Startzeit von I plus Dauer von I ist vergangen, erst dann darf Startzeit von J sein, oder natürlich später, muss nicht sofort sein. Und was wir jetzt hier haben, ist, TJ plus DJ ist der früheste Zeitpunkt, wo I starten darf, aufgrund dieser Beziehung.
38:44
Früher darf I nicht starten. Aber, wie wir sehen, wie wir in diesem Beispiel gesehen haben, dieses H, dieser Job H hier bei P2, der kann nicht unbedingt starten, wenn, was ist noch vor H? Ach, nur E. Nee, das ist ein schlechtes Beispiel.
39:07
Na, ich glaube wir haben hier, doch hier, zwischen D und A, genau. Wenn es nur nach A ginge, sowohl hier als auch hier, dann könnte D sofort starten, nachdem A beendet ist.
39:22
Aber es geht nicht nur nach A, es geht auch nach B. Und wenn es nur nach A und B ginge, dann könnte D auf jeden Fall so früh starten, wie es hier in P2 vorkommt. Aber Sie sehen, dass D sogar vielleicht später startet, wegen der Reihenfolgebeziehungen.
39:42
Nicht nur wegen der Reihenfolgebeziehungen, sondern wegen der Maschinenbeziehungen. Wenn es die Maschinenbeziehungen nicht gäbe, dann könnten wir D auf jeden Fall so früh starten lassen, wie in P2. Aber zum Beispiel mit einem Delay zu A. Ja, D startet nicht unmittelbar, nachdem A fertig ist, weil D noch auf B zu warten hat.
40:04
Und das ist der Slack, das ist der Abstand zwischen dem Ende eines vorangehenden Jobs zu diesem Job. Und das ist unsere Repräsentation. Für jeden Job merken wir uns, was der minimale Slack ist, der natürlich, wenn es geht, Null sein sollte.
40:30
Was haben wir dadurch gewonnen, dass wir das so komisch codieren? Was wir dadurch gewonnen haben? Wir haben ja ursprünglich, die nachliegende Idee ist, dass wir die Startzeiten der Jobs selber nehmen, als Repräsentation einer zulässigen Lösung.
40:45
Eine zulässige Lösung ist die Menge der Startzeiten für die einzelnen Jobs. Jeden Job sagen wir, wann er starten soll. Das ist das, was rauskommt, wenn man so ein Scheduling-Problem als Lösung haben will. Hätte ich vielleicht ein bisschen deutlicher sagen sollen, sage ich jetzt.
41:01
Es ist also naheliegend, wenn wir das codieren wollen für genetische Algorithmen, dass wir die Startzeiten, den Vektor der Startzeiten tatsächlich als Codierung hernehmen. Was wir gewinnen, wenn wir das so ausdrücken, ist, dass der Lösungsraum jetzt sehr einfach strukturiert ist oder die Codierung des Lösungsraums sehr einfach strukturiert ist.
41:24
Wieder ein Beispiel dafür, es gibt gute und schlechte Codierungen oder geeignete und weniger geeignete Codierungen. Denn das, was jetzt für jedes einzelne Job empfiehlt, sind gerade die nicht negativen Zahlen der Lösungsraum dafür.
41:43
Die sämtlichen Vektoren mit nicht negativen Einträgen sind die möglichen Lösungen, weil wir das so ein bisschen etwas umständlicher codiert haben. Und damit ist der Lösungsraum natürlich viel, viel einfacher strukturiert. Und je einfacher der Lösungsraum strukturiert ist, umso größer ist die wahrscheinlich, umso besser funktionieren alle diese Wanderungsalgorithmen.
42:08
So, und der entscheidende Punkt jetzt ist das, was ich jetzt eben gesagt habe. Und dadurch, dass das so einfach strukturiert ist, der Lösungsraum.
42:20
Jede Lösung ist ein Vektor mit nicht negativen Einträgen, so viele Komponenten, wie wir Jobs haben. Und jeder mögliche Vektor mit nicht negativen Einträgen ist eine zulässige Lösung, wenn wir die Resource Constraints herausgenommen haben und stattdessen bestrafen.
42:42
Das heißt also, mit diesem kleinen Trick, dass wir diese Slacks hernehmen, haben wir es hinbekommen, dass wir blind links, ohne noch irgendwas machen zu müssen, einfach solche Strategien anwenden können. Denn wenn ich als Ausgang zwei Eltern habe, die nicht negativ, zwei Vektoren dieser Länge, Länge gleich Anzahl Jobs,
43:07
deren Einträge nicht negativ sind und ich fange da an rumzutauschen, mehr als rumtauschen mache ich ja gar nicht. Dann ist das, was rauskommt auf jeden Fall wieder Vektoren, zwei Vektoren derselben Länge mit nicht negativen Einträgen sind auch wieder, sind auch wieder diese, sind auch wieder zulässige Lösungen.
43:31
Und aus diesen Werten, aus dieser Repräsentation, ich brauche jetzt doch nochmal wieder Tafelplatz, aus dieser komischen Repräsentation lässt sich natürlich umgekehrt wieder die Startzeit herausrechnen.
44:14
Wir haben jetzt A, B, C und D muss auf alle drei warten. Das sind die drei auf D warten muss.
44:29
Das bedeutet T, wie war das jetzt? Wir wissen das XI, was drin steht, ist gleich das Minimum, das kann man jetzt explizit
44:43
reinschreiben, aus, warten Sie mal, das kann man ja auch, ich schreibe es mal direkt so hin, wie es die Formel hier oben sagt, Minimum aus, also X von D, wir sind D, Minimum von der Startzeit von D minus Startzeit von A plus Dauer von A,
45:13
Komma, Startzeit von D minus Startzeit von B plus Dauer von B, Komma und dritter Fall Startzeit von D minus Startzeit von C plus Dauer von C.
45:34
Davon ist es das Minimum. Und wenn Sie jetzt von links nach rechts durch die Startzeiten berechnen,
45:40
den allerersten Startzeit Null geben, meinetwegen, oder das Datum, wo Sie das Projekt beginnen wollen, als Startzeit hernehmen, und dann können Sie von links nach rechts durch in topologischer Reihenfolge, Sie erinnern sich an topologische Sortierungen aus der GDE 2, Sie erinnern sich?
46:00
Also das ist was ganz Primitives, wenn Sie wie hier einen A-Zykluschen gerichteten Grafen haben, keine Zykle drin, dann können Sie, so wie hier, sich vorstellen, dieser Graf ist von links nach rechts gezeichnet, sodass jede Kante von einem Punkt links zu einem Punkt weiter rechts jeweils geht, und dann können Sie
46:21
links beginnend das Ganze aufrollen, dann berechnen Sie erst die Startzeiten von A, das wären in beiden Fällen Null, dann berechnen Sie Startzeiten von C, D und E, und wenn Sie die haben von D und E, dann können Sie Startzeiten von F und dann von H berechnen, und dann können Sie, wenn Sie diese Startzeiten haben, auch noch die von G berechnen.
46:40
Nach dieser Formel, weil Sie ja die dann schon, wenn Sie von links nach rechts durchgehen haben, dann müssen Sie das Ganze nur noch umstellen nach der Startzeit von T, das geht sogar ganz einfach. Die Startzeit von T ist gleich, jetzt muss ich sehen, da muss ich alles rüberbringen,
47:08
xd plus Maximum, ja, ich bringe diese Restterme rüber und muss dann aus dem Minimum deshalb Maximum machen, Maximum aus Ta plus Da, Tb plus Db, Tc plus Dc.
47:36
Ja, auf die Art und Weise kriegen Sie aus den Startzeiten, die Sie
47:42
jetzt schon vorher berechnet haben, dann die nächste Startzeit auf Basis der Repräsentation. Ja, eine etwas kompliziertere Form der Kodierung, weil Sie dann das, was sich eigentlich interessiert, die Startzeiten erst mit dieser unten abgeleiteten Formel wieder zurückrechnen müssen, algorithmisch rechnen müssen,
48:03
also Sie müssen die richtige Reihenfolge einhalten, dass Sie zuerst die linkesten Startzeiten, dann die zweitlinkesten und so weiter berechnen. Aber hat den Vorteil eben, und deshalb ist es hier als Beispiel, genau dafür ist es hier auch ein Beispiel, hat den Vorteil, dass der Lösungsraum so einfach strukturiert ist, dass Sie einfach blind links austauschen können und so weiter.
48:26
So, ich darf vielleicht mal ganz kurz an dieser Stelle.
48:53
So, alles klar. Gut, das ist die Idee des Ganzen. Auf die Art und Weise kann man beispielsweise genetische Algorithmen anbringen, verwenden, obwohl eigentlich der Lösungsraum nicht so
49:08
strukturiert ist, dass man solche einfachen Maßnahmen wie diesen One-Point-Crossover oder Two-Point-Crossover anwenden könnte. Wenn wir ein bisschen rumbasteln, wenn wir die Kodierung etwas ändern, haben wir plötzlich eine Kodierung des Lösungsraums, in der das blind links möglich ist.
49:29
So, genau. Es gibt aber auch noch die andere Variante. Das habe ich jetzt noch hier an der Tafel, so etwas stehen.
49:43
Ja, dass man tatsächlich eine solche Strategie anwendet, wie beispielsweise beim TSB, aber erst einmal zulässt, dass das, was herauskommt rechts die Offspring, dass die zunächst mal nicht zulässig sind. Aber bevor es weitergeht, dass man die dann repariert.
50:03
Ja, dass man da noch ein paar kleine Modifikationen einführt, um dafür zu sorgen, dass aus diesen unzulässigen Lösungen wieder zulässige Lösungen werden. Das will ich Ihnen an diesem Beispiel zeigen. Ich möchte aber vorweg eine interessante Beobachtung machen. Sowohl aus Klausuren in früheren Jahren als auch aus mündlichen Prüfungen in früheren Jahren
50:24
habe ich immer wieder zu meinem Erstaunen gemerkt, wenn ich nach genetischen Algorithmen frage, dass es einen gewissen Prozentsatz von Teilnehmern eine Prüfung gab, die schlicht und einfach auf diese spezielle Reparierstrategie fürs TSB eingegangen sind.
50:46
Und die anscheinend der Meinung waren, das sind genetische Algorithmen. Das geht auch konform mit Erfahrung aus der GDE 2. Das ist ein anscheinend ein nicht geringer Prozentsatz von Studierenden gibt, die sich da auch auf die kleinsten technischen Feinheiten stürzen.
51:07
Und also denken Sie ans QuickSort. Ja, was ist QuickSort? Das ist ein rekursiver Algorithmus. Rekursionsabbruch ist die Sequenz hat kein oder ein Element und Rekursionsschritt bedeutet zerlegen, Rekursion wieder zusammenfügen, salopp gesagt.
51:24
Aber dass es durchaus viele Studierende gibt, die dann etwa in der mündlichen Prüfung sagen, anfangen mit, da wird links und rechts ein Pointer gesetzt und die gehen immer weiter in die Mitte und so weiter. Sie kennen das. Und dann, wenn man fragt, ja, was macht man denn mit dem Ganzen,
51:40
nachdem man da jetzt sowas gemacht hat, dann Schwierigkeiten haben, dann dann weiterzukommen. Ich finde, das ist eine sehr interessante, wenn auch bestürzende Beobachtung. Und das geht auch konform mit etwas anderem, nämlich dass das in den Evaluationsbögen ich immer wieder zu lesen bekomme. Ich würde mich mit den unwichtigen Dingen besonders ausführlich befassen und die wichtigen Dinge sehr kurz abhandeln.
52:05
Es könnte sein, dass es da unterschiedliche Auffassungen dazu gibt, was die wichtigen und was die unwichtigen Dinge bei so einem Thema sind. Das, was wir jetzt hier heute gesagt haben, hier von dieser Folie aus sind wir gestartet.
52:23
Das, was ich hier konzeptionell gesagt habe, das ist das Wichtige. Und diese, worüber wir jetzt reden, ist natürlich nur noch ein Zusatz, der natürlich nicht den entscheidenden Wichtigkeitsgrad hat. Natürlich auch wichtig ist, sonst würde ich das nicht machen. Ich mache hier nicht unwichtige Sachen.
52:45
Aber wenn wir von genetischen Algorithmen reden, dann ist das natürlich ein Nebendetail, was nicht zur Essenz eines genetischen Algorithmes gehört. So, was insbesondere, weil es jetzt ein Beispiel ist dafür, dass es keine generische Strategie ist, sondern nur eine spezielle Strategie,
53:10
die nur bei einer speziellen Problemstellung Anwendung findet, nur dafür entwickelt worden ist, nämlich beim TSB. PMX, partially mapped crossover, weiß nicht, wer sich das ausgedacht hat.
53:21
Sie kennen das aus dem Englischen, dass das öfters mal X verwendet wird für irgendwas, was da so mit einem K-Laut, mit einem Kultural-Laut anlautet. Was machen wir hier? Das erste, was wir machen, ist das, was Sie an der Tafel sehen. Wir haben hier diesen two point crossover auf Basis der Kodierung, die wir angesprochen haben.
53:48
Wir haben eine Komponente, einen Index für jeden einzelnen Knoten und der Index gibt die Position an innerhalb der Rundtour.
54:02
So, was passiert jetzt? Wir haben jetzt hier ein Beispiel. Ich mache das eigentlich am besten anhand des Beispiels, damit das klar ist. So, wir haben jetzt die zwei parents. Das sind zwei Rundtouren. Sie sehen, die obere, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.
54:20
Jeder der zehn Zahlen, wir haben zehn Komponenten, jeder der zehn Zahlen kommt genau einmal vor. Jeder Knoten hat einen, genau einen der Plätze 1 bis 10 und kein Platz wird doppelt vergeben. Und genauso hier unten 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Ah, die 11 hatte ich eben oben vergessen. Wir haben 11 Knoten.
54:43
So, das sind die beiden parents, zwei Rundtouren. Und die wollen wir, verzeihen Sie mir das Wortspiel, die wollen wir verheiraten. So, das heißt two point crossover, den Mittelteil wird einfach ausgetauscht. Ja, links vom Mittelteil bleibt alles gleich, rechts vom Mittelteil bleibt alles gleich. Die Mitte wird ausgetauscht.
55:04
So, und wenn Sie sich das jetzt, die beiden Offsprings, so wie Sie jetzt da sind, genau anschauen, dann stellen Sie fest. Beispielsweise hier, wo haben wir denn mal ein schönes Beispiel, in dem oberen Offspring O1 kommt die 2 zweimal vor.
55:24
Die 1 kommt zweimal vor. In dem unteren kommt, wie sieht es da aus, die 5 kommt zweimal vor, die 4 kommt zweimal vor. Und ich glaube, das war es dann. Die 3 kommt hier unten auch nochmal zweimal vor und hier oben die 9 nochmal zweimal vor. Und da in beiden jeweils, ich glaube, wenn ich richtig gezählt habe, 3 Positionen zweimal vorkommen,
55:48
muss es auch in jedem der beiden 3 Positionen geben, die gar nicht vorkommen. So, das sind also keine zulässigen Lösungen mehr, das sind keine Rundtouren mehr.
56:01
Ich habe den leisen Verdacht, dieses Bild ist daran schuld, dass doch eine gewisse Anzahl von Studierenden sich beim Thema genetischen Algorithmus, insbesondere auf PMX festkrallt. Muss man auch zugeben, das ist jetzt irgendwie das schönste anschauliche von dem ganzen Thema bisher.
56:21
So, was macht dieses PMX jetzt? Gehen wir nochmal zurück. Also vor allem erst einmal beachten Sie, dass wir jetzt nur noch O1 hier betrachten, nicht mehr O2.
56:41
O2 haben wir jetzt vergessen, ist egal, das funktioniert alles genauso. So, Repair Loop. Wir haben eine Schleife. Solange das noch keine Rundtour ist, solange noch irgendeiner dieser 11 Städter zweimal auftritt, soll Folgendes passieren. Wir wählen uns aus diesem inneren Bereich und aus diesem äußeren Bereich zwei Indizes mit gleicher Position.
57:11
Ja, so schauen Sie sich das nochmal an. Dadurch, dass wir von hier oben, von den Parents zu den Offspringen durch einen Austausch dieses Mittelteils gekommen sind,
57:21
wodurch, was kann denn, wie kann das denn passieren, dass das ein und dieselbe Position zweimal auftritt? Also sie kann passieren dadurch, dass sie außerhalb vom Mittelteil ist, so wie die zwei hier bei dem O1 und nochmal innerhalb vom Mittelteil ist. Nur dadurch kann sie zweimal auftreten, so wie hier unten auch bei dem O2, die drei einmal im Mittelteil und die drei einmal im Außenteil.
57:43
So, wir wählen uns also eine solche Verdopplung einer Position. Wir wissen von vornherein, wir müssen sie einmal suchen innerhalb des Mittelteils und einmal suchen außerhalb des Mittelteils. Und was wir jetzt machen ist, dass wir hier eine ganz komische Sache machen.
58:05
Den Offspring an dieser Position J außerhalb setzen wir gleich den Parent an dieser zugehörigen Position innerhalb. So, was heißt das hier? Wir gucken uns nur noch O1 an, also Sie vergessen jetzt hier nochmal O2.
58:26
Die 5 kommt zweimal vor, eine innerhalb und eine außerhalb. Und dieser 5 außerhalb wird überschrieben durch den anderen Wert, der hier steht.
58:43
Diese 5 außerhalb wird die Anschöpfung innerhalb. Diese 5 hier, gucken wir uns an, wir machen sozusagen an dieser Stelle den Tausch rückgängig. Haben wir eine 2 hier anstelle der 5. Haben zunächst einmal diese 5, diese Problematik mit der 5 gelöst, dass die 5 nicht mehr zweimal auftritt, denn eine davon haben wir überschrieben.
59:12
Irgendwas habe ich hier falsch gesagt. Irgendwo bin ich jetzt durcheinander gekommen. O1, der äußere Wert wird durch die innere Position ersetzt.
59:35
Also der äußere Wert hier, wo sind wir denn jetzt? Die 1, jetzt habe ich es glaube ich wieder.
59:40
Die 1 kommt doppelt vor an Position 1 außerhalb, an einerseits an Position innerhalb. Und dieser Wert 1 wird getauscht durch den, der hier an derselben Stelle steht, diese 6. Ja, ich gehe von...
01:00:00
Ich betrachte mir ein paar, das zweimal vorkommt und an die Stelle, wo es außerhalb des Mittelbereichs vorkommt, schreibe ich das hin, was hier innerhalb des Mittelbereichs dem gegenüber steht. Die 6, so, die haben wir jetzt hier. Bitte? Ja, okay, die Frage ist gut. Ich beziehe mich hier auf Offspring 2, habe hier die 6 hergenommen.
01:00:28
Die Frage ist, ob wir nicht den Parent 1 nehmen sollen stattdessen. Ja, schauen Sie mal. Das ist dieselbe 6 durch den Austausch. Ich hätte jetzt auch nach hier oben gehen können. Da haben Sie voll und ganz recht. Das ist Jacke wie Hose. Ich bin jetzt hierhin gerutscht, weil die beiden Zahlen irgendwie so schön nah beieinander waren.
01:00:45
Aber Sie können sich das genauso denken, so wie ich das auch formuliert habe als Formel, dass hier, dass man sozusagen so geht. Was hier hin zu schreiben ist, ist, ich gehe zu dem anderen Vorkommen von 1 und gehe hier zum P1. Ob ich jetzt hier nach da hoch gehe oder von hier aus nach da runter gehe, ist derselbe Wert.
01:01:03
Aber es ist natürlich schon wichtig, da konsistent zu bleiben. So, jetzt haben wir diesen Vorkommen der 5 durch eine 6 ersetzt und stellen fest, wir haben das Problem nur verschoben. Wir haben jetzt anstelle der 5 die 6 dupliziert. Und die 9 haben wir auch noch weiterhin dupliziert.
01:01:23
Und haben wir noch ein Duplikat? Die 2 ist auch nochmal dupliziert. So, jetzt machen wir erst einmal, als nächstes, der Algorithmus ist blind. Der nimmt sich jetzt irgendeiner, irgendeiner Position wieder her, die 2 mal vorkommt. Der ist vollkommen egal welche. Zum Beispiel die 2, die Doppelung der 2, der Position 2 macht wieder dieselbe Operation.
01:01:48
2 kommt hier vor, schreibt da, das Gegenstück ist die 5, schreibt da die 5 rein. Ok, dann haben wir aber immer noch, welche Probleme haben wir?
01:02:01
Wir haben immer noch die 6, die kommt 2 mal vor an der Position, einmal an der Position. Doppeln, eine Verdopplung und machen dieselbe Operation. Hier schreiben wir dann an diese Stelle die 3 rein. Das, was das Gegenstück von der 6 hier im Mittelteil ist. Jetzt haben wir immer noch ein Problem irgendwo. Was haben wir denn noch für ein Problem?
01:02:23
Irgendwas muss noch doppelt vorkommen. Die 9 kommen noch doppelt vor. Jetzt sind wir endlich mal nicht mehr da vorne. Jetzt sind wir mal da hinten im hinteren Anschlussstück und machen aber völlig dasselbe. An diese Position schreiben wir die 4. Warum die 4? Wir gehen hin zu anderen neuen und gucken uns an, was da steht. Das ist die 4. Und damit sind wir, glaube ich, fertig.
01:02:46
Jetzt haben wir alles gelöst. Wir haben eine neue Runde konstruiert. In dem Beispiel hat das funktioniert. Wir wollen natürlich nicht, dass diese Methode nur in diesem Beispiel funktioniert. Wir wollen natürlich, dass sie immer funktioniert. Warum funktioniert sie immer?
01:03:06
Zunächst einmal bemerken wir, was wir eben jetzt auch gesehen haben. Es kann durchaus passieren, wenn wir eine solche Verdopplung auflösen, dass wir uns eine neue Verdopplung einhandeln, an derselben Stelle, plus mit einem anderen Wert.
01:03:20
Also kann man nicht einfach jede Position, jeden Index im Array einmal durchgehen und da die Verdopplung auflösen. Man muss gucken, bis wirklich alles aufgelöst ist. Wann hört die Repair Loop auf? Dann, wenn keine Doppelung mehr da ist. Wenn keine Doppelung mehr da ist, wir haben in diesem Beispiel 11 verschiedene Werte.
01:03:45
Wir haben 11 Positionen. Keine Doppelung mehr heißt tatsächlich eine Permutation. So, also was wir beweisen müssen, ist, dass diese Repair Loop terminiert. Denn wenn sie terminiert, dann haben wir eine richtige Rundtour gefunden.
01:04:05
So, was betrachten wir hier? Haben wir den Graphen gezeichnet? Nee, wenn er nicht hier gezeichnet ist, zeichnen wir ihn an der Tafel. Wie ist die Zeit?
01:05:02
So, das ist das Beispiel, die beiden Eltern. Und was wir jetzt bauen als Graphen. Jetzt muss ich mal gucken, dass ich diesen Graphen möglichst so zeichne, dass der nicht so allzu sehr zusammenhängt. Das heißt, es müsste eigentlich ganz gut gehen.
01:05:21
Die eins, Pfeil zur sechs, Pfeil zur drei. Damit habe ich schon mal zwei Kanten erledigt. Zehn und elf stehen in so einer Beziehung zueinander.
01:05:43
Und dann haben wir noch die neun und die vier, die kommen nirgendwo außer in der einen Kante vor. Wir haben jetzt vier Kanten erledigt. Sechs Kanten haben wir. Zwei bis fünf und neun bis vier haben wir noch.
01:06:04
So, das ist der ganze Graph. Was ist dieser Graph? Also der ist jetzt eine... Sie sehen jetzt hier vor einem Easy Exposition, vor einer... Ja gut, ich würde das hier übersetzen, nicht wörtlich, sondern um es leichter verständlich zu machen, um es zu illustrieren.
01:06:24
Führen wir diesen Graph ein. Was ist dieser Graph? Naja, das sehen Sie ja hier. Dieser Graph hat sehr viel mit den Änderungen zu tun. Denn hier haben wir die Änderung von sechs zu drei. Das ist gerade die eine Kante.
01:06:40
Hier haben wir die Änderung von eins zu sechs gehabt. Das ist die Kante von eins zu sechs dort. Von zwei zu fünf haben wir irgendwo die zwei durch die fünf ersetzt. Und zehn, elf ist nochmal eine Sondersituation. Das sehen Sie hier am besten bei den beiden Parents.
01:07:01
Die hatten wir nicht ändern müssen, weil sie... Da hatten wir nichts dran ändern müssen, weil in beiden Parents sowohl die zehn als auch die elf jeweils nur innerhalb dieses Mittelbereichs vorkommen. Das heißt also, wenn wir die beiden Mittelbereiche austauschen, um sie bei einem Offspring zu kommen, bleibt es dabei eine zehn und eine elf jeweils.
01:07:26
Das Beispiel ist gerade so konstruiert, dass die beiden jeweils ihren Platz wechseln. Sie sehen, was dieser Graph beinhaltet. Und Sie sehen auch, bei jedem Mal, jedes Mal in der Repair Loop, das können wir nochmal zurückgehen zu diesem schönen großen Bild.
01:07:53
Jedes Mal in der Repair Loop, wir haben zunächst am Anfang, ganz am Anfang hatten wir das, das und das als Duplikate, glaube ich.
01:08:08
Richtig? Die neun kam zwei Mal vor, die zwei kam zwei Mal vor, die eins kam zwei Mal vor. So, jetzt haben wir die... Was haben wir zuerst gemacht?
01:08:21
Wir haben die eins durch die sechs ersetzt. Das heißt also, wenn Sie sich vorstellen, das sind drei Pointer, die auf Knoten zeigen, dann zeigt dieser Knoten nicht mehr hier drauf, sondern hier drauf. Das nächste, was wir gemacht haben, war, dass wir die... Was haben wir denn als nächstes gemacht? Wir haben die zwei durch die fünf ersetzt.
01:08:43
Das heißt also, dieser Pointer zeigt nicht mehr auf die zwei, der zeigt auf die fünf. Und Sie sehen schon, worauf das Ganze hinausläuft. Wir haben beim nächsten Mal, was haben wir jetzt gemacht? Als nächstes die sechs durch die drei ersetzt. Das heißt, dieser Pointer ist eins weiter gegangen.
01:09:02
Und zum Schluss haben wir die neun durch die vier ersetzt. Ja, und entscheidend ist, dass wir nur im a-zyklischen Bereich dieses Grafen waren. Das heißt also, dass dieses Ersetzen irgendwann zwangsläufig zum Ende kommt. Im zyklischen Teil, der zyklische Teil interessiert uns gar nicht, auch wenn er ein bisschen komplizierter ist als jetzt hier.
01:09:26
Stellen Sie sich vor, Sie haben im mittleren Bereich... Wir können das Beispiel ja mal ein bisschen weiterführen. Sie haben jetzt hier, ein bisschen größer, der mittlere Bereich.
01:09:41
Sie haben jetzt hier den mittleren Bereich. Kann man das noch lesen? Geht noch, ja? Gut, und jetzt haben Sie zum Beispiel hier irgendwo die zehn, die elf und die zwölf. Und Sie haben an den selben Positionen jetzt so ein Zykl die elf, die zwölf und die zehn.
01:10:09
So, dann haben Sie auch einen Zykl. Ich weiß jetzt nicht, warum ich den zeichnen muss. Von der zehn zur elf, von der elf zur zwölf, von der zwölf zu zehn zurück.
01:10:23
Oder vielleicht umgekehrt, weiß ich jetzt nicht, wie die Logik war, ist auch egal. Aber das spielt alles keine Rolle. Der zyklische Bereich, die Zykel sind alles... Jeder Zykel enthält nur Knoten, die nur im mittleren Bereich sind. Nur die in beiden Parents im mittleren Bereich sind und die machen keinen Ärger.
01:10:44
Das ist das Argument auf illustrative Art und Weise. Ich hoffe, illustrativ rüber gekommen. Und das ist das Argument, warum das ganze terminiert, weil es in diesem Grafen, dieses Pointerverschieberei niemals in einem Zykel enden kann, in dem es dann immer weiter geht.
01:11:05
So, und damit haben wir PMX auch schon beendet. So, wir betrachten jetzt noch weiter problemspezifische Crossover Strategien.
01:11:24
Wie viel Zeit haben wir noch? Okay, genau, warum das jetzt problemspezifisch ist, muss ich mal nachdenken. Das ist schon allgemeiner, eigentlich eine allgemeine Strategie.
01:11:44
Gucken wir uns einfach diese Strategie an, bevor wir jetzt hier weiter nachdenken. So, was passiert hier?
01:12:01
Genau, jetzt weiß ich wieder. Es ist noch eine weitere problemspezifische Crossover Strategie. Wieder TSB. Also TSB, sehen Sie, ist immer wieder ein sehr dankbares Thema, an dem man viele Dinge sehr anschaulich machen kann. Sie müssen dann natürlich immer im Hinterkopf behalten.
01:12:21
Deshalb mache ich auch immer mal ein paar mehr Beispiele, dass das jetzt hier keine Vorlesung ist über optimales Lösen des TSB, sondern über Optimierungsalgorithmen allgemein. Aber es ist halt ein schönes Beispiel für alle möglichen Zwecke. So, was passiert hier? Dazu will ich ein Beispiel, an dem ich mich aufhängen kann, leider nicht.
01:12:42
Dann muss ich das Beispiel selber basteln.
01:13:31
So, ich mache mir jetzt die Sache mal vielleicht ein bisschen einfach, indem ich zwei bestimmte Rundtouren hernehme.
01:13:42
P1, 1, 2, 3, 4, 5, 6, 7, 8, 9. Die zweite Rundtour, die ich mir hernehme, ist 9, 8, 7, 6, 5, 4, 3, 2, 1.
01:14:06
Ich hoffe mal, dass das Beispiel so, wie ich es jetzt gewählt habe, den Punkt illustriert. Wenn nicht, muss ich das Beispiel noch ein bisschen abändern. So, wir nehmen uns wieder, steht hier da oben,
01:14:23
wir nehmen uns wieder zwei Positionen her. Machen wir uns ganz einfach auch wieder. Das ist L und das ist R. Einfach gedrittelt alles. Und diesmal machen wir es von Anfang an so,
01:14:40
dass wir von Anfang an ohne Reparaturmaßnahmen schon eine Rundtour herbekommen. Zwei Rundtouren natürlich herbekommen. 1, 2, 3, Position 1, 2, 3, Position 1, 2, 3, Ende.
01:15:10
So, vielleicht ein bisschen mehr Platz für die Ziffern.
01:15:33
So, gehen wir mal durch.
01:15:40
Der zweite Spiegelstrich sagt, die Mittelteile werden einfach übernommen. 4, 5, 6, 6, 5, 4. So, jetzt sind in den beiden Offspringen noch 6 Positionen zu besetzen. Und was wir machen ist, wir nehmen die noch fehlende R ein.
01:16:04
Das Beispiel ist doch vielleicht nicht so illustrativ, wie ich es gehofft habe. Ich würde gerne dann doch den zweiten Älter nochmal ein bisschen anders definieren, damit da ein bisschen mehr Leben reinkommt in das Beispiel.
01:16:26
Weiß ich jetzt nicht. 1, 2, 3, 4, 5, 6, 7, 8, 9. So, ich hoffe, das ist jetzt ein gutes Beispiel.
01:16:40
So, ich übernehme also hier die 8, 1, 7. Und jetzt gucke ich mir hier oben an, welche fehlen. Das sind die 1, 2, 3 und die 7, 8, 9. Und die klaue ich mir für hier unten, aber in der relativen Reihenfolge.
01:17:02
Das erste, was ich links finde, ist die 2. Die 2 fehlt, klaue ich mir. Die 6 und die 4 fehlen nicht. Die 8 fehlt, ist das nächste. Die 1 fehlt, ist das nächste. Habe ich was übersehen?
01:17:24
Ja, die ist aber das nächste, was kommt. Die 7 kommt jetzt als nächstes so hier hin. Die 9 fehlt und die 3 fehlt. Ich habe mir jetzt hier alle hergenommen, die hier in der Mitte nicht sind. Alle, die noch gefehlt haben.
01:17:41
Und ich habe sie in der relativen Reihenfolge hergenommen, wie sie hier drin sind. 2, 8, 1, 7, 9, 3. Und genau dasselbe mache ich mit dem anderen Offspring. So, was fehlt? Die 2 fehlt als erstes. Ne, andersrum. Die 1 fehlt nicht.
01:18:01
Die 2 fehlt, nehme ich. Die 3 fehlt, nehme ich. Die 4 fehlt, nehme ich auch. Die 5 fehlt. Die 7 fehlt nicht. Die 8 fehlt nicht. Die 9 fehlt. Irgendetwas fehlt. Die 6 fehlt noch. Die 6 und die 9. So, und auf die Art und Weise habe ich auch eine Rekombination erreicht,
01:18:24
wo gleich ohne große Reparaturmaßnahmen, also ganz ohne Reparaturmaßnahmen, schon 2 Permutationen wieder rausgekommen sind. Und wenn Sie sich das nochmal angucken, hier mit dem Beispiel, auch in den Beispielen, die wir vorher hatten, wenn Sie sich jetzt mal die beiden Parents ansehen. Wir haben schon immer 2 Parents genommen, die sehr weit auseinander liegen.
01:18:45
Gegensätze ziehen sich an, wie im echten Leben. Und wenn Sie sich, wenn Sie jetzt mal die Parents und die Offspring miteinander vergleichen und auch die Offspring untereinander vergleichen, da ist schon gehörig was durcheinander gekommen. Ja, die Rundtouren, die da rauskommen,
01:19:02
haben nicht mehr allzu viel gemeinsam mit den Rundtouren, die wir reingesteckt haben. Hängt natürlich davon ab, wie wir das L und das R wählen. Wenn wir die ganz extrem wählen, extrem breites Mittelteil oder extrem dünnes Mittelteil, ist die Ähnlichkeit natürlich größer.
01:19:25
So, Mutation. Auf Rekombination verlässt man sich typischerweise nicht, wenn man sowas implementiert, sondern man sagt, okay, was wir jetzt eben gesagt haben, eine gewisse Anzahl von Paaren von Eltern werden für die Reproduktion ausgewählt.
01:19:43
Das kann durchaus auch bedeuten, dass ein und dasselbe Elternteil, dass ein und dasselbe Elter für mehrere Paare ausgewählt wird, wie halt im täglichen Leben, wie halt auch im echten Leben auch. Dass das keine reine 1 zu 1 Paarung sein muss.
01:20:02
So, wie wir das gesehen haben, Rekombination. Und dann, wenn man typischerweise noch mal Mutation an, muss nicht sein. Man macht es meistens, um noch mal ein bisschen Schritt weiterzukommen. Wir sind da näher dran an der biologischen Evolution.
01:20:22
Und die Erfahrung sagt, oder die Erfahrung von vielen Leuten, die damit gearbeitet haben, sagt, dass das anscheinend, ohne dass man so genau versteht, warum, durchaus positiv ist für das Endergebnis des genetischen Algorithmus. Bis jetzt kann man das nicht verstehen, warum das so ist, muss man einfach so stehen lassen als ein Erfahrungssatz.
01:20:46
So, abschließende Bemerkungen. Wie bei den anderen Themen auch, also diesen ersten Spiegelstrich kann man auch zu jedem anderen Thema sagen. Was wir hier behandelt haben, ja, man könnte auch eine Vorlesung, eine Zwei-Semester-Vorlesung rein über genetische Algorithmen machen.
01:21:02
Wäre ein bisschen vielleicht zu viel des Guten. Könnte man aber machen. Es gibt einen Haufen mathematischer Theorie. Es gibt aber noch einen viel größeren Haufen von Literatur, von wo genetische Algorithmen in verschiedensten Versionen angewandt werden auf verschiedenste Problemstellungen.
01:21:22
Beispielsweise, vielleicht sollte ich das erwähnen, vielleicht schon bei den Evaluationsstrategien erwähnen sollten. Wer an der TU Darmstadt besonders rührig ist zu dem Thema, ist Professor Adami vom Fachbereich 18 Elektro-Informationstechnik, der sehr viel mit Simulation und Robotik und so weiter macht, mehr auf der Hardware-Seite, während hier im Fachbereich 20
01:21:41
der Herr von Strück eher auf der Software-Seite arbeitet. Und also Herr Adami ist von Haus aus Regelungstechniker, bzw. das ist eigentlich sein Gebiet. Und da wendet er sehr erfolgreich solche Sachen wie Evaluationsstrategien, genetische Algorithmen an. Weil, also Erfolg ist natürlich immer relativ.
01:22:01
Weil es einfach keine, im Gegensatz zu so schönen Problemstellungen wie bei der GDI 2, für solche Regelungstechnischen Probleme, hochgradig nicht lineare Probleme mit Rückkoppelung, Rückkoppelungsschleife usw. Weil es dafür nun mal keine guten, schönen, einfachen Algorithmen gibt. Ja, das ist genau das, warum man sich mit solchen komischen Algorithmen befasst,
01:22:23
weil es einfach viele Problemstellungen gibt, die so unübersichtlich sind, dass es keine schönen Algorithmen dafür gibt. Oder zumindest hat die Menschheit diese Algorithmen bisher noch nicht gefunden, falls es sie, wie erwartet, doch gibt. Und damit ist man dann relativ erfolgreich,
01:22:41
besser als alles andere, was man bisher gefunden hat. So, es gibt auch, so wie wir es beim Simulated Inline gesehen haben, durchaus einige mathematische Ansätze, nicht quantifiziert mit Konvergenzraten, also mit der Geschwindigkeit der Konvergenz, aber so Ansätze zu beweisen unter gewissen Voraussetzungen,
01:23:04
konvergieren genetische Algorithmen tatsächlich zu guten Lösungen. Aber da ist man noch nicht wirklich, hier sehen Sie to the best of the lecturers knowledge, the lecturer ist meine Wenigkeit, zu meinem besten Wissen ist man da noch nicht wirklich in der Praxis angekommen,
01:23:25
sondern man muss dann Annahmen treffen, damit man da was mathematisch beweisen kann, die doch eher unrealistisch sind. Und wie beim Simulated Inlink, man kann sie nicht direkt übertragen, die mathematischen Ergebnisse, aber sie geben einem schon einen gewissen Anhaltspunkt,
01:23:40
was man tun sollte und warum das gut ist, wenn man das tut. Ist ja auch immerhin was, mehr kann man da wahrscheinlich von der Mathematik nicht erwarten. So, damit sind wir heute mit unserem Termin fertig, passt ja wunderbar, weil der nächste Art von Algorithmen, wir klettern hier die Evolutionsstufen hoch.
01:24:05
Zuerst asexuelle Mutation und Selektion, dann nächste Stufe sexuelle Rekombination und die nächste Evolutionsstufe ist Kultur. Dass Tiere, Menschen, also Tiere vor allem erst einmal auf vielfältige Art miteinander zusammenarbeiten.
01:24:23
Nicht nur zusammentreffen, um sich zu vermehren, sondern zusammenarbeiten für ein gemeinsames Ziel. So, Sie haben noch eine Frage?
01:24:55
Ah, okay, die Foliennummern stimmen nicht, sagen Sie. Die Foliennummer 140 stimmen nicht.
01:25:01
Okay, das muss man dann nochmal durchlaufen lassen, denke ich. Das sollte dann, das übliche Problem mit Latich, wenn es nicht zweimal durchläuft, stimmen die Querverweise nicht. Was immer noch ein vergleichsweise geringes Problem ist, im Vergleich zu Querverweisen bei anderen Textverarbeitungssystemen. Aber dazu sage ich das nicht.
01:25:21
Okay, danke für den Hinweis. Kulturelle Algorithmen, wir werden nicht so weit hochgehen, dass wir versuchen, die menschliche Kultur zu simulieren, sondern wir sind zufrieden mit einer sehr einfachen, wohlverstandenen, simpelstrukturierten Form von Zusammenarbeit, nämlich das, was zum Beispiel Ameisen so machen, um ein gemeinsames Ziel zu erreichen.
01:25:42
Für heute möchte ich mich bedanken und wünsche Ihnen noch eine angenehme Restwoche.