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

doi:10.3778/j.issn.1002-8331.2010.17.014

Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (17): 48-51.DOI: 10.3778/j.issn.1002-8331.2010.17.014

• 研究、探讨 • Previous Articles Next Articles

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

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

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

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

通讯作者: 刘新闯

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

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

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

CLC Number:

TP18

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.

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

[1]	QIAN Zhengyuan, ZENG Guosun. Differential Evolution Algorithm Guided by Elite Island Population [J]. Computer Engineering and Applications, 2021, 57(20): 73-81.
[2]	SHI Yuqiang, TIAN Yongzheng, ZHANG Yuqi, SHI Xiaoqiu. Solving FJSP by Multi-population Genetic Algorithms with Complex Network Structure [J]. Computer Engineering and Applications, 2021, 57(2): 257-266.
[3]	GUO Jiali, WANG Qiuping, WANG Xiaofeng. Hybrid Moth Flame Algorithm with Learning Strategy and Neighboring Search [J]. Computer Engineering and Applications, 2021, 57(12): 170-179.
[4]	WU Shujing, YOU Youpeng, LUO Fuyuan. Genetic-Variable Neighborhood Search Algorithm with Elite Protection Strategy for Flexible Job Shop Scheduling Problem [J]. Computer Engineering and Applications, 2020, 56(22): 236-243.
[5]	JI Xunsheng, CAI Yiqing. Solving Multi-Objective FJSP Using Historical Information and Restriction Operator [J]. Computer Engineering and Applications, 2020, 56(2): 272-278.
[6]	CAI Yanguang, CHEN Houren, QI Yuanhang. Variable Neighborhood Quantum Fireworks Algorithm for Solving CVRP [J]. Computer Engineering and Applications, 2019, 55(9): 230-236.
[7]	GENG Huantong, ZHOU Lifa, DING Yangyang, ZHOU Shansheng. Improved MOEA/D Algorithm Based on New Differential Evolution Model [J]. Computer Engineering and Applications, 2019, 55(8): 138-146.
[8]	ZHOU Lin. Integrated Optimization Research on Vehicle Routing and Scheduling in City Logistics with Time-Dependent and CO2 Emissions Considerations [J]. Computer Engineering and Applications, 2019, 55(8): 264-270.
[9]	LUO Xiong, QIAN Qian, FU Yunfa. Review of Application of Genetic Algorithms for Solving Flexible Job Shop Scheduling Problems [J]. Computer Engineering and Applications, 2019, 55(23): 15-21.
[10]	XIAO Junming, GAO Hongyang, ZHU Yongsheng, QU Boyang. Multi-Objective Power Dispatching Considering New Energy Access [J]. Computer Engineering and Applications, 2019, 55(23): 241-247.
[11]	DENG Ye, ZHU Wanhong, WANG Fengshan, LIU Huali. Research on Multi-Objective Robust Vehicle Routing Problem in Emergency Logistics [J]. Computer Engineering and Applications, 2019, 55(1): 248-255.
[12]	GU Chunhua, LIU Xinping, LUO Fei, DING Weichao. Improved NSGA-II algorithm based on synchronous update of external archive [J]. Computer Engineering and Applications, 2018, 54(20): 28-34.
[13]	LI Hongya1, PENG Yuzhong1，2, DENG Chuyan1, GONG Daoqing1. Review of hybrids of GA and PSO [J]. Computer Engineering and Applications, 2018, 54(2): 20-28.
[14]	XU Qingzheng1, YANG Heng1, WANG Na1, WU Guohua2, JIANG Qiaoyong3. Recent advances in multifactorial evolutionary algorithm [J]. Computer Engineering and Applications, 2018, 54(11): 15-20.
[15]	DENG Ye, ZHU Wanhong, TANG Jian. Study on vehicle routing problem with stochastic demands and time windows combining with new remediation strategies [J]. Computer Engineering and Applications, 2018, 54(11): 241-248.

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

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics