武 建, 趙海霞

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

1 引言

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

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

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

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

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

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

本文通過數(shù)值對比分析驗證算法的有效性：

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

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

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

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

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

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

2.1 問題描述

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

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

2.2 頂點的分辨域

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

對于任意頂點x ∈V(G)，頂點x 的分辨域RN(x)為

頂點x 的分辨度RD(x)為

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

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

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

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

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

設(shè)

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

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

3 模型求解算法研究

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

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

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

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

同時，對滿足分辨域條件(5)的候選頂點，驗證是否滿足分辨域限制條件

對于滿足分辨域條件(6)的候選頂點，令

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

轉(zhuǎn)到步驟3.

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

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

注1 算法1 的步驟4 上施加的修補技術(shù)為：對每個頂點v ∈{v|S(v) = 1, v ∈V(G)}，驗證是否滿足

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

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

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

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

表2 基本參數(shù)

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

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

步驟3 首先，根據(jù)式(11),(12)計算與當(dāng)前訪問頂點對應(yīng)的啟發(fā)因子向量，并且每隔一定迭代步數(shù)N，按照(11)-(14)計算并調(diào)整期望啟發(fā)因子向量.其次，按照轉(zhuǎn)移概率計算公式(15)選擇下一訪問頂點v ∈V(G)，其中頂點v ∈V(G)滿足頂點分辨域限制條件(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)著色向量附近運行算法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ī)條件著色分辨算法中的分辨域限制條件、修補技術(shù)、著色分辨向量(解向量)函數(shù)，并加入了蟻群遍歷尋優(yōu)的思想，用概率的方法選擇著色頂點.通過設(shè)計與問題背景相適應(yīng)的遍歷網(wǎng)絡(luò)，信息素向量及其更新策略，動態(tài)期望啟發(fā)因子向量及其調(diào)整策略，具有動態(tài)特性的轉(zhuǎn)移概率，從全局和局部兩個角度出發(fā)建立了一般圖度量維數(shù)問題的0-1 蟻群條件著色分辨算法.算法將全局搜索和局部搜索相結(jié)合，在保持搜索多樣性的同時，保證求解質(zhì)量和較好的收斂性.為了避免算法過早收斂，算法采用局部搜索的次數(shù)不宜太多.蟻群算法的較早研究見文獻(xiàn)[25,26].下文進(jìn)一步給出算法2 的設(shè)計細(xì)節(jié).

3.1 解向量

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

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

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

圖1 圖G

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

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

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

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

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

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

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

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

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

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

在實驗中，計算τmax和τmin的公式如下

其中

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

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

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

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

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

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

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

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

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

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

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

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

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

3.6 局部搜索設(shè)計

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

4 數(shù)值分析

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

4.1 參數(shù)初始化

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

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

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

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

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

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

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

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

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

圖4 J10 的基

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.6 算法參數(shù)分析

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

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

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

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

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

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