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

劉陸洲，張曉霞

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

1 問題的提出

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

2 多維背包問題

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

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

3 改進的蛙跳算法

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

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

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

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

4 實驗結(jié)果與分析

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

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

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

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

5 結(jié)語

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