基于差分进化的金字塔演化策略求解一维下料问题

Pyramid Evolution Strategy Based on Differential Evolution for Solving One-dimensional Cutting Stock Problem

一维下料问题是组合优化中一类经典的NP-hard问题,被广泛用于机械制造及工程应用等领域。针对传统群智能算法在求解该类问题时难以平衡种群内部个体及种群之间开采与探索、竞争与协作矛盾的问题,在金字塔演化策略(Pyramid Evolution Strategy,PES)的基础上,提出了求解一维下料问题的基于差分进化的PES算法。该算法充分利用PES算法的优势,很好地解决了以上两个矛盾;但是由于PES算法未考虑种群当前个体与最优个体之间的协作关系,因此其收敛速度较慢。为此,在PES算法的加速过程中引入差分进化的变异、交叉操作,并对产生的不可行试验个体进行修复,使得算法能够充分利用种群个体间的差异信息,这一方面有利于加快算法的收敛速度,另一方面可以实现对新个体附近区域的局部开采,有利于提高算法的求解精度。将提出的算法应用于6组一维下料算例,实验结果表明,与其他8种算法相比,所提算法在求解精度和收敛速度上均有更好的性能表现,验证了该算法求解一维下料问题的可行性和有效性。

One-dimensional cutting stock problem is a classic NP-hard problem in combinatorial optimization,which is widely used in mechanical manufacturing and engineering applications.It is difficult for traditional swarm intelligence algorithm to ba-lance the contradictions of mining and exploration,competition and cooperation between individuals and populations with in a po-pulation when solving one-dimensional cutting stock problem.On the basis of pyramid evolution strategy,an algorithm based on pyramid evolution strategy and differential evolution is proposed in this paper.The algorithm makes full use of the advantages of the PES algorithm and solves these two contradictions well,but the PES algorithm does not consider the cooperative relationship between the current individual and the optimal individual,it may lead the convergence speed of the algorithm to be slowly.To this end,the mutation and crossover operations of differential evolution are introduced into the accelerating process of PES algorithm,and the invalid individuals are corrected by the repair operator.On the one hand,it is conducive to speed up the convergence speed of the algorithm,on the other hand,it can utilize the differences among individuals and realize the local mining of the area near the individuals in the population,which is beneficial to improve the accuracy of the algorithm.The proposed algorithm is applied to six examples.The experimental results show that the algorithm has high optimization accuracy and convergence speed compared with other eight algorithms,which verifies the feasibility and effectiveness of the algorithm for solving the one-dimensional cutting stock problem.