自适应差分演化算法及其应用研究

发布时间：2017-04-20 05:12

  本文关键词：自适应差分演化算法及其应用研究，由笔耕文化传播整理发布。

【摘要】：近年来,计算智能领域飞速发展,特别是演化计算,作为一门新兴学科发展相当迅速。演化计算中用到所有算法统称为演化算法,主要包括演化规划、演化策略、遗传编程、遗传算法等。演化算法具有自适应、自搜索、并行性等特点,己在很多工程领域得到广泛应用。差分演化算法是连续搜索空间上全局优化的有效算法,已被证明是解决实值优化问题的有效候选算法。差分演化算法表述简洁,并且易于操作,由于其特有的较强优越性,它已在诸多领域中得到广泛的应用。如工程设计、生物与化学工程、控制工程、电力调度与规划、神经网络与模糊控制设计、信号处理等。本文仅仅研究了自适应差分演化算法的两个改进算法及其应用。首先分析了标准差分演化算法中控制参数对算法的影响,设计了基于个体适应值的自适应差分演化算法；其次为了将自适应差分演化算法应用于求解组合优化问题,本文设计了基于集合的自适应离散差分演化算法；再次,本文将基于自适应差分演化算法应用于模糊核聚类算法中；最后,研究基于自适应离散差分演化生成安全椭圆曲线的问题和生成De Bruijn序列的问题。本文的主要研究内容和创新点具体如下：1.提出基于个体适应值的自适应差分演化算法。差分演化算法中存在种群规模NP、缩放因子F和杂交概率CR等3个控制参数。对于大多数优化问题,这些控制参数会直接影响算法搜索结果,即搜索最优解。同时这些控制参数也会直接影响算法的收敛性能,针对不同的问题需要进行不同的设置。很多专家建议种群规模NP∈[5D,10D],缩放因子F∈[0,1],杂交概率CR∈[0,1]。对于标准差分演化算法,在演化进程的不同阶段,个体的差异性是不一样的。这是由于个体在搜索空间所处的位置不同所造成的,于是设定差分演化算法的控制参数无法满足算法在不同阶段的性能要求。在差分演化算法中,其缩放因子F和杂交概率CR等控制参数的选择会直接影响算法搜索结果,即搜索最优解。因此,应考虑缩放因子F和杂交概率CR能够随着个体的适应值动态调整。杂交概率用于表示待变异个体的基因选入新个体的概率。当前大部分差分演化算法的参数自适应机制利用参数的随机调整策略。仿真实验显示随机调整策略仅在参数设置不合适的情况下才算是一种好的选择。但是参数的随机调整忽视其有效性可能导致丢失高质量的参数值。因此,在本文的自适应差分演化算法中保留了产生高质量个体的参数设置,只调整不能产生高质量个体的参数。本文提出了一种基于个体适应值的自适应差分演化算法(The Individual Adaptive Value Based Self-adaptive Differential evolution Algorithm, IAVBSaDE)从仿真实验结果来看,本文提出的自适应差分算法在多个函数中得到更好的结果。个别函数得到与真实最优解相同的结果,真正找到了最佳解决方案。总之,本文提出的算法具有较强的竞争力,在四种算法结果中优于或近似于迭代运算的最优解。2.提出基于集合的自适应离散差分演化算法(SBSaDDE)。差分演化算法是连续搜索空间上全局优化的有效算法,已被证明是解决实值优化问题的有效候选算法。差分演化算法表述简洁,并且易于操作,可它能收敛到搜索空间的期望区域,找到一些问题的最优解。然而,标准差分演化算法仅限于解决连续决策变量的问题。所以,将其应用于组合优化问题非常有限。旅行商问题被认为是经典的离散优化问题。同时,差分演化算法已被证明是一个强大的演化算法,但是它的变异过程包含一系列的算术运算都是作用在连续空间。最近几年,研究人员开始致力于使用差分演化算法来解决组合优化问题。许多相关的研究大都集中在改进差分演化算法来解决基于排列的组合优化问题。为了将自适应差分演化算法应用于求解组合优化问题,本文提出了一种基于集合的自适应离散差分演化算法。为了使算法能够刻画旅行商问题的离散搜索空间,候选解向量和算术运算子都是重新定义的。通过数值试验,提出的方法被证明在质量和前景上都是有效的。通过将SBSaDDE与当前最前沿的离散差分演化算法—离散差分演化算法(DDE)、带有最小值定位变异策略的离散差分演化算法(DDE-SVP)。这些离散差分演化算法的参数设置遵照原文中的参数。仿真结果表明：本人提出的算法不论在平均解还是最优解都胜于DDE和DDE-SVP等离散差分演化算法。3.提出基于自适应差分演化算法的模糊核聚类算法。模糊C均值聚类算法和模糊核聚类算法都是基于目标函数的聚类算法,目标函数的全局最值点对应着聚类算法的最优聚类结果,由于现实生活中具体的实际问题,其目标函数往往存在许多个局部极值点,而模糊聚类算法的每一步迭代,都是减小目标函数值,至少不增加目标函数值。因此,如果初始化时聚类算法落在一个局部极值点附近,就很可能会造成算法收敛到局部最优,这势必将影响聚类结果,使得算法不能实现全局最优。差分演化算法是一种简单高效且易于操作的并行搜索算法,具有特有的较强的全局搜索能力。本文提出基于个体适应值的自适应差分演化算法用于模糊核聚类算法(Self-adaptive Differential Evolution Based Kernel FCM, SaDEBKFCM),利用算法SaDEBKFCM得到更佳的聚类中心以及隶属度矩阵,其目的是增强两种模糊聚类算法(FCM, KFCM)的全局优化能力。通过仿真实验,在IRIS数据集上,相比其他三种方法,SaDEBKFCM聚类算法尽管平均运行时间稍长,但是该算法的聚类效果很好,比FCM和GAFCM两种算法的正确率有明显提高,比DEFCM算法的正确率稍有提高。4.研究基于自适应离散差分演化生成安全椭圆曲线的问题。随着云计算、物联网等新技术新应用的快速发展,椭圆曲线密码体制可以很好地运用于云计算安全、移动终端安全等安全应用。为了将差分演化算法应用于生成Koblitz安全椭圆曲线,本文提出一种基于集合的自适应离散差分演化算法生成安全椭圆曲线的方法,产生的安全椭圆曲线基域的范围、曲线的规模和产生的效率均超过美国国家标准与技术研究所(NIST)公布的相关参数。本文的算法搜索的安全椭圆曲线基于最大为1913比特,远超美国NIST公布的最高571比特基域,对现有的攻击方法起到很好的防护作用。同时,本文的算法在163比特以上的安全椭圆曲线基域为19个(a=0,b=1时有9个：233,571,1913等；a=1,b=1时有10个：163,283,701等),完全覆盖了美国NIST推荐的5个基域的安全椭圆曲线。5.研究基于自适应离散差分演化生成De Bruijn序列的问题。二元n阶de Bruijn序列是周期为2”的循环序列,在一个周期内每一个n比特串仅且出现一次。de Bruijn序列是稳定的,也就是说,1和0的个数相同,并且有良好的随机性。由于de Bruijn序列具有良好的统计特性,所以,它已成为常用的随机数生成方法,也是流密码等对称加密体制的密钥生成方法之一。本文提出基于自适应差分演化算法的随机化构造方法。该构造方法将de Bruijn序列模拟成一种特殊类型的旅行商问题(TSP),并试图找到最优解。对于n=3,4,…,10,每一个种群规模本文都是重复实验100次。如果输出旅行路径长度为2”,即找到了最优路径,那么就认为算法是成功的。实验证明,本文设计的基于自适应离散差分演化算法生成de Bruijn序列的模型,具有成功率高、运行速度快、算法易于编程实现、消耗的计算机内存资源小、搜索的序列数目多等优点。综上所述,本文在分析了已有的自适应差分演化算法的基础上,重点研究了基于个体适应值的自适应差分演化算法和基于集合的自适应离散差分演化算法两种改进自适应差分演化算法。通过将两种改进的自适应差分演化算法分别用于模糊核聚类、生成安全椭圆曲线和de Bruijn序列的算法等实际应用中。在研究中通过实验的方法证明了各算法的有效性。
【关键词】：演化计算 差分演化算法 自适应差分演化算法 演化密码 de Bruijn序列 安全椭圆曲线
【学位授予单位】：中国地质大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP18
【目录】：

• 作者简介6-8
• 摘要8-11
• ABSTRACT11-17
• 第一章 绪论17-30
• §1.1 研究背景17-20
• §1.2 国内外研究现状20-25
• 1.2.1 改进差分演化算法的操作20
• 1.2.2 加入新的操作20-21
• 1.2.3 参数自适应差分演化算法21-22
• 1.2.4 混合差分演化算法22-23
• 1.2.5 多策略差分演化算法23-25
• §1.3 本文研究目的及研究内容25-29
• 1.3.1 文本研究目的25-26
• 1.3.2 本文的主要研究内容26-28
• 1.3.3 拟解决的关键问题28-29
• §1.4 论文结构安排29-30
• 第二章 差分演化算法概论30-36
• §2.1 标准差分演化算法30-33
• 2.1.1 变异操作30-31
• 2.1.2 杂交操作31
• 2.1.3 选择操作31-32
• 2.1.4 标准差分演化算法基本流程32-33
• 2.1.5 标准差分演化算法的控制参数33
• §2.2 差分演化算法的应用33-36
• 第三章 改进的自适应差分演化算法36-52
• §3.1 基于个体适应值的自适应差分演化算法36-44
• 3.1.1 缩放因子的自适应36-37
• 3.1.2 杂交概率的自适应37-38
• 3.1.3 实验结果分析38-44
• §3.2 基于集合的自适应离散差分演化算法44-52
• 3.2.1 算法结构44-48
• 3.2.2 参数自适应策略48-49
• 3.2.3 试验结果分析49-52
• 第四章 自适应差分演化算法在模糊聚类中的应用52-69
• §4.1 模糊集的基本概念52-54
• §4.2 模糊集合的运算、关系及矩阵54-57
• §4.3 模糊聚类分析的一般步骤57-61
• 4.3.1 标准化数据57-58
• 4.3.2 确定模糊矩阵58-60
• 4.3.3 模糊聚类60-61
• §4.4 自适应差分演化算法在模糊核聚类分析中的应用61-69
• 4.4.1 算法中相关策略63-64
• 4.4.2 基于自适应差分演化算法的模糊核聚类算法步骤64-65
• 4.4.3 仿真实验结果分析65-69
• 第五章 基于自适应差分演化算法生成安全椭圆曲线69-81
• §5.1 椭圆曲线及相关概念69-73
• §5.2 二进制域F_2~m及安全椭圆曲线的标准73-75
• 5.2.1 二进制域73
• 5.2.2 安全椭圆曲线的标准73-75
• §5.3 基于集合的自适应离散差分演化算法生成安全椭圆曲线75-81
• 5.3.1 基于离散自适应差分演化算法生成Koblitz安全椭圆曲线75-78
• 5.3.2 基于离散自适应差分演化算法生成Koblitz椭圆曲线的安全性分析78-81
• 第六章 自适应差分演化算法生成DE BRUUN序列81-92
• §6.1 引言81-84
• §6.2 生成DE BRUIJN序列的方法84-86
• §6.3 一种特殊类型的TSP：TSP_n~*86-88
• §6.4 基于集合的自适应离散差分演化算法构造DE BRUIJN序列88-92
• 6.4.1 算法的理论基础88
• 6.4.2 算法的模型88-89
• 6.4.3 算法的步骤89-90
• 6.4.4 试验结果及分析90-91
• 6.4.5 实验结果分析91-92
• 第七章 总结与展望92-96
• §7.1 研究成果总结92-95
• §7.2 研究展望95-96
• 致谢96-97
• 参考文献97-105

【相似文献】

中国期刊全文数据库 前10条

1 龚文引;谢丹;;针对本科生的演化算法教学探讨[J];计算机时代;2012年07期

2 熊盛武,李元香,康立山,陈毓屏;用演化算法求解抛物型方程扩散系数的识别问题[J];计算机学报;2000年03期

3 曾三友,康立山,丁立新;基于偏序关系的演化算法[J];计算机工程;2001年08期

4 周永华,毛宗源;基于混合杂交与间歇变异的演化算法[J];计算机工程与应用;2003年06期

5 闫震宇,康立山,陈毓屏,付朋辉;一种新的多目标演化算法——稳态淘汰演化算法[J];武汉大学学报(理学版);2003年01期

6 王涛,李歧强;基于空间收缩的并行演化算法[J];中国工程科学;2003年03期

7 何国良,李元香;多个粒子参与交叉的一种动态演化算法[J];计算机工程与应用;2004年08期

8 刘敏忠,邹秀芬,康立山;一种基于偏序排名的高效的多目标演化算法[J];小型微型计算机系统;2004年12期

9 王龙奎,汪祖柱;关于多目标演化算法的策略分析[J];安徽大学学报(自然科学版);2005年03期

10 田丽,林锦国,刘建峰,张光云;基于演化算法的客户关系管理系统研究[J];微处理机;2005年03期

中国重要会议论文全文数据库 前3条

1 冯珊;李锋;周凯波;;面向演化算法应用的智能体系统建模与仿真研究[A];西部开发与系统工程——中国系统工程学会第12届年会论文集[C];2002年

2 张文俊;谢晓锋;马君;;并行演化算法在半导体器件综合中的应用[A];2006年全国开放式分布与并行计算学术会议论文集（二）[C];2006年

3 谢柏桥;戴光明;郑蔚;王剑文;;有指导的多目标演化算法在区域星座设计中的应用[A];中国宇航学会深空探测技术专业委员会第四届学术年会论文集[C];2007年

中国博士学位论文全文数据库 前10条

1 俞扬;演化计算理论分析与学习算法的研究[D];南京大学;2011年

2 库俊华;自适应差分演化算法及其应用研究[D];中国地质大学;2015年

3 彭晟;演化算法的静电场论模型[D];武汉大学;2011年

4 陈明;演化算法渐近行为的若干问题研究[D];武汉大学;2012年

5 彭飞;实值演化算法投资组合研究[D];中国科学技术大学;2011年

6 万书振;动态环境下差分演化算法研究与应用[D];武汉理工大学;2012年

7 魏波;交互式与自适应演化算法研究[D];武汉大学;2013年

8 赖鑫生;演化算法与混合算法的性能研究[D];华南理工大学;2014年

9 武志峰;差异演化算法及其应用研究[D];北京交通大学;2009年

10 陈天石;演化算法的计算复杂性研究[D];中国科学技术大学;2010年

中国硕士学位论文全文数据库 前10条

1 杨颖;一种多差分向量的自适应差分演化算法[D];浙江大学;2015年

2 陈伟;队伍演化算法及其在微波电路设计中的应用[D];杭州电子科技大学;2015年

3 吴昊;多群体并行演化算法的研究[D];南京邮电大学;2015年

4 要婷婷;基于模因演化算法的有限容量弧路径问题研究[D];北京交通大学;2016年

5 邢雪;基于Pi演算的关系演化算法的研究与实现[D];吉林大学;2016年

6 戴志晃;一种基于熵量守恒的改进演化算法的研究[D];江西理工大学;2010年

7 潘伟丰;一种基于平均矢量偏差的仿生演化算法[D];江西理工大学;2008年

8 胡中波;差分演化算法及其在函数优化中的应用研究[D];武汉理工大学;2006年

9 李程俊;组合优化问题的并行演化算法研究[D];武汉理工大学;2003年

10 赵永翔;多目标差分演化算法的构造及其应用[D];武汉理工大学;2007年

  本文关键词：自适应差分演化算法及其应用研究，，由笔耕文化传播整理发布。

本文编号：317969