Значения функций с использованием дифференциальной эволюции

Question

Как я могу использовать дифференциальную эволюцию, чтобы найти максимальные значения функции функции f(x) = -x(x+1) от -500 до 500? Мне это нужно для шахматной программы, которую я делаю, я начал изучать дифференциальную эволюцию и до сих пор нахожу ее довольно трудной для понимания, не говоря уже о ее использовании. Может ли кто-нибудь помочь мне, введя меня в алгоритм простым способом и, возможно, приведя пример псевдокода для такой программы?

Answer 1

Во-первых, извините за поздний ответ.

Могу поспорить, что вы не будете знать производных функции, которую будете пытаться максимально использовать, поэтому вы хотите использовать алгоритм дифференциальной эволюции, а не что-то вроде метода Ньютона-Рафсона.

Я нашел отличную ссылку, которая объясняет дифференциальную эволюцию простым способом: http://web.as.uky.edu/statistics/users/viele/sta705s06/diffev.pdf.

На первой странице есть раздел с объяснением алгоритма:

Пусть каждое поколение точек состоит из n точек с j членами в каждом.

Инициализировать массив с размером j, Добавить номер j различных случайных значений х из -500 to 500интервал, который вы рассматриваете прямо сейчас. В идеале вы должны знать, где будет находиться максимальное значение, и сделать его более вероятным для вашего x ценности быть там.

Для каждого j случайным образом выберите две точки yj,1 и yj,2 из набора точек x (m) . Построить точку-кандидата cj = x (m) j + α(yj,1 - yj,2). В основном, два значения y включают выбор случайного направления и расстояния, и кандидат определяется путем добавления этого случайного направления и расстояния (масштабируемого на α) к текущему значению.

Хм... Это немного сложнее. Итерируйте по массиву, который вы создали на последнем шаге. Для каждого x значение, выберите два случайных индекса (yj1 а также yj2). Построить кандидата x значение с cx = α(yj1 − yj2)где вы выбираете α, Вы можете попробовать поэкспериментировать с различными значениями альфа.

Проверьте, какой из них больше, значение кандидата или значение х в j, Если значение кандидата больше, замените его на x значение в j,

Делайте все это, пока все значения в массиве не будут более или менее похожи. Тахда, любое из значений массива будет максимальным значением. Просто чтобы уменьшить случайность (или, может быть, это не важно....), усредните их все вместе.

Чем более строгие вы делаете 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));

}

}

Если после прочтения у вас возникнут вопросы, не стесняйтесь задавать их в комментариях. Я сделаю все возможное, чтобы помочь.