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

Question

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

我们有一个随机大小的矩形，还有一些半径不同的圆，每个圆的数量都是有限的。每个圈子都有指定的成本。我们想用这些圆圈完全填充我们的矩形，接近最小的成本。

现在我想用遗传算法解决这个问题，但是我在网上找不到任何文章，这与我的问题相同。

有人知道吗？

Answer 1

您的问题与背包问题有关：在一组具有权重 W 和值 V 的 N 个项目中，您希望选择具有最大值的那组项目，但它们的权重总和仍然低于某个界限。

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

容器内物体的排列可以描述为一个包装问题。您可能想查看圆形包装和相关文献。简单的放松也可以基于矩形。如果您将圆形视为矩形，则可以使用矩形包装的快速方法。如果您的圈子的大小差异很大，那么这可能是一种不好的放松。