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

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

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