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

免疫遗传算法及其在TSP中的应用研究

作　者: 代冉
导　师: 路燕
学　校: 山东科技大学
专　业: 计算机软件与理论
关键词: 遗传算法(GA) 人工免疫算法(AIA) 免疫遗传算法(IGA) 信息熵 TSP
分类号: TP18
类　型: 硕士论文
年　份: 2008年
下　载: 31次
引　用: 0次
阅　读: 论文下载

内容摘要

遗传算法(GA)是一种模拟自然界生物进化的搜索算法,由于它简单易行、鲁棒性强,尤其是不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程,从而使它的应用范围极为广泛。但是在遗传算法的实际工程优化应用中,常常存在早熟收敛、局部搜索能力不足和收敛速度慢的问题.本论文在深入研究这些问题的基础上,提出以下几点创新性工作:(1)借鉴生物免疫系统的某些优良特性,结合人工免疫算法(AIA),提出了一种新的基于疫苗免疫浓度调节机制,融合了免疫记忆、多样性保持、自我调节、新陈代谢等功能的免疫遗传算法(IGA)框架,并对其性能进行理论分析,包括Markov链全局收敛性分析和模式增长分析。证明了保留最优个体的免疫遗传算法以概率1收敛到全局最优解;提出平均浓度阈值的概念,得出IGA模式定理,可知免疫操作使优良模式的增长速度加快。将提出的免疫遗传算法框架应用到旅行商问题(TSP)问题中,通过MATLAB仿真实验对TSPLIB标准测试库中的城市数据进行对比测试,仿真结果表明IGA在寻优结果和收敛速度方面均优于GA,验证了算法的可行性和有效性;并定义了多样性评价函数,仿真结果验证了IGA的多样性保持能力,从而克服了GA早熟收敛和容易陷入局部最优的缺陷。(2)针对基于信息熵的AIA运行速度慢的缺陷,分析了影响其运行速度的原因,深入研究了信息熵的计算过程,提出了一种加速群体信息熵计算的方法,并进行了数值仿真实验。实验结果表明,基于改进方法构造的信息熵的人工免疫算法,其运行速度得到了大幅度提高。(3)针对TSP的特点,结合启发式交叉(HX)中的贪心思想和边重组交叉(ER)中的双向边思想,提出一种新的交叉算子——双向边贪心交叉算子(DEGX)。仿真实验表明,DEGX的寻优结果和收敛速度均优于HX和ER,有效地增强了局部搜索能力,使收敛速度加快。

全文目录

摘要  5-6
ABSTRACT  6-10
1 绪论  10-17
  1.1 研究背景和意义  10-13
  1.2 研究动机和研究内容  13-16
  1.3 本论文结构安排  16-17
2 遗传算法简介  17-28
  2.1 基本遗传算法描述  17-23
  2.2 模式定理  23-26
  2.3 遗传算法改进的主要途径  26-28
3 人工免疫算法简介  28-37
  3.1 人工免疫系统  28-33
  3.2 基于信息熵的人工免疫算法  33-35
  3.3 遗传算法和免疫算法的比较  35-37
4 一种新的免疫遗传算法的设计和性能分析  37-50
  4.1 一种新的免疫遗传算法设计  37-42
  4.2 免疫遗传算法性能分析  42-46
  4.3 信息熵计算的改进方法  46-48
  4.4 实验设计与结果分析  48-49
  4.5 本章小结  49-50
5 免疫遗传算法在TSP中的应用  50-64
  5.1 TSP问题简介  50-51
  5.2 免疫遗传算法在TSP中的实现  51-56
  5.3 实验设计与结果分析  56-63
  5.4 本章小结  63-64
6 总结与展望  64-66
  6.1 总结  64-65
  6.2 展望  65-66
致谢  66-67
攻读硕士期间主要成果  67-68
参考文献  68-71

免疫遗传算法及其在TSP中的应用研究

内容摘要

全文目录

相似论文