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