Neighborhood-Based Approaches - Local Search with Side Constraints

Video thumbnail (Frame 0) Video thumbnail (Frame 13051) Video thumbnail (Frame 25921) Video thumbnail (Frame 38791) Video thumbnail (Frame 51661) Video thumbnail (Frame 64531) Video thumbnail (Frame 77401) Video thumbnail (Frame 90266) Video thumbnail (Frame 100189) Video thumbnail (Frame 108546) Video thumbnail (Frame 111924) Video thumbnail (Frame 121655) Video thumbnail (Frame 130556) Video thumbnail (Frame 133084)
Video in TIB AV-Portal: Neighborhood-Based Approaches - Local Search with Side Constraints

Formal Metadata

Title
Neighborhood-Based Approaches - Local Search with Side Constraints
Alternative Title
Feature-based local search / Kernighan-Lin/ Iterated Local Search / Population-Based Approaches
Title of Series
Part Number
6
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 license.
Identifiers
Publisher
Release Date
2012
Language
German

Content Metadata

Subject Area
Abstract
Auf Basis analytischer Sachverhalte entwickeln wir algorithmische Ideen für Verfahren auf Graphen. Daraus entstehen zunächst generische Verfahren, welche formal bezüglich ihrer Korrektheit und Laufzeit analysiert werden. Im Anschluss daran werden in jedem Kapitel Techniken zur Verbesserung und Beschleunigung vorgestellt. Abgerundet wird der Stoffplan durch zahlreiche Modellierungs- und Anwendungsbeispiele und der (optionalen) Implementierung eines Benchmarks verschiedener algorithmischer Varianten.
Loading...
Zahl Slide rule Trail Military base Model theory Moment (mathematics) Complex (psychology) Similarity (geometry) Lösung <Mathematik> Sign (mathematics) Solution set Strategy game Time evolution Antiderivative Mathematical optimization
Kante Point (geometry) Random number Zahl Distribution (mathematics) State of matter Model theory Graph (mathematics) Constraint (mathematics) Direction (geometry) Lösung <Mathematik> Zielfunktion Mass Average Mechanism design Strategy game String (computer science) Length Directed graph Evaporation Constraint (mathematics) Trail Point (geometry) Moment (mathematics) Desire path Translation (relic) Rounding Mechanism design Abzweigung <Strömungsmechanik> Function (mathematics) Travelling salesman problem Antiderivative Iteration Negative number Object (grammar) Linie Mathematical optimization Directed graph
Kante Polymorphism (materials science) Expression Neighbourhood (graph theory) Zahl Graph (mathematics) Weight Constraint (mathematics) Direction (geometry) Covering space Algebraic structure Mass Zielfunktion Atomic nucleus Subset Finite set Graph (mathematics) Divisor Vertex (graph theory) Summation Length Arc (geometry) Constraint (mathematics) Ant colony optimization algorithms Slide rule Point (geometry) Moment (mathematics) Complex (psychology) Desire path Feasibility study Set (mathematics) Translation (relic) Existence Element (mathematics) Rounding Simulated annealing Subset Mechanism design CW-Komplex Travelling salesman problem Function (mathematics) Cost curve Vertex (graph theory) Iteration Negative number Factorization Local ring
Kante Neighbourhood (graph theory) Constraint (mathematics) Weight Lösung <Mathematik> Zielfunktion Function (mathematics) Sparse matrix Mortality rate Mathematical structure Variable (mathematics) Substitute good Solution set Zusammenhang <Mathematik> Interface (chemistry) Heuristic Modulform Spacetime Divisor Length Local ring Arc (geometry) Logical constant Constraint (mathematics) Slide rule Surface Neighbourhood (graph theory) Moment (mathematics) Complex (psychology) Feasibility study Set (mathematics) Term (mathematics) Translation (relic) Rectangle Zielfunktion Simulated annealing Subset Position Travelling salesman problem Function (mathematics) Time evolution Cost curve Natural number Ecke Relation <Mathematik> Orientierbare Mannigfaltigkeit Mathematical optimization Factorization
Kante Algebraic structure Lösung <Mathematik> Subset Fraction (mathematics) Solution set Strategy game Network topology Partition of a set Spacetime Social class Raum <Mathematik> Decision theory Neighbourhood (graph theory) Wurzelbaum Feasibility study Partition (number theory) Subset Solution set Root Search algorithm Network topology Sheaf (mathematics) Helmholtz decomposition Mathematical optimization
Kante Constraint (mathematics) Direction (geometry) Lösung <Mathematik> Equation Weight Continuous function Variable (mathematics) Number Subset Plane (geometry) Solution set Network topology Partition of a set Decision tree learning Slide rule Decision tree learning Decision theory Wurzelbaum Dimensional analysis Feasibility study Set (mathematics) Continuous function Variable (mathematics) Subset Partition (number theory) Solution set Root Tower Network topology Helmholtz decomposition Set theory
Lösung <Mathematik> Decision tree learning Canonical ensemble Parameter (computer programming) Subset Plausibilität Network topology Partition of a set Uniqueness quantification Cloning Vertex (graph theory) Partition (number theory) Decision tree learning Decision theory Moment (mathematics) Feasibility study Exponential function Mereology Set (mathematics) Element (mathematics) Partition (number theory) Subset Calculation Solution set Root Network topology Mathematical optimization Thomas Bayes
Sierpinski triangle Root Wavefront Plane (geometry) Höhe Zusammenhang <Mathematik> Network topology Optimization problem Feasibility study Set (mathematics) Mathematical optimization
Adaptive optimization Root Plane (geometry) Network topology Number theory Feasibility study Mathematical optimization
so genau sind die anderen immer so seine Haftstrafe Lernmaterialien an der TU Darmstadt so guten Tag meine Damen und Herren
ich darf Sie herzlich begrüßen hier mal wieder des 1. 4 Aufnahmen sind schon gerendert da warte ich noch vom LC oft Informationen unter welcher URL die Filme dann zu finden sein werden also sind schon fahren Sie sind nur noch nicht verfügbar platziert und dann werden wir Schritt für Schritt die weiteren Filme auch einmal hatte die Kamera nicht geklappt bei der Gelegenheit habe ich einen weiteren Knopf einer Kamera entdeckt in den und den ich hätte verschieben müssen um damit es dabei umgekehrt ich habe aus Versehen verschoben das zu merken da werden wir dann halt gucken wie wir das Tafelbild was sich da an gezeichnet hatte wie wir das dann trotzdem nachträglich Verger Ähnliches wieder einbringen ist der Film so wir haben beim letzten Mal in genetischer Algorithmen betrachtet da vor Evolution das sind alles verschiedene Stufen der Evolution die man versucht zu simulieren er wird zum Stade gehen die der Versuch sexuelle der Vererbung Fortpflanzung und Verbreitung zu auf der zu simulieren Mutation und Selektion genetischer Algorithmen das war das Thema vom letzten Termin der Versuch das zu simulieren das eben nicht durch Mutation allein neue Gene entstehen also neue zulässige Lösungen die die wir als Kinder als Drinks repräsentiert haben sondern dass wir versuchen das anzukreuzen das das wir 2 Tiere es könne man auch mehr nehmen aber wir haben 2 hergenommen die Natur auch 2 Individuen hernimmt ihre Kinder nimmt und sie zu 2 neuen gehen macht die wieder 2 9 zulässigen Lösung entspricht in der Hoffnung dass auf diese Art und Weise ein größerer Bereich des Lösungsraum er durchsucht werden kann natürlich immer mit der Zielsetzung der ganzen Sache eine Tendenz zu geben hin zum Besseren das kennt das zieht sich ja wie ein Leitfaden durch alle diese Versuche von dem einfachen können so verfahren wegzukommen nein erlaubt es auch Verschlechterungen aber meinen baut eine Tendenz ein das ist doch im Laufe der Zeit immer mehr ins bessere hineingeht so den ist für der Evolution ist Kultur im weitesten Sinne sie denken vielleicht bei Kultur irgendwie an bildende Kunst Musik und so weiter aber eigentlich ist Kultur ein Begriff der also eigentlich eigentlich ist das das lateinische Wort für Ackerbau und ähnliches Kultur in und eigentlich und wo wir hinschauen sogar noch primitive Sache 1. Anfänge von etwas was man im weitesten Sinn als Kultur bezeichnen könnte in der Tierwelt also wäre wenn wir hier von Call schwört also in dem mein von Chor Kooperation wir hatten Wettbewerb in der genetischen NRW zum Strategien wir hatten Rekombination also das das sie in das sich der Vermischung wenn man so will ich weisen für das kann das ist deutsches Wort ein bei genetischen Algorithmen jetzt kommen wir zur Zusammenarbeit zu Kollaboration und dann nimmt man natürlich wie wie auch bisher aus der Biologie eine möglichst einfache Schema dass man gut über tragen kann unter Schema das wäre das hier vor allem betrachten wollen ist das wie Ameisen aber es zusammenarbeiten er Ameisen arbeiten offensichtlich sehr erfolgreich zusammen und Zusammenarbeit ist auch essenziell für den Erfolg für den evolutionären Erfolg von Ameisen Ameisen natürlich ein Beispiel Insektenwelt finden sie genug andere Beispiele auch den Westen und so weiter und so fort bei höheren Lebewesen selbstverständlich auch aber Ameisen sind schönes Beispiel für eine für eine Zusammenarbeit die auf sehr einfachen Prinzipien auf sehr einfachen primitiven basiert und das ist natürlich wunderbar prädestiniert zu Übertragung in die Informatik so in der so Strategien wie gesagt es gibt es nicht wirklich soziale Aktivitäten wie man sie noch mal sehen würde sondern es gibt Wettbewerb im Wettbewerb um Ressourcen nicht gegen den Namen kenntlich gegen Anderson Mann sondern man Wettstreite Welt der fitteste ist genetische Algorithmen ja sozialer von sozialer Aktivität kann man da immer noch nicht reden was heißt jetzt kultureller Algorithmen das heißt dass die dass die einst für die vielen Lösungen in gewisser Weise auf die anderen Lösungen reagieren positiv oder negativ und im Englischen gibt es den den Sproch Go Go wird aber dass gehe schließlich immer den den Gewinnern an das ist offenkundig in der Tierwelt und auch in der Menschenwelt 1 sehr gute Strategie für den Einzelnen ja man kann natürlich darüber streiten ob das jetzt eine sehr ob das jetzt die Gesellschaft als Ganzes wenn jeder versucht sich immer an die Gewinner anzuschließen aber vielen einzumischen ist eine sehr gute Struktur die zu sein so dass wir alle diese Strategie als einen sehr Bases sozialen Strategien in unserem Reptilien und vorliegenden haben das ist sie gemeint und genau das passiert auch schon mit den Ameisen wenn eine Ameise erkennt dass eine andere Ameisen mit der sie für Kontakt hat dass die auf auch über offene gewisse Quelle gestoßen ist und versucht sie diese Ameise zu folgen oder den Weg zu beschreiten die also vorher gegangen ist so wie funktioniert das die Zahl der Beobachtung dabei ist die kann man in jedem Vorgarten machen wenn man meisten befahl hat manche Leute können diese Beobachtung auch in der eigenen Küche machen wenn Sie da Ameisen befahl haben ja es fängt damit an dass irgendwelche Kundschafter völlig ziellos völlig ohne Plan und auch nicht auf geradem Wege sondern irgendwie Zickzack durch die Gegend laufen und es endet mit einer und wenn da irgendwo interessante Beute ist was immer das sein mag ende des damit das relativ schnell sehr schnell eine Ameisenstraßen Standes eine Straße und wenn man sich das mal anguckt in diesen Tag war ist das typischerweise tatsächlich der kürzeste der beste Weg in diesem Tag heißt natürlich er gibt das beschwerliche Teile das muss man sozusagen als Weglänge miteinbeziehen es ist nicht der geometrisch kürzeste Weg unbedingt sondern es ist der gemäß Kriterium und Beschwerlichkeit der kürzeste Weg der typischerweise dabei herauskommt ja eine eine grandiose Leistung für die wir hier der GTI 2 eine ganze mehr vor ganze für mindestens eine Vorlesungsstunde wenn nicht sogar noch mehr opfern müssen um das in dem Algorithmus nachzubilden was die Ameisen da völlig ohne und wenn ich ganz viel los aber nicht nicht mit dem mit mit 0 Verständnis für Algorithmen da einfach so durch Kollaboration hinbekommen so was das wie läuft das wie wie ist der Steuerungsmechanismus muss Steuerungsmechanismus geben oder muss dezentral sein solange wir nicht glauben dass es da eine übergeordnete Ameisen Gottheit gibt die das alles von oben steuert so lange es des Hypothese wohl gerechtfertigt dass das das völlig dezentral in den einzelnen Ameisen und in ihrer Zusammenarbeit in ihren lokalen Zusammenarbeit alles drinsteht dieser Steuerungsmechanismus und wie läuft das wann immer eine Ameise Leute irgendwo entlang läuft liegt in der Spur eine Spur von Duft Substanz von von Pheromonen und Ameisen habe ich ihm gesagt laufe die Kundschafter laufen völlig ziellos herum aber in dem Moment wenn
eine Ameise spuren aufnimmt versucht sie dem intensivsten Spur die sie aufgenommen hat zu folgen versucht sie in die Richtung zu gehen wo die Spur am intensivsten ist das funktioniere auch ich hundertprozentig ja Ameisen können kann natürlich auch nicht so richtig Spurhalten dass auch ein Element des Zufalls noch weiterhin drin dass sie die Spur wieder verliert oder oder nicht die die intensivste sondern nur die zweite intensivste Spur verfolgt und so weiter so des die kürzer und die haben wir in einem dieser Prozess so ähnlich wie bei Simmel in Dillingen zum Beispiel oder auch die im Biber der Evolution Strategien und ich also das Zufall ist wichtig erfahren wir dass man wenn man nicht versucht Intelligenz so sein sondern wenn man Entscheidung dem Zufall überlässt das da dass das zu besseren Ergebnissen führt so hier ist die Tendenz trennen von der ich gesprochen habe zum Besseren hin je kürzer und ich habe und beschwerlicher also habe ich ihn genannt und Einfahrt ist umso größer ist die Wahrscheinlichkeit dass da eine Spur ist aber auch Ameisen sind nur Menschen Obst Vorsicht natürlich hier was eben sagte auch dass es zu weiß behaftet aber Zufalls Verhaftung ist wie gesagt wichtig denn das ist die Strategie vielleicht werden um Auswirkungen optimal um ob der um das hineinstürzen und ich wieder herauskomme so kann optimal zu vermarkten so wie sieht das aus ich will dazu meine bescheidenen künstlerischen Fertigkeiten strapazieren wir haben hier irgendwo wo wir Betracht jetzt eine natürlich eine völlig idealisierte Situation die so niemals auftreten oder mir und wo das Netz Nest das Ameisen ist und da laufen irgendwelche Ameisen irgendwie lernt hier läuft eine Ameise lang also für mich sind Ameisen Sohn Pi mit 3 statt 2 Beine dieser vielleicht auch ein bisschen anders lagen kann bisschen so hin und her noch und hier gibt wird eine eine Futterquelle Erde die kann sich natürlich auch hier beliebig noch selber kreuzen und diesen Futterquelle und die andere ich übertreibe das natürlich jetzt die andere läuft zufällig auf einem wenn auf einem sehr viel weniger beschwerlichen Weg wo sie gerade zu dazu getrieben wird vielleicht vielleicht ich damit so ein kleines Tal aus Sicht der Ameise wo es beschwerlich ist nach rechts oder links den Hang hoch zu gehen also bleibt sie tendenziell immer einen Tal und wird durch das darauf viel direkter hierhin geführt zu dieser Futterquelle so wenn wer es jetzt 1. wenn beide gleichzeitig los gehen natürlich die Ameise die oben angeht die in dem Moment wenn sie hier ist das 1. Futter schnappt und wieder zum Bau zurück kehren will gibt es in dieser idealisierten in diesen idealisierten Szenario nur eine Spur oder der sie folgen kann nämlich ihre eigene sie wird also nach sie hergekommen ist über ihre eigene Spur zurück gehen jetzt kommt die andere also ein bisschen später steht auch fest dass sie das dann änderte Futterquelle ist und wird versuchen wieder wird wird hat zum Ziel wieder als mit mit dem Stück von dieser Futterquelle zurück zum Bau zu er mehr als dieses einfache Programm Gerlos Schwärmer aus Versuche Pheromonen zu folgen versuche versuche bequeme Wege zu gehen und wenn Futter gefunden hast versuche weiter den Pheromon zu folgen und falls falls du am Nest ankommst falls das der Fall ist dann dann für 3 in die nach oder was immer dann die Aufgabe so über gibt es dann an die dortigen Arbeiter oder was auch immer so wenn die zweite ankommt dann ist diese Spur hier wahrscheinlich noch da hin und zurück das ist mit großer Wahrscheinlichkeit für diese zweite Ameise da nicht ihre eigenen Spur zurück folgen sondern sondern dieser Spur ebenfalls und das ist die Tendenz übertrieben gezeichnet es natürlich das ist die Tendenz die der Sache innewohnt die tatsächlich nach allem was man weiß diese einfacher Mechanismus sorgt dafür dass Ameisenstraßen gibt und dass diese Ameisenstraßen ich in die beliebig Kreuz und Quer sie laufen sondern wirklich richtig gute kürzeste Weg ist und und wenn diese Tendenz in der Natur wo also noch viel mehr zu was behaftetes und völlig unkontrolliert ist wenn diese Tendenzen Natur so so guten Erfolgen führt ist die Idee natürlich naheliegend ob man nicht diese Grundprinzipien übertragen kann man ein Computerprogramm um sich um auf diese Art und Weise zu für bestimmte Problemstellungen die so ähnlich sind wie das Ameisen Problem vielleicht ebenfalls zu guten Lösungen zu kommen so was der Kontrollmechanismus geht über positives und negativ also Stimulierung und und und Reduktion der Stimulierung also die Stimulierung ist wie ich sagte jede also versucht den Pheromonen in 1. Linie zu folgen wenn keine da sind er habe beim Kundschafter wenn man das kann ganze Tag Pheromon frei ist was die 1. Ameise ist dann läuft die aber seine Zigzag versucht nur bequem zu gehen so aber dieser Stimulation des die verringert sich natürlich 1. Mal Duftstoffe haben so an sich dass sie leicht flüchtig sind das ist essenziell ein Duftstoff der nicht leicht flüchtig es kann ist in sich unlogisch er wenn eine andere Ameise diesen Weg aber da immer noch rechtzeitig folgt dann gibt es natürlich ein Refresh weil diese Ameise natürlich ebenfalls Duftstoffe hinterlässt und so dass ich hier so so eine ergo zu 1 so eine praktisch praktisch seine abspielbar seit dem deutschen Abstimmung mit den Füßen ergibt das passt vielleicht ganz gut als Formulierung hier die Tendenz ist so da wo viele Ameise gegangen sind sind gehen auch mehr Ameisen hin und da wo es bequem ist da gehen auch mehr Ameisen hin und das beides sorge dafür in der Tendenz und offensichtlich sehr sehr gut in der Natur das immer mehr Ameisen sich diesen diesem einen hat diesen einen Weg anschließen also diesen Weg jetzt vielleicht vorher noch gar nicht schlecht es keine einzige Kundschaft Ameise genau diesen kürzesten Weg gegangen aber so nach und nach und zwar eine recht schnell konvergiert das Verhalten der ganzen Ameisen zu einem einem Strom auf einer einzigen Straße sie sehen aber auch manchmal das ist ja durchaus Abzweigung von Ameisenstraßen gibt wenn sie dann strahlenderen haben oder wenn sie wegen absichtlichen Steinreihen das dann einzelne Ameisen den sind aber Ameisen also rechts entlang gehen dass sich also des Ameisenstraße zerteilt und wieder wieder zusammenfügt da sind Sie natürlich das Zufallselement ganz der weltweiten so wie comma da jetzt dem Algorithmus wir haben wenn wir diese Analogie mit den kürzesten Wegen erheben
dann kann man natürlich nicht jedes beliebige algorithmische Probleme auf die Art und Weise zu lösen wir brauchen etwas wo wo wir im weitesten Sinne irgendwas mit Fragen zu tun haben also was ich zunächst mal brauchen ist ein gerichteter Graph das kann ganz abstrakt sein wir werden das gleich sehen die Lösungen sollen fahre in diesen Grafen sein und die Nebenbedingungen wer dieses Problem hat dass die Lösungen erfüllen müssen Sie den sprechen Lösungen die er so ne mit denen die die Zahl der Fälle müssen wie wärs gleich im Beispiel sehen was das heißt und natürlich ist es wichtig die Ziele und somit also bringt die wir optimieren wollen im das und wie gehen wir ein das wird nicht immer so hundertprozentig glaubten dass wir sagen können die Zielfunktion die wir optimieren wollen wenn wir zulässige Lösungen Pfade übersetzt haben ja bei letzte Woche habe zulässige Lösung in Strings übersetzt sie beim Festmahl verwählt hier übersetzen wir jetzt soll das Siegel Lösungen in wir müssen uns Gedanken machen was das für die Zielfunktion heißt es wird nicht immer so ohne weiteres glauben ist die das die in die Kosten der einer zulässigen Lösung gerade die die Länge dieses Pfades ist aber zumindest hier liest er packte mit zumindest ungefähr näherungsweise müssen wir versuchen das hinzukriegen und dann lassen wir die Ameisen einfach laufen die Ameisen laufen herum Silos zufällig ja wir wissen was das heißt können Sie von ziemlich legen und so weiter zufällig in irgendeine Richtung sind immer zu Zeitung die jeder und auf einen Knoten jeder einzelne Ameise und läuft in jedem Schritt von einem Knoten zum nächsten Kunden über eine zufällig gewählte kannte aber zufällig heißt nicht immer gleich verteilt zufällig heißt kann durch das heißen eine kann hat höhere Wahrscheinlichkeit dass er gefolgt wird als andere könnten nämlich abhängig von dem Pheromonen Maß was auf dieser Kante liegt ja auf der Kante auf einen essen könnten legen ihre kann hat einen wird der aktuelle Stand wie viel Pheromon auf dieser Kante drauf sind und die Hoffnung willst die Zielsetzung ist dass genau das passiert was auch in der Natur passiert dass die Ameisen ohne sie über und über von anderen etwas zu wissen sich reorganisieren konvergieren zu einem kurz kurzen der vielleicht nicht kürzesten Fahrt das wirklich immer klappen aber zum einen kurzen Fahrt zum Beispiel die SPD die habe ich ja schon mehrfach gesagt das ist hier keine Vorlesung über das Handeln zu Handlungsreisen Problem das ja vor Optimierungsalgorithmen aber trotzdem dass die SPD ist immer wieder ein gutes Beispiel um alle diese Dinge zu illustrieren so wir haben jetzt also eine Instanz das die SPD auf Endpunkten also n Objekte und der Distanz Matrix die und sagt von einem Objekt zum nächsten Objekt wie viel länger ist das so irgendwie lassen wir die Ameisen jetzt auf diesen Punkten auf diesen Objekten fallen auf diesen Knoten der mehr im Grunde heißer TSB wir haben einen vollständigen Grafen auf den N Punkten da typischerweise erlauben von einem Punkt um andern direkt zu gehen muss nicht sein man kann's auch einschränken auf will gewissen trafen wir uns bisher immer so betrachtet das ist er das ist diese Punkte sind das ist das ist ein vollständiger Graf ist er falsche gerichteter Graph weil die Richtung der von von A nach B kann unter Umständen länger haben Hamas von B nach A ja denken Sie sie sind zu Fuß unterwegs als die Talstation des ist die Bergstation dann ist die Dauer von A nach B hoch sicherlich ein anderer als von den noch unter so wie das selbe wir können es am besten aber diese Informatik in denen wir eine weil Schleife haben eine Schleife haben wo in jeder Runde in jeder Iteration die einzelnen Ameisen irgendwas tun wir unterteilen das hier zweckmäßigerweise wir haben Änderung im Grunde sind es 2 ineinander geschachtelte Meckerer uns bezieht sich das in die Iteration der äußeren Schleife und meine Ara und das sind die Iteration der inneren Schleife und was passiert in der inneren Schleife wir haben es immer die Situation die Ameisen sind irgendwie verteilt wieder einmal soll der muss vor entschieden wie viel Ameisen wir reinwerfen diese Anzahl bleibt auch gleich also wir lassen keine Ameisen sterben das noch keine Ameise geboren werden und dem Zustand haben wir jede Ameise auf irgendeinem dieser Knoten und auf den Kanten haben wir Pheromon Werte die das widerspiegeln wo die Ameisen angelaufen sind so was passiert in einer meine und in einer solch er in einer Iteration der inneren Schleife läuft jeder Ameise zu einem Punkt hin an dem sie in dieser Iterationen der äußeren Streifen noch nicht gewesen ist das heißt also in jeder Iteration der äußeren Schleife besucht die Ameise alle Punkte 1 und landet dann auf den letzten Punkt den Sie dann besucht und das ist eine mittlerer und eine Iteration aus umschlagen beendet wenn Inderin jede also einmal in period besucht hat und dann kann die nächste Iteration Staaten wo wir das genau dasselbe passiert jede Ameise macht eine Rundtour und wir merken uns wann immer es zu jedem Zeitpunkt natürlich wie wie wir das bei anderen Ansätzen gesehen haben auch das ist die beste Lösung die wir jemals gesehen haben wir nämlich die letzte Lösung die wir gesehen haben sollen in dem die das die beste Lösung die wir jemals gesehen habe die speichern wir mit natürlich jedes Mal wenn wir eine neue bessere Lösung sehen wird in gibt es sprechen Update oder eines Algorithmus für die beste Lösung die wir jemals gesehen haben ausgegeben so und jetzt kommt der Steuerungsmechanismus eine Kante wenn wenn eine eine Ameise von von über Kante geht dann lässt sie Pheromon dar diese Pheromone dieser Pheromonen wert sind schritt für Schritt in jeder Iteration der der inneren Schleife singt der Pheromone wert nach irgendeinem Schema in jeder Iteration der der inneren Schleife gucken wenn sie da Ameise an die Kanten die rausgehen Wirkung ist natürlich nur die Karten Raudi die raus die zu einem Knoten führen dennoch nicht besucht worden ist denn das Gerät zum ruhig der inneren Schleife jeden Club nur einmal zu besuchen das heißt also wir haben eine gewisse Auswahl der könnten und aus diesem kannten wird zufällig eine gewählt und darüber über diese kann der geht dann die Ameise weiter wie werden diese Wahrscheinlichkeiten definiert sie wird einerseits definiert über die Distanz ja also jede größere Distanzen sie größer die Länge dieser kann ist umso weniger wahrscheinlich ist es dass die also diese kannte nimmt und aber auf der anderen Seite als Korrekturfaktor je mehr für Hormone auf dieser Kante ist und so wahrscheinlich ist es dann doch wieder dass diese Kante gewählt wird das kann man sich ganz das kann man ganz einfach Berechnungsschema daraus machen beispielsweise das dieser dass sie sagen ja ja
die Wahrscheinlichkeit dass eine Karte genommen wird ist die Länge dieser kannte hierorts also die also steht auf der auf dem Objekt I und diese kann davon in ist eine Möglichkeit diese von für die Ameise den nächsten Schritt zu tun vor zu tun und das ist vielleicht also I J die Wahrscheinlichkeit wird ja kleiner je größer die Länge ist plus die vor Hormonmenge eskaliert mit einem konstanten Faktor ich zu kurz es mal so für und Männer die gerade auf ihrer drauf ist und wenn wir Wahrscheinlichkeiten haben wollen müssen wir das immer summieren über das ich mal J 0 das ist das spezifische Möglichkeit von dem aktuellen Knoten Ilos weiter zu gehen dann muss man das Skalieren in dem wir die Summe über alle bilden von diesen Werten und dieser J das und alle Möglichkeiten alle Knoten die noch nicht gesehen worden sind also J alle noch nicht vor dem dieser einen Ameise gesehenen Knoten in dieser Manager und er wenn man wenn man Wahrscheinlichkeiten angeben will muss man immer durch die die dir den relativen wärs dem man einer Kante geben will dividiert durch die Summe aller dieser relativen Werte wie alle anderen Optionen dann hat man immer werde zwischen 1 und 1 das ist der einzige Grund warum man da immer sondern nach Art das ist einfacher Schema man kann sie auch andere schimmerte ausdenken wie man die Wahrscheinlichkeit berechnet dass eine Kante genommen werden soll und mit diesen Wahrscheinlichkeiten geht man was genau da so unendlich Zufallsgenerator Herr der vielleicht eine jetzt eine Zahl zwischen 0 und 1 berechnet manche tun das andere berechnen beliebiges ins oder was auch immer wir mal an ein Double zwischen 1 und 1 ist dann ist dann würde ein bestimmter Abschnitt im Bereich 0 bis 1 ein bestimmter Abschnitt hier würde der ein kannte entsprechen einander Abschnitt der 2. kannte ein Abschnitt der 3. kannte und so weiter und die Länge dieser 1 und davor landet diese Karte wird genommen da wo der Zufallsgenerator die des Ergebnisses Zufallsgenerators ist und die Länge dieser einzelnen Abschnitte des 0 1 sind genau diese wertet diese Wahrscheinlichkeiten so das einfache Schema wie man solche 7 einen Zufallsgenerator benutzen kann um eine Auswahl aus verschiedenen Optionen mit unterschiedlichen Wahrscheinlichkeiten zu treffen ZK bringt ist vielleicht interessanteres Problem dabei weil wir hier eigentlich gar nix mit kürzesten Wegen zu tun haben überhaupt nix mit wegen eigentlich nicht mal was mit Grafen also ein illustratives Beispiel dafür in das waren ja durchaus solche Algorithmen auch anwenden kann in Situationen wo man es eigentlich gar nicht vermutet hätte Drogen und und was wird Carolin sie haben eine große Menge das ist es das ist eine Menge im Allgemeinen gehen wir von endlichen Mengen aus könnte der würde sogar ohne Licht sein aber das interessiert uns nicht ich glaube das ist er jetzt nie etwas nee das ist falsch das ist das 1. ganz unten das ist die Menge was ist es das sind Teilmengen ja irgendwelche Teilmengen die sich auch beliebig überlappen dürfen dürfen sogar identisch seien aus Versehen mal was natürlich nicht viel bringt aber es ist nicht ausgeschlossen so und Problem heißt also zunächst einmal das sind die Elemente von erst diese Teilmengen es wird keine heißt eine eine Teilmenge aus diesem es zu finden also eine Menge von solchen Kringeln hierzu finden H auszuwählen eine möglichst kleine Menge von solchen Mengen mit der Eigenschaft dass jedes Element von 11 in mindestens einer dieser Auswahl an das ja so so dass Sie haben eine Auswahl dieser Teilmengen die die gesamte Grundlinie F überdeckt das führt Körbe Ring so was machen wir jetzt das sagt die diese Folie wir bauen uns den künstlichen Grafen nämlich dass ein Knoten sind gerade diese diese Teilmengen und der Graf es vollständig das heißt also wir haben jede kann jeder gerichtete kannte von einem Element von so jemanden den man von S so das bedeutet Teilmengen 3 Teilmengen können wir als Pfade ansehen haben Sie sich umgethan erleben dieses Element dieses hier dieses hier dann können Sie das verstehen als in ihren der Reihenfolge allzu Einfahrt ihren abstrakten Graf nicht was da da ist noch was sehen können ich versuchs nochmal ein bisschen die Pfeile deutlicher zu machen so ich habe leider hier keine haben uns zur Verfügung alles wahr ist gut also hier dieser Frage und die Sorge vor während eine Repräsentation dieser Tag in dieser Teilmenge von ist dieser 3 Teilmenge von S durch einen Pfad natürlich nicht die einzige mögliche sie könne noch natürlich auch andere vor der Zeichen in die diese 3 Elemente Gemenge genauso repräsentieren aber es letztendlich wurscht so jetzt sind wir schon mal nah dran so jetzt wollen wir natürlich erhabenen rechtlich eine Zielsetzung wir wollen also was wir wissen dass wir wollen Fahrt konstruieren einen kürzesten Fahrt sogar wollen wir konstruieren in Bezug auf die Kanten länger je weniger kannten wir drin haben von einer Dame von einem Ende mit unserer Lösung zum nächsten und so gering dass die Anzahl der da eine Menge die wir ausgewählt haben ist vielleicht jetzt ein bisschen abstrakt momentan aber ich glaube falls Sie dass jetzt nicht hundertprozentig erfassen dass Sie das dann hinterher wenn sie nochmal die Vorlesung nachverfolgen vielleicht auch die Aufnahme nachverfolgen und notfalls ohne Frage im Forum stellen dann doch das ist doch einsichtig wird so jetzt wollen wir also Pfade finden
die Steuern wir jetzt den Algorithmus der diese 10 Ameisenalgorithmus der diese Frage für wir müssen erst mal ausdrücken was das bedeutet ein guten Fado was es bedeutet über Kante zu geben wie gut oder wie schlecht das ist ja die die Ameise weiß auch nichts von keine Fragen die weißen etwas von einzelnen kann sie steht an einem Knoten und guckt sich in Anführungszeichen die einzelnen kann man die von diesem Knoten ausgehen das heißt also die Frage ist wie soll das Gewicht einer Kante seien die ausdrückt das ist eine gute kannte das ist eine weniger gute kannte und was man zum Beispiel hernehmen kann ist als ein anderes Beispiel die keine Naivität das was man hinzugewinnt an über Deckungsleistung wenn man von dieser von diesen zu diesem geht jetzt habe ich die Zeichnung ist vielleicht in etwas ungeschickt für das was ich hier an diesem dash sagen würde sie dann wieder die Menge f und Sie haben jetzt ihre Menge S 1 und dem allgemeinen werden Sie sich wahrscheinlich überlappen so die Ameise steht auf S 1 und sammelt ihr der Weg den sie durchläuft so ähnlich wie man die SPD in der Beginn sie durchläuft ergibt dann die Lösung die diese also vorschlägt so welchen Sinn soll es haben für also von S 1 S 2 zu gehen wäre der Sinn liegt in in dieser größer das sind zusätzlich überdeckt Elemente und das ergibt und sofort ist auch das ist statt Kriterium beim TSB Wanderstab Kriterium einfach wir wissen jeder Rundtour hat kannten und Knoten also nach Schritten Staub das was wir da das was sie einmal so beschrieben hat ist sein die SPD hier sehr stark Kriterium für die meine war und dass die Ameise eine Lösung durchläuft und und dann wieder beginnen nur eine Lösung zu durchlaufen hier stoppt Kriterium das alle Mengen die diese Ameise so durchlaufen hat beginnend irgendwo wo sie zufällig gerade steht nach diesem Schema weiterlaufen zu und Mengen durchlaufend dass diese Mengen aller zusammengenommen F überdenken das ist die Ziele setzt das das wäre der Punkt an dem wir sagen können okay die am Ansatz ähnlich wie beim TSB eben hat eine zulässige Lösung durchlaufen vielleicht nochmal ganz kurz wir hatten etwas vorher gesagt hier die Zielfunktion die Kostenfunktion kann wenigstens näherungsweise ausgedrückt werden wenigstens so ungefähr so heuristisch ausgedrückt werden als die Länge des Vaters und das ist ein Beispiel dafür was das zum Beispiel bedeuten kann dass man sagt ok das was die das was in jedem Schritt hinzugenommen würde an er einen bislang noch nicht überdeckten der lärmenden von F das ist natürlich letztendlich nicht wirklich das richtige Maß aber es ist schon ungefähr die richtige Richtung es sorgt dafür dass die Ameisen Tendenzen in die richtige Richtung gehen so diesen Fall komplexer Künstlerin ist eine wissen mit Ameisen jetzt fertig übrigens ich wollte es gerade habe gerade überlegt was diese frühesten den damals noch zu tun hat und dann ist mir eingefallen Moment hatte gar nix mehr zu tun an dieser Stelle wenn wir auch die kulturellen Algorithmen nicht mehr die vertiefen auch hier gilt wieder man könnte ganze vorlesungsfreie nur zu kulturellen Algorithmen und zu deren Einsatz in der Praxis hier ausrichten aber das ist nicht das Ziel dieser Veranstaltung die hier sie haben ordentlich wenn sie dieser falschen aufmerksamen gefolgt sind und sich auch entsprechend effektiv auf die Prüfung vorbereiten werden dann haben Sie sicherlich in der alles Rüstzeug erworben um selbst vertieft ja das weiter zu recherchieren wenn irgendeine dieses eines dieser Themen für Sie mal irgendwann in ändert im Studio noch oder später in der betrieblichen Praxis für sie wichtig ist so also das indes noch mal so ein bisschen bekomme jetzt wäre wer er betrachtet keine weiteren spezifisch der spezielle Modifikation des lokalen Suche Schemas mehr Sonne bekommen dann zum zum Ende dieses großen Abschnitt ist um Mitternacht noch mal ein allgemeines Thema dabei nicht so Kern Bestandteil aller dieser Algorithmus natürlich irgendwas was mit Nachbarschaftsstruktur mit Grafik Struktur in irgend einer Weise zu tun hat bei lokaler Suche hatten wir schon wir wollen vielleicht am besten immer idealerweise sogar nicht nur irgendeine verbessernde Lösung haben sondern die F und unter allen Nachbarn der aktuelle Lösung eine Lösung haben wo es eine maximale Verbesserung gibt oder zumindest eine Verbesserung gibt das bedeutet wir müssen durch die Nachbarn irgendwie in einem sehr effizienten Schema rumlaufen bis wir wenn wir damit zufrieden sind entweder die 1. Lösung gefunden haben in der Nachbarschaft der Verbesserung der geben würde ein Verbesserungen Schritt vorwärts oder wenn der ambitionierte sind das für die gesamte Nachbarschaft durchlaufen und und das gemerkt haben was ist der beste Verbesserung Schritt welche Nachbarin bietet einen besten Verbesserungen Schritt und den nehmen wir dann ja das brauchen wir für lokale Suche als fundamentale Eigenschaft der Nachbarschaft Struktur dass das Gut in der Nachbarschaft als Knotens gut in Nummer Weber ist das Bauen über simulierte denn wenn überhaupt nicht ändern sie in sich tragen wenn in einer Runde in einer Iteration stehen wir wie üblich auf einen Knoten in unserer naher Nachbarschaft Struktur und würfeln zufällig eine andere kannte aus und mit gewisser Wahrscheinlichkeit gehen wir diese kannte und mit der kommen mit der Wahrscheinlichkeit bleiben wir wo wir sind und wir sind wieder das heißt also hier brauchen wir ihr eine Nachbarschaft in der wir in der wir auf leichte Art und Weise zufällig eine kannte einen Nachbarn werden das funktioniert aber oft nicht das so richtig gut wegen wegen Nebenbedingungen komplexer nehmen mit dem hier natürlich wie immer das Beispiel TSP also ich habe meine vor vielen Jahren mit mit mit jemandem gesprochen der sich der sich sehr gut beim TSB auskennt und wir waren uns einig sie haben schon viele Anwendung von TSB in der Praxis gesehen aber noch nie in Reinform noch nie in Reinkultur immer mit welchen zusätzlichen Bedingungen oder sonstige Verkomplizierung ein so was haben wir hier die Situation wenn wir uns noch mal das ursprüngliche DSP ansehen da haben wir eine Nachbarschaft definiert 2 Opfer das wir den 2 raus und tun 2 andere kann wieder ein so dass das Ganze wieder eine Rundtour ergibt Wir zerlegen die Rundtour in 2 Teile diverser kann rausnehmen und dann werden wir die Zwecke Teile wieder zusammen und andere runter zu erzeugen muss man wissen technisch tricksen muss man noch die Kanten auf der eine der beiden Rundtouren alle umdrehen aber das ist der kleine so in der
realen Welt wenn wir Damen TSP zu tun haben dann gibt es irgendwelche Nebenbedingungen zum Beispiel diesen Bedingungen dass gesagt wird bestimmte Punkte müssen angelaufen werden bevor bestimmte andere Punkte angelaufen werden er das ist eine typische dass das ist eine typische nehmigungen Reihenfolge Beziehung Präsenz Kunstvereins na andere hier nicht aufgeführte typische dem Meeting ist etwa das bestimmte Knoten nur in bestimmten Fenstern angelaufen werden dürfen das also gesagt wir dieser Knoten Mons irgendwo zwischen Position Tausenden Position 2000 seien in der ganzen Reihenfolge in der die Knoten angelaufen werden oder solche Dinge das Problem ist jetzt dass diese schöne Nachbarschaft nicht mehr funktioniert denn sie haben eine Rundtour also zeigen wir die Nachbarschaft von dich die ganze Drill vielleicht doch noch mal auf auch wenn wir das schon oft genug gemacht haben werden wie war das noch mal Sie haben hier eine Rundtour sollte man relativ kleine Rundtour zu Genussprinzip an so und sie jetzt 2 Kanten aus welchen nämlich da vielleicht diese Karte hier und diese könnte hier und die wahrscheinlich und bastle mir daraus eine neue Rundtour also was bleibt die hier bleiben alle die nicht die bleibt ja ja so ungefähr und die bleibt ich lasse noch absichtlich die Orientierungen weg so was sich jetzt noch brauche ist wieder 2 neue kannten die das Ganze zu Natur verbinden die hier und die hier Zumba müssten das dann sein dann am eine neue Tour und sie sehen schon wir können unmöglich die rein die Orientierung in der einzelnen kannten hier aufrecht erhalten da kriegen Sie keine konsistente Orientierungen sondern in einem der beiden übrig gebliebenen Teile der ursprünglichen und Tour müssen Sie alle Orientierung ändern und umdrehen zum Beispiel darum drehen wir hier um hier unten behalten Sie bei wie sie vorher war und dann gehen wir diesen beiden kann noch diese Orientierung Gewalt und dann passt das das ist und war funktioniert wunderbar problemlos weil im wer einen Plus ist hier jetzt löst Form in der reinen Formen vom TSB funktioniert aber überhaupt nicht mehr wenn Sie wenn Sie solche Reihenfolgen Beziehung drin haben ja weil weil sie haben nicht unter Kontrolle es kann ja sein wenn woran kann oder mal ein Beispiel ja immer ganz einfaches Beispiel hier ist die hier ist der Staat mehr ist zu einfach was ich mir denke also wo ändern sich dann mal die reine folgen wir haben aber hier ist der Staat ich glaube das schon gut und hier muss E I I und hier ist Fjord und sie haben sie haben die bilden das Ifo J kommen musste nach dem Staat das 1. was man sieht es 2. J dann haben wir hier die Situation dass es wieder Start hier SID hier ist J und Sie sehen das stündlich mehr weil wir diese bis kannten ausgetauscht haben ohne zu wissen was wir da tun und wenn wir jetzt nicht nun paar also wenn wir die Situation haben ja Millionen von Knoten und vielleicht sehen solche Paare dann ist die Wahrscheinlichkeit groß dass es da jetzt nicht so viel passieren wird aber wenn das Verhältnissen anders ist es wenn sie im Verhältnis zur Gesamtzahl der Knoten doch eine ganze Menge von solchen Paaren habe mit Reihenfolge Beziehungen Wahrscheinlichkeit wirklich groß dass er war immer weiterkommen ja egal wenn Sie versuchen irgendwo klingeln Problem ein und ein paar steht in der Regel ja also die die Nachbarschaft ist hochgradig zerstört dadurch die ganzen kannten die ganzen schönen kannten von einer zu müssen wir sind zunächst so dass Lösung sind alle weg weil zu nicht mehr zulässigen Lösungen führen so das ist dass er den er wird das also sagte denn wahrscheinlich mehr bekam weil ich Spaß sogar unzusammenhängend kann sein dass man nicht mehr von über alle über den kommt das heißt wir bleiben einfach viel zu früh stehen viel zu früh einfach nicht mehr weiter und wir verbringen die ganze Zeit damit eine Nachbarn nach dem nächsten auszuprobieren in der Hoffnung dass einer von den doch zulässig ist und eine ganze Menge zu unzulässiger Lösung sehen wir dabei völlig völlig ohne Sinn und Zweck ohne dass uns und was bringt so was kann man da tun die typische Form der so ähnlich schon mal in etwas anderen Zusammenhang gesehen hier bei bei kleidet wirken Search das wir ich glaube da war das weiß es nicht genau dass wir diese diese mehr Nebenbedingungen die uns dieses Problem unser schöner Putt und so schöne Situation völlig kaputtmachen dass wir diese nervigen den Bedingungen gerade das wir die fallen lassen dass wir die nicht mehr man 7 Dämonen aber natürlich nicht ersatzlos sondern dass wir sagen wir erlauben zwar unzulässige lösen wir erlauben zwar Lösungen wie die hier wo ihn nicht mehr vor J kommt was eigentlich was eigentlich geboten ist aber wir bestrafen die ganz kräftig richtig kräftig so dann haben wir wieder unsere schöne Nachbarschaft Struktur die wir ursprünglich hatten in der das Leben schön ist und durch diese Bestrafung das ist die Zielsetzung weil das immer unser genau Ansatz ist ob Sie mir den Wedding oder immer so schwer die oder so weiter dieses Bestrafungen gibt wenn man ganz starke Tendenz der in 1 solche Lösungen wie diese zu minimieren bedeute das Bestrafung zum Beispiel indem man auf die Länge der Rundtour als Ziel Funktionswert noch die Anzahl der Verletzten Paarbeziehungen mit den ganz großen Faktor drauf addiert das wäre dann eine Möglichkeit es bestrafen Smart und Sie sehen jetzt so langsam auch den Vorteil dieser ganzen Verfahren oder einen weiteren Vorteil dieser ganze waren die wir jetzt gesehen haben ja dadurch dass sie so generisch sind ich mehr für sie aber die Übungsaufgabe damit das möglichst generischen machen dadurch dass diese Verfahren so generisch sind kann man kann man wunderbar solche Manipulationen durchführen kann man wunderbar an der Probleme die man hier hat Durchblick durch solche Dinge wie
Bestrafungen eine wieder versuchen zu heilen und man bleibt immer noch im selben algorithmischen schlimmer dran muss den Algorithmus aber nicht ändern es ist man kann immer dieselbe Idee weiter verfolgen ja weiß dass das schöne Siegel diese Bestrafung wir die ganze Zeit von Tendenzen bei 7 den gelingt davon Tendenz das eine Tendenz zum Besseren gibt bei den Ameisen im von der Tendenz zum Besseren gesprochen über das unschuldigen so weiter auch und Manipulationen der Zielfunktion um bestimmte Dinge möglichst zu verhindern möglich zu vermeiden oder möglichst oft zu vermeiden sind genau eine solche Tendenz passt wunderbar in diese ganzen algorithmische Schemata hinein der erzeugen so eine Tendenz okay da diese 1. dash ist das was ich eben gerne erst einmal sagte dass man zusätzlich zur eigentlichen Kosten Funktionen beim TSB die Länge der Rundtour dass man zusätzlich noch an Strafe deren draufsetzt hoch gewichtet mit eine entsprechende Strafe Faktor den man drauf multipliziert wo man die Anzahl der der der Verletzten Bedingungen der Verletzten relaxiert Nebenbedingungen dann bestraft wichtig dabei ist er sicher zu machen man muss man muss man muss diesen diese Strafe folgte dem man drauf setzt das Verhältnis zwischen der ursprünglichen Kostenfunktion diesen Zuse Strafe der haben der sich in diesem Strafakte ausdrückt dem wird um Mut 10 ja ich alle falls Sie nicht ganz klar ist was ich damit meine sollte vielleicht doch noch mal Kurt an der Tafel formulieren nein wir haben wieder die Low L das ist für sie zu ähnlich wie wir das hatten wir haben die Länge der Rundtour ja weil ich mich ich noch mal etwas verkürzt länger der Rundtour die ursprüngliche die ursprüngliche Zielfunktion Plus strafe Faktor nur weil an soll Verletzungen von Bedingungen ja das ist ein einfaches sinnvolles Schema wie man die Zielfunktion variieren kann und das für uns auf dieser vor jetzt hier geht ist der hier und die Einsicht sich machen dass diese Strafe Faktor im Laufe des Algorithmus nicht unbedingt konstant bleiben aus sie kenne das von der Temperatur beim 7 links was ja auch in gewisser Weise in einer komplexeren weisen Strafe Faktor dafür ist dass man dass man halt nicht unbedingt eine schlechtere Lösung wählt setzen müssen bis 10 schräg die Analogie vergessen Sie am besten gleich wieder aber der ich wenn das vielleicht noch mal erläutern an einem Beispiel dass ihnen wohl bekannt vorkommen sollte nämlich aus unsere Übungsaufgabe dann wir Problem die Welt wäre wunderbar einfach wenn ich diese Bedingung wäre das die richtige alle des jungen Zellen nicht dass sie völlig Rechtecke sich nicht überlappen durften ja ich meine gut im Extremfall wenn sie sich beliebig überlappten dürfen mehr dann haben dann hängen sie hatten Sie die alle an denselben period das ist das Beste was sie tun können alle übereinander wenn Sie nicht die Bedingung zu an sich an die Übungsaufgabe sollen eine gegebene Menge von Rechtecken platzieren disjunkt also dürfen sich nicht überlappen dürfen sich berühren aber nicht überlappen so dass er die Baronin Box-Thron rum minimale Fläche hat und wenn wir jetzt diese des und das Bedingung Relax ihren da mir die Problemstellung ganz einfach können wir machen und jetzt bestrafen wir das wieder jetzt bestraft ist bestrafen wir denn über alle ab wer zum Beispiel in dem wir für jedes Paar von von Recht Ecken einfaches Beispiel für das Waffenrecht Ecken berechnen wie viel die sich überlappen und das alles für für alle paar von richtigen aufzunehmen ist vielleicht ein bisschen viel Rechenaufwand das so zu machen quadratischen und der richtige kann man vielleicht auch geschickter machen will ich Ihrer Fantasie überlassen so und das und und solche Flächen bestrafen wir am Anfang wenig diese Überlappungen ja gerne seiner Nachbarschaft Strukturen aber scharf Struktur in der jedes richtige und unterziehen können beliebig bewegen kann ja es gibt schauen sie ins Forum der dafür Diskussionen schon weil er zum Thema geeignete Nachbarschaften das habe ich jetzt ich muss gestehe ich habe in dem Moment noch nicht daran gedacht dass das wir dass wir zu diesem Thema dann auch noch kommen werden aber dieser Punkt über die ich hier rede wird die vielleicht noch mal ein bisschen dieses Thema geeignete Nachbarschaftsbeziehungen Führungsaufgabe noch mal von einer anderen Seite beleuchten von einer sehr hilfreichen Seite ja am Anfang bestrafen wir die relativ wenig so so dass der Algorithmus so in guten Bereichen ist wohl der den sehr guten Bereichen und die weit länger der Algorithmus läuft umso härter bestrafen wie hier die solche Überlappungen sodass tendenziell schrittweise diese Überlappungen abgebaut werden das ist die Idee und am Ende bestrafen sie praktisch mit unendlich so das ist dann tatsächlich alles mit Gewalt auseinandergetrieben wird was noch was ich noch überlappt in aber dadurch dass wir sie nur bestrafen und nicht mehr zum da das Algorithmus zur harten Bedingungen machen haben ein viel übersichtlicheren Lösungsraum viel einfacher strukturieren Lösungsraum viel viel bessere Möglichkeiten mit Nachbarschaften und zu hantieren wie viel bessere Möglichkeiten wie mehr Wahrscheinlichkeit dafür dass diese suchen vielleicht bei der wir zur Strategie dass einzelne Individuen in der Evolution Strategie tatsächlich in Bereiche kommen die die die sehr vielversprechend sind wo es wirklich gute und echte Lösung dann geben könnte so das ist glaube ich im wesentlichen das was ich gesagt habe eben diese vor überspringen das auch noch mal das was ich eben gesagt habe kann auch überspringen ja also ich glaube es macht keine Probleme mehr manchmal froh sie haben es da noch mal zu lesen aber ich habe Satire noch meine eigenen Worten gesagt was sind die Probleme das Problem ist das funktioniert sehr gut konvergiert gut also gut gegen gegen sehr gute Lösungen da wäre durchaus nicht immer sehr schnell das heißt also wir müssen unter Umständen lange warten dass der Algorithmus funktioniert das Algorithmus zu guten Lösungen zu echten Lösungen auch kommt aber wenn er die gefunden hat dann sind die nach der Fahrt sagt die Erfahrung oft sehr sehr gut
so damit sind wir mit dem ganzen Abschnitt Suchverfahren Nachbarschaft basierte Verfahren durch und wir kommen zu einer zweiten großen Klasse von Verfahren dich Entscheidungs- basierte Verfahren genannt habe also diese Kapitelüberschriften Nachbarschaft basieren Scheidungs- basiert ich glaube nicht dass sich die 3. Bewohner habe ich glaube die habe ich hier für diese Vorlesung selbst ausgewählt weil es auch ein etwas anderer Zugang ist als in sicherer Tod typischerweise sieht man nicht in der Literatur diesen malischen Zwang zur Vereinheitlichung den ich hier an den Tag lege sondern das sind dann wirklich und wie einzelne einzelne Themen einzelne Abschnitte und wenn man sie liest dann kann man erahnen dass die was miteinander zu tun haben es gibt auch Hinweise in dem im Buch das die was irgendwie miteinander zu tun haben aber nicht so systematisch zusammengeführt wie hier ich habe sehen was noch nie gesehen ich habe auch das mich von Bucht auszumachen so worum geht es
hier es ist völlig das vergessen Sie Nachbarschaften der Nachbarschaften spielen bis ihre Prüfungsvorbereitung oder bis zur Oder abgesehen davon aber haben Jungs Aufgabe wie Sie es keine Rolle mehr so was wir hier machen ist den Lösung nicht als einen Grafen aufzufassen nicht als Nachbarschafts Grafen wo die zulässige Lösungen die die Knoten sind im Grafen und Kanten geben Nachbarschaften an sondern wir versuchen hier anders vorzugehen nämlich dass wir den Lösungsraum Schritt für Schritt zerlegen und wir werden sehen dass diverse Strategien die man meistens völlig unabhängig voneinander betrachtet dass das einfach nur spezifische Ausprägung dieser Grundidee sind so ich betrachte es zunächst mal wieder abstrakt ich Mut jetzt wieder maximal 8 Fraktionen so so wir haben jetzt eine Lösung zu eine Instanz der kann beliebig will jetzt irgendwie sein ja und was und beliebig komplex strukturiert er zum zweidimensional ich kann Ihnen aus bekannten Gründen keine höherdimensional Zeichnung anbieten so und vielleicht sind hier hier irgendwo sind dies über gute Lösung irgendwo da vielleicht nicht nur an einer Stelle vielleicht auch noch mal hier hier hier vielleicht sogar die beste Lösung aber da komme ich rein gar diesen Lösungsraum ist verboten der in den Bedingungen aber hier irgendwas sind diese berühmten Lösung und hier ist also nicht so toll so dieser Verfahren haben alle im Prinzip die Grundidee gemeinsam dass sie schrittweise den Wesens Raum legen so in 2 Hälften irgendwo so zwischendurch und versuchen herauszufinden ob es sich lohnt diese Hälfte weiter zuzulegen wenn es sich nicht lohnt wenn man wenn man eine etwas wenn man genug herausgefunden hat um zu entscheiden so können nein es lohnt sich nicht mehr diese Lösung in diesem Teil des Lösungs Raums weiterzuverfolgen da verfolge man noch den weiter und zerlegt den irgendwie anders wieder weiter zerlegt und so weiter es kann auch sein wie schwer wir wissen durch das was Sie eben gesagt habe ich unsere Draufsicht das hier nix prägen das passiert habe hier so gesagt kann aber sein dass das der Algorithmus nicht bekommt dass der keine ausreichendes Wissen über diese Seite aus bekommt und trotzdem und deshalb sagt ok ich weiß es nicht ob der prägen gute Lösung drin sind also mache ich hier weiter und sein Weg ist muss sich umgehend hier eine sehr stellt sein ja der Frau und die Zielsetzung ist natürlich und da sowieso kaum riesengroße ist wir können natürlich sagen ok wir zahlen bis wie bisher in jedem zeitlebens Teile in jedem Bereich nur noch eine einzige zulässige Lösung haben aber der während typischerweise exponentiell viele zulässige Lösung haben oder Schlimmeres ist das keine gute Strategie seine Strategie muss sein möglichst häufig zu verhindern dass man weiter zerlegt möglichst häufig sagen zu können ja es lohnt sich nicht diesen Bereich der es Lösungsraum weiterzuverfolgen sie abstrakte Sichtweise noch mal abstrakt aber eine etwas andere Abstraktion was ich hier so gezeichnet habe mit den schrittweisen Zerlegungen kann man natürlich also Baumstruktur auffassen der Knuth der die Wurzel des Baumes steht stellvertretend für die gesamte dem gesamten Lösungsraum ein Nachfolger der Wurzeln hier steht stellvertretend für das was ich links gezeichnet habe der andere Knoten in denen der andere unmittelbarer Nachfolger der Wurzel steht stellvertretend für das was ich rechts bezeichnet habe und so weiter und fort wenn mir diese Teilmenge weiter zulegen in 2 ergeben sich wieder zu einer Folge Knoten und so weiter und so fort und so rum ausgedrückt muss das Ziel sein diesen Klo diesen Baum möglichst klein zu halten möglichst häufig hier entscheiden zu können es lohnt sich nicht mehr den Teil der da drunter ist die der sich durch die weiteren Verfeinerung ergeben würde wenn wir diese Verfeinerung machen würden es lohnt sich nicht das weiter zu verfolgen wir wissen oder
wir sind unsere einigermaßen sicher dass sich das nicht lohnt also schneiden wir habe hier ist der Baum zu Ende hieß noch mal das selbe noch mal in etwas anderer Darstellung ist immer dieselbe Information so will kann man sich das vorstellen das kann man sich das einmal vorstellen da geht es darum hören zum Beispiel wenn Sie eine Problemstellung mit binären Variablen haben und E haben wenn Sie binäre Variable immer erst mal zu den zweiten Beispiel eine eine stetige Variable XII die also wir Zahlen annehmen kann dann heißt das zum Beispiel hier das ist die Achse dieser Variablen XI das ist der Nullpunkt und wenn ich hier durchschneiden heißt wir nehmen zu den Bedingungen her zu den Bedingungen die eine unzulässige Lösung aussieht ein nehmen wir einerseits noch die Bedingungen Kind 2 hier XII kleiner Rolle und hier nehmen wir noch mal die bedingt Herr X E mehr auf die Gleichung ist auch noch 8. vielleicht so ich sie größer gleich 0 ja da wir wissen aus wir haben unsere ursprünglichen Problemstellung Bedingungen die eine zulässige Lösung die sagen was eine sie lösen müssen was nicht ja beim TSB zum Beispiel bedingt dass es nur und ist jetzt das nehmen wir noch wenn wir irgendwelche konnte Variablen drin haben zum Beispiel beim Skier gelegen haben eine kontinuierliche variabel drin wo sie ein Job platzieren das in Entscheidung treffen in die eine Richtung gehen Sie bei der Zerlegung wenn Sie sagen dieser Job soll in den nächsten 10 Tagen beginnen und die und gehen Sie wenn Sie sagen dieser Jobs soll erst nach diesen 10 Tagen beginnen kleiner 10 Tage größer gleich 10 Tage das wäre ein Beispiel so könnt aber und für Beispiel eines ist die SPD wie üblich wieder ein gutes was was in leeren Variablen viele kannte die DDR war ja ob diese könntet oder soll ich dran ist und sie zerlegenden Lösungsraum die Menge aller zulässigen und Touren in 2 Teile wenn Sie auf der einen Seite die Bedingung einfügen diese Kante ist drin ja sie betrachten also die Teilmenge aller zulässigen Lösungen in den für die gilt dass diese kannte enthaltenes Änderung Tower und auf der anderen Seite die dir die in die andere Seite dieser Zuteilungsmenge das ist die Menge aller zulässigen Lösung aller und in den diese kann der nicht enthalten ist das ist kein währende typischer Art wie man das erledigen kann ja gerne sie abstrakt gesehen und auf dieser Folie jetzt sagen wir an diesen Beispielen was das konkret bedeuten kann ich hier Feature ist TSB war ein Beispiel die ist ein Feature bist Problemen sie einen sich das über Fischer bis Problemen über allegorisch Ansätze für wieder bis Probleme gesprochen haben da geht das selbe wie beim TSB sie nehmen sich ein Feature er über und P 1 kannte und sie zerlegen dienen die Lösungsmenge in die Menge aller zulässigen Lösungen wo dieses Feature dazu gehört und in die Menge aller zulässigen Lösung für dieses Feature nicht dazu gehört das ist einfach das Schema wie man schrittweise zerlegen kann und was sie versuchen ist Sie haben die ursprünglichen der Bedingungen was sein wir sie Lösung ist sie nehmen diese Bedingungen zu und sie versuchen aus diesem eingeschränkten Bedingungen zu sehen so sehr mit den Osten und herauszulesen ob es sich lohnt diesen diesen Teil weiter zu gehen oder was ich nicht und Kinder die Magie aber ist es ist es wäre Magie wenn es so gut funktionieren würde wie wir es jetzt vielleicht bei Ihnen angekommen ist aber wie üblich werden ja von den beschweren Problemen nichts funktioniert wirklich perfekt hier das kann ich ihn nicht anbieten wenn wir von den Dächern Probleme in das sind dann die Entscheidungsbäume an jeder Stelle eine Entscheidung die ich Sie gleich 0 ist es gleich 1 bei binären Variablen oder das andere Beispiel sie genannt habe dieser Job wie dem muss ein schockierter soll den 1. 10 Tagen oder eben nicht in den 1. 10 Tagen genommen begonnen werden das ist dieser Entscheidungsbaum setzen ist dass sie den Schein brauchen was wir zum Beispiel machen können ist hier wenn wir Fische blasiert sind dass wir die Features in eine gewisse Ordnung bringen das muss nicht die Reihenfolge sei mit der sie indiziert sind nicht selten wird man sie in der in der Reihenfolge ihres Gewichtes Herr nehme die schwersten zuerst oder die am wenigsten schwersten so schweren so erst und es an jeder Ebene sie was
nicht an jeder Ebene nehmen wir uns ein Feature vor ich glaube diesen gerade diesen Baum soll dich mal zeichnen damit das klar ist was gemeint ist mehr er hat Ruth ist können sie haben hier die Wurzel des Baumes und habe mir die Entscheidung Feature 1 ja oder nein und eine Richtung soll ich vielleicht ein bisschen flacher zeichnen so eine Richtung des ja eine Richtung ist dahin mit der Semantik dieser Teil warum hier entspricht den zulässigen Lösung in denen dieses Feature 1 enthalten ist und dieser Teile Dornier entspricht den zulässigen Lösungen in den dieses Feature 1 nicht enthalten ist hier ist jetzt die nächste Frage Feature 2 ja oder nein so dann haben wir hier einen feine wo sowohl Fischer 1 also Feature 2 in der Lösung dran sind Feature 1 Jahr aber Feature 2 nicht Feature 1 nicht aber Feature zwar ja und hier beide nicht und so weiter also diese Menge dieser Teil waren hier der hier noch dranhängen weiter entspricht der Menge der zulässigen Lösungen in den weder Feature 1 noch Feature 2 drin ist und der hier beispielsweise entspricht der Menge zu wissen müssen wo zwar Feature 1 aber nicht wieder 2 dran ist und so das ist sinnvoller wenn der Baum nicht gut ein warm und
Partitionen ist vom zulegen Sitzungsraumes das haben wir so weit betrachtet das er mich schönen Worten gesagt hier nun vielleicht der letzte dash hier noch die wo endet diese Zerlegung in der ja in dem Moment werden wenn die wenn die Teilmenge die diesen Klonen spricht nur noch ein 1 zu 1 endete das heißt es 1 1 7 einige Mängel ist im Englischen als es im Garten
so das spannende eine Sache ist wie man da einen angeht geht ja wir haben jetzt wichtig ist dass das nun abstraktes Konstrukt ist ja das wird niemals in den Rechner reinpassen natürlich nicht ja die Menge der zulässigen Lösungen der die Blätter wären sehr viel zu groß das heißt also etwas was wir ja durchaus auch von anderen Ursachen her kennen der dieser Baum ist nur ein abstraktes den Konstrukt wie durchlaufen immer nur Teile dieses Baumes wie betrachten in dem Moment nur einen Teil des Baumes der klein genug ist um den Rechner anzupassen so was wie kann man vorgehen wir haben jetzt ein Problem wir können natürlich nicht den ganzen Baum durchlaufen ist viel zu kurz wer auch ein bisschen mit Kanonen auf Spatzen geschossen weil es gibt auch einfacher Möglichkeiten sämtliche zulässigen Lösungen durchzugehen zu enormer werden auf das er hinauslaufen würde wenn mit diesen ganzen Baum durchlaufen würde und jedes Blatt einmal besuchen würden so es gibt 2 Möglichkeiten wie man gehen kann Potäntschl Exhaust trifft das heißt wir lassen den Algorithmus tatsächlich so laufen wie es Ihnen gesagt habe ja an jedem Knoten schauen wir ist es wirklich notwendig in den Teil Baum runter zu gehen oder ist es nicht notwendig wenn nicht dann ging ich runter sondern vergessen dass sie dem anderen weiter und wenn es notwendig ist den gehen werden Teil unter im schlimmsten Fall passiert dann genau das was sie eigentlich nicht machen können nämlich alle den gesamten Baum zu durchlaufen weil wir nie ein keinem Knoten jemals festgestellt stellen konnten er wir können nicht mit ausreichender Sicherheit sagen es lohnt sich nicht diesen Teil vom zu durchsuchen es kann immer noch sein dass die wirklich guten Lösung in diesem Teil drin sind das kann man nicht ausschließen mehr da wäre dann die Hoffnung dass die Regel zum Ausschluss vom Bauer von Teil Bäumen stark genug ist stark genug greift das eben nicht das passiert dass der Baum ganz Durchlauf wird sondern dass es möglichst häufig nicht er heute möglich sei wie abgeschnitten wird so dass aus diesen riesigen Entscheidungsbaum Sommersonne Bonsai-Bäumchen wird andere Möglichkeit ist dass wir von vornherein sagen sie geben die wir gehen nicht das Risiko ein dass wir am Ende dastehen und den gesamten Baum durchsuchen was er gar nicht geht sondern wir sagen und vorne rein oder auch mittendrin nein bewusst absichtlich wir besuchen auch Teile des Baumes nicht obwohl wir nicht wirklich ausschließen können das dann nicht diese Brückenlösung Lösung sind ja das unwürdig kommen nur wir versuchen eine jedem einzelnen Knoten und möglichst sicher zu sein mit möglichst großer Wahrscheinlichkeit mit möglichst guten Gewissens sagen zu können ja da wird wohl wahrscheinlich keine wir da wären wahrscheinlich nicht die Lösung drin sein dieser nicht verpassen möchten gut das das habe ist genau das was ich eben im Prinzip gesagt habe hier vielleicht noch einen Begriff der Bayer Tuningen das ist der Begriff wenn wir ja wenn wir so einen Sohn Baum als Ganzes abschneiden können insofern sie 7 Literatur also wir versuchen ein Zertifikat Sitte viel Geld eine eine Gewissheit ist das mal so vorsichtig eine Gewissheit zu erzeugen oder eine große Plausibilität zu erzeugen wenn schon keine keine keine wirklichen Beweise dass wir keinen Fehler machen wenn wir diesen Teilnorm abschneiden das wären da nicht reingehen müssen weil da nix Interessantes passiert und die andere Variante dass wir das irgendwie absichtlich vorsätzlich Teile des Baumes es gebe überspringen das also Tuning machen und uns wirklich sicher zu sein der das heißt das dass die Suche dass wir einen wir bauen sich einen Fehler ein wir versuchen diesen Fehler möglichst klein zu halten mit Plausibilität Argumenten aber wir haben einen systematischen wieder dran es kann sein dass die schönen Lösungen die wir eigentlich haben wollen alle drin sind in den Teilen diese abgeschnitten haben und das versuchen wir möglichst unwahrscheinlich zu machen so das Ganze kann man natürlich auch als ein Algorithmus formulieren wir fangen an mit der Wurzel die repräsentiert hier steht in der wir das auch das ursprüngliche Problem aber natürlich was sie konkret repräsentiert ist die Menge der zulässigen Lösungen für die gegen Instanz Alex Blood ist noch nicht fertig und solange es also was sie hätte im Prinzip haben ist das Schema für Grafen suche das allgemeine generische Schema für Grafen suche dass sie einerseits als Tiefensuche andererseits ausbreiten suchte genau spezifizieren können sie haben ein
Exploit vielleicht kann man das auch noch visualisieren mehr period die warum so Sie wissen Mengen zeitlich als Kriege und Bäume zahle ich nicht als Dreiecke so dass ist der Baum hier ist die Wurzel ich und sind dann die Blätter wir müssen nicht alle auf gleicher Höhe sein ist und es vielleicht ein bisschen ein bisschen allgemeiner zeichnen so dass der Baum so und in jenen Zustand dieses algorithmisches Schema ist haben wir eine Freund durch den Baum man durch die irgendwie 1. Mal aus sehen kann ja hier sind die einzelnen könnten und diese und besteht aus kannten so ich das mal also Zeichen ich jetzt nicht hier in Gänze so aus als man kannten von Exploits Knoten diese hier Explorer Ort und hier ist alles ein Exploit ja sie kenne solche Schemata zum Beispiel Funke sowie Algorithmus die die man schon bearbeitet hatten die immer noch nicht bearbeitet hat und so etwas und in jedem Schritt gehen sie einem beliebig 1. einmal einen Knoten mehr zu den Exporten explorieren den sozusagen und haben die werden von entsprechend um diesen einen Knoten verschoben nach unten dies natürlich Spezialfälle wenn die Wellen Freunden so aussieht vielleicht nicht ganz hundertprozentig auf einer Ebene so meine ich immer haben können sondern so auf 2 Ebenen verteilt das heißt dann würde man jetzt hier den als nächstes nehmen und so weiter das ist das was sie auch in einen Zusammenhang kennen gelernt haben als breiten suche bereits für das deutsch wenn Sie hingegen diese Wellenfront ganz anders haben zum zum Beispiel indem sie erst einmal hier zum Beispiel ganz links muss ich ganz links Inhalt irgendwo ganz und das gehen dann weiter so hier teilweise exploriert haben schon immer weiter und dann hier weitergehen wenn die Wellenfront so aussieht das ist auch etwas was sie am von anderswoher kennen die tiefen Suche DFS es einheitliche Schema das ist sozusagen der allgemeine Frage der der der der generischen Fall und das sind die beiden extremen Fälle zu den das ganze ausarten kann durchlaufen wir ja schützt 2 aber ist wir werden 1 ein Exploit Knoten das ist der in diesem Bild das ist der in diesem Bild und wenn sie wenn sie echt ist der es machen dann ist auch hier gegeben welches der nächste sein muss nämlich der hier aber es muss nicht das der es seien sie könnten wenn Sie glauben dass das sinnvoll ist könnten Sie auch das alles überspringen zum Beispiel hier weitergehen ja Sie haben auf volle Narrenfreiheit in diesem allgemeinen Schema so jetzt immer und diesen Knoten also her das ist der hier etwa in diesem Schema und jetzt geht es wieder eben die ganze gesagt haben jetzt geht es um die um diesen Teil warum der da drunter hängt ja sehen ich ich eben sagte wolle müssen bei mir Dreiecke die nach oben zeigen und 2 Libyer sagt entweder wie kriegen wir das hin diesen Teil warum nicht zu durchsuchen sondern schon fertig zu werden dass wir sagen etwa bei einem Optimierungsproblem bestellen fest also gar keine zulässige der Menge drin oder dann kann das Abschneiden da oder wie finden vielleicht auf eine Art und Weise optimalen Algorithmen eine optimale Lösung in diesem Treiber um und das ist in diesen Tagen untergegangen sind und das ist eine Möglichkeit wie wir das machen können wir dann sehen oder wir stellen fest wir sind uns ziemlich sicher dass dieser dieser dieser Teil Baum und interessantesten schneiden wir den ab oder wenn man da nix sagen können dann gehen wir und da in diesem Tagen also dann werden dann werden diese Nachfolger von diesen Knoten hier werden Sie Teil teilte Wellenfront so und das Ganze ist richtig schön abstrakt
nicht wir werden dieses ab sagte Schemer wieder genauso wie das abstrakte Schema bei Nachbarschaft suchen mit Leben füllen einerseits mit Beispielen was das für konkrete Problemstellungen heißen kann andererseits auch mit konkret also der konkreten Algorithmen die auf verschiedene Arten und Weisen hier beispielsweise auch DFS und wenn es tatsächlich realisieren hier kommt es bei BFS zu das wird etwas werden was ich vielleicht aus an konnte schon kennen den Namen dynamische Programmierung weiß nicht ob Sie diesen Begriff gehört haben dass man versucht festzustellen 2 Lösung auf gleicher Ebene sind identisch alles war gut ist was sich aus eine so als einen der aus dem einige rauskriegen kann kann ich aus aus dem andern rauskriegen also man kann ich schneide wegschneiden oder hier bei TMS dass mein Mann ist vielleicht mal ganz runter gegangen hat gute Lösung gefunden und auf Basis dieser guten Lösung kann man besser entscheiden dass das etwa irgendwelche Teile Bäume uninteressant sind weil die Lösung die hier raus kommen könnten nicht so gut sein können wie das was wir hier schon gefunden haben das das haben Sie vielleicht auch schon mal anderswo gehört dass hat den Namen Braun schon bei und aber für heute sind wir durch gleich ist wieder mal langsam für das zuwege pünktlich geschafft habe das Ganze hier aufzubauen können wir auch pünktlich hier Enten und ich wünsche Ihnen noch immer schöner 2. Wochenhälfte bis dann
Loading...
Feedback
hidden