二维矩形块布局的交叉熵方法实现 |
| |
引用本文: | 吕盛坪,陆一平,查建中,吕胜祥.二维矩形块布局的交叉熵方法实现[J].北方交通大学学报,2009(2):39-43. |
| |
作者姓名: | 吕盛坪 陆一平 查建中 吕胜祥 |
| |
作者单位: | 北京交通大学机械与电子控制工程学院,北京100044 |
| |
基金项目: | 河北省自然科学基金资助项目(F20060003040);北京交通大学科技基金资助项目(2006XZ011) |
| |
摘 要: | 给定一个小矩形块集和一个固定宽度而高度变化的大矩形的二维布局问题,就是将这矩形集中的所有矩形正交布置于这个大矩形中,并且保证矩形块之间不发生重叠,目的就是使得布局后这个大矩形块的高度最小.本文提出通过DROP或DROPF(DROP FILL)的启发式解码策略与交叉熵算法相结合求解该类问题.试验结果显示,算法稳定有效,较经典元启发式算法在提高空间利用率上有较大提高.
|
关 键 词: | 二维矩形块布局问题 交叉熵 DROP DROPF |
A Cross-Entropy Method for Two-Dimensional Packing Problem with Rectangle Pieces |
| |
Institution: | LU Shengping, LU Yiping, ZHA Jianzhong, LU Shengxiang (School of Mechanical and Electronic Control Engineering, Beijing Jiaotong University, Beijing 100044, China) |
| |
Abstract: | Given a set of rectangular pieces and an object of fixed width and variable height, the two-dimensional packing problem consists of orthogonally placing all the pieces within the object, without overlapping, so that the overall height of the layout is minimized. This paper proposes a new algorithm by combining the DROP or DROPF (DROP FILL) heuristic decoder policy into the Cross-Entropy to solve the problem. The experiment results demonstrated that the algorithm is stable and fairly efficient. And it improves the occupation rate comparing with the classical meta-heuristic algorithm. |
| |
Keywords: | 2D-R-ODP cross-entropy(CE) DROP DROPF |
本文献已被 维普 等数据库收录! |
|