东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

基于记忆库拉马克进化算法的作业车间调度

期刊名称：软件学报
时间：0
页码：3082-3093
语言：中文
分类：TP301[自动化与计算机技术—计算机系统结构;自动化与计算机技术—计算机科学与技术]
作者机构：[1]西安电子科技大学计算机学院,陕西西安710071, [2]西安电子科技大学智能感知与图像理解教育部重点实验室,陕西西安710071, [3]西安电子科技大学智能信息处理研究所,陕西西安710071
相关基金：Supported by the National Natural Science Foundation of China under Grant Nos.60703107, 60703108, 60803098, 60803706, 60872135 （国家自然科学基金）; the National High-Tech Research and Development Plan of China under Grant Nos.20060101Z1119, 2009AA12Z210 （国家高技术研究发展计划（863））; the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant Nos.20060701007, 20070701022 （国家教育部博士点基金）; the Key Scientific and Technological Innovation Special Projects of Shaanxi ＂＇13115＂ of China under Grant No.2008ZDKG-37 （陕西省“13115”科技创新工程重大科技专项项目）; the Program for Cheung Kong Scholars and Innovative Research Team in University of China under Grant No.IRT0645 （国家教育部长江学者和创新团队支持计划）; the China Postdoctoral Science Foundation Funded Project under Grant Nos.200801426, 20080431228 （中国博士后科学基金资助项目）.
相关项目：基于量子计算和拉马克学习的免疫聚类与分类

关键词：作业车间调度, 多种群遗传算法, 记忆库, 拉马克进化, 局部搜索, 模拟退火, job shop scheduling, multi-population genetic algorithm, memory-base, Lamarckian evolution, local search, simulated annealing

中文摘要：

多种群遗传算法相比遗传算法在性能上能够有所提高，但对具有较多局部最优解的作业车间调度问题，多种群遗传算法仍然难以改善易陷入局部最优解和局部搜索能力差的缺点．因此，提出了一种求解作业车间调度问题的新算法MGA—MBL（multi—population genetic algorithm based on memory—baseand Lamarckian evolution for job shop 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.

同期刊论文项目