苏绍娟，王丽铮，王呈方

（武汉理工大学 交通学院，武汉430063）

航线配船主要是解决多船型在多条航线上的合理配置问题，目的在于充分利用现有的条件和资源，以最少的投入，换取最大的效益。由于在航运市场中存在很多不确定的因素，所以建立不确定性的航线配船模型符合实际情况。

粒子群优化算法（PSO）是一种新兴的群智能优化算法，相对遗传算法、模拟退火等算法而言，PSO更简单有效，并已得到众多学者的重视和研究，许多实际应用非常成功。但它同许多智能方法一样存在早熟问题。在航体配船，由于存在随机、模糊现象，使问题更加复杂，计算量非常大，所以提高计算速度很重要。根据不确定航线配船数学模型的特点及粒子群算法本身的特征，本文对粒子群算法进行了相应的改进。

1 数学模型

在若干港口之间长期从事大宗货物运输的定线运输船队，其船舶运行组织具有很强的规律性和相对的稳定性。我国沿海的石油、矿石、煤炭等大宗工业物资的运输就属于这种情况。科学的配置船舶会带来巨大的效益。

1.1 目标函数

以总利润最大化为目标函数：即收入减去营运费用再减去闲置费用的最大值［1］。

式中：Aij——i型船在j航线上的单船年利润；

DWi——船舶的载重吨；

ij——i船在j航线上的年航行次数；

Yj——j航线的运价；

DHYij——i船在j航线上的单航次耗油量；

RJ——燃油单价；

——船价；

α——与收入有关的成本占收入的比例；

α1——与船价相关的成本占船价的比例；

α2——船舶的闲置费占船价的百分比。

1.2 约束条件

1）船舶在该航线上的运量不能大于货运需求量，即

2）保证各航线上的某型船数量与该船的闲置量之和与船队中拥有的这种船的数量Ait相等。

3）变量非负性约束

式中：xij——决策变量，在j航线上配置的i型船数量；

pi——决策变量，i型船的闲置量；

——i型船舶在j航线上营运时的单船年运量；

——j航线上货运需求量；

Ai——船队中拥有的j型船数量；

K——船型总数；

G——航线总数。

需要说明的是ij是模糊量，Yj和是随机变量，所以A P～ij是同时含有模糊和随机的不确定量。即目标函数是含有模糊和随机的不确定量。由于航次数是三角模糊量，所以船舶的年货运量同样是模糊数，约束实质上是模糊约束。

2 粒子群算法的改进

粒子群算法是继蚁群算法之后又一群体智能算法，在粒子群算法中，每个粒子根据自己的飞行经验和同伴的飞行经验来调整自己的飞行速度和方向从而寻找问题的最优解。它是一种随机搜索算法，而且是从多个初始点开始进行搜索的，比较容易快速地接近或达到最优解。

2.1 混沌算法

混沌变量产生的方法有多种，选用较为广泛的Logistic映射，即：

将混沌变量zik映射到优化变量取值区间成为xi，n+1：

二次载波的数学模型为：

式中：λ——时变参数zt的衰减因子，λ≺1，通常取λ∈［0.95，0.999］；

x＊——第一阶段搜索到的最优解；

zt——时变参数。

这样就可以实现在次优值的双侧邻域内通过逐步缩小混沌变量遍历的区域范围进行混沌细搜索，从而找到全局最优值。

对于时变参数zt的初始值的选择问题，模仿模拟退火算法初始退火温度的思路来确定，即先按混沌寻优方法的第一阶段搜索N个可行解，并记录这N个可行解中所对应的目标函数值的最大最小值fmax和fmin，选择参数P（0＜P＜1），于是按下式确定zt的初始值z0：z0＝

2.2 粒子群算法的改进

本文对标准粒子群算法进行了以下改进［2-7］。

1）初始化。

采用混沌系列初始化粒子的位置，既不改变粒子群优化算法初始化时所具有的随机性本质，又利用混沌提高了种群的多样性和粒子搜索的遍历性。根据公式（6）和 （7）取足够多的混沌序列点数，选择性能较好的N个可行解组成初始群体。

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

1999年Clerc对算法的数学研究证明，采用约束因子（constriction factor）控制速度的权重，能够保证算法的收敛且可以有效搜索不同的区域，从而得到高质量的解。

3）加入“第三个”极值，即在从第k代向第k+1代飞行的过程中，粒子除追随个体极值pbest和全局极值gbest外，还追随从粒子群中随机选取的某个粒子的个体极值nbest进行速度更新。则粒子群数学模型为：

式中：c3——非负常数；

r3——［0，1］之间的随机数；

l——在粒子群中随机选取的某个粒子。

为保证收敛性，c1+c2+c3＞4。

在粒子的速度迭代公式中增加nbestt后，由pbest，gbest，nbest三者共同向下一代提供信息，粒子获得的信息量增大，从而可能更快的找到优化解。同时类似于GA中的变异操作，提供扰动信息，增加了粒子的多样性，从而可使粒子跳出局部最优区域，使算法搜索未知的空间，避免算法过早收敛。nbest只起补充作用，因此C3的取值通常较小，一般为0.1～0.5。

4）粒子群优化算法在运行过程中，如果某粒子发现了一个当前最优位置 ，其它粒子将迅速向其靠拢。如果该最优位置是局部最优点，粒子群就无法在解空间内重新搜索，因此，算法陷入局部最优，出现了所谓的早熟收敛现象。实验证明，粒子群优化算法无论是早熟收敛还是全局收敛，粒子群中的粒子都会出现“聚集”现象。要么所有粒子聚集在某一特定位置，要么聚集在某几个特定位置，这主要取决于问题本身的特性以及适应度函数的选择。

为了定量描述粒子群的状态，给出群体适应度方差的定义。

设粒子群的粒子数目为n，fi为第i个粒子的适应度，favg为粒子群目前的平均适应度，σ2为粒子群的群体适应度方差，则σ2可以定义为：

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

式（11）表明，群体适应度方差σ2反映的是粒子群中所有粒子的“聚集”程度。σ2越小，则粒子群的“聚集”程度就越大，若此时算法不满足结束条件，而“聚集”将使群体失去多样性陷入了早熟状态，故当σ2＜C（C为一给定常数）时，进行早熟处理。

如果出现早熟现象，以目前得到的pg＝（pg1，pg2，…，pgn）作为二次载波的当前最优解，在局部区域进行混沌优化，从而引导粒子快速跳出局部最优，加快收敛速度。

2.3 改进PSO的计算流程

1）采用混沌系列初始化粒子的位置及相关参数，使用模糊随机模拟技术检验其可行性。

2）使用模糊随机模拟技术［8］计算每个粒子的最优位置pi＝（pi1，pi2，…，pin）为当前粒子所在的位置，并计算其对应的适应度pbest，并计算全局最优位置为pg＝（pg1，pg2，…，pgn）当前群体中具有最优适应度的粒子的位置，gbest为该粒子的适应度。

3）判断算法收敛准则（根据实际问题来确定）是否满足，如果满足，转向9）；否则执行4）。

4）对于粒子群中的所有粒子，执行如下操作：（1）根据式（9）和式（10）更新粒子的位置与速度并计算出其适应度；（2）如果粒子i的适应度优于它对应的pbest，则pi＝（pi1，pi2，…，pin）设置为第i个粒子的新位置，并更新pbest；（3）如果群体中具有最优适应度的粒子的适应度优于gbest，则将pg＝（pg1，pg2，…，pgn）设置为该粒子的位置，并更新gbest。

5）判断算法收敛准则是否满足，如果满足，执行9）。

6）根据式（11）与（12）计算群体适应度方差σ2，并判断是否成立，若成立则转向7）进行混沌搜索；否则转向4）。

7）设置混沌搜索的最优解向量z＝pg，zbest＝gbest。

8）根据式（6）、（7）产生混沌变量，进行混沌搜索，得最优解向量x及对应的适应值xbest，令pg＝x，gbest＝xbest转3）。

9）输出pg＝（pg1，pg2，…，pgn）及gbest，算法运行结束。

3 航线配船实例及结果分析

某沿海矿石运输公司现有2.5万吨级、3.5万吨级和4.5万吨级船舶分别为1艘、2艘和3艘。收集了72个干散货船价格并将其转换为4万吨级的干散货船船价，采用概率统计的方法进行随机模拟，得出4万吨级船的船价为符合对数正态分布的随机数，概率密度为：

由参考文献［9］可知其他吨位的船价概率密度大致为：

通过对沿海干散货运输的调研及单船经济指标计算，得出航次数、运价、各航线上的运量等见表1。

表1 航次数、运价、各航线上的运量

采用本文提出的粒子群算法来求解仿真实例，令c1＝2.8，c2＝1.3，c3＝0.3，种群规模 N＝30，最大迭代次数为500次，约束因子λ＝0.729，混沌初始化100个可行解，混沌搜索500次。运行结果及目标函数收敛曲线见图1。

图1 两种方法计算结果比较

可见改进后迭代156次即可达到最优，而标准PSO迭代500次还未达到最优，可见改进后PSO的有效性。

4 结束语

由于航线配船涉及的资金投入产出额很大，合理地对船舶进行组织优化对航运企业来说意义重大。本文提出的改进的PSO，在原模型的基础上，加入“第三个”极值，增加粒子获得的信息量增大，同时采用约束因子控制速度的权重，并将混沌理论引入到PSO中，不但可以找到优良的初始种群，也避免了早熟现象的出现，能够保证算法的收敛且可以有效搜索不同的区域，从而得到高质量的解，实例也证明了该方法的有效性。

［1］张德洪，顾家骏.运输船舶船型技术经济论证方法［M］.北京：人民交通出版社，1989.

［2］吕振肃，侯志荣.自适应变异的粒子群优化算法［J］.电子学报，2004，32（3）：416-420.

［3］赵志刚，苏一丹.带自变异算子的粒子群优化算法［J］.计算机工程与应用，2006，13：45-47.

［4］刘华蓥，林玉娥，张君施.基于混沌搜索解决早熟收敛的混合粒子群算法［J］.计算机工程与应用，2006，13：77-79.

［5］刘洪波，王秀坤，谭国真.粒子群优化算法的收敛性分析及其混沌改进算法［J］.控制与决策，2006（6）：636-640.

［6］赵 强.改进的混沌优化方法及其应用［J］.自动化与仪器仪表，2006（3）：90-92.

［7］高海昌，冯博琴，侯 芸，朱 利.自适应变异的混合粒子群优化策略及其应用［J］.西安交通大学学报，2006，6（40）：663～666.

［8］刘宝碇，赵瑞清，王 纲.不确定规划及应用［M］.北京：清华大学出版社，2003.

［9］刘祖源，施金龙，毛筱菲.船舶贸易与经营［M］.北京：人民交通出版社，1999.