基于遺傳算法的有向無(wú)環(huán)圖畫圖算法

摘要：在研究了現(xiàn)有畫有向無(wú)環(huán)圖的主要方法的基礎(chǔ)上提出一種基于遺傳算法的有向無(wú)環(huán)圖畫圖算法，將一般有向無(wú)環(huán)圖的畫圖問(wèn)題轉(zhuǎn)換為函數(shù)優(yōu)化問(wèn)題， 用遺傳算法求目標(biāo)函數(shù)最優(yōu)解的近似值。實(shí)驗(yàn)表明此算法具有算法統(tǒng)一、方法簡(jiǎn)單、容易實(shí)現(xiàn)、易于修改，并且具有自適應(yīng)、自學(xué)習(xí)和易于并行化的特點(diǎn)。

關(guān)鍵詞：畫圖；邊交叉的縮減；遺傳算法；有向無(wú)環(huán)圖

中圖分類號(hào)：TP301．6文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2008)12-0063-03

0引言

圖是一種應(yīng)用十分廣泛的數(shù)據(jù)結(jié)構(gòu)，它可以被用來(lái)表示任何可以用對(duì)象以及對(duì)象之間的聯(lián)系表達(dá)的信息。計(jì)算機(jī)科學(xué)的每一個(gè)領(lǐng)域和軟件產(chǎn)業(yè)的每一個(gè)部門均在某種形式上用圖表示關(guān)系信息模型。通常表示復(fù)雜系統(tǒng)模型的圖的頂點(diǎn)數(shù)和邊數(shù)均相當(dāng)大， 以至于用人工方法將圖整齊、美觀地畫出來(lái)幾乎是不可能的。如何用計(jì)算機(jī)自動(dòng)地將圖整齊、美觀地畫出來(lái)便成為一個(gè)十分重要的課題。因此人們對(duì)于畫圖算法有著相當(dāng)大的興趣。

在對(duì)畫圖算法的研究中，對(duì)各種不同類型的圖有不同的畫圖算法，如畫樹^[1]、畫平面圖^[2]、畫有向圖^[3]、畫無(wú)向圖^[3]等。在各種畫圖算法中，有向無(wú)環(huán)圖占有非常重要的地位，它在很多領(lǐng)域有著廣泛的應(yīng)用，如數(shù)據(jù)庫(kù)建模、軟件工程設(shè)計(jì)等。將有向無(wú)環(huán)圖整齊、美觀地畫出來(lái)便成為了一個(gè)重要的研究課題。近年來(lái)，許多學(xué)者對(duì)有向無(wú)環(huán)圖自動(dòng)畫圖算法進(jìn)行了大量的研究^[4，5]。對(duì)于畫一般的有向無(wú)環(huán)圖， 根據(jù)應(yīng)用和觀點(diǎn)的不同 有不同的美觀準(zhǔn)則，但仍普遍接受以下美觀準(zhǔn)則：方向向上的邊應(yīng)該盡量避免；所有的點(diǎn)應(yīng)盡量均勻分布；跨度大的長(zhǎng)邊也應(yīng)盡量減少；整個(gè)圖中應(yīng)盡可能地減少邊的交叉數(shù)。在本文的算法中假設(shè)畫圖時(shí)大多數(shù)邊都指向一個(gè)指定的方向。

雖然已有許多快速畫出滿足上述美觀準(zhǔn)則的有向無(wú)環(huán)圖的算法，然而這些算法不具有重用性。針對(duì)一種應(yīng)用設(shè)計(jì)出來(lái)的畫圖算法一般不再適用于其他應(yīng)用，而且也難以在這些算法中添加新的美觀準(zhǔn)則，以適應(yīng)不同用戶的需要。本文將一般的有向無(wú)環(huán)圖的畫圖問(wèn)題看成是一個(gè)函數(shù)優(yōu)化問(wèn)題，然后用遺傳算法^[6]來(lái)求目標(biāo)函數(shù)最優(yōu)解的近似值，從而得到一種畫有向無(wú)環(huán)圖算法。該算法可以根據(jù)應(yīng)用的不同，通過(guò)設(shè)計(jì)不同的目標(biāo)函數(shù)來(lái)得到不同的畫圖算法，而且容易添加或減少美觀標(biāo)準(zhǔn)以適應(yīng)不同用戶的需要。

1算法描述

1．1算法思想框架

在本文中研究的有向圖都認(rèn)為是無(wú)環(huán)圖，因此在此不考慮刪除圖中環(huán)的問(wèn)題。本文中基于遺傳算法畫有向圖主要是研究邊交叉數(shù)最小化的問(wèn)題，并將減少邊交叉數(shù)作為主要標(biāo)準(zhǔn)進(jìn)行考慮。利用遺傳算法畫圖時(shí)可以將優(yōu)化圖的問(wèn)題轉(zhuǎn)換成函數(shù)優(yōu)化問(wèn)題。如何對(duì)圖進(jìn)行編碼表示、如何設(shè)計(jì)目標(biāo)函數(shù)，是利用遺傳算法畫有向圖的關(guān)鍵。具體操作如下：首先編碼和初始化種群；然后設(shè)計(jì)適應(yīng)度函數(shù)，確定選擇策略；接著設(shè)計(jì)雜交算子和變異算子，再給出控制參數(shù)；最后給出終止準(zhǔn)則。

上述算法已用Delphi語(yǔ)言編程實(shí)現(xiàn)。使用本文算法對(duì)頂點(diǎn)數(shù)為32、邊密度為10％的圖進(jìn)行實(shí)驗(yàn)，結(jié)果如圖2所示。本文所有實(shí)驗(yàn)數(shù)據(jù)運(yùn)行環(huán)境為Celeron 2.5 GHz CPU，512 MB內(nèi)存微型機(jī)。

在下面實(shí)驗(yàn)中，假定節(jié)點(diǎn)n＝15，20，25，30。對(duì)于每個(gè)n，在邊密度分別為2％、5％、10％時(shí)進(jìn)行了實(shí)驗(yàn)。分別使用遺傳算法與文獻(xiàn)[9]中的算法（在該算法中，采用文獻(xiàn)[7]中的刪環(huán)算法和文獻(xiàn)[8]中的分層算法進(jìn)行局部調(diào)整）產(chǎn)生10個(gè)有向無(wú)環(huán)圖，并進(jìn)行了相應(yīng)的比較，結(jié)果如表2所示。其中列在邊密度為2％、5％、10％下每一格中的數(shù)據(jù)，表示用該算法在對(duì)應(yīng)的邊密度情況時(shí)計(jì)算產(chǎn)生10個(gè)有向無(wú)環(huán)圖的邊交叉點(diǎn)平均數(shù)。

從表2中的數(shù)據(jù)可以看出，利用遺傳算法可以明顯減少交叉點(diǎn)數(shù)。盡管遺傳算法的計(jì)算結(jié)構(gòu)比較優(yōu)良，但在實(shí)驗(yàn)中發(fā)現(xiàn)，相同頂點(diǎn)、邊的密度不同對(duì)算法運(yùn)行效率有較大的影響。一般而言，邊的密度較大，則算法運(yùn)算時(shí)間較長(zhǎng)；而邊的密度較小時(shí)，算法效果較好，且運(yùn)算時(shí)間也較短。

3結(jié)束語(yǔ)本文將遺傳算法引入到畫圖問(wèn)題中，設(shè)計(jì)了一種基于遺傳算法畫有向無(wú)環(huán)圖的算法。實(shí)驗(yàn)結(jié)果表明，基于遺傳算法畫有向無(wú)環(huán)圖算法具有方法簡(jiǎn)單、易于實(shí)現(xiàn)、畫出的圖形美觀等優(yōu)點(diǎn)。如何在該算法的基礎(chǔ)上，考慮有環(huán)圖的畫圖算法是進(jìn)一步研究的方向。

參考文獻(xiàn)：

［1］CRESCENZI P，PENNA P.Minimumarea hv drawings of complete binary trees[C]//GED D.Proc of Graph Drawing’97. Berlin:SpringerVerlag，1998:371-382.

[2]KOSAK C，MARKS J，SHIEBER S.Automating the layout of network diagrams with specified visual organization[J].IEEE Trans on System， Man and Cybernetics，1994，24(3):440-454.

[3]BATTISTA G D，EADES P，TAMASSIA R.Algorithms for drawing graphs: an annotated bibliography[J].Computational Geometry: Theory and Applications，1994，4(5):235-282.

[4]JUNGER M，MUTZEL P，ODENTHAL T.A polyhedral approach to the multilayer crossing minimization problem[C]//Proc of the 5th International Symposium on Graph Drawings.Berlin:SpringerVerlag， 1997:13-24.

[5]EADES P，WHITESIDES S.Drawing graphs in two layers[J].Theoret Comput Sci，1994，131(2):361-374.

[6]MICHALEWICZ Z.Genetic algorithms+data structures=evolution programs[M].3rd ed. Berlin: SpringerVerlag，1996.

[7]BERGER B，SHOR P.Approximation algorithms for the maximum acyclic subgraph problem[C]//Proc of the 1st ACMSIAM Symposium on Discrete Algorithms.1990:236-243.

[8]MEHLHORN K.Data structures and algorithms volumes 2:graph algorithms and NPcompleteness[M].Heidelberg:Springer，1984.

[9]JUNGER J，MUTZEL P.2layer straightline crossing minimization:performance of exact and heuristic algorithms[C]//BRANDENBURG F J.Proc of the 3rd International Symposium on Graph Drawing. Berlin:SpringerVerlag，1995:337-348.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”