求解固定費(fèi)用運(yùn)輸問(wèn)題的混沌人工蜂群算法

廣東工業(yè)大學(xué)自動(dòng)化學(xué)院 張永前 蔡延光 湯雅連

1.引言

固定費(fèi)用運(yùn)輸問(wèn)題（fcTP）[1-3]屬于高級(jí)運(yùn)輸問(wèn)題，是運(yùn)輸問(wèn)題的擴(kuò)展。許多實(shí)際運(yùn)輸和分配問(wèn)題，如具有固定物流費(fèi)用的最小費(fèi)用網(wǎng)絡(luò)流（轉(zhuǎn)運(yùn)）問(wèn)題，可以用公式表示為固定費(fèi)用運(yùn)輸問(wèn)題。除了運(yùn)輸問(wèn)題的兩個(gè)約束條件，fcTP還考慮在每個(gè)工廠與倉(cāng)庫(kù)之間的每一次運(yùn)輸會(huì)存在一定的固定成本，而每一家工廠或倉(cāng)庫(kù)還需要固定投資。線性運(yùn)輸問(wèn)題則沒(méi)有考慮這些固定成本和投資。fcTP屬于非線性運(yùn)輸問(wèn)題，目標(biāo)函數(shù)具有不連續(xù)性，比運(yùn)輸問(wèn)題更難處理。在實(shí)際問(wèn)題中，找到fcTP的最小運(yùn)輸費(fèi)用，對(duì)于減少運(yùn)輸成本，合理有 效分配資源，有著十分重要的意義。

關(guān)于fcTP的研究文獻(xiàn)已有許多。早期工作包括：用分支定界法[4]求解pfcTP(pure fixed charge transportation problem)，采用Benders型策略和約束性Lagrangean啟發(fā)式算法， 將后者與分支定界法相結(jié)合，計(jì)算結(jié)果表明兩種方法都是可行的，但是不適用于大規(guī)模問(wèn)題模型；文獻(xiàn)[1]用分支法求解fcTP，產(chǎn)生了好的初始解，而且每次迭代能使解接近于最優(yōu)解；文獻(xiàn)[5]中提出fcTP中的目標(biāo)函數(shù)是一個(gè)階躍函數(shù)，并用啟發(fā)式算法對(duì)sfcTP(step fixed charge transportation problem)求解；文獻(xiàn)[6]中提出用生成樹(shù)遺傳算法求解非線性固定運(yùn)輸問(wèn)題，并通過(guò)實(shí)驗(yàn)證明了該算法求解fcTP的有效性，但是仍然擺脫不了遺傳算法陷入局部最優(yōu)以及收斂速度慢的局限性。本文提出了用CABC(Chaos Articficial Bee Colony Algorithm)求解fcTP，并給出詳細(xì)分析及實(shí)驗(yàn)結(jié)果對(duì)比分析。

2.問(wèn)題描述及數(shù)學(xué)模型的建立

固定費(fèi)用運(yùn)輸問(wèn)題描述為：在考慮了與活動(dòng)水平成比例的可變成本和固定成本這兩類費(fèi)用后，通過(guò)分配每家工廠的可用供應(yīng)量，滿足每個(gè)倉(cāng)庫(kù)的需求，來(lái)確定使運(yùn)輸成本最小的運(yùn)輸計(jì)劃，即以運(yùn)輸成本為目標(biāo)函數(shù)，尋找使目標(biāo)函數(shù)最小化，同時(shí)滿足下列條件的運(yùn)輸計(jì)劃：

(I)工廠i到倉(cāng)庫(kù)j的運(yùn)輸量應(yīng)不超過(guò)工廠i的可用量也不小于倉(cāng)庫(kù)j的需求量。

(II)運(yùn)輸量為0的情況下，不計(jì)算其引起的成本費(fèi)用。

m家工廠和n個(gè)倉(cāng)庫(kù)的固定費(fèi)用運(yùn)輸問(wèn)題的數(shù)學(xué)模型如下：

3.算法設(shè)計(jì)

3.1 人工蜂群算法

人工蜂群（ABC）算法[7-10]是Karaboga提出的一種模仿蜜蜂覓食的仿生智能優(yōu)化算法，與遺傳、免疫克隆、粒子群等算法相比，ABC算法是一種較好的全局優(yōu)化算法，具有設(shè)置參數(shù)少、計(jì)算簡(jiǎn)單、收斂速度快等優(yōu)點(diǎn)。ABC算法將蜂群分為三組：采蜜蜂群、跟隨蜂群和偵察蜂群。蜜蜂與一個(gè)正在采蜜的蜜源對(duì)應(yīng)，記錄蜜源的相關(guān)信息，通過(guò)搖擺舞與其他蜜蜂分享信息；跟隨蜂在跳舞區(qū)等待分享采蜜蜂帶來(lái)的蜜源信息；偵察蜂探索新的蜜源。算法的搜索活動(dòng)包括3個(gè)階段：(1)采蜜蜂對(duì)蜜源進(jìn)行搜索并記憶蜜源的花蜜量；(2)觀察蜂根據(jù)從采蜜蜂處獲得的信息選擇一個(gè)蜜源位置并對(duì)記憶的位置作一定的改變；(3)確定偵察蜂并且使其開(kāi)拓新的蜜源來(lái)替代舊蜜源。在算法中，一個(gè)蜜源的位置代表優(yōu)化問(wèn)題中一個(gè)可能的解，蜜源的花蜜量代表解的質(zhì)量(適應(yīng)度)。根據(jù)蜜源的花蜜量，觀察蜂選擇某個(gè)蜜源的概率為(6)式，其中為蜜源個(gè)數(shù)，fit(i)為蜜源i的適應(yīng)度值。

為了根據(jù)記憶位置Xi產(chǎn)生一個(gè)新的候選位置Vi，標(biāo)準(zhǔn)ABC算法采用式(7)更新。其中k為不同于i的蜜源， j為隨機(jī)選擇的下標(biāo)，ijφ為[-1，1]之間的隨機(jī)數(shù)。

假如蜜源Xi經(jīng)過(guò)“l(fā)imit”次采蜜蜂和觀察蜂的循環(huán)搜索更新之后，不能夠被改進(jìn)，那么該位置將被放棄，該位置的采蜜蜂成為偵察蜂。“l(fā)imit”是ABC算法中一個(gè)重要的控制參數(shù)，用來(lái)控制偵察蜂的選擇。偵察蜂發(fā)現(xiàn)新位置并替換Xi的操作如式(8)所示。

3.2 動(dòng)態(tài)搜索

按(7)式生成解空間[11]：則yi越大，則種群在第i維坐標(biāo)上的空間分布就越大。

3.3 混沌理論

混沌[11]是自然界廣泛存在的一種非線性現(xiàn)象，是一種貌似無(wú)規(guī)則的運(yùn)動(dòng)，是非線性動(dòng)力系統(tǒng)所特有的一種運(yùn)動(dòng)形式，具有隨機(jī)性、遍歷性及規(guī)律性等特點(diǎn)，在一定范圍內(nèi)能按其自身的規(guī)律不重復(fù)地遍歷所有狀態(tài)。常用的混沌模型有Logistic映射模型，而Logistic映射所產(chǎn)生的序列不均勻，浪費(fèi)了計(jì)算時(shí) 間，所以本文采用Z映射[12]，如式(10)所示。

3.4 混沌人工蜂群算法

3.4.1 基本思想

混沌人工蜂群算法的基本思想主要有：

(1)利用混沌運(yùn)動(dòng)的遍歷性以當(dāng)前搜索停滯的解為基礎(chǔ)產(chǎn)生混沌序列，用產(chǎn)生的混沌序列中的最優(yōu)位置替代其原位置，使得搜索停滯的解繼續(xù)進(jìn)化，提高算法的收斂速度和精度。

(2)將種群分為兩部分：一部分動(dòng)態(tài)調(diào)整搜索區(qū)域，加快算法的收斂速度；另一部分在原空間內(nèi)搜索，保證位于空間邊緣的解不被忽略。

(3)在每一次混沌搜索空間調(diào)整后，進(jìn)行壓縮后的迭代，使群體適應(yīng)新環(huán)境。

3.4.2 算法流程

混沌人工蜂群算法的步驟為：

Step1：參數(shù)初始化設(shè)置，混沌序列初始化種群。

Step2：根據(jù)(6)式，計(jì)算每個(gè)解xi的適應(yīng)度。

Step3：若符合調(diào)整搜索空間的條件，則按(9)式產(chǎn)生新的解空間；若不符合，則根據(jù)(7)式產(chǎn)生新的解vi，并計(jì)算其適應(yīng)度值。

Step4：若vi與xi的適應(yīng)度值相等，則用vi代替xi，否則保留xi不變。

Step5：根據(jù)輪盤賭選擇策略選擇與xi相關(guān)的概率值pi。

Step6：跟隨蜂根據(jù)pi選擇食物源，并根據(jù)(7)式進(jìn)行領(lǐng)域搜索產(chǎn)生新的解，如果與xi的適應(yīng)度值相等，則用代替xi，否則保留xi不變。

Step7：如果有需要放棄的解存在，則利用混沌搜索產(chǎn)生一個(gè)新解來(lái)代替。

Step8：判斷是否達(dá)到最大迭代次數(shù)，達(dá)到則輸出結(jié)果，否則執(zhí)行Step3。

4.仿真實(shí)例

以文獻(xiàn)[2]中的實(shí)例為實(shí)驗(yàn)對(duì)象，5x10問(wèn)題模型如表1所示。本文中的實(shí)驗(yàn)是在Intel(R)Core?i3 CPU2.53GHz、內(nèi)存為2.0G、安裝系統(tǒng)為win7的PC機(jī)上采用Matlab7.1編程實(shí)現(xiàn)的。算法參數(shù)設(shè)置如下：種群規(guī)模n=200，limit=50，迭代次數(shù)Gen=2000。采蜜蜂群的規(guī)模，跟隨蜂群的規(guī)模。并與文獻(xiàn)[3]中的免疫克隆選擇算法求解的結(jié)果相比較。由表2知，混沌人工蜂群算法在求解固定費(fèi)用運(yùn)輸問(wèn)題時(shí)略優(yōu)于免疫克隆選擇算法。

5.結(jié)束語(yǔ)

提出了混沌人工蜂群算法，分析了固定費(fèi)用運(yùn)輸問(wèn)題的模型。將混沌搜索策略引入到算法中，提高了算法的局部搜索能力，引導(dǎo)個(gè)體逐步趨于全局最優(yōu)解。仿真實(shí)驗(yàn)表明，該算法的提出有一定的優(yōu)越性。人工蜂群算法是一種新的群智能優(yōu)化技術(shù)，目前關(guān)于這方面的文獻(xiàn)相當(dāng)較少，因而具有廣闊的應(yīng)用前景。人工蜂群算法中的參數(shù)設(shè)置如何影響算法性能也需要進(jìn)一步探討。總之，對(duì)人工蜂群算法的深入研究將會(huì)在很大程度上拓展群智能和拓寬應(yīng)用領(lǐng)域，從而能解決更多的實(shí)際問(wèn)題。

表1 5x10問(wèn)題的抽樣數(shù)據(jù)

表2 兩種算法比較結(jié)果

[1]Veena Adlakha,Krzysztof Kowalski.On the fixedcharge transportation problem,Omega,Int.J.Mgmt.Sci.27(1999):381-388.

[2]玄光男,程潤(rùn)偉.遺傳算法與工程優(yōu)化[M].北京:清華大學(xué)出版社,2009:242-246.

[3]秦子玄,陳霞,唐小鵬,梁時(shí)木,漆楊,于中華.基于免疫克隆選擇算法的固定費(fèi)用運(yùn)輸問(wèn)題優(yōu)化[J].計(jì)算機(jī)應(yīng)用研究,2009,26(7):2530-2534.

[4]Maud Gothe-Lundgren and Torbjorn Larsson.A set covering reformulation of the pure fixed charge transportation problem.Discrete Applied Mathematics 48(1994):245-259.

[5]Krzysztof Kowalski,Ben jamin Lev.On step fi xed-charge transportation problem.Omega 36(2008):913-917.

[6]Jung-Bok Jo,Yinzhen Li,Mitsuo Gen.Nonlinear fixed charge transportation problem by spanning tree-based genetic algorithm.Computer&Industrial Engineering 53(2007):290-298.

[7]銀建霞,孟紅云.具有混沌差分進(jìn)化搜索的人工蜂群算法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(29):27-30.

[8]拓守恒.一種求解高維約束優(yōu)化問(wèn)題的人工蜂群算法[J].計(jì)算機(jī)應(yīng)用研究,2012,29(3):937-940.

[9]張超群,鄭建國(guó),王翔.蜂群算法研究綜述[J].計(jì)算機(jī)應(yīng)用研究,2011,28(9):3201-3206.

[10]W.Y.Szeto,Yongzhong Wu,Sin C.Ho.An artificial bee colony algorithm for the capacitated vehicle routing problem.European Journal of Operational Research 215(2011):126-135.

[11]暴勵(lì),曾建潮.自適應(yīng)搜索空間的混沌蜂群算法[J].計(jì)算機(jī)應(yīng)用研究,2010,27(4):1330-1334.

[12]王毅,趙建軍,馮巍巍,付龍文,陳令新.基于自適應(yīng)混沌粒子群優(yōu)化的防空目標(biāo)分配[J].計(jì)算機(jī)工程,2012,38(20):144-147.