algorithm - 如何使用遗传算法找到位于多边形边界内的最大圆？

Question

我想实现代码，用遗传算法找到位于多边形边界内的最大圆。

有人知道吗？

Answer 1

计算几何中可能有一种已知的算法可以准确地做到这一点。如果您想使用遗传算法来做到这一点，并且满足于一个好的圆而不是最优的圆，那么这当然是可能的（尽管进化算法似乎更自然一些）。圆可以用 形式的三元组来表示(x,y,r)。变异算子可以以各种方式（例如正态分布增量）来改变坐标。交叉将类似于例如(a,b,c) x (d,e,f) => (a,e,f), (d,b,c). 你需要一个目标函数。从概念上讲，它是面积——但很难确保始终满足约束条件。您可以做的是使用面积减去每个违反约束的惩罚作为目标函数。可以调整惩罚以最终杀死所有违反约束但不应该太大以至于阻止探索解决方案空间的所有部分的圈子。这些参数通常需要在反复试验的基础上进行调整。