一種改進的模擬退火螢火蟲混合算法求解0/1背包問題

任靜敏，潘大志

(西華師范大學數學與信息學院，四川南充 637000)

0 引言

背包問題(knapsack problem，KP)[1]是運籌學中典型的組合優化問題，即給定n個物品的重量和價值，選擇一組物品，使其總重量不超過給定的背包容量，并得到盡可能大的總價值.模型廣泛運用于資本預算、負荷問題、資源配置、項目選擇實際問題中.目前解決背包問題有兩類方法：精確算法和啟發式算法，其中精確算法有分支界定法、動態規劃法、回溯法、割平面法等，精確算法能求得問題的最優解，但往往時間成本過大，占有內存較大.啟發式算法的出現有效的提高了這些問題的求解效率.隨著啟發式算法不斷被研究和改進，求解背包問題在求解時間和求解精度上取得平衡，目前的啟發式算法有遺傳算法[2]、蟻群算法[3]、粒子群算法[4]、人工魚群算法[5]、螢火蟲算法[6]等.

此前已有學者將螢火蟲算法、模擬退火算法等用于求解一些實際問題.例如，候聰亞等[7]將振蕩權重函數和模擬退火算法引入到螢火蟲算法中,抑制螢火蟲算法在極值點區域出現無規則的振蕩現象,并將改進后的算法用于對橋式起重機箱型主梁優化.羅天洪等[8]提出一種基于時變螢火蟲群優化算法，該算法根據螢火蟲與鄰域內所有螢火蟲個體間的最小距離改變而時變步長，引入Boltzman選擇機制，實時動態調整搜索過程中的移動方向與位置，增強了算法的動態適應性，改進后的算法用于平面冗余機器人手臂運動學逆解問題求……