馮艷紅 王改革 李明亮 李 晰

組合優(yōu)化問題(Combinatorial Optimization Pro-blem, COP)的求解一直是運(yùn)籌學(xué)領(lǐng)域重要的研究主題之一.典型的組合優(yōu)化問題包括:作業(yè)車間調(diào)度問題(Job Shop Scheduling Problem, JSSP)[1-2],圖著色問題(Graph Coloring Problem, GCP)[3],車輛路徑規(guī)劃問題(Vehicle Routing Problem, VRP)[4],旅行商問題(Travelling Salesman Problem, TSP)[5],多維背包問題(Multidimensional Knapsack Problem, MKP)[6].

多需求多維背包問題(Multidemand MKP, MDMKP)[7]是MKP的一個(gè)重要擴(kuò)展,也被證明是一類復(fù)雜的NP-hard問題.相比MKP,MDMKP包含一組與背包約束沖突的需求約束,是一類更難求解的多約束0-1規(guī)劃問題.現(xiàn)實(shí)生活中的很多問題可以建模為MDMKP,包括設(shè)備配置、選址方案設(shè)計(jì)、投資預(yù)算、證券選擇等,但是,MDMKP并未引起廣大學(xué)者更多的關(guān)注.

目前,針對MDMKP問題的求解分為兩類:確切性算法(Exact Algorithm)和啟發(fā)式算法(Heuristic Algorithm).Cappanera等[7]提出嵌套禁忌搜索啟發(fā)式算法,在標(biāo)準(zhǔn)禁忌搜索算法中增加擾動策略.Gortázar等[8]介紹一種黑盒分散搜索算法,特別提出一種靜態(tài)罰函數(shù)法,處理MDMKP問題的約束.Arntzen等[9]提出交替控制樹搜索框架,交替使用確切性算法和啟發(fā)式算法求解問題.Lai等[10]提出高效的基于兩階段解的禁忌搜索算法.Al-Shihabi[11]提出基于核思想的優(yōu)化框架,更新28個(gè)已知最優(yōu)解.因此,尋找有效的方法解決MDMKP問題是有意義的.

群智能算法[12-13]是利用群體智能高效求解優(yōu)化問題的方法,具有不依賴梯度信息、對待求解問題無需連續(xù)、可導(dǎo)等特點(diǎn),已被廣泛應(yīng)用于求解各類優(yōu)化問題,特別是組合優(yōu)化問題.受蛾子趨光性和萊維飛行的啟發(fā),Wang[14]提出蛾子搜索算法(Moth Search, MS),基于萊維飛行算子(Lévy Flight Ope-rator, LFO)和直接飛行算子(Straight Flight Ope- rator, SFO)實(shí)現(xiàn)種群中個(gè)體的更新.目前,MS已在數(shù)值優(yōu)化、約束優(yōu)化、多目標(biāo)優(yōu)化、組合優(yōu)化等諸多領(lǐng)域被廣泛應(yīng)用[15-16].因此,將MS應(yīng)用到MDMKP問題,無疑為該問題的求解提供一種新的方法.

因此,本文提出改進(jìn)蛾子搜索算法(Modified Moth Search, MMS),用于求解MDMKP問題.主要思想是:引入突變概率,設(shè)計(jì)突變直接飛行算子(Mutation SFO, MSFO),增強(qiáng)MMS的搜索能力;擴(kuò)大參數(shù)α的調(diào)節(jié)范圍,設(shè)計(jì)自適應(yīng)萊維飛行算子(Adaptive LFO, ALFO),幫助算法跳出局部最優(yōu);增加均勻變異算子(Uniform Mutation Operator, UMO),增強(qiáng)種群多樣性.

本文方法的創(chuàng)新之處在于:1)采用自適應(yīng)ε約束處理法解決MDMKP中兩組相互沖突的約束條件,從而易于采用群智能算法求解;2)對自適應(yīng)ε約束處理法的參數(shù)使用正交實(shí)驗(yàn)方法進(jìn)行驗(yàn)證,得到一組針對MDMKP問題的最適合參數(shù);3)基于空間轉(zhuǎn)換思想,設(shè)計(jì)應(yīng)用連續(xù)型群智能算法求解離散優(yōu)化問題的框架.

1 多需求多維背包問題模型

給定具有n個(gè)物品的集合V={1,2,…,n},MDMKP問題[10]可描述為:從集合V中選取一組滿足所有問題約束的物品組合并使所選物品總價(jià)值最大.數(shù)學(xué)描述如下:

xj∈{0,1}, ?j∈{1,2,…,n}.

(1)

其中,cj表示物品j的價(jià)值;xj表示物品是否被選中,xj=1表示物品被選擇,xj=0表示物品未被選擇;ai,j表示物品j對第i種資源的消耗量;bi表示第i種資源總量.特別地,式(1)的小于等于約束稱為背包約束,大于等于約束稱為需求約束.

不失一般性,有如下假設(shè):

2 改進(jìn)蛾子搜索算法求解多需求多維背包問題

2.1 基本蛾子搜索算法

在MS中,假設(shè)待求解問題對應(yīng)d維解空間,隨機(jī)初始化具有N個(gè)個(gè)體的種群

P={X1,X2,…,XN}

分布于此解空間,第i個(gè)蛾子個(gè)體在解空間的位置向量

Xi=[xi,1,xi,2,…,xi,d]T.

顯然,每個(gè)個(gè)體位置對應(yīng)目標(biāo)問題的一個(gè)潛在解.MS按照適應(yīng)度值升序排序后將種群等分為子種群1(SP1)和子種群2(SP2).子種群1中的個(gè)體依據(jù)LFO進(jìn)行位置更新,子種群2中的個(gè)體依據(jù)SFO進(jìn)行位置更新.

1)LFO.SP1中的個(gè)體i位置更新公式如下:

2)SFO.SP2中的個(gè)體i位置更新公式如下:

考慮最小優(yōu)化問題,MS流程如算法1所示.

算法1MS

輸入初始化所有參數(shù),適應(yīng)度函數(shù)f(X),

隨機(jī)初始化N個(gè)個(gè)體,確定問題維度D,

最大迭代次數(shù)T

輸出最優(yōu)蛾子個(gè)體的位置,對應(yīng)適應(yīng)度函數(shù)值

step 1 WHILE未達(dá)到最大迭代次數(shù)或終止條件DO.

step 2 計(jì)算個(gè)體適應(yīng)度值并進(jìn)行升序排列,記錄最優(yōu)個(gè)體信息.

step 3 種群劃分.適應(yīng)度值較小的N/2個(gè)體組成SP1,余下個(gè)體組成SP2.

step 4 應(yīng)用LFO更新SP1.

step 5 應(yīng)用SFO更新SP2.

step 6 合并兩個(gè)新生成子種群為一個(gè)種群.

step 7 判斷終止條件是否滿足.若未滿足,t=t+1,轉(zhuǎn)step 2.

2.2 改進(jìn)的蛾子搜索算法

一般而言,MS能夠求得全局最優(yōu)解.但是,面對一些復(fù)雜的約束優(yōu)化問題,特別是問題的可行解介于可行域和不可行域邊界之時(shí),MS可能會陷入局部最優(yōu).

MDMKP問題是復(fù)雜的離散約束優(yōu)化問題,問題的可行域是離散的,如何使搜索能穿梭于各個(gè)可行區(qū)域間,是該問題的主要挑戰(zhàn).多種群可能是解決該問題的方案之一.MS是基于兩個(gè)子種群進(jìn)化的群智能算法,為此,提出如下改進(jìn)策略.

1)自適應(yīng)萊維飛行算子(ALFO).在LFO中,參數(shù)α控制蛾子飛行的步長,該步長只與當(dāng)前迭代次數(shù)有關(guān),忽略總迭代次數(shù).受文獻(xiàn)[17]啟發(fā),將參數(shù)α修改為

2)突變直接飛行算子(MSFO).在SFO中,參數(shù)λ是調(diào)節(jié)因子,控制算法的收斂速度和種群多樣性.在MS中,參數(shù)λ∈U(0,1),為了使蛾子朝著當(dāng)前最優(yōu)個(gè)體飛去,使用一個(gè)與最大迭代次數(shù)和當(dāng)前迭代次數(shù)相關(guān)的突變率λ對蛾子個(gè)體的局部搜索進(jìn)行擾動.突變率

顯然:過高的突變率增加算法在搜索空間中搜索更多區(qū)域的概率,防止種群收斂到任何最優(yōu)解;過小的突變率可能導(dǎo)致種群早熟收斂到局部最優(yōu).參數(shù)λ從0.9線性遞減到0,突變率增加算法的搜索能力.

3)均勻變異算子(UMO).為了增加種群多樣性,對種群中每個(gè)個(gè)體的每個(gè)基因,以較小的概率pm進(jìn)行變異,即更新當(dāng)前基因?yàn)殡S機(jī)生成的(0,1)內(nèi)的隨機(jī)實(shí)數(shù).變異公式

xi,j=rand(),rand()≤pm,

其中,xi,j表示個(gè)體i的第j個(gè)分量,rand()是在(0,1)內(nèi)服從均勻分布的實(shí)數(shù).

將上述3種策略應(yīng)用到MS框架中,得到MMS.

2.3 解的表示

MS的提出是用來求解連續(xù)優(yōu)化問題,LFO和SFO在連續(xù)空間上的計(jì)算是封閉的,而MDMKP問題

的每個(gè)潛在解對應(yīng)一個(gè)二進(jìn)制向量,因此,直接應(yīng)用MS求解MDMKP問題是不可行的.

本文基于空間轉(zhuǎn)換機(jī)制[18],采用映射的方法,將搜索空間的實(shí)值向量轉(zhuǎn)換為問題空間的二進(jìn)制向量.假設(shè)

Ω={(x1,x2,…,xn)|Li≤xi≤Ui,1≤i≤n}

為n維搜索空間,

Φ={(y1,y2,…,yn)|yi∈{0,1},1≤i≤n}

為由所有可行解和不可行解組成的問題空間,則可構(gòu)建如下映射:

m∶Ω→Φ.

(2)

本文選取一種簡單有效的映射函數(shù)m(x)=x,映射方法

種群中的任何個(gè)體表示為一個(gè)二元組〈X,Y〉,其中,X構(gòu)成問題的搜索空間,Y形成問題的候選解空間.在本文中,X∈[-5,5]n,則Y∈{0,1}n.

下面以n=10為例,具體實(shí)值向量映射為二進(jìn)制向量的映射過程如表1所示.

表1 實(shí)值向量映射為二進(jìn)制向量Table 1 Mapping process from real valued vectors to binary vectors

2.4 自適應(yīng)ε約束處理法

由式(1)可知,MDMKP包含m個(gè)小于等于不等式約束,q個(gè)大于等于不等式約束,顯然兩組約束是對立的.采用傳統(tǒng)的約束處理技術(shù)如罰函數(shù)法,基于特定問題的不可行解修復(fù)法等很難對該約束進(jìn)行處理.

因此,本文采用自適應(yīng)ε約束處理法[19-21].該方法的核心思想是:基于人為設(shè)定的ε值,對個(gè)體的違約程度進(jìn)行排序,從而將個(gè)體劃分為不同的區(qū)域.在不同的區(qū)域中,可行解和不可行解采用不同的評價(jià)準(zhǔn)則.此方法有效利用不可行域中目標(biāo)函數(shù)值較好的不可行解信息,具有更好的收斂性能.ε水平控制方法如下:

(3)

其中,Xθ表示種群中個(gè)體按照約束違反程度升序排序后的第θ個(gè)個(gè)體,Tc表示代數(shù)控制參數(shù),cp在區(qū)間[2,10]中取值.

設(shè)兩個(gè)個(gè)體X1、X2的目標(biāo)函數(shù)值分別為f1、f2,約束違約度分別為φ1、φ2,則基于ε水平的個(gè)體比較規(guī)則如下:

具體算法框架如算法2所示.

算法2自適應(yīng)約束處理法

輸入初始化所有參數(shù),初始種群,當(dāng)前代數(shù)t

輸出第t代的ε值

step 1 對初始種群中所有個(gè)體的違約目標(biāo)進(jìn)行降序排列.

step 2 計(jì)算違約目標(biāo)值第θ·N大的值,記錄ε(0).

step 3 如果t≥Tc返回0值.

step 4 否則

step 4.1 計(jì)算當(dāng)前代所有個(gè)體違約目標(biāo)值.

step 4.2 如果違約目標(biāo)值為0的個(gè)體個(gè)數(shù)大于等于ap·N, 返回0值.

step 4.3 否則基于式(3)的第1項(xiàng)計(jì)算ε(t).

step 5 輸出ε(t).

2.5 求解算法框架

融合2.1節(jié)～2.4節(jié)的內(nèi)容,給出MMS求解MDMKP問題的流程,如算法3所示.

算法3MMS求解MDMKP框架

輸入初始化所有算法參數(shù),最大迭代次數(shù)T,

隨機(jī)初始化N個(gè)個(gè)體,適應(yīng)度函數(shù)f(X),

問題實(shí)例I

輸出最優(yōu)蛾子個(gè)體的位置,

對應(yīng)的適應(yīng)度函數(shù)值

step 1 WHILE未達(dá)到最大迭代次數(shù)或終止條件DO.

step 2 應(yīng)用式(2)對個(gè)體編碼為二元組〈X,Y〉.

step 3 基于自適應(yīng)ε約束處理法對個(gè)體進(jìn)行排序,記錄最優(yōu)個(gè)體信息.

step 4 種群劃分.較優(yōu)的N/2個(gè)體組成SP1,余下個(gè)體組成SP2.

step 5 應(yīng)用ALFO更新SP1.

step 6 應(yīng)用MSFO更新SP2.

step 7 應(yīng)用UMO更新SP1和SP2.

step 8 合并兩個(gè)新生成子種群為一個(gè)種群.

step 9 判斷終止條件是否滿足.若未滿足,t=t+1,轉(zhuǎn)step 2.

2.6 時(shí)間復(fù)雜度分析

應(yīng)用MMS求解MDMKP問題主要由種群初始化、自適應(yīng)ε約束處理、ALFO、MSFO、UMO組成.設(shè)種群規(guī)模為N,測試用例中物品個(gè)數(shù)為D,則種群初始化時(shí)間復(fù)雜度為O(ND).

在迭代過程中,對種群中所有個(gè)體按照自適應(yīng)ε約束處理,時(shí)間復(fù)雜度為O(N),SP1應(yīng)用ALFO進(jìn)行位置更新,時(shí)間復(fù)雜度為O(DN/2),SP2應(yīng)用MSFO進(jìn)行位置更新,時(shí)間復(fù)雜度為O(ND/2),UMO的時(shí)間復(fù)雜度為O(ND).

因此,每次迭代過程中算法的時(shí)間復(fù)雜度為

與MS一致.

3 實(shí)驗(yàn)及結(jié)果分析

本節(jié)通過實(shí)驗(yàn)評價(jià)MMS的綜合性能.實(shí)驗(yàn)包括如下3部分:1)考察自適應(yīng)ε約束處理法參數(shù)對算法性能的影響;2)考察3種策略對算法性能的影響;3)對比MMS與MS,驗(yàn)證MMS的優(yōu)越性.

3.1 測試函數(shù)與仿真環(huán)境

為了驗(yàn)證MMS的優(yōu)化性能,選取文獻(xiàn)[10]中的兩組測試用例與MS進(jìn)行對比.每組包含48個(gè)測試用例,表示為n-m-q-g-id.例如100-5-2-0-0表示該測試用例包含100個(gè)物品、5個(gè)背包約束、2個(gè)需求約束、第0組的第0個(gè)實(shí)例.第1組中n=100,第2組中n=250,兩組實(shí)例其余參數(shù)設(shè)置如下:

m=5,10,q=2,5,10,g=0,1,id=0,1,2,3,4,5.

與g=0組不同的是,g=1的組中項(xiàng)目對資源的消耗值可以為負(fù)值.具體實(shí)驗(yàn)數(shù)據(jù)可在https://grafo.etsii.urjc.es/optsicom/binaryss.html#instances下載.

為了確保實(shí)驗(yàn)的公平性,依據(jù)文獻(xiàn)[14],MS和MMS在所有測試用例上設(shè)置相同參數(shù).種群規(guī)模為50,迭代次數(shù)為1 000.算法參數(shù)設(shè)置如下:φ=0.618,MAXSTEP=1.0,λ取值為在(0,1)區(qū)間上服從均勻分布的隨機(jī)數(shù).此外,為了消除隨機(jī)性對算法性能的評估,2種算法在所有96個(gè)測試用例上均進(jìn)行30次獨(dú)立實(shí)驗(yàn).

本文采用最好目標(biāo)值(Best)、平均目標(biāo)值(Avg.)、最差目標(biāo)值(Worst)這3個(gè)基本性能指標(biāo).同時(shí),為了對比最好目標(biāo)值與已知最優(yōu)值(BKV)之間的相對偏差,引入Gap值考察算法逼近BKV的程度:

本文所有實(shí)驗(yàn)的硬件環(huán)境為:Intel(R) Core(TM) i5-2415M CPU 2.30 GHz、內(nèi)存4.00 GB,操作系統(tǒng)為Microsoft Windows 7.編程語言為Python,解釋器為Python3.9.

3.2 自適應(yīng)ε約束處理法參數(shù)分析

自適應(yīng)ε約束處理法包含3個(gè)主要參數(shù):θ,cp,Tc.一般而言,算法性能對參數(shù)設(shè)置具有敏感性.因此,基于正交實(shí)驗(yàn)設(shè)計(jì)(Orthogonal Experimental Design, OED)[22]尋找一組較優(yōu)的參數(shù)組合.實(shí)驗(yàn)包含3個(gè)因子,每個(gè)因子包含3個(gè)水平,設(shè)計(jì)具有9種組合的正交表.

選取100-5-2-0-0作為測試用例,每組參數(shù)組合獨(dú)立運(yùn)行30次,取平均值作為實(shí)驗(yàn)對比值,則不同參數(shù)值的組合如表2所示.正交實(shí)驗(yàn)參數(shù)及實(shí)驗(yàn)結(jié)果如表3所示.因子分析如表4所示,表中黑體數(shù)字表示最優(yōu)值.

表2 不同參數(shù)值組合Table 2 Combination of different parameter values

表3 正交實(shí)驗(yàn)參數(shù)及實(shí)驗(yàn)結(jié)果Table 3 Parameters of orthogonal experiment and experimental results

表4 基于正交設(shè)計(jì)方法的因子分析Table 4 Factor analysis based on orthogonal design method

從表4的標(biāo)準(zhǔn)差可以發(fā)現(xiàn):Tc是3個(gè)參數(shù)中最重要的參數(shù),需要合理選擇.基于上述OED,分析最適合的參數(shù)組合為θ=0.2,cp=5,Tc=500.下面實(shí)驗(yàn)將采用這組參數(shù).

3.3 改進(jìn)策略有效性分析

為了驗(yàn)證3種策略對MMS性能的影響,對比研究MS,包括MS應(yīng)用ALFO(簡記為MS-I)、MS應(yīng)用MSFO(簡記為MS-II)、MS應(yīng)用UMO(簡記為MS-III)、融合3種策略的MMS.選取100-5-2-0-id和100-5-2-1-id形式的12個(gè)測試用例,每種算法對每個(gè)測試用例均獨(dú)自運(yùn)行30次,實(shí)驗(yàn)結(jié)果如表5所示,表中黑體數(shù)字表示5種算法求解同個(gè)測試用例的最優(yōu)值,total欄表示4種改進(jìn)算法與MS相比取得更優(yōu)值的個(gè)數(shù).

表5 不同改進(jìn)策略的實(shí)驗(yàn)結(jié)果Table 5 Experimental results of different improvement strategies

由表5可知,ALFO和UMO均能在可行域復(fù)雜的情況下,充分挖掘搜索空間,對所有的12個(gè)測試用例的求解質(zhì)量均有所提高.MSFO對9個(gè)測試用例的最優(yōu)值有更高的精度,說明MSFO可以有效增加種群多樣性.同時(shí),融合3種策略的MMS的最優(yōu)值和Gap值都優(yōu)于單一改進(jìn)策略的MS,尋優(yōu)性能顯著,表明MMS能夠充分發(fā)揮不同改進(jìn)策略的優(yōu)點(diǎn).

為了從統(tǒng)計(jì)意義上說明4種改進(jìn)算法與MS是否有顯著性差異,采用Wilcoxon秩和檢驗(yàn)驗(yàn)證MS的12個(gè)測試用例的Best值在α= 0.05的顯著性水平下與其它算法的顯著性差異.其中:p-value>0.05,表明接受原假設(shè)H0,即認(rèn)為兩種優(yōu)化算法之間無顯著性差異,算法尋優(yōu)能力相當(dāng);p-value<0.05,拒絕原假設(shè)H0,即兩種算法存在顯著性差異.由此可見,MS-I、MS-III、MMS與MS存在顯著性差異,MS-II與MS無顯著性差異.由表5還可以看出,1)MMS在幾乎所有的12個(gè)測試用例中,取得的Best值均超過其它四種算法.說明三種策略的組合有益于提高算法求解性能.2)MS-I、MS-III在所有的12個(gè)測試用例上均優(yōu)于MS,MS-II在絕大多數(shù)測試用例上優(yōu)于MS,說明三種改進(jìn)策略均能夠提高M(jìn)S的優(yōu)化性能.3)相比MS-I和MS-III,MS-II的改進(jìn)效果不是很明顯,可能的原因是過高的突變率增加在搜索空間搜索更多可行域的概率,延緩算法收斂速度,太小的突變率導(dǎo)致算法早熟收斂.

3.4 MMS與MS對比

為了驗(yàn)證MMS對于MDMKP的求解能力,與MS對96個(gè)測試用例進(jìn)行對比,實(shí)驗(yàn)結(jié)果如表6～表9所示,表中黑體數(shù)字表示最優(yōu)值.

表6 MS和MMS求解100-5-x-x-x測試用例的實(shí)驗(yàn)結(jié)果Table 6 Experimental results of MS and MMS on test instances(100-5-x-x-x)

表7 MS和MMS求解100-10-x-x-x測試用例的實(shí)驗(yàn)結(jié)果Table 7 Experimental results of MS and MMS on test instances(100-10-x-x-x)

表8 MS和MMS求解250-5-x-x-x測試用例的實(shí)驗(yàn)結(jié)果Table 8 Experimental results of MS and MMS on test instances(250-5-x-x-x)

續(xù)表8Table 8(Continued)

表9 MS和MMS求解250-10-x-x-x測試用例的實(shí)驗(yàn)結(jié)果Table 9 Experimental results of MS and MMS on test instances (250-10-x-x-x)

由表6可以看出:1)就求得最優(yōu)結(jié)果的總個(gè)數(shù)而言,MMS的Best指標(biāo)、Avg.指標(biāo)、Worst指標(biāo)分別有20、24、20個(gè)優(yōu)于MS;2)就4種評價(jià)指標(biāo)平均值而言,MMS均優(yōu)于MS.

由表7可以看出,除了Worst指標(biāo)以外,MMS劣于MS.由此可以推斷,MMS可能對于測試用例的屬性具有敏感性.

由表8可以看出:1)就求得最優(yōu)結(jié)果的總個(gè)數(shù)而言,MMS的Best指標(biāo)、Avg.指標(biāo)、Worst指標(biāo)分別有20、8、6個(gè)優(yōu)于MS;2)就4種評價(jià)指標(biāo)平均值而言,MMS均優(yōu)于MS.

由表9可以看出,MMS的Avg.指標(biāo)有12個(gè)優(yōu)于MS,Worst指標(biāo)有10個(gè)優(yōu)于MS,Best指標(biāo)有4個(gè)劣于MS.

從表6～表9的對比結(jié)果可以看出,隨著問題維數(shù)的增大,MMS優(yōu)于MS的求解結(jié)果更加明顯,說明改進(jìn)策略在搜索復(fù)雜的可行域時(shí)優(yōu)勢突顯.

為了圖形化顯示MS和MMS求解n=100,250兩組實(shí)例的Gap指標(biāo)分布情況,圖1給出小提琴圖,圖中紅點(diǎn)表示中位數(shù),黑色盒型表示最集中的50%區(qū)域.從圖1可以看出:1)兩種算法均存在較明顯的離散值(上側(cè)的須和下側(cè)的須較長);2)MS求解兩組測試用例的Gap值分布相對集中,MMS的Gap值分布不太均勻.說明相比MS,MMS能夠求得更優(yōu)解,但算法的穩(wěn)定性需要進(jìn)一步提高.

(a)n=100

(b)n=250圖1 2種算法求解兩組測試用例的Gap值分布Fig.1 Gap value distribution of 2 algorithms on 2 sets of instances

3.5 測試用例屬性對算法性能影響

在MDMKP的每一組測試用例中,n-m-q-g-0測試用例中背包中物品價(jià)值系數(shù)全部為正整數(shù),n-m-q-g-1測試用例中背包中物品價(jià)值系數(shù)包含負(fù)整數(shù).為了說明算法的求解性能是否與測試用例的特征具有相關(guān)性,對MMS求得的兩組測試用例(n=100,250)的Gap值繪制散點(diǎn)圖,如圖2所示.

(a)n=100

(b)n=250圖2 96個(gè)測試用例的Gap值分布散點(diǎn)圖Fig.2 Scatter plot of Gap value distribution of 96 instances

從圖2可以得出如下結(jié)論.

1)總體而言,Gap值的分布與測試用例的分組基本一致,即同組的6個(gè)測試用例Gap值可以作為一組,其中100-10-5-1、250-5-2-0、250-5-5-0、250-10- 10-1四組測試用例尤其明顯,說明測試用例的屬性對算法的求解性能具有一定影響.

2)對于背包約束個(gè)數(shù)和需求約束個(gè)數(shù)相同的兩組實(shí)例,即g=0,1,組別為0的正系數(shù)測試用例求解效果明顯優(yōu)于組別為1的兼具正負(fù)系數(shù)的測試用例,前者整體處于后者的底端,說明收益可為正負(fù)值,增加求解難度.

3)背包約束個(gè)數(shù)的增加使可行域的搜索變得困難,解的質(zhì)量變差,Gap值相對較大.然而,需求約束個(gè)數(shù)增加,求解效果影響不明顯.可能的原因是約束條件比較寬泛.

4 結(jié) 束 語

MDMKP問題包含兩組對立的約束條件,使得該問題的求解非常困難.如果采用合適的方法,處理好約束,那么有可能降低問題的難度.本文提出基于ε約束處理法的改進(jìn)蛾子搜索算法(MMS),用于求解該問題,基于96個(gè)標(biāo)準(zhǔn)測試函數(shù)的實(shí)驗(yàn)表明,MMS比MS具有更高的尋優(yōu)精度.實(shí)驗(yàn)分析表明3種改進(jìn)策略對算法性能具有各自的影響:自適應(yīng)萊維飛行算子(ALFO)擴(kuò)大蛾子飛行步長的調(diào)節(jié)范圍,對個(gè)體進(jìn)行局部擾動,以更大概率跳出局部最優(yōu);變異直接飛行算子(MSFO)引入合適的突變率,防止種群過早收斂,增加在搜索空間中搜索更多區(qū)域的概率;均勻變異算子(UMO)以較小的概率更新種群中部分個(gè)體的基因,增加種群多樣性.同時(shí),本文還分析ε約束處理法的3個(gè)主要參數(shù)對算法性能的影響.

本研究工作豐富現(xiàn)存的求解MDMKP問題的技術(shù),下一步將考慮應(yīng)用不同約束處理方法,如可行性法則、多目標(biāo)優(yōu)化法等.此外,該框架也可應(yīng)用于求解其它的多約束組合優(yōu)化問題,如凸可分背包問題、動態(tài)背包問題、多目標(biāo)背包問題等.盡管MMS優(yōu)于MS,但解的質(zhì)量還需要進(jìn)一步提高.因此,提出更好的策略在復(fù)雜的搜索空間中尋求高質(zhì)量解將是下一步的研究工作.