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

发布时间：2021-03-09 06:40

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

【文章来源】：计算机科学. 2020,47(S1)北大核心

【文章页数】：6 页

【部分图文】：

合并后支持度挖掘工件

区块存储至缓存资料库

本文的目标是运用区块来增强生成可行解时的重组性能,并使用B-区块来降低错误位置的概率。区块重组是重排混乱的区块从而形成适当的序列。本文提出一个“基于区块的模型”(Block-Based Model,BBM)。BBM定义为三元组(H,S,R),其中H是具有固定基因长度的非空块的有限集合,其可以随着问题的大小而变化,S是不在区块中的其余作业,R为组合区块方法。上述模型的示意图如图3所示。在R1中,染色体(可行解)是通过区块优先的选择方式来创建的,而在R2中染色体是通过概率矩阵优先的方式创建的,然后再放入区块。通过R1构建可行解时,首先放入区块,然后在使用轮盘赌法填满剩余的位置之前,使用B-区块来降低B-区块中包含信息的概率。下面以一个简单的例子进行说明。


本文编号：3072432