Neighborhood-Based Approaches - Population-Based Approaches

Video thumbnail (Frame 0) Video thumbnail (Frame 3151) Video thumbnail (Frame 4741) Video thumbnail (Frame 12384) Video thumbnail (Frame 13899) Video thumbnail (Frame 27123) Video thumbnail (Frame 40347) Video thumbnail (Frame 53571) Video thumbnail (Frame 55146) Video thumbnail (Frame 57251)
Video in TIB AV-Portal: Neighborhood-Based Approaches - Population-Based Approaches

Formal Metadata

Title
Neighborhood-Based Approaches - Population-Based Approaches
Title of Series
Part Number
5
Number of Parts
12
Author
License
CC Attribution - ShareAlike 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this 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...
Radical (chemistry) Direction (geometry) Moment (mathematics) Feasibility study Perturbation theory Optimum Lösung <Mathematik> Local ring Local ring
Radical (chemistry) Function (mathematics) Perturbation theory Feasibility study Optimum Local ring Mathematical optimization Local ring
Kante Slide rule Direction (geometry) String theory Perturbation theory Feasibility study Lösung <Mathematik> Set (mathematics) Term (mathematics) Sampling (statistics) Subset Similarity (geometry) Plane (geometry) Strategy game Solution set Function (mathematics) Time evolution Local ring Directed graph
Graph (mathematics) String theory Lösung <Mathematik> Subset Permutation Matrix (mathematics) Strategy game String (computer science) Vertex (graph theory) Length Rule of inference Slide rule Euclidean vector Element (mathematics) Feasibility study Set (mathematics) Formalismus <Mathematik> Binary file Permutation Connected space Position Index Travelling salesman problem Object (grammar) Matrix (mathematics) Group representation
Standard deviation Process (computing) Constraint (mathematics) Graph (mathematics) Lösung <Mathematik> Limit (category theory) Mass Infinity Total S.A. Sampling (statistics) Permutation Degree (graph theory) Solution set Strategy game String (computer science) Chromosomal crossover Summation Fundamental theorem of algebra Rule of inference Slide rule Theory Feasibility study Rounding Position Positional notation Function (mathematics) Military operation Strategy game Chromosomal crossover Mathematical optimization Group representation
Process (computing) Constraint (mathematics) Theory Feasibility study Lösung <Mathematik> Limit (category theory) Total S.A. Zielfunktion Group representation
Process (computing) Constraint (mathematics) Theory Feasibility study Lösung <Mathematik> Point cloud Limit (category theory) Total S.A. Zielfunktion Sign (mathematics) Partial derivative Maß <Mathematik> Group representation
Function (mathematics) Constraint (mathematics) Graph (mathematics) Feasibility study Infinity Approximation Zielfunktion Group representation
so genau sind die anderen immer so sein dass er verlängert Ferien an der TU Darmstadt so Taylor sollst
diese period hatte ich letztes Mal kurz übersprungen weil ich mir in dem Moment nicht sicher war ob ich das richtig rüberbringen würde das mir natürliches nochmal gesehen hat ja gesagt dass ich das dann auf dieses Mal verschieben würde das ist jetzt auch keine besonders tief liegende Sache worum geht es also sie erinnern sich wir hatten Varianten von Search bei denen wir auch in dem Moment in denen lokale so in ein lokales Optimum gekommen sind dann noch etwas anderes gemacht haben zum Beispiel bei tabu suche das wird dann eben bei gegangen sind sozusagen dieselbe Richtung auch wenn es Verschlechterungen gibt werden auf der anderen Seite gesehen die einfache Idee dass man nicht eine lokale Suche macht sondern beispielsweise eine Million lokale suchen von zufällig ausgewählten verschiedenen Startpunkten in der Hoffnung wenn wir die wirklich ausreichend zufällig aus suchen dann gibt es ausreichend viele Treffer unter den Millionen die in eine wo wir schon in einem sehr guten Bereich des Lösung Frauen sind und wenn wir dann von dort aus lokale Suche machen dass wir dann schon zu einem sehr guten Lokalen auf dem und das ist die Hoffnung die natürlich in der Praxis durchaus ihre Bestätigung findet nicht immer aber immer öfter also nicht immer aber sicherlich in vielen verschiedenen Situationen beziehungsweise werden diese Bestätigung nicht als wenn es doch nicht so gut funktioniert sollte man sich vielleicht überlegen ob man die die diese zufällige Auswahl dieser eine Million oder 1 oder 10 Millionen oder wie viel auch immer Staat Lösungen ob man an den ich ein bisschen was vom Astrid denn irgendwo muss ja die gute Lösung so hier das ist ein bisschen dass dazwischen wir machen eine im Prinzip machen wir eine lokale Suche aber
wir wenn wir im lokalen Optimum gelandet sind dann nach dem Kursrutsch nicht nur einfach keinen Schritt in der Nachbarschaft und wir machen eine größere Änderung zum Beispiel bei einer Rundtour das sehe dass sie einfach eine größere Anzahl von Knoten hernehmen immer noch klein im Verhältnis zur Gesamtzahl der Knoten ohne größere Hansafunk hernehmen und die deren der deren zum Beispiel deren Platzierung beliebig umändern so dass sie dann also eine neue Rundtour bekommen mit der sie dann wieder weiter machen in der Hoffnung den Sie da irgendwie willkürlich herum die Kritik Knoten geschoben haben dass sie dann zu einer Lösung kommen die außerhalb dieses Lokal Optimums und seinen Einflussbereich ist jenseits der nächsten Bergkette kehrte auf der anderen Seite so dass sie dann so wie hier im Bild angedeutet eine Chance haben zu den besseren lokalen Optimum zu kommen und das ist eigentlich alles was dazu zu sagen ist mehr will ich auch
dazu nicht sagen wir können dann
zum zum eigentlichen Thema des heutigen Tages kommen zum 1. Thema sollen wir Tagesgeld Algorithmen das ist ein sehr eine sehr beliebte Vorgehensweise wir haben beim letzten Mal Evolutions- Evolution Strategien betrachtet die in gewisser Weise eine Simulation der biologischen Evolution der allen biologischen Evolution ist Mutation und Selektion die die die einzelne Video auf der Ebene der Gene der Erbanlagen mutieren in der Natur natürlich extrem langsam er hier und ist natürlich schneller haben wir haben keine 5 Milliarden Jahre Zeit bis wir zu Lösungen kommen die immer noch so schlecht sind wie der Homo sapiens sondern wir wollen in kürzerer Zeit zu besseren Lösungen kommen und einer der wesentlichen Punkte warum es überhaupt oder der vielleicht der entscheidende Punkt warum es überhaupt in der biologischen Evolution zu einer solchen Explosion von Artenvielfalt einer solchen Höherentwicklung von einfachsten Lebewesen bis zu so merkwürdigen Lebewesen die uns gekommen ist liegt daran das eben Mutation und Selektion das nicht durch Mutation und Selektion im Laufe der Zeit eine neue Strategie heraus gebildet hat sexuelle Vererbung Rekombination und genau das wird hier simuliert das heißt also wir haben nicht mehr wieder wird sonst Strategien eines individuellen die im Wettstreit miteinander liegen die die die da also die die nicht die gegen Anna kämpfen sondern die die alle sozusagen im im selben Hamster Rat vorwärts laufen und die die die richtige Richtung laufen die gewinnen die duplizieren sich und dann den 2 separate Individuen ihren Weg und die die die in die falsche Richtung laufen die werden aus dem Spiel genommen hier geht es jetzt darum wir nehmen uns 2 in der Natur wieder Beloki 2 Individuen her und lassen von denen jetzt nachkommen entwickeln und zwar weil das ein besonders einfaches Schema ist immer auch gleich 2 Nachkommen also immer Zwillinge so wir brauchen wir brauchen allerdings dafür eine speziellere Kodierung was allerdings auch kein großes Problem ist wir haben bisher zunächst einmal immer eine sehr abstrakte Struktur zugrunde gelegt das ist die Nachbarschaftsbeziehungen auf den auf den zulässigen Lösung was nicht damals war als ein gerichteter Graph mit denen kann die Knoten sie als zulässigen Lösungen und die Kanten definieren die Nachbarschaftsbeziehungen wir haben beim letzten Mal auch Algorithmen betrachtet die eine stärkere Struktur benötigen das waren die Feature bei ist Algorithmen das heißt wenn Sie sich erinnern es gibt eine Menge von Features und jeder jeder der zulässige Lösung eine bestimmte Teilmenge dieser Grundmenge hier brauchen wir auch wieder eine zusätzliche Struktur und zwar codieren wir denn Lösungsraum die die Elemente des Lebensraums aus ich zulässigen Lösungen als es Drings über einem Alphabet und dann folgen wir voll und ganz der Biologie ist die sich vielleicht aus dem Biologieunterricht oder die von Ihnen die bei mir also mische Modellierung gehört haben er in denen sich das vielleicht aus spreche Mode Währungsproblemen die Erbanlagen dessen Konzept DNA-Sequenzen wenn man das Ganze wenn man die ganzen biologischen Details ab weg absolviert und sich anschaut was ist denn die Informationen oder wie ist Information die aber der Erbanlagen kodiert in den DNA-Sequenzen dann kann man sagen der auf gesehen ist das es dringend über einem Alphabet von 4 Buchstaben diese 4 Buchstaben meistens CGT dass die Anfangsbuchstaben der 4 Säuren die die tatsächliche Information in dieser Doppelhelix codieren wobei wir natürlich als Informatica immer zuerst nicht Analphabet mit 4 Buchstaben sondern ein Alphabet mit 2 Buchstaben denken und 1 aber das ist nicht zwingend notwendig ich sollte dazu sagen wenn sie weiterlesen zu diesem Thema dann also vor allem in Informatik auch weiterlesen dann werden Sie feststellen dass die Übertragung der biologischen Begriffe die in der Biologie natürlich alle ganz klare feste Bedeutung haben aber die Übertragung Informatik ist nicht so wirklich standardisiert müssen sie aber ich denke es sollte in jedem Fall aus dem Kontext klar was damit hier was gemeint ist so bei Fichte willst
Problemdefinition das ist eine ganz einfache Kiste was heißt doch mal wieder bis habe ich eben schon mal gesagt Sie haben eine gute Menge von Features endlich sollte typischerweise endlich sein ist nicht zwingend notwendig aber sollte endlich endlich sein und da wir gewisse Teilmengen dieser Grundmenge sind zulässige Lösungen sie wissen sie können jede Teilmenge einer Menge auch kodieren als 0 1 Viktor als in kartesischen weg dieser Teilmenge indem sie ein weg im Sektor haben der so lange ist wie diese Teilmenge wie diese Gesamtmenge Element dazu also für die eine Komponente für jeden Einzelnen es ist also meint dieser Grundmenge und einer 1 an einer Komponente besagte an einem Index besagt dass dieses Element dieses Feature in der Teilmenge drin ist und eine 0 besagt dass sie nicht drin ist und schon haben Sie einen entsprechender Kodierung TSB ja haben
wir natürlich auch als Feature basiert modelliert ist nämlich wieder Einzelkarte zu sagen ob sie drin ist oder nicht aber da ich hier in diesem Kontext ist es durchaus sinnvoll oder so sinnvoll mehr an eine andere Kodierung des DSB zu denken die wir auch betrachtet haben einfach Kodierung was bedeutet denn eine Testpiel Lösung das ist eine Reihenfolge der Städte die Reihenfolge in der sie diese Städte besuchen wollen das ist das ist einfach eine zulässige Lösung des DSB und das kann man natürlich auch alle entsprechend als eine Permutation konnte er codieren das heißt also was ist mit der Mutation eine Permutation von N Elementen von allen Objekten es ist einfach 1 trinken den können Sie 1. dringen er über dem Alphabet auffassen wo sie jedem einzelnen Objekt dort seine Position zu weiß er sich reimen sie haben den verschiedene in C ist für jedes viele Stadtteile und Sie schreiben der jeweils die Positionen in der Reihenfolge so sie müssen natürlich festlegen welche Stadt es ist die Nummer 1 bei einer Rundtour ist ist ja eigentlich egal und dann ergibt sich da ergibt sich automatisch aus darunter welches die welche Stadt es an Position 2 welche Stadt an Position 3 und so weiter so oder auch so wenn Sie 0 1 wir da Vektoren haben wollen wenn sie nur eines Tricks haben wollen können Sie auch eine andere Matrix definieren wo sie sagen der Wert die die Komponente eine Zeile I und der Zeit und der Spalte J ist entweder 0 und 1 und 2 1 genau dann wenn i die Position von I in der Rundtour gerade J ist was sich ob das aus der Linien Algebra mitgenommen haben das ist im Prinzip eine Permutation Smart etwas mit Mutations Matrix in dem sich die 1 Matrix der diagonal alles 1 alles andere 0 und dann kommentieren sie die Diesch Zeilen oder die Spalten und alles was sie auf diese Art und Weise generieren können mitmachen naheliegenderweise Permutation trickst so Graf Karl Rink ist noch an Beispiel bekommen gleich zum Algorithmus ich glaube ich mal kurz vorausschauend darf ja wohl letztes Beispiel keine Sorge Graf Kollegen sie Sie erinnern sich das war das Problem aus auf der einen Seite entstanden ist aus dem aus der Frage mit wie viel Vorhaben wie fahren braucht man um eine Landkarte zu färben wo wir dann jedes Land durch einen Knoten ersetzt er repräsentiert haben und wenn 2 Länder benachbart sind dann sind die beiden Knoten verbunden durch eine ungerichtete kannte und die Aufgabe besteht darin dass es genau das Graf gelang Problem jedem einzelnen Knoten eine Farbe zuzuweisen so dass 2 Knoten die mit markanter verbunden sind unterschiedliche Farben haben und natürlich wird das Objekt die dass das Optimierungs- Ziel dabei ist die Anzahl der Farben die Sie benutzt haben dafür zu minimieren so das wir haben uns auch Dreiräder natürlich an dem Manne triviale Möglichkeit einer anders Graf gar rings in die wir leben Knut eine andere Farbe geben das heißt wir müssen von vorne herein wir werden nicht mehr als Farben brauchen wenn wir n Knoten dem Grafen haben das heißt wir können von vornherein die Länge des Strings da oder das Alphabet begrenzen wir haben wieder dieselbe Situation die beim TSB wir haben für jeden Knoten einen Index die für Farbe und dieser Index die Farbe wird dadurch ausgedrückt durch die durch die Nummer dieser Farbe die wir ohne bestimmte der Allgemeinheit auf 1 bis n reduzieren können auch hier wieder in ähnlich wie beim TSB können Sie beispielsweise auch verschiedene sehr analoge Kodierungen hier nehme also wichtiger Punkt hierbei ist auch immer was immer wieder mitschwingt haben es gibt nicht die Problemstellung ja es gibt auf der einen Seite die abstrakte Problemstellungen wie sie in der Welt vorkommt wie das TSP Sie wollen sie wollen bestimmte Punkte möglichst schnell hintereinander anlaufen und auf der einen Seite gibt es dann die Codierung dieser Problemstellung in einem Formalismus und wie diese Kodierung ist da haben Sie wie Sie hier an diesem Beispiel auch sehen da haben Sie eine gewisse Handlungsfreiheit wie diese Kodierung ist davon hängt es natürlich ab die Algorithmen die sie an werden dann später gute oder schlechte Ergebnisse liefern oder umgekehrt von Algorithmen diese anwenden wollen hängen ein das dann ab was eine gut oder was eine schlechte Kodierung ist das sind Dinge die man nicht so richtig gut verbalisieren kann wo man Erfahrungswerte sammeln kann und wo man dann eben auch herumspielen kann er sie haben Problem wie dieses Graf Gelenkproblemen sie werden eine Kodierung sie lassen darauf Algorithmen rumlaufen und sie kommen auf keinen grünen Zweig es funktioniert einfach nicht und ich Sie kommen zu keinem guten Lösungen sie können den Algorithmen um spielen dass sie dass sie das in den andern Album muss auswählen oder dass sie an dem Algorithmus diese ausgewählt habe noch ein bisschen drehen und und Schrauben und oder Sie können sich auch überlegen ob die Kodierung die ich gewählt habe die vernünftige ist oder ob ich nicht wie dass eine andere Kodierung werden sollte und da kommt wieder ins Spiel das was ändern Übungsaufgabe auch sehr wichtig ist ja wenn Sie das so abstrakt formuliert Algorithmus so abstrakt formulieren wie ich es vor der eine in der Programmieraufgabe dann ist es überhaupt kein Problem mehr da drunter eine Kodierung rauszunehmen und eine Kodierung reinzustecken ja dann dann brauchen dann brauchen Sie vor den ganzen Algorithmus nichts aber auch gar nichts nochmal neu programmieren der Abstraktion die Attraktion auf die Spitze zu treiben wie wir das hier Programmieraufgaben machen ist nicht einfach eine Schikane und ist auch nicht nur didaktisch zu Unterstützung des Vorlesung Stoff ist sondern hat handfeste Vorteile und das ist eine Denkweise die Ihnen sicherlich über die über die hier betrachtete der Thematik Optimierungsalgorithmen weithinaus helfen kann denn sie an Datenbanksysteme dass sie das dann Datenbankschema Schema ändern ohne dass sie die ganzen Applikation da drüber ändern müssen so wieder mal das Wort zum Sonntag jetzt kommen wir wieder zurück zu den genetischen Algorithmen wie kann man sich das vorstellen also grundsätzlich sieht das so aus ich das schon im mündlich angedeutet habe ich mache nur noch meine kleinen scheint das die vielleicht vorher machen sollen ob des ob die Kamera das richtig gut mir geht es so wir nehmen uns 2 zulässige Lösungen her wir haben wieder wie bei den Evolution Strategien eine Population von Lösungen also Bodylotion nehmen uns nicht immer eine Lösung her und schmeißen raus oder oder war oder lassen Sie sich duplizieren sondern wir nehmen 2 die wer Bilgi auch die sich möglichst deutlich unterscheiden sollten ja wirklich wie wie auch wollen wir keine Inzucht produzierende wollen keine Inzucht dass das wissen Sie ja ist die Erfahrung pro verstärkt negative ab Merkmale die normalerweise durch diese Rekombination wenn die Erbanlagen der beiden Partner ausreichend weit auseinander sind typischerweise nicht verstärkt würden so und die bilden zusammen wieder 2 neue und sie sehen schon vielleicht allein durch dieses Bild schon bekommen Sie eine Ahnung davon wie wichtig es ist dass wir eine vernünftige Kodierung haben in Form von Strings wie der Biologie auch ich glaube wenn die Biologie keines trinkst erfunden hätte als Erbanlagen gäbe es uns wahrscheinlich
nicht als gebe es definitif nicht in ist in der bei uns drin aber aber ob es zu einer solchen Explosion von Artenvielfalt hätte kommen können und von solche Weiterentwicklung das ist dann schon fraglich so wir haben das ist ein bisschen anders natürlich wir müssen natürlich Abstriche machen wir müssen Kompromisse schließen wir wenn wir das Ganze als Computerprogramm laufen lassen dann wie in der Evolution Schuldigen auch läuft das immer in Runden ab dass es in der in der natürlichen Evolution natürlich nicht der Fall und wir haben immer Zwillinge immer Zwillingsgeburten und die die typische starre geben wir uns gleich noch ansehen werden sehen so aus da ist die beiden schafft das spielt Rolle da spielt Rolle B um den zu produzieren und da spielt Rolle und da spielt Rolle B und dann den zu produzieren das wenn wir gleich sehen was das heißt nur noch zu Themen ok da ich sicherlich auch öfters mal rein verfallen dass ich von Quass war sprechen anstelle von Rekombination das ist eigentlich in Gänge aus doch sowohl in der in der Informatik als auch in der Biologie so Qualität Qualität einer Kurs einer solchen Rekombination Strategie am na ja wir werden natürlich von vorne rein wie auch in der Biologie vor allem Eltern aus die die besonders gut sind also was was bei uns bedeutet deren Ziel Funktionswert besonders gut ist am in der Bilder geben die Fitness was Michael gesagt hatte Angepasstheit bedeutet im Gegensatz zu dem was die Sozialdarwinisten glauben so das heißt wir machen das selber im Prinzip wie in der in der Wende wird so Scholle gehen wir lassen den Zufall sein seine Raum aber die wenigen zulässigen Lösung die besonders gut sind die haben eine sehr viel höhere Schauers für die Rekombination ausgewählt zu werden als diejenigen zulässigen Lösung die nicht besonders gut sind da zum Beispiel und und wenn mehr und mehr und wenn wir wenn wir zu gute Lösung haben dann sollte er dann sollte auch möglichst viel an Gemeinsamkeiten von diesen Eltern durchaus übertragen werden wenn sie zum Beispiel jetzt zwar 2 Pole und 2 Positionen denselben wert haben dabei dann sollte das eigentlich auch bei den beiden Offspring bei den beiden Nachkommen ebenso wie jeweils diesen Wert haben und wenn ein bestimmter Wörter nicht ist dann sollte bei den bei den Eltern dann soll der bei den Offspring danach nach komme auch nicht sein aber trotzdem die die die Grundidee bisschen das was eben auch in der Biologie den Erfolg der Rekombination ausmacht ist das eben im Gegensatz zum Mutation und Selektion nicht allzu große Ähnlichkeit zwischen den Eltern und den Nachkommen haben sondern dadurch dass 2 sehr unterschiedlich möglichst unterschiedlicher Eltern gewählt werden ergibt sich automatisch aus auch die Nachkommen wenn wir das aber wenn wir das vernünftig und man davon und den Kurs Strategie machen dass auch die Nachkommen dann sich unter einander stark unterscheiden sich auch von den Eltern stark unterscheiden so das wie er nebenbei bemerkt auch noch einen viel größeren Bereich des Lösungs explodieren bei den ich immer nur kleine Schritte voran machen sondern gleich große Springer so wir gucken uns das jetzt an nur die Notation wir haben also hier das kann ich eine Tafel eintragen diese Notation wir haben hier P 1 und ihr B 2 und hier haben wir Ostring 1 und Ostring 2 und das ist schon die ganze Notation auf dieser Folie so das Zeichen ich ihn lieber an als dass ich versuche in die Folie zu erklären 1 Punke so ganz primitive Sache guten ich muss das Bild jetzt aber etwas variieren sie haben hier den per 1 es mir aber comma dass nicht sowieso ein Bild davon dann da ist Nein ist nicht da also mache ich das jetzt hier und den per 2 und Sie haben jetzt hier irgendwo eine Nummer 1 Position P irgendwo drin dieselbe Position hier so haben das schaffe ich so und das schreibe wie ich so und was wir jetzt rauskriegen sind wir aufs ich bringe 1 und der Offspring 2 das ist die Position des hier auf der Seite und genauso hier die Position P auf der Seite und was jetzt rauskriegen ist eine Rekombination die bis dahin gleich dem per Hand eines ist und umgekehrt die bis dahin den Paaren gleichen kann 2 ist und was letztendlich gemacht worden ist ist dass dieser Bereich nach B vertauscht worden ist da sehen Sie wie Sie einfach die Sache wird wenn wir tatsächlich solche zulässige Lösung als Drinks codieren bei werden einfach solche Operationen machen können die sonstige nehmen und so aus einem sollen aus den und woanders hin anhängen Toboll Grasober ist eine leichte Verkomplizierung des Ganzen kann betont period nein Roth sie haben wieder 2 per Hand werden 2 älteren und vielleicht ein bisschen länger und wir haben jetzt 2 Positionen L und ja es muss ich kucken wie jedes Jahr hier ist 11 auf der Seite hier ist er auf der Seite um aber das selbe Spielchen wieder denn schon vielleicht so und den straffällig so zu Unterscheidung und was dabei jetzt herauskommt ist ein Offspring 1 und 1 auf in 2 tragen wir dieselben 2 Position ab L und ja und alles vor allen bleibt wie es ist als hinterher das war es falsch das müsste jetzt eigentlich andersrum seien so alles hinter er bleibt so wie es ist und das zwischen L und R inklusive wir zwischen beiden hin und her
getauscht die beiden sind ausgetauscht dritte Möglichkeit jährlich vom Crossover das ist eine etwas andere Strategie die man nicht so richtig gut für gut zeichnen kann denke ich aber die man gut das verbalisieren kann für jede einzelne Positionen dürfen wir also genau gesagt wir Werfen eine Münze die wird müsse es aber nicht um den Fifty-Fifty sondern die kann durchaus wieder Unterstützer unterschiedliche Wahrscheinlichkeiten haben und mit einer gewissen Wahrscheinlichkeit Wert wird werden die wird an dieser Position ausgetauscht zwischen den beiden Strings und mit einer mit entsprechender Restwahrscheinlichkeit bleiben die Werte so wie sie sind so wie es ist es ist die also der der 1. dash ist hier dass die Werte so bleiben wie sie sind 2. dash ist dass die Wärter zwischen beiden ausgetauscht werden das ist so schon mal die gängigen grundlegenden Strategien für für Kreisau war die immer wieder gerne Anwendung finden und die durchaus viel bringen jetzt aber das Problem dabei ja so abstrakt wie wir das ist eben auf dieser Folie gesehen haben habe ich das Problem was dahinter ist natürlich schön auch weg abstrahiert das Problem ist wenn wir so eine Strategie anwenden ob das dann was dann am Ende rauskommt immer noch eine zulässige Lösung ist ja es mir nicht gesagt ja wenn ich aus wenn ich will nicht alles was ich als dieses Drinks gut ihre ist eine zulässige Lösung so nur bestimmte davon unzulässige Lösung welches anfange da so Behinderung zu hantieren des Strings aus teils auszutauschen wer sagt denn dass diese Lösung dann dass das dann was Männer rauskommt dass zulässige Lösungen sind es natürlich witzlos wenn sie das nicht sind eine Möglichkeit die oft für verwendet wird ist was man sagt OK wir erlauben auch zu nicht zulässige Lösungen im Laufe des Algorithmus ja wir erlauben dass über wir erweitern sozusagen den Lösungsraum auf alle möglichen Strings die Vorkommen nicht nur auf die Strings die zulässige Lösung darstellen aber natürlich nicht ersatzlos denn Songs comma mit Sicherheit am Ende eine unzulässige Lösung raus wir bestrafen das das ist der er dass das was da was da es keine zulässige Lösung ist denken Sie beispielsweise als die SPD wenn wir jetzt anfangen beliebig wird zwischen wenigen und 2 Rundtouren näher und tauschen da irgendwelche kannten Informationen aus China die für bestimmte kannten tauschen mit Information aus einem 1 will und nicht drin das was dabei rauskommt alte zu aufzwingen sind die und dennoch und Touran kann gar nicht sein also sehr unwahrscheinlich dass das Für und Horn sind extrem Astronomen unwahrscheinlich das man aber dann sagt das sagt diese diese Strategie ok wir lassen das zu uns ist es wichtiger dass der Lösungsraum sehr einfach strukturiert ist damit wir sehr sehr schnell auf auf diesen Lösungsraum die Suche als sich ausbreiten lassen können ohne große ohne große Fisimatenten aber die E der Kosten der zu einer solchen zu lesen oder unzulässige Lösung ist nicht mehr einfach die Summe der Kantenlängen sondern die Summe der Kantenlängen plus ein straft Herrn der bestraft wie weit weg das was wir da in den Namen von einer Rundtour ist wie weit weg das von einer unter ist da kann man natürlich da kann man dann natürlich schauen wir sind kann man für versuchen als Maß beispielsweise her zunehmend wie viele Knoten gibt es die nicht genau eine reingeht und ich genau eine ausgehende kann da haben oder solche solche Sachen kann man versuchen als Strafe Therme zu definieren und sie sehen auch hier das ist auch wieder ein Beispiel Kodierung haben wenn sie das TSB kodieren es als Permutation und da dann haben Sie dieses Problem nicht mehr so in dieser verschärften Frauen und andere ist Beispiel hier ist machen den Ausflug dieses Problem Stellungnahme noch nicht in den Beispielen eingeführt ist aber auch eine sehr wichtige Problemstellung genau nehmen weil in dieses Beispiel ja was Sie haben stellen sich vor Sie haben ein großes Projekt zu organisieren ein richtig großes Projekt ein großes Bauprojekt oder so etwas dieses riesengroße Bauprojekt besteht natürlich aus vielen vielen vielen Einzel- Jobs Jobs ist die typische der typische Begriff dabei der englischen Literatur ja ich habe mir angewöhnt hier von vorne rein immer von Job zu sprechen jeder Versuch das was anderes zu seinen Aufgaben oder Teilprojekt oder sowas war hat nicht funktioniert ich habe dann doch am Ende von Jobs gesprochen so diese ganzen weiterhin unter waren PaaS Aufgaben Jobs das Jobs das hatten großes J als Abkürzung dies stehen natürlich in Beziehung zueinander ja bestimmt denken Sie an einem Bauprojekt Sie können die Wenders dann hochziehen wenn der Keller gebaut ist ja und Sie können es dann mit dem Dach Gebälk anfangen wenn die Wände hochgezogen sind sie können es dann mit den Fenstern anfallen wenn die wenn die wenn der eingesetzt und und so weiter und so fort dass Sie diese Pfeile hier in diesem Bildchen diese einzelnen Jobs sind die Knoten Fall besagt beispielsweise hier des Job des darf erst begonnen werden wenn er schon beendet ist dazwischen also vorher kann Job den ich anfangen wir haben jeweils eine geschätzte Dauer wie lange das dauern wird diese einzelnen Jobs denken Sie beispielsweise an Tage dass bei einem Bauprojekt das können das können typischerweise Tage sein wie das dauert bei einem Ablauf in einer Fabrik ganz vielleicht eher Stunden oder Minuten je nachdem wo es geht so dass es eine Mitwissens Konsquenz dass bestimmte Jobs erst dann starten können wenn andere fertig sind und dann kommt natürlich noch Ressorts Kunstschätze zu denen sie wieder an einem Bauprojekt Sie haben das sie haben 2 Kräne und Sie Sie haben 3 Aufgaben die mit Kreide dienen Kran benötigen Sie können nicht diese 3 Aufgaben zeitgleich machen so ein von den dreien müssen Sie einer von den dreien muss warten muss eingeplant wenn zum Zeitpunkt um mindestens einer von den anderen beiden fertig ist und dann den Kran zur Verfügung stellt so Sohn was wir minimieren wollen hier ist die gesamt dauert das heißt vom Beginn des 1. Laufs bis zum Ende des letzten Jobs Jahr vom 1. Spatenstich bis zur schlüsselfertigen Übergabe wenn man so will so war die sind endlich wer die Problemstellung sind auch hat in der Praxis schwer hier wäre hier wäre so ein Beispiel wie man sich etwa sowas vorstellen kann diese diese vor sie haben Sie haben 2 Kräne oder 2 sonstige Maschinen M 1 M 2 Maschinen Maschinen zu und Sie können dem Grafen er nehmen und man sieht wenn jeder von denen eine von den beiden Maschinen und die beiden Maschinen sind austauschbar erzeugt werden beispielsweise wenn ihn der von den eine Maschine braucht und ist es egal auf welche das ist dann wären das ja zu dass sie wären 2 zulässige Lösung zwar 2 recht gute natürlich packen Sie die Lösung so eng wie nur irgend möglich aber sie sehen es geht nicht über also eng Haar können Sie dieses Haar bei bei P 2 bei der zweiten Lösung beim zweiten älter können Sie nicht beliebig nach links direkt ans des anhängigen weil H noch auf E zu warten hat und es hier platziert also kein Haar frühestens 4 platziert sein sie können nicht einfach alles so weit nach links wie möglich platzieren ich habe ihn von Eltern im Singular gesprochen das mache ich öfter im Englischen ist es möglich per Hand im Singular zu verwenden im Deutschen eigentlich nicht aber in der Informatik hatte sich inzwischen eingebürgert tatsächlich von älter im Singular zu sprechen damit man jetzt nicht überlegen muss ist das jetzt Vater oder es ist jetzt Mutter dann kommt in alle möglichen der politischen Probleme reine mit älter hat man das Problem von Wohnungen eingelöst so
so das ist jetzt ein Beispiel für das was ich eben gesagt habe das wir auch unzulässige Lösungen zu lassen vielleicht nicht alle aber aber wenigstens gewisse nämlich dass wir die Ressourcen Bedingungen ignorieren also Tool ist ja was was heißt das sich oder einem das Leben einfacher machen wird auch hier gerne verwendet in der Informatik und der und ist am meisten und Leben zu verstehen mit die er das dass diese Ressourcen Bedingungen also entweder abschwächen Eröffnung einer Art und Weise dass wir sagen wir tun so als ob wir noch eine Maschine mehr hätten dann muss das Leben einfacher oder sogar ganz ignorieren aber nicht aber nicht ohne Ersatz denn wir bestrafen jetzt wenn jetzt Lösungen so wie hier das 1 soll zulässige
Lösungen werden 2 Maschinen und sämtliche Jobs sind auf den beiden Maschinen platziert wenn wir sagen wir lassen diese Bedingung fallen dass das dass wir nur 2 Maschinen haben dass alle Jobs auf diesen 2 Maschinen sind wenn du sie uns gar nicht wir unser einmal wir gehen davon aus dass sie unendlich viele Maschinen haben ja dann haben wir
diese Sauce kommst wenn es diese diese die Bedingung dass die dass wir nicht mehr Maschinen verwenden als wir haben die haben wir dann ihnen ignoriert aber wir bestrafen es eine Lösung mehr als 2 Maschinen braucht zum Beispiel indem sie einfach zählen wie viel höher Cloud auf den nicht existierenden zusätzliche Maschinen ist das kann dass sie eine sinnvolle Bestrafung so aber die die Reihenfolge Beziehungen die die lassen wir so wie sie sind und was wir jetzt als Repräsentierung sinnvollerweise hernehmen ist dass jeder Job eine zwar hat die aber erklärungsbedürftig ist diese wäre zwar hat eine Bedeutung wenn sich hier diesen dieses Bild diese Formel ansehen für jeder für jede Reihenfolge Beziehung führt Kunst das haben wir hier irgendwo mit
es ausgedrückt diese Reihenfolge Beziehung dass dieser Job J starten darf wenn i zu Ende ist was bedeutet dass es zu Ende Startzeit von E Plus dorvon von es vergangen erst dann darf Startzeit von J sein oder natürlich später muss nicht sofort sein und was wir
jetzt hier haben ist DJ ist der früheste Zeitpunkt wo es starten darf aufgrund dieser Beziehung früher darf ihn nicht starten
Loading...
Feedback
hidden