背包問(wèn)題的遺傳算法求解.pdf

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

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

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

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