シミュレーテッドアニーリングの仕組み

このページは機械翻訳を使用して翻訳されました。元の英語を参照するには、ここをクリックします。

アルゴリズムの概要

シミュレーテッドアニーリングアルゴリズムは、次の手順を実行します。

アルゴリズムはランダムな試行ポイントを生成します。アルゴリズムは、現在の温度に応じたスケールを持つ確率分布によって、現在のポイントから試行ポイントまでの距離を選択します。AnnealingFcn オプションを使用して、試行ポイントの距離分布を関数として設定します。選択肢：
- @annealingfast (デフォルト) — ステップの長さは現在の温度に等しく、方向は均一にランダムです。
- @annealingboltz — ステップの長さは温度の平方根に等しく、方向は均一にランダムです。
- @myfun — カスタムアニーリングアルゴリズム、myfun。カスタムアニーリング関数の構文については、アルゴリズムの設定を参照してください。
試行ポイントを生成した後、アルゴリズムは必要に応じて試行ポイントをシフトして境界内にとどめます。アルゴリズムは、試行ポイントの各実行不可能なコンポーネントを、違反した境界と前回の反復での (実行可能な) 値の間で一様にランダムに選択された値にシフトします。
アルゴリズムは、新しいポイントが現在のポイントよりも優れているか劣っているかを判断します。新しいポイントが現在のポイントよりも優れている場合は、それが次のポイントになります。新しいポイントが現在のポイントよりも悪い場合でも、アルゴリズムはそれを次のポイントにすることができます。アルゴリズムは、受け入れ関数に基づいて悪い点を受け入れます。AcceptanceFcn オプションを使用して受け入れ関数を選択します。選択肢：
- @acceptancesa (デフォルト) — シミュレーテッドアニーリング受け入れ関数。合格確率は
  $\frac{1}{1 + \exp (\frac{Δ}{\max (T)})},$
  ここで、
  Δ = 新しい目標 – 古い目標。
  T₀ = コンポーネントの初期温度 i
  T = 現在の温度。
  Δ と T は両方とも正なので、受け入れられる確率は 0 から 1/2 の間になります。温度が低いほど、合格確率は低くなります。また、Δ が大きいほど、受け入れ確率は低くなります。
- @myfun — カスタム受け入れ関数、myfun。カスタム受け入れ関数の構文については、アルゴリズムの設定を参照してください。
アルゴリズムは体系的に温度を下げ、これまでに見つかった最良のポイントを保存します。TemperatureFcn オプションは、アルゴリズムが温度を更新するために使用する関数を指定します。k はアニーリングパラメータを表します。（アニーリングパラメータは再アニーリングまでの反復回数と同じです。）オプション:
- @temperatureexp (デフォルト) — T = T₀ * 0.95^k 。
- @temperaturefast — T = T₀ / k.
- @temperatureboltz — T = T₀ / log(k).
- @myfun — カスタム温度関数、myfun 。カスタム温度関数の構文については、温度オプションを参照してください。
simulannealbnd は ReannealInterval ポイントを受け入れた後に再アニールします。再アニーリングでは、アニーリングパラメータが反復回数よりも低い値に設定され、各次元の温度が上昇します。アニーリングパラメータは、各次元における目的関数の推定勾配の値に依存します。基本的な式は
$k_{i} = \log (\frac{T_{0}}{T_{i}} \frac{\max_{j} (s_{j})}{s_{i}}),$
ここで、
k_i = コンポーネント i のアニーリングパラメーター。
T₀ = コンポーネント i の初期温度。
T_i = コンポーネント i の現在の温度。
s_i = 方向 i の目標の勾配に方向 i の境界の差を掛けた値。
simulannealbnd は、Inf やその他の不適切な値からアニーリングパラメータ値を保護します。
アルゴリズムは、目的関数の平均変化が FunctionTolerance に比べて小さい場合、またはその他の停止基準に達した場合に停止します。アルゴリズムの停止条件を参照してください。

アルゴリズムの詳細については、Ingber [1] を参照してください。

アルゴリズムの停止条件

シミュレーテッドアニーリングアルゴリズムは、次の条件を使用して停止するタイミングを決定します。

FunctionTolerance — アルゴリズムは、 StallIterLim 回の反復における目的関数の値の平均変化が FunctionTolerance の値よりも小さくなるまで実行されます。既定値は 1e-6 です。
MaxIterations — 反復回数がこの最大反復回数を超えると、アルゴリズムは停止します。最大反復回数は正の整数または Inf として指定できます。既定値は Inf です。
MaxFunctionEvaluations は目的関数の評価の最大回数を指定します。関数評価の回数が MaxFunctionEvaluations の値を超えると、アルゴリズムは停止します。既定値は 3000*numberofvariables です。
MaxTime は、アルゴリズムが停止するまでに実行される最大時間を秒単位で指定します。既定値は Inf です。
ObjectiveLimit — 最適な目的関数の値が ObjectiveLimit の値より小さい場合、アルゴリズムは停止します。既定値は -Inf です。

参考文献

[1] Ingber, L. Adaptive simulated annealing (ASA): Lessons learned. Invited paper to a special issue of the Polish Journal Control and Cybernetics on “Simulated Annealing Applied to Combinatorial Optimization.” 1995. Available from https://www.ingber.com/asa96_lessons.ps.gz

参考

simulannealbnd

シミュレーテッドアニーリングの仕組み

アルゴリズムの概要

アルゴリズムの停止条件

参考文献

参考

関連するトピック