基于NGA的任意多边形优化排样技术的研究
|
摘要
本文采用二步法对任意多边形的优化排样技术进行了研究。首先，将零件库中的零件根据其面积大小进行分类，把面积比较小的零件存成一个填充库，剩下的零件存成一个排样库。在此基础上，用基于小生境技术的遗传算法对排样库中的零件进行排样：先建立优化排样的数学模型，根据该数学模型将多边形在矩形板料上的排列方式转化为特定的编码，并建立编码和和排样方式的映射模型，然后采用基于小生境的遗传算法对排样过程进行优化。为了减少排样图中的空隙，提高材料的利用率，在采用NGA对排样库中的零件进行排样的基础上，本文通过一定的填充算法，将筛出来的填充库中的零件逐个填充到排样图的空隙中，完成最后的排样。根据文中提出的思路，设计开发了能够实际应用的优化排样系统。
This paper had been carrying out a study on the layout technology of arbitrary polygons with two-step theory. First, we sorted the accessories in parts-storage into two portions according to their sizes: A fill-storage was established to accommodate the small accessories and a layout-storage to the others. Then, the theme provided efficient layout solutions to those accessories of layout-storage with niched genetic algorithm as a tool: through establishing the mathematical model of layout-optimizing problem and according to this model, the theme translated the layout of polygons in rectangle into a special coding of genetic algorithm. Following these steps, a mapping model between the codes and the layout of polygons were set up. With that, the theme optimized the layout process using niched genetic algorithm. For decreasing the interstices in the layout picture and promoting the utilization ratio, we fulfilled the last layout process by filling all parts of fill-storage into this layout result which basing
on NGA method. According to this thinking-routine discussed above, we designed and developed effective layout optimization system.
This paper had been carrying out a study on the layout technology of arbitrary polygons with two-step theory. First, we sorted the accessories in parts-storage into two portions according to their sizes: A fill-storage was established to accommodate the small accessories and a layout-storage to the others. Then, the theme provided efficient layout solutions to those accessories of layout-storage with niched genetic algorithm as a tool: through establishing the mathematical model of layout-optimizing problem and according to this model, the theme translated the layout of polygons in rectangle into a special coding of genetic algorithm. Following these steps, a mapping model between the codes and the layout of polygons were set up. With that, the theme optimized the layout process using niched genetic algorithm. For decreasing the interstices in the layout picture and promoting the utilization ratio, we fulfilled the last layout process by filling all parts of fill-storage into this layout result which basing
on NGA method. According to this thinking-routine discussed above, we designed and developed effective layout optimization system.
引文
[1] 周泓一，金延赞．二维不规则形状的最优布局问题[J]．浙江大学学报，1988(2)：92-98．
[2] Andrea Lodi, Silvano Martello., Daniele Vigo Recent advances on two-dimensional bin packing problems, Discrete Applied Mathematics 123 (2002) 379-396
[3] J.O. Berkey, P.Y. Wang, Two dimensional finite bin packing algorithms, J. Oper. Res. Soc. 38 (1987)423-429.
[4] N. Christo8des, C. Whitlock, An algorithm for two-dimensional cutting problems, Oper. Res. 25(1977)30-44.
[5] F.K.R. Chung, M.R. Garey, D.S. Johnson, On packing two-dimensional bins, SIAM J. Algebraic Discrete Meth. 3(1982)66-76.
[6] J.B. Frenk, G.G. Galambos, Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem, Computing 39(1987)201-217.
[7] 曹炬，周济，余俊矩形件排样优化的背包算法 中国机械工程，1994，5(2)：11-12
[8] 曹炬 二维异形切割件优化排样的拟合算法 中国机械工程，2000，4，11(4)：438-441．
[9] 龚时华等 计算机自动排样中NFP问题的算法实现．华中理工大学学报，1998，12，26(12)：29-31．
[10] 马建，滕弘飞，刘德全基于样图的排样及其样图检索方法 软件学报 2000，11(12)
[11] 滕健，李滨慧，施洪生等．用神经网络解决二维不规则零件的排料问题[J]．机械设计与制造工程 1999，28(6)，11：61-63
[12] A. Lodi, S. Marteilo, D. Vigo, Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems, INFORMS J. Comput. 11(1999)345-357.
[13] B.E. Bengtsson, Packing rectangular pieces—a heuristic approach, Comput. J. 25(1982)353-357.
[14] A. El-Bouri, N. Popplewell, S. Balakrishnan, A. Alfa, A search based heuristic for the two-dimensional bin-packing problem, INFOR 32(1994)265-274.
[15] A. Lodi, S. Martello, D. Vigo, Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems, INFORMS J. Comput. 11(1999)345-357.
[16] Exact and Heuristic Approaches for Assignment in Multiple-Container Packing, Boston College Technical Report BCCS-97-02, 1997,2
[17] Y. Prasad and S. Somasundaram. CASNS-a heuristic algorithm for the nesting of irregular-shaped sheet-metal blanks. Computer-Aided Engineering Journal, pages 69-73, April 1991.
[18] S.A. Segenreich and F. Braga, "Optimal Nesting of General Plane Figures: A Monte Carlo Heuristical Approach," Computers and Graphics 1986,10(3), 229-238.
[19] C.H. Dagli, Pipatpong Poshyanonda, Genetic Neuro-Nester for Irregular Patterns, Intelligent Engineering Systems Through Artificial Neural Networks, Volume 3, p. 825, ASME Press, New York 1993.
[20] 王小平，曹立明 遗传算法理论、应用及软件实现[M]，西安交通大学出版社 2002，1
[21] 陈国良，王熙法，庄镇泉等．遗传算法及其应用[M]．北京：人民邮电出版社，1996．
[22] Goldberg, D. E., 1989, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley.
[23] 曹炬，冯松．遗传算法在矩形件优化排样中的应用[J]．计算机工程与应用，1995，5．
[24] 贾志欣，殷国富，罗阳．二维不规则零件排样问题的遗传算法求解[J]．计算机辅助设计与图形学学报，2002，14(5)：467-470
[25] Kikuo Fujita, Shinsuke Akagi and Noriyasu Hirokawa. Hybrid Approach for Optimal Nesting Using a Genetic Algorithm anda Local Minimization Algorithm[J].
[26] 张和民，程耀东，柯映林．二维凹多边形的自动补凸技术——及其在CAD／CAM中的应用[J]．机电工程，1996，1：8-10．
[27] Cavicchio D J.Reproductive Adaptive Plans. Proceedings of the ACM 1972 Annual Conference, 1972:1-11
[28] Goldberg D E, Richardson J. Genetic Algorithms with Sharing for Multimodal Function Optimization. Genetic Algorithms and Their Applications: Proceedings of the Second International Conference on Genetic Algorithms, Hillsdale, NJ,. 1987:41-49
[29] 韩祯祥，文福栓．模拟进化优化方法及其应用．遗传算法[J]．计算机科学，1995(12)：47-56．
[30] 张成才，孙喜梅，朱陶业．AutoCAD的DXF文件格式及其转换接口研究[J]．微型电脑应用 2001，17(8)：54-56
[31] 曹建国，李建明．AutoCAD12.0应用与开发教程(三)[M]，学苑出版社，1994，10
[32] 周培德 计算几何[M] 北京：清华大学出版社，1999
[33] 张全火，曾晓帆，范慧琳等．任意两个多边形的求交算法[J]．华侨大学学报(自然科学版)1995,16(1)，1
[2] Andrea Lodi, Silvano Martello., Daniele Vigo Recent advances on two-dimensional bin packing problems, Discrete Applied Mathematics 123 (2002) 379-396
[3] J.O. Berkey, P.Y. Wang, Two dimensional finite bin packing algorithms, J. Oper. Res. Soc. 38 (1987)423-429.
[4] N. Christo8des, C. Whitlock, An algorithm for two-dimensional cutting problems, Oper. Res. 25(1977)30-44.
[5] F.K.R. Chung, M.R. Garey, D.S. Johnson, On packing two-dimensional bins, SIAM J. Algebraic Discrete Meth. 3(1982)66-76.
[6] J.B. Frenk, G.G. Galambos, Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem, Computing 39(1987)201-217.
[7] 曹炬，周济，余俊矩形件排样优化的背包算法 中国机械工程，1994，5(2)：11-12
[8] 曹炬 二维异形切割件优化排样的拟合算法 中国机械工程，2000，4，11(4)：438-441．
[9] 龚时华等 计算机自动排样中NFP问题的算法实现．华中理工大学学报，1998，12，26(12)：29-31．
[10] 马建，滕弘飞，刘德全基于样图的排样及其样图检索方法 软件学报 2000，11(12)
[11] 滕健，李滨慧，施洪生等．用神经网络解决二维不规则零件的排料问题[J]．机械设计与制造工程 1999，28(6)，11：61-63
[12] A. Lodi, S. Marteilo, D. Vigo, Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems, INFORMS J. Comput. 11(1999)345-357.
[13] B.E. Bengtsson, Packing rectangular pieces—a heuristic approach, Comput. J. 25(1982)353-357.
[14] A. El-Bouri, N. Popplewell, S. Balakrishnan, A. Alfa, A search based heuristic for the two-dimensional bin-packing problem, INFOR 32(1994)265-274.
[15] A. Lodi, S. Martello, D. Vigo, Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems, INFORMS J. Comput. 11(1999)345-357.
[16] Exact and Heuristic Approaches for Assignment in Multiple-Container Packing, Boston College Technical Report BCCS-97-02, 1997,2
[17] Y. Prasad and S. Somasundaram. CASNS-a heuristic algorithm for the nesting of irregular-shaped sheet-metal blanks. Computer-Aided Engineering Journal, pages 69-73, April 1991.
[18] S.A. Segenreich and F. Braga, "Optimal Nesting of General Plane Figures: A Monte Carlo Heuristical Approach," Computers and Graphics 1986,10(3), 229-238.
[19] C.H. Dagli, Pipatpong Poshyanonda, Genetic Neuro-Nester for Irregular Patterns, Intelligent Engineering Systems Through Artificial Neural Networks, Volume 3, p. 825, ASME Press, New York 1993.
[20] 王小平，曹立明 遗传算法理论、应用及软件实现[M]，西安交通大学出版社 2002，1
[21] 陈国良，王熙法，庄镇泉等．遗传算法及其应用[M]．北京：人民邮电出版社，1996．
[22] Goldberg, D. E., 1989, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley.
[23] 曹炬，冯松．遗传算法在矩形件优化排样中的应用[J]．计算机工程与应用，1995，5．
[24] 贾志欣，殷国富，罗阳．二维不规则零件排样问题的遗传算法求解[J]．计算机辅助设计与图形学学报，2002，14(5)：467-470
[25] Kikuo Fujita, Shinsuke Akagi and Noriyasu Hirokawa. Hybrid Approach for Optimal Nesting Using a Genetic Algorithm anda Local Minimization Algorithm[J].
[26] 张和民，程耀东，柯映林．二维凹多边形的自动补凸技术——及其在CAD／CAM中的应用[J]．机电工程，1996，1：8-10．
[27] Cavicchio D J.Reproductive Adaptive Plans. Proceedings of the ACM 1972 Annual Conference, 1972:1-11
[28] Goldberg D E, Richardson J. Genetic Algorithms with Sharing for Multimodal Function Optimization. Genetic Algorithms and Their Applications: Proceedings of the Second International Conference on Genetic Algorithms, Hillsdale, NJ,. 1987:41-49
[29] 韩祯祥，文福栓．模拟进化优化方法及其应用．遗传算法[J]．计算机科学，1995(12)：47-56．
[30] 张成才，孙喜梅，朱陶业．AutoCAD的DXF文件格式及其转换接口研究[J]．微型电脑应用 2001，17(8)：54-56
[31] 曹建国，李建明．AutoCAD12.0应用与开发教程(三)[M]，学苑出版社，1994，10
[32] 周培德 计算几何[M] 北京：清华大学出版社，1999
[33] 张全火，曾晓帆，范慧琳等．任意两个多边形的求交算法[J]．华侨大学学报(自然科学版)1995,16(1)，1