应用改进混合进化算法求解零空闲置换流水车间调度问题

发布时间：2025-01-20 15:55

　　 针对总拖期时间最小化的零空闲置换流水车间调度问题,提出了一种基于关键块结构的混合进化算法。该算法以遗传算法为框架,设计了依据关联规则计算染色体上基因之间关联强度的方法,以便挖掘优势染色体上的优势基因组成关键块,并在优势关键块的基础上构建具有较优解的人工染色体种群。同时,引入双精英进化机制,提高算法交叉和变异的有效性,避免算法的无效交叉。精英进化产生的子代种群依据关联规则挖掘关键块,基于交换邻域结构,结合NEH算法的思想,互换非关键块上工件之间的位置,得到局部搜索解。最后,通过对Taillard基准问题进行仿真测试,并将本文算法运行结果与其他算法进行比较,验证了算法的有效性。

【文章页数】：9 页

【部分图文】：

图3关键块筛选2．3构建人工染色体种群

，直到穷尽所有大于阈值的基因关键块。图2给出上述步骤关键块挖掘构建的过程。2．2．3关键块筛选本研究运用关联规则数据分析方法产生关键块，将单个基因作为候选项目集向外延伸。将关键块的长度设置为2，对关键块暂存器中的关键块的工件与机器进行对比，若关键块之间出现重复的工件或涵盖的机器出....

图1数据编码

(7)lift=c(x→y)s(y)(8)为使关联法则成立且有意义，需设立最小支持度和最小信心水平，当运用关联规则进行挖掘时，超过所设立的阈值，才能认定为有意义的信息。2．2．2构建与挖掘区块关键块是一个具有高度竞争优势的基因结构，对于降低所求问题的复杂度具有显著的效果。本研究通....

图4人工染色体组合机制2．4双精英协同进化

排的机器位置，直到人工染色体完成组合。人工染色体的组合方式如图4所示。图4人工染色体组合机制2．4双精英协同进化2．4．1协作变异机制协同进化是改善进化算法性能的有效途径［21］，它将个体拆分成多个子集，每个子集对应一类决策，子集独立进化，将进化后的子集组合成完整的解，对完整的解....

图9优势种群保留

?邢乱皇来?难莼?。符号表示及步骤如下所示:AC:代表人工染色体种群，AC={AC1，AC2，…，ACn};O:代表精英进化染色体种群，O={O1，O2，…，On}。步骤1将人工染色体种群AC及所产生的精英进化染色体种群O混合放入选择池中;步骤2从选择池中随机选择两条解，将适应度....

本文编号：4029348