52800字硕士毕业论文矩形布局中遗传算法和蚁群算法的进一步深入分析
论文类型：硕士毕业论文
论文字数：52800字
论点：算法,矩形,遗传
论文概述：
摘要 优化排料是指在给定的板材上尽可能多的排放给定规格的零件，使得板材的利用率最高，一个好的排料方案可以大大降低企业的生产成本，提高企业的竞争力，因此优化排样成为众多企
论文正文：
简介:进入20世纪90年代后，随着计算复杂性理论的成熟以及模拟退火算法、遗传算法、禁忌搜索算法和神经网络等现代优化算法的发展，许多学者开始将这些具有逼近零件布局全局最优解特征的算法应用于零件布局，显示出解决复杂布局问题的强大能力。由本网站的硕士论文中心组织。
简介
1.1布局问题
随着社会的进步和科学技术的发展，各种高科技逐渐渗透到我们的日常生活中，从而将大量的人力从各种艰苦的工作中解放出来。
从20世纪40年代的蒸汽时代到日益成熟的信息时代，机械已经逐渐取代了人力。特别是随着计算机的普及和信息高速公路的建设，以前看似复杂的问题变得更加容易了。然而，随着生产力的提高和生产规模的扩大，对原材料的需求也在增加。产品生产中的零件毛坯直接从原材料中获得。随着对材料需求的增加，价格也在上涨。如何降低价格，实现利润的快速增长，是当今社会对所有企业最严格的要求。最大限度地节约材料，提高材料利用率是提高生产效率的重要手段。如何从源头上解决这些问题，要求下料时充分考虑材料的利用率。过去，它主要由人力控制，依靠工人的传统经验，但结果往往不尽如人意。首先，依靠传统经验冲裁时，大部分不能从整体上找到最佳结果，而是根据零件的形状直接从板材上切割下来，这样会造成大量的材料浪费。第二，由于企业无法设定预算，导致钢材大量积压，资金占用严重；第三，落料切割过程混乱，难以对固定时间和定量定额的落料过程进行管理，导致落料生产效率低，钢材浪费严重。因此，如何切割板材和切割材料成为解决这个问题的最重要的事情。
布局问题自20世纪中叶以来已引起广泛关注。20世纪60年代初，吉尔摩和戈莫里研究了一维、二维和三维布局问题。利用列生成技术解决一维布局问题。矩形布局是参照一维布局正式研究的。提出了“一刀切”和“正交切割”的经典二维切割方法，并以“背包问题”为模型，利用线性规划和动态规划，提出了求解闸刀式N级切割的嵌套算法[1][2][3]
1.2布局问题的研究现状
国外对布局问题的研究始于前苏联坎托沃里克14年，193 9年发表了一篇关于一维布局问题的论文。到了50年代中期，保罗11} 15、艾斯曼16、赫尔曼和瓦伊·达[首次提出线性规划法来解决印刷和造纸工业中的矩形包装问题，但材料利用率不高。二维切削问题是一种计算复杂度最高的优化计算问题——NP完全问题[。20世纪60年代初，吉尔摩和戈莫里L9} 1 [}aa]提出了一维下料方案和二维布局问题。由于许多学者开始对布局问题进行大量的研究，虽然已经取得了一些成果，但是仍然没有通用的标准方法来解决。由于对矩形零件布局的研究不仅可以直接解决矩形零件布局问题，而且可以作为解决二维不规则零件布局问题(通过包络矩形法将不规则零件布局问题转化为矩形零件布局问题)的基础，一直是许多学者关注的热点和焦点，大量的研究成果出现在[[23-25上。启发式算法在解决布局问题中起着重要作用。Yanasse}26]提出了一种顺序嵌套的顺序嵌套算法。该算法的主要思想是根据嵌套部分的长度、宽度和面积给出一定的优先级规则。根据这个优先顺序，零件从板的左下角开始按顺序排列。该算法规则简单，易于编程。其缺点是材料利用率不高，容易造成左侧高现象。Dagli和Tatoglu提出使用启发式算法来解决问题，但启发式规则难以确定，布局结果不稳定，无法应用于实践。Amaral}2\'}提出了一种交互式布局方法。虽然计算结果相对稳定，但布局效果并不理想。进入70年代和80年代后，随着智能优化算法(神经网络、遗传算法、禁忌搜索、模拟退火等)的不断出现。)，为解决布局问题提供了新思路。进入20世纪90年代后，随着智能优化算法的不断发展和成熟，它们已成功应用于旅行商问题、包装问题和任务调度问题等组合优化问题，显示了智能优化算法的优越性。将这些算法应用于布局问题正变得越来越流行。霍普和图尔顿总结了遗传算法在布局问题中的应用，并根据空之间的维数和布局图案的几何形状对布局问题进行了分类。对遗传算法中嵌套问题的编码方法、遗传算子和解码算法进行了研究和讨论。
中国对计算机辅助布局的研究起步较晚，始于20世纪80年代。起初，研究主要集中在矩形布局上。研究成果也主要集中在清华大学、浙江大学、上海交通大学、华中科技大学和四川大学等高校和研究机构。到目前为止已经取得了很大的进步，但是总体来说，国内外关于布局的研究在深度和广度上还存在很大的差距。20世纪90年代后，矩形件布局技术进一步发展。曹菊[2S]提出了一种利用背包问题的矩形包装近似优化算法。崔耀东[X29]提出了一种分块策略，将制造同一产品所需的各种不规则形状的零件嵌套成不同尺寸的矩形块，每个块由多个零件组成，下料时，整个板材由矩形块切割而成，多个矩形块可以排列在同一板材上；1995年，曹菊、周记、[等人构造了一个近似算法。该算法的主要思想是根据布局过程中的局部优化原理动态连续地生成一些较小的矩形，然后排列这些较小的矩形区域，同时消除一些已经排列好的矩形区域，直到所有矩形块都排列好。李建勇提出用混沌人工神经网络[[31味口C人工神经网络分别进行布局优化计算。在过去的10年里，许多大学也开始研究新的智能算法，如文件[·[32-36]，这些算法主要基于遗传算法和蚁群算法，主要是因为这两种算法相对于其他算法具有明显的优势。
。然而，由于当时计算技术落后，在实际应用中还没有真正实现。直到20世纪70年代末，随着计算机技术和运筹学的发展，计算速度突飞猛进，关于最优下料问题的理论研究才得以付诸实践，这一领域的研究空在随后的十年或更长时间内活跃起来。模仿手工布局，辅以手工经验和逻辑，学者们在0.7080年代设计了许多启发式算法1.3本文的主要研究内容和创新点
从二维布局问题中最常见的矩形布局出发，通过阅读大量文献，了解布局的研究现状和发展趋势，并比较了当前几种相对先进的算法，选择了两种先进的算法——遗传算法和蚁群算法——对矩形布局进行深入研究。本文的主要研究内容如下:
(1)比较了一些成熟的算法。
(2)深入理解遗传算法和蚁群算法，比较它们的优缺点。
(3)对于遗传算法，对初始群体的基因编码进行了改进，有效地提高了初始群体的质量。在遗传操作方面，提出了一种新的交叉算子，并将这两种算子结合使用。在变异算子方面，综合运用了两种变异算子，以一定的概率随机选择不同的变异算子；在解码方面，采用文件[39“基于最低水平线的搜索算法”。
(4)蚁群算法综合考虑矩形面积和宽高比两个因素，动态生成期望的启发式因子。
(5)对遗传算法和蚁群算法的融合时机进行了分析和研究，得出了最佳融合时机并应用于本文。
(6)设计并实现了一个基于遗传蚁群算法的矩形布局系统；
(7)通过实例说明了该算法的可行性、有效性和实用性。-[11]，由于冲裁过程中切割方法和排列方法的不同，人们无法一一列出矩形件研究中的所有排列，规划和优化只能通过启发式算法来进行，以减少大量切割方法带来的不同排列方法。然而，启发式算法高度依赖于要解决的问题，并且通常只能处理一个或几个特殊问题。此外，经常有不可行的例子[·[[12][[13]，这严重限制了对此类问题的研究。进入20世纪90年代后，随着计算复杂性理论的成熟以及模拟退火算法、遗传算法、禁忌搜索算法和神经网络等现代优化算法的发展，许多学者开始将这些具有逼近零件布局全局最优解特征的算法应用于零件布局，显示出较强的解决复杂布局问题的能力。近十年来，越来越多的人使用这些算法来研究矩形零件的优化布局。此外，随着现代优化算法理论和其他优化问题的应用研究逐渐成熟，越来越多的学者致力于利用智能优化算法解决布局问题。优化算法的“布局问题”研究已成为我国运筹学、计算机科学和工程研究领域的热点。
[4]
[5]
《背包函数的理论与计算》，1966，(14) 1045-1047
[2)吉尔摩，戈莫里，戈莫里，切割问题的线性规划方法《切削用量的线性规划方法》，北京，1965，(13):94-120
[4。Opns。王培炎，1961，(9):849-859
[5]约束二维下料问题的两种算法。运筹学学会，1983年，31:573-586
[6]比斯利. J.E .二维切割的界限。Opns。
摘要4-5[/BR/]摘要5
1引言9-13
1.1布局问题的表述9-10
1.2布局问题的研究现状10-11
1.3主要研究内容和创新点11-12
本章总结12-13
2矩形布局问题的数学模型建立和各种算法13-21 [/BR/] 2.1矩形布局问题的数学模型建立和描述 2.2.1贪婪算法15[/比尔/] 2.2.2 BL算法15-16[/比尔/] 2.2.3向下步进算法16[/比尔/] 2.2.4最低水平线算法16-17[/比尔/] 2.3启发式算法17-19[/比尔/] 2.3.1模拟退火算法17-18[/比尔/] 2.3.2粒子群优化算法18[/比尔/] 2.3.3遗传算法18-19 2.5.2处理因素20 [/BR/]本章摘要20-21
3遗传算法蚁群算法在嵌套问题中的具体应用21-49
3.1遗传算法21-27
3.1.1遗传算法的生物学基础21
3.1.2遗传算法的发展21-23
3.1.3遗传算法的近期发展23-24 [/BR/] 3.1.4 3.2.3遗传操作28
3.2.4终止条件28-29
3.3遗传算法的基本流程29-30
3.4遗传算法在本文中的具体应用及相关改进30-32
3.4.1基因编码改进30
3.4.2初始种群生成改进30-31
3.4.3解码算法生成31-32
3 3.6蚁群算法36-43
3.6.1蚁群算法的生物学原理36-38
3.6.2蚁群算法的数学模型38-40
3.6.3蚁群算法的基本流程40
3.6.4最大-最小蚂蚁系统40-41 [/BR/] 3.6.5最优-最差蚂蚁系统41-42 [/BR/] 3.6.6蚁群算法主要改进 3.7.1遗传蚁群算法系统流程图44-46
3.7.2预处理46 [/BR/] 3.7.3遗传蚁群算法的具体规则46-47
3.7.4遗传蚁群算法的融合47-48
摘要48-49
4矩形布局设计与实施49-59
4.1系统设计49-53
4 4.2.1零件列表和零件信息列表设计53-54 [/BR/] 4.2.2图纸和图纸信息列表设计54-55
4.3实验结果55-59
4.3.1遗传算法和蚁群算法的比较55-56
4.3.2遗传算法和遗传蚁群算法的比较56-59
摘要和展望59-61
摘要59-60 [Beasley . j . e .无张力二维断头台切割算法。《运筹学杂志》，1985，36(4):298-306
您可能对工程硕士论文有购买需求，请到工程硕士论文的渠道选择:达格利·华赫。解决下料问题的计算机软件包。Tj的国际会议生产研究，温莎，安大略省，卡纳卡，1983，11:480-486
[10]斯里拉姆和康森美。修改后的霍普菲尔德二维模块布局网络。IEEE电路系统国际研讨会论文集，1990，38(6):1664-1667
[11]达格利计算机信息系统，基于知识的切割问题系统。欧洲运筹学杂志，1990，44:160-166
[12] Daza V P等人.约束二维下料问题的精确解。《欧洲运筹学杂志》，1995，84:633-644，
[13]莫拉比托·雷诺等.一种切割库存问题的“与或图”方法。欧洲操作研究杂志，1992，58:263-271
[14]康托罗维奇。组织和计划生产的数学方法。管理学1960，6:363-422
[15]保罗.阿. e .线性规划:优化新闻纸产品的关键。加拿大纸浆和纸张杂志，1956，5:145-150
[16]艾森曼。k。三重损失问题。科学，1957，3: 279-284
[17]赫尔曼。k。瓦杰达。行程计算中的线性规划。《世界纸贸易评论》，1958，7: 28-36 [/BR/] [18]王玲。智能优化算法及其应用。北京:清华大学出版社。2001.10
[19]吉尔摩，戈莫里，雷。切割库存问题的线性规划方法。运筹学，1961，9:849-859
[20]吉尔摩，戈莫里，雷。切屑问题的线性规划方法2。运筹学，1963，11:863-888
[21]曹矩，周吉，余军.矩形零件布局优化的背包算法。中国机械工程，1994，5 (2): 11-12
[22]崔耀东。矩形毛坏叶盘布局的优化算法。机械技术专家，1998，6: 32-33
[23]曹矩。周记。矩形零件布局优化的近似算法。计算机辅助设计与图形杂志，1995，7(3):190-195
[24]李建勇，E .明诚，曹跃东。利用混沌人工神经网络进行布局优化计算。制造自动化，2000，22(1): 21-22
[25]马轩。张亚龙。基于遗传算法的大型矩形件优化布局。智能系统杂志，2007，2 < 5): 48-52
[26]潘阳，李富平，杨文同等。基于遗传算法和启发式方法的二维不规则零件布局。设计与研究[。2005.7: 36-37
[27]黄洪兵。蚂蚁算法在矩形零件优化布局中的应用[[。制造业信息化2006，2: 98-100
[28]徐文伯刘瑞杰。引用该论文[[。江南大学学报。2005年，4(1): 23-26
[29]陈豪。谭利伟。一种改进的蚁群算法[[·[]。重庆文理学院学报。2008，27(1):28-31
[30]俞友明，刘玉书，颜光伟。遗传算法的编码理论及应用[[。计算机工程与应用，2005，35:86-89
[31]张晋，李东力，李平。遗传算法编码机制的比较研究[[]。中国矿业大学学报，2002，6:637-640
[32]魏新新，刘先锋，黄强，等.遗传算法选择方法比较分析四川.《通信与计算机》，2008年，8(5):61-65；
[33]龚智辉。基于遗传算法的矩形件优化排样系统研究。2003年6月，湖南大学硕士学位论文
[8]
[9]