5遺傳算法與組合優(yōu)化

1、第五章遺傳算法與組合優(yōu)化5.1 背包問題(knapsack problem)5.1.1問題描述0/1背包問題：給出幾個(gè)尺寸為S , S ,，S的物體和容量為C的背包，此處S , S ,， Sn和C都是正整數(shù)；要求找出n個(gè)物件何一個(gè)子集使其盡可能多地填滿容量為C的背包。數(shù)學(xué)形式：最大化W S Xi 二1滿足 W S X C, X . e 0,1, 1 i ni二1廣義背包問題：輸入由c和兩個(gè)向量c=(sS2，S)和p=(pp2，p)組成。 設(shè)X為一整數(shù)集合，即X=1，2，3，n，T為X的子集；則問題就是找出滿足約束條件 W X C，而使W P獲得最大的子集T，即求S和P.的下標(biāo)子集。iiieTi

2、eT在應(yīng)用問題中，設(shè)S的元素是n項(xiàng)經(jīng)營活動(dòng)各自所需的資源消耗，C是所能提供的資源總 量，P的元素是人們從每項(xiàng)經(jīng)營活動(dòng)中得到的利潤或收益，則背包問題就是在資源有限的條 件下，追求總的最大收益的資源有效分配問題。廣義背包問題可以數(shù)學(xué)形式更精確地描述如下：最大化W P Xi 二1滿足 W S X C, X & 0,1, 1 i ni二1背包問題在計(jì)算理論中屬于NP一完全問題，其計(jì)算復(fù)雜度為O(2n)，若允許物件可以部分 地裝入背包，即允許X，可取從0.00到1.00閉區(qū)間上的實(shí)數(shù)，則背包問題就簡化為極簡單 的P類問題，此時(shí)計(jì)算復(fù)雜度為O(n)。5.1.2遺傳編碼采用下標(biāo)子集T的二進(jìn)制編碼方案是常用的

3、遺傳編碼方法。串T的長度等于n (問題規(guī)模), T (1忍i忍n) =1表示該物件裝入背包，T =0表示不裝入背包?；诒嘲鼏栴}有近似求解知識， 以及考慮到遺傳算法的特點(diǎn)(適合短定義距的、低階的、高適應(yīng)度的模式構(gòu)成的積木塊結(jié)構(gòu) 類問題)，通常將P , S按P/S值的大小依次排列，即P/S NP/S NNP/S。i i i i1122n n5.1.3適應(yīng)度函數(shù)在上述編碼情況下，背包問題的目標(biāo)函數(shù)和約束條件可表示如下。目標(biāo)函數(shù)： J (T) = t Pi ii = 1約束條件：2 t S C i = 1按照利用懲罰函數(shù)處理約束條件的方法，我們可構(gòu)造背包問題的適應(yīng)度函數(shù)f(T)如下式: f(T) =

4、 J(T) + g(T)式中g(shù)(T)為對T超越約束條件的懲罰函數(shù)，懲罰函數(shù)可構(gòu)造如下：C 一。r-lC - 0式中Em為Pi/S(1in)i的最大值，0為合適的懲罰系數(shù)。5.2 貨郎擔(dān)問題(Traveling Salesman ProblemTSP)在遺傳其法研究中，TSP問題已被廣泛地用于評價(jià)不同的遺傳操作及選擇機(jī)制的性能。之 所以如此，主要有以下幾個(gè)方面的原因：TSP問題是一個(gè)典型的、易于描述卻難以處理的NP完全(NP-complete)問題。有效地解 決TSP問題在可計(jì)算理論上有著重要的理論價(jià)值。TSP問題是諸多領(lǐng)域內(nèi)出現(xiàn)的多種復(fù)雜問題的集中概括和簡化形式。因此，快速、有效地 解決TSP

5、問題有著極高的實(shí)際應(yīng)用價(jià)值。TSP問題因其典型性已成為各種啟發(fā)式的搜索、優(yōu)化算法的間接比較標(biāo)準(zhǔn)，而遺傳算法就 其本質(zhì)來說，主要是處理復(fù)雜問題的一種魯棒性強(qiáng)的啟發(fā)式隨機(jī)搜索算法。因此遺傳算法 在TSP問題求解方面的應(yīng)用研究，對于構(gòu)造合適的遺傳算法框架、建立有效的遺傳操作以 及有效地解決TSP問題等有著多方面的重要意義。問題描述：尋找一條最短的遍歷n個(gè)城市的路徑，或者說搜索整數(shù)子集X=1, 2,，n （X的元 素表示對n個(gè)城市的編號）的一個(gè)排列 （X） = vi，v2，vj,使Ji-1n H（如功+1）+ d（功皿）f-1取最小值。式中的d（v, v ）表示城市v到城市v的距離。i i+1ii+1

6、5.2.1編碼與適應(yīng)度函數(shù)編碼以遍歷城市的次序排列進(jìn)行編碼。如碼串1 2 3 4 5 6 7 8表示自城市l(wèi)開始，依次經(jīng)城市2，3，4，5，6，7，8，最后返 回城市1的遍歷路徑。顯然，這是一種針對TSP問題的最自然的編碼方式。這一編碼方案的 主要缺陷在于引起了交叉操作的困難。采用“邊”的組合方式進(jìn)行編碼。例如碼串2 4 5 3 6 8 7 1的第1個(gè)碼2表示城市1到城市2的路徑在TSP圈中，第2個(gè) 碼4表示城市2到城市4的路徑在TSP圈中，以此類推，第8個(gè)碼1表示城市8到城市1的 路徑在TSP圈中。這一編碼方式有著與前面的“節(jié)點(diǎn)”遍歷次序編碼方式相類似的缺陷。間接“節(jié)點(diǎn)”編碼方式。以消除“一

7、點(diǎn)交叉”策略（或多點(diǎn)交叉策略）引起的非法路徑問題。碼串長度仍為n，定 義各等位基因的取值范圍為（n - i + 1），i為基因序號，解碼時(shí)，根據(jù)相應(yīng)基因位的取值， 從城市號集合中不回放地取一個(gè)城市號，直至所有城市號被取完。由于這種編碼方式特征遺 傳性較差，因此現(xiàn)行的研究中很少采用。適應(yīng)度函數(shù)適應(yīng)度函數(shù)常取路徑長度Td的倒數(shù)，即f=1/Td若結(jié)合TSP的約束條件（每個(gè)城市經(jīng)過且只經(jīng)過一次），則適應(yīng)度函數(shù)可表示為：f=1/（Td +a *N，其中N是對TSP路徑不合法的度量（如取付N為未遍歷的城市的個(gè)數(shù)），a為懲罰系數(shù)， 常取城市間最長距離的兩倍多一點(diǎn)（如2.05*匕）；5.2.2交叉策略問題：基

8、于TSP問題的順序編碼（其它編碼如以邊的組合狀態(tài)進(jìn)行編碼也呈現(xiàn)相似特性）， 若采取簡單的一點(diǎn)交叉或多點(diǎn)交叉策略，必然以極大的概率導(dǎo)致未能完全遍歷所有城市的非 法路徑。如8城市的TSP問題的兩個(gè)父路徑為1 2 3 4 | 5 6 7 88 7 6 5 | 4 3 2 1若采取一點(diǎn)交叉，且交叉點(diǎn)隨機(jī)選為4,則交叉后產(chǎn)生的兩個(gè)后代為8 7 6 5 5 6 7 81 2 3 4 4 3 2 1顯然，這兩個(gè)子路徑均未能遍歷所有8個(gè)城市，都違反TSP問題的約束條件。可以采取上述構(gòu)造懲罰函數(shù)的方法，但試驗(yàn)效果不佳?？赡艿慕忉專哼@一方法將本已十分復(fù)雜的TSP問題更加復(fù)雜化了。因?yàn)闈M足TSP問題約 束條件的可行

9、解空間規(guī)模為n!；而按構(gòu)造懲罰函數(shù)的方法，其搜索空間規(guī)模變?yōu)樾?；隨著n 的增大n!與nn之間的差距是極其驚人的。解決這一約束問題的另一種處理方法是對交叉、變異等遺傳操作做適當(dāng)?shù)男拚蛊渥?動(dòng)滿足TSP的約束條件。常用的幾種交叉方法：1 .部分匹配交叉(PMX， Partially Matched Crossover)法PMX操作是由Goldberg和Lingle于1985年提出的。在PMX操作中，先依據(jù)均勻隨機(jī)分 布產(chǎn)生兩個(gè)位串交叉點(diǎn)，定義這兩點(diǎn)之間的區(qū)域?yàn)橐黄ヅ鋮^(qū)域，并使用位置交換操作交換兩 個(gè)父串的匹配區(qū)域。實(shí)例：如兩父串及匹配區(qū)域?yàn)?TOC o 1-5 h z A = 9 8 4|56

10、7|1320B = 8 7 1|230|9546首先交換A和B的兩個(gè)匹配區(qū)域，得到A=9 84|230|l320B=8 71|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”=9 8 4 | 2 3 0 | 1 6 5 7同理可得：B”=8 0 1 | 5 6 7 | 9 2 4 3這樣，每個(gè)子串的次序部分地由其父串確定。順序交叉法(OX, Order Crossover)法與PMX法相似，Davis(1985)等人提出了一種O

11、X法，此方法開始也是選擇一個(gè)匹配區(qū)域: TOC o 1-5 h z A = 9 8 4|567|1320B = 8 7 1|230|9546并根據(jù)匹配區(qū)域的映射關(guān)系，在其區(qū)域外的相應(yīng)位置標(biāo)記H,得到A=9 84|567|1HHHB=8 H1|230|9H4H再移動(dòng)匹配區(qū)全起點(diǎn)位置，且在其后預(yù)留相等于匹配區(qū)域的空間(H數(shù)目)，然后將其余的 碼按其相對次序排列在預(yù)留區(qū)后面，得到A”=5 6 7 H H H 1 9 8 4B”=2 3 0 H H H 9 4 8 1最后將父串A，B的匹配區(qū)域相互交換，并放置到A”，B”的預(yù)留區(qū)內(nèi)，即可得到兩個(gè)子 代：A”=5 6 7 | 2 3 0 | 1 9 8

12、4B”=2 3 0 | 5 6 7 | 9 4 8 1雖然，PMX法與OX法非常相似，但它們處理相似特性的手段卻不同。PMX法趨向于所期 望的絕對城市位置，而OX法卻趨向于期望的相對城市位置。循環(huán)交叉(CX，cycle crossover)法Smith等人提出的CX方法與PMX方法和OX方法有不同之處。循環(huán)交叉的執(zhí)行是以父串的 特征作為參考，使每個(gè)城市在約束條件下進(jìn)行重組。設(shè)兩個(gè)父串為C = 9 8 2 1 7 4 5 0 6 3D=1 2 3 4 5 6 7 8 9 0不同于選擇交叉位置，我們從左邊開始選擇一個(gè)城市C=9D=1再從另一父串中的相應(yīng)位置，尋找下一個(gè)城市：C=9 1D=1 一一一

13、一一一一一 9 一再輪流選擇下去，最后可得C=9 2 3 1 5 4 7 8 6 1 0D=1 8 2 4 7 6 5 1 0 9 3基于知識的交叉方法這種方法是一種啟發(fā)式的交叉方法，按以下規(guī)劃構(gòu)造后代：隨機(jī)地選取一個(gè)城市作為子代圈的開始城市。比較父串中與開始城市鄰接的邊，選取最小的邊添加到圈的路徑中。重復(fù)第(2)步，如果發(fā)現(xiàn)按最小邊選取的規(guī)劃產(chǎn)生非法路徑(重復(fù)經(jīng)過同一城市)，則 按隨機(jī)法產(chǎn)生一合法的邊，如此反復(fù)，直至形成一完整的TSP圈。使用這一方法，可獲得較好的結(jié)果。在200個(gè)城市的TSP優(yōu)化方面，已產(chǎn)生接近由模擬 退火程序計(jì)算出的最優(yōu)結(jié)果。不過，這一方法使用了基于問題的一些知識，損失了遺

14、傳算法 的通用性和魯棒性。關(guān)于TSP問題的遺傳交叉方法還有各種各樣的變形方法，一般來說，交叉方法應(yīng)能使父 串的待征遺傳給子串，子串應(yīng)能部分或全部地繼承父串的結(jié)構(gòu)特征和有效基因。5.2.3變異技術(shù)從遺傳算法的觀點(diǎn)來看，解的進(jìn)化主要靠選擇機(jī)制和交叉策略來完成，變異只是為選擇、 交叉過程中可能丟失的某些遺傳基因進(jìn)行修復(fù)和補(bǔ)充，變異在遺傳算法的全局意義上只是一 個(gè)背景操作。針對TSP問題，主要的變異技術(shù)如下述。位點(diǎn)變異變異僅以一定的概率(通常較小)對串的某些位作值的變異。逆轉(zhuǎn)變異在串中，隨機(jī)選擇兩點(diǎn)，再將這兩點(diǎn)內(nèi)的子串按反序插入到原位置中，如串A的逆轉(zhuǎn)點(diǎn) 為3，6，則經(jīng)逆轉(zhuǎn)后，變?yōu)锳A =1 2 3

15、| 4 5 6 | 7 8 9 0A=1 2 3 | 6 5 4 | 7 8 9 0這種變異操作對于TSP問題，就調(diào)整前后引起的TSP圈的長度變化而言用于最細(xì)微的調(diào) 整，因而局部優(yōu)化的精度較高；但碼串絕對位置所呈現(xiàn)的“模式”變化較大，所需的計(jì)算也 稍為復(fù)雜一點(diǎn)。3 .對換變異隨機(jī)選擇串中的兩點(diǎn)，交換其值(碼)。對于串AA=1 2 3 4” 5 6 7” 8 9若對換點(diǎn)為4，7，則經(jīng)對換后，A為A=1 2 3 7” 5 6 4” 8 9這種變異操作在求解TSP問題優(yōu)化算法中常被采用。在遺傳算法中，對換變異操作對碼 串絕對位置所呈現(xiàn)的“模式”變化影響較小，所需的計(jì)算也簡單一些，但局部優(yōu)化精度稍差。

16、插人變異從串中隨機(jī)選擇1個(gè)碼，將此碼插入隨機(jī)選擇的插入點(diǎn)中間，對于上述A而言.若取插 入碼為5,選取插入點(diǎn)為23之間.則A=1 2 5 3 4 6 7 8 95.2.4選擇機(jī)制和群體構(gòu)成在遺傳算法中，最常見的選擇機(jī)制是依據(jù)適應(yīng)度的比例概率選擇機(jī)制；在有限規(guī)模的群 體中，適應(yīng)度較高的個(gè)體有較大的機(jī)會繁殖后代，即生物進(jìn)化論上的適者生存規(guī)則。在新一代群體構(gòu)成方法方面存在：N方式：全部替換上一代群體的全刷新代際更新方式。E方式：保留一個(gè)最好的父串的最佳保留(elitist)群體構(gòu)造方式。G方式：按一定比例更新群體中的部分個(gè)體的部分更新方式(或稱代溝方法，這種情況的 極端是每代僅刪去一個(gè)最不適的個(gè)體的最

17、劣死亡方式)。B方式：從產(chǎn)生的子代和父代中挑選最好的若干個(gè)個(gè)體的群體構(gòu)成形式。從群體規(guī)模來看，有變化規(guī)模的方式，也有恒定規(guī)模的群體構(gòu)成方式等。一般講，N方式的全局搜索性能最好，但收斂速度最慢；B方式收斂速度最快，但全局搜 索性能最差；E方式和G方式的性能介于N方式和B方式之間。在求解貨郎擔(dān)問題的應(yīng)用中， 多選用E方式。5.2.5基于遺傳算法求解TSP的算法實(shí)現(xiàn)編碼與適應(yīng)度函數(shù)我們以n城市的遍歷次序作為遺傳算法的編碼，由于在可行解群體的韌始化、交叉操作 及變異操作中均隱臺TSP問題的合法性約束條件，故適應(yīng)度函數(shù)取為哈密爾頓圈的長度的倒 數(shù)(無懲罰函數(shù))。選擇機(jī)制開始，我們用隨機(jī)方法產(chǎn)生初始解群。

18、隨著遺傳算法的執(zhí)行，我們保留M個(gè)較優(yōu)的個(gè)體 作為樣本群體，以供選擇；在每一代運(yùn)算過程中，個(gè)體被選中的概率與其在群體中的相對適 應(yīng)度成正比。3 .交叉方法我們選用的交叉方法與OX法有點(diǎn)類似，現(xiàn)介紹如下：隨機(jī)在串中選擇一個(gè)交配區(qū)域，如兩父串及交配區(qū)域選定為 TOC o 1-5 h z A=1 2 |3456| 789B = 9 8 |7654| 321將B的交配區(qū)域加到A的前面或后面，A的交配區(qū)域加到B的前面或后面得到A=7 654|12 3456789B=3 456|98 7654321在入中自交配區(qū)域后依次刪除與交配區(qū)相同的城市碼，得到最終的兩子串為A=7 6 5 4 1 2 3 8 9B=3

19、 4 5 6 9 8 7 2 1與其它方法相比，這種方法在兩父串相同的情況下仍能產(chǎn)生一定程度的變異效果，對維 持群體內(nèi)一定的多樣化持性有一定的作用，實(shí)驗(yàn)中也顯示了較好的結(jié)果。4.變異技術(shù)由于在選擇機(jī)制中采用保留最佳樣本方式，以及引入了“進(jìn)化逆轉(zhuǎn)”操作技術(shù)，為保持 群體內(nèi)個(gè)體的多樣化，我們采取連續(xù)多次對換的變異技術(shù)，使可行解有較大的順序排列上的 變化，以抑制“進(jìn)化逆轉(zhuǎn)”的同化作用。變異操作發(fā)生的概率取得比較?。?%左右），一旦變 異操作發(fā)生，則用隨機(jī)方法產(chǎn)生交換次數(shù)K，對所需變異操作的串進(jìn)行K次對換（對換的兩 碼位也是隨機(jī)產(chǎn)生的）。“進(jìn)化逆轉(zhuǎn)”操作引入“進(jìn)化逆轉(zhuǎn)”操作的主要目的是改善遺傳算法的局

20、部搜索能力。所謂局部搜索通常 指的是基于鄰域的試探搜索方法。在基本遺傳算法操作中，交叉操作在可行解空間今動(dòng)作范 圍較寬，步伐較大；變異操作由于受“選擇”壓力的作用，通常也難以發(fā)揮局部搜索的功效 （特別在遺傳算法趨向收斂的后期階段）。因此，在遺傳算法框架中加入適當(dāng)?shù)?、基于鄰域?局部搜索機(jī)制，構(gòu)成一種全局搜索和局部搜索相結(jié)合的優(yōu)化搜索算法，對改進(jìn)優(yōu)化質(zhì)量以及 提高搜索效率都是很有意義的。在自然遺傳和進(jìn)化過程中，“逆轉(zhuǎn)”也是一種常見的現(xiàn)象。如一染色體內(nèi)各片斷的正常順 序是（123456），在區(qū)間23和區(qū)間56發(fā)生了兩處斷裂，斷裂片斷又以反向順 序插入，于是逆轉(zhuǎn)后的染色體順序變?yōu)椋?25-4-3-6

21、）。自然生物遺傳上的“逆轉(zhuǎn)”現(xiàn) 象有消極的作用（如導(dǎo)致致死因素、不育因素等），也可能產(chǎn)生積極的作用（如導(dǎo)致生物的適 應(yīng)能力增強(qiáng)等）。從進(jìn)化意義上講，如果說交叉、變異等遺傳操作使子代趨向于擁有較優(yōu)品質(zhì) 的基因型的話，那么逆轉(zhuǎn)、對換等遺傳操作的功能就是使這些基因型及其組合以較優(yōu)的次序 遺傳給后代。在針對TSP問題的遺傳算法中，“逆轉(zhuǎn)”是一種常見的“變異”技術(shù)。我們使用 的“進(jìn)化逆轉(zhuǎn)”是一種單方向的（朝著改進(jìn)的方向）和連續(xù)多次的“逆轉(zhuǎn)”操作，即對于結(jié)定 的串，若“逆轉(zhuǎn)”使串（可行解）的適應(yīng)度提高，則執(zhí)行逆轉(zhuǎn)換作，如此反復(fù)，直至不存在這 樣的逆轉(zhuǎn)操作為止。這一操作實(shí)際上使給定的串改良到它的局部極點(diǎn)，這種局部爬山能力與 基本遺傳算法的全局搜索能力相結(jié)合在實(shí)驗(yàn)中顯示了較好的效果。算法的流程框圖實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)中，群體規(guī)模定為100，交叉概率為0.95，變異概率為0.003，初始可行解群體由隨 機(jī)法產(chǎn)生。實(shí)驗(yàn)結(jié)果表明：（1）當(dāng)nV15時(shí)，隨機(jī)樣本實(shí)驗(yàn)表明，本算法可100%搜索到用窮舉法求得的最優(yōu)解。（2）當(dāng)15VMV30時(shí)，我們對一