Verschiedene Geräte sollen jeweils eine bestimmte Anzahl an Prozessen durchführen, wobei jeder Prozess aus einer Leistungsbezug-Zeitreihe besteht. Für die Durchführung der Prozesse steht ein bestimmter Zeitraum zu Verfügung in welchem sie sich verschieben lassen, allerdings sollen die Prozesse immer in der selben Reihenfolge durchgeführt werden.
Die zu optimierende Zeitreihe x ist die Summe aller Leistungsbezug-Zeitreihen und soll so optimiert werden, dass ein bestimmtes Leistungs-Maxima (wenn möglich) nicht überschritten wird bzw. die Maxima und die Zeitdauer der Maxima möglichst gering gehalten werden.
Die Prozesse habe ich für jedes Gerät in Cell-Matrizen abgespeichert.
Einfaches Beispiel:
ProzesseGerät1 = {A1,B1,C1}
ProzesseGerät1 = {A2 ,B2}
Prozessdauer jeweils 1 Minute.
Leistungsbezug immer 1kW außer bei C1 3kW.
Zeitraum: 4 Minuten
Optimal wäre dann wenn beide Geräte möglichst kurz gleichzeitig arbeiten und während Prozess C1 nur Gerät 1 arbeitet etc...
Welches Optimierungstool eignet sich für dieses Problem?
Ich kenne bisher nur cplex bzw.
cplexlp
, damit kann ich upper Bounds setzen (z.B. 3kW), aber diese Grenze ist dann nicht sehr dynamisch. Außerdem weiß ich auch nicht wie ich diese feste Prozessreihenfolge in Gleichungen definieren soll.
wenn die Funktion nicht linear ist, bleibt für ganzzahlige Optimierung eigentlich nur
ga
. Wie groß ist i? Falls nicht allzu groß, kann auch Testen aller Kombinationen eine Option sein.
Grüße,
Harald
_________________
1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
i wird sehr groß werden, das ist der Nachteil dieser Methode. Ich werde versuchen i soweit möglich zu begrenzen, aber das Problem ist dass ich hier mit Sekunden-Werten rechne und mal mit 10-Sekunden-Verschiebungen anfange. Auch wenn ich dass dann in einzel-Optimierungen für 15-Minuten-Abschnitte aufteile, komme ich für i immer in den 5-stelligen Bereich...
So ist das wohl noch nicht lauffähig. Was fehlt denn noch? (die Variablen, bzw. Matrizen PP, b, Aeq etc. sind alle weiter oben definiert).
Bin mich gerade erst am einlesen in genetic algorithm...kann da jemand was empfehlen, wo ich nachlesen kann wie ich das mit ga() in Matlab implementiere?
1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Allerdings ignoriert er bei der Optimierung komplett meine Nebenbedingungen, scheinbar kann ich bei binärer Optimierung keine NBs mit Equations oder Iniquations setzen: "Warning: All constraints are ignored for 'bitString' population; bound constraints are set to [0 1]."
Ich habe meinen NBs nun aber alle so formuliert...
Einfaches Beispiel:
Ich will dass jeweils die ersten und letzten drei Zeilen (n = 6) von
x
summiert 1 ergeben.
Aeq = [1,1,1,0,0,0; 0,0,0,1,1,1]
beq = [1; 1]
Aeq * x = beq
Wie kann ich das nun mit einer Constraint-Funktion lösen?
Also sowas:
ga does not enforce nonlinear constraints to be satisfied when the PopulationType option is set to 'bitString' or 'custom'.
Ich sehe höchstens die Möglichkeit, das als ein Paar von Ungleichungen zu repräsentieren, also
A*x <= b und
-A*x <= -b
Ob das gut klappen wird, ist die andere Frage...
Grüße,
Harald
_________________
1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
dazu ist x binär und ich will eine Reihe von Nebenbedingungen in Form von Equations und Inequations formulieren.
Hintergrund: A*x ist eine Leistungskurve über den Tag. sum(A*x) entsprechend die Energiemenge für einen Tag, die immer gleich bleibt. Ich will nun die Energiemenge miminieren für die Leistungswerte A*x > b.
ga (genetic algorithm) habe ich bereits versucht. Hier kann ich zwar schön die Minimierungsfunktion formulieren mit der Fitness-Funktion, aber es ist nicht möglich Nebenbedingungen zu formulieren wenn x binär ist.
Auch der Trick dass ich x auf Integer setze mit Grenzen 0 und 1 verursacht Fehler bei den NBs.
Die Frage ist also ob es noch einen anderen Solver gibt der dieses Problem lösen kann?
Evlt. kann ich meine Funktion f(x) bzw. die Beträge mit einem mathematischen Kniff und Fallunterscheidungen als Nebenbedingungen doch zu einer linearen Funktion machen? Ist mir aber och nichts eingefallen...
Als zweites (unabhängig vom ersten Problem) würde ich dann noch gerne
f(x) = max(A * x)
minimieren. x wiederum binär und mit den gleichen NBs wie davor.
Hintergrund: Ich will die Leistungsspitze im betrachteten Zeitraum minimieren.
Ich kenne bisher außer ga nur cplex, damit kann ich zwar binär mit NBs optimieren, aber nur in der Form c*x (cplexbilp) oder (C*x-d)^2 (cplexlsqbilp) oder Ähnliches minimieren...keine Beträge oder max() in der Minimierungsfunktion.
When there are integer constraints, ga does not accept linear or nonlinear equality constraints, only inequality constraints.
Das würde ich so verstehen, dass inequality constraints schon unterstützt werden. Ein reproduzierbares Beispiel wäre hilfreich.
Grüße,
Harald
_________________
1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Ja, wenn ich statt binär auf IntCon setze (mit Grenze 0,1 - also wieder binär), sind Inequations erlaubt.
Ich habe dann deinen Trick angewandt mit Aeq * x <= 1 & -Aeq * x <= -1 ...
wenn mein Problem einfach bleibt klappt das, aber sobald die Matrizen etwas größer werden kann er diese Constraints nicht mehr einhalten.
Nicht mal annähernd...und für mein Problem muss er das strikt einhalten.
Dann kommt:
Zitat:
Optimization terminated: average change in the penalty fitness value less than options.FunctionTolerance
but constraints are not satisfied.
Weiß nicht ob man da mit sonstigen Einstellungen der Parameter in ga was erreichen kann?
Aber letztlich gehen Equations wohl aus gutem Grund nicht und dann klappt eben dieser Trick mit umwandeln in Inequations auch schlecht.
Ich hänge mal meine Files an mit zwei Beispielen.
In beiden Fällen habe ich zwei Geräte. Gerät1 soll zwei Prozesse ausführen, Gerät2 soll drei Prozesse ausführen. Also insgesamt fünf Prozesse.
Der Zeitraum sind n Sekunden. Nun sollen die Prozesse zu unterschiedlichen Zeiträumen ausgeführt werden können bzw. der optimale Zeitraum ausgewählt werden. Dies wird in der Matrix "PP" gespeichert.
Die Matrix "PP" hat n Zeilen und speichert in jeder Spalte einen möglichen Zeitraum für einen Prozess. Prozess 1 kann beispielsweise in einem von 10 verschiedenen Zeiträumen ausgeführt werden, also gehören Spalte 1 bis 10 zu Prozess 1, dann folgt Prozess2.
Schau dir PP an, dann verstehst du schnell.
x soll nun wählen welcher Zeitraum von den 10 möglichen bei Prozess1 ausgeführt wird. Also darf von den ersten 10 Zahlen von x nur EINE 1 betragen, alle anderen 0. Dasselbe für Prozess2,3,4,...
Das ist die erste Nebenbedingung die in "Aineq" & "bineq" gespeichert ist. Je eine Zeile pro Prozess, und nochmal je eine Zeile mit -1.
Danach folgt die Nebenbedingung dass Prozess 2 nicht vor Prozess 1 ausgeführt werden darf und auch nicht gleichzeitig da sie beide zu Gerät1 gehören. Dasselbe für Prozess3 bis 5 von Gerät2.
Hier habe ich in den NBs einfach alle möglichen falschen Auswahlen ausgeschlossen.
Letztlich soll der Zeitraum 15*60 Sekunden betragen und es werden 20 bis 50 Geräte mit insgesamt bis zu 500 Prozessen.
fitness.m
Beschreibung:
Fitness-Funktion: sum(((PP * x - b) + abs(PP * x - b)) * punish)
Das gleiche sollte sich auf größere Probleme übertragen lassen, sofern die Struktur gleich ist.
Vorteil: die NB sind erledigt, die Dimension des Problems reduziert sich.
Grüße,
Harald
_________________
1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
In deinem Beispiel ist dann u die zu optimierende Entscheidungsvariable?
Für die NB dass jeder Prozess nur einmal ausgewählt wird, klappt das super. Bzw. die fällt dann eben weg.
Aber kann ich damit auch meine zweite Nebenbedingung formulieren? Dass Prozesse nicht gleichzeitig stattfinden und die Reihenfolge eingehalten wird.
Binär habe ich das bisher so formuliert, dass ich alle "falschen" Auswahlen ausschließe.
3 Zeitschritte und 2 Prozesse angenommen:
nicht gleichzeitig:
Aineq = [1,0,0,1,0,0;0,1,0,0,1,0;0,0,1,0,0,1]
Reihenfolge einhalten (Prozess2 NICHT vor Prozess1):
Aineq = [0,1,0,1,0,0; 0,0,1,1,0,0;0,0,1,0,1,0]
und beides eben mit bineq = [1;1;1]
Aineq * x <= bineq
Kann ich das auch mit u formulieren?
Das sind dann ja quasi Bedingungen:
if u(1) == 1
u(2) ~= 4
if u(1) == 2
u(2) ~= 4&5
if u(1) == 3
u(2) ~= 4&5&6
oder auch
if u(1) == 1
u(2) = 5|6
if u(1) ==2
u(2) = 6
...
bei meinem Kurz-Beispiel sind u(2)=4 sowie u(1)=3 natürlich überflüssig . Aber am Ende habe ich dann ja viel mehr Zeitschritte, wo es diese Bedingungen zu beachten gilt...
eine Möglichkeit kann auch sein:
wenn Nebenbedingungen nicht erfüllt sind, die Zielfunktion erhöhen, quasi als Strafe. Dann fallen Lösungen, die die NB verletzen, letztlich weg.
Grüße,
Harald
_________________
1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
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