基于链约束的Job-Shop型知识化制造单元自进化算法  

Self-evolution algorithm for Job-Shop knowledgeable manufacturing cell based on link constraint

作　　者：李文超[1,2,3] 严洪森[1,2] 

机构地区：[1]东南大学自动化学院,江苏南京210096 [2]东南大学复杂工程系统测量与控制教育部重点实验室,江苏南京210096 [3]江苏大学汽车与交通工程学院交通运输系,江苏镇江212013

出　　处：《计算机集成制造系统》2012年第9期1911-1920,共10页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(60934008;50875046)~~

摘　　要：以最大完工周期为目标的Job-shop调度问题是一类NP完全问题,迄今仍未发现其求解的有效算法。通过Job-shop型知识化制造单元自身结构特性分析,构建其链约束模型,并通过对其链路图添加约束获得可行调度。在此基础上提出一种自进化算法,该算法在运行中通过q学习能够不断从环境中获取所需知识,使其搜索能力逐步提高。对于学习过程中系统状态过多的问题,采用径向基函数网络对q函数进行逼近。通过仿真计算表明了所提算法对该类问题具备明显的学习进化能力。The Job-shop scheduling problem with make-span as goal belongs to the NP complete problem and the valid algorithm for its solution hasn＇t been given until now. Through analyzing the characteristics of Job Shop knowledgeable manufacturing cell structure, the link constraint model was constructed, and feasible scheduling was obtained by adding constraint to its link-path graph. On these bases, a self-evolution algorithm with learning ability was proposed. Through adopting the q-function of reinforcement learning in algorithm, the needed knowledge was obtained from its environment to improve its search ability. The approximation of q function was implemented by using Radial Basis-Function（RBF）network to avoid too many states in learning process. Numerical simulation results showed that the proposed algorithm had excellent learning and evolution ability for this kind of problems.

关 键 词：自进化算法 强化学习 知识化制造单元 径向基函数网络 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]