微粒群优化算法在装备制造业的应用方向研究

摘要： 为了优化和创新造船模式，本文分析了一种新型算法——微粒群优化算法（PSO）的原理，并探索其在大型钢结构领域方向的应用，简要设想了分段堆放优化、水火弯板工艺参数和车间生产作业调度优化等三个方面，达到省时省资源和能量，以促进制造业更好的发展。

Abstract： To optimize and bring forth new ideas into shipbuilding mode， the article analyze the principle of a new algorithm—particle swarm optimization（PSO） and envisage it applied into large steel， envisaging the optimization of subsection placement，line-heating process parameter and Job-shop Scheduling， take less time and energy， to promote the better development of Chinese manufacturing industry.

关键词： 微粒群算法；装备制造；分段堆放；水火弯板；车间调度

Key words： PSO；equipment manufacturing industry；Subsection Placement；line-heating；Job-shop Scheduling

中图分类号：U673.2 文献标识码：A 文章编号：1006-4311（2012）30-0036-03

0 引言

大型装备制造是一个兼容制造和建造的复杂的生产过程。在金融危机的影响下，为了适应工业和科技的进步，为了市场和战场的战斗需要，也为了提高生产效率和改善作业环境，不断优化和创新制造流程和制造技术就成为装备制造业永恒的主题。本文意在分析一种新型优化算法——微粒群优化算法在大型装备制造业界的应用。

1 微粒群算法

20世纪90年代初，产生了一种模拟自然生物群体为主的优化技术，Dorigo等从生物进化的机理中受到启发，通过模拟蚂蚁的寻径行为，提出了蚁群优化方法。微粒群算法（Particle swarm optimization，PSO）由Kennedy和Eberhart于1995年提出，是一种模拟鸟群寻找食物的社会行为的随机群体进化算法[1]，这些研究可以称为群体智能。通常单个自然生物并不是智能的，但是整个生物群体却表现出处理复杂问题的能力，群体智能就是这些团体行为在人工智能问题中的应用。微粒群优化最初是处理连续优化问题的，目前其应用已扩展到组合优化问题。由于其简单、有效的特点，已经得到了众多学者的重视和研究。

起初人们知识不够丰富的时候就利用它解决简单的一些线性问题，后来人们拓宽知识面后就想办法求优化问题，在这个里面就发现微粒群算比传统方法更好的地方。第一，微粒群算法可以描述目标函数，传统优化方法做不到，同时可以比较灵活地设定目的函数，使算法被广泛地应用；第二，算法自己有比较好的特性，依据这个特性把全局和局部收敛进行平衡。第三，算法可以与其他的进化算法融合。那么有些学者把一些算子，比如说选择算子、变异算子等加入PS0算法，选择算子有这种作用，能够把最好的粒子直接性地复制到下一代，这样就能确保最好的粒子。交叉算子有这样的作用使一对一对的粒子之间相互交换各自的信息资料，然后都具有向新的区域飞行的能力。另一种想法是把PS0中的速度思想加到进化规划中，加快了进化规划算法的速度，从而来进行指导变异操作[2]。

1.1 算法原理 PSO算法与其他优化方法类似，都是基于群体的演化算法，根据群体对环境的适应度将群体中的个体移动到好的区域，然而它不像其他演化算法那样对个体使用演化算子，而是将每个个体看作D维搜索空间中的一个没有体积的微粒，在搜索空间中以一定的速度飞行。这个速度根据它本身的飞行经验以及同伴的飞行经验进行动态调整。第i个微粒表示为Xi=（xi1，xi2，…，xiD）和速度Vi=（vi1，vi2，…，viD），它经历过的最好位置（有最好的适应值）记为Pi=（pi1，pi2，…，piD），也称为pbest。体所有微粒经历过的最好位置的索引号用符号g表示，即Pg，也称为gbest。对每一代，其第d 堆（1≤d≤D）根据如下方程变化[2]

vid=wvid+c1rand（）（pid-xid）+c2Rand（）（pgd-xid）

xid=xid+vid

其中：w为惯性权重（inertia weight），c1和c2为加速常数（acceleration constants），rand（）和Rand（）为两个在[0，1]范围内变化的随机函数。

1.2 PSO算法基本流程（如图1所示）

2 PSO算法在大型钢结构制造领域方面的应用设想

以最为典型的大型装备船舶结构制造为例，现代制造模式的三个要素初步可总结为生产流程、生产组织和运行机制，其中“船体分道作业流程”又是整个现代造船模式应用研究的重中之重，如图2所示。结合微粒群算法的特点，本文设想PSO算法可以应用于造船作业的某些领域。

2.1 分段堆放位置的优化 由于国内分段制造场地的排列比较混乱，降低了场地利用率，也不易进行管理，所以找到一种优化方法对于改善这一现状是必要的。

总段组合的原则是使高空作业低空化，低空作业平地化，从而提高预舾装率。如图3所示，为尽量减少船坞合拢所需的作业时间，根据分段堆放的要求，它们应放置在交通运输方便且吊车能够起吊的地方。为了方便总段组合作业，给定需要组合的分段一个排序π；令k=1，取出π中的前2个分段，对它们进行吊装，确定使吊装这些分段的最大完成时间的最小的排序，并作为当前序列；令k=k+1，取出π中接下来的2个分段并视作一个块，将第k个块整体分别插入到当前序列中各个可能的位置，并尝试调换同一个块中两个分段的次序，最终确定使吊装这些分段的最大完成时间最小所对应的序列，并作为当前序列；重复刚刚的步骤，知道π中所有的分段均得到新的堆放位置。按照这一新的方案堆放分段将对缩短制造周期会起到很大的作用。

2.2 水火弯板工艺参数优化 水火弯板是很有特色、但难度却很大的一种曲面钢板成型工艺。它是通过平板或单向曲率板局部加热和收缩变形来实现双向曲度成型要求的。在确定水火弯板加工参数时，是以确定的区域内能量消耗最少为优化目标的。如何优化水火弯板工艺参数，使其既满足曲板整体形状所需要的局部变形量，又要达到加热的总能量最少也是一项值得研究的课题。

文献[4]对坐标轮换法进行了改造，考虑了局部能量的合理分配，给出了水火弯板加工方案。其基本原理是在解决非线性多变量函数整数规划的优化问题时可以用坐标轮换法把一个多变量问题转化为一系列较少变量的问题来求解，即先将一部分变量暂设为定值或取极限约束，以剩余变量为目标变量进行优化求解，然后再对暂设为定值或取极限约束的变量进行优化，最终确定优化方案。这种优化方法的工艺参数设计的思想是依据曲板整体形状所需要局部变形的理论计算结果，在局部输入其变形所需要的能量。其能量函数为：

E=f（s，lh，t）（1）

式中：s是加热线间距；lh是加热线长度；t是加热时间。

因为水火弯板板边变形量是s的单值函数，加热线条数k必须取整，且可由s惟一确定。将s暂设为定值，则局部能量消耗只与每条焰道的加热时间t成正比，所以目标函数为：

minE=■ti（2）

根据文中所述的约束条件和某实船板算例得出优化的焰道布置方案可以节省能量在2%～5%之间，图4（a）和（b）分别表示某实船板水火加工成型工艺参数的经验方案和优化方案。

由上述优化方案来看，微粒群优化算法也可尝试应用于水火弯板的工艺参数优化中。水火弯板参数的设置是以能量消耗最少为目标的，而能量的消耗是由加热线间距s、加热线长度lh和加热时间t来决定。其能量函数还是定为：

E=g（s，lh，t）（3）

根据以下约束条件[5，6]建立各焰道加热线长度矩阵L、各焰道加热时间矩阵T和各焰道能量消耗矩阵E：

L=[lh1 lh2 … lhk] （4）

T=[t1 t2 … tk] （5）

E=[E1 E2 … Ek] （6）

其中k为焰道数，且与s成反比关系。

①速度约束

当12mm≤hp

当14mm≤hp

当18mm≤hp

②焰道长度约束

0.15Bp

350mm

③收缩量约束

Ac=a0Ra1pla2hsa3ta4

Lc=b0Rb1plb2hsb3tb4

式中：Rp为横向曲率半径。

总消耗能量为：E=■Ei

根据s、v、lh在约束内的不同取值，对应的k、ti也各不相同，每个焰道消耗的能量也随着变化，从而总能量也在变化。与PSO算法相关连，就可以得出一目标函数，进而转化为求解消耗能量最小值时的最佳参数排序问题。由此得出微粒群优化算法是可以应用于水火弯板的工艺参数优化相关方面。

2.3 车间生产作业调度优化 车间生产作业调度理论作为企业生产计划与控制理论的重要组成部分，提升企业竞争力的一个重要途径是实现对该问题的有效求解。车间生产作业调度研究的目的是对生产资源进行优化配置，是根据已知各生产作业的加工时间及加工设各，并在满足约束条件的限制下，使生产资源得到优化配置，以使生产作业的某项指标（所有机器的完工时间、工件流程时间、延迟时间及生产成本等）达到最优。车间生产作业调度一般可以描述为优化作业的加工顺序，使生产资源得到优化配置的过程。因此，对于该问题的研究一直是企业界与学术界关注的焦点问题。其中主要考虑的是最小化作业的最大完成时间。

近年来，PSO算法逐渐用于对车间生产作业调度（JSP）问题的求解，文献[7]中做了系统的阐述分析。

JSP问题用于描述a个工件在b台机器上加工，每个工件包含a道工序，且已知对应每道工序在各自对应机器上的加工时间。车间生产作业调度问题满足的约束条件：

①每个工件的下一道工序只能在上一道工序完成后才能开始加工；

②每个工件都须经过埘台机器加工；

③每台机器在同一时刻只能加工某一工件的一道工序；

④每个工件加工的优先级相同。

结合上述对JSP问题已知条件的描述，根据已知各工件的加工工序，构建了对应工件加工的工序排列矩阵X；根据各工序加工时间，构建各工件的加工时间矩阵T；根据机器加工工件的不同，构建了各机器对应加工工序的调度矩阵DX，文献[7]是以所有机器完工时间最短作为优化目标。不同的调度方案满足的约束条件数学表达式为：

Sij+tij？燮Si（j+1）（7）

式（7）中表示工件i的第j道工序的起始加工时间，i=1，2，…，a；j=1，2，…，b。它意义在于表明工件i只有在上一道工序加工完成后才能加工下一道工序。

Sijk+tij？燮Sghk或Sijk？叟Sghk+tgh（8）

式（8）中Sijk表示工件i的第j道工序在机器k上加工的起始时间，Sghk表示工件g的第h道工序在机器k上加工的起始时间，tij与tgh是对应工序的加工时间，其中i≠g。它的意义在于确保机器在某一时刻只能加工一个工件。

对于一个调度方案，结合己知各工序的加工时间与约束条件，可以计算出各机器完成所有工件加工的结束时间。依据最短加工时间这一优化目标，车间生产作业调度问题的可以描述为根据不同的调度矩阵DX求解各机器最大的完工时间，并使其最小化，JSP问题优化目标函数可以定义为：

F（DX）=Min（Max（TE））（9）

式（9）中TE表示在满足约束的条件下，对应一种调度方案每一台机器结束加工的时间。

造船企业的生产过程实质上是一个“物的流通”过程，大型装备即是制造物料流动、组合的最终结果。我国装备制造业存在着重生产、轻流通的现象，忽略了对车间生产物流的合理组织，生产流程设备布置不合理，导致物流量过大，制造效率低下，车间生产作业调度问题也一直是装备制造现代化研究的热点之一。

相比与大多数行业车间流水线似的生产特点，PSO算法应用于其中能有个标准化流程，但由于造船企业具有产品品种多、变动性大、车间调度的工作量大而复杂等特点，从而导致生产过程稳定性差缺乏柔性。国内大型装备制造业的车间一般由加工车间、平直车间、曲面车间和模块车间组成，每个车间都要各自的加工加工流程，标准也各不相同，而车间内部零件、部件、分段的尺寸、形状、精度要求也是随着船种类、大小、客户要求、规范限制而变化，难以有一个统一化、规模化的生产，所以将PSO算法应用于其中有一定的难度，图5为弯曲板切割加工流程图。不过PSO算法的提出也为车间的生产作业调度问题提供了一种新途径，相信在不久的将来，当现代装备制造业全面进入数字化时代时，微粒群优化算法可以成为解决车间调度问题的一种方便有效的方法。

3 总结与展望

微粒群算法是一种相当简单的算法，只需很少的代码和参数，但在各种问题的求解与应用中却展现了它的特点和魅力。微粒群算法自提出以来引起了国际上很多领域众多学者的关注和研究，近些年来已经开始应用于物流、维修保障、工程项目、系统设计、机器人技术等领域并取得了一定的成绩，但还没有涉及到大型装备制造业。本文详细阐述了算法的由来和原理，初步设想PSO算法可以应用于大型船体钢结构的分段堆放优化、水火弯板参数设置和车间作业调度优化之中，当然还有很多作业都可以将其引入，这有待于后续的深入研究。2008年，压载舱涂层新标准—PSPC的出台对涂层本身和人素质的要求又达到了一个新的高度，势必会影响制造周期。我们在考虑如何提高工艺水平的同时还应该从其它方向研究怎样减小制造的周期，以平衡PSPC带来的影响。

参考文献：

[1]J Kennedy， R Eberhart. Particle Swarm optimization [C]. In： Proceedings of IEEE International Conference on Neural Networks. Piscataway， NJ： IEEE Press， 1995： 1944-1948.

[2]谢晓峰，张文俊，杨之廉.微粒群算法综述.清华大学微电子学研究所，2003.

[3]刘幸.改进微粒群算法及在优化中的应用.武汉工程大学硕士学位论文，2009.

[4]刘玉君，王东，纪卓尚，邓燕萍.水火弯板工艺参数优化设计.大连理工大学学报，2000.

[5]董守富，孙振烈.船体外板水火加工成形研究[A].中船总科技报告[R].大连：大连理工大学，1997.

[6]张笛夫.水火弯板回归模型的建立及分析[D].大连：大连理工大学，1997.

[7]葛茂根.基于微粒群优化的车间生产作业调度方法研究. 合肥工业大学硕士学位论文，2006.

[8]熊鹰.微粒群算法的若干改进及应用.武汉理工大学硕士学位论文，2006.

[9]安静，杨东升，汪镭，康琦，吴启迪.一种微粒群智能寻优动态评价模式.南京理工大学学报，2009.