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

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

アルゴリズムの概要

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

1. アルゴリズムはランダムな試行ポイントを生成します。アルゴリズムは、現在の温度に応じたスケールを持つ確率分布によって、現在のポイントからの試行ポイントの距離を選択します。AnnealingFcn オプションを使用して、試行点の距離分布を関数として設定します。選択肢：

   • @annealingfast (デフォルト) — ステップの長さは現在の温度に等しく、方向は均一にランダムです。

   • @annealingboltz — ステップの長さは温度の平方根に等しく、方向は均一にランダムです。

   • @myfun — カスタムアニーリングアルゴリズム、myfun。カスタム アニーリング関数の構文については、アルゴリズムの設定 を参照してください。

   試行ポイントを生成した後、アルゴリズムは必要に応じて試行ポイントを境界内に収まるようにシフトします。アルゴリズムは、試行ポイントの各実行不可能なコンポーネントを、違反した境界と前回の反復での (実行可能な) 値の間で均一にランダムに選択された値にシフトします。

2. アルゴリズムは、新しいポイントが現在のポイントよりも優れているか劣っているかを判断します。新しいポイントが現在のポイントよりも優れている場合は、それが次のポイントになります。新しいポイントが現在のポイントよりも悪い場合でも、アルゴリズムはそれを次のポイントにすることができます。アルゴリズムは、受け入れ関数に基づいて悪いポイントを受け入れます。AcceptanceFcn オプションを使用して受け入れ関数を選択します。選択肢：

   • @acceptancesa (デフォルト) — シミュレーテッド アニーリングの受け入れ関数。合格確率は

     $$\frac{1}{1+\exp \left(\frac{\Delta }{\max (T)}\right)},$$

     ここで、

     Δ = 新しい目標 – 古い目標。
     T₀ = コンポーネントの初期温度 i
     T = 現在の温度。

     Δ と T は両方とも正なので、受理確率は 0 から 1/2 の間になります。温度が低いほど、合格確率は低くなります。また、Δ が大きいほど、受け入れ確率は小さくなります。

   • @myfun — カスタム受け入れ関数、myfun。カスタム受け入れ関数の構文については、アルゴリズムの設定 を参照してください。

3. アルゴリズムは体系的に温度を下げ、これまでに見つかった最良のポイントを保存します。TemperatureFcn オプションは、アルゴリズムが温度を更新するために使用する関数を指定します。k をアニーリングパラメーターとします。（アニーリングパラメーターは再アニーリングまでの反復回数と同じになります。）オプション:

   • @temperatureexp (デフォルト) — T = T₀ * 0.95^k。

   • @temperaturefast — T = T₀ / k.

   • @temperatureboltz — T = T₀ / log(k).

   • @myfun — カスタム温度関数、myfun。カスタム温度関数の構文については、温度オプション を参照してください。

4. simulannealbnd は、ReannealInterval ポイントを受け入れた後に再アニーリングします。再アニーリングでは、アニーリングパラメーターが反復回数よりも低い値に設定され、各次元の温度が上昇します。アニーリングパラメーターは、各次元における目的関数の推定勾配の値によって異なります。基本的な式は

   $$k_i=\log \left(\frac{T_0}{T_i}\frac{\underset{j}{\max }\left(s_j\right)}{s_i}\right),$$

   ここで、

   k_i = コンポーネント i.
   T のアニーリングパラメーター₀ = コンポーネント i.
   T_i の初期温度 = コンポーネント i.
   の現在の温度 s_i = 方向 i の目的関数の勾配 × 方向 i.

   の境界の差

   simulannealbnd は、Inf やその他の不適切な値からアニーリングパラメーター値を保護します。

5. アルゴリズムは、目的関数の平均変化が 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://arxiv.org/pdf/cs/0001018.

参考

simulannealbnd

トピック

• シミュレーテッド アニーリングとは
• シミュレーテッド アニーリングの用語
• 多くの局所最小値を持つ関数の最小化
• シミュレーテッド アニーリング法を用いた最小化