【正文】 iPOPSIZE/2 。 sortFitness(indexPF,parentGenome)。j++){ parentGenome[indexPF[i]].Gene[j] = nextGenome[indexCF[i]].Gene[j]。 for(int j=0。i++){ parentGenome[indexPF[i]].Fitness = nextGenome[indexCF[i]].Fitness。 for(int i=0。j++){ parentGenome[indexPF[i]].Gene[j] = parentGenome[indexPF[iPOPSIZE*8/10]].Gene[j]。 for(int j=0。i++){ parentGenome[indexPF[i]].Fitness = parentGenome[indexPF[iPOPSIZE*8/10]].Fitness。 } } //精英策略：保持優(yōu)秀的父染色體 void keepBestParents(){ for(int i=POPSIZE*8/10。i++){ indexFitness[i] = selectedMaxFitness(Genome)。 for(int i=0。 } } return maxPos。amp。 iPOPSIZE 。 i = POPSIZE。 iPOPSIZE 。 //獲取當(dāng)前 HASH表中的最大 Fitness的索引 int selectedMaxFitness(GENE *Genome){ int maxPos = 0。 } } return index。 } End++。 Begin = End。 crossProb = (double)summaryBE/(double)summaryF。 正文： 基于遺傳算法的背包問(wèn)題求解 31 summaryF = summaryFitness(0,POPSIZE)。 bool flag = true。 int summaryF = 0。 double crossProb = 。 } } return summaryF。 iEnd 。i++){ summaryF += parentGenome[i].Fitness。 } }else{ for(int i=Begin。 iEnd 。 //計(jì)算從 Begin－ End位置的染色體的適應(yīng)度之和 正文： 基于遺傳算法的背包問(wèn)題求解 30 int summaryFitness(int Begin,int End){ int summaryF = 0。 } //賭輪 選擇函數(shù)代碼段 int Begin = 0。 } TraverseHashTable(hashTable)。amp。 double pDiff = hashTable[index].Diff/(double)POPSIZE。 } } index = maxFitness(hashTable)。 if(parentGenome[i].FitnesshashTable[index].maxFitness){ hashTable[index].maxFitness = parentGenome[i].Fitness。 pNodeNext = hashTable[index].Next。 if(NULL==pNode){ pNode = new HASHNODE。 hashTable[index].Count++。 iPOPSIZE 。 initHashTable(hashTable)。 int index = 0。 } coutendl。 while(NULL!=lastPos){ coutlastPosFitness:。 lastPos = hashTable[i].Next。i++){ 正文： 基于遺傳算法的背包問(wèn)題求解 28 if(hashTable[i].Count==0){ continue。 for(int i=0。 HASHNODE *lastPos = NULL。 } return pHead。 lastPos = pHead。 while(NULL!=pHead){ if(pHeadFitness==Fitness){ break。 } } return index。i++){ 正文： 基于遺傳算法的背包問(wèn)題求解 27 if(hashTable[i].maxFitnessmaxF){ maxF = hashTable[i].maxFitness。 for(int i=1。 } } //在 HASH表頭結(jié)點(diǎn)中搜索最大的適應(yīng)度 int maxFitness(HEAD *hashTable){ int maxF = hashTable[0].maxFitness。 hashTable[i].Diff= 0。i++){ hashTable[i].maxFitness = 0。 } } } //初始化 HASH表 void initHashTable(HEAD * hashTable){ for(int i=0。 Genome[iD].Weight = Weight[idModify]。 } } 正文： 基于遺傳算法的背包問(wèn)題求解 26 } //染色體大小檢查 void checkCapacity(GENE * Genome,int iD){ while(Genome[iD].WeightCAPACITY){ int idModify = rand()%NUMG。 jNUMG 。 } } } //計(jì)算染色體的適應(yīng)度 void calculateFitness(GENE * Genome,int iD){ Genome[iD].Fitness = 0。 jNUMG 。//子染色體索引 //計(jì)算染色體的大小 void calculateCapacity(GENE * Genome,int iD){ Genome[iD].Weight = 0。 int indexPF[POPSIZE]。//新的染色體 //需要裝入背包的物品的大小和價(jià)值 int Weight[NUMG]={6,9,8,8,6, 1, 10,5,7, 1}。可自行編寫(xiě)隨機(jī)生成染色體的函數(shù)來(lái)生成染色體 GENE parentGenome[NUMG]={ {0,0,{0,0,1,0,1,1,0,1,0,1}}, {0,0,{0,0,1,1,0,0,0,1,0,1}}, {0,0,{0,0,0,1,1,0,0,0,1,1}}, {0,0,{0,1,0,0,0,1,0,1,1,0}}, {0,0,{1,0,1,0,0,1,1,0,0,1}}, {0,0,{1,1,0,0,0,1,0,0,1,1}}, {0,0,{0,1,0,0,0,1,0,1,1,0}}, {0,0,{1,0,1,1,0,1,0,0,0,0}}, {0,0,{1,1,1,0,1,1,0,1,0,0}}, 正文： 基于遺傳算法的背包問(wèn)題求解 25 {0,0,{1,1,1,1,0,0,0,0,0,0}} }。 //染色體中對(duì)應(yīng)的基因 }GENE。 //每個(gè)染色體的大小 int Fitness。//頭結(jié)點(diǎn) //HASH 表 HEAD hashTable[DIST]。 HASHNODE *Next。 int Count。 }HASHNODE。 define SIM //算法終止條件之一：染色體之間的相似度上限 define MP //變異率 define DIST 13 //程序中 HASH表的距離 //程序中用到的 HASH表中鏈表結(jié)點(diǎn)結(jié)構(gòu)定義 typedef struct Node{ int Fitness。 最后，感謝所有在生活和學(xué)習(xí)上給予我?guī)椭娜耍? 正文： 基于遺傳算法的背包問(wèn)題求解 21 參考文獻(xiàn)： [1] 陳國(guó)良 ,等 .遺傳算法及其應(yīng)用 [M].北京 :人民郵電出版社 ,~10. [2] 陳文清 . 遺傳算法綜述 [J]. 武漢 : 華中科技大學(xué) ,~58. [3] 王麗微 .遺傳算法的研究與應(yīng)用 [D].博士學(xué)位論文，哈爾濱 。每一次，碰到一個(gè)困難，不知該如何繼續(xù)的時(shí)候，總是身邊的朋友鼓勵(lì)我，幫助我查找相關(guān)資料，因?yàn)閷?duì)人工智能不太熟悉，所以論文完成階段也是困難重重，但通過(guò)網(wǎng)上論壇上咨詢(xún)，朋友的幫助，也一步步克服了困難，所以在這里也要特別感謝那些幫助過(guò)我的認(rèn)識(shí)的和不認(rèn)識(shí)的朋友。從一開(kāi)始的開(kāi)題報(bào)告答辯就一直磕磕碰碰，那個(gè)時(shí)候差點(diǎn)失去信心，不知道接下來(lái)的論文工作該如何進(jìn)行，但鄧?yán)蠋熯€是用他的切身經(jīng)歷鼓勵(lì)我，以他淵博的學(xué)識(shí)、科學(xué)嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度、一絲不茍的工作作風(fēng)和無(wú)私忘我的奉獻(xiàn)精神深深地影響著我，將使我受益終身。 首先，我衷心地感謝我的指導(dǎo)老師鄧 大勇老師，我的整個(gè)論文都是在鄧大勇老師的關(guān)懷和細(xì)心指導(dǎo)下完成的。 到目前，遺傳算法的理論機(jī)制仍不是很清楚，這可能和生命科學(xué)的研究一樣，將是一個(gè)永恒的研究課題，但也是一個(gè)難題。遺傳算法的商業(yè)應(yīng)用五花八門(mén) ,覆蓋面甚廣。 如果一個(gè)應(yīng)用問(wèn)題不能求得目標(biāo)函數(shù)的全局最優(yōu)值 ,而只能或只希望求一定意義下的 滿意解 ，這時(shí) ,可供選擇的方 法之一自然是遺傳算法，因?yàn)檫z傳算法比其他算法有更多的優(yōu)勢(shì)。 6 展望 遺傳算法作為一種對(duì)生物進(jìn)化現(xiàn)象進(jìn)行仿真的程序，取得了人工遺傳的模擬效果，具有自適應(yīng)性。 正文： 基于遺傳算法的背包問(wèn)題求解 19 我們通過(guò)上述例子，嚴(yán)格按照遺傳算法對(duì) 背包 問(wèn)題進(jìn) 行了完整的求解，事實(shí)說(shuō)明，用遺傳算法來(lái)解決此類(lèi)組合優(yōu)化問(wèn)題也是比較有效的，而且非常好用，它的解的空間比較大，而且在最后能無(wú)限度地接近最優(yōu)解。進(jìn)化過(guò)程最后一代中的最優(yōu)解就是用遺傳算法解最優(yōu)化問(wèn)題所得到的最終結(jié)果。這樣通過(guò)選擇和繁殖就產(chǎn)生了下一代群體。在接下去的繁殖過(guò)程中，遺傳算法提供了交叉和變異兩種算法對(duì)挑選后的樣本進(jìn)行交換和基因突變。接著就像自然界中 的遺傳規(guī)律 一樣，利用選擇機(jī)制從群體中隨機(jī)挑選個(gè)體作為繁殖過(guò)程前的個(gè)體樣本。因此，我們認(rèn)為本文算法是可行的和有效的。 通過(guò)上述仿真實(shí)驗(yàn) 和數(shù)據(jù)測(cè)試 ，可以得出利用本文算法求解 背包 問(wèn)題能夠獲得較滿意的效果。 停止時(shí)的種群 : Weight Value 染色體中的基因 29 78 0100110111 29 78 0100110111 29 78 0100110111 29 78 0100110111 29 78 0100110111 29 78 0100110111 29 78 0100110111 正文： 基于遺傳算法的背包問(wèn)題求解 15 28 64 0100100111 29 78 0100110111 29 78 0100110111 停止時(shí)的 HASH 表 : 頭結(jié)點(diǎn)索引 maxFitness Count Diff 單鏈表中的結(jié)點(diǎn)內(nèi)容 0 78 9 1 78: 12 64 1 1 64: 當(dāng) PM= 時(shí)， 程序在運(yùn)行了 13次后停止運(yùn)行。 停止時(shí)的種群 : 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 正文： 基于遺傳算法的背包問(wèn)題求解 14 停止時(shí)的 HASH 表 : 頭結(jié)點(diǎn)索引 maxFitness Count Diff 單鏈表中的結(jié)點(diǎn)內(nèi)容 0 78 9 1 78: 12 64 1 1 64: 當(dāng) PM= 時(shí)， 程序在運(yùn)行了 3次后停止運(yùn)行 。程序的初始狀態(tài)和結(jié)束狀態(tài)如下面的表格所示：