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

Question

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

问题描述：

目标 - 通过改变零件放置的顺序来最小化无限片材的长度（宽度恒定）。

我面临的问题：

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

SA 行驶的路径 - MATLAB 输出

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

我得到离散输出的原因可以从下图中看出。具有相同长度 55 的序列可能有多种可能性。

效率根据最大长度计算

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

效率根据边界切割长度计算

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

Image Processing Toolbox

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

Answer 1

我想通了，如何使用Image Processing Toolbox找到边界切割区域

没有

。我想将此发布为其他有类似问题的人的答案。也欢迎更好的解决方案。

放置零件的逻辑：

放置从

Left-> Right

开始的零件，直到

Right most end

，然后转到

Left end

并将下一个零件放在上一个零件上，移动

Right

，依此类推。

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

我只是创建一个单维矩阵，其长度等于纸张的宽度（在上面的屏幕截图中 -> 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]

现在我已经找到了整个纸张宽度上每个像素的最大占用长度。要找到面积，我需要找到向量的总和

boundaryLength

boundaryArea = sum(boundaryLength);

边界切割利用率为例：

Answer 2

我可以看看您用于解决此问题的代码吗？我仍在弄清楚模拟退火是如何工作的。