李 斌，唐志斌

（1.福建理工大學 機械與汽車工程學院，福州 350118；2.福建省大數(shù)據(jù)挖掘與應用技術重點實驗室（福建理工大學），福州 350118；3.福建理工大學 交通運輸學院，福州 350118）

0 引言

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

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

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

1 問題描述

1.1 0-1背包問題描述

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

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

算法1 修復法。

輸入X，H1，H2，W；

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

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

1.2 多背包問題描述

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

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

1.3 異構多背包問題描述

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

圖1 HMKP的求解架構Fig.1 HMKP solution architecture

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

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

HMKP 可以描述為：有m堆物品，對應每堆物品的數(shù)量分別為{n1，n2，…，nm}，有m個背包，背包的容量屬性為Cj(j=1，2，…，m)，每堆物品對應一個背包，且只能選擇放入或者不放入該背包，不能放入其他背包中，第j堆物品中的第i件物品的重量屬性為wji，價值屬性為pji，從每堆物品中選擇部分物品放入相對應的背包中，使所有背包中的所有物品總價值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個背包，xji=0 表示第j堆物品中的第i件物品不放入第j個背包。HMKP 的數(shù)學表達式為：

本文描述的HMKP 是一個基礎原型問題，當面臨具體實際問題時，可以允許部分物品有選擇裝入背包的權利，本文的研究對于未來HMKP 的擴展有一定的借鑒意義。

2 求解0-1KP的二進制帝國競爭算法

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

2.1 基本帝國競爭算法

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

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

2.2.1 個體解的編碼表示

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

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

1）DisEA 離散化方法。

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

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

2）BMV 離散化方法。

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

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

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

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

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

算法2 修復機制（O-RM）。

輸入X，H3，W；

輸出X'。

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

算法3 修正機制（O-CM）。

輸入X，H4，W，w'；

輸出X'。

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

2.3 種群多樣性改進機制

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

2.3.1 雙點自變異算子

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

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

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

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

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

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

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

2.4 BICA框架

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

算法4 二進制帝國競爭算法（BICA）。

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

輸出 Best results。

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

3 求解HMKP的多級二進制帝國競爭算法

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

3.1 多級二進制帝國競爭算法結構

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

圖3 ICA與MLB-ICA的種群結構Fig.3 Population structures of ICA and MLB-ICA

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

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

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

3.2 MLB-ICA框架

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

算法5 多級二進制帝國競爭算法（MLB-ICA）。

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

輸出 Best results。

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

圖4 描述了帝國數(shù)量設置為8，求解3 個背包組合HMKP條件下MLB-ICA 的算法框架?？梢钥闯?，MLB-ICA 依托于BICA 并行求解HMKP，在帝國間信息交互環(huán)境中綜合考慮所有背包內(nèi)物品的總價值并評價算法求解得出較優(yōu)方案，最終輸出最優(yōu)HMKP 方案。從尋優(yōu)結果來看，HMKP 并非簡單地分割出多個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 算法的平衡改進機制

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

3.3.2 算法的時間復雜度分析

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

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

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

4 仿真實驗與結果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表5 BICA在測試集2上的測試結果Tab.5 Test results of BICA on test set 2

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

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

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

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

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

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

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

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

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

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

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

4.3 改進策略的有效性驗證

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

表9 ICA、BICA-A、BICA-B和BICA的測試結果Tab.9 Test results of ICA，BICA-A，BICA-B and BICA

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

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

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

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

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

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

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

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

TPAS 能幫助算法從基層種群層面進一步精細搜索較優(yōu)解，pro_col和TimeTPAS決定了局部搜索的深度。帝國主義國家在空間解的搜索中具有關鍵作用［36］，而TPAS 對帝國主義國家執(zhí)行操作的設計使它在局部搜索中的關鍵作用更加明顯。本節(jié)僅討論TimeTPAS的選取對BICA-BMV 性能的影響，pro_col選取了一個適中的值，設置為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)最好。理論情況下，無限地增大TimeTPAS值，算法能夠達到最優(yōu)性能，但是算法計算復雜度會因此線性增加。據(jù)實驗統(tǒng)計，TimeTPAS=75 的求解時間會比TimeTPAS=50 的求解時間至少增加30 個百分點。綜合考慮，TimeTPAS=50 在4 組取值中相對更優(yōu)，可以認為TimeTPAS值的設置很合理。

4.4.3 多級搜索步長參數(shù)

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

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

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

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

4.5 種群進化分析

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

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

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

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

4.6 MLB-ICA性能分析

選用測試集1、2 中的算例作為基礎算例，分別組合2～6個KP 基礎算例，得到測試集3 中的10 個算例，命名為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，每次實驗算法連續(xù)獨立運行次數(shù)Times=50。初始種群中帝國數(shù)e=8，帝國中的王國數(shù)為m，m根據(jù)算例中隨機組合KP 的個數(shù)而定，每個聯(lián)盟國附屬殖民地的個數(shù)為col_num=9，選取測試結果的最優(yōu)解GAPbest與它對應的gapi、最差解GAPworst與它對應的gapi、均值解、中位數(shù)解GAPmedian與它對應的gapi、標準差、平均迭代次數(shù)（迭代次數(shù)）評價算法性能，測試結果如表11 所示。

表11 MLB-ICA在測試集3上的測試結果Tab.11 Test results of MLB-ICA on test set 3

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

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

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

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

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

5 結語

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