论文部分内容阅读
多目标优化问题(Multi-objective Optimization Problem,MOP)的本质是在某种约束条件下实现多个目标函数的均衡,多目标置换流水车间调度问题(Permutation Flow Shop Scheduling Problem,PFSP)是其应用之一,因PFSP自身复杂程度高、不同目标之间的冲突、多目标测试数据不统一等使求解算法极具挑战性。本文基于子群体进化算法(Sub-population Evolutionary Algorithm,SPEA)、分群、切比雪夫权重分割法(Chebyshev’s Partition Method)和链接学习技术(Linkage Learning technique,LLT)等提出基于链接学习的子群体进化算法(Sub-population Evolutionary Algorithm based on Linkage Learning,SEABLL),以求解多目标置换流水车间调度问题,经总结做出以下改善工作:(1)考虑子群体再接空间的分布,透过H划分群体尽可能实现解空间上的均匀分布,利用切比雪夫方法调控权重,从而能够找到更好的解。(2)在子群体进化算法中,利用以概率为核心的二元变量概率模型进行区块挖掘和区块竞争,构建区块后暂存数据库供LLT组合人造解(artificial chromosome,AC)并注入演化过程,提高解的质量,交叉方法同时进行,利用子群体筛选后的非支配解与优质支配解进行交叉,非支配解进行变异,并设置一定数量的进行交叉与变异以便找更广泛的解以供筛选。为比较算法的性能,在Taillard标准例题测试,首先对比切比雪夫和线性权重所求的有效解的数量(number of efficient solutions,NES)和与参考集(reference set,RS)的平均距离(average distance,Dav),证明切比雪夫的优越性。其次,为证明双变量概率模型的有效性,设置代数100和200及其与子群体遗传算法Ⅱ(sub-population genetic algorithmⅡ,SPGAⅡ)在例题ta010、ta020、ta050、ta060、ta080上的解的分布的对比,证明所提SEABLL分布较好。最后在ta001-ta092上39个标准测试例题中比较SEABLL与SPGAⅡ两种算法所求非支配解数量(number of non-dominated solutions,NNDS)、证明92%的例题优于SPGAⅡ,且规模较大的优势显著。