基于遺傳算法的0/1背包問題的改進(jìn)算法*

蔡照鵬，楊盛苑

(河南城建學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，河南平頂山467036)

作為強(qiáng)有力且應(yīng)用廣泛的隨機(jī)搜索和優(yōu)化方法，遺傳算法可能是當(dāng)今影響最廣泛的進(jìn)化計(jì)算方法之一［1］。在過去的幾年中，研究人員將更多的注意力放在工業(yè)工程領(lǐng)域的優(yōu)化問題上，因而得到了深入的研究［2］。理論方面的研究大多是圍繞該問題簡單的結(jié)構(gòu)，這種特點(diǎn)既可以深入探索許多組合特性，又可以通過解決一系列背包子問題來最終求解更為復(fù)雜的優(yōu)化問題。從實(shí)踐的角度來看，這些問題可以表述許多工業(yè)問題的應(yīng)用，最典型的應(yīng)用包括資本預(yù)算、貨物裝載和儲(chǔ)存分配等［3］。

在目前對(duì)背包問題的研究中，比較成熟的是使用貪心算法、回溯算法、遺傳算法、動(dòng)態(tài)規(guī)劃算法等求解。與其他組合優(yōu)化問題類似，許多研究人員常采用遺傳算法來求解背包問題［4］。本文提出了采用十進(jìn)制實(shí)數(shù)表示法求解背包問題的方法。

1 背包問題描述

背包問題:假設(shè)需要從許多物品中選擇一些來填充一個(gè)背包。存在n個(gè)不同的物品可以使用，每個(gè)物品j具有重量wj和費(fèi)用cj，物品被裝入的部分占該物品的百分比Xj(0≦Xj≦1)，背包可以承重的上限是W。問題是如何尋找物品的最優(yōu)子集從而在滿足背包承重約束上線W的條件下最大化總費(fèi)用，即在的條件下，求，其中m表示背包中裝入的物品的個(gè)數(shù)。其中費(fèi)用、重量和承重是正整數(shù)。

0/1背包問題:在背包問題的基礎(chǔ)上，每個(gè)物品不能被分割，一個(gè)物品只有被裝載和不被裝載兩種狀態(tài)，不存在部分裝載的情況，即上述背包問題中的Xj只能取0或者1。其數(shù)學(xué)模型實(shí)際上是一個(gè)0－1規(guī)劃問題。

背包問題是一個(gè)NP難的問題。相對(duì)于傳統(tǒng)的算法(如動(dòng)態(tài)規(guī)劃算法、回溯算法等)，使用遺傳算法求解背包問題能最快找出較優(yōu)的解。然而在一般情況下，使用基本遺傳算法解決背包問題時(shí)，得到問題的近似解不能滿足逼近最優(yōu)解的要求，并且算法會(huì)搜索一些無效解，成為當(dāng)前亟待解決的問題。本文探討了改進(jìn)遺傳算法解決0/1背包問題，使遺傳算法的搜索效率更高，并得到最優(yōu)的解。

一般認(rèn)為，遺傳算法有5個(gè)基本的組成部分［5］:問題解的遺傳表示、創(chuàng)建解初始種群的方法、根據(jù)個(gè)體適應(yīng)值對(duì)其進(jìn)行優(yōu)劣判定的評(píng)價(jià)函數(shù)、用來改變復(fù)制過程中產(chǎn)生的子個(gè)體遺傳組成的遺傳算子即雜交(這是遺傳算法中最主要的遺傳操作)［6］、遺傳算法的參數(shù)值。

遺傳算法由一群個(gè)體組成的種群P(t)(t代表遺傳代數(shù))。每一個(gè)個(gè)體均代表問題的潛在的解。遺傳算法的步驟描述如下:

(1)隨機(jī)生成初始種群;(2)是否滿足停止條件，如果滿足則轉(zhuǎn)到步驟(7)，否則，計(jì)算當(dāng)前群體每個(gè)個(gè)體的適應(yīng)度函數(shù);(3)根據(jù)當(dāng)前群體的每個(gè)個(gè)體的適應(yīng)度函數(shù)進(jìn)行選擇生成中間群體;(4)以概率Pc選擇兩個(gè)個(gè)體進(jìn)行染色體交換，產(chǎn)生新個(gè)體替換老個(gè)體，插入到群體中去(交叉);(5)以概率Pm選擇某一個(gè)染色體的某一位進(jìn)行改變，產(chǎn)生新的個(gè)體替換老的個(gè)體(變異);(6)轉(zhuǎn)到步驟(2);(7)終止。

2 算法二次優(yōu)化

2.1 算法準(zhǔn)備

染色體的編碼:采用十進(jìn)制實(shí)數(shù)表示法，首先選取正整數(shù)Mj，然后轉(zhuǎn)變?yōu)榕c背包個(gè)數(shù)相同的n位二進(jìn)制，并且按照項(xiàng)目中各個(gè)物品的重量由大到小映射，即這個(gè)n位二進(jìn)制的第一位對(duì)應(yīng)的物品重量最大，第二位對(duì)應(yīng)的物品重量次之，以此類推，最后一位對(duì)應(yīng)的物品的重量最小，顯然0≤Mj≤2n(0≤j≤n，n為背包的個(gè)數(shù))。

適應(yīng)值計(jì)算方法:與傳統(tǒng)算法相類似，當(dāng)染色體是“存活的”，即該染色體Mj所表示的選中物品的總重量沒有超過背包的重量上限W時(shí)，其適應(yīng)值為其所表示的選中物品的總價(jià)值，否則為0。

選擇辦法:對(duì)個(gè)體進(jìn)行評(píng)價(jià)，計(jì)算一代種群中的每一條染色體的適應(yīng)值。根據(jù)一代種群中的染色體Nj選擇概率的大小，采用輪盤賭選擇方式選取，即選取MAX(Mj/(M1+… +Mn))。

雜交算子:隨機(jī)選擇兩條染色體Mi和Mj，將Mi和Mj轉(zhuǎn)變?yōu)閚位二進(jìn)制以后，隨機(jī)選取一個(gè)不大于背包個(gè)數(shù)n的數(shù)acrossBit，acrossBit稱為雜交位，使兩條染色體從開始到雜交位的所有位進(jìn)行按序交換，即單點(diǎn)雜交方式。

變異算子:選取一條染色體Mj，將Mj轉(zhuǎn)變?yōu)閷?duì)應(yīng)的n位二進(jìn)制后，隨機(jī)選取一個(gè)雜交位，將該位進(jìn)行反置，即“0”變“1”，或者“1”變“0”。

最優(yōu)個(gè)體保護(hù):由于雜交和變異具有隨機(jī)性，有可能破壞最優(yōu)解結(jié)構(gòu)，因此要對(duì)最優(yōu)解進(jìn)行保護(hù)，方法是選取上一代中滿足條件且適應(yīng)值最大的個(gè)體Mj，并且選取下一代中適應(yīng)值最小的個(gè)體Mi，將Mj復(fù)制到下一代Mi對(duì)應(yīng)的位置(即將Mi覆蓋)。

處理死亡個(gè)體:首先將一代種群中的所有染色體按照適應(yīng)值由小到大排序，并檢查每一條染色體是否滿足

2.2 算法流程

(1)隨機(jī)生成初始種群P(t)，種群P(t)中每一條染色體都是隨機(jī)生成的正整數(shù)Mj(0≤Mj≤2n);(2)是否已經(jīng)進(jìn)行了t代，如果是則轉(zhuǎn)到步驟(8)，否則根據(jù)適應(yīng)值計(jì)算方法計(jì)算P(t)中每一條染色體的適應(yīng)值，并按照適應(yīng)值由小到大進(jìn)行排序;(3)檢查P(t)中的各染色體的值是否小于limitw，若大于則處理死亡個(gè)體，并且更新limitw的值為最小值;(4)根據(jù)選擇辦法對(duì)種群P(t)中的每一條染色體進(jìn)行評(píng)價(jià);(5)通過雜交、變異等方法，生成下一代群體P(t+1);(6)根據(jù)上述方法，保護(hù)最優(yōu)個(gè)體;(7)轉(zhuǎn)到步驟(2);(8)終止。

3 算法模擬

模擬環(huán)境:時(shí)間單位為s;硬件環(huán)境，CPU為Intel Core2 duo E8400，內(nèi)存容量為2.00GB;軟件環(huán)境，操作系統(tǒng)為Microsoft Windows xp，開發(fā)環(huán)境為Microsoft VC++6.0。，若不滿足，首先保存該染色體的值limitw(limitw的初值為背包的承重約束上線W)，并且更新limitw的值為最小的值，limitw的含義是適應(yīng)值等于或大于limitw的染色體，沒有必要進(jìn)行下一步的雜交和變異，因?yàn)檫@n位二進(jìn)制是根據(jù)物品的重量由大到小進(jìn)行映射的，當(dāng)適應(yīng)值等于limitw的染色體無法滿足條件時(shí)，大于limitw的染色體更無法滿足條件，然后將該染色體及其之后的染色體重新生成新一代染色體，直到生成的群體中的每一條染色體均滿足以上算法的實(shí)驗(yàn)數(shù)據(jù)如表1所示。實(shí)驗(yàn)效果對(duì)比如圖1所示。

表1 8組實(shí)驗(yàn)結(jié)果數(shù)據(jù)

4 結(jié)論

遺傳參數(shù)假定:雜交概率 Pc=0.8，變異概率 Pm=0.1。從實(shí)驗(yàn)結(jié)果可以看出:改進(jìn)后的遺傳算法明顯比以前的遺傳算法搜索的效率高，運(yùn)行時(shí)間短，并且誤差小。這說明，改進(jìn)后的遺傳算法可以有效避免無效搜索和算法在局部搜索，即能夠及時(shí)發(fā)現(xiàn)無效解，避免沒有必要的計(jì)算，并且防止算法在一個(gè)并非最優(yōu)解的局部不停搜索，甚至無法找到最優(yōu)解。這些證明對(duì)原遺傳算法在背包問題中應(yīng)用的改進(jìn)是有效可行的。

圖1 實(shí)驗(yàn)結(jié)果對(duì)比圖

［1］ 玄光男，程潤偉.遺傳算法與工程優(yōu)化［M］.北京:清華大學(xué)出版社，2009.

［2］ Alander J.An Indexed Bibliography of Genetic Algorithms［C］//Finland:Art of CAD Ltd，1994:102 －103.

［3］ Gordon V and Whitley D.Serial and parallel genetic algorithms as functions optimizers［C］//New York:Forrest，2008:177－183.

［4］ Michalewicz Z.Genetic Algorithm+Data Structure=Evolution Programs［M］.3rd.New York:Springer-Verlag，1996.

［5］ 王小平，曹立明.遺傳算法理論，應(yīng)用與軟件實(shí)現(xiàn)［M］.西安:西安交通大學(xué)出版社，2002.