二维矩形块布局的交叉熵方法实现

A Cross-Entropy Method for Two-DimensionalPacking Problem with Rectangle Pieces

给定一个小矩形块集和一个固定宽度而高度变化的大矩形的二维布局问题,就是将这矩形集中的所有矩形正交布置于这个大矩形中,并且保证矩形块之间不发生重叠,目的就是使得布局后这个大矩形块的高度最小.本文提出通过DROP或DROPF(DROP FILL)的启发式解码策略与交叉熵算法相结合求解该类问题.试验结果显示,算法稳定有效,较经典元启发式算法在提高空间利用率上有较大提高.

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.