シミュレーテッドアニーリングの実装。どのようにパフォーマンスを向上させるには？

Question

更新

私はグローバルな最小値を見つけるでしょう、プロットは、この関数が多くの極小値を持つことを示しています。

f[x_] = 0.5 x^2 + Cos[Pi x] 2 Sin[Pi x] + Cos[Pi x] + 2 Sin[Pi x]; 
plt1 = Plot[f[x], {x, -5, 5}, PlotStyle -> RGBColor[1, 0, 0],Frame -> True] 

紙（http://ww.w.sliponline.org/Publications/Conferences/24/c24.pdf）によると、私は、SAのアルゴリズムを実装するだろうが、パフォーマンスが非常に遅いです。

fTmp = fBest = xBest = xTmp = 999.0; 
k = 0; 
LIMIT = 10^6; 
tTmp = tInit = 300; 
Alpha = 0.999999999; 

For [tTmp = tTmp * Alpha;, k < LIMIT, k++, 
    xTmp = RandomReal[{-5, 5}]; 
    fTmp = f[xTmp]; 
    If [fTmp < fBest, fBest = fTmp; xBest = xTmp, 
    PRA = N[Min[{1, Exp[-(fTmp - fBest)/tTmp]}]]; 
    R = RandomReal[{0.0, 1.0}]; 
    If [R < PRA, fBest = fTmp; xBest = xTmp; k++,]; 
    ]; 
tTmp = tTmp * Alpha; 
]; 
Print[xBest] 
Print[fBest] 

---

-0.390741 
-2.10428 

それは、シミュレーテッドアニーリングの性能と精度を向上させることは可能ですか？お気軽にコメントしてください、ありがとうございます。精度を向上させるために

Answer 1

、あなたが行うことができますいくつかのものがあります。

1. は、アルゴリズムのパラメータを変更します。同様の問題についてSAを利用した研究論文では、パラメータの選択について説明します。あるいは、問題のパラメータで独自のメタ最適化を実行することもできます。異なるタイプの例については、https://en.wikipedia.org/wiki/Hyperparameter_optimizationを参照してください。
2. 複数の最適化ステップを実行します。この場合、新しい実行での最初の実行時に最適解を使用してアルゴリズムを再実行することができます。最適な解を検索する別のアルゴリズムを使用することもできます。あなたの特定のケースでは最適なソリューションに近づいているので、あなたのソリューションに関するブルートフォース検索がより良い結果をもたらすかもしれません。

パフォーマンスは、10^6回の反復の固定ループを使用しないことで改善できます。代わりに、連続する解の間の値の差を、指定された公差よりも小さいものとして使用します。

また、あなたのシステムがおそらく異なる初期値を持つアルゴリズムの複数のインスタンスを実行する必要があり、複数のコアを利用することができます。これによりパフォーマンスが直接的に向上するわけではありませんが、同じ期間に同じリソースからさらに多くの情報が得られる可能性があります。これで十分でない場合は、遺伝的アルゴリズムなどの他のグローバル最適化アルゴリズムを試すことをお勧めします。