智能优化排料方法研究
|
摘要
二维不规则排料问题是指,将一系列形状各异的待排件排放在给定材料上,找出使材料的利用率最高的方案,减少原材料的浪费。排料优化问题是NP完全问题,在许多工业制造和生产领域都有着重要的应用,也是研究的热点。
本文给出了二维不规则排料的分层实现:最上层是负责排料布局过程整体优化的智能优化算法,它确定了各个不规则待排件的排放次序、旋转角度和镜像方式;接着是负责排料组织工作的启发式BLF算法,它将排放次序、旋转角度和镜像方式确定了的不规则待排件逐个放入面料,进行排放;然后是不规则待排件的并靠判交算法以及负责实现不规则待排件面积计算、旋转、镜像、移动等操作的几何计算算法;最底层是不规则待排件的几何表达方法,即栅格水平线扫描区间表示法。对每层一一进行了实现和阐述。
对于负责排料过程整体优化的智能优化算法,本文选取了遗传算法、模拟退火算法、遗传模拟退火算法和粒子群优化算法应用到二维不规则排料问题中。将一种基于惯性权值凹函数递减策略的粒子群优化算法引入优化排料领域,与基于惯性权值线性递减策略的粒子群优化算法相比较,提高了面料利用率。针对在迭代后期容易陷入局部最优这一现象,本文提出了一种改进的基于粒子位移邻域变异的粒子群优化算法,与惯性权值递减策略相结合,形成基于粒子位移邻域变异惯性权值递减策略的粒子群优化算法,并将之应用到排料过程,与两种基于惯性权值递减策略的粒子群优化算法对比,提高了面料利用率。最后对各智能优化算法在排料中的应用效果进行了多次实验,展示了排料效果图,对实验数据进行定量对比分析,得出如下结论:(1)智能优化算法的排料效果均优于启发式直接排料;(2)智能优化算法中粒子群系列算法和模拟退火算法在排料效果上都比较好。模拟退火算法迭代过程完成后有时会取得非常好的效果,但也会有比较差的结果出现,这种情况随着迭代次数的增加有所改善;而粒子群系列算法在每次迭代完成后表现都很稳定,效果也好;(3)综合来看,基于粒子位移邻域变异惯性权值凹函数递减策略的粒子群优化算法排料效果最好。
Given a set of irregular shapes, the two-dimensional irregular nesting problem is a problem of packing the shapes within a sheet and trying to find the best arrangement that could maximize the utilization of materials, and minimize the wastage of raw materials. The problem is NP-hard even when the shapes and the material involved are rectangles. It impacts upon a wide variety of industrial applications and motivates many areas of research.
This paper gives a general view of the irregular nesting procedure by dividing it into several layers. The top-level is the intelligent optimal algorithms. They are in charge of the overall effect of the nesting procedure by ways of generating the best nesting order, rotating angle and mirroring way of every irregular shape. The next one would be the Bottom-Left-Fill heuristic algorithm which organizes the nesting procedure, putting the shapes onto the sheet one by one using BLF strategy. What comes next are the algorithm for judging whether the shapes intersect with each other, and the computational geometry methods for irregular polygons such as calculating area, rotating, mirroring, and shifting. The bottom layer is the geometric representation method for irregular shapes, approximating the irregular shapes by horizontal scan-lines, and representing them by sets of intervals.
With regard to the intelligent optimal algorithms in charge of the overall nesting process, this paper selects the genetic algorithm, simulated annealing algorithm, genetic simulated annealing algorithm and particle swarm optimization algorithm to generate the best nesting order, rotating angle and mirroring way for every irregular shapes. Besides, the paper introduces a two-dimensional irregular shapes nesting process based on a concave function strategy for decreasing inertia weight swarm optimization algorithm. To avoid the problem of trapping into local optimum at the end of the iterative process, this paper proposes an improved swarm optimization algorithm based on a kind of swarm position neighborhood mutation, and applies it to the nesting field with the combination of the decreasing inertia weight strategy. Compare with the other two decreasing inertia weight swarm optimization algorithms, this one brings out a higher material utilization rate.
Finally experiments are made to compare and quantitatively analyze the different results of these intelligent optimal algorithms, and the corresponding conclusion is drawn as following: (1) The nesting results of intelligent optimal algorithms are all better than those of traditional heuristic algorithm; (2) Among the intelligent optimal algorithms, both the particle swarm optimization algorithm and simulated annealing algorithm could give a satisfying nesting result. For the simulated annealing algorithm, perfect results happen occasionally, and so do bad ones. Nevertheless, the results will generally get better when iteration increases. As for the particle swarm optimization algorithms, they perform stably each time after the iterations, with remarkably good effects; (3) All in all, the particle swarm optimization algorithm based on the concave function strategy for decreasing inertia weight with swarm position neighborhood mutation has the best nesting performance.
本文给出了二维不规则排料的分层实现:最上层是负责排料布局过程整体优化的智能优化算法,它确定了各个不规则待排件的排放次序、旋转角度和镜像方式;接着是负责排料组织工作的启发式BLF算法,它将排放次序、旋转角度和镜像方式确定了的不规则待排件逐个放入面料,进行排放;然后是不规则待排件的并靠判交算法以及负责实现不规则待排件面积计算、旋转、镜像、移动等操作的几何计算算法;最底层是不规则待排件的几何表达方法,即栅格水平线扫描区间表示法。对每层一一进行了实现和阐述。
对于负责排料过程整体优化的智能优化算法,本文选取了遗传算法、模拟退火算法、遗传模拟退火算法和粒子群优化算法应用到二维不规则排料问题中。将一种基于惯性权值凹函数递减策略的粒子群优化算法引入优化排料领域,与基于惯性权值线性递减策略的粒子群优化算法相比较,提高了面料利用率。针对在迭代后期容易陷入局部最优这一现象,本文提出了一种改进的基于粒子位移邻域变异的粒子群优化算法,与惯性权值递减策略相结合,形成基于粒子位移邻域变异惯性权值递减策略的粒子群优化算法,并将之应用到排料过程,与两种基于惯性权值递减策略的粒子群优化算法对比,提高了面料利用率。最后对各智能优化算法在排料中的应用效果进行了多次实验,展示了排料效果图,对实验数据进行定量对比分析,得出如下结论:(1)智能优化算法的排料效果均优于启发式直接排料;(2)智能优化算法中粒子群系列算法和模拟退火算法在排料效果上都比较好。模拟退火算法迭代过程完成后有时会取得非常好的效果,但也会有比较差的结果出现,这种情况随着迭代次数的增加有所改善;而粒子群系列算法在每次迭代完成后表现都很稳定,效果也好;(3)综合来看,基于粒子位移邻域变异惯性权值凹函数递减策略的粒子群优化算法排料效果最好。
Given a set of irregular shapes, the two-dimensional irregular nesting problem is a problem of packing the shapes within a sheet and trying to find the best arrangement that could maximize the utilization of materials, and minimize the wastage of raw materials. The problem is NP-hard even when the shapes and the material involved are rectangles. It impacts upon a wide variety of industrial applications and motivates many areas of research.
This paper gives a general view of the irregular nesting procedure by dividing it into several layers. The top-level is the intelligent optimal algorithms. They are in charge of the overall effect of the nesting procedure by ways of generating the best nesting order, rotating angle and mirroring way of every irregular shape. The next one would be the Bottom-Left-Fill heuristic algorithm which organizes the nesting procedure, putting the shapes onto the sheet one by one using BLF strategy. What comes next are the algorithm for judging whether the shapes intersect with each other, and the computational geometry methods for irregular polygons such as calculating area, rotating, mirroring, and shifting. The bottom layer is the geometric representation method for irregular shapes, approximating the irregular shapes by horizontal scan-lines, and representing them by sets of intervals.
With regard to the intelligent optimal algorithms in charge of the overall nesting process, this paper selects the genetic algorithm, simulated annealing algorithm, genetic simulated annealing algorithm and particle swarm optimization algorithm to generate the best nesting order, rotating angle and mirroring way for every irregular shapes. Besides, the paper introduces a two-dimensional irregular shapes nesting process based on a concave function strategy for decreasing inertia weight swarm optimization algorithm. To avoid the problem of trapping into local optimum at the end of the iterative process, this paper proposes an improved swarm optimization algorithm based on a kind of swarm position neighborhood mutation, and applies it to the nesting field with the combination of the decreasing inertia weight strategy. Compare with the other two decreasing inertia weight swarm optimization algorithms, this one brings out a higher material utilization rate.
Finally experiments are made to compare and quantitatively analyze the different results of these intelligent optimal algorithms, and the corresponding conclusion is drawn as following: (1) The nesting results of intelligent optimal algorithms are all better than those of traditional heuristic algorithm; (2) Among the intelligent optimal algorithms, both the particle swarm optimization algorithm and simulated annealing algorithm could give a satisfying nesting result. For the simulated annealing algorithm, perfect results happen occasionally, and so do bad ones. Nevertheless, the results will generally get better when iteration increases. As for the particle swarm optimization algorithms, they perform stably each time after the iterations, with remarkably good effects; (3) All in all, the particle swarm optimization algorithm based on the concave function strategy for decreasing inertia weight with swarm position neighborhood mutation has the best nesting performance.
引文
[1]黄席樾,向长城,殷礼胜.现代智能算法理论及应用[M].第2版.北京:科学出版社,2009
[2]刘心雄,许昌永,王弘.不规则图形样件的自动排料设计[J].华中科技大学学报(自然科学版),2002,30(2):19-20
[3]陶永兰,魏福玉,王龙山.最优化技术在板材排料工艺中的应用[J].汽车工艺与材料,1997,3:45-46
[4]L.V.Kantorovich.Mathematical method of organizing and planning production(an English translation of a Russian paper published in 1939)[J].Management Science,1960,6:363-422
[5]Gilmore EC,Gomory R.E.A linear programming approach to the cutting stock problem[J].Operations Research,1961,9:849-859
[6]Gilmore P.C,Gomory R.E.A linear programming approach to the cutting stock problem Ⅱ[J].Operations Research,1963,11:863-888
[7]Gilmore P.C,Gomory R.E.Multistage cutting stock problems of two and more dimensions[J].Operations Research,1965,13:94-120
[8]Gilmore P.C,Gomory R.E.The theory and computation of Knapsack functions[J].Operations Research,1965,13:94-120
[9]Dyckhoff H.A typology of cutting and packing problems[J].European Journal of Operational Research,1990,44:145-159
[10]Hopper E,Turton B.C.H.An empirical investigation of meta-heuristic and heuristic algorithm for a 2D Packing Problem[J].European Journal of Operational Research,2001,128:34-57
[11]Burke E.K,Kendall G,Whitwell G.A New Placement Heuristic for the Orthogonal Stock Cutting Problem[J].Operations Research,2004,52(4):655-671.
[12]Yanasse H.H.Computational complexity of the capacitated lot size problem[J].Management Science,1982,28(10):74-186
[13]Dagli C.H.Knowledge-based systems for cutting stock problems[J].European Journal of Operational Research,1990,44:160-166.
[14]Schollmeyer M,Lin J Q,Krishnamurthy K,et al.Hybrid expert system and operations research for solving nesting problems[A],In:Proceedings of the World Congress on Expert System[C].New York:Pergamon Press,1991:1223-1231
[15] Dowsland K.A, Dowsland W.B. Packing problems[J]. European Journal of Operational Research, 1992, 56:2～14.
[16] Gomes A.M, Oliveira J.F. A 2-exchange heuristic for nesting problems[J]. European Journal of Operational Research, 2002,141:359～370
[17] Hopper E. Two-dimensional packing utilizing evolutionary algorithms and other meta-heuristic methods [D]. Cardiff: University of Wales, 2000
[18] Albano A, Sapuppo G. Optimal allocation of two-dimensional irregular shapes using heuristic search methods[J]. IEEE Transactions on Systems, 1980,10(5):242～248
[19] Art R C. An approach to the two dimensional irregular cutting stock probIem[R]. London: IBM Cambridge Scientific Centre, 1966
[20] Blazewicz J, Hawryluk P, Walkowiak R. Using a tabu search approach for solving the two-dimensional irregular cutting problem[J]. Annals of Operations Research, 1993, 41:313～325
[21] Marques, V.M.M, Bispo C.F.G, Sentieiro U.S. A system for the compaction of two-dimensional irregular shapes based on simulated annealing[A]. In: International Conference on Industrial Electronics, Control and Instrumentation[C], 1991, 3:1911～1916
[22] Oliveira J.F, Ferreira J.S. Algorithms for nesting problems[A]. In: Vidal RVV (ed). Applied simulated annealing[C], 1993:255～273
[23] Konopasek M. Mathematical Treatments of Some Apparel Marking and Cutting Problems[R]. U.S.: Department of Commerce Report, 1981
[24] Dighe R, Jakiela M.J. Solving Pattern Nesting Problems with Genetic Algorithms Employing Task Decomposition and Contact Detection[J], Evolutionary Computation, 1996,3:239～266
[25] Smith D. Bin Packing with adaptive search[A]. In: Lawrence Erlbaum Associates, Proceedings of the First International Conference on Genetic Algorithms and Applications [C], Hillsdale,N.J., 1985:202～207
[26] Jakobs S. On genetic algorithms for the packing of polygons[J]. European Journal of Operations Research, 1996, 88:165～181
[27] Baker B.S, Coffman E.G, Rivest R.L. Orthogonal Packings in Two Dimensions [J]. SIAM Journal on Computing, 1980, 9(4):846～855
[28] Bounsaythip C, Maouche S. Irregular Shape Nesting and Placing with Evolutionary Approach[A]. In: Proceedings of the IEEE International Conference on Systems, Man and Cybernetics[C], 1997,4:342～3430
[29] Fujita K, Akaji S, Hirokawa N. Hybrid approach for optimal nesting using a genetic algorithm and a local minimization algorithm[J].Advances in Design Automation,ASME,1993b,65(1):477-484
[30]Ratanapan K,Dagli C.H.An object-based evolutionary algorithm for solving irregular nesting problems[A].In:Proceedings for Artificial Neural Networks in Engineering Conference(ANNIE'97)[C],New York:ASME Press,1997,7:383-388
[31]王华昌,李志刚.冲裁件优化排样算法的研究[J].中国机械工程,2001,12(2):199-202
[32]贾志欣.排样问题的研究现状与趋势[J].计算机辅助设计与图形学学报,16(7):890-897
[33]崔耀东,周儒荣.单一尺寸矩形毛坯排样时长板的最优分割[J].计算机辅助设计与图形学学报,2001,13(5):434-437
[34]许超,金霞.数控直角剪排样优化系统研究[J].中国机械工程,2001,12(10):1145-1147
[35]贾志欣,殷国富,罗阳等.矩形件排样的模拟退火算法求解[J].四川大学学报,2001,33(5):35-38
[36]须文波,刘瑞杰.Ant_Q算法在矩形件优化排料中的应用[J].江南大学学报(自然科学版),2006,5(3):270-273
[37]陶献伟,王华昌,李志刚.基于填充算法的矩形件排样优化求解[J].中国机械工程,2003,14(13):1104-1107
[38]李爱平,张丰,刘雪梅.基于包容矩形的优化排样算法及实现[J].计算机工程与应用,2007,43(1):198-220
[39]苏英慧,金一庆.木规则鞋片的自动排料设计[J].浙江理工大学学报,2005,22(2):120-123
[40]顾振华,何援军,刘胡瑶.二维不规则图形排料CAD系统的设计[J].工程图学学报,2008,2:17-22
[41]刘萍,陆金桂.基于遗传算法的二维排样优化方法[J].南京化工大学学报,2001,23(5):9-12
[42]滕健,李滨慧,施洪生.用神经网络解决二维不规则零件的排料问题[J].机械设计与制造工程,1999,28(6):61-63
[43]李英华,周兆英,熊沈蜀等.二维几何形状优化排样系统2DUnivNest[J].机械工程师,1999(7):38-39
[44]陈勇.二维不规则形优化排样技术研究[D].杭州:浙江大学,2003
[45]彭文利,陈淑如,张定华.优化排料算法的研究现状与趋势[J].模具工业,2006(8):14-18
[46]曾凤华.剩余矩形匹配算法在矩形件排样中的应用[J].机电工程技术.2006,35(3):64-65
[47]Baker B.S,Coffman Eg,Rivest R.L.Orthogonal Packing in two dimensions[J].SIAM Journal on Computing,1980,9(4):846-855
[48]李伙穆,陈其明,颜庆陆.不规则多边形面积计算公式的证明及应用[J].黎明职业大学学报,2008,3:35-40
[49]王小平,曹立明.遗传算法--理论、应用与软件实现[M].第1版.西安:西安交通大学出版社,2002
[50]A.Ramesh,N.Ramesh Babu.A generic approach for nesting of 2-D sheets using genetic and heuristic algorithm[J].Computer-Aided Design,2001(33):879-891
[51]L Feng-Tse,K Cheng-Yon,H Ching-Chi.Applying the genetic approach to simulated annealing in solving some NP-hard programs[A].IEEE Transactions on Systems,Man and Cybernetics[C],1993:29-57
[52]Shi Y,Eberhart R.Empirical Study of Particle Swarm Optimization[A].Proc.of International Conference on Evolutionary Computation[C],Washington,USA,1999:1945-1950
[53]Shi Y,Eberhart R.Fuzzy adaptive particle swarm optimization[A].The IEEE Congress on Evolutionary Computation.San Francisco,USA:IEEE,2001:101-106
[54]Eberhart R,Shi Y.Tracking and optimizing dynamic systems with particle swarms[A].The IEEE Congress on Evolutionary Computation.San Francisco,USA:IEEE,2001:94-100
[55]陈贵敏,贾建援,韩琪.粒子群优化算法的惯性权值递减策略研究[J].西安交通大学学报,2006,40(1):53-56
[56]黄建江,须文波,董洪伟.一种不规则零件排样的新粒子群优化策略[J].计算机工程与应用,2007,43(19):64-70
[57]赵宗淦,陈秋郁.计算机优化排样[J].电子工艺技术,1996,4:23-25
[58]宋亚男,邓飞其,叶家玮.基于改进免疫遗传算法的不规则图形排样[J].计算机工程,2005,31(9):170-172
[59]计华.一种基于四叉树结构的排料算法[J].计算机工程,2003,29(9):80-82
[60]刘嘉敏,张胜男,黄有群.二维不规则形状自动排料算法的研究与实现[J].计算机辅助设计与图形学学报,2000,12(7):488-491
[61]陈勇,唐敏,童若锋等.基于遗传模拟退火算法的不规则多边形排样[J].计算机辅助设计与图形学学报,2003,15(5):598-603
[62]胡华.多边形的旋转靠接算法[J].计算机研究与发展,1998,35(6):567-571
[63]唐荣锡,汪嘉业.计算机图形学教程(修订版)[M].第2版.北京:科学出版社,2001
[2]刘心雄,许昌永,王弘.不规则图形样件的自动排料设计[J].华中科技大学学报(自然科学版),2002,30(2):19-20
[3]陶永兰,魏福玉,王龙山.最优化技术在板材排料工艺中的应用[J].汽车工艺与材料,1997,3:45-46
[4]L.V.Kantorovich.Mathematical method of organizing and planning production(an English translation of a Russian paper published in 1939)[J].Management Science,1960,6:363-422
[5]Gilmore EC,Gomory R.E.A linear programming approach to the cutting stock problem[J].Operations Research,1961,9:849-859
[6]Gilmore P.C,Gomory R.E.A linear programming approach to the cutting stock problem Ⅱ[J].Operations Research,1963,11:863-888
[7]Gilmore P.C,Gomory R.E.Multistage cutting stock problems of two and more dimensions[J].Operations Research,1965,13:94-120
[8]Gilmore P.C,Gomory R.E.The theory and computation of Knapsack functions[J].Operations Research,1965,13:94-120
[9]Dyckhoff H.A typology of cutting and packing problems[J].European Journal of Operational Research,1990,44:145-159
[10]Hopper E,Turton B.C.H.An empirical investigation of meta-heuristic and heuristic algorithm for a 2D Packing Problem[J].European Journal of Operational Research,2001,128:34-57
[11]Burke E.K,Kendall G,Whitwell G.A New Placement Heuristic for the Orthogonal Stock Cutting Problem[J].Operations Research,2004,52(4):655-671.
[12]Yanasse H.H.Computational complexity of the capacitated lot size problem[J].Management Science,1982,28(10):74-186
[13]Dagli C.H.Knowledge-based systems for cutting stock problems[J].European Journal of Operational Research,1990,44:160-166.
[14]Schollmeyer M,Lin J Q,Krishnamurthy K,et al.Hybrid expert system and operations research for solving nesting problems[A],In:Proceedings of the World Congress on Expert System[C].New York:Pergamon Press,1991:1223-1231
[15] Dowsland K.A, Dowsland W.B. Packing problems[J]. European Journal of Operational Research, 1992, 56:2～14.
[16] Gomes A.M, Oliveira J.F. A 2-exchange heuristic for nesting problems[J]. European Journal of Operational Research, 2002,141:359～370
[17] Hopper E. Two-dimensional packing utilizing evolutionary algorithms and other meta-heuristic methods [D]. Cardiff: University of Wales, 2000
[18] Albano A, Sapuppo G. Optimal allocation of two-dimensional irregular shapes using heuristic search methods[J]. IEEE Transactions on Systems, 1980,10(5):242～248
[19] Art R C. An approach to the two dimensional irregular cutting stock probIem[R]. London: IBM Cambridge Scientific Centre, 1966
[20] Blazewicz J, Hawryluk P, Walkowiak R. Using a tabu search approach for solving the two-dimensional irregular cutting problem[J]. Annals of Operations Research, 1993, 41:313～325
[21] Marques, V.M.M, Bispo C.F.G, Sentieiro U.S. A system for the compaction of two-dimensional irregular shapes based on simulated annealing[A]. In: International Conference on Industrial Electronics, Control and Instrumentation[C], 1991, 3:1911～1916
[22] Oliveira J.F, Ferreira J.S. Algorithms for nesting problems[A]. In: Vidal RVV (ed). Applied simulated annealing[C], 1993:255～273
[23] Konopasek M. Mathematical Treatments of Some Apparel Marking and Cutting Problems[R]. U.S.: Department of Commerce Report, 1981
[24] Dighe R, Jakiela M.J. Solving Pattern Nesting Problems with Genetic Algorithms Employing Task Decomposition and Contact Detection[J], Evolutionary Computation, 1996,3:239～266
[25] Smith D. Bin Packing with adaptive search[A]. In: Lawrence Erlbaum Associates, Proceedings of the First International Conference on Genetic Algorithms and Applications [C], Hillsdale,N.J., 1985:202～207
[26] Jakobs S. On genetic algorithms for the packing of polygons[J]. European Journal of Operations Research, 1996, 88:165～181
[27] Baker B.S, Coffman E.G, Rivest R.L. Orthogonal Packings in Two Dimensions [J]. SIAM Journal on Computing, 1980, 9(4):846～855
[28] Bounsaythip C, Maouche S. Irregular Shape Nesting and Placing with Evolutionary Approach[A]. In: Proceedings of the IEEE International Conference on Systems, Man and Cybernetics[C], 1997,4:342～3430
[29] Fujita K, Akaji S, Hirokawa N. Hybrid approach for optimal nesting using a genetic algorithm and a local minimization algorithm[J].Advances in Design Automation,ASME,1993b,65(1):477-484
[30]Ratanapan K,Dagli C.H.An object-based evolutionary algorithm for solving irregular nesting problems[A].In:Proceedings for Artificial Neural Networks in Engineering Conference(ANNIE'97)[C],New York:ASME Press,1997,7:383-388
[31]王华昌,李志刚.冲裁件优化排样算法的研究[J].中国机械工程,2001,12(2):199-202
[32]贾志欣.排样问题的研究现状与趋势[J].计算机辅助设计与图形学学报,16(7):890-897
[33]崔耀东,周儒荣.单一尺寸矩形毛坯排样时长板的最优分割[J].计算机辅助设计与图形学学报,2001,13(5):434-437
[34]许超,金霞.数控直角剪排样优化系统研究[J].中国机械工程,2001,12(10):1145-1147
[35]贾志欣,殷国富,罗阳等.矩形件排样的模拟退火算法求解[J].四川大学学报,2001,33(5):35-38
[36]须文波,刘瑞杰.Ant_Q算法在矩形件优化排料中的应用[J].江南大学学报(自然科学版),2006,5(3):270-273
[37]陶献伟,王华昌,李志刚.基于填充算法的矩形件排样优化求解[J].中国机械工程,2003,14(13):1104-1107
[38]李爱平,张丰,刘雪梅.基于包容矩形的优化排样算法及实现[J].计算机工程与应用,2007,43(1):198-220
[39]苏英慧,金一庆.木规则鞋片的自动排料设计[J].浙江理工大学学报,2005,22(2):120-123
[40]顾振华,何援军,刘胡瑶.二维不规则图形排料CAD系统的设计[J].工程图学学报,2008,2:17-22
[41]刘萍,陆金桂.基于遗传算法的二维排样优化方法[J].南京化工大学学报,2001,23(5):9-12
[42]滕健,李滨慧,施洪生.用神经网络解决二维不规则零件的排料问题[J].机械设计与制造工程,1999,28(6):61-63
[43]李英华,周兆英,熊沈蜀等.二维几何形状优化排样系统2DUnivNest[J].机械工程师,1999(7):38-39
[44]陈勇.二维不规则形优化排样技术研究[D].杭州:浙江大学,2003
[45]彭文利,陈淑如,张定华.优化排料算法的研究现状与趋势[J].模具工业,2006(8):14-18
[46]曾凤华.剩余矩形匹配算法在矩形件排样中的应用[J].机电工程技术.2006,35(3):64-65
[47]Baker B.S,Coffman Eg,Rivest R.L.Orthogonal Packing in two dimensions[J].SIAM Journal on Computing,1980,9(4):846-855
[48]李伙穆,陈其明,颜庆陆.不规则多边形面积计算公式的证明及应用[J].黎明职业大学学报,2008,3:35-40
[49]王小平,曹立明.遗传算法--理论、应用与软件实现[M].第1版.西安:西安交通大学出版社,2002
[50]A.Ramesh,N.Ramesh Babu.A generic approach for nesting of 2-D sheets using genetic and heuristic algorithm[J].Computer-Aided Design,2001(33):879-891
[51]L Feng-Tse,K Cheng-Yon,H Ching-Chi.Applying the genetic approach to simulated annealing in solving some NP-hard programs[A].IEEE Transactions on Systems,Man and Cybernetics[C],1993:29-57
[52]Shi Y,Eberhart R.Empirical Study of Particle Swarm Optimization[A].Proc.of International Conference on Evolutionary Computation[C],Washington,USA,1999:1945-1950
[53]Shi Y,Eberhart R.Fuzzy adaptive particle swarm optimization[A].The IEEE Congress on Evolutionary Computation.San Francisco,USA:IEEE,2001:101-106
[54]Eberhart R,Shi Y.Tracking and optimizing dynamic systems with particle swarms[A].The IEEE Congress on Evolutionary Computation.San Francisco,USA:IEEE,2001:94-100
[55]陈贵敏,贾建援,韩琪.粒子群优化算法的惯性权值递减策略研究[J].西安交通大学学报,2006,40(1):53-56
[56]黄建江,须文波,董洪伟.一种不规则零件排样的新粒子群优化策略[J].计算机工程与应用,2007,43(19):64-70
[57]赵宗淦,陈秋郁.计算机优化排样[J].电子工艺技术,1996,4:23-25
[58]宋亚男,邓飞其,叶家玮.基于改进免疫遗传算法的不规则图形排样[J].计算机工程,2005,31(9):170-172
[59]计华.一种基于四叉树结构的排料算法[J].计算机工程,2003,29(9):80-82
[60]刘嘉敏,张胜男,黄有群.二维不规则形状自动排料算法的研究与实现[J].计算机辅助设计与图形学学报,2000,12(7):488-491
[61]陈勇,唐敏,童若锋等.基于遗传模拟退火算法的不规则多边形排样[J].计算机辅助设计与图形学学报,2003,15(5):598-603
[62]胡华.多边形的旋转靠接算法[J].计算机研究与发展,1998,35(6):567-571
[63]唐荣锡,汪嘉业.计算机图形学教程(修订版)[M].第2版.北京:科学出版社,2001