kramann.info
© Guido Kramann

Login: Passwort:










5.5 Optimierung mittels modifizierter Gradientenverfahren

  • Wie arbeiten Optimierungsverfahren?
  • Eine Klasse solcher Verfahren, bilden die modifizierten Gradienten-Verfahren.
  • Da bei den meisten Optimierungsproblemen der Gradient an einer bestimmten Stelle im Parameterraum nicht berechnet werden kann, wird bei diesen Verfahren versucht ihn durch Testberechnungen in der Umgebung des aktuellen Ortes abzuschätzen.
  • Problematisch ist die Anwendung solcher Verfahren bei stark zerklüfteten Parameterräumen mit vielen lokalen Minima, da diese Verfahren in ihrer Grundform dann nur meistens nur ein lokales Minimum finden und nicht das globale.
  • Abhilfe schafft die Kombination mit anderen Verfahren, wobei das modifizierte Gradientenverfahren eingesetzt, um noch eine Verbesserung zu bewirken, wenn man schon recht nahe an einem lokalen Optimum ist.
  • Im folgenden sollen zwei solcher Verfahren für ein einfaches Beispiel mit Scilab implementiert werden:
  • Als Grundlage zu optimierende Funktion wird im folgenden wieder z = x3-4*x+y3-16*y verwendet.
  • Zur Orientierung: Das gesuchte lokale Minimum liegt bei [x,y]=[2/sqrt(3),4/sqrt(3)]=[1,154700538,2,309401077].
  • Der folgende mit Scilab erstellte 3-D-Plot zeigt den Graph dieser Funktion im Bereich -3>x>3, -3>y>3.
fxy.png

Bild 5.5-1: z = x3-4*x+y3-16*y für -3>x>3, -3>y>3.

  • Zur Erstellung des Graphen wurde folgendes Scilab-Skript verwendet:
  • alpha und theta legen dabei den Blickwinke des Betrachters fest.
function z=f(x,y)
    z = x^3-4*x+y^3-16*y
endfunction

x=-3:0.1:3;
y=x;

fplot3d(x,y,f,alpha=5,theta=31);
 

Code 5.5-1: Scilab-Skript, um den Graph der Funktion z = x3-4*x+y3-16*y zu erstellen.

  • Wenn es keine Möglichkeit gibt, für den zu optimierenden Sachverhalt eine Gradientenfunktion zu bilden und ausgehend von einem aktuellen Punkt in die Richtung der Koordinatenachsen gesucht wird, um den Punkt mit dem größten Abstieg zu suchen, dann hat man das Problem, dass man mit größerer Näherung an den Zielpunkt die Suchweite sukkzessive verringern muß.
  • Folgende Umsetzung in Scilab löst dieses Problem am Beispiel einer speziellen schon mehrfach verwendeten Funktion z = x3-4*x+y3-16*y.
  • Für jede Suchrichtung wird untersucht, ob es eine Verbesserung bringt, den bisher verwendeten Richtungsvektor in seiner Länge zu halbieren oder zu verdoppeln.
  • Hierdurch werden die Schritte in der Nähe des gescuhten Wertepaares automatisch kürzer:
function z=f(x,y)
    z = x^3-4*x+y^3-16*y
endfunction

//Suchen ausgehend von einem aktuellen Punkt in Richtung [xricht,yricht] nach dem kleinsten Wert
//für die übergebene Funktion funk.
function alfabest=frichtung(x,y,xricht,yricht,funk)
    alfa = [-2.0,-1.0,-0.5,0.5,1.0,2.0];
    wert_best = funk(x+alfa(1)*xricht,y+alfa(1)*yricht);
    alfa_best = alfa(1);

    for i=2:6
        wert = funk(x+alfa(i)*xricht,y+alfa(i)*yricht);
        if wert < wert_best
            wert_best = wert;
            alfa_best = alfa(i);
        end
    end
    alfabest = alfa_best;
endfunction


//Matrix mit Einheitsvektoren U=[ex,ey] geben zu Beginn
//Suchrichtung vor:
U=[[1;0],[0;1]]

z=[4;4];
znull=z;
for i=1:15
    alfax = frichtung(z(1,1),z(2,1),U(1,1),U(2,1),f);
    alfay = frichtung(z(1,1),z(2,1),U(1,2),U(2,2),f);
    //Neuen Punkt in die Richtung setzen, die den größten Abstieg liefert:
    wertx = f(z(1,1)+alfax*U(1,1),z(2,1)+alfax*U(2,1));
    werty = f(z(1,1)+alfay*U(1,2),z(2,1)+alfay*U(2,2));
    if  wertx < werty
        z(1,1) = z(1,1) + alfax*U(1,1);
        z(2,1) = z(2,1) + alfax*U(2,1);
    else
        z(1,1) = z(1,1) + alfay*U(1,2);
        z(2,1) = z(2,1) + alfay*U(2,2);
    end    
    U(:,1) = alfax*U(:,1);
    U(:,2) = alfax*U(:,2);
    z=z
    fehler = abs(z(1)-2/sqrt(3))+abs(z(2)-4/sqrt(3))
end
 

Code 5.5-1: Beispiel für die Anwendung eines konkreten modifizierten Gradientenverfahrens am Beispiel der Funktion z = x3-4*x+y3-16*y.

  • Eine weitere Verbesserung liefert das Verfahren von Powell.
  • Gegenüber dem vorangegangenen Beispiel wird hier noch geschaut, welches die mittlere Suchrichtung ist und diese als eine der Suchrichtungen gesetzt.
  • Da die Gefahr besteht, dass U dadurch mit der Zeit linearabhängig wird, wird immer derjenige Richtungsvektor behalten, dessen Skalaprodukt mit dem neuen möglichst klein ist.
  • Als mittlere Suchrichtung wird dabei einfach der Differenzvektor zwischen aktueller Position und der Startposition verwendet, da die aktuelle Position die Summe aus allen Richtungen seit Beginn des Algorithmus darstellt.
  • Um diesen Summenvektor der aktuellen Situation anzupassen, wird er auf die Länge des zuletzt verwendeten Vektors gebracht.
  • Gegenüber dem vrangehenden Verfahren, ist der Fehler bei gleicher Interationsanzahl bei nachfolgdendem Verfahren etwas besser:
function z=f(x,y)
    z = x^3-4*x+y^3-16*y
endfunction

function alfabest=frichtung(x,y,xricht,yricht,funk)
    alfa = [-2.0,-1.0,-0.5,0.5,1.0,2.0];
    wert_best = funk(x+alfa(1)*xricht,y+alfa(1)*yricht);
    alfa_best = alfa(1);

    for i=2:6
        wert = funk(x+alfa(i)*xricht,y+alfa(i)*yricht);
        if wert < wert_best
            wert_best = wert;
            alfa_best = alfa(i);
        end
    end
    alfabest = alfa_best;
endfunction

U=[[1;0],[0;1]]

z=[4;4];
znull=z;
for i=1:15
    betrag=1.0;
    alfax = frichtung(z(1,1),z(2,1),U(1,1),U(2,1),f);
    alfay = frichtung(z(1,1),z(2,1),U(1,2),U(2,2),f);
    //Neuen Punkt setzen:
    wertx = f(z(1,1)+alfax*U(1,1),z(2,1)+alfax*U(2,1));
    werty = f(z(1,1)+alfay*U(1,2),z(2,1)+alfay*U(2,2));
    if  wertx < werty
        z(1,1) = z(1,1) + alfax*U(1,1);
        z(2,1) = z(2,1) + alfax*U(2,1);
        betrag = norm(alfax*U(:,1));
    else
        z(1,1) = z(1,1) + alfay*U(1,2);
        z(2,1) = z(2,1) + alfay*U(2,2);
        betrag = norm(alfay*U(:,2));
    end    
    U(:,1) = alfax*U(:,1);
    U(:,2) = alfax*U(:,2);

    //Konjugierte Richtung einsetzen:
    if  wertx < werty
        if abs((z-znull)'*U(:,1))<abs((z-znull)'*U(:,2))
            U(:,2)=U(:,1);
        end
        U(:,1) = betrag*(z-znull)/norm(z-znull);
    end        
    
    z=z
    fehler = abs(z(1)-2/sqrt(3))+abs(z(2)-4/sqrt(3))
end
 

Code 5.5-2: Implementierung eines modifizierten Gradientenverfahrens unter Verwendung konjugierter Richtungsvektoren nach Powell.