基于区块挖掘与重组的启发式算法求解置换流水车间调度问题

Heuristic Algorithm Based on Block Mining and Recombination for Permutation Flow-shop Scheduling Problem

组合优化广泛应用于任务问题,例如旅行推销员问题(Traveling Salesman Problem,TSP)、调度问题等。文中提出基于进化式的区块模型(Evolutionary-Based Block Model,EBBM)来提升优化算法的收敛效果,以避免陷入局部优化困境。区块的主要思想是从染色体中找到关键区块,并使用这些区块来改进进化式算法(Evolutionary Algorithms,EAs)以求解组合优化问题(Combinatorial Optimization Problems,COPs)。区块是一种挖掘染色体中基因对演化影响的信息,包含了对进化有帮助的信息以及阻碍进化的信息,所提方法借助区块信息指引算法的演化方向,通过两种不同信息的相互影响,不仅提高了算法的收敛速度,还提高了算法求解的多样性,从而达到求解稳定性高和求解质量优良的目标。文中提出的区块机制包括构建概率矩阵,通过关联规则生成区块并应用块来构建人造染色体。由于将区块作为构建人造解的基本单位,因此通过关联规则所挖掘的区块不仅具有多样性,还能按照设定置信度的大小控制演化过程所需的区块信息强度。最后为评估所提算法的求解能力,以置换流水车间调度问题(Permutation Flow-shop Scheduling Problem,PFSP)为测试的例题,采用平均误差率、最佳误差率以及收敛曲线图探讨算法的求解效果。实验结果表明,通过正反信息所产生的区块机制有助于提高收敛效果,且可避免陷入局部优化问题。

Combinatorial optimization is widely used in task problems,such as traveling salesman problem(TSP),scheduling problems.In this study,an evolutionary-based block model(EBBM)was proposed to enhance the speed of convergence so as to avoid premature convergenceproblem.The main idea of blocks is to find key blocks from chromosomes and use these blocks to improve evolutionary algorithms(EAs)to solve combinatorial optimization problems(COPs).Block is a kind of information that explores the effects of individual genes on the evolution of chromosomes,containing information that is helpful for evolution and information that hinders evolution.In this paper,these two different kinds of information are stored and used.The evolution direction of the information providing algorithm,through the influence of two different information,not only improves the convergence speed of the algorithm,but also improves the diversity of the algorithm solution,so as to achieve goals of high stability and good solution quality.The block mechanism proposed includs building a probability matrix,generating blocks by associated rule and applying blocks to construct artificial chromosomes.Since the block is used as the basic unit for constructing the artificial solution in this paper,the blocks mined by the association rules not only have diversity,but also control the block information strength required for the evolution process according to the set confidence level.Finally,in order to confirm the quality of solutions,the proposed approach is experimentally implemented on permutation flow-shop scheduling problem(PFSP).According to the average error rate,the optimal error rate and the convergence curve,the solution effect of the algorithm is discussed,the experimental results show that the block mechanism by positive and negative information is useful to improve the speed of convergence and avoid premature convergence problem.In additional,the results also demonstrate that BBEM is applicable and efficient to the COPs.