【正文】 n index。 iPOPSIZE 。 iPOPSIZE 。 } } return maxPos。i++){ indexFitness[i] = selectedMaxFitness(Genome)。i++){ parentGenome[indexPF[i]].Fitness = parentGenome[indexPF[iPOPSIZE*8/10]].Fitness。j++){ parentGenome[indexPF[i]].Gene[j] = parentGenome[indexPF[iPOPSIZE*8/10]].Gene[j]。i++){ parentGenome[indexPF[i]].Fitness = nextGenome[indexCF[i]].Fitness。j++){ parentGenome[indexPF[i]].Gene[j] = nextGenome[indexCF[i]].Gene[j]。 iPOPSIZE/2 。 for(int j=0。 } for(。 } calculateCapacity(nextGenome,i)。 calculateFitness(nextGenome,i+POPSIZE/2)。 iPOPSIZE 。 nextGenome[i].Weight = Weight[partPos]。 nextGenome[i].Fitness += Value[partPos]。i++){ coutparentGenome[i].Weight。j++){ coutparentGenome[i].Gene[j]。 bool flag = true。i++){ for(int j=0。 } } checkCapacity(parentGenome,i)。 flag = checkFitness()。nCountnGenerations){ nCount++。 //更新種群 printGenome()。 indexMaxResult = maxFitness(hashTable)。 }else{//失敗 coutOH,Sorry!。 }}。 coutThe information in Genome is as below:endl。 coutThe information in Genome is as below:endl。//產(chǎn)看是否滿足SIM coutnCountendl。 //交叉 mutation()。 while(flagamp。用于隨機(jī)產(chǎn)生染色體 //generatePopulation()。j++){ if(parentGenome[i].Gene[j]==1){ parentGenome[i].Weight += Weight[j]。 //初始化染色體種群 for(int i=0。 }}void main(){ int nGenerations = 1000。 for(int j=0。t mutate! } } } }}//打印所有的父代染色體void printGenome(){ for(int i=0。 }else{ if(nextGenome[i].Weight+Weight[partPos]CAPACITY){ nextGenome[i].Gene[partPos]=1。 if(probMP){ int partPos = rand()%NUMG。 } sortFitness(indexCF,nextGenome)。 checkCapacity(nextGenome,i)。j++){ nextGenome[i].Gene[j] = parentGenome[Father].Gene[j]。j++){ nextGenome[i].Gene[j] = parentGenome[Father].Gene[j]。 int Father = selectIndex()。 sortFitness(indexPF,parentGenome)。 for(int j=0。 for(int i=0。 for(int j=0。 }}//精英策略：保持優(yōu)秀的父染色體void keepBestParents(){ for(int i=POPSIZE*8/10。 for(int i=0。amp。 i = POPSIZE。//獲取當(dāng)前HASH表中的最大Fitness的索引int selectedMaxFitness(GENE *Genome){ int maxPos = 0。 } End++。 crossProb = (double)summaryBE/(double)summaryF。 bool flag = true。 double crossProb = 。 iEnd 。 } }else{ for(int i=Begin。//計(jì)算從Begin－End位置的染色體的適應(yīng)度之和int summaryFitness(int Begin,int End){ int summaryF = 0。 } TraverseHashTable(hashTable)。 double pDiff = hashTable[index].Diff/(double)POPSIZE。 if(parentGenome[i].FitnesshashTable[index].maxFitness){ hashTable[index].maxFitness = parentGenome[i].Fitness。 if(NULL==pNode){ pNode = new HASHNODE。 iPOPSIZE 。 int index = 0。 while(NULL!=lastPos){ coutlastPosFitness:。i++){ if(hashTable[i].Count==0){ continue。 HASHNODE *lastPos = NULL。 lastPos = pHead。 } } return index。 for(int i=1。 hashTable[i].Diff= 0。 } }}//初始化HASH表void initHashTable(HEAD * hashTable){ for(int i=0。 } }}//染色體大小檢查void checkCapacity(GENE * Genome,int iD){ while(Genome[iD].WeightCAPACITY){ int idModify = rand()%NUMG。 } }}//計(jì)算染色體的適應(yīng)度void calculateFitness(GENE * Genome,int iD){ Genome[iD].Fitness = 0。//子染色體索引//計(jì)算染色體的大小void calculateCapacity(GENE * Genome,int iD){ Genome[iD].Weight = 0。//新的染色體//需要裝入背包的物品的大小和價(jià)值int Weight[NUMG]={6,9,8,8,6, 1, 10,5,7, 1}。 //染色體中對(duì)應(yīng)的基因}GENE。//頭結(jié)點(diǎn)//HASH表HEAD hashTable[DIST]。 int Count。define SIM //算法終止條件之一：染色體之間的相似度上限define MP //變異率define DIST 13 //程序中HASH表的距離//程序中用到的HASH表中鏈表結(jié)點(diǎn)結(jié)構(gòu)定義typedef struct Node{ int Fitness。每一次，碰到一個(gè)困難，不知該如何繼續(xù)的時(shí)候，總是身邊的朋友鼓勵(lì)我，幫助我查找相關(guān)資料，因?yàn)閷?duì)人工智能不太熟悉，所以論文完成階段也是困難重重，但通過(guò)網(wǎng)上論壇上咨詢，朋友的幫助，也一步步克服了困難，所以在這里也要特別感謝那些幫助過(guò)我的認(rèn)識(shí)的和不認(rèn)識(shí)的朋友。首先，我衷心地感謝我的指導(dǎo)老師鄧大勇老師，我的整個(gè)論文都是在鄧大勇老師的關(guān)懷和細(xì)心指導(dǎo)下完成的。遺傳算法的商業(yè)應(yīng)用五花八門(mén),覆蓋面甚廣。6 展望遺傳算法作為一種對(duì)生物進(jìn)化現(xiàn)象進(jìn)行仿真的程序，取得了人工遺傳的模擬效果，具有自適應(yīng)性。 遺傳算法利用目標(biāo)函數(shù)的信息，而不是導(dǎo)數(shù)或者其他輔助信息； 進(jìn)化過(guò)程最后一代中的最優(yōu)解就是用遺傳算法解最優(yōu)化問(wèn)題所得到的最終結(jié)果。在接下去的繁殖過(guò)程中，遺傳算法提供了交叉和變異兩種算法對(duì)挑選后的樣本進(jìn)行交換和基因突變。因此，我們認(rèn)為本文算法是可行的和有效的。停止時(shí)的種群:WeightValue染色體中的基因29780100110111297801001101112978010011011129780100110111297801001101112978010011011129780100110111286401001001112978010011011129780100110111停止時(shí)的HASH表:頭結(jié)點(diǎn)索引maxFitnessCountDiff單鏈表中的結(jié)點(diǎn)內(nèi)容0789178:12641164: 當(dāng)PM=，程序在運(yùn)行了13次后停止運(yùn)行。程序的初始狀態(tài)和結(jié)束狀態(tài)如下面的表格所示：初始的種群:WeightValue染色體中的基因21520010110101222300110001012240000110001122530100010110264510100110012453110001001122530100010110232510110100002648101011010025290111000000初始的HASH表:頭結(jié)點(diǎn)索引maxFitnessCountDiff單鏈表中的結(jié)點(diǎn)內(nèi)容0521152:1534253:403291129:6451145:9481148:10231123:12251125: 不同交叉概率下所得測(cè)試結(jié)果 在程序?qū)崿F(xiàn)上，本文采用VC++，512M以上內(nèi)存的微機(jī)上進(jìn)行的，操作系統(tǒng)是WinXP。 仿真結(jié)果與測(cè)試試驗(yàn)中用到的物品的重量和價(jià)值分別存儲(chǔ)于以下兩個(gè)數(shù)組之中。}如果當(dāng)前maxFitness最大的頭結(jié)點(diǎn)滿足if語(yǔ)句中的判斷條件，則sameFlag置為真，即算法停止迭代的條件得到了滿足。double pDiff = hashTable[index].Diff/(double)POPSIZE。}HEAD。如下代碼中的注釋：typedef struct Head{ int maxFitness。實(shí)際上，父代種群中優(yōu)秀的染色體已被保留，updateGeneration中只是用新種群中的優(yōu)秀染色體來(lái)代替父代中的染色體。變異操作由mutation函數(shù)實(shí)現(xiàn)。程序中精英策略由keepBestParents函數(shù)和sortFiness函數(shù)來(lái)實(shí)現(xiàn)。使得基因能夠適應(yīng)環(huán)境（背包的容量）而繼續(xù)生存。calculateCapacity函數(shù)用于計(jì)算交叉操作后的染色體的容量。j++){ nextGenome[i].Gene[j] = parentGenome[Father].Gene[j]。j++){ nextGenome[i].Gene[j] = parentGenome[Father].Gene[j]。當(dāng)然把舊的種群中的一部分基因完全保留到下一代中去也是很有意義的。randProb為介于[0,1]之間的隨機(jī)數(shù)。圖1 賭輪選擇流程圖 程序中用一個(gè)Begin來(lái)代表當(dāng)前賭輪上的指針的位置，End則用來(lái)使賭輪循環(huán)轉(zhuǎn)動(dòng)。PM= ：變異概率為20％，變異可以保證種群的多樣性，從而防止算法收斂于某個(gè)局部解。用于隨機(jī)產(chǎn)生一個(gè)整數(shù)，進(jìn)而轉(zhuǎn)換作染色體。 遺傳算法求解01背包問(wèn)題時(shí)用到的參數(shù)POPSIZE：種群大小，即已知的可行解的個(gè)數(shù)。 //染色體代表的物品的總重量 int Fitn