Spiral optimization algorithm

Short description: Optimization algorithm

The spiral shares the global (blue) and intensive (red) behavior

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]

## Contents

* 1 Metaphor
* 2 Algorithm
* 3 Setting
* 3.1 Setting 1 (Periodic Descent Direction Setting)
* 3.2 Setting 2 (Convergence Setting)
* 4 Future works
* 5 Extended works
* 6 References

## 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

Spiral Optimization (SPO) 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 kmax (termination criterion) is as follows:

0) Set the number of search points m≥2 and the maximum iteration number kmax.
1) Place the initial search points xi(0)∈ℝn(i=1,…,m) and determine the center x⋆(0)=xib(0), ib=argmini=1,…,m{f(xi(0))}, and then set k=0.
2) Decide the step rate r(k) by a rule.
3) Update the search points: xi(k+1)=x⋆(k)+r(k)R(θ)(xi(k)−x⋆(k))(i=1,…,m).
4) Update the center: x⋆(k+1)={xib(k+1)(if f(xib(k+1))<f(x⋆(k))),x⋆(k)(otherwise), where ib=argmini=1,…,m{f(xi(k+1))}.
5) Set k:=k+1. If k=kmax is satisfied then terminate and output x⋆(k). Otherwise, return to Step 2).

## Setting

The search performance depends on setting the composite rotation matrix R(θ), the step rate r(k), and the initial points xi(0)(i=1,…,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 kmax. The conditions on R(θ) and xi(0)(i=1,…,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 kmax.

* Set R(θ) as follows:R(θ)=[0n−1⊤−1In−10n−1] where In−1 is the (n−1)×(n−1) identity matrix and 0n−1 is the (n−1)×1 zero vector.
* Place the initial points xi(0)∈ℝn (i=1,…,m) at random to satisfy the following condition:

mini=1,…,m{maxj=1,…,m{rank[dj,i(0)R(θ)dj,i(0)⋯R(θ)2n−1dj,i(0)]}}=n where dj,i(0)=xj(0)−xi(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=δkmax(constant value) where a sufficiently small δ>0 such as δ=1/kmax or δ=10−3.[3]

### Setting 2 (Convergence Setting)

This setting ensures that the SPO algorithm converges to a stationary point under the maximum iteration kmax=∞. The settings of R(θ) and the initial points xi(0)(i=1,…,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)={1(k⋆≦k≦k⋆+2n−1),h(k≧k⋆+2n), where k⋆ is an iteration when the center is newly updated at Step 4) and h=δ2n,δ∈(0,1) such as δ=0.5. Thus we have to add the following rules about k⋆ to the Algorithm:

•(Step 1) k⋆=0.
•(Step 4) If x⋆(k+1)≠x⋆(k) then k⋆=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 kmax) 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]

## References

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.
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.
3. ↑ 3.0 3.1 Tamura, K.; Yasuda, K. (2016). "Spiral Optimization Algorithm Using Periodic Descent Directions". SICE Journal of Control, Measurement, and System Integration 6 (3): 133–143. doi:10.9746/jcmsi.9.134. Bibcode: 2016JCMSI...9..134T. https://www.jstage.jst.go.jp/article/jcmsi/9/3/9_134/_pdf.
4. ↑ 4.0 4.1 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.
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. https://doi.org/10.1109/ROPEC.2017.8261609.
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.
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". Applied Mathematical Modelling 40 (9–10): 5442–5461. doi:10.1016/j.apm.2016.01.002. http://umpir.ump.edu.my/id/eprint/16770/7/Adaptive Spiral Dynamics Metaheuristic Algorithm For Global Optimisation With Application To Modelling Of A Flexible System.pdf.
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. PMID 24083108.
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. Bibcode: 2014IJEPE..62..163B.
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.
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.

* v
* t
* e

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear

| … functions|

* Golden-section search
* Interpolation methods
* Line search
* Nelder–Mead method
* Successive parabolic interpolation

|

… and gradients|

| Convergence|

* Trust region
* Wolfe conditions

|

Quasi–Newton|

* Berndt–Hall–Hall–Hausman
* Broyden–Fletcher–Goldfarb–Shanno and L-BFGS
* Davidon–Fletcher–Powell
* Symmetric rank-one (SR1)

Other methods|

* Gauss–Newton
* Gradient
* Levenberg–Marquardt
* Conjugate gradient
* Truncated Newton

… and Hessians|

* Newton's method

Optimization computes maxima and minima.

Constrained nonlinear

| General|

* Barrier methods
* Penalty methods

|

Differentiable|

* Augmented Lagrangian methods
* Sequential quadratic programming
* Successive linear programming

Convex optimization

| Convex
minimization|

* Cutting-plane method
* Reduced gradient (Frank–Wolfe)
* Subgradient method

|

Linear and
quadratic|

| Interior point|

* Affine scaling
* Ellipsoid algorithm of Khachiyan
* Projective algorithm of Karmarkar

|

Basis-exchange|

* Simplex algorithm of Dantzig
* Revised simplex algorithm
* Criss-cross algorithm
* Principal pivoting algorithm of Lemke

Combinatorial

| Paradigms|

* Approximation algorithm
* Dynamic programming
* Greedy algorithm
* Integer programming
* Branch and bound/cut

|

Graph
algorithms|

| Minimum
spanning tree|

* Borůvka
* Prim
* Kruskal

|

* Bellman–Ford
* Dijkstra
* Floyd–Warshall

Network flows|

* Dinic
* Edmonds–Karp
* Ford–Fulkerson
* Push–relabel maximum flow

Metaheuristics

* Evolutionary algorithm
* Hill climbing
* Local search
* Simulated annealing
* Tabu search

* Software

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Spiral optimization algorithm. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Spiral_optimization_algorithm&oldid=4349966"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template