学位论文 > 优秀研究生学位论文题录展示

求解组合优化问题的混合蛙跳算法的研究

作 者: 王园媛
导 师: 王彦祺
学 校: 石家庄经济学院
专 业: 计算机应用技术
关键词: 混合蛙跳算法 组合优化 局部搜索策略 旅行商问题 背包问题
分类号: TP301.6
类 型: 硕士论文
年 份: 2010年
下 载: 122次
引 用: 0次
阅 读: 论文下载
 

内容摘要


群体智能算法是一种高效的优化算法。由单个结构复杂的个体所完成的任务可由大量结构简单的个体所组成的群体合作来完成,并且后者往往更具有健壮性、灵活性和经济上的优势。在无集中控制且不提供全局模型的前提下,群体智能算法为解决组合优化问题提供了一种新对策。混合蛙跳算法是一种新兴的群体智能算法。目前,利用混合蛙跳算法求解组合优化问题的相关成果不多见。本文对于如何利用混合蛙跳算法求解组合优化问题进行了探讨。主要研究成果如下:首先,传统的混合蛙跳算法是通过全局最优解和当前子种群的局部最优解对子种群中的最差个体施加影响,这种优化方式是对子种群中的单一个体施加影响。在第三章中,本文提出了一种利用全局最优解“指导”每个子种群整体向前进化的策略。与传统的混合蛙跳算法不同,这种子种群进化策略可以同时作用于多个个体,是一种并行爬山的进化方式。随着城市数量的增加,常见的演化算法容易陷入局部极值的陷阱,无法搜索到全局最优路径。由于将郭涛算法和混合蛙跳算法的优点进行了有机的结合,“当前最优解作用于整个子种群”的混合蛙跳算法在求解TSP问题时表现出了良好的性能,能够以极小的时间代价搜索到用户的满意解。其次,传统的混合蛙跳算法是通过全局最优解和当前子种群的局部最优解“吸引”每个子种群中的最差青蛙。通过这种“吸引”的作用,这两个个体指导了最差青蛙的进化方向。与传统的混合蛙跳算法不同,本文利用子种群中的其它个体对最差的个体的“排斥”作用来指导最差青蛙的进化方向。第四章中,本文利用“排斥最差个体”的混合蛙跳算法求解背包问题,该算法能够高效率地搜索到问题的全局最优解。

全文目录


摘要  5-6
Abstract  6-9
第1章 绪论  9-13
  1.1 研究背景及意义  9-10
  1.2 混合蛙跳算法的研究现状  10
  1.3 本文的主要工作和创新点  10-11
  1.4 本文的组织结构  11-13
第2章 混合蛙跳算法求解组合优化问题的设计思路  13-23
  2.1 群体智能算法求解组合优化问题的框架  13-22
    2.1.1 群体智能算法的基本概念  13-14
    2.1.2 蚁群算法  14-16
    2.1.3 粒子群算法  16-18
    2.1.4 人工鱼群算法  18-19
    2.1.5 混合蛙跳算法  19-21
    2.1.6 群体智能算法求解组合优化问题的框架  21-22
  2.2 混合蛙跳算法求解组合优化问题的设计思路  22-23
第3章 "当前最优解作用于整个子种群"的混合蛙跳算法求解TSP  23-35
  3.1 旅行商问题的描述和现有求解方法  23
  3.2 郭涛算法求解旅行商问题  23-26
  3.3 "当前最优解作用于整个子种群"的混合蛙跳算法求解旅行商问题  26-29
    3.3.1 编码与适应度函数  27
    3.3.2 子种群的划分  27-28
    3.3.3 求解流程  28-29
  3.4 仿真实验及分析  29-34
    3.4.1 实验条件和测试集  29
    3.4.2 实验参数和结果  29-33
    3.4.3 实验分析  33-34
  3.5 结论  34-35
第4章 "排斥最差个体"的混合蛙跳算法求解背包问题  35-47
  4.1 0-1背包问题的描述和现有的求解方法  35
  4.2 类电磁机制算法的介绍  35-38
    4.2.1 初始化  36
    4.2.2 计算每个粒子所受的合力  36-37
    4.2.3 粒子沿合力方向移动  37
    4.2.4 局部搜索  37-38
    4.2.5 结束准则  38
    4.2.6 小结  38
  4.3 "排斥最差个体"的混合蛙跳算法求解0-1背包问题  38-42
    4.3.1 编码与适应度函数  39-40
    4.3.2 划分子种群  40
    4.3.3 "排斥最差个体"的子种群进化  40-42
  4.4 仿真实验及分析  42-45
    4.4.1 实验条件和测试集  42-43
    4.4.2 实验参数和结果  43-44
    4.4.3 实验分析  44-45
  4.5 结论  45-47
第5章 总结与展望  47-49
  5.1 总结  47-48
  5.2 展望  48-49
参考文献  49-53
致谢  53-55
作者简介  55
攻读硕士学位期间发表的论文和科研成果  55

相似论文

  1. 语音情感识别的特征选择与特征产生,TP18
  2. 融合粒子群和蛙跳算法的模糊C-均值聚类算法研究,TP18
  3. DNA自组装模型在组合优化问题中的应用研究,TP399-C8
  4. 变邻域搜索算法研究及在组合优化中的应用,TP301.6
  5. 基于Copula风险控制的贷款组合优化模型研究,F224
  6. 连续竞争反应装置的效益优化方法与应用研究,TQ015
  7. 基于下偏度最小化贷款组合优化模型,F224
  8. 基于违约相关性的集中度风险控制方法研究,F830.5
  9. 高速公路融资结构优化研究,F540.58
  10. 人工萤火虫群优化算法分析改进及应用研究,TP301.6
  11. 多目标人工萤火虫群优化算法及其应用,TP301.6
  12. 蚁群优化算法及其应用研究,TP301.6
  13. 混合蚁群算法及其应用研究,TP301.6
  14. 证券市场风险测量与修正,F832.51
  15. 非线性无约束共轭梯度法,O224
  16. 变电站经济运行与无功电压优化控制的研究,TM63
  17. 基于遗传算法优化问题的研究,TP18
  18. 智能优化算法及在通信中的应用研究,TN92
  19. 遗传算法改进及其在背包问题与函数优化中的应用,TP18
  20. 基于群体智能算法的动态目标跟踪技术研究,TP391.41
  21. 混合算法在物流运输问题中的研究和应用,TP301.6

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com