（计算机应用技术专业论文）抽象数据关系的三维实时动态可视化研究.pdf

摘要 摘要 抽象数据关系可视化主要是针对于数据结构的可视化，而图是应用最一般且 最广泛的数据结构。图的可视化包括静态图可视化和动态图可视化，但动态图可 以看成是由静态图组成的序列，因此静态图布局算法是动态图布局算法的基础。 一般静态无向图的作图是将布局问题转化为求一个目标函数的极值问题，再 利用某种算法来求目标函数的最优解的近似值来得到节点布局坐标。而一般动态 图的作图通常是使用静态布局算法分别对动态图的单个图进行布局，结果，布局 后的各个图之间缺乏联系，不能保持动态图的稳定性。 、 本文将协同进化遗传算法应用于静态图的布局算法中，通过协同进化遗传算 法来求解布局目标函数极值。同时针对动态图，在协同进化遗传布局算法的基础 上将现实中的“前进队伍插队”应用到动态稳定性布局算法中达到动态稳定性效 果。 协同进化遗传布局算法将种群分为两个子群，在两个子群独立进化的过程 中，模拟自然界的协同过程不断进行子群间的交流，最后达到共同进化的目的， 较快的收敛到全局最优解。实验证明，将协同进化遗传算法应用到无向图的布局 中，能有效地克服单纯遗传算法的缺陷，如很容易陷入局部最优、随着问题规模 的增大收敛性显著降低等等。同时，协同进化遗传算法是一种有效的搜索最优解 的算法，它在收敛性和收敛时间方面的效果都优于遗传模拟退火布局算法。 “前进队伍插队”动态稳定性布局算法其最初的布局是由协同进化遗传布局 算法产生，其美观性决定了动态图的后续美观性。对图的每一次动态更新都是在 前一次稳定的布局的基础上，通过使用重心、牵制权重等概念，进行“局部变化 大，整体变化小”的布局更新，并根据新图的结构和变化来控制节点的布局，从 而在布局算法中即考虑了图的全局结构也尽量保持了原有图形的稳定性。 本文最后对这两种算法都进行了实验验证及分析，证明了这两种算法在静态 图和动态图的布局中具有较高的可行性和有效性。 关键词：可视化；数据结构；算法；协同进化；动态稳定性 广东上业大学工学硕士学位论文 a b s t r a c t v i s u a l i z a t i o no fa b s t r a c td a t ar e l a t i o n si sa i m e dm a i n l ya tv i s u a l i z i n gd a t a s t r u c t u r e ，a n dg r a p hi st h em o s tg e n e r a la n df r e q u e n tu s e dd a t as t r u c t u r e v i s u a l i z a t i o n o f g r a p hi n c l u d i n gs t a t i ca n dd y n a m i cg r a p hv i s u a l i z a t i o n s i n c ed y n a m i cg r a p hc a n b er e g a r d e d a sas e r i e so fs t a t i cg r a p h , s t a t i cg r a p hl a y o u ta l g o r i t h ms e r v e sa sab a s i s f o rd y n a m i cg r a p h l a y o u td r a w i n gf o rg e n e r a ls t a t i cu n d i r e c t e dg r a p hi st r a n s f o r m e d i n t oa n o p t i m i z a t i o no fc e r t a i no b j e c t i v ef u n c t i o nm o d e l e dt o r e f l e c tc e r t a i na e s t h e t i c so f g r a p hl a y o u t as o l u t i o nf o rt h i sn u m e r i c a lp r o b l e mb r i n g so p t i m i z e dg r a p hl a y o u t a n dl a y o u td r a w i n gf o rd y n a m i cg r a p hi su s u a l l yu p d a t e db yt h es a m es t a t i cg r a p h l a y o u ta l g o r i t h m s ot h er e s u ro fl a y o u td r a w i n gi sl a c ko fc o n t a c tb e t w e e ng r a p h s , a n dh a sm a d ei ti m p o s s i b l et om a i n t a i nt h es t a b i l i t yo fd y n a r n i cg r a p h t h i sp a p e ra p p l i e sc o e v o l u t i o ng e n e t i ca l g o r i t h mi ng r a p hl a y o u ta l g o r i t h m ， w h e r ec o e v o l u t i o ns e r v e st os o l v et h eo p t i m i z a t i o no fo b j e c t i v ef u n c t i o n a sf o r d y n a m i cl a y o u t ，a p p l y i n g j u m pt h em o v i n gq u e u e i nl a y o u ta l g o r i t h mf o rd y n a m i c g r a p hb a s e do nc o e v o l u t i o ng e n e t i ca l g o r i t h mi sa i m e dt om a i n t a i n i t ss t a b i l i t y c o e v o l u t i o ng e n e t i ca l g o r i t h mf o rg r a p hl a y o u td i v i d e st h ew h o l ep o p u l a t i o n i n t ot w os u b p o p u l a t i o n sw h i c hc o m m u n i c a t ew i t h e a c ho t h e ri nt h ep r o c e s so f e v o l u t i o n ，s i m u l a t i o np r o c e s sf o rt h ep u r p o s eo fa c h i e v i n gb e t t e ro rf a s t e re v o l u t i o n a l e f f e c tt h a ni nc o u n t e r p a r tc a s eo fo n l yas i n g l ep o p u l a t i o n e x p e r i m e n t a ld a t ah a s s h o w nt h a tc o e v o l u t i o ng e n e t i ca l g o r i t h ma p p l i e di ng r a p hl a y o u to fg e n e r a l u n d i r e c t e dg r a p hc a ne f f e c t i v e l yo v e r c o m et h es h o r t c o m i n g so fs i m p l eg e n e t i c a l g o r i t h m , s u c ha s at e n d e n c yo fl o c a lo p t i m u m , o ras i g n i f i c a n tr e d u c t i o no f c o n v e r g e n c ew i t ht h ei n c r e a s i n gs c a l eo f t h ep o p u l a t i o ne t c f u r t h e r , i nr e s p e c t so f c o n v e r g e n c ea n dt e m p o r a lc o s tf o ri t ，c o e v o l u t i o ng e n e t i ca l g o r i t h mf o rg r a p h l a y o u ti ss u p e r i o rt og e n e t i cs i m u l a t e da n n e a l i n ga l g o r i t h mf o rg r a p hl a y o u t t h ei n i t i a ll a y o u to f j u m pt h em o v i n gq u e u e s t a b i l i t yl a y o u tf o rd y n a m i c g r a p hi sp r o d u c e db yc o e v o l u t i o ng e n e t i ca l g o r i t h mf o rg r a p hl a y o u t ，s ot h e n a b s 丁ra c t a e s t h e t i c so fd y n a m i cg r a p ha r ed e t e r m i n e db yt h ea e s t h e t i c so fc o e v o l u t i o ng e n e t i c a l g o r i t h mf o rg r a p hl a y o u t i nt h i sa l g o r i t h m , g r a p hl a y o u ti ss m o o t h l yu p d a t e d a c c o r d i n gt op r o g r e s s i v et o p o l o g i c a lc h a n g e s b yc o n t r o l l i n gb a r y c e n t e ra n dp i n n i n g w e i g h td e f i n e di nt h i sp a p e r , t h eu p d a t ee f f e c to f ”l a r g ep a r t i a lc h a n g e s ，s u b t l eo v e r a l l c h a n g e s ”i sa c h i e v e d a n d , p o s i t i o n so fv e r t i c e sa r em a n a g e db o t hb ys t r u c t u r ea n d c h a n g e so ft h eu p d a t e dg r a p h , t h ea l g o r i t h me s s e n t i a l l yt a k et h ew h o l eu n d a t e d s t r u c t u r ea n dc o n t i n u a ls t a b i l i t yi n t oa c c o u n t t h e s et w oa l g o r i t h m sa r et e s t e dr e s p e c t i v e l ya n da r ep r o v e dr e s p e c t i v e l yt h e i r f e a s i b i l i t ya n de f f e c t i v e n e s si ng r a p hd r a w i n gf o rs t a t i ca n dd y n a m i cg r a p h k e y w o r d s ：v i s u a l i z a t i o n ；d a t as t r u c t u r e ；a l g o r i t h m ；c o e v o l u t i o n ；d y n a m i cs t a b i l i t y i h 广东- t 业大学 ：学硕+ 学位论文 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包 含本人或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 论文作者签字： 指导教师签字： 2 0 0 8 年5 月1 8 日 够 躲 第一章绪论 第一章绪论 科学计算可视化( v i s u a l i z a t i o ni ns c i e n t i f i cc o m p u t i n g ) 是当前计算机科学的 一个重要研究方向，主要研究如何把科学数据转换成可视的、能帮助科学工作者 理解的信息的计算方法，是把计算机图形学与图象处理技术应用于计算科学的综 合学科。 软件可视化【1 1 是科学计算可视化领域里的一个重要的分支，已经成为计算机 教学领域里不可或缺的辅助工具。抽象数据关系可视化则是软件可视化的又一重 要分支。 本章简要介绍了抽象数据关系可视化的研究背景，抽象数据关系可视化的研 究意义，以及实现抽象数据关系可视化的开发工具的选择等。 1 1 研究背景 软件的主体是程序，当程序被编译并装载入计算机后，便只是存储在存储介 质上了，随后对于软件运行过程中的程序结构、运行行为都不可见，这使得对大 型复杂软件的直接理解几乎不可能，给软件开发、测试、维护和评估带来极大的 困难，阻碍了软件的发展和应用。因此软件可视化技术成为计算机软件界研究的 热点。软件可视化利用印刷术、图形、动硒和具有现代人一机交互功能的电影制 片技术和计算机图形技术等手段，使得软件便于理解和有效使用。 软件可视化指对计算机程序( 较低层) 或算法( 较高层) 的可视化，如图 1 1 所示，主要是分为程序可视化和算法可视化两大部分。程序可视化指对程序 代码或数据结构的静态或动态特征进行的可视化，可分为静态代码可视化、动态 代码可视化( 代码动画) 、静态数据可视化、动态数据可视化( 数据动画) 。算法 可视化指对软件高层抽象的可视化，也有一个从静态到动态的范围问题，所以分 为静态算法可视化、动态算法可视化( 算法动画) 。 抽象数据关系可视化归于程序可视化的研究范围，并着重于数据结构可视化 的研究。抽象数据关系可视化的主要任务是通过对算法和数据逻辑结构的自动抽 象来完整直观地对数据关系的可视化，最后实现算法与数据的动态关系及演变过 广东上业大学工学硕士学位论文 程，让学生对知识有一种直观的理解。 图1 - 1 软件可视化涉及的领域范围 f i g u r e1 - 1 t h ea r c a 略c o v e r e di nt h es o f t w a r ev i s u a l i z a t i o n s h n e i d e r m a n 做过一个实验【舶，他将参加实验的人分为两组，一组只有程序 的清单；第二组除了程序清单外，还有程序的伪代码描述；第三组除了程序清单 外，还有程序中主要数据结构的图形可视化，比较这三组人员对程序的理解，调 试和编写水平。实验结果是：只有程序清单的一组正确回答问题的平均分数为 5 0 6 ；有程序的伪代码描述的第二组的平均分数是6 0 6 ；有程序中主要数据结构 的图形显示的第三组的平均分数是8 4 7 。从实验结果可以很明显的看出研究数据 结构的可视化确实能够有效提高对程序的理解，因此对抽象数据关系的可视化研 究具有非常重要作用。 1 2 研究意义 目前已经有许多应用广泛的可视化集成开发环境，如v i s u a l b a s i c ，v i s u a l c + + ，d e p h i ，j b u i l d e r 等等。这些可视化集成开发环境虽然在一定程度上简化了程 序界面设计，降低了编写界面程序的困难，有效地提高了软件开发的效率。但是， 在调试程序方面，并没有实现程序应用的数据结构或变量的可视化，并不是真正 意义上的可视化1 3 - 6 1 。 为了达到真正意义上的可视化，广东工业大学可视计算工作室自行研制了 a n y v i e w 系列的面向教学和开发的可视化程序开发环境系列软件，可以广泛用于 编程可视化教学、程序可视化分析和程序可视化调试等方面，其主要特点是实现 了程序运行过程中的可视化，目前该软件适用于c 语言、p a s c a l 语言和j a v a 。它 2 第一章绪论 可以在源程序的运行过程中实时地图形化表示各种数据结构及其变化过程。图 1 - 2 就是a n y v i e w 系列对部分数据结构的可视化表达。 h + 。豳。 n 一一互囵一一重圈一吨蚕圈 盎 p ( a ) 单向链表 国 誊啦 。匿窜4j ”擘雪铲 卤 函国圈翻 ， 面由 圄 ，jt。 豳豳 ( b ) - 叉树 咱曩圈* 匿图溺 f * 匿圈圈 +- * 囝圜圈圈 女 w每 堰受曲* 团委薹董圈呕匿曩三噩囹 ( c ) 图十字链表 图i - 2 a n y v i e w 对部分数据结构的可视化表达 f i g u r ei - 2 v i s u a l i z a t i o no fs o m ed a t as t r u c t u r e si na n y v i e w 在a n y v i e w 的设计中，数据结构的布局显得尤为重要，一个好的布局通常 可以传递非常准确的信息，目前大多数对数据结构可视化的研究都是基于二维图 形表示，如本文前面提到的a n y v i e w 系列集成开发环境。 二维可视化表达能够很好的表示一些简单的数据结构，如数组、链表、树( 二 叉、三叉等) 及简单的图等，但是二维可视化表达受空间的约束，存在一定的局 限性，如图的二义性问题。图1 3 ( a ) 试图来表达立方体图的三维结构，但在二 维中这样表达就存在边与边的交叉，不能很清楚的表达结点与边、边与边的实际 关系。图1 3 嘞虽然解决了( a ) 中边交叉问题，但边长不一致，没有完整表达立方 体图的特性。 三维图形表示不仅能完成所有二维的图形表示，而且还可以解决二维可视化 表达的局限性所带来的二义性问题。二维图形表示一旦画好后就不能再进行任何 改变( 如缩小、放大等) ，并且只能在有限的画布里显示，对于超出画布的图形 目露 0 1 ， 3 广东工业大学t 学硕士学位论文 部分将会被截断，这样就需要根据实际的画布大小来确定布局算法、结点大小以 及边的长短，尽量避免可视的对象超出画布范围。而三维图形表示可以定义一个 足够大的宇宙空间，可以通过空间的旋转、镜头的缩放等操作来调整，以达到最 佳效果。三维可视化表达更容易给人一个直观的、易于理解的图像模型，这正是 抽象数据关系可视化的最终目标。 ( a )( b ) 图1 3 立方体图的二二维可视表达 f i g u r e l - 32 dv i s u a l i z a t i o no f t h ec u b eg r a p h 根据以上分析，本文针对抽象数据关系的三维实时动态可视化研究具有非常 重要的意义。 1 3 研究内容和目标 本工作室开发的a n y v i e w 系列已经完整的实现对于数组、链表、树和简单 图等一些简单的数据结构的二维可视化，但对数据结构特别是一般图的三维可视 化还没有完全实现。抽象数据关系的可视化主要针对数据结构的可视化，而图是 最广泛、最一般的数据结构，为此本课题的研究对象是图。本文计划从静态布局 算法设计和动态布局的稳定性两个方面对图展开三维实时可视化研究。 第一，静态布局算法设计 本文由浅入深，从一般弹簧二维布局算法扩展到弹簧三维布局算法，在弹簧 建模的基础上，使用遗传算法来搜索目标函数的全局最优解。但是遗传算法的对 最优解的收敛速度相对比较慢，本文将协同进化遗传算法应用于一般无向图的布 局算法中，以改善一般无向图通用布局算法的收敛速度。 协同进化遗传算法的主要研究工作在于如何将协同进化过程应用到布局算 法中，为此本文引入个体基因块概念及基因块的划分方法。通过将个体基因块的 划分，在进化过程中，评价子群中的个体基因块的优劣，将一些好的、优秀的基 4 第一章绪论 因块保留下来，并与其它子群进行协同，从而达到共同进化，加快布局算法的收 敛速度。 第二，动态布局的稳定性 本文根据现实生活中的插队现象，将这种现象引入到动态图的稳定性布局 中，提出一种“前进队伍插队”的动态稳定性算法设计思想。该算法引入了两个概 念，一个是重心概念，另一个是牵制权重概念。 为了能让新增节点迅速融入到之前稳定的图中，新增节点的初始化位置是非 常重要的。根据弹簧建模思想，如果让新增节点的初始化位置置于与其联系节点 的重心位置，将有利于新增节点的迅速归队，大大减少算法的进化代数。 牵制权重是评价节点的稳固程度，牵制权重越大，节点在进化过程中变化的 幅度越小，反之在进化过程中变化的幅度越大，这样不会因图的更新而扰乱到所 有节点，有利于保持原有图的稳定性。同时由于采用的仍然是弹簧建模方式，因 此在美观性方面不会有较大程度的改变。 通过引入重心和牵制权重两个概念，可以让算法在动态图的布局过程中在保 持动态图的稳定性性的同时兼顾美观性。 1 4 设计与开发工具的选择 由于抽象数据关系的三维实时动态可视化研究是从a n y v i e w 系列研究开发 中细分出来的一个核心模块之一，研究的效果要能够满足a n y v i e w 系列的运行 要求，即处理、运行速度要快。基于这个原因，选择了v i s u a lc + + 作为开发工具。 v i s u a lc + + 是功能强大的可视化开发工具之一，它不仅支持面向对象、可视化的 开发风格，而且还支持传统的软件开发方法( 如c 语言编程) 。v i s u a lc + + 提供 了面向对象的应用程序框架m f c ( m i c r o s o f tf o u n d a t i o nc l a s s ) ，简化了程序员的编 程工作，提高了模块的可重用性，封装了w m d o w s 的a p i 函数、u s e r 、k e r n e l 、 g d i 函数，简化了编程时创建、维护窗口的许多复杂的工作。 在3 d 图形方面，由于本课题研究的最终目的是嵌入到a n y v i e w 编译器中， 所以为了不显著增加主应用程序的负担，选择o p e n g l l 7 】作为数据结构三维可视 化的图形编程语言。o p e n g l 是s g i 公司的三维图形编程工具，它已经成为一个工 业标准的计算机三维图形软件开发接口，并广泛应用于游戏开发、建筑、产品设 计、医学、地球科学、流体力学等领域。o p e n g l 是用于开发简捷的交互式二维 5 广东工业大学上学硕士学位论文 和三维图形应用程序的最佳环境，任何高性能的图形应用程序，从3 d 动画、c a d 辅助设计到可视化访真，都可以利用o p e n g l 高质量、高性能的特点。而且 o p e n g l 非常接近硬件，是一个图形与硬件的接i z i 。 1 5 论文的组织 本文的内容组织如下： 第一章介绍了抽象数据关系的三维实时动态可视化的研究背景、研究意义、 研究内容和目标，以及开发工具的选择等。 第二章简要介绍了现阶段各种布局算法的发展情况，详细说明了弹簧建模思 想，重点介绍了一般无向图的通用布局算法，包括遗传模拟退火布局算法，最后 简单介绍了协同进化遗传算法。 第三章介绍了如何将协同进化遗传算法应用于图的布局算法中。重点介绍了 个体基因块的划分方法，以及编码设计、适应度函数设计、协同算子设定等。最 后给出具体的实现算法和步骤。 第四章简要介绍了图的静态与动态可视化以及图的美观性与动态稳定性的 统一，重点介绍了“前进队伍插队”的稳定性布局算法的算法思想，并详细介绍了 算法的实现过程。 第五章主要是各算法实验结果比较与研究。首先是静态可视化的美观性和时 空复杂度比较，对比算法的优劣。其次是动态图可视化的稳定性与复杂度分析。 结论简要总结了本文的研究工作，最后提出本文的后续研究与展望。 6 第二章图布局算法的研究现状 第二章图布局算法的研究现状 长期以来，世界各国学者已经提出了相当多的作图布局算法，每种布局算法 相对于具体的应用有不同的审美准则。一般认为作图布局算法应尽量满足以下几 个美观性准则m o l ： 保持整体布局对称性； 尽量避免边的交叉和弯曲； 尽量保持边长统一； 节点分布均匀； 对于有向图，其边的指向保持一致。 各种不同的作图布局算法会针对其中的一部分或某些要素进行优化，最终目 的是要让人们能够从生成的图形中更容易地发现图的结构特点、更快捷地获得最 大的信息量。， 2 1 图布局算法的发展 2 1 1 图的2 d 布局 在过去的近2 0 年中，世界各国的学者研究的布局算法大都是基于2 d 的。 在2 d 布局算法中，根据应用的不同可以分为以下三类布局方法： 拓扑形状( t o p o l o g y - s h a p e ) 布局方法，由正交作图( o r t h o g o n a ld r a w i n g ) 扩 展而来，主要应用于实体关系i 虱( e n t i t y - r e l a t i o n s h i pd i a g r a m ) 和数据流图 ( d a t af l o wd i a g r a m ) ； 层次( h i e r a r c h i c a l ) 布局方法，主要应用于节点具有层次依赖关系的图中， 如p e r t 图、概念图、树等； 力导引算法( f o r c e d i r e c t e da l g o r i t h m ，以下简称f d a ) 布局方法，主要 应用于无向图的布局。 前两类方法都是通过将作图过程分解成一系列的步骤来处理美观性作图所 带来的潜在的冲突，每一步都追求一个或多个审美准则。最后一种方法是将物理 受力模型应用于布局图中，并寻求一种整体平稳状态或整体最小的受力配置。 7 广东工业大学工学硕士学位论文 2 1 2 力导引布局 力导引布局是本文研究的重点。f d a 最早是由p e t e re a d e s 提出的【l o 】，随后 被世界全国的学者发展出各种改进、优化布局算法。f d a 被广泛采用的一个主 要原因就在于其不但算法简单、易于理解和实现，更重要的是它能画出相当优美 的图形布局，并且能充分展现出图的整体结构及其自同构特征。但是f d a 布局算 法存在的一个较大的缺点，即运算复杂度高。由于f d a 每次迭代都必须重新计 算全部节点间的作用力关系，因此总循环次数通常在节点数n 的立方数量级，总的 时间复杂度是o ( n 3 ) 。对于节点较多的图或网，其布局时间很长，许多学者仍在 努力研究，不断提高f d a 算法的运算性能 1 1 q 4 1 但也有另外一些学者则致力于通 过引入不同的力学模型来使f d a 算法的最终结果更加美观在此方面有学者提出 了将节点集间的连接性映射为它们之间的几何路径的力学模型1 15 1 ，这使得高度连 接的点集在图中被显示为高密度的区域。 随着对网络特别是复杂网络的研究同益深入越来越多的学者大量开展适用 于复杂网络的可视化算法研究。其中由d s c h a n 、k s c h u a 、c l e c k i e 和a p a r h a r 提出的o d l 算法便是专门适用于幂律( p o w e r - l a w ) 网络的f d a 布局算法1 1 6 1 。在效 率比较实验中，o d l 的执行速度明显地快于以往的各种弹性模型算法。 2 1 3 图的3 d 布局 尽管当前的研究工作都集中在2 d 布局上，但随着信息的多样性发展，2 d 越来越难对信息进行完整可视化，为此越来越多的学者开始将研究工作从2 d 布 局转到3 d 布局 1 7 - 2 2 l 。 在传达信息结构方面，3 d 图形通过视角旋转给人以自然的、强烈的直观感， 这是3 d 可视化最吸引人的地方。随着显示设备和支持3 d 图形的硬件不断升级， 3 d 图形的显示速度越来越快，3 d 可视化将会越来越受到可视化学者的青睐。 对于图的3 d 布局，可以通过固定三维中的一维，再使用2 d 布局方法进行 布局，最后映射到3 d 环境中。这种布局方法只是变换了可视化环境，从2 d 转 到3 d ，所使用的布局方法仍然是2 d 布局方法，因此严格说来这不是真正意义 上的3 d 布局，因为它的动机只是想当然的认为节点应该被布局在一个单一的平 面上，没有充分利用到第三维信息。本文所提到的布局算法都是建立在真正的 8 第二章图布局算法的研究现状 3 d 布局方法上的，充分可视化图的真实结构。 2 23 d 弹簧建模 在图的布局算法发展相当短的历程中，弹簧建模布局算法是属于传统的物理 模型，这种模型将布局问题与某些易于计算机模拟的理想物理系统做了形式上的 类推。弹簧布局算法易于理解和实现，并能画出相当优美的、充分展现图的对称 特征的图l ”1 。尽管弹簧布局算法最初是在一般无向图的2 d 布局算法中提出来的， 但它同样适用于3 d 布局问题。 2 2 1 建模思想 弹簧布局算法的思想非常简单、直观。每个图被定义为由弹簧连接的理想无 摩擦的铰链机械系统。图中的每个节点当作铰链，每条边当作一个弹簧( 类型i ) ， 这个弹簧的长度指定为自然或无张力的长度。另外在所有节点( 包括没有边相连 的节点) 之间还存在一个假想的弹簧( 类型i i ) ，这个弹簧只存在斥力。弹簧布 局算法就是在这个理想的机械物理系统中找到一个平衡状态，这种平衡状态就是 图的期望布局。 代表边的类型i 弹簧用于控制边的长度，类型i i 的弹簧用于控制那些没有边 相连的节点的距离，因此弹簧布局算法大致满足以下两个审美准则： 尽量保持边的长度统一； 没有边相连的节点不能重叠。 通过这种物理模拟方法所生成的图的布局具有非常好的对称性。一般而言， 一个机械系统有多个不同的平衡状态，如图3 1 所示，其中b 和c 为平面图a 的 两种不同的3 d 平衡状态。要寻找一个图的所有平衡状态( 如通过图形显示后去 挑选“好”的一个) 在当前来说基本上是依靠人工来分辨。有些通过不同( 随机) 的初始化状态或者互换节点对位置来寻找全局最小能量的平衡状态。 最小能量的方法是由k a m a d a1 9 8 9 年提出来的【2 4 1 ，他使用著名的牛顿拉普 生数字极限搜索技术( n e w t o n - r a p h s o nn u m e r i c a le x t r e m u ms e a r c ht e c h n i q u e ) 来寻 找线性弹簧系统( 1 i n e a r - s p r i n gs y s t e m ) 最小能量的平衡状态。 9 广东= 业大学工学硕士学位论文 v 2 v v 2 v ( a )( b )( c ) 图2 1( b ) 和( c ) 是图( a ) 的两种不同的3 d 平衡状态 f i g u r e2 - l t h eg r a p hs h o w ni n ( a ) h a st h et w od i s t i n c te q u i l i b r i u m c o n f i g u r a t i o n s ( b ) a n d ( c ) i nt h r e ed i m e n s i o n s 2 2 2 弹簧建模 v 2 给定一个图g = ( v e ) ，其中v 、e 分别为节点和边的集合。在机械系统中， 用理想铰链代表每一个节点v v 。铰链的位置就是布局所对应节点的位置。用 弹簧( 类型i ) 代表每一条边e e ，每个弹簧都相同，即具有相等的自然的、 无张力的弹簧长度，其目的在于当弹簧的长度大于自然长度时弹簧将对铰链产生 一个吸引力，当弹簧的长度小于自然长度时弹簧将对铰链产生一个排斥力。也就 是说，弹簧的力的大小与弹簧的长度成反比，当弹簧的长度等于零时，弹簧将产 生任何作用力。 为了提高最终布局效果，对于弹簧的作用力的公式是可以选择的。大部分都 是选择经典的线性弹簧定律( h o o k el a w ) 作为弹簧力的计算公式。e a d e s 提出用对 数定律( l o g a r i t h m i cl a w ) 取代线性定律l l o l 。为了减少计算工作量也可以采用有理 多项式定律【2 5 j ( r a t i o n a lp o l y n o m i a ll a w ) 。 ( j ) = 乞( r ( 2 1 ) 其中，s 是弹簧的实际长度，l 是无张力时的弹簧长度，坟s ) 是当弹簧长度为 s 时的力的大小计算公式，k 是一个常数。 所有节点( 包括没有直接相连通的节点) 间还存在一个斥力，在机械系统中 1 0 式项 性 数 多 靴 撇 够 确 d 小叫m ，二， l ， 拍 几 第二章图布局算法的研究现状 作为一个隐形弹簧( 类型i i ) 来实现，通常采用以下公式来计算： 邝m 2 ( 2 2 ) k a m a d a 使用类型i 的长度来决定斥力，他将弹簧的自然长度l 设为相斥节 点间的最短图理论路径长度。图2 - 2 给出三个节点的受力情况和受力后的移动轨 迹。 弱弹簧( 类型i i ) 斥力 f ( b ) x 强弹簧蔷型。力 初始位置 最终位置 ( a )( b ) 图2 2 三个节点受力情况和受弱弹簧斥力后的移动轨迹 f i g u r e2 - 2 f o r c e sa n dm o v et r a c k si na3 - v e r t e xc h a i n 当固定一个节点后，图2 2 ( a ) 显示了其余两个节点的受力情况，在受弱弹簧 ( 类型i i ) 斥力影响后，图2 - 2 ( b ) 画出了节点的移动轨迹。 2 3 无向图通用布局算法 武汉大学的黄竞伟等学者提出了几种布局算法i 卿7 1 。算法设计思想是将一般 无向图的画图问题转化为函数优化问题，然后用遗传算法求目标函数的最优解的 近似值，从而得到无向图自动画图算法的一个一般框架。 该方法对于不同的无向图，布局算法的框架都一样，所不同的只是反映无向 图作图问题的美观标准的目标( 适应度) 函数，其优点：布局算法统一、方法简 单且容易实现、便于修改，并且易于并行化，甚至可以直接用来画非连通图。 遗传算法是根据生物进化思想而启发得出的一种全局优化算法。遗传算法本 质上是一种不依赖具体问题的直接搜索方法【2 s 】，它把问题的解表示成“染色体”， 在执行遗传算法之前先给出一群“染色体”，称为假设解。然后把这些假设解放入 相关问题的“环境”中，按自然界适者生存的原则，从中选择适应环境的“染色体” 进行复制，再通过交叉、变异过程产生更适应环境的新一代“染色体”群。这样经 过一代又一代地进化，最后会收敛到最适应环境的一个“染色体”上，从而求得问 广东工业大学r 学硕士学位论文 题的解。 图2 3 显示了遗传算法的执行过程。 l 变异为9 图2 - 3 遗传算法原理 淘汰4 ，5 提高1 ，2 2 3 交叉 产生6 7 f i g u r e2 - 3t h ep r i n c i p l eo f g e n e t i ca l g o r i t h m 标准遗传算法的基本流程如图2 - 4 所示。 图2 4 遗传算法基本流程图 f i g u r e2 - 4b a s ef l o wc h a r to f g e n e t i ca l g o r i t h m 1 2 第二章图布局算法的研究现状 遗传算法应用非常广泛，在模式识别、神经网络、图像处理、机器学习、工 业优化控制、自适应控制、生物科学、社会科学等方面都可以应用。接下来本文 将详细描述无向图通用布局算法的过程，其中大部分过程是本文提出的协同进化 遗传布局算法需要使用到的。 2 3 1 目标函数的选择 弹簧建模最早就1 9 8 4 年由e a d e s 提出【1 0 l ，k a m a d a 在1 9 8 9 年提出的一种改 进的弹簧建模1 2 钔。他使用相同自然长度的弹簧取代图的边，还使用更大自然长度 的的弹簧连接非连通的节点。算法开始前所有节点随机分布，当弹簧被拉伸时， 弹簧对终点有一个拉力，相反，当弹簧被挤压时，弹簧对终点有一个斥力。有边 相邻的节点被短的弹簧拉到一起，而长的弹簧则将不相邻的节点分开，与此同时 也控制了布局图形的总大小。当弹簧的总能量最小时，系统达到平衡状态。 一般无向图的通用布局算法采用文献 2 4 1 q b 的最小能量计算公式作为遗传 算法的目标函数。一般而言，一个无向图可表示为g = ( v e ) ，其中v 、e 分别为 节点和边的集合。设顶点个数为i l ，令p i ，p 2 ，p l l 表示节点v l ，v 2 ，v n v 在可视 空间上的映像。则式( 2 3 ) 为系统所有边( 弹簧) 的能量总和计算公式。 e = 善娄。吉乃( 1 只一乃l 一? ：f ，) ( 2 3 ) 其中，p i 代表第i 个节点v i ( i = l ，2 ，n ) ，l o 表示v i 和v j 问弹簧的自然长度， 表示v i 和v j 间的弹簧强度。 用氐代表v i 和v j 问的最短路径长度，则可以用式( 2 4 ) 计算1 0 和b ： 2 ：i ! ，= lx4 ， ( 2 4 ) 其中，l 为期望的单边长度，当可视空间固定时l 可以用式( 2 5 ) 计算得到： k l o m a x t , j ( 2 5 ) 其中，l o 表示图的可视空间( 通常定为一立方体) 的边长。 毛= k ( 2 6 ) 其中，k 为常数。 由于无向图的边没有方向性，所以当i 不等于j 时，从节点v i 到v j 的最短路 径长度等于从节点v j 到节点v i 的最短路径长度，即d i j = d j i ( 当i j 时) ，从而有l i j = l j i 、 k i j = k j i ( 当i ：j 时) 。 1 3 广东工业大学工学硕十学位论文 将节点的三维坐标代入式( 2 3 ) 得到遗传算法的目标函数： 2 3 2 编码设计 - - 芝窆吾气 ( # 一巧) 2 + ( 露一巧2 ，2 + 、，2 一弓) 2 + 巧 。5 1 _ ，蚺1 二 、 ( 2 7 ) 标准遗传算法采用的是二进制编码方案，因为它符合d e j o n g 的编码原理。 即将目标函数的解设计成长度为l 的二进制串b i ( i = l ，2 ，n ) ，这一过程称为编码。 n 个二进制串组成了遗传算法初始解群，即所谓的“染色体”，在每个染色体串中， 每个二进制位代表个体染色体的基因。在经过一系列进化过程后，找到最优“染 色体”，再将最优“染色体”解码，还原成目标函数的解。 二进制编码容易引起精度和效率的冲突。为了得到高精度最优解，个体的二 进制编码串就要保持相当的长度，从而造成计算量的迅速增加。为了避免高精度 的解码计算，减少算法执行时间，通常采用实数( 十进制) 编码方案，这种编码 方案比较直观。 根据目标函数式( 2 7 ) 的每个可能的解( x l ，y l ，z 1 ) 、( x 2 ，y 2 ，z 2 ) 、( ) ( i l ，y n ，z 1 1 ) ，通 常用一个长度为3 n 的实数串( x i ，y l ，z i ，x 2 ，y 2 ，z 2 ，, o dg x n ，y 。，z 1 1 ) 作为目标函数解的编码。 这样，一旦经过遗传算法搜索到了目标函数的全局最优解，就可以直接通过实数 串得到每个节点的三维坐标，省去了解码过程。 2 3 3 适应度函数的选择 适应度函数也称为对象函数，这是问题求解品质的测量函数，通常也称为问 题的“环境”。一般来说，优良的个体具有较高的适应度，劣等的个体具有较小的 适应度。因此适应度函数的设计好坏直接影响到遗传算法的性能高低。 在布局算法中，要得到公式( 2 7 ) 的全局最小值，根据适应度函数的要求，适 应度值高的为优良个体，因此需要对公式( 2 7 ) 进行变换，适应度函数如下： n 、 ，【，y l ，z 1 ，吒，儿，z nj = fc 。- f ( x , ，y l ，z l ，只，乙) ，缈( 五，y l ，z i ，毛，以，乙) c m 。 1 4 第二章图布局算法的研究现状 其中，c n 戳为一个适当相对较大的常数。 2 3 4 遗传算子的设定 遗传算子的设定包括选择算子、交叉算子、变异算子的设定。 1 选择算子 选择算子的作用是判断个体优良与否，标准就是个体各自的适应值的大小。 个体适应值越大，其被选中的机会就越大。个体适应值越小，其被选中的机会就 越小。 在布局算法中采用基于适应值比例的选择算子。为了防止“早熟”发生，可以 用s i g m a 比例变换技术对个体的适应值进行变换，即对个体i 的适应值f 【i ) 首先用 式( 2 9 ) 将f 【i ) 变换到e x p v a l ( i ) ： e x p v a l ( 沪o 卜八。