计算科学 - 进化算法与。梯度优化：比较成本 - 吾爱随笔录

在优化属于统计和机器学习模型的目标函数时，似乎有一个通用规则：

具有许多参数的高维目标函数优化起来“计算成本很高”因此，往往有两种通用类型的算法用于优化目标函数：

梯度下降：梯度下降试图通过重复计算这些目标函数的导数，并朝着这些导数的方向移动来找到这些目标函数的最小点（即“优化”）。
进化算法：进化算法（例如遗传算法）也试图找到这些目标函数的最小点，但不是重复评估函数的导数，它们的工作原理是“同时向多个方向随机移动，并以概率移动在那些产生较小函数值的方向上更多”。这被称为“变异和交叉”——我已经大大简化了这个过程。

我的问题：随着目标函数中维数的增加，重复评估目标函数的导数在计算上变得越来越昂贵——因为进化算法不需要重复评估这些导数，它们被称为“计算上更便宜”与基于梯度的方法相比。尽管在进化算法的收敛上还没有建立主要结果（而在基于梯度的方法的收敛上已经建立了许多理论结果）：对于完全相同的目标函数 - 我们是否确切地知道“交叉和变异”便宜多少？与“评估二阶导数”相比，我们花费了多少？

似乎仍然存在与“交叉和突变”相关的一些成本（例如，随机存储、分类和排列性能良好的“染色体”，即过去的解决方案）——但我们是否知道与评估衍生品相比这要便宜多少（例如，可以我们使用一些 Big-O Landau 表示法或使用线性与多项式时间来限制它）？

谢谢！

附加：梯度下降和遗传算法的比较，用于使用 R 编程语言优化 Rastrign 函数

1) 遗传算法

library(GA)

start.time <- Sys.time()



  #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)

end.time <- Sys.time()
time.taken <- end.time - start.time

结果：

 time.taken

Time difference of 1.266233 secs

GA@solution
                x1          x2
[1,] -4.947186e-06 3.72529e-07

2）梯度下降

library(pracma)

start.time <- Sys.time()

Rastrigin <- function(x)
    {
        return(20 + x[1]^2 + x[2]^2 - 10*(cos(2*pi*x[1]) + cos(2*pi*x[2])))
    }

 steep_descent(c(1, 1), Rastrigin)

end.time <- Sys.time()
    time.taken <- end.time - start.time
    
    time.taken

结果：

time.taken
Time difference of 0.01959896 secs

$xmin
[1] 0.9949586 0.9949586

$fmin
[1] 1.989918

$niter
[1] 3

参考：