船体建造板材套料系统中排样优化算法与碰靠技术研究
|
摘要
提高资源利用效率和应用计算机技术是现代船舶制造工业实现“绿色造船”模式、增强造船企业的国际竞争力的主要方法和途径。排样优化技术则是工业产品设计、制造及使用中如何节约原材料、优化利用资源的重要手段。运用计算机技术实现排样自动化和智能化,将很大程度地提高劳动效率和资源利用率,因此对优化排样问题的研究具有重要经济意义和社会效益。
优化排样问题就是将一系列形状各异的零件排放在给定的原材料上,在满足一定工艺要求或约束的条件下寻找出零件的最优布局,以达到原材料利用率最大的优化目标,具体到不同的行业以及切割、排样环境,表现为不同的约束形式。从数学计算复杂性理论看,优化排样问题属于组合优化问题和NP完全问题,它很难用单一的知识模型(如数学模型)来精确表达,对于二维不规则零件的排样优化,零件形状的复杂性将使得计算求解十分困难。特别的,大规模规则件排样和不规则件排样问题随着问题规模的增大,计算复杂度更是飞速增长。如何缩短排样时间同时提高板料利用率,是该问题研究的难点,也是本文讨论的重点。针对目前排样问题中存在的难点和关键问题,本文围绕排样图形预处理、图形入排控制、图形碰靠技术三个方面进行了深入的研究,提出了一系列解决方案和算法,并通过开发的船体建造板材智能排样系统进行了验算和分析,研究成果和创新点可概括如下:
(1)图形入排控制算法优化
1)由于一般的遗传算法存在早熟收敛问题,本文利用基于排挤机制的小生境技术对算法进行改进,同时根据排样编码的具体含义,给出了改进的免疫浓度定义,通过改进小生境免疫遗传算法从而散步解,避免陷入局部最优。并将其应用于计算机辅助排样领域,将改进的免疫因子和小生境遗传算法相结合,用于求解矩形件及不规则件的排样问题。
2)针对圆形包络的二维不规则件排样问题,本文提出一种基于已入排圆形重心最低规则的圆弧搜索方法作为改进的解码方法(ASALC,Arc Search Algorithm based on the lowest center)。在使用改进遗传算法智能寻优的基础上,在优化计算过程中运用基于圆形包络的新解码算法ASALC将排样序列转化为排样图。
3)排样优化问题中混合算法的改进研究及实现。
(2)碰靠技术研究与改进。
对于基于轮廓矢量信息图形的碰靠技术研究:根据船体建造板材套料系统开发过程中的需要和实例碰靠分析,提出判距-碰靠思路下的基于矩形包络的不规则件碰靠算法和不规则件最佳吻合碰靠定位算法;构建判交-分离思路下的一种碰靠方法——基于基础几何图元的不规则件碰靠技术。对于基于位图的碰靠技术:在对基于位图的图形表示特点进行分析的基础上,对比研究了基于位图的三种碰靠实现模型,给出了碰靠算法选择原则。
(3)图形预处理技术的改进
对二维不规则零件的包络矩形求取方法进行了改进,提出了一种改进的快速求取方法,可以有效地减少计算量,加快运算速度。在对船体零件不规则图形聚类分析的基础上,根据提取的零件图形聚类特征值筛选出同类或相似类零件参与优化排样过程,然后通过同类零件组合(拆分)、其他异类零件(如特殊形状或面积较小的零件)进行快速填充等方法进行图形的预处理。
本课题与广州文冲船厂合作,以自动、交互排样为一体,设计开发出船体建造板材套料系统,并实现排样零件的数据信息管理。
To improve the efficiency of resource usage and to apply the computer technology in modern shipbuilding industry are the main ways and means to achieve a "green building" model and to enhance shipbuilding enterprises’international competitiveness. Packing optimization technology is an important method to economize and optimize the use of resources and materials in industrial product design and manufacture. The application of computer technology to achieve automatc and intelligent layout will improve the labor efficiency and resource utilization to a great extent, therefore, optimal packing study has important economic and social benefits.
Optimal packing is a process to arrange a series of different parts in a given raw material under certain requirements or constraints. The optimization goal is to find the optimal layout of parts in order to achieve maximum utilization of raw materials or the least waste.The optimal packing problem belongs to the NP-complete problem with tiptop calculate complexity, and it is difficult to use a single knowledge model (such as the mathematical model) or effective polynomial algorithms for precise expression, particularly for two-dimensional irregular parts packing optimization with the shape of the complexity of the parts. In particular,with the inereasing of dimentions of regular packing-graphics and irregular graphics,the complexity of computation increases rapidly. How to recrease the time of packing and increase the utilization ratio of materials is the focus that is cared about by researchers and discussed in the dissertation. In view of the current problems and critical issues, this paper studies on the fields of packing graphics pretreatment, packing control, and contacting technology, and puts forward a series of solutions and algorithms. The hull building automatic packing system is designed and implemented for verification and analysis. The following are the main work done in the dissertation:
(1) Control of packing.
1) An improved NIGA(Niche Immune Genetic Algorithm) for solving the packing problem.
2) An new ASALC(Arc Search Algorithm based on the Lowest Center) for decoding in solving the irregular graphics packing problem with the enclosure circle.
3) Combination of the multi-algorithms for solving the irregular graphics packing problem.
(2) Improvement of the packing graphics pretreatment.
(3) Contacting technology study.
优化排样问题就是将一系列形状各异的零件排放在给定的原材料上,在满足一定工艺要求或约束的条件下寻找出零件的最优布局,以达到原材料利用率最大的优化目标,具体到不同的行业以及切割、排样环境,表现为不同的约束形式。从数学计算复杂性理论看,优化排样问题属于组合优化问题和NP完全问题,它很难用单一的知识模型(如数学模型)来精确表达,对于二维不规则零件的排样优化,零件形状的复杂性将使得计算求解十分困难。特别的,大规模规则件排样和不规则件排样问题随着问题规模的增大,计算复杂度更是飞速增长。如何缩短排样时间同时提高板料利用率,是该问题研究的难点,也是本文讨论的重点。针对目前排样问题中存在的难点和关键问题,本文围绕排样图形预处理、图形入排控制、图形碰靠技术三个方面进行了深入的研究,提出了一系列解决方案和算法,并通过开发的船体建造板材智能排样系统进行了验算和分析,研究成果和创新点可概括如下:
(1)图形入排控制算法优化
1)由于一般的遗传算法存在早熟收敛问题,本文利用基于排挤机制的小生境技术对算法进行改进,同时根据排样编码的具体含义,给出了改进的免疫浓度定义,通过改进小生境免疫遗传算法从而散步解,避免陷入局部最优。并将其应用于计算机辅助排样领域,将改进的免疫因子和小生境遗传算法相结合,用于求解矩形件及不规则件的排样问题。
2)针对圆形包络的二维不规则件排样问题,本文提出一种基于已入排圆形重心最低规则的圆弧搜索方法作为改进的解码方法(ASALC,Arc Search Algorithm based on the lowest center)。在使用改进遗传算法智能寻优的基础上,在优化计算过程中运用基于圆形包络的新解码算法ASALC将排样序列转化为排样图。
3)排样优化问题中混合算法的改进研究及实现。
(2)碰靠技术研究与改进。
对于基于轮廓矢量信息图形的碰靠技术研究:根据船体建造板材套料系统开发过程中的需要和实例碰靠分析,提出判距-碰靠思路下的基于矩形包络的不规则件碰靠算法和不规则件最佳吻合碰靠定位算法;构建判交-分离思路下的一种碰靠方法——基于基础几何图元的不规则件碰靠技术。对于基于位图的碰靠技术:在对基于位图的图形表示特点进行分析的基础上,对比研究了基于位图的三种碰靠实现模型,给出了碰靠算法选择原则。
(3)图形预处理技术的改进
对二维不规则零件的包络矩形求取方法进行了改进,提出了一种改进的快速求取方法,可以有效地减少计算量,加快运算速度。在对船体零件不规则图形聚类分析的基础上,根据提取的零件图形聚类特征值筛选出同类或相似类零件参与优化排样过程,然后通过同类零件组合(拆分)、其他异类零件(如特殊形状或面积较小的零件)进行快速填充等方法进行图形的预处理。
本课题与广州文冲船厂合作,以自动、交互排样为一体,设计开发出船体建造板材套料系统,并实现排样零件的数据信息管理。
To improve the efficiency of resource usage and to apply the computer technology in modern shipbuilding industry are the main ways and means to achieve a "green building" model and to enhance shipbuilding enterprises’international competitiveness. Packing optimization technology is an important method to economize and optimize the use of resources and materials in industrial product design and manufacture. The application of computer technology to achieve automatc and intelligent layout will improve the labor efficiency and resource utilization to a great extent, therefore, optimal packing study has important economic and social benefits.
Optimal packing is a process to arrange a series of different parts in a given raw material under certain requirements or constraints. The optimization goal is to find the optimal layout of parts in order to achieve maximum utilization of raw materials or the least waste.The optimal packing problem belongs to the NP-complete problem with tiptop calculate complexity, and it is difficult to use a single knowledge model (such as the mathematical model) or effective polynomial algorithms for precise expression, particularly for two-dimensional irregular parts packing optimization with the shape of the complexity of the parts. In particular,with the inereasing of dimentions of regular packing-graphics and irregular graphics,the complexity of computation increases rapidly. How to recrease the time of packing and increase the utilization ratio of materials is the focus that is cared about by researchers and discussed in the dissertation. In view of the current problems and critical issues, this paper studies on the fields of packing graphics pretreatment, packing control, and contacting technology, and puts forward a series of solutions and algorithms. The hull building automatic packing system is designed and implemented for verification and analysis. The following are the main work done in the dissertation:
(1) Control of packing.
1) An improved NIGA(Niche Immune Genetic Algorithm) for solving the packing problem.
2) An new ASALC(Arc Search Algorithm based on the Lowest Center) for decoding in solving the irregular graphics packing problem with the enclosure circle.
3) Combination of the multi-algorithms for solving the irregular graphics packing problem.
(2) Improvement of the packing graphics pretreatment.
(3) Contacting technology study.
引文
[1]魏凉良.智能二维排样系统的研究及软件开发.华南理工大学硕士学位论文2003:l
[2]贾志欣.面向发电设备制造的下料优化排样原理与关键技术.四川大学博士学位论文.2002
[3]杨威.板材排样优化的计算智能方法研究.四川大学硕士学位论文.2002
[4]张达科.服装纸样排版自动优化系统.华南理工大学硕士学位论文.2002
[5] Gomes,A.Miguel; Oliveira,Jose F.. A 2-exchange heuristic for nesting problems. European Journal of Operational Research, 2002, 141(2): 359-370
[6]宋佩华,蒋联源,欧启忠.基于离散粒子群优化算法求解矩形件排样问题.计算机应用与软件, 2008, 25(1):238—240
[7]马广昆,刘嘉敏,黄有群,岳勇,Malcolm Keech.一种有约束矩形排样问题的求解算法.沈阳工业大学学报, 2006, 28(4): 449—453
[8]贾志欣.排样问题的研究现状与趋势.计算机辅助设计与图形学学报, 2004, 16(7): 890—897
[9]白瑞斌.临界多边形法在二维不规则零件排样中的研究与实现.西北工业大学硕士学位论文.2002
[10]周石林.一维下料问题的研究.南京航空航天大学.硕士学位论文.2000
[11] Wei Liangliang, YeJiawei. Contrast of one-dimensional Cutting Algorithm. The 5th World Multiconference on Systemics,Cybernetics and Inofmratics Orlando,USA,2001.
[12] Schilling,Gordian; Georgiadis,Miehael C.. An algorithm for the determination of optimal cutting patterns. Computers and Operations Research, 2002, 29(8): 1041一1058.
[13] Zak,Eugene J.. Modeling multistage cutting stock problems. European Journal of Operational Research, 2002, 141(2): 313-327.
[14] Fayard,Didier;Zissimo Poulos,Vassilis,An approximation algorithm for solving unconstrained two-dimensional knapsack problems , European Journal of Operational Research, 1995, 84(3): 618一632
[15] Dell’Amico,Mauro; Martello,Silvano; Vigo,Daniele. A lower bound for the non-oriented two-dimensional bin packing problem. Discrete Applied Mathematics, 2002, 118(1-2):13-24
[16] Hopper,E.; Turton,B.C.H.. An empirical investigation of meta-heuristic and Heuristic algorithms for a 2D packing problem. European Joural of Operational Research, 2001, 128(1):34一57
[17] Wu,Yu-Liang;Huang,Wenqi; Lau,Siu-chung; Wong,C.K.; Young,Gilbert H..An effective quasi-human based heuristic for solving the rectangle packing problem. European Journal of Operational Research, 2002, 141(2): 341一358
[18] Lodi,Andrea; Martello,Silvano; Vigo,Daniele. Approximation algorithms for The oriented two-dimensional bin Packing Problem. European Journal of Operational Research, 1999, 112(1): 158-166
[19] Cung,Van-Dat; Hifi,Mhand; LeCun,Bertrand. Constrained two-dimensional Cutting stock problems a best-first branch-and-bound algorithm. International Transactions in Operational Research, 2000, 7(3): 185-210
[20] Alvarez-Valdes,Ramon; Parajon,Antonio; Tamarit. Jose’s Manuel,A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems. Computers and Operations Research, 2002, 29(7): 925-947
[21] KlemPous,Ryszard; Kotowski,Jerzy; Szlachcic,Ewa. Interactive proeedures in lagre-scale two-dimensional cutting stock problems. Jounralof Computational and Applied Mathematics, 1996, 66(1-2): 323-331
[22]毕艳丽,张宏国.几何图形的匹配识别.佳木斯大学学报(自然科学版), 2000年, 18(3):252-255
[23] Milenkovic,VictorJ.. Rotational polygon containment and minimum enclosure using only robust 2D constructions. Computational Geometry, 1999, 13(1): 3-19
[24] Theodoracatos,Vassilios E.; Grimsley,James L.. The optimal Packing of arbitrarily-shaped polygons using simulated annealing and polynomial-time cooling schedules. Computer Methods in Applied Mechanics and Engineering, 1995, 125(l-4): 53-70
[25]何春雄.智能计算方法讲义.华南理工大学数学科学学院, 2007
[26] Bennell,Julia A.; Dowsland,Kathryn A.; Dowsland,William B..The irregular cutting-stock problem——a new procedure for deriving the no-fit Polygon.Computers and Operations Research, 2001, 28(3): 271-287
[27]葛红,免疫算法及核聚类人工神经免疫网络的应用研究,华南理工大学博士学位论文,2003年5月,pp:34-37
[28]文军.基于CASE推理的排样算法.湖北民族学院学报(自然科学版),第18卷第2期,2000年5月.
[29]王凌.智能优化算法及其应用.清华大学出版社.2000年9月:1,10-11,12
[30]李明.智能优化排样技术研究.浙江大学博士学位论文. 2006
[31]张荣发.应用线性规划优化框架保持架落料排样工艺.锻压技术.1994年no.l:27-31
[32]范晓英,魏炜.应用线性规划法在钢筋下料中的应用.沈阳建筑工程学院学报, 1998, 14(2): 154一157
[33]张之燕.落料排样工艺的线性规划.模具工业,1994年No.12:12-14
[34] Goldberg DE. Genetic Algorithms in Search , Optimization and Machine Learning Reading,MA: Addison Wesley.1989
[35] Song Yanan,Ye Jiawei,Wei Liangliang,et.al..The Analysis,New Development and of Packing(Nesting),Symposium on the development of ship-building & ship-repairing Industry[C].2003,Guangzhou China,2003.3.21-22,:174-180
[36]伊登峰.多边形优化排样中小零件的填充算法[J].制造业信息化,2007, 12:83-85
[37] Vladimir N.Vapnik著.张学工译.统计学习理论的本质.清华大学出版社.2000年9月:123
[38]边肇棋,张学工.模式识别.清华大学出版社.1999年9月:4
[39] Chiu,S.,“Fuzzy Model Identification Based on Cluster Estimation,”Journal of Intelligent & Fuzzy Systems,1994, 2(3)
[40] Yager,R.andD.Filev,"Generation of Fuzzy Rules by Mountain Clustering," Journal of Intelligent & Fuzzy Systems,1994, 2(3): 209-219
[41]周永权,谢宁新.山峰-减法聚类神经元模型及学习算.广西科学院学报, Vol.18. No.4:148-154
[42]飞思科技产品研发中.matlba6.5辅助神经网络分析与设计..电子工业出版社.2003年l月:165-175
[43]闻新,周露,王丹力,熊晓英.matlab神经网络应用设计.科学出版社.2000: 271-295
[44]张立明.人工神经网络的模型及其应用.复旦大学出版社.1992年9月:127-148
[45] Guo,Guodong; Li,Stan Z.; Chan,Kap Luk. A neural network model with bounded-weights for Pattern classification. Computers and Operations Research, 2004, 31(9): 1411-1426
[46] Angulo,Cecilio; Parra,Xavier; Catala,Andreu. K-SVCR. A support vector machine for multi-class classification. Neurocomput ng, 2003, 55(l-2): 57-77
[47] Arenas-Gareia,J.; Perez-Cruz,F.. Multi-class support vector machines: a new approach. Acoustics, Speech and Signal Processing , 2003. Proceedings.(ICASSP’03).2003 IEEE International Conference on,Volume:2,6-10 April 2003:Ⅱ-781-4
[48] Franc,V.; Hlavac,V.. Multi-class support vector machine. Pattern Recognition, 2002. Proceedings. 16th International Conference , Volume:2 , 11-15 Aug. 2002:236-239
[49] Chao Yuan; Casasent,D.. Support vector machines for class representation and discrimination. Neural Networks,2003. Proceedings of the International Joint Conference on,Volume:2,20-24 July 2003:1611-1616
[50]莫鸿强.遗传算法搜索能力和编码方式研究.华南理工大学工学博士学位文.2001年4月
[51]王小平,曹立明.遗传算法——理论、应用与软件实现.西安交通大学出版2002年l月
[52]张文修,梁怡.遗传算法的数学基础.西安交通大学出版社.2001年4月
[53] [美]Zbigniew Michalewicz David B.Fogel著,曹宏庆,李艳,董红斌等。如何求解问题——现代启发式方法。中国水利水电出版社.2003年2月
[54]王正志,薄涛.进化计算.国防科技大学出版社.2000年11月:96-99
[55] De.Jong K A. An Analysis of the Behavior of Class of Genetic Adaptive System. Doctor Paper of University of Michigan, 1975, No.76-9381
[56]贾志欣,殷国富,罗阳,二维不规则零件排样问题的遗传算法求解,计算辅助设计与图形学学报,第14卷第5期2002年5月,pp467-470
[57] Ramesh Babu, A.; Ramesh Babu, N. A Generic Approach for Nesting of 2-DParts in 2-D Sheets Using Genetic and Heuristic Algorithms. Computer-Aided Design, 2001, 33(12): 879-891
[58]叶家玮,王磊,宋亚男.基于“板宽优先”约束的船体零件排样.机械,Vol.31, No.3:6-9
[59]粱黎明.群论与变换邻域搜索方法.华南理工大学硕士学位论文, 2002: 14
[60] Bennell,Julia A.; Dowsland,Kathryn A.; Dowsland,William B..The irregular cutting-stock problem——a new procedure for deriving the no-fit Polygon. Computers and Operations Research, 2001, 28(3): 271-287
[61]刘嘉敏,佟德刚等.临界多边形生成算法的改进[J].沈阳工业大学学报, 2005, 27(5),567-570
[62]施笑畏,何卫平,杨彭基,平面简单多边形平移干涉检测的最优算法,西北工业大学学报,1999, 17(4)
[63]贾志欣,殷国富,李红林,基于碰撞算法的排样系统的研究与应用,《模具工业》2002,No.3,总253:9-12
[64]王亮申,苏铁明,杨鑫华等.基于顶点的冲裁零件排样系统.机械科学与技术, 2002, 21(21):334-336
[65]胡华,蔡听,姚骏.任意连通多边形的靠接算法.计算机学报, 1995, 18(ll): 868-874
[66]胡华.多变形的旋转靠接算法.计算机研究与发展. 1998, 35(6): 567-571
[67]王峰,俞新陆.基于单一实体的轮廓表示及其水平线迭代切割的排样算法.机械科学与技术, 2001, 20(6): 940-946
[68] Kennedy J. Why Does it Need Velocity[A]? Proc of the IEEE Swarm Intelligence Symposium[C]. Pasadena USA,2005:38-44
[69]滕健,李滨慧,施洪生等.用神经网络解决二维不规则零件的排料问题.机械设计与制造工程, Vol.28,No.6:61-63
[70]赵治国,卢军,贾俐俐.遗传算法和碰撞算法混合求解冲裁件自动排样问题.工程图学学报, 2008年,No.1
[71]史俊友,冯美贵.二维不规则件优化排样的小生境遗传算法.工程设计学报, 14(2)
[72]顾振华,何援军,刘胡瑶.二维不规则图形排料CAD系统的设计.工程图学学报. 2008年2期
[73]张玉萍,黎新,陈淮莉,蒋寿伟.基于图的对称智能排样方法.计算机工程, 2008, 34(7)
[74]吴斯,曹炬.基于小生境免疫遗传算法的硅钢片优化排样.计算机工程, 2008, 34(10): 181-183
[75]郭文兰,张彤.矩形件排样优化的双向双原算法.哈尔滨理工大学学报, 2008, 13(2): 39-42
[76] S. Jakobs. On genetic algorithms for the packing of polygons[J]. Eurpean Journal of Operational Research. 1996(88):165-181
[77] Hopper E, Turton B. C. H. A genetic algorithm for a 2D industrial packing problem[J]. Computers and Industrial Engineering. 199(37):375-378
[78] [美]C.H.PAPADIMITRIOU and K.STEIGLITZ.刘振宏,蔡茂诚.Combinatorial Optimization Algorithms And Complexity.组合最优化算法和复杂性:清华大学出版社:p441
[79]凌少东.进化算法在排样问题上的应用.华中科技大学硕士论文. 2006
[80]方辉.大规模板材排料的分布式协同优化方法研究[D].成都:四川大学,2003
[81] Edmund Burke, Robert Hellier, Graham Kendall, Glenn Whitwell.A New Bottom-Left-Fill Heuristic Algorithm for the Two-Dimensional Irregular Packing Problem[J].Operations Research, 2006, 54(3): 587-601
[82] Glenn Whitwell. Novel Heuristic and Metaheuristic Approaches to Cutting and Packing. Doctor Paper of the University of Nottingham.2004.
[83] E.G. Birgin, F.N.C.Sobral. Minimizing the Object Dimensions in Circle and Sphere Packing Problems. October 12, 2006.
[84]宋晓霞,李勇.一种求解圆形下料问题的快速算法.微计算机信息(测控自动化). 2006, 22(5-1):261-263
[85]李文,梁昔明.基于混沌优化和最速下降法的一种混合算法.计算技术与自动化, 2003, 22(2): 12-14
[86]宋连超,朱建良,张彤.矩形件排样优化贪婪算法及系统开发.哈尔滨理工大学学报, 12(1): 29—35
[87]蒋兴波,吕肖庆,刘成城.一种用于矩形排样优化的改进遗传算法.计算机工程与应用. 2008, 44(22)
[88] Roger B G, Tom M C. A New Algorithm for the Minimal-area Convex EnclosureProblem[J]. European Journal of Operational Research,1995,84: 522-538
[89] Kennedy J. Dynamic-Probabilistic Particle Swarms[A]. Proc of the Genetic and Evolutionaary Computation Conference[C]. Washington,USA,2005:201-207
[90]宋亚男.二维排样系统的图形匹配、入排控制与碰靠算法研究.华南理工大学博士学位论文.2004年6月
[91] YananSong,Jiawei Ye,Feiqi Deng et.al. The Coding,Graphics-Matching,and Packing(nesting) of Arbttray Graphics Based on Bitmap. Proceedings of The Second International Conference on Machine Learning and Cybernetics[C].xi’an,2-5 November,2003:2936-2939
[92]李满江,孟祥旭,志强.矩形件和任意多边形排样问题的算法及应用.贵州工业大学学报(自然科学版), 2002, 31(4)
[93]孙友松,罗月参.冲裁件优化排样的顶点算法.锻压技术,1995年.N.o:423-25
[94]吉晓民,杨先海.冲裁件优化排样的最大截距法.西安理工大学学报, Vol.12,No.2:91-94
[95]蔡玉俊,尹新颖,李天佑,刘岩.冲裁件优化排样类多边形顶点算法的研究.锻压机械.1999年:6-8
[96]李勇,曹矩等.矩形件排样优化的十字线法[J].锻压装备与制造技术,2004,6,98-100
[97]宋连超.矩形件排样优化的最小余料删除法[J].哈尔滨理工大学学报,2006,11(5):10-13
[98]贾志欣,殷国富,罗阳等.矩形件排样的模拟退火算法求解[J].四川大学学报(工程科学版),2001,33(5):35-38
[99]陈学松,曹矩,方乃存.遗传模拟退火算法在矩形优化排样系统中的应用[J].锻压技术,2004(1):27-29
[100]陶献伟,王华昌,李志刚.基于填充算法的矩形件排料优化求解[J] .中国机械工程,2003,14(13):1104-1107
[101]李英华,周兆英,熊沈蜀等.二维几何排样问题分类编码的研究[J].机械科学与技术.2000,19(3):441-444
[102]贾志欣,殷国富,李红林.基于碰撞算法的排料系统的研究与应用[J].模具工业,2002 ,28(3) :9-12
[103]梁利东.船体板材排样优化算法研究与智能系统的设计.华南理工大学博士学位论文. 2009
[104]佟德刚.二维不规则形状排料算法研究与实现[D].沈阳工业大学硕士学位论文.2005,7
[105]曹月东.二维布局优化神经计算方法研究.[D].北京:北方交通大学,1999
[106]曹军,岳琪,张怡卓等.遗传神经网络在家具板材优化下料问题中的应用[J].森林工程,2003,19(1):36-37
[107]高尚.模拟退火算法中的退火策略研究[J].航空计算技术,2002, 32(4): 20-22
[108]王桂宾,周来水,邓冬梅.基于模拟退化算法的矩形件排样[J].中国制造业信息化,2006, 35 (15) :65-67,70
[109]宋亚男,叶家玮,邓飞其等.基于改进免疫遗传算法的矩形件排样.计算机工程与应用, 2004年第12期:22-24
[110]计华.一种基于四叉树结构的排料算法[J].计算机工程, 2003,29(9):80-82
[111]杨彩,史俊友,顾海明.基于遗传模拟退火算法的矩形件排样[J].青岛科技大学学报. 2004, 25(5): 452-456
[112]毛定山,崔先国等.简单多边形凸包的快速算法[J].工程图学学报, 2007, 6 : 96 -101
[113]洪灵,王耘.一种不规则零件排样的快速解码算法[J].计算机辅助设计与图形学学报,2005,17(11):2465-2470
[114]张维锦,张新系.任意多边形的面积计算及在造价分析中的应用[J].华东交通大学学报,2000, 17(1): 17-20
[115]刘胡瑶,何援军.基于重心NFP的二维不规则形状排样算法[J].中国机械工程, 2007, 18 (6) :723-726
[116] Coello Carlos A Coello, Cortes Nareli Cruz.Hybridizing A Genetic Algorithm with An Artificial Immune System for Global Optimization [J].Engineering Optimization.2004, 36(5):607-634
[117]潘中良,熊银根.一种基于小生境的遗传算法及其应用[J].中山大学报, 2001, 5(40): 46~51
[118]段玉波,任伟建,霍凤财等.一种新的免疫遗传算法及其应用[J].控制与决策,2005,20(10):1185-l188
[119] Milenkovic,Victor J.. Densest translational lattice packing of non-convex polygons. Computational Geometry, 2002, 22(1-3): 205-222
[120]李建武.遗传算法适应值曲面及遗传算法困难度分析.天津大学管理学院博士学位论文.2002年10月
[121] Edmund Burke, Robert Hellier.A New Bottom-Left-Fill Heuristic Algorithm for the Two-Dimensional Irregular Packing Problem[J].Operations Research.2006, 54(3):587-601
[2]贾志欣.面向发电设备制造的下料优化排样原理与关键技术.四川大学博士学位论文.2002
[3]杨威.板材排样优化的计算智能方法研究.四川大学硕士学位论文.2002
[4]张达科.服装纸样排版自动优化系统.华南理工大学硕士学位论文.2002
[5] Gomes,A.Miguel; Oliveira,Jose F.. A 2-exchange heuristic for nesting problems. European Journal of Operational Research, 2002, 141(2): 359-370
[6]宋佩华,蒋联源,欧启忠.基于离散粒子群优化算法求解矩形件排样问题.计算机应用与软件, 2008, 25(1):238—240
[7]马广昆,刘嘉敏,黄有群,岳勇,Malcolm Keech.一种有约束矩形排样问题的求解算法.沈阳工业大学学报, 2006, 28(4): 449—453
[8]贾志欣.排样问题的研究现状与趋势.计算机辅助设计与图形学学报, 2004, 16(7): 890—897
[9]白瑞斌.临界多边形法在二维不规则零件排样中的研究与实现.西北工业大学硕士学位论文.2002
[10]周石林.一维下料问题的研究.南京航空航天大学.硕士学位论文.2000
[11] Wei Liangliang, YeJiawei. Contrast of one-dimensional Cutting Algorithm. The 5th World Multiconference on Systemics,Cybernetics and Inofmratics Orlando,USA,2001.
[12] Schilling,Gordian; Georgiadis,Miehael C.. An algorithm for the determination of optimal cutting patterns. Computers and Operations Research, 2002, 29(8): 1041一1058.
[13] Zak,Eugene J.. Modeling multistage cutting stock problems. European Journal of Operational Research, 2002, 141(2): 313-327.
[14] Fayard,Didier;Zissimo Poulos,Vassilis,An approximation algorithm for solving unconstrained two-dimensional knapsack problems , European Journal of Operational Research, 1995, 84(3): 618一632
[15] Dell’Amico,Mauro; Martello,Silvano; Vigo,Daniele. A lower bound for the non-oriented two-dimensional bin packing problem. Discrete Applied Mathematics, 2002, 118(1-2):13-24
[16] Hopper,E.; Turton,B.C.H.. An empirical investigation of meta-heuristic and Heuristic algorithms for a 2D packing problem. European Joural of Operational Research, 2001, 128(1):34一57
[17] Wu,Yu-Liang;Huang,Wenqi; Lau,Siu-chung; Wong,C.K.; Young,Gilbert H..An effective quasi-human based heuristic for solving the rectangle packing problem. European Journal of Operational Research, 2002, 141(2): 341一358
[18] Lodi,Andrea; Martello,Silvano; Vigo,Daniele. Approximation algorithms for The oriented two-dimensional bin Packing Problem. European Journal of Operational Research, 1999, 112(1): 158-166
[19] Cung,Van-Dat; Hifi,Mhand; LeCun,Bertrand. Constrained two-dimensional Cutting stock problems a best-first branch-and-bound algorithm. International Transactions in Operational Research, 2000, 7(3): 185-210
[20] Alvarez-Valdes,Ramon; Parajon,Antonio; Tamarit. Jose’s Manuel,A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems. Computers and Operations Research, 2002, 29(7): 925-947
[21] KlemPous,Ryszard; Kotowski,Jerzy; Szlachcic,Ewa. Interactive proeedures in lagre-scale two-dimensional cutting stock problems. Jounralof Computational and Applied Mathematics, 1996, 66(1-2): 323-331
[22]毕艳丽,张宏国.几何图形的匹配识别.佳木斯大学学报(自然科学版), 2000年, 18(3):252-255
[23] Milenkovic,VictorJ.. Rotational polygon containment and minimum enclosure using only robust 2D constructions. Computational Geometry, 1999, 13(1): 3-19
[24] Theodoracatos,Vassilios E.; Grimsley,James L.. The optimal Packing of arbitrarily-shaped polygons using simulated annealing and polynomial-time cooling schedules. Computer Methods in Applied Mechanics and Engineering, 1995, 125(l-4): 53-70
[25]何春雄.智能计算方法讲义.华南理工大学数学科学学院, 2007
[26] Bennell,Julia A.; Dowsland,Kathryn A.; Dowsland,William B..The irregular cutting-stock problem——a new procedure for deriving the no-fit Polygon.Computers and Operations Research, 2001, 28(3): 271-287
[27]葛红,免疫算法及核聚类人工神经免疫网络的应用研究,华南理工大学博士学位论文,2003年5月,pp:34-37
[28]文军.基于CASE推理的排样算法.湖北民族学院学报(自然科学版),第18卷第2期,2000年5月.
[29]王凌.智能优化算法及其应用.清华大学出版社.2000年9月:1,10-11,12
[30]李明.智能优化排样技术研究.浙江大学博士学位论文. 2006
[31]张荣发.应用线性规划优化框架保持架落料排样工艺.锻压技术.1994年no.l:27-31
[32]范晓英,魏炜.应用线性规划法在钢筋下料中的应用.沈阳建筑工程学院学报, 1998, 14(2): 154一157
[33]张之燕.落料排样工艺的线性规划.模具工业,1994年No.12:12-14
[34] Goldberg DE. Genetic Algorithms in Search , Optimization and Machine Learning Reading,MA: Addison Wesley.1989
[35] Song Yanan,Ye Jiawei,Wei Liangliang,et.al..The Analysis,New Development and of Packing(Nesting),Symposium on the development of ship-building & ship-repairing Industry[C].2003,Guangzhou China,2003.3.21-22,:174-180
[36]伊登峰.多边形优化排样中小零件的填充算法[J].制造业信息化,2007, 12:83-85
[37] Vladimir N.Vapnik著.张学工译.统计学习理论的本质.清华大学出版社.2000年9月:123
[38]边肇棋,张学工.模式识别.清华大学出版社.1999年9月:4
[39] Chiu,S.,“Fuzzy Model Identification Based on Cluster Estimation,”Journal of Intelligent & Fuzzy Systems,1994, 2(3)
[40] Yager,R.andD.Filev,"Generation of Fuzzy Rules by Mountain Clustering," Journal of Intelligent & Fuzzy Systems,1994, 2(3): 209-219
[41]周永权,谢宁新.山峰-减法聚类神经元模型及学习算.广西科学院学报, Vol.18. No.4:148-154
[42]飞思科技产品研发中.matlba6.5辅助神经网络分析与设计..电子工业出版社.2003年l月:165-175
[43]闻新,周露,王丹力,熊晓英.matlab神经网络应用设计.科学出版社.2000: 271-295
[44]张立明.人工神经网络的模型及其应用.复旦大学出版社.1992年9月:127-148
[45] Guo,Guodong; Li,Stan Z.; Chan,Kap Luk. A neural network model with bounded-weights for Pattern classification. Computers and Operations Research, 2004, 31(9): 1411-1426
[46] Angulo,Cecilio; Parra,Xavier; Catala,Andreu. K-SVCR. A support vector machine for multi-class classification. Neurocomput ng, 2003, 55(l-2): 57-77
[47] Arenas-Gareia,J.; Perez-Cruz,F.. Multi-class support vector machines: a new approach. Acoustics, Speech and Signal Processing , 2003. Proceedings.(ICASSP’03).2003 IEEE International Conference on,Volume:2,6-10 April 2003:Ⅱ-781-4
[48] Franc,V.; Hlavac,V.. Multi-class support vector machine. Pattern Recognition, 2002. Proceedings. 16th International Conference , Volume:2 , 11-15 Aug. 2002:236-239
[49] Chao Yuan; Casasent,D.. Support vector machines for class representation and discrimination. Neural Networks,2003. Proceedings of the International Joint Conference on,Volume:2,20-24 July 2003:1611-1616
[50]莫鸿强.遗传算法搜索能力和编码方式研究.华南理工大学工学博士学位文.2001年4月
[51]王小平,曹立明.遗传算法——理论、应用与软件实现.西安交通大学出版2002年l月
[52]张文修,梁怡.遗传算法的数学基础.西安交通大学出版社.2001年4月
[53] [美]Zbigniew Michalewicz David B.Fogel著,曹宏庆,李艳,董红斌等。如何求解问题——现代启发式方法。中国水利水电出版社.2003年2月
[54]王正志,薄涛.进化计算.国防科技大学出版社.2000年11月:96-99
[55] De.Jong K A. An Analysis of the Behavior of Class of Genetic Adaptive System. Doctor Paper of University of Michigan, 1975, No.76-9381
[56]贾志欣,殷国富,罗阳,二维不规则零件排样问题的遗传算法求解,计算辅助设计与图形学学报,第14卷第5期2002年5月,pp467-470
[57] Ramesh Babu, A.; Ramesh Babu, N. A Generic Approach for Nesting of 2-DParts in 2-D Sheets Using Genetic and Heuristic Algorithms. Computer-Aided Design, 2001, 33(12): 879-891
[58]叶家玮,王磊,宋亚男.基于“板宽优先”约束的船体零件排样.机械,Vol.31, No.3:6-9
[59]粱黎明.群论与变换邻域搜索方法.华南理工大学硕士学位论文, 2002: 14
[60] Bennell,Julia A.; Dowsland,Kathryn A.; Dowsland,William B..The irregular cutting-stock problem——a new procedure for deriving the no-fit Polygon. Computers and Operations Research, 2001, 28(3): 271-287
[61]刘嘉敏,佟德刚等.临界多边形生成算法的改进[J].沈阳工业大学学报, 2005, 27(5),567-570
[62]施笑畏,何卫平,杨彭基,平面简单多边形平移干涉检测的最优算法,西北工业大学学报,1999, 17(4)
[63]贾志欣,殷国富,李红林,基于碰撞算法的排样系统的研究与应用,《模具工业》2002,No.3,总253:9-12
[64]王亮申,苏铁明,杨鑫华等.基于顶点的冲裁零件排样系统.机械科学与技术, 2002, 21(21):334-336
[65]胡华,蔡听,姚骏.任意连通多边形的靠接算法.计算机学报, 1995, 18(ll): 868-874
[66]胡华.多变形的旋转靠接算法.计算机研究与发展. 1998, 35(6): 567-571
[67]王峰,俞新陆.基于单一实体的轮廓表示及其水平线迭代切割的排样算法.机械科学与技术, 2001, 20(6): 940-946
[68] Kennedy J. Why Does it Need Velocity[A]? Proc of the IEEE Swarm Intelligence Symposium[C]. Pasadena USA,2005:38-44
[69]滕健,李滨慧,施洪生等.用神经网络解决二维不规则零件的排料问题.机械设计与制造工程, Vol.28,No.6:61-63
[70]赵治国,卢军,贾俐俐.遗传算法和碰撞算法混合求解冲裁件自动排样问题.工程图学学报, 2008年,No.1
[71]史俊友,冯美贵.二维不规则件优化排样的小生境遗传算法.工程设计学报, 14(2)
[72]顾振华,何援军,刘胡瑶.二维不规则图形排料CAD系统的设计.工程图学学报. 2008年2期
[73]张玉萍,黎新,陈淮莉,蒋寿伟.基于图的对称智能排样方法.计算机工程, 2008, 34(7)
[74]吴斯,曹炬.基于小生境免疫遗传算法的硅钢片优化排样.计算机工程, 2008, 34(10): 181-183
[75]郭文兰,张彤.矩形件排样优化的双向双原算法.哈尔滨理工大学学报, 2008, 13(2): 39-42
[76] S. Jakobs. On genetic algorithms for the packing of polygons[J]. Eurpean Journal of Operational Research. 1996(88):165-181
[77] Hopper E, Turton B. C. H. A genetic algorithm for a 2D industrial packing problem[J]. Computers and Industrial Engineering. 199(37):375-378
[78] [美]C.H.PAPADIMITRIOU and K.STEIGLITZ.刘振宏,蔡茂诚.Combinatorial Optimization Algorithms And Complexity.组合最优化算法和复杂性:清华大学出版社:p441
[79]凌少东.进化算法在排样问题上的应用.华中科技大学硕士论文. 2006
[80]方辉.大规模板材排料的分布式协同优化方法研究[D].成都:四川大学,2003
[81] Edmund Burke, Robert Hellier, Graham Kendall, Glenn Whitwell.A New Bottom-Left-Fill Heuristic Algorithm for the Two-Dimensional Irregular Packing Problem[J].Operations Research, 2006, 54(3): 587-601
[82] Glenn Whitwell. Novel Heuristic and Metaheuristic Approaches to Cutting and Packing. Doctor Paper of the University of Nottingham.2004.
[83] E.G. Birgin, F.N.C.Sobral. Minimizing the Object Dimensions in Circle and Sphere Packing Problems. October 12, 2006.
[84]宋晓霞,李勇.一种求解圆形下料问题的快速算法.微计算机信息(测控自动化). 2006, 22(5-1):261-263
[85]李文,梁昔明.基于混沌优化和最速下降法的一种混合算法.计算技术与自动化, 2003, 22(2): 12-14
[86]宋连超,朱建良,张彤.矩形件排样优化贪婪算法及系统开发.哈尔滨理工大学学报, 12(1): 29—35
[87]蒋兴波,吕肖庆,刘成城.一种用于矩形排样优化的改进遗传算法.计算机工程与应用. 2008, 44(22)
[88] Roger B G, Tom M C. A New Algorithm for the Minimal-area Convex EnclosureProblem[J]. European Journal of Operational Research,1995,84: 522-538
[89] Kennedy J. Dynamic-Probabilistic Particle Swarms[A]. Proc of the Genetic and Evolutionaary Computation Conference[C]. Washington,USA,2005:201-207
[90]宋亚男.二维排样系统的图形匹配、入排控制与碰靠算法研究.华南理工大学博士学位论文.2004年6月
[91] YananSong,Jiawei Ye,Feiqi Deng et.al. The Coding,Graphics-Matching,and Packing(nesting) of Arbttray Graphics Based on Bitmap. Proceedings of The Second International Conference on Machine Learning and Cybernetics[C].xi’an,2-5 November,2003:2936-2939
[92]李满江,孟祥旭,志强.矩形件和任意多边形排样问题的算法及应用.贵州工业大学学报(自然科学版), 2002, 31(4)
[93]孙友松,罗月参.冲裁件优化排样的顶点算法.锻压技术,1995年.N.o:423-25
[94]吉晓民,杨先海.冲裁件优化排样的最大截距法.西安理工大学学报, Vol.12,No.2:91-94
[95]蔡玉俊,尹新颖,李天佑,刘岩.冲裁件优化排样类多边形顶点算法的研究.锻压机械.1999年:6-8
[96]李勇,曹矩等.矩形件排样优化的十字线法[J].锻压装备与制造技术,2004,6,98-100
[97]宋连超.矩形件排样优化的最小余料删除法[J].哈尔滨理工大学学报,2006,11(5):10-13
[98]贾志欣,殷国富,罗阳等.矩形件排样的模拟退火算法求解[J].四川大学学报(工程科学版),2001,33(5):35-38
[99]陈学松,曹矩,方乃存.遗传模拟退火算法在矩形优化排样系统中的应用[J].锻压技术,2004(1):27-29
[100]陶献伟,王华昌,李志刚.基于填充算法的矩形件排料优化求解[J] .中国机械工程,2003,14(13):1104-1107
[101]李英华,周兆英,熊沈蜀等.二维几何排样问题分类编码的研究[J].机械科学与技术.2000,19(3):441-444
[102]贾志欣,殷国富,李红林.基于碰撞算法的排料系统的研究与应用[J].模具工业,2002 ,28(3) :9-12
[103]梁利东.船体板材排样优化算法研究与智能系统的设计.华南理工大学博士学位论文. 2009
[104]佟德刚.二维不规则形状排料算法研究与实现[D].沈阳工业大学硕士学位论文.2005,7
[105]曹月东.二维布局优化神经计算方法研究.[D].北京:北方交通大学,1999
[106]曹军,岳琪,张怡卓等.遗传神经网络在家具板材优化下料问题中的应用[J].森林工程,2003,19(1):36-37
[107]高尚.模拟退火算法中的退火策略研究[J].航空计算技术,2002, 32(4): 20-22
[108]王桂宾,周来水,邓冬梅.基于模拟退化算法的矩形件排样[J].中国制造业信息化,2006, 35 (15) :65-67,70
[109]宋亚男,叶家玮,邓飞其等.基于改进免疫遗传算法的矩形件排样.计算机工程与应用, 2004年第12期:22-24
[110]计华.一种基于四叉树结构的排料算法[J].计算机工程, 2003,29(9):80-82
[111]杨彩,史俊友,顾海明.基于遗传模拟退火算法的矩形件排样[J].青岛科技大学学报. 2004, 25(5): 452-456
[112]毛定山,崔先国等.简单多边形凸包的快速算法[J].工程图学学报, 2007, 6 : 96 -101
[113]洪灵,王耘.一种不规则零件排样的快速解码算法[J].计算机辅助设计与图形学学报,2005,17(11):2465-2470
[114]张维锦,张新系.任意多边形的面积计算及在造价分析中的应用[J].华东交通大学学报,2000, 17(1): 17-20
[115]刘胡瑶,何援军.基于重心NFP的二维不规则形状排样算法[J].中国机械工程, 2007, 18 (6) :723-726
[116] Coello Carlos A Coello, Cortes Nareli Cruz.Hybridizing A Genetic Algorithm with An Artificial Immune System for Global Optimization [J].Engineering Optimization.2004, 36(5):607-634
[117]潘中良,熊银根.一种基于小生境的遗传算法及其应用[J].中山大学报, 2001, 5(40): 46~51
[118]段玉波,任伟建,霍凤财等.一种新的免疫遗传算法及其应用[J].控制与决策,2005,20(10):1185-l188
[119] Milenkovic,Victor J.. Densest translational lattice packing of non-convex polygons. Computational Geometry, 2002, 22(1-3): 205-222
[120]李建武.遗传算法适应值曲面及遗传算法困难度分析.天津大学管理学院博士学位论文.2002年10月
[121] Edmund Burke, Robert Hellier.A New Bottom-Left-Fill Heuristic Algorithm for the Two-Dimensional Irregular Packing Problem[J].Operations Research.2006, 54(3):587-601