改進的遺傳蟻群混合算法求解多維0/1背包問題

劉夢佳，向鳳紅，郭 寧，毛劍琳

(昆明理工大學 信息工程與自動化學院，云南 昆明 650500)

多維背包問題(Multidimensional Knapsack Problem，MKP)又名多約束背包問題，是著名的整數規劃問題之一。在實際應用中，許多問題都可以用多維背包問題來描述，如材料切割、資源分配、貨物裝載、投資決策等[1]。在近幾十年里世界上許多研究機構和個人對它做了大量的研究，已有的求解方法可分為精確方法(如分支定界法、回溯法、動態規劃法等[2])，近似算法(如貪婪法、拉格朗日法、蟻群優化算法[3-5]、粒子群算法[6]、遺傳算法[7]、布谷鳥算法[8]等)以及混合算法3大類。

遺傳算法[7]是受生物進化啟發發展起來的一種智能優化算法，它模擬生命進化機制，即模擬自然選擇和遺傳進化中發生的繁殖、交配和突變現象，從任意一個初始種群出發，通過選擇、交叉和變異操作，產生一群新的更適應環境的個體，一代代不斷繁殖、進化，最后收斂到最適應環境的個體上，求得問題的最優解。遺傳算法具有較強的全局搜索能力，但收斂速度較慢，求解精度不高。蟻群算法[9]求解多維背包問題時，每只螞蟻主要根據積累在物品上的信息素量的大小來依次選擇是否生產該物品，被螞蟻選擇的物品就是要消耗資源所生產的物品。在蟻群算法進行過程中，信息素正反饋的思想使其能較快收斂到局部最優解，但其全局搜索能力較低，易陷入局部最優，產生早熟現象。近年來，遺傳蟻群混合算法得以快速發展，涌現出多種混合方式[10-13]。……