变点交叉多目标遗传算法在作业车间调度中的应用

A Transition Point Crossover Fashion Multi-Objective Genetic Algorithm in Job Shop Scheduling Research

针对传统多目标遗传算法在求解作业车间调度问题时收敛速度慢和容易陷入局部最优化的不足,提出一种采用变点交叉方式的多目标遗传算法.运算初期采用多点交叉的方式,在于提高收敛速度.在运算后期逐步减少交叉点,直至采用两点交叉、单点交叉的方式,避免丢失最优解导致早熟收敛.同时设计一种交互权重将多目标问题变为单一目标问题,体现决策者偏好,同时简化求解过程.最后将提出的改进算法运用于作业车间调度问题,与无偏好多目标优化的小生境Pareto遗传算法(NPGA)进行了对比,结果显示了该算法的有效性.

Aiming at the traditional multi-objective genetic algorithm for solving job shop scheduling problem in slow convergence rate and easy to fall into local optimization,a transition point crossover fashion is proposed using multi-objective genetic algorithms.The initial approach of the multi-point crossover operator is to improve convergence speed which gradually reduces in the latter part of the intersection of computing,until cross with two and single-point crossover approach to avoid missing the optimal solution leading to premature convergence.At the same time,the weight will transform an interactive multi-objective problem into single objective problem to reflect the decision maker preferences,while simplifying the solution process.The improved algorithm is applied to a job shop scheduling problem in contrast with no preference for multi-objective optimization Pareto genetic algorithm niche（NPGA）,and the results show the effectiveness of the algorithm.