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

数 学 杂 志增刊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 文献4是一篇很好的有关画图的综述性文章 1 画图在电路布线、网络管理、软件工程、图形学等领域中有着众多的应用 1k am ada 和 k aw a i 在文2中给出了一个画一般 连通无向图的算法, 他们将一个连通图图看作是一个顶点为钢环, 边为弹簧的动态系统, 而画图过程则是一个逐步减少整个系统总能量的过程 1 他们用下列函数描述总能量:1nne = 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 之间的理想弹簧长度, 算法的最终目的是要找到 (p 1 , p 2 , p n ) 使 ( 1) 式达到最小, 这需要求解一个具有 2n 个变量的非线性方程组, 但该方程组的解很难求出, 故一般只能求出 (1) 式局部最小值点的近似解 1 在本文中, 我们利用遗传算法求带约束条件 a x , y b 的(1) 式的全局 最小值点的近似值, 其优点在于方法简单, 易于实现, 稳定性好, 可以不用变换将一个连通图画到任何一个指定的有限区域中, 这样可以通过将连通分支分别画到不同的区域中, 而得到非连 通图的一种画法 1画图问题一个图 g = (v , e ) 是一个顶点与边的集合对, 其中 v 为顶点的集合, e 为边的集合, 为直 观起见, 通常我们用平面上的点表示顶点, 用平面上的直线或曲线表示连接顶点之间的边 1 在2 收稿日期: 19972012291国家自然科学基金与高等学校博士学科点专项科研基金资助项目 1增刊黄竞伟等 基于遗传算法的无向图画图算法69某些画图算法中, 顶点的位置是受限的, 例如要求顶点的位置处于网格点上5 , 同心圆上6 ,或平行线上7 , 边可以画作直线, 折线或曲线 1 本文中, 我们假定顶点的位置在某个有限区域 中, 且顶点坐标为整数, 而边画作直线, 这样画图算法的目的是在一定的美学条件下, 将图画到 某个有限区域中 (譬如显视屏上) , 而算法的中心思想是对图中的每一个顶点 v 指定一对坐标 (x v , y v ) , 一旦每个顶点都被指定一对坐标后, 则将图画出来就是一件很容易的事情了, 这只需 在有边相连的顶点之间画出一条直线即可 1 对于不同类型的图, 有不同的美学标准, 但对于画 一般的无向图, 通常有以下美学准则:11 尽可能将顶点均匀地分布在有限区域中;21 尽可能避免边的交叉;31 尽可能使边长一致;41 反映图的内在对称性;在我们的算法中, 只有准则 3 得到了明显的体现, 但算法的结果也基本满足准则 1、41画图问题的遗传算法由上面的讨论知, 画图算法的中心任务是求出 p 1 , p 2 ,3, p n 使(1) 式最小 1设(x 1 , y 1 ) , (x 2 , y 2 ) , (x n , y n ) , 为点 p 1 , p 2 , p n 的平面坐标, 则(1) 式可以表示为nne = 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 中, 因而我们的目的是求带约束条件的目标函数nne = k ij ( (x i - x j ) 2 + (y i - y j ) 2 +li j - 2 l ij (x i - x j ) 2 + (y i - y j ) 2(3)i= 1 j = i+ 1a 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 个步骤进行讨论 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 ) 的二进制编码到有限区域( 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 编码, 我们首先利用公式jbj = (x im ) m o d 2, 1 j lm = 1得到整数 x i 的二进制编码(b1 b2 , bl ) , 再利用公式lx i = a + (b - a ) bm 2l - m /(2l - 1)m = 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 ,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) , 首先用公式若 ( 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 采用算法运行若干代后终止算法 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) ) ;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 umf 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 = (y 1 , y 2 ,实验结果对于上述算法, 我们已在 486 微机上用 t u rbo p a sca l 编程实现, 得到了与2果, 下面是我们的算法所画出的若干图例 14类似的结图 1图 2图 3图 4结束语在本文中, 我们用遗传算法求解画图问题, 对一些简单图的画法, 我们得到了与文2 类似 的结果 1 但对于一些较复杂的图而言, 由于文2 中的算法对于图的某些初始状态易于陷入局 部最小值的近似值, 因而导至较差的画法 1 而我们的算法的稳定性较好, 实验表明, 画法的最 终结果不依赖于图的初始状态 1 我们的算法不仅可以用来画连通图, 也可以用来画非连通图,这只需要将不同的连通分支画到不同的区域中即可 1 本文所研究的是静态图无向的画图算 法, 如何将遗传算法应用到动态无向图的画图算法上, 这需要我们进一步的研究 1572数学杂志v o l. 18ref eren ce s1b eck e r, b. . h o tz, g. . o n th e op t im a l layo u t o f p lana r g rap h s w ith f ixed bo unda ry. s iam 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 en t. so f tw a re2p rac t ice and e xp e r ience. 1991, 21 (11) 1129 11641t am a ssia, r. . b a t t ista, g. d. . b a t in i, c. . a u tom a t ic g rap h d raw ing and readab ility o f d iag ram s.341988, 18 (1) 61 791ie e e t ran s. sy st. m an c ybe rn.5b a t in i, c. . n a rde lli, e. . and t am a ssia, r. . a l ayo u t a lgo r ithm fo r d a ta f low d iag ram s, ie e e t ran s. so f tw a re e ng. 1986, se - 12 (4) 538 5461c a rp ano , m . . a u tom a t ic d isp lay o f h ie ra rch ized g rap h fo r com p u te r2a ided d ec isio n a na ly sis. ie e e t ran s. sy st. m an c ybe rn. 1980, sm c - 10 (11) 705 7151r ow e, l. a. . d iv is, m . . m e ssinge r, e. . m eye r, c. . sp irak is, c. . t uan, a. . a b row se r fo rd irec ted g rap h s. so f tw a re p rac t. e xp e r. . 1987, 17 (1) 61 67167a gra ph d raw ing al go r ithm ba sed o n genet ical go r ithm s fo r general und irected gra phh u an g j in gw e i (黄竞伟)k an g l ish an (康立山)(s