求解置换流水车间调度问题的改进遗传算法  

Improved genetic algorithm for permutation flow-shop problem

作　　者：涂雪平[1] 施灿涛[1] 李铁克[1] 

机构地区：[1]北京科技大学经济管理学院,北京100083

出　　处：《计算机工程与应用》2009年第36期50-53,70,共5页Computer Engineering and Applications

基　　金：国家自然科学基金No.70771008;No.70371057~~

摘　　要：针对置换流水车间调度问题的基本特征和传统遗传算法易早熟的缺陷,设计了改进遗传算法来求解此问题。采用NEH和Palmer启发式算法进行种群初始化,以提高初始解的质量;根据Metropolis准则对染色体进行选择操作,避免陷入局部最优;在变异过程中引入禁忌算法,避免迂回搜索;在算法迭代过程中引入了保优机制,避免丢失优秀染色体的基因信息;采用自适应终止准则,以保证解的质量。基于典型Benchmark算例的仿真实验结果表明,算法在求解质量和收敛速度方面明显优于NEH算法和种群经过初始优化的传统遗传算法。According to the features of permutation flow-shop problem and the premature defect of GA,an improved GA for this problem is proposed.In the process of proposed GA,the NEH and the Palmer heuristics are used to initialize the population to improve the quality of the initial solutions,the Metropolis rule is employed in chromosome selection for avoiding fall into local optimum,and the tabu-search algorithm is embedded to get away from circuitous search.In order to save the genetic information of excellent chromosomes,an＂elite mechanism＂is presented to remember good genes,and the best solutions will be saved in each run.The auto-adaptive termination rule is suggested to further improve solution quality.At last,the effectiveness of the improved GA is verified based on some benchmark problems.The results show that the solution quality and the convergence speed are better than the NEH and original GA initialized by heuristic algorithm.

关 键 词：置换流水车间调度 遗传算法 METROPOLIS准则 禁忌搜索 保优机制 

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