基于NDP的遗传算法及其在JSP中的应用  

Genetic algorithm based on NDP with application to job shop scheduling

作　　者：金锋[1] 宋士吉[1] 吴澄[1] 

机构地区：[1]清华大学自动化系,北京100084

出　　处：《清华大学学报（自然科学版）》2006年第4期488-491,共4页Journal of Tsinghua University(Science and Technology)

基　　金：国家"九七三"重点基础研究项目(2002CB312205);国家自然科学基金资助项目(60574077);国家"八六三"高技术项目(2004AA414020)

摘　　要：遗传算法被广泛应用于求解车间作业调度问题(JSP),但遗传算法具有最优参数难以确定的问题。对此,该文提出了一种基于神经元动态规划(NDP)的遗传算法NDP-GA。该文将遗传算法用M arkov决策过程模型描述,建立了M arkov决策过程最优策略与遗传算法最优参数之间的联系。在此基础上,用神经元动态规划逼近M arkov决策过程的最优策略,并用学习到的策略指导遗传算法最优参数的选择。数值计算结果表明,该文提出的算法能自动收敛到最优遗传参数,并在求解JSP问题时能稳定地得到满意解。Genetic algorithms （GA） are widely used to solve job shop scheduling problems, but the optimal parameters of genetic algorithms are difficult to determine. A GA based on neuro-dynamie programming （NDP） was formulated using the Markov decision process （MDP） model based on the relationship between the optimal MDP model and the optimal parameters for the GA. Then the neuro-dynamic programming method was used to approximate the optimal parameters which were used to guide the selection of the GA parameters. Computational results show that the method can automatically select the optimal parameters to give good stable solutions for solving job shop problems.

关 键 词：神经元动态规划 车间作业调度 遗传算法 Qlearning 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]