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

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

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

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

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

收稿日期:2014-07-07 修回日期:2014-08-28 发布日期:2014-12-31 出版日期:2014-12-01
通讯作者: 李茂军
作者简介:王鼎湘(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-31 Published:2014-12-01
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]	侯阳张琼赵紫煊朱正宇张晓博. 基于YOLOv5s的复杂场景下高效烟火检测算法——YOLOv5s-MRD[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	张奇业, 曾心蕊. 带高斯核的支持向量数据描述问题的高效积极集法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3808-3814.
[3]	曹晓意罗煦琼李景贺恩锋. 改进人工势场法下的多无人机编队路径规划方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[4]	袁志超杨磊田井林魏晓威李康顺. 面向复杂约束多目标优化问题的双种群双阶段进化算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[5]	冷琴, 毛政元. 考虑设施规模决策的两级选址-路径优化[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3513-3520.
[6]	彭庆媛, 王晓峰, 王军霞, 华盈盈, 唐傲, 何飞. 可满足性问题相变研究综述[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3503-3512.
[7]	孙仁科, 皇甫志宇, 陈虎, 李仲年, 许新征. 神经架构搜索综述[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 2983-2994.
[8]	孙安泰, 刘烨, 徐冬梅. 多智能体系统的动态面渐近补偿算法[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3151-3157.
[9]	颜超英, 张紫仪, 曲映楠, 李秋禹, 郑地翔, 孙丽珺. 基于联盟链的双向拍卖碳交易[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3240-3245.
[10]	杨志龙邹德旋李灿邵莹莹马乐杰. 融入限制反向学习与柯西-高斯变异的蜣螂优化算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[11]	姚光磊, 熊菊霞, 杨国武. 基于神经网络优化的花朵授粉算法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2829-2837.
[12]	力尚龙, 刘建华, 贾鹤鸣. 融合多狩猎协调策略的爬行动物搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2818-2828.
[13]	李焱, 潘大志, 郑思情. 多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1897-1904.
[14]	张倩婷胡丽莹陈黎飞. 时间序列的鲁棒形态表征方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[15]	胡林波倪志伟程家乐刘文涛朱旭辉. 基于融合社区检测的复杂协作众包任务分配方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.