矩形排料中遗传算法与蚁群算法的进一步透彻分析
导读：进入九十年代以后，随着计算复杂度理论的成熟以及模拟退火算法、遗传算法、禁忌搜索算法以及神经网络等现代优化算法的发展，众多学者开始将这些具有逼近全局最优解特性的算法运用于零件排样中，显示出了强大的求解复杂排样问题的能力。由本站硕士论文中心整理。
1绪论
1.1排料问题的提出
随着社会的进步，科技的发展，各种高科技逐渐的渗透到我们的日常生活中，从而把大量的人力从各种艰苦的劳动中解放出来。
从20世纪40年代蒸汽时代的到来到现在信息时代的日益成熟，机械逐步的代替了人力，尤其是伴随着电脑的普及，信息高速公路的搭建，以前一些看似复杂的问题也变得简单起来。但是随着生产力的日益提高，生产规模的不断扩大，对原材料的需求也越来越大，产品生产中的零件毛坯是直接从原材料下料得到的，由于对材料的需求越来越多，导致价格也越来越高，如何降低价格，实现利润的快速增长是当今社会对各个企业提出的最为严厉的要求，最大限度地节约材料，提高材料利用率是生产中提高效益的一个重要手段，如何从源头上解决这类问题，那就要求在对原材料进行下料的时候充分考虑到材料利用率。以前主要是由人工控制的，依靠的是工人师傅的传统经验，但是得到的结果往往不尽人意，首先，在依靠传统经验进行下料的时候，大多并不能从整体上寻求一个最优的结果，而只是依零件形状从板材直接顺序剪切，这就会造成材料的大量浪费;二是由于企业不能套料预算，导致大量钢材积压，资金占用严重;三是在下料切割过程混乱，很难定时定量定额的管理下料过程，从而造成下料生产效率低，钢材浪费严重。因而如何剪切板材，如何下料就成为解决这个问题的重中之重。
布局问题引起人们的普遍关注始于二十世纪中叶，六十年代初期，Gilmore和Gomory对一维、二维、三维排料问题进行了研究，采用列生成技术求解一维下料问题，并参照一维排样对矩形排样进行了形式化研究。提出了经典的“一刀切”和“正交切割”的二维切割方式，并利用线性规划和动态规划，以“背包问题”为模型，提出解决Guillotine切割的N级切割的排样算法【1][2][3][4]，但由于当时计算技术的落后，在实际应用中并没有得到真正的实现。直到七卜年代后期，随着计算机技术和运筹学的发展，计算速度突飞猛进，才使得对优化下料问题的理论研究得以付诸实践，而且在此后十多年的时间里，此领域的研究空前活跃。模仿人工排样并辅以人工经验和逻辑，学者们设计了众多的启发式算法[5]-[11] 0.7080年代，由于下料过程中切割方式和排列方式的不同，人们对矩形件的研究不能对所有排列进行一一列举，规划选优，只能通过启发式算法来减少因庞大数量切割方式给运算带来的不同排列方式，但启发式算法对处理的问题具有很强的依赖性，常常是只能处理某个或某几个特殊的问题的，而且，常有不可行的实例出现[[12][13]，严重制约了对这类问题的研究。进入九十年代以后，随着计算复杂度理论的成熟以及模拟退火算法、遗传算法、禁忌搜索算法以及神经网络等现代优化算法的发展，众多学者开始将这些具有逼近全局最优解特性的算法运用于零件排样中，显示出了强大的求解复杂排样问题的能力。近十几年来，人们更多的采用这些算法来研究矩形件优化排样问题。而且随着现代优化算法的理论和在其它优化问题上的应用研究逐渐成熟，越来越多的学者己经投身到利用智能优化算法来解决排料问题上，优化算法研究“布局问题”已经成为国内运筹学、计算机科学和工程领域研究的热点问题。
1.2排料问题研究现状
国外关于下料排样问题的研究最早始于前苏联人Kantovorich}l4}，193 9年发表了一篇关于一维下料问题的论文。到五十年代中期，Pau11}15}, Eisemann}l6},Herrmann和Vaj da[l']首次提出用线性规划(Linear Programming)方法来解决印刷和造纸工业的矩形件排样问题，但材料利用率不高。二维切割问题是优化问题中具有最高计算复杂度的一类优化计算问题—NP完全问题[ys}。到了60年代初期，Gilmore和Gomory}l9}一[}aa]提出了一维下料方案和二维排样问题。从众多学者开始对排样问题进行大量的研究至今，虽然取得了一定的成果，但仍没有通用的标准方法来进行求解。由于研究矩形件排样既可以直接解决矩形件排样问题，又可以作为解决二维不规则零件排样问题的基础(通过包络矩形法将不规则零件排样问题转换为矩形件排样问题)，一直是众多学者所关注的热点与焦点，涌现出了大量的研究成果[[23-25]。启发式算法在排样问题求解中占据了重要的地位。Yanasse}26]提出依次序排料的定序排样算法，算法的主要思想是根据排样零件的长、宽、面积等给出一定的优先级规则，零件按照这种优先级顺序，从板材的左下角开始，按次序排放每一个零件，该算法规则简单，易于编程实现，其缺点就在于材料利用率不高，易造成左偏高现象。Dagli和Tatoglu提出利用启发式算法进行求解，但启发规则难以确定，排样结果不稳定，不能应用于实践。Amaral}2'}提出了一种交互式排样方法，虽然计算结果比较稳定，但排样效果却不尽人意。步入70, 80年代后，随着智能优化算法(神经网络、遗传算法、禁忌搜索、模拟退火等)的不断出现，为排样问题的解决提供了新的思路。进入90年代后，随着智能优化算法不断发展，日益成熟，它们在旅行商问题、装箱问题、任务调度问等组合优化问题方面得到了成功的应用，体现出了智能优化算法的优越性。把这些算法应用于排样问题，正日益成为热门。E.Hopper和B. Turton对遗传算法排样问题中的应用进行了综述，按照空间维数和排样图形的几何形状对排样问题进行了分类。对遗传算法中的排样问题编码方法、遗传算子和解码算法进行了研究讨论。
我国的计算机辅助排样研究起步比较晚，大约始于80年代，开始时，主要集中在对矩形件排样的研究上，研究成果也主要集中在清华大学、浙江大学、上海交通大学、华中科技大学和四川大学等高等院校和研究所。至今已经获得了很大的发展，但是总体上，国内就排样问题研究和国外相比，无论是深度和广度方面，仍然有很大的差距。90年代后，矩形件排样技术有了进一步的发展。曹炬[}2s}提出了利用背包问题解法的矩形件排样的近似优化算法;崔耀东[X29]提出了组块策略，将制造同一产品所需各种不规则形状零件套排成大小各异的矩形组块，每一组块包括多个零件，下料时在整张板上按矩形组块剪切，同一张板上可以排列多个矩形组块;95年曹炬，周济[[30]等人又构造了一种近似算法，该算法的主要思想是在排样过程中根据局部最优原则不断地动态产生一些较小的矩形，然后对这些小矩形区域进行排样，同时消去一些己经排过的矩形区域，直至所有的矩形件被排完;李建勇提出分别用混沌人工神经元网络[[31味口C人工神经元网络进行排料优化计算。近10年来，各大高校也涌起了对新型智能算法的研究，如文献[[32-36]，算法主要围绕遗传算法、蚁群算法进行的，主要因为这两种与其它算法相比有着显著的优点。
1.3本文主要研究内容及创新点
本文就二维排料问题中最常见的矩形排料为出发点，通过大量文献阅读，了解了当前排料的研究现状及发展趋势，并比较了当前比较先进的几种算法，选取其中两种先进的算法一遗传算法、蚁群算法，就矩形件排样做了深入研究。本文的研究内容主要有以下几个方面:
(1)针对几种比较成熟的算法，做了相关比较;
(2)遗传算法、蚁群算法进行深入了解，比较了遗传算法、蚁群算法的优缺点;
(3)针对遗传算法，对基因编码初始化种群做出改进，以便有效的提高初始种群的质量，在遗传操作方面，提出了一种新的交叉算子，并将两种算子综合使用;变异算子方面，综合运用两种变异算子，并以一定概率随机选择不同的变异算子;解码方面通过采用文献【39]“基于最低水平线的搜索算法”;
(4)针对蚁群算法，综合考虑了矩形面积和宽高比例两个因素，动态生成了期望启发因子;
(5)对遗传算法、蚁群算法融合时机进行了分析研究，得出了最佳融合时机，并将其运用到本文中;
(6)设计并实现基于遗传一蚁群算法的矩形排样系统;
(7)通过实例说明该算法的可行性、有效性及实用性。
参考文献
[1]Gllmore P.C, Gomory R.E. The theory and computation of Knapsack functions. Opns. Res,1966, (14)1045一1047
[2] Gilmore P. C.，Gomory R.E. A linear programming approach to the cutting stock problem-PartII.Opns. Res, 1963, (11):863-887
[3]Gllmore P.C.Gomory R.E. Multistage cutting stock problem of two and more dimensions.Opns Res, 1965,(13):94-120
[4]Gllmore P.C, Gomory R.E. A linear programming approach to the cutting stock. Opns. Res,1961,(9): 849-859
[5]Wang P.Y Two algorithms for constrained two-dimensional cutting stock Problems. Operations Research society, 1983,31:573-586
[6]Beasley J.E. Bounds for Two-dimensional cutting.http://sblunwen.com/gclw/ Journal of the operational Research Society,1985,36:71-74
[7]Beasley J.E. An exact two-dimensional non-guillotine cutting tree search Produce. Opns. Soe,1985,33:49-64
[8]Beasley J.E. Algorithms for unstrained two-dimensional guillotine cutting. Journal of operational Research,1985,36(4):298-306
[9]Dagli C. H. A computer package for solving cutting stock problem Tj’International Conference Production Research, Windsor,Ontario, Canaca,1983,11:480-486
[10]Sriram M. and Kang S.M. A modified Hopfield net work for two-dimensional module Placement. Proceedings of IEEE International Symposium on circuits system,1990,38(6):1664-1667
[11]Dagli C.I-i. Knowledge-based system for cutting problems. European Journal of Operational Research,1990,44:160-166
[12] Daza V P et al. Exact solutions for constrained two-dimensional cutting stock Problems. European Journal of Operational Research,1995,84:633-644
[13]Morabito R.N. et al. An and-or-graph approach to cutting stock problem. European Journal ofOperational Researeh,1992,58:263-271
[14]Kantorovich. L.V Mathematical method of organizing and planning production (an Engfish translation of a Russian paper published in 1939).Management Science 1960,6:363-422
[15]Paull .A. E. Linear programming: A key to optimum newsprint product. Pulp and Paper Magazine of Canada,1956,5:145一150
[16]Eisemann .K .The trip loss problem.Science,1957,3:279-284
[17]Herrmann .K, Vajda. S. Linear programming in trip calculation. The World's Paper Trade Review,1958,7:28-36
[18]王凌.智能优化算法及其应用「M].北京:清华大学出版社，2001.10
[19]Gilmore P.C, Gomory.R.E. A linear programming approach to the cutting stock problem.Operations Research,1961,9:849-859
[20]Gilmore P.C, Gomory.R.E. A linear programming approach to the cutting stock problem II.Operations Research,1963,11:863-888
[21]曹矩，周济，余俊.矩形件排样优化的背包算法.中国机械工程，1994,5(2): 11-12
[22]崔耀东.矩形毛坏卜料排样的一种优化算法.机械工艺师，1998,6: 32-33
[23]曹矩，周济.矩形件排样优化的一种近似算法.计算机辅助设计和图形学学报，1995, 7(3):190-195
[24 ]李建勇，鄂明成，曹月东.利用混沌人工神经元网络进行布局优化计算.制造业自动化，2000,22(1): 21-22
[25]马炫，张亚龙.基于遗传算法的大规模矩形件优化排样.智能系统学报，2007,2 < 5 ) : 48-52
[26]杨攀，李富平，杨文通等.基于遗传算法和启发式方法的二维不规则零件排料.设计与研究[J]. 2005, 7: 36-37
[27]黄红兵.蚂蚁算法在矩形件优化排样中的应用[[J].制造业信息化2006,2: 98-100
[28]刘瑞杰，须文波.求解矩形件优化排料蚁群算法[[J].江南大学学报.2005,4(1): 23-26
[29]陈浩，潭立伟.一种改进的蚁群算法[[J].重庆文理学院学报.2008,27(1):28-31
[30]余有明，刘玉树，阎光伟.遗传算法的编码理论与应用[[J].计算机机工程与应用，2005,35:86-89
[31]张晋，李冬黎，李平.遗传算法编码机制的比较研究[[J].中国矿业大学学报，2002,6:637-640
[32]魏全新，刘贤锋，黄锵等.遗传算法选择方法的比较分析川.通讯和计算机，2008,8(5):61-65;
[33]龚志辉.基于遗传算法的矩形件优化排样系统研究.2003,6,湖南大学硕士学位论文
摘要 4-5
ABSTRACT 5
1 绪论 9-13
1.1 排料问题的提出 9-10
1.2 排料问题研究现状 10-11
1.3 本文主要研究内容及创新点 11-12
本章小结 12-13
2 矩形排料问题的数学模型建立及及各种算法 13-21
2.1 矩形排料问题数学模型的提出及建立 13-15
2.1.1 矩形件排样问题的描述 13
2.1.2 数学模型的建立 13-15
2.2 矩形排样的定序算法 15-17
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.3.4 蚁群算法 19
2.4 矩形件排样算法的优缺点综合比较 19-20
2.5 矩形排样算法的影响因素和约束条件 20
2.5.1 几何因素 20
2.5.2 加工因素 20
本章小结 20-21
3 遗传算法蚁群算法在排料问题中的具体应用 21-49
3.1 遗传算法 21-27
3.1.1 遗传算法生物学基础 21
3.1.2 遗传算法的发展 21-23
3.1.3 遗传算法最新动态 23-24
3.1.4 遗传算法的特点 24-25
3.1.5 遗传算法的应用 25-27
3.2 遗传算法的基本构成部分 27-29
3.2.1 编码 27
3.2.2 适应度函数 27-28
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.4.4 适应度函数的选择 32
3.5 遗传操作 32-36
3.5.1 交叉算子生成及改进 32-34
3.5.2 变异算子 34-35
3.5.3 染色体的选择 35-36
3.6 蚁群算法 36-43
3.6.1 蚁群算法的生物学原理 36-38
3.6.2 蚁群算法数学模型 38-40
3.6.3 蚁群算法的基本流程 40
3.6.4 最大-最小蚂蚁系统 40-41
3.6.5 最优-最差蚂蚁系统 41-42
3.6.6 蚁群算法主要改进 42
3.6.7 蚁群算法的特点 42-43
3.6.8 蚁群算法的应用 43
3.7 遗传算法与蚁群算法的融合 43-48
3.7.1 遗传-蚁群算法系统流程图 44-46
3.7.2 前期预处理 46
3.7.3 遗传-蚁群算法的具体规则 46-47
3.7.4 遗传-蚁群算法的融合 47-48
本章小结 48-49
4 矩形排样设计与实现 49-59
4.1 系统设计 49-53
4.1.1 系统主界面 50-51
4.1.2 板材编辑界面 51
4.1.3 零件编辑界面 51-52
4.1.4 排样参数输入界面 52
4.1.5 数据管理模块 52-53
4.2 数据库设计 53-55
4.2.1 零件表与零件信息表设计 53-54
4.2.2 板材表与板材信息表设计 54-55
4.3 实验结果 55-59
4.3.1 遗传算法与蚁群算法比较 55-56
4.3.2 遗传算法与遗传-蚁群算法比较 56-59
总结与展望 59-61
总结 59-60
展望 60-61
参考文献 61-64
致谢 64-65
攻读硕士期间发表的学术论文 65-66
您可能有工程硕士学位论文方面的购买需求，请到工程论文硕士论文频道选取：