摘要
矩形件排样是一个平面二维优化布局的问题,由于其众多的约束条件和计算上的复杂性,在短时间内求其最优解相当困难,属于典型的NP完全问题。针对矩形件排样问题,本文采取一种改进的最低水平线搜索算法,通过判断排样中产生的废弃空闲区域的位置关系,对邻接的空闲区域进行有效的合并,并结合分布估计算法求解矩形件排样优化问题。最后,通过模拟实验,采用本文算法求解后矩形板材的利用率为93.75%,充分体现了本文算法的有效性。
Rectangular packing is a planar layout optimization problem and NP-complete problem, It is difficult to find its exact global optimum in a short time because of the numerous constraints and the high complexity of computation. Facing the problem of rectangular packing ,This paper took the improved Lowest Horizontal Search Algorithm and the Estimation of Distribution Algorithms （EDAs） to solve the rectangular packing problem, which make full use of the space area by merging adjacent free area based on the position relationship of wasted free area which produced by rectangular packing. Finally, with the simulation experiment, utilization ratio of rectangular plate is 93.75% with the algorithm of this paper, which proved the effectiveness of the algorithm.
作者
马康
高尚
MA Kang GAO Shang(School of Computer Science and Engineering ,Jiangsu University of Science and Technology ,Zhenjiang 212003, China)
出处
《电子设计工程》
2017年第2期49-54,共6页
Electronic Design Engineering
