R を準備しています…
機械学習の基礎(東京女子大学 2026年度後期)
第8回 シミュレーテッド・アニーリング等の最適化手法
管理

第8回 シミュレーテッド・アニーリング等の最適化手法

このページの使い方

  1. 画面上部の帯が緑になるまで待つ(Rの準備。初回は数十秒かかる)。
  2. 「導入ゲーム」で、霧の山の最高地点をめざす(2分)。
  3. Ⅰでしくみを読み、黒い枠のRプログラムを上から順に「▶ 実行」で動かす。
  4. Ⅰ-2 で名前の由来(金属の焼きなまし)を、Ⅰ-3 でほかの手法との比較を読む。
  5. Ⅲの例題を、ステップの順に実行する。
  6. Ⅳで、生成AIに自分のテーマのデータとプログラムを作らせて分析する。
  7. 最後の「課題用プログラム」で、データ作成 → プログラム → 実行 → 考察 を行い、レポートにまとめる。

黒い枠のプログラムは自由に書き換えてよい。「元のコードに戻す」で元に戻る。

今日の目標

  1. 「最適化」が、たくさんの候補の中から最も良い解を探す問題であることを説明できる。
  2. 山登り法が局所的最適解で止まる理由と、焼きなまし法がそれを乗り越えるしくみ(温度と受容確率)を説明できる。
  3. 焼きなまし法が金属の焼きなましと似ている点(エネルギー・温度・ゆっくり冷やす理由)と、似ていない点を説明できる。
  4. 山登り法・遺伝的アルゴリズムなどと比べた、焼きなまし法の長所と欠点を説明できる。
  5. 巡回経路問題(配達の順番)やナップサック問題(荷物の選択)を、Rで焼きなまし法を使って解ける。
  6. 見つかった解が「最適解とは限らない」ことを理解し、くり返し実行して安定性を確かめられる。
  7. 生成AIに作らせた自分の問題で同じ分析を行い、結果が妥当かを確かめられる。

導入ゲーム:霧の山で、いちばん高い所をめざせ

あなたは濃い霧に包まれた、起伏の激しい山地(約5 km 四方)の真ん中にいる。見えるのは足もとのまわり(半径70 m ほど)だけ。制限時間 2分 のうちに、できるだけ標高の高い地点にたどり着こう。

記録は「2分間に通った中でいちばん高い地点の標高」である(焼きなまし法が「これまでの最良解」をメモするのと同じ)。全員が同じ地形で競う。

操作キーボード画面のボタン(スマホ・タブレット)
1マス(20 m)歩く矢印キー、または W・A・S・D(押しっぱなしで歩き続ける。2つ同時押しでななめ)↑ ← → ↓ を押し続ける
大ジャンプ(半径約500 m 以内のどこかへ、でたらめに跳ぶ。4秒かかる)スペースキー、または J「大ジャンプ」
残り時間2:00
いまの標高— m
これまでの最高(記録)— m
全体の中での位置(地形は見えない)
名前を入れて「スタート」を押す。本番は全員いっせいにスタートしよう。終わるまで、となりの画面は見ないこと。
あなた記録の地点出発点★ 本当の最高峰(終了後に表示)

ランキング(本番の地形・1人1回目の記録)

まだ記録がない。

記録を消す(教員用)

ふり返り:ゲームの中に、今日の手法がすべて出てくる
ゲームでの行動対応する手法・用語このページで学ぶ場所
まわりで一番高い方へ、上りだけを選んで歩いた山登り法。近くの小さな峰(局所的最適解)で止まりやすいⅠ ステップ3
あえて下り坂を下りて、別の山をめざした焼きなまし法の「悪くなる動きも受け入れる」Ⅰ ステップ4
最初は大胆に、残り時間が減ったら近くを細かく温度を下げる(冷却スケジュール)Ⅰ ステップ5・6、Ⅰ-2
大ジャンプで、まったく別の場所からやり直したランダム・リスタートⅠ ステップ3のトリビア、Ⅰ-3
仲間と手分けして、良い場所の情報を持ち寄る(もしできたら)遺伝的アルゴリズム・粒子群最適化(集団で探す)Ⅰ-3、第9回

ゲームでは「高いほどよい」(最大化)だが、Ⅰ以降は「小さいほどよい」(最小化)で説明する。標高にマイナスを付ければ同じ問題になる(ステップ3の「ていねいに」)。

Ⅰ 最適化と焼きなまし法のしくみ

ステップ1最適化とは「いちばん良い答えを探す」こと

これまでの回は「データから予測する」手法だった。今回は、決まった評価基準のもとで、最も良い答え(解)を探す問題を扱う。これを最適化という。

問題解評価(小さいほどよい)候補の数
配達の順番(巡回経路問題)地点を回る順番移動距離の合計12地点で約2,000万通り
荷物の選択(ナップサック問題)各荷物を入れるか入れないか−(価値の合計)、容量超過は罰10個で1,024通り、50個で約1,000兆通り
時間割の作成各授業の時間と教室重なりや希望に合わない数天文学的な数
ニューラルネットの学習(第10回)重みの値予測の誤差無限(連続値)

候補をすべて調べれば必ず最適解が見つかる(全探索)が、候補の数が多すぎて現実には不可能なことが多い。そこで「十分に良い解を、現実的な時間で見つける」工夫が必要になる。

候補の数の爆発
図1 巡回経路の候補の数は、地点が増えると爆発する
ていねいに:なぜ「11! ÷ 2」通りなのか

12地点を回る順番を数えてみる。出発点は本店に決まっているので、残り11地点の並べ方を考えればよい。

  • 1番目に行く地点の選び方は11通り、2番目は残りから10通り、3番目は9通り……最後は1通り。
  • 全部掛けると 11×10×9×…×1 = 11!(11の階乗)= 39,916,800 通り。
  • ただし「本店→駅前→団地→…→本店」と、その逆回りは道のりがまったく同じなので、同じ経路とみなして 2 で割る。

よって 39,916,800 ÷ 2 = 19,958,400 通り(約2,000万通り)である。

たとえ話:1秒に1億通り調べられるコンピュータでも……
地点の数経路の数全部調べる時間(1秒に1億通り)
10約18万0.002秒
12(今日の例題)約2,000万0.2秒
15約436億約7分
20約6京(6×1016)約19年
30約4.4×1030約1,400兆年(宇宙の年齢の約10万倍)

地点を3つ増やすだけで時間が何千倍にもなる。宅配便のドライバーが1日に回る数十か所の順番を、全部調べて決めることはできない。だから「全部は調べずに、十分良い答えを見つける」方法が必要になる。

エピソード:100万ドルの懸賞がかかった問題

巡回セールスマン問題は、「NP困難」と呼ばれる難しい問題の仲間である。この仲間の問題を「地点が増えても現実的な時間で必ず最適解を出せる方法」があるかどうかは、P対NP問題という未解決問題と深く結びついている。アメリカのクレイ数学研究所は、2000年にこれを7つの「ミレニアム懸賞問題」の1つに選び、解いた人に100万ドルを出すとしている。今のところ、誰も受け取っていない。

トリビア:巡回セールスマン問題の歴史
最適化と焼きなまし法の歴史
図2 最適化と焼きなまし法の歴史
  • 巡回経路の問題は、1832年のドイツのセールスマン向け手引書に、すでに「どう回ると効率がよいか」として登場する。数学の問題として定義したのは1930年代のメンガーで、当時は「配達人問題」と呼ばれた。
  • 「巡回セールスマン問題」という名前が文書に初めて現れたのは、1949年の数学者ジュリア・ロビンソンの報告書である。
  • 1954年、ダンツィクらはアメリカの49都市を回る最短経路を「これより短い経路はない」という証明つきで求めた。コンピュータの力が上がった2006年には、85,900地点の最短経路が証明つきで解かれた(計算量はCPU 1台で136年分)。
  • 自然界にも「解く」ものがいる。アリは餌と巣の間に短い道を見つけ、粘菌は餌の間に効率のよい経路を作る。アリの行動をまねた「アントコロニー最適化」という手法もある。
ステップ2谷がいくつもある関数

まず、1つの数 x を動かして f(x) を最小にする問題で考える。下の関数には谷がいくつもあり、いちばん低い谷(大域的最適解)のほかに、まわりより低いだけの谷(局所的最適解)がある。

ていねいに:「局所的」と「大域的」
  • 局所的(きょくしょてき)=「その場所のまわりだけを見れば」という意味。局所的最適解は、すぐ近くと比べればいちばん低いが、全体ではもっと低い所がある谷である。
  • 大域的(たいいきてき)=「全体を見渡して」という意味。大域的最適解は、全体でいちばん低い谷である。

英語では local optimum(ローカル)と global optimum(グローバル)という。「ローカル線」「グローバル企業」の、あのローカルとグローバルである。

たとえ話:近所でいちばん安いスーパー

自分の家から歩いて行ける3軒のスーパーを比べて、いちばん安い店を見つけたとする。これは「局所的に」いちばん安い店である。でも、電車で2駅先には、もっと安い業務用スーパーがあるかもしれない。こちらが「大域的に」いちばん安い店である。

近所だけ見ていると「ここが一番だ」と満足してしまい、遠くのもっと良い店には気づけない。これが、このあと出てくる山登り法の弱点そのものである。

ステップ3山登り法:近所を見て、良ければ移る

いちばん単純な方法は、いまの解の近所(少しだけ変えた解)を試し、良くなるなら移ることをくり返す山登り法である(最小化なので「谷下り」だが、慣例でこう呼ぶ)。

霧の中の登山者
図3 たとえ:霧の中で、いちばん低い谷を探す。足もとしか見えない。

導入ゲームの「霧の山」と同じ状況である(ゲームは高い所、ここでは低い所を探す)。

ていねいに:最小化なのに「山登り」と呼ぶわけ

「いちばん大きい値を探す(最大化)」と「いちばん小さい値を探す(最小化)」は、符号を逆にすれば同じ問題になる。たとえば「点数を最大にする」は「−(点数)を最小にする」と同じである。このため、教科書によって山を登る話(最大化)で説明したり、谷を下る話(最小化)で説明したりする。名前は最大化の言い方が残ったものである。

このページでは、すべて「小さいほどよい」にそろえている。例題2(ナップサック問題)で価値に −1 を掛けているのも、この理由である。

ていねいに:下のプログラムの「近く」とは

近く <- function(x) x + rnorm(1, 0, 0.3) は、「いまの x に、平均0・標準偏差0.3 の正規分布の乱数を1つ足す」関数である。つまり、ほとんどの場合 −0.6〜+0.6 くらいの範囲で、左右どちらかに少しだけ動いた点を作る。これが「霧の中で1歩だけ足を出してみる」ことにあたる。

山登り法と局所的最適解
図4 山登り法は出発点に近い谷で止まる。焼きなまし法はときどき山を越える。

読み取り方:出発点が 4 のときだけ大域的最適解(3.12)にたどり着き、ほかは近くの谷で止まった。一度谷に入ると、まわりはすべて「悪くなる」動きなので抜け出せない。

ていねいに:なぜ「谷から出られない」のか

山登り法のルールは「良くなるときだけ移る」である。谷の底にいると、右に1歩出しても左に1歩出しても、必ず少し高く(悪く)なる。だから何百回試しても、すべての候補が却下される。隣の谷に行くには、いったん山を登らなければならないのに、そのルールがないのである。

山登り法が悪いのではない。谷が1つしかない問題なら、山登り法は速くて確実である。問題は「谷がいくつもある」ときだけ起きる。

たとえ話:「今がいちばん」の落とし穴

部活でもアルバイトでも、今の場所が「前よりは良い」と、そこから動かなくなりがちである。少しでも条件が下がる変化は、すべて断ってしまうからだ。でも、一時的に条件が下がる道(たとえば新しいことを一から始める)を通らないと、たどり着けない場所もある。山登り法は「一時的な損を絶対に受け入れない人」にあたる。

トリビア:山登り法の別名
  • 山登り法は英語で hill climbing。近所だけを調べて進むので、局所探索(local search)とも呼ばれる。例題3の optim も局所探索の一種である。
  • 山登り法を「出発点を変えて何回もやり直す」工夫は、ランダム・リスタートと呼ばれる。単純だが、実務ではかなり効く。ステップ7の比較でも、山登り法の「最良」は悪くないことに注目しよう。
ステップ4焼きなまし法の考え方:悪い動きも、ときどき受け入れる

金属を高温にしてからゆっくり冷やすと、原子が落ち着いた並びになり、丈夫な金属になる。この「焼きなまし」になぞらえたのが焼きなまし法(シミュレーテッド・アニーリング、SA)である。

金属の焼きなまし
図5 名前の由来:急に冷やすと原子がばらばらのまま固まり、ゆっくり冷やすと整う

→ 金属の中で何が起きているのか、なぜ似ているのかは、Ⅰ-2 で図を使ってくわしく説明する。

金属の焼きなまし焼きなまし法
温度が高い:原子が激しく動く温度が高い:悪くなる動きもよく受け入れる(広く探す)
ゆっくり冷やす温度を少しずつ下げる(冷却率を掛ける)
温度が低い:原子が落ち着く温度が低い:良くなる動きだけ受け入れる(山登り法と同じ)
箱を揺らすたとえ
図6 もう一つのたとえ:でこぼこの箱にボールを入れ、揺らし方をだんだん弱くする

でこぼこの箱にボールを入れて、はじめは強く揺らす。ボールは山を飛び越えて箱の中を動き回る。揺らし方をだんだん弱くすると、ボールは高い所に行けなくなり、深い谷にとどまる。最後にほとんど揺らさなければ、ボールは谷の底に落ち着く。「揺らしの強さ」が温度である。

たとえ話:中学理科の「火成岩」を思い出そう

マグマが冷えて固まった岩石を火成岩という。中学の理科で習ったとおり、

  • 地下深くでゆっくり冷えたマグマ → 花こう岩のような深成岩。結晶が大きく、よくそろう(等粒状組織)。
  • 地表近くで急に冷えたマグマ → 玄武岩のような火山岩。小さな結晶やガラス質の部分が多い(斑状組織)。さらに急に冷えると、黒曜石のようなガラスになる。

原子や分子は、時間をかけて冷やされると「いちばん落ち着く並び方(エネルギーが最も低い並び)」を見つけられる。急に冷やすと、途中のでたらめな並びのまま固まってしまう。焼きなまし法の「急に冷やすと途中の谷で止まる」は、これとまったく同じ話である。

トリビア:「焼きなまし」と「焼き入れ」は正反対
  • 焼き入れ:熱した鉄を水や油で急に冷やす。硬くなるが、もろくなる。日本刀の刃の硬さはこの工程で生まれる。
  • 焼きなまし(焼鈍=しょうどん):熱した金属を炉の中などでゆっくり冷やす。内部のゆがみが取れ、やわらかく粘り強くなる。加工しやすくするために行う。
  • ガラス工芸でも、作ったガラスを「徐冷炉」でゆっくり冷やす。急に冷やすと内部にゆがみが残り、あとで突然割れることがある。
悪くなる動きを受け入れる確率 = exp( − 悪くなる量 ÷ 温度 )
ていねいに:この式を1つずつ読む

(1) exp とは:exp(□) は「e の □ 乗」のことである。e = 2.718… という決まった数(ネイピア数)。大事な性質は次の3つだけ覚えればよい。

□ の値exp(□) の値意味
01確率100%
マイナスの数(−0.2、−1、−5 など)0 と 1 の間確率として使える
マイナスが大きくなる(−1 → −5 → −10)0 に近づく(0.37 → 0.007 → 0.00005)ほとんど起きない

(2) 「− 悪くなる量 ÷ 温度」の部分:悪くなる量はプラスの数なので、マイナスを付けると、かっこの中は必ず0以下になる。だから答えは必ず 0〜1 の間の確率になる。

(3) 具体的に計算してみる:悪くなる量が 1 のとき、

温度かっこの中受け入れる確率ひとことで
10−1 ÷ 10 = −0.10.905(約90%)ほぼ受け入れる
5−1 ÷ 5 = −0.20.819(約82%)だいたい受け入れる
1−1 ÷ 1 = −10.368(約37%)3回に1回くらい
0.2−1 ÷ 0.2 = −50.007(約0.7%)まず受け入れない

(4) 式が言っていることは、次の2つだけである。

  • 悪くなる量が大きいほど、受け入れにくい(大きな損はなかなか引き受けない)。
  • 温度が高いほど、受け入れやすい(はじめのうちは冒険する)。

この2つの性質を持つ式ならほかにも作れるが、物理の世界で原子のふるまいを正しく表す式が exp だったので、それをそのまま借りている(下のエピソード参照)。

ていねいに:「確率で受け入れる」はどうやってプログラムにするのか

プログラムの中では runif(1) < exp(-差 / 温度) と書いてある。runif(1) は 0〜1 の間の数をでたらめに1つ出す関数である。これは「0〜1 の数直線のどこかにダーツを投げる」ことにあたる。

受け入れる確率が 0.82 なら、数直線の 0〜0.82 の部分が「当たり」になる。ダーツがそこに刺さる確率は、ちょうど 82% である。下で試してみよう。

受け入れる確率 = exp( − 1.0 ÷ 5.0 ) = 0.819
0緑=当たり(受け入れる)/赤=はずれ(元の解にとどまる)1
差と温度を動かして、緑の部分の長さがどう変わるかを見よう。
ていねいに:「温度」は本物の温度ではない

焼きなまし法の「温度」は、℃ではない。exp の中で「悪くなる量 ÷ 温度」と割り算しているので、温度は悪くなる量と同じ単位を持つ。

  • 経路の問題なら、悪くなる量は km なので、温度も km で考える。「温度5」は「5 km くらい遠回りになる変更なら、まあ受け入れてもよい」という気前のよさを表す。
  • ナップサック問題なら、温度は「点」で考える。

だから、開始温度の目安は「1回の変更で悪くなる量と同じくらい」になる(ステップ5の表)。温度がそれより小さすぎると最初から山登り法と同じになり、大きすぎると最初のうちはただでたらめに動き回るだけになる。

受け入れ確率の表
図7 温度と「悪くなる量」の組み合わせごとの、受け入れる確率

読み取り方:温度5のときは、少し悪くなる動き(差0.5)を90%の確率で受け入れる。温度0.2では、同じ動きをほとんど受け入れない(8%)。

トリビア:焼きなまし法の生まれ
  • 「受け入れる確率 exp(−差÷温度)」の式は、1953年にメトロポリスらが物理の計算(原子の動きの模擬)のために考えた方法から来ている。この論文の著者5人のうち4人は、2組の夫婦だった(ローゼンブルース夫妻とテラー夫妻)。
  • これを「最適化」に使い、「焼きなまし法」と名付けたのは、1983年のカークパトリックらの論文(Science誌)である。彼らはコンピュータの回路の配置(部品をどう並べれば配線が短いか)と巡回セールスマン問題を例にした。
  • ほぼ同じ方法を、1985年にスロバキアのチェルニーも独立に発表している。良いアイデアは、同じ時期に別々の場所で生まれることがある。
エピソード:exp の式の「ふるさと」はボルツマンの墓

「温度が高いほど、エネルギーの高い(不安定な)状態も起こりやすい」という関係を exp の式で表したのは、19世紀オーストリアの物理学者ボルツマンである。この式は今も「ボルツマン分布」と呼ばれ、物理や化学の教科書に必ず出てくる。

ボルツマンの考え(物質は原子の集まりで、そのふるまいは確率で表せる)は、当時は激しく批判された。いまではウィーンの中央墓地にある彼の墓に、彼の名を冠したもう1つの有名な式 S = k log W(エントロピーの式)が刻まれている。焼きなまし法は、この物理の考え方をそっくり借りて、「原子」を「解」に、「エネルギー」を「評価の値」に読みかえたものである。

エピソード:MANIAC と、プログラムを書いた人

1953年のメトロポリスらの計算は、ロスアラモス研究所の初期の電子計算機 MANIAC(マニアック)で行われた。当時のコンピュータは部屋いっぱいの大きさで、今のスマートフォンよりはるかに遅い。

この論文の手法は、のちに筆頭著者の名をとって「メトロポリス法」と呼ばれるようになった。しかし後年の証言によれば、実際にプログラムを書いて計算を走らせたのは、共著者のアリアナ・ローゼンブルースだったとされる。彼女はこの分野を離れたあとも長く語られることが少なかったが、2020年に亡くなったときに、その功績が改めて紹介された。

ステップ5焼きなまし法の手順
焼きなまし法の流れ
図8 焼きなまし法の流れ
決めるもの意味目安
初期解出発点でたらめでよい
近傍(近所の解の作り方)解を少しだけ変える方法問題ごとに決める(ステップ8)
開始温度最初の温度「悪くなる量」と同じくらいの大きさ
冷却率1回ごとに温度に掛ける数0.99〜0.999(1に近いほどゆっくり)
回数くり返す回数温度が十分下がるまで
ていねいに:冷却率 0.998 とは、どのくらいの速さか

冷却率は「1回ごとに温度に掛ける数」である。温度5、冷却率0.998なら、

5 → 5×0.998 = 4.990 → 4.990×0.998 = 4.980 → …

と、毎回0.2%ずつ下がる。1回ではほとんど変わらないが、何百回もくり返すと大きく下がる。分かりやすい目安は「温度が半分になるまでの回数」である。

冷却率1回で下がる割合温度が半分になる回数温度5から3000回後の温度
0.910%約7回ほぼ0(10−137くらい)
0.982%約34回ほぼ0
0.991%約69回ほぼ0
0.9950.5%約138回約0.0000015
0.9980.2%約346回約0.012
0.9990.1%約693回約0.25

冷却率0.9は「7回ごとに温度が半分」なので、数十回でほぼ山登り法になってしまう。冷却率は 1 との差がわずかに見えても、くり返すと大きな違いになる。

トリビア:「70の法則」で暗算できる

お金の世界には「70の法則」がある。年利 r% で預けると、お金が2倍になるのは約 70÷r 年後、というものだ(年利2%なら約35年)。同じ計算が「半分になる」ほうにも使える。冷却率0.998は「1回0.2%減る」なので、70÷0.2 = 350回で温度が半分になる。上の表の346回とほぼ同じである。

ていねいに:なぜ「最良解」を別にメモしておくのか

焼きなまし法は、ときどきわざと悪い解へ移る。そのため、最後にいる解が、途中で一度通った解より悪いことがある。そこで、プログラムでは「いまいる解」とは別に、「これまでに見つけた中でいちばん良い解」を記録しておき、最後にそれを答えとして返す(関数 焼きなまし の中の 最良解、最良値)。

たとえ話:服屋さんめぐり

ショッピングモールで服を探すとき、気に入った服を見つけても、「もっと良いのがあるかも」と別の店にも行ってみる。その途中で、さっきより気に入らない店にも入る(悪い解へ移る)。でも、いちばん気に入った服がどの店の何だったかはメモしておく。最後に「やっぱり2軒目のあの服」と戻れるのはそのためである。

そして、はじめのうちは遠くの店まで気軽に見に行く(温度が高い)が、閉店時間が近づくと近くの店だけを見て決める(温度が低い)。焼きなまし法の動きは、この買い物のしかたによく似ている。

やってみよう:1歩ずつ動かす

赤い玉がいまの解、緑の点がこれまでの最良、だいだいの点は通った場所である。「1歩進める」を押すたびに、候補を1つ作り、受け入れるかどうかを「くじ」で決めるようすが下に表示される。

出発点: 開始温度: 冷却率:

「自動で進める」は800回で止まる。乱数しだいで、いちばん低い谷に着くことも着かないこともある(この設定ではおよそ半分)。何度か試そう。開始温度を 0.2 にすると、ほとんど山登り法と同じ動きになり、出発点の谷から出られない。冷却率 0.9 では温度がすぐ下がり、途中の谷で止まりやすい。

このページでは、この手順を 焼きなまし(初期解, 評価, 近傍, 回数, 開始温度, 冷却率) という関数にして用意してある。

ステップ6Rで焼きなまし法を動かす

山登り法では抜け出せなかった、いちばん遠い谷(出発点 8)から始める。

読み取り方:左の図では、最初は値が大きく上下している(悪い解も受け入れている)。温度が下がるにつれて落ち着き、最後は大域的最適解(3.12)にたどり着いた。

ていねいに:左の図の「3つの時期」
時期温度図の見た目していること
序盤(0〜500回くらい)高い上下に大きくギザギザ谷から谷へ自由に動き回り、全体を広く探す
中盤中くらいギザギザが小さくなる浅い谷からは出られるが、深い谷からは出にくくなる。良い谷にしぼっていく
終盤低いほぼ平ら山登り法と同じ。その谷の底まで細かく下りる

「最初は広く、だんだん狭く」が焼きなまし法の基本の形である。自分のデータで動かしたときも、推移の図がこの形になっているかを確かめるとよい(Ⅳのステップ4)。

ていねいに:set.seed(3) は何をしているのか

焼きなまし法は乱数(でたらめな数)を使うので、実行するたびに結果が変わる。set.seed(数) は、乱数の「出発点」を決める命令で、同じ数を指定すれば毎回同じ乱数の列が出る。授業で全員が同じ結果を見られるように使っている。

set.seed(3) を set.seed(10) などに変えると結果が変わる。何度か変えて試すと、焼きなまし法がいつも成功するわけではないことが分かる。

トリビア:コンピュータの「でたらめ」はにせもの

コンピュータは決まった計算しかできないので、本当のでたらめは作れない。実際には、でたらめに見える数を決まった計算式で次々に作っている(疑似乱数)。Rが標準で使う「メルセンヌ・ツイスタ」は、1997年に日本の松本眞さんと西村拓士さんが発表した方法で、同じ並びがくり返すまでの長さが 219937−1(6,000けた以上の数)もある。Pythonなど、世界中のソフトウェアで使われている。

冷やす速さを変えてみる

冷却の速さ
図9 冷却率と温度の下がり方

読み取り方:冷却率0.9では20回とも途中の谷で止まり、0.998では15回いちばん低い谷に着いた。ゆっくり冷やすほど成功しやすいが、時間がかかる。

たとえ話:テスト勉強の計画

試験範囲が広いとき、最初から1つの単元だけを深く勉強すると、ほかの単元に手が回らない(急に冷やす)。最初の数日は全体をざっと見て、どこが出そうか・どこが苦手かを広く探り(温度が高い)、試験が近づいたら重要な所にしぼって仕上げる(温度が低い)ほうがうまくいきやすい。ただし、広く探る期間が長すぎると、仕上げの時間が足りなくなる。冷却率の決め方は、この「探る時間」と「仕上げる時間」の配分の問題である。

エピソード:「必ず最適解に着く」冷やし方はあるが……

1984年、ゲマン兄弟(スチュアートとドナルド)は、温度を非常にゆっくり(回数の対数に反比例するくらい)下げれば、焼きなまし法は確率1で大域的最適解にたどり着くことを数学的に証明した。

ところが、その下げ方はあまりにも遅く、実際に使うと全探索より時間がかかってしまうことさえある。そこで実務では、このページのように「温度に0.99〜0.999を掛ける」速い冷やし方を使い、保証はあきらめて、十分良い解を速く得る。理論と実務の折り合いのつけ方がよく分かる例である。

ステップ7山登り法と焼きなまし法を比べる

どちらの方法も乱数を使うので、1回の結果では比べられない。出発点を変えて20回ずつ試す。

読み取り方:山登り法が大域的最適解に着いたのは20回中3回、焼きなまし法は10回だった。焼きなまし法でも必ず着くわけではない。回数を増やす・ゆっくり冷やす・何度か実行して最良を採るのが実務での使い方である。

ていねいに:なぜ1回ではなく20回試すのか

乱数を使う方法は、1回の結果が「たまたま」良かったり悪かったりする。サイコロを1回振って6が出ても、「このサイコロは6が出やすい」とは言えないのと同じである。20回試して「何回成功したか」「値がどれくらいばらつくか」を見て、はじめて手法どうしを公平に比べられる。

下の箱ひげ図は、20回分の結果の分布を表す。箱が低い位置にあり、箱が小さい(つぶれている)ほど、良い結果が安定して出ていることを意味する。赤い点線がいちばん低い谷の値である。

トリビア:「どんな問題にも最強の手法」はない

1997年にウォルパートとマクレディが示した「ノーフリーランチ定理」によると、あらゆる問題を平均すると、どの探索手法も性能は同じになる。ある問題で焼きなまし法が山登り法に勝つなら、別の問題では負けている。名前の由来は「ただのランチはない(タダより高いものはない)」ということわざである。だから、問題の性質(谷が1つか、たくさんあるか)を見て手法を選ぶことが大切になる。

ステップ8「近所の解」の作り方は問題ごとに決める

数値の問題では「少し足す」でよいが、順番や組み合わせの問題では、解を少しだけ変える方法を自分で決める必要がある。

近傍の作り方
図10 「近所の解」の作り方いろいろ
2-optによる近傍
図11 経路の近傍(2-opt):区間を逆順にすると、交差がほどける
問題近所の解の作り方このページの関数
数値の最小化少し足す・引く近く(ステップ3で定義)
巡回経路経路の一部を逆順にする(2-opt)経路の近傍
荷物の選択1つの荷物を入れる↔入れないに切り替える選択の近傍(例題2で定義)
なぜ2-optで「交差がほどける」のか:交差した2本の線を、区間を逆順にしてつなぎ直すと、必ず短くなる(三角形の「2辺の和は残りの1辺より長い」から)。だから最短の経路には交差がない。図に交差が残っていれば、まだ改善できる。
ていねいに:2-optを文字で追ってみる

6地点 A〜F を、A→B→C→D→E→F→A の順に回る経路があるとする。関数 経路の近傍 が、3番目から5番目(C〜E)を選んだとすると、その区間だけを逆順にする。

変更前:A → B → C → D → E → F

変更後:A → B → E → D → C → F

変わった「道」を数えてみよう。

  • なくなった道:B–C と E–F の2本
  • 新しくできた道:B–E と C–F の2本
  • C–D、D–E は向きが逆になっただけで、同じ道である。

つまり、経路のうち2本の道だけを付け替える変更になっている。「2-opt」の「2」は、この2本のことである。変更が小さいので、「近所の解」としてちょうどよい。

ていねいに:2つの地点を入れ替えるだけではだめなのか

「C と E を入れ替える」(A→B→E→D→C→F)という近傍も考えられる。上の例では、たまたま区間の逆順と同じ結果になるが、離れた2地点を入れ替えると、それぞれの前後の道が変わるので、最大4本の道が一度に変わる。変化が大きすぎると「近所の解」とは言いにくく、良い経路を少しずつ磨くのが難しくなる。2-optが定番なのはこのためである。

トリビア:2-opt、3-opt、そしてその先
  • 2-optは、1958年にクロースが巡回セールスマン問題の解き方として発表した。
  • 3本の道を付け替える「3-opt」もある(1965年、リン)。さらに、付け替える本数をその場で変える「リン=カーニハン法」(1973年)は、今でも巡回セールスマン問題の最強クラスの方法の土台になっている。
  • カーニハンは、プログラミング言語C の有名な入門書『プログラミング言語C』の著者の一人でもある。
ステップ9ほかの最適化手法との関係
探し方のいろいろ
図12 同じ景色を、手法ごとにどう探すか
手法考え方最適解の保証向いている問題
全探索すべての候補を調べるあり候補が少ない(数百万以下)
貪欲法その場で最も良い選択をくり返すなし速さ重視。おおまかな解でよいとき
山登り法近所で良ければ移るなし(局所解で止まる)谷が1つの問題
焼きなまし法悪い動きも温度に応じて受け入れるなし(確率的に近づく)谷が多い組み合わせ問題
遺伝的アルゴリズム(第9回)解の集団を進化させるなし谷が多い問題。解を組み合わせられるとき
勾配法(第10回)傾きの方向に下るなし(局所解)微分できる連続の問題

→ 長所と欠点のくわしい比較と、同じ地形で手法を競わせる実験は Ⅰ-3 にある。

トリビア:身近にある最適化
  • 宅配便の配達順やごみ収集車の経路は、巡回経路問題そのものである。配達先が数十か所になると、人の勘では最適に近い順番を決めにくい。
  • 時間割、シフト表、プロ野球の対戦日程も、「重なりや希望に合わない数」を最小にする最適化問題として解かれている。
  • テストの問題選びも最適化である。1973年には、学生が「解く問題を自分で選べる試験」の採点にナップサック問題の解き方が使われた。
たとえ話:「いつもの店」と「新しい店」

お昼ごはんの店を選ぶとき、いつもの店に行けばまず満足できる(活用)。新しい店に行くと、はずれることもあるが、もっと好きな店が見つかるかもしれない(探索)。

大学に入ったばかりのころは新しい店をどんどん試し、卒業が近づくと、お気に入りの店に通うようになる。これはまさに「温度を下げていく」焼きなまし法の動きである。機械学習では、この「探索と活用のバランス」が大きなテーマで、焼きなまし法の温度は、そのバランスを時間とともに変える仕組みだと言える。

エピソード:日本生まれの「量子アニーリング」

焼きなまし法は「熱で揺らして」山を越える。これに対し、量子力学の「トンネル効果」(粒子が山を飛び越えずにすり抜ける現象)を使って谷から抜け出す方法が量子アニーリングである。1998年、東京工業大学の門脇正史さんと西森秀稔さんが理論を発表した。

2011年にはカナダのD-Wave社がこの考えにもとづく専用の計算機を売り出し、話題になった。日本でも富士通の「デジタルアニーラ」や日立の「CMOSアニーリング」など、焼きなまし法の考え方を専用の回路で高速に実行する計算機が作られ、配送計画や工場の生産計画に使われている。

ステップ10よくある疑問
わざと悪い解に移るのは、遠回りでむだではないのか。
短い目で見るとむだだが、長い目で見ると必要である。谷を出て隣の深い谷に行くには、いったん山を登るしかない。焼きなまし法は「最終的に良い解に着く」ために、途中の損を計画的に受け入れている。しかも、通った中で最も良い解はメモしてあるので(ステップ5)、遠回りしても答えが悪くなることはない。
温度を下げずに、ずっと同じ温度で探してはだめなのか。
温度が高いままだと、良い谷に入ってもすぐに出て行ってしまい、谷の底まで下りられない。温度が低いままだと、山登り法と同じで最初の谷から出られない。「最初は広く探し、最後は1つの谷を細かく下りる」ために、温度を下げる必要がある。
見つかった解が本当にいちばん良いかは、どうすれば分かるのか。
一般には分からない。分かるのは、全探索ができる小さな問題(例題2のステップ2-3)か、特別な数学の方法で証明できる場合だけである。実務では、何回か実行して同じくらいの値が出るか(安定性)、ほかの手法より良いかを確かめて、「見つかった中で最も良い解」として報告する。
焼きなまし法とAI(機械学習)は、どう関係するのか。
機械学習の「学習」は、「予測の誤差が最も小さくなるパラメータを探す」最適化問題である(第10回のニューラルネットで扱う)。焼きなまし法は、こうした最適化の考え方を、谷がはっきり見える小さな問題で体験するのにちょうどよい。「局所的最適解」「探索と活用」「乱数に頼るので何回か試す」という考え方は、機械学習のあらゆる場面に出てくる。
開始温度と冷却率は、どう決めればよいのか。
決まった正解はなく、試して決める。目安は、①開始温度は「1回の変更で悪くなる量」と同じくらい、②冷却率は 0.99〜0.999、③回数は「最後の温度が開始温度の100分の1以下になる」くらい。推移のグラフを見て、序盤に上下し、終盤に落ち着いていれば、おおむね良い設定である。

Ⅰ-2 なぜ金属の「焼きなまし」に似ているのか

ステップ4で、名前の由来を表で簡単に見た。ここでは、金属の中で実際に何が起きているのかを図で順に追い、それが焼きなまし法のどの部分にあたるのかを確かめる。最後に、似ていない点(たとえの限界)も整理する。

2-1金属は「原子の並び」でできている

金属は、原子が規則正しく並んだ結晶でできている。ただし、現実の金属の並びは完全ではなく、原子が抜けたすき間(空孔)、並びのずれ(転位)、向きのちがう小さな結晶の境目(結晶粒界)などの欠陥がある。金属の硬さ・粘り・割れにくさは、この欠陥の量や形で大きく変わる。

① 高温(とけている・赤く熱い)原子が激しく動き回る。並びはばらばら② ①をゆっくり冷やす(焼きなまし)原子が整列する。乱れ(欠陥)が少ない③ ①を急に冷やす(急冷)途中の並びのまま固まる。向きのちがう小さな粒・すき間空いている所=空孔(原子のすき間)色=向きのそろった粒(結晶粒)線=原子の動き
図13 高温の状態から、ゆっくり冷やすか、急に冷やすかで、原子の並びが変わる(模式図)
  • ①高温:原子は熱によって激しくゆれ、場所を入れかわることもできる。どんな並びにも「なれる」状態である。
  • ②ゆっくり冷やす:原子は動ける時間のあいだに、少しずつ「落ち着く並び」に移っていく。欠陥が少ない、整った結晶になる。
  • ③急に冷やす:原子が並びかえる前に動けなくなる。そのときの途中の並びのまま固まり、欠陥やゆがみが多く残る。
2-2工場で行う「焼きなまし」の手順
時間 →温度原子が動き回れる高い温度室温① 加熱② 保つ③ 炉の中でゆっくり冷やす水や油で急に冷やす(焼き入れ)焼きなまし:やわらかく、粘り強く、内部のゆがみが少ない焼き入れ:硬いが、もろい・ゆがみが残る
図14 焼きなましと焼き入れの温度の変え方(模式図。実際の温度や時間は材料によって大きくちがう)

焼きなましは「①加熱 → ②その温度でしばらく保つ → ③炉の中でゆっくり冷やす」の3段階で行う。②で原子が十分に動いて並びかえる時間をとり、③で少しずつ動けなくしていく。目的は、加工でたまった内部のゆがみを取ること、金属をやわらかく、粘り強くして次の加工をしやすくすることである。

ていねいに:焼きなまし法の手順と1対1で対応している
工場の焼きなまし焼きなまし法(プログラム)
①加熱:原子が自由に動ける温度まで上げる開始温度を十分高くする(悪い動きもよく受け入れる)
②保つ:その温度で原子が並びかえる時間をとる温度をほとんど変えずに、何回も近所の解を試す
③ゆっくり冷やす冷却率を 1 に近くする(0.99〜0.999)
急に冷やす(焼き入れ・急冷)冷却率を小さくする/開始温度を 0 にする = 山登り法と同じ

焼きなまし法の論文では、温度をいきなり 0 にすることを、英語で急冷を意味する quench(クエンチ)と呼ぶことがある。つまり山登り法は「計算の世界の焼き入れ」にあたる。

トリビア:「なます」は「鈍す」
  • 「焼きなまし」は漢字で焼き鈍しと書く(専門用語では焼鈍=しょうどん)。「鈍す(なます)」は「鋭さをにぶくする・やわらかくする」という意味で、硬くなった金属をやわらかく戻すことを表している。
  • 英語の anneal は、古い英語で「火にかける・焼く」を意味する語から来ている。ガラスや金属を炉で処理する職人の言葉が、20世紀に計算の言葉になった。
2-3「エネルギー」という、ものさし

物理では、原子の並び方ごとにエネルギーという量が決まる。原子どうしがちょうどよい距離で整列しているほどエネルギーは低く、エネルギーが低い並びほど安定している(自然はエネルギーの低い状態に落ち着こうとする)。

ありうる並び方をすべて横1列に並べ、それぞれのエネルギーを高さで表すと、次のようなでこぼこの地形になる。これは、ステップ2の「谷の多い関数」とまったく同じ形の問題である。

原子の並び方(すべての並び方を、横1列に並べたと考える) → エネルギー(低いほど安定)→いちばん低い谷=きれいな結晶浅い谷=欠陥のある並び山の上=不安定な、途中の並び● 局所的に安定な並び ● いちばん安定な並び
図15 原子の並び方とエネルギーの地形(模式図)。焼きなまし法の「谷の多い関数」と同じ形をしている
  • いちばん低い谷=欠陥のない、きれいな結晶。最適化でいう大域的最適解。
  • 浅い谷=欠陥を含んだ並び。まわりと比べると安定なので、そこから自然には出にくい。最適化でいう局所的最適解。
  • 山の上=谷から谷へ移る途中の、不安定な並び。

金属をきれいな結晶にしたい職人と、最適解を探したいプログラマーは、同じ形の問題(でこぼこの地形で、いちばん低い谷を探す)に取り組んでいることになる。

2-4温度が決めるのは「どこにいやすいか」:ボルツマン分布

温度 T のとき、原子の集まりが「エネルギー E の並び」にいる確率は、exp( − E ÷ T )に比例する。これをボルツマン分布という(ステップ4のエピソード)。焼きなまし法の受容確率 exp( − 差 ÷ 温度)は、この分布を作り出すための仕組みである。

下のスライダーで温度を変えて、オレンジ色の「いやすさ」がどう変わるかを見よう。

温度 8(とても高い)いちばん低い谷にいる確率 13%温度 2いちばん低い谷にいる確率 28%温度 0.8いちばん低い谷にいる確率 51%温度 0.25(低い)いちばん低い谷にいる確率 82%黒い線:エネルギー(評価の値) オレンジ:その場所にいる確率(ボルツマン分布)
図16 温度ごとの「いやすさ」。温度が下がるほど、いちばん低い谷に集まる
ていねいに:図16から読み取れる2つのこと
  1. どの温度でも、低い谷ほど「いやすい」。exp( − E ÷ T )は、E が小さいほど大きいからである。
  2. 温度が下がるほど、その差が極端になる。温度8ではどの谷にも同じくらいいるが、温度0.25ではほぼ全員が「いちばん低い谷」に集まる。温度を 0 に近づけると、確率は限りなく 100% に近づく。

したがって、「各温度で十分に落ち着かせながら(ボルツマン分布になるまで待ちながら)、温度を 0 に近づける」ことができれば、いちばん低い谷に着く。これが焼きなまし法の理論上の根拠である。

読み取り方:最後の行は、温度 8, 2, 0.8, 0.25, 0.1 のときに、いちばん低い谷にいる確率である。温度を下げるほど 1(100%)に近づく。

2-5なぜ「ゆっくり」冷やさないといけないのか

2-4 の話には「各温度で十分に落ち着かせれば」という条件がついていた。ここが「ゆっくり」の理由である。

越える高さ ΔE浅い谷(いまいる所)深い谷(行きたい所)熱のゆれで、たまたま越える越えるまでの平均の待ち時間 ∝ exp( ΔE ÷ 温度 ) ※∝ は「比例する」
図17 浅い谷から深い谷へ移るには、山(高さ ΔE)を越えなければならない

谷にいる原子(や解)が隣の谷へ移るには、間の山を越える必要がある。熱によるゆれで山を越えるまでの平均の待ち時間は exp(ΔE ÷ 温度)に比例する(化学で習う「アレニウスの式」と同じ考え方)。具体的に計算すると、次のようになる。

山の高さ ΔE \ 温度温度 2温度 1温度 0.5
1(低い山)1.62.77.4
22.77.455
4(高い山)7.4552,981

数字は exp(ΔE ÷ 温度)。待ち時間の「倍率」の目安である。

ていねいに:この表が言っていること
  • 温度が高いうちは、高い山でも比較的すぐ越えられる。だから、あちこちの谷を行き来して「どの谷が深いか」を広く比べられる。
  • 温度を下げると、高い山から順に越えられなくなる(温度0.5で高さ4の山は、待ち時間が約3,000倍)。このとき、どの大きな谷にいるかが先に決まり、その後、谷の中の細かいでこぼこが決まっていく。「大まかな形が先、細部はあと」である。
  • 温度を急に下げると、山を越える前に動けなくなる。最初にいた谷、またはたまたまいた谷で固まってしまう。これが急冷で欠陥が残る理由であり、山登り法が局所的最適解で止まる理由でもある。

やってみよう:200個の玉を、ゆっくり冷やす/急に冷やす

200個の玉(原子、または200本の焼きなまし法)を地形の上にでたらめに置き、全部を同時に焼きなまし法で動かす。冷やし方だけを変えて、最後にいちばん低い谷に何個集まるかを比べよう。

ボタンを押すと始まる(6,000回くり返す。数秒かかる)。

結果の目安(筆者が各5回試した平均):ゆっくり冷やすと約60%、急に冷やすと約25%、温度0では約20%の玉が、いちばん低い谷に集まった。ゆっくり冷やしても100%にはならないのは、6,000回では「十分にゆっくり」とは言えないためである(ステップ6のエピソード)。

2-6対応関係のまとめ
金属の焼きなまし(物理)焼きなまし法(計算)原子の並び方(配置)解(経路・荷物の選び方・x の値)エネルギー評価の値(小さいほどよい)温度温度(悪い動きをどれだけ許すかのつまみ)熱による原子のゆれ近所の解を作り、確率で受け入れるその温度でしばらく保つ同じくらいの温度で何回もくり返すゆっくり冷やす冷却率を 1 に近くするきれいな結晶(いちばん低いエネルギー)大域的最適解欠陥・ガラス(途中で固まった並び)局所的最適解
図18 金属の焼きなましと焼きなまし法の対応
エピソード:カークパトリックらが思い描いたのは「結晶を育てる」実験

1983年の論文で、カークパトリックらは、物質のいちばん安定な状態を調べる実験として「融かした物質から単結晶を育てる」ことを例にあげた。物質をいったん融かし、温度をゆっくり下げ、特に固まり始める温度の近くで長い時間をかける。急に冷やすと、結晶にならずに欠陥だらけの状態やガラスになってしまう。彼らは、この「注意深い焼きなまし」をコンピュータの中でまねれば、回路の配置のような組み合わせの問題でも良い解が得られると考えた。

「固まり始める温度の近くで時間をかける」という考えは、焼きなまし法でも有効である。ステップ6の推移の図で言えば「中盤」の時期で、ここで良い谷が選ばれる。冷却を工夫する研究の多くは、この時期にどれだけ時間を使うかを調整している。

2-7似ていない点:たとえの限界

名前は物理から借りているが、まったく同じではない。次の表の左右のちがいを知っておくと、「温度」などの言葉を誤解しにくい。

観点金属の焼きなまし焼きなまし法
動くものばく大な数の原子が同時に動くふつうは解1つを順番に動かす(2-5の200個の玉は、200本を同時に走らせた特別な例)
温度実在の量(℃、K)。材料ごとに意味のある温度が決まっている評価の値と同じ単位を持つ調整つまみ。問題ごとに自分で決める
動き方自然法則で決まっている「近所の解」の作り方を人が設計する(ステップ8)。設計しだいで性能が大きく変わる
最良の記録金属は、途中で一番良かった並びを覚えていないこれまでの最良解をメモしておける(ステップ5)
目的やわらかさ・ゆがみの除去など。完全な結晶を作ることが目的とは限らない評価の値が最も小さい解(最適解)を見つけること
急冷の結果鋼の焼き入れで硬くなるのは、急冷で特別な結晶構造(マルテンサイト)ができるため。単に「並びが乱れる」だけではない温度0=山登り法。近くの谷で止まる
まとめると、焼きなまし法が物理から借りたのは「悪くなる変化を、温度に応じた確率 exp(−差÷温度)で受け入れ、温度を少しずつ下げる」という一点である。それ以外の部分(近所の作り方、温度の単位、最良解のメモ)は、計算のために作り変えられている。

Ⅰ-3 ほかの手法と比べた、焼きなまし法の長所と欠点

ステップ9の表を、もう少しくわしく見る。最初に結論を表にまとめ、そのあと図と実験で理由を確かめる。

3-1結論の一覧(目安)
観点全探索山登り法山登り法+
ランダム・リスタート
焼きなまし法タブー探索遺伝的
アルゴリズム
勾配法
作りやすさ(プログラムの短さ)◎◎◎○△△○
調整するつまみの少なさ◎◎○△△×○
局所的最適解から抜け出す力—×○◎◎○×
谷が多い問題での解の良さ◎×○○○○△
大きな問題でも計算が終わるか×◎◎○○○◎
複数のコンピュータで手分けしやすいか◎△◎△△◎△
最適解の保証◎××△×××
使える問題候補が少ない問題「近所の解」が決められれば、連続でも組み合わせでも主に組み合わせ連続・組み合わせ微分できる連続の問題

◎ とても良い ○ 良い △ 問題による・工夫が必要 × 苦手。これは一般的な傾向をまとめた目安(筆者の評価)で、問題や設定しだいで入れかわる(ステップ7のノーフリーランチ定理)。焼きなまし法の「最適解の保証 △」は、「無限にゆっくり冷やせば確率1で最適解に着く」という理論があるが、現実には使えない(ステップ6のエピソード)という意味である。

3-2それぞれの手法の「探し方」を図で比べる
山登り法近くの谷に下りて止まるランダム・リスタート出発点を変えて何度もやり直す焼きなまし法山を越えながら、だんだん落ち着くタブー探索××××××××××××最近いた所を「禁止」にして先へ進む遺伝的アルゴリズム○ 第1世代 ● 第25世代集団で探し、良い解どうしを組み合わせる勾配法(第10回)傾きの向きに、まっすぐ下りる○=出発点 ●=最後にいた所(どれも「小さいほどよい」最小化。いちばん低い谷は中央やや右)
図19 同じ「谷の多い関数」を、手法ごとに探したようす(実際にプログラムで動かした結果)
手法ひとことで局所的最適解からの抜け方決めるもの(つまみ)
山登り法良くなるときだけ移る抜けられない近所の作り方
ランダム・リスタート山登り法を、出発点を変えて何回も別の場所からやり直す近所の作り方、やり直しの回数
焼きなまし法悪い動きも、温度に応じた確率で受け入れる確率的に山を越える近所の作り方、開始温度、冷却率、回数
タブー探索近所でいちばん良い解へ移る。ただし最近いた解には戻らない戻れないので、押し出されるように先へ進む近所の作り方、禁止リストの長さ
遺伝的アルゴリズム解の集団を、選択・交叉・突然変異で世代交代させる集団のどこかが別の谷にいれば移れる集団の大きさ、交叉・突然変異の確率、選び方、世代数
勾配法傾き(微分)の向きに下りる抜けられない(出発点を変える工夫が必要)1回に進む幅(学習率)
トリビア:それぞれの手法の生まれ
  • 遺伝的アルゴリズム:アメリカのホランドが1975年の本『自然・人工システムにおける適応』で体系化した。生物の進化をまねている。
  • タブー探索:1986年にグローバーが提案した。「タブー(禁止)」は、最近いた解を禁止リストに入れることから。
  • 粒子群最適化(PSO):1995年にケネディとエバーハートが提案した。鳥や魚の群れが、仲間の情報を使いながらえさを探す動きをまねている。
  • 遺伝的アルゴリズムなどの「進化的な方法」は、NASAの人工衛星(2006年打ち上げの Space Technology 5)のアンテナの形を設計するのにも使われた。人間なら思いつかない、ねじれた針金のような形になった。
3-3焼きなまし法の長所と欠点
長所
  1. 作りやすい:必要なのは「評価の値を計算する関数」と「近所の解を作る関数」の2つだけ。このページの関数 焼きなまし も十数行である。
  2. 局所的最適解から抜け出せる:悪くなる動きを確率で受け入れるので、山を越えられる。
  3. どんな問題にも使いやすい:順番(経路)、組み合わせ(荷物)、数値(x)のどれにも、近所の作り方を変えるだけで使える。微分も要らない。
  4. 記憶が少なくてすむ:持っておく解は「いまの解」と「最良解」の2つだけ。
  5. 理論の裏づけがある:十分ゆっくり冷やせば最適解に近づくことが証明されている(実用上の速さとは別)。
  6. 制約を「罰」で入れられる:容量オーバーなどを評価の値に足すだけでよい(例題2)。
欠点
  1. つまみの調整が必要:開始温度・冷却率・回数で結果が大きく変わる。良い値は問題ごとに試して決めるしかない(ステップ6)。
  2. 時間がかかる:ゆっくり冷やすほど良いが、そのぶん評価の計算回数が増える。評価1回の計算が重い問題(シミュレーションが必要な問題など)では使いにくい。
  3. 実行ごとに結果がちがう:乱数を使うので、何回か実行して確かめる必要がある(ステップ7)。
  4. 解の良さの保証がない:見つかった解が最適か、最適からどれくらい離れているかは分からない。
  5. 1本の探索なので手分けしにくい:1つの解を順番に動かすので、たくさんのコンピュータで同時に計算する効果が出にくい(工夫した方法はある:3-6)。
  6. 良い解どうしの情報を組み合わせない:過去に見つけた別の良い解の「良い部分」を使うことはしない。ここが遺伝的アルゴリズムとの大きなちがいである。
3-4焼きなまし法と遺伝的アルゴリズム(第9回)のちがい
焼きなまし法:解は1ついまの解(1=その荷物を入れる)1010110010↓ 1か所だけ切りかえる(近所の解)候補1010100010↓ 良ければ移る。悪くても 確率 exp(−差÷温度) で移る1回に調べるのは1つ。ほかの解の情報は使わない。遺伝的アルゴリズム:解の集団親A(良い解)1010110010親B(良い解)0111001101切れ目↓ 交叉:前半はA、後半はBから受けつぐ子1010101101↓ 突然変異:まれに1か所を切りかえる子(突然変異のあと)1010101111良い解どうしの「部品」を組み合わせられる。そのかわり、集団の数だけ計算が必要。
図20 新しい解の作り方のちがい(例題2のナップサック問題で、1=その荷物を入れる、0=入れない)
観点焼きなまし法遺伝的アルゴリズム
持っている解1つ集団(数十〜数百)
新しい解の作り方いまの解を少しだけ変える(近所)2つの親を組み合わせる(交叉)+少し変える(突然変異)
悪い解の扱い温度に応じた確率で受け入れる悪い解は次の世代に残りにくい(選択)
探す範囲を変える仕組み温度を下げる(最初は広く、だんだん狭く)集団がだんだん良い所に集まる
得意な問題解を少しずつ変えると評価も少しずつ変わる問題解をいくつかの「部品」に分けられ、良い部品の組み合わせで良い解になる問題
起きやすい失敗冷やすのが速すぎて、途中の谷で止まる集団が早いうちに1つの谷に集まり、みんな同じ解になる(早熟収束)
つまみ開始温度・冷却率・回数集団の大きさ・交叉率・突然変異率・選び方・世代数
ていねいに:「交叉が効く問題」と「効かない問題」

交叉は、親Aの良い部分と親Bの良い部分を合わせれば、もっと良い子ができることを期待している。ナップサック問題では、「テントと寝袋を入れる」という良い部分と「救急箱とカメラを入れる」という良い部分を合わせられるので、交叉が効きやすい。

一方、巡回経路問題で「前半はAの順番、後半はBの順番」とそのままつなぐと、同じ地点を2回通ったり、通らない地点が出たりして、経路として成り立たない。そのため、経路の問題では特別な交叉の方法が必要になる。焼きなまし法の2-opt(ステップ8)のような「少しだけ変える」方法のほうが、素直に使える場面も多い。

3-5実験:霧の山の地形で、5つの手法を比べる

導入ゲームの「本番」の地形で、5つの手法に同じ回数だけ標高を調べさせ、最高峰(2,400 m)の頂上付近(50 m 以内)に着けた割合を比べる。ゲームと同じく「高いほどよい」問題である。各手法を30回ずつ実行する。

標高を調べる回数:
ボタンを押すと始まる(数秒かかる)。回数を変えて、2回試そう。
手法このページでの設定
でたらめ探索地図のどこか1点をでたらめに選ぶことをくり返す
山登り法出発点(地図の中央)から。近所=いまの地点から平均 約500 m 以内のどこか1点。高くなれば移る
山登り法+ランダム・リスタート60回続けて高くならなかったら、でたらめな地点からやり直す
焼きなまし法出発点(中央)から。近所は山登り法と同じ。開始温度 800 m、最後の温度 2 m
遺伝的アルゴリズム30地点の集団。2つの親の「あいだ」の地点に子を作る(交叉)。半分の子は近所へずらす(突然変異)
結果の読み取り方(筆者が各200回試したときの結果)
手法1,500回のとき4,000回のとき読み取れること
でたらめ探索15%40%回数を増やせば少しずつ当たるが、効率は悪い
山登り法25%29%回数を増やしてもほとんど伸びない。局所的最適解で止まっているから
山登り法+リスタート60%95%この地形では非常に強い
焼きなまし法61%81%回数を増やすと、ゆっくり冷やせるので伸びる
遺伝的アルゴリズム82%82%少ない回数で強いが、増やしても伸びない(早熟収束)
  • 事実:この地形・この設定では、焼きなまし法は山登り法よりはっきり良いが、いつも1位ではない。少ない回数では遺伝的アルゴリズム、多い回数ではランダム・リスタートのほうが良かった。
  • 理由の推測:この地図は2次元(東西・南北)で、全部で約6.5万地点しかない。「でたらめな場所からやり直す」だけで地図の大部分を調べられるので、ランダム・リスタートが有利になる。巡回経路問題のように候補が天文学的に多い問題では、でたらめなやり直しはほとんど当たらず、焼きなまし法のように「良い解を少しずつ磨く」方法が有利になりやすい。
  • 教訓:手法の優劣は、問題と設定で入れかわる(ノーフリーランチ定理)。実務では、いくつかの手法を同じ条件(同じ計算回数)で比べてから選ぶ。
3-6どの手法を選ぶか、組み合わせるか
Q1 候補の数は、全部調べられるくらい少ない?はい全探索Q2 「最適であることの証明」が必要?(式で書ける・時間に余裕がある)はい厳密解法(整数計画法・分枝限定法)※専用ソフトを使うQ3 なめらかな連続の問題で、傾き(微分)が計算できる?はい勾配法(第10回)谷が多ければ、出発点を変えて何回かQ4 良い解どうしの「部品」を組み合わせると良くなりそう?はい遺伝的アルゴリズム(第9回)いいえいいえいいえいいえ焼きなまし法・タブー探索(評価と「近所の解」さえ決めれば使える)時間があれば、何回か実行して最良を採る/ランダム・リスタートと比べる
図21 手法の選び方の目安(筆者のまとめ。実際には迷ったら複数を試して比べる)

実際の研究や実務では、手法を組み合わせることも多い。

組み合わせしくみねらい
遺伝的アルゴリズム+局所探索(メメティック・アルゴリズム)交叉で作った子を、山登り法や焼きなまし法で少し磨いてから集団に戻す「広く探す」と「細かく仕上げる」の両立
レプリカ交換法(並列テンパリング)温度のちがう焼きなまし法を何本も同時に走らせ、ときどき解を交換する焼きなまし法の「手分けしにくい」欠点をおぎなう
焼きなまし法を何回か実行して最良を採る出発点や乱数を変えて数回実行結果のばらつきをおさえる(例題1・2のステップでも行った)
エピソード:コンピュータの中の回路は、今も「焼きなまし」で並べられている

カークパトリックらが最初の例にした「回路の部品の配置」は、今も焼きなまし法の代表的な使い道である。たとえば、FPGA(あとから回路を書きかえられる半導体)の研究で広く使われている配置ツール「VPR」は、部品の置き場所を決めるのに焼きなまし法を使っている。部品の数は何万〜何十万にもなるが、「2つの部品の場所を入れかえる」という単純な近所の作り方で、配線の短い配置を見つけている。

Ⅱ 例題データ

名前内容使う場所
配達先12か所の地点の名前と位置(横・縦、km)。授業用の架空の町Ⅰ(操作教材)、例題1
荷物、容量10個の荷物の重さ(kg)と価値(点)。容量は20kg例題2

このページで用意した関数:経路の長さ()、経路を描く()、経路の近傍()、山登り()、焼きなまし()。データを書き換えてしまったときは、ページを再読み込みすると元に戻る。

Ⅲ 例題1:配達の順番を決める(巡回経路問題)

本店を出発して11か所に配達し、本店に戻る。移動距離が最も短くなる順番を探す。これは巡回セールスマン問題と呼ばれる有名な問題で、地点が増えると全探索は不可能になる。

やってみよう:経路が短くなるようすを見る

「山登り法を100回」を何度か押すと、やがて1回も移れなくなる(局所的最適解)。「番号順に戻す」のあと「焼きなまし法」を試して、最良の長さを比べよう。見つかっている最短は 36.24 km である。

ステップ1-1データと、番号順の経路を見る

見るところ:番号順に回ると経路が何度も交差し、長い。12地点でも候補は約2,000万通りある。

ステップ1-1b貪欲法(最近傍法)で作る

いちばん素朴な作り方は、「いまいる地点から、まだ行っていない最も近い地点へ進む」をくり返す最近傍法である。これは貪欲法の一種で、一瞬で経路ができる。

読み取り方:番号順(約60 km)よりずっと短いが、最後のほうで遠くに残った地点へ大きく戻るため、39.52 km にとどまる。図に交差が残っていることを確かめよう。山登り法・焼きなまし法は、この経路を出発点にしてもよい。

たとえ話:夏休みの宿題を「楽な順」にやる

最近傍法は、「いまいちばん近い所へ行く」をくり返すだけなので、先のことを考えない。夏休みの宿題を、その日にいちばん楽なものから片付けていくと、最初は順調でも、最後に面倒な自由研究と読書感想文がまとめて残って苦しくなる。最近傍法の「最後に遠くの地点へ大きく戻る」は、これと同じことが起きている。

貪欲法(どんよくほう、greedy)の「貪欲」は「目先の得に飛びつく」という意味である。速くてそこそこ良い答えを出すが、最適とは限らない。

ステップ1-2山登り法で改善する

読み取り方:左の図では、長さが階段状に下がって途中で止まる(それ以上良くなる近傍がない=局所的最適解)。

ていねいに:なぜ「階段状」になるのか

毎回の候補は、2-optで区間をでたらめに選んで作る。ほとんどの候補は今より長くなるので却下され、そのあいだ長さは変わらない(階段の平らな部分)。たまに短くなる候補が見つかると、そこへ移って長さが一段下がる(階段の段差)。経路が良くなるほど「短くなる候補」は減るので、段差の間隔はだんだん広がり、最後は平らなまま動かなくなる。

ステップ1-3焼きなまし法で探す

読み取り方:最初のうちは長さが上下するが、やがて山登り法より短い経路(36.24 km)に落ち着いた。図の経路に交差がないことを確かめよう。

ていねいに:開始温度 5 は、この問題に合っているか

12地点の経路で、2-optを1回行うと、長さはだいたい数km変わる。開始温度5は「5 km くらい長くなる変更でも、はじめのうちは37%くらいの確率で受け入れる」ことを意味する(exp(−5÷5) = 0.37)。「悪くなる量と同じくらい」という目安どおりの設定である。地点の範囲が100 km四方の問題なら、悪くなる量も大きくなるので、開始温度も大きくする必要がある。

ステップ1-410回ずつ試して、安定性を比べる

読み取り方:山登り法は最良では焼きなまし法と並ぶが、平均と最悪が悪い(出発点によって結果が変わる)。焼きなまし法は10回とも36〜37 kmに収まった。

Ⅲ 例題2:荷物を選ぶ(ナップサック問題)

容量20kgのリュックに、価値の合計が最も大きくなるように荷物を選ぶ。解は「入れる/入れない」の並びである。

ステップ2-1データと解の表し方
ステップ2-2評価と近傍を決めて、焼きなまし法で解く

焼きなまし法は「小さいほどよい」値を扱うので、価値の合計に−1を掛ける。容量を超えた解には大きな罰を加える。

ていねいに:評価の値を表にすると
解の例重さ価値評価の値(小さいほどよい)
何も入れない0 kg00
テント・食料・水18 kg26−26
最適解(価値38)20 kg 以下38−38(いちばん小さい)
全部入れる37 kg(17 kg オーバー)57100 + 17×10 = 270

価値を最大にする問題が、「評価の値を最小にする」問題に変わっていることを確かめよう。

ていねいに:なぜ「禁止」ではなく「罰」にするのか

容量オーバーの解を「絶対に選ばない(禁止)」にする方法もある。しかし、焼きなまし法では、いったん少しオーバーして、そこから別の荷物を出すという回り道が、良い解への近道になることがある。たとえば「寝袋を出してテントを入れたい」とき、1つずつしか入れ替えられないので、「テントを入れる(一時的にオーバー)→ 寝袋を出す」の2歩が必要になる。

そこで、オーバーした解も一応は候補として認め、そのかわり評価に大きな罰点を足して「とても悪い解」として扱う。これをペナルティ法という。罰を「100+オーバーした量×10」としたのは、次の2つのためである。

  • 荷物の価値は全部足しても57なので、評価の値は最も良くても −57。罰を100以上にすれば、オーバーした解は「何も入れない解(0)」よりも必ず悪くなる。最終的な答えにオーバーした解が選ばれることはない。
  • 「×10」の部分で、少しのオーバーより大きなオーバーのほうが悪くなる。少しオーバーした解から容量内に戻りやすくなる。
たとえ話:駐車違反の反則金

道路の「駐車禁止」は、車が物理的に止まれないわけではない。止めることはできるが、反則金という罰がある。罰が十分に大きければ、ふつうはだれもそこに止め続けようとはしない。ペナルティ法は、これと同じように「入ってもいいが、損をする」場所として、容量オーバーの領域を扱っている。

ステップ2-3全探索で本当の最適解を確かめる

荷物が10個なら候補は1,024通りなので、すべて調べられる。

ていねいに:なぜ 210 = 1,024 通りなのか

荷物1つごとに「入れる/入れない」の2通りがある。荷物が2個なら 2×2=4通り(両方入れる・1つ目だけ・2つ目だけ・どちらも入れない)、3個なら 2×2×2=8通り。10個なら 2 を10回掛けて 1,024 通りである。

荷物が1個増えるごとに候補は2倍になる。紙を半分に折るたびに厚さが2倍になり、0.1 mm の紙を42回折ると月まで届く厚さになる、という話を聞いたことがあるだろうか(ふつうの紙は、実際には7〜8回くらいしか折れないが)。荷物50個で約1,000兆通りになるのも、この「倍々ゲーム」のためである。

読み取り方:焼きなまし法が見つけた解(価値36)は、最適解(価値38)より少し劣っていた。焼きなまし法の解は最適解とは限らない。ステップ2-2の回数や開始温度を変えて、最適解にたどり着くか試してみよう。荷物が50個なら全探索は不可能なので、こうした近似手法に頼ることになる。

ステップ2-4貪欲法で解く:「割安な順」に詰める

ナップサック問題の貪欲法は、「重さ1kgあたりの価値」が高い順に、入る限り詰めていく方法である(1957年にダンツィクが提案)。

読み取り方:この問題では、貪欲法でも最適解(価値38)になった。ただし貪欲法はいつも最適とは限らない。たとえば容量10kgで、A(6kg・価値9)、B(5kg・価値7)、C(5kg・価値7)なら、貪欲法は割安なAを先に入れて価値9で終わるが、最適はB+Cの価値14である。

たとえ話:旅行のスーツケース

旅行の荷造りで「小さくて役に立つもの」から詰めていくのは、だれでも自然にやる貪欲法である。たいていはうまくいくが、最後に「大きいけれど絶対に必要なもの」が入らなくなることがある。そんなとき人は、いったん詰めたものを出して入れ直す。この「出して入れ直す」が、焼きなまし法の「一時的に悪い状態を受け入れる」ことにあたる。

トリビア:ナップサック問題と暗号

1978年、マークルとヘルマンは、ナップサック問題が難しいことを利用した暗号(ナップサック暗号)を発表した。「荷物の重さの合計だけを知らされても、どの荷物を入れたかは分からない」という性質を、秘密を守るのに使ったのである。ところが数年後、シャミア(RSA暗号の「S」の人)が、この暗号の弱点を突いて解読する方法を示した。問題そのものは難しくても、作り方にすきがあると解けてしまうという教訓として知られている。

ステップ2-5回数・開始温度・冷却率を変えて試す

焼きなまし法が最適解にたどり着く割合は、設定によって変わる。12通りの設定で10回ずつ試す(少し時間がかかる)。

読み取り方:開始温度が高く、ゆっくり冷やす設定(開始温度10・冷却率0.998)が最もよく最適解に着く。開始温度2では、罰(容量超過で100以上)の山を越えられず、ほとんど着かない。開始温度は「悪くなる量」と同じくらいという目安(Ⅰのステップ5)の意味がここで分かる。

Ⅲ 例題3:2変数の関数の最小化(GenSAパッケージ)

Rには焼きなまし法のパッケージ GenSA がある。谷がたくさんある2変数の関数で、ふつうの最適化関数 optim(局所探索)と比べる。

ていねいに:2変数になると何が変わるのか

これまでは x だけを動かす「1本の道の上の谷」だった。2変数では x と y の2つを動かすので、地図の上の谷になる。下のプログラムの図は、地形図(等高線)と同じ見方をする。色の違いが高さ(関数の値)を表し、等高線で囲まれた小さな輪の1つ1つがくぼみである。

この関数は、ゆるやかなおわん形(真ん中が低い)の上に、たまごパックのような小さなくぼみがたくさん並んだ形をしている。小さなくぼみの1つ1つが局所的最適解で、おわんの真ん中(原点)が大域的最適解である。

ていねいに:optim と GenSA
  • optim は R に最初から入っている最適化関数で、何も指定しないと「ネルダー=ミード法」という局所探索を使う。三角形を伸ばしたり縮めたりしながら、坂を下る方向へ転がしていく方法である。速いが、出発点の近くの谷で止まる。
  • GenSA は Generalized Simulated Annealing(一般化焼きなまし法)の略である。このページの 焼きなまし 関数より工夫が多く、温度の下げ方や近所の解の作り方を自動で調整する。lower、upper で探す範囲を、max.time = 2 で「最大2秒まで探す」ことを指定している。
ステップ3-1局所探索と焼きなまし法を比べる

読み取り方:出発点 (4, 4) から始めると、optim は近くの谷(値1.94)で止まり、GenSA は原点の大域的最適解(値0)にたどり着いた。

Ⅳ 自分の興味のあるデータで分析する

このページの生成AIに、データとRのプログラムを作らせて実行する。上から順にボタンを押していけばよい。

最初にボタンを押したとき、授業用パスコードを聞かれる。授業で伝えたものを入力する。

ステップ1テーマを決めて、データを作らせる

テーマの例:観光地めぐり/宅配の配達先/学校の各教室/お祭りの屋台

テーマ:  地点の数:

追加の希望(なくてよい):

(30秒〜1分ほどかかる)
ステップ2分析のプログラムを書かせる
(20〜40秒ほどかかる)
ステップ3プログラムを実行する

ステップ2のプログラムが下の枠に入る。「▶ 実行」を押す。プログラムは自分で書き換えてもよい。

エラーが出たら: (直したプログラムが上の枠に入るので、もう一度「▶ 実行」を押す)

ステップ4結果が妥当かを確かめる
観点確かめ方
経路の長さは短くなったか番号順の経路と比べて、山登り法・焼きなまし法でどれだけ短くなったか
焼きなましの推移の形最初は上下に揺れ、後半で落ち着いているか。揺れないなら開始温度が低すぎ、最後まで揺れるなら冷却率が大きすぎる
安定しているか初期解を変えた5回で、結果の長さのばらつきは小さいか。山登り法と比べてどうか
図は妥当か描いた経路に交差(×の形)が残っていないか。残っていれば、回数を増やすと改善することが多い
結果を言い過ぎていないか見つかった経路が「最短」とは限らない。「見つかった中で最も短い」と言う
(参考)生成AIに送った指示文を見る

データを作る指示

(まだ送っていません)

プログラムを書く指示

(まだ送っていません)

課題

このページの最後にある「課題用:生成AIで経路の最適化」を利用して、自分で決めたテーマのデータ(生成AIを利用して良い)で焼きなまし法による巡回経路の最適化を行い、その結果を3ページ程度のレポートにして提出せよ。レポートの形式は自由である。

なおファイル名は 学生番号_名前.docx とする。たとえば k24x7777_東女花子.docx である。

(提出方法・期限はWebClassの指示に従うこと)

レポートに入れるとよいもの(例)
  1. テーマと、なぜそのテーマを選んだか
  2. データの説明(地点の数、配置の特徴)
  3. 番号順・貪欲法・山登り法・焼きなまし法の経路の長さの比較
  4. 焼きなまし法の推移のグラフと、見つかった経路の図
  5. 初期解を変えて5回ずつ実行した結果(最良・平均・最悪)
  6. 考察:焼きなまし法は安定して良い経路を出したか、図に交差が残っていないか、設定(回数・開始温度・冷却率)を変えるとどうなったか、「最短」と言ってよいか

生成AIの考察は、そのまま写さず、実行結果の数値と見比べて確かめてから、自分の言葉で書き直すこと。AIの考察に誤りや言い過ぎを見つけたら、それもレポートに書いてよい。

課題用:生成AIで経路の最適化(データ作成 → プログラム → 実行 → 考察)

テーマを決めて、上から順に4つのボタンを押していけばよい。結果はレポートの材料として使う。

最初にボタンを押したとき、授業用パスコードを聞かれる。授業で伝えたものを入力する。

[1]データを生成AIに作らせる

テーマの例:観光地めぐり/宅配の配達先/学校の各教室/お祭りの屋台/テーマパークのアトラクション

テーマ:  地点の数:

追加の希望(なくてよい):

(30秒〜1分ほどかかる)
[2]分析とグラフのRプログラムを生成AIに書かせる
(20〜40秒ほどかかる)
[3]プログラムを実行して、結果を見る

[2]のプログラムが下の枠に入る。「▶ 実行」を押す。図は右クリック(スマートフォンでは長押し)で保存するか、スクリーンショットを撮ってレポートに貼る。

エラーが出たら: (直したプログラムが上の枠に入るので、もう一度「▶ 実行」を押す)

[4]実行結果をもとに、生成AIに考察を書かせる

[3]の実行結果(文字の出力)を生成AIに渡して、考察を書かせる。図そのものは渡さない。

(30秒〜1分ほどかかる)
まとめレポートの材料をまとめてコピーする

テーマ、データの説明、プログラム、実行結果、AIの考察を1つの文章にまとめてコピーする。Wordに貼り付けて、レポートの下書きに使う。

(参考)生成AIに送った指示文を見る

[1]データを作る指示

(まだ送っていません)

[2]プログラムを書く指示

(まだ送っていません)

[4]考察を書く指示

(まだ送っていません)