基于遗传算法的有向无环图研究

摘要

有向图是研究可视化软件和信息工程问题的基本模型。由于图容易让人明白和记忆,因此人们对于有向图算法有着相当大的兴趣。近年来,画图受到了越来越多的关注,对画图算法的研究已经成为计算机科学领域中的一个新的研究方向。有向图画图算法是画图领域的一个重要研究课题。目前,Sugiyama启发式方法及其相应变种是画有向图的主要方法。Sugiyama启发式方法通常把画图问题分成三个子问题：分层、每层顶点之间的排序以及调整。因为遗传算法在组合优化问题(搜索范围比较大)中能够取得相当好的全局优化结果,所以可以将遗传算法用于画图问题中。事实上,画图问题就是一个优化的过程。本文提出了一个基于遗传算法的有向无环图画图算法。主要内容如下： 1.介绍了研究画图的意义以及画图问题的研究现状。 2.介绍了图的基本概念,图的表示；然后介绍了图的评判标准以及目前现有的画图算法方法；最后介绍了遗传算法的基本流程。 3.介绍了基于启发式的有向图画图算法。算法主要包括三个步骤：删除环、分层、减少边交叉。我们对于每一个步骤都给出了一些比较经典的启发式方法。 4.提出了一个基于遗传算法的有向无环图画图算法,给出了算法的设计方法和步骤,并将其与以前的启发式方法作了比较。实验表明这种编码对于有向无环图是非常有效的。在基于遗传算法的有向无环图画图算法中,我们采用了边长度表示法进行编码。在遗传算法的设计过程中,我们还加入了质心启发式方法用来提高算法的效率。

目录

文摘

英文文摘

声明

第1章绪论

1.1研究画图的意义

1.2画图问题的研究现状

1.3本文的研究内容

第2章预备知识

2.1图的基本概念，表示

2.1.1图的基本概念

2.1.2图的表示

2.2画图算法

2.2.1画图算法概述

2.2.2图的评估标准

2.2.3画图算法方法介绍

2.2.4演化计算的概述

2.3遗传算法的设计与实现

2.3.1遗传算法的框架

2.3.2编码和初始化

2.3.3适应值函数

2.3.4遗传算子

第3章基于启发式的有向图画图算法

3.1删除环

3.2分层

3.3减少边交叉

第4章基于遗传算法的有向无环图画图算法

4.1基于遗传算法的有向无环图画图的实现

4.1.1编码和初始化种群

4.1.2设计适应函数值

4.1.3确定选择策略

4.1.4设计杂交算子

4.1.5设计变异算子

4.1.6给出控制参数

4.1.7给出终止准则

4.2算法实验结果

第5章结论

参考文献

附录

致谢