【正文】 正文： 基于遺傳算法的背包問題求解 20 致謝 在論文即將完成之際，我非常感謝所有幫助過和支持過我的人。選擇機制保證適應正文： 基于遺傳算法的背包問題求解 19 度較高的個體能夠保留較多的樣本；而適應度較低的個體則保留 較少的樣本，甚至被淘汰。程序中設定了算法的最大迭代次數(shù)為1000。 HASH 表中的頭結點紀錄了頭結點所指向的單鏈表的信息。這里沒有使后代死亡，而是隨機地調整了染色體中的基因。假設如下兩個父代： 父代 1: 1 14 2 13 8 6 3 2 5 4 3 4 3 2 4 父代 2: 1 12 3 5 6 8 5 6 3 1 8 5 6 3 3 隨機選擇一個交叉點為 11，交叉后為： 子代 1: 1 14 2 13 8 6 3 2 5 4 8 5 6 3 3 子代 2: 1 12 3 5 6 8 5 6 3 1 3 4 3 2 4 交叉過程的目的就是希望新的基因是由舊的基因中好的部分組合而成的，從而新的基因比原先的基因要好。 MAXB：二進制表示的染色體換算之后的最大十進制整數(shù)。 常用的辦法是預先給定算法的終止進化代數(shù)。 ②維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。排序選擇機制的主要思想是：對群體中的所有個體按其適應度大小進行排序，基于這個排序來分配各個體被選中的概率。選擇算子可看作是種群空間到父體空間的隨機映射，它按照某種準則或概率分布從當前種群中以高的概率選取那些好的個體組成不同的父體以供生成新的個體。因此，許多用戶認為既然要用遺傳算法解決問題，為什么不讓它同時調整編碼呢 ?一些專家就采用了自適應編碼 [11]。 (6)按照遺傳操作形成下一代群體 。例如，用遺傳算法進行航空控制系統(tǒng)的優(yōu)化、用遺傳算法優(yōu)化設計透平機械、設計模糊控制器等，都取得了較好的效果。 遺傳算法的 應用領域 遺傳算法的主要應用領域包括以下幾個方面： 函數(shù)優(yōu)化問題。 背包問題的求解，一直以來倍受人們的關注。遺傳算法正是借鑒生物的自然選擇和遺傳進化機制而開發(fā)出的一種全局優(yōu)化自適應概率搜索算法?；静挥盟阉骺臻g的知識或其他輔助信息，而僅用適應度 來評估個體優(yōu)劣 。它是在 1975 年首次由美國密西根大學的 D. J. Holland 教授和他的同事們借鑒生物正文： 基于遺傳算法的背包問題求解 3 界自然選擇和進化機制基礎之上提出的。隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴大，有時在目前的計算機上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。被用來調整人工神經網(wǎng)絡的連接權及網(wǎng)絡拓 撲優(yōu)化。 (7)判斷新產生的群體是否能滿足結束指標，如果滿足，則算法結束，如果不滿足，則返回步驟 (6)。 適應度函數(shù)的設計主要滿足以下條件： ①單值、連續(xù)、非負、最大化 :這 個條件是容易理解和實現(xiàn)的。 設群體大小為 n，其中個體 i 的適應度值為 fi，則 i 被選擇的概率 psi為： /si i ip f f? ? （ 41） 顯然，概率 psi反映了個體 i 的適應度在整個群體的個體適應度總和中所占的比例。 交叉算子 交叉操作是遺傳算法中最主要的遺傳操作。 群體規(guī)模 大種群含有較多模式，為遺傳算法提供了足夠的模式采樣容量，可以改進 GA搜索的質量，防止早熟前收斂。 xi∈｛ 0,1｝， xi=1 表示物品 i 裝入了背包， xi =0 表示物品 i 未裝入背包。 PM= ：變異概率為 20％，變異可以保證種群的多樣性，從而防止算法收斂于某個局部解。j++){ nextGenome[i].Gene[j] = parentGenome[Father].Gene[j]。 程序中精英策略由 keepBestParents 函數(shù)和 sortFiness 函數(shù)來實現(xiàn)。 }HEAD。程序的初始狀態(tài)和結束狀態(tài)如下面的表格所示： 初始的種群 : Weight Value 染色體中的基因 21 52 0010110101 22 23 0011000101 22 40 0001100011 22 53 0100010110 26 45 1010011001 24 5 1100010011 正文： 基于遺傳算法的背包問題求解 13 3 22 53 0100010110 23 25 1011010000 26 48 1010110100 25 29 0111000000 初始的 HASH 表 : 頭結點索引 maxFitness Count Diff 單鏈表中的結點內容 0 52 1 1 52: 1 53 4 2 53:40 3 29 1 1 29: 6 45 1 1 45: 9 48 1 1 48: 10 23 1 1 23: 12 25 1 1 25: 不同交叉概率下所得測試結果 在程序 實現(xiàn)上，本文采用 VC++ 作為程序開發(fā)工具，測試是在奔騰 ，512M 以上內存的微機上進行的，操作系統(tǒng)是 WinXP。進化過程最后一代中的最優(yōu)解就是用遺傳算法解最優(yōu)化問題所得到的最終結果。每一次，碰到一個困難，不知該如何繼續(xù)的時候，總是身邊的朋友鼓勵我，幫助我查找相關資料，因為對人工智能不太熟悉，所以論文完成階段也是困難重重，但通過網(wǎng)上論壇上咨詢，朋友的幫助，也一步步克服了困難，所以在這里也要特別感謝那些幫助過我的認識的和不認識的朋友。 如果一個應用問題不能求得目標函數(shù)的全局最優(yōu)值 ,而只能或只希望求一定意義下的 滿意解 ，這時 ,可供選擇的方法之一自然是遺傳算法，因為遺傳算法比其他算法有更多的優(yōu)勢。 通過上述仿真實驗 和數(shù)據(jù)測試 ，可以得出利用本文算法求解背包問題能夠獲得較滿意的效果。amp。 代際更新 代際之間的更新，即用新生成的種群代替取代舊的種群。 } partPos 為隨機產生的整數(shù)，代表交叉的位置。 用 summaryF 表示當前全部 染色體的價值總和。 //用元素取值于定義域｛ 0,1｝的數(shù)組表示染色體。 變異概率 變異操作是保持種群多樣性的有效手段，交叉結束后，交配池中的全部個體位串上的每位等位基因按概率隨機改變，因此每代中大約發(fā)生 n 次變異。所謂變異運算，是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成一個新的個體。 ③期望值方法 在賭輪選擇機制中，當個體數(shù)不太多時，依據(jù)產生的 隨機數(shù)有可能會出現(xiàn)不正正文： 基于遺傳算法的背包問題求解 7 確地反映個體適應度的選擇，即存在統(tǒng)計誤差。它們構成了遺傳算法的核心，使得算法具有強大的搜索能力。 ④實數(shù)編碼：實數(shù)編碼具精度高、大空間搜索的優(yōu)點。具體步驟如下： (l)編碼，把問題的解轉化成位串表示形式 。由于可以采用字符編碼，而且不必使用恰好的目標函數(shù)估值，遺傳算法也成為解決復雜調度問題的有效工具。近年來，遺傳算法從理論到實際都已經取得了許多重要成果。 數(shù)學模型限制條件為 ：1niii WX C? ?? 所求表達式為 ：1 ?niiiMAX V X? ?? 其中 ， {0,1},1 ,iX i n? ? ?1iX? 表示物品放入背包 ， 0iX? 表示物 品未放入背包。 理工類 本科 生 畢業(yè)設計（論文） ( 2020屆 ) 題 目： 基于遺傳算法求解背包問題 學 院： 數(shù)理與信息工程學院 專 業(yè)： 計算機科學與技術 學生姓名： 金甜甜 學號： 06220313 指導教師 ： 鄧大勇 職稱： 副教授 合作導師： 職稱： 完成時間： 2020 年 3 月 31 日 成 績： 理工類 浙江師范大學本科畢業(yè)設計 (論文 )正文 目 錄 摘 要 ....................................................................................................................................1 1 引 言 ...............................................................................................................................1 2 背包問題概述 ...................................................................................................................2 3 遺傳算法概 述 ...................................................................................................................2 遺傳算法的特點 ......................................................................................................3 遺傳算法的應用領域 ...............................................................................................3 4 遺傳算法的基本原理 ........................................................................................................4 基