基于牛顿力学和博弈论模型的粒子网络优化算法

doi:10.6040/j.issn.1672-3961.1.2016.070

山东大学学报(工学版) ›› 2017, Vol. 47 ›› Issue (1): 28-36.doi: 10.6040/j.issn.1672-3961.1.2016.070

基于牛顿力学和博弈论模型的粒子网络优化算法

易云飞^1a,b,苗剑^1a*,林郭隆²,殷智³

1.河池学院, a. 计算机与信息工程学院;b. 智能计算与模式识别重点实验室, 广西宜州 546300;2. 武汉大学计算机学院, 湖北武汉 430072;3. 河池市人民政府办公室, 广西河池 547000

收稿日期:2016-03-31 出版日期:2017-02-20 发布日期:2016-03-31
通讯作者: 苗剑(1974— ),男,江苏睢宁人,教授,博士,主要研究方向为优化算法与制造业信息化等.E-mail:16841421@qq.com E-mail:gxyiyf@163.com
作者简介:易云飞(1981— ),男,广西资源人,副教授,博士,主要研究方向为机器学习与智能计算等.E-mail:gxyiyf@163.com
基金资助:
国家自然科学基金资助项目(61170305);河池学院科研启动经费资助项目(XJ2016KQ01);国家级大学生创新创业训练计划资助项目(201610605029)

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

YI Yunfei^1a,b, MIAO Jian^1a*, LIN Guolong², YIN Zhi³

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

摘要/Abstract

摘要： 为克服标准粒子群算法在求解高维TSP问题时求解精度不高、易陷入局部最优等不足,将每个粒子均赋予质量和加速度,利用泊松分布和牛顿第二运动定律动态调整粒子加速度,并将粒子维数以相似度划分为优势部分和劣势部分,正常更新时只对劣势部分进行相应处理,保持并扩大其优势部分以提高收敛速度,扰动时更新其优势部分以达到远离当前粒子网络的目的来跳出局部最优。当有粒子碰撞时,引入反向学习策略处理粒子,选择合适的降速模型来提高收敛速度。最后,将改进后的算法用于求解TSPLIB中的标准实例问题,并与经典算法进行比较。试验结果表明,提出的新算法在求解旅行商问题时具有高效率、低迭代次数及强收敛等特性。该结果可为智能算法在求解优化问题时提高精确性和加快收敛等方面的研究提供一定的参考。

关键词: 牛顿力学, 博弈论模型, 泊松分布, 粒子网络, 旅行商问题, 粒子群算法

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

中图分类号:

TP18

易云飞,苗剑,林郭隆,殷智. 基于牛顿力学和博弈论模型的粒子网络优化算法[J]. 山东大学学报(工学版), 2017, 47(1): 28-36.

YI Yunfei, MIAO Jian, LIN Guolong, YIN Zhi. Particle network optimization algorithm based on Newtonian mechanics and game theory model[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(1): 28-36.

参考文献

[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.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于牛顿力学和博弈论模型的粒子网络优化算法

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

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

多维度评价

本文评价

推荐阅读 0

[1]	梁蒙蒙,周涛,夏勇,张飞飞,杨健. 基于PSO-ConvK卷积神经网络的肺部肿瘤图像识别[J]. 山东大学学报(工学版), 2018, 48(5): 77-84.
[2]	马汉杰,林霞,胥晓晖,张健,张智晟. 基于自适应粒子群算法的智能家居管理系统负荷优化模型[J]. 山东大学学报(工学版), 2017, 47(6): 57-62.
[3]	王立宏,李强. 旅行商问题的一种选择性集成求解方法[J]. 山东大学学报(工学版), 2016, 46(1): 42-48.
[4]	戴红伟, 杨玉, 仲兆满, 李存华. 改进量子交叉免疫克隆算法及其应用[J]. 山东大学学报(工学版), 2015, 45(2): 17-21.
[5]	荆业飞1,张承慧1*,徐蓓蓓2，李珂1,褚晓广1. 基于阻抗匹配的小型风电系统功率输出优化方法[J]. 山东大学学报(工学版), 2013, 43(5): 39-43.
[6]	张飞,耿红琴. 基于混沌粒子群算法的车间作业调度优化[J]. 山东大学学报(工学版), 2013, 43(3): 19-22.
[7]	曾华1,崔文2,付连宁1,吴耀华1*. Lin-Kernighan算法初始解的启发式构造策略[J]. 山东大学学报(工学版), 2012, 42(2): 30-35.
[8]	蔡荣英,王李进,吴超,钟一文*. 一种求解旅行商问题的迭代改进蚁群优化算法[J]. 山东大学学报(工学版), 2012, 42(1): 6-11.
[9]	刘建华1,2, 黄添强2, 严晓明2. 融合PSO算法思想的进化算法[J]. 山东大学学报(工学版), 2010, 40(5): 34-40.
[10]	王振树李林川李波. 基于粒子群与模拟退火相结合的无功优化算法[J]. 山东大学学报(工学版), 2008, 38(6): 15-20.