（系统分析与集成专业论文）基于遗传算法的有向无环图研究.pdf

摘要 有向图是研究可视化软件和信息工程问题的基本模型。由于图容易让人明白和记忆， 因此人们对于有向图算法有着相当大的兴趣。近年来，画图受到了越来越多的关注，对 画图算法的研究已经成为计算机科学领域中的一个新的研究方向。 有向图画图算法是画图领域的一个重要研究课题。目前，s u g i y a m a 启发式方法及其 相应变种是画有向图的主要方法。s u g i y a m a 启发式方法通常把画图问题分成三个子问 题：分层、每层顶点之间的排序以及调整。因为遗传算法在组合优化问题( 搜索范围比 较大) 中能够取得相当好的全局优化结果，所以可以将遗传算法用于画图问题中。事实 上，画图问题就是一个优化的过程。因此，本文提出了一个基于遗传算法的有向无环图 画图算法。研究工作的主要内容： 1 介绍了研究画图的意义以及画图问题的研究现状。 2 介绍了图的基本概念，图的表示；然后介绍了图的评判标准以及目前现有的画图 算法方法；最后介绍了遗传算法的基本流程。 3 介绍了基于启发式的有向图画图算法。算法主要包括三个步骤：删除环、分层、 减少边交叉。我们对于每一个步骤都给出了一些比较经典的启发式方法。 4 提出了一个基于遗传算法的有向无环图画图算法，给出了算法的设计方法和步骤， 并将其与以前的启发式方法作了比较。实验表明这种编码对于有向无环图是非常有效 的。在基于遗传算法的有向无环图画图算法中，我们采用了边长度表示法进行编码。在 遗传算法的设计过程中，我们还加入了质心启发式方法用来提高算法的效率。 关键词：有向图；无环图；启发式；遗传算法；有向无环图 a bs t r a c t s e v e r a lr e c e n tt o o l sf o rv i s u a l i z i n gs o f t w a r ea n di n f o r m a t i o ne n g i n e e r i n gp r o b l e m sh a v e u s e dd i r e c t e dg r a p h sa sab a s i cm o d e l t h u sc o n s i d e r a b l ei n t e r e s th a sa r i s e ni na l g o r i t h m sf o r d r a w i n gd i r e c t e dg r a p h sb e c a u s et h e ya r ee a s yt ou n d e r s t a n da n dr e m e m b e r i nt h el a s ty e a r s ， t h ef i e l do fg r a p hd r a w i n gh a sr e c e i v e di n c r e a s i n ga t t e n t i o n ，a n dt h es t u d yo fg r a p hd r a w i n g h a sb e c o m ean e wr e s e a r c hd i r e c t i o ni nc o m p u t e rs c i e n c e t h es t u d yo fa l g o r i t h m sf o rd r a w i n gd i g r a p h si so n eo ft h em o s ti m p o r t a n tr e s e a r c h s u b j e c t si ng r a p hd r a w i n g n o w , t h es u g i y a m ah e u r i s t i ca n di t sv a r i a n t sa r et h ep r e d o m i n a n t m e t h o d sf o rd r a w i n gd i r e c t e dg r a p h s t h i sh e u r i s t i cd e c o m p o s e st h ed r a w i n gp r o b l e mi n t o t h r e es u b - p r o b l e m s ：l a y e r i n g ，o r d e r i n go ft h en o d e si ne a c hl a y e r , a n df i n e - t u n i n g s i n c e g e n e t i ca l g o r i t h m s ( g a ) h a v es h o w nt ob eg o o dg l o b a lo p t i m i z e r sf o rab r o a dr a n g eo f o p t i m i z a t i o np r o b l e m s ，i ts e e m sn a t u r a lt ot r yt oa p p l yt h e mt og r a p hd r a w i n ga sw e l l a n d i n d e e d ，t h ep r o b l e mo fg r a p hd r a w i n gi sap r o c e s st oo p t i m i z e s o ，t h i sp a p e rp r o v i d e st h e g r a p hd r a w i n ga l g o r i t h mf o rd r a w i n gd i r e c t e da c y c l i cg r a p hb a s e do ng e n e t i ca l g o r i t h m s r e s e a r c hw o r km a i n l yi n v o l v e st h ef o l l o w i n g ： ( 1 ) f i r s tp r e s e n t ss o m eb a s i ci d e a sa b o u tg r a p hd r a w i n ga n dh a sad i s c u s s i o no fi t sc u r r e n t r e s e a r c hs i t u a t i o ni nt h e o r e t i c a la n dp r a c t i c a li s s u e s ( 2 ) f i r s t l yw ep r e s e n tb a s i cn o t i o no fg r a p h ，t h er e p r e s e n t a t i o no fg r a p h ，t h e ng i v es o m e e v a l u a t i o nc r i t e r i ao fg r a p ha n dp r o v i d es o m ed r a w i n gm e t h o d sf o rg r a p h sa tp r e s e n t ，f i n a l l y i n t r o d u c et h eb a s i cp r o c e s so fg e n e t i ca l g o r i t h m s ( 3 ) w ei n t r o d u c et h eh e u r i s t i ca l g o r i t h m so fd r a w i n gd i r e c t e dg r a p h t h ea l g o r i t h m i n c l u d e st h e r es t e p s ：c y c l er e m o v a l ，l a y e ra s s i g n m e n t ，c r o s s i n gr e d u c t i o n w ep r o v i d e s o m ec l a s s i c a lh e u r i s t i ca l g o r i t h m si ne a c hs t e p ( 4 ) w ei n t r o d u c et h eg r a p hd r a w i n ga l g o r i t h mf o rd r a w i n gd i r e c t e da c y c l i cg r a p hb a s e d o ng e n e t i ca l g o r i t h m s ，p r o v i d et h ed e s i g nm e t h o da n ds t e po ft h ea l g o r i t h m a sc o m p a r e d w i t ht h ef o r m e rh e u r i s t i cm e t h o d s ，t h eg e n e t i ca l g o r i t h mi sm o r ee f f i c i e n t w eu s ean e w r e p r e s e n t a t i o n - - t h ee d g el e n g t hr e p r e s e n t a t i o n ，w h i l ew ed e s i g ng e n e t i ca l g o r i t h mf o r d i r e c t e dc y c l eg r a p h t h i sr e p r e s e n t a t i o ni sv e r ye f f i c i e n tf o rd i r e c t e dc y c l eg r a p h h o w e v e r , w ea d dc e n t r o i dh e u r i s t i ci ng e n e t i ca l g o r i t h mt oi m p r o v et h ee f f i c i e n c y n k e y w o r d s ：d i r e c t e dg r a p h ；a c y c l i cg r a p h ；h e u r i s t i c ；g e n e t i ca l g o r i t h m ；d i r e c t e da c y c l i cg r a p h 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研 究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文 不包含任何其他个人或集体己经发表或撰写的成果作品。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律后果由本人承担。 论文作者签名：胡牟芳 日期：文口口3 年b 月孑日 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学位 论文的印刷本和电子版，并提供目录检索与阅览服务；学校可以允许采用影 印、缩印、数字化或其它复制手段保存学位论文；在不以赢利为目的的前提 下，学校可以公开学位论文的部分或全部内容。( 保密论文在解密后遵守此 规定) 作者签名：即辛号 指剥雠茎趣 日期：反。叼占； 日期：专心6 岁 第1 章绪论 1 1 研究画图的意义 第1 章绪论 图( g r a p h ) 是一种抽象的数据结构，它可以用来作为关系信息的数学模型，它着重用 于刻画复杂信息内部元素及其之间的关系。自从图论诞生以来，数学家都一直在研究图 的几何表示。画图问题是典型数学问题之一( 构造一个平面图的直线平面画法) 。每一 个平面图都有一个平面直线画法。然而早期的研究结果主要关心的是证明直线画法的存 在性，而不是设计将图画出来的算法。计算机科学家在六十年代开始用画图帮助理解软 件。d e k n u t h 在1 9 6 3 年所写的画流程图论文【1 】也许是第一篇将画图算法用于可视化 目的的论文。 信息可视化技术是人机交互技术领域研究的一个重要课题。该技术致力于采用图或 图形机制来表现信息的结构，从而便于人们对大量的信息进行更有效的利用。关系信息 可视化系统大多数用图作为表示各种关系结构的数学模型。图可以被用来表示任何可以 用对象以及对象之间的联系表达的信息，其中顶点表示信息中的对象，边表示对象之间 的关系，所以几乎计算机科学的每一个领域和软件产业的每一个部门都在某种形式上用 图表示关系信息模型。 信息的类型有很多，比如数值型数据、图、地理数据等。不同类型的信息有不同的 表现形式。比如，数值型数据可以使用柱型图表或饼型图表来表示，地理数据可以用编 码的地图来表示。 在当前的信息时代，采用手工画图的方法显然是不足取的，一方面，用于表示实际 系统模型的图的结构通常很复杂，具有大量的边和顶点，以至于用手工方法将图整齐、 美观地画出来几乎是不可能的：另一方面，即使用手工方法能够画出来，也必将耗费大量 的时间和精力。因此，基于计算机技术的自动画图问题成为一个重要的研究课题。 基于计算机技术的画图技术较手工绘图的优势在于： ( 1 ) 可以将人们从大量繁琐的画图、编辑图的工作中解放出来，从而使人们能够将 主要精力放在对图结构的分析上。利用计算机画图ga ，) 我们只需要输入图的顶点 集v 和图的边关系集e ，我们就可以将图形象的表示出来，这样就可以大大的减少我们 的工作量。 湖北大学顾：卜学位论义 ( 2 ) 便于图的浏览、编辑、修改和保存。人们可以方便地浏览图的结构，对其进行 实时地编辑、修改；采用计算机技术所画的图，显示于计算机屏幕上，保存于计算机的 磁盘中；通过屏幕，用磁盘可以更加方便的保存图，可以节约资源。 ( 3 ) 画图速度快。随着计算机技术的飞速发展，许多巨型计算机的计算速度己达到每 秒亿万次。对于大部分复杂图来说，都可以在较短的时间内画出令人满意的图。因此， 基于计算机技术的画图技术之“性育旨时间比”是比较大的。 ( 4 ) 有利于充分利用当前计算机领域中的其它技术成果，如网络技术、人机交互技术、 并行计算等。 1 2 画图问题的研究现状 近年来，画图受到了越来越多的关注，自1 9 9 2 年起，国际上每年举办一次画图学术研 讨会，其会议论文集被斯谱林格出版社发表在l n c s 中，形成了以美国的b r o w n 大学，澳 大利亚的n e w c a s t l e 大学，意大利的罗马第三大学等为首的若干研究中心，研究学者遍及 英国、德国、日本、加拿大、芬兰等国家。在过去十多年里，对画图问题的研究在画图 算法、系统、应用方面都取得了长足的进展。发表了大量的有关画图算法的学术论文， 文献【1 1 是一篇很好的有关画图的综述性文章，文中列举了3 0 0 多篇参考文献，也出现了许 多研究和商用自动画图工具和系统。人们关心的主要问题有： ( 1 ) 哪些因素影响画图的效果是否令人满意。 ( 2 ) 如何能够自动、美观地画出图来。 ( 3 ) 画图技术在实际工程中的应用。 关于画图的研究大致可以分为理论和应用两个方面。在理论方面的研究主要包括： ( 1 ) 研究图自身的组合性质及其表示方法。严格来说，对图的特性的研究不属于画 图问题的范畴，但是对其的研究很必要。其一，我们说过，图是信息的直接抽象，画图 是信息的再现。如果图自身不能够准确地反映信息，那么图即使画得再好，也是没有意 义的：其二，设计画图算法时需要考虑图的特性和用途。一般来说，不同的图有不同的美 观要求。而且即使是相同结构的图，也需要采用不同的画法以适应各自应用的特殊要求。 图与画图之间是一种互动关系。 有学者己在这方面进行了一些研究，提出了一些新的图结构，如组合图 ( c o m p o u n dg r a p h ) 1 2 1 ，簇型图( c l u s t e r e dg r a p h ) 【3 】等。组合图的特点在于，它含有两种类型 的边：表示包含关系的边及表示相邻关系的边；簇型图的特点在于，图的构成部分问的内 2 第i 章绪论 在结构存在较大的差异，因此不适合采用全局的美观准则来指导画图。针对这些新的图 结构，人们提出了一些新的画图思路。例如对于簇型图来说，有元画图方法( m e t ah e u r i s t i c d r a w i n gm e t h o d ) 等。文献【2 l 提出了一种组合图的画图方法。 ( 2 ) 分析人的审美心理，研究什么样的美观准则或画法能够更好地满足人们的需求。 我们己提到，美观准则是画图算法要实现的目标，因此，我们在着手进行算法设计 之前，必须首先明确究竟要满足哪些美观准则。选择一组合适的美观准则并不是件容易 的事，其一是从具体应用问题中抽象出合适的图结构模型比较困难，其二是关于“究竟 什么样的图才更美观”是一个很主观的问题，不同的应用有不同的美观要求。例如，在 图论的研究中，一般将图的顶点画为圆圈或者椭圆，边画为直线或者圆滑曲线；而在v l s i 设计中，顶点一般被画为方框，而边则被画为直线或折线。因此，根据应用的目的，制 定出合适的美观准则是设计有效画图算法的前提。 ( 3 ) 依据图的特性和美观准则，设计有效的画图算法。 这是研究画图的主要任务。一般来说，对各种不同类型的图有不同的画图算法，譬 如有画树、平面图、有向图、无向图的算法。而在每一类图中，又根据图的特性和相应 的美观准则的不同，而有不同的算法。设计一个好的画图算法，除了要考虑图的类型、 可采用的画图标准、美观准则等因素外，还需考虑算法的时间效率。设计一个画图既快 又好的算法是一项很困难的事。有时，我们需要在算法的时间效率和画图效果方面做一 权衡。 在应用方面，主要是利用画图算法，开发出具有人机交互功能的实用的画图工具或 系统。开发系统与纯粹研究画图算法的最大区别在于，系统允许人交互地参与到画图的 过程之中，以期能更好地画出令人满意的图。于是，基于人机交互技术的“动态画图算 法”的研究也应运而生。 目前，人们己开发出一些画图系统，它们有的功能简单、有的功能比较强大，有的 系统是专为特定领域开发的，有的系统的应用领域则较为广泛。 1 3 本文的研究内容 在对于有向图的画图算法研究中，大部分都是通过启发式算法来实现。然而在利用 启发式算法画图时，一般都是根据画图优化的目标选择相应的启发式算法。当优化的目 标发生了改变时，算法也要进行相应的改变。因此在使用启发式算法画图时，算法的通 用性就不行。在本文中，我们提出了利用遗传算法画有向无环图算法。遗传算法在优化 3 湖北人学硕j ：学位论文 领域已经证明了它的优越性，另外使用遗传算法画图更具有通用性，当我们改变优化条 件时，我们只需要对适应值函数进行设计的改变，算法其他方面并不需要太大的改变。 本文的组织如下：第一章概述了研究画图的意义以及画图问题的研究现状；第二章 介绍了本文需要的一些预备知识，具体包括图的基本概念，画图算法以及简要的介绍了 演化计算( 其中重点介绍了遗传算法的设计) ；第三章介绍了基于启发式的有向图画图 算法；第四章是介绍了基于遗传算法的有向无环图画图算法，这是本文的核心内容，也 是我们主要的工作重点。 4 第2 章预备知识 第2 章预备知识 本章我们将介绍图的基本概念，表示，画法，画图算法以及遗传算法。 2 1 图的基本概念，表示 本节主要介绍了一些关于图的基本知识，这些知识在我们的研究中是经常用到的。 2 1 1 图的基本概念 一个图g ：，) 是一个顶点与边的集合对，其中v 表示顶点的非空有限集合，e 表 示边的集合，每条边表示两个顶点之间的联系。图中存在两种类型的边：无向( 图2 1 ) 和有向( 图2 2 ) 。如果一个图中的所有边为有向的，我们称这个图为有向图；如果一 个图中的所有边为无向的，我们称这个图为无向图；如果一个图中同时包含有向边和无 向边，那我们称这个图为混合图。 在本文研究中，我们研究的是有向图的画法。 图2 1 无向图 湖北人学硕士学位论文 图2 2 有向图 一条边e ； ，y ) 的端点是u ，v ；我们称u ，v 是相互邻接的，也可以成n 是v 的邻接 结点( a d j a c e n tv e r t i c e s ) ，反之，v 也可以称为u 的邻接结点，边e 与顶点1 1 和顶点v 相关联。我们定义6 + ( ，) 为顶点v 的出边集合，其中6 + ( y ) 一 ( v ，“) i p ，u ) e e ；6 一o ) 为 顶点v 的入边集合，其中6 。o ) = 0 ，y ) 1 0 ，v ) e ) ；6 ( v ) 为顶点v 的相邻边集合。 1 6 + ( 1 ，) l ( 1 6 一o ) 1 ) 被称作为顶点v 的出度( 入度) 。 孤立结点( i s o l a t e dv e r t e x ) 不与任何结点相连接的结点称为孤立结点( 度数为零的 结点) ，也就是说，不存在任何包含顶点v 的边e = ，v ) e ，则称顶点v 是孤立结点。 环( 1 0 0 p 或者c y c l e ) 两端点相同的边称为环和自回路( c i r c u i t ) 。如图2 3 所示。 图2 3 环 设u 和v 是图g 的顶点，图g 的一条边u v 链( c h a i n 和w a l k ) 是有限的顶点和边 交替序列u o e l u ，e 2 “川e 。“。u = “。，y - - - - u 。) ，其中与边q ( 1s is 甩) 相邻的两顶点吩一。和吩 6 第2 章预备知识 正好是巳的两个端点。1 1 ( 链中出现的边数) 称为链的长度( 1 e n g t h ) 。u ( u 。)v ( u 。) 称 为链的端点( e n d - - v e r t i c e s ) ，其余的顶点称为链的内部点( i n t e r n a lv e r t i c e s ) 。一条u v 链，当u ：v 时，称它为开的，否则称为闭的。边互不同的链称为迹( t r a i l ) ，内部 点互不同的链称为路( p a t h ) 。 2 1 2 图的表示 通常表示图的两种重要方法是邻接列表和邻接矩阵： 邻接列表通常包含一组连接的列表，图中每一顶点都有一个连接的列表。邻接列表的 每一个元素表示属于该列表顶点的邻接点。 邻接矩阵m 常常用来表示有n 个顶点的图。每个元素要么为o ，要么为1 。如果矩阵 中第i 行，第j 列元素为1 ，则表示存在一条r e - ( f ，j ) e e 。相反，如果矩阵中第i 行， 第j 列元素为o ，则表示不存在边e 一( f ，j ) e e 。图2 4 是一个原始图，图2 5 是图2 4 的邻接列表表示，图2 6 是图2 4 的邻接矩阵表示。在本文研究中，我们是使用邻接矩 阵表示。 图2 4 原始图 7 湖北人学硕上学位论义 2 2 画图算法 图2 6 图的邻接矩阵表示 画图算法是解决如何生成图的一个几何表达的问题。在本节中我们简要的介绍了画 图算法，图的好坏评判标准以及常用的画图算法方法。 2 2 1 画图算法概述 一个图基本上可以说是一个顶点之间的任意二元联系的一个列表( 可以是有向的或 者无向的) 。通常，这些联系都是用一个邻接矩阵表示的。这种形式的表示对于图的各 8 皿 一 5 o o o 1 o 4 1 o 1 0 o 3 o 1 o o o 2 1 o o o 0 1 0 0 0 0 1 1 2 3 4 5 第2 章预备知识 种计算都足以满足，比如，找一对顶点之间的最短路径问题。但是如果要使某个图很容 易的被人们观看，那就需要把图表示成不同于邻接矩阵的形式，简而言之就是画图算法 被用来做什么的。 一个画图算法是以一个图g = ，e ) 为输入，给图g 中的每个顶点赋坐标值( 可能 是2 维的，也可能是3 维的) 。然后将e 中的每条边设置为一根曲线，其中这根曲线的 端点就是这条边连接的两个顶点。有时候画图算法也将些关于图的说明作为辅助的输 入。辅助的输入让画图算法指定一些辅助的限制，比如一个根结点或者顶点需要画在中 间。 对于每个图都存在无数中可能的规划。究竟那种规划适合，那种不适合? 当某一算 法被设计执行时，存在许多的标准。典型的标准就是美学的标准( 也就是图看起来好看， 很容易被理解，展示了图的所有重要属性等等) 。其他的标准如边的交叉数，整个图所 占的面积，图的对称性，以及弯曲度等等。画一个图的最重要的属性之一就是平面化。 如果一个图不存在边交叉，那么这个图就是平面图( 如图2 1 0 所示) 。 回匿 图2 7 同一个图，一个有边交叉，另一个没有边交叉 画图算法特别是用来设计画涉及数以千计的点和边的巨型图。这有一个额外的问题 出现画图算法中大多数被规定的目标都是n p 一难度问题，即大多数目标都不能在 线性的计算时间内得到，因此往往要折中考虑。例如：测试一个图的平面性可以在线性 的时间内完成，而最小化交叉点数却是一个n p 一难度问题。 画图中还存在一个问题就是在优化的标准中，标准彼此之间就是相互冲突的。比如， 对于要在同一时间内优化一个图使得边交叉数最小同时图有最大的对称性是不太可能 的( 如图2 1 1 所示) 。从图2 1 2 我们可以看出要使边交叉数最少和使图的层次长度最少 也是彼此相矛盾的。 _ 9 湖北人学硕l ：学位论义 图2 8 同一个图，一个使边交叉数最少，一个优化对称性 图2 9 同一个图，一个使得层次最少，一个使得交叉点最少 2 2 2 图的评估标准 如何评估一个画图算法? 有许多标准被应用到画图中，它们中大部分都是美学的标 准，其中这些美学的标准很难在数学意义上做详细的说明。我们怎么弄清楚一个图是否 是美观的? 计算机是不能够判断的。这就是为什么需要一个标准集，画图算法需要遵守 这些标准。每一个算法都是用来满足一个和多个目标。最重要的标准如下所示： ( 1 ) 最小化图中的边交叉数 1 0 第2 章预备知识 ( 2 )最小化图所占的面积 ( 3 ) 尽量使得边不弯曲 ( 4 ) 最大的对称性 ( 5 ) 使最长边的长度最小 ( 6 )顶点的分布应均匀 画图的许多属性都是很难被计算的，甚至很难估计。测试图的平面性需要线性的时间 ( 估计) ，但是图( 图是平面图) 的最小交叉数是n p 一难度问题。在一个平面直角画 图中，最小边的弯曲一般情况下也是n p 一难度问题。 因为大部分最小化最大化问题( 这些问题为了要取得算法所要达到的目标而需要被 解决) 都是n p 一一难度计算问题，所以我们有必要折衷考虑。如果有且仅有一个最小化 最大化结构被发现了，它通常是可以满足的。这个最大化最小化结构并不一定要是最 好的( 最终的) 。画图算法的大部分目标证明是有许多不同方式解决的优化问题。在优 化问题中，有许多可能的办法是优化到局部最优而并不是整个的全局最优。发现一个全 局最小化最大化解通常都是n p 一难度，而发现一个局部最小化最大化解大部分可以在 线性时间内完成。 2 2 3 画图算法方法介绍 画图是一个新的而且有活力的研究课题。事实上，关于画图有数以百计的不同种类 型的算法。在这里，我们将对其中的一些算法给一个大致的总体介绍。每个算法都拥有 它的使用限制，有些算法是专门为某一类型的图特定设计的，然而其他的算法可以因为 具有更一般性，可以被应用于不同类型的图。大部分图都是用有向无环图( d i r e c t e d a c y c l i cg r a p h s ，简称d a g ) 。因为有向无环图特别的重要，常常有许多算法都是主要 集中在这种类型的图，而不能被应用到其他类型的图去。 ( 1 ) 层次画图 层次图在所有图中占有很大的比例。层次图包括完全二叉树和一般二叉树。分层是 被应用到层次图中的一个一般技术。分层的过程为：图g 一，e ) 中的顶点集合v 被分 成有限组l ；，使得v = l lu l ：u 厶u u l ，其中对于每条边 ， ，) e 都满足：h 厶， v e l ，( bj ) 。e 中的每个子集l i 都被画在2 维坐标系统a e ( 其中y 的坐标固定维y = f ) 。 湖北人学硕上学位论义 树通常被画成平面的，直线的以及向上的图。向上的图是表示父结点是在子结点上 面的几何术语( y 。删 y 棚协。) 。比如一个树( 特别是有根树) 包括大量的层次，确定 和展示对称性以及同构子树将可以满足人们的需要。分层( 上面提到的) 也常常被应用 在树中，因为同一层次中的顶点都有一些相同点，因此它们被放在同一样的y 坐标中。 关于树的画图算法另外一个重要的属性就是图所占的面积。层次画图要求面积于刀2 成 比例( n 是顶点的个数) 。 层次图也包括能被画成树的一类图。存在许多形式的树经常被使用在不同的应用 中。二叉树( 图2 1 0 ) 是一种每个顶点最多只有两个子结点的树。二叉树能够作为例子 被用在形式化的表示一个二元决策树中。一个有根树是表示只存在一个结点在最顶端的 树，其他的结点都是从这个根结点引发出来的。有根树能够作为例子被用在形式化的表 示一个概率树中( 贝叶斯网络) ，概率树经常被用在形式化机械知识算法。 图2 1 0 有根二叉树 画层次图的另外一个技术采用另一种方法。这种技术采取两步过程：第一步就是将 图平面化；第二步生成一个平面的向上的图。这种方法相比分层方法不是很实用。因为 确定一个有向无环图能否被画成一个平面的向上的图是一个n p 一完全难度。进一步来 说，对于特定类型的图，算法需要在多项式的时间才能发现。 ( 2 ) 一般无向图画法- - g i o i t o g i o t t o 是一种能够画任何形式的任意的无向图的算法。g i o t i o 被设计用来得到 一个最小化弯曲的直角图。算法包括两个核心步骤：首先，平面化( p l a n a r i z a t i o n ) ，构 建一个平面图( 通过对交叉点引入辅助点) ；然后，弯曲最小化( b e n dm i n i m i z a t i o n ) ， 为了使边的弯曲最小化，执行边的弯曲最小化过程。如果2 1 5 所示。 第2 章颅蔷知识 图2 1 1g i o t t o 算法的两个步骤 这两个步骤称为正交化和压缩。g i o t t o 算法要求在进行第二步时输入的是一个平 面图，那也就是为什么需要执行第一步有效的平面化。如果该图不能转变成一个平 面图，我们就需要引进一个辅助点使图能够平面化。 ( 3 ) 力引导技术 在画图的过程中，存在许多的地方可以引入力引导( f o r c e d i r e c t e d ) 方法。这些方 法的大部分都是来源于物理和数学中。在这些领域有许多有名的方法，这些方法是用来 解决一些比较困难的优化问题。画图中的问题也主要是优化问题。因此这些技术也可以 被使用到画图中去。两个特别有名的关于画图力引导技术是弹簧嵌入式( s p r i n g e m b e d d e r ) 和模拟退火( s i m u l a t e da n n e a l i n g ) 。关于这两个方法如下所述。 ( 4 ) 弹簧嵌入式 弹簧嵌入式算法是力引导技术的一个应用。 弹簧嵌入式最初是由e a d e s 提出来的。它的大概思想是：用弹簧( s p r i n g ) 代替每 条边。弹簧具有一个属性，那就是当端点被伸长，它能吸引端点；当端点被压缩，它又 能排斥端点。边的最佳长度就是弹簧的自然长度。弹簧在自然长度时，被弹簧连接的两 顶点之间是没有力的。最初系统产生的图是被随机的选择( 边的长度，顶点的位置都是 被随机选择) 。接下来的步骤就是完全的让系统运行，直到系统处于一个固定的状态。 1 3 湖北人学硕士学位论文 通过这种过程能生成比较“好”的图。连接顶点的由顶点和弹簧组成的系统能够很容易用 许多数学的等式表示。这种等式的系统可以解决找到一个稳定的状态问题。当达到最小 的能量( e = m i n 上，q ) 二。 ) ) 时，也就达到了弹簧系统的最终状态。其中，e 是每条 边的长度，弹簧的自然长度为0 。 ( 5 ) 模拟退火 另外一个应用到画图中的力引导方法就是模拟退火方法【2 4 】。模拟退火( s a ) 是一 个灵活的最优化方法，它适合于大规模的组合优化问题。它最初被使用在统计力学领域， 但它也成功地应用于其他的优化问题，像旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 和v l s i 规划。使用模拟退火的问题由以下特征： a 大规模离散的结构空间； b 完全搜索的空间很大； c 目标代价函数是最小化。 在获取一些初始的结构后，通过反复执行方法从而在每一步选择一个新的结构，对 新的结构进行评估，有可能用它代替以前的结构。这种行为反复执行直到一些终止条件 被满足了( 也就是不能在缩减目标函数) 。这个过程在一个最小化的结构中终止，但是 一般是一个局部的最小化，而不是令人满意的全局最优化。模拟退火方法通过使用一些 标准避免局部最小化。这些准则来源于一个液体被冷却成水晶形式的过程( 这个过程叫 做退火) 类比。我们都知道，当一液体慢慢的被冷却，它将达到一个被完全整齐的形式。 这种形式称为晶体，他表示系统能量最小化的状态。相反，快速的冷却将导致形成一个 无组织的结构，那就有更高的能量，表示处于局部最小化。当液体慢慢地被冷却时，有 所不同的原因是：原子有时间达到彼此温度之间的热量平衡。 2 2 4 演化计算的概述 大自然是人类最好的老师。人类不断将观察到的自然界现象和人类自己的需要联系 起来，从中获得灵感，解决实际问题。这种方法被证明极为有效，现有已形成专门的科 学分支仿生学( b i o n i c s ) 。演化计算是一种基于大自然演化的规律而发展起来的一 种通用问题的求解方法，它采用简单的编码技术来表示各种复杂的结构，并通过对一组 编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。由 于它采用种群的方式搜索，这使得它可同时搜索解空间的各个区域。而且用种群组织搜 1 4 第2 章预备知识 索的方式使得演化算法特别适合于大规模并行。六、七十年代由于计算机不够普及而且 速度也跟不上要求，加上当时基于符号处理的人工智能方法正处于其顶峰状态，使得人 们难以认识到演化计算的有效性与适应性。八十年代初期，由于计算机速度的提高以及 并行计算机的普及，已使得演化计算对计算机的要求已不再是制约其发展的因素。另外， 由于演化算法对于刻画问题特征的条件要求很少，再加上它效率很高、易于操作、简单 通用，从而使得它已经广泛应用于各种不同的领域中。更由于它的不断发展和优化，机 器学习及各种工程技术应用领域取得的成功，演化计算已表现了良好的应用前景。 把计算机科学与进化论结合起来的尝试始于上世纪五十年代。六十年代中期，美国 m i c h i g a n 大学的j o h nh o l l a n d 提出了遗传算法【4 1 。随后，他将该算法用于自然和人工系 统的自适应行为的研究中。他的目标并不是用该算法求解一个具体问题，而是通过研究 自然界中的自适应现象来找到一种方法，将这种自适应机制应用到计算科学中。1 9 7 5 年，他发表了其快创性的著作“a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s ：a ni n t r o d u c t o r y a n a l y s i sw i t ha p p l i c a t i o n st ob i o l o g y , c o n t r o l ，a n da r t i f i c i a li n t e l l i g e n c e ”。在其中，他描述了 遗传算法的理论框架。遗传算法以使用位串编码的“个体”组成“种群”，使用诸如“杂 交”、“变异”等遗传算子进行“种群”的繁殖，通过选择机制来演化出“后代”。这种算法 以其通用的编码技术和简单有效的遗传操作作为其广泛的应用和成功奠定了基础。 最初演化计算有三大分支：遗传算法( g e n e t i c a l g o r i t h m ，g a ) ，演化规划( e v o l u t i o n a r y p r o g r a m m i n g ，e p ) i s l ，演化策略( e v o l u t i o n a r ys t r a t e g y , e s ) 6 1 。九十年代初，在遗传算 法的基础上又发展了一个分支：遗传程序设计( g e n e t i cp r o g r a m m i n g ，g p ) 1 7 1 8 】) 。在本 文中我们利用的遗传算法求解。 2 3 遗传算法的设计与实现 遗传算法集中体现了演化计算的特点。下面我们对遗传算法做一个详细地介绍。通 过对遗传算法的介绍，我们可以知道整个遗传算法总体上有一定的了解。 2 - 3 1 遗传算法的框架 遗传算法的流程图如图2 1 8 所示： 遗传算法( g a ) 的形式化描述可以用一个8 元组表示： g a = ( c ，e ，p 0 ，m ，q g , f ，1 i j ，t ) 1 5 湖北人学颀f ：学位论文 其中： c 一个体的编码方法； e 爪体适应度评价函数； 昂初始群体； m 群体大小； f 选择算子； g 一杂交算子； 、卜变异算子； t - 遗传算子终止条件。 2 3 2 编码和初始化 在遗传算法中如何描述问题的可行解，即把一个问题的可行解从其解空间转换到遗 传算法处理的搜索空间的转换方法就称为编码。编码空间与解空间的关系如图2 1 9 所 示。而在算法开始时，要给算法提供一组随机产生的初始解，称为“初始种群”。 1 6 第2 章预备知识 图2 1 2 遗传算法的流程图 图2 1 3 解空间与编码空间 1 7 湖北人学硕r 上学位论文 2 3 2 1 编码 编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。 编码方法除了决定了个体的染色体排列形式之外，它还决定了个体从搜索空间的基因型 转换到解空间的表现型时的解码方法，编码方法也影响到杂交算子、变异算子等遗传算 子的运算方法。由此可见，编码方法在很大程度上决定了如何进行群体的遗传进化运算 以及遗传进化运算的效率。一个好的编码方法，有可能会使得交叉运算、变异运算等遗 传操作可以简单地实现和执行。而一个差地编码方法，却有可能会使得交叉运算、变异 运算等遗传操作难以实现，也有可能会产生很多在可行解集合内无对应可行解地个体， 这些个体经解码处理后所表示的解被称为无效解。虽然有时产生一些无效解却并不完全 都是有害的，但大部分情况下它却是影响遗传算法运行效率的主要因素之一。 针对一个具体应用问题，如何设计一种完美的编码方案一直是遗传算法的应用难点 之一，也是遗传算法的一个重要研究方向。可以说目前还没有一套既严密又完整的指导 理论及评价准则能够帮助我们设计编码方案。作为参考，d ej o n g 曾提出了两条操作性 较强的实用编码原则( 又称为编码规则) 1 9 ： 编码原则一( 有意义积木块编码原则) ：应使用能易于产生与所求问题相关的且具 有低阶、短定义长度模式的编码方案； 编码原n - - ( 最小字符集编码原则) ：应使用能使问题得到自然表示或描述的具有 最小编码字符集的编码方案。 对于基本遗传算法，编码就是使用二进制编码方法。但由于遗传算法应用的广泛性， 迄今为止人们已经提出了许多种不同的编码方法。我们下面介绍其中两种最主要的：二 进制编码方法和浮点数编码。 ( 1 ) 二进制编码 二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集是由二 进制符号0 和1 所组成的二值符号集 0 ，1 ) ，它所构成的个体基因型是一个二进制编码符 号串。 ( 2 ) 浮点数编码方法 对于一些多维、高精度要求的连续函数优化问题，使用二进制编码来表示个体时将 会有些不利之处。为改进二进制编码方法的缺点，人们提出了个体的浮点数编码方法。 所谓浮点数编码方法，是指个体的每个基因值用某一范围内的一个浮点数来表示，个体 第2 章颅备知识 编码长度等于其决策变量的个数。因为这种编码方法使用的是决策变量的真实值，所以 浮点数编码方法也叫做真值编码方法。 2 3 2 2 初始化 遗传算法的特点之一就是它同时搜索解空间内的许多点，因而首先得有一组随机产 生的初始解，称为“初始种群”。一般而言，种群的规模要根据具体问题及试验来确定。 随机产生的染色体有可能是非法的，为使得初始种群中的所有染色体都是合法的，一种 方法是对随机产生地每个染色体进行合法性检查，如果其非法，则舍去，直到产生合法 的染色体为止。这种方法虽然简单，但效率不高。 如果我们能够使得任一个随机产生地染色体都是合法的，而不必进行合法性检查， 则无疑能够大大提高生成初始种群的效率。这种方法要求我们首先得根据具体问题找出 合法的染色体所具备的特征规律，然后按照这个规律仔细设计算法，就能够保证随机生 成的染色体是合法的。本文我们将讨论的基于遗传算法的有向图顶点分层算法都是采用 这种方法来生成初始种群。 2 3 3 适应值函数 在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某 个物种对于其生存环境的适应程度。对生存环境适应程度较高的物种将有更多的繁殖机 会；而对生存环境适应程度较低的物种，其繁殖机会就相对较少，甚至会逐渐灭绝。与 此相类似，遗传算法中也使用适应度这个概念来度量群体中各个个体在优化计算中有可 能达到或接近于或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概 率就较大；而适应度较低的个体遗传到下一代的概率就相对小一些。度量个体适应度的 函数称为适应度函数( f i t n e s sf u n c t i o n ) 。 遗传算法的一个特点是它仅使用所求问题的目标函数值就可得到下一步的有关搜 索信息。而对目标函数值的使用是通过评价个体的适应度来体现的。评价个体适应度的 一般过程： ( 1 ) 对个体编码串进行解码处理后，可得到个体的表现型； ( 2 ) 由个体的表现型可计算出对应个体的目标函数值； ( 3 ) 根据最优化问题的类型，由目标函数值按一