混合帝國競爭算法求解帶多行程批量配送的多工廠集成調(diào)度問題

唐捷凱，胡 蓉，錢 斌，金懷平，向鳳紅

（1.昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院，云南昆明 650500；2.昆明理工大學(xué)云南省人工智能重點(diǎn)實(shí)驗(yàn)室，云南昆明 650500）

1 引言

在經(jīng)濟(jì)全球化趨勢下，大量企業(yè)的生產(chǎn)模式已由傳統(tǒng)集中式向分布式轉(zhuǎn)變，并進(jìn)一步構(gòu)建起集生產(chǎn)和運(yùn)輸為一體的供應(yīng)鏈［1～3］.為應(yīng)對(duì)分布式供應(yīng)鏈所帶來的車輛成本上升，則要提高車輛的利用率，使用相同車輛分批次多行程運(yùn)輸已成為必然趨勢［4～6］.基于上述背景，研究帶多行程批量配送的多工廠集成調(diào)度問題（Multi-Factory Integrated Scheduling Problem with Multi-Trip Batch Delivery，MFISP_MTBD）具有重要的經(jīng)濟(jì)效益.

當(dāng)前生產(chǎn)和運(yùn)輸集成調(diào)度問題的研究主要有兩類.第一類為單工廠生產(chǎn)與運(yùn)輸配送集成調(diào)度問題，現(xiàn)有研究分別對(duì)帶多行程運(yùn)輸［7］、批量運(yùn)輸［7，8］和多車型運(yùn)輸［9］等約束條件的此類問題進(jìn)行了建模與求解.第二類為多工廠生產(chǎn)與運(yùn)輸配送集成調(diào)度問題［1，10］.由文獻(xiàn)調(diào)研可知，目前對(duì)于第二類集成調(diào)度問題的研究還十分有限，且尚未考慮實(shí)際生產(chǎn)中廣泛存在的各工廠間生產(chǎn)效率差異與多行程運(yùn)輸?shù)燃s束條件.因此，建立考慮上述約束條件的MFISP_MTBD 數(shù)學(xué)模型，并設(shè)計(jì)求解該問題的有效算法具有重要的理論價(jià)值和實(shí)踐意義.

貝葉斯概率模型是一種基于貝葉斯統(tǒng)計(jì)推斷所提出的統(tǒng)計(jì)概率模型［11］，該概率模型繼承了先驗(yàn)分布這一獨(dú)特的統(tǒng)計(jì)學(xué)特征.因其良好的統(tǒng)計(jì)推斷效果［12］，近年來基于該模型的學(xué)習(xí)型智能算法［13］被廣泛用于求解可重入作業(yè)車間調(diào)度問題［14］、低碳分布式流水線調(diào)度問題［15］和帶時(shí)間窗的車輛調(diào)度問題［16］.

帝國競爭算法（Imperialist Competitive Algorithm，ICA）是一種具有高效全局搜索能力的群智能算法，已被廣泛應(yīng)用于求解生產(chǎn)調(diào)度［17，18］、路徑規(guī)劃［19］等領(lǐng)域的問題.然而，ICA 的同化機(jī)制在一定程度上導(dǎo)致其存在過早收斂的問題［20］，針對(duì)該問題現(xiàn)有算法的主要改進(jìn)可以分為兩類.第一類為引入接受差解的機(jī)制，在一定程度上緩解ICA 的過早收斂［20，21］.第二類為引入概率模型對(duì)ICA 同化機(jī)制進(jìn)行優(yōu)化［22］，使之成為學(xué)習(xí)型智能算法.然而，現(xiàn)有學(xué)習(xí)型ICA 所采用的二維概率模型僅能學(xué)習(xí)編碼間的相鄰關(guān)系信息，卻無法學(xué)習(xí)編碼所在的位置信息.因此，將貝葉斯概率模型與ICA 相結(jié)合將更加有利于引導(dǎo)帝國對(duì)解空間進(jìn)行更加高效且深入的探索.

本文研究了MFISP_MTBD 的建模與求解.針對(duì)實(shí)際供應(yīng)鏈體系中各工廠間生產(chǎn)效率差異與多行程運(yùn)輸?shù)燃s束條件，建立以最小化加工與運(yùn)輸總成本為目標(biāo)的MFISP_MTBD 模型.根據(jù)MFISP_MTBD 特性提出基于多行程標(biāo)簽機(jī)制的兩階段編解碼策略，同時(shí)設(shè)計(jì)新型啟發(fā)式規(guī)則以提升初始種群的質(zhì)量.設(shè)計(jì)基于貝葉斯統(tǒng)計(jì)推斷的混合帝國競爭算法（Hybrid Bayesian statistical inference-based Imperialist Competitive Algorithm，HBICA）對(duì)其進(jìn)行求解.該算法一方面引入基于貝葉斯概率模型的學(xué)習(xí)型同化機(jī)制，實(shí)現(xiàn)優(yōu)質(zhì)解的高效學(xué)習(xí)與算法全局的高效引導(dǎo)；另一方面設(shè)計(jì)“殖民掠奪”變鄰域局部搜索機(jī)制進(jìn)行有側(cè)重的深入搜索.通過仿真實(shí)驗(yàn)和算法對(duì)比驗(yàn)證了HBICA 求解MFISP_MTBD 的有效性.

2 MFISP_MTBD的問題描述

2.1 符號(hào)定義

MFISP_MTBD 涉及的有關(guān)數(shù)學(xué)符號(hào)定義如表1所示.

表1 符號(hào)表

2.2 問題模型

MFISP_MTBD可描述為：將N個(gè)客戶的工件訂單分配至F個(gè)分布在不同地理位置且具備加工能力的工廠分別按照πf的順序進(jìn)行加工，工件加工完成后通過各工廠的車隊(duì)按照的順序分批配送給客戶.該模型主要分為生產(chǎn)階段和配送階段.在生產(chǎn)階段，各工廠加工具有相同的單位能耗Ep(kW·h)，但各工廠對(duì)同一工件存在差異化的加工時(shí)間Pif.所有工件均可安排在任意工廠進(jìn)行加工，工件被分配至某一工廠后便不能再次分配至其他工廠，各工廠在同一時(shí)間只能加工一個(gè)工件.不同工件之間相互獨(dú)立且在加工時(shí)不允許發(fā)生搶占.在配送階段，各工廠的車隊(duì)擁有足夠數(shù)量具有相同速度V和載重約束Q的同質(zhì)車輛，啟用新車輛的固定成本為FC.已啟用的車輛在配送計(jì)劃批次中工件都完工后從工廠出發(fā)將工件送達(dá)客戶并返回，當(dāng)車輛返回工廠后經(jīng)過時(shí)長為tm的維護(hù)后，在CRkfw時(shí)刻即可開始新的行程.各工廠依據(jù)工件的完工時(shí)間Ci、截止交貨期di等約束，靈活規(guī)劃車輛數(shù)量和每輛車各批次運(yùn)輸路線將工件配送給客戶.MFISP_MTBD示意圖如圖1所示.

圖1 MFISP_MTBD示意圖

MFISP_MTBD 的優(yōu)化目標(biāo)為在集成調(diào)度問題中找到最優(yōu)排序π*，使得總成本ΤC最小.

其中，式（1）保證每一個(gè)工件都被分配到一個(gè)工廠.式（2）和式（3）保證每一個(gè)工件都有一個(gè)前置和后續(xù)工件在工廠中被加工.式（4）和式（5）計(jì)算各工件在生產(chǎn)階段的完工時(shí)間.式（6）計(jì)算所有工廠在生產(chǎn)階段產(chǎn)生能耗的總和.式（7）保證每一個(gè)工件都被分配到所在工廠的一個(gè)配送行程.式（8）和式（9）保證每一個(gè)客戶都有一個(gè)前置和后續(xù)客戶在配送行程中被服務(wù).式（10）保證配送行程均滿足車輛載重約束.式（11）～（15）計(jì)算配送行程的往返時(shí)間及各工件送達(dá)客戶的時(shí)間.式（16）和式（17）計(jì)算各車在配送行程中各路段的貨運(yùn)負(fù)載.式（18）計(jì)算各車在配送行程中各路段產(chǎn)生的油耗［8］.式（19）計(jì)算所有車在配送行程中產(chǎn)生的總油耗.式（20）計(jì)算各工件總違規(guī)超時(shí)時(shí)長.式（21）計(jì)算由工廠能耗費(fèi)用、車輛油耗費(fèi)用、車輛固定成本以及違規(guī)超時(shí)懲罰所組成的總成本.

3 HBICA求解MFISP_MTBD

MFISP_MTBD 的本質(zhì)是一個(gè)復(fù)雜的組合優(yōu)化問題，高效求解此類問題的關(guān)鍵在于如何針對(duì)問題特性設(shè)計(jì)合理的編解碼策略和改進(jìn)算法設(shè)計(jì).

HBICA 中，國家π就是原問題的一個(gè)解；定義為HBICA 第G代的國家種群，其中Nna為NPop 的規(guī)模，PImp為初始化中 殖民國家在Nna的占比，NImp為NPop 中殖民國家的規(guī)模，NCol為NPop 中殖民地的規(guī)模；定義EmpPopE(G)為第G代第E帝國的國家種群，EmpPopE(G)=為該帝國所包含的國家數(shù)量為該帝國的殖民國家為該帝國殖民地.

3.1 編碼與解碼

3.1.1 國家編碼與解碼

在編碼過程中，每個(gè)國家編碼π首先按工廠編號(hào)遞增的順序依次將各廠的工件加工順序錄入，然后在工廠工序間插入取值為(N，N+F)的(F-1)個(gè)工廠分隔符.以規(guī)模為N=8，F(xiàn)=3 的問題為例，編碼9 與10 為工廠分隔符，其編碼如圖2所示.

圖2 編碼示意圖

在解碼過程中，針對(duì)優(yōu)化目標(biāo)為最小化ΤC 的MFISP_MTBD 設(shè)計(jì)了一種融合了多行程標(biāo)簽［4］的新型解碼策略.該解碼策略分為2 個(gè)階段，首先在π中通過識(shí)別工廠分隔符依次讀取各工廠工件的加工順序；然后以各工件完工時(shí)間作為釋放時(shí)間，按照先完工先運(yùn)輸（First Completed First Transported，F(xiàn)CFT）的規(guī)則，以最大化利用車輛為目標(biāo)對(duì)車輛路徑進(jìn)行規(guī)劃.具體步驟如下所示：

步驟1：若當(dāng)前解碼位置α=0，則將當(dāng)前工廠編號(hào)設(shè)置為f=1，分配到工廠的工件數(shù)Nf=0，令α=α+1；轉(zhuǎn)至步驟2.

步驟2：若π(α)≤N，則將π(α)置于πk中的第Nf+1位，令α=α+1，Nf=Nf+1；若π(α)＞N，則令當(dāng)前工廠編號(hào)f=f+1，令Nf=0，α=α+1.轉(zhuǎn)至步驟3.

步驟3：若α≤(N+F-1)，按照式（1）～（5）計(jì)算得到πf(Nf)的完工時(shí)間，轉(zhuǎn)至步驟2；若α＞(N+F-1)，令F=f，f=1，工廠啟用車輛數(shù)為k=0，轉(zhuǎn)至步驟4.

步驟7：若Nf＞δf+1，則轉(zhuǎn)至步驟5；否則，轉(zhuǎn)至步驟8.

步驟8：若f+1 ≤F，令f=f+1，k=0，轉(zhuǎn)至步驟4；否則，輸出加工序列和運(yùn)輸序列.

3.1.2 資源編碼與解碼

針對(duì)本文提出的“殖民掠奪”變鄰域搜索，HBICA將與各國家π相對(duì)應(yīng)的局部搜索具象為資源個(gè)體Λ.每個(gè)Λ 均由9 種不同的鄰域搜索操作LSs排列而成，其鄰域搜索操作次數(shù)為η，且同一Λ 中允許出現(xiàn)相同的LSs.解碼Λ 時(shí)，對(duì)π從左到右依次執(zhí)行Λ 中的鄰域搜索操作.每執(zhí)行完一次鄰域搜索操作，就將得到的新解與舊解進(jìn)行對(duì)比，若新解優(yōu)于舊解，則用新解替換舊解，否則，舍棄新解.以η=5 的資源個(gè)體Λ 為例，其示意圖如圖3所示.

圖3 資源個(gè)體示意圖

3.2 初始化帝國

3.2.1 初始化國家

本文針對(duì)MFISP_MTBD 這類問題的性質(zhì)［1］，設(shè)計(jì)啟發(fā)式規(guī)則產(chǎn)生高質(zhì)量初始解，其步驟如下：

步驟1：隨機(jī)生成包含全部工件的工件序.

步驟2：從左到右依次取出工件，按式（6）～（21）計(jì)算其插入各工廠加工序的最后所帶來的ΤC增量.

步驟3：將當(dāng)前工件安排在ΤC 增量最小的工廠進(jìn)行加工.若尚有工件未分配工廠，則轉(zhuǎn)至步驟2，否則，輸出由啟發(fā)式規(guī)則生成的新國家.

同時(shí)為兼顧初始種群的質(zhì)量和分散性，根據(jù)啟發(fā)式規(guī)則使用概率PH來隨機(jī)選擇啟發(fā)式規(guī)則生成與隨機(jī)生成兩種方式對(duì)NPop(1)進(jìn)行初始化.然后，隨機(jī)生成Nna個(gè)資源個(gè)體并與NPop(1)各國家建立一一對(duì)應(yīng)的關(guān)系.

3.2.2 構(gòu)建帝國

構(gòu)建帝國首先需要計(jì)算所有初始國家的ΤC，將NPop(1)中ΤC 較小的NImp個(gè)國家作為殖民國家存入各帝國種群EmpPopE(1)中的同時(shí)將對(duì)應(yīng)的資源個(gè)體存入帝國資源域ERPopE(1)中的

然后將殖民國家力量進(jìn)行歸一化，并以此劃分殖民地，其具體計(jì)算如式（23）～（25）所示：

其中，式（23）為初始殖民國家數(shù)量（即初始帝國數(shù)量）的計(jì)算式，PImp為初始殖民國家占比；式（24）為殖民國家的實(shí)力PΤC的計(jì)算式；式（25）為獲取殖民地的概率PE的計(jì)算公式，且

最后，依據(jù)PE以輪盤賭的方式依次將NCol個(gè)殖民地及其資源個(gè)體分別劃分至EmpPopE(1)與ERPopE(1)從而完成初始帝國的構(gòu)建.

3.3 同化

HBICA 的同化階段是通過在各帝國使用貝葉斯網(wǎng)絡(luò)學(xué)習(xí)精英國家的結(jié)構(gòu)信息，分別構(gòu)建NImp個(gè)貝葉斯概率模型，繼而通過采樣各帝國所屬貝葉斯概率模型更新全部殖民地以實(shí)現(xiàn)同化.其中，精英國家為各帝國中按ΤC 遞增排序的前Nelite個(gè)國家，其中Nelite的計(jì)算如下：

式（26）為每個(gè)帝國中精英國家的數(shù)量計(jì)算式，其中Pelite為精英國家占比.

3.3.1 構(gòu)建貝葉斯概率模型

圖4 精英國家貝葉斯網(wǎng)絡(luò)圖

顯然，上述貝葉斯概率模型存在如下問題：（1）在后續(xù)采樣過程易產(chǎn)生非法解，例如N1，3→N2，2→N3，1→N4，3；（2）部分定向弧概率為0，則意味著在更新殖民地時(shí)將永遠(yuǎn)無法得到此序列，這將不利于算法跳出局部最優(yōu)解；（3）部分定向弧概率為1，則新殖民地在此節(jié)點(diǎn)的序列均相同，這將導(dǎo)致算法過早收斂.

針對(duì)上述問題，本文對(duì)初始化貝葉斯網(wǎng)絡(luò)進(jìn)行了以下改進(jìn)：（1）賦予所有可行的定向弧權(quán)重該操作在避免產(chǎn)生非法解的同時(shí)提升了國家的多樣性；（2）引入最低國家數(shù)量標(biāo)準(zhǔn)γ，其中γ=則挑選當(dāng)前帝國中精英國家構(gòu)造貝葉斯網(wǎng)絡(luò)；否則，以殖民國家為原型隨機(jī)使用LSs生成個(gè)虛擬國家擴(kuò)充至帝國，再挑選其中的精英國家構(gòu)造貝葉斯網(wǎng)絡(luò)，該操作有助于提升小規(guī)模帝國搜索的有效性.

3.3.2 采樣

為了提高采樣的執(zhí)行效率，本文結(jié)合貝葉斯概率模型的特點(diǎn)，提出了一種融合了禁忌表的輪盤賭采樣方式，其采樣步驟如下：

步驟1：建立與編碼長度相同的禁忌表Τabu=[Φ1，Φ2，…，ΦN+F-1]，令?Φ=Τrue.使用輪盤賭的方法選擇第一個(gè)節(jié)點(diǎn)N1，i，將N1，i存入新國家編碼第1 位，令Φi=False，國家編碼位置x=2.

步驟2：將滿足Φj=Τrue 的Nx-1，i到Nx，j定向弧權(quán)重歸一化計(jì)算P(Nx，j|Nx-1，i)，繼而使用輪盤賭選擇下一節(jié)點(diǎn)Nx，j.

步驟3：將Nx，j存入新國家編碼第x位，令Φj=False，i=j，x=x+1.若x＜N+F，則跳轉(zhuǎn)至步驟2；否則，輸出國家編碼替換舊殖民地.

3.4 革命

殖民地革命作為一種對(duì)殖民地國家編碼的操作方式，其無序擾動(dòng)策略使某些國家在解空間中的位置產(chǎn)生突變，增加了算法的搜索范圍并預(yù)防整個(gè)搜索進(jìn)程過早進(jìn)入局部最優(yōu)［3］.

具體來說，首先對(duì)所有殖民地以PR的革命發(fā)生概率隨機(jī)判斷是否革命；然后對(duì)發(fā)生革命的殖民地隨機(jī)選擇鄰域搜索操作LSs進(jìn)行擾動(dòng)，若擾動(dòng)后殖民地ΤC發(fā)生改善，則更新殖民地；最終，在各帝國中選出該帝國當(dāng)前最優(yōu)國家成為新的殖民國家，從而實(shí)現(xiàn)對(duì)各帝國的革命.

3.5 殖民掠奪

將局部搜索作為優(yōu)化工具融入ICA，將有利于提升國家的適應(yīng)度，進(jìn)而促進(jìn)算法性能的加強(qiáng)［16］.然而，使用局部搜索勢必造成算法計(jì)算復(fù)雜度的提升，占用較多計(jì)算資源，進(jìn)而降低算法迭代效率.因此，設(shè)計(jì)合理的局部搜索的分配規(guī)則將有助于提升局部搜索策略使用效率的提升.故本文提出了“殖民掠奪”變鄰域局部搜索機(jī)制，該機(jī)制利用9種針對(duì)MFISP_MTBD 設(shè)計(jì)的鄰域搜索操作動(dòng)態(tài)構(gòu)建局部搜索，并通過資源競爭與掠奪來對(duì)局部搜索進(jìn)行分配，從而實(shí)現(xiàn)了局部搜索合理高效的運(yùn)用.

3.5.1 鄰域搜索操作

本文設(shè)計(jì)9種不同的鄰域搜索操作，如下所示：

（1）LS1：國家編碼序列交叉操作，從國家編碼序列中隨機(jī)選擇2位進(jìn)行交換.

（2）LS2：國家編碼序列前向插入操作，從國家編碼序列中依次隨機(jī)選擇2位，將先選中的編碼插到后選中的編碼之前.

（3）LS3：國家編碼序列逆序操作，從國家編碼序列中隨機(jī)選擇2 位，將包含所選2 位及其之間的編碼顛倒排列順序.

（4）LS4：國家編碼序列相鄰交換操作，從國家編碼序列中隨機(jī)選擇一位，以相同的概率隨機(jī)選擇其與其向前或向后相鄰的編碼進(jìn)行交換.

（5）LS5：工廠加工序列交叉操作，隨機(jī)選擇一個(gè)Kf≥2的工廠，再從該工廠加工序中隨機(jī)選擇2位進(jìn)行交換.

（6）LS6：工廠加工序列前向插入操作，隨機(jī)選擇一個(gè)Kf≥2的工廠，再從該工廠加工序中隨機(jī)選擇2位，將先選中的工件插到后選中的工件之前.

（7）LS7：工廠加工序列逆序操作，隨機(jī)選擇一個(gè)Kf≥2的工廠，再從該工廠加工序中隨機(jī)選擇2位，將包含所選2位及其之間的工件顛倒排列順序.

（8）LS8：車輛行程服務(wù)序列交叉操作，隨機(jī)選擇2個(gè)車輛行程服務(wù)序列，將2個(gè)車輛行程所包含的工件全部交換.

（9）LS9：車輛行程服務(wù)序列逆序操作，隨機(jī)選擇一個(gè)車輛行程服務(wù)序列，將該車輛行程服務(wù)序列的工件顛倒排列順序.

在此基礎(chǔ)上進(jìn)一步將鄰域搜索操作組合成不同的局部搜索并作為HBICA 的資源個(gè)體Λ 提供給國家使用，將有利于Λ 對(duì)國家在多種鄰域結(jié)構(gòu)下持續(xù)的優(yōu)化，從而實(shí)現(xiàn)對(duì)解空間深入有效的搜索.

3.5.2 資源競爭與掠奪

HBICA 將帝國內(nèi)部的國家按編號(hào)依次連接，通過在各帝國內(nèi)部展開資源競爭與掠奪實(shí)現(xiàn)細(xì)致而有側(cè)重的局部搜索.其具體步驟如下所示：

步驟1：令帝國編號(hào)E=1，國家編號(hào)i=1.

步驟2：當(dāng)i=1時(shí)，令

步驟6：在E帝國內(nèi)進(jìn)行殖民關(guān)系轉(zhuǎn)換操作，依次使用弱勢國家的Λ對(duì)進(jìn)行優(yōu)化.

3.6 帝國競爭與刪除

帝國競爭的本質(zhì)是各帝國按照帝國實(shí)力EΤCE對(duì)殖民地的爭奪.帝國實(shí)力由殖民國家實(shí)力與殖民地實(shí)力2部分所組成，其具體計(jì)算如下：

在帝國競爭過程中，首先確定最弱小的帝國，并從中割讓一塊殖民地.然后其余帝國依據(jù)帝國實(shí)力以輪盤賭的方式?jīng)Q定殖民地的新歸屬，其具體計(jì)算如下：

其中，EΤPE為E帝國獲取殖民地的概率.

由于HBICA 在同化中使用貝葉斯概率模型學(xué)習(xí)精英國家結(jié)構(gòu)信息.因此，若割讓的殖民地滿足成為新帝國精英國家的條件，則最弱小帝國的部分優(yōu)質(zhì)結(jié)構(gòu)信息也將被新帝國所接納.故HBICA 選擇而不是傳統(tǒng)的作為被割讓的殖民地，進(jìn)而保證被割讓殖民地信息有更高的概率被新帝國貝葉斯概率模型學(xué)習(xí)，從而實(shí)現(xiàn)帝國間的優(yōu)質(zhì)信息交互.

在完成帝國競爭后，HBICA進(jìn)入帝國刪除階段.即檢查此時(shí)最弱小帝國所擁有的殖民地?cái)?shù)量，若該帝國喪失全部的殖民地，則該帝國的殖民國家將淪為殖民地并劃歸其他帝國，至此該帝國滅亡.

3.7 帝國重構(gòu)

針對(duì)HBICA 帝國兼并速度加快的特點(diǎn)，設(shè)計(jì)了“帝國重構(gòu)”擾動(dòng)機(jī)制.即算法在未滿足終止條件前，若所有國家兼并為單一帝國，則在保留國家種群中具有最優(yōu)秀ΤC 值的NImp個(gè)編碼不同的國家作為新的殖民國家，并重新劃分由初始化國家操作重新生成的殖民地以實(shí)現(xiàn)帝國的重新構(gòu)建.

該擾動(dòng)機(jī)制有助于提升算法后期對(duì)多個(gè)優(yōu)質(zhì)解區(qū)域同時(shí)搜索的能力，減緩過早收斂，從而實(shí)現(xiàn)HBICA 的整體性能.

3.8 算法流程

據(jù)算法描述，HBICA算法流程如圖5所示.

圖5 HBICA流程圖

4 實(shí)驗(yàn)分析與比較

由于目前尚無適合MFISP_MTBD 的標(biāo)準(zhǔn)算例，本文所有的測試算例均在Gharaei 等［1］為解決MFISP_BD所提供的數(shù)據(jù)分布區(qū)間上隨機(jī)生成共計(jì)27 個(gè)按照N×F組合的測試算例.所有算法和實(shí)驗(yàn)均由Delphi 2010編程實(shí)現(xiàn)，操作系統(tǒng)為Windows 10，CPU為2.90 GHz，內(nèi)存為16 GB.

4.1 參數(shù)設(shè)置

在HBICA 中，啟發(fā)式規(guī)則使用概率PH、初始殖民國家占比PImp、精英國家占比Pelite和資源個(gè)體的鄰域搜索次數(shù)η為關(guān)鍵參數(shù).本文對(duì)中等規(guī)模問題（90×6）采用實(shí)驗(yàn)設(shè)計(jì)（Design Of Experiment，DOE）［24］行實(shí)驗(yàn)分析，得出HBICA 的最佳參數(shù)組合為PH=0.4，PImp=0.020，Pelite=0.3，η=6.

4.2 仿真結(jié)果比較與分析

本節(jié)將每種算法放在各測試問題上以相同時(shí)間（(N×F×100)ms）下獨(dú)立運(yùn)行21次.其中，AVG為算法獨(dú)立運(yùn)行21次輸出最優(yōu)結(jié)果的平均值，Average為所有規(guī)模問題通過相關(guān)算法獲得的每個(gè)性能指標(biāo)輸出結(jié)果的平均值，NB 為所有規(guī)模問題通過相關(guān)算法獲得的每個(gè)性能指標(biāo)最優(yōu)值的總數(shù)，在各指標(biāo)下的占優(yōu)值用粗體進(jìn)行標(biāo)識(shí).

4.2.1 驗(yàn)證算法改進(jìn)的有效性

為驗(yàn)證HBICA 中“貝葉斯概率模型同化機(jī)制”與“殖民掠奪”自適應(yīng)變鄰域局部搜索機(jī)制2 種關(guān)鍵改進(jìn)的有效性，本節(jié)將HBICA 與ICA 及其變形算法進(jìn)行比較，其結(jié)果如表2 所示.其中，ED_ICA 為采用二維概率模型同化機(jī)制的ICA，B_ICA 為采用貝葉斯概率模型同化機(jī)制的ICA.

表2 ICA、ED_ICA、B_ICA與HBICA的有效性對(duì)比結(jié)果

由表2 可知，B_ICA 解的質(zhì)量相較于ED_ICA 與ICA 有明顯的提升，驗(yàn)證了貝葉斯概率模型同化機(jī)制的有效性.HBICA 解的質(zhì)量相較于B_ICA 有顯著的提升，驗(yàn)證了“殖民掠奪”變鄰域局部搜索機(jī)制的有效性.

4.2.2 HBICA與其他算法的比較

為驗(yàn)證HBICA 的有效性，將HBICA 與近年來求解相關(guān)問題的有效算法（IWOA［10］、HGA［4］和TS［8］）進(jìn)行對(duì)比，各算法比較結(jié)果如表3所示.

由表3可知，HBICA在大部分問題上的測試結(jié)果都明顯優(yōu)于對(duì)比算法，表明HBICA 是求解MFISP_MTBD的有效算法.HBICA 一方面利用貝葉斯概率模型同化機(jī)制實(shí)現(xiàn)對(duì)優(yōu)質(zhì)解信息的高效學(xué)習(xí)與殖民地的再建構(gòu)，有利于快速發(fā)現(xiàn)問題解空間中優(yōu)質(zhì)區(qū)域；另一方面利用“殖民掠奪”引導(dǎo)局部搜索對(duì)優(yōu)質(zhì)解區(qū)域進(jìn)行集中優(yōu)化，有利于算法對(duì)優(yōu)質(zhì)解區(qū)域進(jìn)行較深入的搜索，從而能高效地發(fā)現(xiàn)復(fù)雜問題的優(yōu)質(zhì)解.因此，HBICA能在上述實(shí)驗(yàn)中取得較好結(jié)果.

表3 HBICA與3種有效算法的對(duì)比結(jié)果

5 結(jié)論

為綜合考慮存在于多工廠供應(yīng)鏈的實(shí)際運(yùn)輸中常見的車輛重復(fù)使用情況，本文提出了一種基于貝葉斯統(tǒng)計(jì)推斷的混合帝國競爭算法，求解以最小化總成本為目標(biāo)的MFISP_MTBD.首先，設(shè)計(jì)了基于多行程標(biāo)簽機(jī)制的新型編解碼策略，并構(gòu)造新型啟發(fā)式規(guī)則以提高初始解的質(zhì)量.然后，采用貝葉斯概率模型學(xué)習(xí)機(jī)制替換標(biāo)準(zhǔn)帝國競爭算法中的同化機(jī)制，將各種群向優(yōu)質(zhì)解區(qū)域進(jìn)行快速引導(dǎo).其次，采用“殖民掠奪”變鄰域局部搜索機(jī)制，實(shí)現(xiàn)對(duì)優(yōu)質(zhì)區(qū)域細(xì)致而有側(cè)重的搜索.最后，通過在不同測試問題上的仿真實(shí)驗(yàn)與算法比較，驗(yàn)證了HBICA是求解MFISP_MTBD的有效算法.