• 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]

Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018142

[2]

Leong-Kwan Li, Sally Shao. Convergence analysis of the weighted state space search algorithm for recurrent neural networks. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 193-207. doi: 10.3934/naco.2014.4.193

[3]

Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015

[4]

Mohamed A. Tawhid, Ahmed F. Ali. An effective hybrid firefly algorithm with the cuckoo search for engineering optimization problems. Mathematical Foundations of Computing, 2018, 1 (4) : 349-368. doi: 10.3934/mfc.2018017

[5]

Leong-Kwan Li, Sally Shao, K. F. Cedric Yiu. Nonlinear dynamical system modeling via recurrent neural networks and a weighted state space search algorithm. Journal of Industrial & Management Optimization, 2011, 7 (2) : 385-400. doi: 10.3934/jimo.2011.7.385

[6]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177

[7]

Chunlin Hao, Xinwei Liu. Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 19-29. doi: 10.3934/naco.2012.2.19

[8]

Tao Zhang, Yue-Jie Zhang, Qipeng P. Zheng, P. M. Pardalos. A hybrid particle swarm optimization and tabu search algorithm for order planning problems of steel factories based on the Make-To-Stock and Make-To-Order management architecture. Journal of Industrial & Management Optimization, 2011, 7 (1) : 31-51. doi: 10.3934/jimo.2011.7.31

[9]

Qiang Long, Changzhi Wu. A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1279-1296. doi: 10.3934/jimo.2014.10.1279

[10]

Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial & Management Optimization, 2019, 15 (1) : 235-259. doi: 10.3934/jimo.2018041

[11]

Yaofeng Su. Almost surely invariance principle for non-stationary and random intermittent dynamical systems. Discrete & Continuous Dynamical Systems - A, 2019, 39 (11) : 6585-6597. doi: 10.3934/dcds.2019286

[12]

Ming-Jong Yao, Tien-Cheng Hsu. An efficient search algorithm for obtaining the optimal replenishment strategies in multi-stage just-in-time supply chain systems. Journal of Industrial & Management Optimization, 2009, 5 (1) : 11-32. doi: 10.3934/jimo.2009.5.11

[13]

Abdel-Rahman Hedar, Ahmed Fouad Ali, Taysir Hassan Abdel-Hamid. Genetic algorithm and Tabu search based methods for molecular 3D-structure prediction. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 191-209. doi: 10.3934/naco.2011.1.191

[14]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703

[15]

Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-34. doi: 10.3934/jimo.2019030

[16]

Zhong Wan, Chaoming Hu, Zhanlu Yang. A spectral PRP conjugate gradient methods for nonconvex optimization problem based on modified line search. Discrete & Continuous Dynamical Systems - B, 2011, 16 (4) : 1157-1169. doi: 10.3934/dcdsb.2011.16.1157

[17]

Mingyong Lai, Xiaojiao Tong. A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search. Journal of Industrial & Management Optimization, 2012, 8 (2) : 469-484. doi: 10.3934/jimo.2012.8.469

[18]

Xiangyu Gao, Yong Sun. A new heuristic algorithm for laser antimissile strategy optimization. Journal of Industrial & Management Optimization, 2012, 8 (2) : 457-468. doi: 10.3934/jimo.2012.8.457

[19]

Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2019, 15 (2) : 909-932. doi: 10.3934/jimo.2018077

[20]

Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial & Management Optimization, 2019, 15 (4) : 2009-2021. doi: 10.3934/jimo.2018134

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (12)
  • HTML views (0)
  • Cited by (24)

Other articles
by authors

[Back to Top]