圖的度量維數(shù)問(wèn)題的0-1 蟻群條件著色分辨算法研究

武 建, 趙海霞

(1- 太原理工大學(xué)信息與計(jì)算機(jī)學(xué)院，太原 030600; 2- 山西財(cái)經(jīng)大學(xué)應(yīng)用數(shù)學(xué)學(xué)院，太原 030006;3- 山西財(cái)經(jīng)大學(xué)統(tǒng)計(jì)學(xué)院，太原 030006)

1 引言

設(shè)圖G = (V(G),E(G))是頂點(diǎn)集和邊集分別為V(G)和E(G)的簡(jiǎn)單連通圖.任意頂點(diǎn)u,v ∈V(G)的距離是指頂點(diǎn)u, v 之間最短u ?v 路徑的長(zhǎng)度，記作dG(u,v).任意兩個(gè)頂點(diǎn)u,v ∈V(G)構(gòu)成的頂點(diǎn)對(duì)記作p(uv = vu).若u 與v 相鄰，則uv ∈E(G).否則，uv /∈E(G).經(jīng)典圖著色理論的本質(zhì)是對(duì)頂點(diǎn)進(jìn)行分類，即用不同顏色組成的顏色集對(duì)頂點(diǎn)進(jìn)行分類.因而，將圖頂點(diǎn)分為兩類的一種途徑是：給定顏色集{0,1}(兩種不同顏色的標(biāo)號(hào))，為所有頂點(diǎn)分配顏色0 或顏色1.本文稱這樣的頂點(diǎn)著色為圖的一個(gè)0-1 著色.其他術(shù)語(yǔ)見(jiàn)文獻(xiàn)[1].

化合物分子分類問(wèn)題是化學(xué)領(lǐng)域的一個(gè)重要研究課題.化合物分子分類研究的一個(gè)基本問(wèn)題是如何表征每個(gè)化合物分子[2].圖是研究這一問(wèn)題的有力工具.每個(gè)化合物分子按照內(nèi)部化學(xué)結(jié)構(gòu)可以轉(zhuǎn)化為一個(gè)圖，簡(jiǎn)稱分子圖.根據(jù)化合物分子的性質(zhì)，通過(guò)建立適當(dāng)?shù)木嚯x度量，各個(gè)化合物分子之間的關(guān)系可以轉(zhuǎn)化為各個(gè)圖之間的關(guān)系.在選定的距離度量下，若兩個(gè)圖之間距離為1，則在兩個(gè)圖之間連接一條邊.按照這種連接關(guān)系，大型的化合物分子庫(kù)就構(gòu)成了一個(gè)以每個(gè)分子圖為頂點(diǎn)的大型復(fù)雜網(wǎng)絡(luò)，簡(jiǎn)稱分子網(wǎng)絡(luò).化合物分子分類研究的基本問(wèn)題就是表征分子網(wǎng)絡(luò)的每個(gè)頂點(diǎn).解決該類問(wèn)題的一種途徑是為分子網(wǎng)絡(luò)建立一個(gè)表征系統(tǒng).

假設(shè)化合物分子庫(kù)中有n 個(gè)化合物分子.其對(duì)應(yīng)的分子圖分別為G1,G2,··· ,Gn.選定距離度量dH，并建立分子網(wǎng)絡(luò)H.在分子網(wǎng)絡(luò)H 中，按照一定順序選擇k(< n)個(gè)分子圖構(gòu)成有序分子圖簇S = {Gi1,Gi2,··· ,Gik}, ik∈{1,2,··· ,n}.分子網(wǎng)絡(luò)的每個(gè)分子圖Gj(j ∈{1,2,··· ,n})依據(jù)其到有序分子圖簇S 中每個(gè)元素的距離度量dH，與一個(gè)k-維距離向量rdH(Gj|S)對(duì)應(yīng).即

rdH(Gj|S)=(dH(Gj,Gi1),dH(Gj,Gi2),··· ,dH(Gj,Gik)).

對(duì)于任意的分子圖Gl, Gm, l ?= m ∈{1,2,··· ,n}，若rdH(Gl|S) ?= rdH(Gm|S)成立，則每個(gè)分子圖與一個(gè)唯一的k-維距離向量對(duì)應(yīng).分子圖簇S 即可作為分子網(wǎng)絡(luò)的一個(gè)表征系統(tǒng).如何找到一個(gè)包含元素最少的表征系統(tǒng)即為圖的度量維數(shù)問(wèn)題.本文在一般簡(jiǎn)單連通圖上研究圖的度量維數(shù)問(wèn)題，即在一般圖上建立圖的最優(yōu)表征系統(tǒng).

圖的度量維數(shù)問(wèn)題是在機(jī)器導(dǎo)航、聲吶系統(tǒng)布置、化學(xué)等多個(gè)領(lǐng)域有著廣泛的應(yīng)用背景的組合優(yōu)化問(wèn)題[2-6]，也是關(guān)于圖的距離主題的研究熱點(diǎn)之一.特殊圖類上的度量維數(shù)研究見(jiàn)文獻(xiàn)[7-14].度量維數(shù)問(wèn)題在研究?jī)?nèi)容和研究方法上的拓展見(jiàn)文獻(xiàn)[15-23].圖的度量維數(shù)問(wèn)題的算法研究較少.為了解決該問(wèn)題，本文提出了反映圖的分辨特性的分辨表結(jié)構(gòu)，并導(dǎo)出了圖的頂點(diǎn)分辨域、分辨度概念(見(jiàn)第2.2 節(jié)).與圖的頂點(diǎn)鄰接關(guān)系相比較，實(shí)際復(fù)雜網(wǎng)絡(luò)的分辨表是易得的.因而，圖的分辨表是研究圖的分辨特性的有力工具.同時(shí)，本文在拓展經(jīng)典圖著色分類思想的基礎(chǔ)上，建立了圖的度量維數(shù)問(wèn)題的非線性計(jì)算模型(見(jiàn)第2.3 節(jié)).通過(guò)設(shè)計(jì)與問(wèn)題背景相一致的運(yùn)行參數(shù)(見(jiàn)第3.1 節(jié)至第3.6 節(jié))，建立了求解模型的0-1 蟻群條件著色分辨算法(見(jiàn)算法3.2).

本文通過(guò)數(shù)值對(duì)比分析驗(yàn)證算法的有效性：

1) 通過(guò)求解特殊圖類的度量維數(shù)，驗(yàn)證了本文提出的分辨域限制條件、修補(bǔ)技術(shù)、局部搜索對(duì)提高算法求解質(zhì)量有較大影響；

2) 通過(guò)與整數(shù)規(guī)劃算法計(jì)算結(jié)果的對(duì)比驗(yàn)證了本文算法具有較好的表現(xiàn)；

3) 在特殊圖類和隨機(jī)圖上的計(jì)算結(jié)果比較分析表明全局搜索和局部搜索的結(jié)合策略較大程度的改進(jìn)了算法求解質(zhì)量，但在規(guī)則圖上提高算法求解質(zhì)量具有一定挑戰(zhàn)；

4) 與遺傳算法[24]計(jì)算結(jié)果相比較，本文提出的算法不僅在求解質(zhì)量方面有所提升，而且在最壞的情況下能為圖提供極小分辨集；

5) 通過(guò)定義評(píng)價(jià)指標(biāo)，主要探索了螞蟻候選頂點(diǎn)集選取比例系數(shù)對(duì)算法求解質(zhì)量的影響，并給出了進(jìn)一步研究課題.一般蟻群算法及其參數(shù)分析見(jiàn)文獻(xiàn)[25-28].

2 圖的度量維數(shù)問(wèn)題及其0-1 著色分辨模型的建立

2.1 問(wèn)題描述

給定簡(jiǎn)單連通圖G=(V(G),E(G)).對(duì)任意頂點(diǎn)u, v, x ∈V(G)，若它們滿足則稱頂點(diǎn)x 可分辨頂點(diǎn)對(duì)u, v，或稱uv 是頂點(diǎn)x 的一個(gè)可分辨頂點(diǎn)對(duì)，記作x?uv.若任意頂點(diǎn)對(duì)u, v ∈V(G)可由有序頂點(diǎn)子集S ?V(G)中的至少一個(gè)頂點(diǎn)分辨，則稱S 是圖G 的一個(gè)分辨集.基數(shù)(所含頂點(diǎn)數(shù))最小的分辨集為圖的一個(gè)基，其對(duì)應(yīng)的基數(shù)為圖的度量維數(shù)，記作dim(G).確定任意連通圖的度量維數(shù)及其基的問(wèn)題就是所謂的圖的度量維數(shù)問(wèn)題.

dG(u,x)?=dG(v,x),

2.2 頂點(diǎn)的分辨域

假設(shè)圖G 的所有不同頂點(diǎn)對(duì)構(gòu)成的集合為PG，即

對(duì)于任意頂點(diǎn)x ∈V(G)，頂點(diǎn)x 的分辨域RN(x)為

頂點(diǎn)x 的分辨度RD(x)為

將所有頂點(diǎn)及其分辨域按行排列在一起構(gòu)成的表為圖的頂點(diǎn)分辨表RT(G)，見(jiàn)表1. 其中i ∈{1,2,··· ,n}, j ∈{1,2,··· ,mi}.

表1 分辨表RT, pij =uv ∈PG, mi =RD(vi)

本文提出了圖的分辨域概念，進(jìn)而建立了圖的一種新的存儲(chǔ)形式：分辨表.分辨表直接反映了圖的分辨特性.與圖的頂點(diǎn)鄰接關(guān)系相比較，實(shí)際復(fù)雜網(wǎng)絡(luò)的分辨表是易得的.因而，圖的分辨表是研究圖的分辨特性的有力工具.

2.3 度量維數(shù)問(wèn)題的0-1 著色分辨模型

給定顏色集{0,1}，與頂點(diǎn)集對(duì)應(yīng)的1×n 階著色分辨向量函數(shù)為

設(shè)

則圖度量維數(shù)問(wèn)題的0-1 著色分辨模型可描述為

0-1 著色分辨模型(4)從圖本身的分辨特性角度尋找圖的一個(gè)基，并計(jì)算圖的度量維數(shù).模型(4)是非線性的，反映了問(wèn)題的組合特性，拓展了經(jīng)典的頂點(diǎn)著色分類思想.與頂點(diǎn)集對(duì)應(yīng)的1×n 階著色分辨向量函數(shù)S 也是圖G 的一個(gè)解向量.即元素值為1 的對(duì)應(yīng)頂點(diǎn)構(gòu)成了圖G 的一個(gè)近似分辨集或基，元素值1 的個(gè)數(shù)為圖G 的近似度量維數(shù).

3 模型求解算法研究

算法1 0-1 隨機(jī)條件著色分辨算法

步驟0 算法初始化.建立圖G 的分辨表RT (表1)和頂點(diǎn)對(duì)集合PG(式(1)).初始化與頂點(diǎn)集對(duì)應(yīng)的著色分辨向量S =(0)1×n.著色為1 的頂點(diǎn)對(duì)應(yīng)的分辨域構(gòu)成的無(wú)重復(fù)元素集合R=φ.

步驟1 選取頂點(diǎn)v ∈V(G)，為頂點(diǎn)v 分配顏色1，即S(v) = 1.令R = RN(v)，若R=PG，算法終止運(yùn)行并輸出圖的度量維數(shù)1 及其對(duì)應(yīng)基.否則，轉(zhuǎn)到步驟2.

步驟2 選取頂點(diǎn)v ∈V，使得頂點(diǎn)v ∈V 滿足分辨域限制條件

同時(shí)，對(duì)滿足分辨域條件(5)的候選頂點(diǎn)，驗(yàn)證是否滿足分辨域限制條件

對(duì)于滿足分辨域條件(6)的候選頂點(diǎn)，令

對(duì)于不滿足分辨域條件(6)的候選頂點(diǎn)，令

轉(zhuǎn)到步驟3.

步驟3 判斷算法終止條件是否滿足.若R ?= PG，則轉(zhuǎn)到步驟2.否則，轉(zhuǎn)到步驟4.

步驟4 輸出結(jié)果.即對(duì)0-1 著色向量S 施加修補(bǔ)技術(shù)并輸出圖的度量維數(shù)和基.

注1 算法1 的步驟4 上施加的修補(bǔ)技術(shù)為：對(duì)每個(gè)頂點(diǎn)v ∈{v|S(v) = 1, v ∈V(G)}，驗(yàn)證是否滿足

若滿足，則令S(v) = 0.對(duì)著色向量重復(fù)施加修補(bǔ)技術(shù)，直到?jīng)]有頂點(diǎn)滿足式(7)，即直到分辨集是極小分辨集為止.

算法1 在隨機(jī)選擇頂點(diǎn)時(shí)加入了對(duì)頂點(diǎn)分辨域的限制條件，并且為屬于分辨集的頂點(diǎn)分配顏色值1，不屬于分辨集的頂點(diǎn)分配顏色值0.因而算法1 是一種有條件的著色分辨算法，簡(jiǎn)稱0-1 隨機(jī)條件著色分辨算法.同時(shí)，修補(bǔ)技術(shù)的采用使得算法所得分辨集至少是一個(gè)極小分辨集.這一點(diǎn)優(yōu)于一般的遺傳算法.經(jīng)過(guò)多次迭代后，取最優(yōu)的著色向量(分配顏色值1 的頂點(diǎn)數(shù)最小的著色向量)作為圖的著色向量.其對(duì)應(yīng)的分配顏色值1 的頂點(diǎn)構(gòu)成的頂點(diǎn)子集作為圖的一個(gè)近似的分辨基或基，分配顏色值1 的頂點(diǎn)數(shù)為圖的近似度量維數(shù).算法1 可作為其他近似算法的局部搜索策略.

算法2 0-1 蟻群條件著色分辨算法

步驟0 基本參數(shù)列表初始化，如表2 所示.

表2 基本參數(shù)

步驟1 迭代初始化.建立圖G 的分辨表RT (表1)和頂點(diǎn)對(duì)集合PG(式(1)).初始化與頂點(diǎn)集對(duì)應(yīng)的著色分辨向量S =(0)1×n.著色為1 的頂點(diǎn)對(duì)應(yīng)的分辨域構(gòu)成的無(wú)重復(fù)元素集合R=φ.

步驟2 將螞蟻k 隨機(jī)放到遍歷網(wǎng)絡(luò)的頂點(diǎn)上.螞蟻k 開(kāi)始為其第一個(gè)訪問(wèn)頂點(diǎn)v ∈V(G)分配顏色1.即S(v) = 1.令R = RN(v).若R = PG，算法終止運(yùn)行并輸出圖的度量維數(shù)1 及其對(duì)應(yīng)基.否則，轉(zhuǎn)到步驟3.

步驟3 首先，根據(jù)式(11),(12)計(jì)算與當(dāng)前訪問(wèn)頂點(diǎn)對(duì)應(yīng)的啟發(fā)因子向量，并且每隔一定迭代步數(shù)N，按照(11)-(14)計(jì)算并調(diào)整期望啟發(fā)因子向量.其次，按照轉(zhuǎn)移概率計(jì)算公式(15)選擇下一訪問(wèn)頂點(diǎn)v ∈V(G)，其中頂點(diǎn)v ∈V(G)滿足頂點(diǎn)分辨域限制條件(5)和(6).轉(zhuǎn)到步驟4.

步驟4 判斷螞蟻k 是否著色完畢.若R ?=PG，則轉(zhuǎn)到步驟3.否則，記錄螞蟻k 的著色向量，轉(zhuǎn)到步驟5.

步驟5 判斷是否滿足k ≤m.若滿足，則當(dāng)前螞蟻數(shù)k 增加1，轉(zhuǎn)到步驟2.否則，轉(zhuǎn)到步驟6.

步驟6 在m 只螞蟻的著色向量中選擇最優(yōu)著色向量.按照一定概率在所選最優(yōu)著色向量附近運(yùn)行算法1，即進(jìn)行局部搜索.所得或所選0-1 著色向量為本次迭代圖的最優(yōu)著色向量.根據(jù)公式(9),(10)和迭代最優(yōu)著色向量更新信息素向量，迭代步數(shù)增加1. 若迭代步數(shù)小于或等于最大迭代步數(shù)，則轉(zhuǎn)到步驟1.否則，轉(zhuǎn)到步驟7.

步驟7 輸出圖的最優(yōu)著色向量，并確定圖的最優(yōu)度量維數(shù)和基.

算法2 保留了0-1 隨機(jī)條件著色分辨算法中的分辨域限制條件、修補(bǔ)技術(shù)、著色分辨向量(解向量)函數(shù)，并加入了蟻群遍歷尋優(yōu)的思想，用概率的方法選擇著色頂點(diǎn).通過(guò)設(shè)計(jì)與問(wèn)題背景相適應(yīng)的遍歷網(wǎng)絡(luò)，信息素向量及其更新策略，動(dòng)態(tài)期望啟發(fā)因子向量及其調(diào)整策略，具有動(dòng)態(tài)特性的轉(zhuǎn)移概率，從全局和局部?jī)蓚€(gè)角度出發(fā)建立了一般圖度量維數(shù)問(wèn)題的0-1 蟻群條件著色分辨算法.算法將全局搜索和局部搜索相結(jié)合，在保持搜索多樣性的同時(shí)，保證求解質(zhì)量和較好的收斂性.為了避免算法過(guò)早收斂，算法采用局部搜索的次數(shù)不宜太多.蟻群算法的較早研究見(jiàn)文獻(xiàn)[25,26].下文進(jìn)一步給出算法2 的設(shè)計(jì)細(xì)節(jié).

3.1 解向量

假設(shè)著色分辨向量函數(shù)S(見(jiàn)2.3 節(jié))與圖G 的頂點(diǎn)標(biāo)號(hào)集V(G) = {1,2,··· ,n}對(duì)應(yīng).其初值S = (0)1×n.在算法運(yùn)行過(guò)程中，為屬于分辨集的頂點(diǎn)分配顏色值1，不屬于分辨集的頂點(diǎn)保持顏色值0 不變.每只螞蟻對(duì)應(yīng)一個(gè)著色分辨向量(函數(shù)).稱每次迭代所得最優(yōu)解向量為圖G 的一個(gè)迭代最優(yōu)著色分辨向量.算法運(yùn)行結(jié)束后所得解向量即為圖的最優(yōu)著色分辨向量.其中分配顏色值1 的頂點(diǎn)構(gòu)成圖G 的近似最優(yōu)分辨基或基.顏色值1 的個(gè)數(shù)為圖G 的近似最優(yōu)度量維數(shù).

3.2 螞蟻遍歷網(wǎng)絡(luò)

給定圖G，在圖G 中添加邊，使得G 成為一個(gè)完全圖.稱所添加的邊為人工邊，所得圖為人工網(wǎng)絡(luò).例如，假定圖1 給定一個(gè)具有8 個(gè)頂點(diǎn)和9 條邊的供螞蟻遍歷的圖G.通過(guò)添加人工邊，得到人工網(wǎng)絡(luò)圖2.其中，實(shí)線表示原始邊，虛線表示人工邊.螞蟻在人工網(wǎng)絡(luò)上按照一定概率到達(dá)任何一個(gè)頂點(diǎn)，而不受其他頂點(diǎn)的阻礙. 從而增強(qiáng)了螞蟻搜索行為的多樣性.

圖1 圖G

圖2 人工網(wǎng)絡(luò)

3.3 信息素向量及其更新與限制策略

蟻群算法已經(jīng)廣泛應(yīng)用于組合優(yōu)化問(wèn)題的研究中.目前，利用蟻群算法求解的大部分組合優(yōu)化問(wèn)題均十分關(guān)注最優(yōu)解以及整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu).在傳統(tǒng)的蟻群算中，當(dāng)前螞蟻遍歷網(wǎng)絡(luò)時(shí)，其選擇下一頂點(diǎn)的行為會(huì)受到與當(dāng)前訪問(wèn)頂點(diǎn)相關(guān)聯(lián)的網(wǎng)絡(luò)邊上信息素的影響，同時(shí)螞蟻也要釋放一定數(shù)量的信息素.因而，信息素的存放方式對(duì)算法的運(yùn)行效率具有重要的影響.傳統(tǒng)的蟻群算法將螞蟻釋放的信息素保存到網(wǎng)絡(luò)的邊上，進(jìn)而構(gòu)成了一個(gè)存儲(chǔ)規(guī)模較大的信息素存儲(chǔ)矩陣(其階數(shù)為網(wǎng)絡(luò)的頂點(diǎn)數(shù))，簡(jiǎn)稱信息素矩陣.在螞蟻遍歷網(wǎng)絡(luò)搜索最優(yōu)解的過(guò)程中，螞蟻要查閱信息素矩陣，獲取與當(dāng)前訪問(wèn)頂點(diǎn)所關(guān)聯(lián)邊上的信息素存儲(chǔ)量，并將其作為選擇下一網(wǎng)絡(luò)頂點(diǎn)的重要影響因素.信息素矩陣及其更新的進(jìn)一步論述見(jiàn)文獻(xiàn)[25-30].對(duì)于信息素的更新和限制，本文采用最大最小蟻群算法[26,27]中的信息素更新和限制策略.

不同于經(jīng)典組合優(yōu)化問(wèn)題，圖的度量維數(shù)問(wèn)題只關(guān)注圖的分辨集及其所含頂點(diǎn)的個(gè)數(shù)，而不關(guān)注分辨集的拓?fù)浣Y(jié)構(gòu). 因而本文嘗試將螞蟻釋放的信息素存放到網(wǎng)絡(luò)頂點(diǎn)上，進(jìn)而建立了一個(gè)存儲(chǔ)規(guī)模較小且便于查閱的與網(wǎng)絡(luò)頂點(diǎn)相對(duì)應(yīng)的信息素存儲(chǔ)向量

實(shí)現(xiàn)整機(jī)閉環(huán)測(cè)試環(huán)境的自動(dòng)構(gòu)建，整機(jī)智能測(cè)試系統(tǒng)需要對(duì)測(cè)試線把座進(jìn)行控制，而控制需要?jiǎng)恿υ磥?lái)提供支持。智能測(cè)試系統(tǒng)對(duì)測(cè)試把座自動(dòng)控制的特點(diǎn)是：水平直線移動(dòng)，移動(dòng)位移較小。因此，動(dòng)力源的選擇可以采用以下兩種方案：1是采用氣動(dòng)系統(tǒng)作為控制源，2是采用伺服電機(jī)作為控制源?？紤]到測(cè)試系統(tǒng)對(duì)測(cè)試把座的控制數(shù)量較多，氣閥與伺服電機(jī)相比，氣閥體積小，布局較為容易。所以采用氣動(dòng)系統(tǒng)作為動(dòng)力源，較為合理。

其中iter-max 是算法的最大迭代步數(shù)，τ0為根據(jù)問(wèn)題選擇的常數(shù)，τj(t)為迭代步t 頂點(diǎn)j 上的信息素量，n 為網(wǎng)絡(luò)頂點(diǎn)數(shù).

在算法迭代運(yùn)行過(guò)程中，網(wǎng)絡(luò)頂點(diǎn)上的信息素隨著迭代時(shí)間(步數(shù))的推移不斷的揮發(fā).一般地，參數(shù)ρ 表示信息素?fù)]發(fā)的強(qiáng)度.ρ 的值越大，網(wǎng)絡(luò)頂點(diǎn)上的信息素?fù)]發(fā)的越快.算法每次迭代運(yùn)行完成后，只有一只螞蟻按照其對(duì)應(yīng)的著色向量和式(9)更新其對(duì)應(yīng)分辨集中頂點(diǎn)上的信息素，即與當(dāng)前迭代最優(yōu)著色分辨向量對(duì)應(yīng)的螞蟻更新其分辨集(顏色值為1 的頂點(diǎn)構(gòu)成分辨集)對(duì)應(yīng)頂點(diǎn)上的信息素.

其中dimbest是當(dāng)前迭代步的最優(yōu)度量維數(shù)，(9)式體現(xiàn)了當(dāng)前迭代最優(yōu)分辨集單位頂點(diǎn)上信息素的增量.對(duì)于不在當(dāng)前迭代最優(yōu)分辨集的頂點(diǎn)，由于信息素的揮發(fā)，其上的信息素存量變?yōu)?/p>

式(9)表明迭代最優(yōu)分辨集所含頂點(diǎn)數(shù)越少，其對(duì)應(yīng)螞蟻在此分辨集的每個(gè)頂點(diǎn)上釋放的信息素越多.為了防止迭代中出現(xiàn)停滯現(xiàn)象，本文將頂點(diǎn)上的信息素限制在一個(gè)區(qū)間[τmin,τmax]內(nèi).頂點(diǎn)上的信息素量τj(j =1,2,··· ,n)滿足

若τj≥τmax，則令τj=τmax； 若τj≤τmin，則令τj=τmin.

在實(shí)驗(yàn)中，計(jì)算τmax和τmin的公式如下

其中

3.4 動(dòng)態(tài)期望啟發(fā)因子向量及其調(diào)整策略

根據(jù)傳統(tǒng)蟻群算法原理[25,27,28]，螞蟻遍歷網(wǎng)絡(luò)并選擇下一訪問(wèn)頂點(diǎn)的行為不僅要受到邊上信息素的影響，還要受到網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響.例如，在旅行商問(wèn)題(TSP 問(wèn)題)中，當(dāng)前螞蟻在候選頂點(diǎn)集合中選擇下一個(gè)訪問(wèn)頂點(diǎn)的行為要受到當(dāng)前訪問(wèn)頂點(diǎn)與候選頂點(diǎn)之間最短距離的影響.若某個(gè)候選頂點(diǎn)與當(dāng)前訪問(wèn)頂點(diǎn)之間的最短距離較大，則該候選頂點(diǎn)被當(dāng)前螞蟻選擇的可能性較小.反之，則較大.因而，傳統(tǒng)蟻群算法引入了存儲(chǔ)規(guī)模較大且固定不變的期望啟發(fā)因子矩陣(其階數(shù)是網(wǎng)絡(luò)的頂點(diǎn)數(shù)，除主對(duì)角線元素為0 外，其它元素是網(wǎng)絡(luò)兩點(diǎn)間最短距離的倒數(shù))來(lái)引導(dǎo)螞蟻在候選頂點(diǎn)集中選擇下一個(gè)可能的訪問(wèn)頂點(diǎn).關(guān)于啟發(fā)因子矩陣的詳細(xì)描述間文獻(xiàn)[27-29].

本文嘗試建立與圖的度量維數(shù)問(wèn)題相適應(yīng)的，存儲(chǔ)規(guī)模較小且具有一定動(dòng)態(tài)特性的期望啟發(fā)因子向量，進(jìn)一步通過(guò)具體的啟發(fā)因子向量調(diào)整策略，增強(qiáng)螞蟻搜索解空間的多樣性.假設(shè)當(dāng)前螞蟻k 訪問(wèn)頂點(diǎn)vi∈{v|S(v) = 0, v ∈V(G)}，即令S(vi) = 1，得解向量S′.在迭代步t，與當(dāng)前訪問(wèn)頂點(diǎn)vi對(duì)應(yīng)的所有可訪問(wèn)頂點(diǎn)構(gòu)成的候選頂點(diǎn)集合為Jk(vi) = {v|S′(v) = 0, v ∈V(G)}.由于圖的度量維數(shù)問(wèn)題不關(guān)注最優(yōu)解及整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，所以本文假設(shè)人工螞蟻在選擇下一訪問(wèn)頂點(diǎn)vj∈Jk(vi)時(shí)會(huì)受到頂點(diǎn)分辨度(式(3))的影響：分辨度較大的頂點(diǎn)被訪問(wèn)的可能性也較大.本文依據(jù)螞蟻候選頂點(diǎn)集動(dòng)態(tài)變化的特點(diǎn)，利用頂點(diǎn)的分辨度構(gòu)造期望啟發(fā)因子

由式(11)可得到期望啟發(fā)因子向量為

其中，式(11)對(duì)頂點(diǎn)分辨度進(jìn)行歸一化處理，有助于提高算法的搜索速度.

當(dāng)前螞蟻選擇下一訪問(wèn)頂點(diǎn)時(shí)，在式(12)的影響下，分辨度較大的候選頂點(diǎn)被選擇的可能性也較大.然而，圖的分辨集或基不一定僅僅由分辨度較大的頂點(diǎn)構(gòu)成.因而，算法每隔一定迭代步數(shù)N 利用公式(12)將向量ηi(t)中的部分最大分量減去某個(gè)常數(shù)，即令

3.5 轉(zhuǎn)移概率設(shè)計(jì)

在螞蟻釋放到頂點(diǎn)上的信息素和與頂點(diǎn)分辨度相關(guān)的動(dòng)態(tài)期望啟發(fā)因子的共同作用下，螞蟻k 從當(dāng)前訪問(wèn)頂點(diǎn)i ∈V(G)依據(jù)概率pkij(t)(式(15))獨(dú)立地選擇下一可達(dá)頂點(diǎn)j ∈Jk(i).

其中，常數(shù)α, β 分別反映信息素和動(dòng)態(tài)期望啟發(fā)因子的相對(duì)重要程度，t 為當(dāng)前迭代步.

與傳統(tǒng)蟻群算法中的轉(zhuǎn)移概率計(jì)算公式相比較，轉(zhuǎn)移概率計(jì)算公式(15)具有幾個(gè)較為顯著的特點(diǎn)：

1) 用存儲(chǔ)規(guī)模較小的信息素向量和啟發(fā)因子向量代替了傳統(tǒng)轉(zhuǎn)移概率計(jì)算公式中的信息素矩陣和啟發(fā)因子矩陣，在降低存儲(chǔ)規(guī)模的同時(shí)，避免了大量的矩陣遍歷搜索，大大提高了轉(zhuǎn)移概率的計(jì)算速度；

2) 啟發(fā)因子的動(dòng)態(tài)變化使得轉(zhuǎn)移概率具有一定的動(dòng)態(tài)特性.而與具有擾動(dòng)特性的公式(13)有效結(jié)合，轉(zhuǎn)移概率計(jì)算公式(15)在一定程度保證了在候選頂點(diǎn)集合中分辨度較小且啟發(fā)因子較低的頂點(diǎn)成為下一個(gè)訪問(wèn)頂點(diǎn)的可能性，提高了算法搜索的多樣性；

3) 在每次迭代的初始階段，轉(zhuǎn)移概率的計(jì)算速度較慢，這是由初始階段螞蟻候選頂點(diǎn)集的規(guī)模較大導(dǎo)致的.隨著算法的繼續(xù)運(yùn)行，轉(zhuǎn)移概率的計(jì)算速度將逐步加快.

3.6 局部搜索設(shè)計(jì)

在算法運(yùn)行前期，對(duì)螞蟻的候選頂點(diǎn)施加了頂點(diǎn)分辨域限制條件(式(5),式(6))，而沒(méi)有對(duì)迭代最優(yōu)解施加修補(bǔ)技術(shù)(式(7)).從而在提高解的質(zhì)量的同時(shí)，保持搜索解空間的多樣性.在算法運(yùn)行后期，為了保證算法的收斂性，每隔一定迭代步數(shù)，當(dāng)前迭代最優(yōu)著色向量對(duì)應(yīng)螞蟻進(jìn)行局部搜索.具體搜索算法或策略采用算法1.考慮到算法運(yùn)行的時(shí)間復(fù)雜性，螞蟻在局部迭代搜索過(guò)程中，只要求每次迭代的起始頂點(diǎn)取自當(dāng)前迭代最優(yōu)著色向量對(duì)應(yīng)的分辨集.保證迭代最優(yōu)解對(duì)應(yīng)螞蟻在當(dāng)前迭代最優(yōu)解的附近進(jìn)行隨機(jī)搜索，并搜索有限次.局部搜索既提高了解的質(zhì)量，又保證了算法具有較好的收斂性.

4 數(shù)值分析

圖的度量維數(shù)問(wèn)題的研究一直以來(lái)都聚焦于特殊圖類度量維數(shù)的計(jì)算.目前，僅有一類線性規(guī)劃模型和遺傳算法分別考慮了該問(wèn)題的數(shù)值計(jì)算方面.文獻(xiàn)[2]最早提出了計(jì)算時(shí)間和空間復(fù)雜度較高的線性規(guī)劃理論模型.對(duì)于頂點(diǎn)規(guī)模較大的圖而言，利用該模型求解其度量維數(shù)是困難的.文獻(xiàn)[24]提出了計(jì)算圖度量維數(shù)的遺傳算法，并在圖著色測(cè)試集上得到了一些圖的度量維數(shù)近似計(jì)算結(jié)果.由于圖的度量維數(shù)問(wèn)題沒(méi)有相應(yīng)的算法測(cè)試圖集，因而包括隨機(jī)圖在內(nèi)的大部分圖類的度量維數(shù)計(jì)算問(wèn)題仍是一個(gè)開(kāi)放課題，其精確度量維數(shù)有待進(jìn)一步研究.算法1 作為一種簡(jiǎn)單隨機(jī)搜索算法，其全局搜索能力有限.本文按照局部搜索設(shè)計(jì)(見(jiàn)3.6 節(jié))將算法1 作為局部搜索策略與具有較強(qiáng)全局搜索能力的蟻群搜索策略相結(jié)合，建立了能夠進(jìn)一步提高求解質(zhì)量的改進(jìn)型蟻群算法2.

4.1 參數(shù)初始化

根據(jù)分辨域的定義(見(jiàn)第2.2 節(jié))生成圖的分辨表(表1)，用來(lái)存儲(chǔ)頂點(diǎn)的分辨特性.根據(jù)式(1)計(jì)算圖G 的所有不同頂點(diǎn)對(duì)構(gòu)成的集合PG.根據(jù)最大最小螞蟻系統(tǒng)[26-28]，信息素重要程度參數(shù)α 取值為[1,4]，啟發(fā)因子重要程度參數(shù)β 取值為[3,5]，信息素?fù)]發(fā)系數(shù)ρ 取值為0 ～1，信息素總量常數(shù)Q 的取值為依賴于與實(shí)際問(wèn)題相關(guān)的參數(shù)α, β, ρ 的取值，螞蟻個(gè)數(shù)的取值一般為10 ～50.根據(jù)問(wèn)題的需要，動(dòng)態(tài)期望啟發(fā)因子向量的初值設(shè)置為空，信息素向量的分量設(shè)置為常數(shù)1.由于信息素總量Q 的取值一般會(huì)受到問(wèn)題規(guī)模的影響，因而本文假定信息素總量Q 隨頂點(diǎn)數(shù)的增加而增加，即

其中n 是網(wǎng)絡(luò)的頂點(diǎn)數(shù)，常數(shù)W =100.信息素總量Q 隨網(wǎng)絡(luò)頂點(diǎn)數(shù)呈非線性變化.

最大迭代步數(shù)iter-max 設(shè)置為100 ～500.當(dāng)螞蟻對(duì)應(yīng)的候選頂點(diǎn)集規(guī)模較大時(shí)，轉(zhuǎn)移概率計(jì)算的時(shí)間復(fù)雜度也較大.因而，本文從當(dāng)前候選頂點(diǎn)集中選取一部分頂點(diǎn)作為螞蟻的實(shí)際候選頂點(diǎn)集.實(shí)際候選頂點(diǎn)集的選取比例系數(shù)記作Sample(0 < Sample ≤1)，其中Sample = 1 表示當(dāng)前候選頂點(diǎn)集就是實(shí)際候選頂點(diǎn)集，其它基本參數(shù)的詳細(xì)分析見(jiàn)文獻(xiàn)[26,27].

4.2 Jahangir 圖上的計(jì)算結(jié)果

本節(jié)主要對(duì)模型求解算法2 進(jìn)行數(shù)值分析，在Jahangir 圖[31]上驗(yàn)證算法2 中分辨域限制條件和修補(bǔ)技術(shù)以及局部搜索設(shè)計(jì)的有效性.

輪圖[32]W2k= K1+ C2k，其中，邊e = uv ∈E(W2k)(u ∈K1, v ∈C2k)是輪圖W2k的一根輻條.在輪圖W2k上交替刪除k 根輻條得到Jahangir 圖，記作J2k.例如，圖3 為有5 根輻條的Jahangir 圖J10.

圖3 J10

算法2 在Jahangir 圖上運(yùn)行的基本實(shí)驗(yàn)參數(shù)為：圖的分辨表(表1)，啟發(fā)因子向量η(式(12))，螞蟻個(gè)數(shù)m = 10，信息相對(duì)重要程度參數(shù)α = 1，期望啟發(fā)因子相對(duì)重要程度參數(shù)β = 5，信息素?fù)]發(fā)系數(shù)ρ = 0.95，初始迭代步iter = 1，最大迭代步數(shù)iter-max = 100，信息素向量Tau(式(8))，頂點(diǎn)上的初始信息素均為1.算法2 在每個(gè)Jahangir 圖上的運(yùn)行次數(shù)T = 20.算法每隔N1= 20 代進(jìn)行一次局部搜索，局部搜索的最大迭代次數(shù)LN = 20.期望啟發(fā)因子不進(jìn)行調(diào)整.候選頂點(diǎn)集選取比例系數(shù)Sample=0.5.

在前期試驗(yàn)中，計(jì)算了大量Jahangir 圖的度量維數(shù).文獻(xiàn)[31]證明了當(dāng)k ≥4 時(shí)，圖J2k的 度 量 維 數(shù) 是」.算 法2 在k 的 取 值 為4,5,··· ,50 的Jahangir 圖 上 的 運(yùn) 行 結(jié)果，如表3 所示.其中N, T, Odim, dim, GRN1, GRN2, LRN1, LRN2, LR, LS, t 分別表示Jahangir 圖的圈上的頂點(diǎn)數(shù)(單位：個(gè))，算法運(yùn)行次數(shù)(單位：次)，Jahangir 圖的精確度量維數(shù)，Jahangir 圖的近似度量維數(shù)，分辨域限制條件(5)在全局搜索中的平均作用次數(shù)(單位：次)，分辨域限制條件(6)在全局搜索中的平均作用次數(shù)(單位：次)，分辨域限制條件(5)在局部搜索中的平均作用次數(shù)(單位：次)，分辨域限制條件(6)在局部搜索中的平均作用次數(shù)(單位：次)，局部搜索中修補(bǔ)技術(shù)的作用次數(shù)(單位：次)，局部搜索成功次數(shù)(即通過(guò)局部搜索尋找到更好解的次數(shù))(單位：次)，算法在每個(gè)圖上運(yùn)行一次平均每代運(yùn)算時(shí)間(單位：秒)等.特別地，Jahangir 圖J10的基和度量維數(shù)見(jiàn)圖4，其中方塊頂點(diǎn)表示圖的一個(gè)基.

表3 Jahangir 圖的度量維數(shù)計(jì)算結(jié)果

續(xù)表3 Jahangir 圖的度量維數(shù)計(jì)算結(jié)果

圖4 J10 的基

4.3 隨機(jī)圖上的計(jì)算結(jié)果

假設(shè)Gn,p表示頂點(diǎn)數(shù)為n，邊存在概率為p 的簡(jiǎn)單連通隨機(jī)圖類.本節(jié)采用與4.2 節(jié)相同的參數(shù)設(shè)置，在隨機(jī)圖上驗(yàn)證算法2 中分辨域限制條件和修補(bǔ)技術(shù)以及局部搜索設(shè)計(jì)的有效性：首先，利用算法2 計(jì)算了隨機(jī)圖G ∈Gn,p的度量維數(shù)，其中，頂點(diǎn)數(shù)n ∈{2,3,··· ,100}，邊存在概率p = 0.1.算法在隨機(jī)圖上的運(yùn)行結(jié)果見(jiàn)表4.特別地，隨機(jī)圖G(n = 10, p = 0.1)的基和度量維數(shù)見(jiàn)圖5.其中方塊頂點(diǎn)表示圖的一個(gè)基.其次，按照度量維數(shù)問(wèn)題的線性規(guī)劃模型[2]，利用Matlab 內(nèi)置的整數(shù)規(guī)劃求解算法計(jì)算了隨機(jī)圖的度量維數(shù).

圖5 隨機(jī)圖G(n=10, p=0.1)的基

在表4 中，n 表示隨機(jī)圖的頂點(diǎn)；Ldim, Lt(單位：秒)分別表示隨機(jī)圖度量維數(shù)的整數(shù)規(guī)劃求解結(jié)果及其平均用時(shí)；dim, t(單位：秒)分別表示基于算法2 的隨機(jī)圖的度量維數(shù)計(jì)算結(jié)果及其每代平均用時(shí)；參數(shù)GRN1, GRN2, LRN1, LRN2, LR, LS 的含義與4.2 節(jié)相同.

表4 隨機(jī)圖的度量維數(shù)計(jì)算結(jié)果

續(xù)表4 隨機(jī)圖的度量維數(shù)計(jì)算結(jié)果

4.4 Jahangir 圖和隨機(jī)圖計(jì)算結(jié)果比較分析

表3 和表4 的GRN2 列、LRN2 列表明，分辨域限制條件(6)對(duì)算法在Jahangir 圖上的運(yùn)行結(jié)果影響較小，而在隨機(jī)圖上的運(yùn)行結(jié)果有較大影響.結(jié)合前期試驗(yàn)分析，對(duì)于頂點(diǎn)數(shù)較大或邊存在概率較大，頂點(diǎn)分辨度分布比較規(guī)則的圖，算法在運(yùn)行時(shí)可取消分辨域限制條件(6)的限制.

表3 和表4 的GRN1 列、LRN1 列表明，分辨域限制條件(5)在全局搜索和局部搜索中都起到了提高近似解質(zhì)量的重要作用.LR 列表明了修補(bǔ)技術(shù)在局部搜索中的有效性.算法每隔一定步數(shù)啟用一次局部搜索.LS 列表示當(dāng)算法在某個(gè)圖上運(yùn)行一定次數(shù)時(shí)，局部搜索對(duì)近似最優(yōu)度量維數(shù)的改進(jìn)次數(shù)，即局部搜索成功的次數(shù).LS 列表明局部搜索策略對(duì)提高算法的求解質(zhì)量具有一定的有效性.

表3 和表4 的dim 列是算法的度量維數(shù)近似計(jì)算結(jié)果.表3 中的度量維數(shù)近似計(jì)算結(jié)果與精確度量維數(shù)較為接近，算法運(yùn)行結(jié)果較好.Jahangir 圖的頂點(diǎn)分辨度分布較為規(guī)則，頂點(diǎn)分辨度缺乏多樣性，因而算法求解較為困難.表4 的Ldim 列、dim 列、Lt 列、t列從運(yùn)行結(jié)果和運(yùn)行時(shí)間方面表明算法2 的運(yùn)行表現(xiàn)顯著優(yōu)于整數(shù)規(guī)劃求解算法.一部分原因是隨機(jī)圖的頂點(diǎn)分辨度具有較大的多樣性，有利于算法跳出局部最優(yōu).

4.5 ORLIB 圖例的計(jì)算結(jié)果對(duì)比分析

ORLIB 開(kāi)放圖數(shù)據(jù)庫(kù)存儲(chǔ)了大量與實(shí)際圖論問(wèn)題相關(guān)的圖例，但尚無(wú)與圖的度量維數(shù)問(wèn)題相關(guān)的測(cè)試圖例.文獻(xiàn)[24]利用遺傳算法計(jì)算了圖著色圖例的近似度量維數(shù)，但這些圖的精確度量維數(shù)仍然未知.本節(jié)利用算法2 計(jì)算了部分相同圖類的近似度量維數(shù)，計(jì)算結(jié)果摘錄于表5.

表5 ORLIB 圖例的度量維數(shù)計(jì)算結(jié)果

具體地，算法2 在gcol 圖例上運(yùn)行的基本實(shí)驗(yàn)參數(shù)為：圖的分辨表(表1)，啟發(fā)因子向量η(式(12))，螞蟻個(gè)數(shù)m = 10，信息相對(duì)重要程度參數(shù)α = 2，期望啟發(fā)因子相對(duì)重要程度參數(shù)β = 5，信息素?fù)]發(fā)系數(shù)ρ = 0.95，初始迭代步iter = 1，最大迭代步數(shù)iter-max = 100，信息素向量Tau(式(8))，頂點(diǎn)上的初始信息素均為1.算法2 在每個(gè)gcol 圖例上的運(yùn)行次數(shù)T = 20.算法每隔3 代進(jìn)行一次局部搜索，局部搜索最大迭代次數(shù)為10.期望啟發(fā)因子每隔20 代進(jìn)行調(diào)整.當(dāng)頂點(diǎn)數(shù)比較大時(shí)，候選頂點(diǎn)集選取比例系數(shù)Sample=0.5.

在表5 中，第一列(Graph)表示圖例，第二列(Node)表示每個(gè)圖例的頂點(diǎn)數(shù)(單位：個(gè))，第三列(Edge)表示每個(gè)圖例的邊數(shù)(單位：條)，第四列(T)表示算法2 在每個(gè)圖例上的運(yùn)行次數(shù)(單位：次)，第五列(dim1)表示利用算法2 所得圖例的度量維數(shù)，第七列(LR)，第八列(LS)分別表示算法2 的修補(bǔ)技術(shù)和局部搜索成功的次數(shù)(單位：次)，第九列(t)表示算法2 在每個(gè)圖上運(yùn)行一次平均每代用時(shí)(單位：秒)，最后一列(dim2)是文獻(xiàn)[24]利用遺傳算法所得圖的度量維數(shù).

第二列、第三列、第九列表明隨著圖的頂點(diǎn)數(shù)和邊數(shù)規(guī)模的增大，算法運(yùn)行的時(shí)間復(fù)雜度顯著增加.因而，算法根據(jù)第六列(Sample)的設(shè)置從候選頂點(diǎn)集合中選擇一定比例的頂點(diǎn)作為螞蟻的實(shí)際候選頂點(diǎn)集合.考慮到算法求解質(zhì)量和轉(zhuǎn)移概率計(jì)算的時(shí)間復(fù)雜性，當(dāng)圖的頂點(diǎn)數(shù)較大時(shí)，比例系數(shù)Sample 取值為0.5.這在一定程度上降低了轉(zhuǎn)移概率計(jì)算的時(shí)間復(fù)雜度，又不會(huì)使得求解質(zhì)量最差.在實(shí)際應(yīng)用中，可根據(jù)實(shí)際問(wèn)題的求解質(zhì)量容忍范圍，比例系數(shù)Sample 可取不同的值.

第五列(dim1)和第十列(dim2)表明算法2 通過(guò)利用修補(bǔ)技術(shù)(LR)和局部搜索(LS)得到了較好的計(jì)算結(jié)果.修補(bǔ)技術(shù)和局部搜索確保了算法2 在最壞的情況下所得圖的分辨集是圖的一個(gè)極小分辨集.這一點(diǎn)優(yōu)于文獻(xiàn)[24]中的遺傳算法.算法2 所得圖例的最優(yōu)分辨集(也是極小分辨集)見(jiàn)表6，其中頂點(diǎn)的標(biāo)號(hào)與其在數(shù)據(jù)庫(kù)(ORLIB)中頂點(diǎn)的標(biāo)號(hào)一致.例如，200 表示圖的標(biāo)號(hào)為200 的頂點(diǎn)，其對(duì)應(yīng)于鄰接矩陣的第200 行，第200 列.Graph，Resolving set 分別表示圖例和其對(duì)應(yīng)的分辨集.

表6 gcol 圖例的最優(yōu)分辨集

續(xù)表6 gcol 圖例的最優(yōu)分辨集

4.6 算法參數(shù)分析

根據(jù)實(shí)際問(wèn)題的特點(diǎn)，本文引入了圖的分辨表作為存儲(chǔ)圖的分辨特性的數(shù)據(jù)結(jié)構(gòu).該參數(shù)與圖的分辨模型結(jié)合充分體現(xiàn)了圖的度量維數(shù)問(wèn)題的組合特性.在算法設(shè)計(jì)方面，引入了人工遍歷網(wǎng)絡(luò)，信息素向量和動(dòng)態(tài)期望啟發(fā)因子，在較大程度上降低了蟻群搜索的空間復(fù)雜度和時(shí)間復(fù)雜度.在Jahangir 圖，隨機(jī)圖和gcol 圖例上的數(shù)值實(shí)驗(yàn)表明算法引入的分辨域限制條件一定程度上能夠有效提高算法求解質(zhì)量.對(duì)于算法設(shè)計(jì)中的基本參數(shù)，如信息素重要程度參數(shù)α，期望啟發(fā)因子重要程度參數(shù)β，信息素?fù)]發(fā)系數(shù)ρ，螞蟻個(gè)數(shù)m，在文獻(xiàn)[25-27]中已有詳細(xì)的分析，這里不再贅述.算法引入的其它參數(shù)，如局部搜索間隔代數(shù)和動(dòng)態(tài)期望啟發(fā)因子調(diào)整的間隔代數(shù)要根據(jù)實(shí)際圖例進(jìn)行選定.由于Jahangir 圖度量維數(shù)是已知的，因此下文基于Jahangir 圖的數(shù)值實(shí)驗(yàn)對(duì)新引入的候選頂點(diǎn)集選取比例系數(shù)(Sample)進(jìn)行分析，進(jìn)一步研究其對(duì)算法求解質(zhì)量的影響.

本節(jié)隨機(jī)生成h 個(gè)Jahangir 圖：J20, J30, J34, J48, J54, J60, J62, J68, J80, J82, J86,J100，分析候選頂點(diǎn)集選取比例系數(shù)對(duì)求解質(zhì)量的影響.令Oi表示Jahangir 圖的真實(shí)度量維數(shù)，Di表示算法輸出的Jahangir 圖度量維數(shù)，建立平均誤差指標(biāo)

根據(jù)比例系數(shù)的不同，算法在生成圖上的平均誤差指標(biāo)數(shù)據(jù)見(jiàn)表7.從圖6 中可以直觀的看出平均誤差隨候選頂點(diǎn)選取比例系數(shù)的變化趨勢(shì).即在其它參數(shù)不變的情況下候選頂點(diǎn)選取比例系數(shù)Sample 取值0.7 ～0.8 較好.對(duì)于不同的圖類，該參數(shù)的取值范圍需要進(jìn)一步的確定.

表7 比例系數(shù)與平均誤差

圖的頂點(diǎn)分辨度的分布情況對(duì)算法運(yùn)行效果的影響具有一定的不確定性.與復(fù)雜網(wǎng)絡(luò)的度分布研究類似[33]，為了進(jìn)一步認(rèn)識(shí)圖或?qū)嶋H復(fù)雜網(wǎng)絡(luò)的內(nèi)在分辨特性，刻畫(huà)一般圖或?qū)嶋H復(fù)雜網(wǎng)絡(luò)的頂點(diǎn)分辨度的概率分布可作為圖的度量維數(shù)問(wèn)題的進(jìn)一步研究課題：給定一般簡(jiǎn)單連通圖或?qū)嶋H復(fù)雜網(wǎng)絡(luò)，刻畫(huà)其頂點(diǎn)分辨度的概率分布.

圖6 平均誤差隨候選頂點(diǎn)選取比例系數(shù)的變化