基于链结学习的子群体进化算法求解多目标调度问题

发布时间：2018-07-04 10:14

  本文选题：多目标组合优化 + 链接学习技术　； 参考：《天津理工大学》2017年硕士论文

【摘要】：多目标优化问题(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Ⅱ,且规模较大的优势显著。
[Abstract]:The essence of Multi-Objective Optimization problem (MOP) is to realize the equilibrium of multiple objective functions under some constraint conditions. The permutation flow shop scheduling problem (PFSP) is one of its applications, because of the complexity of PFSP itself. The conflict between different targets and the inconsistency of multi-objective test data make the algorithm very challenging. This paper is based on Sub-population Evolutionary algorithm (SPEA). Chebyshevs Partition method and Linkage Learning technique (LLT) are proposed to solve the multi-objective permutation job-shop scheduling problem. After summing up the following improvements are made: (1) considering the distribution of subpopulation reconnection space, the uniform distribution of solution space is realized through H partition, and the weight is adjusted by Chebyshev method. Thus a better solution can be found. (2) in the subpopulation evolutionary algorithm, the binary variable probabilistic model with probability as the core is used for block mining and block competition, and the post-block database is constructed for artificial chromosome AC and injected into the evolution process. In order to improve the quality of the solution, the crossover method is carried out simultaneously, and the non-dominant solution is crossed with the superior dominant solution after the selection of subpopulations, and the non-dominant solution is mutated, and a certain number of crossover and variation is set up in order to find a more extensive solution for screening. In order to compare the performance of the algorithm, in the Taillard standard example test, the superiority of Chebyshev is proved by comparing the quantity (number of efficient solutionsNess of the efficient solutions obtained by Chebyshev and the linear weights and the average distance between Chebyshev and the reference set (reference sets). Secondly, in order to prove the validity of the bivariate probabilistic model, the distribution of the solutions of algebras 100 and 200 and their solutions on the example of ta01010 / ta020 / ta050 / ta060 / ta080 is compared with that of the subpopulation genetic algorithm 鈪，

本文编号：2095731