基于差分进化和自适应遗传算法的矩形件排样方法研究

《基于差分进化和自适应遗传算法的矩形件排样方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据广西大掌工程硕士学位论文基于差分进硼缯口自适应遗传算法的矩形件掉样劣哼赫研究1．1排样问题的提出第一章绪论二维板材排样问题又称为二维板材下料问题，是著名数学家希尔伯特最早提出的23个数学难题之一，该问题自提出以来便引起了众多学者的关注并投身其中进行探索研究，他们提出了许多各自的排样算法，然而该类问题属于具有较高复杂度的NP完全问题，也是较典型的组合优化问题之一，至今为止尚无有效的方法可以对其精确解进行求解。随着社会经济的发展，服装、玻璃、皮革制品、家具等现代工业的生产过程中都有排样或类似的问题需要解决。矩形件排样问题通常是指在定宽不限长的矩形板材上排放矩

2、形件，矩形件的尺寸大小及数量有一定的限制，且矩形件在板材上排放时有如下约束：各矩形件间不能相互重叠、所排入的矩形件不能超出板材边界，最终目的是为了使矩形板材的利用率最大化。我国是人口大国，资源紧缺，因此提高板材切割下料生产环节中的效率以及板材下料的利用率是提高工业生产的经济效益和减少资源浪费的重要手段，本文研究的排样问题对实际生产具有重要的理论意义和现实意义。目前玻璃、管材、皮革、铝合金、布匹等材料的主流切割设备中，以剪床和锯床居多，历史也最为悠久，且下料方式简单易操作，皆由工人按照所需的零件数量和尺寸在板材上切割下料。对于矩形件排样这类具有较高复杂性的NP完全

3、问题，仅仅依靠人工方法进行板材排样不仅耗时、排样效果差、生产成本高，而且往往难以获得较优的排样方案用于生产下料，从而导致原材料的严重浪费。因此针对矩形件排样这一组合优化问题，设计出一种能有效提高排样效率及排样效果的排样算法具有重要的意义。二维排样问题分为两类：一类是二维不规则零件排样，另一类是二维规则零件排样。而二维规则零件排样问题中又可分为二维矩形件排样、二维圆形件排样等问题。本文研究的问题为二维矩形件排样优化问题。万方数据F-西大学工程硕士掌位论文基于差分进1匕和自适应遗传算法的矩形件排样方法研究1．2矩形件排样问题的研究现状1．2．1国外研究现状矩形件排样

4、问题自提出以来便受到广大学者的关注，该问题从复杂度上分析属于NP完全目题，无法在可接受的时间范围内快速寻找到问题的最优解。国外有关排样问题的研究最早由前苏联经济学家Kantorovich发起，起初主要针对一维摊样问题提出用线性规划方法来求解，但是线性规划方法只能用于求解小规模的一维排样闷题。随后Gilmore和Gomory在对一维排样问题深入研究的基础上，将前人提出韵算法应用于求解二维和三维排样问题中，为实际生产提供了可行的排样方法，也为后续的研究奠定了基础。在各类排样问题中矩形件排样问题应用最为广泛、最典型，因此国外众多学者针对矩形件排样问题提出了各种各样的求

5、解方法。Paull和Eisemann应用线性耀划方法求解机械制造业实际生产中遇到的矩形件排样优化问题，但利用该方法求解得到的排样方案板材利用率并不高【IJ。针对二维矩形件排样问题这一具有较高计算复杂度的优化问题(NP完全问题)，二十世纪五十年代，科学家们以生物进化机理为基础，创立了能够有效求解实际生活中复杂优化闷题豹模拟进化算法(SimulatedEvolutionaryAlgorithm)，主要有遗传算法、进化策略以及进化规划【21。遗传算法【3圳、进化策略及进化规划的基本思想均源自于达尔文的进化论，但三者的进化层次有所侧重，其中对遗传算法的研究最为深入，其应

6、用也最为广泛。到二十世纪九十年代，由于遗传算法是求解NP完全类型的组合优化问题及非线性多模型、多目标函数优化问题的较理想的优化算法之一，因此遗传算法在多个学科领域得到广泛关注及应用。同时学者们认为对于组合优化问题，寻求其最优解并非明智之举，可以转丽考虑寻求该问题的较优解或近似最优解15J。经典遗传算法在最初的应用中存在收敛速度馒和易陷入早熟的缺陷，为解决这些问题，Srinivas等【6】创造性地提出了自适应遗传算法(AGA)。自适应遗传算法的思想为：设计能自适应地调整交叉概率和变异概率的调整公式，使个体的交叉概率和变异概率可以随自身适应度值或进化代数的变化而变化

7、，增强个体对周围环境的适应能力，以此方法来保留种群中的优秀个体，防止算法陷入局部最优及产生早熟现象。此外，比遗传算法起步稍晚的差分进化算法因其卓越的性能在各个领域中也得到广泛的应用。差分进化算法【7】是由Store和Price提出的一种基于种群个体基因差异的进化2万方数据广西大掌工霜L硕士掌位论文基于差分进1匕和自适应遗传算法的矩形件排样勇哼去研究算法。与遗传算法相比，差分进化算法中所需设置的参数少、设计简单、易于实现，其最大的特点是新个体的生成来自于父代多个个体的线性组合，而非遗传算法中由单一的、t■父代个体通过交叉和变异产生。差分进化算法作为计算机科学领域的

8、一种优化方法，根据优化要