基于群体共享的最优保存小生境遗传算法在作业车间调度问题中的应用

Application of the Niche Genetic Algorithm Based on the Optimal Individual Protection and Population Sharing to Solve Job Shop Problem

作业车间调度问题是一个典型的NP-hard难题,利用普通小生境遗传算法解决此类问题时存在早熟和局部退化现象.提出一种基于群体共享的最优保存小生境遗传算法,通过保存最优个体来保护最优解,并借助共享群体实现对小生境中子群的启发.实验结果表明,改进后的小生境遗传算法能够更好地收敛于全局最优解,避免了算法早熟和局部退化问题.

Job shop problem is a typical NP-hard problem.It is of no use to solve the problem using general genetic algorithm because of the premature and local degeneration.It is better to solve the problem using optimal individual protection and population sharing.Protecting the best individuals will help to get the optimal solution.Sharing group could enlighten the evolution.Result shows that using the algorithm we could be able to get a better global optimal solution.Premature and local degeneration is avoided.