蚁群算法并行化研究-自动化基础-论文之家

您现在的位置：硕士论文 >> 电子论文 >> 自动化 >> 自动化基础 >> 正文

蚁群算法并行化研究

作者：高彦明 Publish: 2006-3-24 Hits:-

【中文题名】

蚁群算法并行化研究

【英文题名】

A Research on Parallelization of Ant Colony Optimization

【学科专业】

计算机软件与理论

【论文级别】

硕士论文

【投稿时间】

2006-3-24

【中关键词】

并行,蚁群算法,信息素,多处理机,启发式搜索,

【英关键词】

Parallelization,ACO,Pheromone,Multi-processor,Meta-heuristic,

【分类导航】

工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>>

【论文摘要】

蚁群算法作为一种新的启发式搜索算法,大量实验结果表明,它在解许多NP-hard问题时都表现出较好的求解能力。因而它吸引了众多学者不断对其扩展改进,也在经历着一个不断发展完善的过程。本文在调查研究了蚁群算法及其并行化研究现状的基础上,提出并实现了新的并行化策略,主要思想是基于多蚁群在解的构造过程和信息素更新过程中共享同一个信息素矩阵,并针对典型ACO算法分别设计并实现了相应的并行算法,而且尝试了不同ACO算法在并行过程中的混合应用。文中主要以ACS和MMAS的并行实现为例,详细描述了算法设计思想和程序实现过程,提供了各自应用于对称TSP问题大量实例的实验结果,并与相应串行算法在相同计算环境下的实验结果做出比较,以及不同并行实现之间的横向比较。实验结果表明,本文的并行方案相对于串行ACO及现有的并行策略具有一定的优势,提供了解决组合优化问题的一种有力手段。

【论文题纲】

摘要	3-4
Abstract	4-5
目录	5-10
第一章绪论	10-12
1．1 课题背景	10
1．2 课题内容	10-11
1．3 课题意义	11
1．4 本文的组织结构	11-12
第二章预备知识	12-17
2．1 组合优化问题	12
2．1．1 全局最优与局部最优	12
2．1．2 TSP问题	12
2．2 并行计算机	12-14
2．2．1 并行计算机的应用	13
2．2．2 并行计算机的类型	13-14
2．3 并行算法及编程模型	14-17
2．3．1 并行算法的性能评价	14-15
2．3．2 并行编程模型	15-17
第三章蚁群系统及其并行的发展	17-27
3．1 基本蚁群系统(AS)	17-18
3．2 AS扩展	18-21
3．2．1 Elitist Ant System(EAS)	18
3．2．2 Rank-Based Ant System(RAS)	18-19
3．2．3 Max-Min Ant System(MMAS)	19
3．2．4 Ant Colony System(ACS)	19-21
3．2．5 其它改进算法	21
3．3 ACO与局部搜索	21-22
3．4 并行ACO的研究现状	22-23
3．5 其它启发式(Metaheuristics)算法的并行研究	23-26
3．5．1 禁忌搜索(TS)	24
3．5．2 基因算法(GA)	24-25
3．5．3 模拟退火(SA)	25-26
3．6 小结	26-27
第四章 ACO并行策略设计及实现	27-50
4．1 MMAS的并行(PMMAS)	28-32
4．1．1 初始化	28-29
4．1．2解的构造与信息素更新	29-31
4．1．3 信息素的重新初始化	31-32
4．1．4 终止条件	32
4．1．5 小结	32
4．2 ACS的并行(PACS)	32-34
4．3 MMAS与ACS的混合并行(MMACS)	34-35
4．4 局部优化的作用	35-37
4．4．1 TSP的FDC分析	35-36
4．4．2 局部搜索在并行ACO中的应用	36-37
4．5 并行ACO的实现	37-50
4．5．1 数据结构	38-39
4．5．2 空间复杂度分析	39-40
4．5．3 算法描述	40-47
4．5．4 时间复杂度	47
4．5．5 并行线程的协调	47-48
4．5．6 其它并行策略的实现	48-50
第五章实验结果及分析	50-59
5．1 PMMAS的实验结果及分析比较	50-52
5．2 PACS的实验结果及分析比较	52-55
5．3 MMACS的实验结果及分析比较	55-56
5．4 并行实现间的横向比较	56-57
5．5 小结	57-59
第六章结束语	59-61
6．1 总结	59
6．2 相关工作及展望	59-61
参考文献	61-65
攻读学位期间发表的论文	65-66
致谢	66-67
附录	67

【DOI】

LunWen.ID:2.2008.387629



付费论文：有参考文献 300元

1、注册会员 2、购买本文 3、下载文章
注:此文为收费论文，需付费购买。每页大约1000字。

代写论文流程

载入中…

Web lunwenjia


热门搜索：并行论文蚁群算法信息素多处理机启发式搜索

自动化基础最新论文

自动化基础热门论文