文化基因算法在多約束背包問題中的應用

摘 要：文化基因算法是一種啟發式算法，與一些經典數學方法相比，更適于求解多約束背包問題。文化基因算法是一種基于種群的全局搜索和基于個體的局部啟發式搜索的結合體，針對多約束問題，提出采用貪婪策略通過違反度排序的方法處理多約束條件，全局搜索采用遺傳算法，局部搜索采用模擬退火策略，解決具有多約束條件的0－1背包問題。通過對幾個實例的求解，表明文化基因算法與標準遺傳算法相比，具有更優的搜索性能。

關鍵詞：文化基因算法；背包問題；遺傳算法

中圖分類號：TP301 文獻標識碼：A

1 引言

背包問題是典型的組合優化問題，同時也是一個典型的NP完全問題。背包問題是指從若干件物品中選擇部分物品，放入有一定承重限制的背包，應如何選擇物品使得裝入背包中的物品價值最大。各國研究者們一直在研究如何更好地求解背包問題，因為背包問題是從很多實際應用問題，諸如資源分配、投資決策、貨物裝載等抽象出的數學模型。簡單的背包問題可以用動態規劃法、回溯法、分支界定法、貪心法等方法求解，隨著問題復雜性的增加，越來越多的人采用啟發式算法解決背包問題，如禁忌搜索、模擬退火算法、遺傳算法、蟻群算法、粒子群算法等。

“注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”