相关电子技术论文

相关标签

基于多链编码遗传算法的二维卷材下料问题优化方法

发布时间:2019-12-04 11:43

  摘 要

  本文介绍了二维下料问题的背景和研究进展,并详细描述了本课题的研究对象和研究内容,论述了二维卷材下料问题的问题特性。在此基础上,以纸板厂纸板排样切割作业为研究对象,综合考虑其生产工艺特性和任务要求,提出一种基于自适应容许条带长度差的分割式纸板排样模型,并依据模型特性详尽论述了该模型原料的四种主要损失形式,在此基础上生成了以材料损耗率最小化为目标的目标函数。

  在算法设计阶段,本文通过对基础遗传算法框架的归纳总结,依据模型特性设计出一种基于多链结构的遗传算法对问题进行求解。在不同参数条件和问题规模下,通过仿真实验验证了该算法解决实际生产任务的有效性。

  关键词:二维下料问题;遗传算法;排样优化;排样模型

  第一章 绪 论

  一.1. 研究背景

  下料问题在机械行业中的型材板材等金属件切割、服装行业中的皮革布料裁剪、建筑行业中的木料石材切割和玻璃行业中的玻璃划割等领域都有广泛的应用。随着社会经济的快速发展和对相关产品的需求不断增大,企业的生产规模日益扩大,生产活动所需资源越来越多。与此同时,由于生产工艺或改进成本的制约,部分生产领域未能及时提高资源的利用效率,降低废弃资源占比。这些未被充分利用的资源不仅造成了大量经济损失,也给环境带来了污染和破坏。下料活动作为产品生产链的首道工序,其调度方案的优劣严重影响着原材料的利用程度和后续工艺的成品率,同时下料方案的改动基本不需要对生产现场做出大量改动。在此情况下,下料问题的改进是企业降低资源浪费,提高资源利用效率,承担环境责任的高效优化举措之一。

  下料问题是探讨如何在原材料上合理地排布零件的位置,从而在满足生产需求的前提下,达到原材料消耗最小,加工时间最短,操作复杂度最小等目标。其包括方案排样和图案切割,方案排样是确定零件在原材料上的合理布局,图案切割即对该排样布局进行切割作业生成零件。

  下料问题按照原材料和零件的维数不同可划分为一维、二维、和三维(多维)下料问题,其中,一维下料问题多应用于型材、棒材的加工切割中,二维下料问题主要适用于板材、卷材等原材料和零件仅在二维层次上有要求的生产领域,而多维是指原材料和零件的长宽高、材质等均有特定的有区分的要求。二维卷材下料问题是属于二维下料问题中的开放维度问题,即二维原材料中的某一维度长度无限,生产时应当使该原材料所耗长度尽可能短。

  二维下料问题具有高度计算复杂度,属于非确定性的多项式完全问题,至今尚未有一种有效求解的多项式时间算法。

  一.2. 国内外研究进展

  一.2.1. 国外研究进展

  国外有关二维下料问题的研究起步比较早。早期对该问题的求解主要采用数学规划和启发式算法,数学规划方法主要包括线性规划、整数规划、动态规划以及混合规划等,这些方法的主要缺陷是:算法所需的计算资源(时间和空间)会随着问题规模的扩大而呈指数级增长,不适用于求解大规模的二维下料排样优化问题。而后出现的启发式算法放弃了寻找最优解的想法,转而试图在多项式时间内找出问题的近优解(满意解),之后数学规划领域也借助模型构建,通过寻求模型的最优解来获得问题的近优解。“寻求近优解”是目前解决二维下料问题等NP-难问题的主流方法。Aryanezhad等[1]为了解决许多精确算法因耗时长、应用局限度高、复杂程度高等问题而不能实际应用于生产生活的问题,设计了一个简单快速的启发式算法来解决这个问题,实验证明该算法具有良好的生产指导能力和生产模式兼容性。Wuttke等[2]在顺序决策板材置换损失模型的基础上提出了基于反馈回路的顺序启发式混合整数规划模型,测试表明该数学规划算法具有良好的近优能力。

  二十世纪九十年代以后,随着模拟退火、遗传算法等进化算法理论以及人工神经网络理论的日益成熟,其也被广泛应用于二维下料问题的求解中。Onwubolu等[3]首次对开放维度(卷材)下料问题建立了一个通用模型,并在考虑最多允许两种类型零件双拼的基础上通过运用遗传算法对该模型进行求解,由于元启发式算法自身的特点,此次实验结果存在部分解劣于Benati(1997)实验结果的现象。Leung等[4]分别将遗传算法和模拟退火算法应用于二维下料模型并对实验结果进行了比较。Jiang等[5]提出基于粒子群算法和模拟退火算法的混合算法以求解非切纸机下料模型,实验表明该算法从运行效果和运算速度上均优于上述两种标准算法。从目前的研究进展来看,复合算法的性能一般都优于组成该算法的单独算法,这也是后期算法的一大主流分支。

  一.2.2. 国内研究进展

  国内对二维下料问题的研究起步比较晚,起初多用人机合作的方式通过旋转、平移零部件来生成排样方案。之后主要采用数学规划方法(线性规划[6][7]、动态规划[8]等)、启发式算法(顺序启发式算法[9][10]、贪心启发式算法[11]、分组降维启发式算法[12]等)、进化算法(人工鱼群算法[13]、蜂群算法[14]、遗传算法[15]等)等进行求解。就目前国内外研究进展来看,国内对于该问题的研究在深度与广度上和国外比都是存在一定差距的。

  一.3. 研究意义

  二维下料排样方案的优劣会直接影响到企业的经济效益和后续的加工过程。一个合理的排样方案不但可以直接减少材料浪费,降低材料成本,而且可以简化加工操作、降低制造费用,给企业带来经济效益,提高企业竞争力。因此,对二维下料问题的研究会对生产效率的提升和生产成本的降低产生深远的影响。

  一.4. 结构安排

  本文以某一纸板厂为背景研究二维卷材下料问题,并设计一种算法以求解该问题。论文的组织结构如下:

  第一章 绪论。首先概述了下料问题的行业背景、分类和相关特征,其次介绍了二维下料问题在国内外的研究进展和发展趋势,并阐述了该课题的研究意义,最后介绍了本文的工作内容和行文结构。

  第二章 二维卷材下料问题模型探究。首先定义了二维卷材下料问题的标准定义和相关术语,之后分别讨论了相关模型的条件假设、模型建立、约束条件和目标函数,其中在模型建立阶段特别提出了基于订单分割的排样规格,具体论述了原材料损耗的四种主要形式。

  第三章 多链结构遗传算法设计。从标准遗传算法的介绍和原理展开,根据下料模型和相关参数设计了一种多链结构的遗传算法。

  第二章 二维卷材下料问题模型探究

  二.1. 术语定义

  二维卷材下料问题是一种在纸板切割、布料裁剪等工程领域应用广泛的排列组合优化问题,其核心是规划零件在原材料上的排列布局。以下是标准术语定义:

  排布可以组成条带,条带长度为直线方向所有零件尺寸之和,宽度为直线垂直方向上所有零件尺寸中最大值,条带方向视为和直线方向一致。一般来说,条带按其组成零件的不同可以划分为三种类别:普通条带、匀质条带、同质条带,普通条带可以放置任意长宽尺寸的零件,匀质条带只可以放置相同宽度的零件,同质条带只能放置相同尺寸的零件。通常的,普通条带和匀质条带对原材料的利用率会比较高,但加工步骤也更为繁琐,对机器和工序的要求更高,一般只有多品种小批量的订单会采取这种方式。另外,如果是卷材加工的企业,由于裁剪机械的限制往往只能采用同质条带的排样方式。图2.1是不同类别条带的示意图。

  一个或多个条带沿宽度方向排列形成段。段的长度为组成条带中长度最大值,宽度为组成条带的宽度之和,段的方向视为与条带长度方向一致。

  排样方式是一单元原材料上排列的段的集合,其确定了该单元原材料上生产的零件数量、零件布局和生产顺序。

  定义5:排样方案(cutting plan)

  排样方案是问题的可行解,是排样方式的集合。该方案应该是综合考虑了原材料库存、订单满足能力、加工工艺限制等因素的结果。

  定义6:原材料(stock)

  原材料是被加工的主体,排样方案需要符合原材料的特性才有实际意义。其一般是型材、板材、纸张等规则矩形件,具有特性为宽度、长度和库存

  二.2. 条件假设

  本文以纸板厂生产瓦楞纸为研究背景,由于切割机器特性和生产工艺要求等限制,该排样下料模型应满足以下条件:

  1、切裁机器为切纸机。

  2、原材料和零件都是矩形件。

  3、因为压线纹理的需求,零件生产时初始方向是固定的,即不可以长宽互换后生产。

  4、当某个零件类型的订单被满足时,即使多生产的零件可以在后续的订单中被用到,也视之为材料浪费。

  5、零件的排样不能重叠且均要位于原材料范围内。

  二.3. 问题描述

  时会出现各订单零件组成条带的长度差过大,导致方案不经济的情况。因而对较长条带所属的订单进行分割,分割后的子订单会在后续生产中当成独立订单紧接着母订单生产。具体排样规则如下:

  第三章 多链结构遗传算法设计

  三.1. 遗传算法简介

  遗传算法最早由Holland提出,是通过模拟自然界生物进化发展机制“物竞天择,适者生存”而产生的一种随机全局搜索的优化方法,它主要借鉴了孟德尔的遗传学说和达尔文的进化论思想,具有并行、高效、全局搜索的优点。它能在迭代搜索过程中自动获取和积累关于种群个体优劣性征的知识,并据此适应性地调整种群生物进化方向以求得更优异的个体。

  三.1.1. 构成参数

  一个标准的遗传算法框架主要由四个部分组成:

  (1)染色体编码及解码。模型中的每一个方案解,不管可以或者不可行,都需要经由一定逻辑编码运算才能被机器识别、分析、处理,经过编码处理的方案就称为染色体,其一般是二进制或者实数编码形式。在算法迭代出满意方案后,又需要将数字编码形式的染色体进行解码以反馈到现实问题中。

  编码的优劣是影响遗传算法性能的首要因素,其应当能表征出该模型的所有可行解并尽可能简洁。

  (2)遗传操作算子。包括选择算子、交叉算子和变异算子,是主导种群迭代进化的基本参数。

  (3)适应度评价体系。适应度是衡量一个个体生存能力的关键指标,适应度值越大,该个体在下一代存活繁衍的可能性就越大。适应度一般是模型优化目标的直接转化。

  (4)运行参数。包括种群大小、算法终止条件、各操作算子的概率参数等。

  三.1.2. 实现逻辑

  在解决问题时需要先根据模型特点及可能解集合产生一个合理的编码模式,并依据种群大小生产算法的初始种群。最后得到的最终解即从该初始种群中迭代进化而来。每个个体都有各自的性征,通过将各个个体经由适应度评价体系进行检测可以确定个体繁衍并存活到下一代的可能性,之后按照优胜劣汰的法则通过父代种群来产生子代种群,同时为了在进化中保证种群多样性,防止种群过早落入“进化陷阱”,还要使其中某些个体以一定小概率发生基因变异。通过这样的方式迭代进化直至若干代种群中的染色体趋同。此时得到的最优解即为方案的最终解。图3.1是标准遗传算法的运行过程

  三.2. 算法结构

  (1)编码

  在编码前需要确定工厂的生产参数。该工厂采用双切刀机进行生产,机器设有横切刀2个,纵切刀8个,即最多允许两个订单进行相拼,同时横刀方向上最多允许存在7条条带。纸卷设有9种规格门幅,最小门幅宽度为2000mm,最大门幅宽度为2800mm,各相邻门幅宽度相差100mm。

  B)交叉机制

  在生物的进化过程中,种群中两个个体通过交配繁衍生成新的个体,其中生物基因的交叉重组和变异是推动生物进化进程的核心要素。交叉是指把两个父代染色体的基因结构经过拆分、替换、重组而生成子代染色体的过程,核心理念是该方法以片段交叉的方式组合生成新个体,减少对优质基因结构片段的破坏,从而得以在解空间中进行有引导性的搜索。

  染色体第一链需要重复冲突检测,故采用顺序交叉,此交叉方法的特点是在于其运行方式能自动保证染色体不会因基因片段交叉重组而产生基因重复的问题。具体交叉逻辑如图3.4所示。首先随机生成基因片段起始点

  (4)适应度评价

  个体的适应能力指的是个体对环境的适应程度,也表示个体存活并繁衍后代的概率,这个能力指标映射到算法中就是个体的适应度值,其是用来判断种群中个体优劣程度的函数,一般由模型目标函数改动或调用得到。

  遗传算法在进化迭代过程中一般不需要其他外部数据的参与,仅需用适应度评判去评估种群各个体的优劣以作为遗传操作进程中“优胜劣汰”的标准,并且应用函数对种群进行评价会占据算法运行的大部分时间,故适应度函数的设计会对算法性能产生重要的影响。

  作为适应度函数,该方法有助于缩小较优个体和较劣个体之间的差距,使种群不会在进化早期因为某些特优个体而过早陷入局部最优解,同时也会增大劣质个体的生存概率,以此提高种群多样性。

  (5)终止条件判断

  当种群中个体历史上出现的最高适应度值连续代未发生改变时,则认为该种群已经进化完全,所得最优个体即为算法的最终解。

  第四章 仿真实验

  四.1. 参数选择

  四.1.1. 模型参数选择

  算法以某一瓦楞纸板厂的生产线实际参数和日常订单为例,随机选取一部分订单如下表1所示:

  代内各代的适应度最大值、平均值和最小值的变化情况,在迭代过程中适应度的最小值和平均值有着较大的波动,这说明该进化方式能保证种群发展的多样性需求。另外,随着拥有更高适应度的个体不断产生,这些个体会在种群中稳定存活和快速繁殖,从而使种群适应度平均值随之增大,并且此种趋势往往会比优质个体的出现延后三四个代际。

  (1)该算法具有良好的近优性能,在不同种群规模下,算法结果最终稳定在106m2左右。

  (2)在迭代相同代数的情况下,种群规模越大,算法近优能力越强,但这需要耗费更多的计算资源。

  (3)随着算法的运行种群呈现出趋同倾向,这意味着算法在后期有着陷入局部最优解的可能。目前运算结束时结果平的标准差为29左右,表明该算法仍能在运算过程中保证种群的多样性。

  个算例的平均运行时间和平均运行结果的数值及其标准偏差。从表中可以看出,随着订单规模的扩大,该算法有着向随机搜索算法偏离的倾向,目前该算法仍不能妥善解决组合爆炸的问题。

  第五章 结论与展望

  本文依据某瓦楞纸板厂的工艺特点设计了关于二维卷材下料问题的数理模型,重点分析其原材料损耗形式并提出一种分割订单式生产模块和自适应的容许条带长度差参数以解决订单的拼接难题,同时针对模型特点提出一种合理的算法结构加以求解,实验证明该算法能初步解决该工厂的二维卷材下料问题,为相关工厂的生产实践提供方案指导。

  虽然实验得了较好的结果,但由于作者水平的限制,本文仍有很多不足有待解决,未来的研究方向主要包括以下两点:

  (1)规模的扩大对算法的影响。

  目前即使遗传算法等进化算法对处理大规模的非多项式难题有着较为成熟的方法框架,但是随着算法的规模持续扩大,进化算法仍然会有向随机搜索算法发展的趋势,因此将某些能对解空间进行预处理的算法框架嵌套进进化算法中或许是一个有效的解决方法。

  (2)模型的复杂化对算法的影响。

  染色体模型的设计对算法性能的影响至关重要,但随着问题的复杂度不断增大,比如将下料问题和运输问题、仓储问题等联合调度,染色体模型的复杂度也必然会扩大,目前对于这种问题的主要解决方案是先分段求解每个问题再对结果进行整合,然而这样往往会牺牲一些更优的解集,求解效果不太理想。目前对于该问题目前尚未有比较合理的解决思路,也将是下一步需重点研究的方向。

毕业论文:http://www.3lunwen.com/jsj/dzjs/5411.html

上一篇:基于多尺度特征值的眼底血管自动分割

下一篇:没有了

     移动版:基于多链编码遗传算法的二维卷材下料问题优化方法

本文标签:
最新论文