[1]裴小兵,张春花.应用改进区块遗传算法求解置换流水车间调度问题[J].智能系统学报,2019,14(3):541-550.[doi:10.11992/tis.201801041]
PEI Xiaobing,ZHANG Chunhua.An improved puzzle-based genetic algorithm for solving permutation flow-shop scheduling problems[J].CAAI Transactions on Intelligent Systems,2019,14(3):541-550.[doi:10.11992/tis.201801041]
点击复制
PEI Xiaobing,ZHANG Chunhua.An improved puzzle-based genetic algorithm for solving permutation flow-shop scheduling problems[J].CAAI Transactions on Intelligent Systems,2019,14(3):541-550.[doi:10.11992/tis.201801041]
应用改进区块遗传算法求解置换流水车间调度问题
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
14
期数:
2019年第3期
页码:
541-550
栏目:
学术论文—机器学习
出版日期:
2019-05-05
- Title:
- An improved puzzle-based genetic algorithm for solving permutation flow-shop scheduling problems
- Keywords:
- production scheduling; combinatorial optimization; genetic algorithms; ant colony optimization; building block; artificial chromosome
- 分类号:
- TP18
- 摘要:
- 针对最小化最大完工时间的置换流水车间调度问题，提出一种将遗传算法与蚁群算法相结合的改进区块遗传算法。算法利用随机机制和改进反向学习机制相结合的方式产生初始解，以兼顾初始种群的多样性和质量。通过若干代简单遗传算法操作产生精英群体，借鉴蚁群算法中利用蚂蚁信息度浓度统计路径和节点信息的思想，对精英群体所携带信息进行统计分析并建立位置信息素矩阵和相依信息素矩阵，根据两矩阵挖掘区块并将区块与非区块组合形成染色体。将染色体进行切段与重组，以提高染色体的质量，使用二元竞赛法保留适应度较高的染色体。算法通过Reeves实例和Taillard实例进行测试，并将结果与其他算法进行比较，验证了该算法的有效性。
- Abstract:
- Targeting the permutation flow-shop scheduling problem that minimizes maximum completion times, an improved block genetic algorithm combined with an ant colony algorithm is proposed. The algorithm uses a random mechanism and the improved opposition-based learning mechanism to generate the initial solution. It takes into account the diversity and quality of the initial population. Elite populations are generated through several generations of simple genetic algorithm operations. Based on the idea of using ant information density concentration’s statistical path and node information in the ant colony algorithm, the information carried by elite groups was counted. Position pheromone and dependent pheromone matrices were established. Mining blocks according to two matrices were developed and blocks were combined with non-blocks to form artificial chromosomes. Chromosomes were cut and recombined to increase chromosome quality. The binary race method was used to retain chromosomes with higher fitness. The algorithm was tested through the Reeves and Taillard instances, and the results were compared with other algorithms to verify effectiveness of the algorithm.
- 参考文献/References:
-
[1] 周明, 孙树栋. 遗传算法原理及应用[M]. 北京:国防工业出版社, 1999:6.
[2] 夏小云, 周育人. 蚁群优化算法的理论研究进展[J]. 智能系统学报, 2016, 11(1):27-36 XIA Xiaoyun, ZHOU Yuren. Advances in theoretical research of ant colony optimization[J]. CAAI transactions on intelligent systems, 2016, 11(1):27-36
[3] 李金忠, 夏洁武, 曾小荟, 等. 多目标模拟退火算法及其应用研究进展[J]. 计算机工程与科学, 2013, 35(8):77-88 LI Jinzhong, XIA Jiewu, ZENG Xiaohui, et al. Survey of multi-objective simulated annealing algorithm and its applications[J]. Computer engineering and science, 2013, 35(8):77-88
[4] TAYEB F B S, BESSEDIK M, BENBOUZID M, et al. Research on permutation flow-shop scheduling problem based on improved genetic immune algorithm with vaccinated offspring[J]. Procedia computer science, 2017, 112:427-436.
[5] CHEN Rongchang, CHEN J, CHEN T S, et al. Synergy of genetic algorithm with extensive neighborhood search for the permutation flowshop scheduling problem[J]. Mathematical problems in engineering, 2017, 2017:3630869.
[6] BESSEDIK M, TAYEB F B S, CHEURFI H, et al. An immunity-based hybrid genetic algorithms for permutation flowshop scheduling problems[J]. International journal of advanced manufacturing technology, 2016, 85(9/10/11/12):2459-2469.
[7] GANGULY S, MUKHERJEE S, BASU D, et al. A novel strategy adaptive genetic algorithm with greedy local search for the permutation flowshop scheduling problem[M]//Swarm, Evolutionary, and Memetic Computing. Berlin, Heidelberg:Springer, 2012:687-696.
[8] 齐学梅, 王宏涛, 陈付龙, 等. 求解多目标PFSP的改进遗传算法[J]. 计算机工程与应用, 2015, 51(11):242-247 QI Xuemei, WANG Hongtao, CHEN Fulong, et al. Improved genetic algorithm for multi-objective of PFSP[J]. Computer engineering and applications, 2015, 51(11):242-247
[9] 崔琪, 吴秀丽, 余建军. 变邻域改进遗传算法求解混合流水车间调度问题[J]. 计算机集成制造系统, 2017, 23(9):1917-1927 CUI Qi, WU Xiuli, YU Jianjun. Improved genetic algorithm variable neighborhood search for solving hybrid flow shop scheduling problem[J]. Computer integrated manufacturing systems, 2017, 23(9):1917-1927
[10] CHANG P C, HUANG W H, WU J L, et al. A block mining and re-combination enhanced genetic algorithm for the permutation flowshop scheduling problem[J]. International journal of production economics, 2013, 141(1):45-55.
[11] JIN Jian. A hybrid discrete biogeography-based optimization for the permutation flow shop scheduling problem[J]. International journal of production research, 2016, 54(16):4805-4814.
[12] DORIGO M, GAMBARDELLA L M. Ant colony system:a cooperative learning approach to the traveling salesman problem[J]. IEEE transactions on evolutionary computation, 1997, 1(1):53-66.
[13] 陈慧芬. 基于链结学习的子群体进化算法求解多目标调度问题[D]. 天津:天津理工大学, 2017. CHEN Huifen. Sub-population evolutionary algorithm based on linkage learning for multi-objective scheduling problem[D]. Tianjin:Tianjin University of Technology, 2017.
[14] 裴小兵, 陈慧芬, 张百栈, 等. 改善式BVEDA求解多目标调度问题[J]. 山东大学学报(工学版), 2017, 47(4):25-30 PEI Xiaobing, CHEN Huifen, ZHANG Baizhan, et al. Improved bi-variables estimation of distribution algorithms for multi-objective permutation flow shop scheduling problem[J]. Journal of Shandong University (engineering science), 2017, 47(4):25-30
[15] 裴小兵, 赵衡. 基于二元分布估计算法的置换流水车间调度方法[J]. 中国机械工程, 2017, 28(22):2752-2759 PEI Xiaobing, ZHAO Heng. Permutation flow shop scheduling problem based on hybrid binary distribution estimation algorithm[J]. China mechanical engineering, 2017, 28(22):2752-2759
[16] 张敏, 汪洋, 方侃. 基于改进区块进化算法求解置换流水车间问题[J]. 计算机集成制造系统, 2018, 24(5):1207-1216 ZHANG Min, WANG Yang, FANG Kan. Improved block-based evolutionary algorithm for solving permutation flowshop scheduling problem[J]. Computer integrated manufacturing systems, 2018, 24(5):1207-1216
[17] CHANG P C, CHEN Menghui. A block based estimation of distribution algorithm using bivariate model for scheduling problems[J]. Soft computing, 2014, 18(6):1177-1188.
[18] MILLER B L, GOLDBERG D E. Genetic algorithms, tournament selection, and the effects of noise[J]. Complex systems, 1995, 9(3):193-212.
[19] CHANG P C, CHEN S H, FAN C Y, et al. Generating artificial chromosomes with probability control in genetic algorithm for machine scheduling problems[J]. Annals of operations research, 2010, 180(1):197-211.
[20] HSU C Y, CHANG P C, CHEN M H. A linkage mining in block-based evolutionary algorithm for permutation flowshop scheduling problem[J]. Computers & industrial engineering, 2015, 83:159-171.
- 相似文献/References:
-
[1]李枝勇,马良,张惠珍.多目标0-1规划问题的蝙蝠算法[J].智能系统学报,2014,9(6):672.[doi:10.3969/j.issn.1673-4785.201310038]
LI Zhiyong,MA Liang,ZHANG Huizhen.Bat algorithm for the multi-objective 0-1 programming problem[J].CAAI Transactions on Intelligent Systems,2014,9():672.[doi:10.3969/j.issn.1673-4785.201310038]
[2]夏小云,周育人.蚁群优化算法的理论研究进展[J].智能系统学报,2016,11(1):27.[doi:10.11992/tis.201510002]
XIA Xiaoyun,ZHOU Yuren.Advances in theoretical research of ant colony optimization[J].CAAI Transactions on Intelligent Systems,2016,11():27.[doi:10.11992/tis.201510002]
[3]胡志强,李文静,乔俊飞.带扰动的变频正弦混沌神经网络研究[J].智能系统学报,2018,13(4):493.[doi:10.11992/tis.201703003]
HU Zhiqiang,LI Wenjing,QIAO Junfei.Frequency-conversion sinusoidal chaotic neural network with disturbance feature[J].CAAI Transactions on Intelligent Systems,2018,13():493.[doi:10.11992/tis.201703003]
[4]裴小兵,孙志卫.改进区块遗传算法解决分布式车间调度问题[J].智能系统学报,2021,16(2):303.[doi:10.11992/tis.201906035]
PEI Xiaobing,SUN Zhiwei.Solving distributed-shop scheduling problems based on modified genetic algorithm[J].CAAI Transactions on Intelligent Systems,2021,16():303.[doi:10.11992/tis.201906035]
备注/Memo
收稿日期:2018-01-23。
基金项目:国家创新方法工作专项项目（2017IM060200）；天津市哲学社会科学规划项目（TJYY17-013）.
作者简介:裴小兵,男,1965生,教授,博士,主要研究方向为生产调度、精益生产。发表学术论文14篇;张春花,女,1992生,硕士研究生,主要研究方向为生产调度、智能算法。
通讯作者:张春花.E-mail:Zhang_chunhua1203@126.com
更新日期/Last Update:
1900-01-01