在R语言中实现元启发式算法

Question

我想知道在哪里可以找到一些关于如何在R中实现元启发式算法的好教程和免费数据示例。我问这个问题是因为我找到了很多关于如何做到这一点的资源，但是我在从理论上转向实现时遇到了很大的问题。

Essentials of Metaheuristics (作者Sean Luke教授) 这本书是一个很好的开始，但是对于编程基础有限且没有算法经验的人来说，如果没有一些带有“真实示例”的数据等，很难实现它们。

从Essentials of Metaheuristics（第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

我希望有一个能够使用真实数据给我提供示例的东西。 我正在寻找类似于这样的东西。 我看到了很多关于特定算法（如GA）的问题，也许我正在重复已经存在的问题，但我没有找到这个特定的问题，但如果这是重复的，请警告我。 其他语言，如Python，也会有所帮助（例如任何类似于R的语言）。

- Gago-Silva

---

“Introduction to Numerical Methods and Optimization in Finance” 附带的 R 包是否对您有所帮助？http://www.portfolioprobe.com/2011/10/27/introduction-to-numerical-methods-and-optimization-in-finance/ - Patrick Burns

我会看一下 @PatrickBurns。任何使用真实数据的东西对我来说都是很大的帮助。谢谢！ - Gago-Silva

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将是每一步候选系数的向量，“quality”是平方误差损失：sum((y - yhat)^2)。请注意，在这里，“quality”越低，结果越好。

对于“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. 根据您对最小值的进展（例如每个候选解决方案相对于上一次迭代移动了多少），用threshold来表达。

- Hong Ooi