3

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

4

1 に答える 1

3

初めまして、返信が遅くなり申し訳ありません。

最大化しようとしている関数の導関数がわからないことは間違いありません。そのため、ニュートン-ラフソン法のようなものではなく、微分進化アルゴリズムを使用する必要があります。

分化進化を簡単に説明する素晴らしいリンクを見つけました: http://web.as.uky.edu/statistics/users/viele/sta705s06/diffev.pdf .

最初のページには、アルゴリズムの説明を含むセクションがあります。

ポイントの各世代は n ポイントで構成され、それぞれに j 項があるとします。

size で配列を初期化しますj。現在検討している間隔jから、いくつかの異なるランダムな x 値を追加します。-500 to 500理想的には、最大値がどこにあるかを知っていて、x値がそこにある可能性を高めます。

各 j について、2 つの点 yj,1 と yj,2 を一連の点 x (m) から一様にランダムに選択します。候補点 cj = x (m) j + α(yj,1 − yj,2) を作成します。基本的に、2 つの y 値にはランダムな方向と距離の選択が含まれ、そのランダムな方向と距離 (α でスケーリング) を現在の値に追加することで候補が見つかります。

うーん...これはもう少し複雑です。最後のステップで作成した配列を反復処理します。値ごと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));

}

}

これを読んだ後に質問がある場合は、コメントで遠慮なく質問してください。私は助けるために最善を尽くします。

于 2012-02-17T14:56:51.007 に答える