JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE) ›› 2017, Vol. 47 ›› Issue (1): 28-36.doi: 10.6040/j.issn.1672-3961.1.2016.070

Previous Articles     Next Articles

Particle network optimization algorithm based on Newtonian mechanics and game theory model

YI Yunfei1a,b, MIAO Jian1a*, LIN Guolong2, YIN Zhi3   

  1. 1. a. College of Computer and Information Engineering, b. Key Laboratory of Intelligent Computing and Pattern Recognition, Hechi University, Yizhou 546300, Guangxi, China;
    2. Computer School, Wuhan University, Wuhan 430072, Hubei, China;
    3. Hechi Municipal People's Government Office, Hechi 547000, Guangxi, China
  • Received:2016-03-31 Online:2017-02-20 Published:2016-03-31

PDF (PC)

944

Abstract: In order to overcome the bad convergence and accuracy of the standard particle swarm optimization algorithm in solving the high dimensional TSP problem, each particle was given their own character, such as mass and acceleration was given, and Newton second law with a Poisson distribution was introduced to dynamic control the particle acceleration. In addition, the particle dimensions were divided into advantages and disadvantages section based on its similar to reduce the dimension of update, normally update would only change the disadvantage parts to keep and extend their advantage parts so that it could improve the convergence speed, when the disturbance it would update its advantage parts to away from the current network so that it could jump out of local optimum,when particles collide, opposition-based learning strategy was used to deal with disadvantage section, and a better model of slow convergence was selected. Finally, via numerous simulations of TSPLIB and comparison with other classical algorithms, the results showed that the improved algorithm had the feature of high efficiency, low computational complexity and strong convergence, which were especially crucial for the functioning of large-scale distribution problems. Research results could provide a reference for the study on intelligent algorithms in solving optimization problems, such as how to improve the accuracy and speed up the convergence. 山 东 大 学 学 报 (工 学 版)第47卷 - 第1期易云飞,等:基于牛顿力学和博弈论模型的粒子网络优化算法 \=-

Key words: travelling salesman problem, particle swarm optimization, Newtonian mechanics, game theory, Poisson distribution, particle network

CLC Number: 

  • TP18
[1] 毛澄映,喻新欣,薛云志.基于粒子群优化的测试数据生成及其实证分析[J].计算机研究与发展,2014,51(4):824-837. MAO Chengying, YU Xinxin, XUE Yunzhi. Algorithm design and empirical analysis for particle swarm optimization based test data generation[J]. Journal of Computer Research and Development, 2014, 51(4):824-837.
[2] 范德斌,邓长寿,袁斯昊,等.基于MapReduce模型的分布式粒子群算法[J].山东大学学报(工学版),2016,46(5):1-9. FAN Debin, DENG Changshou, YUAN Sihao, et al. Distributed particle swarm optimization algorithm based on MapReduce[J].Journal of Shandong University(Engineering Science), 2016, 46(5):1-9.
[3] SHI Y, EBERHART RC. Fuzzy adaptive particle swarm optimization[C] //Proceedings of the IEEE Congress on Evolutionary Computation. Seoul, Korea:IEEE, 2001:101-106.
[4] PERAM T, VEERAMACHANENI K, MOHAN C K. Fitness-distance-ratio based particle swarm optimization[C] //Proceedings of the Swarm Intelligence Symposium. Indianapolis, Indiana, USA:IEEE Press, 2003:174-181.
[5] FRANS V D B, ENGELBRECHT A P. A cooperative approach to particle swarm optimization[J]. IEEE Press Transactions on Evolutionary Computation, 2004, 8(3):225-239.
[6] TIZHOOSH H R. Opposition-based learning:a new scheme for machine intelligence[C] // Proceedings of the International Conference on Intelligent Agents, Web Technologies and Internet Commerce. Washington D C, USA:IEEE Press, 2005:695-701.
[7] RAHNAMAYAN S, TIZHOOSH H R, SALAMA M M A. Opposition based differential evolution[J].Springer Berlin Heidelberg, 2008, 12(1):64-79.
[8] 喻飞,李元香,魏波,等.透镜反向学习策略在粒子群算法中的应用[J].电子学报,2014,42(2):230-235. YU Fei, LI Yuanxiang, WEI Bo, et al. The application of a novel OBL based on lens imaging principle in PSO[J].Chinese Journal of Electronics, 2014, 42(2):230-235.
[9] 纪震,周家锐,廖惠连.智能单粒子优化算法[J].计算机学报,2010,33(3):556-561. JI Zhen, ZHOU Jiarui, LIAO Huilian. A novel intelligent single particle optimizer[J].Chinese Journal of Computers, 2010, 33(3):556-561.
[10] 迟玉红,孙富春,王维军,等.基于空间缩放和吸引子的例子群优化算法[J].计算机学报,2011,34(1):115-130. CHI Yuhong, SUN Fuchun, WANG Weijun, et al. An improved particle swarm optimization algorithm with search space zoomed factor and attractor[J]. Chinese Journal of Computers, 2011, 34(1):115-130.
[11] 陶新民,刘福荣,刘玉.一种多尺度协同变异的粒子群优化算法[J].软件学报,2012,23(7):1805-1815. TAO Xinmin, LIU Furong, LIU Yu. Multi-scale cooperative mutation particle swarm optimization algorithm[J]. Journal of Software, 2012, 23(7):1805-1815.
[12] 伍大清,郑建国.基于混合策略自适应学习的并行粒子群优化算法[J].控制与决策,2013,28(7):1087-1093. WU Daqing, ZHENG Jianguo. Improved parallel particle swarm optimization algorithm with hybrid strategy and Self-adaptive learning[J]. Control and Decision, 2013, 28(7):1087-1093.
[13] 李栋,徐志明,李生,等.在线社会网络中信息扩散[J].计算机学报,2014,37(1):189-206. LI Dong, XU Zhiming, LI Sheng, et al. A survey on information diffusion in online social networks[J]. Chinese Journal of Computers, 2014, 37(1):189-206.
[14] REGO C, GAMBOA D, GLOVER F, et al. Traveling salesman problem heuristics: leading methods, implement-tations and latest advances[J]. European Journal of Operational Research, 2011, 211(3):427-441.
[15] JUNGER M, REINELT G, RINALDI G. Handbooks in OR & MS: chapter4 the traveling salesman problem[M]. Amesterdam, North-Holland: Elsevier Science, 1995:225-330.
[16] ANGELINE PJ. Using selection to improve particle swarm optimization[C] //Proceedings of the IEEE International Conference on Evolutionary Computation. Anchorage, Alaska, USA:IEEE Press, 1998:84-89.
[17] GOLDENBERG J, LIBAI B, MULLER E. Talk of the network: a complex systems look at the underlying process of word-of-mouth[J].Marketing Letters, 2001, 12(3):211-223.
[18] GOLDENBERG J, LIBAI B, MULLER E. Using complex systems analysis to advance marketing theory development: modeling heterogeneity effects on new product growth through stochastic cellular automata [J]. Academy of Marketing Science Review, 2001, 31(3):8-11.
[19] GRANOVETTER M. Threshold models of collective behavior[J]. American Journal of Sociology, 1987, 83(6):1420-1443.
[20] HETHCOTE, HERBERT W. The mathematics of infectious diseases[J]. SIAM Review-Society for Industrial and Applied Mathematics, 2000, 42(4):599-653.
[21] MAY R M, LOYD A L. Infection dynamics on scale-free network[J]. Physical Review E, 2001, 64(2):126-166.
[22] SATORRAS R Pastor, VESPIGNANI A. Epidemic spreading in scale-free networks[J].Physical Review Letters, 2001, 86(14):3200-3203.
[23] YOUNG H P. The Diffusion of innovation in social networks[M]. Oxford: Oxford University Press, 2003.
[24] 饶卫振,金淳,陆林涛.考虑边位置信息的求解ETSP问题改进贪婪算法[J].计算机学报,2013,36(4):836-850. RAO Weizhen, JIN Chun, LU Lintao. An improved greedy algorithm with information of edges' location for solving the euclidean traveling salesman problem[J]. Chinese Journal of Computers, 2013, 36(4):836-850.
[1] FAN Debin, DENG Changshou, YUAN Sihao, TAN Xujie, DONG Xiaogang. Distributed particle swarm optimization algorithm based on mapreduce [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(6): 23-30.
[2] WANG Qiming, LI Zhanguo, FAN Aiwan. Quantum ant colony algorithm based on the game theory [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(2): 33-36.
[3] DONG Hongbin, ZHANG Guangjiang, PANG Jinwei, HAN Qilong. A clustering ensemble algorithm based on co-evolution [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(2): 1-9.
[4] WANG Huifang, ZHAO Zhicheng, ZHANG Jinggang. Design of a fractional order IMC-IDμ controller for high order systems [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(6): 77-82.
[5] HUA Jingxin, BO Yuming, CHEN Zhimin. Forecasting of real estate market based on particle swarm optimized neural network [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(4): 22-30.
[6] JING Ye-fei1, ZHANG Cheng-hui1*, XU Bei-bei, LI Ke1, CHU Xiao-guang1. An output power optimization method based on impedance matching for a small wind generation system [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2013, 43(5): 39-43.
[7] ZHANG Fei, GENG Hong-qin. Optimization of job-shop scheduling problem based on chaos particle swarm optimization algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2013, 43(3): 19-22.
[8] LI Xiang1, WANG Hai-peng1, LI Yong-jian2*. Optimization and coordination of a three-echelon reverse supply chain [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(6): 50-55.
[9] XU Long-qin1, LIU Shuang-yin1,2,3,4*. Water quality prediction model based on APSO-WLSSVR [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(5): 80-86.
[10] LIU Bin, ZHANG Ren-jin. A path planning method using two-stage particle swarm optimization [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(1): 12-18.
[11] CHEN Ming-zhi1, 2, CHEN Jian3, XU Chun-yao3, YU Lun3, LIN Bo-gang1, 2. A new clustering algorithm for user access patterns based on network virtual environments [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2011, 41(6): 43-49.
[12] DAI Ping, LI Ning*. A fast SVM-based feature selection method [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(5): 60-65.
[13] LIU Jianhua1,2， HUANG Tiangqiang2， YAN Xiaoming2. Evolutionary algorithm based on idea of particle swarm optimization [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(5): 34-40.
[14] XIA Hui1, WANG Hua1, CHEN Xi2. A kind of ant colony parameter adaptive optimization algorithm  based on particle swarm optimization thought [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(3): 26-30.
[15] ZHANG Xun-Hua, GAO Qing. The impact of global warming on the design standard ofbuilding envelops [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(5): 52-57.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd