基于遺傳算法的集合覆蓋問(wèn)題scp

基于遺傳算法的集合覆蓋問(wèn)題scp

20世紀(jì)70年代，美國(guó)密根大學(xué)的約翰霍拉德教授提出了一種算法，該算法用于研究自然和人工系統(tǒng)的自適應(yīng)行為。在此基礎(chǔ)上，通過(guò)學(xué)生knehdejang和大衛(wèi)戈?duì)柌裨诟鞣N優(yōu)化問(wèn)題上的改進(jìn)和普及，這種遺傳統(tǒng)計(jì)方法可以廣泛應(yīng)用于各種優(yōu)化問(wèn)題。遺傳統(tǒng)計(jì)作為一種新的優(yōu)化搜索算法，與傳統(tǒng)的優(yōu)化算法相比，具有適應(yīng)性強(qiáng)、抗干擾性強(qiáng)、魯棒性強(qiáng)、適合執(zhí)行和整體搜索等顯著特征。近年來(lái)，它引起了許多科學(xué)家的注意，越來(lái)越多的科學(xué)研究和應(yīng)用產(chǎn)生了很大的影響。它取得了許多良好的研究成果廣泛應(yīng)用于自動(dòng)控制、計(jì)算機(jī)科學(xué)、機(jī)器人學(xué)、模式識(shí)別和神經(jīng)網(wǎng)絡(luò)等領(lǐng)域。集合覆蓋問(wèn)題(SCP)是經(jīng)典組合優(yōu)化問(wèn)題之一,被廣泛應(yīng)用到航空的人員行程安排、電路設(shè)計(jì)、運(yùn)輸?shù)能囕v路線安排等領(lǐng)域.該問(wèn)題已被證明是一個(gè)NP完全問(wèn)題.集合覆蓋問(wèn)題形式上可以描述如下:令A(yù)=(aij)是一個(gè)m行,n列的0-1矩陣.C=(cj)是一個(gè)n維整數(shù)向量.令M={1,…,m},N={1,…,n}表示矩陣A的行向量和列向量.值cj(j∈N)表示列j的代價(jià).不失一般性,我們假定cj>0,j∈N.如果aij=1,我們則認(rèn)為列j∈N覆蓋了行i∈M.集合覆蓋問(wèn)題(SCP)要求一個(gè)最小代價(jià)的子集合S?N,這樣每一行i∈M至少被一列j∈S覆蓋.SCP的一個(gè)自然的數(shù)學(xué)模型可以描述如下:v(SCΡ)=min∑j∈Νcjxj,(1)v(SCP)=min∑j∈Ncjxj,(1)服從于∑j∈Νaijxj≥1,j∈Μ,(2)xj∈{0,1},j∈Ν.ifj∈Sthenxj=1elsexj=0.(3)服從于∑j∈Naijxj≥1,j∈M,(2)xj∈{0,1},j∈N.ifj∈Sthenxj=1elsexj=0.(3)例如,上圖中A為一個(gè)6×8矩陣,向量C為矩陣A的列向量代價(jià)值.向量x為矩陣A的一個(gè)集合覆蓋,而本例的最小覆蓋為x=(0,0,0,1,0,1,0,1),代價(jià)為15.1基于啟發(fā)式遺傳計(jì)算的方法1.1遺傳算法步驟遺傳算法是一種基于生物進(jìn)化原理構(gòu)想出來(lái)的搜索最優(yōu)解的仿生算法,它模擬基因重組與進(jìn)化的自然過(guò)程,把待解決問(wèn)題的參數(shù)編成二進(jìn)制碼或十進(jìn)制碼(也可編成其它進(jìn)制碼),即基因,若干基因組成一個(gè)染色體(個(gè)體).許多染色體進(jìn)行類似于自然選擇、配對(duì)交叉和變異運(yùn)算,經(jīng)過(guò)多次重復(fù)迭代(即世代遺傳)直至得到最后的優(yōu)化結(jié)果.遺傳算法的步驟如下:1)初始化第0代種群P0;2)對(duì)第i代種群Pi迭代執(zhí)行步驟(i)～(v),直到滿足停止準(zhǔn)則;(i)計(jì)算Pi中每個(gè)個(gè)體的適應(yīng)值,并按照適應(yīng)值的大小對(duì)所有個(gè)體進(jìn)行排序;(ii)將Pi中適應(yīng)值最佳的個(gè)體加入Pi+1;(iii)按照適應(yīng)值的大小順序在Pi中選擇兩個(gè)父體;(iv)按概率選擇雜交算子或變異算子對(duì)兩父體進(jìn)行遺傳操作,將生成的個(gè)體加入Pi+1;(v)如果Pi+1的規(guī)模已經(jīng)與Pi持平則i←i+1并轉(zhuǎn)2,否則轉(zhuǎn)iii;3)將最終種群中適應(yīng)值最佳的個(gè)體作為遺傳算法的結(jié)果.1.2基于遺傳交叉的啟動(dòng)算法1.2.1優(yōu)化染色體結(jié)構(gòu)對(duì)于特殊應(yīng)用問(wèn)題的遺傳算法的設(shè)計(jì)第一步是設(shè)計(jì)一種合適的表示方案.對(duì)于集合覆蓋問(wèn)題,因?yàn)榫仃嘇是0-1矩陣,向量x的元素也是0或1,因?yàn)橛?-1二進(jìn)制表示是一個(gè)顯而易見的選擇.這里我們用一個(gè)n位的二進(jìn)制串作為染色體結(jié)構(gòu),這里n是矩陣A的列數(shù),第i位的值“1”意味著第i列被選擇.用二進(jìn)制表示進(jìn)行遺傳操作有個(gè)重要問(wèn)題要必須考慮,那就是可能產(chǎn)生不可靠的結(jié)果.產(chǎn)生的染色體并不能覆蓋集合,這樣就會(huì)影響遺傳效率.有兩種方法處理這種不可靠結(jié)果.一種方法是應(yīng)用一個(gè)類似懲罰函數(shù)去處理不可行的解決方案,比如比較極端的懲罰方法是丟棄該染色體,并產(chǎn)生新染色體來(lái)代替這個(gè)不可靠染色體.另一個(gè)方法是設(shè)計(jì)一個(gè)啟發(fā)操作算子,把不可行的染色體轉(zhuǎn)變成可行的染色體.我們選擇后一個(gè)方法,用啟發(fā)式操作,因?yàn)橐粋€(gè)好的懲罰函數(shù)經(jīng)常很難定義.1.2.2性能代價(jià)比優(yōu)先算法正如上邊所提起的,由于變異操作引起的染色體并不適合問(wèn)題集合(如,一些行沒(méi)有覆蓋),這導(dǎo)致遺傳算法收斂的速度變慢,因此需要讓所有染色體有個(gè)合理的補(bǔ)充操作.這里,我們提出一個(gè)啟發(fā)式操作算子,這個(gè)算子不僅僅保持所產(chǎn)生的染色體的可靠性,而且提供一個(gè)額外的局部?jī)?yōu)化過(guò)程,目的使遺傳算法更有效率.對(duì)于每個(gè)染色體所覆蓋集合的情況不外乎兩種情況:一種是染色體不覆蓋集合,另一種是覆蓋了集合,但有冗余,造成改染色體的代價(jià)不是較優(yōu).對(duì)于第一種情況的處理辦法一種是丟棄,但有可能丟失最優(yōu)解,導(dǎo)致收斂的速度變慢;本算法采用的是另一種解決方法,通過(guò)性能代價(jià)比較優(yōu)的列來(lái)彌補(bǔ)該染色體,使該染色體以較優(yōu)代價(jià)保留在種群中.性能代價(jià)比是指某列所能覆蓋的行數(shù)與該列的代價(jià)比.對(duì)于第二種情況,本算法采用的是通過(guò)保留性能代價(jià)比較優(yōu)且能覆蓋集合的列,去除多余的冗余列來(lái)替代該冗余染色體,并保留在種群中.具體的算法如下.·修補(bǔ)染色體.對(duì)于一個(gè)染色體,很容易判斷是否覆蓋一個(gè)集合.如果不覆蓋集合,染色體在遺傳進(jìn)化過(guò)程中不利于收斂,因此通過(guò)修補(bǔ)染色體使之能覆蓋集合是一個(gè)很好的辦法.修補(bǔ)染色的方法很多,如果修補(bǔ)后的染色體的代價(jià)過(guò)大,就會(huì)產(chǎn)生過(guò)多的冗余,就會(huì)造成另一個(gè)極端.早期有人提出用貪心算法來(lái)補(bǔ)償染色體,但這種算法只考慮染色體中基因的代價(jià)而并沒(méi)有考慮到染色體中的基因在集合中的性能.本算法采用一個(gè)性能代價(jià)比優(yōu)先算法找出更適合的基因來(lái)補(bǔ)償染色體,使得補(bǔ)償后的染色體為較優(yōu)的染色體.這里說(shuō)的性能指染色體中的某位基因所對(duì)應(yīng)集合中的列的含1的個(gè)數(shù),如果該列含1的個(gè)數(shù)多,則該列覆蓋的行數(shù)就多,說(shuō)明該基因的性能比較高.采用同樣的方法就可以找出其他位置的基因就可以覆蓋集合.為了找出較優(yōu)的染色體,還要考慮每個(gè)基因的代價(jià),所以對(duì)于每個(gè)基因采用公式f(j)=(r∑i=0Aij)/cjf(j)=(∑i=0rAij)/cj來(lái)計(jì)算基因的性能代價(jià)比,其中r表示集合A的行數(shù),cj為第j列的代價(jià).性能代價(jià)比較高的基因優(yōu)先選擇,從而保證補(bǔ)償后的染色體能覆蓋集合且代價(jià)較優(yōu).該算法如下.令I(lǐng):所有行的集合;J:所有列的集合;U:未覆蓋A的行的集合;Col:集合A的列數(shù);Pj:新增加一個(gè)染色體中的基因位置,j∈J對(duì)于每個(gè)新產(chǎn)生的未覆蓋集合的染色體進(jìn)行如下處理:1)產(chǎn)生該染色體的U;2)?i?i∈U,Ρ(k)=min(Col∑j=1Aij/cj),k∈J2)?i?i∈U,P(k)=min(∑j=1ColAij/cj),k∈J;3)對(duì)每一個(gè)k,修補(bǔ)該染色體;4)如果修補(bǔ)后的染色體不覆蓋,轉(zhuǎn)到1.·消除染色體的冗余.一個(gè)染色體含有“1”的基因的多少對(duì)該染色體覆蓋集合A的狀況有很大關(guān)系,如果含“1”不多,很可能不能覆蓋集合A,如果含“1”過(guò)多,則該染色體的代價(jià)也相應(yīng)過(guò)大.這樣的染色體經(jīng)過(guò)遺傳操作后,并不利于收斂到較優(yōu)解.為了使染色體在種群中的效率較高,一種采用的辦法就是消除染色體中冗余基因,使得消除后的染色體還能覆蓋集合A,并使該染色體的代價(jià)減小.本算法采用性能代價(jià)比優(yōu)先方法.為了更有效率的找出冗余基因,我們根據(jù)集合A和染色體含“1”基因的位置產(chǎn)生兩個(gè)中間向量,通過(guò)對(duì)該中間向量的操作找出其中較優(yōu)的基因,并刪除其余冗余的基因.一個(gè)中間向量a用染色體中含“1”基因的位置來(lái)表示,另一個(gè)中間向量b用來(lái)表示中間向量a中選中一個(gè)性能代價(jià)比較優(yōu)的基因后沒(méi)有覆蓋集合A的行號(hào).依次根據(jù)性能代價(jià)比找出較優(yōu)的基因,計(jì)算中間向量b,中間向量a中的基因被選中后就在向量a中刪除該基因,因隨著中間向量a中被選種的基因增多,中間向量b的個(gè)數(shù)減少,直到中間向量b為空,表示所選的基因覆蓋了集合A.1)計(jì)算向量a中每個(gè)基因的性能代價(jià)比;選出性能代價(jià)比最大的基因,記錄該基因在染色體中的位置并初始化中間向量a;2)根據(jù)該性能代價(jià)比最大的基因計(jì)算出未覆蓋集合A的行號(hào),并初始化中間向量b;3)計(jì)算中間向量a中每個(gè)基因的性能代價(jià)比并選出最大的基因;4)計(jì)算該基因覆蓋集合的行號(hào),并在向量b中去除這些行號(hào);5)在中間向量a中刪除該基因;6)如果中間向量b不空,則跳轉(zhuǎn)到3;7)如果中間向量b為空,則讓未被選出的含“1”基因變異成“0”.2遺傳參數(shù)的選擇2.1種群數(shù)目的影響在應(yīng)用遺傳算法解決實(shí)際問(wèn)題的過(guò)程中人們發(fā)現(xiàn),種群對(duì)遺傳算法所求得的解的質(zhì)量有一定的影響,選擇適當(dāng)?shù)姆N群大小可以提高算法的性能.種群數(shù)目如果過(guò)大,雖然可以在比較小的代數(shù)收斂到最優(yōu)解,但會(huì)執(zhí)行效率降低.種群數(shù)目如果過(guò)小,則收斂過(guò)慢.在集合覆蓋問(wèn)題中,本算法并沒(méi)有采取對(duì)種群大小進(jìn)行嚴(yán)格的限制,對(duì)于大多數(shù)情況,一般采用染色體的長(zhǎng)度于集合密度的乘積作為種群的大小的一個(gè)大概范圍.對(duì)于一些特殊情況,如集合行、列值較小,集合密度過(guò)大的情況,則再適當(dāng)?shù)恼{(diào)整.2.2種群中染色體被選擇在父代的選擇是在種群中每個(gè)個(gè)體賦予產(chǎn)生后代的機(jī)會(huì),這有很多廣泛的可用方法,包括按比例選擇,錦標(biāo)賽選擇和輪盤賭選擇.這里選擇的是按比例選擇.種群中每個(gè)染色體被選擇的概率為pi=(1/fi)/Ν∑i=1(1/fi)pi=(1/fi)/∑i=1N(1/fi),其中fi為染色體的適應(yīng)度,N為種群大小.用這種選擇技術(shù)可以算出最大代價(jià)的染色體.但為了求最小代價(jià),我們可以采用(Col∑i=1fi)-fi(∑i=1Colfi)?fi作為染色體的適應(yīng)度,在根據(jù)按比例選擇找出父代染色體.2.3交叉率的生成交叉(crossover)是引入新個(gè)體的主要方法,在被選擇的染色體內(nèi)產(chǎn)生一個(gè)隨機(jī)數(shù)設(shè)為斷點(diǎn),將雙親在斷點(diǎn)一側(cè)的基因進(jìn)行交叉交換,生成新的后代.設(shè)置一個(gè)交叉率(pc)用來(lái)控制交配池中參與交叉的染色體個(gè)數(shù),一定的交叉率可以保證交配池中不斷產(chǎn)生新個(gè)體,但又不至于新個(gè)體數(shù)目太多,導(dǎo)致遺傳秩序遭到破壞.交叉的方法也有很多,不同的交叉方法對(duì)應(yīng)的交叉率也是不一致的,因本算法是對(duì)染色體進(jìn)行啟發(fā)式修改,不同的交叉方法對(duì)種群的影響相近.因此本算法采用單點(diǎn)一致交叉,交叉率經(jīng)測(cè)試采用0.6較為適宜.2.4變異率范圍的確定變異(mutation)是產(chǎn)生新個(gè)體的另一種途徑,它是染色體上的基因發(fā)生突變的過(guò)程,可以提供初始種群中不存在的基因,為種群提供新的內(nèi)容.變異產(chǎn)生的是真正意義上的新個(gè)體,使得個(gè)體可以盡可能的覆蓋整個(gè)搜索空間,保證遺傳算法具有全局搜索功能.變異率是一個(gè)種群中發(fā)生變異的基因數(shù)目與全體基因數(shù)的比值.在應(yīng)用遺傳算法解決不同問(wèn)題時(shí),選取運(yùn)行的變異率是影響算法效率的重要因素.控制一個(gè)合理水平的變異率既可獲得新基因,又不會(huì)失去從雙親繼承的好的特性.對(duì)于集合覆蓋問(wèn)題,采用對(duì)多個(gè)不同集合應(yīng)用本算法求解,根據(jù)變異率和集合覆蓋值建立坐標(biāo)系,近似描繪變異率對(duì)集合覆蓋影響的曲線.因?yàn)椴煌募蠈?duì)應(yīng)的函數(shù)覆蓋值的大小不同,為了顯示方便,根據(jù)函數(shù)覆蓋值范圍轉(zhuǎn)換成0,1之間.根據(jù)計(jì)算的離散點(diǎn)模擬曲線.如圖1為測(cè)試幾個(gè)不同集合的圖象,這些集合在后邊有說(shuō)明,見圖1.根據(jù)圖1,對(duì)于不同的集合,都可用下邊方程來(lái)模擬此曲線:其中r為集合的行數(shù),Col為集合的列數(shù)當(dāng)r≥Col則y=Col/r*x+1/Col*1/xr<Col則y=Col/r*(1-x)+1/Col*1/(1-x)從圖像上可以看出,為了得到最優(yōu)解的變化率范圍就是在曲線的最小值附近,令y=0,解得當(dāng)r≥Col?x=√r/Colr≥Col?x=r/Col?????√,當(dāng)r＜Col?x=1-√r/Colr＜Col?x=1?r/Col?????√.可見,較優(yōu)的變異率范圍由上式確定.2.5是否收斂的理論的終止條件遺傳算法在實(shí)際操作中都要經(jīng)過(guò)多代進(jìn)化,直到適應(yīng)值趨于穩(wěn)定,或者找到最優(yōu)解或者達(dá)到規(guī)定的遺傳代數(shù),進(jìn)化過(guò)程結(jié)束.由于遺傳算法不包含目標(biāo)函數(shù)的梯度等信息,所以在進(jìn)化過(guò)程中無(wú)法確定個(gè)體在解空間的位置,也就無(wú)法給出是否收斂的理論判據(jù).通常的做法是在達(dá)到預(yù)先規(guī)定的進(jìn)化代數(shù)時(shí)停止進(jìn)化,本文采用的就是這種做法,最大進(jìn)化代數(shù)定為1000代.但是也可以采用其他的停止準(zhǔn)則,例如當(dāng)相鄰兩代的最佳適應(yīng)值之差小于某個(gè)事先確定的閾值時(shí)停止進(jìn)化.3測(cè)試集合的細(xì)節(jié)本文提出的算法用c語(yǔ)言進(jìn)行編寫,并在主頻1G,內(nèi)存2G的PC機(jī)上運(yùn)行.被測(cè)試的集合采用JEBeasley在OR-Library提供的測(cè)試集合,地址在http://mscmga.ms.ic.ac.uk/info.html提供的.這些測(cè)試集合的細(xì)節(jié)在下表中給出.對(duì)于scpcyc06集合,采用的種群大小為10,通過(guò)采用不同的交叉率、變異率,計(jì)算出的最小代價(jià)值.根據(jù)下邊的計(jì)算結(jié)果,我們發(fā)現(xiàn)較好的交叉率在0.6左右.scp42集合為行大于列的結(jié)合,scpcyc07集合為列大于行的集合,根據(jù)這兩個(gè)集合測(cè)試,對(duì)于不同的種群大小,相同的交叉率,我們發(fā)現(xiàn)變異率和最小代價(jià)的關(guān)系符合圖1的結(jié)果.下表為采用啟發(fā)式遺傳算法和未采用啟發(fā)式遺傳算法所計(jì)算最小代價(jià)