计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (11): 49-52.DOI: 10.3778/j.issn.1002-8331.2009.11.015

• 研究、探讨 • 上一篇    下一篇

共生进化算法母体选择策略性能研究及改进

苏兆锋1,邱洪泽2   

  1. 1.鲁东大学 管理学院,山东 烟台 264025
    2.山东大学 计算机学院,济南 250061
  • 收稿日期:2008-03-03 修回日期:2008-05-23 出版日期:2009-04-11 发布日期:2009-04-11
  • 通讯作者: 苏兆锋

Research on parents selection method in symbiotic evolutionary algorithm

SU Zhao-feng1,QIU Hong-ze2   

  1. 1.School of Management,Ludong University,Yantai,Shandong 264025,China
    2.Computer Science and Technology Academy,Shandong University,Jinan 250061,China
  • Received:2008-03-03 Revised:2008-05-23 Online:2009-04-11 Published:2009-04-11
  • Contact: SU Zhao-feng

摘要: 轮盘赌在传统遗传算法中能加快进化速度和提高解质量,以共生进化算法求解一个复杂的柔性作业调度为例,跟踪共生种群进化过程。研究轮盘赌在以求得最优组合为目标的共生进化算法中对种群进化速度、种群多样性以及解质量的影响。为提高种群进化的解质量,引入了Worst策略。仿真实验表明,轮盘赌在共生进化算法中的应用不能促进解质量的提高,Worst策略能有效调节种群的进化速度并能提升解质量。

关键词: 轮盘赌, 作业调度, 共生进化算法

Abstract: Roulette wheel method is often adopted in traditional genetic algorithm to improve evolution speed and solution quality.Jobs with high production flexibility will lead to much more process plans and enhance the difficulty of scheduling problem.The optimality of job shop scheduling depends on the result of process planning.Symbiotic Evolutionary Algorithm(SEA) is a good alternative for dealing with the problem usually.A complex job shop scheduling problem is selected as the test-bed problem for symbiotic evolutionary algorithm to test and compare the performance of two parents selection operations,random and roulette wheel methods.The experimental results show the ineffectiveness of roulette wheel method selection both in accelerating evolution speed and improving solution quality.To improve SEA performance,“Worst strategy” is proposed to adjust the evolution process and shows better performance for different test-bed problems.

Key words: roulette wheel, job shop scheduling problem, Symbiotic Evolutionary Algorithm(SEA)