In mathematics, the spiral optimization (SPO) algorithm is a metaheuristic inspired by

spiral In mathematics, a spiral is a curve which emanates from a point, moving farther away as it revolves around the point. Helices Two major definitions of "spiral" in the American Heritage Dictionary are:two-dimensional unconstrained optimization 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. There are effective settings for the SPO algorithm: the periodic descent direction setting and the convergence setting.

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_

(termination criterion) is as follows: 0) Set the number of search points

m\geq 2

and the maximum iteration number

k_

. 1) Place the initial search points

x_i (0) \in \mathbb^n~(i=1, \ldots, m)

and determine the center

x^(0)= x_(0)

\displaystyle i_\text =\mathop_ \

,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^(k) + r(k) R(\theta) (x_i(k) - x^(k))\quad(i=1, \ldots, m).

4) Update the center:

x^(k+1) =
 \begin
 x_(k+1) & \big( \text f(x_(k+1)) < f(x^(k)) \big),\\
 x^(k) & \big(\text \big),
 \end

where

\displaystyle i_\text = \mathop_ \

. 5) Set

k := k+1

. If

k=k_

is satisfied then terminate and output

x^(k)

. Otherwise, return to Step 2).

Setting

The search performance depends on setting the composite

rotation matrix In linear algebra, a rotation matrix is a transformation matrix that is used to perform a rotation in Euclidean space. For example, using the convention below, the matrix :R = \begin \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end ...

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_

. 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_

. * Set

R(\theta)

as follows:

R(\theta) = \begin
0_^\top &-1\\
I_& 0_\\
\end

where

I_

is the

(n-1)\times (n-1)

identity matrix and

0_

is the

(n-1)\times 1

zero vector. * Place the initial points

x_i(0) \in \mathbb^n

(i = 1,\ldots, m)

at random to satisfy the following condition:

\min_ \ = n

where

d_(0) = x_(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:

~~~\text

where a sufficiently small

\delta > 0

such as

\delta = 1/k_

\delta = 10^

Setting 2 (Convergence Setting)

This setting ensures that the SPO algorithm converges to a stationary point under the maximum iteration

k_ = \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
1 & (k^\star \leqq k \leqq  k^\star + 2n-1), \\
h & (k \geqq k^\star + 2n),
\end

where

k^\star

is an iteration when the center is newly updated at Step 4) and

\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^(k+1)\neq x^(k)

then

k^\star = k+1

Future works

* The algorithms with the above settings are

deterministic Determinism is a philosophical view, where all events are determined completely by previously existing causes. Deterministic theories throughout the history of philosophy have developed from diverse and sometimes overlapping motives and consi ...

. Thus, incorporating some random operations make this algorithm powerful for

global optimization Global optimization is a branch of applied mathematics and numerical analysis that attempts to find the global minima or maxima of a function or a set of functions on a given set. It is usually described as a minimization problem because the max ...

. Cruz-Duarte et al.Cruz-Duarte, J. M., Martin-Diaz, I., Munoz-Minjares, J. U., Sanchez-Galindo, L. A., Avina-Cervantes, J. G., Garcia-Perez, A., & Correa-Cely, C. R. (2017). Primary study on the stochastic spiral optimization algorithm. 2017 IEEE International Autumn Meeting on Power, Electronics and Computing (ROPEC), 1–6. https://doi.org/10.1109/ROPEC.2017.8261609 demonstrated it by including

stochastic Stochastic (, ) refers to the property of being well described by a random probability distribution. Although stochasticity and randomness are distinct in that the former refers to a modeling approach and the latter refers to phenomena themselv ...

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_

) 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.

References

{{Reflist, refs= {{cite journal , last1=Kaveh , first1=A. , last2=Mahjoubi , first2=S. , title=Hypotrochoid spiral optimization approach for sizing and layout optimization of truss structures with multiple frequency constraints , journal=Engineering with Computers , date=October 2019 , volume=35 , issue=4 , pages=1443–1462 , doi= 10.1007/s00366-018-0675-6, s2cid=54457145 , url=https://www.semanticscholar.org/paper/b6cf0fd9584d8c02a72139bed14312f9d0d0ef62

References

{{cite journal , last1 = Tamura , first1 = K. , last2 = Yasuda , first2 = K. , title = Primary Study of Spiral Dynamics Inspired Optimization , journal = IEEJ Transactions on Electrical and Electronic Engineering , year=2011 , volume=6 , issue=S1 , pages=98–100 , doi=10.1002/tee.20628 , s2cid = 109093423 , url= {{cite journal , last1 = Tamura , first1 = K. , last2 = Yasuda , first2 = K. , title = Spiral Dynamics Inspired Optimization , journal = Journal of Advanced Computational Intelligence and Intelligent Informatics , year = 2011 , volume = 132 , issue = 5 , pages = 1116–1121 , doi=10.20965/jaciii.2011.p1116 , url= , doi-access = free {{cite journal , last1 = Tamura , first1 = K. , last2 = Yasuda , first2 = K. , title = Spiral Optimization Algorithm Using Periodic Descent Directions , journal = SICE Journal of Control, Measurement, and System Integration , year = 2016 , volume = 6 , issue = 3 , pages = 133–143 , doi=10.9746/jcmsi.9.134 , url=https://www.jstage.jst.go.jp/article/jcmsi/9/3/9_134/_pdf , bibcode = 2016JCMSI...9..134T , doi-access = free {{cite journal , last1 = Tamura , first1 = K. , last2 = Yasuda , first2 = K. , title = The Spiral Optimization Algorithm: Convergence Conditions and Settings , journal = IEEE Transactions on Systems, Man, and Cybernetics: Systems , year = 2020 , volume = 50 , issue = 1 , pages = 360–375 , doi = 10.1109/TSMC.2017.2695577 , s2cid = 126109444 , url = https://www.semanticscholar.org/paper/7b7d76b8b030b15f8d5fbf3ff8fb1bd33405c538 {{cite journal , last1 = Nasir , first1 = A. N. K. , last2 = Tokhi , first2 = M. O. , title = An improved spiral dynamic optimization algorithm with engineering application , journal = IEEE Trans. Syst.,Man, Cybern., Syst. , year = 2015 , volume = 45 , issue = 6 , pages = 943–954 , doi=10.1109/tsmc.2014.2383995 , s2cid = 24253496 , url= {{cite journal , last1 = Nasir , first1 = A. N. K. , last2 = Ismail , first2 = R.M.T.R. , last3 = Tokhi , first3 = M. O. , title = Adaptive spiral dynamics metaheuristic algorithm for global optimisation with application to modelling of a flexible system, journal = Appl. Math. Modell. , year = 2016 , volume = 40 , issue = 9–10 , pages = 5442–5461 , doi=10.1016/j.apm.2016.01.002 , url=http://umpir.ump.edu.my/id/eprint/16770/7/Adaptive%20Spiral%20Dynamics%20Metaheuristic%20Algorithm%20For%20Global%20Optimisation%20With%20Application%20To%20Modelling%20Of%20A%20Flexible%20System.pdf , doi-access = free {{cite journal , last1 = Ouadi , first1 = A. , last2 = Bentarzi , first2 = H. , last3 = Recioui , first3 = A. , title = multiobjective design of digital filters using spiral optimization technique , journal = SpringerPlus , year = 2013 , volume = 2 , issue = 461 , pages = 697–707 , doi=10.1186/2193-1801-2-461 , pmid = 24083108 , pmc = 3786071 , url= {{cite journal , last1 = Benasla , first1 = L. , last2 = Belmadani , first2 = A. , last3 = Rahli , first3 = M. , title = Spiral optimization algorithm for solving combined economic and Emission Dispatch , journal = Int. J. Elect. Power & Energy Syst. , year = 2014 , volume = 62 , pages = 163–174 , doi=10.1016/j.ijepes.2014.04.037 , url= {{cite journal , last1 = Sidarto , first1 = K. A. , last2 = Kania , first2 = A. , title = Finding all solutions of systems of nonlinear equations using spiral dynamics inspired optimization with clustering , journal = Journal of Advanced Computational Intelligence and Intelligent Informatics , volume = 19 , issue = 5 , pages = 697–707 , doi=10.20965/jaciii.2015.p0697 , url= , year = 2015 , doi-access = free Collective intelligence Multi-agent systems Evolutionary algorithms Optimization algorithms and methods