面向異構(gòu)多背包問(wèn)題的多級(jí)二進(jìn)制帝國(guó)競(jìng)爭(zhēng)算法

李 斌，唐志斌

（1.福建理工大學(xué) 機(jī)械與汽車(chē)工程學(xué)院，福州 350118；2.福建省大數(shù)據(jù)挖掘與應(yīng)用技術(shù)重點(diǎn)實(shí)驗(yàn)室（福建理工大學(xué)），福州 350118；3.福建理工大學(xué) 交通運(yùn)輸學(xué)院，福州 350118）

0 引言

背包問(wèn)題（Knapsack Problem，KP）［1］是一類(lèi)經(jīng)典的組合優(yōu)化問(wèn)題，也是典型的NP-hard 問(wèn)題［2］。該類(lèi)問(wèn)題有諸多變種，如0-1 背包問(wèn)題、完全背包問(wèn)題、多維背包問(wèn)題［3-4］、多重背包問(wèn)題［5］、其他變種背包問(wèn)題［6-7］等。其中，0-1KP 是最基礎(chǔ)的背包問(wèn)題。現(xiàn)實(shí)中很多問(wèn)題都被擬合成背包問(wèn)題進(jìn)行研究，如貨物裝載問(wèn)題、資源分配問(wèn)題、電網(wǎng)維護(hù)檢修問(wèn)題、投資決策問(wèn)題等。

窮舉法、動(dòng)態(tài)規(guī)劃法［8］等傳統(tǒng)精確算法能準(zhǔn)確得出背包問(wèn)題的最優(yōu)解，但是隨著物品數(shù)量和背包容量的增加，算法的時(shí)間復(fù)雜度成指數(shù)上升，難以得到最優(yōu)解或需要遠(yuǎn)超期望的時(shí)間才能獲取最優(yōu)解，表現(xiàn)出計(jì)算效率低、對(duì)硬件設(shè)備要求高的特點(diǎn)。因此，傳統(tǒng)精確算法大部分情況下只適合求解小規(guī)模背包問(wèn)題。元啟發(fā)式算法作為近似精確算法，已成為近幾年研究背包問(wèn)題的主流方法。目前，差分進(jìn)化（Differential Evolution，DE）算法［9］、遺傳算法［10］、粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法［11］、狼群算法［12］、獅群算法［13］、鯨魚(yú)優(yōu)化算法［14］都已成功應(yīng)用于優(yōu)化求解背包問(wèn)題。帝國(guó)競(jìng)爭(zhēng)算法（Imperialist Competitive Algorithm，ICA）［15］是基于群體智能的元啟發(fā)式算法，它獨(dú)特的演化原理使算法在前期具有一定的全局勘探能力，在后期具有較強(qiáng)的局部挖掘能力。背包問(wèn)題的求解難度主要在于從次理想解到理想解的過(guò)程，這個(gè)過(guò)程需要不斷在當(dāng)前解的周?chē)臻g作尋優(yōu)嘗試。因此，相較于遺傳算法、DE、PSO 等元啟發(fā)式算法，后期具有較強(qiáng)局部尋優(yōu)能力的ICA 存在一定優(yōu)勢(shì)；也正因?yàn)镮CA獨(dú)特的演化原理，它也容易因過(guò)快收斂而陷入局部最優(yōu)。

本文基于ICA 的不足和KP 的特點(diǎn)，提出求解0-1KP 的二進(jìn)制帝國(guó)競(jìng)爭(zhēng)算法（Binary Imperialist Competitive Algorithm，BICA）。BICA 基于標(biāo)準(zhǔn)ICA，通過(guò)離散化方法成功獲得求解KP 的能力，并引入雙點(diǎn)自變異算子和跳出局部最優(yōu)算法（Jump out of Local Optimum Algorithm，JLOA）增強(qiáng)算法性能，算法在尋優(yōu)過(guò)程產(chǎn)生的新解將通過(guò)改進(jìn)后的修復(fù)優(yōu)化機(jī)制處理。大量實(shí)驗(yàn)表明BICA 在求解0-1KP 時(shí)具有較強(qiáng)的性能，表現(xiàn)為尋優(yōu)精度高、算法穩(wěn)定性好、求解效率高，能作為有效求解大規(guī)模0-1KP 的新方法。此外，本文從典型物流服務(wù)場(chǎng)景中共性抽象出一種新KP 變種-異構(gòu)多背包問(wèn)題（Heterogeneous Multiple Knapsack Problem，HMKP）。為有效處理HMKP，將BICA 種群結(jié)構(gòu)改進(jìn)為一種多級(jí)算法結(jié)構(gòu)，提出求解HMKP 的多級(jí)二進(jìn)制帝國(guó)競(jìng)爭(zhēng)算法（Multiple Level Binary Imperialist Competitive Algorithm，MLB-ICA），相關(guān)算例實(shí)驗(yàn)表明，MLB-ICA 能有效求解HMKP。本文的研究不僅為0-1KP 的求解提供有效的新方法，還嘗試探索了KP 新變種問(wèn)題，且提供了一種針對(duì)性的群集智能算法解決方案。

1 問(wèn)題描述

1.1 0-1背包問(wèn)題描述

0-1KP 可以描述為：有n件物品和一個(gè)容量為C的背包，第（ii={1，2，…，n}）件物品的重量屬性為wi，價(jià)值屬性為pi，從n件物品中選擇部分物品放入背包，使得在背包容量限制下背包內(nèi)所有物品總價(jià)值V最大化。定義物品裝入方案為[x1，x2，…，xi，…，xn](xi={0，1})，xi=1 表示第i件物品放入背包；xi=0 表示第i件物品不放入背包。0-1KP 的數(shù)學(xué)表達(dá)式為：

0-1KP 是典型的基于約束條件的離散最大化問(wèn)題，對(duì)于違反約束條件的物品裝入方案，有罰函數(shù)法［16］和修復(fù)法［17-18］對(duì)不可行方案進(jìn)行可行化處理。罰函數(shù)法和修復(fù)法都有操作簡(jiǎn)單的特點(diǎn)，但懲罰函數(shù)的設(shè)計(jì)卻沒(méi)有統(tǒng)一的標(biāo)準(zhǔn)來(lái)借鑒，怎樣設(shè)計(jì)一個(gè)合理的懲罰函數(shù)仍然是一個(gè)難題。修復(fù)法在現(xiàn)有研究中更常見(jiàn)，分為修復(fù)和修正兩個(gè)操作：修復(fù)操作將不可行解處理為可行解；修正操作在約束條件下對(duì)當(dāng)前方案進(jìn)一步優(yōu)化。修復(fù)法的描述如算法1 所示。

算法1 修復(fù)法。

輸入X，H1，H2，W；

其中：X是待處理解；H1、H2是分別按照價(jià)值密度升序、降序排列的物品索引列表；W是當(dāng)前背包內(nèi)物品總重量；X'是經(jīng)修復(fù)法處理后的可行解［19］。

元啟發(fā)式算法能在可接受時(shí)間內(nèi)求解大規(guī)模0-1KP 問(wèn)題，而這是傳統(tǒng)精確算法的不足。處理0-1KP 的元啟發(fā)式算法可分為兩類(lèi)：第一類(lèi)是以遺傳算法［18］、禁忌搜索算法［20］為代表的可直接通過(guò)0-1 編碼方式求解問(wèn)題的算法；第二類(lèi)是以DE 算法［21］、ICA 為代表的不可直接0-1 編碼的連續(xù)域群集智能算法。第二類(lèi)算法提出于連續(xù)域相關(guān)問(wèn)題的研究中，可借助編碼轉(zhuǎn)換方式將實(shí)數(shù)編碼轉(zhuǎn)換為二進(jìn)制0-1 編碼以求解0-1KP，該過(guò)程不可避免地會(huì)增加算法計(jì)算復(fù)雜度，但連續(xù)域上的搜索空間相對(duì)更精細(xì)，基于種群的連續(xù)域算法有更多機(jī)會(huì)直接找到最優(yōu)理想解。BICA 分別引入兩種已被廣泛使用和被證明有效的編碼轉(zhuǎn)換函數(shù)幫助ICA 間接求解0-1KP，并在后續(xù)實(shí)驗(yàn)中研究了兩種編碼轉(zhuǎn)換函數(shù)對(duì)算法性能的影響。

1.2 多背包問(wèn)題描述

多背包問(wèn)題（Multiple Knapsack Problem，MKP）［22］可描述為：有n件物品和m個(gè)容量屬性為Cj(j=1，2，…，m)的背包，第（ii={1，2，…，n}）件物品的重量屬性為wi，價(jià)值屬性為pi，從n件物品中選擇部分物品放入m個(gè)背包中，在各個(gè)背包容量約束下，使所有背包中的所有物品總價(jià)值V最大化。定義背包內(nèi)物品裝入方案為[x1，x2，…，xi，…，xn] (xi=[xi1，xi2，…，xij，…，xim]，i=1，2，…，n，j=1，2，…，m)，其 中，xij=1 表示第i件物品放入第j個(gè)背包；xij=0 表示第i件物品不放入第j個(gè)背包。MKP 的數(shù)學(xué)表達(dá)式為：

MKP 中物品可選擇的背包不唯一，利用傳統(tǒng)精確算法求解MKP 的計(jì)算復(fù)雜度將成指數(shù)級(jí)增長(zhǎng)，遠(yuǎn)高于求解0-1KP 時(shí)的計(jì)算復(fù)雜度，元啟發(fā)式算法因此成為研究MKP 的首選。元啟發(fā)式算法求解MKP 需確定個(gè)體解的編碼方式，現(xiàn)有研究中常用編碼方式有整數(shù)編碼［23］、m×n階0-1 矩陣編碼［24］，前者因編碼方式簡(jiǎn)單且具有更低計(jì)算復(fù)雜度而更受偏好。

1.3 異構(gòu)多背包問(wèn)題描述

異構(gòu)多背包問(wèn)題（Heterogeneous Multiple Knapsack Problem，HMKP）是多背包問(wèn)題的一種特殊形式，不可以簡(jiǎn)單看作多個(gè)0-1KP 的再組合優(yōu)化問(wèn)題。HMKP 是從離散組合優(yōu)化的角度從多個(gè)典型的物流服務(wù)場(chǎng)景共性抽象而來(lái)，是多個(gè)復(fù)雜物流系統(tǒng)的計(jì)劃調(diào)度問(wèn)題原型。該問(wèn)題的提出和建立，能更好地處理物流行業(yè)中的控制決策問(wèn)題［25］?；趶?fù)雜物流服務(wù)場(chǎng)景，HMKP 的求解架構(gòu)如圖1 所示。

圖1 HMKP的求解架構(gòu)Fig.1 HMKP solution architecture

相較于MKP，HMKP 中部分或全部物品對(duì)待放入的背包有指定要求，它的求解因此更復(fù)雜。作為MKP 特殊形式的HMKP，它的求解算法的編碼方式可選擇整數(shù)編碼或0-1 二進(jìn)制編碼，但是這兩種編碼方式在算法的演化過(guò)程中不可避免地需要限制個(gè)體解編碼串上部分基位的取值，以滿足這部分基位所代表的物品對(duì)分配背包的要求。

MLB-ICA 從算法設(shè)計(jì)上入手，先給所有物品都分配一個(gè)滿足它的需求的背包，接著利用BICA 并行求解各部分的最優(yōu)配置方案，后續(xù)在物品對(duì)背包約束條件下變換各物品被分配的背包，循環(huán)演進(jìn)。

HMKP 可以描述為：有m堆物品，對(duì)應(yīng)每堆物品的數(shù)量分別為{n1，n2，…，nm}，有m個(gè)背包，背包的容量屬性為Cj(j=1，2，…，m)，每堆物品對(duì)應(yīng)一個(gè)背包，且只能選擇放入或者不放入該背包，不能放入其他背包中，第j堆物品中的第i件物品的重量屬性為wji，價(jià)值屬性為pji，從每堆物品中選擇部分物品放入相對(duì)應(yīng)的背包中，使所有背包中的所有物品總價(jià)值V最大化。定義背包內(nèi)物品裝入方案為[x1，x2，…，xj，…，xm] (xj=[xj1，xj2，…，xji，…，xjnj]；xji={0，1}，i=1，2，…，nj；j=1，2，…，m)，xji=1 表示第j堆物品中的第i件物品放入第j個(gè)背包，xji=0 表示第j堆物品中的第i件物品不放入第j個(gè)背包。HMKP 的數(shù)學(xué)表達(dá)式為：

本文描述的HMKP 是一個(gè)基礎(chǔ)原型問(wèn)題，當(dāng)面臨具體實(shí)際問(wèn)題時(shí)，可以允許部分物品有選擇裝入背包的權(quán)利，本文的研究對(duì)于未來(lái)HMKP 的擴(kuò)展有一定的借鑒意義。

2 求解0-1KP的二進(jìn)制帝國(guó)競(jìng)爭(zhēng)算法

在設(shè)計(jì)改進(jìn)算法求解0-1KP 時(shí)，本文充分考慮了問(wèn)題特點(diǎn)和算法的不足，提出了二進(jìn)制帝國(guó)競(jìng)爭(zhēng)算法（BICA）。在算法的運(yùn)行過(guò)程中，修復(fù)優(yōu)化處理機(jī)制將個(gè)體解限制在約束范圍內(nèi)，首先通過(guò)離散化方法的標(biāo)準(zhǔn)ICA 框架對(duì)解空間進(jìn)行初步搜尋，其次依托兩種種群多樣性改進(jìn)機(jī)制進(jìn)一步提高解的質(zhì)量。本章將分別介紹基本ICA、算法中個(gè)體解的編碼表示和修復(fù)優(yōu)化處理、雙點(diǎn)自變異算子和跳出局部極值機(jī)制。

2.1 基本帝國(guó)競(jìng)爭(zhēng)算法

ICA［15］最早于2007 年被提出，是基于帝國(guó)發(fā)展與競(jìng)爭(zhēng)的新型進(jìn)化算法，種群中的個(gè)體稱(chēng)為國(guó)家，大種群被分成若干個(gè)亞種群，這些亞種群稱(chēng)為帝國(guó)，帝國(guó)中表現(xiàn)最好的國(guó)家稱(chēng)為帝國(guó)主義國(guó)家，其他國(guó)家被稱(chēng)為帝國(guó)的附庸殖民地國(guó)家，簡(jiǎn)稱(chēng)殖民地。殖民地在帝國(guó)主義國(guó)家的殖民影響下，在國(guó)家特征上表現(xiàn)為趨同，在算法上表現(xiàn)為空間位置的趨近，該操作為殖民地的同化操作；此外，帝國(guó)間通過(guò)競(jìng)爭(zhēng)最弱帝國(guó)的最弱殖民地實(shí)現(xiàn)不同亞種群間的信息交流。ICA 主要通過(guò)以下操作實(shí)現(xiàn)：初始化帝國(guó)種群操作、殖民地同化操作、交換殖民地與帝國(guó)主義國(guó)家地位操作、帝國(guó)間競(jìng)爭(zhēng)操作、帝國(guó)覆滅操作。目前，ICA 已經(jīng)成功應(yīng)用于工廠調(diào)度、旅行商、供應(yīng)鏈優(yōu)化設(shè)計(jì)、能源傳輸?shù)葘?shí)際問(wèn)題的優(yōu)化中。

2.2 算法中個(gè)體解的編碼表示和修復(fù)優(yōu)化處理

2.2.1 個(gè)體解的編碼表示

BICA 采用二進(jìn)制編碼方法，個(gè)體解由一條n元編碼串X表示，n為該背包問(wèn)題中物品的數(shù)量，編碼串上的每個(gè)基位取值為1 和0 分別表示該基位所指代物品的狀態(tài)為已放入和未放入背包。

絕大多數(shù)元啟發(fā)式算法的設(shè)計(jì)只適合求解連續(xù)實(shí)數(shù)域上的數(shù)值優(yōu)化問(wèn)題，不能直接處理離散域上的組合優(yōu)化問(wèn)題，算法從連續(xù)實(shí)數(shù)域過(guò)渡到離散組合域的方法稱(chēng)為離散化方法（Discretization Method，DM）。本文引入兩種簡(jiǎn)單可行的DM 將實(shí)數(shù)映射為它的等效0-1 變量，這兩種方法分別是離散演化算法（Discrete Evolutionary Algorithm，DisEA）［26］、最佳匹配值（Best-Matched Value，BMV）法［21］。

1）DisEA 離散化方法。

設(shè)ICA 中個(gè)體X的編碼為D維實(shí)數(shù)向量X=(x1，x2，…，xD)（xj∈[-1，1]，j=1，2，…，D），對(duì)應(yīng)組合優(yōu)化問(wèn)題的解Y=[y1，y2，…，yD（]yj∈{0，1}）。

定義映射φDisEA：[-1，1] →{0，1}，則Y=φDisEA(X)滿足：

2）BMV 離散化方法。

設(shè)ICA 中個(gè)體X的編碼為D維實(shí)數(shù)向量X=[x1，x2，…，xD]（xj∈[0，1]，j=1，2，…，D），對(duì)應(yīng)組合優(yōu)化問(wèn)題的 解Y=[y1，y2，…，yD]（yj∈{0，1}），定義映射φBMV：[0，1] →{0，1}。相較于DisEA 以實(shí)數(shù)值0 作為從實(shí)數(shù)域映射到離散域的分界線，BMV 選擇實(shí)數(shù)向量X的算術(shù)平均值A(chǔ)vg作為映射操作中的分界線。則Y=φBMV(X)滿足：

2.2.2 個(gè)體解的修復(fù)優(yōu)化處理

在經(jīng)典修復(fù)法的修復(fù)操作和修正操作之上，本文經(jīng)部分改進(jìn)提出修復(fù)機(jī)制（Operation Repair Mechanism，O-RM）與修正機(jī)制（Operation Correction Mechanism，O-CM）。

O-RM 如算法2 所示，它的輸入端和遍歷條件與經(jīng)典修復(fù)操作不同：經(jīng)典修復(fù)操作輸入的物品索引列表H1為所有物品按價(jià)值密度升序排序所得，且在算法1 的步驟2）中不僅需要判斷W和C的大小，還需判斷當(dāng)前物品的狀態(tài)；而O-RM的輸入端的物品索引列表H3為已放入背包內(nèi)的物品按價(jià)值密度升序排序所得，且不需要進(jìn)一步判斷當(dāng)前物品狀態(tài)。

O-CM 如算法3 所示，它的輸入端、遍歷條件、機(jī)制觸發(fā)條件與經(jīng)典修正操作不同，前兩項(xiàng)與O-RM 優(yōu)勢(shì)分析同理，此外，經(jīng)典修正操作無(wú)觸發(fā)機(jī)制，而O-CM 以C-W>w'作為觸發(fā)條件，當(dāng)列表H2被全部遍歷完后算法結(jié)束。經(jīng)典修復(fù)法中物品索引列表內(nèi)元素個(gè)數(shù)遠(yuǎn)多于改進(jìn)后的修正優(yōu)化機(jī)制，O-CM 設(shè)置的觸發(fā)條件能避免當(dāng)前配置方案下不可能得到進(jìn)一步優(yōu)化卻仍然迫使修正操作無(wú)效運(yùn)行的情況發(fā)生。因此，O-RM 和O-CM 能在一定程度上降低算法修復(fù)和優(yōu)化配置方案的計(jì)算復(fù)雜度。

算法2 修復(fù)機(jī)制（O-RM）。

輸入X，H3，W；

輸出X'。

算法2 中，X是待修復(fù)解；H3是已放入背包內(nèi)的按照價(jià)值密度升序排序的物品索引列表；W是當(dāng)前背包內(nèi)物品總重量；X'是修復(fù)后的可行解。

算法3 修正機(jī)制（O-CM）。

輸入X，H4，W，w'；

輸出X'。

算法3 中，X是待優(yōu)化可行解；H4是未放入背包內(nèi)的按照價(jià)值密度降序排序的物品索引列表；W是當(dāng)前背包內(nèi)物品總重量；w'是背包外物品的最小重量；X'是進(jìn)一步優(yōu)化后的可行解。

2.3 種群多樣性改進(jìn)機(jī)制

ICA 在進(jìn)化進(jìn)程中會(huì)因帝國(guó)走向崩塌造成種群多樣性喪失、亞種群間自主互動(dòng)行為減少，最終導(dǎo)致算法易陷入局部最優(yōu)。面對(duì)ICA 的不足，BICA 以增強(qiáng)種群多樣性為切入點(diǎn)，在殖民地同化操作后，引入了雙點(diǎn)自變異算子和跳出局部最優(yōu)機(jī)制為種群提供額外自進(jìn)化、重組進(jìn)化的機(jī)會(huì)，克服算法缺陷從而提高ICA 求解KP 的能力。

2.3.1 雙點(diǎn)自變異算子

本文設(shè)計(jì)了一種新型局部搜索策略：雙點(diǎn)自變異策略（Two-Point Automutation Strategy，TPAS），原理如圖2 所示。對(duì)于每個(gè)待變異個(gè)體對(duì)應(yīng)的背包配置方案，在已放入背包的物品中隨機(jī)挑選一件物品1，并在未放入背包的物品中隨機(jī)挑選一件物品2，將物品1 拿出背包，物品2 放入背包，隨后將處理后的方案對(duì)應(yīng)的個(gè)體解經(jīng)O-RM、O-CM 處理，并利用貪婪算子保留子代與父代中的較優(yōu)個(gè)體。KP 的最優(yōu)解位于約束邊界附近，TPAS 基于該特征向下以每個(gè)國(guó)家當(dāng)前位置為起始點(diǎn)執(zhí)行全空間解域的局部搜索。

圖2 雙點(diǎn)自變異策略原理Fig.2 Principal of two-point automutation strategy

ICA 中的個(gè)體包括帝國(guó)主義國(guó)家和殖民地兩種角色，本文對(duì)兩種角色進(jìn)行不同設(shè)計(jì)。每個(gè)殖民地都有pro_col=0.5 的概率執(zhí)行TPAS 操作，操作完成即結(jié)束。每個(gè)帝國(guó)主義國(guó)家將循環(huán)TimesTPAS=50 次TPAS 操作，若當(dāng)前對(duì)應(yīng)的個(gè)體解表現(xiàn)變好或達(dá)到最大循環(huán)次數(shù)，操作結(jié)束。

2.3.2 跳出局部最優(yōu)機(jī)制

ICA 在運(yùn)行過(guò)程中種群多樣性不斷降低，導(dǎo)致算法“早收早斂”；此外，殖民地同化機(jī)制和雙點(diǎn)自變異操作都引入了貪婪算子，因此算法有更大概率過(guò)早陷入局部困境。前期工作發(fā)現(xiàn)，當(dāng)算法陷入局部最優(yōu)時(shí)，保留最優(yōu)部分解，重新初始化剩余種群能夠有效逃逸當(dāng)前困境。因此，本文設(shè)計(jì)了一種重新隨機(jī)初始化種群的跳出局部最優(yōu)算法（JLOA），當(dāng)算法只剩下一個(gè)帝國(guó)或者連續(xù)u=20 次最優(yōu)解都未更新時(shí)，保留所有帝國(guó)主義國(guó)家，剩余殖民地將在約束范圍內(nèi)通過(guò)隨機(jī)初始化的方式產(chǎn)生，并初始化帝國(guó)。

綜上所述，常規(guī)凝血檢驗(yàn)項(xiàng)目對(duì)異位妊娠大出血輸血治療不良反應(yīng)監(jiān)測(cè)的應(yīng)用效果可觀，合理應(yīng)用可以減少輸血治療過(guò)程中惡性事件的發(fā)生。

文獻(xiàn)［27］中也設(shè)計(jì)了一種跳出局部最優(yōu)機(jī)制，與本文的觸發(fā)條件類(lèi)似，不同之處在于觸發(fā)后的操作。本文通過(guò)隨機(jī)初始化對(duì)種群進(jìn)行處理，相較于前者的重新分配殖民地，更具隨機(jī)性。JLOA 中的隨機(jī)性表現(xiàn)為兩方面：一方面通過(guò)隨機(jī)初始化的方式初始化所有殖民地；另一方面通過(guò)隨機(jī)分配的方式將所有殖民地分配給帝國(guó)主義國(guó)家從而初始化帝國(guó)，這些隨機(jī)因子的引入能有效擺脫種群個(gè)體在陷入局部最優(yōu)時(shí)小范圍解空間的密集群聚現(xiàn)象。JLOA 在算法可能陷入局部最優(yōu)的節(jié)點(diǎn)被觸發(fā)，通過(guò)大范圍地初始化種群個(gè)體，在平衡算法探索能力和開(kāi)發(fā)能力中扮演了極其重要的角色，保留了種群中最優(yōu)秀的部分個(gè)體，確保前期優(yōu)化過(guò)程的有效性。

2.4 BICA框架

BICA 主要由四部分實(shí)現(xiàn)：1）離散化方法，本文對(duì)引入DisEA 離散化方法的BICA 命名為BICA-DisEA，對(duì)引入BMV離散化方法的BICA 命名為BICA-BMV，兩個(gè)算法除選用的DM 不同，運(yùn)行參數(shù)和運(yùn)行機(jī)制均完全相同；2）本文改進(jìn)的修復(fù)優(yōu)化法O-RM 和O-CM 對(duì)個(gè)體解編碼更新后的子代實(shí)現(xiàn)檢驗(yàn)、修復(fù)、優(yōu)化三流程；3）標(biāo)準(zhǔn)ICA 框架，利用尋優(yōu)原理中的同化策略、帝國(guó)間競(jìng)爭(zhēng)策略推動(dòng)算法實(shí)現(xiàn)對(duì)空間解的勘探和開(kāi)發(fā)；4）本文提出的兩種新型改進(jìn)機(jī)制，一方面執(zhí)行雙點(diǎn)自變異策略幫助種群個(gè)體實(shí)現(xiàn)對(duì)自身周?chē)臻g的精細(xì)搜索，另一方面利用跳出JLOA 給算法在較可能陷入局部最優(yōu)解的兩個(gè)節(jié)點(diǎn)上提供逃逸通道。以達(dá)到算法的最大迭代次數(shù)（FEsmax）作為終止運(yùn)行的唯一條件，BICA 的描述如下。

算法4 二進(jìn)制帝國(guó)競(jìng)爭(zhēng)算法（BICA）。

輸入cou_num，imp_num，n，F(xiàn)Esmax，cimp_num；

輸出 Best results。

其中：cou_num是種群中國(guó)家的總數(shù)量；imp_num是帝國(guó)主義國(guó)家的最大數(shù)量；n是KP 中物品的總數(shù)量；cimp_num是當(dāng)前算法狀態(tài)下帝國(guó)主義國(guó)家的數(shù)量；FEsmax是算法的最大迭代次數(shù)；FEs是算法當(dāng)前迭代次數(shù)。

3 求解HMKP的多級(jí)二進(jìn)制帝國(guó)競(jìng)爭(zhēng)算法

HMKP 作為特殊的組合優(yōu)化問(wèn)題，求解過(guò)程中算法需要同時(shí)處理多約束條件下的多個(gè)背包的物品狀態(tài)。因此算法設(shè)計(jì)難度較大，但I(xiàn)CA 具有多種群的特點(diǎn)，所以能處理HMKP。本文將ICA 種群結(jié)構(gòu)設(shè)計(jì)成一種多級(jí)種群結(jié)構(gòu)，并將BICA 中的改進(jìn)機(jī)制融入多級(jí)二進(jìn)制帝國(guó)競(jìng)爭(zhēng)算法結(jié)構(gòu)中，提出一種多級(jí)二進(jìn)制帝國(guó)競(jìng)爭(zhēng)算法（MLB-ICA）。

3.1 多級(jí)二進(jìn)制帝國(guó)競(jìng)爭(zhēng)算法結(jié)構(gòu)

定義ICA 中種群的地位為等級(jí)，則ICA 擁有帝國(guó)和國(guó)家兩個(gè)等級(jí)，稱(chēng)為二級(jí)結(jié)構(gòu)。帝國(guó)為結(jié)構(gòu)中的第一等級(jí)，國(guó)家為結(jié)構(gòu)中的第二等級(jí)。MLB-ICA 在帝國(guó)等級(jí)之下，增設(shè)了王國(guó)等級(jí)，王國(guó)中勢(shì)力最強(qiáng)的國(guó)家不再是帝國(guó)主義國(guó)家，而是聯(lián)盟國(guó)，王國(guó)中除聯(lián)盟國(guó)之外的國(guó)家都為聯(lián)盟國(guó)的殖民地，多級(jí)結(jié)構(gòu)中帝國(guó)為第一等級(jí)，王國(guó)為第二等級(jí)，國(guó)家為第三等級(jí)?；綢CA 和MLB-ICA 的種群結(jié)構(gòu)如圖3 所示。

圖3 ICA與MLB-ICA的種群結(jié)構(gòu)Fig.3 Population structures of ICA and MLB-ICA

圖3（a）展示的MLB-ICA 種群結(jié)構(gòu)對(duì)應(yīng)的是3 個(gè)背包的HMKP，帝國(guó)中王國(guó)的個(gè)數(shù)對(duì)應(yīng)HMKP 中背包的個(gè)數(shù)，帝國(guó)中每一個(gè)王國(guó)都對(duì)應(yīng)處理1 個(gè)簡(jiǎn)單KP。種群中帝國(guó)的個(gè)數(shù)為e，當(dāng)HMKP 中每個(gè)背包最優(yōu)值Optimumi已知時(shí)，定義最優(yōu)值與算法所求得當(dāng)前背包內(nèi)物品總價(jià)值Vij之差為gapij（i=1，2，…，e；j=1，2，…，m），所有背包的gap值之和定義為GAP，則HMKP 的數(shù)學(xué)模型可以轉(zhuǎn)換為：

1）交換殖民地與帝國(guó)主義國(guó)家地位操作的重新設(shè)計(jì)。多級(jí)ICA 結(jié)構(gòu)中，已不存在帝國(guó)主義國(guó)家，取而代之的是聯(lián)盟國(guó)，當(dāng)王國(guó)中存在某個(gè)殖民地表現(xiàn)比當(dāng)前王國(guó)中的聯(lián)盟國(guó)更優(yōu)時(shí)，該殖民地成為新的聯(lián)盟國(guó)，原聯(lián)盟國(guó)下放為王國(guó)的殖民地。至此，完成交換殖民地與聯(lián)盟國(guó)地位操作。

2）帝國(guó)間競(jìng)爭(zhēng)最弱帝國(guó)中的最弱殖民地操作的重新設(shè)計(jì)。不同王國(guó)中的殖民地個(gè)數(shù)在多級(jí)ICA 結(jié)構(gòu)中保持不變，所以帝國(guó)競(jìng)爭(zhēng)操作難以實(shí)行。但對(duì)ICA 來(lái)說(shuō)，帝國(guó)競(jìng)爭(zhēng)操作必不可少，沒(méi)有帝國(guó)競(jìng)爭(zhēng)，帝國(guó)間就不能進(jìn)行有效信息交流。在MLB-ICA 中，設(shè)計(jì)了最強(qiáng)聯(lián)盟國(guó)的游走操作實(shí)現(xiàn)王國(guó)間的有效信息交流。處理同一背包的不同帝國(guó)的聯(lián)盟國(guó)中，gap值最小的聯(lián)盟國(guó)作為最強(qiáng)聯(lián)盟國(guó)，最強(qiáng)聯(lián)盟國(guó)在處理同一背包的不同帝國(guó)的王國(guó)中游走，將優(yōu)質(zhì)信息在不同帝國(guó)間擴(kuò)散。最強(qiáng)聯(lián)盟國(guó)的游走操作使殖民地有機(jī)會(huì)向來(lái)自其他帝國(guó)表現(xiàn)最好的聯(lián)盟國(guó)學(xué)習(xí)，并且最強(qiáng)聯(lián)盟國(guó)的去處按帝國(guó)GAP值的大小通過(guò)輪盤(pán)賭的方式?jīng)Q定，因此表現(xiàn)最好的聯(lián)盟國(guó)也有機(jī)會(huì)去到表現(xiàn)較差的帝國(guó)中從而改進(jìn)當(dāng)前亞種群質(zhì)量，為殖民地的搜索提供更多指導(dǎo)，進(jìn)一步提高種群多樣性。

3.2 MLB-ICA框架

MLB-ICA 是在經(jīng)典ICA 結(jié)構(gòu)的基礎(chǔ)上，融入BICA 中的雙點(diǎn)自變異算子和跳出局部最優(yōu)策略提出的改進(jìn)算法。MLB-ICA 以達(dá)到最大迭代次數(shù)（FEsmax）作為算法終止運(yùn)行的唯一條件，它的描述如算法5 所示。

算法5 多級(jí)二進(jìn)制帝國(guó)競(jìng)爭(zhēng)算法（MLB-ICA）。

輸入cou_num，e，m，F(xiàn)Esmax；

輸出 Best results。

其中：cou_num是種群中國(guó)家的總數(shù)；e是帝國(guó)數(shù)；m是背包個(gè)數(shù)，也代表帝國(guó)中王國(guó)的數(shù)量；FEsmax是算法的最大迭代次數(shù)；FEs是算法當(dāng)前迭代次數(shù)。

圖4 描述了帝國(guó)數(shù)量設(shè)置為8，求解3 個(gè)背包組合HMKP條件下MLB-ICA 的算法框架?？梢钥闯?，MLB-ICA 依托于BICA 并行求解HMKP，在帝國(guó)間信息交互環(huán)境中綜合考慮所有背包內(nèi)物品的總價(jià)值并評(píng)價(jià)算法求解得出較優(yōu)方案，最終輸出最優(yōu)HMKP 方案。從尋優(yōu)結(jié)果來(lái)看，HMKP 并非簡(jiǎn)單地分割出多個(gè)0-1KP 并讓BICA 分別求解最優(yōu)解，MLB-ICA追求的是整體最優(yōu)，這是多組合多約束的KP 求解方案。

圖4 MLB-ICA的算法框架Fig.4 Algorithm framework of MLB-ICA

3.3 算法的特性分析

3.3.1 算法的平衡改進(jìn)機(jī)制

導(dǎo)致ICA 全局尋優(yōu)能力不足，易陷入局部最優(yōu)的主要原因是帝國(guó)間缺少有效的信息交流，種群多樣性水平受限。本文提出的兩種改進(jìn)機(jī)制以提高種群多樣性為目的，TPAS 引導(dǎo)每個(gè)殖民地和帝國(guó)主義國(guó)家（聯(lián)盟國(guó)）通過(guò)對(duì)編碼串上兩個(gè)基位的翻轉(zhuǎn)對(duì)自身周?chē)慕饪臻g不斷局部開(kāi)發(fā)；JLOA 克服算法自身不足和貪婪策略的副作用，隨機(jī)初始化所有的殖民地。在改進(jìn)算法的邏輯框架中，機(jī)制間合理分配任務(wù)，同化策略與TPAS 強(qiáng)化了算法的局部尋優(yōu)能力，JLOA 不斷讓個(gè)體分散于尋優(yōu)空間的所有角落來(lái)為算法提供強(qiáng)勁的全局搜索能力。理論上可以證明改進(jìn)算法相對(duì)標(biāo)準(zhǔn)ICA，開(kāi)發(fā)和勘探能力都得到了較大程度的增強(qiáng)，并且全局探索和局部搜索二者之間能夠得到合理的互補(bǔ)和平衡。

3.3.2 算法的時(shí)間復(fù)雜度分析

計(jì)算成本是衡量算法有效性的關(guān)鍵指標(biāo)，算法的時(shí)間復(fù)雜度是其中最常用的指標(biāo)。假定國(guó)家總數(shù)為a，其中帝國(guó)主義國(guó)家（聯(lián)盟國(guó)）數(shù)為a1，殖民地?cái)?shù)為a2，則BICA 和MLB-ICA兩個(gè)算法在求解物品數(shù)量為n、背包個(gè)數(shù)為m的背包問(wèn)題時(shí)單次迭代的最大時(shí)間復(fù)雜度分別為O((8a+9)n)、O((8a+9)n)，略大于標(biāo)準(zhǔn)ICA 的O(2an)。

表1 為先進(jìn)元啟發(fā)式算法：離散正弦余弦算法（Discrete Sine Cosine Algorithm，DSCA）19］、混合貪婪遺傳算法（Hybrid Greedy Genetic Algorithm，HGGA）［18］、基于反向?qū)W習(xí)的高斯擾動(dòng)帝王蝶優(yōu)化（Opposition-based learning Monarch Butterfly Optimization with Gaussian perturbation，OMBO）［28］與BICA 求解0-1KP 時(shí)的單次迭代最大時(shí)間復(fù)雜度對(duì)比。后續(xù)章節(jié)能通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)BICA 尋優(yōu)效率高，較少次的迭代后就能找到次理想解或理想解。雖然BICA 在單次迭代時(shí)間復(fù)雜度上不占優(yōu)勢(shì)，但是它能以較高效率求解高復(fù)雜度問(wèn)題。值得注意的是，BICA 和MLB-ICA 的最大時(shí)間復(fù)雜度相同，說(shuō)明MLBICA 的結(jié)構(gòu)并未在本質(zhì)上提高算法的計(jì)算成本，所以它的結(jié)構(gòu)的設(shè)計(jì)在理論上很合理。從分析結(jié)果看，MLB-ICA 的時(shí)間復(fù)雜度與背包個(gè)數(shù)m無(wú)明顯的直接關(guān)系，與KP 中物品的總數(shù)量n呈典型的線性關(guān)系，所以算法具有很強(qiáng)的適應(yīng)性和可行性，這對(duì)于MLB-ICA 在物流服務(wù)場(chǎng)景中的應(yīng)用至關(guān)重要。

表1 不同算法的單次迭代最大時(shí)間復(fù)雜度對(duì)比Tab.1 Comparison of maximum time complexity of different algorithms for a single iteration

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

本章通過(guò)仿真實(shí)驗(yàn)的方法實(shí)現(xiàn)以下4 個(gè)目標(biāo)：1）驗(yàn)證BICA 的性能；2）驗(yàn)證本文的改進(jìn)機(jī)制的有效性；3）分析BICA 中部分關(guān)鍵參數(shù)選擇的合理性和算法的有效性；4）驗(yàn)證MLB-ICA 能夠有效求解HMKP 并有較好的性能。引入2個(gè)測(cè)試集分別進(jìn)行仿真實(shí)驗(yàn)。

測(cè)試集1［21］是一個(gè)中等規(guī)模算例集，根據(jù)問(wèn)題特征中物品重量屬性與價(jià)值屬性之間的關(guān)系，算例被分成無(wú)相關(guān)、弱相關(guān)、強(qiáng)相關(guān)、完全相關(guān)4 類(lèi)。每類(lèi)包括5 個(gè)算例，算例中物品的數(shù)量分別為100、200、300、500、1 000。所以測(cè)試集1 共有20 個(gè)算例，分別命名為KP01～KP20。

測(cè)試集2［29］是一個(gè)大規(guī)模算例集，根據(jù)問(wèn)題特征中物品的重量屬性與價(jià)值屬性之間的關(guān)系，算例被分成無(wú)相關(guān)、弱相關(guān)、強(qiáng)相關(guān)3 類(lèi)。每類(lèi)包括5 個(gè)算例，算例中物品的數(shù)量分別為800、1 000、1 200、1 500、2 000。所以測(cè)試集2 共有15 個(gè)算例，分別命名為KP21～KP35。

算法以達(dá)到最大迭代次數(shù)（FEsmax）作為終止運(yùn)行的唯一條件，運(yùn)行參數(shù)如表2 所示。每次實(shí)驗(yàn)算法連續(xù)獨(dú)立運(yùn)行次數(shù)Times=50。所有實(shí)驗(yàn)均 在 PyCharm 2021.2.3（Professional Edition）集成環(huán)境中編寫(xiě)與測(cè)試，運(yùn)行環(huán)境為Intel Core i5-10400 CPU @ 2.90 GHz、32 GB 內(nèi) 存、64 位Windows 10 操作系統(tǒng)，編程語(yǔ)言采用PyThon3.9。

表2 算法運(yùn)行參數(shù)Tab.2 Parameters of algorithms

算法運(yùn)行參數(shù)中，θ值是經(jīng)典固定值；imp_num(m)、col_num、pro_col、TimeTPAS和u這5 個(gè)參數(shù)的選取通過(guò)前期實(shí)驗(yàn)確定，借鑒文獻(xiàn)［30］中對(duì)算法參數(shù)分析的方法，本文將在4.4 節(jié)深入分析上述5 個(gè)參數(shù)對(duì)算法的影響。

4.1 BICA在中等規(guī)模算例集上的表現(xiàn)與比較

首先，選用中等規(guī)模測(cè)試集1 測(cè)試BICA 的性能，算法最大迭代次數(shù)FEsmax=2 000，選取算法運(yùn)行次數(shù)Times=50 的最優(yōu)解、均值解、算法取得最優(yōu)解時(shí)的當(dāng)前迭代次數(shù)的平均值（簡(jiǎn)稱(chēng)為迭代次數(shù)）、取得理想值的成功率（簡(jiǎn)稱(chēng)為成功率）建立評(píng)價(jià)算法性能的指標(biāo)體系。從測(cè)試結(jié)果來(lái)看，BICADisEA 和BICA-BMV 在測(cè)試集1 的20 個(gè)算例上都能找到最優(yōu)理想值，且20 個(gè)算例中有19 個(gè)算例都能被100%找到最優(yōu)理想值，僅在KP03 這個(gè)算例上，兩個(gè)算法都未能在每次求解中找到理想值，但成功率非常高，分別為88%和92%。BICADisEA 和BICA-BMV 在20 個(gè)算例上的迭代次數(shù)分別為18.33和14.41，尤其是完全相關(guān)算例和弱相關(guān)算例的迭代次數(shù)大都接近0，說(shuō)明兩個(gè)算法在測(cè)試集1 的算例上求解效率較高。

引入采用同樣在測(cè)試集進(jìn)行實(shí)驗(yàn)的二元學(xué)習(xí)差分進(jìn)化（Binary Learning Differential Evolution，BLDE）［31］、二分二元差分進(jìn)化（Dichotomous Binary Differential Evolution，DBDE）［32］、新型二元差分進(jìn)化（Novel binary Differential Evolution，Nbin-DE）［21］與BICA-DisEA 和BICA-BMV 進(jìn)行橫向?qū)Ρ?，選取均值解作為評(píng)價(jià)算法性能的指標(biāo)，測(cè)試結(jié)果如表3 所示，同等算例中表現(xiàn)最好的結(jié)果加粗表示。由于BICA-DisEA 和BICABMV 測(cè)試結(jié)果的均值解相同，所以在表3 中直接用BICA 代表兩個(gè)算法。

表3 BICA與其他3個(gè)元啟發(fā)式算法在測(cè)試集1上的測(cè)試結(jié)果比較Tab.3 Comparison of test results of BICA and other three meta-heuristic algorithms on test set 1

可以看出，4 個(gè)算法中，只有Nbin-DE、BICA-DisEA 和BICA-BMV 能完全獲得所有算例的理想值；完全相關(guān)算例的求解難度是0-1KP 中最小的。為了解BICA 與其他3 個(gè)元啟發(fā)式算法之間的差異性，應(yīng)用非參數(shù)Wilcoxon 秩和檢驗(yàn)在置信水平α=0.05 的條件下進(jìn)行測(cè)試，結(jié)果如表4 所示。

表4 基于BICA和3個(gè)對(duì)比算法表現(xiàn)的非參數(shù)Wilcoxon秩和檢驗(yàn)測(cè)試結(jié)果Tab.4 Results of non-parametric Wilcoxon rank sum test based on performance of BICA and three comparison algorithms

可以看出，在求解中等規(guī)模測(cè)試集1 時(shí)，BICA 與BLDE的性能具有顯著差異性，與DBDE 間的性能差異不明顯。

4.2 BICA在大規(guī)模算例集上的表現(xiàn)與比較

為了進(jìn)一步驗(yàn)證BICA 的性能，在大規(guī)模測(cè)試集2 上進(jìn)行測(cè)試，算法最大迭代次數(shù)FEsmax=5 000，結(jié)果如表5 所示。

表5 BICA在測(cè)試集2上的測(cè)試結(jié)果Tab.5 Test results of BICA on test set 2

從表5 可以看出，BICA-DisEA 和BICA-BMV 在測(cè)試集2的15 個(gè)算例上除了KP32 外都能找到理想最優(yōu)值，但求解KP32 的結(jié)果非常接近理想最優(yōu)值。其中，BICA-DisEA 有4個(gè)算例能100%找到理想最優(yōu)值，BICA-BMV 有12 個(gè)算例能100%找到理想最優(yōu)值。通過(guò)最差解、均值解指標(biāo)能看出，兩個(gè)算法在未能100%找到理想最優(yōu)解的算例上的測(cè)試結(jié)果非常接近理想值。從表5 也能很容易驗(yàn)證BMV 離散化方法對(duì)于ICA 求解KP 問(wèn)題更有效；同時(shí)，從迭代次數(shù)指標(biāo)來(lái)看，BMV 相較于DisEA，前者應(yīng)用于ICA 的離散化操作求解KP會(huì)更加地高效，因?yàn)锽ICA-BMV 在15 個(gè)算例的平均迭代次數(shù)為121.02，小于BICA-DisEA 的794.30。

將具有較強(qiáng)求解KP 性能的混沌帝王蝶優(yōu)化（Chaotic Monarch Butterfly Optimization，CMBO）［33］、OMBO［28］、融合全局勢(shì)力更新算子的帝王蝶優(yōu)化（Monarch Butterfly Optimization with Global position updating operator，GMBO）［34］、融合混合貪婪修復(fù)算子的噪聲方法（Noising Methods with hybrid greedy repair operator，NM）［35］、HGGA［18］與本文的兩個(gè)BICA 進(jìn)行橫向比較。表6 給出了7 個(gè)算法在測(cè)試集2 上的測(cè)試結(jié)果平均排名，平均排名指標(biāo)參考了最優(yōu)解、最差解、均值解、標(biāo)準(zhǔn)差4 個(gè)評(píng)價(jià)指標(biāo)，能較全面地反映算法間的相對(duì)性能強(qiáng)弱。

表6 對(duì)比算法在大規(guī)模算例上的平均排名Tab.6 Average ranking of comparison algorithms on large-scale numerical examples

如表6 所示，在大規(guī)模無(wú)相關(guān)算例的測(cè)試結(jié)果中，BICABMV、BICA-DisEA、HGGA、NM 這4 個(gè)算法表現(xiàn)最好。而從表5 中本文提出的兩種算法性能表現(xiàn)可以看出：BICA-BMV的最優(yōu)解、最差解、均值解都取得了最優(yōu)；BICA-DisEA 雖然也能找到5 個(gè)算例的理想最優(yōu)解，但測(cè)試結(jié)果卻有欠穩(wěn)定。

如表5～6 所示，在大規(guī)模弱相關(guān)算例的測(cè)試結(jié)果中，除了GMBO，其他算法都有非常好的表現(xiàn)，BICA-BMV 的表現(xiàn)最優(yōu)，且僅在算例KP29 上未找到最優(yōu)解。

如表5～6 所示，在大規(guī)模強(qiáng)相關(guān)算例上，NM 和HGGA 的表現(xiàn)最優(yōu)，BICA-BMV 僅在算例KP32 未取得理想最優(yōu)解；相較于BICA-BMV，BICA-DisEA 表現(xiàn)相對(duì)較弱，且性能不穩(wěn)定。

綜上所述，7 個(gè)算法中BICA-BMV 的性能整體最優(yōu)，在所有類(lèi)型問(wèn)題的測(cè)試結(jié)果上都具有很高的精度和穩(wěn)定性。應(yīng)用非參數(shù)Wilcoxon 秩和檢驗(yàn)在置信水平α=0.05 的條件下比較BICA-BMV、BICA-DisEA 和5 個(gè)先進(jìn)對(duì)比算法之間差異的顯著性，顯著性p 值如表7 所示。BICA-BMV 與CMBO、GMBO 之間存在顯著性差異，與OMBO、HGGA、NM 之間不存在顯著性差異；BICA-DisEA 與GMBO 之間存在顯著性差異，與其他4 個(gè)對(duì)比算法之間不存在顯著性差異。此外，BICABMV 和BICA-DisEA 之間p 值為0.426，說(shuō)明兩者之間不存在顯著性差異。

表7 基于BICA和5個(gè)對(duì)比算法表現(xiàn)的非參數(shù)Wilcoxon秩和檢驗(yàn)測(cè)試結(jié)果Tab.7 Results of non-parametric Wilcoxon rank sum test based on performance of BICA and 5 comparison algorithms

BICA-BMV 和HGGA 是7 個(gè)算法中表現(xiàn)最優(yōu)異的兩個(gè)算法，兩者之間性能差異不明顯，表8 展示了兩者在都能100%得到理想最優(yōu)解的9 個(gè)算例時(shí)的迭代次數(shù)，能直接反映算法的尋優(yōu)效率?？梢钥闯?，HGGA 在所有算例的迭代次數(shù)都遠(yuǎn)大于BICA-BMV，說(shuō)明BICA-BMV 的尋優(yōu)效率更高，并且在求解大規(guī)模強(qiáng)相關(guān)算例時(shí)該優(yōu)勢(shì)更加明顯。

表8 HGGA和BICA-BMV的迭代次數(shù)對(duì)比Tab.8 Comparison of ierations between HGGA and BICA-BMV

實(shí)驗(yàn)結(jié)果表明BICA-BMV 的性能優(yōu)于BICA-DisEA，而B(niǎo)ICA-BMV 和BICA-DisEA 之間只有DM 不同，其他參數(shù)和機(jī)制都保持一致，進(jìn)一步表明BMV 對(duì)于ICA 離散化求解KP 更有效。DisEA 最初提出于粒子群優(yōu)化（PSO）離散化求解經(jīng)典折扣背包問(wèn)題［26］，BMV 最初提出于差分進(jìn)化（DE）算法離散化求解0-1KP［21］，這兩個(gè)DM 都適用于本文研究的算法，而ICA 和PSO、DE 有很多本質(zhì)上的相同之處，都是連續(xù)域上的群集智能算法，所以引入DisEA 和BMV 對(duì)ICA 來(lái)說(shuō)較合理。對(duì)于BICA 中代表個(gè)體解的實(shí)數(shù)向量X，DisEA 以0 作為映射操作的分界線，BMV 以實(shí)數(shù)向量X的算術(shù)平均值A(chǔ)vg作為映射操作中的分界線，前者是固定分界線，后者是動(dòng)態(tài)分界線，這也是BICA-BMV 性能優(yōu)于BICA-DisEA 的根本原因。對(duì)于基于ICA 的改進(jìn)算法，種群Partitioning 和Clustering 行為具有動(dòng)態(tài)自主交互特性。在實(shí)數(shù)向量映射為離散向量過(guò)程中，BMV 不影響算法的任何行為，但TPAS 需要個(gè)體解從離散向量反向映射為連續(xù)向量，這個(gè)過(guò)程BMV 將通過(guò)Avg值的動(dòng)態(tài)變化直接引導(dǎo)Partitioning 和Clustering 的交互，從實(shí)驗(yàn)結(jié)果來(lái)看，BMV 給BICA 的尋優(yōu)帶來(lái)較多的正反饋。DisEA 和BMV在ICA 上的應(yīng)用拓寬了它們?cè)谒惴ㄉ系膽?yīng)用，驗(yàn)證了兩者的適用性。至少在ICA 上，DisEA 和BMV 對(duì)于群智能算法應(yīng)用于求解離散化問(wèn)題是有效的手段。

4.3 改進(jìn)策略的有效性驗(yàn)證

本節(jié)將通過(guò)消融實(shí)驗(yàn)分析各改進(jìn)策略的有效性。僅以BICA-BMV 作為研究對(duì)象并直接命名為BICA；對(duì)引入BMV離散化方法的基礎(chǔ)ICA 命名為ICA；對(duì)僅引入TPAS 改進(jìn)策略的算法命名為BICA-A；對(duì)僅引入JLOA 改進(jìn)策略的算法命名為BICA-B。表9 給出了它們求解算例KP03、KP21～25 和KP29 的測(cè)試結(jié)果，測(cè)試算例中包括前期實(shí)驗(yàn)未能完全取得理想解的算例，以及求解難度較大的無(wú)相關(guān)算例。

表9 ICA、BICA-A、BICA-B和BICA的測(cè)試結(jié)果Tab.9 Test results of ICA，BICA-A，BICA-B and BICA

從表9 能夠發(fā)現(xiàn)，BICA 的測(cè)試結(jié)果優(yōu)于其他算法。BICA-A、BICA-B 的測(cè)試結(jié)果優(yōu)于ICA，說(shuō)明TPAS 和JLOA 兩個(gè)改進(jìn)策略均能有效提高ICA 的性能。同時(shí)，在TPAS 和JLOA 的共同作用下，ICA 的性能得到了進(jìn)一步提高。圖5 展示了4 個(gè)算法在相同隨機(jī)數(shù)種子下求解算例KP03 和KP21時(shí)收斂曲線?？梢钥闯?，4 個(gè)算法的收斂能力都較強(qiáng)，但BICA 最優(yōu)，能在陷入局部最優(yōu)時(shí)更快逃逸出來(lái)，當(dāng)TPAS 未能發(fā)揮作用時(shí)，JLOA 能給BICA 進(jìn)一步進(jìn)化的動(dòng)力。

圖5 ICA、BICA-A、BICA-B和BICA的收斂曲線Fig.5 Convergence curves of ICA，BICA-A，BICA-B and BICA

4.4 算法關(guān)鍵參數(shù)分析

imp_num(m)、col_num、pro_col、TimeTPAS和u對(duì)算法演化過(guò)程都會(huì)產(chǎn)生較大的影響，5 個(gè)關(guān)鍵參數(shù)可以分為3 組：第1組是國(guó)家數(shù)量配置參數(shù)；第2 組是局部搜索深度參數(shù)；第3 組是多級(jí)搜索步長(zhǎng)參數(shù)。下面將分別選取上文中的部分算例對(duì)這3 組參數(shù)進(jìn)行具體分析，因ML-BICA 是基于BMV 離散化方法構(gòu)建的，所以本節(jié)只討論關(guān)鍵參數(shù)對(duì)BICA-BMV 性能的影響。

4.4.1 國(guó)家數(shù)量配置參數(shù)分析

ICA 是一個(gè)基于多種群的算法，Partitioning 和Clustering是它的核心運(yùn)作原理之一，帝國(guó)主義國(guó)家（王國(guó)）的最大數(shù)量在很大程度上代表Partitioning 的水平，而帝國(guó)主義國(guó)家與殖民地?cái)?shù)量的比值能代表Clustering 的水平［27］。當(dāng)Partitioning和Clustering 之間處于一個(gè)相對(duì)平衡的狀態(tài)時(shí)，算法的性能會(huì)被最大化激發(fā)。圖6 展示了BICA-BMV 在不同帝國(guó)主義國(guó)家和殖民地?cái)?shù)量配置下求解KP03 和KP21 的成功率。為簡(jiǎn)化描述，imp_num(m)用a1替代，col_num用a2替代。

可以看出，a1和a2∶a1的增大都能提高算例的成功率；但當(dāng)a1>8 且a2∶a1>9 時(shí)，該趨勢(shì)不再明顯，甚至出現(xiàn)成功率下降的情況。分析結(jié)果來(lái)看，BICA-BMV 的兩個(gè)運(yùn)行參數(shù)a1和a2∶a1分別設(shè)置為8 和9 比較合理。

4.4.2 局部搜索深度參數(shù)分析

TPAS 能幫助算法從基層種群層面進(jìn)一步精細(xì)搜索較優(yōu)解，pro_col和TimeTPAS決定了局部搜索的深度。帝國(guó)主義國(guó)家在空間解的搜索中具有關(guān)鍵作用［36］，而TPAS 對(duì)帝國(guó)主義國(guó)家執(zhí)行操作的設(shè)計(jì)使它在局部搜索中的關(guān)鍵作用更加明顯。本節(jié)僅討論TimeTPAS的選取對(duì)BICA-BMV 性能的影響，pro_col選取了一個(gè)適中的值，設(shè)置為0.5。圖7 展示了BICABMV 在不同TimeTPAS取值下KP03、KP21 和KP29 的成功率。

圖7 BICA-BMV在KP03、KP21和KP29上的局部搜索深度參數(shù)分析Fig.7 Local search depth parameter analysis of BICA-BMV on KP03，KP21 and KP29

從圖7 可以看出，隨著TimeTPAS增加，算法的求解成功率也在提高。4 組取值中，TimeTPAS=50，75 的綜合表現(xiàn)最好。理論情況下，無(wú)限地增大TimeTPAS值，算法能夠達(dá)到最優(yōu)性能，但是算法計(jì)算復(fù)雜度會(huì)因此線性增加。據(jù)實(shí)驗(yàn)統(tǒng)計(jì)，TimeTPAS=75 的求解時(shí)間會(huì)比TimeTPAS=50 的求解時(shí)間至少增加30 個(gè)百分點(diǎn)。綜合考慮，TimeTPAS=50 在4 組取值中相對(duì)更優(yōu)，可以認(rèn)為T(mén)imeTPAS值的設(shè)置很合理。

4.4.3 多級(jí)搜索步長(zhǎng)參數(shù)

雖然JLOA 有兩個(gè)觸發(fā)條件，但算法更容易因?yàn)檫B續(xù)最優(yōu)解未更新的次數(shù)達(dá)到設(shè)定閾值u而觸發(fā)JLOA。當(dāng)BICABMV 正常進(jìn)化時(shí)，帝國(guó)的數(shù)量會(huì)隨著迭代次數(shù)的增加而減小，減小的過(guò)程也是算法多極化搜索水平下降的過(guò)程，所以本文把參數(shù)u值也稱(chēng)為多級(jí)搜索步長(zhǎng)參數(shù)。u越小，算法越容易因?yàn)橛|發(fā)JLOA 而重新初始化種群，帝國(guó)的數(shù)量因此越快恢復(fù)為初始值。隨著基本ICA 的迭代，帝國(guó)數(shù)量最終必然歸為一。BICA-BMV 迭代過(guò)程中帝國(guó)數(shù)量變化表現(xiàn)為不規(guī)則振蕩，振蕩幅度與u值直接相關(guān)。為了更形象展示這個(gè)過(guò)程，收集BICA-BMV 在u取值為｛20，40，60，80，100｝，求解KP03 時(shí)帝國(guó)數(shù)隨迭代次數(shù)變化的數(shù)據(jù)，如圖8 所示。可以看出，u值越大，帝國(guó)數(shù)量變化振蕩幅度越大。

圖8 不同u值條件下帝國(guó)數(shù)量的變化Fig.8 Change of empire number under different u values

為了比較u值對(duì)算法的影響，選用未能完全取得理想解的算例KP03、KP21、KP29、KP32 進(jìn)行對(duì)比，測(cè)試結(jié)果如表10所示。從圖8 和表10 可以看出，增大u，雖然帝國(guó)數(shù)量波動(dòng)范圍會(huì)變大，但測(cè)試結(jié)果并沒(méi)有明顯提高，甚至在大部分算例上出現(xiàn)結(jié)果變差的情況?？紤]到ICA 收斂較快，一個(gè)相對(duì)較小的u值將引導(dǎo)算法在少量迭代后就觸發(fā)JLOA，避免過(guò)早陷入局部最優(yōu)。但并不是u越小越好，本文發(fā)現(xiàn)u=20 剛好能讓算法在帝國(guó)數(shù)上有變化。從表10 也能發(fā)現(xiàn)，u=20時(shí)算法表現(xiàn)較優(yōu)。因此，帝國(guó)數(shù)量不是最終歸一最佳，多極發(fā)展對(duì)ICA 也是不錯(cuò)的選擇，所以將u值設(shè)置為20。

表10 BICA在不同u值條件下的測(cè)試結(jié)果Tab.10 Test results of BICA-BMV under different u values

4.5 種群進(jìn)化分析

多極發(fā)展是BICA 尋優(yōu)性能的保證，但這并不代表Partitioning 和Clustering 水平的下降，因?yàn)锽ICA 的種群仍然在迭代進(jìn)程中不斷地實(shí)現(xiàn)分區(qū)、初始化、重組?；贗CA 尋優(yōu)原理和改進(jìn)策略TPAS、JLOA，Partitioning 和Clustering 的交互會(huì)更頻繁和持續(xù)，算法也不斷向更優(yōu)的方向進(jìn)化。進(jìn)化是一個(gè)全種群變優(yōu)的過(guò)程，可以把種群進(jìn)化看成是帝國(guó)主義國(guó)家和殖民地交換地位次數(shù)變多的過(guò)程。殖民地因?yàn)楸憩F(xiàn)比它所在帝國(guó)的帝國(guó)主義國(guó)家更好，會(huì)出現(xiàn)交換兩者地位的現(xiàn)象，原殖民地成為新的帝國(guó)主義國(guó)家，原帝國(guó)主義國(guó)家變?yōu)楫?dāng)前帝國(guó)的殖民地。本文選取算例KP28 和KP29 進(jìn)行實(shí)驗(yàn)，BICA-BMV 求解KP28 和KP29 時(shí)的收斂情況和種群交換地位總次數(shù)如圖9 所示。表5 的結(jié)果說(shuō)明KP28 和KP29 求解難度較大，且相較于BICA-DisEA，BICA-BMV 在這兩個(gè)算例上都表現(xiàn)得更好，所以被選取的兩個(gè)算例具有一定的合理性。

圖9 KP28和KP29的收斂情況和種群交換地位次數(shù)情況Fig.9 Conditions of convergence and times of population status exchange for KP28 and KP29

基于Partitioning 和Clustering 相關(guān)行為的作用，種群進(jìn)化總體朝變優(yōu)方向發(fā)展，在前期算法最優(yōu)解提升空間大，所以殖民地與帝國(guó)主義國(guó)家交換地位的情況發(fā)生頻繁，算法當(dāng)前找到的最優(yōu)解不斷更新；到后期算法已經(jīng)尋找到次理想解，國(guó)家種群中的最優(yōu)個(gè)體難以進(jìn)一步提升勢(shì)力，因此在勢(shì)力最強(qiáng)國(guó)家所在帝國(guó)發(fā)生地位交換也較困難，但是此時(shí)很可能有部分帝國(guó)已經(jīng)覆滅，重新初始化殖民地會(huì)因此初始化新的帝國(guó)，交換地位操作在新產(chǎn)生的帝國(guó)中又將變得容易，交換地位的總次數(shù)進(jìn)一步變多，這是種群得到進(jìn)一步進(jìn)化的表現(xiàn)。這些分析大致符合圖9 中曲線特點(diǎn)和變化趨勢(shì)。

總體來(lái)看，BICA 中的改進(jìn)機(jī)制確實(shí)改善了標(biāo)準(zhǔn)ICA 在全局尋優(yōu)能力上的不足，局部尋優(yōu)能力也得到進(jìn)一步提升。然而，在貪婪環(huán)境中以亞種群-帝國(guó)作為勘探載體將面臨兩個(gè)問(wèn)題：一是帝國(guó)數(shù)較少；二是帝國(guó)內(nèi)殖民地趨同、聚集特征愈發(fā)明顯。這使得BICA 面對(duì)KP03、KP21、KP29、KP32 這類(lèi)局部最優(yōu)解欺騙性大的算例時(shí)，空間解的勘探不夠全面和細(xì)致，會(huì)過(guò)快收斂到局部最優(yōu)。在求解測(cè)試集1 和2 的算例時(shí)，BICA-DisEA 和BICA-BMV 在少量的迭代次數(shù)后就能找到最優(yōu)解，這會(huì)增加算法持續(xù)陷入局部最優(yōu)的可能。

4.6 MLB-ICA性能分析

選用測(cè)試集1、2 中的算例作為基礎(chǔ)算例，分別組合2～6個(gè)KP 基礎(chǔ)算例，得到測(cè)試集3 中的10 個(gè)算例，命名為KP36～KP45，物品規(guī)模為｛1 800，1 300，1 700，1 100，1 400，800，1 900，2 100，2 200，3 000｝。

采用MLB-ICA 求解HMKP 的性能，算法最大迭代次數(shù)FEsmax=1 000，每次實(shí)驗(yàn)算法連續(xù)獨(dú)立運(yùn)行次數(shù)Times=50。初始種群中帝國(guó)數(shù)e=8，帝國(guó)中的王國(guó)數(shù)為m，m根據(jù)算例中隨機(jī)組合KP 的個(gè)數(shù)而定，每個(gè)聯(lián)盟國(guó)附屬殖民地的個(gè)數(shù)為col_num=9，選取測(cè)試結(jié)果的最優(yōu)解GAPbest與它對(duì)應(yīng)的gapi、最差解GAPworst與它對(duì)應(yīng)的gapi、均值解、中位數(shù)解GAPmedian與它對(duì)應(yīng)的gapi、標(biāo)準(zhǔn)差、平均迭代次數(shù)（迭代次數(shù)）評(píng)價(jià)算法性能，測(cè)試結(jié)果如表11 所示。

表11 MLB-ICA在測(cè)試集3上的測(cè)試結(jié)果Tab.11 Test results of MLB-ICA on test set 3

表11 中MLB-ICA 的測(cè)試結(jié)果為理想最優(yōu)解與當(dāng)前背包總價(jià)值的差值，所以GAP直接反映了算法在當(dāng)前測(cè)試算例的偏離水平，gapi反映了算法在第i個(gè)組合算例的偏離水平。組合算例中選取的都是BICA 能夠找到理想最優(yōu)解的算例，可以看出，MLB-ICA 能找到測(cè)試集3 中所有算例的理想最優(yōu)解。組合算例中也并非所有算例都能100%找到理想最優(yōu)解，這在表11 中也有明顯體現(xiàn)。所以，可以認(rèn)為MLB-ICA 較完整地繼承了BICA 的尋優(yōu)能力和特點(diǎn)，多級(jí)ICA 結(jié)構(gòu)起到了橋梁作用。從均值解指標(biāo)來(lái)看，MLB-ICA 的測(cè)試結(jié)果都非常接近0，說(shuō)明MLB-ICA 有較高的求解精度。

數(shù)學(xué)規(guī)劃求解工具Gurobi 對(duì)于求解MIP（Mixed Integer Programming）問(wèn)題具有通用性，表現(xiàn)出求解速度快、精度高、結(jié)果穩(wěn)定的特點(diǎn)，理論上能有效求解HMKP。通過(guò)Python 編譯程序調(diào)用Gurobi 求解器求解測(cè)試集3，并與表11 中的結(jié)果進(jìn)行對(duì)比，在驗(yàn)證MLB-ICA 的性能上具有較大的意義。

Gurobi 求解HMKP 表現(xiàn)出非常強(qiáng)的穩(wěn)定性，這在前期通過(guò)較多次數(shù)的實(shí)驗(yàn)得到了證實(shí)，MLB-ICA 和Gurobi 求解器求解測(cè)試集3 中算例的均值解和求解時(shí)間如表12 所示。

表12 MLB-ICA和Gurobi在測(cè)試集3上的均值解和求解時(shí)間Tab.12 Mean solutions and solving time of MLB-ICA and Gurobi on test set 3

從表12 可以看出，MLB-ICA 的平均求解精度比Gurobi提高了28%，但求解時(shí)間與Gurobi 之間存在較大的差距。MLB-ICA 能在更多的算例上跳出Gurobi 陷入的局部最優(yōu)，這說(shuō)明MLB-ICA 也具有較強(qiáng)的全局搜索能力，因此在一定程度上驗(yàn)證MLB-ICA 能有效求解HMKP 并有較好的性能。

5 結(jié)語(yǔ)

本文基于傳統(tǒng)多背包問(wèn)題，提出了一種背包問(wèn)題的新變種—HMKP，針對(duì)HMKP 強(qiáng)約束性和高計(jì)算復(fù)雜度的特性，改進(jìn)和定制了帝國(guó)競(jìng)爭(zhēng)算法對(duì)該問(wèn)題進(jìn)行求解。面向標(biāo)準(zhǔn)ICA 的不足和KP 的特征，提出了TPAS 和JLOA 兩個(gè)策略提高算法求解KP 性能。在O-RM 和O-CM 的監(jiān)督下，選用高效離散化方法并引入所提改進(jìn)機(jī)制提出了求解0-1KP 的BICA。通過(guò)大量實(shí)驗(yàn)并與其他元啟發(fā)式算法進(jìn)行比較，顯示出BICA 全面、高效的尋優(yōu)能力，實(shí)驗(yàn)結(jié)果也證明本文所提出的兩種改進(jìn)機(jī)制是有效的，BMV 相對(duì)于DisEA 能幫助BICA 獲得更強(qiáng)的尋優(yōu)能力。基于BICA 設(shè)計(jì)了求解HMKP的MLB-ICA，MLB-ICA 依托于BICA 并行求解HMKP，通過(guò)10個(gè)算例對(duì)MLB-ICA 進(jìn)行了性能測(cè)試，并與典型的商業(yè)求解器Gurobi 的求解結(jié)果進(jìn)行了詳細(xì)的對(duì)比分析，實(shí)驗(yàn)結(jié)果表明MLB-ICA 能夠有效求解HMKP 并得到優(yōu)于Gurobi 的測(cè)試結(jié)果，但在求解時(shí)間上，MLB-ICA 占劣勢(shì)。未來(lái)，將結(jié)合復(fù)雜物流系統(tǒng)的實(shí)際服務(wù)場(chǎng)景與離線/在線作業(yè)需求，對(duì)本文所提算法與機(jī)制展開(kāi)面向物流行業(yè)的算法修正與應(yīng)用探討。