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

Question

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

问题描述：

目标：通过改变部件放置的顺序，使无限长的板材长度（宽度为常数）最小化。

我面临的问题：

所得到的输出结果是离散的（只有15个可能的利用率％），而不是连续的（因为存在11！* 2 ^ 11种可能的解->我们期望结果是连续的）。

模拟退火算法的路径 - MATLAB输出：

与此相同的SA代码生成的预期结果：

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

利用率从最大长度计算：

我假设如果我按如下方式更改计算利用率%的方式，我可以解决这个问题。

利用率从边缘切割长度计算：

尽管我已经找到了如何解决这个问题，但我不知道如何找到边界切割面积以找到效率。有人有找到红线下面积的方法吗？我需要避免使用“图像处理工具箱”。

FYI：

矩形存储为从每个矩形的左下位置到原点的x，y距离。我有相应的长度，宽度值在另一个变量中。

- Santhan Salai

Answer 1

I figured it out, 如何找到“Boundary-Cut Area”而不使用“Image Processing Toolbox”。 我想将此作为答案发布，以帮助其他遇到类似问题的人。欢迎更好的解决方案。

放置零件的逻辑：从左到右放置零件，直到最右端，然后移到左端并将下一个零件放置在上一个零件上，向右移动等等。

找到边界切割区域的解决方案：我只需创建一个单维矩阵，其长度等于纸张的宽度（在上面的屏幕截图中-> 200）。默认情况下，我将它们的值设置为零。

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);

边界切割利用率的一个例子：。

- Santhan Salai