背包問題中的遺傳算法變異算子研究

1、背包問題中的遺傳算法的變異算子研究 JIANGXI AGRICULTURAL UNIVERSITY本 科 畢 業(yè) 論 文（設(shè) 計(jì)）題目： 背包問題中遺傳算法的變異算子研究 學(xué) 院： 理學(xué)院 姓 名： 學(xué) 號： 專 業(yè)： 信息與計(jì)算科學(xué) 年 級： 2009級 指導(dǎo)教師： 職 稱： 二一三 年五 月15背包問題中遺傳算法的變異算子研究摘要背包問題是管理科學(xué)和計(jì)算機(jī)領(lǐng)域的NP難題,對于大規(guī)模問題,目前的主流算法是遺傳算法等進(jìn)化算法. 而變異算子是遺傳算法能否找到全局最優(yōu)解的關(guān)鍵之一. 但是目前專門針對背包問題的變異算子研究并不多. 鑒此, 本文旨在研究,具有不同變異算子的遺傳算法在解0-1背包問題時(shí)

2、的性能表現(xiàn). 本文首先介紹了0-1背包問題的數(shù)學(xué)模型及其求解的意義. 然后,介紹了遺傳算法的主要算子及其優(yōu)缺點(diǎn),并詳細(xì)介紹了遺傳算法的變異算子. 本文通過對變異算子的不同改進(jìn),得到不同的遺傳算法,并且將這些不同算法進(jìn)行實(shí)驗(yàn)測試,以期得到具有最佳變異算子的遺傳算法. 最后通過數(shù)值實(shí)驗(yàn),比較了不同變異算子的優(yōu)缺點(diǎn). 基于0-1背包問題的仿真實(shí)驗(yàn)表明：不同變異算子會(huì)影響遺傳算法的收斂速度和計(jì)算精度,在性能上各有優(yōu)劣.關(guān)鍵詞：遺傳算法；變異算子；背包問題；MATLABAbstractKnapsack problem is a NP hard problem which is widely involv

3、ed in management science and computer science. The most popular algorithms to solve the large scale problems are evolutionary algorithms, such as genetic algorithm and so. It is well known that the mutation operator is the key operator of the genetic algorithm. But there are few literatures dedicate

4、d to study the impact of mutation operator in genetic algorithm to solve the knapsack problem. In view of this, this paper aims to study the performance of the genetic algorithms with different mutation operator in solving the 0-1 knapsack problem. Firstly the mathematical model of 0-1 knapsack prob

5、lem and its significance are introduced. Then, the operator of genetic algorithm and its advantages and disadvan- tages are discussed. With different mutation operators designed, four genetic algorithms are presented accordingly. Finally, the numerical experiments were conducted to test the performa

6、nce of the different algorithm. Simulation results in solving the 0-1 knapsack problems indicate that different mutation operator will affect the performance of the genetic algorithm in its convergence speed and computational accuracy.Key words : genetic algorithm；mutation operator；knapsack problem；

7、matlab目錄1 背包問題11.1 背包問題的定義11.2 背包問題的意義12 遺傳算法12.1 遺傳算法12.2 遺傳算法的優(yōu)缺點(diǎn)22.3 遺傳算法的步驟22.4 遺傳算法流程圖33 問題假設(shè)及符號說明43.1 問題假設(shè)43.2 符號說明44 遺傳算法的主要算子44.1 選擇算子44.2 交叉算子54.3 變異算子65 數(shù)據(jù)測試85.1 算法測試規(guī)范85.2 測試目的及實(shí)例數(shù)據(jù)95.3 參數(shù)設(shè)置105.4 運(yùn)行環(huán)境105.5 運(yùn)行結(jié)果圖115.6 結(jié)果分析146 結(jié)論15參考文獻(xiàn)16附錄17背包問題中遺傳算法變異算子研究1 背包問題1.1 背包問題的定義背包問題(Knapsack prob

8、lem)是一種NP困難組合優(yōu)化的問題.可描述如下：決策者有一個(gè)背包,其承重能力為W,有m件可選擇物品,每個(gè)物品的質(zhì)量和價(jià)值分別為,而決策者的目的則是在允許的承重范圍之內(nèi),選出合理的物品,以使背包中的物品總價(jià)值得到最大化.本文中僅考慮0-1背包問題,即每種物品僅有一件,若物品i選入背包的數(shù)量描述為,則0-1背包問題可用數(shù)學(xué)規(guī)劃模型進(jìn)行如下表示：1.2 背包問題的意義 背包問題在現(xiàn)代理科學(xué)中具有重要的應(yīng)用 ,是運(yùn)籌學(xué)中的一個(gè)典型的NP優(yōu)化難題,在實(shí)際生活中也有著及其廣泛的應(yīng)用背景.許多關(guān)于工業(yè)和金融的問題,都可以建立背包問題的數(shù)學(xué)模型,例如資源分配、投資決策、貨物裝載、網(wǎng)絡(luò)資源分配、線性材料切割等

9、都可歸結(jié)為背包問題.因此,研究背包問題無論是在理論上還是在實(shí)際應(yīng)用中都有著極其重大的意義.如今的社會(huì),背包問題影響力愈來愈大,是現(xiàn)在數(shù)學(xué)問題不可忽視的一部分.2 遺傳算法2.1 遺傳算法 在自然界中“物競天擇,適者生存”是一種永恒不變的規(guī)律,遺傳算法就是據(jù)此而提出來的一種隨機(jī)搜索算法.遺傳算法起源于對生物系統(tǒng)所進(jìn)行的計(jì)算機(jī)模擬.它是從問題的一組潛在解開始迭代尋優(yōu)的算法.一個(gè)群體由一定數(shù)目的染色體組成.染色體是由編碼形成的基因組成,所以在遺傳算法初始階段需要進(jìn)行編碼格式的確定.遺傳算法的編碼主要有實(shí)數(shù)編碼與二進(jìn)制編碼兩種類型,本文中采用的即是二進(jìn)制編碼.生成初代群體之后,模擬生物解的適者生存、優(yōu)

10、勝劣帶的機(jī)制,進(jìn)行遺傳操作,逐代演化,產(chǎn)生出更加適應(yīng)環(huán)境的染色體.在每一代,根據(jù)問題可行域中個(gè)體的適應(yīng)度大小選擇優(yōu)良個(gè)體,并借助于自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異,產(chǎn)生出新的一代群體.這個(gè)過程將導(dǎo)致種群像自然進(jìn)化一樣使后生代種群比前代更加適應(yīng)于環(huán)境,群體經(jīng)過若干代,保留最適應(yīng)環(huán)境的染色體,從而得到問題的最優(yōu)解.2.2 遺傳算法的優(yōu)缺點(diǎn)由于遺傳算法是基于整個(gè)群體進(jìn)行智能的優(yōu)化算法,故而其具有良好的全局搜索能力,可以快速地將解空間中的全體解搜索得出,不易陷入局部解中；且由于內(nèi)在并行性,可以方便地進(jìn)行分布式計(jì)算,加快求解速度.與此同時(shí),由于遺傳算法是進(jìn)行的群體優(yōu)化,導(dǎo)致其局部搜索能力比較差,在

11、算法執(zhí)行后期的效率較低.在實(shí)際應(yīng)用中,遺傳算法容易產(chǎn)生局域收斂問題.而如何在選擇出優(yōu)良的個(gè)體的同時(shí),還要維持群體的多樣性,一直是遺傳算法中較難解決的問題.2.3 遺傳算法的步驟l 選定編碼格式：編碼需具有完備性、健全性和非冗余性此三大特性.本文根據(jù)0-1背包問題的特性采取二進(jìn)制編碼,即0-1編碼格式.l 初始群體的確定：隨機(jī)的產(chǎn)生數(shù)量為n的長度為m的初始染色體,其中m為物品數(shù)量,每個(gè)染色體代表一種潛在可行解,這些染色體就是初始群體.l 適應(yīng)度函數(shù)和適應(yīng)值的設(shè)計(jì)：為了確定染色體的優(yōu)劣,必須擁有合適的適應(yīng)值規(guī)范,目標(biāo)函數(shù)為適應(yīng)值函數(shù),并計(jì)算個(gè)體的適應(yīng)值.l 確定選擇的標(biāo)準(zhǔn)：挑選合理的選擇算子,主要

12、錦標(biāo)賽選擇、輪盤賭選擇等算子,本文中根據(jù)背包問題的特性采用排序選擇算子.l 產(chǎn)生新的群體：根據(jù)選擇標(biāo)準(zhǔn),當(dāng)前群體淘汰劣質(zhì)的染色體,并且同時(shí)復(fù)制優(yōu)秀染色體補(bǔ)入群體,得到一個(gè)新的群體.l 交叉：將所有染色體進(jìn)行兩兩不重復(fù)配對,進(jìn)行交叉,得到新的染色體后形成新的群體,本文采用單點(diǎn)交叉.l 變異：變異是在小概率的情況下改變了染色體上的基因.l 終止條件：本文采用限制算法遺傳代數(shù)為終止條件,當(dāng)遺傳代數(shù)達(dá)到限制遺傳代數(shù)時(shí),算法終止.2.4 遺傳算法流程圖開始Gen=1編碼產(chǎn)生初始群體滿足終止條件?計(jì)算群體中各個(gè)體適應(yīng)度從左至右依次執(zhí)行遺傳算子根據(jù)適應(yīng)度復(fù)制淘汰個(gè)體選擇兩個(gè)交叉?zhèn)€體選擇個(gè)體變異點(diǎn)執(zhí)行變異執(zhí)行

13、交叉執(zhí)行復(fù)制復(fù)制個(gè)體替換淘汰個(gè)體交叉后添入新群體中變異后添入新群體中結(jié)果結(jié)果結(jié)果Gen=Gen+1輸出結(jié)果終止YNYYYNNNPcPv圖 2-1 遺傳算法流程圖3 問題假設(shè)及符號說明3.1 問題假設(shè)假設(shè)背包的空間足夠大,可以裝的下所有的物品,僅僅是重量承受有要求.假設(shè)所有的物品不重復(fù),即沒有相同的物品.每樣物品數(shù)量僅有1個(gè),即選入包中只能為0個(gè)或者1個(gè).所有的染色體均為單倍體.3.2 符號說明表1 求解問題的符號說明符號說明Wmnk背包的承重能力可以選擇的物品數(shù)量第i個(gè)物品的重量第i個(gè)物品的價(jià)值種族的染色體數(shù)量大小染色體的向量表示適應(yīng)函數(shù)第i個(gè)染色體染色體發(fā)生交叉的概率染色體發(fā)生變異的概率染色

14、體交叉位點(diǎn)4 遺傳算法的主要算子4.1 選擇算子 選擇,是將群體中的適應(yīng)度低的染色體替換為適應(yīng)度高的染色體的操作過程,它是遺傳算法群體的整體優(yōu)化的基礎(chǔ),可以使群體最優(yōu)解越來越趨近于問題的理論最優(yōu)解.目前,主要的選擇算子包括適應(yīng)值比例選擇、Boltzmann選擇、排序選擇、聯(lián)賽選擇、精英選擇、穩(wěn)態(tài)選擇.本文中采用的是排序選擇,排列選擇是將當(dāng)代群體的染色體按照適應(yīng)值排列,淘汰適應(yīng)值低的染色體,并補(bǔ)入適應(yīng)值高的染色體.對于一個(gè)確定好且數(shù)量為n的群體,是由多個(gè)染色體組成,可用向量描述,根據(jù)適應(yīng)值函數(shù)可得到第i個(gè)染色體的適應(yīng)值,適應(yīng)值函數(shù)表達(dá)式可用如下表示：,其中為當(dāng)前群體中染色體對應(yīng)的方案價(jià)值的最小值

15、.適應(yīng)值得出后,即可進(jìn)行排序選擇算子操作,最終得到新的群體,用圖解表示則可用下圖表示：選擇100111101101011001100110100111101101011010011110適應(yīng)值：4適應(yīng)值：9適應(yīng)值：10適應(yīng)值：10適應(yīng)值：9適應(yīng)值：10圖 4-1 排序選擇算子示意圖圖4-1表示當(dāng)前群體內(nèi)有三條染色體,經(jīng)過選擇算子后選擇后,淘汰適應(yīng)值僅有4的染色體01100110,并將適應(yīng)值最高為的染色體10011110補(bǔ)入至淘汰染色體的相應(yīng)群體位置,最終得到一個(gè)新的群體.4.2 交叉算子交叉,是進(jìn)化算法中的遺傳算法所獨(dú)有的原始性特征,它是模仿自然界的有性繁殖時(shí)的基因重組過程,將當(dāng)代原有的優(yōu)良基

16、因遺傳給下一代個(gè)體,并生成包含更復(fù)雜基因結(jié)構(gòu)體的新個(gè)體.一般,交叉操作會(huì)經(jīng)過下列幾個(gè)步驟：l 從交配池中隨機(jī)選出不重復(fù)的交配個(gè)體l 根據(jù)交叉概率確定是否進(jìn)行交叉操作,形成新的染色體l 進(jìn)行交叉操作,將配對染色體上的對應(yīng)基因進(jìn)行交換,形成新的染色體. 交叉分為單點(diǎn)交叉,兩點(diǎn)交叉,多點(diǎn)交叉和一致交叉等形式.單點(diǎn)交叉是最為基礎(chǔ)的交叉方式.首先需要選出兩條不同的染色體,檢驗(yàn)交叉概率后,成功后隨機(jī)在某一基因位點(diǎn),染色體的對應(yīng)基因片段進(jìn)行互換,得到兩條新的染色體.本文中采用的是單點(diǎn)交叉方法,可用圖解表示：01001110101110010100100111101011r0.8圖4-2 單點(diǎn)交叉示意圖 圖4

17、-2表示染色體01001011與11101001在=0.8概率下,生成隨機(jī)數(shù)r0.8后,隨機(jī)生成染色體交叉位點(diǎn)k為4,最終在此位基因發(fā)生單點(diǎn)交叉,形成兩條新的染色體01001001與11101011. 由于交叉算子有效的增強(qiáng)了群體之間的染色體的相互聯(lián)系,使基因的流動(dòng)性得到提高,即群體的染色體保證了多樣性,能夠有效防止遺傳算法的局域收斂,加強(qiáng)了遺傳算法的全局搜索能力,在遺傳算法中扮演一個(gè)十分重要的角色.4.3 變異算子 變異操作是模擬自然界生物體進(jìn)化中的染色體上某位基因發(fā)生的突變,從而改變?nèi)旧w的結(jié)構(gòu)和物理性狀的現(xiàn)象.一般遺傳算法中,采用的是根據(jù)變異概率隨機(jī)對某位基因進(jìn)行變異.本文中,主要研究變

18、異算子的性質(zhì),在整個(gè)遺傳算法框架內(nèi)嵌入不同的變異算子,從而得到不同的遺傳算法.然后通過背包問題實(shí)例測試各個(gè)具有不同變異算子的遺傳算法,得到每種變異算子的優(yōu)缺點(diǎn),故重點(diǎn)進(jìn)行介紹變異算子的性能優(yōu)劣.關(guān)于二進(jìn)制的變異算子,本文中列舉了四種變異算子形式,四種變異算子進(jìn)行變異的流程圖解可用如下圖表示：l 第一種變異算子,是對群體中的每一條染色體的每一位基因進(jìn)行變異,此變異算子廣泛應(yīng)用于各個(gè)遺傳算法的變異算子之中,是最基本最常用的變異算子.例如圖4-3,當(dāng)物品數(shù)m=8時(shí),染色體10110101進(jìn)行變異概率=0.02的變異,生成m個(gè)服從0,1的均勻分布的隨機(jī)數(shù),最終得到一個(gè)隨機(jī)數(shù)集合r,r=0.01,0.5

19、,0.15,0.06,0.5,0.4,0.9,0.8,判斷其每個(gè)元素是否小于,若小于,則表明此元素對應(yīng)的基因發(fā)生了變異,進(jìn)行基因取反操作,如上述集合r可知染色體第1位基因發(fā)生變異,得到新的染色體00110101.r0.021011010100110101r=0.01,0.5,0.15,0.06,0.5,0.4,0.9,0.8圖 4-3 第一種變異算子示意圖l 第二種變異算子,此變異算子是基于第一種變異算子的計(jì)算量過高而進(jìn)行改良得到.它首先需要得到一條染色體的整體變異概率P,然后對每條染色體進(jìn)行如下操作：生成一個(gè)滿足0,1均勻分布的隨機(jī)數(shù)r,若rP,則表明此染色體可能發(fā)生變異,然后對每位基因進(jìn)行

20、如下操作：生成一個(gè)滿足0,1均勻分布的隨機(jī)數(shù)s,當(dāng)s時(shí),表明此位基因會(huì)發(fā)生變異,進(jìn)行取反操作.此變異算子最終使得原本需要次的計(jì)算量改良降為的計(jì)算量.如：圖4-4,當(dāng)物品數(shù)m=8,=0.02時(shí),對染色體10110101進(jìn)行變異操作,生成隨機(jī)數(shù)為r,當(dāng)rP后,生成一組隨機(jī)數(shù)集合S=0.5,0.3,0.6,0.015,0.7,0.8,0.4,0.9,表明第4位基因發(fā)生變異,最終得到新的染色體10100101.101101011010010110110101rP圖 4-4 第二種變異算子示意圖l 第三種變異算子.與第一、二種變異算子相比,此算子更加簡化了算法量.此算子第一步與上述第二種變異算子相同,首

21、先需要求出一條染色體的變異概率P,然后對每條染色體進(jìn)行如下操作：生成一個(gè)滿足0,1均勻分布的隨機(jī)數(shù)r,若rP,則表明此染色體發(fā)生變異：確定基因變異位,為了計(jì)算量的減少,此變異算子采用連續(xù)變異基因位的方法,即將k個(gè)連續(xù)的基因進(jìn)行變異,為避免一條染色體變異的基因個(gè)數(shù)不會(huì)過多,導(dǎo)致算法易陷入局部解之中,所以在算子中添加了一個(gè)約束條件,使每條染色體基因變異個(gè)數(shù)不能超過一條染色體基因變異的期望值,即,然后進(jìn)行基因片段取反,得到一條新的染色體.通過此算子,可使得算法量將降低為.圖4-5,染色體1011010111在的概率下,通過隨機(jī)數(shù)r判斷染色體發(fā)生變異后,隨機(jī)生成兩個(gè)基因位點(diǎn)a=3,b=4,確定出變異基

22、因片段為3至4位基因,最后進(jìn)行基因取反操作,得到新的染色體1000010111.10110101111000010111a=3,b=41011010111rP圖 4-5 第三種變異算子示意圖l 第四種變異算子,它是基于第三種變異算子進(jìn)行改良,首先需要求出一條染色體的變異概率P,然后對每條染色體進(jìn)行如下操作：生成一個(gè)滿足0,1均勻分布的隨機(jī)數(shù)r,若rP,則表明此染色體發(fā)生變異：,進(jìn)行變異操作：確定基因變異位,為了計(jì)算量的減少,此變異算子采用連續(xù)變異基因位的方法,即將k個(gè)連續(xù)的基因進(jìn)行變異,為避免一條染色體變異的基因個(gè)數(shù)不會(huì)過多,導(dǎo)致算法易陷入局部解之中,所以在算子中添加了一個(gè)約束條件,使每條染色

23、體基因變異個(gè)數(shù)不能超過一條染色體基因變異的期望值,確定出變異基因片段后,選出當(dāng)前群體的最優(yōu)染色體,將此基因片段的基因變異為最優(yōu)染色體相應(yīng)基因片段信息,最終形成一條新的染色體. 圖4-6,染色體1011010111在的概率下,通過隨機(jī)數(shù)r判斷染色體發(fā)生變異后,隨機(jī)生成兩個(gè)基因位點(diǎn)a=5,b=6,確定出變異基因片段為5至6位基因,當(dāng)代群體的最優(yōu)染色體為1100011001,變異后得到新的染色體1011110111.10110101111011110111a=5,b=61011010111rP1100111001最優(yōu)染色體:圖4-6 第四種變異算子示意圖5 數(shù)據(jù)測試5.1 算法測試規(guī)范l 編碼規(guī)范,

24、遺傳算法中,編碼一般需要具備三大特性：完備性、健全性、非冗余性.完備性：問題空間中的所有可行解均可成為一條染色體的表現(xiàn)型.健全性：每一種染色體必須對應(yīng)問題空間中的某一個(gè)潛在可能解.非冗余性：染色體與問題空間中的可能潛在解必須一一對應(yīng).由于每種物品數(shù)量僅有一個(gè),且只分為選入背包與不選入背包兩種情況,故可用二進(jìn)制進(jìn)行編碼.例如對m=10的情形,染色體1011010111表示第1,3,4,6,8,9,10個(gè)物品放入背包之中,其它物品則不放入背包之中.l 初始群體,初始群體的產(chǎn)生一般通過隨機(jī)生成足夠數(shù)量且合格的染色體.隨機(jī)生成一條染色體后,檢驗(yàn)重量是否合格,失敗后則重新隨機(jī)生成一條染色體,直到生成了一

25、條合格的染色體并補(bǔ)入進(jìn)初始群體中.一直到初始群體的大小達(dá)到了指定的數(shù)量為止,否則繼續(xù)生成染色體.l 終止條件,遺傳算法作為一種迭代式算法,必須要確立一個(gè)明確的終止條件,用以終止算法,輸出最終結(jié)果.一般而言,遺傳算法有兩種判斷算法是否終止的方法：設(shè)定最大遺傳代數(shù),此方法簡單,但結(jié)果不夠精確；通過群體的收斂程度判斷,通過計(jì)算群體中的基因位相似度進(jìn)行判斷.本文中采用設(shè)定遺傳代數(shù)作為算法終止條件,當(dāng)遺傳代數(shù)達(dá)到設(shè)定數(shù)值時(shí),算法終止,輸出最優(yōu)解.相似度計(jì)算方法：首先計(jì)算群體中所有染色體第一位基因兩種基因的個(gè)數(shù),取其最大值,將其除以群體染色體個(gè)數(shù),得到第一位基因相似度,類似,求取接下來的每一位基因的相似度

26、,將所有的相似度累加,除以染色體的基因總位數(shù),得到的就是基因相似度,最終通過確定此值是否滿足條件而確定該如何執(zhí)行下一步操作.基因相似度=,其中m為基因的總位數(shù),表示所有染色體中第i位基因?yàn)?的染色體個(gè)數(shù),表示所有染色體中第i位基因?yàn)?的染色體個(gè)數(shù),n表示群體中的染色體個(gè)數(shù).例如染色體1010、1110、0111的相似度為.5.2 測試目的及實(shí)例數(shù)據(jù)本文旨在通過不同的實(shí)例測試使用不同變異算子的遺傳算法求解背包問題時(shí)性能的差異,最終確定選擇何種變異算子的遺傳算法解決背包問題的效果達(dá)到最佳.例1物品數(shù)量為m=20,質(zhì)量價(jià)值分別如下：Weight=3,12,5,4,7,2,1,4,15,9,5,11,

27、3,10,8,9,2,6,5,4Value=24,17,11,8,15,25,33,29,18,20,15,31,10,21,18,19,17,22,14,11物品總重量為125,背包最大承重為60,理論最優(yōu)解為262例2物品數(shù)量為m=35,質(zhì)量價(jià)值分別如下：Weight=15,10,11,17,10,9,15,15,14,18,21,17,6,15,7,9,4,15,17,11,10,9,15,14,18,21,17,10,11,17,7,9,14,11,4Value=37,61,53,33,43,36,37,46,25,24,16,24,11,64,17,46,27,37,61,53,29

28、,23,12,13,19,18,22,26,21,28,11,24,31,25,24物品總質(zhì)量為443,背包最大承重為200,理論最優(yōu)解為729例3物品數(shù)量為m=50,質(zhì)量價(jià)值分別如下：Weight=5,13,14,15,7,9,4,15,17,11,10,9,15,14,18,21,17,6,7,10,7,9,14,11,4,16,15,10,11,17,7,9,14,11,4,16,15,10,11,17,10,9,15,14,18,21,17,6,7,10Value=16,24,11,64,17,46,27,37,61,53,29,23,12,13,19,18,22,26,21,28,1

29、1,24,31,33,43,36,37,46,25,24,16,24,11,64,17,46,27,37,61,53,33,43,36, 37,46,25,24,16,24,11物品總重量為592,背包最大承重為300,理論最優(yōu)解為1088.例4物品數(shù)量為m=100,質(zhì)量價(jià)值分別如下：Weight=5,7,9,4,15,17,11,10,9,15,14,18,21,17,6,7,10,7,9,14,11,4,16,15,10,11,17,7,9,14,11,4,16,15,10,11,17,10,9,15,15,14,18,21,17,6,15,7,9,4,15,17,11,10,9,15,1

30、4,18,21,17,10,11,17,7,9,14,11,4,16,15,11,4,9,14,11,4,16,15,10,11,10,9,15,14,18,21,17,10,11,17,7,9,14,11,4,16,15,11,4,9Value=16,24,11,64,17,46,27,37,61,53,29,23,12,13,19,18,22,26,21,28,11,24,31,33,43,36,37,46,25,24,16,24,11,64,17,46,27,37,61,53,33,43,36, 37,46,25,24,16,24,11,64,17,46,27,37,61,53,29,2

31、3,12,13,19,18,22,26,21,28,11,24,31,25,24,16,24,11,64,17,46,27,61,46,27,37,61,53,33,43,36,37,46,25,24,11,64,17,46,27,37,61,53物品總重量為1191,背包最大承重為600,理論最優(yōu)解為22675.3 參數(shù)設(shè)置表2 本文算法參數(shù)選擇參數(shù)值變異概率交叉概率群體大小n算法執(zhí)行次數(shù)終止遺傳代數(shù)物品數(shù)量0.020.81502510020-1005.4 運(yùn)行環(huán)境l 操作系統(tǒng)：64位 Windows7 旗艦版l 處理器：Intel Core is-2350M CPU 2.30GHzl 內(nèi)存

32、：4Gb,3.82Gb可用5.5 運(yùn)行結(jié)果圖例1結(jié)果圖表以及分析：表3 例1算法平均所用時(shí)間、背包內(nèi)最高價(jià)值、平均價(jià)值、最低價(jià)值變異算子編號算法平均時(shí)間(s)最高價(jià)值平均價(jià)值最低價(jià)值2.0286 1.8801 1.8402 1.9157262262262262261.32261.20259.96258.36258258255254 圖5-1 例1最優(yōu)解背包價(jià)值箱圖圖5-2 例1最優(yōu)解背包價(jià)值標(biāo)準(zhǔn)差圖在求解算例一時(shí),根據(jù)表3中的算法平均時(shí)間,在四種變異算子中,第二、三種變異算子的算法平均耗時(shí)較短,使用第一、四種變異算子的算法耗時(shí)較長,其中使用第三種變異算子的遺傳算法耗時(shí)最短,可最快得到遺傳算法結(jié)

33、果.使用第一種變異算子的遺傳算法耗時(shí)最長.結(jié)合圖5-1、5-2以及表3,四種變異算子中.使用第一、二種變異算子的遺傳算法精確度較高,使用第三、四種變異算子的遺傳算法精確度較低.其中使用第一種變異算子的遺傳算法的精確度最高,可最精確的得到背包問題的理論最優(yōu)值.使用第四種變異算子的遺傳算法精確度最低,不利于精確獲得問題理論最優(yōu)解.因此,從遺傳算法的計(jì)算速度上看,使用第三種變異算子的遺傳算法更好獲取到算法結(jié)果;從算法的精確度和穩(wěn)定性看,則應(yīng)當(dāng)選取第一種變異算子,可更加精確穩(wěn)定的獲得算法結(jié)果;綜合考慮計(jì)算速度和精度,則應(yīng)當(dāng)使用第二種變異算子,可快速獲得問題最優(yōu)解的同時(shí)能保證足夠的精確度以及穩(wěn)定性.例2

34、結(jié)果圖表以及分析：表4 例2算法平均所用時(shí)間、背包內(nèi)最高價(jià)值、平均價(jià)值、最低價(jià)值變異算子編號算法平均時(shí)間(s)最高價(jià)值平均價(jià)值最低價(jià)值2.3474 2.1409 1.9850 2.1040 729729729729724.80725.72723.04714.92719718715695 圖5-3 例2最優(yōu)解背包價(jià)值箱圖圖5-4 例2最優(yōu)解背包價(jià)值標(biāo)準(zhǔn)差圖在求解算例二時(shí),根據(jù)表4中的算法平均時(shí)間,在四種變異算子中,使用第三種變異算子的遺傳算法平均耗時(shí)最短,所以使用此變異算子的遺傳算法可最快速的獲得算法的結(jié)果值.使用第一變異算子的算法耗時(shí)最長,使用二、三種變異算子的遺傳算法則耗時(shí)較短.結(jié)合圖5-3

35、、5-4以及表4,四種變異算子中.使用第一、二種變異算子的遺傳算法的算法精確度較高,使用第四種變異算子的遺傳算法的算法精確度最低.其中使用第二種變異算子的遺傳算法的精確度最高,可最精確的得到背包問題的理論最優(yōu)值.使用第四種變異算子的遺傳算法精確度最低,不利于精確獲得問題理論最優(yōu)解.因此,從遺傳算法的計(jì)算速度上看,使用第三種變異算子的遺傳算法更好獲取到算法結(jié)果;從算法的精確度和穩(wěn)定性看,則應(yīng)當(dāng)選取第二種變異算子,可更加精確穩(wěn)定的獲得算法結(jié)果;綜合考慮計(jì)算速度和精度,則應(yīng)當(dāng)使用第二種變異算子,可快速獲得問題最優(yōu)解的同時(shí)能保證足夠的精確度以及穩(wěn)定性.例3結(jié)果圖表以及分析：表5 例3算法平均所用時(shí)間、

36、背包內(nèi)最高價(jià)值、平均價(jià)值、最低價(jià)值變異算子編號算法平均時(shí)間(s)最高價(jià)值平均價(jià)值最低價(jià)值2.5665 2.3638 2.0604 2.1790 10881087108710741076.21077.11057.31060.61051106210321027 圖5-5 例3最優(yōu)解背包價(jià)值箱圖圖5-6 例3最優(yōu)解背包價(jià)值標(biāo)準(zhǔn)差圖在求解算例三時(shí),根據(jù)表5中的算法平均時(shí)間,在四種變異算子中,使用第三、四種變異算子的遺傳算法平均耗時(shí)較短,可較為快速的獲得算法的結(jié)果值.使用第一變異算子的遺傳算法耗時(shí)最長,其中使用第三種變異算子的遺傳算法耗時(shí)最短.結(jié)合圖5-5、5-6以及表5,四種變異算子中.使用第一、二種

37、變異算子的遺傳算法的算法精確度較高,使用第三、四種變異算子的遺傳算法的算法精確度較低.其中使用第二種變異算子的遺傳算法的精確度最高,可最精確的得到背包問題的理論最優(yōu)值.使用第三種變異算子的遺傳算法精確度最低,不利于精確獲得問題理論最優(yōu)解.因此,從遺傳算法的計(jì)算速度上看,使用第三種變異算子的遺傳算法更好獲取到算法結(jié)果;從算法的精確度和穩(wěn)定性看,則應(yīng)當(dāng)選取第二種變異算子,可更加精確穩(wěn)定的獲得算法結(jié)果;綜合考慮計(jì)算速度和精度,則應(yīng)當(dāng)使用第二種變異算子,可快速獲得問題最優(yōu)解的同時(shí)能保證足夠的精確度以及穩(wěn)定性.例4結(jié)果圖表以及分析：表6 例4算法平均所用時(shí)間、背包內(nèi)最高價(jià)值、平均價(jià)值、最低價(jià)值變異算子編

38、號算法平均時(shí)間(s)最高價(jià)值平均價(jià)值最低價(jià)值3.2834 3.1494 2.2367 2.3750 22232264224422092187.42207.72165.12148.02144215720812058 圖5-7 例4最優(yōu)解背包價(jià)值箱圖圖5-8 例4最優(yōu)解背包價(jià)值標(biāo)準(zhǔn)差圖在求解算例四時(shí),根據(jù)表6中的算法平均時(shí)間,在四種變異算子中,使用第三、四種變異算子的遺傳算法平均耗時(shí)較短,可較為快速的獲得算法的結(jié)果值.使用第一、二變異算子的遺傳算法耗時(shí)較長,其中使用第三種變異算子的遺傳算法耗時(shí)最短,使用第一種變異算子的遺傳算法耗時(shí)最長.結(jié)合圖5-7、5-8以及表5,四種變異算子中.使用第二種變異算

39、子的遺傳算法的算法精確度最高,可最為精確的獲得問題的理論最優(yōu)解,使用第三、四種變異算子的遺傳算法的算法精確度較低.使用第四種變異算子的遺傳算法精確度最低,不利于精確獲得問題理論最優(yōu)解.因此,從遺傳算法的計(jì)算速度上看,使用第三種變異算子的遺傳算法更好獲取到算法結(jié)果;從算法的精確度和穩(wěn)定性看,則應(yīng)當(dāng)選取第二種變異算子,可更加精確穩(wěn)定的獲得算法結(jié)果;綜合考慮計(jì)算速度和精度,則應(yīng)當(dāng)使用第二種變異算子,可快速獲得問題最優(yōu)解的同時(shí)能保證足夠的精確度以及穩(wěn)定性.5.6 結(jié)果分析 通過上述的四則算例的結(jié)果分析,使用第一、二種變異算子的遺傳算法在算法結(jié)果的精確度以及穩(wěn)定性上有著較為良好的優(yōu)勢；而使用第三、四種變

40、異算子的遺傳算法在算法的運(yùn)行速度上有著較為良好的優(yōu)勢.總體說來,當(dāng)從算法的計(jì)算速度上考慮,應(yīng)當(dāng)使用第三種變異算子最優(yōu),可更快的獲得算法的結(jié)果；從算法的結(jié)果精確度及穩(wěn)定性上考慮,使用第一種變異算子可使遺傳算法效果達(dá)到最優(yōu)；綜合算法的速度與精確度,則應(yīng)當(dāng)選取第二種變異算子,可使算法的效益比率最高,可較快得到結(jié)果的同時(shí)獲得較為精確的結(jié)果.6 結(jié)論 遺傳算法是一種具有定向制導(dǎo)的隨機(jī)搜索技術(shù),其定向制導(dǎo)的原則是：導(dǎo)向以高適應(yīng)度模式為祖先的“家族”方向,為了保證群體的多樣性,防止算法陷入舉步最優(yōu)解,引入了變異算子.采用二進(jìn)制編碼的遺傳算法,其變異算子比較單調(diào),且沒有相關(guān)文獻(xiàn)系統(tǒng)地分析各類變異算子對遺傳算法

41、影響,故本文設(shè)計(jì)了四種的變異算子,并通過0-1背包問題實(shí)例的仿真實(shí)驗(yàn)結(jié),比較了個(gè)變異算子的優(yōu)劣.基于第一、二種變異算子的算法精度高,更穩(wěn)定,而基于第三、四種變異算子的算法收斂速度更快.參考文獻(xiàn)參考文獻(xiàn)1Duane Hanselman、Bruce Littlefield著,朱仁峰譯制版 精通Matlab7,清華大學(xué)出版社 2006年出版,p27-29 p317-3212李敏強(qiáng)、寇紀(jì)淞等 遺傳算法的基本理論與應(yīng)用 科學(xué)出版社2002版,p27-45、p47-483萬福永、戴浩暉等著,數(shù)學(xué)實(shí)驗(yàn)教程(Matlab版) ,科學(xué)出版社 2006版,p169-1764遺傳學(xué)編寫組遺傳學(xué)北京:中國大百科全書出

42、版社,19835張文修, 梁怡遺傳算法的數(shù)學(xué)基礎(chǔ) M 1西安: 西安交通大學(xué)出版社, 2001.6王小平,曹立明遺傳算法 理論、應(yīng)用與軟件實(shí)現(xiàn) M西安: 西安交通大學(xué)出版社, 2002.7陳國良, 王煦法, 莊鎮(zhèn)泉, 王東生遺傳算法及其應(yīng)用M 人民郵電出版社, 2001.8張永兵,王斌,張永飛等基于遺傳算法的背包問題求解.大理學(xué)院學(xué)報(bào),2005,4(5):24269網(wǎng)絡(luò)資源：28附錄附錄1 主程序1.1 測試程序 clear all; %清除緩存IssueMatrix=; %重量價(jià)值關(guān)系矩陣 MaxValue=600; %背包容量 pc=0.8; %交叉概率 pv=0.02; %單個(gè)基因變異概

43、率 PopulationNumber=150; %群體大小 n=25; %每種問題執(zhí)行次數(shù)n for i=1:n y1(i,1),z1(i,1)=Main(IssueMatrix,MaxValue,pc,pv,PopulationNumber,1); %獲取算法終止時(shí)的遺傳代數(shù)以及最優(yōu)解 y2(i,1),z2(i,1)=Main(IssueMatrix,MaxValue,pc,pv,PopulationNumber,2); y3(i,1),z3(i,1)=Main(IssueMatrix,MaxValue,pc,pv,PopulationNumber,3); y4(i,1),z4(i,1)=M

44、ain(IssueMatrix,MaxValue,pc,pv,PopulationNumber,4); end figure; var1(1)=mean(y1); var1(2)=mean(y2); var1(3)=mean(y3); var1(4)=mean(y4); plot(1:1:4,var1,o); %繪制平均算法終止所用時(shí)間圖 title(平均算法終止所用時(shí)間圖); xlabel(變異算子編號); ylabel(時(shí)間); figure; boxplot(z1,z2,z3,z4); %繪制最優(yōu)結(jié)果值的箱圖 title(遺傳算法最終結(jié)果價(jià)值箱圖); xlabel(變異算子編號); yl

45、abel(結(jié)果值); figure; var2(1)=std(z1,1); var2(2)=std(z2,1); var2(3)=std(z3,1); var2(4)=std(z4,1); plot(1:4,var2,o); %繪制最優(yōu)結(jié)果值的標(biāo)準(zhǔn)差圖 title(遺傳算法最終結(jié)果價(jià)值標(biāo)準(zhǔn)差圖); xlabel(變異算子編號); ylabel(標(biāo)準(zhǔn)差);1.2 執(zhí)行主程序function y,z=Main(IssueMatrix,MaxValue,pc,pv,PopulationNumber,action)global Gen; %遺傳代數(shù),初始為0global VariationCount

46、%染色體發(fā)生變異的次數(shù)global CrossCount %染色體發(fā)生交叉的次數(shù)Gen=0; %初始化計(jì)數(shù)器global VariationCountglobal CrossCountglobal CodingLength %定義編碼長度global Population %定義種群VariationCount=0;CrossCount=0;a=size(IssueMatrix);CodingLength=a(1,2);InitPopulation(IssueMatrix,MaxValue,CodingLength,PopulationNumber); %初始化種群Gen=1;time=0;t

47、ic;%計(jì)時(shí)開始while (GenMaxValue %判別是否合格 y=GetCoding(IssueMatrix,MaxValue,CodingLength); %不合格重新獲取end3 數(shù)據(jù)統(tǒng)計(jì)程序3.1 計(jì)算重量function y=CountWeight(IssueMatrix,CodingMatrix,CodingLength) y=0; for i=1:CodingLength y=y+IssueMatrix(1,i)*CodingMatrix(1,i); %累加重量 end3.2 計(jì)算價(jià)值function y=CountValue(IssueMatrix,CodingMatrix,CodingLength) y=0; for i=1:CodingLe