【文章內容簡介】 它表示遺傳算法運行到指定的進化代數(shù)之后就停止運行，并將當前種群中的最優(yōu)個體作為所求問題的最優(yōu)解輸出。由于遺傳算法不同于傳統(tǒng)的優(yōu)化算法，它沒有利用目標函數(shù)的梯度等信息，所以在遺傳進化過程中，很難有明 確的搜索終止準則。 常用的辦法是預先給定算法的終止進化代數(shù)。一般來說，預先給定算法的終止進化代數(shù)只能找到問題在給定時限內所能尋求的相對滿意解，但不一定是問題的最優(yōu)解或較高精度的近似解。為了獲得較高精度的近似解，通?？梢罁?jù)種群適應度的穩(wěn)定來適時調整終止進化代數(shù)的設置，或者在連續(xù)進化數(shù)代以后，如果解的適應度沒有明顯的改進，則終止進化過程。終止進化代數(shù)一般的取值范圍是 1001000。 5 實現(xiàn)求解背包問題的遺傳算法 0_1 背包問題中染色體的表示 用向量 X來表示染色體， X = ｛ x1， x2，??， xn｝。， xi∈｛ 0,1｝， xi=1 表示物品 i 裝入了背包， xi =0 表示物品 i未裝入背包。 每個染色體對應其當前裝入背包的物品的總價值和總重量。背包中物品的中價值代表了該物品的適應度。 程序中定義了這樣的一個結構來表示染色體： typedef struct{ int Weight。 //染色體代表的物品的總重量 int Fitness。 //染色體代表的物品的價值（適應度） int Gene[NUMG]。 //用元素取值于定義域｛ 0,1｝的數(shù)組表示染色體。 }GENE。 遺傳算法求解 01 背包問題時用到的參數(shù) POPSIZE：種群大小，即已知的可行解的個數(shù)。 NUMG：染色體中基因的個數(shù)，即物品的總數(shù)。 CAPACITY：背包的容量。 MAXB：二進制表示的染色體換算之后的最大十進制整數(shù)。用于隨機產生一個整數(shù)，進而轉換作染色體。 SIM：染色體之間的相似度閾值。當染色體之間的相似度達到閾值時，算法即停止運行。 PC= ：交叉概率為 100％。 PM= ：變異概率為 20％，變異可以保證種群的多樣性，從而防止算法收斂于某個局部解。 選擇操作 選擇操作采用了賭輪選擇（ Roulettewheel selection）的方法。函數(shù)selectIndex()中包含了選擇染色體的具體過程。其流程圖如圖 1所示。 正文： 基于遺傳算法的背包問題求解 10 圖 1 賭輪選擇流程圖 程序中用一個 Begin 來代表當前賭輪上的指針的位置， End 則用來使賭輪循環(huán)轉動。 用 summaryBE 表示當前賭輪上的指針轉過的染色體的總價值。 用 summaryF 表示當前全部染色體的價值總和。 用 randProb 作為染色體選擇的閾值。 randProb 為介于 [0,1]之間的隨機數(shù)。 選擇使 summaryBE/summaryF 大于閾值 randProb 的染色體作為要選擇的染色體。 交叉操作 單點交叉操作的簡單方式是將被選擇出的兩個個體 S1 和 S2作為父母個體， 從[0， 1]中產生一個隨機數(shù) p，如果 ppc，將兩者的部分基因碼值進行交換。假設如下兩個父代： 父代 1: 1 14 2 13 8 6 3 2 5 4 3 4 3 2 4 父代 2: 1 12 3 5 6 8 5 6 3 1 8 5 6 3 3 隨機選擇一個交叉點為 11，交叉后為： 子代 1: 1 14 2 13 8 6 3 2 5 4 8 5 6 3 3 子代 2: 1 12 3 5 6 8 5 6 3 1 3 4 3 2 4 交叉過程的目的就是希望新的基因是由舊的基因中好的部分組合而成的，從而新的基因比原先的基因要好。當然把舊的種群中的一部分基因完全保留到下一代中去也是很有意義的。 程序中采用了單點交叉的策略。如下程序代碼所示： 正文： 基于遺傳算法的背包問題求解 11 for(int j=0。 jpartPos 。j++){ nextGenome[i].Gene[j] = parentGenome[Father].Gene[j]。 nextGenome[i+POPSIZE/2].Gene[j] = parentGenome[Mother].Gene[j]。 } for(。jNUMG。j++){ nextGenome[i].Gene[j] = parentGenome[Father].Gene[j]。 nextGenome[i+POPSIZE/2].Gene[j] = parentGenome[Mother].Gene[j]。 } partPos 為隨機產生的整數(shù)，代表交叉的位置。第一個 for 循環(huán)將 partPos 位置之前的基因遺傳給一個后代，而第二個循環(huán)則將 partPos 位置之后的基因進行了交換。 calculateCapacity 函數(shù)用于計算交叉操作后的染色體的容量。 calculateFitness 函數(shù)用于計算交叉操作后的染色體的適應度。 checkCapacity 函數(shù)則用于檢查交叉后的染色體的合理性，容量超出背包的染色體是不合理的。這里沒有使后代死亡，而是隨機地調整了染色體中的基因。使得基因能夠適應環(huán)境（背包的容量）而繼續(xù)生存。 精英策略 精英策略為了不使最優(yōu)解在交叉的過程中，不會丟失最優(yōu)解而采取的策略。其思想是保存上一代中的適應性強的染色體。相應地取代下一代中適應性弱的染色體。 程序中精英策略由 keepBestParents 函數(shù)和 sortFiness 函數(shù)來實現(xiàn)。需要說明的是 sortFitness 僅僅對種群的索引進行了排序。然后用父代中 20%的適應度較大的優(yōu)秀染色體替換子代中 20%的適應性弱的染色體。 變異操作 染色體的變異可以保持種群的多樣性，防止最優(yōu)解的丟失以及算法收斂到局部最優(yōu)解。 變異操作由 mutation 函數(shù)實現(xiàn)。 首先產生一個介于 0 和 1 之間的隨機數(shù) prob，若 prob 小于 MP則進行變異操作：隨機產生一個位置 partPos，然后變異前染色體的 partPos 位置的基因為 1，則變異為 0，否則變異為 1；相應地要進行適應度和染色體容量的變化。 代際更新 代際之間的更新，即用新生成的種群代替取代舊的種群。這個操作在updateGeneration 函數(shù)中實現(xiàn)，同時這個操作使用了前面提及的精英策略。實際上，父代種群中優(yōu)秀的染色體已被保留， updateGeneration 中只是用新種群中的優(yōu)秀染色體來代替父代中的染色體。 由于對父代和子代的染色體都進行了排序，因此程序中將子代的 80％視作優(yōu)秀，將父代中的前 20％視作優(yōu)秀。 算法的終止 程序中采用了一個 HASH 表來對子代種群的適應度 進行 HASH 操作。 HASH 表中的正文： 基于遺傳算法的背包問題求解 12 頭結點紀錄了頭結點所指向的單鏈表的信息。如下代碼中的注釋： typedef struct Head{ int maxFitness。 //單鏈表中的最大的 Fitness int Count。 //HASH 到該結點的染色體的數(shù)目 int Diff。 //單鏈表中有多少不同的 Fitness HASHNODE *Next。 }HEAD。 用這樣的一個 HASH 表結構可以只需遍歷 HASH 表中的頭結點，即可知當前的種群的適應度最大的染色體是否集中。 具體地，如 checkFitness 函數(shù)中的下面幾行代碼： index = maxFitness(hashTable)。 double CPount = hashTable[index].Count/(double)POPSIZE。 double pDiff = hashTable[index].Diff/(double)POPSIZE。 if(CPount= amp。amp。 pDiff=){ sameFlag = false。 } 如果當前 maxFitness 最大的頭結點滿足 if 語句中的判斷條件，則 sameFlag 置為真，即算法停止迭代的條件得到了滿足。 TraverseHashTable 函數(shù)則用于遍歷 HASH 表。 算法終止的另一個條件是迭代的次數(shù)。程序中設定了算法的最大迭代次數(shù)為1000。 仿真結果 與測試 試驗中用到的物品的重量和價值分別存儲于以下兩個數(shù)組之中。 int Weight[NUMG]={6,9,8,8,6, 1, 10,5,7, 1}。 int Value[NUMG]={2,20,5,4,19,14,18,8,11,6}。 父代種群存儲于 parentGenome[NUMG]中，子代種群存儲于 nextGenome[NUMG]中。程序的初始狀態(tài)和結束狀態(tài)如下面的表格所示： 初始的種群 : Weight Value 染色體中的基因 21 52 0010110101 22 23 0011000101 22 40 0001100011 22 53 0100010110 26 45 1010011001 24 53 1100010011 正文： 基于遺傳算法的背包問題求解 13 22 53 0100010110 23 25 1011010000 26 48 1010110100 25 29 0111000000 初始的 HASH 表 : 頭結點索引 maxFitness Count Diff 單鏈表中的結點內容 0 52 1 1 52: 1 53 4 2 53:40 3 29 1 1 29: 6 45 1 1 45: 9 48 1 1 48: 10 23 1 1 23: 12 25 1 1 25: 不同交叉概率下所得測試結果 在程序實現(xiàn)上，本文采用 VC++ 作為程序開發(fā)工具，測試是在奔騰 ，512M 以上內存的微機上進行的，操作系統(tǒng)是 WinXP。 當 PM= 時， 程序在運行了 16次后停止 運行。 停止時的種群 : Weight Value 染色體中的基因 29 78 0100110111 29 78 0100110111 29 78 0100110111 29 78 0100110111 29 78 0100110111 29 78 0100110111 29 78 0100110111 28 64 0100100111 29 78 0100110111 29 78 0100110111 正文： 基于遺傳算法的背包問題求解 14 停止時的 HASH 表 : 頭結點索引 maxFitness Count Diff 單鏈表中的結點內容 0 78 9 1 78: 12 64 1 1 64: 當 PM= 時， 程序在運行了 3次后停止運行 。 停止時的種群 : Weight Value 染色體中的基因 22 53 0100010110 22 53 0100010110 24 53 1100010011 24 53 1100010011 22 53 0100010110 22 53 0100010110 24 53 1100010011 22 53 0100010110 22 53 0100010110 26 48 1010110100 停止時的 HASH 表 : 頭結點索引 maxFitness Count Diff 單鏈表中的結點內容 1 53 9 1 78: 9 48 1 1 48: 當 PM= 時， 程序在運行了 26次后停止運行。 停止時的種群 : Weight Value 染色體中的基因 29 78 0100110111 29 78 0100110111 29 78 0100110111 29 78 0100110111 29 78 0100110111 29 78 0100110111 29 78 0100110111 正文： 基于遺傳算法的背包問題求解 15 28 64 0100100111 29 78 0100110111 29 78 0100110111 停止時的 HASH 表 : 頭結點索引 maxFitness Count Diff 單鏈表中的結點內容 0 78 9 1 78: 12 64 1 1 64: 當 PM= 時， 程序在運行了 13次后停止運行。 停止時的種群 : Weight Value 染色體中的基因 29 78 0100110111 29 78 0100110111 29