蘇紹娟，王麗錚，王呈方

（武漢理工大學 交通學院，武漢430063）

航線配船主要是解決多船型在多條航線上的合理配置問題，目的在于充分利用現(xiàn)有的條件和資源，以最少的投入，換取最大的效益。由于在航運市場中存在很多不確定的因素，所以建立不確定性的航線配船模型符合實際情況。

粒子群優(yōu)化算法（PSO）是一種新興的群智能優(yōu)化算法，相對遺傳算法、模擬退火等算法而言，PSO更簡單有效，并已得到眾多學者的重視和研究，許多實際應用非常成功。但它同許多智能方法一樣存在早熟問題。在航體配船，由于存在隨機、模糊現(xiàn)象，使問題更加復雜，計算量非常大，所以提高計算速度很重要。根據(jù)不確定航線配船數(shù)學模型的特點及粒子群算法本身的特征，本文對粒子群算法進行了相應的改進。

1 數(shù)學模型

在若干港口之間長期從事大宗貨物運輸?shù)亩ň€運輸船隊，其船舶運行組織具有很強的規(guī)律性和相對的穩(wěn)定性。我國沿海的石油、礦石、煤炭等大宗工業(yè)物資的運輸就屬于這種情況?？茖W的配置船舶會帶來巨大的效益。

1.1 目標函數(shù)

以總利潤最大化為目標函數(shù)：即收入減去營運費用再減去閑置費用的最大值［1］。

式中：Aij——i型船在j航線上的單船年利潤；

DWi——船舶的載重噸；

ij——i船在j航線上的年航行次數(shù)；

Yj——j航線的運價；

DHYij——i船在j航線上的單航次耗油量；

RJ——燃油單價；

——船價；

α——與收入有關的成本占收入的比例；

α1——與船價相關的成本占船價的比例；

α2——船舶的閑置費占船價的百分比。

1.2 約束條件

1）船舶在該航線上的運量不能大于貨運需求量，即

2）保證各航線上的某型船數(shù)量與該船的閑置量之和與船隊中擁有的這種船的數(shù)量Ait相等。

3）變量非負性約束

式中：xij——決策變量，在j航線上配置的i型船數(shù)量；

pi——決策變量，i型船的閑置量；

——i型船舶在j航線上營運時的單船年運量；

——j航線上貨運需求量；

Ai——船隊中擁有的j型船數(shù)量；

K——船型總數(shù)；

G——航線總數(shù)。

需要說明的是ij是模糊量，Yj和是隨機變量，所以A P～ij是同時含有模糊和隨機的不確定量。即目標函數(shù)是含有模糊和隨機的不確定量。由于航次數(shù)是三角模糊量，所以船舶的年貨運量同樣是模糊數(shù)，約束實質上是模糊約束。

2 粒子群算法的改進

粒子群算法是繼蟻群算法之后又一群體智能算法，在粒子群算法中，每個粒子根據(jù)自己的飛行經(jīng)驗和同伴的飛行經(jīng)驗來調整自己的飛行速度和方向從而尋找問題的最優(yōu)解。它是一種隨機搜索算法，而且是從多個初始點開始進行搜索的，比較容易快速地接近或達到最優(yōu)解。

2.1 混沌算法

混沌變量產(chǎn)生的方法有多種，選用較為廣泛的Logistic映射，即：

將混沌變量zik映射到優(yōu)化變量取值區(qū)間成為xi，n+1：

二次載波的數(shù)學模型為：

式中：λ——時變參數(shù)zt的衰減因子，λ?1，通常取λ∈［0.95，0.999］；

x＊——第一階段搜索到的最優(yōu)解；

zt——時變參數(shù)。

這樣就可以實現(xiàn)在次優(yōu)值的雙側鄰域內通過逐步縮小混沌變量遍歷的區(qū)域范圍進行混沌細搜索，從而找到全局最優(yōu)值。

對于時變參數(shù)zt的初始值的選擇問題，模仿模擬退火算法初始退火溫度的思路來確定，即先按混沌尋優(yōu)方法的第一階段搜索N個可行解，并記錄這N個可行解中所對應的目標函數(shù)值的最大最小值fmax和fmin，選擇參數(shù)P（0＜P＜1），于是按下式確定zt的初始值z0：z0＝

2.2 粒子群算法的改進

本文對標準粒子群算法進行了以下改進［2-7］。

1）初始化。

采用混沌系列初始化粒子的位置，既不改變粒子群優(yōu)化算法初始化時所具有的隨機性本質，又利用混沌提高了種群的多樣性和粒子搜索的遍歷性。根據(jù)公式（6）和 （7）取足夠多的混沌序列點數(shù)，選擇性能較好的N個可行解組成初始群體。

2）加入約束因子的PSO模型。

1999年Clerc對算法的數(shù)學研究證明，采用約束因子（constriction factor）控制速度的權重，能夠保證算法的收斂且可以有效搜索不同的區(qū)域，從而得到高質量的解。

3）加入“第三個”極值，即在從第k代向第k+1代飛行的過程中，粒子除追隨個體極值pbest和全局極值gbest外，還追隨從粒子群中隨機選取的某個粒子的個體極值nbest進行速度更新。則粒子群數(shù)學模型為：

式中：c3——非負常數(shù)；

r3——［0，1］之間的隨機數(shù)；

l——在粒子群中隨機選取的某個粒子。

為保證收斂性，c1+c2+c3＞4。

在粒子的速度迭代公式中增加nbestt后，由pbest，gbest，nbest三者共同向下一代提供信息，粒子獲得的信息量增大，從而可能更快的找到優(yōu)化解。同時類似于GA中的變異操作，提供擾動信息，增加了粒子的多樣性，從而可使粒子跳出局部最優(yōu)區(qū)域，使算法搜索未知的空間，避免算法過早收斂。nbest只起補充作用，因此C3的取值通常較小，一般為0.1～0.5。

4）粒子群優(yōu)化算法在運行過程中，如果某粒子發(fā)現(xiàn)了一個當前最優(yōu)位置 ，其它粒子將迅速向其靠攏。如果該最優(yōu)位置是局部最優(yōu)點，粒子群就無法在解空間內重新搜索，因此，算法陷入局部最優(yōu)，出現(xiàn)了所謂的早熟收斂現(xiàn)象。實驗證明，粒子群優(yōu)化算法無論是早熟收斂還是全局收斂，粒子群中的粒子都會出現(xiàn)“聚集”現(xiàn)象。要么所有粒子聚集在某一特定位置，要么聚集在某幾個特定位置，這主要取決于問題本身的特性以及適應度函數(shù)的選擇。

為了定量描述粒子群的狀態(tài)，給出群體適應度方差的定義。

設粒子群的粒子數(shù)目為n，fi為第i個粒子的適應度，favg為粒子群目前的平均適應度，σ2為粒子群的群體適應度方差，則σ2可以定義為：

其中f為歸一化定標因子，其作用是限制σ2的大小，取值如下：

式（11）表明，群體適應度方差σ2反映的是粒子群中所有粒子的“聚集”程度。σ2越小，則粒子群的“聚集”程度就越大，若此時算法不滿足結束條件，而“聚集”將使群體失去多樣性陷入了早熟狀態(tài)，故當σ2＜C（C為一給定常數(shù)）時，進行早熟處理。

如果出現(xiàn)早熟現(xiàn)象，以目前得到的pg＝（pg1，pg2，…，pgn）作為二次載波的當前最優(yōu)解，在局部區(qū)域進行混沌優(yōu)化，從而引導粒子快速跳出局部最優(yōu)，加快收斂速度。

2.3 改進PSO的計算流程

1）采用混沌系列初始化粒子的位置及相關參數(shù)，使用模糊隨機模擬技術檢驗其可行性。

2）使用模糊隨機模擬技術［8］計算每個粒子的最優(yōu)位置pi＝（pi1，pi2，…，pin）為當前粒子所在的位置，并計算其對應的適應度pbest，并計算全局最優(yōu)位置為pg＝（pg1，pg2，…，pgn）當前群體中具有最優(yōu)適應度的粒子的位置，gbest為該粒子的適應度。

3）判斷算法收斂準則（根據(jù)實際問題來確定）是否滿足，如果滿足，轉向9）；否則執(zhí)行4）。

4）對于粒子群中的所有粒子，執(zhí)行如下操作：（1）根據(jù)式（9）和式（10）更新粒子的位置與速度并計算出其適應度；（2）如果粒子i的適應度優(yōu)于它對應的pbest，則pi＝（pi1，pi2，…，pin）設置為第i個粒子的新位置，并更新pbest；（3）如果群體中具有最優(yōu)適應度的粒子的適應度優(yōu)于gbest，則將pg＝（pg1，pg2，…，pgn）設置為該粒子的位置，并更新gbest。

5）判斷算法收斂準則是否滿足，如果滿足，執(zhí)行9）。

6）根據(jù)式（11）與（12）計算群體適應度方差σ2，并判斷是否成立，若成立則轉向7）進行混沌搜索；否則轉向4）。

7）設置混沌搜索的最優(yōu)解向量z＝pg，zbest＝gbest。

8）根據(jù)式（6）、（7）產(chǎn)生混沌變量，進行混沌搜索，得最優(yōu)解向量x及對應的適應值xbest，令pg＝x，gbest＝xbest轉3）。

9）輸出pg＝（pg1，pg2，…，pgn）及gbest，算法運行結束。

3 航線配船實例及結果分析

某沿海礦石運輸公司現(xiàn)有2.5萬噸級、3.5萬噸級和4.5萬噸級船舶分別為1艘、2艘和3艘。收集了72個干散貨船價格并將其轉換為4萬噸級的干散貨船船價，采用概率統(tǒng)計的方法進行隨機模擬，得出4萬噸級船的船價為符合對數(shù)正態(tài)分布的隨機數(shù)，概率密度為：

由參考文獻［9］可知其他噸位的船價概率密度大致為：

通過對沿海干散貨運輸?shù)恼{研及單船經(jīng)濟指標計算，得出航次數(shù)、運價、各航線上的運量等見表1。

表1 航次數(shù)、運價、各航線上的運量

采用本文提出的粒子群算法來求解仿真實例，令c1＝2.8，c2＝1.3，c3＝0.3，種群規(guī)模 N＝30，最大迭代次數(shù)為500次，約束因子λ＝0.729，混沌初始化100個可行解，混沌搜索500次。運行結果及目標函數(shù)收斂曲線見圖1。

圖1 兩種方法計算結果比較

可見改進后迭代156次即可達到最優(yōu)，而標準PSO迭代500次還未達到最優(yōu)，可見改進后PSO的有效性。

4 結束語

由于航線配船涉及的資金投入產(chǎn)出額很大，合理地對船舶進行組織優(yōu)化對航運企業(yè)來說意義重大。本文提出的改進的PSO，在原模型的基礎上，加入“第三個”極值，增加粒子獲得的信息量增大，同時采用約束因子控制速度的權重，并將混沌理論引入到PSO中，不但可以找到優(yōu)良的初始種群，也避免了早熟現(xiàn)象的出現(xiàn)，能夠保證算法的收斂且可以有效搜索不同的區(qū)域，從而得到高質量的解，實例也證明了該方法的有效性。

［1］張德洪，顧家駿.運輸船舶船型技術經(jīng)濟論證方法［M］.北京：人民交通出版社，1989.

［2］呂振肅，侯志榮.自適應變異的粒子群優(yōu)化算法［J］.電子學報，2004，32（3）：416-420.

［3］趙志剛，蘇一丹.帶自變異算子的粒子群優(yōu)化算法［J］.計算機工程與應用，2006，13：45-47.

［4］劉華鎣，林玉娥，張君施.基于混沌搜索解決早熟收斂的混合粒子群算法［J］.計算機工程與應用，2006，13：77-79.

［5］劉洪波，王秀坤，譚國真.粒子群優(yōu)化算法的收斂性分析及其混沌改進算法［J］.控制與決策，2006（6）：636-640.

［6］趙 強.改進的混沌優(yōu)化方法及其應用［J］.自動化與儀器儀表，2006（3）：90-92.

［7］高海昌，馮博琴，侯 蕓，朱 利.自適應變異的混合粒子群優(yōu)化策略及其應用［J］.西安交通大學學報，2006，6（40）：663～666.

［8］劉寶碇，趙瑞清，王 綱.不確定規(guī)劃及應用［M］.北京：清華大學出版社，2003.

［9］劉祖源，施金龍，毛筱菲.船舶貿(mào)易與經(jīng)營［M］.北京：人民交通出版社，1999.