求解固定費用運輸問題的混沌人工蜂群算法

廣東工業大學自動化學院 張永前 蔡延光 湯雅連

1.引言

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

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

2.問題描述及數學模型的建立

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

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

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

m家工廠和n個倉庫的固定費用運輸問題的數學模型如下：

3.算法設計

3.1 人工蜂群算法

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

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

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

3.2 動態搜索

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

3.3 混沌理論

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

3.4 混沌人工蜂群算法

3.4.1 基本思想

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

(1)利用混沌運動的遍歷性以當前搜索停滯的解為基礎產生混沌序列，用產生的混沌序列中的最優位置替代其原位置，使得搜索停滯的解繼續進化，提高算法的收斂速度和精度。

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

(3)在每一次混沌搜索空間調整后，進行壓縮后的迭代，使群體適應新環境。

3.4.2 算法流程

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

Step1：參數初始化設置，混沌序列初始化種群。

Step2：根據(6)式，計算每個解xi的適應度。

Step3：若符合調整搜索空間的條件，則按(9)式產生新的解空間；若不符合，則根據(7)式產生新的解vi，并計算其適應度值。

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

Step5：根據輪盤賭選擇策略選擇與xi相關的概率值pi。

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

Step7：如果有需要放棄的解存在，則利用混沌搜索產生一個新解來代替。

Step8：判斷是否達到最大迭代次數，達到則輸出結果，否則執行Step3。

4.仿真實例

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

5.結束語

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

表1 5x10問題的抽樣數據

表2 兩種算法比較結果

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

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

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

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

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

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