文化基因算法在多約束背包問題中的應(yīng)用

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

關(guān)鍵詞：文化基因算法；背包問題；遺傳算法

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

1 引言

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

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