Diese Seite wurde mithilfe maschineller Übersetzung übersetzt. Klicken Sie hier, um die neueste Version auf Englisch zu sehen.

Suchen Sie nach globalen oder mehreren lokalen Minima

Live Script öffnen

Dieses Beispiel veranschaulicht, wie GlobalSearch effizient ein globales Minimum findet und wie MultiStart viele weitere lokale Minima findet.

Die Zielfunktion für dieses Beispiel hat viele lokale Minima und ein eindeutiges globales Minimum. In Polarkoordinaten lautet die Funktion

$f (r, t) = g (r) h (t)$

wobei

$\begin{array}{l} g (r) = (\sin (r) - \frac{\sin (2 r)}{2} + \frac{\sin (3 r)}{3} - \frac{\sin (4 r)}{4} + 4) \frac{r^{2}}{r + 1} \\ h (t) = 2 + \cos (t) + \frac{\cos (2 t - \frac{1}{2})}{2} . \end{array}$

Zeichnen Sie die Funktionen $g$ und $h$ und erstellen Sie ein Oberflächendiagramm der Funktion $f$ .

figure
subplot(1,2,1);
fplot(@(r)(sin(r) - sin(2*r)/2 + sin(3*r)/3 - sin(4*r)/4 + 4) .* r.^2./(r+1), [0 20])
title(''); ylabel('g'); xlabel('r');
subplot(1,2,2);
fplot(@(t)2 + cos(t) + cos(2*t-1/2)/2, [0 2*pi])
title(''); ylabel('h'); xlabel('t');

figure
fsurf(@(x,y) sawtoothxy(x,y), [-20 20])
% sawtoothxy is defined in the first step below
xlabel('x'); ylabel('y'); title('sawtoothxy(x,y)');
view(-18,52)

Das globale Minimum liegt bei $r = 0$ mit Zielfunktion 0. Die Funktion $g (r)$ wächst in $r$ ungefähr linear mit einer sich wiederholenden Sägezahnform. Die Funktion $h (t)$ hat zwei lokale Minima, von denen eines global ist.

Die sawtoothxy.m-Datei konvertiert kartesische Koordinaten in Polarkoordinaten und berechnet dann den Wert in Polarkoordinaten.

type sawtoothxy

function f = sawtoothxy(x,y)
[t r] = cart2pol(x,y); % change to polar coordinates
h = cos(2*t - 1/2)/2 + cos(t) + 2;
g = (sin(r) - sin(2*r)/2 + sin(3*r)/3 - sin(4*r)/4 + 4) ...
    .*r.^2./(r+1);
f = g.*h;
end

Einzelnes globales Minimum über `GlobalSearch`

Um mit GlobalSearch nach dem globalen Minimum zu suchen, erstellen Sie zunächst eine Problemstruktur. Verwenden Sie den 'sqp'-Algorithmus für fmincon,

problem = createOptimProblem('fmincon',...
    'objective',@(x)sawtoothxy(x(1),x(2)),...
    'x0',[100,-50],'options',...
    optimoptions(@fmincon,'Algorithm','sqp','Display','off'));

Der Startpunkt ist [100,-50] statt [0,0], daher startet GlobalSearch nicht bei der globalen Lösung.

Validieren Sie die Problemstruktur, indem Sie fmincon ausführen.

[x,fval] = fmincon(problem)

x = 1×2

   45.7236 -107.6515

fval = 555.5820

Erstellen Sie das GlobalSearch-Objekt und stellen Sie die iterative Anzeige ein.

gs = GlobalSearch('Display','iter');

Legen Sie aus Gründen der Reproduzierbarkeit den Startwert des Zufallszahlengenerators fest.

rng(14,'twister')

Führen Sie den Solver aus.

[x,fval] = run(gs,problem)

 Num Pts                 Best       Current    Threshold        Local        Local                 
Analyzed  F-count        f(x)       Penalty      Penalty         f(x)     exitflag        Procedure
       0      200       555.6                                   555.6            0    Initial Point
     200     1463   1.547e-15                               1.547e-15            1    Stage 1 Local
     300     1564   1.547e-15     5.858e+04        1.074                              Stage 2 Search
     400     1664   1.547e-15      1.84e+05         4.16                              Stage 2 Search
     500     1764   1.547e-15     2.683e+04        11.84                              Stage 2 Search
     600     1864   1.547e-15     1.122e+04        30.95                              Stage 2 Search
     700     1964   1.547e-15     1.353e+04        65.25                              Stage 2 Search
     800     2064   1.547e-15     6.249e+04        163.8                              Stage 2 Search
     900     2164   1.547e-15     4.119e+04        409.2                              Stage 2 Search
     950     2359   1.547e-15           477        589.7          387            2    Stage 2 Local
     952     2423   1.547e-15         368.4          477        250.7            2    Stage 2 Local
    1000     2471   1.547e-15     4.031e+04        530.9                              Stage 2 Search

GlobalSearch stopped because it analyzed all the trial points.

3 out of 4 local solver runs converged with a positive local solver exit flag.

x = 1×2
10^-7 ×

    0.0414    0.1298

fval = 1.5467e-15

Der Solver findet drei lokale Minima, einschließlich des globalen Minimums bei [0,0].

Mehrere lokale Minima über `MultiStart`

Um mit MultiStart nach mehreren Minima zu suchen, erstellen Sie zunächst eine Problemstruktur. Da das Problem keine Einschränkungen aufweist, verwenden Sie den fminunc-Solver. Legen Sie Optionen fest, um in der Befehlszeile keine Anzeige anzuzeigen.

problem = createOptimProblem('fminunc',...
    'objective',@(x)sawtoothxy(x(1),x(2)),...
    'x0',[100,-50],'options',...
    optimoptions(@fminunc,'Display','off'));

Validieren Sie die Problemstruktur durch Ausführen.

[x,fval] = fminunc(problem)

x = 1×2

    8.4420 -110.2602

fval = 435.2573

Erstellen Sie ein Standard-MultiStart-Objekt.

ms = MultiStart;

Führen Sie den Solver 50 Iterationen lang aus und zeichnen Sie die lokalen Minima auf.

rng(1) % For reproducibility
[x,fval,eflag,output,manymins] = run(ms,problem,50)

MultiStart completed some of the runs from the start points. 

10 out of 50 local solver runs converged with a positive local solver exitflag.

x = 1×2

  -73.8348 -197.7810

fval = 766.8260

eflag = 2

output = struct with fields:
                funcCount: 8574
         localSolverTotal: 50
       localSolverSuccess: 10
    localSolverIncomplete: 40
    localSolverNoSolution: 0
                  message: 'MultiStart completed some of the runs from the start points. ...'

manymins=1×10 GlobalOptimSolution array with properties:
    X
    Fval
    Exitflag
    Output
    X0

Der Solver findet das globale Minimum nicht in der Nähe von [0,0]. Der Löser findet 10 verschiedene lokale Minima.

Zeichnen Sie die Funktionswerte an den lokalen Minima auf:

histogram([manymins.Fval],10)

Zeichnen Sie die Funktionswerte an den drei besten Punkten auf:

bestf = [manymins.Fval];
histogram(bestf(1:3),10)

MultiStart startet fminunc von Startpunkten mit gleichmäßig zwischen –1000 und 1000 verteilten Komponenten. fminunc bleibt häufig in einem der vielen lokalen Minima hängen. fminunc überschreitet sein Iterationslimit oder Funktionsauswertungslimit 40 Mal.

Siehe auch

GlobalSearch | MultiStart | createOptimProblem

Suchen Sie nach globalen oder mehreren lokalen Minima

Einzelnes globales Minimum über GlobalSearch

Mehrere lokale Minima über MultiStart

Siehe auch

Themen

Einzelnes globales Minimum über `GlobalSearch`

Mehrere lokale Minima über `MultiStart`