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

基于遗传算法的TSP求解研究

专 业: 计算机软件与理论
关键词: 旅行商问题 NP—完全理论 插入法 遗传算法 VC++程序设计
分类号: O24
形 态: 共 24 页 约 15,720 个字 约 .752 M内容
阅 读: 全文阅读说明

内容摘要


TSP是组合优化中最为著名的问题,它综合了一大类组合优化问题的典型特征,并以不同的形式存在于超大规模集成芯片制造、印刷电路板设计、X-射线结晶学、机器人控制等高科技领域。

求解TSP的经典遗传算法初始化原始种群时一般采用两种方式:

随机选取和使用局部搜索算法获得原始个体。

但两者均不尽如人意。

前者所得种群很少包含好的模式,致使随后的遗传操作难以使种群得到进化;而后者将增加大量的时间开销,使算法对大规模的TSP无能为力。

改用快速的常规算法初始化种群可成为一种折衷方案。

该文采用作者修改的插入法初始化种群,在不降低原始个体适应性的情况下,缩短算法所需时间。

经典遗传算法存有过早收敛的弊端,其根本原因是群体失去多样性后的近亲交配。

该文采用小群体并行育种和间歇突变的策略,在一定程度上解决了这一问题。

根据TSP的特点,该文对遗传操作和选择策略的各个环节作了细致的探讨,采取不定长基因、共点基因段作为遗传操作的单位,在保持群体多样性的情况下,促进种群的进化,并保证算法的收敛……

全文目录


摘要
第一章 引言
第二章 旅行商问题及其求解方法
第三章 求解TSP的遗传算法
第四章 算法的实现与实验结果
第五章 总结
参考文献

相似论文

  1. 蚁群算法研究及其在聚类中的应用,55页,O242.23 TP311.13
  2. 群智能算法研究及应用,54页,O242.23 TP31
  3. 并行ILU分解及其在迭代法上的应用,46页,O241 TP311
  4. 差分方程及离散神经网络的动力学性质分析,56页,O241.84
  5. 抽象空间方程的若干问题,49页,O241
  6. 离散的不适定问题的正则化方法与数值计算,69页,O241
  7. 几类非线性问题的数值解法,73页,O241.7
  8. 自由边界问题的数值算法研究,65页,O241.82
  9. CA-BSP模型及其性能评测,71页,O246 TP338.6
  10. 形式系统序列极限行为的计算研究及其应用,155页,O211.4
  11. 一种基于神经网络和多元统计分析的动态预测建模方法,66页,O211.61 TP183
  12. 交通流时间序列分离方法研究,47页,O211.61 U491.112 TP311.13
  13. 灰色神经网络与支持向量机预测模型研究,54页,O211.67 TP18
  14. 基于XML的概率数据模型研究,45页,O211.9 TP312
  15. 模糊因子分析方法在医疗费用统计中的应用研究,60页,O212 TP301.6 R19
  16. 贝叶斯分类器研究及其在Web文档分类中的应用,58页,O212.8 TP311.13 TP393.07
  17. 基于Cos方法的参数估计研究,52页,O212.8 TP311.56
  18. 基于贝叶斯网络的信息检索研究,51页,O212.8 TP391.3
  19. 多产品选址问题的计算复杂性与近似算法,52页,O22 O242.2
  20. 多产品选址问题的算法设计与分析,49页,O22 O242.2
中图分类: > O24 > 数理科学和化学 > 计算数学

© 2012 book.hzu.edu.cn