（计算机应用技术专业论文）有向无环图的布局优化方法与实现.pdf

摘要 摘要 有向无环图d a g ( d i r e c t e d a c y c l i cg r a p h ) 广泛应用于数据库建模、工程设计等领域。 将矩阵存储的d a g 图正确、美观地绘制出来，可以使其更直观、清晰，并且方便各种问题 的分析和处理。d a g 画图是一个有挑战的工作，要求的算法不仅要正确表达各个结点的偏 序关系，同时还要给出图的方向。后者表明无向图的画图方法不能用于有向图，但是有向图 可以从相应的无向图的画图方法得到可用的策略。 在d a g 画图领域，已经有很多有效的针对不同类型和不同领域的画图方法。本文从画 图的3 条审美标准出发，提出针对审美标准的解决方法，设计了新的画图方法：提出了分层 问题的多项式时间算法和消除哑结点算法；通过重新设计交叉算子、变异算子和控制参数改 进了已有的分层和最小化边交叉的遗传算法。 为了验证所提出的画图算法的可行性和正确性，用j a v a 语言实现了l e m d e s ( l a y e r e d e d g e - c r o s s e sm i n i m i z a t i o na n dd u m m y - n o d e se l i m i n a t i o ns y s t e m ) 原型系统，通过对试验结果 的分析，表明所提出的算法能取得比传统算法更好的计算结果。 关键词：层次图；最小化边交叉数；遗传算法；哑结点 a b s t r a c t d a g ( d i r e c t e da c y c l i cg r a p h ) i sw i d e l yu s e di nd a t a b a s em o d e l i n ga n de n g i n e e r i n gd e s i g n d a gi sa l w a y ss t o r e db ym a t r i x m a n yp r o b l e m si nd a gc l o s e l yd e p e n do nt h ep r e c i s e n e s sa n d c l e a m e s so ft h ec o r r e s p o n d i n gm a t r i x v i s u a l i z i n gd a gi sac h a l l e n g i n gt a s k ，r e q u i r i n ga l g o r i t h m s m a tf a i t h f u l l yr e p r e s e n tt h er e l a t i v es i m i l a r i t i e so ft h en o d e s a sw e l la sg i v i n gs o m es e n s eo ft h e o v e r a l ld i r e c t i o n a l i t y t h el a t t e rr e q u i r e m e n tr e n d e r sa l g o r i t h m sd e s i g n e df o ru n d i r e c t e dg r a p h s i n a p p r o p r i a t ef o rd i g r a p h s ，h o w e v e r , a l g o r i t h m sf o rd i g r a p hd r a w i n gu s u a l l ya d o p ts o m eu s e f u l s t r a t e g i e sf r o mt h e i ru n d i r e c t e dc o u n t e r p a r t s m a n ya p p r o a c h e so fg r a p hd r a w i n gh a v eb e e nd e v e l o p e df o rd i f f e r e n tt y p e so fg r a p h sa n d d i f f e r e n ta p p l i c a t i o nd o m a i n s t h r o u g ha n a l y z i n gt h ea e s t h e t i cc r i t e r i aa n dg e n e r a lm e t h o d s ，t h i s p a p e rp r o p o s e st h ea l g o r i t h mo fd r a w i n gd a gf i r s t ，ap o l y n o m i a lt i m ea l g o r i t h mt om a k et h e g r a p h sl a y e r e di sp r o p o s e d s e c o n d ，a na l g o r i t h mt oe l i m i n a t i n gt h ed u m m yn o d e si sp r o p o s e d a l s o ，t h eg e n e t i ca l g o r i t h mo fe d g e - c r o s s e sm i n i m i z a t i o ni si m p r o v e d c o m p a r i s o nr e s u l t ss h o w t h a tt h ep r o p o s e da n di m p r o v e da l g o r i t h m sa r em o r ee f f e c t i v et h a nt r a d i t i o n a lo n e s ap r o t o t y p es y s t e ml e m d e s ( l a y e r e d e d g e - c r o s s e s m i n i m i z a t i o na n dd u m m y - n o d e s e l i m i n a t i o ns y s t e m ) i si r r i p l e m e n t e db yj a v at ov e r i f yt h ep r o p o s e da n di m p r o v e da l g o r i t h m s t h i s p r o t o t y p es y s t e mc o n t a i n sm a k i n gt h eg r a p hl a y e r e d ，e d g e - c r o s s e sm i n i m i z a t i o na n d d u m m y - n o d e se l i m i n a t i o n t h er e s u l t so fi m p l e m e n t a t i o na n de x p e r i m e n ts h o wt h a tt h ep r o p o s e d m e t h o dc a ny i e l dg r a p h sw h i c ha r ea e s t h e t i c a l l yp l e a s i n g k e y w o r d s ：l a y e r e dg r a p h ；e d g e - c r o s s e sm i n i m i z a t i o n ；g e n e t i ca l g o r i t h m ；d u m m y - n o d e s h 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 研究生签名： 桶帆 日期： 参扩、s 、zz 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文 的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档 的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借 阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东 南大学研究生院办理。 研究生签名：超生鱼导师签名： 影 易锡 日 第一章引言 1 1 研究背景 第一章引言 有向无环图d a g ( d i r e c t e d a c y c l i cg r a p h ) 广泛应用于数据库建模和工程设计等领域【。 例如，网格数据库中主要采用基于d a g 的查询计划建模方式；基于d a g 结构的综合管理 信息数据库，能够将各种应用环境所需的数据集成在一起，有效的解决了不同应用环境中数 据的一致性和相关性问题；工程设计上用d a g 可以清晰的表达工程的进度等等。 将矩阵存储的d a g 图正确、美观地绘制出来，可以使其更直观、清晰，并且方便各种 问题的分析和处理。d a g 画图是一个有挑战的工作，要求的算法不仅要正确表达各个结点 的偏序关系，同时还要给出图的方向。后者表明无向图的画图方法不能直接应用于有向图， 但是有向图可以从相应的无向图的画图方法得到可用的策略。 1 2 研究现状 一种普遍接受的有向图的画图方法是p e t e re a d e s 的t 作1 6 】。p e t e re a d e s 规定了： 图的美观标准：避免反向边；结点排列均匀；减少边交叉。 令根据不同的目标分别确定结点的x 和y 坐标。x 坐标用来保存方向信息；y 坐标通过 其他美观标准来确定，比如减少边交叉。 夺首先对图分层，每个结点被安排在唯一的层上，确定了结点的x 坐标。不允许出现跨 层的边，如果边跨越2 层或者以上，则需要添加哑结点将边分割。哑结点导致了处理问 题规模的增大和边的弯曲，因此哑结点的数目要尽可能的少，这是一个n p 难问题。 冷 边交叉数与结点横坐标无关，只与相临两层上的结点序列相关( 即与结点的纵坐标相 关) 。设第f 层的结点序列已经确定( i = 0 ，l ，2 j i 一1 ) ，通过安排第i + 1 层的结点序列减 少边交叉，这是一个p 问题。 以p e t e re a d e s 的工作为基础，已经提出了很多成功的启发式方法。 本文进行结果比较的算法，l c a r m e l 等的工作【lj ，组合层次与能量算法( c o m b i n i n g h i e r a r c h ya n de n e r g y ) 。l c a r m e l 将图视为在横向和纵向上具有能量的物体( 可以视为2 个弹 簧) 。首先根据结点数和边数计算横向和纵向上能量为0 ( 即无形变) 的位置；设置当图在 横向上被压缩时( 定义为压缩能量) ，纵向上表现为被拉伸( 定义为拉伸能量) ，同样图在横 向上被拉伸时，纵向上表现为被压缩；组合层次与能量算法的目标是使图在横向和纵向上的 能量和最小。由于计算能量平t 0 j n 权求最小值都是在多项式时间内实现的，因此组合层次与能 量算法的时间复杂度是多项式时间的。 t d w y e r 等【2 1 ，提出了一种绘制有向图的改进方法。与传统方法类似，指定一个轴存储 幽的方向信息。与传统方法不同的是，不再把结点的x 和y 坐标分开计算。分开计算是受 剑算法中分治法的启发，但是这种分离使得边的长度统，结点分布均匀，可能会导致在画 图结果t j 难以控制一些美观准则。冈此，借助无向图画图的方法，将x 坐标和】，坐标同时 进行计算。通过组合运用优化和二次规划米实现。d w y e r ，t 等，进一步改进了上述方法。 给山了新的二次规划解决的方、法【引，提高了运算的效率。 m h a r r i g a n 和p h e a l ，4 1 ，提出了一种使用生成树绘制d a g 图的方法。把图的起始结 东南大学硕士学位论文 点去掉，把图分割为多个树，对每一个树进行传统方法的处理，最后将这些树组合起来成图。 这样分治的优点是对于每一个树来，由于问题规模较小，可以得到很好的结果；但是在将树 组合成图时可能会使得整张图的效果不佳。 y k o r e n 等1 2 0 j ，改进了光谱画图法。光谱画图法的优点是将图视为一个整体进行优化， 定义类似于谱线的一些标准曲线作为图的额外信息；可以大大降低计算时间，对于一个结点 为 的d a g 图，光谱画图法的时间复杂度为d ( 疗) 。然而光谱画图法得到的图很难符合人们 的审美标准，大量弯曲的弧线使得整张图难以理解。因此y k o r e n 在使用光谱画图法绘图 后引入审美修正算法，对图进行修改使得图符合人们的审美标准。但是审美修正算法的时问 复杂度是非多项式时间的。因此，画图算法本质上并没有提高速度。 武汉大学的黄竞伟教授提出了一种基于美观标准的画图算法【5 5 1 1 5 6 1 。将一般无向图的画 图问题转化为函数优化问题，用启发式算法求目标函数的最优解的近似值，从而得到无向图 自动画图算法，这是画图的一个一般框架。但在实际应用中，不同的用户可能有不同的审美 标准，因此在实际应用时根据用户的审美标准设置相应的目标函数，这样算法具有统一、无 需修改，并且易于并行化，可以直接用来画不同类型和不同审美标准的图。这种方法需要在系 统设置目标函数时，对审美标准进行读取和分析，算法运行时间较长，且人们的审美标准在 大多数情况下类似，因此，这种方法适在实际中应用不多。 1 3 主要研究内容 本文结合实验室国家自然科学基金项目( n o 6 0 5 0 4 0 2 9 、n o 6 0 6 7 2 0 9 2 和n o 9 0 4 1 2 0 1 4 ) ， 在对现有的d a g 图画图方法进行深入研究的基础上，设计了基于遗传算法的d a g 画图算 法，实现了l e m d e s ( l a y e r e de d g e - c r o s s e sm i n i m i z a t i o na n dd u m m y - n o d e se l i m i n a t i o n s y s t e m ) 原型系统。具体的研究和实现- 下作有以下几个方面： 研究现有的d a g 画图方法。仔细分析现有的d a g 画图方法的优点和不足，设计新的 基于遗传算法的d a g 画图方法。 令 在工作中，设计了多项式时间的分层方案，改进了基于遗传算法的解决方案，通过实验 对2 种算法进行了比较，对结果进行了分析。 最小化边交叉上作中，在传统遗传算法解决的基础上，重新设计了算法的交叉算子、变 异算子和控制参数，进一步对算法进行了优化，并通过实验与目前流行的画图方法进行 了比较，对结果进行了理论分析。 夺 消除哑结点t 作中，介绍了删除哑结点的原则，然后提出了搜索容易删除哑结点的思想 并给出了2 条搜索规i l ! | j ，最后用一个例子展示了哑结点删除的过程。 实现了基于遗传算法的d a g 画图原型系统l e m d e s 。在对算法性能测试的基础上对系 统进行功能性测试。 1 4 论文的创新工作 本文的创新t 作主要体现在以下儿个方面： 对丁已有的分层和边交义遗传算法，重新设计了交义算子、变异算子和控制参数，实验 分析并设定控制参数。 夺 提出了解决分层问题的多项式时间的算法。 2 第一章引言 设计了哑结点的消除规则。 1 5 论文的组织结构 根据以上研究内容，本文其余部分的组织结构安排如下： 第二章介绍预备知识，全面分析d a g 画图问题，着重探讨d a g 画图问题中的3 个胛 难问题，由传统解决方法中的不足引出本文的解决方案。 第三章介绍分层问题遗传算法求解的思想和流程，分析算法的时间复杂度；介绍添加哑 结点算法的思想和时间复杂度；介绍分层问题的多项式时间算法思想，通过具体实验与遗传 算法从计算时间和结果两个方面进行比较，并分析产生这种结果的原因。 第四章介绍最小化边交叉问题遗传算法求解的思想，并分析算法的时间复杂度；通过实 验分析控制参数对于遗传算法本身的影响；通过实验对完全基于遗传算法的d a g 画图方法 ( g e n e t i c ) ，多项式算法解决分层和遗传算法解决边交义的d a g 画图方法( p o l y n o m i a lt i m e a n dg e n e t i c ) 与当前主流的画图方法组合能量算法( c o m b i n i n gh i e r a r c h ya n de n e r g y ) 在计算时 间和结果上进行比较，分析实验结果；通过实验简单探讨遗传算法迭代次数的规律。消除哑 结点问题，介绍删除哑结点的基本原则；提出搜索容易删除哑结点的思想并给出搜索规则， 用一个例子展示哑结点删除的过程。 第五章从结构和模块划分两个角度介绍l e m d e s 原型系统；给出系统输入，输出的文 件格式和网络图的画图结果；给出l e m d e s 原型系统和专用画图软件的界面和运行结果。 第八章对整篇论文进行总结，并对未来工作进行展望。 3 东南大学硕士学位论文 2 1概述 2 1 1 层次图 第二章有向无环图布局问题描述 层次图定义：个d a g 图g = ( y ，目，矿和层分别是顶点和d a g 边的集合，若它满足： ( 1 ) v 由h 个互不相交的子集构成： v = v o t j r , u u k 小( 圪n v = ，“叻其中匕 = o , 1 ，_ 一1 ) 为结点的集合，且位于第”层。 ( 2 ) 对于任意条边( f ，_ ，) f ，f 圪， ，k ，都满足“ ，其中边的长度等于v 一“。则称d a g 图 g 为“h 一层d a g 图( k - l a y e r e dd i g r a p h ) ”，记为g = ( v ，e ，| i i ) ，如图2 1 ( a ) ，图中的虚线即表 示图的层次，也称为图的高度。若g 中没有边长大于l 的边，则称其为“规范的h 层d a g 图( p r o p e rh - l a y e r e dd i g r a p h ) 6 如图2 一l ( b ) 。 o ( a ) 层次图 4 o ( ”规范层次图 图2 1 层次图和规范层次图 4 4 第二章有向无环图布局问题描述 2 1 2 遗传算法简介 遗传算法( g e n e t i ca l g o r i t h m ) 是模拟达尔文的遗传选择和自然淘汰的生物进化过程的 计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是有美国m i c h i g a n 大学 j h o l l a n d 教授于1 9 7 5 年首先提出来的，并出版了颇有影响的专著 a d a p t a t i o ni nn a t u r a la n d a r t i f i c i a ls y s t e m s ，遗传算法这个名称才逐渐为人所知，j h i l l a n d 教授所提出的遗传算法通 常为简单遗传算法( s g a ) 。 遗传算法是从代表问题可能潜在的解集的一个种群( p o p u l a t i o n ) 开始的，而一个种群 则由经过基因( g e n e ) 编码的一定数目的个体( i n d i v i d u a l ) 组成。每个个体实际上是染色体 ( c h r o m o s o m e ) 带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内 部表现( 即基因型) 是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是 由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因 型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码， 初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代( g e n e r a t i o n ) 演化产生出越来 越好的近似解，在每一代，根据问题域中个体的适应度( f i m e s s ) 大小挑选( s e l e c t i o n ) 个 体，并借助于自然遗传学的遗传算子( g e n e t i co p e r a t o r s ) 进行组合交叉( c r o s s o v e r ) 和变异 ( m u t a t i o n ) ，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种 群比前代更加适应于环境，末代种群中的最优个体经过解码( d e c o d i n g ) ，可以作为问题近 似最优解。 2 1 3 常用符号定义 令 夺 夺 本文中常用的符号约定如下： 输入的邻接矩阵所表达的d a g 图g = ( y ，d 。 分层后层次数( 即图的高度) 为h ，宽度为w 。 、 转化为规范层次图需要添加哑结点数为k ，结点总数为，l ，边的条数为。 用f ，k 表示结点，结点i 所在的层次为l ( 0 ，“，y 表示层次，对于一个起始结点 为i ，终止结点为j 的边就表示为( f ，) ，其长度为岛。 在遗传算法中，由于染色体长度即图中结点个数，因此染色体长度为刀，染色体群含染 色体个数为珑，遗传代数为t 。 2 2基本审美标准和对应的解决方案 2 2 1 基本审美标准 精确的定义一张d a g 图是否美观是很困难的：无论是“好( g o o d ) ”，“不错( n i c e ) ” 和“赏心悦目( a e s t h e t i c a l l yp l e a s i n g ) ”都是非常主观的概念，而且随着应用环境和川户的 心境而变化。然而下面的准j j ! u 是被人们普遍接受的【6 1 。 第一，所谓有向图当然要有一个同定而且统一的方向：符合这个标准则需要所有边的方 向相同。在一些应用中，倾向丁朋轴表示方向；在另一些的应用中可能倾向- 丁川y 轴表 5 东南大学硕士学位论文 示方向。本文以x 轴表示方向，当然，以x 轴表示方向的图可以通过旋转9 0 。转变成以y 轴 表示方向的图。因此第一条审美标准g ：避免反向边。 第二，如果在一个区域中有过多的结点，则整张图会变的难以理解。因此第二条审美标 准g ：结点尽量均匀分布在整张画布上。 第三，过多边的交叉使得用户难以明确看出图中边的起始结点和终止结点，从而导致整 张图难以理解。这引出了第三条审美标准g ：尽量减少图中边交叉的数量。 针对每一条审美标准，应当有一条解决方案。因此在下一节中，我们给出了3 条基本解 决方案s l ，最和墨，每一条方案对应一个审美标准，即墨对应g ，i = l ，2 ，3 。 2 2 2 基本解决方案 首先，本文研究的是有向无环图，由于图中不存在环，因此可以轻易避免出现反向边， 而对于一般的有向图，则在画图前应当首先进行去环的工作。因此第一条解决方案s ：对于 一般的有向图，在画图前需要去除图中的环。 其次，墨要解决的是d a g 图中结点的层次问题，也就是确定每个结点的x 坐标。 假设g = ( 矿，e ) 是一张简单的d a g 图。o ，1 一 一1 将g 分成h 层。那么图的高度( h e i g h t ) 就等于层次数h ，而图的宽度( w i d t h ) 即w = m a x l z 1 ，其中( o “j i i ) 。注意图中所有的 结点均处于竖直线( 即层次) 上。 图2 - 2 显不层次的层次图 如果图中所有边的长度均为l ，则称这样的d a g 图是规范的。 在实际应用中，结点并不一定被放置到固定的层次上；边的长度也不一定都为1 ，因此， 是的目的是将给定邻接矩阵的d a g 图转化为层次图，再将层次图转化为规范层次图。 画图时假设，每个结点的人小一致( 即图形中所有结点是一样的) ，而且与相邻结点( 包 括横向和纵向) 的距离有一个最小值，设置最小值的目的是为了避免出现边穿越结点的情况。 一般刚圆表示结点，设结点的半径为r ，则结点与其相邻结点的距离的最小值设为6 r1 6 1 。 层次图的高度由图的层次数决定；层次图的宽度由每层上的结点数的最火值决定。层次图的 宽度和高度就可以作为最终结果中d a g 图的宽度和高度。从输入矩阵的角度考虑，层次图 的高度由输入图的关键结点的个数决定，即关键结点越多( 关键路径越长) ，图的高度越人； 而图的宽度由输入图边的条数决定( 即输入矩阵中l 的个数) 。冈为图中边越多，表现在层 6 第二章有向无环图布局问题描述 次图上，同一层上结点的个数就越多，从而图的宽度越大。 通常采用最长路径分层法【引。入度为0 的结点f 被放置在第0 层，如果结点，与f 的最大 距离为埘，则结点，被放置在第用一1 层上。这样的分层方法有两个优点： 第一，结点层次的计算方法简单，计算时间少。 第二，每个结点均处于其可能存在的最小层次，也就是说，通过最长路径法确定的结点 的层次为研一l ，则，的层次不可能为p ，其中p l ，则用边i 斗j 啊寸呻刀柚啼代替边( f ，力，其中， 一2 为加 入的哑结点( 为了保证图中不存在长度大于l 的边而加入的虚结点，他们不存在于输入矩阵 中) 。图2 - 2 的层次图添加哑结点后的结果如图2 3 ，其中a ，皿，皿为添加的哑结点。 图2 - 3 显不层次的规范层次图 哑结点的加入又产生了新的问题： 第一，无论是分层还是计算交叉，计算时间都会随着结点数的增加而交长，更多的结点 意味着更k 的计算时问。因此，应当尽量减少加入1 亚结点的数量。 第二，在画图结束时，如果直接去除哑结点，那么哑结点意味着边的弯曲。如何在保证 图的边不弯曲的情况下去除1 亚结点是一个很少有人涉足的问题。 冈此第二条解决方案墨：加入尽可能少的哑结点将输入矩阵进行分层。 最后，& 的目的是在确定每个结点的y 坐标的同时，满足g 。 规范层次图中边交叉的个数与每个结点的具体位置无关，只与每层上的结点序列相关 州。冈此降低边交义的问题就转化成了如何适当的安排每层结点序列的问题，而不是确定每 7 东南大学硕士学位论文 个结点的具体位置。虽然问题表面上看来简化了许多，然而事实上即使对于一个只有2 层的 d a g 图，确定结点序列使得边交叉数最少的问题仍是一个朋，难问题【l l ，不能在多项式时间 内找到其最优解。 逐层扫描是经常采用的方法，首先第0 层的序列随机选定，对于“= l 。西一l ，确定第“层 的结点序列使得第“一1 层和第层之间的交叉数尽可能的小。然而这又带来了新的问题，第 ”层结点序列是在第“一l 层结点序列确定，并保证第“一l 层和第“层之间交义尽可能小的前 提下确定的，也就是说结点序列的确定只取决于前一层，而与前面的其他层无关。但是图是 一个整体，整个图的交叉数为所有层之间交叉数的总和，在每层结点序列只由前一层确定的 情况下，整个图的交叉数是否最优又成了一个新问题，仍然是胛难问趔1 1 】，如图2 - 4 。 o 1 2h - 2h - 1 图2 - 4 整张图交叉数的n p - h a r d 问题 如何将图视为一个整体，找到一个能够一次性优化整张图交义数的算法将在第四章中详 细探讨。因此第三条解决方案岛：将图视为一个整体，最小化图的交叉数。 8 第三章有向无环图分层算法 第三章有向无环图分层算法 3 1 分层问题的遗传算法求解 3 1 ，1 编码 设d a g 图的顶点数为n ，顶点的编号为0 刀一l ，各顶点的层次编码可设计为： c o d e = ( o ) ，工( 1 ) ，三( 2 ) 。上一1 ) ) ，工( f ) 为编号为f 的顶点所在的层次。 c o d e 可以用一个数组表示，数组下标为项点编号，数组元素为顶点所在的层次。为保 证编码的合法性，编码应当满足： ( 1 ) 0 l ( 0 三( f ) 编码工作实质上只需要对结点进行一遍扫描，因此编码工作的时间复杂度为d ( 玎) 。 3 1 2 初始化 初始化就是对编码的实际赋值，当然赋值要满足合法性( 即满足3 1 1 节中的( 1 ) 和( 2 ) ) 。 我们使用的初始化方法为： i f ( p m r d o ) = 纠 l ( ) m i h 卜o ； e l s e l 6 ) m i 斧m q x l t t ) l 七l ： i f ( s u c c o ) = 刭 l ( ；m n 产l 嘛西。 e l s e l 6 ) m d 一m i n l 砂 一l ： 其中结点i 为结点歹前驱，结点k 为结点，的后继。k 根据用户的需要由用户提供，k 不 应过小，过小会造成纵向上的结点堆积( 即图的宽度过大) ；k 也不应过火，过人会使得 图的层次过多，影响图的美观。设图的最小层次为k 。，则可以设置： k = 旦k 。 w 例如，如果用户希望图的高度为图宽度的2 倍，则可以设置k = 2 奉厶谢。 每个顶点i 所在的层次三( f ) 在区间【( f ) 商。，( f ) 一】中随机产生，而且得剑的初始解是合 法的。 初始化工作中分为若干个1 ：作，包括计算每个结点的直接前驱，计算每个结点的直接后 继和对每个结点的层次进行赋值。计算某结点的直接前驱时，要读取输入矩阵中该结点所在 列中标：怎为1 的所在行的结点( 即每次扫描的时间复杂度为o ( n ) ) ，扫描刀次的时问复杂度 为o ( n 2 ) ，因此计算所有结点的直接前驱一i ：作的时间复杂度为o ( n 2 ) 。同样计算结点直接后 继i ：作的时间复杂度也为o ( n 2 ) 。对每个结点的层次进行赋值只需要扫描一遍结点，冈此赋 9 东南大学硕士学位论文 值工作的时间复杂度为烈刀) 。综上所述，初始化工作的时间复杂度为o ( n 2 ) 。 3 1 3 适值函数和哑结点数目的确定 目标函数定义为： 厂= ( 工( _ ，) 一工( f ” i = 1j = l f = 1 f 其中的含义为图中边的总长度之合，设边的条数为，需要添加的哑结点的数目为 k 。不难看出，长度为l 的边不需要添加哑结点；长度为z 的边需要添加哑结点的数目为 ，一1 。因此： k = f n 3 1 4 选择策略 选择策略采用遗传算法中最基本的a + 以选择策略。即假设初始解群的数量为m ，将m 个 父代与m 个子代放在一起竞争，选出最好的a 个父代和最好的a 个子代解作为下一代的双亲 ( 其中a = m 2 ) 。 3 1 5 交叉和变异 交叉算子，交叉的目的是大规模改变结点的层次。通过生成3 个随机整数来实现， p o s r o ，m l 】， 以，c 如【o ，a - 1 ( c h i 哦) 。p o s 用于选择交义的位置，嘶和c 用于选择 发生交叉的2 个染色体。例如： 假设p o s = 2 ： 。 交义前： c o d e , = ( a o ，a l ，a 2 ，a 3 a n i ) c o d e 2 = ( t o ，6 l ，6 2 ，岛屯一i ) 交叉后： c d 如= ( a o ，a l ，a 2 ，6 3 也一1 ) 如= ( b o ，b j ，6 2 ，a 3 a n 1 ) 变异算子，变异的目的是随机改变某个顶点所在的层次。通过生成2 个随机整数米实现， i 【o ，刀一l 】，“【( f ) m l n ( f ) 。】。i 用于选择发生变异的结点编号，u 就是新的( f ) 。本文中 解群通过交叉得到子代后，子代会以一定的儿率发生变异，对丁不同的参数设置，得剑解的 质量是不同的，这只有通过反复的实验米验证。由丁分层问题较为简单，优化的程度不人， 所以不同参数的设置对算法本身的影响很难体现出米，我们将在第四章中通过实验验证不同 控制参数对丁算法本身的影响。 修复算子，在交义和变异的过程中，会出现不满足条什的解，因此在每次得到子代时都 需要川修复算子来去掉不符合条件的染色体。通过上述设计的交义和变异箅子，不会产生1 f 法解，冈此这里不需要设置修复算子。 i o 第三章有向无环图分层算法 3 1 6 控制参数 这里的控制参数包括：初始解规模m ，交叉概率p ，变异概率g ，迭代次数t ，迭代最 大代数m a xg e n e r a t i o n 。 初始解规模m ，可以根据问题的规模和优化的倾向性来确定。所谓优化的倾向性即优 化时更注重结果的质量还是计算时间。因此可以写成： 脚= 等 其中一是问题的规模( 即顶点的数目) ，q 为用户要求的结果质量与最优结果的近似比 值( 也可以理解为用户对结果质量的期望值) ，t 。为某一多项式算法计算时间与用户要求的 计算时问的比值。 交叉概率p ，p 用于控制发生交叉的概率。p 越大，解群发生改变的幅度越大，解改进 的速度就越快；但另一方面，随着p 的增大，计算时间也随之增加。因此可以写成： p = 口q - + 弦。 仅+ p = 1 其中和r 定义同上。口是对解质量要求的权重。是对计算时间要求的权重。根据 用户要求的不同来确定p 的值。 变异概率g ，q 用于控制发生变异的概率。实质上变异是对交叉的补充。交叉是大幅度 的改进解的质量，而变异是在细节上对解质量的优化h 5 1 。因此可以写成： q = 1 。p 迭代次数t 的终止代数m a x g e n e r a t i o n ，m a x g e n e r a t i o n 用于控制计算的代数。显然， m a xg e n e r a t i o n 是需要动态确定的，结束条件可以设定为当下一代的解比上一代优化的程 度低于某一阀值时，停止迭代。 关于参数的设定，将在第四章中详细介绍。 控制参数确定后，整个算法的计算过程可以写成： t ：= o ：s ：= o ： i n i t i a l i z e ( p ( t ) ) j w h i l et m a x _ g e n e r a t i o n ； w h i l e s p 似2 取d o u b l er l i o u ： 谚r l p c n c r o s s o v e r ( p ( t ) ) j 取d o u b l er e l o 1 1 ： i fr 2 q c n m u t a t e ( p ( t ) ) ； s ：= t + i ： e n d ： t ：= t + l ： e n d ； 其中p ( t ) 为第t 代的染色体群，s 用于控制交义操作的次数。 东南大学硕士学位论文 3 1 7 分层遗传算法流程和时间复杂度分析 根据给出的算法，可以得到如图3 1 的分层遗传算法的流程图。( 其中m a x g e n e r a t i o n 表 示遗传计算的总代数，p ( f ) 表示第t 代的染色体群，其中t = l 。a 勃l a x g e n e r a t i o n ) i i n i t i a l i z e ( p ( o ) ic a - c u a 钯胁e s s ， c h o o s e d 图3 - 1 分层问题遗传算法的流程图 设染色体群包含染色体的个数计为m ，分层问题中染色体| j = = 度无疑是结点个数n 。冈此 对于每一代时间复杂度为o ( m 幸力) ，得到计算t 代的时间复杂度为o ( t 幸所n ) 。 遗传算法遗传代数的确定是相对困难的，一般可以设置当前的最优解相对于上一代无改 进时停1 ：，这本身就是n p 问题。分层遗传算法的时间复杂度是与t 相关的，冈此是1 f 多项 式时间的。 3 2 添加哑结点 通过遗传算法的使用，每个实结点的层次已经确定，现行：的i ：作是根据实结点的层次添 1 2 三| 豳 匡 一 第三章有向无环图分层算法 加哑结点，以保证图中不存在长度超过l 的边，即把层次图转化为规范层次图，以便最小化 边交叉问题的处理。算法的思想是逐个搜索边，通过添加哑结点把长度大于1 的边分割成多 个长度为1 的边。整个算法过程： # - - - 0 ；j ：= o ：c o u n t ：= 0 w h i l ef 刀j w h i l e j i ) k ：= l i ) + i ： w h i l ek h i e r a r c b ( i 】七1 n e w m a t r i x n + c o u n t - 1 n + c o u n t = 1 ； i fk = l o ) 一1 n e w m a t r i x n + c o u n q 圈= l ： c o u n t ：= c o u n t + l ； i c = k + j ： e n d ； j ：_ j 七l ： e n d ： t ：= t + l ： e n d ： 上述算法中，c o u n t 是计数器。m a t r i x 是输入的邻接矩阵，n e w m a t r i x 是添加哑结点后的 规范层次图的矩阵。在添加哑结点的过程中，可以看到要对哑结点的不同位置分别进行处理 ( k 代表添加哑结点的编号) ： 令 添加的哑结点是需添加哑结点边上的第一个哑结点，则如果添加的哑结点同时是需添加 哑结点边上的最后一个哑结点：n e w m a t r i x i k = l 且n e w m a t r i x k j = 1 。如果添加的哑 结点不是需添加哑结点边上的最后一个哑结点：只需要n e w m a t r i x i k = l 。 添加的哑结点不是需添加哑结点边上的第一个哑结点。如果添加的哑结点同时是需添加 哑结点边上的最后一个哑结点：n e w m a t r i x k l 】【j i 】- l 且n e w m a t r i x k j = 1 。如果添加的 哑结点不是需添加哑结点边上的最后一个哑结点：只需要n e w m a t r i x k 一1 】 尼】= 1 。 整个算法可以通过流程图清晰表达，如图3 2 。 1 3 东南大学硕士学位论文 图3 - 2 添加哑结点算法流程 3 3 分层问题的多项式时间算法求解 3 3 1 分层问题多项式时间算法思想 分层工作的遗传算法需要用户提供图的层次k 。，目的是当图的结点数较多时，防止纵 向上的结点堆积。然而当图的结点数比较少，而且偏序关系复杂时，我们希望在多项式时间 内解决分层问题，又避免纵向上的结点堆积。与任务的开工完_ l 时间问题类似，我们计算每 个结点层次的方法如下： i f ( p r e d o ) = 鳓 l o ) m t o ： e l s e l o ) m l t m c l x l t ) 七i ： f f ( s u c c o ) = 纠 l o ) m o x 一l o ) m i n ： e l s e l o ) m 。t 卜m i n l k ) 一】： 与遗传算法解决分层问题初始化方法不同的是，对丁终i 卜结点，我们设置其最小层次与 最人层相等。则显然关键路径上的结点的最小层次与最人层次相等。 例如，给定一个1 4 个结点的邻接矩阵： 1 4 第= 章冉向尤耶图分层算法 计算每个结点可能处于的最小层次和展大层次得到：结点o ：【i ，1 1 ；结点1 2 ，2 】；结点 2 ：f 3 ，3 】；结点3 ： 2 ，卸；结点4 ：1 2 ，剐；结点5 ： 2 ，5 】；结点6 ：【2 ，叼；结点7h ，4 ；结点8 ：【5 ，5 】； 结点9 ：【6 ，8 】：结点1 0 ： 6 ，q ：结点1 1 7 ，7 】；结点1 2 ： 8 ，8 】；结点1 3 ： 9 ，明。 可以看到结点0 1 ，2 ，7 ，8 ，1 0 ，1 1 1 2 ，13 的层次已经确定( 定义为确定结点) 而层次可以浮动的结点为结点3 ，4 ，5 ，6 ，9 ( 定义为浮动结点) 。 为了清晰表达确定结点和浮动结点，用图分析如图3 0 。瞰中确定结点0 ，1 ，2 7 ， 8 ，1 0 ，1 1 1 2 ，1 3 也就是芙键结点用红色粗线条标出关键路径。浮动节点3 ，4 ，5 ，6 9 用蓝色标记。分层的日的就是确定这些浮动结点的层次而使得幽中边的比宣最小。 o 目3 - 3 关键路径和浮鲒 在3 13 中已经得到需要淤加哑结点的数目虬。，= ，一n 其中，为图中边的总蚝度之 台为边的条数。现在我们将n 分为2 部分：第一部分是边的丽个端结点均为关键路径 上的结点( 即结点的可能展人自j 最小层玖相等，结点f 自崖次已经确定) ，这部分边的个数计 为虬，总k 度计为 ：第一部分盐边的两个端结点不全是关键路径上的结点，这些边的个 数计为n ，总长度计为，。不难舀出对丁一个给定的d a g 幽，“， ，是确定的t 而 f 是变化的，边的总个数可咀，j 成： = + 同样，边的总k 度，山川定的 车可变的，组成： 矜匮 东南大学硕上学位论文 l = 氏七f 综上，需要添加哑结点的数目就可以转化为： 么。，= ( f o 一) + ( 。一) 由于0 ，五，都是确定的，所以k 取决于，也就是说求哑结点数目问题转化 成了求两个端结点不全是关键路径上的结点的边的总长度的问题。 下面就上面1 4 结点d a g 图的例子来讨论厂。 设结点i 所在的层次为( f ) ，与结点i 相关的边的总长度计为z ，其中f = 0 , 1 1 3 。可以 得到： f = 石+ 六+ 正+ 五+ 石 不难看出石= 工( 3 ) 一l ( 0 ) + 三( 7 ) 一上( 3 ) + ( 8 ) 一l ( 3 ) = ( 7 ) + l ( 8 ) 一上( o ) 一三( 3 ) ，而注意到其中 三( 7 ) + 三( 8 ) 一( 0 ) 为常数，可以认为六= g - l ( 3 ) ，其中g 为常数。 对于结点9 ，石= l ( 9 ) - l ( 7 ) + l ( 9 ) 一l ( 8