通用进化算法的收敛性分析

doi:10.3724/SP.J.1087.2013.01571

计算机应用 ›› 2013, Vol. 33 ›› Issue (06): 1571-1573.DOI: 10.3724/SP.J.1087.2013.01571

通用进化算法的收敛性分析

彭复明¹,姚敏²,白顺科¹

1. 南京工业职业技术学院计算机与软件学院，南京 210046
2. 浙江大学计算机科学与技术学院，杭州 310027

收稿日期:2013-01-04 修回日期:2013-02-22 发布日期:2013-06-05 出版日期:2013-06-01
通讯作者: 彭复明
作者简介:彭复明（1962-）,男,江苏南京人,讲师，硕士,主要研究方向：进化计算；姚敏（1954-）,男,安徽安庆人,教授，博士生导师，博士, 主要研究方向：计算智能、模糊信息处理、模式识别、图像处理；白顺科（1968-）,男,湖北十堰人,讲师，博士, 主要研究方向：测试计量技术与仪器。

Convergence analysis of general evolutionary algorithms

PENG Fuming¹,YAO Min²,BAI Shunke¹

1. College of Computer and Software, Nanjing Institute of Industry Technology, Nanjing Jiangsu 210046, China
2. College of Computer Science and Technology, Zhejiang University, Hangzhou Zhejiang 310027,China

Received:2013-01-04 Revised:2013-02-22 Online:2013-06-05 Published:2013-06-01
Contact: PENG Fuming

摘要/Abstract

摘要： 传统进化算法的收敛性专注于具体算法，对应的研究成果也仅仅适用于具体算法。为了研究所有进化算法的收敛性问题，提出了一种包含所有操作类型算子的通用进化算法，建立了一套概率空间用于研究算法的收敛性，所有有关算法的术语都用严格的数学语言加以定义。在概率空间中，有七个算法收敛性定理被完整地证明，其中之一找到了算法依概率收敛的充分必要条件。更为重要的是，这些定理适用所有进化算法。它建立了一个体系，用来指导进化算法的设计，从理论上判断进化算法的收敛性。

关键词: 收敛, 概率空间, 通用进化算法, 定理, 证明

Abstract: Traditional Evolutionary Algorithm (EA) convergence research focuses on specific algorithm; consequently the conclusion is only suitable for some specific algorithm. In order to study the convergence of all EAs, this paper presented a general EA including EAs of all operator types. A probability space was set up for the purpose of studying the algorithm’s convergence, and all terms on the algorithm were strictly defined in mathematical language, and seven theorems related to the algorithm’s convergence were completely proved in the probability space. One of the theorems found the sufficient and necessary conditions for the algorithm’s convergence in probability. More importantly, these theorems are suitable to all types of EAs. A system composed of these theorems was established, which could be used to guide the EA design and judge the correctness of an EA theoretically.

Key words: convergence, probability space, general evolutionary algorithm, theorem, prove

中图分类号:

TP301.6

彭复明姚敏白顺科. 通用进化算法的收敛性分析[J]. 计算机应用, 2013, 33(06): 1571-1573.

PENG Fuming YAO Min BAI Shunke. Convergence analysis of general evolutionary algorithms[J]. Journal of Computer Applications, 2013, 33(06): 1571-1573.

参考文献

［1］RUDOLPH G. Convergence analysis of canonical genetic algo-rithms［J］．IEEE Transactions on Neural Networks，1994，5(1)：96-101．

［2］黄翰，林智勇，郝志峰，等．基于关系模型的进化算法收敛性分析与对比［J］.计算机学报，2011，34(5)： 801-811.

［3］周育人，闵华清，许孝元，等．多目标演化算法的收敛性研究［J］.计算机学报，2004，27(10)：1415-1421.

［4］严太山，崔杜武．求解无约束优化问题的知识进化算法及其收敛性分析［J］.控制理论与应用，2010，27(10)：1376-1382.

［5］ZHONG W，LIU J，XUE M，et al．A multiagent genetic algorithm for global numerical optimization［J］.IEEE Transactions on Systems，Man and Cybernetics，Part B: Cybernetics，2004，34(2)：1128-1141.

［6］LEUNG Y，WANG Y．An orthogonal genetic algorithm with quantization for global numerical optimization［J］.IEEE Transactions on Evolutionary Computation，2001，5(1)：41-53.

［7］LIU J，ZHONG W，JIAO L．An organizational evolutionary algorithm for numerical optimization［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part B: Cybernetics，2007，37(4)：1052-1064.

［8］EIBEN A E, RUDOLPH G. Theory of evolutionary algorithms: a birds eye view［J］.Theoretical Computer Science，1999，229(1/2)：3-9.

［9］HANNE T．On the convergence of multiobjective evolutionary algorithms［J］.European Journal of Operational Research，1999，117(3): 553-564.

［10］SEMENOV M A, TERKEL D A.Analysis of convergence of an evolutionary algorithm with self-adaptation using a stochastic Lyapunov function［J］. Evolutionary Computation, 2003，11(4)：363-379.

［11］ZHOU Y，HE J.Convergence analysis of a self-adaptive multi-objective evolutionary algorithm based on grids［J］.Information Processing Letters，2007，104(4)：117-122.

［12］RUDOLPH G.On a multi-objective evolutionary algorithm and its convergence to the pareto set［C］// Proceedings of the 2nd IEEE World Congress on Computational Intelligence. Piscataway:IEEE,1998:511-516.

［13］KHOSRAVIANI M, POUR-MOZAFARI S, EBADZADEH M M. Convergence analysis of quantum-inspired genetic algorithms with the population of a single individual［C］// Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation. New York:ACM，2008:1115-1116.

［14］CHAKRABORTY P, DAS S, ROY G G,et al. On convergence of the multi-objective particle swarm optimizers［J］．Information Sciences，2011，181(8)：1411-1425.

［15］CHUNG K L. A course in probability［M］. 3rd ed. New York: Academic Press，2001:76-77.

［16］RUDOLPH G.Convergence of evolutionary algorithms in general search spaces［C］// Proceedings of IEEE International Conference on Evolutionary Computation. Piscataway: IEEE，1996:50-54.

［17］RUDOLPH G，AGAPIE A．Convergence properties of some multi-objective evolutionary algorithms［C］// Proceedings of the 2000 Congress on Evolutionary Computation. Piscataway: IEEE, 2000:1010-1016.

［18］HE J，YU X．Conditions for the convergence of evolutionary algorithms［J］．Journal of Systems Architecture,2001，47(7)：601-612.

［19］ZHAO X C．Convergent analysis on evolutionary algorithm with non-uniform mutation［C］// Proceedings of the IEEE Congress on Evolutionary Computation．Piscataway: IEEE，2008: 940-944.

[1]	尹新媛, 郑小建, 熊金波. 格上无非交互式零知识证明的两轮三方PAKE协议[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 805-810.
[2]	贾淼, 姚中原, 祝卫华, 高婷婷, 斯雪明, 邓翔. 零知识证明赋能区块链的进展与展望[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3669-3677.
[3]	赵振皓, 张仕斌, 万武南, 张金全, 秦智. 基于信誉值和强盲签名算法的委托权益证明共识算法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3717-3722.
[4]	王一帆, 林绍福, 李云江. 基于区块链和零知识证明的高速公路自由流收费方法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3741-3750.
[5]	陶文萱, 陈钢. 基于二幂阶矩阵的量子中间表示与翻译[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3141-3150.
[6]	曹锋, 杨小玲, 易见兵, 李俊. 矛盾体分离超演绎方法及应用[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3074-3080.
[7]	马勇健, 史旭华, 王佩瑶. 基于两阶段搜索与动态资源分配的约束多目标进化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 269-277.
[8]	欧云, 周恺卿, 尹鹏飞, 刘雪薇. 双收敛因子策略下的改进灰狼优化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2679-2685.
[9]	徐赛娟, 裴镇宇, 林佳炜, 刘耿耿. 基于多阶段搜索的约束多目标进化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2345-2351.
[10]	唐淑敏, 金瑜. 区块链中基于中国剩余定理投票方案的共识机制[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 458-466.
[11]	黄霖, 符强, 童楠. 基于自适应调整哈里斯鹰优化算法求解机器人路径规划问题[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3840-3847.
[12]	徐贵双, 殷新春. 车载自组网无证书条件隐私保护认证方案[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3358-3367.
[13]	赵洪, 喻书涵, 韩妍妍, 李兆斌. 无证书签名方案的分析与改进[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 147-153.
[14]	沙林秀, 聂凡, 高倩, 孟号. 基于布朗运动与梯度信息的交替优化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2139-2145.
[15]	聂青青, 万定生, 朱跃龙, 李致家, 姚成. 基于时域卷积网络的水文模型[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1756-1761.

通用进化算法的收敛性分析

Convergence analysis of general evolutionary algorithms

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics