On the global convergence of real-coded chemical reaction optimization

ZHOU Hui, YANG Zhen, ZHU Li-qing, CHENG Ya-qiao

Systems Engineering - Theory & Practice ›› 2015, Vol. 35 ›› Issue (12) : 3233-3240.

PDF(499 KB)
PDF(499 KB)
Systems Engineering - Theory & Practice ›› 2015, Vol. 35 ›› Issue (12) : 3233-3240. DOI: 10.12011/1000-6788(2015)12-3233

On the global convergence of real-coded chemical reaction optimization

  • ZHOU Hui, YANG Zhen, ZHU Li-qing, CHENG Ya-qiao
Author information +
History +

Abstract

Chemical reaction optimization is a kind of new natural calculation methods due to its superior performance and strong adaptability, but it lacks theoretical analysis. Aiming at this problem, we study the convergence of the real-coded chemical reaction optimization as well as its convergence speed. First, set up a RCCRO Markov chain model in its continuous time and prove that it is finite and absorbable. Second, prove its convergence through this finite and absorbable RCCRO Markov chain. Third, by adopting different combinations of the elementary reactions, study its effectiveness and the necessary conditions of global convergence to this algorithm. Finally, analyze the convergence speed and the first arrive time of RCCRO.

Key words

real-coded chemical reaction optimization (RCCRO) / Markov chain / convergence / convergence rate / first hitting time

Cite this article

Download Citations
ZHOU Hui , YANG Zhen , ZHU Li-qing , CHENG Ya-qiao. On the global convergence of real-coded chemical reaction optimization. Systems Engineering - Theory & Practice, 2015, 35(12): 3233-3240 https://doi.org/10.12011/1000-6788(2015)12-3233

References

[1] Lam A Y S, Li V O K. Chemical-reaction-inspired metaheuristic for optimization[J]. IEEE Transactions on Evolutionary Computation, 2010, 14(3): 381-399.
[2] Taillard E D. FANT: Fast ant system[R]. Technical Report, IDSIA-46-98, 1998.
[3] Connolly D T. An improved annealing scheme for the QAP[J]. European Journal of Operational Research, 1990, 46(1): 93-100.
[4] Taillard E D. Robust taboo search for the quadratic assignment problem[J]. Parallel Computing, 1991, 17(4): 443-455.
[5] Lam A Y S, Li V O K. Chemical reaction optimization for cognitive radio spectrum allocation[C]. IEEE Global Communications Conference, Miami, FL, 2010: 1-5.
[6] Lam A Y S, Xu J, Li V O K. Chemical reaction optimization for population transition in peer-to-peer live streaming[C]//IEEE Congress on Evolutionary Computation, 2010: 1-8.
[7] Xu J, Lam A Y S, Li V O K. Chemical reaction optimization for task scheduling in grid computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 22(10): 1624-1631.
[8] Yu J J Q, Lam A Y S, Li V O K. Evolutionary artificial neural network based on chemical reaction optimization[C]//IEEE Congress on Evolutionary Computation, New Orleans, LA, USA, 2011.
[9] Pan B, Lam A Y S, Li V O K. Network coding optimization based on chemical reaction optimization[C]//IEEE Global Communications Conference, Houston, TX, USA, 2011.
[10] Lam A Y S, Li V O K, Yu J J Q. Real-coded chemical reaction optimization[J]. IEEE Transactions on Evolutionary Computation, 2010, 16(3): 339-353.
[11] Yu J J Q, Lam A Y S, Li V O K. Real-coded chemical reaction optimization with different perturbation functions[J]. IEEE Transactions on Evolutionary Computation, 2012: 1-8.
[12] 罗磊,谢静,周晖,等.一种新的群搜索优化实现算法[J].南通大学学报(自然科学版), 2012, 11(2): 1-8.Luo Lei, Xie Jing, Zhou Hui, et al. A novel realization algorithm of group search optimizer[J]. Journal of Nantong University (Natural Science Edition), 2012, 11(2): 1-8.
[13] He S, Wu Q H, Saunders J R. Group search optimizer: An optimization algorithm inspired by animal searching behavior[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(5): 973-990.
[14] Yao X, Liu Y, Lin G. Evolutionary programming made faster[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(2): 82-102.
[15] Gong W, Cai Z, Ling C X, et al. A real-coded biogeography based optimization with mutation[J]. Applied Mathematics and Computation, 2010, 216(9): 2749-2758.
[16] Albert Y S L, Victor O K L, Jin X. On the convergence of chemical reaction optimization for combinatorial optimization[J]. IEEE Transactions on Evolutionary Computation, 2013, 17(5): 605-620.
[17] Leung Y, Gao Y, Xu Z. Degree of population diversity——A perspective on premature convergence in genetic algorithms and its Markov chain analysis[J]. IEEE Transactions on Neural Networks, 1997, 8(5): 1165-1176.
[18] Eiben A E, Aarts E H L, van Hee K M. Global convergence of genetic algorithms: A Markov chain analysis[M]//Parallel Problem Solving from Nature, Berlin: Springer-Verlag, 1991: 4-12.
[19] Rudolph G. Convergence analysis of canonical genetic algorithms[J]. IEEE Transactions on Neural Networks, 1994, 5(1): 96-101.
[20] Hajek B. Cooling schedules for optimal annealing[J]. Mathematics of Operations Research, 1988, 13(2): 311-329.
[21] Gutjahr W J. A generalized convergence result for the graph-based ant system metaheuristic[J]. Journal of Probability in the Engineering and Information Sciences, 2003, 17(4): 545-569.
[22] Gutjahr W J. ACO algorithms with guaranteed convergence to the optimal solution[J]. Information Processing Letters, 2002, 82(3): 145-153.
[23] Huang H, Wu C, Hao Z. A pheromone-rate-based analysis on the convergence time of ACO algorithm[J]. IEEE Transactions on Systems, Man and Cybernetics——Part B, 2009, 39(4): 910-923.
[24] Stutzle T, Dorigo M. A short convergence proof for a class of ant colony optimization algorithms[J]. IEEE Transactions on Evolutionary Computation, 2010, 6(4): 358-365.
[25] Althofer I, Koschnick K U. On the convergence of threshold accepting[J]. Applied Mathematics Optimization, 1991, 24(1): 183-195.
[26] Rudolph G. Finite Markov chain results in evolutionary computation: A tour d'horizon[J]. Fundamenta Informaticae, 1998, 35(4): 67-89.
[27] He J, Yu X. Conditions for the convergence of evolutionary algorithms[J]. Journal of Systems Architecture, 2001, 47(7): 601-612.
[28] Yu Y, Zhou Z. A new approach to estimating the expected first hitting time of evolutionary algorithms[J]. Artificial Intelligence, 2008, 172(15): 1809-1832.
[29] Motwani M, Raghavan P. Randomized algorithms[M]. Cambridge, UK: Cambridge University Press, 1995.
[30] Huang H, Lin Z Y, Hao Z F, et al. Convergence analysis and comparison of evolutionary algorithms based on relation model[J]. Chinese Journal of Computers, 2011, 34(5): 801-811.
PDF(499 KB)

277

Accesses

0

Citation

Detail

Sections
Recommended

/