Optimierungsprobleme mit dem Solver
Zizek Claus
Hi Folks!
Hier mein kleines Excel-Problem:
Ich habe versucht ein Optimierungs-Problem über ein Last-Square Fitting
soll mit dem Solver zu lösen (Ziel: finden des absoluten Minimums eines von
mir entwickeltn Algorithmus der Form y =f(x,z) ). Der Excel-Solver findet
aber leider nicht das absolute Minimum, sondern bleibt in einem der lokalen
Minima hängen (So ein Sch...!). Für eine Funktion y = f(x) habe ich schon
einen sinnvolle Lösung programmiert, um den Solver zu ersetzen. Aber bei
der Abhängigkeit von mehrern Parametern muss ich im Moment passen. Wer
könnte mir bei Problemstellungen dieser Art weiterhelfen?
Danke im voraus!
Viele Grüss
Claus J. Zizek
H+E Eschner
Hi Claus,
"Zizek Claus" <ziz...@buchi.com> wrote:
>... Der Excel-Solver findet
>aber leider nicht das absolute Minimum, sondern bleibt in einem der lokalen
>Minima hängen...
Es gibt ein mathematisches Verfahren für diese Problemstellung, auf
dessen Namen ich aber leider nicht komme:
Im Prinzip ist es die Nachbildung der biologischen Optimierung:
Die Lösungsparameter werden 'zufällig' mutiert (ist wohl wichtig, um
sich nicht auf ein lokales Optimum einzuschießen), und günstige
Eigenschaften der nächsten Generation (Lösungsparametersatz)
weitervererbt.
Vielleicht hilft Dir diese (zu) kurze Beschreibung, auf Deiner Suche
bei entsprechenden Begrifen hellhörig zu werden.
Wie dieses aber mit Excel zu verwirklichen wäre (und ob es das
richtige Werkzeug dafür ist, oder es schon fertige Programme dafür
gibt), weiß ich nicht...
cu, Hanfred
Torsten Harden
Hallo Hanfred, Hallo Claus
bei dem von Hanfred beschriebenen Verfahren handelt es sich um
Genetische Algorithmen. Tatsächlich sind genetische Algorithmen
derzeit wohl das verbreitetste Verfahren zur Lösung derartiger
Probleme, jedoch nicht das einzige. Viele Informationen zu genetischen
Algorithmen sind auf der homepage von ILIGAL zu finden. Es gibt auch
ein Excel-Add in, daß mit einem genetischen Algorithmus optimiert. Die
Adresse habe ich allerdings nicht parat, sollte aber nicht schwer zu
finden sein.
Genetische Algorithmen sind allerdings nicht das einzige Verfahren
nach globalen Optima zu suchen. Wobei man sich immer der Tatsache
bewußt sein muß, daß es häufig nicht sicher ist, ob man wirklich das
globale Optimum gefunden hat. Jedoch die Wahrscheinlichtkeit sollte
möglichst groß sein, auf ein globales Optimum gestoßen zu sein. Andere
Optimierer verwenden einen vergleichbaren Algorithmus, wie er im
Solver vorhanden ist, verbinden diesen jedoch mit einem
Zufallszahlengerator, der ein möglichst großes Spektrum von möglichen
Lösungen abdeckt. Derartige Systeme werden auch von der Firma
angeboten, die auch den Excel-Solver herstellt. Auf deren Homepage
gibt es ausführliche Informationen. Darüber hinaus sind im Internet
eine große Anzahl von Solvern zu finden, die sich dieser Problematik
annehmen. Viele muß man allerdings für sehr viel Geld kaufen.
Allerdings sind viele auch ihr Geld wert.
Grüße
Torsten Harden
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Dipl.-Ing. agr. Torsten Harden
eMail: T.Ha...@tu-bs.de
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Edgar E. Eichler
Hallo Torsten, H+E, Claus
das hier diskutierte Problem ist, glaube ich, gar nicht so schwierig, Nur
aufwendig.
Ist der Datenbestand vorhanden, so sucht man das Max(Mini)mum:
Beispiel
1. Absolute Optima, Lösung aus einem Programm
Sub MinMaxWertErmitteln(Kennung As Integer)
Dim i, i0, j, j0, adr_a As Integer
Dim a, MinMax As Single
Dim m As Integer
Dim n As Integer
If Kennung = 0 Then
MinMax = 1E+30
Else
MinMax = -1E+30
End If
n = Cells(5, 4).Value ' für Adreßrechnung
m = Cells(6, 4).Value + 1 ' für Adreßrechnung
For j = 0 To n - 1
For i = 0 To n - 1
adr_a = 3 + i + AdressFunktion_z(j, m, n)
a = Cells(adr_a, 6).Value ' oder Formeldaten y=f(z,x) !!!!
If Kennung = 0 Then
If a < MinMax Then
i0 = i
j0 = j
MinMax = a
End If
Else
If a > MinMax Then
i0 = i
j0 = j
MinMax = a
End If
End If
Next i
Next j
AnzeigeWerteEintragen MinMax, i0, j0, m, n
End Sub
2. In einem früher geschriebenem Programm habe ich einen Bereich danach
abgesucht, ob der nächste Funktionswert eine Umkehrung bewirkt (genetisch).
Das wäre ein Optimum, das man sich im Programm merkt. Damit erhält man alle
lokale Optima.
3. In dynamischen Prozessen wird man ein Optimierungskriterium definieren
müssen, wie z.B. least-square-Methode = Integral x^2 dt (oder ITAE-Optimum =
Integral t |x| dt), wie in der Regelungstechnik üblich. Hier muß man
numerisch differenzieren und integrieren.
Gruß Edgar E. Eichler
Internet Site: http://ourworld.compuserve.com/homepages/MTEC/
Technologie und Internet Software fuer Ingenieure, VBA und HTML
Torsten Harden schrieb in Nachricht <6ldvpc$r87$2...@news01.btx.dtag.de>...
Torsten Harden
On Tue, 9 Jun 1998 08:30:37 +0200, "Edgar E. Eichler"
<MT...@compuserve.com> wrote:
>Hallo Torsten, H+E, Claus
>
>das hier diskutierte Problem ist, glaube ich, gar nicht so schwierig, Nur
>aufwendig.
>
>Ist der Datenbestand vorhanden, so sucht man das Max(Mini)mum:
Hallo Edgar und auch alle anderen,
vermutlich habe ich das Programm nicht bis ins letzte Detail
verstanden. Offenbar bin ich mit diesem Programm nur in der Lage eine
gegebene Argumenteliste auszuwerten (wenn ich mich hier getäuscht
habe, dann ist alles Folgende als nichtig zu betrachten). Wenn Klaus
mit diesem Ansatz für die Lösung seines Problems weiterkommt, ist das
sicherlich die einfachste und eleganteste Lösung. Bei meinem Posting
bin ich von einer anderen Voraussetzung ausgegangen. Zum einen habe
ich angenommen, daß ein Datenbestand nicht vorhanden ist, da die
Funktionsargumente reelle Zahlen einnehmen können und somit eine
unendliche Zahl von Funktionsargumenten existiert. Weiterhin habe ich
versucht mich auf die allgemeine Problemstellung y=f(x1, x2,...,xi) zu
beziehen (wobei man Edgars Lösungsansatz sicherlich ohne Probleme auf
mehr als 2 Argumente erweitern kann).
Wenn ich Optimierungen höre, habe ich automatisch LP-Probleme (Lineare
Programmierung), NLP-Probleme (nicht lineare Programmierung) oder
Anpassung von Systemen aus gewöhnlichen Differentialgleichungen an
bestimmte Meßwerte im Kopf. Möglicherweise bin ich damit über das Ziel
hinausgeschossen.
Viele Grüße
Torsten
P.S. Eine weitere Diskussion über Optimierungen würde mich in diesem
Forum sehr interessieren.
Edgar E. Eichler
Torsten Harden schrieb in Nachricht <6lj7l9$qe$1...@news01.btx.dtag.de>...
Hallo Torsten,
1. Lineare Optimierung nach der Simplex-Methode (Ungleichungen mit
Beschränkungen): Da sehe ich (noch) keinen Zusammenhang zu y=f(x, z).
Üblicherweise arbeitet man da in der Schreibweise y=f(x1, x2, ...). Das hast
Du auch so gemacht.
2. Spricht man von y=f(x, z) denke ich sofort an Daten, wie z.B. Umsatz =
f(Monate, Jahre) oder Dichte=f(Temperatur, Druck). Will man diese Daten per
Computer verabeiten, kann man z.B. über eine Polynomapproximation die Daten
extrem reduzieren und 'auswerten'.
3. Optimierung von dynamischen Prozessen. Das war hier nicht angesprochen.
4. Erwähnenswert ist auch ein Fall, bei dem nach Auflösen eines
Gleichungssystems das Ergebnis zeigte, daß ein teures Aggregat in einem
thermodynamischen Kreislauf rein technisch nicht notwendig war. Wenn das
keine Optimierung ist?
Ich kann den Begriff Least Square Fitting (=Polynomapproximation) nur zu
(2.) oder (3.) zuordnen, auch dann, wenn bei der (N)LO Koeffizienten benutzt
werden, die 'zuvor' über eine Polynomapproximation gefunden wurden. Beides
zusammen in einem Rechengang zu ermitteln halte ich für unwahrscheinlich.
Das ist der Grund, warum ich an (2.) dachte.
Genetische Algorithmen sind m.E. Trial-and-Error-Methoden. Ich selbst habe
das schon selbst programmiert. Einfach formuliert: Formuliere z.B. ein
technisches System durch ein Dgl-System. Störe das System und lasse es durch
z.B. einen Regler ausregeln. Verstelle einen Regelparameter (z.B. P-Bereich)
und laß das Programm über ein Optimierungskriterium feststellen, ob das
Ergebnis
besser oder schlechter geworden ist. Wenn besser, mach weiter so. Wenn
nicht, ist ein Optimum erreicht.
Durch den Beispiel-Code wollte ich nur mal zeigen, wie einfach ein
Max(Min)imum aus einem Datensatz gefunden werden kann. Wurde zuvor ein
Polynom ermittelt, kann dieses eingesetzt werden.