背包問題的遺傳算法求解.pdf

1、遺傳算法是演化計算中最活躍的一個分支，它是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計算模型。它的思想源于生物遺傳學(xué)和適者生存的自然規(guī)律，是具有“生存＋檢測”的迭代過程的搜索算法。遺傳算法以一種群體中的所有個體為對象，并利用隨機(jī)化技術(shù)指導(dǎo)對一個被編碼的參數(shù)空間進(jìn)行高效搜索。其中，選擇、交叉和變異構(gòu)成了遺傳算法的遺傳操作；參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計、遺傳操作設(shè)計、控制參數(shù)設(shè)定五個要素組成了遺傳算法的核心內(nèi)容。作為一種新

2、的全局優(yōu)化搜索算法，遺傳算法以其簡單通用、魯棒性強(qiáng)、適于并行處理以及高效、實(shí)用等顯著特點(diǎn)，在各個領(lǐng)域得到了廣泛應(yīng)用，取得了良好效果，并逐漸成為重要的智能算法之一。
　　背包問題（Knapsack Problem,KP）的數(shù)學(xué)模型實(shí)際上是一個0-1規(guī)劃問題。假設(shè)有n個物件，其重量用aj表示，價值為cj(j=1,…n)，背包的最大容量為b。如果物件j被選入背包時，定義變量xj=1，否則xj=0?？紤]n個物件的選擇與否，背包內(nèi)物件的總重

3、量為∑ajxj，物件的總價值為∑cjxj，如何決定變量xj(j=1,…,n)的值（即確定一個物件組合）使背包內(nèi)物件總價值為最大。
　　通過對背包問題研究現(xiàn)狀的分析，提出了一種新的解決方法——基于自適應(yīng)的混合遺傳算法。
　　本文首先提出用基本遺傳算法解決背包問題的一般步驟，在求解過程中由于編碼過程會產(chǎn)生很多不滿足約束條件的無效染色體，對于這些不滿足約束條件的基因編碼串，可以利用“貪心法”的思想，優(yōu)先裝入ci/ai較大且xi=1

4、的物品，直到超過背包的容量限制再裝不下為止。對于基因編碼中指示應(yīng)裝入而實(shí)際上已裝不下的物品，修改其基因編碼串中對應(yīng)的xi為0，由此可產(chǎn)生一些新的基因編碼串，并且這些新編碼串總是相對來說質(zhì)量比較好的，特別是它們肯定滿足問題的約束條件。
　　在傳統(tǒng)的遺傳算法中，交叉概率Pc、變異概率Pm等控制參數(shù)與種群進(jìn)化過程無關(guān)，從始至終都保持定值。近年來的研究表明，控制參數(shù)對系統(tǒng)性能有重要的影響；用不變的控制參數(shù)來控制遺傳進(jìn)化，很容易導(dǎo)致“早熟”