一种基于多子群粒子群算法的二维不规则排样方法

技术领域

本发明涉及计算机辅助排样技术，尤其是一种排样方法。

背景技术

目前，国内外对不规则零件的排样方法基本集中在启发式的现代 优化方法中，主要有模拟退火算法、遗传算法、粒子群算法（PSO） 等。在实践中，由于模拟退火算法受退火速度的影响，速度快，容易 陷入局部极值，速度慢则很难不能满足人们的需要；遗传算法则往往 比较容易“早熟”，且局部搜索能力较差；PSO算法具有较强的局部 搜索能力，但也容易陷入极值区域而很难跳出。

排样问题的应用范围非常广泛，如钣金排样、玻璃裁制、服装剪 裁等，由于上述产业生产量大，特别是有些材料较为昂贵，因此，排 样算法效率的提高可以产生很大的社会效益。

发明内容

为了克服已有排样方法的容易陷入极值区域、影响了排样效果的 不足，本发明提供一种具有良好搜索能力的同时、搜索速度快、最终 解较佳、排样效果良好的基于多子群粒子群算法的二维不规则排样方 法。

本发明解决其技术问题所采用的技术方案是：

一种基于多子群粒子群算法的二维不规则排样方法，包括以下步 骤：

第一步，将样片和材料的几何图形转换为一系列的二维坐标区间，然 后使用启发式底左搜索算法来判断样片与材料的二维区间的是否重叠 来移动样片相对于材料中的位置；

第二步，改进型PSO搜索过程如下：

1)以样片排入后的高度的倒数作为适应度值，适应度值1/H越大 则排入效果越好；

2)各个样片的排入状态主要有三种：排入次序、旋转角度和镜像， 所述排入次序order的取值范围1～n，n为样片总数；旋转角度 angle的取值范围0°～360°，镜像mirror表示是否关于y轴对称， 0～1，0表示不关于y轴对称，1表示关于y轴对称；

3)将2）中提出的三个参数作为构成粒子群中的基本粒子的三个 元素，随机初始化所述基本粒子；

4)计算每个粒子的欧式几何位置，按照离原点距离的从小到大的 顺序将所有粒子分为M个子群，M＜n；

5)各参数设置如下：

x_ij=〈order_ij，angle_ij，mirror_ij〉

第i个子群中第j个粒子的位置向量；

v_ij=〈v_ord_ij，v_ang_ij，v_mir_ij〉

第i个子群中第j个粒子的速度向量；

p_ij=〈p_ord_ij，p_ang_ij，p_mir_ij〉

第i个子群中第j个粒子的历史最佳位置向量；

psg_i=〈psg_ord_i，psg_ang_i，psg_mir_i〉

第i个子群历史最佳位置向量；

p_g=〈pg_ord，pg_ang，pg_miri〉

全局历史最佳位置向量；

6)粒子的速度与位置更新公式如下所示：

v_ij(d＋1)=w×v_ij(d)＋c₁×rand_1ij×[p_ij(d)-x_ij(d)]

+c₂×rand_2ij×[psg_i(d)-x_ij(d)]

+c₃×rand_3ij×[p_g(d)-x_ij(d)]

x_ij(d+1)=x_ij(d)+v_ij(d+1)

其中d为迭代次数，c_l、c₂、c₃分别表示趋向粒子本身历史最 优解、子群的最优解、全局最优解的速度控制因子，其中 c₃＞c₂＞c_l＞0,rand_1ij、rand_2ij、rand_3ij为0～1之间的 随机因子，w为惯性因子，w的值w（d）随迭代次数的增加 而线性递减：

w(d)=u-v×d/D

D为最大迭代次数，u，v的值满足；

7)更新历史最优解

每个粒子进行速度更新之后，通过启发式底左搜索算法排入材 料中，计算出粒子的适应度值F，从而更新粒子本身的历史最 优位置，子群以及全局的最优位置；

8)当粒子群的迭代次数达到了初始时设定的最大迭代次数时，粒 子停止迭代，取得当前的全局最优解作为最终排样方案；若未 达到最大迭代次数，继续从步骤6）开始执行。

进一步，所述步骤7）中，当某个子群在连续n次迭代过程中都 未找到更优解时，判定该子群陷入了局部最优解，对所述子群的随机 重置。

更进一步，所述第一步中，启发式底左搜索算法得到过程如下： 样片先从材料的左下角排入，后面的样片往右依次排入，当样片超出 材料的右侧时，将样片相对于材料上移，并从左边开始重新搜索材料 的剩余空间，如此循环往复，直至样片全部排入或样片溢出材料顶部 时停止。

本发明的技术构思为：通过划分多个子群的方法，在不改变趋向 当前最优解的参数的情况下，加入了子群最优解对子群中粒子的影响， 以此增强局部搜索能力，并在子群陷入局部极值时，对子群进行淘汰 重置，使群体有机会跳出局部极值。

本发明的有益效果主要表现在：具有良好搜索能力的同时、搜索 速度快、最终解较佳、排样效果良好。

附图说明

图1为二维不规则排样底层算法的程序流程图。

图2为改进型PSO算法的程序流程图。

图3为某套服装样片基于本发明的排样效果图。

具体实施方式

下面结合附图对本发明作进一步描述。

参照图1～图3，一种基于多子群粒子群算法的二维不规则排样方 法，包括以下步骤：

第一步，二维不规则排样底层算法的选择

对于处理二维不规则样片的排版，首先需要确定样片的轮廓，以 便在样片排入过程中判断各样片是否会重叠，本发明选择将样片和材 料的几何图形转换为一系列的二维坐标区间，从而脱离不规则几何图 形的复杂性进行排样，然后使用启发式底左搜索算法（HBLS）来判断 样片与材料的二维区间的是否重叠来移动样片相对于材料中的位置， 以此完成二维不规则排样的底层算法，其流程可参照图1。

HBLS算法的基本思路是：样片先从材料的左下角排入，后面的样 片往右依次排入，当样片超出材料的右侧时，将样片相对于材料上移， 并从左边开始重新搜索材料的剩余空间，如此循环往复，直至样片全 部排入或样片溢出材料顶部时停止。

第二步，改进型PSO搜索算法

1)有了底层的样片排入算法，就可通过搜索算法将样片排入的状 态参数传递给底层算法进行处理，从而算出每个个体的适应度 值F（本发明以样片排入后的高度的倒数（1/H）作为适应度 值，适应度值越大则排入效果越好）。

2)各个样片的排入状态主要有三种：排入次序（order,1～n，n为 样片总数）、旋转角度（angle，0°～360°）、镜像（mirror， 关于y轴对称，0～1）

3)将2）中提出的三个参数作为构成粒子群中的基本粒子的三个 元素，这里将粒子的总数设定为30个，并随机初始化这30 个粒子。

4)计算每个粒子的欧式几何位置，按照离原点距离的从小到大的 顺序将30个粒子分成5份，每份6个粒子，即分成了5个子 群。根据欧式几何距离划分的目的是为了在初始状态让各子群 尽量分布在不同区域，增强算法的全局搜索能力。

5)各参数设置如下：

x_ij=(order_ij,angle_ij,mirror_ij〉

第i个子群中第j个粒子的位置向量

v_ij=〈v_ord_ij，v_ang_ij，v_mir_ij〉

第i个子群中第j个粒子的速度向量

p_ij=〈p_ord_ij，p_ang_ij,p_mir_ij〉

第i个子群中第j个粒子的历史最佳位置向量

psg_i=〈psg_ord_i，psg_ang_i，psg_mir_i〉

第i个子群历史最佳位置向量

p_g=<pg_ord，pg_ang，pg_miri>

全局历史最佳位置向量

6)粒子的速度与位置更新公式如下所示：

v_ij(d+1)=w×v_ij(d)+c₁×rand_1ij,×[p_ij(d)-x_ij,(d)]

+c₂×rand_2ij×[psg_i(d)-x_ij(d)]

+c₃×rand_3ij×[p_g(d)-x_ij(d)]

x_ij(d+1)=x_ij(d)+v_ij(d+1)

其中d为迭代次数，由此可知，粒子每一代的更新由上一代的 数据来确定，c_l、c₂、c₃分别表示趋向粒子本身历史最优解、 子群的最优解、全局最优解的速度控制因子，其中 c₃＞c₂＞c_l＞0，rand_1ij、rand_2ij、rand_3ij为0～1之间的 随机因子，w为惯性因子，当w较大时，算法对解空间大范围 搜索；反之，算法进行小范围搜索，w的值随迭代次数的增 加而线性递减：

w(d)=u-v×d/D

D为最大迭代次数，u，v的值满足O＜v＜u＜1。

在经典PSO算法中，粒子的速度更新公式为：

v_ij(d+1)=w×v_ij(d)+c′₁×rand_1ij×[p_ij(d)-x_ij(d)]

+c′₃×rand_3ij×[p_g(d)-x_ij(d)]

与改进的PSO算法参数对比，有如下关系：

c′_l=c_l+c₂

c′₃=c₃

改进型PSO算法加入了子群的概念，并在速度更新公式中加入 了子群最优解的影响，增强局部搜索，但是c₃没有改变，从 而保证了算法收敛于较优解的趋势不被减弱。

7)更新历史最优解

每个粒子进行速度更新之后，通过底层排样算法排入材料中， 计算出粒子的适应度值F，从而更新粒子本身的历史最优位 置，子群以及全局的最优位置。

8)子群的淘汰与重置机制

针对PSO算法容易陷入局部最优解的问题，本发明中加入了子 群的子群的淘汰与重置机制，当某个子群在连续n次迭代过程 中都未找到更优解时，那么，认为该子群陷入了局部最优解， 此时通过对子群的随机重置，可使该子群有机会跳出局部最优 解，从而增强了算法的全局搜索能力。

9)当粒子群的迭代次数达到了初始时设定的最大迭代次数时，粒 子停止迭代，取得当前的全局最优解作为最终排样方案。若未 达到最大迭代次数，继续从步骤6）开始执行。

参照图3，本发明的排样效果图，（材料宽度：1200mmm，样片 数：18，迭代次数：600，排样高度H：901mm，材料利用率：78.1%）。