| 摘要 | 第1-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页 |
