基于自适应变级遗传杂草算法的FJSP研究

Self-adaptive Multistage GA-IWO for Solving Flexible Job Shop Scheduling Problem

针对以最小化最大完工时间为目标的柔性作业车间调度问题,建立其数学模型并提出一种自适应变级遗传杂草算法求解之。改进基本入侵杂草优化算法以适应柔性作业车间调度问题的组合优化特点,提出基于总个体数的评价指标,用其分析入侵杂草优化算法在解决柔性作业车间调度问题时的性能及参数对算法的影响,得出入侵杂草优化算法的种群数和个体产生种子数对算法性能的影响关系。分析入侵杂草优化算法和遗传算法在求解柔性作业车间调度问题时各自的优缺点。结合这两种算法,引入汉明距离来测度种群多样性并用该测度值作为变级控制的依据,提出一种根据多样性测度值的动态变化而自适应地在遗传算法和入侵杂草优化算法间串行变级的遗传杂草算法。通过实例对比入侵杂草优化算法、遗传算法和自适应变级遗传杂草算法,证明了自适应变级遗传杂草算法的有效性和优越性。将自适应变级遗传杂草算法用于标准测试实例与多种算法比较,证明了该算法能够有效求解柔性作业车间调度问题。

For flexible job shop scheduling problem with minimizing makespan,a mathematical model and a self-adaptive multistage genetic algorithm/invasive weed optimization algorithm are proposed.For the characteristics of flexible job shop scheduling problem,invasive weed optimization is improved.Using some new evaluating indicators based on total number of individuals to evaluate the performance of improved invasive weed optimization,how the population size and weed size affect invasive weed optimization is addressed.Using the new evaluating indicators to evaluate improved invasive weed optimization and genetic algorithm,some differences between them are illustrated.Using hamming distance to measure the population diversity,the value of population diversity is used to control the self-adaptive multistage between invasive weed optimization and genetic algorithm,obtaining a self-adaptive multistage genetic algorithm/invasive weed optimization algorithm.Using some instances to test genetic algorithm,invasive weed optimization,and self-adaptive multistage genetic algorithm/invasive weed optimization,the advantages of self-adaptive multistage genetic algorithm/invasive weed optimization are shown.Using some standard instances to compare a self-adaptive multistage genetic algorithm/invasive weed optimization with other algorithms,the simulation results show that the proposed algorithm can solve flexible job shop scheduling problem effectively.