Mein MATLAB Forum - goMatlab.de

Mein MATLAB Forum

 
Gast > Registrieren       Autologin?   
Bücher:

Fachkräfte:
weitere Angebote

Partner:


Vermarktungspartner


Forum
      Option
[Erweitert]
  • Diese Seite per Mail weiterempfehlen
     


Gehe zu:  
Neues Thema eröffnen Neue Antwort erstellen

Optimierungsproblem: Prozessverschiebung

 

Yeti11
Forum-Anfänger

Forum-Anfänger


Beiträge: 14
Anmeldedatum: 17.04.19
Wohnort: ---
Version: 2018b
     Beitrag Verfasst am: 29.04.2019, 14:30     Titel: Optimierungsproblem: Prozessverschiebung
  Antworten mit Zitat      
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.
Private Nachricht senden Benutzer-Profile anzeigen


Yeti11
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 14
Anmeldedatum: 17.04.19
Wohnort: ---
Version: 2018b
     Beitrag Verfasst am: 01.05.2019, 10:50     Titel:
  Antworten mit Zitat      
Ich hab mein Problem jetzt mal mathematisch genauer formuliert:

Die zu optimierende Entscheidungsvariable x soll binär sein und bestimmten Nebenbedingungen unterliegen.

Die Funktion f(x) soll für n Zeitschritte minimiert werden:

f(x) = 1/2 * (g(x) - |g(x)|)

mit g(x) = A * x - b , wobei A mit der Dimension [n x i] , x mit [i x 1] und b mit [n x 1]

Wie formuliere ich diese Optimierung am besten in Matlab? Mit welchem Tool/ Solver?
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 19.929
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2014a
     Beitrag Verfasst am: 01.05.2019, 12:06     Titel:
  Antworten mit Zitat      
Hallo,

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 ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Yeti11
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 14
Anmeldedatum: 17.04.19
Wohnort: ---
Version: 2018b
     Beitrag Verfasst am: 02.05.2019, 12:22     Titel:
  Antworten mit Zitat      
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...
Private Nachricht senden Benutzer-Profile anzeigen
 
Yeti11
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 14
Anmeldedatum: 17.04.19
Wohnort: ---
Version: 2018b
     Beitrag Verfasst am: 07.05.2019, 13:17     Titel:
  Antworten mit Zitat      
Ich versuche es jetzt mit ga.

So sieht mein Code bisher aus:

Code:

        options = gaoptimset;
        options = gaoptimset(options, 'PopulationType','bitstring');
 
        [x,fval,exitflag] = ga(@fitness, dimension_pp, Aineq, bineq, Aeq, beq, [], [], [], options);

       
        function f = fitness(x,PP,b,punish)
            f = sum(0.5 * ((PP * x - b) + abs(PP * x - b))*punish);
        end


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?

Bin mich gerade erst am einle
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 19.929
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2014a
     Beitrag Verfasst am: 07.05.2019, 13:23     Titel:
  Antworten mit Zitat      
Hallo,

auf den ersten Blick sehe ich, dass die Schnittstelle der Funktion nicht passt. Abhilfe siehe hier:
https://www.mathworks.com/help/opti.....ing-extra-parameters.html

Mein bevorzugter Weg: anonymous functions.

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 ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Yeti11
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 14
Anmeldedatum: 17.04.19
Wohnort: ---
Version: 2018b
     Beitrag Verfasst am: 08.05.2019, 11:24     Titel:
  Antworten mit Zitat      
Danke, so funktionierts:

Code:
opts = optimoptions(@ga, 'PopulationType','bitstring','PopulationSize',50,'MaxGenerations',150,'MaxStallGenerations',100);
       
[x,fval,exitflag,output,population,scores] = ga(@(x)fitness(x,PP,b,punish), dimension_pp, Aineq, bineq, Aeq, beq, [], [], [], opts);


Code:
function f = fitness(x,PP,b,punish)
    f = 0;
    for p = 1:size(PP,2)
        f = sum(0.5 * ((PP(:,p) * x(p) - b) + abs(PP(:,p) * x(p) - b))*punish)+f;
    end
end



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:
Code:
function [c, ceq] = simple_constraint(x)


Constraints-Funktionen scheint er bei der binären Optiierung zu akzeptieren
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 19.929
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2014a
     Beitrag Verfasst am: 08.05.2019, 18:00     Titel:
  Antworten mit Zitat      
Hallo,

aus der Doku:
Zitat:
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 ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Yeti11
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 14
Anmeldedatum: 17.04.19
Wohnort: ---
Version: 2018b
     Beitrag Verfasst am: 09.05.2019, 10:27     Titel:
  Antworten mit Zitat      
Sobald ich Equations oder Inequations miteingebe, kommt die Warnung dass constraints ignoriert werden. Also gehts auch mit Aineq nicht...

Gibt es keine Möglichkeit in Matlab binär zu Optimieren (also Entscheidungsvariable x binär) und Nebenbedingungen zu setzen?
Private Nachricht senden Benutzer-Profile anzeigen
 
Yeti11
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 14
Anmeldedatum: 17.04.19
Wohnort: ---
Version: 2018b
     Beitrag Verfasst am: 09.05.2019, 16:03     Titel:
  Antworten mit Zitat      
Ich fasse mein Problem nochmal zusammen, wäre wirklich super wenn mir noch jemand helfen könnte.

Ich will folgende Funktion minimieren:

f(x) = sum((A * x - b) + abs(A * x - b)) * c)

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.
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 19.929
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2014a
     Beitrag Verfasst am: 09.05.2019, 20:45     Titel:
  Antworten mit Zitat      
Hallo,

aus der Doku:
Zitat:
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 ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Yeti11
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 14
Anmeldedatum: 17.04.19
Wohnort: ---
Version: 2018b
     Beitrag Verfasst am: 10.05.2019, 13:27     Titel:
  Antworten mit Zitat      
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)

Download
 Dateiname:  fitness.m
 Dateigröße:  168 Bytes
 Heruntergeladen:  1 mal
OptimizationGA.m
 Beschreibung:
Auszuführende Skript

Download
 Dateiname:  OptimizationGA.m
 Dateigröße:  1.71 KB
 Heruntergeladen:  1 mal
KurzesBeispiel.mat
 Beschreibung:
Zeitraum 120 Sekunden. Funktioniert soweit.

Download
 Dateiname:  KurzesBeispiel.mat
 Dateigröße:  2.8 KB
 Heruntergeladen:  1 mal
LangesBeispiel.mat
 Beschreibung:
Zeitraum 15*60 Sekunden. Hier werden Constraints nicht eingehalten.

Download
 Dateiname:  LangesBeispiel.mat
 Dateigröße:  101.28 KB
 Heruntergeladen:  1 mal
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 19.929
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2014a
     Beitrag Verfasst am: 10.05.2019, 13:34     Titel:
  Antworten mit Zitat      
Hallo,

Vorschlag:
Aeq = [1,1,1,0,0,0; 0,0,0,1,1,1]
beq = [1; 1]

Aeq * x = beq

umwandeln in
u(1) ist Integer zwischen 1 und 3
u(2) ist Integer zwischen 4 und 6
und dann
Code:
x = zeros(6,1);
x(u) = 1;


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 ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Yeti11
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 14
Anmeldedatum: 17.04.19
Wohnort: ---
Version: 2018b
     Beitrag Verfasst am: 10.05.2019, 14:32     Titel:
  Antworten mit Zitat      
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...
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 19.929
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2014a
     Beitrag Verfasst am: 10.05.2019, 15:37     Titel:
  Antworten mit Zitat      
Hallo,

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 ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Neues Thema eröffnen Neue Antwort erstellen

Gehe zu Seite 1, 2  Weiter

Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:

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
.


goMatlab ist ein Teil des goForen-Labels
goForen.de goMATLAB.de goLaTeX.de


 Impressum  | Nutzungsbedingungen  | Datenschutz  | Werbung/Mediadaten | Studentenversion | FAQ | goMatlab RSS Button RSS


Copyright © 2007 - 2019 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks
Partner: LabVIEWforum.de

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.