Neighborhood-Based Approaches - Exact Neighborhoods / Heuristic Local-Search Techniques / Simulated Annealing
This is a modal window.
Das Video konnte nicht geladen werden, da entweder ein Server- oder Netzwerkfehler auftrat oder das Format nicht unterstützt wird.
Formale Metadaten
| Titel |
| |
| Serientitel | ||
| Teil | 3 | |
| Anzahl der Teile | 12 | |
| Autor | ||
| Lizenz | CC-Namensnennung - Weitergabe unter gleichen Bedingungen 3.0 Deutschland: Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen und das Werk bzw. diesen Inhalt auch in veränderter Form nur unter den Bedingungen dieser Lizenz weitergeben. | |
| Identifikatoren | 10.5446/21465 (DOI) | |
| Herausgeber | ||
| Erscheinungsjahr | ||
| Sprache |
Inhaltliche Metadaten
| Fachgebiet | ||
| Genre | ||
| Abstract |
|
12
00:00
Nachbarschaft <Mathematik>KreisbewegungRelation <Mathematik>MengenlehreKreisbogenFunktion <Mathematik>Gerichteter GraphTeilbarkeitLokales MinimumRechenschieberBeweistheorieDreizehnNegative ZahlFluss <Mathematik>MengeSummeLokales MinimumNachbarschaft <Mathematik>ZykelKanteOptimumLösung <Mathematik>DynamikObere SchrankeGerichteter GraphLängeZugbeanspruchungMathematikComputeranimation
08:39
Feasibility-StudieGanze ZahlVorzeichen <Mathematik>PaarvergleichHelmholtz-ZerlegungMassestromBeweistheorieStatistische SchlussweiseKreisbogenFluss <Mathematik>MengeKanteGleichungZugbeanspruchungImplizite FunktionPhysikalische GrößeComputeranimation
15:36
Feasibility-StudieGanze ZahlVorzeichen <Mathematik>BeweistheorieKreisbogenStatistische SchlussweiseHelmholtz-ZerlegungMassestromPaarvergleichMengeKanteVollständigkeitFluss <Mathematik>Mathematische LogikKapazität <Mathematik>ZykelVollständige InduktionObere SchrankeKnotenmengeUntere SchrankeMinimumMathematikZugbeanspruchungSchranke <Mathematik>Wald <Graphentheorie>Computeranimation
22:33
Helmholtz-ZerlegungMassestromNachbarschaft <Mathematik>BeweistheorieGlobale OptimierungMultiplizität <Mathematik>Gebundener ZustandLemma <Logik>Negative ZahlRechenschieberRelation <Mathematik>HeuristikApproximationRadikal <Mathematik>StellenringFolge <Mathematik>IterationMinimalgradCoxeter-GruppeLösung <Mathematik>EbeneKettenregelFluss <Mathematik>RichtungOptimumMathematische LogikNachbarschaft <Mathematik>ZahlenbereichMengeZykelMatchingMathematikMinimumZugbeanspruchungZirkel <Instrument>HeuristikStellenringPhysikalische GrößeOptimierungsproblemLösungsraumStrategisches SpielCoxeter-GruppeSimulationComputeranimation
32:28
RechenschieberZufallszahlenEntscheidungstheorieRadikal <Mathematik>IterationLinseRichtungFreiheitsgradLösung <Mathematik>Physikalische GrößePhysikStatistikKanteEinflussgrößeSimulated annealingInhalt <Mathematik>AuswahlaxiomQuelle <Physik>Computeranimation
42:23
Radikal <Mathematik>E-FunktionHausdorff-RaumTieftemperaturStatistische PhysikProzess <Physik>UnendlichkeitLokales MinimumExponentialfunktionIterationZusammenhang <Mathematik>ThermodynamikZahlenbereichGanze ZahlPhysikZahlNegative ZahlAsymptoteLängeSimulated annealingKlasse <Mathematik>Reelle ZahlBillard <Mathematik>ReihenfolgeproblemComputeranimation
52:18
Globale OptimierungNachbarschaft <Mathematik>Simulated annealingFeasibility-StudieAuswahlaxiomStochastische AbhängigkeitKonstanteLoopIterationUnendlichkeitStrom <Mathematik>EnergieSummePotenzielle EnergieOptimumProzess <Physik>ZahlenbereichRichtungStruktur <Mathematik>Markov-KetteLösung <Mathematik>IterationAusdruck <Logik>Inverser LimesKanteMathematikBerechnungStochastikOptimierungMengeWahrscheinlichkeitstheorieNiedrige EnergieExt-FunktorHohe EnergieModulformStochastischer ProzessZusammenhang <Mathematik>ExponentStellenringComputeranimation
01:02:13
BeweistheorieInverser LimesFunktionalgleichungLösung <Mathematik>KonstanteExponentialfunktionIterationZahlenbereichQuotientSummeKanteMengeTermEbeneFreiheitsgradObjekt <Kategorie>Funktion <Mathematik>UmrechnungGleichungComputeranimation
01:12:07
IterationSterbezifferLokales MinimumStellenringTravelling-salesman-ProblemGlobale OptimierungKonstanteMathematikEinfach zusammenhängender RaumKonstanteLösung <Mathematik>Zusammenhang <Mathematik>EbeneLogarithmusIterationEnergieTopologieAussage <Mathematik>Gesetz <Physik>MultiplikationKanteParametersystemPhysikalischer EffektLängeE-FunktionThermodynamisches GleichgewichtMatrizenringOptimierungStützpunkt <Mathematik>MengeOptimierungsproblemReihenfolgeproblemÄhnlichkeitsgeometrieNatürlicher LogarithmusHöheComputeranimation
01:22:02
Globale OptimierungFeasibility-StudieRechenschieberStellenringUnendlichkeitTeilmengeDimensionsanalyseMinkowski-MetrikMathematische LogikLängeVerschlingungKanteMengenlehreMaximaler-Schnitt-ProblemLösung <Mathematik>VektorSchnitt <Mathematik>SummeLaufzeitMatchingTeilmengeVektorrechnungKnotenmengeUngerichteter GraphMengeKantenmengeReihenfolgeproblemKlasse <Mathematik>Gewicht <Mathematik>KomplementaritätUnendlichkeitZählenComputeranimation
Transkript: Deutsch(automatisch erzeugt)
00:02
präsentiert von Open Learnware, die Plattform für Lernmaterialien an der TU Darmstadt. So, hallo allerseits, Sie haben gesehen, ich bin jetzt schon reingekommen, halb vorbereitet, aber es dauert trotzdem wieder so lange. Gut, diesmal war ein Anfängerfehler dabei, dass ich nicht darauf geachtet habe, dass vorne der Linsenschutz weg war
00:24
und ich mich gewundert habe, dass wieder kein Bild zu sehen war. Letztes Mal, dass kein Bild zu sehen war, lag daran, dass es da tatsächlich noch irgendwo einen kleinen verschleckten Schalter gibt, den man nicht so ohne weiteres findet und der sich aus irgendwelchen Gründen umgeschaltet hat.
00:41
Aber seitdem ich das weiß, kann ich da natürlich immer schauen, wenn es nicht angezeigt ist, ob das jetzt klappt oder ob das jetzt nicht klappt. Aber es sieht jetzt alles so aus, dass alles diesmal aufgezeichnet wird. Beim letzten Mal hat es keine Videoaufzeichnung gegeben. Da werde ich dann halt irgendwelche entsprechenden Bilderchen, die ich an der Tafel gezeichnet habe, dann irgendwie noch mal nachliefern.
01:02
Ich muss mir noch überlegen, wie ich das jetzt mache. Das Rendern der Rohdaten, die hier aufgenommen worden sind, kostet eine Menge Zeit. Das muss jemand machen, der die ganze Zeit am Bildschirm, am Computer arbeitet und das man so eben nebenher mal immer anstößt und wieder einen Schritt weiter macht usw.
01:24
Das ist leider nicht mein Arbeitsstil. Mein Arbeitsstil ist doch ein bisschen mehr rumlaufen. Das heißt, ich muss jemanden finden, der die ganze Zeit am Bildschirm arbeitet, eh sowieso, und der das hin und wieder immer nebenher macht. Bis dahin muss ich sie leider vertrösten.
01:42
Die Aufnahmen sind alle da, aber das Rendern kostet doch unglaublichen Aufwand. So, gibt es noch etwas organisatorisches von Ihrer Seite aus? Gut, dann können wir ja zur Thematik wieder einsteigen. Wir waren das letzte Mal hier stehen geblieben bei diesem Thema.
02:02
Min cost flow. Sie erinnern sich, vielleicht gehen wir noch mal ganz kurz zurück zur Definition. Hier. Sie haben ein Netzwerk, also einen gerichteten Graphen. Sie haben auf jeder Kante untere und obere Schranken. Wie viel Fluss darauf sein soll, statischer Fluss.
02:21
Das heißt, erinnert sich nicht in der Zeit. Es gibt auch die Variante dynamischer Fluss. Die ganzen algorithmischen Ansätze für statischen Fluss lassen sich dann in gewisser Weise auf den dynamischen Fall übertragen. Deshalb macht es Sinn, den statischen Fall zu betrachten. Und für jeden Knoten soll gelten die Summe der Flusswerte,
02:43
die auf rausgehenden Kanten rausgeht aus diesem Knoten, minus die Summe der Flusswerte, die in diesen Knoten reingehen, soll einen gewissen vorgegebenen Wert genau treffen. Und was wir wollen, was wir minimieren wollen, ist auf jeder Kante sind noch Kosten drauf.
03:02
Pro Fluss Einheit, die darüber geschickt wird. Und diese Kosten wollen wir minimieren unter allen möglichen zulässigen Flüssen, die diese Eigenschaften haben. Jeder Flusswert, jeder Kante ist zwischen der unteren und der oberen Schranke. Und an jedem Knoten sind, es gilt diese Balance Bedingung,
03:23
wollen wir einen finden mit minimalen Kosten, so berechnet. Und wir haben schon die Nachbarschaft definiert. Der grauße Kontext ist, bevor wir zu den ganzen heuristischen Algorithmen kommen, betrachten wir uns noch diesen Fall als letzten Fall dafür, dass Nachbarschaften auch exakt sein können.
03:48
Was bedeutet, dass die einfache lokale Suche, die nichts anderes tut als solange von einer Lösung zu einer benachbarten zu springen, solange, wie es dabei immer eine stetige echte Verbesserung gibt,
04:03
dass diese Nachbarschaftssuche tatsächlich zu einem globalen Optimum findet. Die Definition von exakt ist ja gerade jedes lokale Optimum ist ein globales Optimum. Und die lokale Suche ist immer erst dann beendet, wenn sie im lokalen Optimum ist. Das heißt, keine benachbarte Lösung ist mehr besser, gleich gut oder schlechter.
04:27
Und Sie sehen hier zwei benachbarte Lösungen. Wir haben gesagt, die Nachbarschaft, zwei Flüsse sind benachbart, wenn Sie, wenn Ihre Flusswerte sich nur in einem einzigen Zykel unterscheiden.
04:40
Die Flusswerte müssen sich immer in einem Zykel unterscheiden. Sie können sich nicht irgendwie in einem Pfad oder so etwas unterscheiden, weil wenn Sie sich beispielsweise in einem nicht geschlossenen Pfad unterscheiden würden,
05:00
ja, zum Beispiel so etwas, ich sollte es etwas allgemeiner zeichnen. Sie erinnern sich, kann auch Rückwärtskanten enthalten. Ja, hier muss die Summe der rein und rausgehenden Kanten von diesem Knoten hier,
05:20
muss diese Differenz rausgehen minus reingehend BV sein. Wenn das hier der Knoten W ist, muss hier BW insgesamt sein. So, wenn zwei Flüsse sich nur auf diesem Pfad unterscheiden, dann kann nicht bei beiden Flüssen hier bei V tatsächlich BV rauskommen,
05:41
als Summe rausgehend minus Summe reingehend. Denn es gibt nur einen Unterschied auf dieser Kante und nirgendwo sonst an diesem Knoten V. Das heißt, einer von den beiden muss diese Bedingung verletzen, dass da gleich Summe BV rauskommt. Das Problem haben wir nicht, wenn wir einen Zykel haben, weil sich da alles dann, das hatten wir beim letzten Mal schon betrachtet,
06:04
weil sich da alles gegenseitig aufhebt. Wenn zwei Flüsse sich wie in diesem Beispiel hier auf der Folie genau in einem Zykel unterscheiden,
06:22
dann sorgt dafür die eine Veränderung hier und die andere Veränderung hier. Wenn die Orientierung des Zykels so rum ist, hier ein Plus, hier ein Minus, hebt sich genau auf, beides sind tatsächlich Flüsse und beide haben diese Bedingung,
06:40
die Balance an jedem dieser Knoten. Wie Sie das an diesem Beispiel hier auch nochmal nachvollziehen können. So, Behauptung, dass diese Nachbarschaft exakt ist, das bedeutet ganz konkret, exakt bedeutet, ich suche einen negativen Zykel, bei dem die Kostenwerte negativ sind, die Summe der Kostenwerte negativ sind,
07:03
wobei ich genau, das hatten wir beim letzten Mal schon betrachtet, schauen muss, Vorwärtskanten auf diesem Zykel, da zählen die Kosten positiv, Rückwärtskanten auf diesem Zykel zählen die Kosten negativ, denn ich werde ja auf diesem Zykel bei Rückwärtskanten wie hier den Fluss vermindern.
07:27
Die meisten Menschen sagen an dieser Stelle nicht vermindern, sondern erniedrigen, den Flusswert erniedrigen, ich habe mir angewöhnt, vermindern zu sagen, weil erniedrigen doch eine etwas andere Konnotation hat.
07:41
So, wir erhöhen um einen gewissen Wert, um ein festes Epsilon, den Fluss auf den Vorwärtskanten, vermindern ihn auf den Rückwärtskanten und das bedeutet, auf den Vorwärtskanten kriegen wir Kosten dazu, weil wir ja mehr Fluss drauf haben, auf den Rückwärtskanten kriegen wir weniger Kosten,
08:02
weil wir ja weniger Fluss drauf haben, deshalb suchen wir nach einem Zykel von negativer Länge. Wie man das macht, kennen Sie aus der GDE 2, Stichworte wie Bellman-Ford, Floyd Warschall. So, also man sucht nach so einem Zykel, das ist die Idee. Wenn man keinen solchen negativen Zykel mehr hat, weiß man definitiv aus diesem Lämmer hier,
08:26
dass der Fluss, den man erreicht hat, ein globales Optimum ist. Und solange man noch so negativen Zykel ist, macht man genau diese Operation, um den Flusswert, um ein bisschen zu verbessern. So, wir gehen mal hier hin, die anderen Folien hatten wir schon mal gesehen.
08:43
Das ist wieder einer von diesen Sätzen oder einer von diesen Lämmer, die einen erst mal erschlagen. Also, wenn ich sowas zum ersten Mal sehe, fühle ich mich erschlagen. Es gibt noch andere, ich weiß nicht, ich kann mich dunkel erinnern, in dem Analysis-Buch, nachdem ich als Student Analysis 2 hatte,
09:03
da gab es zum Beispiel den Satz über implizite Funktionen. Kennen Sie den? Also im Wesentlichen besagt er, dass wir eine Funktion auch dann differenzieren können, wenn sie gar nicht nach y auflösen können. Also wenn sie implizit gegeben ist als eine Gleichung x irgendwas y gleich 0 oder so.
09:21
Und allein die Formulierung dieses Satzes im Mehrdimensionalen hat mehr als die Hefte der Buchseite ausgemacht. Man kann das als eine intellektuelle Herausforderung ansehen. Man kann sich auch davon erschlagen lassen. Am besten erst erschlagen lassen und dann als intellektuelle Herausforderung angehen.
09:41
So, ich will Ihnen sagen, was hier steht. Was hier steht, ist zwei zulässige Flüsse, egal wie die aussehen, deren Differenz lässt sich beschreiben durch eine Menge von Zyklen. Durch eine Menge von Zyklen in dieser Form. Wir haben Zyklen P1 bis PK, eine endliche Anzahl von Zyklen.
10:04
Und ich kann aus F1, F2 basteln, indem ich mir jeden dieser Zyklen hernehme, mir dieses Epsilon hernehme, was es auch gibt, und genau diese Operation machen,
10:23
die wir auch beim letzten Mal gesagt haben, auf jeder Vorwärtskante des Zyklus um Epsilon 1 erhöhen, den Flusswert erhöhen, auf jeder Rückwärtskante des Zyklus um Epsilon 1 vermindern. Und wenn ich das nicht nur mit 1, mit dem ersten Zyklus mache, sondern mit allen von diesen, dann bin ich am Ende bei F2 angelangt.
10:45
Die Aussage ist, wenn ich von F1 nach F2 kommen will, finde ich immer so eine Menge von Zyklen und solche Epsilon-Werte, sodass ich von F1 nach F2 komme, indem ich nacheinander auf allen diesen Zyklen entsprechend den Flusswert ändere.
11:04
Das ist dieser zweite Spiegelstrich hier, nämlich auf den Vorwärtskanten ist der Flusswert des neuen Flusses F2 größer als der Flusswert des alten Flusses F1 auf den Rückwärtskanten umgekehrt, sodass ich also genau, wenn ich genau das mache,
11:25
auf Vorwärtskanten eines Zykls erhöhen, auf Rückwärtskanten eines Zykls vermindern, dass ich genau dann immer hier einen Schritt weiterkomme. So, noch eine kleine Folgerung daraus. Diese Zyklen sind konsistent in dem Sinne, wie wir es letztes Mal kennengelernt haben,
11:43
nämlich in dem Sinne, dass beide Zyklen, wenn die beide die selbe Kante enthalten, dann enthalten sie beide diese Kante entweder als Vorwärtskante oder sie enthalten sie beide als Rückwärtskante. In diesem Sinne konsistent, das geht ja gar nicht anders,
12:00
wenn zwei Zyklen diese Kante als Vorwärtskante hier enthalten. Wenn die eine das als Vorwärtskante enthält, dann heißt es, F2 hat hier größeren Wert als F1 und wenn der andere Zyklo diese Kante als Rückwärtskante enthalten würde, würde das heißen, F2 hat kleineren Wert als F1, aber beides zusammen geht nicht.
12:21
Entweder hat F2 größeren Wert oder kleineren Wert. Oder gleichen Wert, dann interessiert uns nicht. So, hier steht Details are left as an exercise. Möchte ich hier nicht einfach stehen lassen als eine Übung, sondern ich möchte Ihnen den Eindruck geben, warum es tatsächlich so ist,
12:42
dass je zwei Flüsse sich um in so einer Menge von Zyklen nur unterscheidet und nicht anders. Dafür brauche ich dann erstmal ein bisschen Platz.
13:22
Wenn Sie, wie geht, das kann man algorithmisch beschreiben, diesen Beweis, der hier ausgelassen ist, den ich aber nicht auslassen möchte. Sie nehmen sich jetzt eine Kante her, beispielsweise eine Kante A, wo der neue Fluss, zu dem Sie hinwollen, größeren Wert hat als der alte Fluss,
13:44
von dem Sie herkommen. So, dann markieren Sie hier einen Plus. Dann finden Sie hier garantiert eine andere Kante, so rum oder andersrum,
14:08
bei der dann dasselbe ist. Also wenn es wieder so eine Vorwärtskante ist, ich notiere das mal mit A1, eine Kante A2, sodass F2 von A2 größer als F2 von A1 ist.
14:26
Oder, bevor ich das erkläre, warum das so sein muss, nehme ich noch den anderen Fall. Sie finden jetzt hier eine Kante A3, die reingeht, wo F2, A3 kleiner F2, A3, A.
14:47
Habe ich etwas falsch? Ach so, F1, danke. F1 von A3 ist. Warum finden Sie die? Weil hier, bei diesem Knoten, bei den reingehenden Kanten,
15:04
hat der eine Fluss F2 mehr Wert, der reingeht, als der andere Fluss F1. Damit beide dieselbe Balance B haben können, muss da noch irgendwo was anderes sein, was das wieder ausbalanciert.
15:21
Es muss mindestens eine Kante geben, die das ausbalanciert. Und wenn das eine rausgehende Kante ist, die es ausbalanciert, heißt es, auch bei dieser Kante ist es so, dass F2 einen größeren Wert hat als F1. Oder wenn es hier eine Kante ist, die reingeht, die das ausbalanciert, heißt es, hier ist eine Kante bei der F2 kleiner als F1.
15:41
Das ist zwingend notwendig, wenn wir annehmen, dass das zwei Flüsse sind. Das heißt, dass Sie an jedem Knoten diesen selben B-Wert erfüllen. Rausgehende Fluss minus reingehender Fluss gleich dem B-Wert dieses Knotens. Und diese Argumentation kann man immer weiterführen, immer weiter. So lang, vielleicht so lang, vielleicht zweimal hintereinander.
16:02
Wo endet diese Argumentation? Sie muss enden, weil wir einen endlichen Grafen haben. Wo endet sie? Die einzige Möglichkeit, wo sie enden kann und wo es da nicht mehr weitergeht, ist hier. Das heißt, wenn wir nur eine Kante haben, die hier, auf dem sich der Fluss unterscheidet,
16:25
ich habe jetzt hier größer genommen, dieselbe Logik, spiegelsymmetrisch geht natürlich auch umgekehrt, wenn hier ein kleiner stehen würde. Wenn auch nur eine Kante da ist, bei der sich die Flüsse unterscheiden, dann kann man gleich die ganze, weiß man, es gibt gleich einen ganzen Zyklus,
16:41
in dem die beiden sich unterscheiden, anders geht es gar nicht. So, jetzt kann man gucken, hier ein Plus, hier ein Plus, hier ein Minus, hier wieder ein Plus, ein Minus, Minus. Jetzt gucken wir uns an, wie viel könnten wir denn, wie groß könnten wir dieses Epsilon denn setzen,
17:03
maximal, dass wir den Fluss, dass wir den Fluss maximal weit verändern. Naja, da gucken wir uns die Kapazitäten an. Für jede Vorwärtskante die oberen Kapazitäten minus aktuellen Flusswert. Um so viel können wir das verändern, mehr nicht, weil wir ja nicht über den oberen Anschlag hinausgehen dürfen.
17:26
Auf der Rückwärtskante haben wir so viel Platz, weil wir natürlich auch nicht über den unteren Anschlag ausgehen dürfen. Und wenn ich über alle diese Werte jetzt das Minimum bilde
17:47
und um diesen minimalen Wert den Fluss erhöhe, verändere entlang des Zyklus, dann passieren zwei Dinge. Also hier ist nochmal, zeichne ich nochmal ein, die Orientierung des Zyklus.
18:00
Es sind zwei Dinge passiert. Erstens, wir sind zu einem neuen Fluss gekommen, ohne die oberen und unteren Schranken zu verletzen. Und zweitens, da wo das Minimum ist, bei der Kante wo das Minimum ist, bei der Kante gibt es keinen Unterschied mehr. Bei der, ähm, warten Sie mal, äh, ne, was haben wir da jetzt hier?
18:26
Bei der Kante kann, genau, wir haben noch einen Punkt dabei, ich muss das nochmal ein bisschen neu schreiben, das ist noch ein wenig zu, das war jetzt leicht falsch nur, keine Sorge, nur leicht falsch.
18:42
Bei einer Vorwärtskante, äh, können wir den Fluss erhöhen um bis maximal da. So, wir wollen ja nicht über F2 hinausgehen, das war jetzt mein Denkfehler eben.
19:02
Wir wollen ja nicht über F2 hinausgehen. Bei einer Rückwärtskante können wir den Fluss vermindern um diesen Wert, weil wir auch nicht über F2 hinausgehen wollen. Wir können natürlich nicht über den oberen und unteren Anschlag hinausgehen,
19:24
weil der F2 selber ein Fluss innerhalb der Breite von untere bis oberer Schranke ist. Kann uns also nichts passieren. So, jetzt nochmal die Argumentation. Es passieren zwei Dinge. Erstens, wir sind, wir haben, wenn wir an diesem Zykel etwas verändert,
19:41
auf diese Art und Weise den Fluss verändert haben entlang dieses Zykles, dann sind wir wieder zu einem zulässigen Fluss gekommen. Und das zweite was passiert, dort wo das Minimum angenommen wird, gibt es keinen Unterschied mehr zwischen F1 und F2, zwischen dem neu konstruierten Fluss und F2. Und da greift jetzt, was hier unten steht,
20:02
also mit einer Vollständigung über die Anzahl der Kanten, bei denen sich die beiden Flüsse unterscheiden. Wir haben eine Kante weniger, bei der sich mindestens eine Kante, möglicherweise sogar mehr, weil wenn das Minimum an mehreren Kanten angenommen wurde.
20:21
Nach Induktionsvoraussetzung können wir jetzt diesen neuen Fluss, den wir haben, auf diese Art und Weise mit ein paar Zyklen bis F2 treiben. Und wir haben jetzt den neuen Zyklus gefunden, den wir noch zusätzlich zunehmen zu der Menge und haben damit eine Menge von F1 nach F2 gefunden. Eine Menge von Zyklen von F1 nach F2. Ist diese Logik mit der Vollständigung klar geworden?
20:43
Oder noch nicht so richtig? Es ist eine andere Art von Vollständigung, wie Sie, oder ein anderer Anwendungsbereich, als wie Sie es etwa in der Mathematik kennengelernt haben. Da ist ein typischer Anwendungsbereich Summenformel, nicht? Da rechnet man dann ein bisschen rum und hat von N-1 auf N so einen Schritt gemacht.
21:03
Das ist auch dieselbe Logik vollständigen Induktionen, nur eine andere Situation. Die Induktionsbehauptung, die wir durchziehen wollen, ist, dass sich der Fluss F1 in F2 transformieren lässt über solche Zyklen.
21:26
Vollständigung über die Anzahl der Kanten, auf denen die beiden sich unterscheiden. Induktionsanfang, wenn die Anzahl der Kanten null ist, das heißt also, wenn die beiden sich nicht unterscheiden, ist es eine leere Menge von Zyklen, trivialerweise erfüllt. Induktionsschritt.
21:40
Wir gehen davon aus, für alle Flüsse, wir haben jetzt einen Unterschied auf K-Kanten. Für alle Flüsse mit weniger als K-Kanten gilt die Induktionsvoraussetzung, dass es sich tatsächlich der Unterschied in solchen Zyklen ausdrücken lässt. Wir haben jetzt von F1 nach F2 K-Kantenunterschied.
22:00
Wir haben einen Zyklen gefunden, haben das reduziert, auf einen Flussunterschied von weniger als K-Kanten. Induktionsvoraussetzung, da haben wir die Zyklen. Wir haben diesen Zyklen mehr, den wir jetzt eben gefunden haben, fügen ihn hinzu und haben eine Transformation von F1 nach F2 mit Zyklen gefunden.
22:24
Es ist vielleicht ein bisschen ungewöhnlich, auf diese Art und Weise vollständige Induktion zu sehen, aber in unserem Bereich ist es durch Algorithmik durchaus üblich so. Gut, hier sehen Sie nochmal ein Beispiel dafür, an dem Sie nochmal nachprüfen können, dass das tatsächlich so ist.
22:44
Die roten Zahlen hier sind genau die Differenzen zwischen den beiden Flüssen. Und wir nehmen uns zum Beispiel den blauen Zyklen, könnte sein, dass wir uns den blauen Zyklen des ersten hernehmen,
23:00
Vorwärtskante mit 2, mit Unterschied 2, Vorwärtskante mit Unterschied 6, Vorwärtskante mit Unterschied 2, Minimum ist 2. Wenn wir entlang dieses Zykls den Flusswert um 2 ändern, gibt es keinen Unterschied mehr auf diesen beiden Kanten, und der Unterschied hier ist eine 4 geblieben.
23:21
So, jetzt kann man sich beispielsweise einen anderen Zyklen hernehmen, hier unten, der grüne oder türkis oder was das ist, 3, 3, 3, 7. Unterschied 3, das heißt wir verändern den Flusswert um 3, und was dann übrig bleibt sind hier nochmal 4, hier 4, hier 4 und hier 4, passt.
23:47
Und das Beispiel ist natürlich so konstruiert, dass es passt, aber der Satz sagt, dessen Beweis ich jetzt hier skizziert habe, der Satz sagt, dass es immer passt, bei jedem Beispiel. Können Sie sich anstrengen wie Sie wollen, Sie kriegen kein Beispiel hin, das nicht passt.
24:04
So, Exaktheit ist jetzt wieder dasselbe wie beim letzten Mal, als wir das bei Matching kennengelernt haben. Wie war das bei Matching? Wir haben gesehen, zwei Matchings unterscheiden sich in einer disjunkten Menge von Faden und Zyklen. Und die Argumentation war, wenn ein Matching jetzt besser ist als das andere,
24:24
dann muss in diesem Unterschied auch ein Fad sein, bei dem es von da nach da zu einer Verbesserung kommt. Und genau das, was wir gesucht haben, genau das, was die Nachbarschaft konstituiert, ein alternierender Fad, der zu einer Verbesserung führt.
24:41
Und dieselbe Logik ist hier wieder die und dieselbe Logik lässt sich auf viele andere Beispiele auch anwenden. Ich will jetzt hier nicht die Folie durchgehen, sondern ich will es versuchen, vielleicht mündlich ein bisschen davon weggehend zu formulieren, obwohl es das selber aussagt. Wir wissen jetzt, der Unterschied zwischen zwei Flüssen lässt sich beschreiben als so eine Menge von Zyklen,
25:04
jeweils mit Epsilon, Flussänderungen auf jedem dieser Zyklen. So, wenn dieser Fluss optimal ist, das ist auf der Folie F2, und der andere Fluss ist schlechter, ist nicht optimal, das ist F1,
25:21
die beiden unterscheiden sich in Zyklen. Wenn der eine optimal ist und der andere nicht, wenn der eine besser ist und der andere schlechter, dann muss es darunter einen Zyklus geben, bei dem die Kostenwerte negativ sind. Das heißt also, solange wir tatsächlich einen Fluss in der Hand haben, das ist F1 auf der Folie,
25:42
der nicht optimal ist, finden wir einen negativen Zykel, weil wenn es einen besseren Fluss gibt, muss in der die Komposition der Differenz auch ein negativer Zykel dabei sein. Es können nicht alle positiv oder gleich groß sein, sonst wäre der eine Fluss nicht besser als der andere.
26:02
Und das ist es auch schon, jetzt sind wir auch schon wieder weg von der Mathematik. Keine Sorge, jetzt kommen wir wieder zum Holistischen. Okay, ein bisschen Mathematik werden wir heute wahrscheinlich doch nochmal wieder sehen, aber andere Art von Mathematik. Gut, wir verlassen jetzt das Thema exakte Nachbarschaften.
26:23
Ich wollte Ihnen nur ein paar Einblicke geben. Ich wollte Ihnen auch zumuten, bewusst und absichtlich zumuten, dieses Wechselspiel zwischen der konkreten Ebene einer konkreten Problemstellung wie Mincos Flow, noch konkretere Ebene, ein konkretes Beispiel, aber noch abstraktere Ebene,
26:44
ganz abstrakt zu sprechen. Ich denke, das ist eine Zumutung, die vielleicht etwas ungewohnt ist, ich will nicht sagen schwierig ist, aber die viel bringt. Denn letztendlich in anderen Situationen, wenn Sie jetzt nicht gerade nur primitive JavaScript Web-Applikationen schreiben oder so,
27:07
sondern etwas anspruchsvoll ist, dann werden Sie immer wieder damit zu tun haben, dass Sie auf den verschiedenen Ebenen gleichzeitig denken müssen, auch auf so hoher Ebene, wie wir sie hier einnehmen, oft genug.
27:23
So, Schluss mit dem Wort zum Sonntag, gehen wir weiter. Also die meisten Nachbarschaften bei realen Problemstellungen sind natürlich nicht exakt, das wäre zu einfach. Man kann hoffen, dass dieser einfache Algorithmus die lokale Suche trotzdem ein gutes Ergebnis liefert.
27:42
Am Ende wird sie immer in einem lokalen Optimum sein, niemals automatisch an einem globalen Optimum. Dieses lokale Optimum kann aber beliebig schlecht sein gegenüber dem globalen Optimum. Jetzt wollen wir gucken, wie kann man aus lokalen Optima flüchten?
28:01
Das ist letztendlich die Idee der heuristischen Algorithmen. So, nochmal, damit es auch wirklich absolut klar ist, mit dem lokalen Optimum kann beliebig schlecht sein. Man kann auch immer einfach Beispiele konstruieren, wo die lokalen Optima, sämtliche lokalen Optima,
28:21
außerdem globalen Optimum beliebig schlecht sein können. Also, wir müssen nach was anderem suchen. Was kann man tun? Das ist nun ein ganz kurzer Überblick, sozusagen der Fahrplan für den Rest dieses großen Abschnitts nachbarschaftsbasierte Suche. Was kann man alles tun, um aus lokalen Optima zu flüchten?
28:40
Oder zu vermeiden, dass der Algorithmus zu Ende ist, wenn da irgendwann lokales Optimum erreicht ist? Die erste Möglichkeit, die wir uns als erstes betrachtet werden, sind Variationen, bei denen man nicht jedes Mal unbedingt zu einer Lösung, zu einer nächsten Lösung, zu einer nachbarten Lösung geht, die besser ist, sondern hin und wieder auch mal akzeptiert, zu einer schlechteren Lösung zu kommen.
29:02
In der Hoffnung stellen Sie sich das vor wie so ein Berg und Tal, also wie so eine schöne Gebirgslandschaft. Sie sind jetzt in so einem Tal drin. Stellen Sie sich so ein richtig schönes Tal vor, was durch ein See ausgewaschen ist. Also stellen Sie sich vielleicht sogar richtig ein Gebirgssee vor. Sie sind irgendwo unten in dem See drin.
29:24
Oder, na, denken ist es jetzt ein bisschen zu kompliziert. Also denken Sie sich so eine richtig schöne Wanne ausgewaschen durch einen eiszeitlichen See. Aber es gibt natürlich dann auf der einen Seite Bereiche,
29:41
die beliebig hochgehen, 4000er direkt an diesem kleinen Tal. Aber auf der anderen Seite gibt es vielleicht auch einen Pass, der gar nicht so hoch ist, da wo damals der eiszeitliche See seinen Ablauf hatte. Und die Hoffnung ist, wenn man hin und wieder mal auch erlaubt, vorwärts zu gehen durch eine Verschlechterung, dass man es schafft, in Richtung von so einem Pass zu kommen
30:04
und über den Pass rüber dann weiterzukommen, in der Hoffnung, dass es da auf der anderen Seite tiefer runtergeht. So, zweite Möglichkeit ist, dass man nicht einmal vorwärts geht, sondern erstmal eine ganze Kette von Vorwärtsschritten macht,
30:22
ziemlich blind links, und dann guckt auf diese Kette von Vorwärtsschritten, was war jetzt das Beste, und dort wieder anfängt, und dann wieder eine Kette von Vorwärtsschritten in irgendeine andere Richtung macht. Das dritte ist relativ einfach, da werde ich auch nicht viel dazu sagen. Im Prinzip läuft das hinaus. Stellen Sie sich TSP beispielsweise vor,
30:42
oder stellen Sie sich das Problem aus der Übungsaufgabe vor, aus der Programmieraufgabe vor. Sie fangen an mit einer zufälligen Lösung und wenden dann lokale Suche an. Das ist wahrscheinlich kein gutes Ergebnis, wenn Sie es einmal machen. Wenn Sie es eine Millionmal machen, zufällige Lösungen generieren und lokale Suche anwenden,
31:03
dann ist die Wahrscheinlichkeit schon sehr viel größer, dass Sie zu einer ordentlich guten Lösung kommen, weil mit großer Wahrscheinlichkeit haben Sie mal irgendwelche zufallsanfangslösungen generiert, ohne das zu wissen, weil Sie ja blind links vorgehen.
31:21
Mit großer Wahrscheinlichkeit haben Sie aber schon sehr gute Lösungen generiert, und durch die lokale Suche werden Sie natürlich noch ein kleines bisschen besser. Das dritte, das wird uns ein bisschen mehr aufhalten, da sind so Themen wie Evolutionsstrategien, genetische Algorithmen aus der Biologie motiviert, wo es darum geht, dass verschiedene Lösungen
31:40
im Wettbewerb umeinander stehen. Manche sterben, andere duplizieren sich, gehen dann in zwei Richtungen weiter, oder sogar einen Schritt weiter. Die genetische Algorithmen sind die Simulation von geschlechtlicher sexueller Vermehrung. Das heißt, zwei kommen zusammen und produzieren Nachkommen.
32:01
Wobei das immer ein Schema sein wird, zwei kommen zusammen, zwei Lösungen kommen zusammen und aus diesen zwei Lösungen werden wieder zwei neue Lösungen konstruiert, in der Hoffnung, dass diese zwei neuen Lösungen besser sind als die zwei alten Lösungen. So, nochmal hier, was sicherlich auch schon
32:22
bisher der Fall war, Bemerkungen über die Präsentation überschrift. Das bedeutet eine Anmerkung dazu, wie ich hier den Stoff aufbereitet habe, wie wir, Herr Müller-Hannemann und ich, den Stoff hier aufbereitet haben. Wir lassen viele Details in den Algorithmen offen, das haben Sie bei Lokaler Suche schon gesehen.
32:42
Das heißt, diese Details, die können Sie auf vernünftige Art und Weise füllen, wie Sie wollen. Degrees of freedom, Freiheitsgrade. Wenn Sie also tatsächlich jetzt für ein konkretes Problem, einen Algorithmus konkret anwenden wollen,
33:01
eine konkrete Implementation dieses Algorithmus bauen wollen, dann würden Sie diese Freiheitsgrade adäquat füllen mit Inhalten. Zweiter Punkt, natürlich, also die Literatur über solche Verfahren ist riesengroß, es sind unglaublich viele Verfahren entwickelt worden. Ich kann natürlich nicht hier eine erschöpfende Liste
33:23
von Algorithmen geben, aber was immer ich bisher gesehen habe in der Literatur von Verfahren sollte in dieser Taxonomie, wie wir sie hier einführen, sollten immer als Spezialfälle drin sein.
33:43
Wir gehen überall nur ganz kurz drauf, briefly touched upon, wir berühren jeden Sache nur kurz. Und um Sie in den Stand zu versetzen, gegebenenfalls hinterher, wenn Sie tatsächlich mal einen dieser Algorithmen implementieren wollen für eine konkrete Problemstellung,
34:00
dass Sie in der Lage sind, sich die in Selbststudium sehr effizient die dafür notwendigen Informationen selbst anzueignen. Oft genug kann ich dazu sagen, oft genug muss ich sagen, dass inzwischen Wikipedia schon eine sehr gute und praktisch ausreichende Quelle ist. Also ausreichend nicht im Sinne von Schulnote 4,
34:21
sondern ausreichend wirklich im Sinne von danach kann man loslegen. So ein Punkt aber dazu, wenn Sie in die Literatur schauen, es gibt leider hier keine wirkliche Standardisierung der Terminologie. Das heißt also, Sie können nicht erwarten,
34:41
Sie müssen immer gucken, ob die Begriffe, wenn Sie in eine andere Quelle schauen, ob die genau dasselbe aussagen wie hier, oder wenn Sie zwei andere Quellen miteinander vergleichen, ob deren Begrifflichkeiten dieselbe sind. Ist leider so. Wir haben in der Informatik, in weiten Teilen Informatik, keine DIN-Normen für Begrifflichkeiten.
35:03
So, der erste Algorithmus. Juhu, endlich mal ein etwas komplizierterer Algorithmus. Nicht nur dieses, nicht nur mal rumreiten auf diesem einfachen lokalen Sucher. Simulated annealing, auf gut Deutsch simuliertes Abkühlen. Das ist ein, ich hatte eben gesagt, wir werden später Algorithmen betrachten,
35:20
die aus der Biologie motiviert sind. Wir betrachten hier einen ersten Algorithmus, der aus der Physik motiviert ist. Aus Gründen, die ich mindestens zehnmal gelesen und mindestens elfmal vergessen habe, heißt er auch Metropolis-Algorithmus. Das lässt sich aber sicherlich leicht in Wikipedia oder sonst wo nachschlagen, wenn jemand wissen will, warum der Metropolis-Algorithmus heißt.
35:41
So, was ist hier anders? Das ist ein Beispiel für den ersten Punkt von Variation, nämlich wir erlauben auch Sprünge von einer Lösung zu anderen, bei denen es eine Verschlechterung gibt. Aber natürlich nicht beliebig-willkürlich, sondern nach einem kontrollierten Schema.
36:04
So, zunächst einmal bei lokaler Suche haben wir uns die benachbarten Elemente mindestens so lange angesehen, bis wir ein verbessernes Element, eine verbesserte Lösung in der Nachbarschaft gefunden haben. Das ist ein Beispiel für die Freiheitsgrade.
36:21
Wir haben nicht gesagt bei der lokalen Suche, wenn es mehrere Elemente gibt, die Verbesserungen erlauben, welches wir davon nehmen. Eins der Beispiele für die Freiheitsgrade, wenn Sie einen konkreten Algorithmus implementieren, müssen Sie natürlich entscheiden, welches genommen wird. Das kann sein, wenn Sie durch die Liste aller Nachbarn durchgehen, die erste Verbesserungsmöglichkeit, die Sie finden,
36:42
oder Sie gehen noch weiter und nehmen dann die beste Verbesserungsmöglichkeit, also die, wo der Kostenwert sich am stärksten reduziert, oder was auch immer. Hier geht es ein bisschen anders vor. Wir sind auf einer Lösung, und aus der Nachbarschaft wählen wir eine zufällige andere Lösung. Denken Sie ans TSP wieder. Das bedeutet, wir wählen zufällig zwei von den Kanten,
37:04
um diese zwei Opt-Umstöpselung zu machen, die ich jetzt hier schon mehrfach vorgetragen habe und die Sie auch in den Folien finden. So, also, beim Beispiel TSP wählen wir uns zufällig zwei Kanten. Beim Beispiel, die Rechtecke zu platzieren,
37:25
wenn Sie zum Beispiel in Ihrer Nachbarschaft Austauschmöglichkeiten zwischen zwei haben, wählen Sie vielleicht auch zwei. Oder wenn Ihre Nachbarschaft auch die Möglichkeit erlaubt, von einer Lösung zu anderen zu gehen, indem Sie ein Rechtdruck drehen, dann wäre das vielleicht auch eine Möglichkeit, die Sie jetzt rausbekommen.
37:41
So, wenn Sie zufällig wählen, dann ist es offen. Ist dieses benachbarte Element besser? Ist diese benachbarte Lösung besser als die Lösung, auf der Sie gerade sind, oder ist sie schlechter? Beides kann passieren. So, wenn die neue Lösung besser ist, machen wir dasselbe wie bei lokaler Suche.
38:01
Wir gehen einfach hin und fertig. Eine Iteration vorbei, nächste Iteration beginnt. Wenn hingegen diese ausgewürfelte, zufällige, benachbarte Lösung nicht besser ist, wenn sie gleich oder schlechter ist, dann machen wir einen Münzwurf.
38:21
Aber nicht mit einer typischen Münze 50-50, sondern mit einer genau überlegten Wahrscheinlichkeit dafür, dass wir entweder sagen, ja, wir machen diesen Schritt vorwärts, oder dass wir sagen, nein, wir verwerfen diese Lösung. Wir versuchen es nochmal.
38:41
Wir bleiben auf der aktuellen Lösung. Wir gehen keinen Schritt vorwärts. Nächste Iteration, wir versuchen es nochmal. Eine zufällige Lösung. Und dasselbe wieder. Also, wenn dieser Münzwurf, dieser nicht faire Münzwurf, kein 50-50 Münzwurf, wenn der rauskommt, ja, dann gehen wir einen Schritt vorwärts. Und ansonsten bleiben wir da.
39:02
Nächste Iteration fängt wieder von vorne an. Auf der immer noch, auf der Lösung, auf der wir immer noch sind, wählen wir wieder ein zufälliges Element aus und versuchen das Ganze nochmal. Das ist im Prinzip das Schema. Aber es wird etwas, wir müssen noch einiges hier an Details einfüllen in dieses Skelett.
39:23
Also wie bei lokaler Suche und bei allen anderen Verfahren hier, fangen wir mal an mit irgendeiner zulässigen Lösung, auch in Freiheitsgrad, ja, wie sie diese zufällige, wie diese, nein, diese beliebige, das ist keine zufällige unbedingt, diese beliebige, arbitrary, diese beliebig gewählte, zulässige Lösung, mit der sie anfangen.
39:42
Sie können versuchen zum Beispiel mit einer möglichst guten, zulässigen Lösung schon anzufangen. Oder sie können versuchen mit einer wirklich zufälligen Lösung anzufangen, die sie irgendwie gewürfelt haben. Die Erfahrung sagt, dass es sehr häufig wirklich sinnvoll ist,
40:01
nicht zu versuchen, die erste Lösung gut zu machen, sondern dass es häufig wirklich sinnvoll ist, die erste Lösung, mit der man das Ganze startet, wirklich zufällig auszuwählen. Meines Wissens gibt es dafür keine plausible Begründung, sondern es ist einfach ein Erfahrungssatz. Also wir sind hier immer im Spannungsfeld zwischen
40:22
mathematisch logischen Argumentationen und Erfahrungen. So, solange wir, nächster Freiheitsgrad, solange wir nicht der Meinung sind, dass das jetzt zu Ende sein soll, was das genau heißt, werden wir dann noch weiter ausdifferenzieren.
40:40
Wählen wir also aus der Nachbarschaft des aktuellen Elements eine neue Lösung. Und wenn die neue Lösung besser ist, ersetzen wir sie. Ansonsten machen wir diesen Münzwurf, und je nachdem was rauskommt, ersetzen wir sie, gehen einen Schritt weiter oder nicht. Und natürlich merken wir uns im ganzen Lauf,
41:02
da wir ja auch Verschlechterungen haben können, merken wir uns auch immer, welches die beste Lösung ist, die wir bis dahin gesehen haben. Das brauchen wir bei der lokalen Suche nicht. Bei der lokalen Suche wird es ja immer besser, besser, besser, besser. Das heißt, die letzte Lösung ist die beste. Wir brauchen uns nicht zu merken. Aber hier, da wir hier auch Verschlechterungen haben, macht es wenig Sinn, die letzte Lösung als Ergebnis rauszugeben,
41:24
sondern es ist besser, sich immer die Lösung zwischendurch zu merken, die beste Lösung, die man gesehen hat, auf dem Weg. Weil die letzte muss nicht unbedingt die beste sein. So, wie sieht die jetzt aus, dieser Münzwurf?
41:42
Das hatte ich hier noch mal im Englisch, biased coin flipping, also ein unfairer Münzwurf, nicht 50-50. Biased heißt im Englischen so viel wie tendenziös, in eine Richtung gehen, nicht neutral. Solche Dinge ist biased.
42:03
Spielt in der Statistik eine große Rolle, dieses Wort, weil man immer natürlich gucken muss, dass das experimentelle Setting nicht biased ist, dass man da keine systematischen Fehler einbaut, sondern nur wirklich zufällige Fehler in den Messungen drin sind. So, was machen wir?
42:22
Wir wenden natürlich einen Zufallzahlengenerator an. In Java ist, glaube ich, in der Klasse Math ein Zufallzahlengenerator namens RAND drin, kann das sein. Dunkel kann ich mich daran erinnern, dass ich damit mal herumgespielt habe. Also jede ordentliche Programmiersprache hat das eingebaut,
42:43
hat einen Zufallzahlengenerator eingebaut. Ja, was Sie machen würden, zum Beispiel, wenn der Zufallzahlengenerator, manche liefern eine reelle Zahl zwischen 0 und 1, und wenn Sie sagen, mit 80%iger Wahrscheinlichkeit soll ein Ja rauskommen,
43:00
dann würde man sagen, wenn diese Zufallzahl zwischen 0 und 0,8 ist, dann ist es ein Ja, wenn die Zufallzahl zwischen 0,8 und 1 ist, dann ist es ein Nein. Ähnlich, es gibt andere Zufallzahlengenerator, die beispielsweise eine beliebige, natürliche Zahl, eine positive ganze Zahl, eine nicht negative ganze Zahl zurückliefern.
43:20
Da müssten Sie dann halt das Max-Int mitnehmen. Bis 80% vom Max-Int ist es dann ein Ja, und darüber hinaus ist es dann ein Nein, und so weiter. So, warum sieht das so komisch aus mit Exponentialfunktionen? Die Antwort finden Sie nicht in der Formatik, die Antwort finden Sie in der Physik, in der Statistischen Physik,
43:42
in der Thermodynamik, darauf will ich hier nicht eingehen, allein auch deshalb schon mal, weil, als ich das selber gelesen habe, das ist schon lange her, das habe ich natürlich alles längst auch wieder vergessen. Wir nehmen uns das einfach zur Kenntnis, dass die Physik nahelegt im Zusammenhang mit Abkühlprozessen,
44:06
worauf ich noch zu sprechen kommen werde, was die Analogie zu Abkühlprozessen ist, dass es Sinn macht, als Wahrscheinlichkeit für ein Ja, für dieses Bias-Coin-Flipping, für diese unfaire Münzwurf,
44:25
das Jahr für ein Temperaturwert T größer Null herzunehmen. Die Wahrscheinlichkeit für ein Ja und die Wahrscheinlichkeit für ein Nein, das ist natürlich eins Minus diesem Wert. Was wir uns zunächst mal klar machen sollten,
44:43
hierbei ist, was da unten so ein bisschen reingequetscht ist, dadurch, dass dieser abgezogene Wert, wir machen ja einen Münzwurf nur in der Situation, dass wenn der neue Wert von S größer ist als der von S Stern,
45:01
das heißt also hier oben im Zähler steht was Negatives, im Nenner was Positives, also ist insgesamt das Argument zur Exponentialfunktion negativ und Sie wissen, wie die Exponentialfunktion im Negativen aussieht. Wenn Sie ins Unendliche gehen, dann konfiguriert das gegen Null
45:20
und wenn Sie zu eins gehen, an der Stelle eins auch, da hat die Exponentialfunktion den Wert eins. Also Leute, für Sie ist das alles vielleicht zwei Jahre her, für mich ist es 20 Jahre her. So, wie sieht die Exponentialfunktion aus?
45:54
Also irgendwie, ah, sind eigentlich die ganzen Wischer noch da,
46:05
die hier im Laufe der Zeit reingefallen sind? Nee, also die Wischer haben sie alle wieder rausgeholt, aber die Kreiden sind noch alle da.
46:22
So, x-Achse, y-Achse, also hier ist e hoch x und hier ist x und hier ist der Nullpunkt. So, hier ist die eins und die e-Funktion sieht so aus hier,
46:45
Asymptote, die x-Achse und so. Demats wieder? Jemand zu Hause?
47:01
Okay, ich weiß jetzt nicht, wie ich diese Nichtreaktion zu werten habe, aber ich werde sie mal als Zustimmung. So, das bedeutet, in diesem Bereich, im negativen Bereich, ist der Wert zwischen null und eins, das heißt, es ist tatsächlich eine Wahrscheinlichkeit. So, wie sollen wir diese Temperatur definieren?
47:20
Und wir haben noch offen gelassen, wann das Ganze terminieren soll. Die Antwort auf beides nennt sich in der Literatur der Cooling Schedule, das heißt also, die Planung, die Vorabplanung, wie jetzt das Abkühlen sein soll. T, dass das T heißt, ist kein Zufall, Sie haben es auf der letzten Folie gesehen oder auf der vorletzten,
47:41
T steht für Temperature, für die Temperatur. So, wie sieht so ein Cooling Schedule aus? Es ist nicht eine Temperatur, das ist entscheidend wichtig, sondern Abkühlung. Im Laufe der Zeit nimmt die Temperatur ab. Das heißt also, der T-Wert durchläuft im Laufe der Zeit,
48:02
T1, T2, T3 und so weiter. Und für jeden einzelnen dieser T-Werte, dieser Temperaturwerte, gibt es, dieser ganze Temperaturwert gilt für eine gewisse Zeit, für eine gewisse Anzahl von Iterationen, ist das der Temperaturwert. Bis danach, nach dieser Anzahl von Iterationen,
48:22
nach diesen ni vielen Iterationen, dann die Temperatur wieder ein Stück absinkt, von ti auf ti plus eins. Das ist das Schema. Das heißt also, Sie zählen mit so und so viele Male, so und so viele Iterationen waren das mit dem aktuellen Temperaturwert und Sie haben ein Schema, das Ihnen sagt, okay, nach so und so vielen Malen,
48:41
wir werden über Schema noch zu sprechen kommen, nach so und so vielen Malen mit dieser Temperatur, gehen wir eins tiefer zum nächsten tieferen Temperaturwert. So, Terminierung. Terminierung ist natürlich auf jeden Fall erstmal dann,
49:00
wenn sämtliche Temperaturwerte durchlaufen sind und für jeden Temperaturwert die Anzahl der Iterationen, die wir dafür festgelegt haben. Das heißt, wir haben damit automatisch einen Terminierungskriterium. Das wir allerdings natürlich sehr groß setzen sollten vielleicht, damit wir nicht überrascht sind. Es hat eine Sekunde nur gedauert, aber es hat nichts gebracht.
49:22
Sollte eher umgekehrt sein. Es sollte eine gewisse längere Zeit dauern, aber dafür dann auch was bringen. So, aber man wird typischerweise auch weitere Abbruchbedingungen noch einsetzen. Zum Beispiel, also hier steht Termination after fixed amount of CPU time.
49:42
Man wird wahrscheinlich doch eher Realzeit als CPU Zeit anwenden, dass man sagt, okay, ich will das Ergebnis auf jeden Fall morgen um 15 Uhr haben. Und das andere ist, was man auch oft einsetzt, dass man sagt, wenn eine Zeit lang eigentlich sich gar nichts geändert hat,
50:03
vielleicht wirklich nichts geändert hat, oder nur ganz, ganz wenig sich geändert hat, über eine gewisse Anzahl von Iterationen hinweg, die man vorher festlegt, dann soll der Algorithmus stoppen, weil wir nicht mehr glauben, dass da noch was passieren wird. Weil das einfach nur eine Verschwendung von Rechenzeit ist.
50:20
Oder man muss nur unnötig lange warten auf das Ergebnis. Das heißt also, wenn der Cooling Schedule zu lang gewählt worden ist, wiederum länger als wir es eigentlich haben, als wir eigentlich Geduld haben, mit dem Ablauf des Algorithmus, dann können wir also in einem unreifen Zustand den Algorithmus beenden
50:43
und dann diese Lösung, die beste Lösung, die wir bisher bis dahin gesehen haben, dann hernehmen. Was natürlich sicherlich nicht eine Verbesserung darstellt in Bezug auf Qualität der Lösung. Was sprachlich ist hier, nach meinem Kenntnisstand,
51:00
kann man das so im Englischen nicht schreiben, wie man das im Deutschen schreiben kann. Man müsste schon hier einen Nomen dazusetzen, disallows one to stop the procedure oder sowas. Oder disallows the user to stop oder sowas. Aber jedenfalls nicht einfach disallows to stop. Keine Garantie, aber nach meinem Wissen und Verständnis
51:20
ist es so, dass es so, wie es hier formuliert ist, äußerst ungutes Englisches. So, Konvergenz. Was bringt das alles? Vielleicht nochmal zurück. Simuliertes Abkühlen. Wenn wir nochmal drauf zu sprechen kommen, da gibt es noch eine Folie dafür.
51:41
Simuliertes Abkühlen. Stellen Sie sich vor, Sie haben einen großen, irgendwas extrem aufgeheiztes, ein großes Los, etwa Metalllos, etwa in einer Stahlfabrik, ist ein typisches Beispiel. Massiv aufgeheizt. Und das müssen Sie jetzt abkühlen.
52:03
Und zwar mit einer Zielsetzung, mit einem Optimierungsziel dabei. Wenn Sie das Schock abkühlen, dann ist die Struktur dieses Materials, gerade bei metallischen Materialien etwa, schlecht. Bei Schockabkühlung haben Sie eine Menge
52:21
Risse und Frakturen ähnliches drin. Wenn, im schlimmsten Fall zerreißt es Sie sogar, wenn Sie zu schnell Schock haben, wenn das Material nicht stark genug ist, um diese Schockkühlung auszuhalten. Was Sie haben wollen, damit Sie eine gute, was Sie machen müssen, damit Sie eine gute
52:41
Struktur haben, für das Endergebnis, wenn es abgekühlt ist, ist langsam abkühlen. Das hat sehr viel mit Optimierung in unserem Sinne zu tun, weil wir reden hier von potenzieller Energie. Erinnern Sie sich dunkel aus einem Physikunterricht? Irgendwas mit komischen Formeln, wo immer ein halb davor steht.
53:01
Bei Energie steht immer ein halb davor. Weil, wenn Sie abkühlen, die potenzielle Energie springt lokal
53:22
hoch und runter. Es fängt an sich ein bisschen abzukühlen, aber durch die dynamischen Prozesse geht es auch mal wieder ein bisschen an der Stelle ein bisschen wärmer. Wenn es die Gefahr läuft, dass hier ein Riss entsteht, dass hier gerade sich ein Riss abkühlt, ist immer noch eine große Chance dabei, dass durch die hohe Energie,
53:42
die herrscht in diesem Festkörper, dass das noch mal sich ändert und dieses Festfrieren eines Risses dann noch mal verhindert wird. Und je höher die Temperatur ist am Anfang, umso weniger Gefahr besteht.
54:05
Und wenn die Temperatur langsam abkühlt, man muss sie langsam abkühlen, wenn sie sich langsam immer mehr, dass das Material in gewisser Weise friert, also friert ist das falsche physikalische Wort, aber immer mehr durch Abkühlung in feste Strukturen
54:22
reingeht, immer noch mal eine Chance aus einer Situation, aus einer Konstellation mit zu hoher potenzieller Energie, Risse und so was sind einfach zu hohe potenzielle Energie. Ein Riss in der Struktur ist eine
54:43
lokale Stelle, an der sehr hohe potenzielle Energie ist, zu hohe. Wenn die Struktur homogen ist, ist die potenzielle Energie geringer. Also immer wieder, auch wenn es schon kurz vor der Abkühlung ist, vor der endgültigen Abkühlung ist, immer noch eine gewisse Chance, immer noch genug Energie da, dass die Chance besteht,
55:02
aus einem Level von hoher potenzieller Energie rüberzuspringen, auf ein Level von niedriger Energie, durch Energie, die da ist, die Möglichkeit eben mal die potenzielle Energie mal einen Schritt hoch zu bringen und dann wieder hoffentlich tiefer zu bringen.
55:22
So, und das konvergiert gegen einen, dieses langsame Abkühlen konvergiert, gegen einen Materialklotz, wenn man langsam genug abkühlt, gegen einen Materialklotz, der sehr, sehr homogene
55:41
Struktur hat. Natürlich wird man nie das Optimum haben, es wird immer kleine Risse oder ähnliches in der Struktur noch geben, aber man ist dann schon sehr nah dran an diesem Optimum. Und in Analogie zu diesen, zu den thermodynamischen Beschreibungen dieses Konvergenzverhaltens, kann man
56:01
auch hier Konvergenz beweisen. Ups, falsch. Wir betrachten jetzt eine stark zusammenhängende Nachbarschaft. Sie erinnern sich aus der GDI2 oder sonst woher, was stark zusammenhängt heißt, das heißt, sie kommen, wenn sie
56:22
das wieder als einen Grafen betrachten, die zulässigen Lösungen sind Knoten und Nachbarschaftsbeziehungen sind gerichtete Kanten von einer Lösung zu einer benachbarten Lösung. Stark zusammenhängt heißt, sie kommen auf Faden von jedem Knoten zu jedem, zu jedem anderen. Und zurück. So, wir betracht, wir gehen jetzt ein bisschen
56:42
in eine unrealistische Welt, die wir nicht wirklich in dieser Form in einem Algorithmus pressen können, aber der Algorithmus ist nicht weit weg davon. So, zunächst einmal betrachten wir die Situation, die Temperatur ist konstant und jetzt wird es unrealistisch. Wir haben unendlich viele Iterationen. Ja, für Konvergenz, Betrachtung im Sinne
57:01
der Analysis, im Sinne der Mathematik haben wir brauchen was unendliches. Die Anzahl der Iterationen soll endlich sein. Also was passiert, wenn wir den Algorithmus bis in alle Ewigkeiten laufen lassen? So, hier gebe ich Ihnen, ja, schlage ich Ihnen erstmal einen Fakt um die Ohren, den
57:22
Sie fressen müssen, weil, ich gehe mal ganz kurz eins weiter, weil der Beweis dieses Faktums nicht in unsere Vorlesung reinpasst, sollten Sie sich in der Mathematik vertiefen in Richtung Wahrscheinlichkeitstheorie, dann werden Ihnen Markovketten und
57:42
erguden Theorie, erguden Satz begegnen und werden Sie gut aufgepasst haben in dieser Vorlesung über stochastische Prozesse, Wahrscheinlichkeitstheorien stochastische Prozesse, dann wird es für Sie ein leichtes sein, aus diesem erguden Satz als Spezialfall, als Anwendungsfall, dieses Faktum zu
58:01
beweisen. Aber ist nicht unser Thema hier, um das zu beweisen, müssten wir eine ganze Menge Wahrscheinlichkeitstheoretischen Apparat hier einführen, da sprengt die Veranstaltung. Glück für Sie, wenn Sie nicht so viel mit beweisen am Hut haben. Soll ja vorkommen.
58:21
So was steht hier? So was ist dieser dieser Wert, für den wir den Grenzen, für den wir den Limit bilden? Der ist indiziert mit der Temperatur, die wir als fest, beliebig aber fest vorgegeben haben, beliebig aber konstant und dem Laufindex K, das ist die
58:41
Wahrscheinlichkeit für eine, für eine, für irgendwelche, eine ausgewählte, beliebig ausgewählte Lösung S, dass Inschritt K, S die, die Lösung ist, auf der die Suche gerade steht. Ja, also, wenn K eine
59:01
Million ist, beispielsweise, und ich habe als S irgendeine Lösung beim TSB her, nehme mir irgendeine Rundtour her, dann ist P, K, T, S die Wahrscheinlichkeit dafür, dass in diesem, für K gleich eine Million, dass dieses, dass diese Lösung im eine millionsten Schritt
59:20
gerade die Lösung ist, auf der wir gerade stehen. So, diese Wahrscheinlichkeit können wir nicht angeben, weil, allein schon deshalb, weil sie hängt natürlich noch von etwas ab, sie hängt von der Startlösung ab. Ja, stellen Sie sich vor, K gleich eins, Startlösung. Ja, die
59:42
Lösung, die wir als Startlösung gewählt haben, hat Wahrscheinlichkeit eins, alle Ernahmen, Wahrscheinlichkeit null. Also können wir diese Wahrscheinlichkeit überhaupt nicht berechnen irgendwie, aber wir können ihnen den Grenzwert berechnen. Das ist kein Widerspruch, auch wenn wir diese Wahrscheinlichkeit nicht wissen.
01:00:00
Oder andersrum gesagt, egal wie die jetzt genau aussehen, egal wo wir gestartet sind, welches die Startlösung war, im Grenzfall, wenn wir unendlich viele Schritte machen könnten, ist diese Wahrscheinlichkeit, dass es das aktuelle Element ist, konvergiert gegen diesen Wert.
01:00:22
Das ist ein typischer Wert, ein Ausdruck geteilt durch die Summe dieses Ausdrucks über alle zulässigen Lösungen, sodass sich diese Werte alle zu eins aufsummieren. Was Sie oben im Zähler haben, haben Sie unten im Nenner wieder. Sie summieren das hier für alle zulässigen Lösungen auf. Und
01:00:48
wenn Sie jetzt alle zulässigen Lösungen hier betrachten, das aufsummieren, dann kommt insgesamt eins raus, weil hier unten ja schon die Summe steht. Also vielleicht damit, dass kein Missverständnis da übrig bleibt, was ich damit meine. Die Summe über
01:01:30
alle zulässigen Lösungen von diesem Ausdruck links ist gleich die Summe einfach eingesetzt, was da steht.
01:02:00
Also Ihnen ist diese, ich weiß, die Frage ist jetzt spät, aber Ihnen
01:02:03
ist diese Schreibweise vertraut, dass man nicht E hochschreibt, sondern EXP von irgendwas. EXP von X ist nun eine andere Schreibweise für E hoch X, dass Ihnen vertraut.
01:02:22
Gut. EXP von, was steht da oben, minus OBJS durch T geteilt durch diese Summe.
01:02:40
S, nein ich muss jetzt einen anderen Laufindex wählen, habe ich da oben auch gemacht. T aus F von I. Nochmal von diesen Werten, EXP von minus OBJS von T geteilt durch T. Und was kommt dabei raus? Das Endergebnis ist eins. Es handelt sich also
01:03:02
tatsächlich um Wahrscheinlichkeiten, weil jede einzelne ist größer Null und zusammen ergeben sie eins. Also ich bitte mal verzeihen, dass ich so ein bisschen komisch laufe. Ich habe am Wochenende jemandem beim Umzug geholfen und das sollte man sich in meinem Alter genau überlegen.
01:03:28
So, also das nehmen wir erstmal als Wahrheit her. Sage ich Ihnen einfach so, das ist die Wahrheit. Punkt. Wenn Sie es nicht glauben, gehen Sie in entsprechende Lehrveranstaltungen. Sie sehen hier, um was für Lehrveranstaltungen es geht. So, das interessante Punkt
01:03:43
ist jetzt der. Müssen wir jetzt ein bisschen genau sehen, was das heißt. Das ist ein bisschen komplizierter. Der interessante Punkt, den wir dann tatsächlich noch beweisen können mit unseren mathematischen Kompetenzen, ist der, wenn wir jetzt, egal wie der Cooling Schedule genauer aussieht,
01:04:08
wenn wir jetzt gleichzeitig unendlich viele Schritte machen, unendlich viele Iterationen dieses Algorithmus machen und dabei nicht T wie eben konstant lassen, die Temperatur konstant lassen, sondern egal wie gegen null konfigieren lassen, dann ist die Aussage die, dass
01:04:32
die Wahrscheinlichkeit, dass die Suche auf einer optimalen Lösung ist, tendiert gegen eins.
01:04:43
Hier ist es andersrum formuliert. Wenn wir eine nicht optimale Lösung haben, dann geht die Wahrscheinlichkeit dafür, dass das die aktuelle Lösung nach K Schritten ist für K gegen unendlich und T gegen null. Die geht gegen null. Das heißt also, was haben wir hier? Wir haben ein Konvergenz, wir haben ein hartes Konvergenz, eine harte
01:05:06
Konvergenz Aussage. Wenn wir schaffen würden, den Algorithmus unendlich lange laufen zu lassen, dann ist er mit Wahrscheinlichkeit eins. Zum Zeitpunkt unendlich plus eins, was er immer das heißen mag, ist er mit Wahrscheinlichkeit eins. Läuft er nur noch auf irgendwelchen optimalen Lösungen rum. Es kann ja mehrere optimale Lösungen geben.
01:05:23
Das heißt, er muss nicht einfach auf einer stehen bleiben. Was bedeutet das jetzt für die Praxis? Das bedeutet für die Praxis, wir müssen es lange laufen lassen und dann sind wir schon sehr nah dran an diesem schönen Ergebnis. Wir werden es natürlich nie erreichen. Wir werden niemals ein solches Konvergenzergebnis hundertprozentig erreichen. Aber wir kommen dem nahe.
01:05:49
Das will ich jetzt weiter vertiefen, aber zunächst mal kurz den Beweis, der ist wirklich nicht so lang. Wir betrachten uns zwei zulässige Lösungen. Sie können sich vorstellen, eine ist wieder optimal, die andere ist
01:06:02
nicht optimal. Allgemein, wir betrachten zwei zulässige Lösungen mit unterschiedlichen Zielfunktionswerten. S1 ist besser als S2. Jetzt gucken wir uns diesen Quotienten an. Den hier. Geh nochmal zurück. Was steht denn da? Das ist hier oben dieser Term und da unten ist eine Konstante.
01:06:24
Für festes T ist das ein konstanter Wert, hängt nicht ab von irgendeiner einzelnen Lösung. Das hier hängt ab von einer einzelnen Lösung S. Das hier ist für jede Lösung S derselbe Wert. Das heißt, wenn ich jetzt hier den Quotienten nehme, wie hier, kürzt sich das raus. Und übrig bleiben die beiden Zähler. Die beiden Nenner sind identisch.
01:06:46
So, für k ging unendlich, war eben die Aussage, bei festem Temperatur T. Für k ging unendlich, kommt bei fester Temperatur T das raus. Im Quotienten, weil sich die Nenner auskürzen, weil sie identisch sind, bleibt der Quotient der beiden Zähler.
01:07:06
Nach bekannter Umrechnungsformel kann ich den Quotienten aus zwei Exponential ausdrücken zu einer Summe bzw. in diesem Fall zur Differenz machen.
01:07:22
Das ist dasselbe. Das ist nichts anderes als, im Grunde ist das die Funktionalgleichung der Exponentialfunktion. Also was dahinter steht ist einfach E hoch X plus Y gleich E hoch X mal E hoch Y.
01:07:43
Oder Sie können es auch so haben, E hoch X minus Y gleich E hoch X durch E hoch Y. Mehr ist das nicht, was da angewandt wurde. Und wenn dieser Ausdruck hier oben, der Nenner ist positiv, steckt positiv immer. Einmal
01:08:07
größer Null. Der Zähler, was ist denn der? Der ist eine feste Konstante größer Null.
01:08:21
Sind wir jetzt richtig? Genau, der Zähler ist eine feste Konstante größer Null. Für zwei gegebene zulässige Lösungen ist der Zähler fest. Und wenn ich jetzt die Temperatur nicht mehr festhalte, sondern gegen Null gehen lasse, geht das Argument gegen unendlich. Und wenn das Argument für die Exponentialfunktion gegen unendlich geht, geht auch der Exponentialfunktionswert gegen unendlich.
01:08:47
So, dieser Quotient geht gegen unendlich. Wir haben zwei Wahrscheinlichkeiten, deren Quotient gegen unendlich geht. Was heißt das? Sie haben zwei Zahlen, die sind beide zwischen Null und Eins und ihr Quotient geht gegen unendlich.
01:09:01
Das bedeutet, dass ich jetzt nicht verkehrt drum sage, das bedeutet, dass was im Nenner steht, diese Quotienten, diese Wahrscheinlichkeit geht gegen Null. Anders kann der Quotient zweier Wahrscheinlichkeit nicht unendlich werden.
01:09:23
Genau, und nur wenn für die weniger gute Lösung die Wahrscheinlichkeit gegen Null konvergiert, dann funktioniert das. So, für jede Lösung S2, die nicht optimal ist, kann ich eine bessere Lösung finden und kann aus dieser Folie ableiten, deren Wahrscheinlichkeit geht gegen Null.
01:09:44
Wahrscheinlichkeit, dass das die aktuelle betrachtete Lösung ist. Diese Argumentation funktioniert nur bei den optimalen Lösungen nicht. Bei allen Lösungen, die nicht optimal sind, funktioniert diese Argumentation auf dieser Folie. Und für alle diese können wir damit beweisen, dass die Wahrscheinlichkeit, dass wir
01:10:03
an dieser Lösung vorbeikommen, gegen Null geht im Laufe dieses unendlich langen Algorithmus. Was nichts anderes bedeutet, als dass dann die Wahrscheinlichkeit für die optimale Lösung gegen Eins gehen muss. Denn irgendwo muss ja die Gesamtmasse Eins noch bleiben. Sie kann nur auf den optimalen Lösungen bleiben.
01:10:24
So, das ist das, was ich eben gesagt habe. Interessante Bemerkung, man kann nicht nur schließen, dass die optimalen Lösungen sehr wahrscheinlich werden, wenn wir nur langsam genug abkürzen.
01:10:43
Sondern von diesen Kurzenten hier, wenn Sie sich die nochmal genau anschauen. Wenn das gegen unendlich geht, dann bedeutet das, im Laufe des Algorithmus werden bessere Lösungen immer wahrscheinlicher und schlechtere Lösungen immer weniger wahrscheinicher.
01:11:01
Also es ist nicht nur eine Null Eins Sache. Ganz am Ende, nach unendlich vielen Schritten auf den optimalen Lösungen Wahrscheinlichkeit Eins, auf den nicht optimalen Lösungen Wahrscheinlichkeit Null. Sondern schon im Verlauf des Algorithmus trennt sich das. Je besser eine Lösung ist, umso größer ist die Wahrscheinlichkeit, dass wir an ihr vorbeikommen. Ist doch schön, oder?
01:11:22
Und wenn man Simulated Aging gut implementiert, wofür man vielleicht doch ein bisschen Erfahrung braucht. Dann oder für Kreativität, wenn man dann herumspielt mit den ganzen verschiedenen Freiheitsgraden, die wir hier betrachtet haben. Dann kann man auch ordentlich gute Lösungen damit rauskriegen für viele verschiedene Arten von Problemstellungen.
01:11:44
Ich will Ihnen ein Beispiel nennen, wo Simulated Aging erfahrungsgemäß sehr sehr gut funktioniert. Und zwar ist das das Zeichnen eines Grafen in die Ebene. Wenn Sie einen Grafen visualisieren möchten, dann haben Sie ja erst mal nur den Grafen gegeben als eine Menge von Knoten und eine Menge von Kanten.
01:12:07
Wir reden jetzt von ungerichteten Grafen. Als eine Adiazensmatrix oder irgendetwas. Sie wollen aber den Grafen so zeichnen, dass er übersichtlich ist und dass er entsprechende Aussagekraft hat.
01:12:42
Zum Beispiel, wenn Sie so eine eng zusammenhängende Komponente haben, dann sollen die beieinander sein. So vielleicht, wenn es mehrere Komponenten sind, die nichts miteinander zu tun haben, sollen die ein bisschen getrennt sein.
01:13:00
Was Sie da machen können ist zu sagen, okay, wir haben wieder so eine physikalische Vorstellung. Zwei Knoten, die sich berühren, die ziehen sich ein bisschen an. Zwei Knoten, die sich nicht berühren, die stoßen sich ein bisschen ab. Und auch Knoten und Kante, die nicht zusammengehören, so wie hier so in diesem Schema, da ist auch eine gewisse Abstoßung.
01:13:23
Beziehungsweise zwei Kanten, die nichts miteinander zu tun haben, ist auch eine gewisse Abstoßung. Oder, letzter Punkt, die Kanten, die von einem Knoten ausgehen, sollten eine gewisse Abstoßungskraft haben, damit sie sich möglichst gleichmäßig verteilen.
01:13:41
Ein Optimierungsproblem wäre dann, ein energetisches Gleichgewicht zu kriegen, eine Zeichnung in die Ebene von minimaler enthaltener Energie noch, wo die Abstoßungs- und Anziehungskräfte im Gleichgewicht sind. Das ist ein Beispiel dafür, was mit Simulated Leaning sehr gut geht.
01:14:09
Es gibt natürlich noch mehr Beispiele, aber das ist sicherlich das Anschauigste. So, was wir noch nicht gesagt haben, ist, wie wir diesen Cooling Schedule definieren. Da sind wir frei darin, wie wir das machen wollen.
01:14:20
Es gibt eine ganze Menge mathematischer, theoretischer Arbeiten über Simulated Leaning und alles, was damit zu tun hat. Es gibt Arbeiten, aus denen kann man schlussfolgern, dass es eine gute Idee ist, auf die Art und Weise, so wie hier, den Cooling Schedule zu definieren. Man hat eine konstante C und jede Temperatur ist C durch den Zweierlogarithmus oder natürlichen Logarithmus, ist egal, von dem aktuellen Schritt.
01:14:54
Das heißt also, dass ich tatsächlich auch von der aktuellen Temperatur, dass das egal
01:15:05
ist, ob der Zweierlogarithmus oder natürlichen Logarithmus oder irgendetwas steht, folgt aus den Logarithmengesetzen. Das würde ich gerne noch mal kurz als Erinnerung anbringen. Ich nutze jede Gelegenheit, um den Studierenden noch mal klar zu machen, dass
01:15:25
der Logarithmus keine Schikane von Lehrern und von Professoren ist, sondern eine sinnvolle Sache. Sie kennen das ja aus der GDI 2, ja, Bäume haben logarithmische Höhe und ähnliches.
01:15:47
So, wenn wir hier C durch log K von einer Basis A haben, dann, wie Sie wissen, der Logarithmus, sollten Sie das wissen, mit zwei Logarithmen mit demselben Argument oder unterschiedlichen Basen,
01:16:11
ist unabhängig vom Argument, ist nämlich genau das, diese Konstante, in der das Argument nicht mehr vorkommt.
01:16:20
Das heißt also, Sie können das ersetzen durch das mit einer anderen Basis, wobei C Strich gleich C, jetzt muss da irgendwie das mit reinkommen. Warum muss das reinkommen? Muss ich das multiplizieren oder muss ich das dividieren?
01:16:41
Sie können das von relaxt sitzend, davon von ferne besser jetzt als ich überblicken. C Strich gleich C mal, oben steht B, unten steht A, also Logarithmus, wenn ich das richtig gesehen habe, so rum.
01:17:05
War es auch hier wieder Erinnerung, gleich eins durch Umdrehung, Austausch von Basis und Argument.
01:17:24
So, kann ruhig stehen bleiben. So, diese Tiefe, von der hier gesprochen wird, das ist das, was ich vorhin versucht hatte anschaulich zu sagen mit dem Gebirgstal.
01:17:42
Wenn der unterste Punkte von dem Gebirgstal, die Tiefe ist sozusagen der Höhenunterschied zu dem Pass, über den man rüberkommen kann. Ja, ich habe das so versucht zu formulieren, Sie haben so ein paar 4.000 da drum herum, aber Sie haben zwischen den 4.000 auch mal so den einen oder anderen Pass.
01:18:03
Und die Tiefe ist der Pass, also der niedrigste Pass, die niedrigste Höhen, die Sie erreichen müssen, um aus diesem Gebirgstal rauszukommen. So, die minimale Temperatur sollte so hoch sein, das sind Argumente aus der Mathematik, auf
01:18:30
die ich hier nicht weiter eingehen will, die ich Ihnen nur einfach zur Kenntnis geben will. Und wenn man das so macht, dann kann man in der Mathematik einige, also Konvergenzraten,
01:18:41
nicht nur einfach feststellen, ja, das konvergiert, sondern auch etwas über Aussagen, wie schnell es konvergiert. Wobei diese Aussagen, wie schnell es konvergiert, mitunter dann doch nur bedingt für die Praxis hilfreich sind.
01:19:07
Ja, also Sie sehen, die Mathematik kann etwas darüber Aussagen, aber das ist für die Praxis doch nicht so wichtig.
01:19:24
Doch, da ist noch eine Lücke drin, das ist für die Praxis nur bedingt hilfreich. So, Diskussion. Simulated annealing ist populär, wird häufig verwendet. Warum? Es ist leicht zu implementieren. Es ist kaum komplizierter zu implementieren als lokale Suche.
01:19:46
Im Gegenteil, wenn Sie sich freuen, es ist vielleicht sogar einfacher zu implementieren als lokale Suche. Sie erinnern sich lokale Suche, müssen wir alle Nachbarn durchgehen, bis wir eine Nachbarn gefunden haben, der eine Verbesserung erlaubt. Bei simulated links suchen wir uns zufällig Nachbarn raus. Wie ich vorhin sagte, wir suchen uns zufällig zwei Kanten raus im Beispiel TSB.
01:20:05
Sogar einfacher in gewisser Hinsicht zu implementieren als die einfache lokale Suche. Der Programmierer muss keinen großen mathematischen Background haben. Er muss verstehen, dass x, wenn hier x steht, dass er dann die Funktion math.x anzuwenden hat. Das ist alles. Wenn man das einen mathematischen Hintergrund nennen
01:20:24
will, ist ganz ordentlich, liefert für viele Problemstellungen recht gute Lösungen. Und was man überall beobachten kann, so auch sicherlich in der Informatik, je cooler der Name ist, umso erfolgreicher ist irgendwas.
01:20:46
Wenn Sie sich vorstellen, Sie wollen einen Chef überzeugen, dass Sie die und die Methode verwenden wollen, der Chef ist vielleicht auch gar kein Informatiker und schon gar nicht Mathematiker. Sagen wir mal vorsichtig ein Betriebswirt oder ähnliches. Sie stellen sich die zwei Situationen vor.
01:21:05
Sie kommen einmal hin und schlagen vor in Ihrer Präsentation, in Ihrer Vorstandspräsentation. Ich schlage vor, Algorithmus blablabla mit unter besonderer Berücksichtigung blablabla zu machen. Oder ich schlage vor, simulated link zu machen. Wird vermutlich zu unterschiedlichen Reaktionen führen.
01:21:24
Solche Dinge, solche psychologischen Effekte gibt es. Also immer dran denken, wenn Sie irgendwas entwickeln, immer ein cooler Name dazu. Sie sehen ja in der Industrie, gerade auch in der IT Industrie, wie sehr dieser Ratschlag beherzigt wird.
01:21:47
So, das ist aber natürlich noch die natürliche simulated link, nicht die Lösung aller Probleme. Wir reden ja hier über NP-schwere Probleme wie das DSB, bei denen wir nicht hoffen können, dass es mal der einst eine, dass es einen Algorithmus gibt, der die wirklich löst in der vernünftigen Zeit.
01:22:04
Wir haben hier ein Konflikt zwischen Laufzeit und Qualität. Wir können früher abbrechen oder einen kürzeren Cooling Schedule machen. Müssen aber dann, riskieren dann aber, dass die Lösung, die wir am Ende rausbekommen, schlechter ist. Und was durchaus ein Problem ist, Sie müssen einen Algorithmus wie simulated link tune.
01:22:28
Sie müssen Experimente laufen lassen auf realen Daten mit verschiedenen Cooling Schedules, mit verschiedenen Abbruchkriterien und so weiter, bis Sie dann eine Lösung haben, die vernünftig gut läuft.
01:22:41
Sie müssen aufpassen, dass Sie kein Overtuning machen, dass Sie jetzt nicht für die paar Beispiele, auf denen Sie es laufen lassen, super gute Lösung haben. Aber wenn das nächste Beispiel kommt, ist alles wieder Mux. Das ist durchaus ein Problem, aber es ist ein handwerkliches Problem.
01:23:03
Es ist nicht ein Kreativitätsproblem, sich einen ganz neuen Algorithmus auszudecken. Und das ist ein entscheidender Unterschied. So, ich hatte schon kurz angedeutet, was simulated link, was das ist.
01:23:22
Ja, alles, was hier drauf steht, habe ich schon gesagt, können wir abhaken. So, damit sind wir schon durch mit simulated link. Es gibt, also man könnte locker eine ganze Vorlesungsreihe hier, ganzes Semester lang, nur mit simulated link gestalten, insbesondere mit den ganzen mathematischen Arbeiten dazu. Aber das ist nicht Sinn dieser Vorlesung hier.
01:23:40
Gehen wir zum Nächsten über, ich hatte ja heute am Anfang gesagt, auf jeder, bei jedem Algorithmus briefly touched upon. Gucken wir uns immer nur kurz an. So, jetzt gucken wir uns zu einer ganze Klasse von lokalen Suchalgorithmen an, bei denen wir zusätzlich zur Nachbarschaft eine weitere Struktur erwarten, die sehr, sehr häufig gegeben ist.
01:24:06
Nicht immer, aber sehr, sehr häufig. Und aus dieser Struktur leitet sich auch die Nachbarschaft ab. So, denken Sie an TSP wieder als schönes Beispiel.
01:24:24
Die Features, von denen hier auf dieser Folie die Rede ist, sind die einzelnen Kanten, die in der Rundtour drin sein können oder nicht. Eine Rundtour ist eine bestimmte Menge von Kanten. Nicht jede Kante ist eine Rundtour, aber bestimmte Kantenmengen sind Rundtour an. Und die Kanten sind die Features.
01:24:43
Eine endliche Grundmenge, die Menge der Kanten im Fall TSP, von Features. Und die zulässigen Lösungen sind Teilmengen dieser Grundmenge. Selections, Auswahlen davon. Genau das ist es ja, wenn wir eine Rundtour konstruieren, wir wählen aus, welche Kanten dazu gehören und welche nicht.
01:25:03
Beispiele folgen gleich. Generell können wir Features identifizieren mit Dimensionen in einem Raum. Wenn Sie, wenn Sie, wenn Sie, wenn Ihre Lösungen 0,1 Vektoren sind der Länge n,
01:25:24
da haben Sie n Dimensionen, aber Sie haben auch n Features. Nämlich Sie wählen das Feature aus bei einer Lösung, die ein 0,1 Vektor der Länge n ist, eine zulässige Lösung, die so aussieht, können Sie sagen, die mit Wert 1 sind die Features, die ausgewählt wurden,
01:25:41
die mit Wert 0 sind die Features, die nicht ausgewählt wurden. Wir reden aber von Features und nicht von Dimensionen. So, Beispiele. Das erste Beispiel hatten wir schon, TSP. Ich hoffe mal, dass das Beispiel genau dem entspricht, was ich auch gesagt habe.
01:26:01
Genau, die Features sind, ich hatte von Kanten gesprochen, aber allgemein, die Features sind die Paare i, j, die aufeinander folgen können. So, was ist das Matching Problem? Wir wollen eine Teilmenge der Gesamtkantenmenge bestimmen, eben ein Matching. Und damit sind natürlich die Kanten das Eingabegrafen die Features.
01:26:25
Set Covering ist ein Beispiel, was wir jetzt noch nicht betrachtet haben bisher. Wir haben eine Grundmenge von irgendwelcher Art und wir haben Teilmengen auf dieser Grundmenge.
01:26:45
Also meine Intuition zu Set Covering ist immer, so meine Intuition zu Set Covering ist immer,
01:27:24
Sie haben diese Grundmenge, so irgendeine Menge, endlich. Und Sie haben Teilmengen, die vielleicht so aussehen, die sich überlappen können. Beliebig viele, beliebig wilde.
01:27:41
Natürlich im Allgemeinen wilder, als dass man sie so mit schönen Kringeln zeichnen könnte, aber das wird dann natürlich ein bisschen haarig. So, was Sie wollen ist eine Auswahl, also das ist natürlich alles überdeckt, eine Auswahl von solchen Mengen, möglichst wenige davon, sodass jedes Element der Grundmenge in mindestens einem Element dieser Auswahl ist.
01:28:06
Und Sie wollen die Anzahl der ausgewählten Mengen minimieren. Das kommt, diese Problemstellung kommt zum Beispiel in der Logistik oft vor. Die Grundmengen sind beispielsweise Versorgungsstation, Versorgungsmöglichkeiten
01:28:25
und alle Elemente, die von dieser, nein, die Grundmengen sind Kunden oder so etwas. Eine solche kleine Teilmenge ist eine Versorgungsmöglichkeit und diese Menge besteht aus den Kunden, die von da aus versorgt werden können und sie wollen mit möglichst wenigen Versorgungsmöglichkeiten alle Kunden erreichen können.
01:28:45
So nur als grobe Idee, warum diese Problemstellung in der Logistik eine große Rolle spielt. So, das kann man natürlich noch weiter spinnen. Ja, die einzelnen Versorgungsmöglichkeiten können unterschiedlich teuer sein. Dann möchte man nicht die Anzahl, sondern die Gesamtkosten natürlich.
01:29:02
Es ändert sich aber nichts an dem, worüber wir hier sprechen. So, die Elemente, also die verschiedenen Versorgungsmöglichkeiten, die verschiedenen Teilmengen wären dann die Features. MaxCut ist, ist das interessant für uns?
01:29:22
Ja, wir haben jetzt einen ungerichteten Graphen mit Kantengewichten. Ist ja nichts Neues, nicht? Das hatten wir öfter schon mal. Ungerichteten Graphen mit Kantengewichten. In diesem Beispiel da oben hat jede Kante Gewicht 1, aber allgemein muss es nicht Kantengewicht 1 haben. Hat Gewicht 1 natürlich, damit Sie das Gewicht eines Schnitts sofort durch zählen der Kanten heraus bekommen können.
01:29:46
So, alles, jede Teilmenge der Knotenmenge ist ein zulässiger Output. Und was wir wollen, ist die Summe der Kantengewichte, wir wollen eine Teilmenge finden,
01:30:04
sodass die Summe der Gewichte der Kanten, die von dieser Teilmenge rausgehen in die Komplementenmenge, dass wir die maximieren. Und das spielt in verschiedenen Kontexten eine Rolle, auch wieder eine Logistik.
01:30:23
Das ist da, wo es am teuersten ist, dass man da einen Schnitt macht und die beiden Teile jeweils für sich betrachtet. Spielt auch ähnlich, etwa in der Verdrahtung von Microchips eine Rolle. Da werden solche MaxCut Sachen eben auf solche dreidimensionalen Gittergrafen angewandt, sehr häufig angewandt.
01:30:40
Was sind hier die Features? Das sind die Knoten. Ja, eine Lösung besteht aus diesen Knoten. Wir haben immer noch Beispiele, aber wir haben jetzt auch langsam die Zeit. Wann haben wir angefangen? Bitte? 1959 haben wir theoretisch angefangen. Aber ich glaube, wir haben jetzt die 90 Minuten hinter uns, oder?
01:31:07
Okay. Sie sehen aber zunächst einmal, wir haben noch ein paar Beispiele. Nein, noch ein Beispiel haben wir, okay. Sie sehen daran, dass das jetzt keine dramatische Forderung an eine Problemstellung ist. Dass sie Feature basiert ist.
01:31:22
Das heißt, dass die zulässigen Lösungen Features aus einer grundlegenden endlichen Feature-Menge sind. Und das ist eine sehr natürliche, sehr häufig folgende Situation ist. Und wir werden beim nächsten Mal, nachdem wir dann das letzte Beispiel noch durchgegangen sind, Algorithmen sehen, die diese Feature-Struktur, also nachbarschaftsbasierte Algorithmen,
01:31:41
wo die Nachbarschaft auf diese Feature-Struktur basiert und wo diese Algorithmen dann diese spezifische Feature-Struktur stark ausnutzen. So, dann möchte ich für heute enden und wünsche Ihnen noch einen schönen Tag und noch eine schöne zweite Woche in der Hälfte.