3

シミュレーテッド アニーリングを使用して、定義済みの間隔内で、単一変数の多項式関数の局所的な最小値を見つけたいと思います。また、二次関数のグローバル最小値を見つけたいと思います。

このような導関数を使用しないアルゴリズムは、問題に取り組むための最良の方法ではないため、これは研究目的のみです。

アルゴリズム自体は非常に単純ですが、1 次元または n 次元の空間で効率的に隣人を選択する方法がわかりません。

関数の局所的最小値を探しているとしましょう: 2* x^ 3+ x+ 1 間隔 [-0.5, 30] で、間隔が各数値の 10 分の 1 に減ると仮定します (例: {1.1, 1.2)。 ,1.3 , ..., 29.9, 30}.

私が達成したいのは、ランダムウォークと開始点からより低いエネルギーの点への収束速度のバランスです。

毎回指定された間隔から乱数を選択するだけでは、ランダムウォークはなく、アルゴリズムが循環する可能性があります。反対に、単純に 0.1 を同じ確率で加算または減算することによって次のポイントが選択された場合、アルゴリズムは開始ポイントに基づいて徹底的な検索になる可能性があります。

1 次元空間と n 次元空間でシミュレーテッド アニーリングの近隣探索を効率的にバランスさせるにはどうすればよいですか?

4

2 に答える 2

3

したがって、別の n 次元の点 P の近くに「ランダムに」ある n 次元の点 P' を見つけようとしています。たとえば、距離 T です (これはシミュレートされたアニーリングであるため、時々 T を減らすことになると思います)。

これはうまくいくかもしれません：

double[] displacement(double t, int dimension, Random r) {
      double[] d = new double[dimension];
      for (int i=0; i<dimension; i++) d[i] = r.nextGaussian()*t;
      return d;
}

出力はすべての方向にランダムに分布し、原点を中心にしています ( r.nextDouble()45 度の角度を優先し、0.5 を中心にしていることに注意してください)。必要に応じて値を大きくすることで、ディスプレイスメントを変えることができますt。結果の 95% は、元の 2*t 以内になります。

編集：

特定のポイントの近くに変位ポイントを生成するには、次のように変更できます。

double[] displaced(double t, double[] p, Random r) {
      double[] d = new double[p.length];
      for (int i=0; i<p.length; i++) d[i] = p[i] + r.nextGaussian()*t;
      return d;
}

すべての呼び出しに同じものrを使用する必要があります (それぞれに新しいものを作成するRandom()と、同じ変位が何度も得られるため)。

于 2015-06-11T18:12:33.917 に答える