求解同顺序加工调度问题的一种改进遗传算法

An Improved Genetic Algorithm to Solve Permutation Scheduling Problem

同顺序加工调度问题是一类典型的 NP-hard问题 ,具有广泛的工程背景 ,该问题的研究具有重要的理论意义和工程价值 ,同时开发有效的优化算法一直是该领域的热门课题 .结合启发式和随机方法产生初始解 ,对种群进行分解并用多种交叉操作进行进化 ,在整体替换后用模拟退火的 Metropo-lis抽样过程代替变异操作 ,本文提出了一种改进的遗传算法 ,算法保证了初始种群一定的质量和多样性 ,多种交叉操作有利于丰富搜索行为 ,在温度控制下的抽样过程成为概率可控的变异操作且搜索行为一定程度上可控 .基于典型算例的仿真研究验证了改进遗传算法的有效性和较好的初值鲁棒性 ,其优化质量大大优于传统遗传算法和著名的 NEH启发式方法 .

Permutation scheduling is a typical NP-hard problem with wide engineering background, and it is of importance with respect of theory and application and it is always a hot topic in such field to develop effective optimization algorithm. Generating initial solutions by heuristic and random methods, evoluting the separated population with multi-crossover, substituting mutation with Metropolis sampling process of simulated annealing after population updating, this paper proposes an improved genetic algorithm. The algorithm guarantees the quality and diversity of initial population, and enriches searching behavior by multi-crossover, as well as behaves mutation with controllable probability by controlling the temperature so as to control the searching behavior to some extent. Simulation based on benchmarks demonstrates the effectiveness and robustness on initial solutions of the improved genetic algorithm, whose optimization qualities are fairly superior to those of classic genetic algorithm and the famous NEH heuristic.