基于點權(quán)約束的模糊最小權(quán)邊覆蓋問題研究

摘 要：圖論中的邊覆蓋問題由于其廣泛的實際應(yīng)用性，近年來受到廣泛的關(guān)注。為求解基于點權(quán)約束的模糊最小權(quán)邊覆蓋問題首先提出Cons-模糊期望最小權(quán)邊覆蓋模型和Cons-模糊α-最小權(quán)邊覆蓋模型；隨后設(shè)計一種結(jié)合模糊模擬技術(shù)和遺傳算法的混合智能算法求解所提出的決策模型，并在混合智能算法中納入點權(quán)約束因子；最后用一個數(shù)值試驗驗證混合智能算法和決策模型的有效性。

關(guān)鍵詞：模糊變量；最小權(quán)邊覆蓋；點權(quán)約束；混合智能算法

中圖分類號：O221.2；TP18

邊覆蓋問題是圖論中的經(jīng)典問題之一，在實踐中具有廣泛的應(yīng)用性。V和E分別代表無向圖G中頂點和邊的集合。如果圖中的一個頂點和一條邊是關(guān)聯(lián)的，則可以認為它們彼此覆蓋。如果給圖中的邊賦予權(quán)值，如何尋找覆蓋G中所有頂點的最小權(quán)邊覆蓋就是最小權(quán)邊覆蓋問題。且實際應(yīng)用中確定性總是相對的，不確定性是絕對的，邊的權(quán)通常是不確定的。隨機性和模糊性是不確定最為普遍的兩種情形。Zadeh[1]和等先后提出了模糊集概念和模糊變量的概念。Liu在2002年提出了可信性測度以對模糊變量進行更好的度量，并以此為基礎(chǔ)創(chuàng)立了可信性理論[2]。Ni隨后把模糊變量引入到最小權(quán)邊覆蓋問題中，首次對模糊環(huán)境下的最小邊權(quán)問題進行了深入研究[3]。

上述研究往往在滿足邊覆蓋的基礎(chǔ)上以尋求總體模糊權(quán)的最小值為唯一目標(biāo)，尚未考慮到實際應(yīng)用中點權(quán)約束的情形.本文引入點權(quán)約束因子，對基于點權(quán)約束的模糊最小權(quán)邊覆蓋問題研究。

1 決策模型

不確定性變量無法像確定性變量一樣進行直接比較，為了更好的對模糊變量進行比較，我們引入了不確定環(huán)境下常用的兩種決策準(zhǔn)則：期望值準(zhǔn)則和樂觀值準(zhǔn)則。其中期望是不確定性變量的最常用測度之一，它可以較好的衡量不確定變量的水平。

1.1 Cons-模糊期望最小權(quán)邊覆蓋模型

定義1 在賦權(quán)無向圖G中，X表示其中的一個邊覆蓋，X′表示賦權(quán)無向圖G中任意一個邊覆蓋，在滿足點權(quán)約束的情形下，如果滿足

E[W（X，ξ）]≤E[W（X'，ξ）] （1）

那么X即是Cons-模糊期望最小權(quán)邊覆蓋。

基于以上Cons-模糊期望最小權(quán)邊覆蓋的概念，我們提出如下的Cons-模糊期望最小權(quán)邊覆蓋模型：

（2）

1.2 Cons-α最小權(quán)邊覆蓋模型

期望值準(zhǔn)則在某些情況下，不能充分滿足決策者的需要。α是一個介于0和1之間的參數(shù)，可稱為置信水平[4]。我們以α樂觀值準(zhǔn)則從別于期望的另一個角度，對模糊變量進行衡量。

定義2 在賦權(quán)無向圖G中，X表示其中的一個邊覆蓋，X′表示賦權(quán)無向圖G中任意一個邊覆蓋，在滿足點權(quán)約束的情形下，如果滿足

（3）

那么X即是Cons-模糊α-最小權(quán)邊覆蓋。

基于以上Cons-模糊α-最小權(quán)邊覆蓋的概念，我們提出如下的Cons-模糊α-最小權(quán)邊覆蓋模型：

（4）

2 混合智能算法

顯然用確定性算法對上述不確定決策模型是不適用的。為此，我們結(jié)合遺傳算法和模糊模擬技術(shù)，基于點權(quán)約束因子，形成一種新的混合智能算法。其中遺傳算法由Holland于1975年首次提出[5]，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。Beasley等[6]隨后分析了遺傳算法在覆蓋問題中的應(yīng)用。模糊模擬是由Liu于2002年首次提出[7]?；旌现悄芩惴ǖ牟襟E如圖1所示（其中N代表循環(huán)的次數(shù)，模擬生物進化的代數(shù)，通常為一個足夠大的數(shù)）。

圖1 混合智能算法的具體步驟

3 數(shù)值實驗

本節(jié)中，我們將采用數(shù)值模擬的方法進行實驗以驗證算法的有效性。圖2是一個含有23個頂點，40條邊的無向圖。其中，圖中的任意一條邊，其權(quán)均屬于模糊梯形變量。

圖2 數(shù)值試驗中的無向圖

在Cons-模糊期望最小權(quán)邊覆蓋模型中，我們用Cons代表點權(quán)約束因子，分別取值為10，11.487，15，20，25，30進行試驗（其中11.487是模糊邊權(quán)期望的最小值。）在表1中，不難發(fā)現(xiàn)，當(dāng)Cons小于等于11.487時，對邊覆蓋結(jié)果不產(chǎn)生影響，與無點權(quán)約束情形的結(jié)果相同。但隨著Cons的增長，結(jié)果發(fā)生明顯改變，且Cons-權(quán)值越來越大。這是因為雖然覆蓋某個頂點的邊集合權(quán)值較小，但是并不能滿足點權(quán)約束，所以只能取那些在滿足點權(quán)約束條件基礎(chǔ)上權(quán)值較小的邊集合。隨著Cons的增長，滿足點權(quán)約束的最小邊權(quán)也越來越大。當(dāng)Cons大到一定程度時，無解，這是因為覆蓋某個頂點的邊權(quán)之和小于Cons，此時無法滿足邊覆蓋的基本條件。

在Cons-模糊α-最小權(quán)邊覆蓋模型中，設(shè)有兩個參數(shù)，置信水平α和代表點權(quán)約束因子的Cons。在表2中，不難發(fā)現(xiàn)，Con-α-權(quán)值隨著α的增加而增加，隨著Cons的增加而增加。符合預(yù)期估計。而Cons一般均通過改變覆蓋頂點的邊，來影響邊覆蓋的權(quán)值。

4 結(jié)束語

通過實驗表明，點權(quán)約束對模糊最小權(quán)邊覆蓋問題的最優(yōu)解具有較大的影響。因此，考慮點權(quán)約束對邊覆蓋問題至關(guān)重要。本文所提出的決策模型和求解決策模型的混合智能算法對統(tǒng)一確定點權(quán)約束情形下的模糊最小權(quán)邊覆蓋問題進行了研究，幫助決策者在充分考慮點權(quán)約束的情況下進行不確定決策。

參考文獻：

[1]Zadeh L.Fuzzy sets[J].Information and Control，1965（03）：338-353.

[2]Liu B.Uncertainty Theory：An Introduction to its Axiomatic Foundations[M].Springer-Verlag，Berlin，2004.

[3]Ni Y.D.Fuzzy Minimum Weight Edge Covering Problem，Applied Mathematical Modeling[J].2008（07）：1327-1337.

[4]Li X and Liu B.Chance measure for hybrid events with fuzziness and randomness[J].Soft Computing，2009（02）：105-115.

[5]Holland J.Adaptation in Natural and Artificial System [M].University of Michigan Press，Ann Arbor，MI，1975.

[6]Beasley J.E，Chu P.C.A genetic algorithm for the set covering problem[J].European Journal of Operational Research，1996（02）：392-404.

[7]Li P，Liu B.Entropy of credibility distributions for fuzzy variables[J].IEEE Transactions on Fuzzy Systems，2008（01）：123-129.

作者簡介：王辰尹（1987-），女，重慶人，碩士，主要研究方向：計算智能，計算機教育；張冬玲，女，高級講師，主要研究方向：多媒體技術(shù)、計算機教育等。

作者單位：中山大學(xué)新華學(xué)院 信息科學(xué)系，廣州 510520

基金項目：中山大學(xué)新華學(xué)院2013實驗教學(xué)示范中心項目（項目編號：2013S002）。