并行蚁群优化算法的设计与实现.doc

西安邮电 毕 业 设 计（论 文） 题 目： 院 系： 计算机 专 业： 班 级： 学生姓名： 导师姓名： 职称： 教授 起止时间：20年月日 至 20年06月日  西 安 邮 电 大 学 毕 业 设 计 (论文) 任 务 书 学生姓名 王可 指导教师 孙家泽 职称 副教授 学院 计算机学院 专业 网络工程 题目 并行蚁群优化算法的设计与实现 任务与要求 学习群体智能优化算法,掌握蚁群算法的原理及其实现学习并行程序设计，掌握编程技术，深入理解并行的编程语言特点 分析蚁群算法的并行性,给出蚁群算法的并行实现, 利用OpenMP应用编程接口API实现蚁群优化算法程序并将该并行化的算法实现进行测试,进而提高算法的效率。《计算群体智能基础》清华大学出版社; 第1版，作者：(南非)恩格尔伯里特(Andrice P.Engelbrecht) 译者：谭营 等 《MPI与OpenMP并行程序设计：C语言版》 清华大学出版社 OpemMP: 月2日-10月30日 完成《开题报告》 11月1日-11月8日 开题报告答辩 11月8日-11月15日 修改并将《开题报告》（定稿）上传至毕设系统 11月16-12月16日 学习并实现蚁群算法的串行实现 12月17日-2月1日 学习并行程序设计，实现经典查找算法的并行化 2月1日-4月1日 蚁群并行程序实现并调试 4月1日-5月1日 算法优化和实验比对 5月1日-6月日 论文撰写 西安邮电 毕业设计(论文)开题报告 计算机专业 2 级 03班 课题名称： 学生姓名： 学号： 04 指导教师： 报告日期： 20年月日 1.本课题所涉及的问题及应用现状综述 随着科学技术和现代化生产的迅猛发展,优化问题在各行各业中的地位越来越重要,而实际优化问题也更加复杂,因此,迫切需要新的优化理论和方法。 ACA是模拟自然界中真实蚁群的觅食行为而形成的一种模拟进化算法,是20世纪90年代意大利的M. Dorigo等学者提出的。受到其取得了较好的实验结果的影响,ACA激起了其他学者的研究热情,并取得了很多研究和应用成果。10年多来的研究结果已经表明: ACA用于组合优化具有很强的发现较好解的能力,具有分布式计算、易于与其他方法相结合、鲁棒性强等优点,在动态环境下也表现出高度的灵活性和健壮性。目前,蚁群算法己成功地在通讯、交通及人工智能等领域中应用,最突出的是求解NP—难的组合优化问题。 在求解大部分优化组合问题时，串行蚁群算法表现出了卓越的求解能力，但是当求解问题规模越来越大时，串行蚁群优化算法很难在短时间内获得理想的解，所以并行蚁群优化算法的研究受到众多研究者的关注。利用并行技术提高蚁群优化解的质量和计算效率的思路源于Dorigo的工作，Randall和Lewis 实现了第一个具有并行计算思想的蚁群优化算法。扬州大学的陈玲等人为了提高蚁群优化解的质量和避免过早收敛，提出了一种新的并行蚁群策略：每个并行进程选择一个与自身进程所选择最优解出入最大的进程进行信息素交换和更新，同时根据不同的解自适应调整信息交互的时间间隔，既可以适时的将一个进程上的最优解发送到其他进程并且还可以减少通信时间。 2．本课题需要重点研究的关键问题、解决的思路及实现预期目标的可行性分析 蚁群算法本身隐含着一定的并行性，从本质上来说，蚁群算法应以并行式的协同优化计算方式为特征，串行计算机对蚁群算法进行的模拟并不能真正体现蚁群算法的本质特征。因此，进一步的研究工作还应如何开展蚁群算法的并行机实现。 在研究蚁群算法并行机实现问题时，需要解决对蚁群算法并行化过程中并行计算模型的选择以及对蚁群算法的分映射方法的改进问题，还需要解决在对蚁群算法并行化过程中粒度处理标准的问题。从而使并行处理过程具有较好的可扩展性，并具有良好的负载均衡性。目前主要存在如下问题：(1)在不考虑处理机间的差异、选择异步更新方法的情况下，且当问题规模一定时，如何分配处理机数目和每个处理机上的蚁群规模以使效用函数值最大。(2)在不考虑处理机间差异、选择同步更新方法的情况下，如何确定问题规模与加速比之间的关系；