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

1.引言

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

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

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

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

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

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

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

3.算法設(shè)計

3.1 人工蜂群算法

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

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

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

3.2 動態(tài)搜索

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

3.3 混沌理論

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

3.4 混沌人工蜂群算法

3.4.1 基本思想

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

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

(2)將種群分為兩部分：一部分動態(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)式，計算每個解xi的適應(yīng)度。

Step3：若符合調(diào)整搜索空間的條件，則按(9)式產(chǎn)生新的解空間；若不符合，則根據(jù)(7)式產(chǎn)生新的解vi，并計算其適應(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)生一個新解來代替。

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

4.仿真實例

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

5.結(jié)束語

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

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

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

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

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

[3]秦子玄,陳霞,唐小鵬,梁時木,漆楊,于中華.基于免疫克隆選擇算法的固定費(fèi)用運(yùn)輸問題優(yōu)化[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ī)工程與應(yīng)用,2011,47(29):27-30.

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

[9]張超群,鄭建國,王翔.蜂群算法研究綜述[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]暴勵,曾建潮.自適應(yīng)搜索空間的混沌蜂群算法[J].計算機(jī)應(yīng)用研究,2010,27(4):1330-1334.

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