進化算法求解背包問題研究

黃林峰

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

關鍵詞：背包問題 進化算法 進化策略

中圖分類號：TP181 文獻標識碼：A 文章編號：1007-9416（2016）12-0142-01

1 進化算法簡介

進化算法（Evolutionary Algorithms，簡稱EA）也稱為進化計算（Evolutionary Computation，簡稱EC）[1]，是基于自然界中的進化策略，模擬自然生物進化而形成的自適應全局優化搜索算法。它以一個初始種群為對象，通過隨機選擇種群中個體進行重組、變異來產生新的個體。這些個體根據適應能力強弱而被選擇或淘汰，被選擇的個體形成新一代種群。重組、變異、選擇組成了進化算法的三個基本操作。個體編碼，適應度函數計算等是進化算法的重要內容?；趯ι镞M化的模擬，共產生了三種典型的進化算法模型：

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

（2）進化策略（Evolution Strategy，簡稱ES）；

（3）進化規劃（Evolutionary Programming，簡稱EP）。

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

2 背包問題定義

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

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

3 進化算法求解背包問題框架

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

4 結語

背包問題是一種NP難解問題，不存在多項式時間算法能求得其精確解，進化算法由于其自身特點比較適合用來求解背包問題，并得到了很多具體的應用。

參考文獻

[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.