algorithm - 遗传算法：找到适合点的曲线

Question

我正在研究遗传算法。下面是它的工作原理 ：

• 输入：二维点列表
• 输入：曲线的度数
• 输出：以最佳方式通过点的曲线方程（尽量减少从点的 Ys 到曲线的垂直距离之和）

该算法可以为简单的直线和 2 度方程找到好的方程。

但是对于 4 点和 3 度方程及更多，它变得更加复杂。我找不到正确的参数组合：有时我必须等待 5 分钟，但找到的曲线仍然很糟糕。我尝试修改许多参数，从人口规模到选择的父母数量......

GA 编程中的著名组合/定理对我有帮助吗？

谢谢 ！:)

Answer 1

根据给定的内容，您需要一个多项式插值，其中方程的次数是点数减 1。

n = (Number of points) - 1

话虽如此，假设您有 5 个点需要拟合，我将在变量中定义它们：

var points = [[0,0], [2,3], [4,-1], [5,7], [6,9]]

请注意，点数组已按您需要执行的x值排序。

那么等式将是：

f(x) = a1*x^4 + a2*x^3 + a3*x^2 + a4*x + a5

现在根据定义（https://en.wikipedia.org/wiki/Polynomial_interpolation#Constructing_the_interpolation_polynomial），系数计算如下：

现在您需要使用参考页面来得出系数。

Answer 2

这并不复杂，对于度的多项式插值，n您得到以下等式：

p(x) = c0 + c1 * x + c2 * x^2 + ... + cn * x^n = y

这意味着我们需要系数的n + 1基因。c0cn

适应度函数是点到曲线的所有平方距离之和，下面是平方距离的公式。像这样一个较小的值显然更好，如果你不希望你可以取反（1 /平方距离之和）：

d_squared(xi, yi) = (yi - p(xi))^2

我认为为了更快的转换，您可以限制突变，例如，在突变时选择一个新值，其最小值和最大值之间的概率为 20%（例如 -1000 和 1000），概率为 80% 的随机因子在 0.8 到 1.2 之间，您可以将其乘以旧值。