【導(dǎo)讀】傳算子等方面的應(yīng)用情況。題實(shí)例，給出了具體的編碼方法，運(yùn)行參數(shù)，群體大小，最大迭代次數(shù)，以及合適的遺傳算子。些簡單的情況之外，人們對于大型復(fù)雜系統(tǒng)的優(yōu)化和自適應(yīng)問題仍然無能為力。遺傳算法正是借鑒生物的自然選擇和遺傳進(jìn)化機(jī)制而開發(fā)出的一種全局優(yōu)化。自適應(yīng)概率搜索算法。由于其具有思想簡單、易于實(shí)現(xiàn)、應(yīng)用效果明顯等優(yōu)點(diǎn)而被眾多應(yīng)用領(lǐng)域所

　　

【正文】 ,1,1,0,0,0,0,0,0}} }。 GENE nextGenome[NUMG]。//新的染色體 //需要裝入背包的物品的大小和價值 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}。 int indexPF[POPSIZE]。//父染色體索引 int indexCF[POPSIZE]。//子染色體索引 //計(jì)算染色體的大小 void calculateCapacity(GENE * Genome,int iD){ Genome[iD].Weight = 0。 for(int j=0。 jNUMG 。j++){ if(Genome[iD].Gene[j]==1){ Genome[iD].Weight += Weight[j]。 } } } //計(jì)算染色體的適應(yīng)度 void calculateFitness(GENE * Genome,int iD){ Genome[iD].Fitness = 0。 for(int j=0。 jNUMG 。j++){ if(Genome[iD].Gene[j]==1){ Genome[iD].Fitness += Value[j]。 } } 正文： 基于遺傳算法的背包問題求解 26 } //染色體大小檢查 void checkCapacity(GENE * Genome,int iD){ while(Genome[iD].WeightCAPACITY){ int idModify = rand()%NUMG。 if(Genome[iD].Gene[idModify]==1){ Genome[iD].Gene[idModify] = 0。 Genome[iD].Weight = Weight[idModify]。 Genome[iD].Fitness = Value[idModify]。 } } } //初始化 HASH表 void initHashTable(HEAD * hashTable){ for(int i=0。 iDIST 。i++){ hashTable[i].maxFitness = 0。 hashTable[i].Count = 0。 hashTable[i].Diff= 0。 hashTable[i].Next = NULL。 } } //在 HASH表頭結(jié)點(diǎn)中搜索最大的適應(yīng)度 int maxFitness(HEAD *hashTable){ int maxF = hashTable[0].maxFitness。 int index =0。 for(int i=1。 iDIST 。i++){ 正文： 基于遺傳算法的背包問題求解 27 if(hashTable[i].maxFitnessmaxF){ maxF = hashTable[i].maxFitness。 index = i。 } } return index。 } //判斷適應(yīng)度 Fitness是否已經(jīng)在 HASH頭結(jié)點(diǎn)對應(yīng)的鏈表中 HASHNODE* isAlreadyExist(HASHNODE *pHead,int Fitness){ HASHNODE *lastPos = NULL。 while(NULL!=pHead){ if(pHeadFitness==Fitness){ break。 } //coutpHeadFitnessendl。 lastPos = pHead。 pHead = pHeadNext。 } return pHead。 } //遍歷 HASH表 void TraverseHashTable(HEAD * hashTable){ int index = 0。 HASHNODE *lastPos = NULL。 coutI:MAX:C:D:Oendl。 for(int i=0。 iDIST 。i++){ 正文： 基于遺傳算法的背包問題求解 28 if(hashTable[i].Count==0){ continue。 } couti:hashTable[i].maxFitness:hashTable[i].Count:hashTable[i].Diff:。 lastPos = hashTable[i].Next。 coutContent:。 while(NULL!=lastPos){ coutlastPosFitness:。 lastPos = lastPosNext。 } coutendl。 } } //檢查種群中的適應(yīng)度是否 SIM bool checkFitness(){ HASHNODE *pNode = NULL。 int index = 0。 bool sameFlag = true。 initHashTable(hashTable)。 for(int i=0。 iPOPSIZE 。i++){ index = parentGenome[i].Fitness%DIST。 hashTable[index].Count++。 正文： 基于遺傳算法的背包問題求解 29 pNode = isAlreadyExist(hashTable[index].Next,parentGenome[i].Fitness)。 if(NULL==pNode){ pNode = new HASHNODE。 hashTable[index].Diff++。 pNodeNext = hashTable[index].Next。 pNodeFitness = parentGenome[i].Fitness。 if(parentGenome[i].FitnesshashTable[index].maxFitness){ hashTable[index].maxFitness = parentGenome[i].Fitness。 } hashTable[index].Next = pNode。 } } index = maxFitness(hashTable)。 double CPount = hashTable[index].Count/(double)POPSIZE。 double pDiff = hashTable[index].Diff/(double)POPSIZE。 if(CPount= amp。amp。 pDiff=){ sameFlag = false。 } TraverseHashTable(hashTable)。 return sameFlag。 } //賭輪 選擇函數(shù)代碼段 int Begin = 0。 int End = 1。 //計(jì)算從 Begin－ End位置的染色體的適應(yīng)度之和 正文： 基于遺傳算法的背包問題求解 30 int summaryFitness(int Begin,int End){ int summaryF = 0。 if(BeginEnd){ for(int i=Begin。 iEnd 。i++){ summaryF += parentGenome[i].Fitness。 } }else{ for(int i=Begin。 iPOPSIZE 。i++){ summaryF += parentGenome[i].Fitness。 } for(i=0。 iEnd 。i++){ summaryF += parentGenome[i].Fitness。 } } return summaryF。 } //賭輪選擇染色體以便于交叉操作 int selectIndex(){ double randProb = 。 double crossProb = 。 int summaryBE = 0。 int summaryF = 0。 int index。 bool flag = true。 randProb = rand()%1000/。 正文： 基于遺傳算法的背包問題求解 31 summaryF = summaryFitness(0,POPSIZE)。 while(flag){ summaryBE = summaryFitness(Begin,End)。 crossProb = (double)summaryBE/(double)summaryF。 if(crossProbrandProb){ index = End。 Begin = End。 flag = false。 } End++。 if(EndPOPSIZE){ End = 1。 } } return index。 } //排序輔助數(shù)組 bool visitedFlag[POPSIZE]。 //獲取當(dāng)前 HASH表中的最大 Fitness的索引 int selectedMaxFitness(GENE *Genome){ int maxPos = 0。 for(int i=0。 iPOPSIZE 。i++){ if(!visitedFlag[i]){ maxPos = i。 i = POPSIZE。 正文： 基于遺傳算法的背包問題求解 32 } } for(i=0。 iPOPSIZE 。i++){ if(!visitedFlag[i]amp。amp。Genome[maxPos].FitnessGenome[i].Fitness){ maxPos = i。 } } return maxPos。 } //索引排序 void sortFitness(int *indexFitness,GENE *Genome){ memset(visitedFlag,false,NUMG*sizeof(bool))。 for(int i=0。 iPOPSIZE 。i++){ indexFitness[i] = selectedMaxFitness(Genome)。 visitedFlag[indexFitness[i]] = true。 } } //精英策略：保持優(yōu)秀的父染色體 void keepBestParents(){ for(int i=POPSIZE*8/10。 iPOPSIZE 。i++){ parentGenome[indexPF[i]].Fitness = parentGenome[indexPF[iPOPSIZE*8/10]].Fitness。 parentGenome[indexPF[i]].Weight = parentGenome[indexPF[iPOPSIZE*8/10]].Weight。 for(int j=0。 jNUMG 。j++){ parentGenome[indexPF[i]].Gene[j] = parentGenome[indexPF[iPOPSIZE*8/10]].Gene[j]。 } } 正文： 基于遺傳算法的背包問題求解 33 } //更新當(dāng)前的父代染色體 void updateGeneration(){ keepBestParents()。 for(int i=0。 iPOPSIZE*8/10 。i++){ parentGenome[indexPF[i]].Fitness = nextGenome[indexCF[i]].Fitness。 parentGenome[indexPF[i]].Weight = nextGenome[indexCF[i]].Weight。 for(int j=0。 jNUMG 。j++){ parentGenome[indexPF[i]].Gene[j] = nextGenome[indexCF[i]].Gene[j]。 } } } //交叉操作 void crossOver(){ int partPos。 sortFitness(indexPF,parentGenome)。 for(int i=0。 iPOPSIZE/2 。i+