The Markov Model of Bean Optimization Algorithm and Its Convergence Analysis
Tóm tắt
By simulating the self-adaptive phenomena of plants in nature, a novel evolutionary algorithm named Bean Optimization Algorithm (BOA) was proposed in 2008. BOA can be used for resolving complex optimization problems. As BOA is a new optimization algorithm, theoretical analysis of the algorithm is still very preliminary. Research on the state transfer process and the convergence behavior of BOA is of great significance for understanding it. In this paper, we build the Markov chain model of this algorithm and analyze the characters of this Markov chain. Then we analyze the transferring process of the bean memeplex status series and point out that the memeplex status series will enter the best status set. We also prove that this algorithm meets the requirement of global convergence criterion of random search algorithms. Finally we get the conclusion that BOA will make sure to get the global optimum.
Tài liệu tham khảo
J. H. Holland. Adaption in Natural and Artificial Systems (The MIT Press, Cambridge, MA, 1975).
Kennedy J, Eberhart R. C. Particle swarm optimisation, In Proceedings of IEEE International Conference on Neural Networks(Piscataway, NJ, 1995), pp.1942–1948.
Li Xiaolei, Shao Zhijiang, Qian Jixin. An Optimizing Method Based on Autonomous Animats: Fish-swarm Algorithm. Systems Engineering—Theory & Practice, 22(11), (2002), pp.32–38.
Penev Kalin, Littlefair Guy. Free Search-a comparative analysis. Information Sciences, 172(1–2) , (2005), pp.173–193.
Oscar Montiela, Oscar Castillob, Patricia Melinb, Antonio Rodríguez Díazc, Roberto Sepúlvedaa. Human evolutionary model: A new approach to optimization. Information Sciences, 177(10), (2007), pp.2075–2098.
He, S.,Wu, Q.H., Saunders, J.R. Group Search Optimizer: An Optimization Algorithm Inspired by Animal Searching Behavio. IEEE Transactions on Evolutionary Computation, Vol.13(5), (2009), pp.973–990.
Shinn-Ying Ho, Hung-Sui Lin, Weei-Hurng Liauh, Shinn-Jang Ho. OPSO: Orthogonal Particle Swarm Optimization and Its Application to Task Assignment Problems. IEEE Transactions on Systems, Man and Cybernetics, Part A, 38(2), (2008), pp.288–298.
Souda T., Silva A., Neves A. Particle Swarm based Data Mining Algorithms for classification task. Parallel Computing, 30(5), (2004), pp.767–783.
Shutao Li, Xixian Wu, Mingkui Tan. Gene selection using hybrid particle swarm optimization and genetic algorithm. Soft Computing, 12(11) , (2008), pp.1039–1048.
Xiaoming Zhang, Rujing Wang, Liangtu Song. A Novel Evolutionary Algorithm—Seed Optimization Algorithm. Pattern Recognition and Artificial Intelligence. 21(5) , (2008), pp.677–681.
Yunming Li. Solving TSP by an ACO-and-BOA-Based Hybrid Algorithm. In Proceedings of 2010 International Conference on Computer Application and System Modeling(Taiyuan, China, 2010), pp.189–192.
Pengfei Wang, Youqing Cheng. Relief Supplies Scheduling Based on Bean Optimization Algorithm. Economic Research Guide,Vol.8, (2010), pp.252–253.
Xiaoming Zhang, Bingyu Sun, Tao Mei, Rujing Wang, Post-disaster Restoration Based on Fuzzy Preference Relation and Bean Optimization Algorithm. In Proceedings of the 2nd IEEE Youth Conference on Information, Computing and Telecommunications(Beijing, China, 2010), pp.271–274.
Wei Zongshu. Probability Theory and Mathematical Statistics (Higher Education Press, Beijing, China, 2000).
Solis F, Wets R. Minimization by random search techniques. Mathematics of Operations Research, 6(1) , (1998), pp.19–30.
Zhang Wenxiu, Leung Yee. Mathematical Foundation of Genetic Algorithm( Xi’an Jiaotong University Press, Xi’an, China, 2003).
Chen Fang, Ling Wang. An effective shuffledfrog-leapingalgorithm for resource-constrained project scheduling problem. Computers & Operations Research, 39(5) , (2012), pp.890–901.
Xiaoming Zhang, Kang Jiang, Hailei Wang, Wenbo Li, Bingyu Sun. An Improved Bean Optimization Algorithm for Solving TSP, Lecture Notes in Computer Science,Vol.7331, (2012), pp.261–267.
Niknam, T., Amiri, B. An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis. Applied Soft Computing, 10 (1) , (2010), pp.183–197.
L.Y.Tseng, S.C.Chen. A hybrid metaheuristic for the resource-constrained project scheduling problem. European Journal of Operational Research, 175(2) , (2006), pp.707–721