• Previous Article
    A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning
  • JIMO Home
  • This Issue
  • Next Article
    A modified differential evolution based solution technique for economic dispatch problems
October  2012, 8(4): 1039-1056. doi: 10.3934/jimo.2012.8.1039

State transition algorithm

1. 

School of Information Science and Engineering, Central South University, Changsha, 410083, China

Received  March 2011 Revised  April 2012 Published  September 2012

In terms of the concepts of state and state transition, a new heuristic random search algorithm named state transition algorithm is proposed. For continuous function optimization problems, four special transformation operators called rotation, translation, expansion and axesion are designed. Adjusting measures of the transformations are mainly studied to keep the balance of exploration and exploitation. Convergence analysis is also discussed about the algorithm based on random search theory. In the meanwhile, to strengthen the search ability in high dimensional space, communication strategy is introduced into the basic algorithm and intermittent exchange is presented to prevent premature convergence. Finally, experiments are carried out for the algorithms. With 10 common benchmark unconstrained continuous functions used to test the performance, the results show that state transition algorithms are promising algorithms due to their good global search capability and convergence property when compared with some popular algorithms.
Citation: Xiaojun Zhou, Chunhua Yang, Weihua Gui. State transition algorithm. Journal of Industrial & Management Optimization, 2012, 8 (4) : 1039-1056. doi: 10.3934/jimo.2012.8.1039
References:
[1]

G. Albeanu, A monte carlo approach for control search,, Mathematics and Computers in Simulation, 43 (1997), 223.  doi: 10.1016/S0378-4754(96)00069-9.  Google Scholar

[2]

H. A. Abbass, A. M. Bagirov and J. Zhang, The discrete gradient evolutionary strategy method for global optimization,, in, 1 (2003), 435.   Google Scholar

[3]

D. D. Burgess, Rotation in simplex optimization,, Analytica Chimica Acta, 181 (1986), 97.  doi: 10.1016/S0003-2670(00)85224-1.  Google Scholar

[4]

F. V. Berth and A. P. Engelbrecht, A study of particle swarm optimization particle trajectories,, Information Sciences, 176 (2006), 937.  doi: 10.1016/j.ins.2005.02.003.  Google Scholar

[5]

P. Collet and J. P. Rennard, "Stochastic Optimization Algorithms,", Handbook of Research on Nature Inspired Computing for Economics and Management, (2006).   Google Scholar

[6]

K. Deb and R. B. Agrawal, Simulated binary crossover for continuous search space,, Complex Systems, 9 (1995), 115.   Google Scholar

[7]

R. C. Eberhart and Y. H. Shi, Comparison between genetic algorithms and particle swarm optimization,, in, (1998), 611.   Google Scholar

[8]

D. E. Goldberg, "Genetic Algorithms in Search, Optimization, and Machine Learning,", Reading: Addison-Wesley, (1989).   Google Scholar

[9]

C. Hamzacebi and F. Kutay, A heuristic approach for finding the global minimum: Adaptive random search technique,, Applied Mathematics and Computation, 173 (2006), 1323.  doi: 10.1016/j.amc.2005.05.002.  Google Scholar

[10]

C. Hamzacebi and F. Kutay, Continous functions minimization by dynamic random search technique,, Applied Mathematical Modeling, 31 (2007), 2189.  doi: 10.1016/j.apm.2006.08.015.  Google Scholar

[11]

R. Hooke and T. A. Jeeves, Direct search solution of numerical and statistical problems,, Journal of the Association for Computing Machinery(ACM), 8 (1961), 212.   Google Scholar

[12]

J. Kennedy and R. C. Eberhart, Particle swarm optimization,, in, (1995), 1942.   Google Scholar

[13]

J. C. Lagarias, J. A. Reeds, M. H. Wright and P. E. Wright, Convergence properties of the Nelder-Mead simplex method in low dimensions,, SIAM J. OPTIM., 9 (1998), 112.   Google Scholar

[14]

J. J. Liang, A. K. Qin, P. N. Suganthan and S. Baskar, Comprehensive learning particle swarm optimizer for global optimization of multimodal functions,, IEEE Transaction on Evolutionary Computation, 10 (2006), 281.   Google Scholar

[15]

J. Y. Li and R. R. Rhinehart, Heuristic random optimization,, Computers and Chemical Engineering, 22 (1998), 427.   Google Scholar

[16]

T. W. Leung, C. K. Chan and M. D. Troutt, A mixed simulated annealing-genetic algorithm approach to the multi-buyer multi-item joint replenishment problem: advantages of meta-heuristics,, Journal of Industrial and Management Optimization, 4 (2008), 53.   Google Scholar

[17]

J. Matyas, Random optimization,, Automation and Remote Control, 26 (1965), 246.   Google Scholar

[18]

Z. Michalewicz, A modified genetic algorithm for optimal control problems,, Computers Math. Applic, 23 (1992), 83.  doi: 10.1016/0898-1221(92)90094-X.  Google Scholar

[19]

J. A. Nelder and R. Mead, A simplex method for function minimization,, Computer Journal, 7 (1965), 308.   Google Scholar

[20]

A. K. Qin, V. L. Huang, and P. N. Suganthan, Differential evolution algorithm with strategy adaptation for global numerical optimization,, IEEE Transactions on Evolutionary Computation, 13 (2009), 398.   Google Scholar

[21]

G. Rudolph, Convergence analysis of canonical genetic algorithms,, IEEE Transactions on Neural Networks, 5 (1994), 96.   Google Scholar

[22]

D. W. Stroock, "An Introduction to Markov Processes,", Beijing: World Publishing Corporation, (2009).   Google Scholar

[23]

F. J. Solis and R. J. B. Wets, Minimization by random search techniques,, Mathematics of Operations Research, 6 (1981), 19.   Google Scholar

[24]

R. Storn and K. V. Price, Differential evolutionary-A simple and efficient heuristic for global optimization over continous spaces,, Journal of Global Optimization, 11 (1997), 341.  doi: 10.1023/A:1008202821328.  Google Scholar

[25]

Y. H. Shi and R. C. Eberhart, Empirical study of particle swarm optimization,, in, (2001), 1945.   Google Scholar

[26]

T. D. Tran and G. G. Jin, Real-coded genetic algorithm benchmarked on noiseless black-box optimization testbed,, in, (2010), 1731.   Google Scholar

[27]

A. H. Wright, Genetic algorithms for real parameter optimization,, in, (1991), 205.   Google Scholar

[28]

D. H. Wolpert and W. G. Macready, No free lunch theorems for optimization,, IEEE Transactions on Evolutionary Computation, 1 (1997), 67.   Google Scholar

[29]

K. F. C. Yiu, Y. Liu and K. L. Teo, A hybrid descent method for global optimization,, Journal of Global Optimization, 28 (2004), 229.  doi: 10.1023/B:JOGO.0000015313.93974.b0.  Google Scholar

[30]

X. S. Yang, "Engineering Optimization: An Introduction with Metaheuristic Applications,", Wiley, (2010).   Google Scholar

[31]

Y. X. Yuan, "Nonlinear Optimization Calculation Method,", Beijing: Science press, (2008).   Google Scholar

[32]

T. Zhang, Y. J. Zhang, Q. P. Zheng and P. M. Pardalos, A hybrid particle swarm optimization and tabu search algorithm for order planning problems of steel factories on the make-to-stock and make-to-order management architecture,, Journal of Industrial and Management Optimization, 7 (2011), 31.   Google Scholar

[33]

X. J. Zhou, C. H. Yang and W. H. Gui, Initial version of state transition algorithm,, in, (2011), 644.   Google Scholar

[34]

X. J. Zhou, C. H. Yang and W. H. Gui, A new transformation into state transition algorithm for finding the global minimum,, in, (2011), 674.   Google Scholar

show all references

References:
[1]

G. Albeanu, A monte carlo approach for control search,, Mathematics and Computers in Simulation, 43 (1997), 223.  doi: 10.1016/S0378-4754(96)00069-9.  Google Scholar

[2]

H. A. Abbass, A. M. Bagirov and J. Zhang, The discrete gradient evolutionary strategy method for global optimization,, in, 1 (2003), 435.   Google Scholar

[3]

D. D. Burgess, Rotation in simplex optimization,, Analytica Chimica Acta, 181 (1986), 97.  doi: 10.1016/S0003-2670(00)85224-1.  Google Scholar

[4]

F. V. Berth and A. P. Engelbrecht, A study of particle swarm optimization particle trajectories,, Information Sciences, 176 (2006), 937.  doi: 10.1016/j.ins.2005.02.003.  Google Scholar

[5]

P. Collet and J. P. Rennard, "Stochastic Optimization Algorithms,", Handbook of Research on Nature Inspired Computing for Economics and Management, (2006).   Google Scholar

[6]

K. Deb and R. B. Agrawal, Simulated binary crossover for continuous search space,, Complex Systems, 9 (1995), 115.   Google Scholar

[7]

R. C. Eberhart and Y. H. Shi, Comparison between genetic algorithms and particle swarm optimization,, in, (1998), 611.   Google Scholar

[8]

D. E. Goldberg, "Genetic Algorithms in Search, Optimization, and Machine Learning,", Reading: Addison-Wesley, (1989).   Google Scholar

[9]

C. Hamzacebi and F. Kutay, A heuristic approach for finding the global minimum: Adaptive random search technique,, Applied Mathematics and Computation, 173 (2006), 1323.  doi: 10.1016/j.amc.2005.05.002.  Google Scholar

[10]

C. Hamzacebi and F. Kutay, Continous functions minimization by dynamic random search technique,, Applied Mathematical Modeling, 31 (2007), 2189.  doi: 10.1016/j.apm.2006.08.015.  Google Scholar

[11]

R. Hooke and T. A. Jeeves, Direct search solution of numerical and statistical problems,, Journal of the Association for Computing Machinery(ACM), 8 (1961), 212.   Google Scholar

[12]

J. Kennedy and R. C. Eberhart, Particle swarm optimization,, in, (1995), 1942.   Google Scholar

[13]

J. C. Lagarias, J. A. Reeds, M. H. Wright and P. E. Wright, Convergence properties of the Nelder-Mead simplex method in low dimensions,, SIAM J. OPTIM., 9 (1998), 112.   Google Scholar

[14]

J. J. Liang, A. K. Qin, P. N. Suganthan and S. Baskar, Comprehensive learning particle swarm optimizer for global optimization of multimodal functions,, IEEE Transaction on Evolutionary Computation, 10 (2006), 281.   Google Scholar

[15]

J. Y. Li and R. R. Rhinehart, Heuristic random optimization,, Computers and Chemical Engineering, 22 (1998), 427.   Google Scholar

[16]

T. W. Leung, C. K. Chan and M. D. Troutt, A mixed simulated annealing-genetic algorithm approach to the multi-buyer multi-item joint replenishment problem: advantages of meta-heuristics,, Journal of Industrial and Management Optimization, 4 (2008), 53.   Google Scholar

[17]

J. Matyas, Random optimization,, Automation and Remote Control, 26 (1965), 246.   Google Scholar

[18]

Z. Michalewicz, A modified genetic algorithm for optimal control problems,, Computers Math. Applic, 23 (1992), 83.  doi: 10.1016/0898-1221(92)90094-X.  Google Scholar

[19]

J. A. Nelder and R. Mead, A simplex method for function minimization,, Computer Journal, 7 (1965), 308.   Google Scholar

[20]

A. K. Qin, V. L. Huang, and P. N. Suganthan, Differential evolution algorithm with strategy adaptation for global numerical optimization,, IEEE Transactions on Evolutionary Computation, 13 (2009), 398.   Google Scholar

[21]

G. Rudolph, Convergence analysis of canonical genetic algorithms,, IEEE Transactions on Neural Networks, 5 (1994), 96.   Google Scholar

[22]

D. W. Stroock, "An Introduction to Markov Processes,", Beijing: World Publishing Corporation, (2009).   Google Scholar

[23]

F. J. Solis and R. J. B. Wets, Minimization by random search techniques,, Mathematics of Operations Research, 6 (1981), 19.   Google Scholar

[24]

R. Storn and K. V. Price, Differential evolutionary-A simple and efficient heuristic for global optimization over continous spaces,, Journal of Global Optimization, 11 (1997), 341.  doi: 10.1023/A:1008202821328.  Google Scholar

[25]

Y. H. Shi and R. C. Eberhart, Empirical study of particle swarm optimization,, in, (2001), 1945.   Google Scholar

[26]

T. D. Tran and G. G. Jin, Real-coded genetic algorithm benchmarked on noiseless black-box optimization testbed,, in, (2010), 1731.   Google Scholar

[27]

A. H. Wright, Genetic algorithms for real parameter optimization,, in, (1991), 205.   Google Scholar

[28]

D. H. Wolpert and W. G. Macready, No free lunch theorems for optimization,, IEEE Transactions on Evolutionary Computation, 1 (1997), 67.   Google Scholar

[29]

K. F. C. Yiu, Y. Liu and K. L. Teo, A hybrid descent method for global optimization,, Journal of Global Optimization, 28 (2004), 229.  doi: 10.1023/B:JOGO.0000015313.93974.b0.  Google Scholar

[30]

X. S. Yang, "Engineering Optimization: An Introduction with Metaheuristic Applications,", Wiley, (2010).   Google Scholar

[31]

Y. X. Yuan, "Nonlinear Optimization Calculation Method,", Beijing: Science press, (2008).   Google Scholar

[32]

T. Zhang, Y. J. Zhang, Q. P. Zheng and P. M. Pardalos, A hybrid particle swarm optimization and tabu search algorithm for order planning problems of steel factories on the make-to-stock and make-to-order management architecture,, Journal of Industrial and Management Optimization, 7 (2011), 31.   Google Scholar

[33]

X. J. Zhou, C. H. Yang and W. H. Gui, Initial version of state transition algorithm,, in, (2011), 644.   Google Scholar

[34]

X. J. Zhou, C. H. Yang and W. H. Gui, A new transformation into state transition algorithm for finding the global minimum,, in, (2011), 674.   Google Scholar

[1]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005

[2]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014

[3]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[4]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122

[5]

Bing Yu, Lei Zhang. Global optimization-based dimer method for finding saddle points. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 741-753. doi: 10.3934/dcdsb.2020139

[6]

Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2021, 15 (1) : 113-130. doi: 10.3934/amc.2020046

[7]

Emre Esentürk, Juan Velazquez. Large time behavior of exchange-driven growth. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 747-775. doi: 10.3934/dcds.2020299

[8]

Maicon Sônego. Stable transition layers in an unbalanced bistable equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020370

[9]

Puneet Pasricha, Anubha Goel. Pricing power exchange options with hawkes jump diffusion processes. Journal of Industrial & Management Optimization, 2021, 17 (1) : 133-149. doi: 10.3934/jimo.2019103

[10]

Tian Ma, Shouhong Wang. Topological phase transition III: Solar surface eruptions and sunspots. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 501-514. doi: 10.3934/dcdsb.2020350

[11]

Timothy Chumley, Renato Feres. Entropy production in random billiards. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1319-1346. doi: 10.3934/dcds.2020319

[12]

Chao Xing, Jiaojiao Pan, Hong Luo. Stability and dynamic transition of a toxin-producing phytoplankton-zooplankton model with additional food. Communications on Pure & Applied Analysis, 2021, 20 (1) : 427-448. doi: 10.3934/cpaa.2020275

[13]

Yuanshi Wang. Asymmetric diffusion in a two-patch mutualism system characterizing exchange of resource for resource. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 963-985. doi: 10.3934/dcdsb.2020149

[14]

Editorial Office. Retraction: Jinling Wei, Jinming Zhang, Meishuang Dong, Fan Zhang, Yunmo Chen, Sha Jin and Zhike Han, Applications of mathematics to maritime search. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 957-957. doi: 10.3934/dcdss.2019064

[15]

Dominique Chapelle, Philippe Moireau, Patrick Le Tallec. Robust filtering for joint state-parameter estimation in distributed mechanical systems. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 65-84. doi: 10.3934/dcds.2009.23.65

[16]

Patrick W. Dondl, Martin Jesenko. Threshold phenomenon for homogenized fronts in random elastic media. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 353-372. doi: 10.3934/dcdss.2020329

[17]

Min Xi, Wenyu Sun, Jun Chen. Survey of derivative-free optimization. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 537-555. doi: 10.3934/naco.2020050

[18]

Shiqi Ma. On recent progress of single-realization recoveries of random Schrödinger systems. Electronic Research Archive, , () : -. doi: 10.3934/era.2020121

[19]

Pablo D. Carrasco, Túlio Vales. A symmetric Random Walk defined by the time-one map of a geodesic flow. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020390

[20]

Bixiang Wang. Mean-square random invariant manifolds for stochastic differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1449-1468. doi: 10.3934/dcds.2020324

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (79)
  • HTML views (0)
  • Cited by (52)

Other articles
by authors

[Back to Top]