重启进化提高较大搜索规模时柔性作业解质量

计算机工程与应用 ›› 2014, Vol. 50 ›› Issue (14): 245-250.

重启进化提高较大搜索规模时柔性作业解质量

李洪斌1，苏兆锋2

1.鲁东大学交通学院，山东烟台 264025
2.鲁东大学计算机学院，山东烟台 264025

出版日期:2014-07-15 发布日期:2014-08-04

Improving performance of Coevolutionary algorithm for flexible job-shop scheduling problem

LI Hongbin1, SU Zhaofeng2

1.Institute of Traffic, Ludong University, Yantai, Shandong 264025, China
2.Academy of Computer Science and Technology, Ludong University, Yantai, Shandong 264025, China

Online:2014-07-15 Published:2014-08-04

摘要/Abstract

摘要： 种群多样性下降导致的早熟收敛限制了进化算法的求解质量与搜索效率。为应对收敛，提高较大搜索规模时的求解质量，引入随机算法中重启策略。种群收敛时，利用算法前期搜索结果（优势元素）和新产生的随机元素重新构造新种群继续进化。提高柔性作业车间调度问题解质量对实际工业生产有重要的现实意义。将重构思想应用于协同进化算法求解复杂柔性作业调度问题并跟踪种群进化状态。仿真实验结果表明，改进算法在进化过程中维持了较好的种群多样性，大幅提高了算法求解复杂柔性作业调度的搜索性能，并可以简单通过扩大搜索规模提高作业调度解质量。

关键词: 协同进化算法, 重启, 柔性作业调度

Abstract: Reduction of population diversity during evolution process leads to premature convergence, which limits search capability and computational efficiency of evolutionary algorithm. To deal with premature convergence, Restart Strategy（RS） is introduced into coevolutionary algorithm. When evolution loses search capability and efficiency, novel population is constructed with elite candidates and new randomly reproduced candidates, then it continues search process. The improved strategy is introduced to symbiotic evolutionary algorithm for a complex flexible job-shop scheduling problem. Compared with the widely used traditional evolutionary algorithm, solution quality and computational efficiency are improved markedly for different search scale especially for complicated problems. Solution quality can be improved by enlarging search scale with the new strategy.

Key words: coevolutionary algorithm, restart strategy, flexible job-shop scheduling

李洪斌1，苏兆锋2. 重启进化提高较大搜索规模时柔性作业解质量[J]. 计算机工程与应用, 2014, 50(14): 245-250.

LI Hongbin1, SU Zhaofeng2. Improving performance of Coevolutionary algorithm for flexible job-shop scheduling problem[J]. Computer Engineering and Applications, 2014, 50(14): 245-250.

[1]	顾军华，陈博，王锐，张素琪. 结合重要节点信任传播的社会化推荐算法[J]. 计算机工程与应用, 2021, 57(17): 190-195.
[2]	张汝波1，2，孟雷1，史长亭1. 部分可观环境中AUV软件自修复模型研究[J]. 计算机工程与应用, 2017, 53(2): 151-156.
[3]	李泽1，贺利乐1，郭志杰1，郑建校1，吴敏宁2. 改进协同进化算法优化液压集成块管路布置[J]. 计算机工程与应用, 2016, 52(23): 266-270.
[4]	徐康丽1，杨志霞1，蒋耀林2. 基于Krylov-Schur重启技术的Arnoldi模型降阶方法[J]. 计算机工程与应用, 2016, 52(12): 251-255.
[5]	陈华，史悦戎. 基于GPU的重启PGMRES并行算法研究[J]. 计算机工程与应用, 2014, 50(7): 35-40.
[6]	艾依斯1，张爱莲2，吴义忠1. 一种改进的RBF全局优化方法[J]. 计算机工程与应用, 2012, 48(15): 43-48.
[7]	刘新闯1，邱洪泽2，叶松3，苏兆锋3. 调整协同种群构成提升进化算法搜索性能[J]. 计算机工程与应用, 2011, 47(9): 137-141.
[8]	梁存良，叶海智. 任务关键网络系统的最佳恢复策略判定方法[J]. 计算机工程与应用, 2011, 47(20): 96-98.
[9]	董方1，艾丽蓉1，赵婧华2. 卫星地面站系统软件抗衰策略研究[J]. 计算机工程与应用, 2011, 47(17): 118-121.
[10]	曾孝平，李金枝，刘国金. 基于RWR的自然图像抠图[J]. 计算机工程与应用, 2010, 46(25): 160-163.
[11]	梁迪¹,陶泽². 多目标柔性作业调度的优化研究[J]. 计算机工程与应用, 2009, 45(15): 223-225.
[12]	李菲菲¹，姚坤¹，刘希玉². 一种多微粒群协同进化算法[J]. 计算机工程与应用, 2007, 43(22): 44-46.