一種基于模式替代的遺傳算法解０／１背包問題

(1.江西理工大學(xué) 信息工程學(xué)院， 江西 贛州 341000；2.中國科學(xué)院 自動化研究所， 北京 100080)



摘 要：背包問題是一個典型的 NP完全問題。提出一種基于模式替代的遺傳算法解0/1背包問題思想，通過收集每代種群中最好的幾個個體生成模式來引導(dǎo)種群的搜索方向，以提高遺傳算法的搜索速度和尋找最優(yōu)解的能力。通過仿真數(shù)值實(shí)驗(yàn)，將該方法與簡單遺傳算法、貪心算法計算結(jié)果比較分析，充分證明了使用基于模式替代遺傳算法來求解背包問題的有效性和實(shí)用性。

關(guān)鍵詞：背包問題；模式替代；遺傳算法 

中圖分類號：TP311 文獻(xiàn)標(biāo)志碼：A

文章編號：10013695(2009)02047002



Genetic algorithm with schema replaced for solving 0/1 knapsack problem



LI Kangshun1，2，JIA Yuzhen1，ZHANG Wensheng2

(1.School of Information Engineering， Jiangxi University of Science Technology， Ganzhou Jiangxi 341000， China;2.Institute of Automation， Chinese Academy of Sciences， Beijing 100080， China)

Abstract:Knapsack problem is a typical NP complete problem．This paper raised genetic algorithm with schema replaced for solving 0/1 knapsack problem．It leaded the search direction of the population to a schema by collecting the best several individuals in population.So，improved the searching efficiency and ability. At last，gave the simulation experiment，and the answer of the knapsack problem which was solved by simple genetic algorithm，compared greedy algorithm and genetic algorithm with schema replaced．By this comparison，the advantages which use schema replaced to solve knapsack problem is proved to be efficient and practical．

Key words:knapsack problem(KP); schema replaced; genetic algorithm



近年來，背包問題吸引了許多理論和實(shí)際工作者對此問題的深入研究。在理論上盡管背包問題的結(jié)構(gòu)簡單，但它卻具有組合爆炸的性質(zhì)。在實(shí)際應(yīng)用中，許多工業(yè)問題均可以用背包問題來描述，如資金運(yùn)算、貨艙裝載、存儲分配等都是典型的應(yīng)用例子[1]。求解背包問題有許多傳統(tǒng)的算法，如貪心算法、動態(tài)規(guī)劃算法、回溯法、分支限界法等，它們各自都存在一些缺陷。

遺傳算法[2，3]是Holland和他密西根大學(xué)的同事提出的以自然選擇和基因繁殖的思想為基礎(chǔ)的一種高度并行、隨機(jī)和自適應(yīng)全局優(yōu)化搜索算法。遺傳算法一般在開始隨機(jī)產(chǎn)生初始群體，然后不斷地改進(jìn)個體，以得到越來越好的結(jié)果。由于收斂速度和尋找最優(yōu)解往往是一對矛盾，基本遺傳算法(SGA)常表現(xiàn)為收斂速度慢，容易早熟、陷入局部最優(yōu)解。本文提出了基于模式替代的思想，通過收集每代種群中最好的幾個個體生成模式來引導(dǎo)種群的搜索方向，提高了遺傳算法的搜索速度和尋找最優(yōu)解的能力。

1 背包問題

背包問題[4](KP)的一般提法是：已知n個物品的重量（weight）及其價值（或收益profit）分別為wi＞0和pi＞0，背包的容量（contain）假設(shè)設(shè)為ci＞0，如何選擇哪些物品裝入背包可以使得在背包的容量約束限制之內(nèi)所裝物品的價值最大？

該問題的模型可以表示為下述0/1整數(shù)規(guī)劃模型： 

max f(x1，x2，…，xn)=ni=1pixi

目標(biāo)函數(shù)：s.tni=1wixi≤ci

xi∈{0，1}(i=1，2，…，n)

其中：xi為01決策變量，xi=1時表示將物品i裝入背包中，xi=0時則表示不將其裝入背包中。

2 模式的基本理論

1)模式[5，6](schema) 它是基于三值字符集 {0，1，*}所產(chǎn)生的能描述具有某些結(jié)構(gòu)相似性的0、1字符串集的字符串；是一個描述字符串集的模板，該字符串中的某些位置上存在相似性。以長度為 5的串為例，模式*1**0 描述了在位置 2為“1”及在位置5為“0”的字符串，即{01000，01010，01100，01110，11000，11010，11100，11110}。

2)模式階 它是指模式中確定位置的個數(shù)，用來反映模式之間所匹配的字符串的個數(shù)不同。比如模式011*1與模式1****相比，前者的模式階為4，后者的模式階為1，前者的確定性高，能匹配的串的個數(shù)比后者少。

3)模式的定義距 它是指模式中的第一個確定位置和最后一個確定位置之間的距離。比如模式 011*1的定義距為4，而模式0****為0。

4)Holland的模式定理 在遺傳算子選擇、交叉和變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式在子代中將得以指數(shù)級增長。模式定理是遺傳算法的理論基礎(chǔ)。

5)積木塊假設(shè) 低階、短距、高平均適應(yīng)度的模式 (積木塊)在遺傳算子作用下，相互結(jié)合，能生成高階、長距、高平均適應(yīng)度的模式，可最終生成全局最優(yōu)解。

模式定理和積木塊假設(shè)保證了遺傳算法尋找到全局最優(yōu)解的能力。

3 基于模式替代的遺傳算法

遺傳算法通過選擇算子將當(dāng)前群體中的優(yōu)良模式遺傳到下一代群體中；通過交叉算子進(jìn)行模式重組；通過變異算子進(jìn)行模式突變；通過這些遺傳運(yùn)算，一些較差的模式被淘汰，而一些較好的模式逐步被進(jìn)化，最終得到問題的最優(yōu)解。從實(shí)際計算中可以發(fā)現(xiàn)，最優(yōu)解和次優(yōu)解或者表現(xiàn)比較好的個體存在相對程度的相似，也可以說表現(xiàn)良好的個體中含有最優(yōu)解的基因基本遺傳算法在進(jìn)化到一定的代數(shù)后，次優(yōu)解和次優(yōu)解相似的個體占了大部分，那么交叉和變異操作往往可能只是在最優(yōu)解的基因塊內(nèi)部發(fā)生，所以導(dǎo)致遺傳速度很慢。

采用保存最優(yōu)個體的策略能確保遺傳算法找到最優(yōu)解，但是其收斂過程往往是緩慢的。僅僅簡單采取將最好結(jié)果保存不能很好地發(fā)揮好的模式對群體的影響，因此，本文對此進(jìn)行了改進(jìn)。

3.1 改進(jìn)策略

3.1.1 模式生成方法

根據(jù)模式定理，個體中的部分基因在遺傳操作作用下隨著進(jìn)化的迭代，將在種群中迅速增加。收集每一代中最好的一個或者幾個個體，將其記錄下來，構(gòu)成生成模式的采樣空間，對每一位上的1(或0)的個數(shù)進(jìn)行統(tǒng)計。如果某一位上1(或0)的個數(shù)比例超過了某一比例數(shù)pPar(本文中稱之為模式固定率)，則此位值為1(或0)，否則為*(設(shè)置為2)，由此得到模式。那么這些確定的1或0，可以認(rèn)為它是染色體中的優(yōu)良基因。還可以對模式進(jìn)行評估和校正，如果模式中確定的位數(shù)太多，即模式的階數(shù)太大，可以提高比例數(shù)pPar，讓確定的位數(shù)減少。如果模式中確定的位數(shù)太少，即模式的階數(shù)太小，則降低比例數(shù)pPar，讓確定的位數(shù)增加。

例如，模式的采樣空間為1010110110111110，設(shè)在某位上1(或0)的個數(shù)超過或等于0.75(比例數(shù)pPar取0.75)，可以認(rèn)為此位置為定值1(或0)，則以上采樣空間產(chǎn)生的模式為1*1*。

3.1.2 模式替換

選擇算子是優(yōu)良模式增加快慢的關(guān)鍵，選擇算子不會產(chǎn)生新的模式卻會造成一些模式的丟失。弱的選擇算子雖然可以保留更多的模式，但會造成高適應(yīng)度的模式得不到有效保留，算法收斂效率不高，而強(qiáng)的選擇算子雖然加快整體算法的收斂速度但同時加快了一些模式的丟失，算法易陷入局部最優(yōu)，即早熟變異算子對早熟有抑制作用，但總體上交叉和變異算子將破壞模式的遺傳。

本文采用將模式中不確定的“*”進(jìn)行隨機(jī)取值產(chǎn)生新個體，比如若模式是 1*1*，那么可能的隨機(jī)產(chǎn)生的新個體包括{1111，1110，1010，1011}。這些產(chǎn)生的新個體將取代原群體中的最壞的個體，以便好的模式即使在經(jīng)過交叉和變異后也有比較大的概率存活下來，保證了好的基因不丟失，同時減少了過多的模式，在提高尋優(yōu)能力的同時防止早熟。

3.2 算法步驟

a)初始化種群。隨機(jī)產(chǎn)生初始染色體，采用二進(jìn)制編碼，適應(yīng)值函數(shù)即是背包物品的價值。

b)對種群進(jìn)行統(tǒng)計，記錄最好的幾個個體。

c)根據(jù)記錄的最好個體形成模式的采樣空間，根據(jù)3.1.1節(jié)的策略產(chǎn)生模式。

d)進(jìn)行模式替換。根據(jù)模式產(chǎn)生新的個體，如果比最差的個體好則替換群體中的最差個體。

e)進(jìn)行選擇、交叉、變異等操作。對產(chǎn)生的每個新的個體進(jìn)行適應(yīng)值判斷：若產(chǎn)生的個體較本代最差的個體好，則替換掉最差個體，否則保留原個體。

f)是否到最大的遺傳代數(shù)，如果達(dá)到則輸出結(jié)果，結(jié)束算法；否則轉(zhuǎn)b)繼續(xù)執(zhí)行。

4 數(shù)據(jù)實(shí)驗(yàn)

本文就以上算法設(shè)計思想，對所需要實(shí)現(xiàn)的背包問題，用上述方法進(jìn)行了實(shí)驗(yàn)，并取得了良好的結(jié)果。在實(shí)驗(yàn)中，所用的參數(shù)定義為演化代數(shù)1 000，種群規(guī)模200，雜交率0.618，變異率0.06，產(chǎn)生模式的個體數(shù)50，模式位固定率0.7。問題實(shí)例來自文獻(xiàn)[7]。

各算法重復(fù)運(yùn)行10次，比較算法所能夠求得的最好的結(jié)果(總價值／總重量)，并給出其對應(yīng)的染色體，則貪心算法、基本遺傳算法與基于模式替代的遺傳算法對實(shí)例1～3的計算結(jié)果如表1所示。



表1 實(shí)驗(yàn)結(jié)果

上述實(shí)驗(yàn)結(jié)果表明，用模式替代方法確實(shí)能夠有效解決0/1背包問題，而且得到的解比較好、收斂速度快，利用模式替代的方法是一種可行和有效的方法。

5 結(jié)束語

本文為了求解0/1背包問題，在基本遺傳算法的基礎(chǔ)上，根據(jù)模式的一些基本理論，通過好個體的生成來引導(dǎo)種群的搜索方向，形成了基于模式替換的遺傳算法。通過大量的數(shù)值模擬實(shí)驗(yàn)證明了基于模式替換的遺傳算法在求解0/1背包問題時是很有效的，尤其在物品較多時效果更明顯，而且具有很好的穩(wěn)定性。

參考文獻(xiàn)：

［1］

王曉東．算法設(shè)計與分析[M].北京：清華大學(xué)出版社，2003.

[2]HOLLAND J H.Adaptation in natural and artificial systems[M].Ann Arbor：UniversityMichiganPress，1975.

[3]潘正君，康立山，陳毓屏.演化計算[M].北京: 清華大學(xué)出版社，1998.

[4]李娟，方平.一種求解背包問題的混合遺傳算法[J].南昌航空工業(yè)學(xué)院學(xué)報，1998，12(3)：3135.

[5]陳國良，王煦法，莊鎮(zhèn)泉，等.遺傳算法及其應(yīng)用[M]．北京：人民郵電出版社，l996.

[6]周明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京：國防工業(yè)出版社，1999.

[7]賀毅朝，劉坤起，張翠軍，等.求解背包問題的貪心遺傳算法及其應(yīng)用[J].計算機(jī)工程與設(shè)計，2007，28（11）：26552657，2681.