《计算机应用研究》|Application Research of Computers

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

New hybrid particle swarm optimization algorithm forpermutation Flow-Shop scheduling problem

免费全文下载 (已被下载 次)  
获取PDF全文
作者 张其亮,陈永生
机构 同济大学 电子与信息工程学院,上海 200331
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2012)06-2028-03
DOI 10.3969/j.issn.1001-3695.2012.06.006
摘要 针对粒子群算法易早熟的缺点, 提出了一种结合迭代贪婪(IG)算法的混合粒子群算法。算法通过连续几代粒子个体极值和全局极值的变化判断粒子的状态, 在发现粒子出现停滞或者粒子群出现早熟后, 及时利用IG算法的毁坏操作和构造操作对停滞粒子和全局最优粒子进行变异, 变异后利用模拟退火思想概率接收新值。全局最优粒子的改变会引导粒子跳出局部极值的约束, 增加粒子的多样性, 从而克服粒子群的早熟现象。同时, 为了使算法能更快找到或逼近最优解, 采用了循环迭代策略, 在阶段优化结果的基础上, 周而复始循环迭代进行求解。将提出的混合粒子群算法应用于置换流水车间调度问题, 并在问题求解时与几个具有代表性的算法进行了比较。结果表明, 提出的算法能够克服粒子群早熟, 在求解质量方面优于其他算法。
关键词 粒子群算法;迭代贪婪算法;早熟收敛;流水车间调度
基金项目 国家“十一五”科技支撑计划资助项目(115-04-YK-048)
本文URL http://www.arocmag.com/article/01-2012-06-006.html
英文标题 New hybrid particle swarm optimization algorithm forpermutation Flow-Shop scheduling problem
作者英文名 ZHANG Qi-liang, CHEN Yong-sheng
机构英文名 College of Electronic & Information Engineering, Tongji University, Shanghai 200331, China
英文摘要 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.
英文关键词 particle swarm optimization(PSO); iterated greedy(IG); premature stagnation; Flow-Shop scheduling
参考文献 查看稿件参考文献
 
收稿日期
修回日期
页码 2028-2030,2034
中图分类号 TP18
文献标志码 A