遺傳算法在求解背包問(wèn)題中應(yīng)用

摘要：該文先對(duì)演化計(jì)算的基本概念進(jìn)行了簡(jiǎn)要介紹，然后詳細(xì)介紹了遺傳算法的基本原理、應(yīng)用及其基本結(jié)構(gòu)。最后，利用遺傳算法的思想，對(duì)傳統(tǒng)的背包問(wèn)題求解進(jìn)行了詳細(xì)的分析，按照遺傳算法的基本結(jié)構(gòu)，設(shè)計(jì)編碼、確定適應(yīng)值函數(shù)、確定變異和雜交操作，同時(shí)還給出了其非遺傳算法（遞歸算法）和遺傳算法運(yùn)行結(jié)果，并進(jìn)行了綜合分析。

關(guān)鍵詞：演化計(jì)算；遺傳算法；背包問(wèn)題

中圖分類號(hào)：TP317.4文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)26-1800-03

The Application of Genetic Algorithm in Solving Knapsack Problem

WANG Huai-jun1， DING Zhong-wen2

(1. Computer and Information Technology Institute of Langfang Normal College， Langfan 065000， China; 2. Computer and Information Technology Institute of Langfang Normal College， Langfan 065000， China)

Abstract: The paper introduces the basic concept of evolutionary computation， and then describes in detail the basic principles， application and basic structure of genetic algorithm. Finally， analyzes the traditional Knapsack problem using the idea of genetic algorithm， also gives the results of a non-genetic algorithm (Recursive Algorithm) and genetic algorithm in accordance with the basic structure of genetic algorithm， designing codes， determine the fitness function， identify variations and hybrid operation， and analyzes it.

Key words: evolutionary computation; GA; knapsack problem

1 演化計(jì)算和遺傳算法簡(jiǎn)介

大自然是我們解決各種問(wèn)題時(shí)獲得靈感的源泉。幾百年來(lái)，將生物界所提供的答案應(yīng)用于實(shí)際問(wèn)題求解已被證明是一個(gè)成功的方法，并且已形成一個(gè)專門(mén)的科學(xué)分支——仿生學(xué)（bionics）。

演化計(jì)算正是基于這種思想而發(fā)展起來(lái)的一種通用的問(wèn)題求解方法。它采用簡(jiǎn)單的編碼技術(shù)來(lái)表示各種復(fù)雜的結(jié)構(gòu)，并通過(guò)對(duì)一組編碼表示進(jìn)行簡(jiǎn)單的遺傳操作和優(yōu)勝劣汰的自然選擇來(lái)指導(dǎo)學(xué)習(xí)和確定搜索的方向。

而作為演化計(jì)算的重要分支，遺傳算法(Genetic Algorithm，GA)則是一種抽象于生物進(jìn)化過(guò)程的基于自然選擇和生物遺傳機(jī)制的優(yōu)化技術(shù)。

遺傳算法的基本原理如下：

在遺傳算法的執(zhí)行過(guò)程中，每一代有許多不同的種群個(gè)體（染色體）同時(shí)存在。這些染色體中哪個(gè)保留（生存）、哪個(gè)淘汰（死亡），是根據(jù)它們對(duì)環(huán)境的適應(yīng)能力來(lái)決定的，適應(yīng)性強(qiáng)的有更多的機(jī)會(huì)保留下來(lái)。適應(yīng)性強(qiáng)弱是通過(guò)計(jì)算適應(yīng)性函數(shù)f(x)的值來(lái)判別的，這個(gè)值稱為適應(yīng)值。適應(yīng)值函數(shù)f(x)的構(gòu)成與目標(biāo)函數(shù)有密切關(guān)系，往往是目標(biāo)函數(shù)的變種。主要的遺傳算子有如下幾種：

1) 選擇(Selection)算子又稱復(fù)制(reproduction)、繁殖算子。選擇是從種群中選擇生命力強(qiáng)的染色體，產(chǎn)生新種群的過(guò)程。選擇的依據(jù)是每個(gè)染色體的適應(yīng)值大小，適應(yīng)值越大，被選中的概率就越大，其子孫在下一代產(chǎn)生的個(gè)數(shù)就越多。選擇的方法根據(jù)不同的問(wèn)題，采用不同的方案。最常見(jiàn)的方法有比率法、排列法和比率排列法。

2) 雜交(Crossover)算子又稱重組(recombination)、配對(duì)(breeding)算子。當(dāng)許多染色體相同或后代的染色體與上一代沒(méi)有多大差別時(shí)，可通過(guò)染色體重組來(lái)產(chǎn)生新一代染色體。染色體重組分兩個(gè)步驟進(jìn)行：首先，在新復(fù)制的群體中隨機(jī)選取兩個(gè)染色體，每個(gè)染色體由多個(gè)位(基因)組成；然后，沿著這兩個(gè)染色體的基因隨機(jī)取一個(gè)位置，二者互換從該位置起的末尾部分基因。例如，有兩個(gè)用二進(jìn)制編碼的個(gè)體A和B，長(zhǎng)度L=5，A=a1a2a3a4a5，B=b1b2b3b4b5。隨機(jī)選擇一個(gè)整數(shù)k∈[1，L-1]，設(shè)k=4，經(jīng)雜交后變?yōu)椋?/p>

A=a1a2a3|a4a5 A'=a1a2a3b4b5

B=b1b2b3|b4b5 B'=b1b2b3a4a5

遺傳算法的有效性主要來(lái)自選擇和雜交操作，尤其是雜交，在遺傳算法中起著核心作用。

3)變異(Mutation)算子。選擇和雜交算子基本上完成了遺傳算法的大部分搜索功能，而變異則增加了遺傳算法找到接近最優(yōu)解的能力。變異就是以很小的概率，隨機(jī)改變字符串某個(gè)位置上的值。在二進(jìn)制編碼中，就是將0變成1，將1變成0。變異發(fā)生的概率極低（一般取值在0.001～0.02之間）。它本身是一種隨機(jī)搜索，但與選擇、雜交算子結(jié)合在一起，就能避免由選擇和雜交算子引起的某些信息的永久性丟失，從而保證了遺傳算法的有效性。

遺傳算法的研究工作主要集中在以下幾個(gè)方面：

1) 基礎(chǔ)理論：包括進(jìn)一步發(fā)展遺傳算法的數(shù)學(xué)基礎(chǔ)，從理論和試驗(yàn)研究它們的計(jì)算復(fù)雜性。

2) 分布并行遺傳算法：遺傳算法在操作上具有高度的并行性，許多研究人員都在探索在并行機(jī)和分布式系統(tǒng)上高效執(zhí)行遺傳算法的策略。

3) 分類系統(tǒng)：分類系統(tǒng)屬于基于遺傳算法的機(jī)器學(xué)習(xí)中的一類，包括一個(gè)簡(jiǎn)單的基于串規(guī)則的并行生成子系統(tǒng)、規(guī)則評(píng)價(jià)子系統(tǒng)和遺傳算法子系統(tǒng)。

4) 遺傳神經(jīng)網(wǎng)絡(luò)：包括連接權(quán)、網(wǎng)絡(luò)結(jié)構(gòu)和學(xué)習(xí)規(guī)則的進(jìn)化。遺傳算法與神經(jīng)網(wǎng)絡(luò)相結(jié)合，正成功地用于從時(shí)間序列分析來(lái)進(jìn)行財(cái)政預(yù)算。

5) 演化算法：模擬自然進(jìn)化過(guò)程可以產(chǎn)生魯棒的計(jì)算機(jī)算法——演化算法。遺傳算法是其三種典型的算法之一，其余兩種算法是進(jìn)化規(guī)劃(Evolutionary Programming，EP)和進(jìn)化策略(Evolutionary Strategies，ES)。這三種算法是彼此獨(dú)立地發(fā)展起來(lái)的。進(jìn)化規(guī)劃最早由美國(guó)的L.J.Fogel、A.J.Owens和M.J.Walsh提出；進(jìn)化策略則由德國(guó)的I.Rechenberg和H.P.Schwefel建立。具體應(yīng)用也很廣。

2 遺傳算法的基本結(jié)構(gòu)

遺傳算法的基本結(jié)構(gòu)主要可分為遺傳操作非重疊的演化算法和遺傳操作重疊的演化算法。結(jié)合本文的示例，以下僅給出一種遺傳操作重疊的演化算法。

{隨機(jī)初始化種群P(0)，t=0；

計(jì)算P(0)中個(gè)體的適應(yīng)值；

while(不滿足終止條件)do

{根據(jù)個(gè)體的適應(yīng)值及選擇策略計(jì)算P(t)內(nèi)每個(gè)個(gè)體的選擇概率pi；

for(k=0；k

{根據(jù)選擇概率pi在P(t)中選擇兩個(gè)父體；

r=random[0，1]；

If(r≤pr)

執(zhí)行繁殖操作，即將兩個(gè)父體每一位進(jìn)行變異后插入到新群體

P(t+1)中；

Else

執(zhí)行雜交操作，并依概率pm對(duì)兩雜交后代串中的每一位進(jìn)行變

異，然后再將產(chǎn)生的兩個(gè)后代插入到新群體P(t+1)中；}

計(jì)算P(t+1)中個(gè)體的適應(yīng)值；

t=t+1；}}

3 背包問(wèn)題

4 求解背包問(wèn)題的遺傳算法的具體實(shí)現(xiàn)

1)染色體的編碼：采用二進(jìn)制編碼，染色體的每一位表示一個(gè)物品，該位為“0”時(shí)表示不選中該物品，而該位為“1”時(shí)則表示選中該物品。所以染色體的長(zhǎng)度等于物品的總數(shù)目。

2) 適應(yīng)值的計(jì)算：當(dāng)染色體是“存活的”即該染色體所表示的選中的物品的總重量沒(méi)有超過(guò)背包的重量上限時(shí)，其適應(yīng)值為其所表示的選中的物品的總價(jià)值，否則為0。

3) 雜交算子：隨機(jī)選擇兩條染色體，隨機(jī)選取一個(gè)雜交位，將兩條染色體在雜交位之后的所有位進(jìn)行交換，即單點(diǎn)雜交的方式。

4) 變異算子：隨機(jī)選取一個(gè)雜交位，將該位進(jìn)行反置，即“1”變?yōu)椤?”，或者“0”變?yōu)椤?”。

5) 選擇辦法：根據(jù)各條染色體的選擇概率的大小，采用輪盤(pán)的方式選取，選擇概率由適應(yīng)值決定。

6) 復(fù)制：按選擇概率和輪盤(pán)的選擇辦法，直接從父代染色體中選取相等數(shù)量的子代染色體。

5 實(shí)驗(yàn)結(jié)果

在Visual C++ 6.0下編程實(shí)現(xiàn)上面的算法，得到的結(jié)果如下：

采用遞歸程序求解，可得到最優(yōu)解如下（物品按順序從0開(kāi)始編號(hào)）：

The max value is:590

The numbers selected are: 0 1 2 4 5 7 910121316171819202224

采用遺傳算法時(shí)得結(jié)果如下：

1) 當(dāng)種群數(shù)量（population）為50時(shí)

實(shí)驗(yàn)次數(shù)： 1 23 4 5 6 7 8 91011 12

解的價(jià)值：566544562577547554538528575560552564

去掉最低的528和最高的577，解的平均值為：556

該解同最優(yōu)解相差：34，約為5.8%

2) 當(dāng)種群數(shù)量（population）為100時(shí)

實(shí)驗(yàn)次數(shù)： 12 3 4 5 6 7 8 91011 12

解的價(jià)值：584548571565577571559560565586573586

去掉最低的548和最高的586，解的平均值為：571

該解同最優(yōu)解相差：19，約為3.2%

3) 當(dāng)種群數(shù)量（population）為50且演化代數(shù)由30增至60時(shí)

實(shí)驗(yàn)次數(shù)： 12 3 4 5 6 7 8 91011 12

解的價(jià)值：590540575560558542569570557586581553

去掉最低的540和最高的590，解的平均值為：565

該解同最優(yōu)解相差：25，約為4.2%

4) 當(dāng)種群數(shù)量（population）為50、演化代數(shù)為30，但變異數(shù)量增加一倍即到10時(shí)

實(shí)驗(yàn)次數(shù)： 12 3 4 5 6 7 8 91011 12

解的價(jià)值：568555571553577541556573547580569552

去掉最低的541和最高的580，解的平均值為：562

該解同最優(yōu)解相差：28，約為4.7%

6 結(jié)果分析

由于物品數(shù)量較大（25個(gè)），故用遞歸程序求解速度比較緩慢，當(dāng)物品數(shù)量達(dá)到30以上時(shí)，經(jīng)過(guò)相當(dāng)長(zhǎng)的時(shí)間仍無(wú)法完成計(jì)算，說(shuō)明窮舉法對(duì)于大規(guī)模問(wèn)題已經(jīng)無(wú)能為力。

然而采用遺傳算法求解則十分迅速，而且求得的較好解已十分接近最優(yōu)解。如第一次的577，第二次的586，而第三次的590已經(jīng)就是最優(yōu)解，由此可以看出遺傳算法在求解大規(guī)模問(wèn)題時(shí)與傳統(tǒng)算法相比較的明顯優(yōu)勢(shì)。

其次，關(guān)于參數(shù)的設(shè)定——影響演化算法的最優(yōu)化參數(shù)設(shè)置的主要障礙之一是參數(shù)之間的非線性相互作用。由以上實(shí)驗(yàn)可以看出，當(dāng)種群數(shù)量增加時(shí)，由于參與競(jìng)爭(zhēng)的模式增多，所求得的解也更靠近最優(yōu)解；當(dāng)種群演化代數(shù)增加時(shí)，通過(guò)雜交和變異產(chǎn)生的參與競(jìng)爭(zhēng)的新的模式也在增多，故所求得的解也同樣更靠近最優(yōu)解，但顯然，增加種群數(shù)量的效果會(huì)更好些；但當(dāng)增加變異數(shù)量時(shí)，所求得的解增加沒(méi)有以上兩個(gè)明顯，這說(shuō)明過(guò)多的變異不一定會(huì)使結(jié)果趨向最優(yōu)的趨勢(shì)變快。而且我們還可以很明顯的看到，上面參數(shù)對(duì)結(jié)果的影響都是非線性的。這一切都說(shuō)明演化算法本質(zhì)上是一個(gè)動(dòng)態(tài)的適應(yīng)的過(guò)程，任何一個(gè)在演化中固定不變餓參數(shù)設(shè)置都不可能是最優(yōu)的，在演化過(guò)程的不同階段應(yīng)具有不同的合適的參數(shù)設(shè)置，而且參數(shù)之間的相互影響非常復(fù)雜，是非線性的。在針對(duì)特定的問(wèn)題定制演化算法并在尋找問(wèn)題的解的過(guò)程中修改控制演化搜索的設(shè)置及其策略參數(shù)時(shí)，適應(yīng)的方法是一種很好的方法，但同樣不存在“最好”的自適應(yīng)的方法。

7 總結(jié)

本文根據(jù)遺傳算法的基本思路，探討了遺傳算法在解決背包問(wèn)題上的應(yīng)用，同時(shí)通過(guò)其同傳統(tǒng)算法之一遞歸算法的比較以及對(duì)控制參數(shù)的重新設(shè)置，分析了遺傳算法的在解決大規(guī)模問(wèn)題上的優(yōu)點(diǎn)以及控制參數(shù)的難點(diǎn)，對(duì)類似問(wèn)題的解決提供了一種參考。

值得注意的是遺傳算法收斂性的研究，長(zhǎng)時(shí)期以來(lái)僅僅局限在二進(jìn)制編碼方式下通過(guò)選擇控制參數(shù)來(lái)改進(jìn)和提高其收斂性能，但影響其收斂性的不僅僅是控制參數(shù)還有選定的遣傳算子結(jié)構(gòu)、性能和編碼方式等，編碼方式通過(guò)遺傳算子的作用間接影響算法的收斂性能。因此，我們有理由相信將自適應(yīng)的方法應(yīng)用與演化算法中將會(huì)在一定程度上提高算法的性能。

參考文獻(xiàn)：

[1] 陳根社，陳新海.遺傳算法的研究與進(jìn)展[J]. 信息與控制，1994，23(4):215-222.

[2] 方建安，邵世煌.采用遺傳算法學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)控制器[J].控制與決策，1993，8(3):208-289.

[3] Levitin A. Introduction to the Design and Analysis of Algorithms Second Edition[M]. Pearson Education Inc，2007.