Page 28 - 《软件学报》2021年第12期

3692 Journal of Software 软件学报 Vol.32, No.12, December 2021

8 randomly generated h,h∈[dmin g ,dmax g ]
9 rects.add([w,h])
10 for 0→nt do
11 rect_list[i]=rects[i%nt]
12 return rect_list
Wang 和 Valenzela [31] 生成数据的算法思路是: 通过将一个大的矩形不断地进行分割,分割成满足一定面积
比(γ)和宽高比(ρ)的小矩形.这种思路生成的数据集是属于零浪费类型的,装箱的最优解由输入参数控制.具体
的算法流程如算法 3.2 所示.该算法输入的参数有 4 个:n 表示生成小矩形个数,H 表示待分割矩形的高度,γ和ρ
控制生成矩形的面积比和宽高比.算法一开始根据输入的参数随机选择宽度 W,然后在第 3 行~第 18 行进行 n−1
次切割,生成 n 个矩形.首先,随机选择满足面积小于 2m/γ的矩形进行切割,m 是矩形序列中最大矩形的面积.在第
7 行~第 13 行,根据不同的条件选择切割方向.第 13 行~第 18 行根据不同的切割方向,在可切割的范围内随机选
择切割点,并把生成的两个新矩形加入列表中.
算法 3.2. 数据生成算法 2.
Input:
H: The height of the rectangle to be divided;
n: thenumber of rectangles;
γ: the area ratio,γ≥2;
ρ: the aspect ratio,ρ≥2;
Output:
rect_list.
1 randomly generated W,W∈[2H/ρ,ρH/2]
2 rect_list=[[W,H]]
3 for 0→n-1 do
4 m=the area of the largest rectangle in rect_list
5 randomly selected rectangle R from rect_list,and the area of R satisfies S R >2m/γ
6 delete R from rect_list // randomly select the slicing direction
7 if 2R.h/ρ≤R.w≤ρR.h/2 then
8 randomly select horizontal or vertical slicing
9 else if 2R.w/ρ≤R.h≤2ρR.w then
10 horizontal slicing
11 else if 2R.h/ρ≤R.w≤2ρR.h then
12 vertical slicing // randomly select the slicing position
13 if horizontal slicing then
⎡ ⎛ . Rh R .w Rh ⎞ . ⎛ . R w m ⎞ ⎤
−
14 randomly selected y y ∈ , min ρ ⎜ Rw , ⎟ ,max ⎜ , .R h ρ − ⎢ Rw ⎟ ⎥
. ,
. ,
⎣ ⎝ ρ 2 ⎠ ρ γ ⎝ . R h ⎠ ⎦
15 rect_list.add([R.w,y]),rect_list.add([R.w,R.h-y])
16 if vertical slicing then
⎡ ⎛ . R h Rw Rw ⎞ − . . ⎛ . R h m ⎞ ⎤
. ,
17 randomly selected ,x∈ ⎢ x min ρ ⎜ Rh , ⎟ ,max ⎜ , .R w ρ − , . R h ⎟ ⎥
⎣ ⎝ ρ 2 ⎠ ρ γ ⎝ . R h ⎠ ⎦
18 rect_list.add([x,R.h]),rect_list.add([R.w−x,R.h])
19 return rect_list
本文使用算法 3.1 和算法 3.2 共生成 1 000 000 组的数据用于训练模型,共 3 种矩形块数:(1) 矩形块数为 200