针对以最小化最大完工时间、最小化最大拖期和最小化总流程时间为目标的置换流水车间调度问题(permutation flow shop scheduling problem,PFSP),基于双变量分布估计法(bi-variable estimation of distribution algorithm,BVEDA)提出改...针对以最小化最大完工时间、最小化最大拖期和最小化总流程时间为目标的置换流水车间调度问题(permutation flow shop scheduling problem,PFSP),基于双变量分布估计法(bi-variable estimation of distribution algorithm,BVEDA)提出改善式双变量分布估计算法(Improved BVEDA,IBVEDA)进行求解。利用BVEDA中双变量概率模型进行区块构建,根据组合概率公式进行区块竞争和区块挖掘,借用高质量的区块组合人造解,提高演化过程中解的质量;针对算法多样性较差的特点,设计在组合人造解的过程中加入派工规则最短处理时间、最长处理时间和最早交货期,将上述方法并行演化,通过top10的权重适度值总和动态调整上述方法处理的解的数量,最后利用帕累托支配筛选和保存非支配解。试验使用C++代码在Taillard标准算例上测试,IBVEDA与SPGAⅡ和BVEDA比较,并绘制解的分布图证实算法的有效性。展开更多
In this research, we introduce a new heuristic approach using the concept of ant colony optimization （ACO） to extract patterns from the chromosomes generated by previous generations for solving the generalized trave...In this research, we introduce a new heuristic approach using the concept of ant colony optimization （ACO） to extract patterns from the chromosomes generated by previous generations for solving the generalized traveling salesman problem. The proposed heuristic is composed of two phases. In the first phase the ACO technique is adopted to establish an archive consisting of a set of non-overlapping blocks and of a set of remaining cities （nodes） to be visited. The second phase is a block recombination phase where the set of blocks and the rest of cities are combined to form an artificial chromosome. The generated artificial chromosomes （ACs） will then be injected into a standard genetic algorithm （SGA） to speed up the convergence. The proposed method is called ＂Puzzle-Based Genetic Algorithm＂ or ＂p-ACGA＂. We demonstrate that p-ACGA performs very well on all TSPLIB problems, which have been solved to optimality by other researchers. The proposed approach can prevent the early convergence of the genetic algorithm （GA） and lead the algorithm to explore and exploit the search space by taking advantage of the artificial chromosomes.展开更多
文摘针对以最小化最大完工时间、最小化最大拖期和最小化总流程时间为目标的置换流水车间调度问题(permutation flow shop scheduling problem,PFSP),基于双变量分布估计法(bi-variable estimation of distribution algorithm,BVEDA)提出改善式双变量分布估计算法(Improved BVEDA,IBVEDA)进行求解。利用BVEDA中双变量概率模型进行区块构建,根据组合概率公式进行区块竞争和区块挖掘,借用高质量的区块组合人造解,提高演化过程中解的质量;针对算法多样性较差的特点,设计在组合人造解的过程中加入派工规则最短处理时间、最长处理时间和最早交货期,将上述方法并行演化,通过top10的权重适度值总和动态调整上述方法处理的解的数量,最后利用帕累托支配筛选和保存非支配解。试验使用C++代码在Taillard标准算例上测试,IBVEDA与SPGAⅡ和BVEDA比较,并绘制解的分布图证实算法的有效性。
文摘In this research, we introduce a new heuristic approach using the concept of ant colony optimization （ACO） to extract patterns from the chromosomes generated by previous generations for solving the generalized traveling salesman problem. The proposed heuristic is composed of two phases. In the first phase the ACO technique is adopted to establish an archive consisting of a set of non-overlapping blocks and of a set of remaining cities （nodes） to be visited. The second phase is a block recombination phase where the set of blocks and the rest of cities are combined to form an artificial chromosome. The generated artificial chromosomes （ACs） will then be injected into a standard genetic algorithm （SGA） to speed up the convergence. The proposed method is called ＂Puzzle-Based Genetic Algorithm＂ or ＂p-ACGA＂. We demonstrate that p-ACGA performs very well on all TSPLIB problems, which have been solved to optimality by other researchers. The proposed approach can prevent the early convergence of the genetic algorithm （GA） and lead the algorithm to explore and exploit the search space by taking advantage of the artificial chromosomes.
