..第四章遺傳算法與組合優(yōu)化4.1背包問題〔knapsackproblem4.1.1問題描述0/1背包問題：給出幾個尺寸為S1,S2,…,Sn的物體和容量為C的背包,此處S1,S2,…,Sn和C都是正整數(shù)；要求找出n個物件的一個子集使其盡可能多地填滿容量為C的背包。數(shù)學(xué)形式：最大化 滿足 廣義背包問題：輸入由C和兩個向量C＝<S1,S2,…,Sn>和P＝<P1,P2,…,Pn>組成。設(shè)X為一整數(shù)集合,即X＝1,2,3,…,n,T為X的子集,則問題就是找出滿足約束條件,而使獲得最大的子集T,即求Si和Pi的下標(biāo)子集。在應(yīng)用問題中,設(shè)S的元素是n項經(jīng)營活動各自所需的資源消耗,C是所能提供的資源總量,P的元素是人們從每項經(jīng)營活動中得到的利潤或收益,則背包問題就是在資源有限的條件下,追求總的最大收益的資源有效分配問題。廣義背包問題可以數(shù)學(xué)形式更精確地描述如下：最大化 滿足 背包問題在計算理論中屬于NP—完全問題,其計算復(fù)雜度為O<2n>,若允許物件可以部分地裝入背包,即允許X,可取從0.00到1.00閉區(qū)間上的實(shí)數(shù),則背包問題就簡化為極簡單的P類問題,此時計算復(fù)雜度為O<n>。4.1.2遺傳編碼采用下標(biāo)子集T的二進(jìn)制編碼方案是常用的遺傳編碼方法。串T的長度等于n<問題規(guī)模>,Ti<1≤i≤n>＝1表示該物件裝入背包,Ti＝0表示不裝入背包?；诒嘲鼏栴}有近似求解知識,以及考慮到遺傳算法的特點(diǎn)〔適合短定義距的、低階的、高適應(yīng)度的模式構(gòu)成的積木塊結(jié)構(gòu)類問題,通常將Pi,Si按Pi/Si值的大小依次排列,即P1/S1≥P2/S2≥…≥Pn/Sn。4.1.3適應(yīng)度函數(shù)在上述編碼情況下,背包問題的目標(biāo)函數(shù)和約束條件可表示如下。目標(biāo)函數(shù)：約束條件：按照利用懲罰函數(shù)處理約束條件的方法,我們可構(gòu)造背包問題的適應(yīng)度函數(shù)f<T>如下式：f<T>=J<T>+g<T>式中g(shù)<T>為對T超越約束條件的懲罰函數(shù),懲罰函數(shù)可構(gòu)造如下:式中Em為Pi/S<1≤i≤n>i的最大值,β為合適的懲罰系數(shù)。4.2貨郎擔(dān)問題〔TravelingSalesmanProblem——TSP在遺傳其法研究中,TSP問題已被廣泛地用于評價不同的遺傳操作及選擇機(jī)制的性能。之所以如此,主要有以下幾個方面的原因：TSP問題是一個典型的、易于描述卻難以處理的NP完全〔NP-complete問題。有效地解決TSP問題在可計算理論上有著重要的理論價值。TSP問題是諸多領(lǐng)域內(nèi)出現(xiàn)的多種復(fù)雜問題的集中概括和簡化形式。因此,快速、有效地解決TSP問題有著極高的實(shí)際應(yīng)用價值。TSP問題因其典型性已成為各種啟發(fā)式的搜索、優(yōu)化算法的間接比較標(biāo)準(zhǔn),而遺傳算法就其本質(zhì)來說,主要是處理復(fù)雜問題的一種魯棒性強(qiáng)的啟發(fā)式隨機(jī)搜索算法。因此遺傳算法在TSP問題求解方面的應(yīng)用研究,對于構(gòu)造合適的遺傳算法框架、建立有效的遺傳操作以及有效地解決TSP問題等有著多方面的重要意義。問題描述：尋找一條最短的遍歷n個城市的路徑,或者說搜索整數(shù)子集X＝{1,2,…,n}〔X的元素表示對n個城市的編號的一個排列π<X>={v1,v2,…,vn},使取最小值。式中的d<vi,vi+1>表示城市vi到城市vi+1的距離。4.2.1編碼與適應(yīng)度函數(shù)編碼以遍歷城市的次序排列進(jìn)行編碼。如碼串12345678表示自城市l(wèi)開始,依次經(jīng)城市2,3,4,5,6,7,8,最后返回城市1的遍歷路徑。顯然,這是一種針對TSP問題的最自然的編碼方式。這一編碼方案的主要缺陷在于引起了交叉操作的困難。采用"邊"的組合方式進(jìn)行編碼。例如碼串24536871的第1個碼2表示城市1到城市2的路徑在TSP圈中,第2個碼4表示城市2到城市4的路徑在TSP圈中,以此類推,第8個碼1表示城市7到城市1的路徑在TSP圈中。間接"節(jié)點(diǎn)"編碼方式。以消除"一點(diǎn)交叉"策略〔或多點(diǎn)交叉策略引起的非法路徑問題。碼串長度仍為n,定義各等位基因的取值范圍為〔n–i+1,i為基因序號,解碼時,根據(jù)相應(yīng)基因位的取值,從城市號集合中不回放地取一個城市號,直至所有城市號被取完。由于這種編碼方式特征遺傳性較差,因此現(xiàn)行的研究中很少采用。適應(yīng)度函數(shù)適應(yīng)度函數(shù)常取路徑長度Td的倒數(shù),即f＝1/Td若結(jié)合TSP的約束條件〔每個城市經(jīng)過且只經(jīng)過一次,則適應(yīng)度函數(shù)可表示為：f＝1/<Td+α*Nt>,其中Nt是對TSP路徑不合法的度量<如取付Nt為未遍歷的城市的個數(shù)>,α為懲罰系數(shù),常取城市間最長距離的兩倍多一點(diǎn)<如2.05*dmax>。4.2.2交叉策略問題：基于TSP問題的順序編碼〔其它編碼如以邊的組合狀態(tài)進(jìn)行編碼也呈現(xiàn)相似特性,若采取簡單的一點(diǎn)交叉或多點(diǎn)交叉策略,必然以極大的概率導(dǎo)致未能完全遍歷所有城市的非法路徑。如8城市的TSP問題的兩個父路徑為1234|56788765|4321若采取一點(diǎn)交叉,且交叉點(diǎn)隨機(jī)選為4,則交叉后產(chǎn)生的兩個后代為8765567812344321顯然,這兩個子路徑均未能遍歷所有8個城市,都違反TSP問題的約束條件?？梢圆扇∩鲜鰳?gòu)造懲罰函數(shù)的方法,但試驗效果不佳?？赡艿慕忉專哼@一方法將本已十分復(fù)雜的TSP問題更加復(fù)雜化了。因為滿足TSP問題約束條件的可行解空間規(guī)模為n!；而按構(gòu)造懲罰函數(shù)的方法,其搜索空間規(guī)模變?yōu)閚n；隨著n的增大n!與nn之間的差距是極其驚人的。解決這一約束問題的另一種處理方法是對交叉、變異等遺傳操作做適當(dāng)?shù)男拚?使其自動滿足TSP的約束條件。常用的幾種交叉方法：1．部分匹配交叉<PMX,PartiallyMatchedCrossover>法PMX操作是由Goldberg和Lingle于1985年提出的。在PMX操作中,先依據(jù)均勻隨機(jī)分布產(chǎn)生兩個位串交叉點(diǎn),定義這兩點(diǎn)之間的區(qū)域為一匹配區(qū)域,并使用位置交換操作交換兩個父串的匹配區(qū)域。實(shí)例：如兩父串及匹配區(qū)域為A＝984|567|1320B＝871|230|9546首先交換A和B的兩個匹配區(qū)域,得到A’＝984|230|l320B’＝871|567|9546對于A’、B’兩子串中匹配區(qū)域以外出現(xiàn)的遍歷重復(fù),依據(jù)匹配區(qū)域內(nèi)的位置映射關(guān)系,逐一進(jìn)行交換。對于A’有2到5,3到6,0到7的位置符號映射,對A’的匹配區(qū)以外的2,3,0分別以5,6,7替換,則得A"＝984|230|1657同理可得：B"＝801|567|9243這樣,每個子串的次序部分地由其父串確定。2．順序交叉法<OX,OrderCrossover>法與PMX法相似,Davis<1985>等人提出了一種OX法,此方法開始也是選擇一個匹配區(qū)域：A＝984|567|1320B＝871|230|9546并根據(jù)匹配區(qū)域的映射關(guān)系,在其區(qū)域外的相應(yīng)位置標(biāo)記H,得到A’＝984|567|1HHHB’＝8H1|230|9H4H再移動匹配區(qū)至起點(diǎn)位置,且在其后預(yù)留相等于匹配區(qū)域的空間<H數(shù)目>,然后將其余的碼按其相對次序排列在預(yù)留區(qū)后面,得到A"＝567HHH1984B"＝230HHH9481最后將父串A,B的匹配區(qū)域相互交換,并放置到A",B"的預(yù)留區(qū)內(nèi),即可得到兩個子代：A"’＝567|230|1984B"’＝230|567|9481雖然,PMX法與OX法非常相似,但它們處理相似特性的手段卻不同。PMX法趨向于所期望的絕對城市位置,而OX法卻趨向于期望的相對城市位置。3．循環(huán)交叉〔CX,cyclecrossover法Smith等人提出的CX方法與PMX方法和OX方法有不同之處。循環(huán)交叉的執(zhí)行是以父串的特征作為參考,使每個城市在約束條件下進(jìn)行重組。假設(shè)兩個個體：A＝123456789B＝412876935進(jìn)行交叉。以后代A’為例說明生成后代的過程：<1>從A中取第一個元素填人A’的第一個位置：A’＝1########<2>B的第一個元素為"4",則在A中查找"4"的位置,并將它填入A’相應(yīng)的位置中：A’＝1##4#####<3>B的第四個元素為"8",則在A中查找"8"的位置,并將它填入A’相應(yīng)的位置中：A’＝1##4###8#<4>B的第八個元素為"3",則在A中查找"3"的位置,并將它填入A’相應(yīng)的位置中：A’＝1#34###8#<5>B的第三個元素為"2",則在A中查找"2"的位置,并將它填人A’相應(yīng)的位置中:A’＝1234###8#<6>B的第二個元素為"1",而"1"在A’中已經(jīng)出現(xiàn),這樣就構(gòu)成了一個循環(huán)。此時將剩下的位置填入B中對應(yīng)位置的值：A’＝123476985同理,若以A為參照,可以得到B’。最后交叉所得的后代為：A’＝123476985B’＝412856739循環(huán)交叉算子的特點(diǎn)是保留了父代個體中序列的絕對位置。4．基于知識的交叉方法這種方法是一種啟發(fā)式的交叉方法,按以下規(guī)劃構(gòu)造后代：<1>隨機(jī)地選取一個城市作為子代圈的開始城市。<2>比較父串中與開始城市鄰接的邊,選取最小的邊添加到圈的路徑中。<3>重復(fù)第<2>步,如果發(fā)現(xiàn)按最小邊選取的規(guī)劃產(chǎn)生非法路徑<重復(fù)經(jīng)過同一城市>,則按隨機(jī)法產(chǎn)生一合法的邊,如此反復(fù),直至形成一完整的TSP圈。使用這一方法,可獲得較好的結(jié)果。不過,這一方法使用了基于問題的一些知識,損失了遺傳算法的通用性和魯棒性。關(guān)于TSP問題的遺傳交叉方法還有各種各樣的變形方法,一般來說,交叉方法應(yīng)能使父串的待征遺傳給子串,子串應(yīng)能部分或全部地繼承父串的結(jié)構(gòu)特征和有效基因。4.2.3變異技術(shù)從遺傳算法的觀點(diǎn)來看,解的進(jìn)化主要靠選擇機(jī)制和交叉策略來完成,變異只是為選擇、交叉過程中可能丟失的某些遺傳基因進(jìn)行修復(fù)和補(bǔ)充,變異在遺傳算法的全局意義上只是一個背景操作。針對TSP問題,主要的變異技術(shù)如下：1．位點(diǎn)變異變異僅以一定的概率〔通常較小對串的某些位作值的變異。2．逆轉(zhuǎn)變異在串中隨機(jī)選擇兩點(diǎn),再將這兩點(diǎn)內(nèi)的子串按反序插入到原位置中,如串A的逆轉(zhuǎn)點(diǎn)為3,6,則經(jīng)逆轉(zhuǎn)后,變?yōu)锳’A＝123|456|7890A’＝123|654|78903．對換變異隨機(jī)選擇串中的兩點(diǎn),交換其值〔碼。對于串AA＝123456789若對換點(diǎn)為4,7,則經(jīng)對換后,A’為A’＝1237564894．插人變異從串中隨機(jī)選擇1個碼,將此碼插入隨機(jī)選擇的插入點(diǎn)中間,對于上述A而言．若取插入碼為5,選取插入點(diǎn)為2~3之間．則A’＝1253467894.2.4選擇機(jī)制和群體構(gòu)成在遺傳算法中,最常見的選擇機(jī)制是適應(yīng)度比例選擇機(jī)制；在有限規(guī)模的群體中,適應(yīng)度較高的個體有較大的機(jī)會繁殖后代,即生物進(jìn)化論上的適者生存規(guī)則。在新一代群體構(gòu)成方法方面存在：N方式：全部替換上一代群體的全刷新代際更新方式。E方式：保留一個最好的父串的最佳保留〔elitist群體構(gòu)造方式。G方式：按一定比例更新群體中的部分個體的部分更新方式〔或稱代溝方法,這種情況的極端是每代僅刪去一個最不適的個體的最劣死亡方式。B方式：從產(chǎn)生的子代和父代中挑選最好的若干個個體的群體構(gòu)成形式。從群體規(guī)模來看,有變化規(guī)模的方式,也有恒定規(guī)模的群體構(gòu)成方式等。一般講,N方式的全局搜索性能最好,但收斂速度最慢；B方式收斂速度最快,但全局搜索性能最差；E方式和G方式的性能介于N方式和B方式之間。在求解貨郎擔(dān)問題的應(yīng)用中,多選用E方式。4.2.5基于遺傳算法求解TSP的算法實(shí)現(xiàn)1．編碼與適應(yīng)度函數(shù)我們以n城市的遍歷次序作為遺傳算法的編碼,適應(yīng)度函數(shù)取為路徑長度的倒數(shù)〔無懲罰函數(shù)。2．選擇機(jī)制用隨機(jī)方法產(chǎn)生初始種群。適應(yīng)度比例選擇,E方式〔精英保留產(chǎn)生新一代種群。3．交叉方法選用的交叉方法與OX法有點(diǎn)類似,現(xiàn)介紹如下：<1>隨機(jī)在串中選擇一個交配區(qū)域,如兩父串及交配區(qū)域選定為A＝12|3456|789B＝98|7654|321<2>將B的交配區(qū)域加到A的前面或后面,A的交配區(qū)域加到B的前面或后面得到A’＝7654|123456789B’＝3456|987654321<3>在A’中自交配區(qū)域后依次刪除與交配區(qū)相同的城市碼,得到最終的兩子串為A’＝765412389B’＝3456987214．變異技術(shù)采取連續(xù)多次對換的變異技術(shù),使可行解有較大的順序排列上的變化,以抑制"進(jìn)化逆轉(zhuǎn)"的同化作用。變異操作發(fā)生的概率取得比較小〔1%左右,一旦變異操作發(fā)生,則用隨機(jī)方法產(chǎn)生交換次數(shù)K,對所需變異操作的串進(jìn)行K次對換〔對換的兩碼位也是隨機(jī)產(chǎn)生的。5．"進(jìn)化逆轉(zhuǎn)"操作引入"進(jìn)化逆轉(zhuǎn)"操作的主要目的是改善遺傳算法的局部搜索能力。在針