【正文】 個個體的期望值小于0時，則該個體不參與選擇。個體適應(yīng)度越大，其被選擇的概率就越高，反之則被選擇的概率越低。在備選集中按照一定的選擇概率進行操作，這個概率取決于種群中個體的適應(yīng)度及其分布。②合理、一致性：要求適應(yīng)度值反映對應(yīng)解的優(yōu)劣程度，這個條件的達成比較難以衡量。⑥自適應(yīng)編碼：實現(xiàn)選擇合適的固定編碼方式對潛在的遺傳算法用戶來說是一個難題。 編碼按照遺傳算法的工作流程，當用遺傳算法求解問題時，必須在目標問題實際表示與遺傳算法的染色體位串結(jié)構(gòu)之間建立關(guān)系，即確定編碼和解碼運算。(4)隨機初始化群體。此外，遺傳算法還被應(yīng)用到反問題求解、機器人學習、生物計算、圖像處理、人工智能以及遺傳編程等領(lǐng)域。在自動控制領(lǐng)域有很多與優(yōu)化相關(guān)的問題需要求解，而且這些優(yōu)化問題通常要么是通過積分表達的，要么是寫不出明確而嚴格的解析表達式。對這類復雜問題，人們己意識到應(yīng)把主要精力放在尋求其滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。[16]1)在求解問題時，遺傳算法首先要選擇編碼方式，它直接處理的對象是參數(shù)的編碼集而不是問題參數(shù)本身，搜索過程既不受優(yōu)化函數(shù)連續(xù)性的約束，也沒有優(yōu)化函數(shù)倒數(shù)必須存在的要求。經(jīng)過近30年的研究、應(yīng)用，遺傳算法已被廣泛地應(yīng)用于函數(shù)優(yōu)化、機器人系統(tǒng)、神經(jīng)網(wǎng)絡(luò)學習過程、模式識別、圖象處理、工業(yè)優(yōu)化控制等領(lǐng)域。至今尚未找到有效的求解方法，在理論上枚舉法可以解這一問題，但是當n較大時，解題的時間消耗會使枚舉法顯得沒有任何實際價值。具有很強的魯棒性。 現(xiàn)代科學理論研究與實踐中存在著大量與優(yōu)化、自適應(yīng)相關(guān)的問題，但除了一些簡單的情況之外，人們對于大型復雜系統(tǒng)的優(yōu)化和自適應(yīng)問題仍然無能為力。最后，簡單說明了遺傳算法在求解背包問題中的應(yīng)用并對遺傳算法解決背包問題的前景提出了展望。背包問題(Knapsack problem)是一種組合優(yōu)化的NP完全問題,對這個問題的求解前人己經(jīng)研究出了不少的經(jīng)典的方法,例如解析法，窮舉法等，但是這些傳統(tǒng)的優(yōu)化方法存在一些缺點，如算法復雜度太高。數(shù)學模型限制條件為：所求表達式為：其中，表示物品放入背包，表示物品未放入背包。背包問題也可描述為決定性問題，相似問題經(jīng)常出現(xiàn)在商業(yè)、投資組合優(yōu)化、組合數(shù)學，計算復雜性理論、密碼學和應(yīng)用數(shù)學等領(lǐng)域中，因此具有廣泛的實際應(yīng)用領(lǐng)域。近年來，遺傳算法從理論到實際都已經(jīng)取得了許多重要成果。而且對于一些非線性、多模型、多目標的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，而遺傳算法卻可以方便地得到較好的結(jié)果。由于可以采用字符編碼，而且不必使用恰好的目標函數(shù)估值，遺傳算法也成為解決復雜調(diào)度問題的有效工具?；谶z傳算法的機器學習在很多方面都得到成功應(yīng)用。具體步驟如下：(l)編碼，把問題的解轉(zhuǎn)化成位串表示形式。③根據(jù)給定的變異率，對每個染色體進行變異操作。④實數(shù)編碼：實數(shù)編碼具精度高、大空間搜索的優(yōu)點。一般而言，適應(yīng)度函數(shù)是由目標函數(shù)變換而成的。它們構(gòu)成了遺傳算法的核心，使得算法具有強大的搜索能力。它也叫賭輪或蒙特卡羅選擇。③期望值方法在賭輪選擇機制中，當個體數(shù)不太多時，依據(jù)產(chǎn)生的隨機數(shù)有可能會出現(xiàn)不正確地反映個體適應(yīng)度的選擇，即存在統(tǒng)計誤差。3)以各個個體所分配到的概率值作為其能夠被遺傳到下一代的概率，基于這些概率值用比例選擇的方法來產(chǎn)生下一代群體。所謂變異運算，是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成一個新的個體。這組參數(shù)在初始階段或種群進化過程中需要合理地選擇和控制。 變異概率變異操作是保持種群多樣性的有效手段，交叉結(jié)束后，交配池中的全部個體位串上的每位等位基因按概率隨機改變，因此每代中大約發(fā)生n次變異。終止進化代數(shù)一般的取值范圍是1001000。 //用元素取值于定義域｛0,1｝的數(shù)組表示染色體。當染色體之間的相似度達到閾值時，算法即停止運行。用summaryF表示當前全部染色體的價值總和。如下程序代碼所示：for(int j=0。}partPos為隨機產(chǎn)生的整數(shù)，代表交叉的位置。其思想是保存上一代中的適應(yīng)性強的染色體。 代際更新代際之間的更新，即用新生成的種群代替取代舊的種群。 //HASH到該結(jié)點的染色體的數(shù)目 int Diff。amp。 int Value[NUMG]={2,20,5,4,19,14,18,8,11,6}。通過上述仿真實驗和數(shù)據(jù)測試，可以得出利用本文算法求解背包問題能夠獲得較滿意的效果。這樣通過選擇和繁殖就產(chǎn)生了下一代群體。 我們通過上述例子，嚴格按照遺傳算法對背包問題進行了完整的求解，事實說明，用遺傳算法來解決此類組合優(yōu)化問題也是比較有效的，而且非常好用，它的解的空間比較大，而且在最后能無限度地接近最優(yōu)解。到目前，遺傳算法的理論機制仍不是很清楚，這可能和生命科學的研究一樣，將是一個永恒的研究課題，但也是一個難題。最后，感謝所有在生活和學習上給予我?guī)椭娜?！參考文獻：[1] 陳國良,[M].北京:人民郵電出版社,~10. [2] 陳文清. 遺傳算法綜述[J]. 武漢: 華中科技大學,~58.[3] [D].博士學位論文，哈爾濱。 HASHNODE *Next。可自行編寫隨機生成染色體的函數(shù)來生成染色體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}}, {0,0,{1,1,1,1,0,0,0,0,0,0}}}。 jNUMG 。 Genome[iD].Weight = Weight[idModify]。 }}//在HASH表頭結(jié)點中搜索最大的適應(yīng)度int maxFitness(HEAD *hashTable){ int maxF = hashTable[0].maxFitness。 while(NULL!=pHead){ if(pHeadFitness==Fitness){ break。 for(int i=0。 } coutendl。 hashTable[index].Count++。 } } index = maxFitness(hashTable)。}//賭輪選擇函數(shù)代碼段int Begin = 0。i++){ summaryF += parentGenome[i].Fitness。 int summaryF = 0。 Begin = End。 iPOPSIZE 。 } } return maxPos。i++){ parentGenome[indexPF[i]].Fitness = parentGenome[indexPF[iPOPSIZE*8/10]].Fitness。i++){ parentGenome[indexPF[i]].Fitness = nextGenome[indexCF[i]].Fitness。 iPOPSIZE/2 。 } for(。 calculateFitness(nextGenome,i+POPSIZE/2)。 nextGenome[i].Weight = Weight[partPos]。i++){ coutparentGenome[i].Weight。 bool flag = true。 } } checkCapacity(parentGenome,i)。nCountnGenerations){ nCount++。 indexMaxResult = maxFitness(hashTable)。 }}。 coutThe information in Genome is as below:endl。 //交叉 mutation()。用于隨機產(chǎn)生染色體 //generatePopulation()。 //初始化染色體種群 for(int i=0。 for(int j=0。 }else{ if(nextGenome[i].Weight+Weight[partPos]CAPACITY){ nextGenome[i].Gene[partPos]=1。 } sortFitness(indexCF,nextGenome)。j++){ nextGenome[i].Gene[j] = parentGenome[Father].Gene[j]。 int Father = selectIndex()。 for(int j=0。 for(int j=0。 for(int i=0。 i = POPSIZE。 } End++。 bool flag = true。 iEnd 。//計算從Begin－End位置的染色體的適應(yīng)度之和int summaryFitness(int Begin,int End){ int summaryF = 0。 double pDiff = hashTable[index].Diff/(double)POPSIZE。 if(NULL==pNode){ pNode = new HASHNODE。 int index = 0。i++){ if(hashTable[i].Count==0){ continue。 lastPos = pHead。 for(int i=1。 } }}//初始化HASH表void initHashTable(HEAD * hashTable){ for(int i=0。 } }}//計算染色體的適應(yīng)度void calculateFitness(GENE * Genome,int iD){ Genome[iD].Fitness = 0。//新的染色體//需要裝入背包的物品的大小和價值int Weight[NUMG]={6,9,8,8,6, 1, 10,5,7, 1}。//頭結(jié)點//HASH表HEAD hashTable[DIST]。define SIM //算法終止條件之一：染色體之間的相似度上限define MP //變異率define DIST 13 //程序中HASH表的距離//程序中用到的HASH表中鏈表結(jié)點結(jié)構(gòu)定義typedef struct Node{ int Fitness。首先，我衷心地感謝我的指導老師鄧大勇老師，我的整個論文都是在鄧大勇老師的關(guān)懷和細心指導下完成的。6 展望遺傳算法作為一種對生物進化現(xiàn)象進行仿真的程序，取得了人工遺傳的模擬效果，具有自適應(yīng)性。進化過程最后一代中的最優(yōu)解就是用遺傳算法解最優(yōu)化問題所得到的最終結(jié)果。因此，我們認為本文算法是可行的和有效的。程序的初始狀態(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。}如果當前maxFitness最大的頭結(jié)點滿足if語句中的判斷條件，則sameFlag置為真，即算法停止迭代的條件得到了滿足。}HEAD。實際上，父代種群中優(yōu)秀的染色體已被保留，updateGeneration中只是用新種群中的優(yōu)秀染色體來代替