求解分布式约束优化问题的搜索算法研究

发布时间：2017-10-03 09:14

  本文关键词：求解分布式约束优化问题的搜索算法研究

  更多相关文章： 分布式约束优化问题 最好优先搜索策略 深度优先搜索策略 蚁群优化

【摘要】：分布式约束优化问题(DCOP)作为多Agent系统协作问题的重要而有用的抽象,是解决分布式智能系统建模和多目标协同优化的有效技术,具有重要的研究意义和实用价值。与传统的集中控制相比,DCOP提供了强的鲁棒性、隐私性,适用于求解规模大、难度高的组合问题,已成为分布式人工智能领域的研究热点。与此同时,分布式约束优化问题的求解算法也随之被广泛研究,分为完备算法与非完备算法两大类。完备算法旨在搜索所有组合空间,保证最终找到全局最优解;非完备算法旨在在有限的时间内,尽最大努力找到一个较好解。搜索策略是这两类算法采用的典型求解策略,已成为了研究的热点。然而,目前的搜索策略存在较多局限性,不能满足实际问题的需要。在完备算法中主要表现为搜索策略单一;在非完备算法中主要表现为仅依据个体局部信息引导搜索,易陷入局部最优。针对上述问题,论文从策略融合和群智能引导两个方面分别对完备算法与非完备算法展开研究。主要工作如下:(1)介绍了分布式约束优化算法的研究现状、分布式约束优化问题的相关定义和常用通信结构以及分布式约束优化实验的测试问题、实验平台与评价指标。较详细介绍了基于最好优先搜索与深度优先搜索策略的两个典型完备算法以及蚁群优化的相关知识与蚁群优化解决分布式约束满足问题(DCSP)的算法。并且,深入分析了最好优先搜索与深度优先搜索策略各自的特征和存在的问题,探讨了两种搜索策略与伪树的关系,为后面两种策略的结合提供了依据。(2)提出了深度优先搜索与最好优先搜索策略结合的DCOP完备算法。该算法依据两种搜索策略与伪树的关系,采用分层的思想,根据agent在伪树中的位置特点分别采用深度优先搜索策略或最好优先搜索策略,并且给出了分层规则和两种策略的无缝对接方法。该算法不仅充分发挥了两种策略各自的优势,并且保持了原单一策略算法的数据结构与消息类型,没有加剧算法的处理复杂性。本文从理论和实验论证了BD-ADOPT的完备性和有效性。(3)提出了基于蚁群优化引导的DCOP非完备算法。算法引入蚁群优化的群智能特点,依据个体之间协作产生的全局信息引导个体做决策选择从而提高算法的搜索性能。该算法充分考虑了DCSP和DCOP的不同,采用伪树结构作为构造图,提高了搜索的并发性;针对DCOP的特点,设计了对数运算与求倒运算结合的信息素更新与引导概率的计算方式;引入流水线的消息处理机制,提高了搜索效率。最后,通过与其他的算法进行对比验证了该算法的可行性和有效性。
【关键词】：分布式约束优化问题 最好优先搜索策略 深度优先搜索策略 蚁群优化
【学位授予单位】：重庆大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【目录】：

• 摘要3-5
• abstract5-9
• 1 绪论9-15
• 1.1 研究背景、目的及意义9
• 1.2 国内外研究现状9-13
• 1.3 论文的主要研究内容与创新之处13-14
• 1.3.1 论文的主要研究内容13
• 1.3.2 论文的创新之处13-14
• 1.4 论文的组织结构14-15
• 2 分布式约束优化算法研究基础15-29
• 2.1 分布式约束优化问题15-16
• 2.2 分布式约束优化实验16-20
• 2.2.1 实验测试问题16-18
• 2.2.2 实验平台18-19
• 2.2.3 算法评价指标19-20
• 2.3 求解分布式约束优化问题完备搜索算法20-25
• 2.3.1 采用BFS策略的算法－ADOPT20-21
• 2.3.2 采用DFS策略的算法－BnB-ADOPT21-22
• 2.3.3 两种搜索策略的分析22-25
• 2.4 求解分布式约束满足问题的蚁群优化算法25-28
• 2.4.1 蚁群优化算法基本介绍25-26
• 2.4.2 求解分布式约束满足问题的蚁群优化算法26-28
• 2.5 本章小结28-29
• 3 深度优先搜索与最好优先搜索策略结合的DCOP完备算法29-55
• 3.1 引言29
• 3.2 DFS与BFS策略结合的完备算法29-47
• 3.2.1 基于分层的DFS与BFS策略结合思想29-30
• 3.2.2 分层规则30-32
• 3.2.3 算法描述32-36
• 3.2.4 算法的实例分析36-44
• 3.2.5 算法的完备性证明和复杂性分析44-47
• 3.3 实验结果及分析47-54
• 3.3.1 实验方案及配置47-48
• 3.3.2 参数a 实验分析48-49
• 3.3.3 BD-ADOPT算法分析49-53
• 3.3.4 实验总结53-54
• 3.4 本章小结54-55
• 4 基于蚁群优化引导的DCOP非完备算法55-71
• 4.1 引言55
• 4.2 基于蚁群优化引导的非完备搜索算法55-65
• 4.2.1 基于蚁群优化引导的非完备搜索算法思路55-58
• 4.2.2 算法描述58-63
• 4.2.3 算法执行过程63-65
• 4.3 实验结果及分析65-70
• 4.3.1 实验方案及配置65-66
• 4.3.2 蚂蚁数量的确定66
• 4.3.3 算法的性能分析66-70
• 4.4 本章小结70-71
• 5 总结与展望71-73
• 5.1 论文工作总结71
• 5.2 未来工作的展望71-73
• 致谢73-75
• 参考文献75-81
• 附录81
• A. 作者在攻读硕士学位期间发表及录用的论文目录81
• B. 作者在攻读硕士学位期间参加的科研项目81

【相似文献】

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

1 介婧,曾建潮;基于思维进化计算求解约束优化问题的新算法[J];计算机工程与应用;2003年04期

2 李相勇;田澎;孔民;;解约束优化问题的新粒子群算法[J];系统管理学报;2007年02期

3 石晓明;柴玉梅;;基于合作仲裁求解分布式约束优化问题的研究[J];微计算机信息;2008年36期

4 张书花;李艳龙;李磊;景孟旗;;求解线性等式约束优化问题的移动渐近线法[J];电子测试;2013年20期

5 樊重俊，韩崇昭，胡保生，王洁;一类约束优化问题的改进遗传算法[J];控制与决策;1996年05期

6 顾宏杰;许力;;利用带感知能力的粒子群算法求解约束优化问题[J];计算机应用;2011年01期

7 郭鹏;宋福庆;;求解约束优化问题的新方法[J];计算机工程与应用;2011年24期

8 彭宏,冯正柱,杨立洪;解约束优化问题的进化策略与混合进化策略的比较[J];数值计算与计算机应用;1998年01期

9 杨艳;周永权;罗林;袁冠远;;人工萤火虫群优化算法求解约束优化问题[J];小型微型计算机系统;2014年01期

10 丁博;王怀民;史殿习;唐扬斌;;低约束密度分布式约束优化问题的求解算法[J];软件学报;2011年04期

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

1 贺春华;张湘伟;吕文阁;谢庆华;;基于竞选算法的非线性约束优化问题实现[A];数学·力学·物理学·高新技术交叉研究进展——2010（13）卷[C];2010年

2 赵志刚;韦兆文;;基于粒子群算法求解约束优化问题[A];计算机技术与应用进展——全国第17届计算机科学与技术应用（CACIS）学术会议论文集（上册）[C];2006年

3 周岩;濮定国;;解非线性不等式约束优化问题的序列线形方程法[A];中国运筹学会第十届学术交流会论文集[C];2010年

4 孙超利;曾建潮;潘正祥;;一种新的约束优化问题初始解的产生方法[A];2009中国控制与决策会议论文集（2）[C];2009年

5 金豪;朱德通;;双边校正约Hessian阵过滤仿射内点法解非负约束非线性等式约束优化问题[A];中国运筹学会第十届学术交流会论文集[C];2010年

6 邓长寿;赵秉岩;;采用不可行解驱动的DE进化算法求解难约束优化问题[A];2011年中国智能自动化学术会议论文集（第一分册）[C];2011年

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

1 程维新;约束优化问题的QP-free算法研究[D];武汉大学;2013年

2 刘水霞;互补约束优化问题若干算法研究[D];内蒙古大学;2009年

3 万中;平衡约束优化问题的理论与算法研究[D];湖南大学;2001年

4 胡一波;求解约束优化问题的几种智能算法[D];西安电子科技大学;2009年

5 时贞军;约束优化问题的参数控制算法研究[D];大连理工大学;2002年

6 王祝君;非线性优化问题的过滤线搜索方法[D];上海师范大学;2010年

7 孙祥凯;约束优化问题的若干对偶以及微分性研究[D];重庆大学;2012年

8 姜永;二阶锥均衡约束的优化问题[D];大连理工大学;2011年

9 刘玉珍;基于进化计算的单目标优化问题研究[D];湘潭大学;2012年

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

1 徐海东;人工蜂群算法理论与应用研究[D];山东大学;2015年

2 王小朋;两类问题的Newton方法研究[D];武汉理工大学;2015年

3 段庆松;约束优化问题的序列近似方法收敛性[D];大连理工大学;2015年

4 池倩倩;锥约束优化问题的罚逼近[D];苏州大学;2015年

5 王佳;基于Chen-Harker-Kanzow-Smale函数的概率约束优化问题的光滑D.C.近似[D];辽宁师范大学;2015年

6 戚雪彩;人工蜂群算法求解约束优化问题的研究[D];南京师范大学;2015年

7 何琛;求解分布式约束优化问题的搜索算法研究[D];重庆大学;2016年

8 杨亚飞;约束优化问题的粒子群算法方法[D];中国地质大学(北京);2012年

9 李_g;非线性约束优化问题的自适应三次正则化方法[D];大连理工大学;2013年

10 胡一波;解决约束优化问题的两种新的进化算法[D];西安电子科技大学;2006年

，

本文编号：964359