是否有与“遗传算法”相关的一般证明或定理？

我一直在阅读一个名为“模式定理”的数学定理——这个定理是进化计算和遗传算法领域的第一个定理之一，主要负责证明使用“遗传算法”解决优化问题时的合理性目标函数的导数未知或未明确定义。

“遗传算法”可用于解决不同类型的优化问题，例如寻找多项式的根。例如，我们可以使用“遗传算法”来找到以下多项式的根（零点）（这个多项式将被称为“目标函数”，即优化/寻根的目标）：

$$f(x, y) = x \sin{4x} + 1.1y \sin{2y}$$

本质上，“遗传算法”将首先获取 x 和 y 的随机值，并为和的每个随机组合 ,的相应值：给定的值和的组合称为“适应度”。“遗传算法”的工作原理是采用和的许多此类随机组合并记录哪些组合产生较低的适应度值（即和的哪些坐标对应于$x$$y$$f(x,y)$$x$$y$$f(x,y)$$x$$y$$x$$y$$x$$y$$f(x,y)$表面）。然后，“遗传算法”“随机组合”（即“变异”）产生良好适应度值的和组合，并在 x 和 y的这些新“变异组合”处重新评估 y。“遗传算法”多次重复这个突变过程，直到它在$x$$y$$f(x,y)$$x$$y$$f(x,y)$可以忽略不计，或者经过预定义的迭代次数 - 这对于评估目标函数的导数可能非常耗时或成本高昂，或者目标函数的导数定义不明确（即标准优化算法，如梯度）的问题非常有用不能执行下降和牛顿拉普森）。“遗传算法”的优化过程如下所示（左：优化的和选择的建议，右：优化的进度 - 注意随着迭代次数的增加结果的改进）：$x$$y$

关于“遗传算法”的一个有趣观察是，它不“承诺或保证”在优化过程中收敛到目标函数的真正最小点。但是“遗传算法”确实保证的是“目标函数的整体适应度保证随着迭代次数的增加而提高”。换句话说，次迭代”相比，次迭代”后更接近目标函数的真实最小值，其中。这个想法在遗传算法的原始和基本定理之一中表达，称为“模式定理”$m$$n$$m >> n$

显然，这个定理表明产生更好适应度值的“模式”（例如和的组合）更有可能“在突变后存活” - 即产生更好适应度值的“模式”的预期数量可能会增加迭代次数增加。$x$$y$

问题：我花了很长时间试图找到Schema Theorem 证明的推导——试图从数学上解释为什么“遗传算法”可以保证向反对函数的真正最优值移动，因为迭代次数增加？ （反问：毕竟，为什么“遗传算法”不会随着迭代次数的增加而导致更差的适应度结果？）

毕竟：

为什么这种不等式成立？

我很好奇是否有一个数学证明可以证明“遗传算法”和进化计算中最重要和最早的定理之一 - 有人知道模式定理是否有证明吗？

谢谢！

参考：

• https://en.wikipedia.org/wiki/Holland%27s_schema_theorem

• https://www.whitman.edu/Documents/Academics/Mathematics/2014/carrjk.pdf

• https://www.sciencedirect.com/topics/computer-science/schema-theorem（模式定理的替代陈述）

• https://www.researchgate.net/publication/51892214_The_Exact_Schema_Theorem/link/02bfe50f6181790d85000000/download

• http://dynamics.org/Altenberg/FILES/LeeSTPT.pdf

• https://en.wikipedia.org/wiki/Genetic_algorithm

• https://cran.r-project.org/web/packages/GA/vignettes/GA.html

注1：在统计建模的上下文中，“遗传算法”可用于统计模型的“特征选择”和“超参数调优”等任务（例如https://cran.r-project.org/web/包/GenAlgo/vignettes/genalg.pdf，https://topepo.github.io/caret/feature-selection-using-genetic-algorithms.html，https://algotech.netlify.app/blog/optimization-with- _ _ _遗传算法/，https://rpubs.com/jeandsantos88/search_methods_for_hyperparameter_tuning_in_r）

注 2：在 R 中优化函数的遗传算法示例

library(GA)


  #define function to be optimized
Rastrigin <- function(x1, x2)
{
  20 + x1^2 + x2^2 - 10*(cos(2*pi*x1) + cos(2*pi*x2))
}

x1 <- x2 <- seq(-5.12, 5.12, by = 0.1)

#run optimization through the genetic algorithm (with constraints)
GA <- ga(type = "real-valued", 
         fitness =  function(x) -Rastrigin(x[1], x[2]),
         lower = c(-5.12, -5.12), upper = c(5.12, 5.12), 
         popSize = 50, maxiter = 1000, run = 100)

GA | iter = 1 | Mean = -37.396067 | Best =  -6.441093
GA | iter = 2 | Mean = -29.00421 | Best =  -2.51091
GA | iter = 3 | Mean = -22.89516 | Best =  -2.51091

....


GA | iter = 90 | Mean = -3.025916e+00 | Best = -9.301074e-06
GA | iter = 91 | Mean = -5.725962e+00 | Best = -9.301074e-06
GA | iter = 92 | Mean = -5.858303e+00 | Best = -9.301074e-06


....

GA | iter = 250 | Mean = -3.581667e+00 | Best = -1.103990e-06
GA | iter = 251 | Mean = -5.160585e+00 | Best = -1.103990e-06
GA | iter = 252 | Mean = -7.226593e+00 | Best = -1.103990e-06
    

summary(GA)

## Solution = 
##                x1           x2
## [1,] 5.722083e-05 9.223472e-05