一种求解Job Shop调度问题的改进遗传算法  

Improved Genetic Algorithm for Job Shop Scheduling Problems

作　　者：沈镇静[1,2] 郑湃[2,3] 李家霁[2,3] 

机构地区：[1]中国科学院研究生院,北京100049 [2]中国科学院沈阳计算技术研究所,沈阳110171 [3]常州数控技术研究所,常州213164

出　　处：《计算机系统应用》2012年第8期57-62,共6页Computer Systems & Applications

基　　金：江苏省科技攻关项目(BE2010070)

摘　　要：传统遗传算法在求解Job Shop调度问题时存在收敛速度慢,易于早熟的缺点。在病毒遗传算法(VEGA)和灾变遗传算法的基础上提出了一种带有灾变因子的病毒遗传算法(IVEGA-C)。该算法在传统遗传算法的基本结构上加入了病毒感染操作和灾变操作,病毒感染操作实现了同代个体之间横向传递进化信息,灾变操作采用灭绝操作。正是这种改进加快了遗传算法的收敛速度,避免了早熟现象和陷入局部最优解。通过仿真实验验证了IVEGA-C算法在解决Job Shop调度问题中的性能优于传统GA算法和VEGA算法。最后给出了应用该算法的一个实例。Traditional Genetic Algorithm for solving Job Shop Scheduling Problems has some shortcomings such as slow convergence and easy to bring immature convergence. On the basis of Virus Evolutionary Genetic Algorithm （VEGA） and Genetic Algorithm with Catastrophe factor, an improved Virus Evolutionary Genetic Algorithm with Catastrophe factor （IVEGA-C） was proposed. IVEGA-C adds virus infection operation and catastrophe operation to the basic structure of traditional Genetic Algorithm. Virus infection operation passes the evolutionary information between the populations in the same generation and an improved extinction operation was used as the strategy of catastrophe. The improved algorithm speeded up the convergence rate of the Genetic algorithm, avoided the premature phenomena and to fall into local optimal scheduling solution. The simulation results verify that IVEGA-C on solving the Job Shop Scheduling Problems is better than traditional Genetic Algorithm and VEGA. At last we give an example of using this algorithm to solve scheduling problems in our real-world.

关 键 词：JOB Shop调度问题 病毒遗传算法 灾变算子 收敛性 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]