一维下料的基于贪心策略的多目标自适应粒子群算法优化

Multi⁃objective adaptive particle swarm algorithm optimization based on greedy strategy for one⁃dimension cutting stock problem

针对一维下料问题,提出一种基于贪心策略的多目标自适应粒子群算法,在余料率最低和下料方式数量最少两个目标上进行优化。通过将贪心策略应用于粒子群算法,把一维下料问题分割成多个子问题,对每个子问题依次求全局最优解,有效缩小单次处理问题的规模,由所有子问题的最优解取得原问题的近似最优解。为解决种群过早收敛而因此陷入局部最优,设计一种自适应策略。此外,考虑到切换下料方式会产生一定成本,通过最大化当前下料方式使用次数优化下料方式数量。仿真实验结果表明,该算法收敛速度快,取得的下料方案利用率高且下料方式数量较少,具备较好的实用性,并能够为企业带来显著的经济效益。

The multi⁃objective adaptive particle swarm algorithm optimization based on greedy strategy is proposed for the one⁃dimension cutting stock problem,which is optimized in the two aspects of the lowest surplus rate and the minimum number of cutting stock ways.By applying the greedy strategy into the particle swarm algorithm,the one⁃dimension cutting stock problem is divided into multiple sub⁃problems,the global optimal solution of each sub⁃problem are found in turn(which can effectively reduce the scale of single processed problem),and the approximate optimal solution of the original problem is obtained from the optimal solution of all sub⁃problems.An adaptive strategy is designed to prevent the population is trapped into local optimum due to the premature convergence.In consideration of the cost of switching cutting stock ways,the quantity of cutting stock way is optimized by maximizing the number of times that the current cutting stock way is used.The simulation experimental results show this algorithm has fast convergence speed,the utilization rate of the obtained cutting stock plan is high,and the used cutting stock ways are fewer.It has a certain practicability and can bring significant economic benefits to enterprises.