劉陸洲，張曉霞

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

1 問題的提出

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

2 多維背包問題

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

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

3 改進(jìn)的蛙跳算法

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

改進(jìn)的蛙跳算法的概述如下：

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

圖1 改進(jìn)的蛙跳算法的具體流程

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

5 結(jié)語

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