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

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

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

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

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

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

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

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

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

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

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