Algoritmo de otimização espiral - Spiral optimization algorithm

A espiral compartilha o comportamento global (azul) e intensivo (vermelho)

Em matemática, o algoritmo de otimização espiral (SPO) é uma metaheurística inspirada em fenômenos espirais na natureza.

O primeiro algoritmo SPO foi proposto para otimização bidimensional irrestrita baseada em modelos espirais bidimensionais. Isso foi estendido para problemas n-dimensionais generalizando o modelo espiral bidimensional para um modelo espiral n-dimensional. Existem configurações eficazes para o algoritmo SPO: a configuração da direção de descida periódica e a configuração de convergência.

Metáfora

A motivação para focar nos fenômenos espirais se deu pelo insight de que as dinâmicas que geram as espirais logarítmicas compartilham o comportamento de diversificação e intensificação. O comportamento de diversificação pode funcionar para uma busca global (exploração) e o comportamento de intensificação permite uma busca intensiva em torno de uma boa solução encontrada atualmente (exploração).

Algoritmo

Algoritmo de otimização espiral (SPO)

O algoritmo SPO é um algoritmo de busca multiponto sem gradiente de função objetivo , que usa vários modelos espirais que podem ser descritos como sistemas dinâmicos determinísticos. Como os pontos de busca seguem trajetórias espirais logarítmicas em direção ao centro comum, definido como o melhor ponto atual, melhores soluções podem ser encontradas e o centro comum pode ser atualizado.

O algoritmo SPO geral para um problema de minimização sob a iteração máxima (critério de terminação) é o seguinte: ${\ 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).

Configuração

O desempenho da pesquisa depende da configuração da matriz de rotação composta , da taxa de passos e dos pontos iniciais . As configurações a seguir são novas e eficazes. ${\ displaystyle R (\ theta)}$${\ displaystyle r (k)}$${\ displaystyle x_ {i} (0) ~ (i = 1, \ ldots, m)}$

Configuração 1 (configuração da direção de descida periódica)

Essa configuração é uma configuração eficaz para problemas dimensionais elevados sob a iteração máxima . As condições em e juntas garantem que os modelos espirais gerem direções de descida periodicamente. A condição de obras para utilizar as direções de descida periódicas sob o término da pesquisa . ${\ displaystyle k _ {\ max}}$${\ displaystyle R (\ theta)}$${\ displaystyle x_ {i} (0) ~ (i = 1, \ ldots, m)}$${\ displaystyle r (k)}$${\ displaystyle k _ {\ max}}$

• Defina como segue: onde é a matriz identidade e é o vetor zero.${\ 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) \ vezes (n-1)}$${\ displaystyle 0_ {n-1}}$${\ displaystyle (n-1) \ vezes 1}$
• Coloque os pontos iniciais aleatoriamente para satisfazer a seguinte condição:${\ 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}$ onde . Observe que essa condição é quase totalmente satisfeita por uma colocação aleatória e, portanto, nenhuma verificação é realmente adequada. ${\ displaystyle d_ {j, i} (0) = x_ {j} (0) -x_ {i} (0)}$

• Defina na Etapa 2) da seguinte forma: onde um suficientemente pequeno , como ou .${\ displaystyle r (k)}$${\ displaystyle r (k) = r = {\ sqrt [{k _ {\ max}}] {\ delta}} ~~~~ {\ text {(valor constante)}}}$${\ displaystyle \ delta> 0}$${\ displaystyle \ delta = 1 / k _ {\ max}}$${\ displaystyle \ delta = 10 ^ {- 3}}$

Configuração 2 (configuração de convergência)

Essa configuração garante que o algoritmo SPO convirja para um ponto estacionário na iteração máxima . As configurações e os pontos iniciais são os mesmos da Configuração 1. A configuração de é a seguinte. ${\ displaystyle k _ {\ max} = \ infty}$${\ displaystyle R (\ theta)}$${\ displaystyle x_ {i} (0) ~ (i = 1, \ ldots, m)}$${\ displaystyle r (k)}$

• Defina na Etapa 2) da seguinte forma: onde é uma iteração quando o centro é atualizado recentemente na Etapa 4) e como . Assim, temos que adicionar as seguintes regras sobre o Algoritmo:${\ displaystyle r (k)}$${\ displaystyle r (k) = {\ begin {cases} 1 & (k ^ {\ star} \ leqq k \ leqq k ^ {\ star} + 2n-1), \\ h & (k \ geqq k ^ {\ estrela} + 2n), \ end {casos}}}$${\ displaystyle k ^ {\ star}}$${\ displaystyle h = {\ sqrt [{2n}] {\ delta}}, \ delta \ in (0,1)}$${\ displaystyle \ delta = 0,5}$${\ displaystyle k ^ {\ star}}$

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

• (Etapa 4) Se então .${\ displaystyle x ^ {\ star} (k + 1) \ neq x ^ {\ star} (k)}$${\ displaystyle k ^ {\ star} = k + 1}$

Trabalhos futuros

• Os algoritmos com as configurações acima são determinísticos . Assim, a incorporação de algumas operações aleatórias torna este algoritmo poderoso para otimização global . Cruz-Duarte et al. demonstrou isso incluindo distúrbios estocásticos em trajetórias de busca em espiral. No entanto, essa porta permanece aberta para novos estudos.
• Encontrar um equilíbrio apropriado entre as espirais de diversificação e intensificação, dependendo da classe de problema alvo (inclusive ), é importante para melhorar o desempenho.${\ displaystyle k _ {\ max}}$

Trabalhos prolongados

Muitos estudos extensos foram conduzidos no SPO devido à sua estrutura e conceito simples; esses estudos ajudaram a melhorar seu desempenho de pesquisa global e propuseram novas aplicações.

Referências