基于博弈论的量子蚁群算法

doi:10.6040/j.issn.1672-3961.2.2014.045

山东大学学报(工学版) ›› 2015, Vol. 45 ›› Issue (2): 33-36.doi: 10.6040/j.issn.1672-3961.2.2014.045

基于博弈论的量子蚁群算法

王启明^1,2, 李战国^1,2, 樊爱宛^1,2

1. 平顶山学院计算机科学与技术学院, 河南平顶山 467002;
2. 平顶山学院软件学院, 河南平顶山 467002

收稿日期:2014-04-01 修回日期:2015-01-30 出版日期:2015-04-20 发布日期:2014-04-01
作者简介:王启明(1980-),男,河南鲁山人,讲师,硕士,主要研究方向为软件工程算法和物联网.E-mail:wqm8157@126.com
基金资助:
河南省科技计划资助项目(102102210416)

Quantum ant colony algorithm based on the game theory

WANG Qiming^1,2, LI Zhanguo^1,2, FAN Aiwan^1,2

1. School of Computer Science and Technology, Pingdingshan University, Pingdingshan 467002, Henan, China;
2. School of Software Engineering, Pingdingshan University, Pingdingshan 467002, Henan, China

Received:2014-04-01 Revised:2015-01-30 Online:2015-04-20 Published:2014-04-01

摘要/Abstract

摘要： 针对量子蚁群算法求解组合优化问题时易陷入局部最优和收敛速度慢的问题,提出一种基于博弈论的量子蚁群算法(quantum ant colony algorithm based on the game theory, GQACA)。算法采用重复博弈模型,在重复博弈中产生一个博弈序列,使得每次博弈都能够产生最大效益,并得到相应博弈过程的纳什均衡。利用典型的5个标准测试函数对GQACA算法寻优性能进行试验测试。试验结果表明: GQACA算法的收敛精度和稳定性均要优于量子蚁群算法(quantum ant colony algorithm, QACA)和蚁群算法(ant colony algorithm, ACA)。

关键词: 函数优化, 量子蚁群算法, 纳什均衡, 博弈论, 组合优化

Abstract: Local optimum and low convergence rate were the main problems when used Quantum ant colony algorithm to solve combinatorial optimization, a quantum ant colony algorithm based on game theory (GQACA) was put forward. The algorithm generated a game sequence by the repeated game model, which made every game produce maximum benefit and get Nash equilibrium of the corresponding game process. Five typical test functions were used to make experiment test on the optimal performance of the GQACA algorithm.The experiments showed that the convergence precision and stability of the GQACA algorithm were superior to QACA algorithm and ACA algorithm.

Key words: the game theory, nash equilibrium, function optimization, combinatorial optimization, quantum ant colony algorithm

中图分类号:

TP393

王启明, 李战国, 樊爱宛. 基于博弈论的量子蚁群算法[J]. 山东大学学报(工学版), 2015, 45(2): 33-36.

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.

参考文献

[1] 段海滨,王道波,于秀芬. 蚁群算法的研究进展评述[J]. 自然杂志,2006,28(2):102-105. DUAN Haibin, WANG Daobo, YU Xiufen. Review on research progress in ant colony algorithm[J]. Chinese Journal of Nature, 2006, 28(2):102-105.
[2] DORIGO M, GARO G D, GAMBARDELLA M. Ant algorithms for discrete optimization[J]. Artificial Life, 1999, 5(2):137-172.
[3] STTZLE T, DORIGO M. A short convergence proof for a class of ant colony optimization algorithms[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(4):358-365.
[4] 金弟, 杨博, 刘杰, 等. 复杂网络簇结构探测—基于随机游走的蚁群算法[J]. 软件学报, 2012,23(3):451-464. JIN Di, YANG Bo, LIU Jie, et al. Ant colony optimization based on random walk for community detection in complex networks[J]. Journal of Software, 2012, 23(3):451-464.
[5] LI P C, LI S Y. Quantum ant colony algorithm for continuous space optimization[J]. Control Theory and Applications, 2008, 25(2):237-241.
[6] LI P, WANG H. Quantum ant colony optimization algorithm based on bloch spherical search[J]. Neural Network World, 2012, 22(4):325-341.
[7] 袁浩. 基于量子蚁群算法的粗糙集属性约简方法[J]. 计算机工程与科学, 2010, 32(5):82-84. YUAN Hao. A rough set attribute reduction method based on the quantum ant colony algorithm[J]. Computer Engineering & Science, 2010, 32(5):82-84.
[8] LI P, SONG K, YANG E. Quantum ant colony optimization with application[C]//2010 Sixth International Conference on Natural Computation (ICNC). Yantai, China:IEEE, 2010:2989-2993.
[9] HONGGANG W, LIANG M, HUIZHEN Z, et al. Quantum-inspired ant algorithm for knapsack problems[J]. Journal of Systems Engineering and Electronics, 2009, 20(5): 1012-1016.
[10] 沈鹏. 物流配送路径优化问题求解的量子蚁群算法[J].计算机工程与应用, 2013, 49(21):56-59. SHEN Peng. Quantum ant colony algorithm for optimization of logistics distribution route[J]. Computer Engineering and Applications, 2013, 49(21):56-59.
[11] 贾瑞玉,李亚龙,管玉勇. 求解旅行商问题的混合量子蚁群算法[J]. 计算机工程与应用, 2013,49(22):36-39.JIA Ruiyu, LI Yalong, GUAN Yuyong. Hybrid quantum ant colony algorithm for traveling salesman problem[J]. Computer Engineering and Applications, 2013, 49(22):36-39.
[12] CHANDRA MOHAN B, BASKARAN R. A survey: ant colony optimization based recent research and implementation on several engineering domain[J]. Expert Systems with Applications, 2012, 39(4):4618-4627.
[13] 田有亮, 马建峰, 彭长根, 等. 秘密共享体制的博弈论分析[J]. 电子学报, 2011, 39(12):2790-2795. TIAN Youliang, MA Jianfeng, PENG Changgen, et al. Game-theoretic analysis for the secret sharing scheme[J]. Acta Electronica Sinica, 2011, 39(12):2790-2795.
[14] 刘玉岭, 冯登国, 吴丽辉, 等. 基于静态贝叶斯博弈的蠕虫攻防策略绩效评估[J]. 软件学报, 2012, 23(3):712-723. LIU Yuling, FENG Dengguo, WU Lihui, et al. Performance evaluation of worm attack and defense strategies based on static bayesian game[J]. Journal of Software, 2012, 23(3):712-723.
[15] 朱建明, SRINIVASAN Raghunathan. 基于博弈论的信息安全技术评价模型[J]. 计算机学报, 2009, 32(4):828-834. ZHU Jianming, SRINIVASAN Raghunathan. Evaluation model of information security technologies based on game theoretic[J]. Chinese Journal of Computers, 2009, 32(4):828-834.
[16] DORIGO M.Optimization learning and natural algorithms[D]. Milano:Department of Electronics,Politecnico di Milano, Italy, 1992.
[17] MANIEZZO V, DORIGO M, COLORNI A. The ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems, Man, and Cybernetics-Part B, 1996, 26(1):29-41.
[18] DIOSAN L, OLTEAN M.What else is the evolution of PSO telling us[J]. Journal of Artificial Evolution and Applications, 2008, 8(2):1-12.
[19] THOMAS S, HOLGER H H. Max-min ant system[J].Future Generation Computer Systems, 2000, 16(8):889-914.
[20] DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. Evolutionary Computation, IEEE Transactions on, 1997, 1(1):53-66.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于博弈论的量子蚁群算法

Quantum ant colony algorithm based on the game theory

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

多维度评价

本文评价

推荐阅读 0

[1]	易云飞,苗剑,林郭隆,殷智. 基于牛顿力学和博弈论模型的粒子网络优化算法[J]. 山东大学学报(工学版), 2017, 47(1): 28-36.
[2]	戴红伟, 杨玉, 仲兆满, 李存华. 改进量子交叉免疫克隆算法及其应用[J]. 山东大学学报(工学版), 2015, 45(2): 17-21.
[3]	李响1,王海鹏1,李勇建2*. 三级逆向供应链优化与协调研究[J]. 山东大学学报(工学版), 2012, 42(6): 50-55.
[4]	蒋鹏飞,王震 . 制造商与不同质供应商博弈分析[J]. 山东大学学报(工学版), 2008, 38(2): 117-119 .
[5]	谢楠 . 物流配送车辆线路的多目标最优控制研究[J]. 山东大学学报(工学版), 2007, 37(4): 0-0 .