基于差分进化的约束求解算法研究

发布时间：2017-03-18 18:06

  本文关键词：基于差分进化的约束求解算法研究，由笔耕文化传播整理发布。

【摘要】：约束满足问题(Contraint Satisfaction Problems,CSPs)是运筹学和人工智能研究领域的一个重要方向,在人们身边,众多实际问题都能够转化为CSPs来求解。CSPs研究大体上分为表示领域的语言方向和推理领域的算法方向,这两个方向是CSPs研究的两大重要方向,若再细分,表示可分为通用表示和专用表示,推理又可分为约束传播和搜索。CSPs通常都是NP-hard问题,它是由一个变量集合和一个约束集合组成的,求解CSPs也就是为它的变量集合寻找一组赋值,并使其满足它的约束集合,这样的一组赋值就称为CSPs的解。而求解CSPs的方法一般可分为完备性求解算法和非完备性算法。完备性求解算法是基于回溯的搜索算法(BT-backtracking algorithm),该算法在选择实例化变量时,采用深度优先策略,若未找到解则启动回溯机制,直到找到一组解,或者证明该问题是无解的;非完备性求解算法一般是指群体智能算法,通过模拟生物群体的一些行为(如觅食,集聚,进化等),经过迭代最终寻找到最优解,本文所涉及的群体智能算法是差分进化算法。在差分进化算法中,变量的每个可能解叫做参数向量或者基因,差分进化的求解步骤与标准进化算法(Evolutionary Algorithm,EA)大体相同,但却不同于传统进化算法,差分进化算法主要依赖差分向量来扰动当前的试验向量,利用参数向量的差异来探索目标区域。自上世纪90年代后期,在科学与工程领域的优化问题中,差分进化算法的影响力逐步增强,并且有着重要的地位。它的优势明显,首先,与其它进化算法相比,差分进化算法更易直接实现,无论用什么程序语言,算法的主体仅需四到五行代码就可以编写出来;其次,在求解单峰、多峰、离散、连续等问题时,差分进化算法展现出了较好的性能优势,超越了很多算法;再次,差分进化算法的控制参数较少,主要包括种交叉概率CR、缩放系数F、种群规模NP三个控制参数,算法的性能主要也是取决于这三个控制参数;最后,与一些最有竞争力的实参优化器(如自适应协方差矩阵进化策略CMA-ES)相比,差分进化算法的空间复杂度较低。本文提出了基于弧相容技术AC的自适应差分进化算法——AC-FSADE算法,与SADE算法相比,该算法有着三处改进部分,首先,对控制变异操作的缩放系数F进行基于个体适应度的更新,进化开始阶段,缩放系数F较大,搜索步长,有助于算法开拓探索空间,进化后期,缩放系数F较小,搜索步短,有助于算法快速收敛;其次,对控制交叉操作的交叉概率CR也进行基于个体适应度的更新,进化开始阶段,交叉概率CR较小,防止早熟收敛,有助于保持种群多样性,进化后期,交叉概率CR较大,有助于个体保留较好的基因;最后,将弧相容技术AC融入SADE算法中,剔除变量论域中的无效值,减小变量论域,简化算法求解的问题,提高求解成功率。实验结果表明,本文提出AC-FSADE算法有效地提高了算法的求解成功率,与SADE算法相比求解成功率提高了22%左右。所以,在求解CSPs时,AC-FSADE算法是一种比较有潜力的差分进化算法,发展前景广阔。
【关键词】：约束满足问题 差分进化算法 弧相容 自适应 参数调整 适应度
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【目录】：

• 摘要4-6
• Abstract6-11
• 第1章 绪论11-15
• 1.1 研究背景11-12
• 1.2 研究现状12-13
• 1.3 本文工作13-15
• 第2章 约束满足问题与差分进化算法15-36
• 2.1 引言15-19
• 2.1.1 约束满足问题15-18
• 2.1.2 差分进化算法18-19
• 2.2 约束满足问题19-24
• 2.2.1 基本定义20-21
• 2.2.2 约束传播和搜索21
• 2.2.3 随机约束满足问题21-24
• 2.3 基本差分进化算法24-30
• 2.3.1 问题描述25
• 2.3.2 主要流程25-29
• 2.3.3 基本思想29-30
• 2.4 改进的自适应差分进化算法FSADE30-36
• 2.4.1 SADE算法控制参数的设置31-32
• 2.4.2 SADE算法控制参数的改进32-33
• 2.4.3 FSADE算法原理33-36
• 第3章 弧相容技术与AC-FSADE算法36-46
• 3.1 弧相容技术36-44
• 3.1.1 一般弧相容定义37-39
• 3.1.2 一般弧相容算法39-44
• 3.2 基于弧相容技术的AC-FSADE算法44-46
• 第4章 AC-FSADE算法求解随机CSPs46-52
• 4.1 AC-FSADE算法46-48
• 4.2 实验结果及分析48-51
• 4.2.1 实验设置48-49
• 4.2.2 实验结果及分析49-51
• 4.3 小结51-52
• 第5章 结束语52-54
• 5.1 总结52
• 5.2 展望52-54
• 参考文献54-58
• 作者简介58-59
• 致谢59

【相似文献】

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

1 吴燕玲;卢建刚;孙优贤;;基于免疫原理的差分进化[J];控制与决策;2007年11期

2 杨启文;蔡亮;薛云灿;;差分进化算法综述[J];模式识别与人工智能;2008年04期

3 许小健;黄小平;钱德玲;;自适应加速差分进化算法[J];复杂系统与复杂性科学;2008年01期

4 宁桂英;周永权;;基于优进策略的新差分进化算法动力学模型参数的估计[J];计算机与应用化学;2008年05期

5 谭跃;谭冠政;涂立;;一种新的混沌差分进化算法[J];计算机工程;2009年11期

6 王培崇;钱旭;王月;虎晓红;;差分进化计算研究综述[J];计算机工程与应用;2009年28期

7 肖术骏;朱学峰;;一种改进的快速高效的差分进化算法[J];合肥工业大学学报(自然科学版);2009年11期

8 周萧;王万良;徐新黎;;解决作业车间调度问题的混合差分进化算法[J];轻工机械;2010年05期

9 王艳宜;;改进差分进化算法及其应用[J];机械设计与研究;2010年05期

10 张照生;罗健旭;;基于差分进化算法的模糊神经网络控制器[J];计算机与应用化学;2011年12期

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

1 陆丝馨;肖健梅;王锡淮;;基于改进差分进化算法的舰船电网重构[A];第二十九届中国控制会议论文集[C];2010年

2 楼洋;李均利;陈刚;;基于个体排序的差分进化算法[A];'2010系统仿真技术及其应用学术会议论文集[C];2010年

3 张倩;李海港;;多目标问题的差分进化算法研究[A];2009年中国智能自动化会议论文集（第一分册）[C];2009年

4 裴振奎;刘真;赵艳丽;;差分进化算法在多目标路径规划中的应用[A];中国运筹学会模糊信息与模糊工程分会第五届学术年会论文集[C];2010年

5 刘国帅;杨侃;陈静;周景舒;周冉;郑姣;;差分进化算法在三峡电站厂内经济运行中的应用[A];中国水文科技新发展——2012中国水文学术讨论会论文集[C];2012年

6 刘潇;桂卫华;王雅琳;王晓丽;阳春华;;一种改进的多目标差分进化算法研究[A];中国自动化学会中南六省（区）2010年第28届年会·论文集[C];2010年

7 赵娟;蔡涛;邓方;杨红伟;;基于改进差分进化算法的脉冲控制方法[A];中国自动化学会控制理论专业委员会B卷[C];2011年

8 袁沈坚;顾幸生;;基于差分进化的膜计算优化算法[A];上海市化学化工学会2010年度学术年会论文集（自动化专题）[C];2010年

9 姜立强;郭铮;刘光斌;;差分进化算法缩放因子取值策略研究[A];2007'仪表，自动化及先进集成技术大会论文集（二）[C];2007年

10 倪惠康;杜文莉;钱锋;;基于改进差分进化算法的PID参数优[A];2009年中国智能自动化会议论文集（第一分册）[C];2009年

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

1 孙浩;差分进化多目标优化算法及其在铝热连轧轧制规程中应用[D];燕山大学;2015年

2 陈盈果;面向任务的快速响应空间卫星部署优化设计方法研究[D];国防科学技术大学;2014年

3 谢宇;差分进化的若干问题及其应用研究[D];南京理工大学;2015年

4 丁青锋;基于元胞自动机的差分进化算法及其在通信系统中的应用研究[D];上海大学;2015年

5 贾东立;改进的差分进化算法及其在通信信号处理中的应用研究[D];上海大学;2011年

6 刘荣辉;多阶段自适应差分进化算法及应用研究[D];东华大学;2012年

7 郭鹏;差分进化算法改进研究[D];天津大学;2012年

8 王旭;改进差分进化算法及其在可逆逻辑综合中的应用[D];东华大学;2013年

9 董明刚;基于差分进化的优化算法及应用研究[D];浙江大学;2012年

10 王天意;大地电磁迭代有限元与改进差分进化正反演算法研究[D];中国地质大学(北京);2015年

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

1 高静;量子差分进化算法在油田开发中的应用研究[D];浙江大学;2015年

2 万婧;基于离散微粒群算法和混合差分进化算法的复杂生产调度问题求解[D];昆明理工大学;2015年

3 张转;基于差分进化算法的混凝土德拜模型的研究[D];长安大学;2015年

4 江华;差分进化算法的改进及其在K-means聚类算法中的应用[D];华中师范大学;2015年

5 周志刚;基于差分进化算法的信用风险度量模型研究[D];华中师范大学;2015年

6 任甜甜;差分进化算法在反演问题中的研究与应用[D];新疆大学;2015年

7 杨洋;基于差分进化的模糊C-均值聚类算法研究[D];电子科技大学;2015年

8 王丹;基于辅助函数的自适应差分进化算法研究[D];西安电子科技大学;2014年

9 刘家华;基于进化计算的轧制生产过程操作优化算法与系统开发[D];东北大学;2013年

10 王旦平;圆形对称振子阵列天线基于差分进化算法的综合[D];西安电子科技大学;2014年

  本文关键词：基于差分进化的约束求解算法研究，，由笔耕文化传播整理发布。

本文编号：254825