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

1、第四章第四章遺傳算法與組合優(yōu)化遺傳算法與組合優(yōu)化4.14.1背包問題（背包問題（knapsackknapsackproblemproblem）4.1.14.1.1問題描述問題描述0101背包問題背包問題：給出幾個(gè)尺寸為：給出幾個(gè)尺寸為S1，S2，…，Sn的物體和容量為的物體和容量為C的背包，此處的背包，此處S1，S2，…，Sn和C都是正整數(shù)；要求找出都是正整數(shù)；要求找出n個(gè)物件的一個(gè)子集使其盡可能多地填滿容量為個(gè)物件的一個(gè)子集使其盡可能

2、多地填滿容量為C的背包。的背包。數(shù)學(xué)形式數(shù)學(xué)形式：最大化最大化??niiiXS1滿足滿足1CXSniii???niXi???110廣義背包問題廣義背包問題：輸入由：輸入由C和兩個(gè)向量和兩個(gè)向量C＝(S1，S2，…，Sn)和P＝(P1，P2，…，Pn)組成。組成。設(shè)X為一整數(shù)集合，即為一整數(shù)集合，即X＝1，2，3，…，n，T為X的子集，則問題就是找出滿足約束條的子集，則問題就是找出滿足約束條件，而使，而使獲得最大的子集獲得最大的子集T，即

3、求，即求Si和Pi的下標(biāo)子集。的下標(biāo)子集。???TiiCX??TiiP在應(yīng)用問題中，設(shè)在應(yīng)用問題中，設(shè)S的元素是的元素是n項(xiàng)經(jīng)營活動各自所需的資源消耗，項(xiàng)經(jīng)營活動各自所需的資源消耗，C是所能提供的資源是所能提供的資源總量，總量，P的元素是人們從每項(xiàng)經(jīng)營活動中得到的利潤或收益，則背包問題就是在資源有限的的元素是人們從每項(xiàng)經(jīng)營活動中得到的利潤或收益，則背包問題就是在資源有限的條件下，追求總的最大收益的資源有效分配問題。條件下，追求總的最大收

4、益的資源有效分配問題。廣義背包問題可以數(shù)學(xué)形式更精確地描述如下：廣義背包問題可以數(shù)學(xué)形式更精確地描述如下：最大化最大化??niiiXP1滿足滿足1CXSniii???niXi???110背包問題在計(jì)算理論中屬于背包問題在計(jì)算理論中屬于NP—完全問題，其計(jì)算復(fù)雜度為完全問題，其計(jì)算復(fù)雜度為O(2n)，若允許物件可以部，若允許物件可以部分地裝入背包，即允許分地裝入背包，即允許X，可取從，可取從0.00到1.00閉區(qū)間上的實(shí)數(shù)，則背包問題就簡

5、化為極簡閉區(qū)間上的實(shí)數(shù)，則背包問題就簡化為極簡單的單的P類問題，此時(shí)計(jì)算復(fù)雜度為類問題，此時(shí)計(jì)算復(fù)雜度為O(n)。問題描述：問題描述：尋找一條最短的遍歷尋找一條最短的遍歷n個(gè)城市的路徑，或者說搜索整數(shù)子集個(gè)城市的路徑，或者說搜索整數(shù)子集X＝1，2，…，n（X的元的元素表示對素表示對n個(gè)城市的編號）的一個(gè)排列個(gè)城市的編號）的一個(gè)排列π(X)=v1，v2，…，vn，使，使取最小值。式中的取最小值。式中的d(vivi1)表示城市表示城市vi到

6、城市到城市vi1的距離。的距離。4.2.14.2.1編碼與適應(yīng)度函數(shù)編碼與適應(yīng)度函數(shù)編碼編碼1以遍歷城市的次序排列進(jìn)行編碼。以遍歷城市的次序排列進(jìn)行編碼。如碼串如碼串12345678表示自城市表示自城市l(wèi)開始，依次經(jīng)城市開始，依次經(jīng)城市2，3，4，5，6，7，8，最后返回，最后返回城市城市1的遍歷路徑。顯然，這是一種針對的遍歷路徑。顯然，這是一種針對TSP問題的最自然的編碼方式。這一編碼方案的問題的最自然的編碼方式。這一編碼方案的主要缺

7、陷在于引起了交叉操作的困難。主要缺陷在于引起了交叉操作的困難。2采用采用“邊”的組合方式進(jìn)行編碼。的組合方式進(jìn)行編碼。例如碼串例如碼串24536871的第的第1個(gè)碼個(gè)碼2表示城市表示城市1到城市到城市2的路徑在的路徑在TSP圈中，第圈中，第2個(gè)碼個(gè)碼4表示城市表示城市2到城市到城市4的路徑在的路徑在TSP圈中，以此類推，第圈中，以此類推，第8個(gè)碼個(gè)碼1表示城市表示城市8到城市到城市1的路的路徑在徑在TSP圈中。這一編碼方式有著與前面的圈

8、中。這一編碼方式有著與前面的“節(jié)點(diǎn)節(jié)點(diǎn)”遍歷次序編碼方式相類似的缺陷。遍歷次序編碼方式相類似的缺陷。3間接間接“節(jié)點(diǎn)節(jié)點(diǎn)”編碼方式。編碼方式。以消除以消除“一點(diǎn)交叉一點(diǎn)交叉”策略（或多點(diǎn)交叉策略）引起的非法路徑問題。碼串長度仍為策略（或多點(diǎn)交叉策略）引起的非法路徑問題。碼串長度仍為n，定義各等位基因的取值范圍為（定義各等位基因的取值范圍為（n–i1），i為基因序號，解碼時(shí)，根據(jù)相應(yīng)基因位的取值，為基因序號，解碼時(shí)，根據(jù)相應(yīng)基因位的取值，

9、從城市號集合中不回放地取一個(gè)城市號，直至所有城市號被取完。由于這種編碼方式特征遺從城市號集合中不回放地取一個(gè)城市號，直至所有城市號被取完。由于這種編碼方式特征遺傳性較差，因此現(xiàn)行的研究中很少采用。傳性較差，因此現(xiàn)行的研究中很少采用。適應(yīng)度函數(shù)適應(yīng)度函數(shù)適應(yīng)度函數(shù)常取路徑長度適應(yīng)度函數(shù)常取路徑長度Td的倒數(shù)，即的倒數(shù)，即f＝1Td若結(jié)合若結(jié)合TSP的約束條件（每個(gè)城市經(jīng)過且只經(jīng)過一次）的約束條件（每個(gè)城市經(jīng)過且只經(jīng)過一次），則適應(yīng)度函數(shù)可

10、表示為：，則適應(yīng)度函數(shù)可表示為：f＝1(TdαNt)，其中其中Nt是對是對TSP路徑不合法的度量路徑不合法的度量(如取付如取付Nt為未遍歷的城市的個(gè)數(shù)為未遍歷的城市的個(gè)數(shù))，α為懲罰系數(shù)，為懲罰系數(shù)，常取城市間最長距離的兩倍多一點(diǎn)常取城市間最長距離的兩倍多一點(diǎn)(如2.05dmax)。4.2.24.2.2交叉策略交叉策略問題：問題：基于基于TSP問題的順序編碼（其它編碼如以邊的組合狀態(tài)進(jìn)行編碼也呈現(xiàn)相似特性）問題的順序編碼（其它編碼如以邊