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

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

中圖分類號(hào)：O221.2；TP18

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

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

1 決策模型

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

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

定義1 在賦權(quán)無向圖G中，X表示其中的一個(gè)邊覆蓋，X′表示賦權(quán)無向圖G中任意一個(gè)邊覆蓋，在滿足點(diǎn)權(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)則在某些情況下，不能充分滿足決策者的需要。α是一個(gè)介于0和1之間的參數(shù)，可稱為置信水平[4]。我們以α樂觀值準(zhǔn)則從別于期望的另一個(gè)角度，對(duì)模糊變量進(jìn)行衡量。

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

（3）

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

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

（4）

2 混合智能算法

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

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

3 數(shù)值實(shí)驗(yàn)

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

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

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

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

4 結(jié)束語

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

參考文獻(xià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.

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

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

基金項(xiàng)目：中山大學(xué)新華學(xué)院2013實(shí)驗(yàn)教學(xué)示范中心項(xiàng)目（項(xiàng)目編號(hào)：2013S002）。