資源描述：
《用遺傳算法解決0-1背包問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、實現(xiàn)遺傳算法的0-1背包問題求解及其改進姓名：學(xué)號：班級：提交日期：201?年6月27旦_實現(xiàn)遺傳算法的0-1背包問題求解摘要：研究了遺傳算法解決0-1背包問題中的幾個問題:1）對于過程中不滿足重量限制條件的個體的處理，通過代換上代最優(yōu)解保持種群的進化性2）對于交換率和變異率的理解和處理方法，采用逐個體和逐位判斷的處理方法3）對于早熟性問題，引入相似度衡量值并通過重新生成個體替換最差個體方式保持種群多樣性。4）一種最優(yōu)解只向更好進化方法的嘗試。通過實際計其比較表明，本文改進遺傳算法在背包問題求解中具有
2、很好的收斂性、穩(wěn)定性和計算效率。通過實例計算，表明本文改進遺傳算法優(yōu)于簡單遺傳算法和普通改進的遺傳算法關(guān)鍵詞：遺傳算法；背包問題；優(yōu)化1.基本實現(xiàn)原理：一、問題描述0-1背包問題屬于組合優(yōu)化問題的一個例子，求解0-1背包問題的過程可以被視作在很多可行解當(dāng)屮求解一個最優(yōu)解。01背包問題的一般描述如下：給定n個物品和一個背包，物品i的重量為Wi,其價值為Vi,背包的容量為C。選擇合適的物品裝入背包，使得背包中裝入的物品的總價值最大。注意的一點是，背包內(nèi)的物品的重量之和不能大于背的容量C。在選擇裝入背的物品
3、時，對每種物品i只有兩種選擇：裝入背包或者不裝入背包，即只能將物品i裝入背包一次。稱此類問題為0/1背包問題。其數(shù)學(xué)模型為：c的餅下f=l?其中1=Ir2.r3.r40-1背包問題傳統(tǒng)的解決方法奮動態(tài)規(guī)劃法、分支界限法、冋溯法等等。傳統(tǒng)的方法不能奮效地解決0-1背包問題。遺傳算法（GeneticAlgorithms）則是一種適合于在火量的可行解屮搜索最優(yōu)（或次優(yōu)）解的有效算法。二、遺傳算法特點介紹：遺傳算法（GeneticAlgorithm,GA｝是1962年Holland教授首次提出了GA算法的思想
4、是近年來隨著信息數(shù)據(jù)量激增，發(fā)展起來的一種嶄新的全局優(yōu)化算法，它借用了生物遺傳學(xué)的觀點，通過自然選擇、遺傳、變異等作用機制，實現(xiàn)各個個體的適應(yīng)性的提高。基本遺傳算法求解步驟：Step1參數(shù)設(shè)置：在論域空間上定義一個適應(yīng)度函數(shù)/（x）,給定種群規(guī)模W，交叉率Pc和變異率Pm，代數(shù)r;Step2初始種群：隨機產(chǎn)生＜7中的W個染色體slzs2,sN，組成初始種群5=｛slzs2,…,sN｝，置代數(shù)計數(shù)器Step3計算適應(yīng)度：S中每個染色體的適應(yīng)度f（）;SteP4判斷：若終止條件滿足，則取5中適應(yīng)度最大的
5、染色體作為所求結(jié)果，算法結(jié)束。Step5選擇?復(fù)制：按選擇概率PU,）所決定的選中機會，每次從S中隨機選定1個染色體并將其復(fù)制，共做/V次，然后將復(fù)制所得的W個染色體組成群體51;Step6交叉：按交叉率所決定的參加交叉的染色體數(shù)c，從中隨機確定c個染色體，配對進行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體52;Step7變異：按變異率Pm所決定的變異次數(shù)m，從52中隨機確定m個染色體，分別進行變異操作，并用產(chǎn)生的新染色體代替原染色體，得群體53;Step8更新：將群體53作為新一代種群，即用S
6、3代替5,轉(zhuǎn)步3;遺傳算法是一種仿生算法，即模擬生命演化的算法，它從一個代表問題初始解的初始種群出發(fā)，不斷重復(fù)執(zhí)行選擇，雜交和變異的過程，使種群進化越來越接近某一目標(biāo)既最優(yōu)解，如果視種群為超空間的一組點，選擇、雜交和變異的過程即是在超空間中進行點集之間的某種變換，通過信息交換使種群不斷變化，遺傳算法通過模擬達爾文“優(yōu)勝劣汰，適者生存”的原理激勵好的結(jié)構(gòu)，同時尋找更好的結(jié)構(gòu)，作為一種隨機的優(yōu)化與搜索方法，遺傳算法有著其鮮明的待點。一遺傳算法一般是直接在解空間搜索，而不像圖搜索那樣一般是在問題空間搜索，最
7、后才找到解（如果搜索成功的話）。一遺傳算法的搜索隨機地始于搜索空間的一個點集，而不像圖搜索那樣固定地始于搜索空間的初始節(jié)點或終止節(jié)點，所以遺傳算法是一種隨機搜索算法。一遺傳算法總是在尋找優(yōu)解（最優(yōu)解或次優(yōu)解），而不像閣搜索那樣并非總是耍求優(yōu)解,而一般是設(shè)法盡快找到解（當(dāng)然包括優(yōu)解b所以遺傳算法乂是一種優(yōu)化搜索算法。一遺傳算法的搜索過程是從空間的一個點集（種群）到另一個點集（種群）的搜索，而不像圖搜索那樣一般是從空間的一個點到另一個點地搜索。因而它實際是一種并行搜索，適合大規(guī)模并行計算，而且這種種群到種
8、群的搜索有能力跳出局部最優(yōu)解。一遺傳算法的適應(yīng)性強，除需知適應(yīng)度函數(shù)外，幾乎不需要其他的先驗知識。一遺傳算法長于全局搜索，它不受搜索空間的限制性假設(shè)的約束，不要求連續(xù)性，能以很大的概率從離散的、多極值的、含有噪聲的高維問題中找到全局最優(yōu)解。3.程序步驟：一、使用基本遺傳算法解決0-1背包問題：1：打開數(shù)據(jù)文件2:設(shè)罝程序運行主界面3:調(diào)用初始化種群模塊3-1:按照一定的種群規(guī)模和染色體長度以基因為單位用隨機產(chǎn)生的0-1對個體賦值3-2:調(diào)用計算適應(yīng)度函數(shù)
