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

摘要

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