改進(jìn)的粒子群優(yōu)化算法的研究與應(yīng)用

馮艷紅，于 紅，孫 庚

（1.大連海洋大學(xué) 信息工程學(xué)院，遼寧 大連116023；2.大連海洋大學(xué) 遼寧省海洋信息技術(shù)重點(diǎn)實(shí)驗(yàn)室，遼寧 大連116023）

0 引 言

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

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

1 漁港規(guī)劃問題分析及改進(jìn)的PSO 算法

1.1 問題定義

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

圖1 漁船駛?cè)霛O港避風(fēng)過程

漁港規(guī)劃問題定義為：從k個(gè)港中如何選取n （0＜n＜k）個(gè)港，使得m 艘船駛?cè)雗 個(gè)港的距離和為最小 （假設(shè)n個(gè)港的容量滿足m 艘船全部駛?cè)耄?/p>

將該問題抽象出如下數(shù)學(xué)模型

其中，P 為從向量P’中選取n個(gè)漁港構(gòu)成的向量，Z 是元素為zij構(gòu)成的矩陣。式 （1）中函數(shù)f（P，Z）表示船sj駛?cè)敫踦i的距離和；式 （2）～式 （4）是約束條件，式 （2）中pci表示港i已經(jīng)駛?cè)氲拇臄?shù)量，該值小于港pi的容量ai，式 （3）中pcn＋j表示每艘船只能駛?cè)胍粋€(gè)港，式（4）中zij＝1表示船sj駛?cè)敫踦i，zij＝0表示船sj不駛?cè)敫踦i；式 （5）為港pi與船sj間的歐幾里得距離。

該數(shù)學(xué)模型中港向量P 和船駛?cè)敫鄣木仃嘮 為決策變量，船向量S 為已知條件，該問題的解為函數(shù)f（P，Z）最小值時(shí)的向量P 的值。分析該數(shù)學(xué)模型，有以下特點(diǎn)：①zij為0－1變量，pi為離散型實(shí)數(shù)變量；②函數(shù)f 非線性；③符合無障礙離散型約束選址分配問題的特征；④NP 難，船駛?cè)敫鄣姆桨笧?“組合爆炸”問題，無法多項(xiàng)式時(shí)間求解。

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

1.2 改進(jìn)的PSO 算法定義

基本PSO 算法的進(jìn)化模型描述如下

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

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

由目標(biāo)函數(shù)得適應(yīng)度函數(shù)

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

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

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

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

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

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

定義4 速度間的加法：v1v2定義為逐次進(jìn)行v1操作和v2操作，由于速度具有方向性，該加法不滿足交換率，即v1v2?。絭2v1。最大速度vMax 的操作個(gè)數(shù)定義為粒子的維度。

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

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

定義7 位置間的減法：xΘx’結(jié)果為速度v，假設(shè)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 進(jìn)化公式如式 （11）和式 （12）所示

1.3 算法過程描述

算法：基于替換變異操作的改進(jìn)PSO 算法

輸入：x，v

輸出：gb

步驟1 初始化 （t＝1）

init（x，v）

init（pbi，gb）

步驟2 進(jìn)化 （t＝2－＞Iterratormax）

For（t＝2－＞Iterratormax）

根據(jù)式（11），式（12）和式（8）計(jì)算v（t）、x（t）和系數(shù)w（t）。

由式 （10），計(jì)算pbi（t）和gb（t）。

End

步驟3 判定進(jìn)化過程結(jié)束

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

其中Iterratormax為最大迭代次數(shù)，關(guān)于步驟2 中的式（10）的適應(yīng)度函數(shù)fitness（x）的算法描述如下：

該函數(shù)涉及到選址分配問題的分配子問題，該問題規(guī)模大，所以本文采用貪婪思想，用升序排列法，利用式（5）計(jì)算粒子 （港）到船的距離矩陣，采用O（nlogn）復(fù)雜度的、尾遞歸優(yōu)化的、隨機(jī)化快速排序算法對距離排序。在滿足式 （2）、式 （3）和式 （4）的約束條件下，采用已建港優(yōu)先駛?cè)朐瓌t：船優(yōu)先選擇已建的港駛?cè)耄溆嗟木徒側(cè)耄媒谱顑?yōu)解。

2 實(shí)驗(yàn)分析

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

圖2 某省漁港分布

圖3 某省漁船分布

漁港和漁船的坐標(biāo)計(jì)算結(jié)束后，實(shí)驗(yàn)首先在小規(guī)模數(shù)據(jù)上進(jìn)行，具體數(shù)據(jù)見表2，其中，粒子總數(shù)＝Cbn＝6，粒子維度＝a＋n＝6。

實(shí)驗(yàn)環(huán)境為 ThinkPad （Intel I5，CPU2.30GHz，RAM8GB，64位Windows 7），用Java語言實(shí)現(xiàn)該算。分別用傳統(tǒng)的組合漁港和漁船的所有進(jìn)港情況的算法和本文的改進(jìn)PSO 算法求解。比較求解結(jié)果的精確度和運(yùn)行時(shí)間見表3，假設(shè)漁港和漁船的坐標(biāo)數(shù)據(jù)已經(jīng)讀入內(nèi)存，所以運(yùn)行時(shí)間是算法的運(yùn)行時(shí)間，不包含讀取數(shù)據(jù)文件部分。運(yùn)行時(shí)間和準(zhǔn)確度為運(yùn)行30次的平均值。

表2 小規(guī)模實(shí)驗(yàn)數(shù)據(jù)

表3 小規(guī)模數(shù)據(jù)兩種算法的求解準(zhǔn)確度和運(yùn)行時(shí)間

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

表4 大規(guī)模實(shí)驗(yàn)數(shù)據(jù)

由于組合爆炸，得到的解空間為無窮大，傳統(tǒng)的方法無法在計(jì)算機(jī)可接受的時(shí)間和空間內(nèi)完成計(jì)算。本文改進(jìn)的PSO 算法在該規(guī)模上運(yùn)行時(shí)間約為1496s，準(zhǔn)確度可由小規(guī)模實(shí)驗(yàn)的結(jié)果推算。PSO 的實(shí)驗(yàn)結(jié)果為運(yùn)行30次取平均值。由表3和大規(guī)模數(shù)據(jù)上的改進(jìn)PSO 算法的實(shí)驗(yàn)數(shù)據(jù)可知，在小規(guī)模數(shù)據(jù)上，傳統(tǒng)的方法在時(shí)間和準(zhǔn)確度上都有一定的優(yōu)勢，本文的算法的準(zhǔn)確度在可接受范圍，時(shí)間在允許范圍。但在規(guī)模較大時(shí)，傳統(tǒng)的精確算法無法在計(jì)算機(jī)上解決該問題，改進(jìn)的PSO 算法具有明顯的時(shí)間優(yōu)勢和一定的精確度。

3 結(jié)束語

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

［1］LI Fang，F(xiàn)ENG 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］.大連海洋大學(xué)學(xué)報(bào)，2013，28 （5）：511－514.］

［2］YU Hong，F(xiàn)ENG 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）.［于紅，馮艷紅，李放，等.避風(fēng)型漁港規(guī)劃問題的啟發(fā)式算法研究 ［J］.大連海洋大學(xué)學(xué)報(bào)，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）.［吳仆.設(shè)施選址中的一些模型與算法 ［D］.南京：南京航空航天大學(xué)，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）. ［吳桂芳.物流配送中心選址優(yōu)化模型及算法研究 ［D］.武漢：武漢理工大學(xué)，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ìn)型粒子群算法及其在選址問題中的應(yīng)用 ［J］.計(jì)算機(jī)工程與應(yīng)用，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）. ［任子暉，王堅(jiān).加速收斂的粒子群優(yōu)化算法 ［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）.［李太勇，吳江，朱波，等.一種基于距離度量的自適應(yīng)粒子群優(yōu)化算法［J］.計(jì)算機(jī)科學(xué)，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）.［田軍，馬文正，汪應(yīng)洛，等.應(yīng)急物資配送動態(tài)調(diào)度的粒子群算法 ［J］. 系統(tǒng)工程理論與實(shí)踐，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ìn)自適應(yīng)粒子群算法的目標(biāo)定位方法 ［J］.計(jì)算機(jī)科學(xué)，2010 （10）：190－192.］