改进的粒子群优化算法的研究与应用

冯艳红，于 红，孙 庚

（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.］