元启发式算法在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
}

进一步的改进可能是：

使用*apply

• let将内部循环for(i in ...)替换为矢量化代码调整的分布取决于解决方案的特征，而不是如上所述的硬编码(特别是，sigma应该根据您的X variables)

• express threshold的最小进度而变化，例如每个候选解决方案从上一次迭代移动了多远。