黃林峰

摘要：01背包問(wèn)題（Knapsack Problem）是運(yùn)籌學(xué)中一個(gè)經(jīng)典的優(yōu)化難題，在現(xiàn)實(shí)生活中有著非常廣泛的實(shí)際應(yīng)用背景（如預(yù)算控制、貨物裝載、項(xiàng)目選擇等）。背包問(wèn)題的求解算法很多，進(jìn)化計(jì)算作為其中的一種，具有不依賴于初始群體的全局搜索能力，比較適合用來(lái)求解背包問(wèn)題。本文研究了利用進(jìn)化算法求解背包問(wèn)題的具體實(shí)現(xiàn)，對(duì)于現(xiàn)實(shí)中背包問(wèn)題實(shí)際應(yīng)用的求解有重要的意義。

關(guān)鍵詞：背包問(wèn)題 進(jìn)化算法 進(jìn)化策略

中圖分類號(hào)：TP181 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2016）12-0142-01

1 進(jìn)化算法簡(jiǎn)介

進(jìn)化算法（Evolutionary Algorithms，簡(jiǎn)稱EA）也稱為進(jìn)化計(jì)算（Evolutionary Computation，簡(jiǎn)稱EC）[1]，是基于自然界中的進(jìn)化策略，模擬自然生物進(jìn)化而形成的自適應(yīng)全局優(yōu)化搜索算法。它以一個(gè)初始種群為對(duì)象，通過(guò)隨機(jī)選擇種群中個(gè)體進(jìn)行重組、變異來(lái)產(chǎn)生新的個(gè)體。這些個(gè)體根據(jù)適應(yīng)能力強(qiáng)弱而被選擇或淘汰，被選擇的個(gè)體形成新一代種群。重組、變異、選擇組成了進(jìn)化算法的三個(gè)基本操作。個(gè)體編碼，適應(yīng)度函數(shù)計(jì)算等是進(jìn)化算法的重要內(nèi)容?；趯?duì)生物進(jìn)化的模擬，共產(chǎn)生了三種典型的進(jìn)化算法模型：

（1）遺傳算法（Genetic Algorithms，簡(jiǎn)稱GA）；

（2）進(jìn)化策略（Evolution Strategy，簡(jiǎn)稱ES）；

（3）進(jìn)化規(guī)劃（Evolutionary Programming，簡(jiǎn)稱EP）。

這些進(jìn)化模型基于不同的生物進(jìn)化背景，有不同的側(cè)重點(diǎn)，它們的進(jìn)化框架是一樣的，只是在具體的重組、變異或選擇算子上有所不同。

2 背包問(wèn)題定義

背包問(wèn)題（KP）是運(yùn)籌學(xué)中一個(gè)典型的優(yōu)化難題，在現(xiàn)實(shí)生活中有著廣泛的實(shí)際應(yīng)用背景（如預(yù)算控制、貨物裝載、項(xiàng)目選擇等），基本的0/1背包問(wèn)題的形式化定義如下[2]。

其中，n為所有物品的數(shù)目，pj和wj分別為第j個(gè)物品的價(jià)值和重量分別，c為背包的容量。背包問(wèn)題的目標(biāo)就是從給定物品的集合中選出一個(gè)子集，使得選中的所有物品的價(jià)值和最大，但是重量和不能超過(guò)背包的容量c。

3 進(jìn)化算法求解背包問(wèn)題框架

進(jìn)化算法是一種啟發(fā)式的群體搜索算法，符合達(dá)爾文“適者生存”和隨機(jī)信息交換的思想。進(jìn)化算法與傳統(tǒng)優(yōu)化方法相比具有不依賴于初始群體的全局搜索能力等多方面的優(yōu)勢(shì)，因此被廣泛的用來(lái)求解現(xiàn)實(shí)中的各種優(yōu)化問(wèn)題，其中包括背包問(wèn)題。圖1給出了進(jìn)化算法求解背包問(wèn)題的偽代碼。

4 結(jié)語(yǔ)

背包問(wèn)題是一種NP難解問(wèn)題，不存在多項(xiàng)式時(shí)間算法能求得其精確解，進(jìn)化算法由于其自身特點(diǎn)比較適合用來(lái)求解背包問(wèn)題，并得到了很多具體的應(yīng)用。

參考文獻(xiàn)

[1]Deb K. Multi2Objective Optimization Using Evolutionary Algorithms. Chicester， UK： JohnWiley & Sons， 2001.

[2]Hans Kellerer Ulrich Pferschy， David Pisinger. Knapsack Problems， Springer-Verlag Berlin，2004.