摘要
多种群遗传算法相比遗传算法在性能上能够有所提高,但对具有较多局部最优解的作业车间调度问题,多种群遗传算法仍然难以改善易陷入局部最优解和局部搜索能力差的缺点.因此,提出了一种求解作业车间调度问题的新算法MGA-MBL(multi-population genetic algorithm based on memory-base and Lamarckian evolution for jobshop scheduling problem).MGA-MBL在多种群遗传算法的基础上通过引入记忆库策略,不但使子种群间的个体可以进行信息交换,而且有利于保持整个种群的多样性;通过构造基于拉马克进化机制的局部搜索算子来提高多种群遗传算法中子种群进化的局部搜索能力.由于MGA-MBL采用了全局寻优能力较强的模拟退火算法对记忆库中的个体进行优化,从而缓解了多种群遗传算法易陷入局部最优解的问题,并提高了算法求解作业车间调度问题的性能.对著名的benchmark数据进行测试,实验结果证实了MGA-MBL在求解作业车间调度问题上的有效性.
Compared with the Genetic Algorithm, a multi-population genetic algorithm has an enhancement in performance, but for a job shop scheduling problem, which has a lot of local optima, it also has the shortcomings of an easy-to-fall into local optima and a poor ability of local search. Therefore, an effective algorithm is proposed to solve job shop scheduling problem. The proposed algorithm, based on multi-population genetic algorithm, involves the strategy of memory-base and a mechanism of the Lamarckian evolution. Not only does the memory-base make individuals between sub-populations exchange information, but it can maintain the diversity of the population. The local search operator, based on Lamarckian evolution, is adupted to enhance the individual's ability of local search. The simulated annealing algorithm that has a stronger ability to jump out local optima than the genetic algorithm is used, thus, alleviated the problem and enhances the performance of the algorithm for job shop scheduling. The experimental results on the well-known benchmark instances show the proposed algorithm is very effective in solving job shop scheduling problems.
出处
《软件学报》
EI
CSCD
北大核心
2010年第12期3082-3093,共12页
Journal of Software
基金
国家自然科学基金Nos.60703107
60703108
60803098
60803706
60872135
国家高技术研究发展计划(863)Nos.20060101Z1119
2009AA12Z210
陕西省"13115"科技创新工程重大科技专项项目No.2008ZDKG-37
国家教育部长江学者和创新团队支持计划No.IRT0645
中国博士后科学基金资助项目Nos.200801426
20080431228~~
关键词
作业车间调度
多种群遗传算法
记忆库
拉马克进化
局部搜索
模拟退火
job shop scheduling
multi-population genetic algorithm
memory-base
Lamarckian evolution
local search
simulated annealing