一种新的混合粒子群算法求解置换流水车间调度问题

针对粒子群算法易早熟的缺点,提出了一种结合迭代贪婪(IG)算法的混合粒子群算法。算法通过连续几代粒子个体极值和全局极值的变化判断粒子的状态,在发现粒子出现停滞或者粒子群出现早熟后,及时利用IG算法的毁坏操作和构造操作对停滞粒子和全局最优粒子进行变异,变异后利用模拟退火思想概率接收新值。全局最优粒子的改变会引导粒子跳出局部极值的约束,增加粒子的多样性,从而克服粒子群的早熟现象。同时,为了使算法能更快找到或逼近最优解,采用了循环迭代策略,在阶段优化结果的基础上,周而复始循环迭代进行求解。将提出的混合粒子群算法应用于置换流水车间调度问题,并在问题求解时与几个具有代表性的算法进行了比较。结果表明,提出的算法能够克服粒子群早熟,在求解质量方面优于其他算法。

New hybrid particle swarm optimization algorithm for permutation Flow-Shop scheduling problem

For the problem that the PSO is easy to be trapped in local optimal, this paper put forward a hybrid PSO algorithm which combined the IG algorithm. The algorithm judged the particles' status by the change of particles' individual and global best value in continuous generations, and used destruction and construction operation of IG algorithm to mutate the relating particle and the global best position after discovering that the particle was at a standstill or the particle swarm was trapped in local optimal. The new particles being mutated were accepted according to the simulated annealing theory. The mutation of global best particle could guide the particle swarm to escape from the local best value's limit and increase the diversity of particles, which avoided the particle's premature stagnation. Simultaneously, the algorithm adopted cycle iterative method in order to get or approach the best result quickly. It searched the best solution step by step on the basis of stage optimization. The paper applied the hybrid PSO algorithm to the permutation Flow-Shop scheduling problem, and compared it with the other representative algorithm. The result shows that the hybrid PSO algorithm can avoid the particle's premature stagnation effectively and the algorithm is better than other algorithms in the quality of searching the best solution.