服装矩形件样板排样中QPSO算法的应用 本文关键词：矩形，样板，算法，服装，QPSO
服装矩形件样板排样中QPSO算法的应用 本文简介：摘要： 基于皮革服装的CAD技术,采用改进的粒子群算法模型即QPSO算法模型,来对于服装矩形件样板的优化排样进行了比较分析研究。排放算法选择最低水平线法,在优化排样领域引入具有量子行为的QPSO算法,对矩形件排样采用量子行为的QPSO算法模型进行优化求解,经过和传统的算法模型结果进行比较,可获得量子
服装矩形件样板排样中QPSO算法的应用 本文内容：
摘 要： 基于皮革服装的CAD技术, 采用改进的粒子群算法模型即QPSO算法模型, 来对于服装矩形件样板的优化排样进行了比较分析研究。排放算法选择最低水平线法, 在优化排样领域引入具有量子行为的QPSO算法, 对矩形件排样采用量子行为的QPSO算法模型进行优化求解, 经过和传统的算法模型结果进行比较, 可获得量子行为的改进QPSO算法, 求解过程和求解结果均比PSO算法的优越性更为突出, 且证明QPSO算法具有高效性和优越性。矩形板材的排样更适合有效QPSO算法得到的排样方案。
关键词： CAD; QPSO算法; 排样; 优化配置;
Abstract： Based on the CAD technology of leather garment, this paper uses the improved particle swarm optimization model, namely QPSO algorithm model, to compare and analyze the optimal layout of garment rectangular parts. The emission algorithm chooses the lowest horizontal line method, and introduces QPSO algorithm with quantum behavior in the field of optimization layout. The QPSO algorithm model with quantum behavior is used to optimize the rectangular layout. By comparing with the results of the traditional algorithm model, the improved QPSO algorithm with quantum behavior can be obtained. The solving process and results are superior to the PSO algorithm, and it proves that the QPSO algorithm has more advantages than the PSO algorithm. PSO algorithm has high efficiency and superiority. The layout of rectangular plate is more suitable for the layout scheme obtained by effective QPSO algorithm.
Keyword： CAD; QPSO algorithm; layout; optimal allocation;
1、 引言
服装CAD技术又称为计算机辅助服装设计技术, 是利用计算机硬件技术、软件技术, 按照服装设计基本要求, 对服装工艺过程、服装新产品进行输入、设计、输出等的一项专门技术, 属于一项集计算机数据库、图形学、网络通讯等知识于一体的高新技术, 用以实现产品工程设计及技术开发。20世纪70年代后期, 第一套服装工艺设计系统由美国格柏 (Gerber) 公司研制出, 该系统涵盖排样、推板等工艺, 开创了服装CAD技术的新纪元。20世纪80年代末, CDI公司的服装设计系统首次投放市场, 主要进行己有资料的扫描, 如照片、图片、面料, 图像修改后产生新的设计。目前, 日本、美国等发达国家服装CAD普及率高于90%。CAD技术应用流程包括:服装设计过程、服装加工生产过程、市场营销步骤、管理环节等, 集合多种学科, 包括计算机图形学、服装设计领域、数据库语言、计算机网络通信等[1,2,3]。在服装设计领域, 最重要是创造思维及想象力, 服装设计还包括计算机的绘图和计算, 计算机系统具有极大信息储备量、运算速度快、安全可靠且还能将图形图案快速分类处理, 从而提高使服装设计的效率和质量[4]。目前, 服装CAD技术覆盖服装设计全过程, 服装CAD系统组成包括排料系统、放码系统、服装样式设计系统、服装打板系统、电脑试衣系统等。其中关键问题是服装设计优化排样问题, 优化排样指将服装原材料数量和格式提前确定, 在此基础上, 尽可能多的将原材料进行排放, 并通过一系列条件和标准的设定, 使排放的原材料具有最大利用率, 尽可将浪费的原材料量降到最低[8]。服装设计优化排样问题属于原材料合理利用和资源分配问题, 图1为服装CAD系统智能排料示意图。
美国电器工程师Russell Eberhart和社会心理学家James Kennedy在1995年共同提出粒子群算法 (PSO) , 其基本思想是受他们早期对鸟类群体行为进行建模、仿真研究的启发, 粒子群算法速度进化方程由社会、认识组成, 但两部分相对重要性未从理论上给出结论。改进的粒子群PSO算法模型 (即QPSO算法模型) 优点是其可处理PSO算法收敛性能上的不足, 相比于传统随机系统, 量子系统具有不确定性, 属于一个不确定性系统。在进行粒子算法的时, 为确保粒子群聚集性, 须在PSO算法模型中规定一个搜索范围, 使其限制在此固定区域内, 在传统PSO算法中, 此区域范围比较局限;改进的QPSO算法在整个搜索空间中是可行的, 在任意一位置, 粒子能以某一确定概率出现, 这样位置具有良好适应值。在检测皮革面料图像边缘轮廓时, QPSO算法较为简单、性能较稳定、计算量较小, 对不同灰度级范围的皮革面料图像处理非常适合。QPSO算法通过进一步简化对皮革面料图像外轮廓信息进行提取, 以域对象形式识别皮革面料图像的外围轮廓边缘, 图2为QPSO算法得到的皮革面料轮廓图像。
图1 服装CAD系统智能排料示意图
Fig.1 Sketch map of intelligent nesting for garment CAD system
图2 QPSO算法得到的皮革面料轮廓图像
Fig.2 Leather fabric contour image obtained by QPSO algorithm
服装CAD的优点是绘图准确、速度快、易于修改、管理方便等, 对于批量小、品种多、变化速度和范围大、生产设计周期极小的服装设计领域极为合适的[5]。同时服装CAD系统也运用在工业生产中, 不仅可大幅提高服装在绘图设计中的效率、也可提升产品质量、减轻劳动强度, 降低成本, 方便生产管理、改善工作环境等[6]。利用服装CAD系统, 服装企业可有效提高约2.5%面料的使用率, 服装设计周期所缩短约10%, 设备利用率提高2.5倍, 产品生产周期缩短65%, 节省60%的成本[7]。本文基于皮革服装的CAD技术, 采用改进的粒子群算法模型即QPSO算法模型, 来对于服装矩形件样板的优化排样进行了比较分析研究。
2、 改进的粒子群QPSO算法
2.1、 粒子群QPSO算法模型
在量子力学的基础上, 粒子收敛行为衍生出粒子群PSO算法模型, PSO算法模型源自DELTA陷阱, 认为在粒子中有量子行为存在, 从而出现量子行为粒子群算法。与最初衍生出的粒子群PSO算法模型相比, 改进优化后的粒子群QPSO算法模型在全局搜索上优势显着。在量子空间中, 并不能同时确立粒子位置和测量粒子速度, 因此, 通过波函数X (t) 对粒子状态进行描述, X (t) 指在空间某一点, 粒子出现的概率密度, 通过对薛定谔方程进行求解, 可获得粒子在空间某一点出现的概率密度函数。通过蒙特卡洛随机模拟方式, 可对公式 (1) 所表示的粒子位置方程进行计算所:
公式中, 表示在[0, 1]范围内变化的随机数。通过公式 (2) 和 (3) 可获得粒子的位置方程 (4) :
公式中, 粒子数目用表示, 收缩扩张系数用表示, 第个粒子的用表示, 粒子维数用表示, 公式 (4) 为最后得到粒子位置方程:
2.2、 QPSO算法流程
改进的QPSO算法步骤包括:第一步是根据初始化过程, 对粒子群进行初始化操作, 从而使粒子群的随机速度和位置分布均恢复初始化状态;第二步是计算粒子群中每一个粒子的适应值;第三步是设置粒子当前位置, 计算粒子适应值, 进行最佳位置Pi的比较分析, 若优越于Pi适应值, 则将其作为粒子当前最佳位置, 若差于Pi适应值, 则反之;第四步是设置粒子全局最佳位置, 将粒子适应值与全局最佳位置Pg适应值进行比较, 若优越于Pg适应值, 则将其作为粒子当前全局最佳位置;第五步是是对粒子位置和速度进行进化;步骤六是在未达到结束条件时, 则返回步骤二。
3、 二维矩形包络排样的优化算法
二维矩形件排样指给定矩形材料区域条件, 为使矩形材料利用率达到最大化, 找出矩形材料零件最佳排布方案。在数学计算复杂性理论方面, 二维矩形排样是一个极具复杂性的问题, 但其在生产加工的各领域中普遍出现, 包括造纸生产工艺、机械加工工艺中。在上述行业中, 产品材料费用占产品总成本很大比重, 因此通过提高原材料利用率可大幅降低产品材料费用, 获得更大经济利益。因而, 对于材料利用率最大化而言, 采用二维矩形排样算法非常重要。
3.1、 矩形件排样问题的数学模型
3.1.1、 矩形排样问题的描述
矩形排样问题的描述指给定矩形材料条件, 根据矩形材料最佳排样方案, 对矩形材料进行排布, 即在宽为w、长为L的板材P上, 在一定工艺条件下, 将n个给定的零件R1, R2, …RnR以不叠加为前提进行排放操作, 从而使矩形板材材料利用率达到最大化。
3.1.2、 数学模型
将板材竖立放置进行排放, 从而使编程操作更便捷, 假定已知板材宽为w, 高为L。定义待排放矩形件的一组编号为变量i=1, R2, …, n R;矩形件左下角点坐标用 (x1, y1) 表示;矩形件右上角点坐标用 (xr, yr) 表示;所需板料最小高度用表示Hmin;矩形件Ri的高度用hi表示, 宽度用wi表示。矩形件排样问题可通过求最优排放序列Imin解决, 根据公式 (5) 计算得到:
公式中, 待排放矩形件面积总和用表示;所有矩形件排放完后, M为所占用的板材面积, 公式 (6) 和 (7) 为其约束条件:
我们做一个假定RiRj为任意两个矩形件, ! (xil, yil) (xir, yir) (xjl, yjl) (xjr, yjr) "分别为它们对应的左下角、右上角坐标。当出现xil>xjr;xir<xjl;yil>yjr;yir<yjl情况之一时, 它们互不相交。
从数学的角度对矩形排样问题进行归类分析, 在进行求解时, 可采用线性规划松弛法进行求解。使用线性规划松弛法求解存在一个极大弊端, 即在进行调整优化后, 不能保障算出来的解近似最优解的正确性。
3.2 、粒子群算法求解矩形件优化排样问题
利用改进的粒子群QPSO算法模型解决矩形材料优化排放问题, 找到每一个零件最优位置, 随后按照最优位置进行排放, 从而获得一个最优越的矩形材料排放方案。只有将矩形零件全部排放在矩形零件的位置时, 才会得到最优排放方案, 利用率才会最大化。当开始对粒子群当前位置初始化时, 该排样方案不是最佳, 需反复检测寻找每一个零件最优位置, 从而得到最优排放方案, 使每一个零件均可处于最佳位置处, 达到材料利用率最大化。在寻在粒子最佳位置时, 相关性判断重复三次, 并时按照状态不同进行调整。因粒子不是固定静止的, 当改变粒子位置和速度后, 应计算原因, 在粒子群中, 极大可能零件的位置不是整数, 可采用四舍五入法进行调整;如果有一个零件的排样位置超出板材材料, 则需要调整该粒子相应零件位置, 使其处于板材空白位置, 不重叠。在计算粒子适应度函数值时, 若粒子中某零件的排放位置与粒子群计算获取的最优均不相似, 这时就对优化粒子群中零件的排放方式进行重新调整, 从而获得最优解多对应排放方案;在调整粒子群零件排放方式前, 要对于适应度函数值进行计算, 将其中数值大的作为粒子适应度的函数值。
3.2.1、 粒子群初始化
在进行粒子群优化操作的时, 解空间的一个解可用粒子进行表示, 零件数量决定粒子长度。根据零件的组合顺序不同, 从而构成不同粒子。构成粒子主要是根据面积大小排序, 当改变其零件组合的先后顺序, 则可组成一个新粒子。对于每一个粒子都赋予其一个随机速度, 并将其作为粒子初始速度。
图3 算例1的PSO算法进化100次后结果
Fig.3 PSO algorithm evolved 100 times after results of example 3
图4 算例2的PSO算法进化100后的结果
Fig 4 PSO algorithm evolution after 100 results of example 2
3.2.2、 粒子群调整
根据粒子群算法公式, 因存在rand1, rand2, c1, c2, 在微粒当前速度、位置即使全部为整数时, 但因下一个位置可能为实数, 为保证这一项数值为一个整数, 则要通过公式 (8) 对其范围进行限制。
在所要求区间范围内, 粒子群就得到保证, 当粒子进行进化后, 粒子位置会重复出现, 所以要将与其差值最小且为最后出现位置来代替它。
3.2.3、 停止规则
停止规则指板材循环满足设定最大次数或利用率的设定值, 循环停止。在板材优化排放问题上, 板材利用率无最高上限, 且上限越大越好。在本文研究的算法中, 停止规则设定为循环满足设定的最大次数。
3.2.4、 PSO算法排样算例
图3为算例1在c1=c2=2.0, 进化代数100次后的PSO算法排样结果, 图4为算例2的PSO算法进化100后的结果。
4、 基于量子行为的粒子群算法求解矩形件优化排样问题
在微粒群算法基础上, 发展起具有量子行为的粒子群优化算法, 量子行为粒子群矩形排样就是重新调整矩形排样问题, 从而成为一个适合优化的排样问题, 并进行优化。在最初进行初始化操作时, 粒子群的粒子排样根据排样序列进行, 但这样得到的排样结果不是最优排样结果, 因为不是每一个零件都处于最优位置。因此, 需发现具有量子行为的粒子群去优化算法, 找到粒子群中每一个零件的最优位置, 使零件排布更加紧密优越, 板材利用率提高。相同的方法, 在进行QPSO算法的寻优时, 相关判断要进行3次, 随后根据实际操作情况来进行适应性调整。
4.1、 具有量子行为的粒子群算法的排样优化过程
基于QPSO算法的矩形排样优化的操作步骤包括:第一步是当产生初始种群后, 对给定的n种零件或n个零件来一一编号, 随机产生初始种群, 该种群构成包括M个编码和I1, I2, …Im。解码操作为采用改进的最低水平线法, 根据板材实际情况, 计算当前群体各个体适应度;步骤二是记录每一个粒子的当前最优位置, 并且对每一种方案的最小排样高度及各参数指标进行记录;步骤三是对粒子中的最佳位置进行搜寻, 也是对种排样方案中的最小排样高度及多边形样片排样参数进行记录。步骤四是对粒子群局部最佳中间位置进行计算, 也就是计算M种排样方案中的参数均值。步骤五是调整粒子位置, 若样片排入次序不合法, 则会有序号或序号重复出现, 超越0至N-1的范围, 则要对超出范围的序号进行处理, 若序号<0, 在[0, N/2]范围内给其赋以一个随机整数, 若>N-1, 在[N/2, N-1]范围内则给它赋以一个随机整数;然后处理重复序号, 重复序号用和它差值最小的遗漏序号进行代替;步骤六是对于上述提及的步骤一到步骤五的操作流程的重复;步骤六是程序终止。
图5 算例1的QPSO算法进化100代后的排样图
Fig.5 QPSO algorithm evolution after 100 results of example 1
图6 算例2的QPSO算法进化100代后的排样图
Fig.6 QPSO algorithm evolution after 100 results of example 2
表1 算例3的矩形件数据
表2 算例1排样结果数据
4.2 、排样算例
4.2.1 、实验结果
算例1和算例2均采用QPSO算法, 图5和图6为进化100代后的结果。
表1为算例3的矩形件数据, 其中6种工件参数是随机产生的。板材的宽为350 mm, 高为90mm。
4.2.2 、结果分析
图7 算例3的QPSO算法进化100代后的排样图
Fig.7 Evolution QPSO algorithm after 100 generations layout of example 3
图8 排样后结果
Fig.8 Results after nesting
分析PSO和QPSO两种算法的排样算例, 算例1的进化代数为200, 表2为排样结果。
从表2中可看出, QPSO算法具有较快的收敛速度, 在迭代次数相同的情况下, QPSO算法比PSO算法的收敛效果要好。
5、 QPSO算法在服装CAD自动排料中的应用
与任意不规则零件间的排样仿真不同, 在进行衣片排料时, 对工艺要求考虑较多。要求在面料内进行排放, 每套服装衣片, 且各衣片不能重叠。采用QPSO算法, 按照不规则零件排样优化参数进行次序排入, 将其作为衣片优化参数。在终止排料后, 将衣片优化排料结果输出。设定面料长度为505 cm, 幅宽为305 cm、衣片共10片, 对服装样片进行排样。
图8为三种样片排样后的结果, 从图7中可知, 有两种样片基本一致, 但两者方向不同, 因此在处理样片排样时, 将其区分开, 成为三种样片排样。
6、 结语
本文基于皮革服装的CAD技术, 采用改进的粒子群算法模型即QPSO算法模型, 来对于服装矩形件样板的优化排样进行了比较分析研究。排放算法选择最低水平线法, 在优化排样领域引入具有量子行为的QPSO算法, 对矩形件排样采用量子行为的QPSO算法模型进行优化求解, 经过和传统的算法模型结果进行比较, 可获得量子行为的改进QPSO算法, 求解过程和求解结果均比PSO算法的优越性更为突出, 且证明QPSO算法具有高效性和优越性。矩形板材的排样更适合有效QPSO算法得到的排样方案。
参考文献
[1]董礼强, 黄超.规模化智能CAD样板设计资源配置探索[J].服装学报, 2017, 2 (3) :204-208.
[2]程应奋.服装CAD系统在纺织服装企业的应用[J].科技风, 2011, 9:107-109.
[3]高飞.皮革面料裁剪CAD/CAM的应用技术研究[D].上海:上海工程技术大学, 2014.
[4]邓欣.服装CAD的打版模式及应用[J].天津纺织科技, 2017, 1:52-52.
[5]杨玫.数字化技术在服装制版工作中的应用研究[J].自动化与仪器仪表, 2017, 1:121-122.
[6]董礼强, 黄超基于工作室模式的智能CAD资源配置研究[J].浙江纺织服装职业技术学院学报, 2017, 2:46-50.
[7]李爱英, 宁雅.服装CAD技术提高服装企业生产效率方案设计[J].山东纺织经济, 2011, 8:74-76.
[8]王永忠, 王妍萍.服装设备自动化的现状和发展[J].电子科技, 2013, 10:169-172.
服装矩形件样板排样中QPSO算法的应用 来源：网络整理
免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
相关文章