Simplexalgorithmus

Author: Hans Lohninger

Der Simplexalgorithmus ist ein Gradientensuchverfahren. Er wird gerne angewandt, weil er einfach zu verstehen und durchzuführen ist (der Simplexalgorithmus sollte nicht mit der Simplexmethode bei der linearen Programmierung verwechselt werden).

Der Simplexalgorithmus funktioniert so: Hängt der zu optimierende Parameter von k Variablen ab, dann wählen Sie k + 1 Punkte. Diese Punkte dürfen keine kollinearen Vektoren bilden. Nun finden Sie die beiden Punkte mit dem schlechtesten und dem zweitschlechtesten Response. Als Nächstes spiegeln Sie den schlechtesten Punkt am Zentroid der Fläche, die von den anderen k Punkten aufgespannt wird. Dieses Verfahren wird wiederholt, bis der beste Response erreicht ist. Nun müssen wir eine zusätzliche Regel einführen, um den Simplex davor zu bewahren, um einen Grat zu oszillieren: wenn der gespiegelte Punkt der schlechteste Punkt bleibt, dann verwendet man den zweitschlechtesten Punkt für die Reflexion über das Zentroid.

Zum besseren Verständnis können Sie die Entwicklung des Optimierungsprozesses in diesem interaktiven Beispiel verfolgen.

Bitte beachten Sie, dass die Simplexoptimierung dazu neigt, in einem lokalen Maximum (bzw. Minimum) stecken zu bleiben. Die Ergebnisse eines Simplexdurchlaufs hängen von den Anfangsbedingungen ab. Um die Chancen zu erhöhen, das globale Optimum zu finden, sollte man mehrere Simplexdurchläufe mit verschiedenen Startbedingungen wiederholen.