基于粒子群算法的钢板倒垛优化

朱 军，王 跃，卓 杰

（连云港杰瑞深软科技有限公司，连云港 222006）

钢板堆场是船厂钢板原材料进料、分类堆放、保管、预处理和出料的场地，是整个总装化生产系统的物流和信息流的源头，与船厂所有工程及生产工程有联系，确保钢板的稳定物流是至关重要的，其信息化和自动化程度的高低对整个生产效率的提高有重要影响。

由于目前国内各大船厂的钢板堆场管理处在手工作业或半手工作业状态，钢板堆场存放的钢板品种多、量大、周期长；堆场的环境恶劣，钢板的标识、跟踪困难，并且大部分船厂没有对堆场进行科学、合理的规划，钢板的堆放随意性大，不能及时地将钢板进行定位以及不能快速地将钢板从堆场中按照最优化的路径进行出入库操作，因此亟需一种优化手段对其进行优化改善[1]。

工程实践中有很多目标优化问题，多目标优化问题中各目标之间通常相互制约，对其中一个目标优化经常以牺牲其它目标为代价，因此很难评价多目标问题解的优劣性。一般来说，多目标优化问题并不存在唯一最优解，其多个目标不可能同时达到最优。与传统的优化算法相比较，粒子群算法是一种简单有效的仿生算法，具有基于多点并行搜索的特性。

1 粒子群算法原理

粒子群算法，也称粒子群优化算法PSO，是近年来由J.Kennedy和R.C.Eberhart等开发的一种新的进化算法。PSO算法属于进化算法的一种，和模拟退火算法相似，它也是从随机解出发，通过迭代寻找最优解，通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法交叉和变异操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。

PSO同遗传算法类似，是一种基于迭代的优化算法。系统初始化为一组随机解，通过迭代搜寻最优值。同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。

2 钢板倒垛问题描述

船厂钢板管理系统针对造船厂钢板的出入库开发的系统软件，主要由系统管理、钢板管理以及工控网络安全等模块组成，通过扫描终端设备与外部交互，实现钢板的数据采集、传输与更新。系统架构如图1所示。

根据订单中钢板的规格和数量，从堆场中选取合适的钢板，由于堆场面积大，对位数量大，在钢板出入库过程中难免会出现所需要的钢板不在当前钢板堆垛的顶端，在此过程中首先需要先对上方的钢板进行倒垛作业。考虑到倒垛耗费能量大和时间等因素，采用基于规则的知识推理方法为倒垛钢板指定倒放堆位。钢板堆垛状态如图2所示。在钢板出库优化算法得到一组优化出库钢板集合，根据计算公式得到相应倒垛钢板集合和倒垛钢板的可选垛位集合为输入参数[2]，通过离散粒子群优化算法对倒垛问题空间进行优化，得到倒垛方案。

3 钢板倒垛模型建立

从钢板的出库整体流程分析，钢板的倒垛属于内层算法，从内往外一层一层地对钢板进行操作[3]，来减少钢板的出入库时间，提高钢板出入库效率。钢板出库算法流程如图3所示。

图3 钢板出库算法流程Fig.3 Steel plate library algorithm flow chart

其实倒垛问题可看作是约束条件下任务指派问题，可以建立数学模型[4]。定义出库钢板序列X=｛xi∣xi∈V，i=1，2，3…，N｝，其中 i表示钢板 xi出库的作业次序。τ为出库钢板中可行出库序列X的集合，τ中元素的数量由出库钢板在堆场中的分布情况确定。

图4 出库钢板作业次序Fig.4 Out of the library operating sequence

以Stagej中提取第j张出库钢板xj为例，如果xj不是位于钢板堆垛顶端，需要先对其上方的钢板进行倒垛作业。因此，Stagej实际上是包含提取xj以及由此产生的倒垛作业的作业决策子过程。

分析可知，第一组决策变量为指定的出库钢板集合，用向量X的形式表示为

式中：xi为从堆场中选择出的出库钢板，i=1，2，…，N，表示xi出库的次序。在堆场状态已知的情况下，由X可以确定倒垛钢板的集合M：

式中：mij为提取出库钢板xi需要移走的等j张倒垛钢板。为M中钢板指定倒放堆位，可得到另外一组集合Y：

式中：yij为rij的倒垛决策，rij为指提取出库钢板时，需要移走第j张倒垛钢板。

在倒垛过程中需要遵循几个原则：①倒垛钢板应避免将含有待出库钢板的垛位作为目标垛位；②目标垛位的选择要遵循堆场管理要求和作业规则。

基于钢板整体目标，需要有约束条件对其进行约束[5]：①选定的堆垛高度不能超过允许安全高度上限；②倒垛作业必须在一定范围内进行，即倒垛钢板当前堆位与倒垛位之间不能超过一定的距离。

4 钢板倒垛算法实现

PSO算法采用随机产生初始粒子，通过迭代找到最优解。在迭代过程中跟踪2个极值来更新自己，找到最优解。一个是粒子本身找到的最优解—个体极值（pbest）；另一个就整个种群找到最优解—全局最优解（gbest）。

粒子信息可用向量进行表示，第t代第i个粒子位置为

第t代第i个粒子速度：

因此粒子的位置和速度的更新方程为

式中：w为惯性系数，产生扰动的作用，防止算法早熟收敛；c1，c2为学习因子，分别调节向个体最好粒子和全局最好粒子方向飞行的最大步长；r1，r2为介于（0，1）之间的随机数。

开始初始化粒子群中粒子的速度和位置，初始化个体最优值与全局最优值，根据公式更新其速度和位置。由于在优化过程中，需要设定一个目标的最大函数，在迭代过程中，用其减去目标函数值（作业时间最小值），所得到的是粒子的适应度。

5 仿真倒垛结果及分析

为验证粒子群算法倒垛的可行性，使用Matlab对粒子群算法进行仿真，根据设定的初始粒子群和倒垛堆位集合，对钢板倒垛所用的时间进行了仿真，同时与未采用粒子群算法的人工钢板倒垛进行对比，在仿真图上迭代次数来看，迭代次数越多作业时间越少，说明选择的倒垛方案越优，在迭代次数达到一定次数时，作业时间趋于平缓，说明在设计时有个最优的终止条件，将迭代停止得到最优方案。适应度值仿真如图5所示。

图5 适应度值仿真Fig.5 Fitness simulation

此外Matlab对粒子群算法仿真和人工倒板决策进行对比，得出结论是使用粒子群算法的倒垛方案比人工倒板方案的效率更高、作业时间更短、收敛速度和寻优速度都更快。钢板倒垛方案比较结果如表1所示。

表1 钢板倒垛方案比较Tab.1 Comparison of steel plate stacking scheme

6 结语

在分析钢板堆场目前状况的情况下，基于钢板出库流程和优化过程的研究，以及解决钢板倒垛问题时存在诸多不足之处的基础上，本文对钢板出库过程中的钢板倒垛过程进一步研究，提出了适用于船厂钢板倒垛的粒子群算法，将钢板倒垛问题转化为求解最大值问题。通过仿真模拟与人工决策相对比，并改变仿真参数，得到钢板倒垛适应度值仿真模拟图，有效地提高了钢板倒垛的效率，减少作业时间，证明了该算法具有较好的实用性和高效性。

[1]杨乃忠.宝钢厚板生产物流分析及改进措施[D].沈阳：东北大学，2008.

[2]王龙.造船厂钢板出库计划并行嵌套优化算法研究[D].大连：大连理工大学，2011.

[3]张志英，王维泽，侯俊.船厂钢板堆场多时段作业计划优化[J].哈尔滨工程大学学报，2015（5）：638-643.

[4]郑武全，冯定忠，姜懿.钢板倒垛问题的一种顶层搜索算法[J].机械设计与制造工程，2013（2）：61-64.

[5]金淳，王广民，高鹏.造船厂钢板出库作业计划的建模及优化研究[J].工业工程与管理，2009（6）：12-17.