焼きなまし法
焼きなまし法（Simulated Annealing、SA）は、大域的最適化問題を解くための汎用的な乱択アルゴリズムです。これは、広大な探索空間において、与えられた関数の大域的最適解に近似する解を見つけることを目的としています。1983年にS. Kirkpatrickらによって考案され、1985年にV. Cernyによって再発見されました。
このアルゴリズムの名前は、金属工学における焼きなましプロセスに由来します。焼きなましでは、金属材料を加熱し、その後ゆっくりと冷却することで結晶を成長させ、欠陥を減少させます。高温では原子は初期位置から移動しやすくなり、エネルギーの高い状態を彷徨います。その後、ゆっくりと冷却することで、原子はより低いエネルギー状態に落ち着き、初期状態よりもさらにエネルギーが低い状態を得る可能性が高まります。
SAアルゴリズムは、解を反復的に改善していく過程で、現在の解の近傍にあるランダムな解を探索します。この際、関数の値とグローバルパラメータである「温度」（T）が影響します。物理的な焼きなましと同様に、Tの値は徐々に減少していきます。初期のTが高い状態では、解は大きく変化しやすくなりますが、Tがゼロに近づくにつれて解は収束していきます。そのため、初期段階では、山登り法のように局所的な極小状態に陥る心配が少なくなります。
焼きなまし法では、探索空間の各点「s」は物理システムの「状態」に対応し、最小化したい関数E(s)は物理状態の「内部エネルギー」に対応します。このアルゴリズムの目標は、任意の初期状態から開始して、システムをできるだけエネルギーが低い状態にすることです。
各ステップで、SAは現在の状態sの近傍にある状態s'をいくつか評価し、現在の状態を維持するか、近傍状態に遷移するかを確率的に決定します。この決定は、システムが最終的に低いエネルギー状態に移行するように考慮されます。このプロセスは、十分な結果が得られるか、計算時間が終了するまで繰り返されます。
各状態の近傍は、アプリケーション固有の方法でユーザーによって定義されます。たとえば、巡回セールスマン問題では、各状態は「ツアー」（訪問する都市の順列）と考えることができ、近傍は都市の順列中で2つの都市の順序を入れ替えたものとして定義できます。
現在の状態sから新しい状態候補s'への遷移確率は、二つの状態のエネルギーe = E(s)とe' = E(s')の関数P(e, e', T)によって与えられます。ここで、Tは「温度」に対応し、時間とともに変化するグローバルパラメータです。
遷移確率Pの重要な条件として、e' > eの場合でもゼロではない値を返す必要があります。これは、エネルギーが増加する「悪い」状態への遷移も許容することを意味します。これにより、ローカルな極小状態に陥るのを防ぎます。Tが0に近づくにつれて、e' > eの場合にはP(e, e', T)の値をゼロに近づけ、e' < eの場合には値を大きくします。これにより、Tが十分に小さくなると、システムはより低いエネルギー状態に収束し、逆の移動は抑制されます。特に、Tが0になると、山登り法のように近傍の極小に確実に向かうようになります。
関数Pは、e' - eの値が増加するにつれて確率を減少させる値を返すように設定されます。つまり、エネルギーが少し増加するだけの移動の方が、エネルギーが大きく増加する移動よりも、良い解に繋がる可能性が高いという考え方に基づいています。
焼きなまし法の重要な特徴の一つは、シミュレーションが進むにつれて、温度が徐々に下がる点です。初期温度Tは高い値に設定され、焼きなましスケジュールに従ってステップごとに減少します。スケジュールはユーザーが指定する場合もありますが、最終的にはT=0で終了する必要があります。これにより、システムは初期段階でエネルギー関数の小さな変化を無視して、探索空間の広い領域を探索し、徐々にエネルギーの低い領域に探索範囲を狭めて、最終的に最もエネルギーの低い状態に収束します。
理論的には、適切な焼きなましスケジュールを設定すれば、焼きなまし法でグローバルな最適解が得られる確率は1に近づきます。しかし実際には、意味のある結果を得るためには、解空間を十分に探索するための時間が必要です。
焼きなまし法を特定の問題に適用するためには、状態空間、近傍選択方法、遷移確率関数、焼きなましスケジュールなどを適切に選択する必要があります。これらの選択はアルゴリズムの有効性に大きく影響しますが、残念ながらすべての問題に最適な選択が存在するわけではありません（ノーフリーランチ定理）。また、与えられた問題に対して最適な選択を見つける一般的な方法も存在しません。そのため、焼きなまし法の適用は科学というよりもむしろ技術や経験によるところが大きいと言えます。
近傍の選択方法は特に重要です。近傍は「探索グラフ」としてモデル化できます。状態を点とし、近傍となる点との間に線が引かれます。一般的に、初期状態からグラフ上で短いパスを通って「十分良い」状態に到達できる可能性が高く、焼きなまし法の反復でそのようなパスをたどることが期待されます。そのため、sの近傍にsとほぼ同じエネルギーの状態群を配置するように探索グラフを作成します。巡回セールスマン問題の場合、隣接する都市の順序を入れ替えることで近傍を生成する方が、任意の都市を入れ替えるよりもエネルギーの変化が小さくなります。
遷移確率関数Pは、前述の条件を満たしている限り、近傍グラフほど重要ではありません。実際には、同じ確率関数を多くの問題に適用し、焼きなましスケジュールで問題固有の調整を行うことが多いです。Kirkpatrickらが定式化した元の手法では、遷移確率P(e, e', T)はe' < eの場合には1を返し、それ以外の場合にはexp((e-e')/T)と定義されています。この式は、メトロポリス法から派生したものですが、焼きなまし法で特定の数式を使用する数学的な正当性はありません。焼きなまし法では近傍が順次評価されるため、状態sからs'に遷移する実際の確率はその式とは関係ありません。
焼きなましスケジュールは、近傍関数ほど重要ではありませんが、注意して選択する必要があります。初期温度は、上り（エネルギーが増加する）遷移と下り（エネルギーが減少する）遷移の確率がほぼ同じになるように大きく設定する必要があります。一般的に温度は指数関数的に減少するようにスケジュールします。
以下に、焼きなまし法の擬似コードを示します。このコードは、初期状態startStateから開始して、maxIter回までステップを繰り返し、エネルギーがgoalE以下の解が見つかるまで動作します。
function 焼きなまし法(startState, maxIter, goalE)
state = startState
e = EVAL(state)
bestState = state
bestE = e
for (iter = 0; iter < maxIter; iter++)
nextState = NEIGHBOUR(state)
nextE = EVAL(nextState)
if nextE < bestE then
bestState = nextState
bestE = nextE
if bestE <= goalE then
return bestState
if random() <= PROBABILITY(e, nextE, TEMPERATURE(iter / maxIter)) then
state = nextState
e = nextE
return bestState
function PROBABILITY(e1, e2, t)
if e1 >= e2 then
return 1
else
return e^((e1 - e2) / t)
function TEMPERATURE(r)
return α^r
ここで、
EVAL(state)は状態stateの評価値（エネルギー状態）を返します。
NEIGHBOUR(state)は状態stateの近傍をランダムに1つ生成します。
TEMPERATURE(r)は焼きなましスケジュールに従って温度を返します（ここでは定数αのべき乗）。
PROBABILITY(e1, e2, t)は温度tのもとでエネルギーe1からe2への遷移確率を返します。
random()は0以上1以下の乱数を返します。
タブーサーチ (TS): 焼きなまし法と同様に近傍探索を行う手法ですが、探索の堂々巡りを避けるために、すでに評価した解をタブーリストで管理します。
蟻コロニー最適化 (ACO): 多数の蟻（エージェント）を解空間に配置し、最適解を探索します。
遺伝的アルゴリズム (GA): 複数の解をプールし、突然変異や交叉によって新しい解を生成し、確率的な手法で解を選別します。
量子焼きなまし法
最適化問題
マルコフ連鎖
組合せ最適化
シミュレーティド・エボリューション
巡回セールスマン問題
このアルゴリズムの名前は、金属工学における焼きなましプロセスに由来します。焼きなましでは、金属材料を加熱し、その後ゆっくりと冷却することで結晶を成長させ、欠陥を減少させます。高温では原子は初期位置から移動しやすくなり、エネルギーの高い状態を彷徨います。その後、ゆっくりと冷却することで、原子はより低いエネルギー状態に落ち着き、初期状態よりもさらにエネルギーが低い状態を得る可能性が高まります。
SAアルゴリズムは、解を反復的に改善していく過程で、現在の解の近傍にあるランダムな解を探索します。この際、関数の値とグローバルパラメータである「温度」（T）が影響します。物理的な焼きなましと同様に、Tの値は徐々に減少していきます。初期のTが高い状態では、解は大きく変化しやすくなりますが、Tがゼロに近づくにつれて解は収束していきます。そのため、初期段階では、山登り法のように局所的な極小状態に陥る心配が少なくなります。
概要
焼きなまし法では、探索空間の各点「s」は物理システムの「状態」に対応し、最小化したい関数E(s)は物理状態の「内部エネルギー」に対応します。このアルゴリズムの目標は、任意の初期状態から開始して、システムをできるだけエネルギーが低い状態にすることです。
基本的な反復
各ステップで、SAは現在の状態sの近傍にある状態s'をいくつか評価し、現在の状態を維持するか、近傍状態に遷移するかを確率的に決定します。この決定は、システムが最終的に低いエネルギー状態に移行するように考慮されます。このプロセスは、十分な結果が得られるか、計算時間が終了するまで繰り返されます。
状態近傍
各状態の近傍は、アプリケーション固有の方法でユーザーによって定義されます。たとえば、巡回セールスマン問題では、各状態は「ツアー」（訪問する都市の順列）と考えることができ、近傍は都市の順列中で2つの都市の順序を入れ替えたものとして定義できます。
遷移確率
現在の状態sから新しい状態候補s'への遷移確率は、二つの状態のエネルギーe = E(s)とe' = E(s')の関数P(e, e', T)によって与えられます。ここで、Tは「温度」に対応し、時間とともに変化するグローバルパラメータです。
遷移確率Pの重要な条件として、e' > eの場合でもゼロではない値を返す必要があります。これは、エネルギーが増加する「悪い」状態への遷移も許容することを意味します。これにより、ローカルな極小状態に陥るのを防ぎます。Tが0に近づくにつれて、e' > eの場合にはP(e, e', T)の値をゼロに近づけ、e' < eの場合には値を大きくします。これにより、Tが十分に小さくなると、システムはより低いエネルギー状態に収束し、逆の移動は抑制されます。特に、Tが0になると、山登り法のように近傍の極小に確実に向かうようになります。
関数Pは、e' - eの値が増加するにつれて確率を減少させる値を返すように設定されます。つまり、エネルギーが少し増加するだけの移動の方が、エネルギーが大きく増加する移動よりも、良い解に繋がる可能性が高いという考え方に基づいています。
焼きなましスケジュール
焼きなまし法の重要な特徴の一つは、シミュレーションが進むにつれて、温度が徐々に下がる点です。初期温度Tは高い値に設定され、焼きなましスケジュールに従ってステップごとに減少します。スケジュールはユーザーが指定する場合もありますが、最終的にはT=0で終了する必要があります。これにより、システムは初期段階でエネルギー関数の小さな変化を無視して、探索空間の広い領域を探索し、徐々にエネルギーの低い領域に探索範囲を狭めて、最終的に最もエネルギーの低い状態に収束します。
最適解への収束
理論的には、適切な焼きなましスケジュールを設定すれば、焼きなまし法でグローバルな最適解が得られる確率は1に近づきます。しかし実際には、意味のある結果を得るためには、解空間を十分に探索するための時間が必要です。
パラメータ選択
焼きなまし法を特定の問題に適用するためには、状態空間、近傍選択方法、遷移確率関数、焼きなましスケジュールなどを適切に選択する必要があります。これらの選択はアルゴリズムの有効性に大きく影響しますが、残念ながらすべての問題に最適な選択が存在するわけではありません（ノーフリーランチ定理）。また、与えられた問題に対して最適な選択を見つける一般的な方法も存在しません。そのため、焼きなまし法の適用は科学というよりもむしろ技術や経験によるところが大きいと言えます。
状態近傍
近傍の選択方法は特に重要です。近傍は「探索グラフ」としてモデル化できます。状態を点とし、近傍となる点との間に線が引かれます。一般的に、初期状態からグラフ上で短いパスを通って「十分良い」状態に到達できる可能性が高く、焼きなまし法の反復でそのようなパスをたどることが期待されます。そのため、sの近傍にsとほぼ同じエネルギーの状態群を配置するように探索グラフを作成します。巡回セールスマン問題の場合、隣接する都市の順序を入れ替えることで近傍を生成する方が、任意の都市を入れ替えるよりもエネルギーの変化が小さくなります。
遷移確率
遷移確率関数Pは、前述の条件を満たしている限り、近傍グラフほど重要ではありません。実際には、同じ確率関数を多くの問題に適用し、焼きなましスケジュールで問題固有の調整を行うことが多いです。Kirkpatrickらが定式化した元の手法では、遷移確率P(e, e', T)はe' < eの場合には1を返し、それ以外の場合にはexp((e-e')/T)と定義されています。この式は、メトロポリス法から派生したものですが、焼きなまし法で特定の数式を使用する数学的な正当性はありません。焼きなまし法では近傍が順次評価されるため、状態sからs'に遷移する実際の確率はその式とは関係ありません。
焼きなましスケジュール
焼きなましスケジュールは、近傍関数ほど重要ではありませんが、注意して選択する必要があります。初期温度は、上り（エネルギーが増加する）遷移と下り（エネルギーが減少する）遷移の確率がほぼ同じになるように大きく設定する必要があります。一般的に温度は指数関数的に減少するようにスケジュールします。
擬似コード
以下に、焼きなまし法の擬似コードを示します。このコードは、初期状態startStateから開始して、maxIter回までステップを繰り返し、エネルギーがgoalE以下の解が見つかるまで動作します。
function 焼きなまし法(startState, maxIter, goalE)
state = startState
e = EVAL(state)
bestState = state
bestE = e
for (iter = 0; iter < maxIter; iter++)
nextState = NEIGHBOUR(state)
nextE = EVAL(nextState)
if nextE < bestE then
bestState = nextState
bestE = nextE
if bestE <= goalE then
return bestState
if random() <= PROBABILITY(e, nextE, TEMPERATURE(iter / maxIter)) then
state = nextState
e = nextE
return bestState
function PROBABILITY(e1, e2, t)
if e1 >= e2 then
return 1
else
return e^((e1 - e2) / t)
function TEMPERATURE(r)
return α^r
ここで、
EVAL(state)は状態stateの評価値（エネルギー状態）を返します。
NEIGHBOUR(state)は状態stateの近傍をランダムに1つ生成します。
TEMPERATURE(r)は焼きなましスケジュールに従って温度を返します（ここでは定数αのべき乗）。
PROBABILITY(e1, e2, t)は温度tのもとでエネルギーe1からe2への遷移確率を返します。
random()は0以上1以下の乱数を返します。
関連手法
タブーサーチ (TS): 焼きなまし法と同様に近傍探索を行う手法ですが、探索の堂々巡りを避けるために、すでに評価した解をタブーリストで管理します。
蟻コロニー最適化 (ACO): 多数の蟻（エージェント）を解空間に配置し、最適解を探索します。
遺伝的アルゴリズム (GA): 複数の解をプールし、突然変異や交叉によって新しい解を生成し、確率的な手法で解を選別します。
関連項目
量子焼きなまし法
最適化問題
マルコフ連鎖
組合せ最適化
シミュレーティド・エボリューション
巡回セールスマン問題
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。