【正文】 ........................................................................................................ 29 GUI 界面設(shè)計 ............................................................................................................................................. 29 ........................................................29 ...........................................................33 第四章 結(jié)論與展望 .............................................................................................................................................. 36 結(jié)論 .............................................................................................................................................................. 36 展望 ............................................................................................................................................................. 36 總結(jié)與體會 ............................................................................................................................................................ 38 設(shè)計（論文）專用紙 第 IV 頁 致謝 ......................................................................................................................................................................... 40 參考文獻 ................................................................................................................................................................ 41 附錄一 源程序 ...................................................................................................................................................... 43 MATLAB 主程序 .............................................................................................................................................. 43 GUI 界面設(shè)計程序 ............................................................................................................................................ 51 附錄二 外文文獻翻譯 ......................................................................................................................................... 60 附錄三 外文文獻原文 ......................................................................................................................................... 71 設(shè)計（論文）專用紙 第 V 頁 前言 背包問題 (Knapsack Problem)是一種組合優(yōu)化 NP完全問題 ，相似的問題經(jīng)常出現(xiàn)在商業(yè)、組合數(shù)學，計算復(fù)雜性理論、密碼學和應(yīng)用數(shù)學等領(lǐng)域中。 設(shè)計（論文）專用紙 學士學位論文 基于遺傳算法的 01 背包問題研究 學 院： 信息工程與自動化學院 專業(yè)年級 : 自動化 2020 級 起止時間： 2020 年 3 月 — 2020 年 6 月 設(shè)計（論文）專用紙 Kun Ming University of Science and Technology Bachelor39。背包問題可分為一維背包，二維背包問題，完全背包問題，多重背包問題、分組背包問題等等。最后在 matlab 環(huán)境中進行 GUI 界面設(shè)計，通過 GUI界面可以直觀的看到 01背包問題的 2個算例在不同參數(shù)設(shè)置下仿真曲線的變化情況。所以在 前人研究經(jīng)驗的基礎(chǔ)上開展對背包問題的研究具有 重要意義 。首先，很多算法的計算量都很大，迭代的時間很長。 本文將對遺傳算法做進一步研究并結(jié)合應(yīng)用于背包問題的求解，并通過實驗證明遺傳算法對求解背包問題是比較有效的。 遺傳算法的研究現(xiàn)狀與發(fā)展趨勢 查克斯在此之后世界范圍內(nèi)掀起了關(guān)于遺傳算法研究與 設(shè)計（論文）專用紙 4 應(yīng)用的高潮。 今 后幾年 ,可以預(yù)期 ,拓廣更加多樣的應(yīng)用領(lǐng)域 ,其中包括各種 遺傳算法 程序設(shè)計環(huán)境的 開發(fā)仍將是遺傳算法發(fā)展的主流 。 這一思想在 90 年代初逐步形成 ,而由模糊集論的創(chuàng)始人 ,美國 Zadeh LA在 1993 年于漢城召開的國際模糊系統(tǒng)協(xié)會 ( IFSA )第五屆世界會議首先明確提出隨后在許多有關(guān)的國際學 術(shù)會議上得到充分體現(xiàn)。 工科數(shù)學教育也應(yīng)有所調(diào)整 ,以適應(yīng)高新技術(shù)發(fā)展的需要 。遺產(chǎn)算法只需自適應(yīng)值和串編碼等通用信息，故幾乎可以處理任何問題。 設(shè)計（論文）專用紙 6 遺傳算法分類 （ 1） 混合遺傳算法 單用簡單的遺傳算法在許多情況下不是十分有效，容易產(chǎn)生早熟現(xiàn)象以及局部尋優(yōu)能力較差等問題，于是提出了多種混 合算法。 個體適應(yīng)度的評價 或計算在遺傳算法的運行過程中所占用的運行時間比較長。 可以對群體按一定的方式進行分組，分組后各組的個體遺傳進化過程可以在不同的處理機上相互獨立地進行，在適當?shù)臅r候，各處理機之間相互交換信息。學者構(gòu)造了各種復(fù)雜的測試函數(shù)，既有連續(xù)函數(shù)也有離散函數(shù)，有高維的也有低維的，有凹的也有凸的，有多峰的也有單峰的，遺傳算法較其他優(yōu)化方法便于得到較好的結(jié)果。例如：利用 GA的機器學習來調(diào)整人工神經(jīng)網(wǎng)絡(luò)的權(quán)值等；利用 GA學習模糊控制的奴隸度函數(shù)以改進模糊控制系統(tǒng)的性能。 d. 在 matlab 環(huán)境中進行 GUI 界面設(shè)計， 運行界面中遺傳算法主要的參數(shù)可通過手動輸入自行修改，同時通過 GUI 界面可以直接觀察到仿真曲線的變化情況。這個群體不斷的經(jīng)過遺傳和進化操作，并 且每次都按照優(yōu)勝劣汰的規(guī)則將適應(yīng)度較高的個體更多的遺傳到下一代，這樣最終在種群中將會得到一個優(yōu)良的個體 X，它所對應(yīng)的的表現(xiàn)型 X 將達到或接近問題的最優(yōu)解 X*。遺傳算法的 執(zhí)行過程包括了大量的隨機性操作，因此有必要對其數(shù)學機理進行分析。 設(shè)計（論文）專用紙 11 定義 定義距 (defining length)模式 H 中的第一個確定位置和最后一個確定位置之間的距離稱為該模式的定義距，記作δ (H)。 滿足這個假設(shè)的條件比較簡單，包括兩方面： a) 表現(xiàn)型相近的個體，其基因型相近； b) 遺傳因子間相關(guān)性低。在每個串中，每個二進制位就是個體染色體的基因。 遺傳算法的原理可以簡要給出如下：選擇初始值，確定合適的值，完成選擇；進行交叉，變異；重復(fù)直到得到最優(yōu)解這里所指的某種結(jié)束準則一般是指個體的適應(yīng)度達到給定的閥值；或者個體的適應(yīng)度的變化率為零。概括地講，遺傳算法求解組合優(yōu)化問題的具體步驟可描述如下： (1)初始化：選擇一個群體，即選擇一個串或個體的集合 bi， i=l， 2，? n。給出目標函數(shù) f，則 f(bi)稱為個 體 bi的適應(yīng)度。這個過程反映了隨機信息交換；目的在于產(chǎn)生新的基因組合，也即產(chǎn)生新的個體。 單靠變異不能在求解中得到好處。運用簡單遺傳算法求解背包問題時，若問題的規(guī)模不大時能夠得到最優(yōu)解或近似最優(yōu)解。每產(chǎn)生一個染色體，就對它進行一次檢驗，如果不滿足約束條件，則拒絕接受。這個問題解的總組合數(shù)有 2 個，其數(shù)學模型表示為：1niii XW C? ??時，使得1niii XP??大， Xi=1 或 0（ i=1， 2，?， n)。)。 %輪盤， rotary table %生成輪盤，類似于概率分布 For i=2:POP_NUM rtable(i)=rtable(i1)+rtable(i)。 % 交叉操作 cross_index=1:POP_NUM。 %交叉點位置 ,[1, POP_NUM1] temp_cross=samp_arr(cross_index(i), cross_pos:end)。 %變異操作，直接針對整個樣本集操作 muta_arr=( rand(POP_NUM, LEN) P_MUTA )。對各個染色體計算其適應(yīng)度值，淘汰適應(yīng)度值最低的，復(fù)制適應(yīng)度值最高的，用最高的代替最低的，這樣完成選擇；再隨機產(chǎn)生交叉點及相互交叉的染色體進行交叉，計算交叉后的染色體是否符合要求，即裝入背包的物品的總體積小于背包容量，若不符合則交叉失敗，重新交叉，達到交叉最多次數(shù)未交叉成功則退出；交叉完成后就進行變異，根據(jù)變異概率隨機選擇變異的染色體，隨機產(chǎn)生變異點進行變異，變異后也需要計算染色體是否符合要求，若不符合則變異失敗，重新變異，達到變異最多次數(shù)未變異成功則退出。 表 21 算例 1求解結(jié)果 循環(huán)次數(shù) 迭代次數(shù) 最優(yōu)值 最差值 平均值 命中最優(yōu)解概率 20 500 3103 1429 45% 從表 21可以看出在程序運行 20次中命中了 9次最優(yōu)解 3103，平均值為 ，最優(yōu)值與最差值的差值為 1674，說明遺傳算法求解背包問題不易陷入局部最優(yōu)。 表 23 不同交叉概率求解算例 1的結(jié)果 交叉概率 總價值 總體積 3091 998 3095 1000 3103 1000 3103 1000 3103 1000 3103 1000 3103 1000 從表 23 可以看出當交叉概率增大時與之對應(yīng)的總值和 總體積 也隨之增加并在交叉概率為 時命中最優(yōu)解，隨著交叉概率增加大依然保持命中最優(yōu)解。 當物品數(shù)量為 50 時，循環(huán) 20 次的結(jié)果如表 25和仿真圖分別如圖 24,圖 25,圖 26 所示。 Pi 與 C 的數(shù)值由以下公式得出。 表 22 不同種群規(guī)模求解算例 1 的結(jié)果 種群規(guī)模 總價值 總體積 100 3094 996 200 3095 996 400 3103 1000 500 3103 1000 從上表可以看出，隨著種群規(guī)模的增大總價值和總體積也隨之增大，并且在種群 設(shè)計（論文）專用紙 23 規(guī)模為 400 的時候已命中最優(yōu)解