Function Values using Differential Evolution

Question

How can I use differential evolution to find the maximum values of the function function f(x) = -x(x+1) from -500 to 500? I need this for a chess program I am making, I have begun researching on Differential Evolution and am still finding it quite difficult to understand, let alone use for a program. Can anyone please help me by introducing me to the algorithm in a simple way and possibly giving some example pseudo-code for such a program?

Answer 1

First, of all, sorry for the late reply.

I bet that you won't know the derivatives of the function that you'll be trying to max, that's why you want to use the Differential Evolution algorithm and not something like the Newton-Raphson method.

I found a great link that explains Differential Evolution in a straightforward manner: http://web.as.uky.edu/statistics/users/viele/sta705s06/diffev.pdf.

On the first page, there is a section with an explanation of the algorithm:

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

Initialize an array with size j. Add a number j of distinct random x values from -500 to 500, the interval you are considering right now. Ideally, you would know around where the maximum value would be, and you would make it more probable for your x values to be there.

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.

Hmmm... This is a bit more complicated. Iterate through the array you made in the last step. For each x value, pick two random indexes (yj1 and yj2). Construct a candidate x value with cx = α(yj1 − yj2), where you choose your α. You can try experimenting with different values of alpha.

Check to see which one is larger, the candidate value or the x value at j. If the candidate value is larger, replace it for the x value at j.

Do this all until all of the values in the array are more or less similar. Tahdah, any of the values of the array will be the maximum value. Just to reduce randomness (or maybe this is not important....), average them all together.

The more stringent you make the about method, the better approximations you will get, but the more time it will take.

For example, instead of Math.abs(a - b) <= alpha /10, I would do Math.abs(a - b) <= alpha /10000 to get a better approximation.

You will get a good approximation of the value that you want.

Happy coding!

Code I wrote for this response:

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.