改进激素算法求解置换流水车间调度问题  

Improved Hormone Algorithm for Solving the Permutation Flow Shop Scheduling Problem

作　　者：郑堃 练志伟 王玉国 朱长建 顾新艳 刘轩 ZHENG Kun;LIAN Zhiwei;WANG Yuguo;ZHU Changjian;GU Xinyan;LIU Xuan(School of Automotive and Rail Transit,Nanjing Institute of Technology Nanjing 211167;Sino-German Intelligent Manufacturing Research Institute,Nanjing 211800)

机构地区：[1]南京工程学院汽车与轨道交通学院,南京211167 [2]中德智能制造研究院,南京211800

出　　处：《电子科技大学学报》2022年第6期890-903,共14页Journal of University of Electronic Science and Technology of China

基　　金：国家自然科学基金(51805244);国家重点研发计划项目(2018YFE011700)。

摘　　要：遗传算法中由于激素调节的选择、交叉以及变异算子存在较大目标函数值失调的问题,提出了基于改进激素浓度计算法的自适应遗传算法(IHCCM-IAGA)。IHCCM-IAGA采用基于工件排列的编码方式,并利用反向学习法初始化种群,提高了初始解的质量;针对两点交叉(TPX)算子存在冗余度高、效率低等问题,提出了改进型TPX(ITPX),并引入优良基因库及免疫因子,实现两种交叉方式,同时监控整个进化过程,避免了优质染色体的丢失;设计了多种扰动保持丰富的多样性结构以及相关的局部搜索算法组合成变异算子,建立种群湮灭算子,并设置湮灭因子来引导变异算子中的局部搜索。将IHCCM-IAGA应用于置换流水车间调度问题中,并进行该问题标准算例的各项测试,结果表明IHCCM-IAGA切实有效。Based on the large objective function value imbalance problem of selection,crossover and mutation in hormone-regulation based genetic algorithm,an adaptive genetic algorithm based on improved hormone concentration calculation method(referred to as IHCCM-IAGA)is proposed.IHCCM-IAGA adopts the coding method based on the arrangement of work pieces,and uses the reverse learning method to initialize the population,which improves the quality of the initial solution.Aiming at the problems of high redundancy and low efficiency in the two-points crossover(TPX)operator,an improved TPX(improved two-points crossover,ITPX)is proposed,and the introduction of excellent gene pool and immune factors realizes two crossover methods and monitors the entire evolution process,avoiding the loss of high-quality chromosomes.A variety of perturbations are designed to maintain a rich diversity structure and related local search algorithms are combined into a mutation operator.A population annihilation operator is established and an annihilation factor is set to guide the local search in the mutation operator.IHCCM-IAGA is applied to the permutation flow shop scheduling problem,and various tests of the standard calculation example of the problem are performed.The results show that IHCCM-IAGA is effective.

关 键 词：优良基因库 激素浓度 激素调节机制 改进型TPX 置换流水车间调度问题 反向学习法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]