多元优化算法及其收敛性分析

李宝磊; 施心陵; 苟常兴; 吕丹桔; 安镇宙; 张榆锋

doi:10.16383/j.aas.2015.c140585

多元优化算法及其收敛性分析

doi: 10.16383/j.aas.2015.c140585

1.
云南大学信息学院昆明 650091;
2.
玉溪师范学院信息技术工程学院玉溪 653100

基金项目:

国家自然科学基金(61261007, 61361010, 11303094),云南省自然科学基金重点项目(2013FA008)资助

详细信息

作者简介:
李宝磊云南大学信息学院博士研究生.2009 年获得延边大学工学院电子系学士学位. 主要研究方向为智能优化算法, 信号处理. E-mail: bl li@126.com

通讯作者:
施心陵云南大学信息学院教授. 主要研究方向为智能优化算法, 生物医学. E-mail: xlshi@ynu.edu.cn

计量
- 文章访问数: 3043
- HTML全文浏览量: 121
- PDF下载量: 1167
- 被引次数: 0
出版历程
- 收稿日期: 2014-08-11
- 修回日期: 2014-12-16
- 刊出日期: 2015-05-20

Multivariant Optimization Algorithm and Its Convergence Analysis

1.
School of Information, Yunnan University, Kunming 650091;
2.
School of Information Technology and Engineering, Yuxi Normal University, Yuxi 653100

Funds:

Supported by National Natural Science Foundation of China (61261007, 61361010, 11303094), and Key Program of Yunnan Natural Science Foundation (2013FA008)

摘要

摘要: 提出了一种搜索个体分工明确、协同合作的群智能优化算法,并从理论上证明了其收敛性. 由于搜索个体(搜索元)具有分工不同的多元化特点,所以我们称该算法为多元优化算法(Multivariant optimization algorithm, MOA).多元优化算法中, 全局搜索元和局部搜索元基于数据表高效的记录和分享信息以协同合作对解空间进行搜索. 在一次迭代中,全局搜索元搜索整个解空间以寻找潜在解区域,然后具有不同种群大小的局部搜索元组对潜力不同的历史潜在解区域以及新发现的潜在解区域进行不同粒度的搜索. 搜索元找到的较优解按照一定的规则保存在由队列和堆栈组成的结构体中以实现历史信息的高效记忆和共享. 结构体中保存的候选解在迭代过程中不断更新逐渐接近最优解,最终找到优化问题的多个全局最优解以及局部次优解.基于马尔科夫过程的理论分析表明:多元优化算法以概率1 收敛于全局最优解.为了评估多元优化算法的收敛性,本文利用多元优化算法以及其他五个常用的优化算法对十三个二维及十维标准测试函数进行了寻优测试. 实验结果表明,多元优化算法在收敛成功率和收敛精度方面优于其他参与比较的算法.
- 多元优化算法 /
- 收敛性 /
- 结构体 /
- 局部搜索元 /
- 全局搜索元 /
- 优化
Abstract: In this paper, we present a swarm intelligent algorithm and study its convergence property. We name it as multivariant optimization algorithm (MOA) because its multiple searchers (atoms) are variant in responsibilities. The solution space is searched through global-local search iterations which are based on the collaboration and coordination between the local and global search groups in the MOA. In each iteration, the global atoms explore the whole solution space to locate potential areas and then multiple local groups with different numbers of local search atoms are allotted to these potential areas for different levels of refinements. The historical better solutions are recorded in a structure made up of a queue and some stacks, according to a certain rule. The candidate solutions in the structure are improved iteratively and will converge to the optimal solutions. A theoretical convergence analysis based on Markov process shows that MOA converges to more than one global optimal solutions with probability 1. To evaluate its convergence property, MOA and other five frequently compared algorithms are employed to locate the optimal solutions of thirteen two-dimensional and ten-dimensional benchmark functions. The results show that the MOA has competitive performance to the other algorithms in terms of the convergence success rate and accuracy.
- Multivariant optimization algorithm (MOA) /
- convergence /
- structure /
- local atom /
- global atom /
- optimization

HTML全文

参考文献(31)

[1]	Sivanandam S N, Deepa S N. Introduction to Genetic Algorithms. Berlin: Springer-Verlag, 2007. 78-82
[2]	Li Ren-Fu, Dokgo Myongchol, Hu Lin. Path planning based on PSO algorithm convergence and parameters analysis. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2013, 41(S1): 271-275(李仁府, 独孤明哲, 胡麟. 基于PSO 算法的路径规划收敛性与参数分析. 华中科技大学学报(自然科学版), 2013, 41(S1): 271-275)
[3]	[3] Liang J J, Song H, Qu B Y, Mao X B. Path planning based on dynamic multi-swarm particle swarm optimizer with crossover. In: Proceedings of the 8th International Conference on Intelligent Computing Theories and Applications. Berlin: Springer-Verlag, 2012. 159-166
[4]	Liu Chang-Ping, Ye Chun-Ming. Solving permutation flowshop scheduling problem by firefly algorithm. Industrial Engineering and Management, 2012, 17(3): 56-59(刘长平, 叶春明. 置换流水车间调度问题的萤火虫算法求解. 工业工程与管理, 2012, 17(3): 56-59)
[5]	[5] Tang K, Mei Y, Yao X. Memetic algorithm with extended neighborhood search for capacitated arc routing problems. IEEE Transactions on Evolutionary Computation, 2009, 13(5): 1151-1166
[6]	[6] Wang H F, Moon I, Yang S X, Wang D W. A memetic particle swarm optimization algorithm for multimodal optimization problems. Information Sciences, 2012, 197: 38-52
[7]	Zhang Yong, Gong Dun-Wei, Zhang Wan-Qiu. A simplex method based improved particle swarm optimization and analysis on its global convergence. Acta Automatica Sinica, 2009, 35(3): 289-298(张勇, 巩敦卫, 张婉秋. 一种基于单纯形法的改进微粒群优化算法及其收敛性分析. 自动化学报, 2009, 35(3): 289-298)
[8]	Liu Chang-Ping, Ye Chun-Ming. Mutative scale chaos particle swarm optimization algorithm based on self logical mapping function. Application Research of Computer, 2011 28(8): 2825-2827 (刘长平, 叶春明. 基于逻辑自映射的变尺度混沌粒子群优化算法. 计算机应用研究, 2011, 28(8): 2825-2827)
[9]	[9] Brits R, Engelbrecht A P, Van Den Bergh F. Scalability of niche PSO. In: Proceedings of the 2003 IEEE International Symposium on Swarm Intelligence Symposium. New York, USA: IEEE, 2003. 228-234
[10]	Liang J J, Qin A K, Suganthan P N, Baskar S. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE Transactions on Evolutionary Computation, 2006, 10(3): 281-295
[11]	Li Hang, Li Min-Qiang, Kou Ji-Song. Dynamical behavior of genetic algorithms on multi-modal optimization. Acta Automatica Sinica, 2008, 34(2): 180-187(李航, 李敏强, 寇纪淞. 遗传算法求解多模态优化问题的动力性. 自动化学报, 2008, 34(2): 180-187)
[12]	Wang Z, Tang K, Yao X. A memetic algorithm for multi-level redundancy allocation. IEEE Transactions on Reliability, 2010, 59(4): 754-765
[13]	Li Min-Qiang, Kou Ji-Song. Coordinate multi-population genetic algorithm for multi-modal function optimization Acta Automatica Sinica, 2002, 28(4): 497-504(李敏强, 寇纪淞. 多模态函数优化的协同多群体遗传算法. 自动化学报, 2002, 28(4): 497-504)
[14]	Yang X S. Firefly algorithm, stochastic test functions and design optimisation. International Journal of Bio-Inspired Computation, 2010, 2(2): 78-84
[15]	Liu Chang-Ping, Ye Chun-Ming. Novel bioinspired swarm intelligence optimization algorithm: firefly algorithm. Application Research of Computer, 2011, 28(9): 3295-3297(刘长平, 叶春明. 一种新颖的仿生群智能优化算法: 萤火虫算法. 计算机应用研究, 2011, 28(9): 3295-3297)
[16]	Lee K S, Geem Z W. A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice. Computer Methods in Applied Mechanics and Engineering, 2005, 194: 3902-3933
[17]	Liang J J, Suganthan P N. Dynamic multi-swarm particle swarm optimizer. In: Proceedings of the 2005 IEEE International Swarm Intelligence Symposium. NewYork, USA: IEEE, 2005. 124-129
[18]	Zhao S Z, Suganthan P N, Pan Q K, Tasgetiren M F. Dynamic multi-swarm particle swarm optimizer with harmony search. Expert Systems with Applications, 2011, 38(4): 3735-3742
[19]	Li L, Tang K. History-based topological speciation for multimodal optimization. IEEE Transactions on Evolutionary Computation, 2014, (99): 1, DOI: 10.1109/TEVC.2014.2306677
[20]	Li Min-Qiang, Kou Ji-Song, Lin Dan, Li Shu-Quan. The Basic Theory and Application Genetic Algorithm. Beijing: Science Press, 2002. 78-79(李敏强, 寇纪淞, 林丹, 李书全. 遗传算法的基本理论与应用. 北京: 科学出版社, 2002. 78-79)
[21]	Pan Feng, Chen Jie, Gan Ming-Gang, Cai Tao, Tu Xu-Yan. Model analysis of particle swarm optimizer. Acta Automatica Sinica, 2006, 32(3): 368-377(潘峰, 陈杰, 甘明刚, 蔡涛, 涂序彦. 粒子群优化算法模型分析. 自动化学报, 2006, 32(3): 368-377)
[22]	Pan Feng, Chen Jie, Xin Bin, Zhang Juan. Several characteristics analysis of particle swarm optimizer. Acta Automatica Sinica, 2009, 35(7): 1010-1016(潘峰, 陈杰, 辛斌, 张娟. 粒子群优化方法若干特性分析. 自动化学报, 2009, 35(7): 1010-1016)
[23]	Yu Zhi-Gang, Song Shen-Min, Duan Guang-Ren. On the mechanism and convergence of genetic algorithm. Control and Decision, 2005, 20(9): 971-980(于志刚, 宋申民, 段广仁. 遗传算法的机理与收敛性研究. 控制与决策, 2005, 20(9): 971-980)
[24]	Jin Xin-Lei, Ma Long-Hua, Wu Tie-Jun, Qian Ji-Xin. convergence analysis of the particle swarm optimization based on stochastic processes. Acta Automatica Sinica, 2008, 33(12): 1263-1268(金欣磊, 马龙华, 吴铁军, 钱积新. 基于随机过程的PSO收敛性分析. 自动化学报, 2008, 33(12): 1263-1268)
[25]	Pan Feng, Zhou Qian, Li Wei-Xing, Gao Qi. Analysis of standard particle swarm optimization algorithm based on Markov chain. Acta Automatica Sinica, 2013, 39(4): 381-389(潘峰, 周倩, 李位星, 高琪. 标准粒子群优化算法的马尔科夫链分析. 自动化学报, 2013, 39(4): 381-389)
[26]	Li X D. Niching without niching parameters: particle swarm optimization using a ring topology. IEEE Transactions on Evolutionary Computation, 2010, 14(1): 150-169
[27]	Das S, Abraham A, Chakraborty U K, Konar A. Differential evolution using a neighborhood-based mutation operator. IEEE Transactions on Evolutionary Computation, 2009, 13(3): 526-553
[28]	Li X D. Adaptively choosing neighbourhood bests using species in a particle swarm optimizer for multimodal function optimization. In: Proceedings of the 2004 Genetic and Evolutionary Computation Conference. Berlin, Germany: Springer-Verlag, 2004. 105-116
[29]	Liang J J, Suganthan P N, Deb K. Novel composition test functions for numerical global optimization. In: Proceedings of the 2005 IEEE Swarm Intelligence Symposium. New York, USA: IEEE, 2005. 68-75
[30]	Djuriić A B. Elite genetic algorithms with adaptive mutations for solving continuous optimization problems-application to modeling of the optical constants of solids. Optics Communications, 1998, 151(1-3): 147-159
[31]	Shi Y, Eberhart R C. A modified particle swarm optimizer. In: Proceedings of the 1998 IEEE World Congress on Computational Intelligence. New York, USA: IEEE, 1998. 69-73