Ziel ist es die Werte innerhalb einer Reihe derart zu vertauschen, dass man am Ende eine Matrix erhält, in der die größte Spaltensumme, die auftritt, möglichst klein ist.
Das ganze würde ich gerne mit Matlab umsetzen.
Ich habe mich bereits ein wenig in Suchalgorithmen und Genetische Algorithmen eingelesen. Allerdings kann ich die Begrifflichkeiten "Knoten" und "Kanten", die bei der Erklärung der Algorithmen verwendet werden, noch nicht so richtig auf mein Problem übertragen.
Hätte jemand eine Idee für einen Lösungsansatz?
Ich würde mich sehr über Vorschläge freuen!
Vorab schonmal vielen Dank.
Ist es so, dass in einer Zeile immer nur Nullen und ein von Null verschiedener Wert stehen? (in deinem Beispiel ist das ja so)
Gibt es andere/weitere systematische Strukturen in der Matrix, die man ausnützen könnte?
Dann könntest du das als binäres Optimierungsproblem auffassen.
Grüße,
Harald
Thorsten82
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 30.12.2013, 16:21
Titel:
Hallo Harald,
genau du hast es richtig erfasst.
In einer Zeile stehen immer nur Nullen und ein von Null verschieder Wert.
In jeder Zeile kann es ein anderer Wert sein, der von Null verschieden ist.
Und die Anzahl an Nullen in einer Zeile kann sich auch in jeder Zeile unterscheiden.
Ansonsten gibt es keine weiteren systematischen Strukturen.
ich würde es mal mit ga probieren.
Dir muss aber klar sein: du hast im Grunde genommen 1500 Variablen, an denen man drehen kann. Da wirst du i.d.R. kein sinnvolles Resultat innerhalb von Sekunden erwarten können.
Grüße,
Harald
Thorsten82
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 30.12.2013, 21:14
Titel:
Danke für die Hinweise, Harald!
Vor allem der Tipp, das als binäres Optimierungsproblem zu betrachten, hat mich weiter gebracht.
Ich habe nun als Zielfunktion (beim ga entspricht dies der Fitnessfunktion?) bestimmt:
g = max( a, b, c, d, ...) wobei a, b, c, d, ... der Summe der 1., 2., 3., 4., ... Spalte entspricht.
Diese Zielfunktion gilt es zu minimieren.
Pro Zeile, die die Matrix hat, hat man noch eine Nebenbedingung.
In der Nebenbedingung wird festgehalten, wieviele von Null verschiedene Werte in der jeweiligen Zeile sein müssen.
Ich werde mal versuchen, es so mit dem ga umzusetzen.
Gruß
Thorsten
Thorsten82
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 01.01.2014, 19:23
Titel:
Hallo und frohes neues Jahr,
ich habe den ga mal für folgende "einfache" Matrix angesetzt:
Mit folgenden zusätzlichen Einstellungen:
Population size = 50
Generations und Stall generations = 1000
Nach mehreren Durchgängen musste ich feststellen, dass nicht immer eine optimale Lösung gefunden wird.
Muss ich die Generationen vielleicht noch weiter Erhöhen?
Gibt es vielleicht noch andere Einstellungen, die ich für dieses Problem anpassen müsste?
"Creation function" und "Crossover" lassen sich bei Integer Variablen ja nicht verändern.
Wie ich der Doku entnehmen konnte, kommt, alternativ zum ga, für ein binäres Optimierungsproblem nur noch bintprog in Frage, wo allerdings die Funktion linear sein muss.
Oder habe ich was übersehen und es gibt doch einen alternativen solver?
das ist eine Eigenheit der Evolution, dass nicht immer das Optimum herauskommt.
Meistens hilft es eher, PopulationSize zu erhöhen (nimm ruhig 500) anstatt die Anzahl der Generationen.
Zudem könnte man mit custom mutation / crossover functions arbeiten. Das Problem an Evolutionen ist, dass sie auch in die falsche Richtung laufen können. Oft kann man da etwas nachhelfen.
bintprog ist generell eine Alternative, wird hier aber nicht helfen, weil die Zielfunktion eben nicht linear ist.
Wenn du deinen bisherigen Code postest, kann ich mir das gerne mal genauer ansehen.
Vorschläge:
1. Das Ausschreiben der Funktion dürfte bei größeren Matrizen mühsam sein. Ich würde daher versuchen, mit Matrix-Operationen zu arbeiten (z.B. jede Zeile konstant und dann Multiplikation mit einer 0-1 - Matrix, um die momentane Matrix zu erhalten).
2. Als Creation Function: zufällige Anordnungen der 1en innerhalb jeder Zeile
3. Als Mutation Function: ein Paar von Einträgen wird vertauscht (alternativ mehrere Paare). Führt das zu einem besseren Ergebnis, wird dies übernommen. Aber auch wenn das Ergebnis schlechter wird, wird es mit einer gewissen Wahrscheinlichkeit übernommen - die Evolution nimmt ja auch nicht unbedingt den geraden Weg.
4. Als Crossover Function: die Zeilenbelegung der Elternpaare wird zufällig übernommen. Alternativ kann man nach Auswahl einer gewissen Zeilenzahl auch schauen, welche Möglichkeit besser wäre.
Durch 2.-4. braucht man dann gar keine Nebenbedingungen mehr, da sie ja implizit berücksichtigt werden.
Grüße,
Harald
Thorsten82
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 02.01.2014, 23:47
Titel:
Danke für die Vorschläge.
Ich habe versucht sie so umzusetzen.
Für eine Matrix der Größe 3 x 15 scheint dies auch noch halbwegs zuverlässig zu funktionieren.
Bei einer Größe von 3 x 20 dann aber schon nicht mehr. Auch wenn man mit der Population size auf bis zu 1000 und Generations = 100 geht.
Dabei habe ich 3 Varianten als Mutation Function probiert:
1. Dein Vorschlag, ein Paar zu vertauschen
2. Dein alternativer Vorschlag, mehrere Paare zu vertauschen. Dabei wird geprüft wieviele Nullen oder Einsen in einer Zeile sind. Je nach Anzahl wird ein zufällige Anzahl von Paaren vertauscht.
3. In jeder Zeile eine Zufallszahl bilden, anhand der man die Zeile mit circshift rotiert.
Als Crossover Function:
In jeder Zeile wird zufällig entschieden, welchem Elternteil die Zeile übernommen wird.
Zitat:
Alternativ kann man nach Auswahl einer gewissen Zeilenzahl auch schauen, welche Möglichkeit besser wäre.
Kannst du deinen alternativen Vorschlag nochmal erläutern?
Meinst du man kombiniert die Zeilen von zwei Eltern auf verschiedene Weisen, und überprüft welche Möglichkeit eine Verbesserung bringt?
Meinst du man kombiniert die Zeilen von zwei Eltern auf verschiedene Weisen, und überprüft welche Möglichkeit eine Verbesserung bringt?
Z.B. so:
wenn man drei Zeilen hat, wählt man die ersten beiden zufällig aus den Elternpaaren aus und als dritte Zeile dann die, die das bessere Ergebnis bringt.
Grüße,
Harald
Thorsten82
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 05.01.2014, 02:56
Titel:
Hallo,
es scheint jetzt ganz gut zu funktionieren.
Ich möchte nun an mehreren kleineren Matrizen testen, ob der ga auch wirklich das Optimum findet. Hierfür würde ich gerne vorher das Optimum mittels "brute force"-Methode bestimmen.
Ich habe bis jetzt nur den Befehl perms gefunden, um alle Permutationen einer Zeile sofort zu erhalten, wobei man dann ab der Länge 10 Probleme bekommt.
Mit Hilfe des Steinhaus-Johnson-Trotter-Algorithmus habe ich eine Funktion geschrieben, um die Permutationen einer Zeile einzeln zu erhalten.
Nun fehlen mir allerdings noch die Kombinationen der Zeilen zueinander.
Gibt es in Matlab eine Funktion, um systematisch die Permutationen der Zeilen sowie jede mögliche Kombination zu einander zu erhalten?
Oder muss man dies irgendwie über verschachtelte For-Schleifen realisieren?
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
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.
RSS