【正文】 as tested and proved the effectiveness of the geic algorithm for solving knapsack problem。s Degree Thesis Geic Algorithm for 01 Knapsack Problem College： Faculty of Information Engineering and Automation Profession： Automation Class Three, Grade 2020 Name： Number： Teacher： Position： Experimentalist Time: March 2020— June 2020 設(shè)計(jì)（論文）專用紙 畢業(yè)設(shè)計(jì)（論文）任務(wù)書 信自 院 自動(dòng)化 專業(yè) 09 級(jí) 學(xué)生姓名： 畢業(yè)設(shè)計(jì)（論文）題目： 基于遺傳算法的 01背包問題研究 畢業(yè)設(shè)計(jì)（論文）內(nèi)容： ； ； 01背包問題，并在 matlab環(huán)境中實(shí)現(xiàn)仿真； matlab環(huán)境中進(jìn)行 GUI界面設(shè)計(jì)，實(shí)現(xiàn)相關(guān)參數(shù)的輸入與進(jìn)化曲線的輸出顯示。 專題（子課題）題目： 專題（子課題）內(nèi)容： 畢業(yè)設(shè)計(jì)（論文）指導(dǎo)教師（簽字）： 主 管 教 學(xué) 院 （部） 長(zhǎng)（簽字）： 年 月 日 設(shè)計(jì)（論文）專用紙 第 I 頁(yè) 摘要 本文介紹了 01 背包問題的基本概念，綜述了求解 01 背包問題的傳統(tǒng)方法；對(duì)遺傳算法進(jìn)行了理論研究，詳細(xì)的闡述了遺傳算法的基本原理、研究趨勢(shì)和在 01背包問題中的應(yīng)用；利用 Matlab 仿真平臺(tái)對(duì) 2 個(gè)算例進(jìn)行了測(cè)試，證明了遺傳算法求解背包問題的有效性；通過實(shí)例分析了種群規(guī)模、迭代次數(shù)以及變異概率對(duì)算法結(jié)果的影響； 設(shè)計(jì)了圖形用戶界面（ GUI） ，實(shí)現(xiàn)了參數(shù)的輸入與仿真結(jié)果顯示。 Analyzes the population size, number of iterations, and the influence of the mutation probability on the algorithm results。 遺傳算法（ Geic Algorithm）是一類借鑒生物界的進(jìn)化規(guī)律（適者生存，優(yōu)勝劣汰遺傳機(jī)制）演化而來(lái)的隨機(jī)化搜索方法。 在論文首先詳細(xì)介紹了遺傳算法的數(shù)學(xué)基礎(chǔ)、基本原理、實(shí)現(xiàn)過程，以及使用遺傳算法求解 01 背包問題的 2 個(gè)算例并得到相關(guān)仿真結(jié)果，并對(duì)仿真結(jié)果進(jìn)行分析。背包問題主要思路是假定一個(gè)人擁有大量物品，物品的重量各不相同，他要選擇一些物品放入背包中。 在我們的現(xiàn)實(shí)生活中許多問題都可以用背包問題來(lái)描述，例如工廠中的下料問題、管理中的資源分配問題、裝箱問題、資金預(yù)算問題等等都可以建模為背包問題。此后 20幾年背包問題沒有較大的發(fā)展，直到 1974 年，hoeowitz 和 salmi 利用分支節(jié)點(diǎn)法 [3]解答背包問題，他們提出背包問題的可分性，為該問題的求解指出了一條新型道路。 傳統(tǒng)求解背包問題的方法可以概括為精確算法和近似算法，其中精確算法有動(dòng)態(tài)規(guī)劃法，回溯法和分支限界法，近似算法有遺傳算法，貪婪算法和蟻群算法，由于精確算法的時(shí)間復(fù)雜性和空間復(fù)雜性等缺點(diǎn)，近年來(lái)利用近似算法求解背包問題已成為重點(diǎn)。第二，貪婪算法速度快，爬坡能力強(qiáng)，但是它適用于搜索局部最優(yōu)解 ,可能會(huì)陷入局部極值而得不到全局最優(yōu)解。 其次， 進(jìn)化算子的各態(tài)歷經(jīng)性使得遺傳算法能夠非常有效地進(jìn)行概率意義的全局 搜索 。進(jìn)化算法最初是借鑒了進(jìn)化生物學(xué)中的一些現(xiàn)象而發(fā)展起來(lái)的，這些 設(shè)計(jì)（論文）專用紙 3 現(xiàn)象包括遺傳、突變、自然選擇以及雜交等 。在遺傳算法的每一代中，根據(jù)個(gè)體在問題領(lǐng)域中的適應(yīng)度值和從自然遺傳學(xué)中借鑒來(lái)的再造方法進(jìn)行選擇，產(chǎn)生一個(gè)新的近似解。凡是在生存斗爭(zhēng)中獲勝的個(gè)體對(duì)環(huán)境的適應(yīng)性都比較強(qiáng)，因此生物進(jìn)化的過程就是這種“物競(jìng)天擇，適者生存”的過程，這種過程是一個(gè)緩慢的、連續(xù)和長(zhǎng)期的過程。他將遺傳算法定義為適應(yīng)算法，可以廣泛的應(yīng)用于系統(tǒng)最優(yōu)化的研究， 1975 年 DeJone 做了大量實(shí)驗(yàn)，建立了著名的 DeJone 的測(cè)試函數(shù) [5]。 1991 年 Davis 在他的《 Hand book of geic algorithm》 [7]一書中介紹了大量的實(shí)例。 遺傳算法在應(yīng)用方面取得的豐碩成果 ,使人們對(duì)它的發(fā)展前景充滿信心 。 與此同時(shí) ,這并不意味著理論研究會(huì)被忽視 , 這方面同樣有大量工作要做。 當(dāng)前一個(gè)特別值得重視的趨勢(shì)是一些面向?qū)ο?的智能技術(shù) ,其中主要是模糊邏輯 [8](Fuzzy Logic, FL ),神經(jīng)網(wǎng)絡(luò) [9](Neural Network, NN )以及遺傳算法等的綜合應(yīng)用。 例如 ,清華大學(xué)李衍達(dá)院士領(lǐng)導(dǎo)的研究集體在幾乎同一時(shí)期開展了這一重要方向的研究 1995年 , Zadeh 在 IFSA 的第六屆世界會(huì)議上再次強(qiáng)調(diào)了這一方向的重要 設(shè)計(jì)（論文）專用紙 5 性 ,并且認(rèn)為上述所謂的混合智能系統(tǒng)的應(yīng)用將覆蓋從消費(fèi)品生產(chǎn)到核反應(yīng)堆設(shè)計(jì)以至證券管理 ,而 “ 在未來(lái)幾年中可能無(wú)處不在 ” 。 學(xué)術(shù)界要主動(dòng)和企業(yè)界連手開發(fā)遺傳算法的應(yīng)用 ,要重視引進(jìn)或自行研制類似 于 SP licer 的程序設(shè)計(jì)環(huán)境 ,使遺傳算法的應(yīng)用更加方便和快捷 。 遺傳算法的特點(diǎn) a. 算法從問題解的串集開始搜索，而不是從單一解開始。 b. 求解時(shí)使用特定問題的信息極少，容易形成通用算法程序。 遺傳算法的初始串 集本身就帶有大量與最優(yōu)解甚遠(yuǎn)的信息。 d. 算法中的選擇、交叉、和變異都是隨機(jī)操作，而不是確定的精確規(guī)則。混合遺傳算法的基本思想是：對(duì)于每個(gè)新產(chǎn)生的后代在其進(jìn)入下一代群體之前應(yīng)用局部?jī)?yōu)化技術(shù) (如爬山法、模擬退火算法等 )，使之移動(dòng)到最近的局部最優(yōu)點(diǎn)。并行遺傳算法主要從下列四個(gè)方面對(duì)其進(jìn)行改進(jìn)和發(fā)展。 互依賴關(guān)系，這樣各個(gè)個(gè)體的適應(yīng)度計(jì)算過程就可以相互獨(dú)立、并行地進(jìn) 行。這樣，產(chǎn)生群體過程中的選擇、交叉、變異操作就可以相互獨(dú)立地并行進(jìn)行。其典型應(yīng)用領(lǐng) 域如下。 。 ，遺傳算法在自動(dòng)控制領(lǐng)域的應(yīng)用日益增加并取得了較好的成果。 。數(shù)據(jù)挖掘就是大型數(shù)據(jù)庫(kù)中提取人們感興趣的、隱含的、有潛在應(yīng)用價(jià)值的知識(shí) 。介紹了進(jìn)化算法的基本理論，對(duì)典型的幾種進(jìn)化算法進(jìn)行了簡(jiǎn)要說明，并對(duì)遺傳算法的基本理論、應(yīng)用情況和研究趨勢(shì)做了較為詳細(xì)的論述。它最早是有沒過密歇根大學(xué)的 Holland 教授提出的，起源于 60 年代對(duì)自然和人工自適 應(yīng)系統(tǒng)的研究 [13]。 生物進(jìn)化是以集團(tuán)為主體的，與此相適應(yīng)的，遺傳算法的運(yùn)算對(duì)象是由 M個(gè)個(gè)體所組成的集合，成為群體。 b) 個(gè)體適應(yīng)度評(píng)價(jià)：基本遺傳算法按與個(gè)體適應(yīng)度成正比的概率來(lái)決定當(dāng)前群體中每個(gè)個(gè)體遺傳到下一代群體中的機(jī)會(huì)多少。還是求目標(biāo)函數(shù)的最小值 )及其數(shù)學(xué)描述形式或量化方法； 第三步：確定表示可行解的染色體編碼方法，即確定出個(gè)體的基因型 X及遺傳算法的搜索空間； 第四步：確定解碼方法， 即確定出由個(gè)體基因型 x 和個(gè)體表現(xiàn)型 X的對(duì)應(yīng)關(guān)系或轉(zhuǎn)換方法； 第五步：確定個(gè)體適應(yīng)度的量化評(píng)價(jià)方法，即確定出由目標(biāo)函數(shù)值 f(x)個(gè)體適應(yīng)度 F(X)的轉(zhuǎn)換規(guī)則； 第六步：設(shè)計(jì)遺傳算子，即確定出選擇運(yùn)算、交叉運(yùn)算、變異運(yùn)算等遺傳算子的具體操作方法； 第七步：確定遺傳算法的有關(guān)運(yùn)行參數(shù)，即確定出遺傳算法的 M， Pc， Pm等參數(shù)。它將 GA 的運(yùn)算過程理解為模式運(yùn)算過程，并從模式運(yùn)算的角度解釋 GA 的性能特點(diǎn)。例如： o(011*1*)=4。 在遺傳操作中，即使階數(shù)相同的模式，也會(huì)有不同的性質(zhì)，而模式的定義距就反映了這種性質(zhì)的差異。 定義 積木塊 (building block)在模式定理中所指的具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng) 度的模式被定義為積木塊。模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長(zhǎng)，從而滿 足求最優(yōu)解的必要條件，即遺傳算法存在找到全局最優(yōu)解的可能性；而積木塊假設(shè)指出，遺傳算法具備尋找全局最優(yōu)解的能力，即積木塊在遺傳算子的作用下，能生成低階、短距、高平均適應(yīng)度的模式，最終生成全局最優(yōu)解。很明顯，遺傳算法是一種最優(yōu)化方法，它通過進(jìn)化和遺傳機(jī)理，從給出的原始解群中，不斷進(jìn)化產(chǎn)生新的解，最后收斂到一個(gè)特定的串 bi 處，即求出最優(yōu)解。這些選中的個(gè)體用于繁殖下一代。 c) 變異 (Mutation)：這是在選中的個(gè)體中，對(duì)個(gè)體中的某些基因執(zhí)行異向轉(zhuǎn)化。在解決具體問題時(shí)先大致 確定問題的潛在解的一個(gè)集合，這個(gè)集合就是算法的初始種群。這樣在最后滿足收斂條件后的種群最優(yōu)個(gè)體就是問題的近似最優(yōu)解。一般取 n=30在選擇時(shí)，以適應(yīng)度為選擇原則。 a) 適應(yīng)度較高的個(gè)體，繁殖下一代的數(shù)目較多。 (3)交叉：對(duì)于選中用于繁殖下一代的個(gè)體，隨機(jī)地選擇兩個(gè)個(gè)體的相同位置，按交叉概率 pc。 例如有個(gè)體： S1=100101； S2=010111 選擇它們的左邊 3位進(jìn)行交叉操作，則有：S1=010101； S2=l00111 一般而言，交叉概率取值為 。例如有個(gè)體 S=101011。因?yàn)樵谒械膫€(gè)體一樣時(shí)，交叉是無(wú)法產(chǎn)生新的個(gè)體的，這時(shí)只能靠變異產(chǎn)生新的個(gè)體。 遺傳算法流程圖如圖 21 所示： 設(shè)計(jì)（論文）專用紙 15 圖 21 遺傳算法流程圖 一個(gè)簡(jiǎn)單的遺傳算法被 Goldberg 用來(lái)進(jìn)行輪廓描述并用來(lái)舉例說明遺傳算法的基本組成。隨機(jī)初始化染色體，給出物品體積、物品價(jià)值和背包容量 C。也就是說，現(xiàn)在這個(gè)背包里只有 7 這三個(gè)物件。 具體說來(lái)，最終會(huì)產(chǎn)生 M 條染色體，而每條染 色體又有 N個(gè)基因，也就是每條染色長(zhǎng)度是 N。 設(shè)計(jì)（論文）專用紙 17 由于我們之前定義當(dāng)物件 i 被選入背包時(shí)， 設(shè)定變量 Xi=1，否則是 Xi=0。 把所有的物品都放到背包里，那么就可能就會(huì)大于背包容量，如果大于的話，根據(jù)價(jià)值密度的排序，把價(jià)值密度低對(duì)應(yīng)的背包去除，一直到滿足設(shè)定的背包容量為止。 if temp_sum(i) MAX_CAP [temp, index]=sort(rate, 39。 if samp_arr(i,index(j))==1 samp_arr(i,index(j))=0。相應(yīng)程序如下： % 選擇操作（輪盤賭） fit_sum=sum(fit_arr)。 index=1。 (5)交叉操作：判斷染色體是否為活的染色體，若為活的染色體，則將染色體進(jìn)行交叉，一般采用一點(diǎn)交叉方式，交叉概率為 Pc，具體操作是在個(gè)體串中隨機(jī)設(shè)定一個(gè)交叉點(diǎn)，實(shí)行交叉時(shí)，該點(diǎn)前或后的兩個(gè)個(gè)體的部分結(jié)構(gòu)進(jìn)行互換，并生成兩個(gè)新 設(shè)計(jì)（論文）專用紙 19 個(gè)體。%在 1到 POP_NUMi+1之間取隨機(jī)數(shù) temp_pos=i+temp1。 end 選擇個(gè)體中的兩個(gè)位置，把這兩個(gè)位置對(duì)應(yīng)的值進(jìn)行交換， 交叉操作 先對(duì)可能要經(jīng)行交叉的樣本進(jìn)行索引，隨機(jī)得到一個(gè)數(shù)若這個(gè)數(shù)小于交叉概率的話進(jìn)行相鄰交叉否則不交叉。 samp_arr(cross_index(i+1), cross_pos:end)=temp_cross。先選擇一個(gè)變異位進(jìn)行變異，再計(jì)算它的適應(yīng)度，看它是否大于或等于其原來(lái)的適應(yīng)度，若不是的話就重新選擇變異位進(jìn)行變異。 samp_arr(index)=1samp_arr(index)。 %index記錄所取得物體編號(hào) 數(shù)值試驗(yàn)以及結(jié)果分析 程序思路分析如下 ： 采用二進(jìn)制 0I 編碼。 算例 1 A． 實(shí)驗(yàn)設(shè)置與仿真結(jié)果 value = [220,208,198,192,180,180,165,162,160,