java - 使用差异进化的函数值

Question

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

Answer 1

首先，很抱歉回复晚了。

我敢打赌，您不会知道您将尝试取最大值的函数的导数，这就是为什么您想使用微分进化算法而不是 Newton-Raphson 方法之类的算法。

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

在第一页上，有一节是对算法的解释:

Let each generation of points consist of n points, with j terms in each.

初始化一个大小为j的数组.加个号j来自 -500 to 500 的不同随机 x 值，您现在正在考虑的间隔。理想情况下，您会知道最大值在哪里，并且您会为您的 x 增加它的可能性。存在的值(value)。

For each j, randomly select two points yj,1 and yj,2 uniformly from the set of points x (m) . Construct a candidate point cj = x (m) j + α(yj,1 − yj,2). Basically the two y values involve picking a random direction and distance, and the candidate is found by adding that random direction and distance (scaled by α) to the current value.

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

查看j处的候选值和x值哪个大.如果候选值较大，则替换为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));

}

如果您在阅读本文后有任何疑问，请随时在评论中提问。我会尽力提供帮助。