利用优势元素改进进化算法求解柔性作业调度

doi:10.3778/j.issn.1002-8331.2010.17.014

计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (17): 48-51.DOI: 10.3778/j.issn.1002-8331.2010.17.014

利用优势元素改进进化算法求解柔性作业调度

刘新闯¹，邱洪泽²，魏二有³，苏兆锋³

1.曲阜师范大学财务处，山东曲阜 273165
2.山东大学计算机学院，济南 250061
3.鲁东大学管理学院，山东烟台 264025

收稿日期:2008-12-18 修回日期:2009-02-23 出版日期:2010-06-11 发布日期:2010-06-11
通讯作者: 刘新闯

Improving performance of evolutionary algorithm by adding elite solutions to population during evolution process——Application to deal with flexible job-shop scheduling problem

LIU Xin-chuang¹，QIU Hong-ze²，WEI Er-you³，SU Zhao-feng³

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

Received:2008-12-18 Revised:2009-02-23 Online:2010-06-11 Published:2010-06-11
Contact: LIU Xin-chuang

摘要/Abstract

摘要： 进化算法进化过程中种群多样性的降低导致的收敛极大限制了进化算法的求解质量与搜索效率，通过扩大搜索规模并不能有效提高算法求解质量。在共生进化算法求解柔性作业调度的基础上，研究进化算法在较大搜索规模下的种群状态进化过程，并在进化过程向种群内批量加入优势元素，调整种群模式构成。仿真实验表明：与传统进化算法相比，进化过程中加入优势元素能有效提高算法的求解质量与搜索效率，在较短的时间内能得到较好的解，并且在较大搜索规模时表现了更好的搜索性能。

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

Abstract: Deficiency of population diversity always leads to premature convergence，which deeply limits performance of evolutionary algorithm.Solution quality can not be improved by simply enlarging search scale.To improve performance of evolutionary algorithm，part individuals in population are replaced with better solutions.The operation repeats for many times during evolution process according to search scale.The proposed strategy is studied on the basis of a symbiotic evolutionary algorithm which is used for dealing with complex flexible job-shop scheduling problem.Results of extensive computational simulations show that the proposed strategy shows better performance.Compared with traditional evolutionary algorithm，new proposed strategy shows higher efficiency in getting better solutions no matter whether search scale is large or not.

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

中图分类号:

TP18

刘新闯¹，邱洪泽²，魏二有³，苏兆锋³. 利用优势元素改进进化算法求解柔性作业调度[J]. 计算机工程与应用, 2010, 46(17): 48-51.

LIU Xin-chuang¹，QIU Hong-ze²，WEI Er-you³，SU Zhao-feng³. Improving performance of evolutionary algorithm by adding elite solutions to population during evolution process——Application to deal with flexible job-shop scheduling problem[J]. Computer Engineering and Applications, 2010, 46(17): 48-51.

[1]	钱峥远，曾国荪. 精英化岛屿种群引导的差分进化算法[J]. 计算机工程与应用, 2021, 57(20): 73-81.
[2]	白首华，郭广颂，胡天彤. 交互式多目标文化算法优化多模态混合指标[J]. 计算机工程与应用, 2021, 57(17): 80-87.
[3]	崔彩霞，毕超超，范勤勤. 基于隐马尔可夫链的自适应MODE及应用[J]. 计算机工程与应用, 2021, 57(14): 83-94.
[4]	李荣，贺兴时，杨新社. 基于差分进化的飞蛾算法在电力调度中的应用[J]. 计算机工程与应用, 2021, 57(13): 258-268.
[5]	沈鑫，邹德旋，张强. 采用双变异策略的自适应差分进化算法及应用[J]. 计算机工程与应用, 2020, 56(4): 146-157.
[6]	吉训生，蔡益青. 利用历史信息和限制算子求解MOFJSP[J]. 计算机工程与应用, 2020, 56(2): 272-278.
[7]	蔡延光，陈厚仁，戚远航. 变邻域量子烟花算法求解CVRP[J]. 计算机工程与应用, 2019, 55(9): 230-236.
[8]	耿焕同，周利发，丁洋洋，周山胜. 一种基于新型差分进化模型的MOEA/D改进算法[J]. 计算机工程与应用, 2019, 55(8): 138-146.
[9]	周林. 低碳时变城配送车辆路径-发车调度集成优化[J]. 计算机工程与应用, 2019, 55(8): 264-270.
[10]	迟宗正，董绍正，郭童，任志磊，周宽久，郭禾. 求解风力发电机布局问题的超启发式算法研究[J]. 计算机工程与应用, 2019, 55(7): 220-225.
[11]	曾强1，邓敬源1，张进春1，沈玲2. 多工作日历下流水作业调度遗传优化方法[J]. 计算机工程与应用, 2019, 55(4): 238-247.
[12]	肖俊明，高洪洋，朱永胜，瞿博阳. 考虑新能源接入的电力多目标优化调度[J]. 计算机工程与应用, 2019, 55(23): 241-247.
[13]	鞠录岩1，杨建军2，张建兵1，郭龙龙1，李锁斌1. 改进NSGA算法求解多目标柔性车间作业调度问题[J]. 计算机工程与应用, 2019, 55(13): 260-265.
[14]	顾春华，刘鑫平，罗飞，丁炜超. 基于同步更新外部归档集的NSGA-II改进算法[J]. 计算机工程与应用, 2018, 54(20): 28-34.
[15]	申晓宁，孙毅，薛云勇. 采用放松支配关系的高维多目标微分进化算法[J]. 计算机工程与应用, 2018, 54(18): 161-167.

利用优势元素改进进化算法求解柔性作业调度

Improving performance of evolutionary algorithm by adding elite solutions to population during evolution process——Application to deal with flexible job-shop scheduling problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics