algorithm - 在 R 中实现元启发式算法

Question

我在哪里可以找到一些带有免费数据示例的好教程，关于如何在 R 中实现元启发式算法？

我问这个是因为我找到了很多关于如何做到这一点的资源，但是我在从理论到实现它的过程中面临着很大的问题。

Book Essentials of Metaheuristics (by Professor Sean Luke)是一本很好的入门书，但是对于编程背景有限且没有算法经验的人来说，如果没有一些带有数据的“真实示例”等，很难实现它们

从《元启发式基础》一书(第 16 页)中选取一个示例:

Algorithm 5 Steepest Ascent Hill-Climbing
1: n ← number of tweaks desired to sample the gradient
2: S ← some initial candidate solution
3: repeat
4: R ← Tweak(Copy(S))
5: for n − 1 times do
6: W ← Tweak(Copy(S))
7: if Quality(W) > Quality(R) then
8: R ← W
9: if Quality(R) > Quality(S) then
10: S ← R
11: until S is the ideal solution or we have run out of time
12: return S

我想要一些东西，在给我一个使用真实数据的例子之后。我在找东西like this .

我见过很多关于特定算法(如 GA)的问题，也许我在重复已经存在的问题，但我没有特别发现这个问题，但如果重复，请警告我。

Python 等其他语言也有帮助(例如任何类似于 R 的语言)。

Answer 1

我不熟悉元启发式领域，但您提供的伪代码实际上很容易转换为 R 语法:

# I never metaheuristic I didn't like
metah <- function(S, quality, tweak, n, outer.limit, threshold)
{
    outer.n <- 0
    repeat {
        outer.n <- outer.n + 1
        R <- tweak(S)
        for(i in seq_len(n - 1))
        {
            W <- tweak(S)
            if(quality(W) > quality(R))
                R <- W
        }
        if(quality(R) > quality(S))
            S <- R
        if(quality(S) >= threshold || outer.n >= outer.limit)
            break
    }
    S
}

现在您所要做的就是为 quality 和 tweak 提供合适的函数。

例如，假设我们要拟合线性回归。在这种情况下，我们有一个响应向量 y 和一个向量矩阵 X。解决方案 S 将是每一步的候选系数向量，“质量”是平方误差损失:sum((y - yhat)^2)。请注意，这里的质量越低越好。

对于tweak，我们可能会使用来自当前解决方案S 的正态扰动分布，以及用户指定的协方差矩阵。

然后可以将其编码为

require(MASS) # for mvrnorm

quality <- function(S, y, X)
sum((y - X %*% S)^2)

tweak <- function(S, sigma=rep(1, length(s))
S + mvrnorm(length(S), 0, sigma)

metah <- function(y, X, quality, tweak, n, outer.limit, threshold)
{
    outer.n <- 0
    S <- rep(1, ncol(X))
    repeat {
        outer.n <- outer.n + 1
        R <- tweak(S)
        for(i in seq_len(n - 1))
        {
            W <- tweak(S)
            if(quality(W, y, X) < quality(R, y, X)) # note reversed comparison!
                R <- W
        }
        if(quality(R, y, X) < quality(S, y, X))
            S <- R
        if(quality(S) <= threshold || outer.n >= outer.limit)
            break
    }
    S
}

进一步的改进可能是:

1. 使用 *apply

   将内部循环 for(i in ...) 替换为矢量化代码

2. 让调整的分布根据解决方案的特性而变化，而不是像上面那样硬编码(特别是，sigma 应该根据 X 变量的规模而变化)

3. 根据您朝着最小化的进度表达阈值，例如每个候选解决方案与上一次迭代相差多远。