차동 진화를 사용하는 함수 값

Question

차동 진화를 사용하여 -500에서 500까지의 함수 함수 f (x) = -x (x + 1)의 최대 값을 찾는 방법은 무엇입니까? 내가 만들고있는 체스 프로그램에 이것을 필요로하고, 차동 진화에 대한 연구를 시작했으며, 프로그램을 사용하는 것만 큼 이해하기가 어려웠습니다. 누구든지 나를 간단한 알고리즘으로 소개하고 그러한 프로그램을위한 의사 코드 예제를 제공함으로써 나를 도울 수 있습니까?

Answer 1

우선, 늦은 답변에 대해 사과드립니다.

당신이 최대로하려고하는 함수의 파생어를 알지 못하기 때문에 Differential Evolution 알고리즘을 사용하고 Newton-Raphson 방법과 같은 것을 사용하지 않으려 고합니다.

차동 진화를 직접적으로 설명하는 멋진 링크가 있습니다 (http://web.as.uky.edu/statistics/users/viele/sta705s06/diffev.pdf). 포인트 각각 J 조건으로, N- 포인트 구성의

각 세대 보자 첫 페이지

는 알고리즘에 대한 설명이있는 부분이있다.

크기가 j 인 배열을 초기화하십시오. 숫자 j을 임의의 x 값 (-500 to 500)으로 추가하십시오. 현재 고려중인 간격입니다. 이상적으로는 최대 값이 어디에 있는지 알 수 있고 x 값이있을 가능성이 높습니다. 각각의 J 용

은 임의로 2 점 균일 X (m) 세트에서 두 점 YJ, YJ 1을 선택한다. 후보 점 cj = x (m) j + α (yj, 1 - yj, 2)를 생성하십시오. 기본적으로 두 개의 y 값은 이 무작위 방향과 거리를 선택하는 것을 포함하며, 그 후보는 해당 값 방향과 거리 (α로 스케일링)를 현재 값에 더함으로써 발견됩니다.

음 ... 좀 더 복잡합니다. 마지막 단계에서 만든 배열을 반복합니다. x 값마다 두 개의 임의 인덱스 (yj1 및 yj2)를 선택합니다. α을 선택하면 cx = α(yj1 − yj2)으로 후보자 x 값을 생성하십시오. 다른 알파 값을 시험해 볼 수 있습니다.

어느 것이 더 큰지, 후보 값 또는 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)); 

} 

}

, 코멘트에 남겨 주시기 바랍니다. 나는 최선을 다해 도와 줄거야.