シミュレーテッドアニーリング

各ステップにおいて、シミュレーテッドアニーリングヒューリスティックは、現在の状態sの近傍状態s*を考慮し、システムを状態s*へ移行させるか、状態sにとどまるかを確率的に決定します。これらの確率に基づいて、システムは最終的にエネルギーの低い状態へと移行します。通常、このステップは、システムがアプリケーションに適した状態に達するか、または与えられた計算予算を使い果たすまで繰り返されます。

解の最適化には、現在の状態を保守的に変更することによって生成される新しい状態である隣接状態の評価が含まれます。たとえば、巡回セールスマン問題では、各状態は通常、訪問する都市の順列として定義され、任意の状態の隣接状態は、これらの都市のうち任意の2つを入れ替えることによって生成される順列の集合です。隣接状態を生成するために状態を変更する明確な方法は「移動」と呼ばれ、異なる移動によって異なる隣接状態の集合が生成されます。これらの移動は通常、現在の状態への変更を最小限に抑え、巡回セールスマン問題における都市間の接続など、解の各部分を反復的に改善することによって、解を段階的に改善しようとします。

ヒルクライミングのような単純なヒューリスティックは、より良い隣接解を次々と見つけて進み、より良い隣接解が存在しない解に到達した時点で停止しますが、既存のより良い解に必ずたどり着けるとは限りません。その結果は局所最適解に過ぎず、実際の最良の解は異なる可能性のある大域最適解である可能性があります。メタヒューリスティックは、解の隣接解を利用して解空間を探索します。より良い隣接解を優先しますが、局所最適解に陥らないように、確率的に劣った隣接解も受け入れます。十分な時間があれば、大域最適解を見つけることができます。 

現在の状態から遷移する確率${\displaystyle s}$候補者へ 新しい州へ${\displaystyle s_{\mathrm {new} }}$受入確率関数によって指定される${\displaystyle P(e,e_{\mathrm {new} },T)}$それはエネルギーに依存する${\displaystyle e=E(s)}$そして${\displaystyle e_{\mathrm {new} }=E(s_{\mathrm {new} })}$2つの状態、およびグローバルな時間変動パラメータについて${\displaystyle T}$温度と呼ばれる。エネルギーが小さい状態は、エネルギーが大きい状態よりも優れている。確率関数${\displaystyle P}$たとえ${\displaystyle e_{\mathrm {new} }}$より大きい${\displaystyle e}$この機能により、メソッドがグローバルな最適解よりも悪いローカルな最適解に陥ってしまうことを防ぎます。

いつ${\displaystyle T}$ゼロに近づく確率${\displaystyle P(e,e_{\mathrm {new} },T)}$ゼロに近づく必要がある${\displaystyle e_{\mathrm {new} }>e}$それ以外の場合は正の値になります。${\displaystyle T}$すると、システムは下り坂（つまり、エネルギー値が低い方向）への動きをますます優先し、上り坂への動きを避けるようになる。${\displaystyle T=0}$この手順は、下り坂遷移のみを行う貪欲アルゴリズムに帰着する。

シミュレーテッドアニーリングの元の説明では、確率は${\displaystyle P(e,e_{\mathrm {new} },T)}$1に等しいとき${\displaystyle e_{\mathrm {new} }<e}$つまり、この手順は温度に関係なく、可能な場合は常に下り坂へと進む。シミュレーテッドアニーリングの多くの記述や実装では、この条件を依然としてメソッドの定義の一部として扱っている。しかし、この条件はメソッドが機能するために必須ではない。

の${\displaystyle P}$関数は通常、差が小さいときに動きを受け入れる確率が減少するように選択されます。${\displaystyle e_{\mathrm {新しい} }-e}$増加、つまり、大きな上り坂よりも小さな上り坂の方が起こりやすい。ただし、上記の要件が満たされている限り、この要件は厳密には必要ではない。

これらの特性を考慮すると、温度は${\displaystyle T}$国家の進化を制御する上で重要な役割を果たす${\displaystyle s}$システムエネルギーの変動に対するシステムの感度に関して。正確には、大きな${\displaystyle T}$進化${\displaystyle s}$はより粗いエネルギー変動に敏感ですが、より細かいエネルギー変動には敏感です。${\displaystyle T}$小さい。

速い

遅い

冷却スケジュールがシミュレーテッドアニーリングの性能に及ぼす影響を示す例。この問題は、画像のピクセルを再配置して、あるポテンシャルエネルギー関数を最小化することである。この関数は、近距離では類似した色が引き合い、やや離れた距離では反発し合うように作用する。基本的な操作は、隣接する2つのピクセルを交換することである。これらの画像は、高速冷却スケジュール（左）と低速冷却スケジュール（右）で取得され、それぞれ非晶質固体と結晶固体に類似した結果を示している。

アルゴリズムの名前と着想は、制御された温度変化を要求する。そのため、シミュレーションの進行に伴って温度を徐々に下げる必要がある。アルゴリズムは最初は${\displaystyle T}$高い値に設定され、その後、ユーザーが指定できる焼きなましスケジュールに従って各ステップで減少します。${\displaystyle T=0}$割り当てられた時間予算の終盤に差し掛かるにつれて、システムはまず、エネルギー関数の小さな特徴を無視して、良好な解を含む探索空間の広い領域へとさまよい、次に、より狭くなる低エネルギー領域へと漂流し、最終的には最急降下法に従って下り坂を進むことが期待されます。

任意の有限問題に対して、シミュレーテッドアニーリングアルゴリズムがグローバル最適解で終了する確率は、アニーリングスケジュールを延長するにつれて 1 に近づきます。^{[ 12 ]}しかし、この理論的な結果は、成功の確率を十分に確保するために必要な時間が、通常、解空間の完全な探索に必要な時間を超えるため、特に役立つものではありません。^{[ 13 ]}

シミュレーテッドアニーリングは、探索グラフ上のランダムウォークとしてモデル化できます。このグラフの頂点はすべての可能な状態を表し、頂点を結ぶエッジは候補となる移動を表します。neighbour ()関数の重要な要件は、このグラフ上で初期状態からグローバル最適となる可能性のある任意の状態まで十分に短いパスを提供することです。つまり、探索グラフの直径は小さくなければなりません。たとえば、上記の巡回セールスマンの例では、n = 20 都市の探索空間には n! = 2,432,902,008,176,640,000 (2.4 京) 個の状態がありますが、各頂点の近傍の数は   ${\displaystyle \sum _{k=1}^{n-1}k={\frac {n(n-1)}{2}}=190}$エッジ (${\displaystyle n \choose 2}$）、グラフの直径は${\displaystyle n-1}$。

特定の問題におけるシミュレーテッドアニーリングの挙動を調査するには、アルゴリズムの実装において行われたさまざまな設計上の選択から生じる遷移確率を考慮することが有用である。各エッジについて${\displaystyle (s,s')}$探索グラフの遷移確率は、シミュレーテッドアニーリングアルゴリズムが状態へ移動する確率として定義される。 ${\displaystyle s'}$現在の状態が${\displaystyle s}$この確率は、 temperature()で指定される現在の温度、 neighbour()関数によって候補移動が生成される順序、および受理確率関数P()に依存します。遷移確率は単純にはならないことに注意してください。${\displaystyle P(e,e',T)}$なぜなら、候補者は順番に試験を受けるからである。

neighbour()、P()、およびtemperature()の仕様は部分的に冗長です。実際には、多くの問題に対して同じ受理関数P()を使用し、他の2つの関数を具体的な問題に応じて調整するのが一般的です。

Kirkpatrick らによる方法の定式化では、受入確率関数は${\displaystyle P(e,e',T)}$1 と定義されるのは、${\displaystyle e'<e}$、 そして${\displaystyle \exp(-(e'-e)/T)}$それ以外の場合。この式は、物理システムの遷移との類推によって表面上正当化されています。T =1でメトロポリス・ヘイスティングスの提案分布が対称である場合、これはメトロポリス・ヘイスティングスアルゴリズムに対応します。しかし、この受理確率は、メトロポリス・ヘイスティングスの提案分布に類似するneighbour()関数が対称でない場合、あるいは全く確率的でない場合でも、シミュレーテッドアニーリングによく使用されます。その結果、シミュレーテッドアニーリングアルゴリズムの遷移確率は、類似の物理システムの遷移や、一定温度での長期状態分布に対応しません。${\displaystyle T}$いかなる温度においても、その物理システムの熱力学的平衡状態分布と類似している必要はない。しかしながら、シミュレーテッドアニーリングのほとんどの説明では、元の受容関数を前提としており、これはおそらくSAの多くの実装でハードコーディングされている。

1990年、MoscatoとFontanari ^{[ 14 ]}、そして独立にDueckとScheuer ^{[ 15 ]}は、決定論的更新（すなわち、確率的受理ルールに基づかない更新）によって、最終的な品質に影響を与えることなく最適化プロセスを高速化できると提案した。MoscatoとFontanariは、彼らの研究から生まれた「閾値更新」アニーリングの「比熱」曲線の類似性を観察した結果、「シミュレーテッドアニーリングアルゴリズムにおけるメトロポリス更新の確率性は、準最適最小値の探索において主要な役割を果たさない」と結論付けた。その代わりに、「高温でのコスト関数ランドスケープの平滑化と冷却プロセス中の最小値の段階的な定義が、シミュレーテッドアニーリングの成功の基本的な要素である」と彼らは提案した。この方法は、DueckとScheuerの命名により、その後「閾値受理」という名称で普及した。 2001年に、Franz、Hoffmann、Salamonは、コスト/エネルギーランドスケープ上でランダムウォークをシミュレートするアルゴリズムの大きなクラスの中で、決定論的更新戦略が実際に最適なものであることを示した。^{[ 16 ]}

候補生成器を選択する際にはneighbour()、シミュレーテッドアニーリングアルゴリズムを数回反復すると、現在の状態のエネルギーがランダムな状態よりもはるかに低くなることが予想されることを考慮する必要があります。したがって、一般的には、生成器は、遷移先の状態のエネルギーがゼロになるような候補遷移に偏らせるべきです。${\displaystyle s'}$現状と類似している可能性が高い。このヒューリスティック（メトロポリス・ヘイスティングスアルゴリズムの主要原理）は、非常に優れた候補移動だけでなく、非常に劣悪な候補移動も除外する傾向がある。しかし、前者は通常後者よりもはるかに少ないため、このヒューリスティックは一般的に非常に効果的である。

例えば、上記の巡回セールスマン問題では、低エネルギーの巡回ルートで連続する2つの都市を交換しても、そのエネルギー（長さ）への影響はわずかであると予想されます。一方、任意の2つの都市を交換しても、長さが短くなるよりも長くなる可能性の方がはるかに高いです。したがって、連続都市交換型の隣接都市生成器は、任意都市交換型のものよりも優れたパフォーマンスを発揮すると予想されます。後者の方が最適解への経路がやや短くなる可能性はありますが（${\displaystyle n-1}$スワップの代わりに${\displaystyle n(n-1)/2}$)

このヒューリスティックをより正確に表現すると、最初の候補状態を試してみるべきである。${\displaystyle s'}$そのために${\displaystyle P(E(s),E(s'),T)}$大きい。「標準」受入関数の場合${\displaystyle P}$上記のように、それは${\displaystyle E(s')-E(s)}$オーダーは${\displaystyle T}$またはそれ以下。したがって、上記の巡回セールスマンの例では、neighbour()2 つのランダムな都市を交換する関数を使用できます。都市ペアを選択する確率は、それらの距離が一定値を超えるとゼロになります。${\displaystyle T}$。

候補となる生成器を選択する際には、neighbour()「深い」局所的最小値、つまり周囲のすべての状態よりもエネルギーがはるかに低い状態（または連結された状態の集合）の数を減らすように努める必要があります。このようなエネルギー関数の「閉じた集水域」は、高い確率（集水域内の状態数にほぼ比例）で、かつ非常に長い時間（周囲の状態と集水域の底とのエネルギー差にほぼ指数関数的に比例）にわたって、シミュレーテッドアニーリングアルゴリズムを閉じ込めてしまう可能性があります。

原則として、この目標を満たしつつ、エネルギーが類似した候補を優先するような候補生成器を設計することは不可能です。一方、生成器に比較的簡単な変更を加えることで、シミュレーテッドアニーリングの効率を大幅に向上させることはしばしば可能です。たとえば、巡回セールスマン問題では、2 つのツアーを示すことは難しくありません。${\displaystyle A}$、${\displaystyle B}$長さがほぼ等しいので、（１）${\displaystyle A}$が最適である、（2）都市ペアの交換のすべてのシーケンスが変換する${\displaystyle A}$に${\displaystyle B}$両方よりもはるかに長いツアーをこなす、そして（3）${\displaystyle A}$変換できる${\displaystyle B}$連続する都市のセットを反転（順序を逆にする）することによって。この例では、${\displaystyle A}$そして${\displaystyle B}$ジェネレータがランダムなペア交換のみを実行する場合、それらは異なる「深い盆地」に位置しますが、ジェネレータがランダムなセグメント反転を実行する場合は、それらは同じ盆地に位置します。

シミュレーテッドアニーリングを正当化するために用いられる物理的アナロジーは、冷却速度が十分に低く、現在の状態の確率分布が常に熱力学的平衡に近い状態にあることを前提としている。残念ながら、緩和時間（温度変化後に平衡が回復するまで待たなければならない時間）は、エネルギー関数の「地形」と現在の温度に大きく依存する。シミュレーテッドアニーリングアルゴリズムでは、緩和時間は候補生成器にも非常に複雑な形で依存する。これらのパラメータはすべて通常、シミュレーテッドアニーリングアルゴリズムにブラックボックス関数として提供されることに注意されたい。したがって、理想的な冷却速度は事前に決定できず、各問題に対して経験的に調整する必要がある。適応型シミュレーテッドアニーリングアルゴリズムは、冷却スケジュールを探索の進行状況に接続することでこの問題に対処する。熱力学的シミュレーテッドアニーリング^{[ 17 ]}などの他の適応型アプローチは、熱力学の法則に従って、2つの状態間のエネルギー差に基づいて各ステップで温度を自動的に調整する。