我正在使用模拟退火 解决矩形嵌套问题。我能够得到很好的结果,但我得到的解决方案是离散的。即使是全局最优也不一定总能获得。
问题描述:
目标 - 通过改变放置零件的顺序来最小化无限薄板的长度(宽度不变)。
我面临的问题:
我得到的输出结果是离散的(只有 15 个可能的利用率 %)而不是模拟的(因为有 11!*2^11 个可能的解决方案 -> 我们希望结果是模拟的)
SA 行进的路径 - MATLAB 输出
我期望的结果 使用我用于此问题的相同 SA 代码针对不同的问题生成
从下图中可以看出我得到 DISCRETE 输出的原因。给出相同长度 55 的序列可能有很多可能性。
效率根据最大长度计算
我想如果我像这样改变计算利用率百分比的方式就可以解决问题。
效率根据边界切割长度计算
尽管我想出了解决问题的方法,但我不知道如何找到 Boundary Cut AREA 才能找到效率。有人有办法找到红线下的区域吗?我需要避免使用 Image Processing Toolbox
仅供引用: 矩形存储为左下角位置与每个矩形原点的 x,y 距离。我在另一个变量中有相应的长度,宽度值。
最佳答案
我想通了,如何找到 Boundary-Cut Area 而无需 使用 Image Processing Toolbox
。我想将此发布为其他有类似问题的人的答案。也欢迎更好的解决方案。
零件放置逻辑:
从Left-> Right
放置零件,直到Right most end
,然后转到Left end
并将下一个零件放在上面上一部分,向右移动等。
寻找边界切割区域的解决方案:
我只是创建了一个单维矩阵,其长度等于工作表的宽度(在上面的屏幕截图中 -> 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);
Boundary-Cut Utilization 举个例子:
关于matlab - 矩形嵌套 - 使用模拟退火收敛到最优解,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29231658/