【作者】 李明；

【导师】 周泽魁；

【作者基本信息】 浙江大学 ， 控制科学与工程， 2006， 博士

【摘要】 计算机辅助优化排样问题就是将一系列形状各异的零件排放在给定的材料上,找出零件的最优排布,使得给定材料的利用率最高,以达到节约材料,提高效益的目的。从数学计算复杂性理论看,优化排样问题属于具有最高计算复杂性的NP完全问题,至今还无法找到解决该问题的有效多项式时间算法。传统的排样工作都是人工依靠经验进行的,时间长并且效果不理想。由于生产实际的需要,人们迫切需要利用现代科技来解决这一问题。智能优化算法作为现代信息技术,已被广泛应用于许多领域。本文以智能优化算法为基础,提出了几种用于解决优化排样问题的新方法,实验结果证明本文提出的方法是有效的。本文的主要工作和创新点如下: (1)针对矩形件排样问题,本文在建立其数学模型的基础上,将小生境遗传算法应用于计算机辅助排样领域,提出了一种改进的解码算法一高度调整法,将高度调整法和小生境遗传算法相结合,用于求解矩形件排样问题。该方法首先将矩形件的排样问题转化为便于优化求解的排列问题,然后应用小生境遗传算法的全局优化概率搜索能力进行优化求解,优化计算过程中应用高度调整法将排样序列转化为排样图。用该算法对文献中的两个算例进行了求解,取得了很好的排样结果。 (2)提出一种应用粒子群算法优化求解矩形件排样问题的方法。该方法对矩形件的排样位置直接进行编码,以零件左下角的位置坐标和零件的长和宽来确定零件的排样位置,然后用粒子群优化算法对整个解空间进行高效搜索,在进化计算过程中应用了自适应调整规则,最终可获得材料利用率很高的排样结果。排样实例表明,该优化排样算法是有效的,具有广泛的适应性。 (3)将模拟退火算法和粒子群算法相结合,提出了一种基于模拟退火的粒子群算法。并对其中的变异算法进行了改进,提高了算法的收敛速度和精度;对包络矩形求取算法进行了改进,减少了计算量,提高了算法的运算速更多还原

【Abstract】 The aim of the computer aided optimal layout of the parts with different shapes is to find the arrangement of parts and producing the least waste. The problem of optimal layout belongs to the NP-complete problem with tiptop calculate complexity, and cannot find the effective polynomial algorithm up to the present. Conventional layout works all adopt manual operation that have many shortcomings such as low yield, inefficient and long time consuming. People cry for a solution by the modern science and technology because of the need of production. Intelligent optimization algorithms have been used extensively in many domains. In this paper, the application of intelligent optimization algorithms in optimal layout was more investigated. Several new methods were proposed for the problem of optimal layout. The main works and innovation points are listed as follows:(1) In order to solve the problem of rectangular parts optimal layout with dynamic constraints, based on the mathematical model, a novel rectangular optimal layout method is proposed based on novel decoding algorithm - Height Adjustment algorithm (HAA) and niche genetic algorithm (NGA). The problem of rectangular optimal layout can be translated into optimization problem in the field of permutation problem, and then the NGA is used to search the solution space efficiently in order to find the optimal solution of the layout. HAA is used to decode permutation of rectangles to packing pattern during the procedure of optimization. The feasibility of the proposed method is demonstrated by two numerical examples.(2) A novel rectangular optimal layout method using particle swarm optimization (PSO) is proposed. The method coding directly with the positions of the rectangles, determining the packing position of parts by using the left-lower corneal position coordinate, width and length of the parts, and then the PSO with the self-adaptive modulate regulation is used to search the solution space efficientlyin order to find the optimal solution of the layout. The availability of the proposed method is demonstrated by the layout example.(3) A novel particle swarm optimization algorithm based on the simulated annealing algorithm (PSOSA) is presented. The crossover operation and cauchy mutation operation were used to enhance the convergence performance and speed of the algorithm. The proposed algorithm was used to solve the packing problem of two-dimensional irregular parts. Firstly, the proposed method converts the packing problem of two-dimensional irregular parts into rectangular parts packing problem by calculating the surrounding rectangle of irregular parts. Secondly, the proposed algorithm was used to search for the optimal solution of the layout. The strategy of self-adaptive modulation is used to adjust the layout position of each rectangular part during the procedure of optimization. Solutions of two numerical examples show the effectiveness of the proposed algorithm.(4) A novel two-dimensional irregular parts packing method using No Fit Polygon (NFP) and horizontal line scan algorithm is presented. Aiming at the contour of the packing parts, the methods to gain the NFP are discussed step by step, from two convex polygons, one convex polygon and one concave polygon to two concave polygons. And then the polygon compose algorithm, polygon area algorithm and horizontal line scan algorithm were combined with the NFP to solve the problem of two-dimensional irregular parts packing.(5) The design of computer aided optimal layout system is proposed. The demand, the basic function and the module of the layout system are discussed.更多还原