差分進化を使用した関数値

Question

差分進化を使用して、関数関数f（x）= -x（x + 1）の最大値を-500から500まで見つける方法を教えてください。私はチェスプログラムのためにこれを必要としています。私はDifferential Evolutionの研究を始めましたが、プログラムの使用だけでなく、理解するのが非常に難しいと感じています。誰も私をアルゴリズムに簡単な方法で紹介し、おそらくそのようなプログラムの疑似コードの例を与えて助けてくれますか？

Answer 1

まず、遅れて申し訳ありません。

私はあなたが最大にしようとしている関数の導関数を知りませんので、Differential Evolutionアルゴリズムを使用し、Newton-Raphsonメソッドのようなものではないと思っています。

私は、Differential Evolutionを簡単な方法で説明する大きなリンクを見つけました：http://web.as.uky.edu/statistics/users/viele/sta705s06/diffev.pdf。最初のページ

、アルゴリズムの説明のセクションがある：

点の各世代はそれぞれにおけるJ用語と、n個の点から成るう。

サイズjの配列を初期化します。別のランダムx値のjを-500 to 500から追加してください。これは現在検討中です。理想的には、最大値がどこにあるのか知っていれば、x値がそこにある可能性が高くなります。各jについて

、ランダムX （M）点の集合から一様に2点YJ、1及びYJ、2を選択し 。 候補点cj = x （m） j +α（yj、1 - yj、2）を作成します。基本的に2つのyの値は、 ランダムな方向と距離を選択することを含み、そのランダムな値を の方向と距離（αでスケール）を現在の値に加算することによって候補が見つかります。

hmmm ...これはもう少し複雑です。最後のステップで行った配列を繰り返します。 x値ごとに、2つのランダムインデックス（yj1およびyj2）を選択します。候補のxの値をcx = α(yj1 − yj2)とし、αを選択します。さまざまなアルファ値を試してみることができます。

どちらが大きいかを確認するには、候補値または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)); 

} 

}

あなたがこれを読んだ後ご不明な点がございましたら、コメントでそれらをお気軽に。私は助けるために全力を尽くします。