第8回 シミュレーテッド・アニーリング等の最適化手法
このページの使い方
- 画面上部の帯が緑になるまで待つ(Rの準備。初回は数十秒かかる)。
- 「導入ゲーム」で、霧の山の最高地点をめざす(2分)。
- Ⅰでしくみを読み、黒い枠のRプログラムを上から順に「▶ 実行」で動かす。
- Ⅰ-2 で名前の由来(金属の焼きなまし)を、Ⅰ-3 でほかの手法との比較を読む。
- Ⅲの例題を、ステップの順に実行する。
- Ⅳで、生成AIに自分のテーマのデータとプログラムを作らせて分析する。
- 最後の「課題用プログラム」で、データ作成 → プログラム → 実行 → 考察 を行い、レポートにまとめる。
黒い枠のプログラムは自由に書き換えてよい。「元のコードに戻す」で元に戻る。
今日の目標
- 「最適化」が、たくさんの候補の中から最も良い解を探す問題であることを説明できる。
- 山登り法が局所的最適解で止まる理由と、焼きなまし法がそれを乗り越えるしくみ(温度と受容確率)を説明できる。
- 焼きなまし法が金属の焼きなましと似ている点(エネルギー・温度・ゆっくり冷やす理由)と、似ていない点を説明できる。
- 山登り法・遺伝的アルゴリズムなどと比べた、焼きなまし法の長所と欠点を説明できる。
- 巡回経路問題(配達の順番)やナップサック問題(荷物の選択)を、Rで焼きなまし法を使って解ける。
- 見つかった解が「最適解とは限らない」ことを理解し、くり返し実行して安定性を確かめられる。
- 生成AIに作らせた自分の問題で同じ分析を行い、結果が妥当かを確かめられる。
導入ゲーム:霧の山で、いちばん高い所をめざせ
あなたは濃い霧に包まれた、起伏の激しい山地(約5 km 四方)の真ん中にいる。見えるのは足もとのまわり(半径70 m ほど)だけ。制限時間 2分 のうちに、できるだけ標高の高い地点にたどり着こう。
記録は「2分間に通った中でいちばん高い地点の標高」である(焼きなまし法が「これまでの最良解」をメモするのと同じ)。全員が同じ地形で競う。
| 操作 | キーボード | 画面のボタン(スマホ・タブレット) |
|---|---|---|
| 1マス(20 m)歩く | 矢印キー、または W・A・S・D(押しっぱなしで歩き続ける。2つ同時押しでななめ) | ↑ ← → ↓ を押し続ける |
| 大ジャンプ(半径約500 m 以内のどこかへ、でたらめに跳ぶ。4秒かかる) | スペースキー、または J | 「大ジャンプ」 |
霧が晴れた! あなたの道のり
| ゲームでの行動 | 対応する手法・用語 | このページで学ぶ場所 |
|---|---|---|
| まわりで一番高い方へ、上りだけを選んで歩いた | 山登り法。近くの小さな峰(局所的最適解)で止まりやすい | Ⅰ ステップ3 |
| あえて下り坂を下りて、別の山をめざした | 焼きなまし法の「悪くなる動きも受け入れる」 | Ⅰ ステップ4 |
| 最初は大胆に、残り時間が減ったら近くを細かく | 温度を下げる(冷却スケジュール) | Ⅰ ステップ5・6、Ⅰ-2 |
| 大ジャンプで、まったく別の場所からやり直した | ランダム・リスタート | Ⅰ ステップ3のトリビア、Ⅰ-3 |
| 仲間と手分けして、良い場所の情報を持ち寄る(もしできたら) | 遺伝的アルゴリズム・粒子群最適化(集団で探す) | Ⅰ-3、第9回 |
ゲームでは「高いほどよい」(最大化)だが、Ⅰ以降は「小さいほどよい」(最小化)で説明する。標高にマイナスを付ければ同じ問題になる(ステップ3の「ていねいに」)。
Ⅰ 最適化と焼きなまし法のしくみ
これまでの回は「データから予測する」手法だった。今回は、決まった評価基準のもとで、最も良い答え(解)を探す問題を扱う。これを最適化という。
| 問題 | 解 | 評価(小さいほどよい) | 候補の数 |
|---|---|---|---|
| 配達の順番(巡回経路問題) | 地点を回る順番 | 移動距離の合計 | 12地点で約2,000万通り |
| 荷物の選択(ナップサック問題) | 各荷物を入れるか入れないか | −(価値の合計)、容量超過は罰 | 10個で1,024通り、50個で約1,000兆通り |
| 時間割の作成 | 各授業の時間と教室 | 重なりや希望に合わない数 | 天文学的な数 |
| ニューラルネットの学習(第10回) | 重みの値 | 予測の誤差 | 無限(連続値) |
候補をすべて調べれば必ず最適解が見つかる(全探索)が、候補の数が多すぎて現実には不可能なことが多い。そこで「十分に良い解を、現実的な時間で見つける」工夫が必要になる。
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億通り) |
|---|---|---|
| 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日に回る数十か所の順番を、全部調べて決めることはできない。だから「全部は調べずに、十分良い答えを見つける」方法が必要になる。
巡回セールスマン問題は、「NP困難」と呼ばれる難しい問題の仲間である。この仲間の問題を「地点が増えても現実的な時間で必ず最適解を出せる方法」があるかどうかは、P対NP問題という未解決問題と深く結びついている。アメリカのクレイ数学研究所は、2000年にこれを7つの「ミレニアム懸賞問題」の1つに選び、解いた人に100万ドルを出すとしている。今のところ、誰も受け取っていない。
- 巡回経路の問題は、1832年のドイツのセールスマン向け手引書に、すでに「どう回ると効率がよいか」として登場する。数学の問題として定義したのは1930年代のメンガーで、当時は「配達人問題」と呼ばれた。
- 「巡回セールスマン問題」という名前が文書に初めて現れたのは、1949年の数学者ジュリア・ロビンソンの報告書である。
- 1954年、ダンツィクらはアメリカの49都市を回る最短経路を「これより短い経路はない」という証明つきで求めた。コンピュータの力が上がった2006年には、85,900地点の最短経路が証明つきで解かれた(計算量はCPU 1台で136年分)。
- 自然界にも「解く」ものがいる。アリは餌と巣の間に短い道を見つけ、粘菌は餌の間に効率のよい経路を作る。アリの行動をまねた「アントコロニー最適化」という手法もある。
まず、1つの数 x を動かして f(x) を最小にする問題で考える。下の関数には谷がいくつもあり、いちばん低い谷(大域的最適解)のほかに、まわりより低いだけの谷(局所的最適解)がある。
- 局所的(きょくしょてき)=「その場所のまわりだけを見れば」という意味。局所的最適解は、すぐ近くと比べればいちばん低いが、全体ではもっと低い所がある谷である。
- 大域的(たいいきてき)=「全体を見渡して」という意味。大域的最適解は、全体でいちばん低い谷である。
英語では local optimum(ローカル)と global optimum(グローバル)という。「ローカル線」「グローバル企業」の、あのローカルとグローバルである。
自分の家から歩いて行ける3軒のスーパーを比べて、いちばん安い店を見つけたとする。これは「局所的に」いちばん安い店である。でも、電車で2駅先には、もっと安い業務用スーパーがあるかもしれない。こちらが「大域的に」いちばん安い店である。
近所だけ見ていると「ここが一番だ」と満足してしまい、遠くのもっと良い店には気づけない。これが、このあと出てくる山登り法の弱点そのものである。
いちばん単純な方法は、いまの解の近所(少しだけ変えた解)を試し、良くなるなら移ることをくり返す山登り法である(最小化なので「谷下り」だが、慣例でこう呼ぶ)。
導入ゲームの「霧の山」と同じ状況である(ゲームは高い所、ここでは低い所を探す)。
「いちばん大きい値を探す(最大化)」と「いちばん小さい値を探す(最小化)」は、符号を逆にすれば同じ問題になる。たとえば「点数を最大にする」は「−(点数)を最小にする」と同じである。このため、教科書によって山を登る話(最大化)で説明したり、谷を下る話(最小化)で説明したりする。名前は最大化の言い方が残ったものである。
このページでは、すべて「小さいほどよい」にそろえている。例題2(ナップサック問題)で価値に −1 を掛けているのも、この理由である。
近く <- function(x) x + rnorm(1, 0, 0.3) は、「いまの x に、平均0・標準偏差0.3 の正規分布の乱数を1つ足す」関数である。つまり、ほとんどの場合 −0.6〜+0.6 くらいの範囲で、左右どちらかに少しだけ動いた点を作る。これが「霧の中で1歩だけ足を出してみる」ことにあたる。
読み取り方:出発点が 4 のときだけ大域的最適解(3.12)にたどり着き、ほかは近くの谷で止まった。一度谷に入ると、まわりはすべて「悪くなる」動きなので抜け出せない。
山登り法のルールは「良くなるときだけ移る」である。谷の底にいると、右に1歩出しても左に1歩出しても、必ず少し高く(悪く)なる。だから何百回試しても、すべての候補が却下される。隣の谷に行くには、いったん山を登らなければならないのに、そのルールがないのである。
山登り法が悪いのではない。谷が1つしかない問題なら、山登り法は速くて確実である。問題は「谷がいくつもある」ときだけ起きる。
部活でもアルバイトでも、今の場所が「前よりは良い」と、そこから動かなくなりがちである。少しでも条件が下がる変化は、すべて断ってしまうからだ。でも、一時的に条件が下がる道(たとえば新しいことを一から始める)を通らないと、たどり着けない場所もある。山登り法は「一時的な損を絶対に受け入れない人」にあたる。
- 山登り法は英語で hill climbing。近所だけを調べて進むので、局所探索(local search)とも呼ばれる。例題3の
optimも局所探索の一種である。 - 山登り法を「出発点を変えて何回もやり直す」工夫は、ランダム・リスタートと呼ばれる。単純だが、実務ではかなり効く。ステップ7の比較でも、山登り法の「最良」は悪くないことに注目しよう。
金属を高温にしてからゆっくり冷やすと、原子が落ち着いた並びになり、丈夫な金属になる。この「焼きなまし」になぞらえたのが焼きなまし法(シミュレーテッド・アニーリング、SA)である。
→ 金属の中で何が起きているのか、なぜ似ているのかは、Ⅰ-2 で図を使ってくわしく説明する。
| 金属の焼きなまし | 焼きなまし法 |
|---|---|
| 温度が高い:原子が激しく動く | 温度が高い:悪くなる動きもよく受け入れる(広く探す) |
| ゆっくり冷やす | 温度を少しずつ下げる(冷却率を掛ける) |
| 温度が低い:原子が落ち着く | 温度が低い:良くなる動きだけ受け入れる(山登り法と同じ) |
でこぼこの箱にボールを入れて、はじめは強く揺らす。ボールは山を飛び越えて箱の中を動き回る。揺らし方をだんだん弱くすると、ボールは高い所に行けなくなり、深い谷にとどまる。最後にほとんど揺らさなければ、ボールは谷の底に落ち着く。「揺らしの強さ」が温度である。
マグマが冷えて固まった岩石を火成岩という。中学の理科で習ったとおり、
- 地下深くでゆっくり冷えたマグマ → 花こう岩のような深成岩。結晶が大きく、よくそろう(等粒状組織)。
- 地表近くで急に冷えたマグマ → 玄武岩のような火山岩。小さな結晶やガラス質の部分が多い(斑状組織)。さらに急に冷えると、黒曜石のようなガラスになる。
原子や分子は、時間をかけて冷やされると「いちばん落ち着く並び方(エネルギーが最も低い並び)」を見つけられる。急に冷やすと、途中のでたらめな並びのまま固まってしまう。焼きなまし法の「急に冷やすと途中の谷で止まる」は、これとまったく同じ話である。
- 焼き入れ:熱した鉄を水や油で急に冷やす。硬くなるが、もろくなる。日本刀の刃の硬さはこの工程で生まれる。
- 焼きなまし(焼鈍=しょうどん):熱した金属を炉の中などでゆっくり冷やす。内部のゆがみが取れ、やわらかく粘り強くなる。加工しやすくするために行う。
- ガラス工芸でも、作ったガラスを「徐冷炉」でゆっくり冷やす。急に冷やすと内部にゆがみが残り、あとで突然割れることがある。
(1) exp とは:exp(□) は「e の □ 乗」のことである。e = 2.718… という決まった数(ネイピア数)。大事な性質は次の3つだけ覚えればよい。
| □ の値 | exp(□) の値 | 意味 |
|---|---|---|
| 0 | 1 | 確率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.1 | 0.905(約90%) | ほぼ受け入れる |
| 5 | −1 ÷ 5 = −0.2 | 0.819(約82%) | だいたい受け入れる |
| 1 | −1 ÷ 1 = −1 | 0.368(約37%) | 3回に1回くらい |
| 0.2 | −1 ÷ 0.2 = −5 | 0.007(約0.7%) | まず受け入れない |
(4) 式が言っていることは、次の2つだけである。
- 悪くなる量が大きいほど、受け入れにくい(大きな損はなかなか引き受けない)。
- 温度が高いほど、受け入れやすい(はじめのうちは冒険する)。
この2つの性質を持つ式ならほかにも作れるが、物理の世界で原子のふるまいを正しく表す式が exp だったので、それをそのまま借りている(下のエピソード参照)。
プログラムの中では runif(1) < exp(-差 / 温度) と書いてある。runif(1) は 0〜1 の間の数をでたらめに1つ出す関数である。これは「0〜1 の数直線のどこかにダーツを投げる」ことにあたる。
受け入れる確率が 0.82 なら、数直線の 0〜0.82 の部分が「当たり」になる。ダーツがそこに刺さる確率は、ちょうど 82% である。下で試してみよう。
焼きなまし法の「温度」は、℃ではない。exp の中で「悪くなる量 ÷ 温度」と割り算しているので、温度は悪くなる量と同じ単位を持つ。
- 経路の問題なら、悪くなる量は km なので、温度も km で考える。「温度5」は「5 km くらい遠回りになる変更なら、まあ受け入れてもよい」という気前のよさを表す。
- ナップサック問題なら、温度は「点」で考える。
だから、開始温度の目安は「1回の変更で悪くなる量と同じくらい」になる(ステップ5の表)。温度がそれより小さすぎると最初から山登り法と同じになり、大きすぎると最初のうちはただでたらめに動き回るだけになる。
読み取り方:温度5のときは、少し悪くなる動き(差0.5)を90%の確率で受け入れる。温度0.2では、同じ動きをほとんど受け入れない(8%)。
- 「受け入れる確率 exp(−差÷温度)」の式は、1953年にメトロポリスらが物理の計算(原子の動きの模擬)のために考えた方法から来ている。この論文の著者5人のうち4人は、2組の夫婦だった(ローゼンブルース夫妻とテラー夫妻)。
- これを「最適化」に使い、「焼きなまし法」と名付けたのは、1983年のカークパトリックらの論文(Science誌)である。彼らはコンピュータの回路の配置(部品をどう並べれば配線が短いか)と巡回セールスマン問題を例にした。
- ほぼ同じ方法を、1985年にスロバキアのチェルニーも独立に発表している。良いアイデアは、同じ時期に別々の場所で生まれることがある。
「温度が高いほど、エネルギーの高い(不安定な)状態も起こりやすい」という関係を exp の式で表したのは、19世紀オーストリアの物理学者ボルツマンである。この式は今も「ボルツマン分布」と呼ばれ、物理や化学の教科書に必ず出てくる。
ボルツマンの考え(物質は原子の集まりで、そのふるまいは確率で表せる)は、当時は激しく批判された。いまではウィーンの中央墓地にある彼の墓に、彼の名を冠したもう1つの有名な式 S = k log W(エントロピーの式)が刻まれている。焼きなまし法は、この物理の考え方をそっくり借りて、「原子」を「解」に、「エネルギー」を「評価の値」に読みかえたものである。
1953年のメトロポリスらの計算は、ロスアラモス研究所の初期の電子計算機 MANIAC(マニアック)で行われた。当時のコンピュータは部屋いっぱいの大きさで、今のスマートフォンよりはるかに遅い。
この論文の手法は、のちに筆頭著者の名をとって「メトロポリス法」と呼ばれるようになった。しかし後年の証言によれば、実際にプログラムを書いて計算を走らせたのは、共著者のアリアナ・ローゼンブルースだったとされる。彼女はこの分野を離れたあとも長く語られることが少なかったが、2020年に亡くなったときに、その功績が改めて紹介された。
| 決めるもの | 意味 | 目安 |
|---|---|---|
| 初期解 | 出発点 | でたらめでよい |
| 近傍(近所の解の作り方) | 解を少しだけ変える方法 | 問題ごとに決める(ステップ8) |
| 開始温度 | 最初の温度 | 「悪くなる量」と同じくらいの大きさ |
| 冷却率 | 1回ごとに温度に掛ける数 | 0.99〜0.999(1に近いほどゆっくり) |
| 回数 | くり返す回数 | 温度が十分下がるまで |
冷却率は「1回ごとに温度に掛ける数」である。温度5、冷却率0.998なら、
5 → 5×0.998 = 4.990 → 4.990×0.998 = 4.980 → …
と、毎回0.2%ずつ下がる。1回ではほとんど変わらないが、何百回もくり返すと大きく下がる。分かりやすい目安は「温度が半分になるまでの回数」である。
| 冷却率 | 1回で下がる割合 | 温度が半分になる回数 | 温度5から3000回後の温度 |
|---|---|---|---|
| 0.9 | 10% | 約7回 | ほぼ0(10−137くらい) |
| 0.98 | 2% | 約34回 | ほぼ0 |
| 0.99 | 1% | 約69回 | ほぼ0 |
| 0.995 | 0.5% | 約138回 | 約0.0000015 |
| 0.998 | 0.2% | 約346回 | 約0.012 |
| 0.999 | 0.1% | 約693回 | 約0.25 |
冷却率0.9は「7回ごとに温度が半分」なので、数十回でほぼ山登り法になってしまう。冷却率は 1 との差がわずかに見えても、くり返すと大きな違いになる。
お金の世界には「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 では温度がすぐ下がり、途中の谷で止まりやすい。
このページでは、この手順を 焼きなまし(初期解, 評価, 近傍, 回数, 開始温度, 冷却率) という関数にして用意してある。
山登り法では抜け出せなかった、いちばん遠い谷(出発点 8)から始める。
読み取り方:左の図では、最初は値が大きく上下している(悪い解も受け入れている)。温度が下がるにつれて落ち着き、最後は大域的最適解(3.12)にたどり着いた。
| 時期 | 温度 | 図の見た目 | していること |
|---|---|---|---|
| 序盤(0〜500回くらい) | 高い | 上下に大きくギザギザ | 谷から谷へ自由に動き回り、全体を広く探す |
| 中盤 | 中くらい | ギザギザが小さくなる | 浅い谷からは出られるが、深い谷からは出にくくなる。良い谷にしぼっていく |
| 終盤 | 低い | ほぼ平ら | 山登り法と同じ。その谷の底まで細かく下りる |
「最初は広く、だんだん狭く」が焼きなまし法の基本の形である。自分のデータで動かしたときも、推移の図がこの形になっているかを確かめるとよい(Ⅳのステップ4)。
焼きなまし法は乱数(でたらめな数)を使うので、実行するたびに結果が変わる。set.seed(数) は、乱数の「出発点」を決める命令で、同じ数を指定すれば毎回同じ乱数の列が出る。授業で全員が同じ結果を見られるように使っている。
set.seed(3) を set.seed(10) などに変えると結果が変わる。何度か変えて試すと、焼きなまし法がいつも成功するわけではないことが分かる。
コンピュータは決まった計算しかできないので、本当のでたらめは作れない。実際には、でたらめに見える数を決まった計算式で次々に作っている(疑似乱数)。Rが標準で使う「メルセンヌ・ツイスタ」は、1997年に日本の松本眞さんと西村拓士さんが発表した方法で、同じ並びがくり返すまでの長さが 219937−1(6,000けた以上の数)もある。Pythonなど、世界中のソフトウェアで使われている。
冷やす速さを変えてみる
読み取り方:冷却率0.9では20回とも途中の谷で止まり、0.998では15回いちばん低い谷に着いた。ゆっくり冷やすほど成功しやすいが、時間がかかる。
試験範囲が広いとき、最初から1つの単元だけを深く勉強すると、ほかの単元に手が回らない(急に冷やす)。最初の数日は全体をざっと見て、どこが出そうか・どこが苦手かを広く探り(温度が高い)、試験が近づいたら重要な所にしぼって仕上げる(温度が低い)ほうがうまくいきやすい。ただし、広く探る期間が長すぎると、仕上げの時間が足りなくなる。冷却率の決め方は、この「探る時間」と「仕上げる時間」の配分の問題である。
1984年、ゲマン兄弟(スチュアートとドナルド)は、温度を非常にゆっくり(回数の対数に反比例するくらい)下げれば、焼きなまし法は確率1で大域的最適解にたどり着くことを数学的に証明した。
ところが、その下げ方はあまりにも遅く、実際に使うと全探索より時間がかかってしまうことさえある。そこで実務では、このページのように「温度に0.99〜0.999を掛ける」速い冷やし方を使い、保証はあきらめて、十分良い解を速く得る。理論と実務の折り合いのつけ方がよく分かる例である。
どちらの方法も乱数を使うので、1回の結果では比べられない。出発点を変えて20回ずつ試す。
読み取り方:山登り法が大域的最適解に着いたのは20回中3回、焼きなまし法は10回だった。焼きなまし法でも必ず着くわけではない。回数を増やす・ゆっくり冷やす・何度か実行して最良を採るのが実務での使い方である。
乱数を使う方法は、1回の結果が「たまたま」良かったり悪かったりする。サイコロを1回振って6が出ても、「このサイコロは6が出やすい」とは言えないのと同じである。20回試して「何回成功したか」「値がどれくらいばらつくか」を見て、はじめて手法どうしを公平に比べられる。
下の箱ひげ図は、20回分の結果の分布を表す。箱が低い位置にあり、箱が小さい(つぶれている)ほど、良い結果が安定して出ていることを意味する。赤い点線がいちばん低い谷の値である。
1997年にウォルパートとマクレディが示した「ノーフリーランチ定理」によると、あらゆる問題を平均すると、どの探索手法も性能は同じになる。ある問題で焼きなまし法が山登り法に勝つなら、別の問題では負けている。名前の由来は「ただのランチはない(タダより高いものはない)」ということわざである。だから、問題の性質(谷が1つか、たくさんあるか)を見て手法を選ぶことが大切になる。
数値の問題では「少し足す」でよいが、順番や組み合わせの問題では、解を少しだけ変える方法を自分で決める必要がある。
| 問題 | 近所の解の作り方 | このページの関数 |
|---|---|---|
| 数値の最小化 | 少し足す・引く | 近く(ステップ3で定義) |
| 巡回経路 | 経路の一部を逆順にする(2-opt) | 経路の近傍 |
| 荷物の選択 | 1つの荷物を入れる↔入れないに切り替える | 選択の近傍(例題2で定義) |
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本のことである。変更が小さいので、「近所の解」としてちょうどよい。
「C と E を入れ替える」(A→B→E→D→C→F)という近傍も考えられる。上の例では、たまたま区間の逆順と同じ結果になるが、離れた2地点を入れ替えると、それぞれの前後の道が変わるので、最大4本の道が一度に変わる。変化が大きすぎると「近所の解」とは言いにくく、良い経路を少しずつ磨くのが難しくなる。2-optが定番なのはこのためである。
- 2-optは、1958年にクロースが巡回セールスマン問題の解き方として発表した。
- 3本の道を付け替える「3-opt」もある(1965年、リン)。さらに、付け替える本数をその場で変える「リン=カーニハン法」(1973年)は、今でも巡回セールスマン問題の最強クラスの方法の土台になっている。
- カーニハンは、プログラミング言語C の有名な入門書『プログラミング言語C』の著者の一人でもある。
| 手法 | 考え方 | 最適解の保証 | 向いている問題 |
|---|---|---|---|
| 全探索 | すべての候補を調べる | あり | 候補が少ない(数百万以下) |
| 貪欲法 | その場で最も良い選択をくり返す | なし | 速さ重視。おおまかな解でよいとき |
| 山登り法 | 近所で良ければ移る | なし(局所解で止まる) | 谷が1つの問題 |
| 焼きなまし法 | 悪い動きも温度に応じて受け入れる | なし(確率的に近づく) | 谷が多い組み合わせ問題 |
| 遺伝的アルゴリズム(第9回) | 解の集団を進化させる | なし | 谷が多い問題。解を組み合わせられるとき |
| 勾配法(第10回) | 傾きの方向に下る | なし(局所解) | 微分できる連続の問題 |
→ 長所と欠点のくわしい比較と、同じ地形で手法を競わせる実験は Ⅰ-3 にある。
- 宅配便の配達順やごみ収集車の経路は、巡回経路問題そのものである。配達先が数十か所になると、人の勘では最適に近い順番を決めにくい。
- 時間割、シフト表、プロ野球の対戦日程も、「重なりや希望に合わない数」を最小にする最適化問題として解かれている。
- テストの問題選びも最適化である。1973年には、学生が「解く問題を自分で選べる試験」の採点にナップサック問題の解き方が使われた。
お昼ごはんの店を選ぶとき、いつもの店に行けばまず満足できる(活用)。新しい店に行くと、はずれることもあるが、もっと好きな店が見つかるかもしれない(探索)。
大学に入ったばかりのころは新しい店をどんどん試し、卒業が近づくと、お気に入りの店に通うようになる。これはまさに「温度を下げていく」焼きなまし法の動きである。機械学習では、この「探索と活用のバランス」が大きなテーマで、焼きなまし法の温度は、そのバランスを時間とともに変える仕組みだと言える。
焼きなまし法は「熱で揺らして」山を越える。これに対し、量子力学の「トンネル効果」(粒子が山を飛び越えずにすり抜ける現象)を使って谷から抜け出す方法が量子アニーリングである。1998年、東京工業大学の門脇正史さんと西森秀稔さんが理論を発表した。
2011年にはカナダのD-Wave社がこの考えにもとづく専用の計算機を売り出し、話題になった。日本でも富士通の「デジタルアニーラ」や日立の「CMOSアニーリング」など、焼きなまし法の考え方を専用の回路で高速に実行する計算機が作られ、配送計画や工場の生産計画に使われている。
- わざと悪い解に移るのは、遠回りでむだではないのか。
- 短い目で見るとむだだが、長い目で見ると必要である。谷を出て隣の深い谷に行くには、いったん山を登るしかない。焼きなまし法は「最終的に良い解に着く」ために、途中の損を計画的に受け入れている。しかも、通った中で最も良い解はメモしてあるので(ステップ5)、遠回りしても答えが悪くなることはない。
- 温度を下げずに、ずっと同じ温度で探してはだめなのか。
- 温度が高いままだと、良い谷に入ってもすぐに出て行ってしまい、谷の底まで下りられない。温度が低いままだと、山登り法と同じで最初の谷から出られない。「最初は広く探し、最後は1つの谷を細かく下りる」ために、温度を下げる必要がある。
- 見つかった解が本当にいちばん良いかは、どうすれば分かるのか。
- 一般には分からない。分かるのは、全探索ができる小さな問題(例題2のステップ2-3)か、特別な数学の方法で証明できる場合だけである。実務では、何回か実行して同じくらいの値が出るか(安定性)、ほかの手法より良いかを確かめて、「見つかった中で最も良い解」として報告する。
- 焼きなまし法とAI(機械学習)は、どう関係するのか。
- 機械学習の「学習」は、「予測の誤差が最も小さくなるパラメータを探す」最適化問題である(第10回のニューラルネットで扱う)。焼きなまし法は、こうした最適化の考え方を、谷がはっきり見える小さな問題で体験するのにちょうどよい。「局所的最適解」「探索と活用」「乱数に頼るので何回か試す」という考え方は、機械学習のあらゆる場面に出てくる。
- 開始温度と冷却率は、どう決めればよいのか。
- 決まった正解はなく、試して決める。目安は、①開始温度は「1回の変更で悪くなる量」と同じくらい、②冷却率は 0.99〜0.999、③回数は「最後の温度が開始温度の100分の1以下になる」くらい。推移のグラフを見て、序盤に上下し、終盤に落ち着いていれば、おおむね良い設定である。
Ⅰ-2 なぜ金属の「焼きなまし」に似ているのか
ステップ4で、名前の由来を表で簡単に見た。ここでは、金属の中で実際に何が起きているのかを図で順に追い、それが焼きなまし法のどの部分にあたるのかを確かめる。最後に、似ていない点(たとえの限界)も整理する。
金属は、原子が規則正しく並んだ結晶でできている。ただし、現実の金属の並びは完全ではなく、原子が抜けたすき間(空孔)、並びのずれ(転位)、向きのちがう小さな結晶の境目(結晶粒界)などの欠陥がある。金属の硬さ・粘り・割れにくさは、この欠陥の量や形で大きく変わる。
- ①高温:原子は熱によって激しくゆれ、場所を入れかわることもできる。どんな並びにも「なれる」状態である。
- ②ゆっくり冷やす:原子は動ける時間のあいだに、少しずつ「落ち着く並び」に移っていく。欠陥が少ない、整った結晶になる。
- ③急に冷やす:原子が並びかえる前に動けなくなる。そのときの途中の並びのまま固まり、欠陥やゆがみが多く残る。
焼きなましは「①加熱 → ②その温度でしばらく保つ → ③炉の中でゆっくり冷やす」の3段階で行う。②で原子が十分に動いて並びかえる時間をとり、③で少しずつ動けなくしていく。目的は、加工でたまった内部のゆがみを取ること、金属をやわらかく、粘り強くして次の加工をしやすくすることである。
| 工場の焼きなまし | 焼きなまし法(プログラム) |
|---|---|
| ①加熱:原子が自由に動ける温度まで上げる | 開始温度を十分高くする(悪い動きもよく受け入れる) |
| ②保つ:その温度で原子が並びかえる時間をとる | 温度をほとんど変えずに、何回も近所の解を試す |
| ③ゆっくり冷やす | 冷却率を 1 に近くする(0.99〜0.999) |
| 急に冷やす(焼き入れ・急冷) | 冷却率を小さくする/開始温度を 0 にする = 山登り法と同じ |
焼きなまし法の論文では、温度をいきなり 0 にすることを、英語で急冷を意味する quench(クエンチ)と呼ぶことがある。つまり山登り法は「計算の世界の焼き入れ」にあたる。
- 「焼きなまし」は漢字で焼き鈍しと書く(専門用語では焼鈍=しょうどん)。「鈍す(なます)」は「鋭さをにぶくする・やわらかくする」という意味で、硬くなった金属をやわらかく戻すことを表している。
- 英語の anneal は、古い英語で「火にかける・焼く」を意味する語から来ている。ガラスや金属を炉で処理する職人の言葉が、20世紀に計算の言葉になった。
物理では、原子の並び方ごとにエネルギーという量が決まる。原子どうしがちょうどよい距離で整列しているほどエネルギーは低く、エネルギーが低い並びほど安定している(自然はエネルギーの低い状態に落ち着こうとする)。
ありうる並び方をすべて横1列に並べ、それぞれのエネルギーを高さで表すと、次のようなでこぼこの地形になる。これは、ステップ2の「谷の多い関数」とまったく同じ形の問題である。
- いちばん低い谷=欠陥のない、きれいな結晶。最適化でいう大域的最適解。
- 浅い谷=欠陥を含んだ並び。まわりと比べると安定なので、そこから自然には出にくい。最適化でいう局所的最適解。
- 山の上=谷から谷へ移る途中の、不安定な並び。
金属をきれいな結晶にしたい職人と、最適解を探したいプログラマーは、同じ形の問題(でこぼこの地形で、いちばん低い谷を探す)に取り組んでいることになる。
温度 T のとき、原子の集まりが「エネルギー E の並び」にいる確率は、exp( − E ÷ T )に比例する。これをボルツマン分布という(ステップ4のエピソード)。焼きなまし法の受容確率 exp( − 差 ÷ 温度)は、この分布を作り出すための仕組みである。
下のスライダーで温度を変えて、オレンジ色の「いやすさ」がどう変わるかを見よう。
- どの温度でも、低い谷ほど「いやすい」。exp( − E ÷ T )は、E が小さいほど大きいからである。
- 温度が下がるほど、その差が極端になる。温度8ではどの谷にも同じくらいいるが、温度0.25ではほぼ全員が「いちばん低い谷」に集まる。温度を 0 に近づけると、確率は限りなく 100% に近づく。
したがって、「各温度で十分に落ち着かせながら(ボルツマン分布になるまで待ちながら)、温度を 0 に近づける」ことができれば、いちばん低い谷に着く。これが焼きなまし法の理論上の根拠である。
読み取り方:最後の行は、温度 8, 2, 0.8, 0.25, 0.1 のときに、いちばん低い谷にいる確率である。温度を下げるほど 1(100%)に近づく。
2-4 の話には「各温度で十分に落ち着かせれば」という条件がついていた。ここが「ゆっくり」の理由である。
谷にいる原子(や解)が隣の谷へ移るには、間の山を越える必要がある。熱によるゆれで山を越えるまでの平均の待ち時間は exp(ΔE ÷ 温度)に比例する(化学で習う「アレニウスの式」と同じ考え方)。具体的に計算すると、次のようになる。
| 山の高さ ΔE \ 温度 | 温度 2 | 温度 1 | 温度 0.5 |
|---|---|---|---|
| 1(低い山) | 1.6 | 2.7 | 7.4 |
| 2 | 2.7 | 7.4 | 55 |
| 4(高い山) | 7.4 | 55 | 2,981 |
数字は exp(ΔE ÷ 温度)。待ち時間の「倍率」の目安である。
- 温度が高いうちは、高い山でも比較的すぐ越えられる。だから、あちこちの谷を行き来して「どの谷が深いか」を広く比べられる。
- 温度を下げると、高い山から順に越えられなくなる(温度0.5で高さ4の山は、待ち時間が約3,000倍)。このとき、どの大きな谷にいるかが先に決まり、その後、谷の中の細かいでこぼこが決まっていく。「大まかな形が先、細部はあと」である。
- 温度を急に下げると、山を越える前に動けなくなる。最初にいた谷、またはたまたまいた谷で固まってしまう。これが急冷で欠陥が残る理由であり、山登り法が局所的最適解で止まる理由でもある。
やってみよう:200個の玉を、ゆっくり冷やす/急に冷やす
200個の玉(原子、または200本の焼きなまし法)を地形の上にでたらめに置き、全部を同時に焼きなまし法で動かす。冷やし方だけを変えて、最後にいちばん低い谷に何個集まるかを比べよう。
結果の目安(筆者が各5回試した平均):ゆっくり冷やすと約60%、急に冷やすと約25%、温度0では約20%の玉が、いちばん低い谷に集まった。ゆっくり冷やしても100%にはならないのは、6,000回では「十分にゆっくり」とは言えないためである(ステップ6のエピソード)。
1983年の論文で、カークパトリックらは、物質のいちばん安定な状態を調べる実験として「融かした物質から単結晶を育てる」ことを例にあげた。物質をいったん融かし、温度をゆっくり下げ、特に固まり始める温度の近くで長い時間をかける。急に冷やすと、結晶にならずに欠陥だらけの状態やガラスになってしまう。彼らは、この「注意深い焼きなまし」をコンピュータの中でまねれば、回路の配置のような組み合わせの問題でも良い解が得られると考えた。
「固まり始める温度の近くで時間をかける」という考えは、焼きなまし法でも有効である。ステップ6の推移の図で言えば「中盤」の時期で、ここで良い谷が選ばれる。冷却を工夫する研究の多くは、この時期にどれだけ時間を使うかを調整している。
名前は物理から借りているが、まったく同じではない。次の表の左右のちがいを知っておくと、「温度」などの言葉を誤解しにくい。
| 観点 | 金属の焼きなまし | 焼きなまし法 |
|---|---|---|
| 動くもの | ばく大な数の原子が同時に動く | ふつうは解1つを順番に動かす(2-5の200個の玉は、200本を同時に走らせた特別な例) |
| 温度 | 実在の量(℃、K)。材料ごとに意味のある温度が決まっている | 評価の値と同じ単位を持つ調整つまみ。問題ごとに自分で決める |
| 動き方 | 自然法則で決まっている | 「近所の解」の作り方を人が設計する(ステップ8)。設計しだいで性能が大きく変わる |
| 最良の記録 | 金属は、途中で一番良かった並びを覚えていない | これまでの最良解をメモしておける(ステップ5) |
| 目的 | やわらかさ・ゆがみの除去など。完全な結晶を作ることが目的とは限らない | 評価の値が最も小さい解(最適解)を見つけること |
| 急冷の結果 | 鋼の焼き入れで硬くなるのは、急冷で特別な結晶構造(マルテンサイト)ができるため。単に「並びが乱れる」だけではない | 温度0=山登り法。近くの谷で止まる |
Ⅰ-3 ほかの手法と比べた、焼きなまし法の長所と欠点
ステップ9の表を、もう少しくわしく見る。最初に結論を表にまとめ、そのあと図と実験で理由を確かめる。
| 観点 | 全探索 | 山登り法 | 山登り法+ ランダム・リスタート | 焼きなまし法 | タブー探索 | 遺伝的 アルゴリズム | 勾配法 |
|---|---|---|---|---|---|---|---|
| 作りやすさ(プログラムの短さ) | ◎ | ◎ | ◎ | ○ | △ | △ | ○ |
| 調整するつまみの少なさ | ◎ | ◎ | ○ | △ | △ | × | ○ |
| 局所的最適解から抜け出す力 | — | × | ○ | ◎ | ◎ | ○ | × |
| 谷が多い問題での解の良さ | ◎ | × | ○ | ○ | ○ | ○ | △ |
| 大きな問題でも計算が終わるか | × | ◎ | ◎ | ○ | ○ | ○ | ◎ |
| 複数のコンピュータで手分けしやすいか | ◎ | △ | ◎ | △ | △ | ◎ | △ |
| 最適解の保証 | ◎ | × | × | △ | × | × | × |
| 使える問題 | 候補が少ない問題 | 「近所の解」が決められれば、連続でも組み合わせでも | 主に組み合わせ | 連続・組み合わせ | 微分できる連続の問題 | ||
◎ とても良い ○ 良い △ 問題による・工夫が必要 × 苦手。これは一般的な傾向をまとめた目安(筆者の評価)で、問題や設定しだいで入れかわる(ステップ7のノーフリーランチ定理)。焼きなまし法の「最適解の保証 △」は、「無限にゆっくり冷やせば確率1で最適解に着く」という理論があるが、現実には使えない(ステップ6のエピソード)という意味である。
| 手法 | ひとことで | 局所的最適解からの抜け方 | 決めるもの(つまみ) |
|---|---|---|---|
| 山登り法 | 良くなるときだけ移る | 抜けられない | 近所の作り方 |
| ランダム・リスタート | 山登り法を、出発点を変えて何回も | 別の場所からやり直す | 近所の作り方、やり直しの回数 |
| 焼きなまし法 | 悪い動きも、温度に応じた確率で受け入れる | 確率的に山を越える | 近所の作り方、開始温度、冷却率、回数 |
| タブー探索 | 近所でいちばん良い解へ移る。ただし最近いた解には戻らない | 戻れないので、押し出されるように先へ進む | 近所の作り方、禁止リストの長さ |
| 遺伝的アルゴリズム | 解の集団を、選択・交叉・突然変異で世代交代させる | 集団のどこかが別の谷にいれば移れる | 集団の大きさ、交叉・突然変異の確率、選び方、世代数 |
| 勾配法 | 傾き(微分)の向きに下りる | 抜けられない(出発点を変える工夫が必要) | 1回に進む幅(学習率) |
- 遺伝的アルゴリズム:アメリカのホランドが1975年の本『自然・人工システムにおける適応』で体系化した。生物の進化をまねている。
- タブー探索:1986年にグローバーが提案した。「タブー(禁止)」は、最近いた解を禁止リストに入れることから。
- 粒子群最適化(PSO):1995年にケネディとエバーハートが提案した。鳥や魚の群れが、仲間の情報を使いながらえさを探す動きをまねている。
- 遺伝的アルゴリズムなどの「進化的な方法」は、NASAの人工衛星(2006年打ち上げの Space Technology 5)のアンテナの形を設計するのにも使われた。人間なら思いつかない、ねじれた針金のような形になった。
- 作りやすい:必要なのは「評価の値を計算する関数」と「近所の解を作る関数」の2つだけ。このページの関数
焼きなましも十数行である。 - 局所的最適解から抜け出せる:悪くなる動きを確率で受け入れるので、山を越えられる。
- どんな問題にも使いやすい:順番(経路)、組み合わせ(荷物)、数値(x)のどれにも、近所の作り方を変えるだけで使える。微分も要らない。
- 記憶が少なくてすむ:持っておく解は「いまの解」と「最良解」の2つだけ。
- 理論の裏づけがある:十分ゆっくり冷やせば最適解に近づくことが証明されている(実用上の速さとは別)。
- 制約を「罰」で入れられる:容量オーバーなどを評価の値に足すだけでよい(例題2)。
- つまみの調整が必要:開始温度・冷却率・回数で結果が大きく変わる。良い値は問題ごとに試して決めるしかない(ステップ6)。
- 時間がかかる:ゆっくり冷やすほど良いが、そのぶん評価の計算回数が増える。評価1回の計算が重い問題(シミュレーションが必要な問題など)では使いにくい。
- 実行ごとに結果がちがう:乱数を使うので、何回か実行して確かめる必要がある(ステップ7)。
- 解の良さの保証がない:見つかった解が最適か、最適からどれくらい離れているかは分からない。
- 1本の探索なので手分けしにくい:1つの解を順番に動かすので、たくさんのコンピュータで同時に計算する効果が出にくい(工夫した方法はある:3-6)。
- 良い解どうしの情報を組み合わせない:過去に見つけた別の良い解の「良い部分」を使うことはしない。ここが遺伝的アルゴリズムとの大きなちがいである。
| 観点 | 焼きなまし法 | 遺伝的アルゴリズム |
|---|---|---|
| 持っている解 | 1つ | 集団(数十〜数百) |
| 新しい解の作り方 | いまの解を少しだけ変える(近所) | 2つの親を組み合わせる(交叉)+少し変える(突然変異) |
| 悪い解の扱い | 温度に応じた確率で受け入れる | 悪い解は次の世代に残りにくい(選択) |
| 探す範囲を変える仕組み | 温度を下げる(最初は広く、だんだん狭く) | 集団がだんだん良い所に集まる |
| 得意な問題 | 解を少しずつ変えると評価も少しずつ変わる問題 | 解をいくつかの「部品」に分けられ、良い部品の組み合わせで良い解になる問題 |
| 起きやすい失敗 | 冷やすのが速すぎて、途中の谷で止まる | 集団が早いうちに1つの谷に集まり、みんな同じ解になる(早熟収束) |
| つまみ | 開始温度・冷却率・回数 | 集団の大きさ・交叉率・突然変異率・選び方・世代数 |
交叉は、親Aの良い部分と親Bの良い部分を合わせれば、もっと良い子ができることを期待している。ナップサック問題では、「テントと寝袋を入れる」という良い部分と「救急箱とカメラを入れる」という良い部分を合わせられるので、交叉が効きやすい。
一方、巡回経路問題で「前半はAの順番、後半はBの順番」とそのままつなぐと、同じ地点を2回通ったり、通らない地点が出たりして、経路として成り立たない。そのため、経路の問題では特別な交叉の方法が必要になる。焼きなまし法の2-opt(ステップ8)のような「少しだけ変える」方法のほうが、素直に使える場面も多い。
導入ゲームの「本番」の地形で、5つの手法に同じ回数だけ標高を調べさせ、最高峰(2,400 m)の頂上付近(50 m 以内)に着けた割合を比べる。ゲームと同じく「高いほどよい」問題である。各手法を30回ずつ実行する。
| 手法 | このページでの設定 |
|---|---|
| でたらめ探索 | 地図のどこか1点をでたらめに選ぶことをくり返す |
| 山登り法 | 出発点(地図の中央)から。近所=いまの地点から平均 約500 m 以内のどこか1点。高くなれば移る |
| 山登り法+ランダム・リスタート | 60回続けて高くならなかったら、でたらめな地点からやり直す |
| 焼きなまし法 | 出発点(中央)から。近所は山登り法と同じ。開始温度 800 m、最後の温度 2 m |
| 遺伝的アルゴリズム | 30地点の集団。2つの親の「あいだ」の地点に子を作る(交叉)。半分の子は近所へずらす(突然変異) |
| 手法 | 1,500回のとき | 4,000回のとき | 読み取れること |
|---|---|---|---|
| でたらめ探索 | 15% | 40% | 回数を増やせば少しずつ当たるが、効率は悪い |
| 山登り法 | 25% | 29% | 回数を増やしてもほとんど伸びない。局所的最適解で止まっているから |
| 山登り法+リスタート | 60% | 95% | この地形では非常に強い |
| 焼きなまし法 | 61% | 81% | 回数を増やすと、ゆっくり冷やせるので伸びる |
| 遺伝的アルゴリズム | 82% | 82% | 少ない回数で強いが、増やしても伸びない(早熟収束) |
- 事実:この地形・この設定では、焼きなまし法は山登り法よりはっきり良いが、いつも1位ではない。少ない回数では遺伝的アルゴリズム、多い回数ではランダム・リスタートのほうが良かった。
- 理由の推測:この地図は2次元(東西・南北)で、全部で約6.5万地点しかない。「でたらめな場所からやり直す」だけで地図の大部分を調べられるので、ランダム・リスタートが有利になる。巡回経路問題のように候補が天文学的に多い問題では、でたらめなやり直しはほとんど当たらず、焼きなまし法のように「良い解を少しずつ磨く」方法が有利になりやすい。
- 教訓:手法の優劣は、問題と設定で入れかわる(ノーフリーランチ定理)。実務では、いくつかの手法を同じ条件(同じ計算回数)で比べてから選ぶ。
実際の研究や実務では、手法を組み合わせることも多い。
| 組み合わせ | しくみ | ねらい |
|---|---|---|
| 遺伝的アルゴリズム+局所探索(メメティック・アルゴリズム) | 交叉で作った子を、山登り法や焼きなまし法で少し磨いてから集団に戻す | 「広く探す」と「細かく仕上げる」の両立 |
| レプリカ交換法(並列テンパリング) | 温度のちがう焼きなまし法を何本も同時に走らせ、ときどき解を交換する | 焼きなまし法の「手分けしにくい」欠点をおぎなう |
| 焼きなまし法を何回か実行して最良を採る | 出発点や乱数を変えて数回実行 | 結果のばらつきをおさえる(例題1・2のステップでも行った) |
カークパトリックらが最初の例にした「回路の部品の配置」は、今も焼きなまし法の代表的な使い道である。たとえば、FPGA(あとから回路を書きかえられる半導体)の研究で広く使われている配置ツール「VPR」は、部品の置き場所を決めるのに焼きなまし法を使っている。部品の数は何万〜何十万にもなるが、「2つの部品の場所を入れかえる」という単純な近所の作り方で、配線の短い配置を見つけている。
Ⅱ 例題データ
| 名前 | 内容 | 使う場所 |
|---|---|---|
配達先 | 12か所の地点の名前と位置(横・縦、km)。授業用の架空の町 | Ⅰ(操作教材)、例題1 |
荷物、容量 | 10個の荷物の重さ(kg)と価値(点)。容量は20kg | 例題2 |
このページで用意した関数:経路の長さ()、経路を描く()、経路の近傍()、山登り()、焼きなまし()。データを書き換えてしまったときは、ページを再読み込みすると元に戻る。
Ⅲ 例題1:配達の順番を決める(巡回経路問題)
本店を出発して11か所に配達し、本店に戻る。移動距離が最も短くなる順番を探す。これは巡回セールスマン問題と呼ばれる有名な問題で、地点が増えると全探索は不可能になる。
やってみよう:経路が短くなるようすを見る
「山登り法を100回」を何度か押すと、やがて1回も移れなくなる(局所的最適解)。「番号順に戻す」のあと「焼きなまし法」を試して、最良の長さを比べよう。見つかっている最短は 36.24 km である。
見るところ:番号順に回ると経路が何度も交差し、長い。12地点でも候補は約2,000万通りある。
いちばん素朴な作り方は、「いまいる地点から、まだ行っていない最も近い地点へ進む」をくり返す最近傍法である。これは貪欲法の一種で、一瞬で経路ができる。
読み取り方:番号順(約60 km)よりずっと短いが、最後のほうで遠くに残った地点へ大きく戻るため、39.52 km にとどまる。図に交差が残っていることを確かめよう。山登り法・焼きなまし法は、この経路を出発点にしてもよい。
最近傍法は、「いまいちばん近い所へ行く」をくり返すだけなので、先のことを考えない。夏休みの宿題を、その日にいちばん楽なものから片付けていくと、最初は順調でも、最後に面倒な自由研究と読書感想文がまとめて残って苦しくなる。最近傍法の「最後に遠くの地点へ大きく戻る」は、これと同じことが起きている。
貪欲法(どんよくほう、greedy)の「貪欲」は「目先の得に飛びつく」という意味である。速くてそこそこ良い答えを出すが、最適とは限らない。
読み取り方:左の図では、長さが階段状に下がって途中で止まる(それ以上良くなる近傍がない=局所的最適解)。
毎回の候補は、2-optで区間をでたらめに選んで作る。ほとんどの候補は今より長くなるので却下され、そのあいだ長さは変わらない(階段の平らな部分)。たまに短くなる候補が見つかると、そこへ移って長さが一段下がる(階段の段差)。経路が良くなるほど「短くなる候補」は減るので、段差の間隔はだんだん広がり、最後は平らなまま動かなくなる。
読み取り方:最初のうちは長さが上下するが、やがて山登り法より短い経路(36.24 km)に落ち着いた。図の経路に交差がないことを確かめよう。
12地点の経路で、2-optを1回行うと、長さはだいたい数km変わる。開始温度5は「5 km くらい長くなる変更でも、はじめのうちは37%くらいの確率で受け入れる」ことを意味する(exp(−5÷5) = 0.37)。「悪くなる量と同じくらい」という目安どおりの設定である。地点の範囲が100 km四方の問題なら、悪くなる量も大きくなるので、開始温度も大きくする必要がある。
読み取り方:山登り法は最良では焼きなまし法と並ぶが、平均と最悪が悪い(出発点によって結果が変わる)。焼きなまし法は10回とも36〜37 kmに収まった。
Ⅲ 例題2:荷物を選ぶ(ナップサック問題)
容量20kgのリュックに、価値の合計が最も大きくなるように荷物を選ぶ。解は「入れる/入れない」の並びである。
焼きなまし法は「小さいほどよい」値を扱うので、価値の合計に−1を掛ける。容量を超えた解には大きな罰を加える。
| 解の例 | 重さ | 価値 | 評価の値(小さいほどよい) |
|---|---|---|---|
| 何も入れない | 0 kg | 0 | 0 |
| テント・食料・水 | 18 kg | 26 | −26 |
| 最適解(価値38) | 20 kg 以下 | 38 | −38(いちばん小さい) |
| 全部入れる | 37 kg(17 kg オーバー) | 57 | 100 + 17×10 = 270 |
価値を最大にする問題が、「評価の値を最小にする」問題に変わっていることを確かめよう。
容量オーバーの解を「絶対に選ばない(禁止)」にする方法もある。しかし、焼きなまし法では、いったん少しオーバーして、そこから別の荷物を出すという回り道が、良い解への近道になることがある。たとえば「寝袋を出してテントを入れたい」とき、1つずつしか入れ替えられないので、「テントを入れる(一時的にオーバー)→ 寝袋を出す」の2歩が必要になる。
そこで、オーバーした解も一応は候補として認め、そのかわり評価に大きな罰点を足して「とても悪い解」として扱う。これをペナルティ法という。罰を「100+オーバーした量×10」としたのは、次の2つのためである。
- 荷物の価値は全部足しても57なので、評価の値は最も良くても −57。罰を100以上にすれば、オーバーした解は「何も入れない解(0)」よりも必ず悪くなる。最終的な答えにオーバーした解が選ばれることはない。
- 「×10」の部分で、少しのオーバーより大きなオーバーのほうが悪くなる。少しオーバーした解から容量内に戻りやすくなる。
道路の「駐車禁止」は、車が物理的に止まれないわけではない。止めることはできるが、反則金という罰がある。罰が十分に大きければ、ふつうはだれもそこに止め続けようとはしない。ペナルティ法は、これと同じように「入ってもいいが、損をする」場所として、容量オーバーの領域を扱っている。
荷物が10個なら候補は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個なら全探索は不可能なので、こうした近似手法に頼ることになる。
ナップサック問題の貪欲法は、「重さ1kgあたりの価値」が高い順に、入る限り詰めていく方法である(1957年にダンツィクが提案)。
読み取り方:この問題では、貪欲法でも最適解(価値38)になった。ただし貪欲法はいつも最適とは限らない。たとえば容量10kgで、A(6kg・価値9)、B(5kg・価値7)、C(5kg・価値7)なら、貪欲法は割安なAを先に入れて価値9で終わるが、最適はB+Cの価値14である。
旅行の荷造りで「小さくて役に立つもの」から詰めていくのは、だれでも自然にやる貪欲法である。たいていはうまくいくが、最後に「大きいけれど絶対に必要なもの」が入らなくなることがある。そんなとき人は、いったん詰めたものを出して入れ直す。この「出して入れ直す」が、焼きなまし法の「一時的に悪い状態を受け入れる」ことにあたる。
1978年、マークルとヘルマンは、ナップサック問題が難しいことを利用した暗号(ナップサック暗号)を発表した。「荷物の重さの合計だけを知らされても、どの荷物を入れたかは分からない」という性質を、秘密を守るのに使ったのである。ところが数年後、シャミア(RSA暗号の「S」の人)が、この暗号の弱点を突いて解読する方法を示した。問題そのものは難しくても、作り方にすきがあると解けてしまうという教訓として知られている。
焼きなまし法が最適解にたどり着く割合は、設定によって変わる。12通りの設定で10回ずつ試す(少し時間がかかる)。
読み取り方:開始温度が高く、ゆっくり冷やす設定(開始温度10・冷却率0.998)が最もよく最適解に着く。開始温度2では、罰(容量超過で100以上)の山を越えられず、ほとんど着かない。開始温度は「悪くなる量」と同じくらいという目安(Ⅰのステップ5)の意味がここで分かる。
Ⅲ 例題3:2変数の関数の最小化(GenSAパッケージ)
Rには焼きなまし法のパッケージ GenSA がある。谷がたくさんある2変数の関数で、ふつうの最適化関数 optim(局所探索)と比べる。
これまでは x だけを動かす「1本の道の上の谷」だった。2変数では x と y の2つを動かすので、地図の上の谷になる。下のプログラムの図は、地形図(等高線)と同じ見方をする。色の違いが高さ(関数の値)を表し、等高線で囲まれた小さな輪の1つ1つがくぼみである。
この関数は、ゆるやかなおわん形(真ん中が低い)の上に、たまごパックのような小さなくぼみがたくさん並んだ形をしている。小さなくぼみの1つ1つが局所的最適解で、おわんの真ん中(原点)が大域的最適解である。
optimは R に最初から入っている最適化関数で、何も指定しないと「ネルダー=ミード法」という局所探索を使う。三角形を伸ばしたり縮めたりしながら、坂を下る方向へ転がしていく方法である。速いが、出発点の近くの谷で止まる。GenSAは Generalized Simulated Annealing(一般化焼きなまし法)の略である。このページの焼きなまし関数より工夫が多く、温度の下げ方や近所の解の作り方を自動で調整する。lower、upperで探す範囲を、max.time = 2で「最大2秒まで探す」ことを指定している。
読み取り方:出発点 (4, 4) から始めると、optim は近くの谷(値1.94)で止まり、GenSA は原点の大域的最適解(値0)にたどり着いた。
Ⅳ 自分の興味のあるデータで分析する
このページの生成AIに、データとRのプログラムを作らせて実行する。上から順にボタンを押していけばよい。
最初にボタンを押したとき、授業用パスコードを聞かれる。授業で伝えたものを入力する。
テーマの例:観光地めぐり/宅配の配達先/学校の各教室/お祭りの屋台
テーマ: 地点の数:
追加の希望(なくてよい):
(30秒〜1分ほどかかる)ステップ2のプログラムが下の枠に入る。「▶ 実行」を押す。プログラムは自分で書き換えてもよい。
エラーが出たら: (直したプログラムが上の枠に入るので、もう一度「▶ 実行」を押す)
| 観点 | 確かめ方 |
|---|---|
| 経路の長さは短くなったか | 番号順の経路と比べて、山登り法・焼きなまし法でどれだけ短くなったか |
| 焼きなましの推移の形 | 最初は上下に揺れ、後半で落ち着いているか。揺れないなら開始温度が低すぎ、最後まで揺れるなら冷却率が大きすぎる |
| 安定しているか | 初期解を変えた5回で、結果の長さのばらつきは小さいか。山登り法と比べてどうか |
| 図は妥当か | 描いた経路に交差(×の形)が残っていないか。残っていれば、回数を増やすと改善することが多い |
| 結果を言い過ぎていないか | 見つかった経路が「最短」とは限らない。「見つかった中で最も短い」と言う |
(参考)生成AIに送った指示文を見る
データを作る指示
(まだ送っていません)
プログラムを書く指示
(まだ送っていません)
課題
このページの最後にある「課題用:生成AIで経路の最適化」を利用して、自分で決めたテーマのデータ(生成AIを利用して良い)で焼きなまし法による巡回経路の最適化を行い、その結果を3ページ程度のレポートにして提出せよ。レポートの形式は自由である。
なおファイル名は 学生番号_名前.docx とする。たとえば k24x7777_東女花子.docx である。
(提出方法・期限はWebClassの指示に従うこと)
レポートに入れるとよいもの(例)
- テーマと、なぜそのテーマを選んだか
- データの説明(地点の数、配置の特徴)
- 番号順・貪欲法・山登り法・焼きなまし法の経路の長さの比較
- 焼きなまし法の推移のグラフと、見つかった経路の図
- 初期解を変えて5回ずつ実行した結果(最良・平均・最悪)
- 考察:焼きなまし法は安定して良い経路を出したか、図に交差が残っていないか、設定(回数・開始温度・冷却率)を変えるとどうなったか、「最短」と言ってよいか
生成AIの考察は、そのまま写さず、実行結果の数値と見比べて確かめてから、自分の言葉で書き直すこと。AIの考察に誤りや言い過ぎを見つけたら、それもレポートに書いてよい。
課題用:生成AIで経路の最適化(データ作成 → プログラム → 実行 → 考察)
テーマを決めて、上から順に4つのボタンを押していけばよい。結果はレポートの材料として使う。
最初にボタンを押したとき、授業用パスコードを聞かれる。授業で伝えたものを入力する。
テーマの例:観光地めぐり/宅配の配達先/学校の各教室/お祭りの屋台/テーマパークのアトラクション
テーマ: 地点の数:
追加の希望(なくてよい):
(30秒〜1分ほどかかる)[2]のプログラムが下の枠に入る。「▶ 実行」を押す。図は右クリック(スマートフォンでは長押し)で保存するか、スクリーンショットを撮ってレポートに貼る。
エラーが出たら: (直したプログラムが上の枠に入るので、もう一度「▶ 実行」を押す)
[3]の実行結果(文字の出力)を生成AIに渡して、考察を書かせる。図そのものは渡さない。
(30秒〜1分ほどかかる)テーマ、データの説明、プログラム、実行結果、AIの考察を1つの文章にまとめてコピーする。Wordに貼り付けて、レポートの下書きに使う。
(参考)生成AIに送った指示文を見る
[1]データを作る指示
(まだ送っていません)
[2]プログラムを書く指示
(まだ送っていません)
[4]考察を書く指示
(まだ送っていません)