一种求解并行多机间歇调度问题的自适应EDA算法  

An adaptive estimation of distribution algorithm for the identical parallel machine batch scheduling problem

作　　者：李作成[1] 钱斌[1] 胡蓉[1] 历莉[1] 车国霖[1] 

机构地区：[1]昆明理工大学信息工程与自动化学院自动化系,云南昆明650500

出　　处：《计算机与应用化学》2013年第7期743-747,共5页Computers and Applied Chemistry

基　　金：国家自然科学基金资助项目(60904081);云南省中青年学术和技术带头人后备人才项目(2012HB011)

摘　　要：针对广泛存在于化工生产过程中的并行多机间歇调度问题,提出了一种自适应分布估计算法,用于最小化最早完工时间(makespan)。首先,提出了一种具有自适应学习能力的改进策略,该策略根据当前解的改善状况自适应调节学习速率,有效克服了EDA对学习速率较敏感和依赖的不足,进而使得算法的搜索宽度和深度得到合理平衡;其次,设计了一种基于双精英个体的协同进化策略,该策略通过双概率模型协同进化,使算法能充分利用优秀个体的信息来指导搜索方向。仿真实验和算法比较验证了AEDA的有效性和鲁棒性。An adaptive estimation of distribution algorithm, namely AEDA, is proposed to minimize the makespan criterion for the identical parallel machine batch scheduling problem, which widely exists in the chemical production process. Firstly, an improved strategy with adaptive learning capability is presented to adjust the learning rate based on the improvement status of the current solutions, which can overcome EDA＇s sensitivity and dependence of the learning rate and help the algorithm to achieve a reasonable balance between search wide and depth. Secondly, a double elite co-evolutionary strategy is designed by using two probability models to execute co-evolution, which can help the algorithm to adequately utilize the excellent individuals＇ information and guide the effective search direction. Simulation results and comparisons demonstrate the effectiveness and robustness of AEDA.

关 键 词：分布估计算法 并行多机 间歇调度 协同进化 自适应调节 

分 类 号：TQ021.8[化学工程]