Research on Niche Genetic Annealing Algorithm with Elite Strategy and Its Applications

China Mechanical Engineering ›› 2012, Vol. 23 ›› Issue (5): 556-563.

Previous Articles Next Articles

Research on Niche Genetic Annealing Algorithm with Elite Strategy and Its Applications

Liu Aijun1,2;Yang Yu1;Xing Qingsong1;Lu Hui3;Zhang Yudong4

1.State Key Laboratory of Mechanical Tramsmissions, Chongqing University, Chongqing, 400030

2.Southwest Jiaotong University,Chengdu,610031

3.Shanghai Normal University, Shanghai, 201815

4.Columbia University, New York, USA,10032

Online:2012-03-10 Published:2012-03-21
Supported by:

National Natural Science Foundation of China（No. 71071173）;

Program for New Century Excellent Talents in University of Ministry of Education of China（No. NCET-07-0908）;

Research Fund for the Doctoral Program of Higher Education of China

（No. 20090191110004）;
Fundamental Research Funds for the Central Universities( No. CDJZR10110012)

含精英策略的小生境遗传退火算法研究及其应用

刘爱军1,2;杨育1;邢青松1;陆惠3;张煜东4

1.重庆大学机械传动国家重点实验室,重庆,400030

2.西南交通大学,成都,610031

3.上海师范大学,上海,201815

4.哥伦比亚大学,纽约,美国,10032

基金资助:
国家自然科学基金资助项目(71071173)；新世纪优秀人才支持计划资助项目(NCET-07-0908)；高等学校博士学科点专项科研基金资助项目(20090191110004)；中央高校基本科研业务费资助项目(CDJZR10110012)
National Natural Science Foundation of China（No. 71071173）;

Program for New Century Excellent Talents in University of Ministry of Education of China（No. NCET-07-0908）;

Research Fund for the Doctoral Program of Higher Education of China（No. 20090191110004）;
Fundamental Research Funds for the Central Universities( No. CDJZR10110012)

Abstract

Abstract:

According to the defects of traditional genetic annealing algorithm, a niche genetic annealing algorithm was presented, which avoided the effective gene deletions at the early search stage and guaranteed the diversity of solution.Then adaptive double point crossover and swap mutation strategy were introduced to overcome the defects of long solving process and easily converging local minimum value due to the fixed crossover and mutation probability.The elite reserved strategy was imported, optimal solution missing was avoided effectively, evolution speed was accelerated. At last, the new algorithm was tested by three typical functions and the job shop scheduling problems, respectively. The simulation results show that the proposed algorithm can avoid the stagnation, improve the global convergence ability, and attain better optimization performance.

Key words: genetic simulated annealing algorithm, niche, job shop scheduling, simulation

摘要：

针对传统遗传退火算法的缺陷,提出了小生境遗传退火算法,该算法引入小生境技术,避免了搜索初期有效基因的缺失,保证了解的多样性;引入了自适应双点交叉和互换变异策略,克服了算法交叉和变异概率固定不变导致的求解过程较长和易收敛于局部最小值的缺陷;引入精英保留策略,有效地避免了最优解的丢失,加快了进化速度;通过3个经典函数测试,并将其应用于Job Shop调度问题,仿真实验结果表明:新算法有效克服了停滞现象,增强了全局搜索能力,比遗传算法和传统遗传退火算法的寻优性能更佳。 

关键词:

遗传模拟退火算法, 小生境, 作业车间调度, 仿真

CLC Number:

TP278

LIU Ai-Jun-1, 2, YANG Yo-1, GENG Jing-Song-1, LIU Hui-3, ZHANG Yu-Dong-4.

Research on Niche Genetic Annealing Algorithm with Elite Strategy and Its Applications

[J]. China Mechanical Engineering, 2012, 23(5): 556-563.

刘爱军1, 2, 杨育1, 邢青松1, 陆惠3, 张煜东4.

含精英策略的小生境遗传退火算法研究及其应用

[J]. 中国机械工程, 2012, 23(5): 556-563.

References

[1]梁旭 [1],黄明 [1],常征 [2].求解车间调度问题的一种新遗传退火混合策略[J].计算机集成制造系统,2005,11(6):851-854.
[2]张昊[1],陶然[1],李志勇[1],杜华[1].基于自适应模拟退火遗传算法的特征选择方法[J].兵工学报,2009(1):81-85.
[3]潘全科[1],王文宏[1],朱剑英[2].一类解决车间调度问题的遗传退火算法[J].机械科学与技术,2006,25(3):317-321.
[4]刘敏[1],严隽薇[1].基于自适应退火遗传算法的车间日作业计划调度方法[J].计算机学报,2007,30(7):1164-1172.
[5]冯毅[1],李利[1],高艳明[1],田树军[1].一种基于小生境的混合遗传退火算法[J].机械科学与技术,2004,23(12):1494-1498.
[6]虞斌能[1],焦斌[1],顾幸生[2].改进协同粒子群优化算法及其在FlowShop调度中的应用[J].华东理工大学学报：自然科学版,2009,35(3):468-474.
[7]王凌 [1],吴昊 [1],唐芳 [2],郑大钟 [1],金以慧 [1].混合量子遗传算法及其性能分析[J].控制与决策,2005,20(2):156-160.
[8]Jia Chunqiang, Yu Ling, Shu Jun, et al. Optimal Design of Hydraulic Manifold Blocks Based on Nic- hing Genetic Simulated Annealing Algorithm[J]. High Technology Letters,2007, 13(4):363-368.
[9]Sadegheig A. Scheduling Problem Using Genetic Algorithm, Simulated Annealing and the Effects of Parameter Values on GA Performance[J]. Applied Mathematical Modelling, 2006,30 (2) : 147-154.
[10]Andresen M, Brasel H, Morig, et al. Simulated Annealing and Genetic Algorithms for Minimizing Mean Flow Time in an Open Shop[J]. Mathemat- ical and Computer Modelling,2008,48(7/8) : 1279 -1293.
[11]Pere E, Herrera F, Hernandez C. Finding Multi- ple Solutions in Job Shop Scheduling by Niching Genetic Algorithms [J]. Journal of Intelligent Manufacturing, 2003,14: 323-339.

[1]	LI Xixing, YANG Daoming, LI Xin, WU Rui, . Flexible Job Shop AGV Fusion Scheduling Method Based on HGWOA [J]. China Mechanical Engineering, 2021, 32(08): 938-950，986.
[2]	QIU Yongtao1;JI Weixi1,2;ZHANG Chaoyang1,2. Multi-objective Job Shop Scheduling Based on Hybrid Evolutionary Algorithm and Knowledge [J]. China Mechanical Engineering, 2020, 31(24): 2979-2987.
[3]	YANG Dongjing, LEI Deming. A Novel Shuffled Frog-leaping Algorithm for FJSP withTotal Energy Consumption Constraints [J]. China Mechanical Engineering, 2018, 29(22): 2682-2689.
[4]	ZENG Qiang, DENG Jingyuan, CHANG Menghui, ZHANG Jinchun. Genetic Evalution Method for JSP under Mixed Work Calendars [J]. China Mechanical Engineering, 2018, 29(22): 2690-2702.
[5]	YAN Wei, ZHANG Hua, JIANG Zhigang, MA Feng, . Multi-objective Optimization Model Faced to Demands of Energy Saving and High Efficiency for CNC Machining Systems [J]. China Mechanical Engineering, 2018, 29(21): 2571-2580.
[6]	YAN Hao1;BAI Ruilin1;JI Feng2. An Improved Dynamics Parameter Identification Method for SCARA Robots [J]. China Mechanical Engineering, 2017, 28(22): 2707-2713.
[7]	Zhu Chuanjun, Song Wenjia, Zhang Chaoyong , Cao Jing, Zhu Mengzhou. Research on Optimization of FJSP Based on Maintenance Time Window [J]. China Mechanical Engineering, 2016, 27(10): 1337-1343.
[8]	Zhao Min, Yin Huan, Sun Dihua, Zheng Linjiang, He Wei, Yuan Chuan. Flexible Job Shop Scheduling Based on Modified Artificial Fish Swarm Algorithm [J]. China Mechanical Engineering, 2016, 27(08): 1059-1065.
[9]	Yang Hongan, Xi Zhicheng, Xia Changkai, Wang Jinguo. Minimax model and Two Space Co-evolutionary Genetic Algorithm for Job Shop Scheduling Problem [J]. China Mechanical Engineering, 2015, 26(3): 330-338.
[10]	Song Wenjia, Zhang Chaoyong, Ying Yong, Shao Xinyu. Integrated Optimization of Equipment Maintenance and Shop Scheduling Problem Based on Multi-objective Hybrid Imperialist Competitive Algorithm [J]. China Mechanical Engineering, 2015, 26(11): 1478-1487.
[11]	Ling Haifeng;Wang Xishan. A Two-stage Parameter Adaptive Ant Colony Algorithm for Flexible Job Shop Scheduling Problem [J]. China Mechanical Engineering, 2013, 24(24): 3380-3385.
[12]	. Adaptive Genetic Simulated Annealing Algorithm in Optimal Layout of Rectangular Parts [J]. China Mechanical Engineering, 2013, 24(18): 2499-2504.
[13]	LI Hai-Ning, SUN Shu-Dong. Genetic Algorithm for Job Shop Earliness and Tardiness Scheduling Problems with Deadlines [J]. China Mechanical Engineering, 2012, 23(15): 1811-1818.
[14]	CENG Jiang, YANG Yo, WANG Yong-Zhi, CHENG Bo. Multi-objective Optimization Scheduling for Job Shop of Batch Production with Multiple Process Flows [J]. China Mechanical Engineering, 2011, 22(2): 190-196.
[15]	YANG Hong-An, SUN Qi-Feng, GUO Jie. Constrained Optimization Techniques for Job Shop Scheduling [J]. China Mechanical Engineering, 2010, 21(20): 2445-2450,2458.

Research on Niche Genetic Annealing Algorithm with Elite Strategy and Its Applications

含精英策略的小生境遗传退火算法研究及其应用

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics