车间生产调度优化中改进微粒群算法的应用

徐海波，仲梁维，龚文露

（上海理工大学 机械工程学院，上海 200093）

0 引言

作业车间调度问题（Job-shop scheduling problem，JSP）通常理解为运用多台机器进行生产加工，加工包含多个工件，每个工件又包含多道工序，同时每道工序在指定的机器上进行加工。在过去相当长的时间中，算法得到了充分的研究，涌现出了不同的算法与理论，如人工神经网络与模拟退火算法等等。不过由于算法各自的缺陷以及车间生产作业调度的复杂性，标准的算法很难满足求解的需求。为充分发挥各种算法的优势，取长补短，将算法进行有效地结合，可以大大提高算法的求解效率，因而混合算法应运而生，成为算法优化的一大亮点。

1 混合微粒群（PSO）算法设计

1.1 改进的微粒群算法原理

微粒通过跟踪个体极值Pbesti（微粒本身所找到的最优解）和全局极值Pgbest（整个种群目前找到的最优解）来不断更新自己的速度和位置，更新公式如下：

其中：vk为微粒的速度向量；k为迭代次数；xk为当前微粒的位置；w为惯性权重，决定了对微粒当前速度的继承，w一般取（0，1）之间的随机数；c1、c2表示群体的认知系数，使微粒具有自我总结和向群体中优秀个体学习的能力，c1、c2取（0，2）之间的随机数；r1和r2为（0，1）之间的均匀分布的随机数。

1.2 改进的PSO算法设计策略

微粒群算法最初用于求解连续性优化问题，具有较好的全局收敛性。不过在求解离散组合优化问题时，往往具有参数敏感、收敛速度慢等特性，因此需要对混合PSO算法做如下改进：

（1）PSO算法对于初始解具有较强的鲁棒性，是因为PSO算法具有很好的全局收敛性。但在实际生产中，由于优化模型的复杂程度大小不一，这就导致了算法的收敛对初始解具有很大的依赖。本文提出优化选择机制，既保证了初始解的多样性，又提高了算法的收敛性能。

（2）标准PSO算法中通常采用基于编码点的交叉方式，在复杂JSP中具有较慢的收敛速度。本文提出了一种遗传算法的整段交叉思想，在一定范围内提高了收敛速度。同时为了避免PSO算法因收敛速度过快而产生早熟现象，本文提出了一种遗传算法的变异思想。结合遗传算法的变异和交叉思想很好地提高了算法的收敛性。

（3）为保证种群全局最优解和自身最优解的突跳性，以及算法能跳出全局最优，混合微粒群算法采用模拟退火算法的Metropolis抽样准则来作为设定全局最优解与自身最优解的接受准则。

（4）本文的混合PSO算法以机器加工时间最小为优化目标。采用优化选择机制，将目标适应度值按从小到大的顺序排序，并按照该顺序选择出种群。

1.3 混合PSO算法种群变异设计

混合PSO算法粒子的位置更新涉及每个粒子的历史最好位置Pbesti、群体当前最好位置Pgbest和平均最优值Mbest，运用遗传算法的变异和交叉操作，其表达式如图1所示。

图1 变异及交叉图

变异操作：假设父代向量为x，随机产生2个交换点i和j，交换向量x位于交换点i和j上的元素，其他元素不变。

交叉操作：假设父代向量为x和y，经过交叉操作产生子代向量z。首先，随机产生2个交换点i和j，将向量x位于交换点i和j之间的元素复制到向量z的相应位置；其次将向量x上其余元素按照它们在向量y上出现的先后顺序依次填入向量z的位置。粒子的位置更新流程如图2所示。

1.4 模拟退火操作

混合PSO算法在标准PSO算法的基础上引入模拟退火操作的Metropolis抽样准则，参照目标函数，比较微粒与微粒自身最优解之间的适应度的大小，按照Metropolis抽样准则接受比微粒自身最优解大的解，使自身最优解具有一定的突跳性。

图2 微粒位置更新流程图

2 混合PSO算法的求解流程

结合混合PSO算法的求解过程，给出混合PSO算法的求解流程图，如图3所示。

图3 混合PSO算法求解流程

图3中，Pbesti（t）表示微粒i经过t次迭代后相对目标函数适应度最小的一代微粒；Pgbest（t）表示t次迭代后所有微粒中相对目标函数适应度最优的微粒；xi（t）表示微粒i经过t次迭代时的微粒。

3 混合PSO求解实例

3.1 对FT06问题的求解

求解种群为10个粒子，计算代数为1 500代，连续计算20次，通过MATLAB 7.0软件求解，结果显示混合PSO能很好地解决FT06问题，它能9次取得其最优解55，其余解大多都很接近最优解55，而且平均用时达到6s左右，收敛速度比标准PSO快。

3.2 对LA01问题求解

求解种群为50个粒子，计算代数为1 500代，连续计算20次，通过MATLAB 7.0软件求解，结果显示混合PSO能很好地解决LA01问题，混合PSO算法求解20次中有15次取得最优解666，平均收敛代数为550，平均用时达到55s左右，收敛速度比标准PSO快。

4 结语

本文采用优化选择机制，同时引入模拟退火算法中的Metropolis抽样准则，使算法能跳出全局最优，并具有一定的突跳性；引入遗传算法的交叉变异操作，提高了算法的收敛速度，也避免了早熟现象，使微粒更好地向全局最优与自身最优靠近；取长补短，提出了一种混合PSO算法。实例验证混合PSO算法在求解车间生产作业问题中具有一定的收敛性和有效性。

［1］Wang H.Flexible flow shop scheduling：optimum，heuristics and artificial intelligence solutions［J］.Expert Systems，2005，22（2）：78-85.

［2］王万良，吴启迪.生产调度智能算法及其应用［M］.北京：科学出版社，2007.

［3］吴大为，陆涛栋，刘晓冰，等.求解作业车间调度问题的并行模拟退火算法［J］.计算机集成制造系统，2005，11（6）：847-850.

［4］王万良，吴启迪，宋毅.求解作业车间调度问题的改进自适应遗传算法［J］.系统工程理论与实践，2004（2）：58-62.

［5］玄光男，程润伟.遗传算法与工程设计［M］.北京：科学出版社，2000.

［6］周明，孙树栋.遗传算法原理及应用［M］.北京：国防工业出版社，1999.

［7］潘全科，朱剑英.一类解决作业车间调度问题的遗传退火算法［J］.聊城大学学报，2005，18（1）：20-23.

［8］Reeves C.A genetic algorithm for flow shop sequencing［J］.Computers and Operations Research，1995，22（1）：5-13.