国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

集約簡(jiǎn)算法和改進(jìn)遺傳算法混合求解集合覆蓋問(wèn)題

2018-01-29 08:50:00陳向陽(yáng)李汪根胡東輝
池州學(xué)院學(xué)報(bào) 2017年6期
關(guān)鍵詞:適應(yīng)度算子遺傳算法

陳向陽(yáng),李汪根,胡東輝

(1.安慶醫(yī)藥高等??茖W(xué)校公共基礎(chǔ)部,安徽安慶246052;2.安徽師范大學(xué)數(shù)學(xué)計(jì)算機(jī)科學(xué)學(xué)院,安徽蕪湖241000;3.合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院,安徽合肥230002)

1 引言

集合覆蓋問(wèn)題是優(yōu)化組合上的一個(gè)經(jīng)典的NP-問(wèn)題[1]。它已被廣泛應(yīng)用于電路優(yōu)化設(shè)計(jì)、測(cè)試優(yōu)化、車輛路徑優(yōu)化、網(wǎng)絡(luò)節(jié)點(diǎn)選擇、模式識(shí)別、人工智能、生物信息學(xué)等諸多領(lǐng)域。

國(guó)內(nèi)外許多學(xué)者提出了大量的近似算法。如吳信東提出HVC算法[2-3],陳亮提出啟發(fā)式遺傳算法[4],連光耀提出基于粒子群優(yōu)化算法的測(cè)試選擇優(yōu)化方法[5],葛洪偉提出基于SCHF的蟻群算法[6],崔鵬深入研究了關(guān)于集合覆蓋貪心算法的最小測(cè)試集[7]。J.E.Beasley提出拉格朗日函數(shù)啟發(fā)算法和遺傳算法[8-9]。Alberto Caprara改進(jìn)了拉格朗日函數(shù)啟發(fā)算法[10]。Fisher和Kedia提出采用對(duì)偶啟發(fā)式的最優(yōu)解[11]。

任何集覆蓋的近似解與精確解之間都存在一定的距離。1997年,Petr Slavik證明了逼近度ln(|S|)-lnln(|S|)+O(1)的貪心算法[12]。1998 年,Uriel Feige證明了不存在一個(gè)集合覆蓋問(wèn)題的多項(xiàng)式時(shí)間近似算法低于閾值(1-O(1))ln(|S|)[13]。

本文提出了一種集約簡(jiǎn)算法和改進(jìn)遺傳算法的混合方法,用于解決集合覆蓋問(wèn)題。模擬實(shí)驗(yàn)表明,當(dāng)測(cè)試集的規(guī)模比原來(lái)的問(wèn)題小十倍以內(nèi)時(shí)集約簡(jiǎn)算法(SRA)效果明顯。在全局搜索最小和收斂速度上改進(jìn)遺傳算法(MGA)具有明顯的效果。

2 集約簡(jiǎn)算法(SRA)

2.1 基本概念

定義1覆蓋網(wǎng)M{Φ,Ω;Γ},其中 Φ={Ei︱0≦i<n};Ω={Sj︱0≦j<m,Sj是集合Φ的子集,并且對(duì)于任意E屬于Φ,其一定也屬于Sj,即滿足E∈Sj};Γ滿足:如果Ei∈ Sj,(Ei,Sj)∈Γ。這樣的三元組稱為覆蓋網(wǎng)。Φ叫做元素集,Ω是集合;Γ為接觸組,n是計(jì)量,記為|M|;m是規(guī)模,記為||m||。(Ei,Sj)被稱為接觸。Γ中接觸的數(shù)量被稱為覆蓋網(wǎng)M的復(fù)雜度,記為|||M|||。

集合[E]={S|(E,S)∈Γ}被稱為元素E的屬于集合,S的數(shù)量被命名為元素E的出度,記為|E|。當(dāng)|E|=1時(shí),[E]表示唯一一個(gè)元素S。

集合[S]={E|(E,S)∈Γ}被稱為集合S的屬于集合,E的數(shù)量被命名為集合S的入度,記為|S|。

集合<E>={E*|E*∈[S],S∈[E]} 被稱為元素E的相鄰集合。

W(S)= ∏ (1-1/|E|),當(dāng) E∈[S]時(shí),W(S)被稱為集合S的選定索引。

如果兩個(gè)覆蓋網(wǎng)M1和M2,其計(jì)量,規(guī)模和復(fù)雜度都是相等的,兩個(gè)覆蓋網(wǎng)中所有的元素和集合都一一對(duì)應(yīng),且兩覆蓋網(wǎng)中所有接觸完全對(duì)應(yīng),則稱M1和M2是同構(gòu)的。相應(yīng)的元素(或集合)被稱為元素(或集合)的對(duì)應(yīng)點(diǎn)。

定義2簡(jiǎn)化的覆蓋網(wǎng):覆蓋網(wǎng)M{Φ,Ω;Γ},在Ω中兩個(gè)不同的集合S1、S2,[S1]是[S2]的子集,集合S1可以收縮成集合S2,則S2稱為集合S1的收縮點(diǎn),表示為S1→S2,覆蓋網(wǎng)M稱為集合收縮網(wǎng)(SCN)。如果在Ω中有兩個(gè)不同的元素E1、E2,[E1]是[E2]的子集,表示為E2→E1,元素E2可收縮成元素E1,則E1稱為元素E2的收縮點(diǎn),覆蓋網(wǎng)稱為元素收縮網(wǎng)M(ECN)。如果覆蓋網(wǎng)M既不是SCN也不是ECN,M則是一個(gè)簡(jiǎn)化的覆蓋網(wǎng),表示為S1∽S2。如果E1→E2并且 E2→E1,則元素E1和E2相似,表示為S1∽S2。

定義3覆蓋和最小覆蓋:對(duì)于覆蓋網(wǎng)M{Φ,Ω;Γ},集合C={Si|Si∈ Ω 和 ∪Si= Φ,i<||M||}稱為覆蓋網(wǎng)M的覆蓋。集合C中S的數(shù)量稱為覆蓋的度,表示為|C|。如果|Least C|≤|任意覆蓋|,LeastC就稱為覆蓋網(wǎng)M的最小覆蓋。

2.2 集約簡(jiǎn)算法

Data←采用雙十字鏈表存儲(chǔ)的覆蓋矩陣;ElementNumber←覆蓋矩陣元素的數(shù)目;workele←所有元素;WorkSet←所有集合(因?yàn)樵陔娐穬?yōu)化設(shè)計(jì)中所有的集合都有聯(lián)系,所以一開始WorkSet是空);

3 改進(jìn)的遺傳算法(MGA)

標(biāo)準(zhǔn)遺傳算法(SGA)的靈感來(lái)自于生物進(jìn)化的機(jī)制,是一種高度并行的啟發(fā)式搜索算法。它源于一個(gè)代表可行的解決方案的隨機(jī)的人口的染色體,然后基于定義的適應(yīng)度函數(shù)的每個(gè)個(gè)體都在人群中進(jìn)行評(píng)估。更重要的是,通過(guò)使用一系列的遺傳算子,如選擇,交叉或突變產(chǎn)生新的一代。這個(gè)過(guò)程不斷重復(fù),直到滿足停止準(zhǔn)則。最后,最好的染色體被認(rèn)為是最佳的解決方案。

由于SGA容易過(guò)早收斂,需要提高SGA以保證全局最優(yōu)收斂。本文介紹了一種改進(jìn)的遺傳算法,特別地,操作參數(shù)進(jìn)行了優(yōu)化,并采用新的遺傳算子,以提高其性能。MGA實(shí)現(xiàn)細(xì)節(jié)如下:

3.1 編碼

編碼是使用遺傳算法需要解決的首要問(wèn)題。采用二進(jìn)制編碼方案,選擇的位置用1表示,不選的用0表示。

3.2 適應(yīng)

適應(yīng)的選擇是MGA性能的關(guān)鍵。這里的性能是指對(duì)應(yīng)于一個(gè)基因的列中包含1的個(gè)數(shù)。如果是一個(gè)大的數(shù)字則包含更多的行。它說(shuō)明了該基因有相對(duì)高的性能。使用同樣的方法,我們可以找到其他基因的覆蓋集。為了找出最佳的染色體,需要考慮每個(gè)基因的成本。

適應(yīng)度函數(shù)的描述如下:

其中r表示矩陣A的行;CJ表示第j列的成本。

3.3 遺傳算子

三大遺傳算子,包括選擇、交叉和變異,其對(duì)遺傳算法搜索效率有直接影響。在一些具體的問(wèn)題中,選擇適當(dāng)?shù)倪z傳操作參數(shù)是一個(gè)重要的問(wèn)題。

(1)選擇:這里采用的適應(yīng)度比例法是輪盤賭選擇法,這意味著染色體獲得的適應(yīng)度值越高,其被選擇的概率就越大。本文中概率PSI有如下的表達(dá)式:

(2)交叉:交叉操作不僅可以從父母雙方交流信息,而且可以產(chǎn)生與父母不同結(jié)構(gòu)的更好的后代。應(yīng)該注意的是,在這種情況下,在較少的迭代搜索中可以得到一個(gè)更高的適應(yīng)值。使用一個(gè)改進(jìn)的交叉算子。定義X1和x2為父母的字符串。因此,字符串x1和x2的后代被定義如下:

γ是區(qū)間[0,1]中的一個(gè)隨機(jī)數(shù)。

(3)突變:突變的另一個(gè)關(guān)鍵因素是關(guān)于遺傳算法的優(yōu)化性能,可以保持種群的多樣性,也有助于從父輩那里繼承的特征。最重要的是,它使遺傳算法能夠用更好的適應(yīng)度值來(lái)探索染色體。傳統(tǒng)的遺傳算法通常采用簡(jiǎn)單的變異和均勻的突變,因此,它導(dǎo)致局部搜索能力較弱。本文采用了一種特殊的技術(shù)組合變異算子和進(jìn)化的一代,這起著進(jìn)化精細(xì)調(diào)整的作用。用Xk表示一個(gè)父母,其在范圍內(nèi),并假設(shè)后代的產(chǎn)生根據(jù):

注意r1、r2是兩個(gè)獨(dú)立分布的隨機(jī)變量,其范圍是[0,1],t是當(dāng)前迭代次數(shù),T為最大的迭代次數(shù)。

為了防止種群的優(yōu)良基因被破壞,采用動(dòng)態(tài)突變概率確定的方法。當(dāng)個(gè)體的適應(yīng)度值大于平均值時(shí),我們選擇一個(gè)較小的變異概率,否則,選擇較大的概率。

3.4 終止準(zhǔn)則

確定MGA是否該繼續(xù)運(yùn)行:如果它達(dá)到停止條件的最大數(shù)量的迭代T,結(jié)束算法并輸出最佳的權(quán)重和閾值。

4 案例研究

4.1 數(shù)據(jù)與變量

為了測(cè)試本文提出的混合SRA-MGA的影響,采用三組不同的數(shù)據(jù)集合,所有元素都是隨機(jī)生成的。在第一個(gè)實(shí)驗(yàn)中的元素是8位的二進(jìn)制數(shù),研究在相同的比特位,但有不同的數(shù)據(jù)密度,所產(chǎn)生的效果。在這里,數(shù)據(jù)密度是指在同一位的元素的數(shù)量和樣本空間的數(shù)量,如:在8位的樣本空間的數(shù)目是256(2^8),如果選擇其中的100個(gè),密度就是100/256。第二個(gè)和第三個(gè)是不同的位,但都有相同的密度,數(shù)據(jù)密度分別為5/8和25/32。

這些測(cè)試集的詳細(xì)信息如表1所示。

表1 測(cè)試集

4.2 實(shí)驗(yàn)結(jié)果和性能分析

不同的實(shí)驗(yàn)結(jié)果表明,在絕大多數(shù)情況下,SRA-MGA最小覆蓋的算法比QM算法的小得多,并且SRA-MGA算法的選擇集合更穩(wěn)定。

對(duì)在QM和SRA之間SRA減少的集合數(shù)量的比較見表2。從表中可以清楚地看到,SRA引起的集數(shù)減少是QM的幾倍或甚至幾十倍。

表2 SRA-MGA和QM的性能比較

SRA-MGA和GA之間的最小成本比較如表3所示。從表中可以清楚地看到,SRA-MGA的表現(xiàn)比GA更好。

表3 SRA-MGA和GA之間的性能比較

5 結(jié)論

提出的結(jié)合SRA和MGA的混合模型繼承了遺傳算法的優(yōu)勢(shì),克服其弱點(diǎn)。

從定理1和定理2得出,第一次的簡(jiǎn)化是先決條件,它的效果可以從實(shí)驗(yàn)結(jié)果得到。從遺傳算法和SRA-MGA算法的比較中,選擇最有可能的集合比選擇最大出度的集合更有效。

本文的實(shí)驗(yàn)數(shù)據(jù)是隨機(jī)的,但在實(shí)際應(yīng)用中,驗(yàn)證效果還有待進(jìn)一步研究。當(dāng)元素與集合的數(shù)量很小時(shí),SRA-MGA算法的解決方案是最小覆蓋,但這一結(jié)論還沒有被證實(shí)。如何更好地將SRA-MGA算法被應(yīng)用在其他方面,以及如何改進(jìn),這些都是有待進(jìn)一步研究的新問(wèn)題。

[1]Michael R Garey.Computers and Intractability-A Guide to the Theory of NP-Completeness[M].Calif:W.H.Freeman&Co.,San Francisco,1979:71.

[2]吳信東.Optimiaztion problems in extension matrixes[J].Science in China Ser.A1992,35(3):363-373.

[3]吳信東.Inductive learning algorithms and frontiers[J].Artificial Intelligence,1993(7):93-108.

[4]陳亮,任世軍.一種遺傳算法在集合覆蓋問(wèn)題中的應(yīng)用研究[J].哈爾濱商業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2006,22(2):67-70,114.

[5]連光耀,王衛(wèi)國(guó),黃考利等.基于粒子群優(yōu)化算法的測(cè)試選擇優(yōu)化方法研究[J].計(jì)算機(jī)測(cè)量與控制,2008,16(10):1387-1389.

[6]葛洪偉,高陽(yáng).基于蟻群算法的集合覆蓋問(wèn)題[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(4):49-50.

[7]崔鵬,劉紅靜.測(cè)試集問(wèn)題的集合覆蓋貪心算法的深入近似[J].軟件學(xué)報(bào),2006,17(7):1494-1500.

[8]J.E.Beasley.A lagrangian heuristic for set-covering problems[J].Naval Research Logistics,1990,37(1):151-164.

[9]J.E.Beasley,P.C.Chu.A genetic algorithm for the set covering problem[J].European Journal of Operational Research,1996,94:392-404.

[10]Alberto Caprara,Matteo Fischetti,Paolo Toth.A heuristic method for the set covering problem[J].Operations Research,1999,47(5):730-743.

[11]M.L.Fisher,P.Kedia.Optimal solution of set covering/partitioning problems using dual heuristics[J].Management Science,1990,36:674-688.

[12]Petr Slavik.A Tight Analysis of the Greedy Algorithm for Set Cover[J].Journal ofAlgorithms,1997,25(2):237-254.

[13]Uriel Feige.A Threshold of ln n for Approximating Set Cover[J].Journal of theACM,1998,45(4):634-652.

[14]高陽(yáng).基于蟻群算法的集合覆蓋問(wèn)題求解及其應(yīng)用研究[D].無(wú)錫:江南大學(xué),2007:41-43.

[15]馮富寶.集合覆蓋問(wèn)題研究[D].濟(jì)南:山東大學(xué),2006:21-30.

[16]葉靜.大規(guī)模數(shù)據(jù)集邏輯逆向綜合關(guān)鍵算法的研究[D].鄭州:解放軍信息工程大學(xué),2009:55-65.

[17]趙大勝.無(wú)線傳感網(wǎng)絡(luò)廣播與節(jié)點(diǎn)休眠算法中的節(jié)能覆蓋問(wèn)題研究[D].武漢:華中科技大學(xué),2005:81-86.

猜你喜歡
適應(yīng)度算子遺傳算法
改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法
擬微分算子在Hp(ω)上的有界性
各向異性次Laplace算子和擬p-次Laplace算子的Picone恒等式及其應(yīng)用
一類Markov模算子半群與相應(yīng)的算子值Dirichlet型刻畫
基于自適應(yīng)遺傳算法的CSAMT一維反演
一種基于遺傳算法的聚類分析方法在DNA序列比較中的應(yīng)用
基于遺傳算法和LS-SVM的財(cái)務(wù)危機(jī)預(yù)測(cè)
Roper-Suffridge延拓算子與Loewner鏈
基于空調(diào)導(dǎo)風(fēng)板成型工藝的Kriging模型適應(yīng)度研究
基于改進(jìn)的遺傳算法的模糊聚類算法
邵阳市| 浙江省| 隆安县| 江门市| 宣城市| 沈阳市| 江安县| 榆社县| 类乌齐县| 崇仁县| 长武县| 竹山县| 庆城县| 武夷山市| 永年县| 威宁| 内丘县| 阿鲁科尔沁旗| 安仁县| 靖边县| 葵青区| 中阳县| 内丘县| 东方市| 祁东县| 上虞市| 托克逊县| 永吉县| 土默特右旗| 肥乡县| 招远市| 达尔| 夏津县| 乌苏市| 长泰县| 通山县| 光泽县| 荣成市| 琼海市| 叙永县| 珠海市|