摘要：近年來，對信息技術(shù)可視化的研究越來越廣泛，信息技術(shù)可視化也在各個(gè)領(lǐng)域中得到越來越廣泛的應(yīng)用。圖布局是用圖結(jié)構(gòu)解決現(xiàn)實(shí)世界中信息可視化問題的一種重要技術(shù)。該文介紹圖布局FR算法的基本模型，研究FR算法實(shí)現(xiàn)方法，及FR算法的優(yōu)化。

關(guān)鍵詞：圖布局；FR算法

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2013）12-2864-02

1 概述

近年來對信息技術(shù)可視化的研究越來越廣泛，信息技術(shù)可視化也在各個(gè)領(lǐng)域中得到越來越廣泛的應(yīng)用。信息可視化充分利用了人類視覺感知系統(tǒng)，將信息以圖形化方式進(jìn)行展示，直觀快速地解釋信息的意義。

繪圖技術(shù)是信息可視化與應(yīng)用數(shù)學(xué)的一個(gè)交叉領(lǐng)域，主要研究從圖到幾何空間的映射關(guān)系。 繪圖技術(shù)的內(nèi)容極其豐富，主要是根據(jù)不同的實(shí)際應(yīng)用需求，滿足繪圖的基本要求。從圖布局的觀點(diǎn)來看，在圖的繪制中，主要解決的是圖中節(jié)點(diǎn)的布局問題。

2 FR算法的基本模型

1984年，Eades首次提出了用彈力模型實(shí)現(xiàn)圖布局算法。彈力模型即力學(xué)中常用的虎克定律：在彈性限度內(nèi)，物體的形變跟引起形變的外力成正比。Eades將圖中的邊看成力學(xué)中的彈簧，利用彈力關(guān)系決定圖點(diǎn)的布局。

彈簧模型提出后，許多學(xué)者在此基礎(chǔ)上進(jìn)行了深入的研究。最典型的算法有Fruchterman和Reingold提出的FR算法。

FR算法在經(jīng)典彈簧算法的基礎(chǔ)上進(jìn)行了改進(jìn)，引入了力導(dǎo)引模型。力導(dǎo)引模型建立在粒子物理理論的基礎(chǔ)上，將無向圖中的節(jié)點(diǎn)模擬成原子，通過模擬原子間的力場來計(jì)算節(jié)點(diǎn)間的位置關(guān)系。算法通過考慮原子間引力和斥力的互相作用，經(jīng)過不斷的迭代計(jì)算，系統(tǒng)最終進(jìn)入一種動態(tài)平衡狀態(tài)。

FR 算法也沒有太嚴(yán)格地遵照物理規(guī)則來進(jìn)行模擬，而是進(jìn)行了一些簡化。FR 算法在所有的實(shí)體之間計(jì)算排斥力，而吸引力只在相互連接的實(shí)體之間進(jìn)行計(jì)算。

FR 算法的每次迭代主要分為三個(gè)部分：首先是計(jì)算節(jié)點(diǎn)之間相互的排斥力，然后是計(jì)算圖中有邊連接的節(jié)點(diǎn)之間相互的吸引力，最后綜合吸引力和排斥力，并通過最大位移來限制移動的距離。

對于一個(gè)高度為H ，寬度為W 的顯示區(qū)域，其中任意節(jié)點(diǎn)v 有兩個(gè)布局參數(shù)（分量）：節(jié)點(diǎn)的位置pos和所受合力產(chǎn)生的位置偏移量disp。

FR的基本定義如下：

顯示區(qū)域：

[area=W×H]

其中：[W]和[H]是顯示區(qū)域的寬和高；

平衡距離：

FR 算法的偽代碼如下：

for （i = 1； i < 迭代次數(shù)；i++）

{

// 計(jì)算排斥力

// 計(jì)算吸引力

// 對點(diǎn)坐標(biāo)進(jìn)行置換，防止置換超出邊界

foreach（ v in V）

// 減少溫度，使布局更好

t = cool（t）

}

在FR 算法中：cool（t）為模擬退火函數(shù)。

3 應(yīng)用模擬退火算法進(jìn)行優(yōu)化

模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在各個(gè)溫度中都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。

在圖布局算法中，常采用模擬退火算法，在算法中給出“溫度”和“冷卻”的概念，用于限制節(jié)點(diǎn)的最大位移，并且最大位移隨著迭代次數(shù)的增大而減小。這是因?yàn)殡S著迭代次數(shù)的增大，圖形的布局效果越來越好，相應(yīng)需要的調(diào)整也更加細(xì)微?！皽囟取睉?yīng)該從一個(gè)初始值開始逐漸衰退到0。溫度控制節(jié)點(diǎn)的位置移動范圍，使得布局越來越好，調(diào)整越來越小。

模擬退火算法遵循Boltzmann函數(shù)：

其中：p（E）指出狀態(tài)E的能量值的概率分布，作為溫度T和Boltzmann常數(shù)k的函數(shù)。一方面，對每一個(gè)溫度，各個(gè)能量E有非零的概率，因此，系統(tǒng)能以較高的溫度改變它的狀態(tài)。另一方面，在降低溫度時(shí)，系統(tǒng)趨向于非常低的能量狀態(tài)，當(dāng)全局能量最小時(shí)，達(dá)到溫度零。

在本算法中，采用了線性算法。首先設(shè)置一個(gè)初始溫度，即節(jié)點(diǎn)允許的最大位移量。如果初始溫度足夠高，節(jié)點(diǎn)可以任意地移動。因此，將節(jié)點(diǎn)初始最大位移量設(shè)置為繪圖矩形區(qū)域長邊的1/2，其后是溫度減少的過程，典型的是一個(gè)多項(xiàng)式算法。

本文使用線性數(shù)，溫度下降過程的表達(dá)式為：，[γ]稱為冷卻系數(shù)，在0.6到0.95之間，一般使用用[γ=0.8]。

按照式上述公式，模擬退火算法的迭代次數(shù)由初始溫度、冷卻系數(shù)、迭代終止下界決定。初始溫度T0一般設(shè)置為顯示區(qū)域邊長的1/2，每次迭代后，溫度T的值乘以冷卻系數(shù)，因冷卻系數(shù)小于1，溫度T的值遞減，直至溫度Tn到達(dá)迭代終止下界。迭代終止下界是一個(gè)很小的值，即節(jié)點(diǎn)的最小位移量。

我們用FR算法對100個(gè)節(jié)點(diǎn)的圖進(jìn)行了布局計(jì)算。迭代300次后的執(zhí)行效果見圖（b）?？梢钥吹剑季中Ч⒉惶?。

模擬退火算法的迭代次數(shù)由初始溫度、冷卻系數(shù)和迭代終止下界決定。在計(jì)算中，初始溫度T0設(shè)置為顯示區(qū)域邊長的1/2，冷卻系數(shù)為0.9，迭代終止下界為1。因此迭代了315次。顯然比前面不用模擬退火算法循環(huán)300次的效果要好了許多。

由運(yùn)行測試與分析，模擬退火算法在FR算法中起著比較重要的作用，它能有效地防止節(jié)點(diǎn)位移的振蕩，因此，在按循環(huán)次數(shù)迭代時(shí)，也引入了模擬退火算法來限制節(jié)點(diǎn)位移的最大偏移量，按循環(huán)次數(shù)使節(jié)點(diǎn)位移最大偏移量遞減。

4 結(jié)束語

本文主要研究圖的布局算法與實(shí)現(xiàn)方法。闡述了FR算法的原理，給出了算法的偽代碼。并應(yīng)用模擬退火算法對FR算法進(jìn)行優(yōu)化，分析及其執(zhí)行效果，為后繼數(shù)據(jù)分析工作建立一個(gè)堅(jiān)實(shí)的基礎(chǔ)。