進(jìn)化算法求解背包問題研究

黃林峰

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

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

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

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

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

（1）遺傳算法（Genetic Algorithms，簡稱GA）；

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

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

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

2 背包問題定義

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

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

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

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

4 結(jié)語

背包問題是一種NP難解問題，不存在多項(xiàng)式時(shí)間算法能求得其精確解，進(jìn)化算法由于其自身特點(diǎ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.