基于多目標粒子群算法的船舶主尺度優化設計研究

侯 磊

（海軍駐武漢四三八廠軍事代表室，武漢 430060）

1 引 言

船舶主尺度優化設計是船舶總體設計中最基本、最重要的工作之一。主尺度的選擇直接關系到船舶的總體性能和經濟性。尋找一種好的優化設計方法無疑有重要意義。由于船舶航行環節的多變性和船舶本身技術性能的復雜性，采用傳統的設計方法獲得多目標優化的最佳船體主尺度是相當困難的。許多作者探討了進化算法在船舶設計中的應用[1-4]，這些研究大多都是基于經典方法將多目標問題轉化為單目標后求解。由于事先設定了偏好信息，縮減了搜索空間，將不可避免地遺漏更好的可行解，而系統地改變先驗值并不能保證Pareto最優解能夠在前沿上均勻分布。

粒子群優化（Particle Swarm Optimization,PSO）是一種新興的進化計算技術，它是由Kennedy和E-berhart[5]受鳥群覓食行為的啟發于1995年提出的。PSO保留了基于種群的全局搜索策略，采用簡單的速度位移模型，它特有的記憶能力使其可以動態跟蹤當前的搜索情況以調整其搜索策略，具有較強的全局收斂能力和魯棒性，且不需要借助問題的特征信息。PSO作為一種高效的并行搜索算法，非常適于對復雜環境中優化問題的求解。1999年，Mooro和Chapman[6-7]首先在他們未公開發表的文稿中提出擴展PSO求解多目標優化問題，稱之為MOPSO算法，隨后出現了基本框架結構大致相同的二十多種MOPSO算法[7]。目前，MOPSO算法已經運用到運籌學、電力、化工、機械、經濟學、圖像處理等領域，研究內容主要集中在參數選擇、拓撲的結構形式、多種群結構、自適應算法以及理論和應用等方面。

對于多目標優化問題，當Pareto最優解集求出來之后，還需要挑選出最后的折衷解或最優解。這是一個給對象系統做出全局性、整體性評價的工作[8-9]。

本文提出了解決多目標優化問題的兩階段求解思路，將多目標粒子群優化算法與決策方法結合起來，討論了船舶主尺度論證中的優化和決策問題。對于多目標優化問題，采用基于Pareto占優的多目標粒子群算法（σ-MOPSO）求出多目標問題的最優解，然后采用距離理想解最近的決策方法，對Pareto最優解集合給出了排序。文中討論了一艘散裝船概念設計階段主尺度確定的實例。

2 多目標粒子群優化和求解

對于n個目標函數，l個優化變量，I個等式約束和J個不等式約束的多目標最小化優化問題，通常可以表述為如下形式：

在多目標優化中，由于目標之間相互沖突，很難找到一個真正意義上的最優解，而是存在一系列解，其特點為至少存在一個目標優于其他所有的解，這樣的解稱之為非支配解，或Pareto解，這些解的集合即為Pareto最優解集。求解多目標優化問題的主要任務是求得該優化問題的Pareto最優解集。

在PSO方法中，粒子（又稱為微粒）在超微搜索空間飛行，假設一個微粒群有m個微粒組成，每個微粒代表D維搜索空間中的一個解，其中第i個微粒的空間位置為xi=（xi1,xi2,…,xiD），i=1,2,…,m;第i個微粒所經歷的最優位置稱為其個體歷史最優位置，記為pi=（pi1,pi2,…,piD）,又稱個體最優微粒或者pbest；同時，每個微粒還具有各自飛行速度vi=（vi1,vi2,…,viD）。所有微粒經歷過的最優位置稱為全局最優位置，記為pg=（pg1,pg2,…,pgd），又稱為全局最優微粒、領導（leader）、領導微粒或 gbest。 在單目標PSO算法中，微粒的更新公式和速度更新公式分別為：

其中，C1和C2分別是學習認知因子和社會認知因子，w為慣性因子。r1，r2∈ [0, 1]，是服從均勻分布的隨機變量。wvi（t）是微粒先前的飛行公式，又稱為微粒動能，表明微粒在搜索空間中移動的能力，其值越大，越有利于全局搜索，其值小則利于局部搜索，即通過參數w進行控制。C1r1（pi-xi（t ））是認知學習部分，表明微粒自身經驗對于當前搜索傾向的線性吸引程度，并受到C1r1的隨機調整，是對微粒所積累經驗的利用。C2r2（pg-xi（t ））是社會認知部分，表示微粒學習其他微粒經驗的過程，這里也是一種線性吸引，體現了微粒間信息的共享和社會協作。pg的定義與種群拓撲結構直接相關。

對于多目標問題，通常需要考慮Pareto解的數量、解的均勻性以及精確性。由于多目標優化問題的解集為非占優解構成，因此對（2）式的擴展用于多目標優化問題求解，還需要考慮的地方包括：a）兩個粒子之間如何判斷哪個更優；b）個體極值和全局極值的選取；c）如何保持粒子的多樣性；d）是否施加對粒子的擾動等問題。許多作者對這些問題進行了研究。Moore和Chapman基于Pareto占優，采用環形拓撲結構，當要選擇一個個體最優時，從其列表中任意選擇一個即可[6]。Ray和Liew[10]結合進化技巧采用最近鄰居密度估計方法提高多樣性，根據密度值采用輪盤選擇模式選擇領導。Coello等[11]采用外部檔案保持每個粒子的飛行經驗。Li[12]則將多目標遺傳算法—NSGA II[13]的主要機制合并到了PSO方法。Lechuga和Rowe[14]借用小生境技術進行PSO指導搜索，并將粒子沿Pareto前沿擴散。Raquel和Naval[15]適用Pareto占優和擁擠距離方法選擇全局最優粒子。

本文采用Mostaghim和Teich提出的一種選擇領導的σ-MOPSO方法[16]。它可以改進MOPSO方的收斂性和多樣性。該方法賦予群和外部檔案中每個粒子一個σ值，對于兩個目標函數的情況，可以定義f2=α f1上所有點的σ值為：

圖1給出了兩個目標空間中粒子的σ值示意圖。

為選擇粒子的領導，每個粒子選擇外部檔案中與其σ值最接近的粒子作為其領導，但σ的使用使得PSO的選擇壓力更高，在某些困難情況下導致早熟收斂。該方法在決策變量空間上使用了擾動算子RT。該算子相當于進化算法中的變異算子，它可以給每個粒子當前位置附加一個任意的擾動

RT是]間的任意隨機值，以保證粒子在任意方向中的位置更新的可能性。σ-MOPSO方法的流程示意圖見圖2。

對于多目標優化問題的求解，還需要加上一個決策環節。當Pareto最優解集求出來之后，還需要根據設計者的偏好挑選出最后的折衷解或者最優解。現行有很多的決策方法，本文采用距離理想解最近的方法獲得Pareto解的排序。

為了使各個目標函數盡可能小，可以先分別求出各目標函數的最小值，然后讓各目標盡量接近各自的極小值來獲得原來問題的解。可以采用如下函數定義和理想解的距離值[19]：

3 數值算例和討論

本文考慮6個決策變量、3個目標函數和14個約束的散裝貨船多目標船型論證優化問題[17-18]，計算模型見附錄。

a.設計變量的選擇

選擇船長L、船寬B、型深D、吃水T和方形系數CB等5個主尺度和航速Vk（kn）作為設計變量，即

b.約束條件的確定

本例子共有如下14個約束條件：

一共有3個目標函數：運輸成本Tc最小，空船重量Ls最小和年貨運量Ac最大。

3.1 單目標優化計算

這里首先使用序列二次規劃方法（SQP）對單個目標函數分別計算，并且和文獻[18]中共軛梯度方法的結果進行了比較，見表1。對于最小運輸成本設計情況，本文和文獻[18]有細微的偏差，其余兩個情況的結果均相同。

表1 單目標優化計算結果比較Tab.1 Comparison among single criterion optimization results

3.2 多目標粒子群優化

σ-MOPSO 方法的參數設置為：w=0.4，RT=0.07，C1=2，C2=2,種群為200，迭代次數300。外部存檔集大小200。一共得到200個Pareto最優解。這些Pareto解用散點表示在圖3～5中。從多目標優化問題的定義來說，這些200個解都能夠作為問題（1）的解。這是多目標優化問題解的特點，它能夠給設計者更多的選擇空間。

從圖中可以看到，所有Pareto解的分布是比較均勻的。

采用和每個極值距離最短的決策方法，利用表1中的結果，根據距離由近至遠得到前5個備選方案，如表2所示。選取排序第1的方案（定義為A方案）作為最終的滿意解，它用“■”標注在圖3～5中。

圖中還用實線給出了兩個目標函數之間的Pareto前沿。

表2 多目標優化解的排序結果Tab.2 Ranking results for multiobjective optimization

從圖3～5中可以看出，方案A的空船重量最小，運輸成本比較低，但是年貨運量最小。從圖4，5可以得知，A方案位于Pareto前沿上，說明方案A在Ls－Ac，Ls－Tc兩兩目標之間是很滿意的解。但是，A在圖3中卻離開Pareto前沿比較遠。這正是Pareto解的特征，即不可能在每個目標值上均是最優的。

值得注意的是，不同的決策方法會得到完全不同的最終滿意解。這里給出的決策方法，是基于單個設計者或者課題組的決策意見，對于實際的船舶設計，還需要考慮船東等更多人的意見。

4 結 語

本文針對船型主尺度多目標優化設計問題，提出了兩階段求解的方法，即先基于多目標粒子群方法求出Pareto最優解集，再使用距離極值最近的排序方法對Pareto最優解給出了排序。對散裝貨船概念設計階段的主尺度優化算例結果表明，本文的兩階段求解方法，能夠迅速、客觀有效選擇合理的船舶主尺度。在船型方案論證中應用良好，能夠給設計者和船東更多的選擇余地。

這種兩階段綜合方法也能夠用在船舶設計的其他領域。

[1]柳存根,裘泳銘,姚震球,林杰人.遺傳進化算法在船舶初步設計中的應用[J].上海交通大學學報,2000,34(1):41-45.

[2]李文龍,譚家華.基于最小偏差法的集裝箱船型優化[J].中國造船,2002,43(4):1-5.

[3]李文龍,譚家華.集裝箱船主尺度全局最優化的混沌算法[J].中國造船,2003,44(1):11-16.

[4]楊 啟,黃小勇,譚家華,王呈方.基于最優Pareto集的船舶出塢拖輪配置優化[J].中國造船,2005,46(2):69-74.

[5]Kennedy J,Eberhart R C.Particle Swarm Optimization[C]//Proc.IEEE Internation Conference on Neural Network.IEEE Service Center,Piscataway,1995:1942-1948.

[6]Chapman J M R.Application of particle swarm to multiobjective optimization[R].Department of Computer Science and Software Engineering,Auburn University,1999.

[7]Reyes-Sierra M,Coello C A C.Multiobjective particle swarm optimizers:A survey of the state-of-the-art[J].International Journal of Computational Intelligence Research,2006,2(3):287-308.

[8]陳衍泰,陳國宏,李美娟.綜合評價方法分類及研究進展[J].管理科學學報,2004,21(2):69-79.

[9]徐玖平,吳 巍.多屬性決策的理論與方法[M].北京:清華大學出版社,2006.

[10]Tapabrata R,Liew K M.A swarm metaphor for multiobjective design optimization[J].Engineering Optimization,2002,34(2):141-153.

[11]Coello C A C,Pulido G T,Lechuga M S.Handling multiple objectives with particle swarm optimization[J].IEEE Trans.Evolutionary Computation,2004,8(3):256-279.

[12]Li Xiaodong.A non-dominated sorting paticle swarm optimizer for multiobjective optimization[C]//Proceedings of Genetic and Evolutionary Computation Conference(GECCO’2003),2003:37-48.

[13]Deb K,Pratap A,Agarwal S,et al,A fast and elitist multiobjective genetic algorith:NSGA-II[J].IEEE Trans on Evolutionary Computation,2002,6(2):182-197.

[14]Leghuga M S,Rowe J.Particle swarm optimization and fitness sharing to solve multiobjective optimization problems[C]//Congress on Evolutionary Computation(CEC’2005),2005:1204-1211.

[15]Raquel C R,Naval P C.An effective use of crowding distance in multiobjective particle swarm optimization[C]//Proceedings of the Genetic and Evolutionary Computation Conference(GECCO’2005),2005:257-264.

[16]Mostaghim S,Teich J.Strategies for finding good local guides in multiobjective particle swarm optimization(MOPSO)[C]//Proceedings of the 2003 IEEE Swarm Intelligence Symposium,2003:26-33.

[17]Sen P,Yang J B.Multiple criteria decision support in engineering design[M].Springer,London,1988.

[18]Parson M G,Scott R L.Formulation of multicriterion design optimization problems for solution with scalar numerical optimization methods[J].Journal of Ship Research,2004,48(1):61-76.

[19]胡毓達.實用多目標最優化[M].上海:上海科學技術出版社,1988.