一种求解作业车间调度问题的文化遗传算法

An Effective Cultural Genetic Algorithm for Job Shop Scheduling Problem

针对传统遗传算法缺乏有效指导,容易陷入局部极值的缺点,提出了以一种采用种群空间和信仰空间的双层进化结构进行寻优的作业车间调度算法。该算法针对调度问题的特点,以遗传算法为主群体空间,利用优良调度方案的知识信息构成信仰空间。为充分利用父代个体的优良特征加速收敛,算法采取不同的策略在主群体空间中指导遗传操作,在选择操作中引入k近邻法的思想进行动态学习,在变异操作中通过选择合适的变异点进行邻域搜索变异。典型算例的仿真实验与分析表明,算法在计算效率和求解质量上均具有较好的效果。

Aiming at the disadvantages of traditional genetic algorithms that are lack of efficient guidance and easy to get into local extremum, this paper developed a double evolution frame population space and belief space to solve job shop scheduling problem. CGA was to extract the excellent individuals＂ schema of the scheduling solution from the population space of genetic algorithm as the useful knowledge to form belief space. And the belief space was utilized to guide the genetic operator of selection and mutation by two different ways respectively in order to make use of the characteristics of excellent individuals, k--nearest neighbor method was introduced to do dynamic learning in selection operator,and do neighbor search mutation in mutation operator at an appropriate position. The different sizes of the benchmark data taken from literature were used to analyze the efficiency of this algo-rithm. Experimental results indicate that it outperforms current approaches in computational time and quality of the solutions.