Spiral optimization algorithm

Last updated October 26, 2023

In mathematics, the spiral optimization (SPO) algorithm is a metaheuristic inspired by spiral phenomena in nature.

The first SPO algorithm was proposed for two-dimensional unconstrained optimization^[1] based on two-dimensional spiral models. This was extended to n-dimensional problems by generalizing the two-dimensional spiral model to an n-dimensional spiral model.^[2] There are effective settings for the SPO algorithm: the periodic descent direction setting^[3] and the convergence setting.^[4]

Metaphor

The motivation for focusing on spiral phenomena was due to the insight that the dynamics that generate logarithmic spirals share the diversification and intensification behavior. The diversification behavior can work for a global search (exploration) and the intensification behavior enables an intensive search around a current found good solution (exploitation).

Algorithm

The SPO algorithm is a multipoint search algorithm that has no objective function gradient, which uses multiple spiral models that can be described as deterministic dynamical systems. As search points follow logarithmic spiral trajectories towards the common center, defined as the current best point, better solutions can be found and the common center can be updated.

The general SPO algorithm for a minimization problem under the maximum iteration $k_{\max }$ (termination criterion) is as follows:

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

Setting

The search performance depends on setting the composite rotation matrix $R(\theta )$ , the step rate $r(k)$ , and the initial points $x_{i}(0)~(i=1,\ldots ,m)$ . The following settings are new and effective.

Setting 1 (Periodic Descent Direction Setting)

This setting is an effective setting for high dimensional problems under the maximum iteration $k_{\max }$ . The conditions on $R(\theta )$ and $x_{i}(0)~(i=1,\ldots ,m)$ together ensure that the spiral models generate descent directions periodically. The condition of $r(k)$ works to utilize the periodic descent directions under the search termination $k_{\max }$ .

Set $R(\theta )$ as follows: $R(\theta )={\begin{bmatrix}0_{n-1}^{\top }&-1\\I_{n-1}&0_{n-1}\\\end{bmatrix}}$ where $I_{n-1}$ is the $(n-1)\times (n-1)$ identity matrix and $0_{n-1}$ is the $(n-1)\times 1$ zero vector.
Place the initial points $x_{i}(0)\in \mathbb {R} ^{n}$ $(i=1,\ldots ,m)$ at random to satisfy the following condition:

$\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$ where $d_{j,i}(0)=x_{j}(0)-x_{i}(0)$ . Note that this condition is almost all satisfied by a random placing and thus no check is actually fine.

Set $r(k)$ at Step 2) as follows: $r(k)=r={\sqrt[{k_{\max }}]{\delta }}~~~~{\text{(constant value)}}$ where a sufficiently small $\delta >0$ such as $\delta =1/k_{\max }$ or $\delta =10^{-3}$ .^[3]

Setting 2 (Convergence Setting)

This setting ensures that the SPO algorithm converges to a stationary point under the maximum iteration $k_{\max }=\infty$ . The settings of $R(\theta )$ and the initial points $x_{i}(0)~(i=1,\ldots ,m)$ are the same with the above Setting 1. The setting of $r(k)$ is as follows.

Set $r(k)$ at Step 2) as follows: $r(k)={\begin{cases}1&(k^{\star }\leqq k\leqq k^{\star }+2n-1),\\h&(k\geqq k^{\star }+2n),\end{cases}}$ where $k^{\star }$ is an iteration when the center is newly updated at Step 4) and $h={\sqrt[{2n}]{\delta }},\delta \in (0,1)$ such as $\delta =0.5$ . Thus we have to add the following rules about $k^{\star }$ to the Algorithm:

•(Step 1)

k^{\star }=0

.

•(Step 4) If

x^{\star }(k+1)\neq x^{\star }(k)

then

k^{\star }=k+1

.^[4]

Future works

The algorithms with the above settings are deterministic. Thus, incorporating some random operations make this algorithm powerful for global optimization. Cruz-Duarte et al.^[5] demonstrated it by including stochastic disturbances in spiral searching trajectories. However, this door remains open to further studies.
To find an appropriate balance between diversification and intensification spirals depending on the target problem class (including $k_{\max }$ ) is important to enhance the performance.

Extended works

Many extended studies have been conducted on the SPO due to its simple structure and concept; these studies have helped improve its global search performance and proposed novel applications.^[6]^[7]^[8]^[9]^[10]^[11]

Related Research Articles

In statistics, maximum likelihood estimation (MLE) is a method of estimating the parameters of an assumed probability distribution, given some observed data. This is achieved by maximizing a likelihood function so that, under the assumed statistical model, the observed data is most probable. The point in the parameter space that maximizes the likelihood function is called the maximum likelihood estimate. The logic of maximum likelihood is both intuitive and flexible, and as such the method has become a dominant means of statistical inference.

In analytical mechanics, generalized coordinates are a set of parameters used to represent the state of a system in a configuration space. These parameters must uniquely define the configuration of the system relative to a reference state. The generalized velocities are the time derivatives of the generalized coordinates of the system. The adjective "generalized" distinguishes these parameters from the traditional use of the term "coordinate" to refer to Cartesian coordinates.

In linear algebra, a tridiagonal matrix is a band matrix that has nonzero elements only on the main diagonal, the subdiagonal/lower diagonal, and the supradiagonal/upper diagonal. For example, the following matrix is tridiagonal:

The Gauss–Newton algorithm is used to solve non-linear least squares problems, which is equivalent to minimizing a sum of squared function values. It is an extension of Newton's method for finding a minimum of a non-linear function. Since a sum of squares must be nonnegative, the algorithm can be viewed as using Newton's method to iteratively approximate zeroes of the components of the sum, and thus minimizing the sum. In this sense, the algorithm is also an effective method for solving overdetermined systems of equations. It has the advantage that second derivatives, which can be challenging to compute, are not required.

In statistics a minimum-variance unbiased estimator (MVUE) or uniformly minimum-variance unbiased estimator (UMVUE) is an unbiased estimator that has lower variance than any other unbiased estimator for all possible values of the parameter.

In mathematics, differential algebra is, broadly speaking, the area of mathematics consisting in the study of differential equations and differential operators as algebraic objects in view of deriving properties of differential equations and operators without computing the solutions, similarly as polynomial algebras are used for the study of algebraic varieties, which are solution sets of systems of polynomial equations. Weyl algebras and Lie algebras may be considered as belonging to differential algebra.

Covariance matrix adaptation evolution strategy (CMA-ES) is a particular kind of strategy for numerical optimization. Evolution strategies (ES) are stochastic, derivative-free methods for numerical optimization of non-linear or non-convex continuous optimization problems. They belong to the class of evolutionary algorithms and evolutionary computation. An evolutionary algorithm is broadly based on the principle of biological evolution, namely the repeated interplay of variation and selection: in each generation (iteration) new individuals are generated by variation, usually in a stochastic way, of the current parental individuals. Then, some individuals are selected to become the parents in the next generation based on their fitness or objective function value $. Like this, over the generation sequence, individuals with better and better -values are generated.$

Stochastic approximation methods are a family of iterative methods typically used for root-finding problems or for optimization problems. The recursive update rules of stochastic approximation methods can be used, among other things, for solving linear systems when the collected data is corrupted by noise, or for approximating extreme values of functions which cannot be computed directly, but only estimated via noisy observations.

Non-linear least squares is the form of least squares analysis used to fit a set of m observations with a model that is non-linear in n unknown parameters (m ≥ n). It is used in some forms of nonlinear regression. The basis of the method is to approximate the model by a linear one and to refine the parameters by successive iterations. There are many similarities to linear least squares, but also some significant differences. In economic theory, the non-linear least squares method is applied in (i) the probit regression, (ii) threshold regression, (iii) smooth regression, (iv) logistic link regression, (v) Box–Cox transformed regressors ( $).$

The Routh array is a tabular method permitting one to establish the stability of a system using only the coefficients of the characteristic polynomial. Central to the field of control systems design, the Routh–Hurwitz theorem and Routh array emerge by using the Euclidean algorithm and Sturm's theorem in evaluating Cauchy indices.

In statistical decision theory, where we are faced with the problem of estimating a deterministic parameter (vector) $from observations an estimator is called minimax if its maximal risk is minimal among all estimators of . In a sense this means that is an estimator which performs best in the worst possible case allowed in the problem.$

In quantum computing, the quantum phase estimation algorithm is a quantum algorithm to estimate the phase corresponding to an eigenvalue of a given unitary operator. Because the eigenvalues of a unitary operator always have unit modulus, they are characterized by their phase, and therefore the algorithm can be equivalently described as retrieving either the phase or the eigenvalue itself. The algorithm was initially introduced by Alexei Kitaev in 1995.

In coding theory, generalized minimum-distance (GMD) decoding provides an efficient algorithm for decoding concatenated codes, which is based on using an errors-and-erasures decoder for the outer code.

For certain applications in linear algebra, it is useful to know properties of the probability distribution of the largest eigenvalue of a finite sum of random matrices. Suppose $is a finite sequence of random matrices. Analogous to the well-known Chernoff bound for sums of scalars, a bound on the following is sought for a given parameter t :$

<span class="mw-page-title-main">Matrix completion</span>

Matrix completion is the task of filling in the missing entries of a partially observed matrix, which is equivalent to performing data imputation in statistics. A wide range of datasets are naturally organized in matrix form. One example is the movie-ratings matrix, as appears in the Netflix problem: Given a ratings matrix in which each entry $represents the rating of movie by customer, if customer has watched movie and is otherwise missing, we would like to predict the remaining entries in order to make good recommendations to customers on what to watch next. Another example is the document-term matrix: The frequencies of words used in a collection of documents can be represented as a matrix, where each entry corresponds to the number of times the associated term appears in the indicated document.$

In computer science, optimal computing budget allocation (OCBA) is an approach to maximize the overall simulation efficiency for finding an optimal decision. It was introduced in the mid-1990s by Dr. Chun-Hung Chen.

Quantum counting algorithm is a quantum algorithm for efficiently counting the number of solutions for a given search problem. The algorithm is based on the quantum phase estimation algorithm and on Grover's search algorithm.

Pure inductive logic (PIL) is the area of mathematical logic concerned with the philosophical and mathematical foundations of probabilistic inductive reasoning. It combines classical predicate logic and probability theory. Probability values are assigned to sentences of a first-order relational language to represent degrees of belief that should be held by a rational agent. Conditional probability values represent degrees of belief based on the assumption of some received evidence.

In mathematics, the Chambolle-Pock algorithm is an algorithm used to solve convex optimization problems. It was introduced by Antonin Chambolle and Thomas Pock in 2011 and has since become a widely used method in various fields, including image processing, computer vision, and signal processing.

Projection filters are a set of algorithms based on stochastic analysis and information geometry, or the differential geometric approach to statistics, used to find approximate solutions for filtering problems for nonlinear state-space systems. The filtering problem consists of estimating the unobserved signal of a random dynamical system from partial noisy observations of the signal. The objective is computing the probability distribution of the signal conditional on the history of the noise-perturbed observations. This distribution allows for calculations of all statistics of the signal given the history of observations. If this distribution has a density, the density satisfies specific stochastic partial differential equations (SPDEs) called Kushner-Stratonovich equation, or Zakai equation. It is known that the nonlinear filter density evolves in an infinite dimensional function space.

References

↑ Tamura, K.; Yasuda, K. (2011). "Primary Study of Spiral Dynamics Inspired Optimization". IEEJ Transactions on Electrical and Electronic Engineering. 6 (S1): 98–100. doi:10.1002/tee.20628. S2CID 109093423.
↑ Tamura, K.; Yasuda, K. (2011). "Spiral Dynamics Inspired Optimization". Journal of Advanced Computational Intelligence and Intelligent Informatics. 132 (5): 1116–1121. doi: 10.20965/jaciii.2011.p1116 .
1 2 Tamura, K.; Yasuda, K. (2016). "Spiral Optimization Algorithm Using Periodic Descent Directions". SICE Journal of Control, Measurement, and System Integration. 6 (3): 133–143. Bibcode:2016JCMSI...9..134T. doi: 10.9746/jcmsi.9.134 .
1 2 Tamura, K.; Yasuda, K. (2020). "The Spiral Optimization Algorithm: Convergence Conditions and Settings". IEEE Transactions on Systems, Man, and Cybernetics: Systems. 50 (1): 360–375. doi:10.1109/TSMC.2017.2695577. S2CID 126109444.
↑ Cruz-Duarte, Jorge M.; Martin-Diaz, Ignacio; Munoz-Minjares, J. U.; Sanchez-Galindo, Luis A.; Avina-Cervantes, Juan G.; Garcia-Perez, Arturo; Correa-Cely, C. Rodrigo (2017). "Primary study on the stochastic spiral optimization algorithm". 2017 IEEE International Autumn Meeting on Power, Electronics and Computing (ROPEC). pp. 1–6. doi:10.1109/ROPEC.2017.8261609. ISBN 978-1-5386-0819-7. S2CID 37580653.
↑ Nasir, A. N. K.; Tokhi, M. O. (2015). "An improved spiral dynamic optimization algorithm with engineering application". IEEE Transactions on Systems, Man, and Cybernetics: Systems. 45 (6): 943–954. doi:10.1109/tsmc.2014.2383995. S2CID 24253496.
↑ Nasir, A. N. K.; Ismail, R.M.T.R.; Tokhi, M. O. (2016). "Adaptive spiral dynamics metaheuristic algorithm for global optimisation with application to modelling of a flexible system" (PDF). Applied Mathematical Modelling. 40 (9–10): 5442–5461. doi: 10.1016/j.apm.2016.01.002 .
↑ Ouadi, A.; Bentarzi, H.; Recioui, A. (2013). "multiobjective design of digital filters using spiral optimization technique". SpringerPlus. 2 (461): 697–707. doi: 10.1186/2193-1801-2-461 . PMC 3786071 . PMID 24083108.
↑ Benasla, L.; Belmadani, A.; Rahli, M. (2014). "Spiral optimization algorithm for solving combined economic and Emission Dispatch". International Journal of Electrical Power & Energy Systems. 62: 163–174. doi:10.1016/j.ijepes.2014.04.037.
↑ Sidarto, K. A.; Kania, A. (2015). "Finding all solutions of systems of nonlinear equations using spiral dynamics inspired optimization with clustering". Journal of Advanced Computational Intelligence and Intelligent Informatics. 19 (5): 697–707. doi: 10.20965/jaciii.2015.p0697 .
↑ Kaveh, A.; Mahjoubi, S. (October 2019). "Hypotrochoid spiral optimization approach for sizing and layout optimization of truss structures with multiple frequency constraints". Engineering with Computers. 35 (4): 1443–1462. doi:10.1007/s00366-018-0675-6. S2CID 54457145.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[tamura11a-1] Tamura, K.; Yasuda, K. (2011). "Primary Study of Spiral Dynamics Inspired Optimization". IEEJ Transactions on Electrical and Electronic Engineering. 6 (S1): 98–100. doi:10.1002/tee.20628. S2CID 109093423.

[tamura11b-2] Tamura, K.; Yasuda, K. (2011). "Spiral Dynamics Inspired Optimization". Journal of Advanced Computational Intelligence and Intelligent Informatics. 132 (5): 1116–1121. doi: 10.20965/jaciii.2011.p1116 .

[tamura16a-3] 1 2 Tamura, K.; Yasuda, K. (2016). "Spiral Optimization Algorithm Using Periodic Descent Directions". SICE Journal of Control, Measurement, and System Integration. 6 (3): 133–143. Bibcode:2016JCMSI...9..134T. doi: 10.9746/jcmsi.9.134 .

[tamura17a-4] 1 2 Tamura, K.; Yasuda, K. (2020). "The Spiral Optimization Algorithm: Convergence Conditions and Settings". IEEE Transactions on Systems, Man, and Cybernetics: Systems. 50 (1): 360–375. doi:10.1109/TSMC.2017.2695577. S2CID 126109444.

[5] Cruz-Duarte, Jorge M.; Martin-Diaz, Ignacio; Munoz-Minjares, J. U.; Sanchez-Galindo, Luis A.; Avina-Cervantes, Juan G.; Garcia-Perez, Arturo; Correa-Cely, C. Rodrigo (2017). "Primary study on the stochastic spiral optimization algorithm". 2017 IEEE International Autumn Meeting on Power, Electronics and Computing (ROPEC). pp. 1–6. doi:10.1109/ROPEC.2017.8261609. ISBN 978-1-5386-0819-7. S2CID 37580653.

[nasir15a-6] Nasir, A. N. K.; Tokhi, M. O. (2015). "An improved spiral dynamic optimization algorithm with engineering application". IEEE Transactions on Systems, Man, and Cybernetics: Systems. 45 (6): 943–954. doi:10.1109/tsmc.2014.2383995. S2CID 24253496.

[nasir16a-7] Nasir, A. N. K.; Ismail, R.M.T.R.; Tokhi, M. O. (2016). "Adaptive spiral dynamics metaheuristic algorithm for global optimisation with application to modelling of a flexible system" (PDF). Applied Mathematical Modelling. 40 (9–10): 5442–5461. doi: 10.1016/j.apm.2016.01.002 .

[ouadi13a-8] Ouadi, A.; Bentarzi, H.; Recioui, A. (2013). "multiobjective design of digital filters using spiral optimization technique". SpringerPlus. 2 (461): 697–707. doi: 10.1186/2193-1801-2-461 . PMC 3786071 . PMID 24083108.

[benasla14a-9] Benasla, L.; Belmadani, A.; Rahli, M. (2014). "Spiral optimization algorithm for solving combined economic and Emission Dispatch". International Journal of Electrical Power & Energy Systems. 62: 163–174. doi:10.1016/j.ijepes.2014.04.037.

[sidarto15a-10] Sidarto, K. A.; Kania, A. (2015). "Finding all solutions of systems of nonlinear equations using spiral dynamics inspired optimization with clustering". Journal of Advanced Computational Intelligence and Intelligent Informatics. 19 (5): 697–707. doi: 10.20965/jaciii.2015.p0697 .

[KavehMahjoubi-11] Kaveh, A.; Mahjoubi, S. (October 2019). "Hypotrochoid spiral optimization approach for sizing and layout optimization of truss structures with multiple frequency constraints". Engineering with Computers. 35 (4): 1443–1462. doi:10.1007/s00366-018-0675-6. S2CID 54457145.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]