基于云平台的遗传—蚁群混合型算法的研究及在TSP中的应用

发布时间：2017-07-18 00:13

  本文关键词：基于云平台的遗传—蚁群混合型算法的研究及在TSP中的应用

  更多相关文章： 云计算 蚁群算法 遗传算法 自然选择策略蚁群算法 免疫遗传算法 遗传-蚁群混合型算法 旅行商问题

【摘要】：云计算作为计算机行业新兴技术的一个重要组成部分,其运行性能的好坏直接影响到处理大规模问题的效率。对此,探求优化组合智能算法是目前云计算研究的重要任务,同时也具有相当大的挑战。在智能计算领域中,蚁群算法和遗传算法是最具有代表性的两种智能优化算法,前者是对蚂蚁群觅食过程的模拟,后者是模拟自然界中自然选择优胜劣汰过程的计算模型。蚁群算法善于求解离散型优化问题,体现了其优越的性能,但是在寻优过程中极易过早收敛,出现非全局最优解,而遗传算法概念比较简单,易与其它智能优化算法相结合,但局部搜索能力差,进化过程中不能很好地利用系统反馈的信息,产生大量的无效迭代等缺陷。论文在蚁群算法和遗传算法深入研究的基础上,针对两种算法各自存在的优缺点,提出用自然选择策略和免疫机制原理分别对蚁群算法和遗传算法进行改进,将改进后的两种算法,按照扬长避短的方式进行融合,得到遗传-蚁群混合型算法。在遗传-蚁群混合型算法中,首先初始信息素的分布是通过遗传算法的快速随机搜索产生的,然后由自然选择策略蚁群算法积累的信息素构建出比较好的解集,再利用免疫遗传算法的选择、交叉、变异操作以及免疫选择来调节蚁群算法的参数组合,最后利用遗传算法的最优解保留机制,从而得到最优解。论文又将遗传-蚁群混合型优化算法部署到云计算平台中求解旅行商问题。论文设计实验将提出的遗传-蚁群混合型算法分别与蚁群算法和遗传算法在相同云平台环境条件下做对比,仿真测试结果表明：基于遗传-蚁群混合型优化算法相比改进之前的单一算法,在求解旅行商问题时不仅执行时间短,而且求解效果更佳。从而为探索在云平台下求解旅行商问题提供了解决方案。
【关键词】：云计算 蚁群算法 遗传算法 自然选择策略蚁群算法 免疫遗传算法 遗传-蚁群混合型算法 旅行商问题
【学位授予单位】：内蒙古农业大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18;TP393.09
【目录】：

• 摘要3-4
• Abstract4-9
• 1 绪论9-13
• 1.1 研究背景和意义9
• 1.2 国内外研究现状9-11
• 1.2.1 国外研究现状9-10
• 1.2.2 国内研究现状10-11
• 1.3 研究内容与论文结构11-12
• 1.4 论文的创新点12-13
• 2 云计算平台的基本理论13-17
• 2.1 开源分布式并行计算平台Hadoop架构模型13
• 2.2 分布式文件系统HDFS13-14
• 2.2.1 HDFS基本组织结构13-14
• 2.3 分布式计算框架MapReduce14-15
• 2.3.1 MapReduce计算模型的基本概念14-15
• 2.3.2 MapReduce计算模型的基本结构15
• 2.4 本章小结15-17
• 3 蚁群算法与遗传算法的基本理论及其改进17-38
• 3.1 传统蚁群算法原理17-18
• 3.2 传统蚁群算法模型18-22
• 3.2.1 信息素挥发度更新规则19-22
• 3.3 传统蚁群算法的参数影响22-26
• 3.3.1 蚁群算法对参数的分析22-25
• 3.3.2 α、β、ρ组合参数配置对蚁群算法的性能影响25-26
• 3.4 基于自然选择策略的改进蚁群算法26-30
• 3.4.1 路径选择概率更新规则26-27
• 3.4.2 信息素优化更新规则27-30
• 3.5 遗传算法的相关概念30
• 3.6 遗传算法的特点30-31
• 3.7 遗传操作的遗传算子31-32
• 3.8 遗传算法的设计32-33
• 3.8.1 遗传算法求解问题的一般过程32-33
• 3.8.2 遗传算法流程图33
• 3.9 基于免疫系统的改进遗传算法33-36
• 3.10 本章小结36-38
• 4 基于云平台的遗传-蚁群混合型优化算法38-44
• 4.1 基于遗传操作的蚁群算法简介38
• 4.2 免疫遗传算法与自然选择策略蚁群算法融合的基本思想38
• 4.3 遗传-蚁群混合型优化算法的设计与构造38-40
• 4.3.1 算法的基本设计38-39
• 4.3.2 遗传算法中遗传算子的构造39-40
• 4.3.2.1 交叉算子39-40
• 4.3.2.2 变异算子40
• 4.4 遗传-蚁群混合型算法流程40-42
• 4.4.1 IGAACANS算法的流程40-41
• 4.4.2 遗传-蚁群混合型算法在云平台的基本实现步骤41-42
• 4.5 本章小结42-44
• 5 遗传-蚁群混合型算法的仿真测试及结果对比分析44-50
• 5.1 旅行商问题的概述44
• 5.2 IGAACANS混合算法在TSP问题上的仿真验证44-48
• 5.2.1 数据及仿真实验软件44-45
• 5.2.2 三种算法对TSP的仿真45-48
• 5.3 结果对比分析48-49
• 5.4 本章小结49-50
• 6 总结与展望50-51
• 6.1 总结50
• 6.2 展望50-51
• 致谢51-52
• 参考文献52-56
• 作者简介56

，

本文编号：555216