【正文】 ess。xi∈｛0,1｝，xi=1表示物品i裝入了背包，xi =0表示物品i未裝入背包。一般來說，預先給定算法的終止進化代數(shù)只能找到問題在給定時限內所能尋求的相對滿意解，但不一定是問題的最優(yōu)解或較高精度的近似解。一般取pm=—。而交叉概率太低則可能導致搜索阻滯。 群體規(guī)模大種群含有較多模式，為遺傳算法提供了足夠的模式采樣容量，可以改進GA搜索的質量，防止早熟前收斂。變異算子用新的基因值替換原有基因值，從而可以改變個體編碼串的結構，維持群體的多樣性，這樣就有利于防止出現(xiàn)早熟現(xiàn)象。遺傳算法使用交叉算子已經(jīng)從全局的角度出發(fā)找到了一些較好的個體編碼結構，它們已接近或有助于接近問題的最優(yōu)解。變異是生物進化過程中不可缺少的，它為生物的進化和發(fā)展創(chuàng)造了條件。 交叉算子交叉操作是遺傳算法中最主要的遺傳操作。其具體操作過程是：1)對群體中的所有個體按其適應度大小進行降序排序。1)計算群體中每個個體在下一代生存的期望數(shù)目：M=fi /=fi / ∑fi/n （42）2)若某個體被選中并要參與配對和交叉，；若不參與配對和交叉，則該個體的生存期望數(shù)目減去1。2)若當前群體中最佳個體的適應度比總的迄今為止的最好個體的適應度還要高，則以當前群體中的最佳個體作為新的迄今為止的最好個體。設群體大小為n，其中個體i的適應度值為fi，則i被選擇的概率psi為：psi=fi / ∑fi （41） 顯然，概率psi反映了個體i的適應度在整個群體的個體適應度總和中所占的比例。目前常用的選擇策略有賭盤賭選擇算子、排序選擇算子、最優(yōu)保存選擇算子和錦標賽選擇算子等[8]。它是根據(jù)個體適應度函數(shù)值的大小正比于其被放入候選的概率的過程。適應度函數(shù)的尺度變換有線性變換法、幕函數(shù)變換法、指數(shù)變換法[10]。適應度函數(shù)的設計主要滿足以下條件：①單值、連續(xù)、非負、最大化:這個條件是容易理解和實現(xiàn)的。 適應度函數(shù)適應度評價是通過適應度函數(shù)對個體質量的一種測量，是進化過程中自然的唯一依據(jù)。在搜索過程中樹可以自由生長，但是不便于形成更具有結構化和層次性的問題解，實際應用中往往可以加以限制。②大字符集編碼:除基于字符集{0,1}的二進制編碼之外，可以結合實際問題的特征采用D進制數(shù)或字符集來表示長度為L的位串。(7)判斷新產(chǎn)生的群體是否能滿足結束指標，如果滿足，則算法結束，如果不滿足，則返回步驟(6)。①從當前群體中由事先設定好的選擇方法選出兩個染色體。(3)確定遺傳算法的各算子及參數(shù)，包括選擇、交叉、變異方法，交叉率、變異率、群體容量、最大遺傳代數(shù)等。這樣，一代一代地進化，最后就會收斂到最適應環(huán)境的一個“染色體”上，它就是問題的最優(yōu)解[9]。被用來調整人工神經(jīng)網(wǎng)絡的連接權及網(wǎng)絡拓撲優(yōu)化。機器學習。自動控制。 生產(chǎn)調度問題。隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴大，有時在目前的計算機上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。函數(shù)優(yōu)化是遺傳算法的經(jīng)典應用領域，也是對遺傳算法進行性能評價的常用例子。 遺傳算法的特點 從整體上來講，遺傳算法是進化算法中產(chǎn)生最早、影響最大、應用也比較廣泛的一個研究方向和領域，它不僅包含了進化算法的基本形式和全部優(yōu)點，同時還具備若干獨特的性能。算法將根據(jù)適應度值對它進行尋優(yōu)的過程，遺傳算法的尋優(yōu)過程是通過選擇、雜交和變異三個遺傳算子來具體實現(xiàn)的，它的搜索能力由選擇算子和雜交算子決定，變異算子則保證了算法能夠搜索到問題空間的每一個點，從而使其具有搜索全局最優(yōu)的能力。它是在1975年首次由美國密西根大學的D. J. Holland教授和他的同事們借鑒生物界自然選擇和進化機制基礎之上提出的。對于這樣一個典型的、易于描述卻難以處理的NP難題，有效地解決它在可計算理論上有著重要的理論價值。雖然它陳述起來很簡單，但求解卻很困難，并且已經(jīng)被證明是NP完全問題。求出裝入背包中物品價值總和最大的方案。基本不用搜索空間的知識或其他輔助信息，而僅用適應度來評估個體優(yōu)劣。遺傳算法使用群體搜索技術，它通過對當前群體施加選擇、交叉、變異等一系列遺傳操作，從而產(chǎn)生出新一代的群體，并逐步使群體進化到包含或接近最優(yōu)解的狀態(tài)。本科生畢業(yè)設計（論文）( 2010屆 ) 題 目： 基于遺傳算法求解背包問題 目 錄摘要 ……………………………………………………………………………………1英文摘要 ………………………………………………………………………………11 引言 ………………………………………………………………………………12 背包問題概述 ……………………………………………………………………2 背包問題描述 ………………………………………………………………2 研究背包問題的意義 ………………………………………………………23 遺傳算法概述 ……………………………………………………………………2 遺傳算法的特點 ……………………………………………………………3 遺傳算法的應用領域 ………………………………………………………3 4 遺傳算法的基本原理 ……………………………………………………………4 基本流程 ……………………………………………………………………4 編碼 …………………………………………………………………………5 適應度函數(shù) …………………………………………………………………5 遺傳算子 ……………………………………………………………………6 選擇算子 …………………………………………………………………6 交叉算子…………………………………………………………………7 變異算子…………………………………………………………………7 參數(shù)控制 ……………………………………………………………………8 群體規(guī)模 ………………………………………………………………8 交叉概率 ………………………………………………………………8 變異概率 ………………………………………………………………8 算法結束條件控制 …………………………………………………………9 5 實現(xiàn)求解背包問題的遺傳算法 ………………………………………………9 0_1背包問題中染色體的表示………………………………………………9 遺傳算法求解0_1背包問題時用到的參數(shù) ………………………………9 選擇操作 ……………………………………………………………………9 交叉操作 ……………………………………………………………………10 精英策略 ……………………………………………………………………11 變異操作 ……………………………………………………………………11 代際更新 ……………………………………………………………………11 算法終止 ……………………………………………………………………11 仿真結果與測試 ……………………………………………………………12 不同交叉概率下所得測試結果 ………………………………………13 極端數(shù)據(jù)對結果的影響 ………………………………………………15 仿真結果總結 …………………………………………………………18 問題總結 ……………………………………………………………………186 展望 ………………………………………………………………………………18致 謝 …………………………………………………………………………………19參考文獻 ……………………………………………………………………………20附源程序 ……………………………………………………………………………21基于遺傳算法求解背包問題摘 要背包問題(Knapsack problem)是一種組合優(yōu)化的NP完全問題,本文首先介紹了基本遺傳算法的基本原理、特點及其基本實現(xiàn)技術，接著針對背包問題，論述了遺傳算法在編碼表示和遺傳算子（包括選擇算子、交叉算子變異算子這三種算子）等方面的應用情況。關鍵詞：背包問題；遺傳算法；遺傳算子；編碼Genetic Algorithm for KPJin Tian Tian Director: Prof. DaYong Deng(College of Mathematics Physics And Information Engineering ,Zhejiang Normal University)Abstract:KP (Knapsack Problem) is a binatorial optimization of NP plete problem. The primary knowledge, characteristics and the basic techniques of GA are introduced firstly. The encoding model and genetic operators (including selection operation, crossover operation and mutation operation) solving KP are discussed secondly. Combined with examples of knapsack problem, we have given the specific encoding method, operating parameters, popsize, maxgeneration, and suitable genetic operator. At last, the application of genetic algorithm is simple presented, and the prospect for the future of genetic algorithm in solving KP has been given.Keywords: KP ,genetic algorithm, genetic operators ,encoding1 引 言遺傳算法正是借鑒生物的自然選擇和遺傳進化機制而開發(fā)出的一種全局優(yōu)化自適應概率搜索算法。與傳統(tǒng)的優(yōu)化算法相比，遺傳算法具有以下優(yōu)點:在每一時刻，GA同時在多個子空間內進行搜索，對初始值不作要求。2 背包問題概述 背包問題的描述背包問題又稱子集合問題，最早是由Dantzing 于20 世紀50 年代首次提出的，已成為計算機學科中一個經(jīng)典的NP 問題，本文討論的是01背包問題，問題描述如下：指定給n件物品和一個背包，物品i 的重量是wi，其價值為vi，背包的容量為C，求從這n 件物品中選取一部分物品且對每件物品,或者選取,或者不選,每種物品只能裝入背包一次,且要求滿足放入背包中的物品總重量不超過背包容量。 研究背包問題的意義背包問題是組合優(yōu)化領域中的一個典型問題，涉及求多個變量的函數(shù)的最大值。 背包問題的求解，一直以來倍受人們的關注。3 遺傳算法概述遺傳算法（GA）是一類借鑒生物界自然選擇和自然遺傳機制的隨機化的搜索算法，也是一種抽象于生物進化過程的基于自然選擇和生物遺傳機制的優(yōu)化技術。 遺傳算法是將問題的每一個可能性解看作是群體中的一個個體(染色體)，并將每一個染色體編碼成串的形式，再根據(jù)預定的目標函數(shù)對每個個體進行評價，給出一個適應度值。由于它具有良好的全局搜索能力，是目前解決各種優(yōu)化問題的最有效的方法，已經(jīng)成為研究熱點。 遺傳算法的應用領域遺傳算法的主要應用領域包括以下幾個方面：函數(shù)優(yōu)化問題。組合優(yōu)化問題。遺傳算法已經(jīng)在求解旅行商問題、圖形劃分問題等方面得到成功的應用。在單件生產(chǎn)車間調度、流水線生產(chǎn)車間調度、生產(chǎn)規(guī)劃、任務分配、虛擬企業(yè)中的伙伴選擇方面遺傳算法都得到了有效的應用。例如，用遺傳算法進行航空控制系統(tǒng)的優(yōu)化、用遺傳算法優(yōu)化設計透平機械、設計模糊控制器等，都取得了較好的效果。例如，遺傳算法被用于學習模糊控制規(guī)則、確定模糊集的隸屬函數(shù)、改進模糊系統(tǒng)的性能。給出一群“染色體”，作為假設解，然后，把這些假設解置于問題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應環(huán)境的“染色體”進行復制，再通過交叉和變異過程產(chǎn)生更適應環(huán)境的新一代“染色體”群。(2)定義適應性函數(shù)。(6)按照遺傳操作形成下一代群體。④重復①、②、③步，直到新的一代群體被創(chuàng)建出來。常用的編碼方法有如下幾種：①二進制編碼：二進制編碼將問題空間的參數(shù)表示為基于字符集{0,1}構成的染色體位串，是最常用的一種編碼方式。⑤樹編碼：樹編碼是一種非固定常用編碼模式，其表示空間是開放的。因此，許多用戶認為既然要用遺傳算法解決問題，為什么不讓它同時調整編碼呢?一些專家