State transition algorithm

Xiaojun Zhou; Chunhua Yang; Weihua Gui

doi:10.3934/jimo.2012.8.1039

Article Contents

2012, Volume 8, Issue 4: 1039-1056. Doi: 10.3934/jimo.2012.8.1039

This issue Previous Article A modified differential evolution based solution technique for economic dispatch problems Next Article A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning

State transition algorithm

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

Received: February 28, 2011

Revised: March 31, 2012

Published: September 2012

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: 90C26, 90C30, 90C59.

Citation:

Related Papers

Cited by

References

[1]	G. Albeanu, A monte carlo approach for control search, Mathematics and Computers in Simulation, 43 (1997), 223-228.doi: 10.1016/S0378-4754(96)00069-9.
[2]	H. A. Abbass, A. M. Bagirov and J. Zhang, The discrete gradient evolutionary strategy method for global optimization, in "Proceedings of IEEE Congress on Evolutionary Computation," 1 (2003), 435-442.
[3]	D. D. Burgess, Rotation in simplex optimization, Analytica Chimica Acta, 181 (1986), 97-106.doi: 10.1016/S0003-2670(00)85224-1.
[4]	F. V. Berth and A. P. Engelbrecht, A study of particle swarm optimization particle trajectories, Information Sciences, 176 (2006), 937-971.doi: 10.1016/j.ins.2005.02.003.
[5]	P. Collet and J. P. Rennard, "Stochastic Optimization Algorithms," Handbook of Research on Nature Inspired Computing for Economics and Management, 2006.
[6]	K. Deb and R. B. Agrawal, Simulated binary crossover for continuous search space, Complex Systems, 9 (1995), 115-148.
[7]	R. C. Eberhart and Y. H. Shi, Comparison between genetic algorithms and particle swarm optimization, in "Annual Conference on Evolutionary Programming," San Diego, (1998), 611-616.
[8]	D. E. Goldberg, "Genetic Algorithms in Search, Optimization, and Machine Learning," Reading: Addison-Wesley, 1989.
[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-1333.doi: 10.1016/j.amc.2005.05.002.
[10]	C. Hamzacebi and F. Kutay, Continous functions minimization by dynamic random search technique, Applied Mathematical Modeling, 31 (2007), 2189-2198.doi: 10.1016/j.apm.2006.08.015.
[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-229.
[12]	J. Kennedy and R. C. Eberhart, Particle swarm optimization, in "Proceedings of IEEE International Conference on Neural Networks," IEEE Service Center, Piscataway, NJ, (1995), 1942-1948.
[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-147.
[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-295.
[15]	J. Y. Li and R. R. Rhinehart, Heuristic random optimization, Computers and Chemical Engineering, 22 (1998), 427-444.
[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-66.
[17]	J. Matyas, Random optimization, Automation and Remote Control, 26 (1965), 246-253.
[18]	Z. Michalewicz, A modified genetic algorithm for optimal control problems, Computers Math. Applic, 23 (1992), 83-94.doi: 10.1016/0898-1221(92)90094-X.
[19]	J. A. Nelder and R. Mead, A simplex method for function minimization, Computer Journal, 7 (1965), 308-313.
[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-417.
[21]	G. Rudolph, Convergence analysis of canonical genetic algorithms, IEEE Transactions on Neural Networks, 5 (1994), 96-101.
[22]	D. W. Stroock, "An Introduction to Markov Processes," Beijing: World Publishing Corporation, 2009.
[23]	F. J. Solis and R. J. B. Wets, Minimization by random search techniques, Mathematics of Operations Research, 6 (1981), 19-30.
[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-359.doi: 10.1023/A:1008202821328.
[25]	Y. H. Shi and R. C. Eberhart, Empirical study of particle swarm optimization, in "Proceedings of the IEEE Congress on Evolutionary Computation," IEEE Press, Seoul, Korea, (2001), 1945-1950.
[26]	T. D. Tran and G. G. Jin, Real-coded genetic algorithm benchmarked on noiseless black-box optimization testbed, in "Workshop Proceedings of the Genetic and Evolutionary Computation Conference," (2010), 1731-1738.
[27]	A. H. Wright, Genetic algorithms for real parameter optimization, in "Foundations of Genetic Algorithms" (Ed. G. J. E. Rawlins), (1991), 205-220.
[28]	D. H. Wolpert and W. G. Macready, No free lunch theorems for optimization, IEEE Transactions on Evolutionary Computation, 1 (1997), 67-82.
[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-238.doi: 10.1023/B:JOGO.0000015313.93974.b0.
[30]	X. S. Yang, "Engineering Optimization: An Introduction with Metaheuristic Applications," Wiley, 2010.
[31]	Y. X. Yuan, "Nonlinear Optimization Calculation Method," Beijing: Science press, 2008.
[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-51.
[33]	X. J. Zhou, C. H. Yang and W. H. Gui, Initial version of state transition algorithm, in "the 2nd International Conference on Digital Manufacturing and Automation(ICDMA)," (2011), 644-647.
[34]	X. J. Zhou, C. H. Yang and W. H. Gui, A new transformation into state transition algorithm for finding the global minimum, in "the 2nd International Conference on Intelligent Control and Information Processing," (2011), 674-678.