矩形嵌套 - 使用模拟退火收敛到最优解

Question

我正在使用 模拟退火 解决矩形嵌套问题。我能够得到很好的结果，但我得到的解决方案是离散的。即使是全局最优也不总能获得。

问题描述：

Objective - 通过更改零件放置的顺序来最小化无限sheet（宽度不变）的长度。

我面临的问题：

我得到的输出结果是离散的（只有 15 个可能的利用率 %）而不是模拟的（因为有 11！*2^11 个可能的解决方案 -> 我们希望结果是模拟的）

SA 行进的路径 - MATLAB 输出

我期望的结果 使用我用于此问题的相同 SA 代码为不同的问题生成

从下图中可以看出我得到 DISCRETE 输出的原因。可能有很多序列给出相同长度 55 的可能性。

根据最大长度计算的效率

我想如果我像这样改变计算利用率的方式就可以解决问题。

效率计算自边界切割长度

尽管我想出了解决问题的方法，但我不知道如何找到边界切割区域以找到效率。有人有办法找到红线下的区域吗？我需要避免使用 Image Processing Toolbox

仅供参考： 矩形存储为左下角位置与每个矩形原点的 x,y 距离。我在另一个变量中有相应的长度，宽度值。

Answer 1

我想通了，如何使用 Image Processing Toolbox 找到 边界切割区域 而无需 。我想 post 这作为其他有类似问题的答案。也欢迎更好的解决方案。

零件放置逻辑：

放置 Left-> Right 的零件，直到 Right most end ，然后转到 Left end 并将下一个零件放在上一个零件上，移动 Right 等等.

寻找边界切割区域的解决方案：

我只是创建了一个单维矩阵，其长度等于 sheet 的宽度（在上面的屏幕截图中 -> 200）默认情况下，我将它们的值设置为 zero。

boundaryLength = zeros(sheetWidth+1,1);   
% sheetWidth+1 because matlab starts from the index 1 while my range is from 0-200

每次我放置一个零件时，我都会分配值的范围，即从其左下位置的 xDist 到右下位置的 xDist 到 yDist 的值顶线。

for i = 1:numberOfParts
    boundaryLength(xDist(i)+1:xDist(i)+width(Index(i))) = yDist(i)+ height(Index(i));
end

% Index is the order in which i place the part. 
% Here in the above screenshot, my index value is [8, 2, 4, 11, 7, 5, 6, 10, 1, 9, 3]

现在我找到了整个sheet宽度中每个像素的最大占用长度。要找到面积，我需要找到向量的总和 boundaryLength

boundaryArea = sum(boundaryLength);

Boundary-Cut Utilization 举个例子：

矩形嵌套 - 使用模拟退火收敛到最优解

Rectangular Nesting - Convergence to optimal solution using Simulated Annealing

optimization

matlab

geometry

computational-geometry

geometry-surface