基于混沌粒子群算法的多目标二维切割问题

摘要

多维切割问题是木材加工、机加工和造纸等行业在生产中经常遇见的实际问题。排样切割完成后，往往都会有一些大小不等、数量不同的剩余材料。本文优化利用这些材料，进一步减少浪费。通过和贪心启发式^法的比较，证明该混合算法对解决多目标二维切割问题是行之有效的。

【关键词】多目标切割问题 粒子群算法 混沌粒子群算法

二维切割问题在轻 工、排版、玻璃切割等行业的广泛应用，国内外对矩形件排样优化的问题己经做了相当深入的研究，实现了提高板材利用率、缩短排样时间的目的。但在排样切割完成后，往往都会有一些大小不等，数量不同的剩余材料，如何更好地再次利用这些材料，这就是本文所要讨论的内容。

1多目标二维切割问题数学模型

l.1问题描述及建模

本文只考虑剩余的材料是矩形的情况，针对一定数量和大小的零件需求，建立数学模型。由于所剩余的材料大小不等，这类切割问题被定义为多目标的切割问题。

解决复杂的排样问题的二维优化下料模型一般都是构造成线性规划的数学模型，以原材料消耗的总面积最小为目标，但是对于我们所要讨论的情况，仅仅考虑消耗的总面积最小是不够的，还要考虑所用原料的种类最少。

设原材料板材，其长、宽、数量分别记为（Li，Wi，di），其中i=1，2，…，n，待下料的零件的长、宽、数量记为（li，wi，bi），求如何下料使所用原材料的总消耗最小且所用原材料的种类最少。可用如下数学模型来描述：

上述模型是一个大型整数线性规划模型，随着原板材种类的增加，下料方式总数也将急剧增加，导致用单纯形法或分支定界法很难求解。

2混沌粒子群算法

粒子群优化（PSO）算法是在1995年由Kennedy和Eberhart提出的，它是一种集群智能方法的演化计算技术。PSO算法思想就是跟踪最的好点，并逐渐向最好的点靠近。该算法收敛速度快，但和其它全局优化算法一样，PSO算法同样存在容易收敛早熟的现象。

混沌则是一种普遍的非线性现象，它的基本思想是把变量从混沌空间变换到解的空间，它的行为复杂并且类似随机，混沌变量具有遍历性、随机性、规律性特点。尤为重要的是，该算法的遍历性特点可以用做算法搜索过程中避免陷入局部最优的一种优化机制。

综上所述，根据粒子群算法和混沌优化方法各自的优缺点，本文提出了将混沌算法迭代引入粒子群算法中，组成新的混合算法一_混沌粒子群优化算法（CPSO）。该混合算法的主要思想是将混沌融合到粒子运动中，避免陷入局部最优，可以达到较好的效果。

该混合算法步骤如下：

Step1首先设置参数，初始化所有粒子（设群规模为N），随机设置粒子的初始速度和初始位置，计算其中每个粒子的适应度，设置其中每个粒子的个体最优点Pbest，Pbest里的最好设为gbest。

Step2计算粒子新的飞翔位置和飞翔速度，同时更新粒子的最初位置和速度。检验粒子新位置是否在所设置的约束区域内，如果在，就将粒子的位置和速度更新为新计算出的值；否则不更新。

Step3检验每个粒子的适应值，若现值优于Pbest，，就用当前的位置替换Pbest；若所有粒子中有优于gbest的，就重新设置gbest。

Step4根据公式Pi，n+1=Pi，n+citi，n-di更新每个粒子的Pbest的位置，并计算它的函数值。如果比之前的值优，就更新Pbest。再遍历出所有粒子中Pbest的函数值优于gbest的，并且重置gbest。根据式ti，n+1=μti，n（1-ti，n）更新ti，n+l。

Step5根据公式g*=g*+citn-di重新确定gbest的位置，并计算出它的函数值。若这个值比更新前的優就重置；否则，不更新。根据公式tn=μtn（1-tn）更新tn的值。

Step6检查终止条件，若己经达到所设置的最大迭代次数或最优解不再变化，就跳出当前迭代，输出最优值。否则，转Step2。

3混沌粒子群算法求解多目标二维切割问题与贪心启发式算法[6]的比较

文献6中，通过贪心启发式算法解决了一个多目标二维切割的实际问题，但是容易陷入局部最优，而该混沌粒子群算法更容易跳出局部最优，如图1所示。

4结论

本文重点讨论了多目标二维下料问题的解法，即采用混沌粒子群算法的近似求解，该算法简明，易于编程。实践证明，采用该算法能得到很好的解。

参考文献

[1]Beasley J.E.Algorithms for Unconstrained two-dimensional Guillotine Cutting，Journal on Operation Research Society，Vol36，pp.297-306，1985.

[2]Beasley J.E.An Exact two-dimensional Non-guillotine cutting Tree Search Procedure，Journal of Operation Research Society，Vo33，pp.49-64，1985.

[3]李友如，阎春平，刘飞.基于二维约束Non-Guillotine切割的插补算法[J].重庆大学学报（自然科学版），2002（10）.

[4]KwnndeyJ，Eberhart R.Particle swarm optimization.In：Proc IEEE International conference on Neural Networks，Perth，Australia，1995，1942-1948.

[5]李兵，蒋慰孙.混沌优化方法及其应用[J].控制理论与应用，1997，14（04）：613-615.

[6]熊慧，黄菊永.基于贪心启发式算法的多目标二维切割问题[J].电子技术与软件工程，2017.endprint