基于遗传算法的无向图画图算法

V o l. 18 (1998) 增刊 　 数 学 杂 志 J. of M ath. (PRC) 基于遗传算法的无向图画图算法Ξ 黄竞伟　　　　康立山 (武汉大学软件工程国家重点实验室, 武汉　430072) 摘要　在本文中, 我们应用遗传算法求解一般无向图画图问题, 相对已有的算法而言, 所设计 的新算法简单, 稳定性好, 易于实现, 可以不用变换将图画到任何一个指定的有限区域中, 而且可 以直接画出非连通图 1 关键词　图　画图　遗传算法 M R (1991)主题类　68Q20 中图法分类号　TP30116 1　引言 图是一种应用非常广泛的数据结构, 近年来画图 (Graph D raw ing) 受到了越来越多的关 注[ 1 ]、[ 2 ]、[ 3 ]1 文献[ 4 ]是一篇很好的有关画图的综述性文章 1 画图在电路布线、网络管理、 软件工程、图形学等领域中有着众多的应用 1Kam ada 和 Kaw ai 在文[ 2 ]中给出了一个画一般 连通无向图的算法, 他们将一个连通图图看作是一个顶点为钢环, 边为弹簧的动态系统, 而画 图过程则是一个逐步减少整个系统总能量的过程 1 他们用下列函数描述总能量: E = ∑ n i= 1 ∑ n j = j+ 1 K ij (ûP i - P j û - 1ij ) 2 (1) 其中 P i 是顶点V i 在平面上的相应点, K ij为连接 P i 与 P j 之间的弹簧系数, l ij为平面点 P i 与 P j 之间的理想弹簧长度, 算法的最终目的是要找到 (P 1, P 2, ⋯, P n) 使 (1) 式达到最小, 这需要 求解一个具有 2n 个变量的非线性方程组, 但该方程组的解很难求出, 故一般只能求出 (1)式局 部最小值点的近似解 1 在本文中, 我们利用遗传算法求带约束条件a≤x , y≤b 的 (1)式的全局 最小值点的近似值, 其优点在于方法简单, 易于实现, 稳定性好, 可以不用变换将一个连通图画 到任何一个指定的有限区域中, 这样可以通过将连通分支分别画到不同的区域中, 而得到非连 通图的一种画法 1 2　画图问题 一个图G = (V , E ) 是一个顶点与边的集合对, 其中V 为顶点的集合, E 为边的集合, 为直 观起见, 通常我们用平面上的点表示顶点, 用平面上的直线或曲线表示连接顶点之间的边 1 在Ξ 收稿日期: 19972012291 国家自然科学基金与高等学校博士学科点专项科研基金资助项目 1 某些画图算法中, 顶点的位置是受限的, 例如要求顶点的位置处于网格点上[ 5 ], 同心圆上[ 6 ], 或平行线上[ 7 ], 边可以画作直线, 折线或曲线 1 本文中, 我们假定顶点的位置在某个有限区域 中, 且顶点坐标为整数, 而边画作直线, 这样画图算法的目的是在一定的美学条件下, 将图画到 某个有限区域中 (譬如显视屏上) , 而算法的中心思想是对图中的每一个顶点 v 指定一对坐标 (x v , y v ) , 一旦每个顶点都被指定一对坐标后, 则将图画出来就是一件很容易的事情了, 这只需 在有边相连的顶点之间画出一条直线即可 1 对于不同类型的图, 有不同的美学 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 , 但对于画 一般的无向图, 通常有以下美学准则: 11 尽可能将顶点均匀地分布在有限区域中; 21 尽可能避免边的交叉; 31 尽可能使边长一致; 41 反映图的内在对称性; 在我们的算法中, 只有准则 3 得到了明显的体现, 但算法的结果也基本满足准则 1、41 3　画图问题的遗传算法 由上面的讨论知, 画图算法的中心任务是求出 P 1, P 2, ⋯, P n 使 (1)式最小 1 设 (x 1, y 1) , (x 2, y 2) , ⋯, (x n , y n) , 为点 P 1, P 2, ⋯, P n 的平面坐标, 则 (1)式可以表示为 E = ∑ n i= 1 ∑ n j= i+ 1 K ij ( (x i - x j ) 2 + (y i - y j ) 2 + l ij - 2l ij (x i - x j ) 2 + (y i - y j ) 2 ) (2) 　　我们希望将图画到有限区域 a≤x , y≤b 中, 因而我们的目的是求带约束条件的目标函数 E = ∑ n i= 1 ∑ n j = i+ 1 K ij ( (x i - x j ) 2 + (y i - y j ) 2 + l ij - 2l ij (x i - x j ) 2 + (y i - y j ) 2 (3) a ≤ x i, y i ≤ b, i = 1, 2, ⋯, n 的最小值点 1 用遗传算法求解 (3) 的思想是: 首先用称之为染色体的一种简单数据结构对 (3) 式可能的 解 (x 1, y 1) , (x 2, y 2) , ⋯, (x n , y n)进行编码, 然后将一组遗传算子作用于一个解的群体, 即染色 体的群体上, 使得染色的群体能够保持一些关键信息, 通过不断演化, 最后得到 (3)式的最小值 点或近似最小值点 1 设计一个遗传算法的基本步骤由下列 6 部分组成: 11 编码; 21 设计适应度函数; 31 制定选择策略; 41 选择控制参数; 51 设计遗传算子; 61 给出终止准则 1 下面分别对上述 6 个步骤进行讨论 1 11 编码 对 (3) 式每个可能的解 (x 1, y 1, x 2, y 2, ⋯, x n , y n ) , 我们首先分别对 x i, y i 按串长 L 进行 Gray 编码, 然后将 x i, y i 的 Gray 编码按照 x 1y 1x 2y 2⋯, x ny n 的次序联接起来形成可能的解 (x 1, y 1, x 2, y 2, ⋯, x n , y n) 的二进制编码, 从 (x 1, y 1, x 2, y 2, ⋯, x n , y n ) 的二进制编码到有限区域 96增刊 黄竞伟等　基于遗传算法的无向图画图算法 中的可能解 (x 1, y 1, x 2, y 2, ⋯, x n , y n)的转换如下进行: 设 (x i) Gray= (x i1x i2, ⋯, x iL )为 x i 的 Gray 编码, 我们首先利用公式 bj = (∑ j m = 1 x im ) mod 2, 1 ≤ j ≤L 得到整数 x i 的二进制编码 (b1b2, ⋯, bL ) , 再利用公式 x i = a + (b - a)∑ L m = 1 bm 2L - m ö(2L - 1) 得到 a≤x i≤b1 同样可以得到 a≤y i≤b. 21 设计适应度函数 因为本问题是求最小值点, 故我们可以选择一个常数Cm ax≥E (x 1, y 1, x 2, y 2, ⋯, x n , y n) 直 接从 E (x 1, y 1, x 2, y 2, ⋯, x n , y n)设计适应度函数 f (x 1, y 1, x 2, y 2, ⋯, x n , y n) = Cm ax - E (x 1, y 1, x 2, y 2, ⋯, x n , y n) , 　　31 选择策略 为了防止早熟发生, 我们首先用 Sigm a 比例变换技术对个体的适应值进行变换, 即对个 体 i 的适应值 f ( i) , 首先用公式 ExpV al ( i) = 1 + (f ( i) - f ( t) ) ö2Ρ( t) , 若 Ρ( t) > 0 1 , 若 Ρ( t) = 0 将 f ( i)变换到 ExpV al ( i) , 其中 f ( t)为第 t 代群体平均适应值, 而 Ρ( t) 表示第 t 代群体适应值 的标准方差 1 然后对 ExpV al ( i)用基于适应值比例的选择策略, 但保留适应值最高的染色体 1 41 控制参数 在我们的算法中, 我们取N = 20, P c= 0. 9, P m = 0. 011 51 遗传算子设计 在算法中, 我们采用单点杂交与均匀变异算子 1 61 采用算法运行若干代后终止算法 1 基于遗传算法的无向图的画图算法描述如下: P rocedu re GA Graph D raw ing; Begin t: = 0; in it ia lize (P ( t) ) : Evaluate (P ( t) ) ; W h ile no t sa t isfy term inat ion condit ion Do Begin P 1: = Select (P ( t) ) ; P 2: = C ro ssover (P 1) ; P ( t+ 1) : = M u tate (P 2) ; Evaluate (P ( t+ 1) ) ; t: = t+ 1; End; L et (x 1, y 1) , (x 2, y 2) , ⋯, (x n , y n) be the po in ts w ith the m ax im um fitness among the popu la t ion; D raw Graph (G , X , Y ) ; End; 07 数　　学　　杂　　志 V o l. 18 其中过程D raw Graph (G , X , Y ) 画出顶点的 x 坐标为X = (x 1, x 2, ⋯, x n) , 顶点的 y 坐标为 Y = (y 1, y 2, ⋯, y n)的图G1 4　实验结果 对于上述算法, 我们已在 486 微机上用 T u rbo Pascal 编程实现, 得到了与 [ 2 ]类似的结 果, 下面是我们的算法所画出的若干图例 1 图 1　　　　　　　　　　　　　　图 2 图 3　　　　　　　　　　　　　图 4 5　结束语 在本文中, 我们用遗传算法求解画图问题, 对一些简单图的画法, 我们得到了与文[ 2 ]类似 的结果 1 但对于一些较复杂的图而言, 由于文[ 2 ]中的算法对于图的某些初始状态易于陷入局 部最小值的近似值, 因而导至较差的画法 1 而我们的算法的稳定性较好, 实验表明, 画法的最 终结果不依赖于图的初始状态 1 我们的算法不仅可以用来画连通图, 也可以用来画非连通图, 这只需要将不同的连通分支画到不同的区域中即可 1 本文所研究的是静态图无向的画图算 法, 如何将遗传算法应用到动态无向图的画图算法上, 这需要我们进一步的研究 1 17增刊 黄竞伟等　基于遗传算法的无向图画图算法 References 1　Becker, B. . Ho tz, G. . O n the op tim al layou t of p lanar graph s w ith fixed boundary. S IAM J. Comput. 1987, 16 (5)∶946～ 9721 2　Kam ada, T. . Kaw ai. S. . A n A lgo rithm Fo r D raw ing General U ndirected Graph. Info rm ation P rocessing L etters. 1989, 31 (1)∶7～ 151 3　F ruch term an. T. M. J. . R eingo ld. E. M. . Graph D raw ing by Fo rce2directed P lacem ent. Softw are2 P ractice and Experience. 1991, 21 (11)∶1129～ 11641 4　T am assia, R. . Batt ista, G. D. . Batin i, C. . A utom atic graph draw ing and readab ility of diagram s. IEEE T rans. Syst. M an Cybern. 1988, 18 (1)∶61～ 791 5　Batin i, C. . N ardelli, E. . and T am assia, R. . A L ayout A lgo rithm Fo r D ata F low D iagram s, IEEE T rans. Softw are Eng. 1986, SE- 12 (4)∶538～ 5461 6　Carpano, M. . A utom atic D isp lay of H ierarch ized Graph fo r Computer2A ided D ecision A nalysis. IEEE T rans. Syst. M an Cybern. 1980, SM C- 10 (11)∶705～ 7151 7　Row e, L. A. . D ivis, M. . M essinger, E. . M eyer, C. . Sp irak is, C. . T uan, A. . A B row ser fo r D irected Graph s. Softw are P ract. Exper. . 1987, 17 (1)∶61～ 671 A GRAPH D RAW ING AL GOR ITHM BASED ON GENETIC AL GOR ITHM S FOR GENERAL UND IRECTED GRAPH H uang J ingw ei(黄竞伟)　　Kang L ishan (康立山) (S ta te K ey L ab. of S of tw a re E ng ineering ,W uhan U n iversity , W uhan　430072) Abstract In th is paper, w e so lve general undirected graph draw ing p rob lem by genetic algo rithm s. Comparing to the p rio r algo rithm , the designed new algo rithm is mo re simp le, stab le and can be easily imp lem ented. T he algo rithm can draw a graph w ith in any designated area w ithou t any transfo rm ation and can draw non2connected graph s directly. Keywords　graph　graph draw ing　genetic algo rithm M R 1991 Subjcet Classif ica tion　68Q20 27 数　　学　　杂　　志 V o l. 18