Spiraloptimeringsalgoritme - Spiral optimization algorithm

Spiralen deler den globale (blå) og intensive (røde) adfærd

I matematik er spiraloptimeringsalgoritmen (SPO) en metaheuristisk inspireret af spiralfænomener i naturen.

Den første SPO-algoritme blev foreslået til todimensionel ubegrænset optimering baseret på todimensionale spiralmodeller. Dette blev udvidet til n-dimensionelle problemer ved at generalisere den todimensionale spiralmodel til en n-dimensionel spiralmodel. Der er effektive indstillinger for SPO -algoritmen: indstillingen af ​​den periodiske nedstigningsretning og konvergensindstillingen.

Metafor

Motivationen til at fokusere på spiralfænomener skyldtes indsigten om, at dynamikken, der genererer logaritmiske spiraler, deler diversificerings- og intensiveringsadfærden. Diversificeringsadfærden kan fungere for en global søgning (udforskning), og intensiveringsadfærden muliggør en intensiv søgning omkring en aktuelt fundet god løsning (udnyttelse).

Algoritme

Spiraloptimering (SPO) algoritme

SPO -algoritmen er en flerpunktssøgningsalgoritme, der ikke har nogen objektiv funktionsgradient , som bruger flere spiralmodeller, der kan beskrives som deterministiske dynamiske systemer. Da søgepunkter følger logaritmiske spiralbaner mod det fælles centrum, defineret som det nuværende bedste punkt, kan der findes bedre løsninger, og det fælles center kan opdateres.

Den generelle SPO -algoritme til et minimeringsproblem under den maksimale iteration (opsigelseskriterium) er som følger: ${\ displaystyle k _ {\ max}}$

0) Set the number of search points ${\displaystyle m\geq 2}$ and the maximum iteration number ${\displaystyle k_{\max }}$.
1) Place the initial search points ${\displaystyle x_{i}(0)\in \mathbb {R} ^{n}~(i=1,\ldots ,m)}$ and determine the center ${\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))\}}$,and then set ${\displaystyle k=0}$.
2) Decide the step rate ${\displaystyle r(k)}$ by a rule.
3) Update the search points: ${\displaystyle x_{i}(k+1)=x^{\star }(k)+r(k)R(\theta )(x_{i}(k)-x^{\star }(k))\quad (i=1,\ldots ,m).}$
4) Update the center: ${\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}}}$ where ${\displaystyle \displaystyle i_{\text{b}}=\mathop {\text{argmin}} _{i=1,\ldots ,m}\{f(x_{i}(k+1))\}}$.
5) Set ${\displaystyle k:=k+1}$. If ${\displaystyle k=k_{\max }}$ is satisfied then terminate and output ${\displaystyle x^{\star }(k)}$. Otherwise, return to Step 2).

Indstilling

Søgningen ydelse afhænger af indstilling af sammensatte rotation matrix , trin sats , og de første punkter . Følgende indstillinger er nye og effektive. ${\ displaystyle R (\ theta)}$${\ displaystyle r (k)}$${\ displaystyle x_ {i} (0) ~ (i = 1, \ ldots, m)}$

Indstilling 1 (Indstilling af periodisk nedstigningsretning)

Denne indstilling er en effektiv indstilling for højdimensionelle problemer under den maksimale iteration . Betingelserne på og sammen sikrer, at spiralmodellerne genererer nedstigningsretninger med jævne mellemrum. Betingelsen for værker for at udnytte de periodiske nedstigningsretninger under søgeterminering . ${\ displaystyle k _ {\ max}}$${\ displaystyle R (\ theta)}$${\ displaystyle x_ {i} (0) ~ (i = 1, \ ldots, m)}$${\ displaystyle r (k)}$${\ displaystyle k _ {\ max}}$

• Indstil som følger: hvor er identitetsmatricen og er nulvektoren.${\ 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) \ gange 1}$
• Placer de indledende punkter tilfældigt for at opfylde følgende betingelse:${\ 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}$ hvor . Bemærk, at denne betingelse næsten alle er opfyldt af en tilfældig placering, og derfor er ingen kontrol faktisk fin. ${\ displaystyle d_ {j, i} (0) = x_ {j} (0) -x_ {i} (0)}$

• Indstil til trin 2) som følger: hvor en tilstrækkelig lille, såsom eller .${\ displaystyle r (k)}$${\ displaystyle r (k) = r = {\ sqrt [{k _ {\ max}}] {\ delta}} ~~~~ {\ text {(konstant værdi)}}}$${\ displaystyle \ delta> 0}$${\ displaystyle \ delta = 1/k _ {\ max}}$${\ displaystyle \ delta = 10^{-3}}$

Indstilling 2 (konvergensindstilling)

Denne indstilling sikrer, at SPO -algoritmen konvergerer til et stationært punkt under den maksimale iteration . Indstillingerne for og de indledende punkter er de samme med ovenstående indstilling 1. Indstillingen af er som følger. ${\ displaystyle k _ {\ max} = \ infty}$${\ displaystyle R (\ theta)}$${\ displaystyle x_ {i} (0) ~ (i = 1, \ ldots, m)}$${\ displaystyle r (k)}$

• Indstil i trin 2) som følger: hvor er en iteration, når centret er nyligt opdateret i trin 4) og f.eks . Således skal vi tilføje følgende regler om til algoritmen:${\ displaystyle r (k)}$${\ displaystyle r (k) = {\ begin {cases} 1 & (k^{\ star} \ leqq k \ leqq k^{\ star}+2n-1), \\ h & (k \ geqq k^{\ stjerne}+2n), \ slut {sager}}}$${\ displaystyle k^{\ star}}$${\ displaystyle h = {\ sqrt [{2n}] {\ delta}}, \ delta \ in (0,1)}$${\ displaystyle \ delta = 0,5}$${\ displaystyle k^{\ star}}$

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

• (trin 4) Hvis så .${\ displaystyle x^{\ star} (k+1) \ neq x^{\ star} (k)}$${\ displaystyle k^{\ star} = k+1}$

Fremtidige værker

• Algoritmerne med ovenstående indstillinger er deterministiske . Således inkorporerer nogle tilfældige operationer denne algoritme kraftfuld til global optimering . Cruz-Duarte et al. demonstreret det ved at inkludere stokastiske forstyrrelser i spiralsøgningsbaner. Denne dør er imidlertid stadig åben for yderligere undersøgelser.
• For at finde en passende balance mellem diversificering og intensiveringsspiraler afhængigt af målproblemklassen (inklusive ) er det vigtigt at forbedre ydelsen.${\ displaystyle k _ {\ max}}$

Udvidede værker

Mange udvidede undersøgelser er blevet udført på SPO på grund af dets enkle struktur og koncept; disse undersøgelser har hjulpet med at forbedre dens globale søgeevne og foreslåede nye applikationer.

Referencer