《基于遗传算法的无向图画图算法》由会员分享，可在线阅读，更多相关《基于遗传算法的无向图画图算法（5页珍藏版）》请在金锄头文库上搜索。
1、数 学 杂 志增刊 J. o f M a th. (PR C )基于遗传算法的无向图画图算法黄竞伟康立山(武汉大学软件工程国家重点实验室, 武汉430072)摘要 在本文中, 我们应用遗传算法求解一般无向图画图问题, 相对已有的算法而言, 所设计 的新算法简单, 稳定性好, 易于实现, 可以不用变换将图画到任何一个指定的有限区域中, 而且可 以直接画出非连通图 1 关键词 图 画图 遗传算法 M R (1991) 主题类 68Q20 中图法分类号 TP30116引言图是一种应用非常广泛的数据结构, 近年来画图 (G rap h D raw in g ) 受到了越来越多的关 注1 、2 、31
2、文献4是一篇很好的有关画图的综述性文章 1 画图在电路布线、 网络管理、 软件工程、 图形学等领域中有着众多的应用 1K am ada 和 K aw a i 在文2中给出了一个画一般 连通无向图的算法, 他们将一个连通图图看作是一个顶点为钢环, 边为弹簧的动态系统, 而画 图过程则是一个逐步减少整个系统总能量的过程 1 他们用下列函数描述总能量:1nn E = K i j ( P i - P j - 1ij ) 2(1)i= 1 j = j + 1 其中 P i 是顶点V i 在平面上的相应点, K ij 为连接 P i 与 P j 之间的弹簧系数, li j 为平面点 P i 与P j 之间
3、的理想弹簧长度, 算法的最终目的是要找到 (P 1 , P 2 , P n ) 使 ( 1) 式达到最小, 这需要求解一个具有 2n 个变量的非线性方程组, 但该方程组的解很难求出, 故一般只能求出 (1) 式局部最小值点的近似解 1 在本文中, 我们利用遗传算法求带约束条件 a x , y b 的(1) 式的全局 最小值点的近似值, 其优点在于方法简单, 易于实现, 稳定性好, 可以不用变换将一个连通图画到任何一个指定的有限区域中, 这样可以通过将连通分支分别画到不同的区域中, 而得到非连 通图的一种画法 1画图问题一个图 G = (V , E ) 是一个顶点与边的集合对, 其中 V 为顶点
4、的集合, E 为边的集合, 为直 观起见, 通常我们用平面上的点表示顶点, 用平面上的直线或曲线表示连接顶点之间的边 1 在2 收稿日期: 19972012291 国家自然科学基金与高等学校博士学科点专项科研基金资助项目 1增刊黄竞伟等 基于遗传算法的无向图画图算法69某些画图算法中, 顶点的位置是受限的, 例如要求顶点的位置处于网格点上5 , 同心圆上6 , 或平行线上7 , 边可以画作直线, 折线或曲线 1 本文中, 我们假定顶点的位置在某个有限区域 中, 且顶点坐标为整数, 而边画作直线, 这样画图算法的目的是在一定的美学条件下, 将图画到 某个有限区域中 (譬如显视屏上) , 而算法的
5、中心思想是对图中的每一个顶点 v 指定一对坐标 (x v , y v ) , 一旦每个顶点都被指定一对坐标后, 则将图画出来就是一件很容易的事情了, 这只需 在有边相连的顶点之间画出一条直线即可 1 对于不同类型的图, 有不同的美学标准, 但对于画 一般的无向图, 通常有以下美学准则:11 尽可能将顶点均匀地分布在有限区域中;21 尽可能避免边的交叉;31 尽可能使边长一致;41 反映图的内在对称性; 在我们的算法中, 只有准则 3 得到了明显的体现, 但算法的结果也基本满足准则 1、41画图问题的遗传算法 由上面的讨论知, 画图算法的中心任务是求出 P 1 , P 2 ,3, P n 使(1
6、) 式最小 1设(x 1 , y 1 ) , (x 2 , y 2 ) , (x n , y n ) , 为点 P 1 , P 2 , P n 的平面坐标, 则(1) 式可以表示为nn E = K i j ( (x i - x j ) 2 + (y i - y j ) 2 +(x i - x j ) 2 + (y i -y j ) 2 )(2)li j - 2 li ji= 1 j = i+ 1 我们希望将图画到有限区域 a x , y b 中, 因而我们的目的是求带约束条件的目标函数nn E = K ij ( (x i - x j ) 2 + (y i - y j ) 2 +li j - 2
7、 l ij (x i - x j ) 2 + (y i - y j ) 2(3) i= 1 j = i+ 1 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 编码;
8、21 设计适应度函数;31 制定选择策略;41 选择控制参数;51 设计遗传算子;61 给出终止准则 1下面分别对上述 6 个步骤进行讨论 111 编码对 ( 3) 式每个可能的解 (x 1 , y 1 , x 2 , y 2 , x n , y n ) , 我们首先分别对 x i , y i 按串长 L 进行G ray 编码, 然后将 x i , y i 的 G ray 编码按照 x 1 y 1 x 2 y 2 , x n y n 的次序联接起来形成可能的解, x n , y n ) 的二进制编码, 从 (x 1 , y 1 , x 2 , y 2 , x n , y n ) 的二进制编码到
9、有限区域( x 1 , y 1 , x 2 , y 2 ,70数学杂志V o l . 18中的可能解 (x 1 , y 1 , x 2 , y 2 , 设(x i ) G ray = (x i1 x i2 , x n , y n ) 的转换如下进行:, x iL ) 为 x i 的 G ray 编码, 我们首先利用公式j bj = (x im ) m o d 2, 1 j Lm = 1 得到整数 x i 的二进制编码(b1 b2 , bL ) , 再利用公式L x i = a + (b - a ) bm 2L - m /(2L - 1)m = 1 得到 a x i b1 同样可以得到 a y
10、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 , 31 选择策略, x n , y n ) = Cm ax - E (x 1 , y 1 , x 2 , y 2 , x n , y n ) ,为了防止早熟发生, 我们首先用 S igm a 比例变换技术对个体的适应值进行变换, 即对个 体 i 的适应值 f ( i) , 首先用
11、公式若 ( t) 0, 若 ( t) = 01 + (f1( i) -f ( t) ) /2 ( t) ,E xpV a l ( i) =将 f ( i) 变换到 E xpV a l ( i) , 其中 f ( t) 为第 t 代群体平均适应值, 而 ( t) 表示第 t 代群体适应值 的标准方差 1 然后对 E xpV a l ( i) 用基于适应值比例的选择策略, 但保留适应值最高的染色体 141 控制参数在我们的算法中, 我们取N = 20, P c = 0. 9, P m = 0. 01151 遗传算子设计在算法中, 我们采用单点杂交与均匀变异算子 161 采用算法运行若干代后终止算法
12、 1基于遗传算法的无向图的画图算法描述如下: P ro cedu re GA G rap h D raw in g;B eg int: = 0;in it ia lize (P ( t) ) : E va lu a te (P ( t) ) ;W h ile no t sa t isfy te rm in a t io n co n d it io n D oB eg inP 1: = Se lec t (P ( t) ) ; P 2: = C ro sso ve r (P 1) ;P ( t+ 1) : = M u ta te (P 2) ; E va lu a te (P ( t+ 1)
13、) ;t: = t+ 1; E n d;L e t (x 1 , y 1 ) , (x 2 , y 2 ) ,pop u la t io n;, (x n , y n ) b e th e po in t s w ith th e m ax im um f itn e ss am o n g th eD raw G rap h (G , X , Y ) ;E n d;增刊黄竞伟等 基于遗传算法的无向图画图算法71其中过程D raw G rap h (G , X , Y ) 画出顶点的 x 坐标为 X = (x 1 , x 2 , x n ) , 顶点的 y 坐标为, y n ) 的图 G 1Y
14、 = (y 1 , y 2 ,实验结果 对于上述算法, 我们已在 486 微机上用 T u rbo P a sca l 编程实现, 得到了与2果, 下面是我们的算法所画出的若干图例 14 类似的结图 1图 2图 3图 4结束语在本文中, 我们用遗传算法求解画图问题, 对一些简单图的画法, 我们得到了与文2 类似 的结果 1 但对于一些较复杂的图而言, 由于文2 中的算法对于图的某些初始状态易于陷入局 部最小值的近似值, 因而导至较差的画法 1 而我们的算法的稳定性较好, 实验表明, 画法的最 终结果不依赖于图的初始状态 1 我们的算法不仅可以用来画连通图, 也可以用来画非连通图,这只需要将不同
15、的连通分支画到不同的区域中即可 1 本文所研究的是静态图无向的画图算 法, 如何将遗传算法应用到动态无向图的画图算法上, 这需要我们进一步的研究 1572数学杂志V o l . 18Ref eren ce s1B eck e r, B. . H o tz, G. . O n th e op t i m a l layo u t o f p lana r g rap h s w ith f ixed bo unda ry. S I AM J. Com p u t. 1987, 16(5) 946 9721Kam ada, T. . Kaw a i . S. . A n A lgo r ithm Fo r D raw ing Gene ra l U nd irec ted G rap h. Info rm a t io n21989, 31(1) 7 151P ro ce ssing L e t te r s .F ruch te rm an. T. M . J. . R e ingo ld. E. M. . G rap h D raw ing by Fo rce2d irec ted P lacem ent. So f tw a re2P
