基于动作空间求解二维矩形Packing问题的高效算法?

对于二维矩形Packing这一典型的NP难度问题,在黄文奇等人提出的拟人型穴度算法的基础上,通过定义动作空间来简化对不同放入动作的评价,使穴度的计算时间明显缩短,从而使算法能够快速地得到空间利用率较高的布局图案。实验测试了Hopper和Turton提出的21个著名的二维矩形Packing问题的实例。改进的算法对其中的每一个实例都得到了空间利用率为100%的最优布局,且在普通PC机上的平均计算时间未超过7分钟。实验结果表明,基于动作空间对拟人型穴度算法所进行的改进是明显而有效的。     

基于动作空间求解二维矩形Packing 问题的高效算法

对于二维矩形Packing这一典型的NP难度问题,在黄文奇等人提出的拟人型穴度算法的基础上,通过定义动作空间来简化对不同放入动作的评价,使穴度的计算时间明显缩短,从而使算法能够快速地得到空间利用率较高的布局图案.实验测试了Hopper和Turton提出的21个著名的二维矩形Packing问题的实例.改进的算法对其中的每一个实例都得到了空间利用率为100％的最优布局,且在普通PC机上的平均计算时间未超过7分钟.实验结果表明,基于动作空间对拟人型穴度算法所进行的改进是明显而有效的.     

基于动作空间的三维装箱问题的确定性高效率求解算法

三维装箱问题要求将有限个三维矩形物体尽可能多地装入到一个三维矩形箱子中,使得箱子的填充率即体积利用率最大.在求解三维装箱问题的穴度算法的基础之上,进一步做了以下改进:(1)将当前剩余空间中可能放入的每个体积最大的三维矩形虚拟物体所对应的空间定义为动作空间,在动作空间内放入物体并使穴度的定义体现放入物体与动作空间的吻合程度;(2)在物体放入位置的选择上直接体现"金角银边草肚皮"的思想,每一步只选择最靠近箱子边缘的一个动作空间来装载物体;(3)结合捆绑策略,将形状大小相同的物体捆绑为一个较大的矩形块进行放入,对捆绑块形状大小的选择为在不超出动作空间的前提下尽量用物体填满该空间的两至三个维度.实验结果表明,改进后的穴度算法在付出很少的开销代价的情况下显著地提高了箱子的填充率.     

基于穴度的三维时空优化问题的贪心调度算法

研究了基于二维矩形Packing的三维时空优化问题,即对给定的一个任意宽、高的大矩形框和有限个有连续加工时间要求的任意宽、高的小矩形块,如何安排每个小矩形块的入框时刻及其出框前每一时刻的位置和方向,使得所有小矩形块的总加工时间即总调度长度makespan最短。与经典布局问题的不同之处在于,各矩形块在框内可随时间的绵延而改变其位置和方向,从而能更充分地利用矩形框的空间。基于实角与实占角动作的定义,设计了求解其子问题二维矩形Packing问题的增强穴度算法。然后,每步迭代优先考虑剩余加工时间长的矩形块,提出了求解此问题的贪心穴度调度算法(caving-degree based greedy scheduling algorithm,CGSA)。作为比较,同时设计了矩形块在框内不可随时间移动的将时间简单类比为空间的对应Packing问题的调度算法CGSA′。对于实验中提出的满足非闸断模式的4个小型算例,它们在原问题上的最优调度长度为2,但若将时间简单地类比为空间,即矩形块放入框内后不可随时间移动其方位,则其最优调度长度为3。实验表明,算法CGSA在这4个非闸断算例上均得到了最优调度。进一步地研究出满足闸断模式的21组共210个自动生成算例,通过实验验证了算法CGSA的最优解的数目明显多于CGSA′,且CGSA的平均调度长度明显短于CGSA′。     

求解矩形和圆形装填问题的最大穴度算法

在超大规模集成电路设计，裁缝裁剪布料，玻璃切割等工作中提出了矩形和圆形装填问题，即把不同大小的矩形块和圆饼装入一个矩形容器中，以最大化容器的面积利用率为优化目标。对这一问题，可采用模拟退火，遗传算法等国际流行算法进行求解，但这些方法计算时间较长，计算结果的优度也不甚理想。利用人类的智慧和经验，提出了一种求解此问题的最大穴度算法。并对3个随机生成的测试实例进行了实算测试。所得结果的平均面积利用率为90．80％，平均计算时阊为8．38s。测试结果表明，算法对求解矩形和圆形装填问题是行之有效的。     

基于CURE聚类算法的静态R树构建方法

R树索引结构在空间对象查询和复杂空间关系查询方面具有重要作用。传统空间索引结构R树是动态生成的,树的结构是根据连续插入算法实现的,通过分裂子节点直至生成R树的根节点。动态生成算法会导致R树节点最小外包矩形之间的大量重叠,影响空间查询效率,且空间利用率不高。为了弥补动态生成R树的不足,提出了基于CURE算法的静态R树生成方法,给出CU_RHbuilt建树算法,该算法不仅能有效地处理海量数据,识别任何形状的簇,减少矩形重叠度,而且采用划分技术可较大程度地减小计算代价,空间利用率较高。进一步提出了基于CURE算法的R树节点分裂方法。理论研究与实验表明,所提方法具有较高的查询效率。     

基于改进ESLA算法的可重构资源管理

针对动态可重构系统的空闲资源管理问题,改进基于最大空闲矩形的增强型扫描线算法(ESLA),采用一维数组作为辅助空间,同时搜索有效宽度与最大空闲矩形。改进算法能快速计算出可重构系统在运行过程中的所有最大空闲矩形,实现任务间资源的合理分配。实验结果表明,改进算法能减少运行时间开销和存储空间代价,提高可重构系统的资源利用率。     

求解长方体Packing问题的高效算法

对典型的NP难度问题--著名的长方体Packing问题,通过观察体会人类几千年来在砌石头下围棋等活动中形成的经验和智慧,受到谚语"金角银边草肚皮"的启发,并将它发展提高到"价值最高钻石穴",提出了一种最大穴度的占角动作优先处理的拟人算法.计算了Loh和Nee提出的15个代表性的算例,算法在合理的时间内得出了高空间利用率的布局,其精度达到了国际先进的纪录.     

基于差别矩阵的完备属性约简算法

基于差别矩阵思想的属性约简算法需要求出决策表的差别矩阵,然而差别矩阵的求取不但费时而且占用大量的存储空间。为此,提出一种基于差别矩阵中非空对象个数的改进属性约简算法。在利用差别矩阵思想的同时不生成差别矩阵,并给出属性重要度的定义及其快速计算公式,只需要 和 就能计算出属性重要度。实例分析证明,该算法能节省计算时间,求出最小属性约简。     

求解长方体Packing 问题的捆绑穴度算法

在穴度方法的基础上结合捆绑策略,为三维欧氏空间中长方体Packing问题的求解提供了一种高效的启发式算法.试算了由Loh和Nee于1992年提出的15个经典算例,对其中的困难算例LN2,取得了98.2%的空间利用率,比目前的最好纪录高1.6个百分点;对另一个困难算例LN6,取得了96.2%的空间利用率,与目前的最好纪录持平;对其他13个较为容易的算例均取得了最优的布局,与目前的最好纪录持平.总体而言,15个算例的平均空间利用率为70.96%,在整体空间利用率上达到了较好的效果.     

A caving degree based flake arrangement approach for the container loading problem

A caving degree based flake arrangement (CDFA) approach for the NP-hard container loading problem is presented in this paper. Based on the caving degree approach, CDFA binds items in the same size into a larger flake whose binding number is 1 in one of its three dimensions, and then it tries to pack the flake into a corner nearest to the eight vertices of the container. Then, caving degree is redefined to evaluate different placements of flakes, such that an action is selected whose packing flake is as compact and close as possible with other flakes already in (the six surfaces of the container can be regarded as six special flakes). CDFA is extensively tested over two sets of famous benchmarks: 15 LN instances and 1500 BR instances. Experimental results show the high performance of this new approach. Especially for the LN set, CDFA improved current highest volume utilization by 1.3% and 0.5% for two difficult instances LN2 and LN6 respectively; at the same time it got optimal layouts for the other 13 instances, equalling current best records. This breaks current best record created and held by Bortfeldt and Gehring since 1998. Besides, CDFA achieved the second highest average volume utilization among several top efficient algorithms for the BR set.     

求解二维矩形Packing面积最小化问题的动态归约算法

二维矩形Packing 面积最小化问题(rectangle packing area minimization problem,简称RPAMP)是具有NP难度的高复杂度的布局优化问题,也是大规模集成电路设计中floorplanning 问题的一个核心问题.通过动态构造矩形框的宽和高,将求解一个RPAMP 转化为求解一组二维矩形Packing 判定问题(rectangle packing decision problem,简称RPDP).在求解RPDP 的最大适配度算法的基础上,进一步考虑了当前动作对全局紧凑性的影响,评估了当前动作对局部空间的损害程度,设计了求解RPDP 的最小损害度算法.然后,结合矩形框宽、高的动态构造方法,设计得到求解RPAMP 的最终算法.对15 个相关的RPAMP 算例(包括著名的MCNC 算例和GSRC 算例)进行了测试.更新了其中9 个算例的最好记录,另有2 个与当前的最好记录持平.得到了98.50%的平均填充率,将国内外文献中已见报道的最高平均填充率提高了0.85%.     

An action-space-based global optimization algorithm for packing circles into a square container

This paper proposes an action-space-based global optimization (ASGO) approach for the problem of packing unequal circles into a square container such that the size of the square is minimized. Starting from several random configurations, ASGO runs the following potential descent method and basin-hopping strategy iteratively. It finds configurations with the local minimum potential energy by the limited-memory BFGS (LBFGS) algorithm, then selects the circular items having the most deformations and moves them to some large vacant space or randomly chosen vacant space. By adapting the action space defined for the rectangular packing problem, we approximate each circular item as a rectangular item, thus making it much easier to find comparatively larger vacant spaces for any given configuration. The tabu strategy is used to prevent cycling and enhance the diversification during the search procedure. Several other strategies, such as swapping two similar circles or swapping two circles in different quadrants in the container, are combined to increase the diversity of the configurations. We compare the performance of ASGO on 68 benchmark instances at the Packomania website with the state-of-the-art results. ASGO obtains configurations with smaller square containers on 63 instances; at the same time it matches or approaches the current best results on the other five instances.     

Design of efficient packing system using genetic algorithm based on hyper heuristic approach

In practice the maximum usage of container space arises in many applications which is one of the crucial economical requirements that have a wide impact on good transportation. A huge amount of monetary infrastructure is spent by companies on packing and transportation. This study recommends that there exists a scope for further optimization which if implemented can lead to huge saving. In this paper, we propose a new hyper heuristic approach which automates the design process for packing of two dimensional rectangular blocks. The paper contributes to the literature by introducing a new search technique where genetic algorithm is coupled with the hyper heuristic to get the optimal or sub optimal solution at an acceptable rate. The results obtained show the benefits of hyper-heuristic over traditional one when compared statistically on large benchmark dataset at the 5% level of significance. Improvements on the solution quality with high filling rate up to 99% are observed on benchmark instances.     

圆形件卷材排样问题的一种定序定位算法

圆形件卷材排样问题是指将一组不同半径的圆形件互不重叠的排放在宽度指定的 卷材上,使得占据的卷材长度最小。针对该问题提出一种定序定位启发式优化算法。设计基于 最大穴度的定位算法,对于每个特定排样序列,计算待排样圆形件在当前布局的所有可行放置 位置的穴度,选择穴度最高的一个位置放置圆形件;更新当前布局,继续排放剩余圆形件,直 到所有圆形件均排放进卷材为止。采用遗传算法对排样序列进行遗传进化得到多种不同的排样 方案,选择耗费卷材长度最小的一种排样方案作为最终解。实验结果表明,本文算法排样方案 耗费卷材长度较小,且算法计算时间相对合理。     

一种基于二叉树结构表达的矩形物体布局的启发式方法

本文提出了一种利用二叉树结构表达矩形物体布局状态空间的方法．通过将布局空间依次分割，每次放入相对于当前布局空间来说是满足特定条件的最优布局块，并将该布局块定位于当前布局空间的左上角来完成不同大小矩形物体的布局方案的确定．通过调整调序因子ＫＡ和ＫＢ的值，可得到满足不同要求的优化布局方案．同时，所得布局方案均满足工业上一刀切的要求．实验结果证明了该算法的灵活性和有效性．     

A new heuristic algorithm for cuboids packing with no orientation constraints

The three-dimensional cuboids packing is NP-hard and finds many applications in the transportation industry. The problem is to pack a subset of cuboid boxes into a big cuboid container such that the total volume of the packed boxes is maximized. The boxes have no orientation constraints, i.e. they can be rotated by 90^°${90}^{°}$ in any direction. A new heuristic algorithm is presented that defines a conception of caving degree to judge how close a packing box is to those boxes already packed into the container, and always chooses a packing with the largest caving degree to do. The performance is evaluated on all the 47 related benchmarks from the OR-Library. Experiments on a personal computer show a high average volume utilization of 94.6% with an average computation time of 23 min for the strengthened A1 algorithm, which improves current best records by 3.6%. In addition, the top-10 A2 algorithm achieved an average volume utilization of 91.9% with an average computation time of 55 s, which also got higher utilization than current best records reported in the literature.