计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (9): 137-141.

• 数据库、信号与信息处理 • 上一篇    下一篇

调整协同种群构成提升进化算法搜索性能

刘新闯1,邱洪泽2,叶 松3,苏兆锋3   

  1. 1.曲阜师范大学 财务处,山东 曲阜 273165
    2.山东大学 计算机学院,济南 250061
    3.鲁东大学 商学院,山东 烟台 264025
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-03-21 发布日期:2011-03-21

Improving performance of evolutionary algorithm by remodeling evolutionary population

LIU Xinchuang1,QIU Hongze2,YE Song3,SU Zhaofeng3   

  1. 1.Finance Division,Qufu Normal University,Qufu,Shandong 273165,China
    2.Computer Science and Technology Academy,Shandong University,Jinan 250061,China
    3.School of Business,Ludong University,Yantai,Shandong 264025,China

  • Received:1900-01-01 Revised:1900-01-01 Online:2011-03-21 Published:2011-03-21

摘要: 进化过程中种群多样性降低导致的收敛极大限制了进化算法的求解质量与搜索效率。调整种群元素策略利用进化算法收敛本性,在进化过程中向进化种群加入优势元素和随机元素,调整种群元素构成。经共生进化算法求解复杂柔性作业调度测试,定期大规模加入优势元素和随机元素能有效调整种群结构,既利用了前期种群进化收敛的结果又维持了种群进化全程的多样性。使进化算法可通过扩大搜索规模有效提高求解质量,将促进进化算法在各领域的应用深度和广度。

关键词: 早熟收敛, 进化算法, 柔性作业调度

Abstract: Reduction of population diversity leads to premature convergence,which limits search capability and computational efficiency of evolutionary algorithm.To deal with premature convergence,the evolutionary population is updated with elite solutions and new created random solutions periodically during evolutionary process.Adding elite solutions means inheriting results got by anterior evolutionary process from the beginning and adding new solutions created randomly improves population diversity.For large search scale,population is remodeled many times in the whole evolutionary process according to the search scale.To test solution quality and computational efficiency,the proposed remodeling population strategy is applied to symbiotic evolutionary algorithm for dealing with a flexible job-shop scheduling problem.Compared with the widely used traditional evolutionary algorithm,improved algorithm shows better performance for different search scale no matter whether the problem is large or not.The most important is it presents a solution for dealing with premature convergence,which deeply limits performance of evolutionary algorithm.With the remodeling population strategy,the applying depth and width of evolutionary algorithms will be improved.

Key words: premature convergence, evolutionary algorithm, flexible job shop scheduling problem