《并行蚁群优化算法的设计与实现》由会员分享，可在线阅读，更多相关《并行蚁群优化算法的设计与实现（37页珍藏版）》请在金锄头文库上搜索。
1、西安邮电大学毕业设计（论文）题 目：并行蚁群优化算法的设计与实现院系：计算机学院专业：网络工程班级：网络1003班学生姓名：王可导师姓名：孙家泽 职称：副教授起止 时间：2013年09月25日 至2014年06月02日毕业设计（论文）诚信声明书本人声明：本人所提交的毕业论文并行蚁群优化算法的设计与实 现是本人在指导教师指导下独立研究、写作的成果，论文中所引用他 人的文献、数据、图件、资料均已明确标注；对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式注明并表示感谢。本人完全清楚本声明的法律后果，申请学位论文和资料若有不实之 处，本人愿承担相应的法律责任。论文作者签名：时间： 年 月
2、日指导教师签名：时间： 年 月 日西安邮电大学毕业设计(论文)任务书学生姓名 王可 指导教师 孙家泽 职称 副教授学院 计算机学院专业网络工程题目并行蚁群优化算法的设计与实现一、任务与要求学习群体智能优化算法，掌握蚁群算法的原理及其实现。学习并行程序设计，掌 握OpenMP编程技术，深入理解并行的编程语言特点 分析蚁群算法的并行性,给出蚁 群算法的并行实现，利用OpenMP应用编程接口 API实现蚁群优化算法程序并将该并 行化的算法实现进行测试，进而提高算法的效率。二、参考资料(1) 计算群体智能基础清华大学出版社；第1版，作者：(南非)恩格尔伯里特 (Andrice P.Engelbrech
3、t)译者：谭营等(2) MPI与OpenMP并行程序设计：C语言版清华大学出版社(3) OpemMP: htt p:/www.openmp.org三、主要仪器及材料上网计算机一台四、工作计划(时间进度)9月25日-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日论文撰写西安邮电大学毕业设计（论文）开题报告计算机 学
4、院网络工程专业2010级03班课题名称：并行蚁群优化算法的设计与实现学生姓名：王可学号：04102080指导教师：孙家泽报告日期：2013年10月30日1. 本课题所涉及的问题及应用现状综述随着科学技术和现代化生产的迅猛发展，优化问题在各行各业中的地位越来越重 要,而实际优化问题也更加复杂，因此，迫切需要新的优化理论和方法。ACA是模拟自然界中真实蚁群的觅食行为而形成的一种模拟进化算法，是20世纪 90年代意大利的M. Dorigo等学者提出的。受到其取得了较好的实验结果的影响,ACA 激起了其他学者的研究热情，并取得了很多研究和应用成果。10年多来的研究结果已经 表明:ACA用于组合优化具有
5、很强的发现较好解的能力，具有分布式计算、易于与其他 方法相结合、鲁棒性强等优点，在动态环境下也表现出高度的灵活性和健壮性。目前， 蚁群算法己成功地在通讯、交通及人工智能等领域中应用，最突出的是求解NP难的 组合优化问题。在求解大部分优化组合问题时，串行蚁群算法表现出了卓越的求解能力，但是当 求解问题规模越来越大时，串行蚁群优化算法很难在短时间内获得理想的解，所以并 行蚁群优化算法的研究受到众多研究者的关注。利用并行技术提高蚁群优化解的质量 和计算效率的思路源于Dorigo的工作，Randall和Lewis实现了第一个具有并行计算 思想的蚁群优化算法。扬州大学的陈玲等人为了提高蚁群优化解的质量和
6、避免过早收 敛，提出了一种新的并行蚁群策略：每个并行进程选择一个与自身进程所选择最优解 出入最大的进程进行信息素交换和更新，同时根据不同的解自适应调整信息交互的时 间间隔，既可以适时的将一个进程上的最优解发送到其他进程并且还可以减少通信时 间。2. 本课题需要重点研究的关键问题、解决的思路及实现预期目标的可行性分析蚁群算法本身隐含着一定的并行性，从本质上来说，蚁群算法应以并行式的协同 优化计算方式为特征，串行计算机对蚁群算法进行的模拟并不能真正体现蚁群算法的 本质特征。因此，进一步的研究工作还应如何开展蚁群算法的并行机实现。在研究蚁群算法并行机实现问题时，需要解决对蚁群算法并行化过程中并行计算
7、 模型的选择以及对蚁群算法的分映射方法的改进问题，还需要解决在对蚁群算法并行 化过程中粒度处理标准的问题。从而使并行处理过程具有较好的可扩展性，并具有良 好的负载均衡性。目前主要存在如下问题：(1)在不考虑处理机间的差异、选择异步更新方法的情况下，且当问题规模一定时，如 何分配处理机数目和每个处理机上的蚁群规模以使效用函数值最大。在不考虑处理机间差异、选择同步更新方法的情况下，如何确定问题规模与加速比 之间的关系；在处理机增多的情况下，如何选择处理机的最佳数目以使计算时间减少。(3) 在不考虑处理机间的差异、选择同步更新方法的情况下，且当处理机一定时，如何 选择最优的蚁群规模k以使效用函数的值
8、最大。(4) 在其他条件一定的情况下，如何设计一个更好的处理机之间进行信息交换的关系序 列也是一个必须要考虑的问题。(5) 当并行机实现时，局部迭代若干次后需要交换信息。局部迭代次数的增大也会使得 蚁群算法早熟的概率增大，而局部迭代次数减少则会增加通信时间，因此还要努力解 决如何有效避免蚁群算法的过早停滞和减少通信开销之间的平衡问题。掌握OpenMP编程技术，利用OpenMP应用编程接口 API实现蚁群优化算法程序 并将该并行化的算法实现进行测试，进而提高算法的效率。3. 完成本课题的工作方案9月25日-10月30日学习群体智能算法11月1日-11月8日学习并行程序设计11月8 日-11月15
9、日掌握OpenMP编程技术11月16-12月16日学习并实现蚁群算法的串行实现12月17日-2月1日学习并行程序设计，实现经典查找算法的并行化2月1日-4月1日蚁群并行程序实现并调试4月1日-5月1日算法优化和实验比对5月1日-6月2日论文撰写4. 指导教师审阅意见指导教师（签字）： 年月日说明：本报告必须由承担毕业论文（设计）课题任务的学生在毕业论文（设计）正式开 始的第1周周五之前独立撰写完成，并交指导教师审阅。西安邮电大学毕业设（论文成绩评定表学生姓名性学王可 爲男暮 04102080另U号专业 班级网络1003班课题名称:并行蚁群优化算法的设计与实现课题 类型科研难度一般题目毕峻计（论
10、 文时间:扌导师2013年9月25日6月2日曰梆丨孙家泽职称：副教授课题任务 完成情况论文（千字）；设计、计算说明书（千字）；图纸（张）；其它含附件）：指 导 教 师 意 见分项得分：开题调研论分；课题质量（论文内容分；创新 分； 论文撰写（规范）分；学习态度分；外文翻译 分指导教师审阅成绩：指导教曬字：年 月曰评 阅 教 师 意 见分项得分选虹分；开题调研论证分；课题质量论文内容）分；创丄分； 论文撰写（规范）分；外文翻译 分评阅成绩：评阅教媲字：年 月曰验 收 小 组意 见分项得分：准备情迹；毕业设计（论文）质分；（操作）回答问踰 验收成绩：验收教焕长（签字：年 月曰答 辩 小 组意见分项
11、得分：准备情况h陈述情况分；回答问题分；仪丄分 答辩成绩：答辩小组组长字：年 月曰成绩计算方法（填写本系实用1指导教师成绩（夠 评阅成也（夠验收成也（夠答辩成红（夠 比例学生实得成绩分制指导教师成绩评阅成绩验收成绩答辩成绩总评答辩委员会意见毕业论J（设计总评成筛级：院答辩委员会主任）：院签章年 月曰备 注西安邮电大学毕业论文（设计）成绩评定表（续表）摘要IABSTRACT II1引言11.1群智能算法11.2蚁群算法21.3 本文的研究工作32蚁群算法的原理及实现42.1蚁群算法的基本原理42.2蚁群算法的模型52.2.1对称的双桥实验52.2.2非对称的双桥实验62.3 算法基本流程82.4
12、主要的代码分析92.5蚁群算法的实现112.5.1程序运行环境112.5.2运行结果及分析122.5.3 蚁群算法的小结123蚁群算法的并行实现143.1 OpenMP的并行编程143.1.1 OpenMP 的介绍143.1.2 OpenMP环境的搭建143.1.3 并行编程的简述163.2 OpenMP的并行编程173.3.2部分循环代码的并行实现183.3.3 实验结果以及对比分析194结论与展望22致 谢24参考文献23在二十世纪九十年代初，意大利M.Dorigo引进蚁群算法的思想后，这算法在 智能算法的学术界引发了极大的轰动，在接下来的十几年里面，蚁群算法已经在 函数组合优化、数据聚类
13、挖掘、求解最优路径等各个领域取得了很好的反响。在 接下来的一段时间里，蚁群算法因为本身独特的优越性，已经被很多领域采纳进 行实际生活中的运用，但是仍然有自身的缺陷性，毕竟它才刚刚起步，算法还在 不断的优化和改进。本文研究的主要工作是，基于OpenMP环境下，对于并行蚁群算法的研究和设 计。在基于基本的智能算法的理解下，通过学习和研究，对于蚁群算法的串行执 行，和改进后的蚁群优化算法，在OpenMP环境的并行实现。对比分析，并行和串 行的区别和优劣。然而，蚁群算法在执行的时候，本身具有一定的并行性，因为 蚁群蚂蚁都是并发执行的。所以我们这里就只有在并行编程语言里面进行突破 了，学习运用OpenM
14、P并行编程是一个很好的突破口。并行和串行是两个相对的过 程，并行执行就是几个程序指令在同一个周期里面同时一起执行的过程。其主要 表现形式的多个应用程序同时被装入计算机内存和并发执行的。因为并行编程现 在不断的优化和更新，本文工作简略的介绍一下并行语言的特点，以及一些简单 的并行语句和并行编程所需要的环境和环境搭建，并优化与设计该算法，使用 OpenMP应用程序编程接口 API对并行蚁群算法进行测试。关键字：蚁群算法；OpenMP ；并行设计。AbstractIn the early 1990s, after being introduced by the Italian M.Dorigo, t
15、he ant colony optimization has caused great sensation in the academia of intelligent algorithm. In the following decades, ant colony optimization has achieved good response in the field of function combinatorial optimization, data clustering mining, solving the optimal path, etc. In the next period of time, the unique superiority of the ant colony optimization, has been adopted by many fields for use in real
