Particle Swarm Optimization with Exhaustive Disturbance Based on Exploration-Exploitation Balance Theory
LI Kun1, LI Ming1,2, CHEN Hao2
1.College of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 210016 2.School of Information Engineering, Nanchang Hangkong University, Nanchang 330063
Abstract：Based on the viewpoint that the algorithm gain a good performance only because it fits the characters of the optimization problem, exhaustive disturbance mechanism is introduced in the particle swarm algorithm under the theoretical framework of the exploration-exploitation balance. Based on the thorough researches of the intensity and range for exhaustive disturbance, four kinds of method for employing exhaustive disturbance are proposed in this paper. Some groups of orthogonal experiments are designed to find the best way of employing exhaustive disturbance. By analyzing the experimental results, the following conclusions are drawn. Exhaustive disturbance has its limits while dealing with high dimensional optimization problems, the intensity of exhaustive disturbance needs to be restricted within 15%, and the triggering condition of exhaustive disturbance based on population diversity shows better performance than the other triggering conditions. Finally, on the basis of the above conclusions, adaptive particle swarm optimization with exhaustive disturbance is proposed. Comparing with other algorithms, the proposed algorithm has a better performance.
[1] Wolpert D H, Macready W G. No Free Lunch Theorems for Optimization. IEEE Trans on Evolutionary Computation, 1997, 1(1): 67-82 [2] Naudts B, Kallel L. A Comparison of Predictive Measures of Pro-blem Difficulty in Evolutionary Algorithms. IEEE Trans on Evolutionary Computation, 2000, 4(1): 1-15 [3] Li K, Li M, Chen H. Research Progress of Hardness Theories on Evolutionary Algorithm. Acta Electronica Sinica, 2014, 42(2): 383-390 (in Chinese) (李 坤,黎 明,陈 昊.进化算法的困难性理论研究进展.电子学报, 2014, 42(2): 383-390) [4] Malan K M, Engelbrecht A P. A Survey of Techniques for Characterising Fitness Landscapes and Some Possible Ways Forward. Information Sciences, 2013, 241: 148-163 [5] Jones T. One Operator, One Landscape[EB/OL]. [2014-08-20]. http://www.santafe.edu/media/workingpapers/95-02-025.pdf [6] Cˇrepinek M, Liu S H, Mernik M. Exploration and Exploitation in Evolutionary Algorithms: A Survey. ACM Computing Surveys, 2013. DOI: 10.1145/2480741.2480752 [7] Bocanet A, Ponsiglione C. Balancing Exploration and Exploitation in Complex Environments. Vine, 2012, 42(1): 15-35 [8] Liu S H, Crepinsek M, Mernik M, et al. Parameter Control of EAs Using Exploration and Exploitation Measures: Preliminary Results // Proc of the 5th International Conference on Bioinspired Optimization Methods and Their Applications. Bohinj, Slovenia, 2012: 141-150 [9] Li C H, Yang S X, Nguyen T T. A Self-learning Particle Swarm Optimizer for Global Optimization Problems. IEEE Trans on Systems, Man, and Cybernetics: Cybernetics, 2012, 42(3): 627-646 [10] Xin B, Chen J, Peng Z H, et al. An Adaptive Hybrid Optimizer Based on Particle Swarm and Differential Evolution for Global Optimization. Science China: Information Sciences, 2010, 53(5): 980-989 [11] Mukhopadhyay S, Banerjee S. Global Optimization of an Optical Chaotic System by Chaotic Multi Swarm Particle Swarm Optimization. Expert Systems with Applications, 2012, 39(1): 917-924 [12] Chauhan P, Pant M, Deep K. Parameter Optimization of Multi-pass Turning Using Chaotic PSO. International Journal of Machine Learning and Cybernetics, 2015, 6(2): 319-337 [13] Zhao F Q, Tang J X, Wang J B, et al. An Improved Particle Swarm Optimisation with a Linearly Decreasing Disturbance Term for Flow Shop Scheduling with Limited Buffers. International Journal of Computer Integrated Manufacturing, 2014, 27(5): 488-499 [14] Gao H, Kwong S, Yang J J, et al. Particle Swarm Optimization Based on Intermediate Disturbance Strategy Algorithm and Its Application in Multi-threshold Image Segmentation. Information Sciences, 2013, 250: 82-112 [15] Gan X S, Duanmu J S, Meng Y B, et al. Wavelet Neural Network Aerodynamic Modeling from Flight Data Based on PSO Algorithm with Information Sharing and Velocity Disturbance. Journal of Central South University, 2013, 20(6): 1592-1601 [16] Liu W Q. Design of Experiments. Beijing, China: Tsinghua University Press, 2005 (in Chinese) (刘文卿.实验设计.北京:清华大学出版社, 2005) [17] Hofmann K, Whiteson S, de Rijke M. Balancing Exploration and Exploitation in Listwise and Pairwise Online Learning to Rank for Information Retrieval. Information Retrieval, 2013, 16(1): 63-90 [18] Ishii S, Yoshida W, Yoshimoto J. Control of Exploitation-Exploration Meta-Parameter in Reinforcement Learning. Neural Networks, 2002, 15(4/5/6): 665-687 [19] Cook Z, Franks D W, Robinson E J H. Exploration Versus Exploitation in Polydomous Ant Colonies. Journal of Theoretical Biology, 2013, 323: 49-56 [20] Bao Y K, Hu Z Y, Xiong T. A PSO and Pattern Search Based Memetic Algorithm for SVMs Parameters Optimization. Neurocomputing, 2013, 117: 98-106 [21] Posen H E, Levinthal D A. Chasing a Moving Target: Exploitation and Exploration in Dynamic Environments. Management Science, 2012, 58(3): 587-601 [22] Chen J, Xin B, Peng Z H, et al. Optimal Contraction Theorem for Exploration-Exploitation Tradeoff in Search and Optimization. IEEE Trans on Systems, Man and Cybernetics: Systems and Humans, 2009, 39(3): 680-691 [23] Prudius A A, Andrado＇ttir S. Simulation Optimization Using Ba-lanced Explorative and Exploitative Search // Proc of the 36th Conference on Winter Simulation. Washington, USA, 2004: 545-549 [24] Auger A, Schoenauer M, Teytaud O. Local and Global Order 3/2 Convergence of a Surrogate Evolutionary Algorithm // Proc of the 7th Annual Conference on Genetic and Evolutionary Computation. Washington, USA, 2005: 857-864 [25] Chen S, Lu Y M, Yang H Y, et al. Selection Pressure Study of Cellular Genetic with Disturbances. Computer Engineering and Applications, 2011, 47(27): 32-35, 97 (in Chinese) (陈 殊,鲁宇明,杨红雨,等.灾变机制下元胞遗传算法的选择压力研究.计算机工程与应用, 2011, 47(27): 32-35, 97) [26] Lu Y M, Chen S, Li M, et al. Self-adaptive Cellular Genetic Algorithms with Disaster Based on Selection Pressure. Journal of System Simulation, 2013, 25(3): 436-440, 444 (in Chinese) (鲁宇明,陈 殊,黎 明,等.自适应调整选择压力的灾变元胞遗传算法.系统仿真学报, 2013, 25(3): 436-440, 444) [27] Kirley M. A Cellular Genetic Algorithm with Disturbances: Optimisation Using Dynamic Spatial Interactions. Journal of Heuristics, 2002, 8(3): 321-342 [28] Kirley M. Ecological Algorithms: An Investigation of Adaptation, Diversity and Spatial Patterns in Complex Optimisation Problems. Ph.D Dissertation. New South Wales, Australia: Chorles Sturt University, 2002 [29] Alba E, Dorronsoro B. Cellular Genetic Algorithms. New York, USA: Springer-Verlag, 2008 [30] Park T, Ryu K R. A Dual-Population Genetic Algorithm for Adaptive Diversity Control. IEEE Trans on Evolutionary Computation, 2010, 14(6): 865-884 [31] Zhang X H, Dai G Z, Xu N P. Study on Diversity of Population in Genetic Algorithms. Control Theory and Applications, 1998, 15(1): 17-23 (in Chinese) (张晓缋,戴冠中,徐乃平.遗传算法种群多样性的分析研究.控制理论与应用, 1998, 15(1): 17-23) [32] Jones T, Forrest S. Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms // Proc of the 6th International Conference on Genetic Algorithms. Pittsburgh, USA, 1995: 184-192 [33] Yan H J, Li J W, Li M Q. Evolutionary Algorithms: Schema, Emergence and Hardness. Beijing, China: Science Press, 2012 (in Chinese) (杨海军,李建武,李敏强.进化算法的模式、涌现与困难性研究.北京:科学出版社, 2012) [34] Feng Q X, Liu S Y, Zhang J K, et al. Extrapolated Particle Swarm Optimization Based on Orthogonal Design. Journal of Convergence Information Technology, 2012, 7(2): 141-152 [35] Suganthan P N, Hansen N, Liang J J, et al. Problem Definitions and Evaluation Criteria for the CEC 2005 Special Session on Real-Parameter Optimization. Technical Report, 2005005. Singapore, Singapore: Nanyang Technological University, 2005 [36] Das S, Mandal A, Mukherjee R. An Adaptive Differential Evolution Algorithm for Global Optimization in Dynamic Environments. IEEE Trans on Cybernetics, 2014, 44(6): 966-978 [37] Hu Z B, Xiong S W, Su Q H, et al. Finite Markov Chain Analysis of Classical Differential Evolution Algorithm. Journal of Computational and Applied Mathematics, 2014, 268(1): 121-134 [38] Yang Q W, Cai L, Xue Y C. A Survey of Differential Evolution Algorithms. Pattern Recognition and Artificial Intelligence, 2008, 21(4): 506-513 (in Chinese) (杨启文,蔡 亮,薛云灿.差分进化算法综述.模式识别与人工智能, 2008, 21(4): 506-513)
2015, Vol. 28 
