3

如何使用差分进化来找到函数函数 f(x) = -x(x+1) 从 -500 到 500 的最大值？我正在制作的国际象棋程序需要这个，我已经开始研究差分进化，但仍然发现它很难理解，更不用说用于程序了。任何人都可以通过以简单的方式向我介绍算法并可能为此类程序提供一些示例伪代码来帮助我吗？

4

1 回答 1

3

首先，很抱歉回复晚了。

我敢打赌，您不会知道要尝试最大化的函数的导数，这就是您要使用差分进化算法而不是牛顿-拉夫森方法之类的原因的原因。

我找到了一个很好的链接，它以简单的方式解释了差异进化：http ://web.as.uky.edu/statistics/users/viele/sta705s06/diffev.pdf 。

在第一页，有一个部分解释了算法：

让每一代点由n个点组成，每个点有j项。

用 size 初始化一个数组j。从 中添加许多j不同的随机 x 值-500 to 500，即您现在正在考虑的区间。理想情况下，您会知道最大值在哪里，并且您的x值更有可能在那里。

对于每个 j，从点集合 x (m) 中均匀地随机选择两个点 yj,1 和 yj,2 。构造一个候选点 cj = x (m) j + α(yj,1 − yj,2)。基本上，这两个 y 值涉及选择一个随机方向和距离，并且通过将该随机方向和距离（按 α 缩放）添加到当前值来找到候选者。

嗯...这有点复杂。遍历您在上一步中创建的数组。对于每个x值，选择两个随机索引 (yj1和yj2)。用构造一个候选x值cx = α(yj1 − yj2)，您可以在其中选择α. 您可以尝试使用不同的 alpha 值进行试验。

检查哪个更大，候选值或 x 值j。如果候选值较大，则将其替换为x处的值j。

这样做直到数组中的所有值都或多或少相似。Tahdah，数组的任何值都将是最大值。只是为了减少随机性（或者这可能并不重要......），将它们平均在一起。

方法越严格about，得到的近似值就越好，但需要的时间就越多。

例如，代替Math.abs(a - b) <= alpha /10，我会做Math.abs(a - b) <= alpha /10000一个更好的近似值。

您将获得所需值的良好近似值。

快乐编码！

我为此响应编写的代码：

public class DifferentialEvolution {

public static final double alpha = 0.001;

public static double evaluate(double x) {
    return -x*(x+1);
}

public static double max(int N) { // N is initial array size.

    double[] xs  = new double[N];

    for(int j = 0; j < N; j++) {
        xs[j] = Math.random()*1000.0 - 500.0; // Number from -500 to 500.
    }

    boolean done = false;
    while(!done) {
        for(int j = 0; j < N; j++) {
            double yj1 = xs[(int)(Math.random()*N)]; // This might include xs[j], but that shouldn't be a problem.
            double yj2 = xs[(int)(Math.random()*N)]; // It will only slow things down a bit.

            double cj = xs[j] + alpha*(yj1-yj2);

            if(evaluate(cj) > evaluate(xs[j])) {
                xs[j] = cj;
            }
        }

        double average = average(xs); // Edited

        done = true;
        for(int j = 0; j < N; j++) { // Edited
            if(!about(xs[j], average)) { // Edited
                done = false;
                break;
            }
        }

    }
    return average(xs);

}

public static double average(double[] values) {
    double sum = 0;
    for(int i = 0; i < values.length; i++) {
        sum += values[i];
    }

    return sum/values.length;

}

public static boolean about(double a, double b) {
    if(Math.abs(a - b) <= alpha /10000) { // This should work.
        return true;
    }
    return false;
}

public static void main(String[] args) {

    long t = System.currentTimeMillis();
    System.out.println(max(3));
    System.out.println("Time (Milliseconds): " + (System.currentTimeMillis() - t));

}

}

If you have any questions after reading this, feel free to ask them in the comments. I'll do my best to help.

于 2012-02-17T14:56:51.007 回答