交叉型状态空间模型进化算法的全局收敛性分析

计算机应用 ›› 2014, Vol. 34 ›› Issue (12): 3424-3427.

交叉型状态空间模型进化算法的全局收敛性分析

王鼎湘,李茂军,李雪,成立

长沙理工大学电气与信息工程学院,长沙 410004

收稿日期:2014-07-07 修回日期:2014-08-28 出版日期:2014-12-01 发布日期:2014-12-31
通讯作者: 李茂军
作者简介:王鼎湘(1991-),男,湖南长沙人,硕士研究生,主要研究方向:智能控制、图像处理；李茂军(1964-),男,湖南长沙人,教授,博士,主要研究方向:智能计算；李雪(1989-）,女,湖南岳阳人,硕士研究生,主要研究方向:智能计算；成立(1989-）,男,湖南株洲人,硕士研究生,主要研究方向:智能计算。
基金资助:
国家自然科学基金资助项目

Analysis of global convergence of crossover evolutionary algorithm based on state-space model

WANG Dingxiang,LI Maojun,LI Xue,CHENG Li

College of Electrical and Information Engineering, Changsha University of Science and Technology, Changsha Hunan 410004, China

Received:2014-07-07 Revised:2014-08-28 Online:2014-12-01 Published:2014-12-31
Contact: LI Maojun

摘要/Abstract

摘要：

基于状态空间模型的进化算法(SEA)是一种新颖的实数编码进化算法,在实际工程优化问题中取得了良好的优化效果。为促进SEA的理论及应用研究,对交叉型SEA(SCEA)的全局收敛性进行了研究,得出SCEA不是全局收敛的结论。通过改变状态进化矩阵的构造方式和提出弹力搜索操作,得到改进交叉型SEA(SMCEA),利用齐次有限Markov链对SMCEA的全局收敛性进行了证明。最后利用两个测试函数对算法进行实验分析,结果表明,SMCEA在收敛速度、最优解搜索能力和运算时间等方面都有较大改善,验证了SMCEA的有效性,得到了SMCEA优于遗传算法(GA)和SCEA的结论。

Abstract:

Evolutionary Algorithm based on State-space model (SEA) is a novel real-coded evolutionary algorithm, it has good optimization effects in engineering optimization problems. Global convergence of crossover SEA (SCEA) was studied to promote the theory and application research of SEA. The conclusion that SCEA is not global convergent was drawn. Modified Crossover Evolutionary Algorithm based on State-space Model (SMCEA) was presented by changing the comstruction way of state evolution matrix and introducing elastic search operation. SMCEA is global convergent was proved by homogeneous finite Markov chain. By using two test functions to experimental analysis, the results show that the SMCEA are improved substantially in such aspects as convergence rate, ability of reaching the optimal value and operation time. Then, the effectiveness of SMCEA is proved and that SMCEA is better than Genetic Algorithm (GA) and SCEA was concluded.

中图分类号:

TP301.6

王鼎湘李茂军李雪成立. 交叉型状态空间模型进化算法的全局收敛性分析[J]. 计算机应用, 2014, 34(12): 3424-3427.

WANG Dingxiang LI Maojun LI Xue CHENG Li. Analysis of global convergence of crossover evolutionary algorithm based on state-space model[J]. Journal of Computer Applications, 2014, 34(12): 3424-3427.

参考文献

［1］SHARAPOV R R,LAPSHIN A V. Convergence of genetic algorithms［J］. Pattern Recognition and Image Analysis, 2006, 16(3):392-397.
［2］NICOARA E S. Mechanisms to avoid the premature convergence of genetic algorithms［J］. Bulletin of PG University of Ploiesti, Series Mathematics, Informatics, Physics, 2009, 61(1):87-96.
［3］SHENG Y, YI L, WEI Y. An improved genetic algorithm of fast realization in multimodal function optimizations［J］. Journal of Southwest University of Science and Technology, 2009,24(2):82-87.(盛鹰,易丽清,魏泳涛.一种快速实现多峰值函数优化的改进遗传算法［J］. 西南科技大学学报,2009,24(2):82-87.)
［4］RIGAL L, TRUFFET L. A new genetic algorithm specifically based on mutation and selection［J］. Advances in Applied Probability,2007, 39(1):141-161.
［5］ZHU S, SHAO G, WANG H. Immune genetic algorithm based on antibody injection［J］. Journal of Computer Applications, 2009,29(6):1536-1538 (朱思峰,邵国金,王华东.基于抗体注射的免疫遗传算法［J］.计算机应用,2009,29(6):1536-1538.)
［6］CAO X, ZHENG Z, FAN L, et al. An improved genetic algorithm mixed with neural network［J］. Pattern Recognition and Artificial Intelligence, 1999,12(4):486-491.(曹先彬,郑振,范磊,等.融合神经网络的一种改进遗传算法［J］.模式识别与人工智能,1999,12(4):486-491.)
［7］DING J, CHEN Z, YUAN Z. On the Markov convergence analysis for the combination of genetic algorithm and ant algorithm［J］. Acta Automatica Sinica, 2004, 30(4):629-634.(丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法融合的马尔可夫收敛性分析［J］. 自动化学报,2004,30(4):629-634.)
［8］PAN W, DIAO H, JING Y. An improved real-value adaptive genetic algorithm［J］. Control and Decision, 2006,21(7):792-795.(潘伟,刁华宗,井元伟.一种改进的实数自适应遗传算法［J］.控制与决策,2006,21(7):792-795.)
［9］ZHENG J, LYU H, WU J, et al. Convergence analysis of genetic algorithm based on space mating［J］. Pattern Recognition and Artificial Intelligence, 2010,23(5):639-645.(郑金华,吕卉,伍军,等. 基于空间交配遗传算法的收敛性分析［J］. 模式识别与人工智能,2010,23(5):639-645.）
［10］FU H, LI M. Bionic algorithm based on state-space model with application in bidding for power market［J］. Computing Technology and Automation, 2009,28(2):81-84.(付宏艳,李茂军. 基于状态空间模型的仿生算法在电力市场竞价中的应用［J］. 计算技术与自动化, 2009,28(2):81-84.）
［11］MAO Y. Multi-objective reactive power optimization based on bionic algorithm with state-space model［D］. Changsha: Changsha University of Science and Technology,2009.(毛盈旎. 基于状态空间模型仿生算法的多目标无功优化［D］. 长沙:长沙理工大学,2009.）
［12］LIN D, LI M, KOU J. On the convergence of real-coded genetic algorithms［J］. Journal of Computer Research and Development, 2000,37(11): 1321-1327.(林丹,李敏强,寇纪凇. 基于实数编码的遗传算法的收敛性研究［J］. 计算机研究与发展,2000,37(11):1321-1327.）
［13］ZHANG C, ZHENG J, QIAN J. Comparison of coding schemes for genetic algorithms［J］. Application Research of Computers, 2011,28(3):819-822. (张超群, 郑建国, 钱洁. 遗传算法编码方案比较［J］. 计算机应用研究, 2011, 28(3):819-822.)

[1]	肖智豪胡志华朱琳. 求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法[J]. 计算机应用, 0, (): 0-0.
[2]	沙林秀，聂凡，高倩，孟号. 基于布朗运动与梯度信息的交替优化算法[J]. 计算机应用, 0, (): 0-0.
[3]	董永峰孙跃华高立超韩鹏季海鹏. 基于改进一维卷积和双向长短期记忆神经网络的故障诊断方法[J]. 计算机应用, 0, (): 0-0.
[4]	李大海刘庆腾艾志刚王振东. 基于动态D向分割和混沌扰动的阴阳对算法[J]. 计算机应用, 0, (): 0-0.
[5]	雷鹰郑万波魏嵬夏云霓李晓波刘诚武谢洪. 基于概率性能感知演化博弈策略的混合“云+边”环境中任务卸载方法 [J]. 计算机应用, 0, (): 0-0.
[6]	乔钢柱王瑞孙超利. 基于分解的高维多目标改进进化算法[J]. 计算机应用, 0, (): 0-0.
[7]	朱诚潘旭华张勇. 基于趋化校正的哈里斯鹰优化算法[J]. 计算机应用, 0, (): 0-0.
[8]	平凡汤小春潘彦宇李战怀. 不规则任务在图形处理器集群上的调度策略[J]. 计算机应用, 0, (): 0-0.
[9]	杨杰张名扬芮晓彬王志晓. 融合节点覆盖范围和结构洞的影响力最大化算法[J]. 计算机应用, 0, (): 0-0.
[10]	汤安迪, 韩统, 徐登武, 谢磊. 混沌精英哈里斯鹰优化算法[J]. 计算机应用, 2021, 41(8): 2265-2272.
[11]	李蒙蒙, 秦伟, 刘艺, 刁兴春. 结合头脑风暴优化的混合蚁群优化算法[J]. 计算机应用, 2021, 41(8): 2412-2417.
[12]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[13]	张祥飞, 鲁宇明, 张平生. 基于协同进化的约束多目标优化算法[J]. 计算机应用, 2021, 41(7): 2012-2018.
[14]	张萌, 李维华. 用户互动表示下的影响力最大化算法[J]. 计算机应用, 2021, 41(7): 1964-1969.
[15]	王宇, 刘燕丽, 陈劭武. 基于顶点冲突学习的最大公共子图算法[J]. 计算机应用, 2021, 41(6): 1756-1760.