基于遺傳算法的有向無環(huán)圖研究.pdf

1、有向圖是研究可視化軟件和信息工程問題的基本模型。由于圖容易讓人明白和記憶,因此人們對于有向圖算法有著相當大的興趣。近年來,畫圖受到了越來越多的關注,對畫圖算法的研究已經(jīng)成為計算機科學領域中的一個新的研究方向。有向圖畫圖算法是畫圖領域的一個重要研究課題。目前,Sugiyama啟發(fā)式方法及其相應變種是畫有向圖的主要方法。Sugiyama啟發(fā)式方法通常把畫圖問題分成三個子問題：分層、每層頂點之間的排序以及調(diào)整。因為遺傳算法在組合優(yōu)化問題(搜索

2、范圍比較大)中能夠取得相當好的全局優(yōu)化結(jié)果,所以可以將遺傳算法用于畫圖問題中。事實上,畫圖問題就是一個優(yōu)化的過程。本文提出了一個基于遺傳算法的有向無環(huán)圖畫圖算法。主要內(nèi)容如下： 1.介紹了研究畫圖的意義以及畫圖問題的研究現(xiàn)狀。 2.介紹了圖的基本概念,圖的表示；然后介紹了圖的評判標準以及目前現(xiàn)有的畫圖算法方法；最后介紹了遺傳算法的基本流程。 3.介紹了基于啟發(fā)式的有向圖畫圖算法。算法主要包括三個步驟：刪除環(huán)、分層