optimization - 用遗传算法填充大小不等的矩形

Question

昨天我想出了一个我没有答案的问题。

我们有一个随机大小的矩形，也有一些半径不同的圆，每个圆的数量有限。每个圈子都有指定的费用。我们希望用这些圆完全填充矩形，以最小的成本实现。

现在我想用遗传算法解决这个问题，但是我在网上找不到任何文章，与我的问题在某种程度上是一样的。

有人知道吗？

Answer 1

您的问题与Knapsack问题有关：从一组N个权重为W且值为V的项目中，您要选择那组具有最大值的项目，但其权重之和仍低于某个界限。

但是，您的问题更加复杂，因为权重约束的评估不是简单的加法，而是取决于圆的排列。我认为这构成了另一个要解决的NP难题。您将必须找到关于该约束的一些快速近似值，以告诉您是否可能（有时甚至可以告诉您这是不可能的）。

容器内物体的布置可以描述为包装问题。您可能需要查看circle packing和相关文献。一个简单的放松也可以基于矩形。如果将圆视为矩形，可以使用一些快速的矩形包装方法。如果您的社交圈大小相差很大，则放松效果可能不佳。