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

Improved Hormone Algorithm for Solving the Permutation Flow Shop Scheduling Problem

  • 摘要: 遗传算法中由于激素调节的选择、交叉以及变异算子存在较大目标函数值失调的问题,提出了基于改进激素浓度计算法的自适应遗传算法(IHCCM-IAGA)。IHCCM-IAGA采用基于工件排列的编码方式,并利用反向学习法初始化种群,提高了初始解的质量;针对两点交叉(TPX)算子存在冗余度高、效率低等问题,提出了改进型TPX (ITPX),并引入优良基因库及免疫因子,实现两种交叉方式,同时监控整个进化过程,避免了优质染色体的丢失;设计了多种扰动保持丰富的多样性结构以及相关的局部搜索算法组合成变异算子,建立种群湮灭算子,并设置湮灭因子来引导变异算子中的局部搜索。将IHCCM-IAGA应用于置换流水车间调度问题中,并进行该问题标准算例的各项测试,结果表明IHCCM-IAGA切实有效。

     

    Abstract: 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.

     

/

返回文章
返回