基于改進蛙跳算法求解背包問題

劉陸洲，張曉霞

（遼寧科技大學計算機與軟件工程學院，鞍山 114051）

1 問題的提出

近年來，我國物流行業發展迅速、市場規模日益擴大，物流行業逐漸走向有序化，整個行業開始進入到快速發展時期。與此同時，物流行業在如何提高工作效率方面的壓力與日俱增，高人力成本成為了物流公司的一大負擔，這也促使傳統的物流行業必須加快向著智能化、高效化的方向轉型升級。我國無人卡車、人工智能正處于研發測試階段，未來發展前景巨大[1]，因此，研究多維背包問題，對如何選取所要運輸的包裹和怎樣裝載包裹才能更好地利用有限的資源都有著較大的積極作用，同時對加快我國的“智慧城市”建設也有著重要的理論價值和意義。

2 多維背包問題

在一定范圍內給出n 個物品，每個物品都具有三個屬性值，即價值（f），體積（v）和重量（w），其中，fi為第i 個物品所具有的價值，vi為第i 個物品的體積（i=1，2，…，n），wi為第 i 個物品的重量（i=1，2，…，n），背包所能承受的最大重量為W，最大容量為V，則多維背包問題的數學模型為：

其中，所求目標為所有選中物品的總價值之和的最大值F，同時所選物品占用的資源必須遵循約束（2）背包容量V 的限制和約束（3）中背包最大承重W 的限制；約束（4）中xi表示可選擇的物品i 的狀態值被限制為0 或者1，若將物品i 選中放入背包，則xi的值設置為1，否則設置為0。每件物品只能選擇一次，并且不能將物品切割部分放置在背包中。通過對公式（1）-（3）的分析不難看出，該問題的計算復雜度隨物品個數的增加呈現指數形式的增長，因此，背包問題[2]屬于一個NP 完全組合優化問題[3]，在合理時間內，蛙跳算法在非連續的解空間條件下無法精準計算出結果，故需要對蛙跳算法的求解方法進一步改進。

3 改進的蛙跳算法

選用遺傳算法的更新策略來替代普通的蛙跳算法[4-5]的個體更新方式，該方法不但具有蛙跳算法的優點，擁有了較高的搜索性能，而且也提升了在不同解空間下得到更好的解決方案的能力。

改進的蛙跳算法的概述如下：

初始化蛙跳算法的閾值，設置相關的約束參數，包括背包的極限載重W 和極限容積V。在可行解空間下，初始化解決方案，利用隨機數生成器生成適宜數量的個體，個體集為F={x1,x2,…,xF}，并計算它們的適應度fi。將個體按照適應度降序的方式排列并劃分子群，標記子群中最優個體Pb和種群內最優個體Pg。用所要更新的子群中最優個體Pb與當前子群內個體進行交叉遺傳變異操作，產生新的子個體。如果子個體的適應度優于所要更新的親代個體，那么子個體替代親代個體；否則，用整個種群內最優個體Pg與所要更新的個體進行遺傳操作產生新的子個體，如果子個體的適應度優于親代的，則用其替代親代；否則，隨機生成一個新的子個體替代親代個體，完成上述更新操作，則視為個體更新結束。對種群內所有個體都重復執行更新操作直至達到預先設定的迭代次數，則視為種群的局部搜索過程完成。重復不斷地劃分種群、保留下較好的基因序列，直至達到設定的更新閾值即為結束，圖1 給出了改進的蛙跳算法解決多維背包問題的具體流程。

圖1 改進的蛙跳算法的具體流程

4 實驗結果與分析

為驗證改進后算法的性能，所提出的改進型蛙跳算法采用C++編程。測試實例采用OR-Library（http://people.brunel.ac.uk/～mastjjb/jeb/orlib/files/mdmkp_ct1.

txt）中的典型數據。改進的蛙跳算法中存在一些約束參數，這些參數的設置會影響到算法解的質量，我們設定改進的蛙跳算法的種群規模為200，子群數量為20，迭代的最大次數為1000，為測試跳躍閾值對解的影響，選取跳躍值不同時，得出的解的質量，經過大量實驗得出，跳躍閾值為6 時所獲得的解的質量更好。

表1 給出了改進的蛙跳算法與普通的蛙跳算法運行結果的比較，為了能更加清晰的得出改進的蛙跳算法相比普通的蛙跳算法性能上的提升量，設定解的價值、實際載重和占用空間在性能上的權值分別為0.6、0.2 和0.2，通過實驗得出改進的蛙跳算法解的性能更高，平均提升的的權值約5.20‰，從表中的數據可以看出，改進的蛙跳算法在得到高質量解的同時能夠更有效地利用背包資源，該算法在解決MKP 問題時相比普通的蛙跳算法具有一定的優越性。

表1 改進的蛙跳算法與普通的蛙跳算法運行結果比較

5 結語

本文詳細闡述了改進后的蛙跳算法的基本原理，將遺傳算法的交叉遺傳變異機制嵌入到普通的蛙跳算法的更新方法中，獲得了一種計算性能更好的改進算法，避免了算法在解決問題當中出現局部最優和過早收斂的問題。通過大量的實驗，對測試所得的數據進行分析得出：改進后的蛙跳算法在解決多條件背包問題時所產生的解仍然具有較高的可行性，相較于普通的蛙跳算法擁有更廣的適用范圍。