矩形嵌套 - 使用模拟退火收敛到最佳解决方案 [英] Rectangular Nesting - Convergence to optimal solution using Simulated Annealing

问题描述

对于矩形嵌套问题，我正在使用模拟退火。我能够获得好的结果，但是我得到的解决方案是DISCRETE。即使是全球最佳并不总是获得。

问题描述：
$ b 目标 -
通过更改零件的放置顺序来最小化无限工作表（宽度为常量）的长度。

问题我面对：

输出的结果是DISCRETE（只有15个可能的利用率），而不是ANALOG（因为有11！* 2 ^ 11可能的解决方案 - >我们期望结果是类比的）

路径SA - MATLAB output

我期待的结果为使用相同的SA代码我用这个问题的另一个问题

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

$ b 效率根据最大长度计算

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

$ b

效率从边界切割长度计算

尽管我想出了如何解决这个问题，我不知道如何找到边界切割区域以找到效率。任何人都有办法找到红线下的区域？我需要避免使用图像处理工具箱

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

解决方案

我想通了，如何找到使用图像处理工具箱来剪切区域而不使用。我想发布这个作为其他人有类似问题的答案。更好的解决方案也是受欢迎的。

部件放置逻辑：

来自 Left->右，直到最右端，然后转到左端，然后放置下一个在前一部分中，移动 Right 等等。

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

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

  boundaryLength = zeros（sheetWidth + 1， 1）; 
％sheetWidth + 1，因为matlab从索引1开始，而范围从0-200 
  

<每次我放置一个零件时，我都将值的范围从左下角的 xDist 分配给 xDist yDist 顶行的值。

  for i = 1：numberOfParts 
 boundaryLength（xDist（i）+1：xDist（i）+ width Index（i）））= yDist（i）+ height（Index（i））; 
结束
 
％索引是我放置零件的顺序。 
％在上面的屏幕截图中，我的索引值是[8,2,4,11,7,5,6,10,1,9,3] 
  

现在我已经找出了整个纸张宽度中每个像素的最大占用长度。要找到该区域，我需要找到矢量 boundaryLength

 <$ c $的总和c> boundaryArea = sum（boundaryLength）; 
  

边界截取利用率举例：

I'm using Simulated Annealing for Rectangular Nesting problem. I'm able to get good results, but the solution i got is DISCRETE. Even global optimum is not always obtained.

Problem Description:

Objective - To minimize the length of the infinite sheet (Width is constant) by changing the order in which parts are placed.

Problem i Face:

The output Results i get are DISCRETE(only 15 possible utilization %) instead of ANALOG (as there is 11!*2^11 possible solution -> We expect the results to be analog)

Path traveled by SA - MATLAB output

Results I expect Generated for a different problem using the same SA code i used for this problem

Reason i get a DISCRETE output can be seen from following image. There could be many possibility of sequences giving same length 55.

Efficiency calculated from Maximum Length

I presume i could solve the problem if i change the way of calculating utilization% like this.

Efficiency calculated from Boundary cut Length

Even though i figured out how to solve the problem, i don't know how to find the Boundary Cut AREA in order to find the efficiency. Anybody has a way to find the area under the red line? I need to avoid using Image Processing Toolbox

FYI: Rectangles are stored as x,y distance of the bottom-left position from Origin of each rectangle. i have the corresponding length, breadth values in another variable.

解决方案

I figured it out, how to find Boundary-Cut Area without using Image Processing Toolbox. I would like to post this as an answer for others having similar problem. Better solutions are also welcome.

Logic for placing of parts:

Place the parts from Left-> Right, till the Right most end , then go to Left end and place the next part over the previous part, move Right and so on.

Solution for finding Boundary Cut Area:

I just create a Single Dimension Matrix whose length equal to the width of the sheet (In the above screen shot -> 200) By Default, i set their values to zero.

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

Each time i place a part, i assign the range of values i.e from its xDist of the bottom left position till xDist of the bottom right position to yDist value of the top line.

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]

Now i have found out the maximum occupied length of every pixel throughout the sheet width. To find the area, i need to find the sum of the vector boundaryLength

boundaryArea = sum(boundaryLength);

Boundary-Cut Utilization for an example:

这篇关于矩形嵌套 - 使用模拟退火收敛到最佳解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！