改進的粒子群優化算法的研究與應用

馮艷紅，于 紅，孫 庚

（1.大連海洋大學 信息工程學院，遼寧 大連116023；2.大連海洋大學 遼寧省海洋信息技術重點實驗室，遼寧 大連116023）

0 引 言

根據機動漁船的數量容易確定新建或改建的漁港的數量，那么，這些漁港的位置如何選取，才能在滿足漁船避風需求的同時，又使漁船進港避風時行駛的總距離最短，以達到獲得最好的經濟效益和社會效益的目的？本文針對該問題進行研究，從現有的二級及其以下級別的漁港中選取一定數目的漁港進行改建，升級為中心或一級漁港，不考慮新建的情況，本文研究的漁港規劃問題為：假設改建漁港的數目已確定，稱為規劃數量，如何從二級及以下級別的所有漁港中選取規劃數量的漁港為最終改建的漁港，使得漁船進港避風時行駛的總距離最小。

針對該問題，李放等對避風型漁港的選址方案進行了研究，并給出了漁港規劃問題數學模型，通過定義漁港規劃的特征向量，從擬建漁港中選取部分作為規劃漁港［1］，該作者主要用數學的方法分析了漁港的選址，但未采用計算機算法實現其數學模型；于紅等利用漁船就近避風的原則，提出了一種優先考慮最短回港時間的啟發式算法［2］，也是從擬建漁港中選取滿足建港容量系數的作為規劃漁港，解決了漁港的選址問題，但該方法按照容量系數來選取規劃的漁港，未考慮多個漁港的動態組合情況。本文將漁港規劃問題抽象為離散型選址分配問題，關于選址分配問題學者們提出了有效的解決方法。吳仆根據選址問題的特點劃分鄰域，采用一種新的變鄰域搜索方法進行求解，并且在搜索局部最優解時應用了一種基于自然界蜘蛛網模型的蛛網搜索，避免了一些不必要的搜索路徑，提高了算法效率［3］；吳桂芳采用非線性規劃和遺傳算法解決了物流配送中心的選址問題［4］；劉峰等利用PSO 算法解決基本的選址分配問題［5］，但解決的是連續型的選址分配問題。筆者結合漁港規劃問題的特點和以上學者們提出的解決選址分配問題的算法，采用改進的PSO 算法對該問題進行研究，實驗驗證了該算法較傳統的算法表現出較高的效率和準確性。

1 漁港規劃問題分析及改進的PSO 算法

1.1 問題定義

設P’＝ （pi｜i＝0，1，2，…，k），P’為所有漁港（包括已建的漁港和待改建的漁港）構成的向量，元素pi為第i個漁港；S＝ ｛sj｜j＝0，1，2，…，m｝，S 為所有漁船構成的向量，元素sj為第j艘船；ai（i＝0，1，2，…，k）為第i個港的容量，bj（j＝0，1，…，m）為第j艘船的需求，bj＝1。船和港的坐標采用平面直角坐標系坐標，pi（xi，yi）為第i個港的位置坐標，sj（uj，vj）為第j 艘船的位置坐標，dist（pi，sj）為港i與船j 間的距離。在臺風來臨時，漁船駛入漁港避風的過程如圖1 所示，例如，漁船sj駛入漁港p2。

圖1 漁船駛入漁港避風過程

漁港規劃問題定義為：從k個港中如何選取n （0＜n＜k）個港，使得m 艘船駛入n 個港的距離和為最小 （假設n個港的容量滿足m 艘船全部駛入）。

將該問題抽象出如下數學模型

其中，P 為從向量P’中選取n個漁港構成的向量，Z 是元素為zij構成的矩陣。式 （1）中函數f（P，Z）表示船sj駛入港pi的距離和；式 （2）～式 （4）是約束條件，式 （2）中pci表示港i已經駛入的船的數量，該值小于港pi的容量ai，式 （3）中pcn＋j表示每艘船只能駛入一個港，式（4）中zij＝1表示船sj駛入港pi，zij＝0表示船sj不駛入港pi；式 （5）為港pi與船sj間的歐幾里得距離。

該數學模型中港向量P 和船駛入港的矩陣Z 為決策變量，船向量S 為已知條件，該問題的解為函數f（P，Z）最小值時的向量P 的值。分析該數學模型，有以下特點：①zij為0－1變量，pi為離散型實數變量；②函數f 非線性；③符合無障礙離散型約束選址分配問題的特征；④NP 難，船駛入港的方案為 “組合爆炸”問題，無法多項式時間求解。

由于以上分析，該問題具有規模大、NP難、非線性等特點，無法 （或多項式時間內無法）用精確的算法求解。在群體智能算法中，PSO 算法有簡單、快速收斂和不易陷入局部極值等優點，很多學者對該算法進行研究，從提高收斂效率、跳出局部最優、使參數自適應進化過程、設計適應問題的適應度函數等方面對其進行改進［6－10］，本文在研究學者的改進PSO 算法基礎上，提出一種改進的PSO 算法，并設計了適用于漁港規劃問題的適應度函數。將該問題分為選址和分配兩個子問題，選址問題通過改進的PSO算法求解，進化過程中使用的適應度函數由分配子問題計算，由于分配子問題在PSO 算法迭代過程高頻次的調用，所以采用高效的可在nlogn 時間內求解的基于貪心思想的升序法求得近似最優解。

1.2 改進的PSO 算法定義

基本PSO 算法的進化模型描述如下

其中，式 （6）為粒子的速度進化公式，式 （7）為粒子的位置的進化公式，式 （8）為隨進化代數遞減的慣性系數公式。分析可知，數學模型中的向量P＝ （pi｜i＝0，1，2，…，n）即為粒子xi。目標函數根據式 （1）得

約束條件同式 （2）、式 （3）和式 （4）。

由目標函數得適應度函數

式 （6）～式 （10）中的符號含義見表1。

表1 式 （6）～式 （10）中的符號的含義

在漁港規劃問題中，將漁港分為兩類：坐標保持不變的已建的中心或一級漁港、從待改建的漁港中選取一定數量的作為規劃的改建漁港，所以粒子xi由兩部分構成：固有屬性和可變異屬性，固有屬性屬于第一類，可變屬性屬于第二類。在進化過程中，粒子構成的固有屬性部分不變異，可變屬性參與變異。由于是從已有的二級及以下漁港進行改建，所以粒子的數據為離散類型。結合本問題的特性，本文在深入研究了離散問題編碼、田軍等［8］對應急物資需求點和供應量的離散類型粒子的定義和Moayed等［9］提出的基于文化的PSO 算法的基礎上，受其啟發，為保持種群多樣性和粒子的適應性，對非全局最優粒子進行替換變異操作，下面給出替換變異操作、粒子的位置、速度及位置和速度間的運算的定義：

定義1 粒子的位置：x＝ （固有屬性，可變異屬性）＝ （x1，…，xi－1，xi，xi＋1，…，xn），其中x1，…，xi－1為固有屬性，xi，…，xn為可變異屬性。

定義2 替換變異操作：進化過程中，對非全局最優粒子的可變異部分與全局最優的粒子的可變異部分進行替換操作，由于替換變異操作限于兩個粒子間進行，所以這里采用2值替換，即交換數目為2，替換變異因子記為AM（xi，xe）。對于粒子的不變異部分，定義AM（xi，xe）的約束為xi＝xe。對粒子x＝ （x1，…，xi－1，xi，xi＋1，…，xn）進行替換變異操作AM （xi，xe）后結果為 （x1，…，xi－1，xe，xi＋1，…，xn）。

定義3 速度：一個或多個替換變異操作的y有序集合，即v＝ ｛AM1，AM2，…，AMn｝。

定義4 速度間的加法：v1v2定義為逐次進行v1操作和v2操作，由于速度具有方向性，該加法不滿足交換率，即v1v2！＝v2v1。最大速度vMax 的操作個數定義為粒子的維度。

定義5 速度對位置的操作：xv 定義為粒子x 按照速度v 中的替換變異操作按順序逐個進行操作，若v＝｛AM1，AM2，…，AMn｝，xv為先對x 進行AM1操作，結果為x’，再對x’進行AM2操作，以此類推。

定義6 速度的數乘：v2＝cv1，c為常數 （0＜c＜＝1），v2＝ ｛AM1，AM2，…，AM┌c＊｜v1｜┐｝，即選取前┌c＊｜v1｜┐個替換變異為新的速度，｜v｜為集合v 的長度，即度中包含的替換變異操作的數目。

定義7 位置間的減法：xΘx’結果為速度v，假設x＝ （x1，x2，…，xi，…，xn），x’＝ （x’1，x’2，…，x’i，…，x’n），則v＝ ｛AM1（x1，x’1），AM2（x2，x’2），…，AMi（xi，x’i），…，AMn（xn，x’n）｝

由以上定義給出離散域上的帶替換變異操作因子AM的PSO 進化公式如式 （11）和式 （12）所示

1.3 算法過程描述

算法：基于替換變異操作的改進PSO 算法

輸入：x，v

輸出：gb

步驟1 初始化 （t＝1）

init（x，v）

init（pbi，gb）

步驟2 進化 （t＝2－＞Iterratormax）

For（t＝2－＞Iterratormax）

根據式（11），式（12）和式（8）計算v（t）、x（t）和系數w（t）。

由式 （10），計算pbi（t）和gb（t）。

End

步驟3 判定進化過程結束

由式 （10）的兩代的差值小于閾值T 或達到最大迭代次數，則結束，否則返回步驟2。

其中Iterratormax為最大迭代次數，關于步驟2 中的式（10）的適應度函數fitness（x）的算法描述如下：

該函數涉及到選址分配問題的分配子問題，該問題規模大，所以本文采用貪婪思想，用升序排列法，利用式（5）計算粒子 （港）到船的距離矩陣，采用O（nlogn）復雜度的、尾遞歸優化的、隨機化快速排序算法對距離排序。在滿足式 （2）、式 （3）和式 （4）的約束條件下，采用已建港優先駛入原則：船優先選擇已建的港駛入，其余的就近駛入，得近似最優解。

2 實驗分析

港和船的坐標采用正軸等角圓柱投影，即墨卡托投影，將經緯度轉換為平面直角坐標系中的坐標。港的坐標取自某省漁港的坐標。漁船坐標模擬給出，根據給定經緯度范圍的多邊形，通過向量叉乘法求得凸多邊形的面積，根據面積和漁船總數采用均勻分布求得模擬的漁船的坐標，漁港和漁船的平面直角坐標系下的分布如圖2和圖3所示。

圖2 某省漁港分布

圖3 某省漁船分布

漁港和漁船的坐標計算結束后，實驗首先在小規模數據上進行，具體數據見表2，其中，粒子總數＝Cbn＝6，粒子維度＝a＋n＝6。

實驗環境為 ThinkPad （Intel I5，CPU2.30GHz，RAM8GB，64位Windows 7），用Java語言實現該算。分別用傳統的組合漁港和漁船的所有進港情況的算法和本文的改進PSO 算法求解。比較求解結果的精確度和運行時間見表3，假設漁港和漁船的坐標數據已經讀入內存，所以運行時間是算法的運行時間，不包含讀取數據文件部分。運行時間和準確度為運行30次的平均值。

表2 小規模實驗數據

表3 小規模數據兩種算法的求解準確度和運行時間

大規模的數據取自某省漁港規劃問題的數據，見表4。其中規劃的漁港總數n＝11座，已建漁港總數為19座，只需滿足漁船m＝33000艘的約70%駛入漁港即可。粒子總數計算方法：從未建漁港數目b＝78中隨機選取11座，共選擇8組，所以粒子總數＝8，粒子維度＝a＋n＝30。

表4 大規模實驗數據

由于組合爆炸，得到的解空間為無窮大，傳統的方法無法在計算機可接受的時間和空間內完成計算。本文改進的PSO 算法在該規模上運行時間約為1496s，準確度可由小規模實驗的結果推算。PSO 的實驗結果為運行30次取平均值。由表3和大規模數據上的改進PSO 算法的實驗數據可知，在小規模數據上，傳統的方法在時間和準確度上都有一定的優勢，本文的算法的準確度在可接受范圍，時間在允許范圍。但在規模較大時，傳統的精確算法無法在計算機上解決該問題，改進的PSO 算法具有明顯的時間優勢和一定的精確度。

3 結束語

文本以某省的漁港規劃問題為研究對象，抽象為選址分配問題，給出數學模型并用改進的PSO 算法進行求解，并針對該問題設計了高效的適應度函數，最終給出了一種可靠的漁港規劃的解決方法。但如果將該解決方法擴展到其它省份，PSO 的粒子維度過高，如何處理早熟問題？如果漁船需要繞行，如何利用有障礙約束選址分配模型解決該問題，都是本文下一步需要研究的問題。

［1］LI Fang，FENG Yanhong，LUAN Shuguang，et al.The reasonable distribution method for a central fishing harbor and level one fishing harbor in southeast coast of China ［J］.Journal of Dalian Ocean University，2013，28 （5）：511－514 （in Chinese）.［李放，馮艷紅，欒曙光，等.中國東南沿海中心漁港和一級漁港合理布局方法的研究 ［J］.大連海洋大學學報，2013，28 （5）：511－514.］

［2］YU Hong，FENG Yanhong，LI Fang，et al.Heuristic algorithm for planning problem of fishing port sheltered from typhoon ［J］.Journal of Dalian Ocean University，2012，27（4）：373－376 （in Chinese）.［于紅，馮艷紅，李放，等.避風型漁港規劃問題的啟發式算法研究 ［J］.大連海洋大學學報，2012，27 （4）：373－376.］

［3］WU Pu.Some facility location models and algorithms ［D］.Nanjing：Nanjing University of Aeronautics and Astronautics，2010：24－36 （in Chinese）.［吳仆.設施選址中的一些模型與算法 ［D］.南京：南京航空航天大學，2010：24－36.］

［4］WU Guifang.Study on the model and algorithm of logistics dis－tribution center location ［D］.Wuhan：Wuhan University of Technology，2009：32－56 （in Chinese）. ［吳桂芳.物流配送中心選址優化模型及算法研究 ［D］.武漢：武漢理工大學，2009：32－56.］

［5］LIU Feng，WANG Jianfang，LI Jinlai.Novel particle swarm optimization algorithm and its application in solving min－max location problem ［J］.Computer Engineering and Applications，2011，47 （14）：56－58 （in Chinese）. ［劉峰，王建芳，李金萊.改進型粒子群算法及其在選址問題中的應用 ［J］.計算機工程與應用，2011，47 （14）：56－58.］

［6］REN Zihui， WANG Jian.Accelerate convergence particle swarm optimization algorithm ［J］.Control and Decision，2011，26 （2）：201－206 （in Chinese）. ［任子暉，王堅.加速收斂的粒子群優化算法 ［J］.控制與決策，2011，26 （2）：201－206.］

［7］LI Taiyong，WU Jiang，ZHU Bo，et al.Distance measurement based adaptive particle swarm optimization ［J］.Computer Science，2010，37 （10）：214－216 （in Chinese）.［李太勇，吳江，朱波，等.一種基于距離度量的自適應粒子群優化算法［J］.計算機科學，2010，37 （10）：214－216.］

［8］TIAN Jun，MA Wenzheng，WANG Yingluo，et al.Emergency supplies distributing and vehicle routes programming based on particle swarm optimization ［J］.System Engineering－Theory ＆ Practice，2011，31 （5）：898－906 （in Chinese）.［田軍，馬文正，汪應洛，等.應急物資配送動態調度的粒子群算法 ［J］. 系統工程理論與實踐，2011，31 （5）：898－906.］

［9］Moayed Daneshyari，Gary G Yen.Cultural－based multiobjective particle swarm optimization ［J］.IEEE Transactions on Systems，Man，and Cybernetics—Part B：Cybernetics，2011，41 （2）：553－567.

［10］YAO Jinjie，HAN Yan.Research on target localization based on improved adaptive velocity particle swarm optimization algorithm ［J］.Computer Science，2010 （10）：190－192 （in Chinese）.［姚金杰，韓焱.基于改進自適應粒子群算法的目標定位方法 ［J］.計算機科學，2010 （10）：190－192.］