论文部分内容阅读
研究二维矩形布局优化问题,将多个不同重量和尺寸的矩形目标填充到一个圆形容器中,要求给出最小的容器半径,并且系统保持平衡.目前的文献多采用局部搜索方法,但布局质量有待提高.文中设计一种构造式方法——定位法.其基本思想是将一个矩形围绕另外一个已经确定位置的矩形作为参照进行部署.由于围绕着参照矩形部署时只考虑有限个可布局位置,故定位法具有多项式时间复杂性.定位法可能得到较好的布局,但其质量受到布局顺序的影响较大,因此文中提出一种基于遗传算法的布局顺序寻优算法,其中遗传算法的交叉算子和变异算子经过特别的设计,使得遗传的下一代能继续作为布局顺序.在具有大规模测试用例的测试集上的计算结果表明,该布局方法比局部搜索方法有更优良的计算性能.
Research on two-dimensional rectangular layout optimization problem, a number of different weights and sizes of rectangular objects filled into a circular container, requiring a minimum container radius, and the system to maintain balance.The current literature mostly use the local search method, but the layout The quality needs to be improved.In this paper, we design a method of construction-positioning method, the basic idea is to deploy a rectangle around another already-determined rectangle as a reference.As only a limited number of layout locations , So positioning method has the polynomial time complexity.Positioning method may get a better layout, but its quality is greatly affected by the order of layout.Therefore, a layout algorithm based on genetic algorithm is proposed, in which the intersection of genetic algorithm Operators and mutation operators are specifically designed so that the next generation of inheritance can continue to be laid out in order. The computational results on a test set with large test cases show that the layout method has better computational performance than the local search method .