摘要:针对置换流水车间调度问题，提出了一种改进的粒子群算法进行求解。改进算法引入了判断粒子群早熟的方法，并在发现粒子群早熟后采用逆转策略对种群最优粒子进行变异，利用模拟退火思想概率接收新的最优粒子。种群最优粒子的改变会引导粒子群跳出局部极值的约束，从而克服粒子群的早熟状态。通过对置换流水车间调度问题中Car系列和Rec系列部分基准数据的测试，证明了该算法的有效性。
关键词:粒子群算法；多样性；局部收敛；置换流水车间调度
中图分类号: TP18 文献标志码:A
�
Improved particle swarm optimization for permutation flowshop scheduling problem
�
ZHANG Qi.liang�1,2�*，CHEN Yong.sheng�1，HAN Bin�2
1. College of Electronic and Information Engineering,Tongji University, Shanghai 200331,China�；��
2. College of Electricity and Information Engineering, Jiangsu University of Science and Technology, Zhangjiagang Jiangsu 215600, China
Abstract:
To solve permutation flowshop scheduling problem, an improved particle swarm optimization was proposed. Improved algorithm introduced a method to judge the prematurity state of the particle swarm, and used reversion strategy to mutate the best particle after the particle swarm being trapped in premature convergence, simulated annealing method was used to accept the new particle.The mutation for best particle can guide the particle swarm to escape from the local best value"s limit and overcome the particles" premature stagnation.The simulation results based on Car and Rec"benchmarks of permutation flowshop scheduling problem proved the effectiveness of the proposed algorithm.
To solve permutation flowshop scheduling problem, an improved particle swarm optimization was proposed. Improved algorithm introduced a method to judge the premature state of the particle swarm, and used reversion strategy to mutate the best particle after the particle swarm being trapped in premature convergence, and used simulated annealing method to accept the new particle. The mutation for best particle can guide the particle swarm to escape from the local best value�s limit and overcome the particles� premature stagnation. The simulation results based on Car and Rec benchmarks of permutation flowshop scheduling problem prove the effectiveness of the proposed algorithm.�Key words:
Particle Swarm Optimization (PSO); diversity; local convergence; permutation flowshop scheduling
�
0 引言 �
置换流水车间调度问题(Permutation Flowshop Scheduling Problem，PFSP)是一类经典的加工调度问题。该问题通常被描述为�n个工件在m台不同的机器上加工，每个工件有m道工序，每道工序都要在不同的机器上加工，每个工件在机器上的加工顺序相同，每台机器一次在某一时刻只能加工一个工件，每台机器加工的各工件顺序相同。问题中每个工件在每台机器上加工的时间已知，问题的目标是求出工件加工顺序，使得按照该加工顺序加工各工件时所对应的总完工时间C��max�最小。当m�>2时，该问题已被证明是NP.难问题�［1］。�
解决PFSP的方法大致可以分为三类:一类是精确方法，主要有列举法、分支界定法、动态规划法；一类是启发式方法，主要有NEH法；另一类是智能优化方法，主要有遗传算法(Genetic Algorithm,GA)、模拟退火(Simulated Annealing，SA)算法、蚁群算法、粒子群算法等。�
粒子群算法(Particles Swarm Optimization,PSO)是由Kennedy和Eberhart博士于1995年提出的一种基于群体的进化算法�［2］，算法原理源于对鸟群行为的仿真。同其他智能算法相比，粒子群算法简单、易实现，需要调整的参数较少，目前被广泛应用于函数优化、神经网络训练、模糊系统控制以及其他领域�［3］。但PSO 算法存在的一个主要问题是在优化过程中易出现早熟收敛现象，导致粒子多样性降低，易陷入局部最优，难以寻找到全局最优解。多种文献对粒子群算法进行了
改进，并应用到了流水车间调度问题，取得了较好的成效。文献［4］将粒子群算法与迭代贪心算法结合，利用迭代贪心算法中的作业毁坏和构造操作对粒子进行变异，降低群体发生早熟的可能;文献［5］提出一种新的基于群体多样性控制的PSO 算法，算法使粒子在收缩状态下充分搜索，在发散状态下能够飞离群体的聚集位置，不断的收缩―发散过程保证了群体能在较大的空间进行搜索，减少了粒子群算法的早熟收敛现象;文献［6］采用惯性权重线性递减粒子群算法对置换流水车间调度问题进行了优化，并针对提高求解置换流水车间调度问题对粒子群惯性权重的取值、粒子群种群数量、粒子位置和速度的初始化以及粒子位置和速度的限制范围等几个方面展开实验研究;文献［7］将粒子群算法与模拟退火算法相结合，避免粒子群算法出现早熟现象，并把结合后的算法应用到求解流水车间调度问题;文献［8］采用混沌序列初始化粒子位置,以增强搜索多样性，并在算法中嵌入有效判断早熟停滞的方法，一旦检测到早熟迹象，便随机地选择最优解任意一维的分量值，用一个随机值取代它，以扰乱粒子的当前搜索轨迹，使其跳出局部最优，克服了粒子群早熟收敛现象;文献［9］通过分解搜索空间、对种群进行变异、与模拟退火算法结合等方法，提出了可改变的进化搜索算法(Modified Evolutionary Programming,MEP),并将算法应用于PFSP，得到了较好的解。�
上述文献对基于粒子群算法解决流水车间调度问题具有重要的借鉴意义。为了进一步避免粒子群陷入局部最优，提
高算法的寻优精度，本文在借鉴文献［8］的基础上，提出了一种控制粒子多样性的方法。当判断粒子群趋于收敛时，对全局极值进行变异，从而改变粒子的速度向量，导致粒子的寻优轨迹发生变化，进而跳出局部极值的约束。通过对流水车间调度问题中部分Car类问题和Rec类问题的仿真实验表明：当粒子群陷入局部最优时，能通过该方法跳出局部极值的约束，算法寻找最优解的能力要比一般的粒子群算法优越，运行效果令人满意。�
2.3 粒子早熟判断方法及改进�
本文判断粒子出现早熟的方法为：当粒子的全局极值P�g在连续G代后没有改变或者改变很小但还不满足终止条件时，认为粒子已经处于暂时停滞状态，粒子出现了早熟。�
当粒子陷入局部最优时，若无外力的作用其很难逃出局部极值的约束。为了使粒子能够跳出局部极值，本文对能够指导粒子群运行方向的P�g进行变异，变异后粒子群会在新的P�g的引导下改变方向，继续寻找问题最优解，从而避免了粒子重复收敛于一点的现象。图1为粒子群陷入局部最优的情况，粒子都运行在局部极值附近，在局部极值的约束下很难跳出。图2为对P�g进行变异后的情况，P�g由位置1跳变到位置2，粒子方向也随着P�g的改变而发生变化，从而跳出局部极值。经过多次跳变，有利于提高寻优速度和寻找到最优解的可能。本文对P�g采用逆转策略进行变异，在P�g的n个加工工件中随机产生两个工件j1, j2,假定j1