|
|
|
Global Optimization Toolbox: Genetische Algorithmen |
|
| bumbumquietsch* |
Forum-Fortgeschrittener
|
 |
Beiträge: 55
|
|
|
|
Anmeldedatum: 17.10.11
|
|
|
|
Wohnort: München
|
|
|
|
Version: R2011b
|
|
|
|
 |
|
Verfasst am: 08.02.2012, 08:31
Titel: Global Optimization Toolbox: Genetische Algorithmen
|
 |
| |
 |
 |
Hey Leute,
und zwar habe ich mit Hilfe der Matlab "Global Optimization" Toolbox und den genetischen Algorithmen ein Programm geschrieben, welches mein Optimierungsproblem löst. Dabei habe ich mir stark an der "Custom Data Optimization" mit Beispiel des Traveling Salesman orientiert:
http://www.mathworks.de/products/gl.....veling_salesman_demo.html
Mein Programm funktioniert sehr gut und stabil, es können zahlreiche Iterationen durchgeführt werden, das Ergebnis wird mit zunehmner Iteration immer besser und die Ergebnisse sind auch plausibel und nachvollziehbar. Allerdings ist dieser Algorithmus noch nicht optimal. Ich habe vieles aus diesem Custom Data Algorithmus genommen und denke, dass die Werte dort stark an den Travel Salesman angepasst sind.
Der Algorithmus kann durch Anpassung von speziellen Werten nun verbesser werden (http://www.mathworks.de/help/toolbox/gads/f6691.html#brbuk6o) Dazu zählen:
Anzahl der Generationen = Wie viele Iterationen werden durchlaufen
Population = Wie viele Grundvektoren werden zur verfügung gestellt
Mutation, Crossover, Migration Options etc. sowie Elite Count usw.
Kann mir jemand hier vielleicht ein paar Tipps geben, wie dise Werte entsprechend angepasst werden müssen ? Bzw. welche Auswirkung hat welche veränderung eines Wertes ? Z.b. die InitialPopulationn. Ich dachte immer diese muss entsprechend der Länge des Vektors sein der optimiert wird, jedoch brachte mir eine Vergrößerung dieses Wertes auch eine viel bessere Optimierung.
Da ich nicht willkürlich irgendwelche Werte verändern will und mir jemand sagen könnte, auf welche Werte ich achten muss so wäre mir schon sehr geholfen 
Danke für eure Antworten!
|
|
|
|
|
|
| Harald |
Forum-Meister
|
|
Beiträge: 24.495
|
|
|
|
Anmeldedatum: 26.03.09
|
|
|
|
Wohnort: Nähe München
|
|
|
|
Version: ab 2017b
|
|
|
|
|
|
|
Verfasst am: 08.02.2012, 09:28
Titel:
|
|
Hallo,
ich halte es für sehr schwierig, pauschale Ratschläge zu geben. Die Anpassungen sollten anhand des konkreten Problems bzw. des Verlaufs der Optimierung gemacht werden. Eine ausführliche Beschreibung findet man unter
bzw. dort verlinkt.
Falls es sich um ein kontinuierliches Problem handelt, sollte eine 'HybridFcn' zur weiteren Optimierung der Lösung verwendet werden.
Um Performance zu verbessern, kann die Fitness Function vektorisiert werden und das bei der Option 'Vectorized' angegeben werden.
Die 'Initialpopulation' ist eine Matrix aus Individuen, mit denen der GA gestartet wird. Sie kann bis zu 'PopulationSize' viele Individuen enthalten; wenn sie weniger enthält, wird sie über CreateFcn aufgefüllt.
Grüße,
Harald
|
|
|
|
| bumbumquietsch* |
Themenstarter
Forum-Fortgeschrittener
|
|
Beiträge: 55
|
|
|
|
Anmeldedatum: 17.10.11
|
|
|
|
Wohnort: München
|
|
|
|
Version: R2011b
|
|
|
|
|
|
|
Verfasst am: 08.02.2012, 11:44
Titel:
|
|
Hey Harald,
danke für die schnelle Antwort!
Die dokumentation habe ich mir schon mehrmals durchgelesen. Mir ging es um die Tatsache, was einer Veränderung des jeweiligen Wertes bewirkt.
Z.b. die "InitialPopulation": Du hast sehr gut erklärt wie diese aufgebaut ist, aber was bewirkt nun eine zu große InitialPopulation und eine zu kleine ? Also quasi wie wirkt sich meine InitialPopulation Größe auf den Algorithmus aus.
Die Fitness Function ist bei mir Vectorized, von der HybridFcN hab ich leider noch nichts gehört, was macht diese genau ?
Gibt es zu diesem Thema auch irgendwo eine deutsche Anleitung mit der Erklärung der einzelnen Werte ? Was mich auch beschäftigt sind
- Seleciton Options
- Mutation Options
- Crossover Options
wäre cool wenn du mir da noch etwas auf die Sprünge helfne könntest, zur Zeit veränder ich die Werte eher willkürlich ^^
|
|
|
|
| Harald |
Forum-Meister
|
|
Beiträge: 24.495
|
|
|
|
Anmeldedatum: 26.03.09
|
|
|
|
Wohnort: Nähe München
|
|
|
|
Version: ab 2017b
|
|
|
|
|
|
|
Verfasst am: 08.02.2012, 12:53
Titel:
|
|
| |
|
|
Hallo,
Thema InitialPopulation: es gibt kein "zu groß" oder "zu klein". Wenn du als Ausgangspunkt "ganz gute" und am besten noch dabei recht unterschiedliche Individuen hast, dann solltest du sie auf jeden Fall in der InitialPopulation angeben. Ich würde mir aber keine Individuen "zufällig ausdenken". Da sollte stattdessen die entsprechende Vorgehensweise in der CreateFcn implementiert werden.
Wenn die Fitness Function vektorisiert ist, dann ist es wichtig, die Option 'Vectorize' auch auf 'on' zu stellen, da sonst eine for-Schleife über die Individuen verwendet wird.
Thema HybridFcn (macht nur bei kontinuierlichen Problemen Sinn): GA hat unterschiedliche Einsatzgebiete, u.a. globale Optimierung als Alternative zu Algorithmen in der Optimization Toolbox. Das Problem bei letzteren ist, dass sie nur lokale Minima finden. Das Problem bei GA ist, dass er sehr langsam konvergiert und ziemlich sicher nicht mal ein lokales Minimum findet. Allerdings ist das Endergebnis von GA ein sehr guter Startwert für einen Algorithmus aus der Optimization Toolbox wie z.B. fmincon, der dann für das Feintuning verwendet werden kann.
Von einer deutschsprachigen Erklärung ist mir nichts bekannt. Die eine oder andere Frage habe ich hier im Forum schon beantwortet.
Die besten Möglichkeiten, den GA zu beeinflussen, liegen für mich darin, eigene CrossoverFcn und MutationFcn zu schreiben, die aus den Eltern "tendentiell gute" Kinder erzeugen. Das erfordert aber etwas Aufwand und genaue Kenntnisse über die Struktur des Problems.
Um dir wirklich weiterhelfen zu können, müsste man mehr über die Struktur des Problems und den typischen Verlauf einer Optimierung wissen.
Liefern mehrere Durchläufe deines Programms ähnliche Ergebnisse?
Grüße,
Harald
|
|
|
|
| bumbumquietsch* |
Themenstarter
Forum-Fortgeschrittener
|
|
Beiträge: 55
|
|
|
|
Anmeldedatum: 17.10.11
|
|
|
|
Wohnort: München
|
|
|
|
Version: R2011b
|
|
|
|
|
|
|
Verfasst am: 08.02.2012, 13:43
Titel:
|
|
| |
|
|
Okay das bringt mich schonmal etwas weiter 
Ich studiere gerade ausgiebig die Dokumentation der Options für den GA.
Mein Problem entspricht exakt dem Problem des Traveling Salesman was ich oben angegeben habe. Ich habe die komplette Syntax übernommen und meine eigene "distance-Matrix" = Kostenmatrix sowie meinen eigenen Vektor mit "Städten" integriert.
Der Algorithmus läuft stabil und die Ergebnisse sind bei gleichbleibender Generationsanzahl sowie gleicher Population sehr ähnlich. Ich habe eine Reihe von Tests ausgeführt bei denen ich Generationsanzahl erhöht haben --> Der Gütewert meines Vektors wird immer besser, die Zeit vergrößert sich. Dasselbe Spielchen habe ich auch nochmals mit der Population gemacht und auch hier eine Verbesserung der Werte festgestellt.
Worum geht es mir jetzt noch genau?
Die Länge meines "Städte"-Vektors variiert von 30- 300. Ich würde hier gerne für einen entsprechenden Wertebereich eine passende Population wählen. Bis jetzt habe ich die Populationsgröße doppelt so groß wie die Länge meines "Städte" Vektors gewählt. Die Anzahl der Iterationen entspricht einer willkürlichen großen Zahl (100.000 - 1.000.000).
- InitialPopulationen: Auch hier habe ich immer die Länge des Vektors genommen, was könnte man besser machen ?
- Crossover und Mutation sind nach der Funktion des Traveling Salesman Problems (wie oben) implementiert. Kann ich hier noch etwas an den Options machen ?
.- Hybrid Function: Was wäre ein guter Ansatz für den Traveling Salesman ?
Also wie gesagt, als Beispiel kannst du den Custom Algorithm den ich oben reingestellt habe verwenden, mein Programm ist exakt so aufgebaut. Vielleicht kannst du mir anhand dieses Algorithmus ein paar Verbesserungsvorschläge geben!
|
|
|
|
| bumbumquietsch* |
Themenstarter
Forum-Fortgeschrittener
|
|
Beiträge: 55
|
|
|
|
Anmeldedatum: 17.10.11
|
|
|
|
Wohnort: München
|
|
|
|
Version: R2011b
|
|
|
|
|
|
|
Verfasst am: 08.02.2012, 14:19
Titel:
|
|
|
Achja: Was genau macht das FitnessScaling und wie kann ich es integrieren ? Bzw. was bringt mir das Fitness Scaling ?
|
|
|
|
| Harald |
Forum-Meister
|
|
Beiträge: 24.495
|
|
|
|
Anmeldedatum: 26.03.09
|
|
|
|
Wohnort: Nähe München
|
|
|
|
Version: ab 2017b
|
|
|
|
|
|
|
Verfasst am: 08.02.2012, 15:07
Titel:
|
|
Hallo,
mir war nicht klar, dass dein Problem dem Traveling Salesman so stark ähnelt. Dann habe ich keine Verbesserungsvorschläge - die Leute, die die Demo geschrieben haben, kennen sich bei den Möglichkeiten wohl deutlich besser aus als ich
Ich sehe keinen Sinn darin, explizit eine InitialPopulation anzugeben. Ich würde das über createPermutations erzeugen lassen.
Crossover und Mutation so lassen, wie sie sind, außer du hast eine gute Idee zur Verbesserung.
Hybrid: hier nicht anwendbar.
Fitness Scaling: dazu kann ich dir auch nicht mehr sagen, als in der Doku steht.
Grüße,
Harald
|
|
|
|
|
|
|
Einstellungen und Berechtigungen
|
|
Du kannst Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
Du kannst Dateien in diesem Forum posten
Du kannst Dateien in diesem Forum herunterladen
|
|
Impressum
| Nutzungsbedingungen
| Datenschutz
| FAQ
|  RSS
Hosted by:
Copyright © 2007 - 2024
goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
|
|
