【正文】 。選擇機制保證適應(yīng)度較高的個體能夠保留較多的樣本；而適應(yīng)度較低的個體則保留較少的樣本，甚至被淘汰。交叉算法交換隨機挑選的兩個個體的某些位，變異算子則直接對一個個體中的隨機挑選的某一位進行突變。重復(fù)上述選擇和繁殖過程，直到結(jié)束條件得到滿足為止。 與其他算法相比，遺傳算法主要有以下四個方面的不同： 遺傳算法的搜索是基于若干個點，而不是基于一個點； 遺傳算法的轉(zhuǎn)化規(guī)則是概率性的，而不是確定性的。所以，用遺傳算法來解決背包問題是一個很好的方法。在遺傳算法的結(jié)構(gòu)中遺傳操作和選擇機制是兩個重要的因素，其聯(lián)系可用遺傳算法=遺傳操作+選擇過程這個邏輯關(guān)系來表示。可喜的是,近年來遺傳算法在商業(yè)應(yīng)用方面取得了一系列重要成果。遺傳算法具有隱并行性，它可容易改造成為并行/分布式算法，用來解決那些復(fù)雜性問題。致謝在論文即將完成之際，我非常感謝所有幫助過和支持過我的人。鄧?yán)蠋煆恼撐牡倪x題到完成，在各方面都給予了我大力的支持、耐心的幫助和熱情地勉勵，使我能夠面對各種問題和困難，順利地完成論文寫作。同時，在整個論文完成的過程中，同學(xué)和朋友對我的幫助也使我收益良多，不光是精神上的鼓勵，還有學(xué)術(shù)上的幫助，讓我一步步走下來，克服了一個又一個的困難，這也是我所收獲的。在此，我也非常感謝家人對我的支持。哈爾濱工業(yè)大學(xué)，1994.[4] 李敏強，寇紀(jì)松，[M].北京:科學(xué)出版社，2002.[5] [J].西安交通大學(xué)博士論文，1997.[6] 周　明,孫樹棟. 遺傳算法原理及應(yīng)用[M] . 北京:國防工業(yè)出版社,1999[7] 席裕庚,[J].,13(6):697—708.[8] 吉根林. 遺傳算法研究綜述[J ] . 計算機應(yīng)用與軟件,2004 ,21 , (2) :69～71[9] 玄光南,程潤偉著. 遺傳算法與工程優(yōu)化[M ]. 清華大學(xué)出版社,北京: 2004. [10] 印鑒，李明．基于遺傳算法的最優(yōu)布局求解[J]．計算機研究與發(fā)展，2002，39(1O)： 126％．1273． [11] 王小平,曹立明著. 遺傳算法:理論、應(yīng)用與軟件實現(xiàn)[M ]. 西安交通大學(xué)出版社,西安: 2002. [12]周云鵬，題正義．遺傳算法在組合優(yōu)化中的應(yīng)用[M]．遼寧工程技術(shù)大學(xué)學(xué)報 [13] 肖美華，王命延，王洪發(fā)，等．基于遺傳算法和模擬退火算法的布局問題研究[J]．計算機工程與應(yīng)用，2003，39(36)：7072． [14]姜靈敏，陳松喬．二重結(jié)構(gòu)編碼遺傳算法及其在貸款組合優(yōu)化決策中的應(yīng)用[J]．小型微型計算機系統(tǒng) [15] Mitchell, M. (1998). An Introduction to Genetic Algorithms. Massachusettss: The MIT Press. [16]史今遲．背包問題的實用求解算法研究[J]．山東大學(xué)學(xué)報[17] [M].北京:清華大學(xué)出版社,2001. [18] [19] [20] 附源程序：includeincludeincludeincludedefine POPSIZE 10 //定義種群大小define NUMG 10 //每個染色體中基因的數(shù)量define MAXVOL 10 //物品大小的上限define MAXVAL 20 //物品價值的上限define CAPACITY 30 //背包的大小define MAXB (1024) //2的10次方，用來隨機產(chǎn)生一個染色體時候很有用。 struct Node *Next。//鏈表結(jié)點//程序中用到的HASH表中頭結(jié)點結(jié)構(gòu)定義typedef struct Head{ int maxFitness。 int Diff。}HEAD。//染色體的基因結(jié)構(gòu)定義typedef struct{ int Weight。 //適應(yīng)度 int Gene[NUMG]。//染色體基因結(jié)構(gòu)//這里使用固定生成的染色體基因組，便于調(diào)試。GENE nextGenome[NUMG]。int Value[NUMG]={2,20,5,4,19,14,18,8,11,6}。//父染色體索引int indexCF[POPSIZE]。 for(int j=0。j++){ if(Genome[iD].Gene[j]==1){ Genome[iD].Weight += Weight[j]。 for(int j=0。j++){ if(Genome[iD].Gene[j]==1){ Genome[iD].Fitness += Value[j]。 if(Genome[iD].Gene[idModify]==1){ Genome[iD].Gene[idModify] = 0。 Genome[iD].Fitness = Value[idModify]。 iDIST 。 hashTable[i].Count = 0。 hashTable[i].Next = NULL。 int index =0。 iDIST 。 index = i。}//判斷適應(yīng)度Fitness是否已經(jīng)在HASH頭結(jié)點對應(yīng)的鏈表中HASHNODE* isAlreadyExist(HASHNODE *pHead,int Fitness){ HASHNODE *lastPos = NULL。 } //coutpHeadFitnessendl。 pHead = pHeadNext。}//遍歷HASH表void TraverseHashTable(HEAD * hashTable){ int index = 0。 coutI:MAX:C:D:Oendl。 iDIST 。 } couti:hashTable[i].maxFitness:hashTable[i].Count:hashTable[i].Diff:。 coutContent:。 lastPos = lastPosNext。 }}//檢查種群中的適應(yīng)度是否SIMbool checkFitness(){ HASHNODE *pNode = NULL。 bool sameFlag = true。 for(int i=0。i++){ index = parentGenome[i].Fitness%DIST。 pNode = isAlreadyExist(hashTable[index].Next,parentGenome[i].Fitness)。 hashTable[index].Diff++。 pNodeFitness = parentGenome[i].Fitness。 } hashTable[index].Next = pNode。 double CPount = hashTable[index].Count/(double)POPSIZE。 if(CPount= amp。 pDiff=){ sameFlag = false。 return sameFlag。int End = 1。 if(BeginEnd){ for(int i=Begin。i++){ summaryF += parentGenome[i].Fitness。 iPOPSIZE 。 } for(i=0。i++){ summaryF += parentGenome[i].Fitness。}//賭輪選擇染色體以便于交叉操作int selectIndex(){ double randProb = 。 int summaryBE = 0。 int index。 randProb = rand()%1000/。 while(flag){ summaryBE = summaryFitness(Begin,End)。 if(crossProbrandProb){ index = End。 flag = false。 if(EndPOPSIZE){ End = 1。}//排序輔助數(shù)組bool visitedFlag[POPSIZE]。 for(int i=0。i++){ if(!visitedFlag[i]){ maxPos = i。 } } for(i=0。i++){ if(!visitedFlag[i]amp。Genome[maxPos].FitnessGenome[i].Fitness){ maxPos = i。}//索引排序void sortFitness(int *indexFitness,GENE *Genome){ memset(visitedFlag,false,NUMG*sizeof(bool))。 iPOPSIZE 。 visitedFlag[indexFitness[i]] = true。 iPOPSIZE 。 parentGenome[indexPF[i]].Weight = parentGenome[indexPF[iPOPSIZE*8/10]].Weight。 jNUMG 。 } }}//更新當(dāng)前的父代染色體void updateGeneration(){ keepBestParents()。 iPOPSIZE*8/10 。 parentGenome[indexPF[i]].Weight = nextGenome[indexCF[i]].Weight。 jNUMG 。 } }}//交叉操作void crossOver(){ int partPos。 for(int i=0。i++){ partPos = rand()%NUMG。 int Mother = selectIndex()。 jpartPos 。 nextGenome[i+POPSIZE/2].Gene[j] = parentGenome[Mother].Gene[j]。jNUMG。 nextGenome[i+POPSIZE/2].Gene[j] = parentGenome[Mother].Gene[j]。 calculateFitness(nextGenome,i)。 calculateCapacity(nextGenome,i+POPSIZE/2)。 checkCapacity(nextGenome,i+POPSIZE/2)。}//變異操作void mutation(){ for(int i=0。i++){ double prob = (rand()%1000)/。 if(nextGenome[i].Gene[partPos]==1){ nextGenome[i].Gene[partPos]=0。 nextGenome[i].Fitness = Value[partPos]。 nextGenome[i].Weight += Weight[partPos]。 }else{ //don39。 iPOPSIZE 。 coutparentGenome[i].Fitness。 jNUMG 。 } coutendl。 int nCount = 0。 int indexMaxResult = 0。 iPOPSIZE 。 jNUMG 。 parentGenome[i].Fitness += Value[j]。 } //generateChromosomes()。//用于隨機產(chǎn)生種群 printGenome()。 coutnCountendl。amp。 //當(dāng)前循環(huán)次數(shù) crossOver()。 //變異 updateGeneration()。 //打印種群中染色體 flag = checkFitness()。 } coutnCountendl。//所得的01背包問題的最大值 if(nCountnGenerations){//成功 coutThe maxValue is hashTable[indexMaxResult].maxFitnessendl。 printGenome()。 coutThe maxValue may be hashTable[indexMaxResult].maxFitnessendl。 printGenome()