在尝试更直接地回答您的问题之前，让我澄清一些事情。

人们经常使用术语遗传算法(GA)，但在许多情况下，它们真正的意思是进化算法(EA)，它是基于群体（即同时维护多个解决方案）优化算法和受达尔文主义和适者生存启发的方法。GAs 是其中一种方法，其中染色体是二元的，并且您同时具有突变和交叉操作。还有其他方法，例如进化策略或遗传编程。

您还注意到，EA 是元启发式算法，尽管有一些关于其收敛特性的研究 [ 1 ]，但在实践中，它们可能不会收敛。但是，当任何其他潜在方法失败时，EA 绝对有用。

在您的情况下，问题实际上是要找到一个函数的封闭形式（或分析）表达式，该函数由其他较小的函数组成。这确实是创建基因编程（特别是基于树的 GP）的目的。事实上，Knuth 问题是符号回归问题的一个特例，是 GP 应用到的典型问题。因此，GP 可能是您应该尝试的第一种方法。

同时，我在 DEAP 中实现了一个简单的程序，试图解决 Knuth 问题。在这里检查。到目前为止它找到的最佳解决方案（带有一些种子）的适应度是 4，而解决方案是floor(sqrt(float(sqrt(4))))（这里float只是将输入转换为浮点数，以确保类型安全）。我使用差异作为适应度函数，并运行 GP 算法 100 代，每代 100 个人（这不是很多！）。我没有过多地调整超参数，因此，也许，使用正确的种子和超参数，您可以找到正确的解决方案。

为了解决您的问题，原则上您可以使用该编码，但是，正如您所指出的，GA 确实可以返回$4$作为最好的解决方案（实际上并没有那么远$5$)，你可以避免我在每一代人中杀死任何具有这种价值的人。

我没有花太多时间在我的实现和思考这个问题上，但是，正如我上面所说，即使使用基因编程并且只使用 Knuth 的操作，它也可能会陷入局部最优。您可以尝试使用其他操作（例如乘法和加法）来增强我的（或您的）实现，看看是否有改进。