【文章內(nèi)容簡介】 0，1]中產(chǎn)生一個隨機數(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交叉過程的目的就是希望新的基因是由舊的基因中好的部分組合而成的，從而新的基因比原先的基因要好。當然把舊的種群中的一部分基因完全保留到下一代中去也是很有意義的。程序中采用了單點交叉的策略。如下程序代碼所示：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為隨機產(chǎn)生的整數(shù)，代表交叉的位置。第一個for循環(huán)將partPos位置之前的基因遺傳給一個后代，而第二個循環(huán)則將partPos位置之后的基因進行了交換。calculateCapacity函數(shù)用于計算交叉操作后的染色體的容量。calculateFitness函數(shù)用于計算交叉操作后的染色體的適應度。checkCapacity函數(shù)則用于檢查交叉后的染色體的合理性，容量超出背包的染色體是不合理的。這里沒有使后代死亡，而是隨機地調(diào)整了染色體中的基因。使得基因能夠適應環(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)。首先產(chǎn)生一個介于0和1之間的隨機數(shù)prob，若prob小于MP則進行變異操作：隨機產(chǎn)生一個位置partPos，然后變異前染色體的partPos位置的基因為1，則變異為0，否則變異為1；相應地要進行適應度和染色體容量的變化。 代際更新代際之間的更新，即用新生成的種群代替取代舊的種群。這個操作在updateGeneration函數(shù)中實現(xiàn)，同時這個操作使用了前面提及的精英策略。實際上，父代種群中優(yōu)秀的染色體已被保留，updateGeneration中只是用新種群中的優(yōu)秀染色體來代替父代中的染色體。由于對父代和子代的染色體都進行了排序，因此程序中將子代的80％視作優(yōu)秀，將父代中的前20％視作優(yōu)秀。 算法的終止程序中采用了一個HASH表來對子代種群的適應度進行HASH操作。HASH表中的頭結(jié)點紀錄了頭結(jié)點所指向的單鏈表的信息。如下代碼中的注釋：typedef struct Head{ int maxFitness。 //單鏈表中的最大的Fitness int Count。 //HASH到該結(jié)點的染色體的數(shù)目 int Diff。 //單鏈表中有多少不同的Fitness HASHNODE *Next。}HEAD。用這樣的一個HASH表結(jié)構(gòu)可以只需遍歷HASH表中的頭結(jié)點，即可知當前的種群的適應度最大的染色體是否集中。具體地，如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最大的頭結(jié)點滿足if語句中的判斷條件，則sameFlag置為真，即算法停止迭代的條件得到了滿足。TraverseHashTable函數(shù)則用于遍歷HASH表。算法終止的另一個條件是迭代的次數(shù)。程序中設定了算法的最大迭代次數(shù)為1000。 仿真結(jié)果與測試試驗中用到的物品的重量和價值分別存儲于以下兩個數(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)和結(jié)束狀態(tài)如下面的表格所示：初始的種群:WeightValue染色體中的基因21520010110101222300110001012240000110001122530100010110264510100110012453110001001122530100010110232510110100002648101011010025290111000000初始的HASH表:頭結(jié)點索引maxFitnessCountDiff單鏈表中的結(jié)點內(nèi)容0521152:1534253:403291129:6451145:9481148:10231123:12251125: 不同交叉概率下所得測試結(jié)果 在程序?qū)崿F(xiàn)上，本文采用VC++，512M以上內(nèi)存的微機上進行的，操作系統(tǒng)是WinXP。當PM=，程序在運行了16次后停止運行。停止時的種群:WeightValue染色體中的基因29780100110111297801001101112978010011011129780100110111297801001101112978010011011129780100110111286401001001112978010011011129780100110111停止時的HASH表:頭結(jié)點索引maxFitnessCountDiff單鏈表中的結(jié)點內(nèi)容0789178:12641164: 當PM=，程序在運行了3次后停止運行。停止時的種群:WeightValue染色體中的基因22530100010110225301000101102453110001001124531100010011225301000101102253010001011024531100010011225301000101102253010001011026481010110100停止時的HASH表:頭結(jié)點索引maxFitnessCountDiff單鏈表中的結(jié)點內(nèi)容1539178:9481148:當PM=，程序在運行了26次后停止運行。停止時的種群:WeightValue染色體中的基因29780100110111297801001101112978010011011129780100110111297801001101112978010011011129780100110111286401001001112978010011011129780100110111停止時的HASH表:頭結(jié)點索引maxFitnessCountDiff單鏈表中的結(jié)點內(nèi)容0789178:12641164: 當PM=，程序在運行了13次后停止運行。停止時的種群:WeightValue染色體中的基因2978010011011129780100110111297801001101112872010010110297801001101112978010011011129780100110111286401001001112978010011011129780100110111停止時的HASH表:頭結(jié)點索引maxFitnessCountDiff單鏈表中的結(jié)點內(nèi)容0789178:7721172:對于不同變異概率下運行次數(shù)和所得值如下圖所示：從上圖我們可以總結(jié)出：（1） 變異概率太小，可能是某些基因位過早丟失的信息無法恢復，導致無法獲得最優(yōu)解（2） 變異概率過高，則搜索將變成隨機搜索，增大了搜索次數(shù)，但能得到最優(yōu)解 極端數(shù)據(jù)對結(jié)果的影響當初始種群全是零時：WeightValue染色體中的基因000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000所得結(jié)果：當初始種群為：WeightValue染色體中的基因000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000160000000001所得結(jié)果：分析：超過最大迭代次數(shù)，所以只有一個估計值（最大值） 當初始種群為：WeightValue染色體中的基因611071111111111611071111111111611071111111111611071111111111611071111111111611071111111111611071111111111611071111111111611071111111111611071111111111所得結(jié)果：分析：超過最大迭代次數(shù)，所以只有一個估計值（最大值） 仿真結(jié)果總結(jié)通過對以上各種情況分析，我們可知：當前01背包問題的最優(yōu)解為 X =｛0,1,0,0,1,1,0,1,1,1｝對應的最優(yōu)值是78，即當前能夠裝入背包的最大價值。通過上述仿真實驗和數(shù)據(jù)測試，可以得出利用本文算法求解背包問題能夠獲得較滿意的效果。本文的算法不但有很快的收斂速度，而且在進化過程中種群的多樣性保持很好，具有良好的全局搜索能力。因此，我們認為本文算法是可行的和有效的。 問題總結(jié)用遺傳算法解最優(yōu)化問題，首先應對可行域中的個體進行編碼，然后在可行域中隨機挑選指定群體大小的一些個體組成作為進化起點的第一代群體，并計算每個個體的目標函數(shù)值，即該個體的適應度值。接著就像自然界中的遺傳規(guī)律一樣，利用選擇機制從群體中隨機挑選個體作為繁殖過程前的個體樣本。選擇機制保證適應度較高的個體能夠保留較多的樣本；而適應度較低的個體則保留較少的樣本，甚至被淘汰。在接下去的繁殖過程中，遺傳算法提供了交叉和變異兩種算法對挑選后的樣本進行交換和基因突變。交叉算法交換隨機挑選的兩個個體的某些位，變異算子則直接對一個個體中的隨機挑選的某一