【文章內(nèi)容簡介】 (l)編碼，把問題的解轉(zhuǎn)化成位串表示形式 。 (2)定義適應性函數(shù) 。 (3)確定遺傳算法的各算子及參數(shù)，包括選擇、交叉、變異方法，交叉率、變異率、群體容量、最大遺傳代數(shù)等 。 (4)隨機初始化群體 。 正文： 基于遺傳算法的背包問題求解 5 (5)計算群體中每一個染色體的適應值 。 (6)按照遺傳操作形成下一代群體 。 ①從當前群體中由事先設定好的選擇方法選出兩個染色體 。 ②根據(jù)給定的交叉率，對選出的兩個染色體進行交叉操作 。 ③根據(jù)給定的變異率，對每個染 色體進行變異操作 。 ④重復①、②、③步，直到新的一代群體被創(chuàng)建出來 。 (7)判斷新產(chǎn)生的群體是否能滿足結(jié)束指標，如果滿足，則算法結(jié)束，如果不滿足，則返回步驟 (6)。 編碼 按照遺傳算法的工作流程，當用遺傳算法求解問題時，必須在目標問題實際表示與遺傳算法的染色體位串結(jié)構(gòu)之間建立關系，即確定編碼和解碼運算。 編碼就是將問題的解用一種碼來表示，從而將問題的狀態(tài)空間與 GA 的編碼空間相對應，編碼的選擇是影響算法性能與效率的重要因素。 常用的編碼方法有如下幾種： ①二進制編碼：二進制編碼將問題空間的參數(shù)表示 為基于字符集 {0,1}構(gòu)成的染色體位串，是最常用的一種編碼方式。 ②大字符集編碼 :除基于字符集 {0,1}的二進制編碼之外，可以結(jié)合實際問題的特征采用 D 進制數(shù)或字符集來表示長度為 L 的位串。 ③序列編碼：用排列法進行編碼顯得更為自然、合理。 ④實數(shù)編碼：實數(shù)編碼具精度高、大空間搜索的優(yōu)點。 ⑤樹編碼：樹編碼是一種非固定常用編碼模式，其表示空間是開放的。在搜索過程中樹可以自由生長，但是不便于形成更具有結(jié)構(gòu)化和層次性的問題解，實際應用中往往可以加以限制。 ⑥自適應編碼：實現(xiàn)選擇合適的固定編碼方式對潛在的遺傳算法用戶 來說是一個難題。事實上，提出合適的編碼同解決問題本身一樣困難。因此，許多用戶認為既然要用遺傳算法解決問題，為什么不讓它同時調(diào)整編碼呢 ?一些專家就采用了自適應編碼 [11]。 適應度函數(shù) 適應度評價是通過適應度函數(shù)對個體質(zhì)量的一種測量，是進化過程中自然的唯一依據(jù)。因此適應度函數(shù)的選擇至關重要，直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解。一般而言，適應度函數(shù)是由目標函數(shù)變換而成的。對目標函數(shù)值域的某種映射變換稱為適應度的尺度變換。 適應度函數(shù)的設計主要滿足以下條件： ①單值、連續(xù)、非負、最大化 :這 個條件是容易理解和實現(xiàn)的。 ②合理、一致性：要求適應度值反映對應解的優(yōu)劣程度，這個條件的達成比較難以衡量。 正文： 基于遺傳算法的背包問題求解 6 ③計算量?。哼m應度函數(shù)設計應盡可能簡單，這樣可以減小計算時間和空間上的復雜性，降低成本。 ④通用性強：適應度函數(shù)對具體問題應盡可能具有通用性，最好無需使用者改變適應度函數(shù)中的參數(shù)。 適應度函數(shù)的尺度變換有線性變換法、幕函數(shù)變換法、指數(shù)變換法 [10]。 遺傳算子 標準的遺傳算子 一般都包括選擇、交叉和變異三種。它們構(gòu)成了遺傳算法的核心，使得算法具有強大的搜索能力。 選擇算 子 選擇操作就是用來確定如何從父代種群中按照某種方法選取哪些個體遺傳到下一代種群的遺傳運算。它是根據(jù)個體適應度函數(shù)值的大小正比于其被放入候選的概率的過程。在備選集中按照一定的選擇概率進行操作，這個概率取決于種群中個體的適應度及其分布。其主要作用是避免了基因缺失，提高全局收斂性和計算效率。選擇算子可看作是種群空間到父體空間的隨機映射，它按照某種準則或概率分布從當前種群中以高的概率選取那些好的個體組成不同的父體以供生成新的個體。 目前常用的選擇策略有賭盤賭選擇算子、排序選擇算子、最優(yōu)保存選擇算子和錦標賽選擇算子 等 [8]。 在遺傳算法中，目前常用的選擇機制有以下幾種： ①適應度比例方法 適應度比例方法是目前遺傳算法中最基本也是最常用的選擇方法。它也叫賭輪或蒙特卡羅選擇。在該方法中，各個個體的選擇概率和其適應度值成比例。 設群體大小為 n，其中個體 i 的適應度值為 fi，則 i 被選擇的概率 psi為： /si i ip f f? ? （ 41） 顯然，概率 psi反映了個體 i 的適應度在整個群體的個體適應度總和中所占的比例。個體適應度越大，其被選擇的概率就越高，反之則被選 擇的概率越低。 ②最佳個體保存方法 最佳個體保留進化策略的基本思想是當前群體中適應度最高的個體不參與交叉運算和變異運算，而是用來替換掉本代群體中經(jīng)過交叉、變異等遺傳操作后所產(chǎn)生的適應度最低的個體。 具體操作過程是： 1)找出當前群體中適應度最高的個體和適應度最低的個體。 2)若當前群體中最佳個體的適應度比總的迄今為止的最好個體的適應度還要高，則以當前群體中的最佳個體作為新的迄今為止的最好個體。 3)用迄今為止的最好個體替換掉當前群體中的最差個體。 ③期望值方法 在賭輪選擇機制中，當個體數(shù)不太多時，依據(jù)產(chǎn)生的 隨機數(shù)有可能會出現(xiàn)不正正文： 基于遺傳算法的背包問題求解 7 確地反映個體適應度的選擇，即存在統(tǒng)計誤差。也就是說，適應度高的個體也有可能被淘汰 (當然，適應度低的個體也有可能被選擇 )，為克服這種誤差，期望值方法用了如下思想。 1)計算群體中每個個體在下一代生存的期望數(shù)目： _/ / /i i iM f f f f n?? ? （ 42） 2)若某個體被選中并要參與配對和交叉，則它在下一代中的生存的期望值數(shù)目減去 ；若不參與配對和交叉，則該個體的生存期望數(shù)目減去 1。 3)在 2)的兩種情況下，若一個個體的期望值小于 0 時，則該個體不參與選擇 。 ④排序選擇機制 排序選擇方法的主要著眼點是個體適應度之間的大小關系，對個體適應度是否取正值或負值以及個體適應度之間的數(shù)值差異程度并無特別要求。排序選擇機制的主要思想是：對群體中的所有個體按其適應度大小進行排序，基于這個排序來分配各個體被選中的概率。其具體操作過程是： 1)對群體中的所有個體按其適應度大小進行降序排序。 2)根據(jù)具體求解問題，設計一個概率分配表，將各個概率值按上述排列次序分配給各個個體。 3)以各個個體所分配到的概率值作為其能夠被遺傳到下一代的概率，基于這些概率值用比例選擇的方法來產(chǎn)生下一 代群體。是指在計算每個個體的適應度后，根據(jù)適應度大小順序?qū)θ后w中個體排序，然后把事先設計好的概率表按序分配給個體，作為各自的選擇概率。 交叉算子 交叉操作是遺傳算法中最主要的遺傳操作。它是模仿自然界有性繁殖的基因重組過程，對兩個父代個體進行基因操作，其作用在于把原有優(yōu)良基因遺傳到下一代種群中，并生成包含更復雜基因結(jié)構(gòu)的新個體。交叉算子可看作是父體空間到個體空間的隨機映射， 它通常的作用方式是：隨機地確定一個或多個分量位置為交叉點，由此將一對父體的兩個個體分為有限個片斷再以概率 cp （稱為交叉概率）交換相應片斷得到新的個體。 變異算子 在生物種群中總是存在著變異，變異指的是子代和父代之間具有某些不相似的現(xiàn)象，即因為存在著變異現(xiàn)象，所以子代和父代之間中總是不完全相同的。變異是生物進化過程中不可缺少的，它為生物的進化和發(fā)展創(chuàng)造了條件。 在遺傳算法中，變異是指父代染色體中的某些基因片，以相對較小的概率發(fā)生隨機改變的操作過程。所謂變異運算，是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成一個新的個體。 在 遺傳算法中使用變異算子主要有以下兩個目的： ①改善遺傳算法的局部搜索能力。遺傳算法使用交叉算子已經(jīng)從全局的角度出正文： 基于遺傳算法的背包問題求解 8 發(fā)找到了一些較好的個體編碼結(jié)構(gòu)，它們已接近或有助于接近問題的最優(yōu)解。但僅使用交叉算子無法對搜索空間的細節(jié)進行局部搜索。這時若再使用變異算子來調(diào)整個體編碼串中的部分基因值，就可以從局部的角度出發(fā)使個體更加逼近最優(yōu)解，從而提高了遺傳算法的局部搜索能力。 ②維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。變異算子用新的基因值替換原有基因值，從而可以改變個體編碼串的結(jié)構(gòu)，維持群體的多樣性，這樣就有利于防止出現(xiàn)早熟現(xiàn)象 。 參數(shù)控制 在遺傳算法的運行過程中，存在著對其性能產(chǎn)生重大影響的一組參數(shù)。這組參數(shù)在初始階段或種群進化過程中需要合理地選擇和控制。主要包括種群規(guī)模 n、交叉概率 pc以及變異概率 pm。 群體規(guī)模 大種群含有較多模式，為遺傳算法提供了足夠的模式采樣容量，可以改進 GA搜索的質(zhì)量，防止早熟前收斂。但大種群增加了個體適應性評價的計算量，從而使收斂速度降低。 交叉概率 交叉概率 pc控制著交叉算子的應用頻率，在每一代新的種群中，需要對個體的染色體結(jié)構(gòu)進行交叉操作。交叉概率越高， 種群中新結(jié)構(gòu)的引入越快，已獲得的優(yōu)良基因結(jié)構(gòu)的丟失速度也相應升高。而交叉概率太低則可能導致搜索阻滯。一般pc=— 。 變異概率 變異操作是保持種群多樣性的有效手段，交叉結(jié)束后，交配池中的全部個體位串上的每位等位基因按概率隨機改變，因此每代中大約發(fā)生 n 次變異。變異概率太小，可能使某些基因位過早丟失的信息無法恢復；而變異概率過高，則搜索將變成隨機搜索。一般取 pm=— 。 算法結(jié)束條件控制 終止代數(shù)是表示遺傳算法運行結(jié)束條件的一個參數(shù)，它表示遺傳算法運行到指定的進化代數(shù)之后就停止運行，并將當前種群中的最優(yōu)個體作為所求問題的最優(yōu)解輸出。由于遺傳算法不同于傳統(tǒng)的優(yōu)化算法，它沒有利用目標函數(shù)的梯度等信息，所以在遺傳進化過程中，很難有明確的搜索終止準則。 常用的辦法是預先給定算法的終止進化代數(shù)。一般來說，預先給定算法的終止進化代數(shù)只能找到問題在給定時限內(nèi)所能尋求的相對滿意解，但不一定是問題的最優(yōu)解或較高精度的近似解。為了獲得較高精度的近似解，通?？梢罁?jù)種群適應度的正文： 基于遺傳算法的背包問題求解 9 穩(wěn)定來適時調(diào)整終止進化代數(shù)的設置，或者在連續(xù)進化數(shù)代以后，如果解的適應度沒有明顯的改進，則終止進化過程。終 止進化代數(shù)一般的取值范圍是 1001000。 5 實現(xiàn)求解背包問題的遺傳算法 0_1 背包問題中染色體的表示 用向量 X來表示染色體， X = ｛ x1， x2，??， xn｝。， xi∈｛ 0,1｝， xi=1 表示物品 i 裝入了背包， xi =0 表示物品 i 未裝入背包。 每個染色體對應其當前裝入背包的物品的總價值和總重量。背包中物品的中價值代表了該物品的適應度。 程序中定義了這樣的一個結(jié)構(gòu)來表示染色體： typedef struct{ int Weight。 //染色體代表的物品的總重量 int Fitness。 //染色體代表的物品的價值（適應