kramann.info
© Guido Kramann

Heuristische Suchstrategien

Günstige Parameter für beispielsweise einen PID-Regler von Hand zu finden ist oft schwierig.
Es wäre wünschenswert diesen Vorgang zu automatisieren.
Bei komplexeren Systemen existiert häufig nicht ein einziges Optimum.
Es sind of eine Vielzahl an Parametern zu variieren und es gibt viele lokale Minima im Parameterraum.
Ferner ist häufig keine analytische Güte-Funktion F angebbar.
Vielmehr kann immer nur der Wert von F(x_akt) für einen bestimmten Parameter-Vektor x_akt bestimmt werden.
Heuristiken sind hierfür geeignete automatisierte Suchverfahren.
Heuristische Suchverfahren nutzen das bekannte Wissen über das System aus, um geeignete Richtungen für die Suche zu identifizieren.
Einige Methoden:

Angenommen wir wollten für den PID-Regler eine Parameterstudie durchzuführen.
Wir würden für jeden der drei Parameter zunächst einen kleinsten und größt-möglichen Wert festlegen.
Dann würde man diese drei Bereiche in äquidistante Teile gliedern.
Für jede Kombination dieser gerasterten möglichen Parametereinstellungen würde man dann eine Simulation durchführen und den jeweiligen Wert der Fehlerfunktion F bestimmen.
Man erhält so in diesem Fall eine grob gerasterte dreidimensionale Verteilung für F im Parameterraum.
Nun könnte man in viel versprechenden Bereichen die Rasterung verfeinern und in geringeren Abständen im Parameterraum weitere Simulationen durchführen.
Damit erhielte man schließlich einige gute Kombinationen für K, T_N und T_V.

Man bestimmt zunächst F für einen Startpunkt x_akt für K, T_N und T_V.
Nun bestimmt man F für Punkte, die äquidistant auf einer kleinen Sphäre um x_akt herum liegen, z.B. zu diesem Startpunkt die äquidistanten Punkte in Richtung der Koordinatenachsen.
Aus den Differenzen der F-Werte der Sphärenpunkte zu dem Startpunkt, ergeben sich grobe Gradientenvektoren.
Man wählt die Richtung mit der stärksten Verkleinerung des F-Wertes aus.
Man normiert den entsprechenden Richtungsvektor und multipliziert ihn mit einem kleinen Faktor α.
Das ist dann der Weg, den man vom alten Punkt aus geht.
Am neuen Punkt wir das Verfahren wiederholt usw.
Abbruchkriterium z.B.: Der Abstand zwischen neuem und altem Punkt wird kleiner, als die Genauigkeitsgrenze, mit der sich die zu optimierenden Parameter einstellen lassen.
Das Verfahren in dieser Form kann dazu führen, dass es in einem nicht optimalen lokalen Minimum endet.
Es wäre deshalb wichtig eine ganze Reihe von Startpunkten durchzutesten.
So könnte eine Parameterstudie die Startpunkte für das modifizierte Gradientenverfahren liefern.
Damit das Verfahren konvergiert, darf α, also der Abstand zwischen alter und neuer Position nicht zu groß gewählt werden.
Es macht Sinn, α gegen Ende des Verfahrens immer kleiner werden zu lassen, bzw. durch die Steigung des Gradientenvektors zu steuern.

Eine generellere Methode ist es, einen genetischen Algorithmus für die Minimumssuche von F zu implementieren.
Unser Gen wäre beim PID-Regler der Parametervektor x mit den Komponenten K, T_N und T_V.
Eine Reihe solcher unterschiedlichen Gene, z.B. 100 liefern mehr oder weniger kleine Werte für F.
Für eine kommende Generation von Genen werden beispielsweise die 10 besten (kleinste F-Werte) herausgegriffen.
Nun rekombiniert man die zehn besten Gene um wieder auf z.B. hundert neue Gene zu kommen.
D.h. man nimmt das K von dem einen Gen und fügt dort noch T_N und T_V aus einem anderen der 10 besten Gene hinzu.
Damit diese genetische Evolution nicht auch in einem lokalen Minimum landet, können noch Mutationen eingeführt werden:
Es werden moderate zufällige Veränderungen an den Genen einer neuen Generation durchgeführt.
Der Mutationsgrad sollte mit fortschreitender Evolution immer weiter abnehmen, um gewoonnene positive Ergebnisse nicht wieder zu zerstören.
Aufgrund von Tests sollte man die Mutationsrate, die Anzahl der Gene und die Bestenauswahl so einstellen, dass das Verfahren konvergiert.