Spiraloptimierungsalgorithmus

In der Mathematik ist der Spiraloptimierungsalgorithmus (SPO) eine Metaheuristik, die von Spiralphänomenen in der Natur inspiriert ist.

Der erste SPO-Algorithmus wurde für die zweidimensionale unbeschränkte Optimierung ^{[ 1 ]} auf Basis zweidimensionaler Spiralmodelle vorgeschlagen . Dieser wurde auf n-dimensionale Probleme erweitert, indem das zweidimensionale Spiralmodell zu einem n-dimensionalen Spiralmodell verallgemeinert wurde ^{[ 2 ]} . Es gibt effektive Einstellungen für den SPO-Algorithmus: die Einstellung der periodischen Abstiegsrichtung ^{[ 3 ]} und die Konvergenzeinstellung ^{[ 4 ] .}

Die Motivation für die Fokussierung auf Spiralphänomene beruhte auf der Erkenntnis, dass die Dynamiken, die logarithmische Spiralen erzeugen , sowohl Diversifizierungs- als auch Intensivierungsverhalten aufweisen. Das Diversifizierungsverhalten ermöglicht eine globale Suche (Exploration), während das Intensivierungsverhalten eine intensive Suche um eine bereits gefundene gute Lösung herum erlaubt (Exploitation).

Der SPO-Algorithmus ist ein Mehrpunkt-Suchalgorithmus ohne Gradientenfunktion der Zielfunktion . Er verwendet mehrere Spiralmodelle, die als deterministische dynamische Systeme beschrieben werden können. Indem die Suchpunkte logarithmischen Spiralbahnen zum gemeinsamen Zentrum folgen, das als aktuell bester Punkt definiert ist, können bessere Lösungen gefunden und das gemeinsame Zentrum aktualisiert werden.

Der allgemeine SPO-Algorithmus für ein Minimierungsproblem unter dem maximalen Iterationskriterium (Abbruchkriterium) lautet wie folgt: ${\displaystyle k_{\max }}$

0) Legen Sie die Anzahl der Suchpunkte und die maximale Iterationszahl fest .${\displaystyle m\geq 2}$${\displaystyle k_{\max }}$ 1) Platzieren Sie die anfänglichen Suchpunkte und bestimmen Sie den Mittelpunkt , , und setzen Sie dann .${\displaystyle x_{i}(0)\in \mathbb {R} ^{n}~(i=1,\ldots ,m)}$${\displaystyle x^{\star }(0)=x_{i_{\text{b}}}(0)}$${\displaystyle \displaystyle i_{\text{b}}=\mathop {\text{argmin}} _{i=1,\ldots ,m}\{f(x_{i}(0))\}}$${\displaystyle k=0}$ 2) Die Schrittrate wird anhand einer Regel bestimmt.${\displaystyle r(k)}$ 3) Aktualisieren Sie die Suchpunkte: 4) Aktualisieren Sie das Zentrum: wo .${\displaystyle x_{i}(k+1)=x^{\star }(k)+r(k)R(\theta )(x_{i}(k)-x^{\star }(k))\quad (i=1,\ldots ,m).}$${\displaystyle x^{\star }(k+1)={\begin{cases}x_{i_{\text{b}}}(k+1)&{\big (}{\text{if }}f(x_{i_{\text{b}}}(k+1))<f(x^{\star }(k)){\big )},\\x^{\star }(k)&{\big (}{\text{otherwise}}{\big )},\end{cases}}}$${\displaystyle \displaystyle i_{\text{b}}=\mathop {\text{argmin}} _{i=1,\ldots ,m}\{f(x_{i}(k+1))\}}$ 5) Setze . Wenn erfüllt ist, beende und gib aus . Andernfalls kehre zu Schritt 2 zurück. ${\displaystyle k:=k+1}$${\displaystyle k=k_{\max }}$${\displaystyle x^{\star }(k)}$

Die Suchleistung hängt von der Festlegung der zusammengesetzten Rotationsmatrix , der Schrittweite und der Startpunkte ab . Die folgenden Einstellungen sind neu und effektiv. ${\displaystyle R(\theta )}$${\displaystyle r(k)}$${\displaystyle x_{i}(0)~(i=1,\ldots ,m)}$

Diese Einstellung ist bei maximaler Iteration effektiv für hochdimensionale Probleme . Die Bedingungen an und gewährleisten gemeinsam, dass die Spiralmodelle periodisch Abstiegsrichtungen erzeugen. Die Bedingung dient dazu, die periodischen Abstiegsrichtungen bis zum Abbruch der Suche zu nutzen . ${\displaystyle k_{\max }}$${\displaystyle R(\theta )}$${\displaystyle x_{i}(0)~(i=1,\ldots ,m)}$${\displaystyle r(k)}$${\displaystyle k_{\max }}$

• Es wird wie folgt festgelegt : wobei die Einheitsmatrix und der Nullvektor ist.${\displaystyle R(\theta )}$${\displaystyle R(\theta )={\begin{bmatrix}0_{n-1}^{\top }&-1\\I_{n-1}&0_{n-1}\\\end{bmatrix}}}$${\displaystyle I_{n-1}}$${\displaystyle (n-1)\times (n-1)}$${\displaystyle 0_{n-1}}$${\displaystyle (n-1)\times 1}$
• Platziere die Startpunkte zufällig, um die folgende Bedingung zu erfüllen:${\displaystyle x_{i}(0)\in \mathbb {R} ^{n}}$${\displaystyle (i=1,\ldots ,m)}$

${\displaystyle \min _{i=1,\ldots ,m}\{\max _{j=1,\ldots ,m}{\bigl \{}{\text{rank}}{\bigl [}d_{j,i}(0)~R(\theta )d_{j,i}(0)~~\cdots ~~R(\theta )^{2n-1}d_{j,i}(0){\bigr ]}{\bigr \}}{\bigr \}}=n}$ wobei . Beachten Sie, dass diese Bedingung durch eine zufällige Platzierung fast immer erfüllt wird und daher keine Überprüfung eigentlich ausreichend ist. ${\displaystyle d_{j,i}(0)=x_{j}(0)-x_{i}(0)}$

• Setzen Sie in Schritt 2) wie folgt: wobei ein ausreichend kleines wie z. B. oder . ^{[ 3 ]}${\displaystyle r(k)}$${\displaystyle r(k)=r={\sqrt[{k_{\max }}]{\delta }}~~~~{\text{(constant value)}}}$${\displaystyle \delta >0}$${\displaystyle \delta =1/k_{\max }}$${\displaystyle \delta =10^{-3}}$

Diese Einstellung gewährleistet, dass der SPO-Algorithmus nach maximaler Iteration gegen einen stationären Punkt konvergiert . Die Einstellungen für und die Startpunkte entsprechen denen der oben beschriebenen Einstellung 1. Die Einstellung für ist wie folgt. ${\displaystyle k_{\max }=\infty }$${\displaystyle R(\theta )}$${\displaystyle x_{i}(0)~(i=1,\ldots ,m)}$${\displaystyle r(k)}$

• Setzen Sie in Schritt 2) wie folgt: wobei es sich um eine Iteration handelt , in der das Zentrum in Schritt 4) neu aktualisiert wird, und zwar so, dass . Daher müssen wir dem Algorithmus die folgenden Regeln hinzufügen:${\displaystyle r(k)}$${\displaystyle r(k)={\begin{cases}1&(k^{\star }\leqq k\leqq k^{\star }+2n-1),\\h&(k\geqq k^{\star }+2n),\end{cases}}}$${\displaystyle k^{\star }}$${\displaystyle h={\sqrt[{2n}]{\delta }},\delta \in (0,1)}$${\displaystyle \delta =0.5}$${\displaystyle k^{\star }}$

•(Schritt 1) ​​.${\displaystyle k^{\star }=0}$

•(Schritt 4) Wenn dann . ^{[ 4 ]}${\displaystyle x^{\star }(k+1)\neq x^{\star }(k)}$${\displaystyle k^{\star }=k+1}$

• Die Algorithmen mit den oben genannten Einstellungen sind deterministisch . Durch die Einbeziehung von Zufallsoperationen wird dieser Algorithmus jedoch für die globale Optimierung besonders geeignet . Cruz-Duarte et al. ^{[ 5 ]} demonstrierten dies durch die Integration stochastischer Störungen in spiralförmige Suchtrajektorien. Dieses Forschungsfeld bietet jedoch weiterhin Anlass für weitere Untersuchungen.
• Um die Leistung zu steigern, ist es wichtig, je nach Zielproblemklasse (einschließlich ) ein angemessenes Gleichgewicht zwischen Diversifizierungs- und Intensivierungsspiralen zu finden .${\displaystyle k_{\max }}$

Aufgrund seiner einfachen Struktur und seines einfachen Konzepts wurden zahlreiche weiterführende Studien zum SPO durchgeführt; diese Studien trugen zur Verbesserung seiner globalen Suchleistung bei und schlugen neue Anwendungen vor. ^{[ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ]}