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