解最小生成树问题的新的遗传算法

摘要

组合优化是优化领域中的一个重要分支,最小生成树问题(MST)是一类经典的组合优化问题,并且在现实生活中具有广泛的应用,例如,通信网络、电路设计、管道铺设等方面,因此对这类问题的求解算法的研究有很好的现实意义。近几年来,应用遗传算法求解最小生成树问题的近似解已成为一个新的研究方向。
　　 本文的主要工作如下:
　　 首先,针对最小生成问题设计了一个新的遗传算法。依据树的特点,对最小生成树问题设计了一种新的编码方法和解码方法。并针对编码的特点,设计了一种新的可直接产生可行后代的交叉算子和变异算子,有效的提高了搜索效率和种群的多样性。最后,通过数值仿真实验来表明算法的有效性。
　　 其次,在上述编码方法的基础上设计了另一个求解最小生成树问题的遗传算法。此算法中,用到破圈法的某些思想来产生初始种群,为了增加算法的搜索能力和收敛速度,使用了一致交叉算子和一致变异算子来参与进化。实验结果表明,算法适用于求解该问题。

目录

文摘

英文文摘

第一章 绪论

1.1 引言

1.2 研究现状

1.3 本文的研究内容

1.4 本文的组织结构

第二章 遗传算法的基本理论与方法

2.1 遗传算法的产生与发展

2.2 遗传算法的基本概念

2.3 遗传算法的基本思想

2.4 遗传算法的一般流程

2.5 遗传算法的编码方式

2.5.1 编码评估规范

2.5.2 主要的编码方式

2.6 适应度函数及其尺度化

2.6.1 适应度函数

2.6.2 适应度函数的尺度化

2.7 遗传算法的基本算子

2.7.1 选择(Selection)

2.7.2 交叉(Crossover)

2.7.3 变异(Mutation)

2.8 遗传算法的特点及关键问题

2.8.1 遗传算法的特点

2.8.2 遗传算法的关键问题

第三章 求解最小生成树问题的一个新的遗传算法

3.1 最小生成树问题的基本知识及经典算法

3.1.1 最小生成树问题的理论基础

3.1.2 最小树的经典算法介绍

3.2 新的编码方法和解码方法

3.2.1 最小生成树问题的编码策略

3.2.2 新的编码方法和解码方法

3.2.3 适应度函数的选择

3.2.4 种群的初始化算法

3.3 新的遗传算子

3.3.1 选择算子

3.3.2 交叉算子

3.3.3 变异算子

3.4 新的遗传算法

3.5 数值仿真试验

3.6 本章小结

第四章 求解最小生成树问题的另一新的遗传算法

4.1 遗传算法的设计

4.1.1 树的编码策略

4.1.2 适应度函数的选择

4.1.3 种群的初始化算法

4.2 新的遗传算子

4.2.1 选择算子

4.2.2 交叉算子

4.2.3 变异算子

4.3 新的遗传算法

4.4 数值仿真试验

4.5 本章小结

结束语

致谢

参考文献