Algoritmo de optimización en espiral

En matemáticas, el algoritmo de optimización en espiral (SPO, por sus siglas en inglés) es una metaheurística inspirada en los fenómenos espirales de la naturaleza.

El primer algoritmo SPO se propuso para la optimización bidimensional sin restricciones ^{[ 1 ]} , basado en modelos espirales bidimensionales. Este se extendió a problemas n-dimensionales generalizando el modelo espiral bidimensional a un modelo espiral n-dimensional ^{[ 2 ]} . Existen configuraciones efectivas para el algoritmo SPO: la configuración de la dirección de descenso periódico ^{[ 3 ]} y la configuración de convergencia ^{[ 4 ] .}

La motivación para centrarse en los fenómenos espirales surgió de la constatación de que la dinámica que genera las espirales logarítmicas comparte comportamientos de diversificación e intensificación. El comportamiento de diversificación puede ser útil para una búsqueda global (exploración), mientras que el de intensificación permite una búsqueda intensiva en torno a una buena solución encontrada hasta el momento (explotación).

El algoritmo SPO es un algoritmo de búsqueda multipunto sin gradiente de función objetivo , que utiliza múltiples modelos espirales que pueden describirse como sistemas dinámicos deterministas. A medida que los puntos de búsqueda siguen trayectorias espirales logarítmicas hacia el centro común, definido como el mejor punto actual, se pueden encontrar mejores soluciones y actualizar el centro común.

El algoritmo SPO general para un problema de minimización bajo el criterio de iteración máxima (criterio de terminación) es el siguiente: ${\displaystyle k_{\max }}$

0) Establezca el número de puntos de búsqueda y el número máximo de iteraciones .${\displaystyle m\geq 2}$${\displaystyle k_{\max }}$ 1) Coloque los puntos de búsqueda iniciales y determine el centro , , y luego establezca .${\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) Determina la frecuencia de los pasos mediante una regla.${\displaystyle r(k)}$ 3) Actualizar los puntos de búsqueda: 4) Actualizar el centro: donde .${\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) Establezca . Si se cumple, finalice y muestre . De lo contrario, vuelva al paso 2). ${\displaystyle k:=k+1}$${\displaystyle k=k_{\max }}$${\displaystyle x^{\star }(k)}$

El rendimiento de la búsqueda depende de la configuración de la matriz de rotación compuesta , la velocidad de paso y los puntos iniciales . Las siguientes configuraciones son nuevas y efectivas. ${\displaystyle R(\theta )}$${\displaystyle r(k)}$${\displaystyle x_{i}(0)~(i=1,\ldots ,m)}$

Esta configuración es eficaz para problemas de alta dimensión con la iteración máxima . Las condiciones sobre y juntas aseguran que los modelos espirales generen direcciones de descenso periódicamente. La condición funciona para utilizar las direcciones de descenso periódicas bajo la terminación de búsqueda . ${\displaystyle k_{\max }}$${\displaystyle R(\theta )}$${\displaystyle x_{i}(0)~(i=1,\ldots ,m)}$${\displaystyle r(k)}$${\displaystyle k_{\max }}$

• Establecemos lo siguiente: donde es la matriz identidad y es el vector cero.${\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}$
• Coloca los puntos iniciales al azar para satisfacer la siguiente condición:${\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}$ donde . Tenga en cuenta que esta condición se cumple casi por completo con una colocación aleatoria y, por lo tanto, no realizar ninguna comprobación es realmente aceptable. ${\displaystyle d_{j,i}(0)=x_{j}(0)-x_{i}(0)}$

• Establecido en el paso 2) de la siguiente manera: donde un suficientemente pequeño como o . ^{[ 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}}$

Esta configuración garantiza que el algoritmo SPO converja a un punto estacionario bajo el número máximo de iteraciones . Las configuraciones de y los puntos iniciales son los mismos que en la Configuración 1 anterior. La configuración de es la siguiente. ${\displaystyle k_{\max }=\infty }$${\displaystyle R(\theta )}$${\displaystyle x_{i}(0)~(i=1,\ldots ,m)}$${\displaystyle r(k)}$

• Establecido en el Paso 2) de la siguiente manera: donde es una iteración cuando el centro se actualiza por primera vez en el Paso 4) y tal como . Por lo tanto, debemos agregar las siguientes reglas sobre al Algoritmo:${\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 }}$

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

•(Paso 4) Si entonces . ^{[ 4 ]}${\displaystyle x^{\star }(k+1)\neq x^{\star }(k)}$${\displaystyle k^{\star }=k+1}$

• Los algoritmos con la configuración anterior son deterministas . Por lo tanto, la incorporación de algunas operaciones aleatorias hace que este algoritmo sea potente para la optimización global . Cruz-Duarte et al. ^{[ 5 ]} lo demostraron al incluir perturbaciones estocásticas en trayectorias de búsqueda en espiral. Sin embargo, esta posibilidad queda abierta a futuras investigaciones.
• Encontrar un equilibrio apropiado entre las espirales de diversificación e intensificación, dependiendo de la clase de problema objetivo (incluyendo ), es importante para mejorar el rendimiento.${\displaystyle k_{\max }}$

Se han realizado numerosos estudios exhaustivos sobre el SPO debido a su estructura y concepto sencillos; estos estudios han contribuido a mejorar su rendimiento de búsqueda global y han propuesto nuevas aplicaciones. ^{[ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ]}