最適化問題とは（全体像）
最適化問題は、「条件を守りながら、いちばん良い選び方を見つける」問題のこと。たとえば「配達ルートを最短にする」「限られた容量に価値の高い荷物を詰める」など。
ところが、こうした問題のなかには正解を1つずつ確かめると、組み合わせが爆発的に増えて現実的な時間で解けないもの（NP困難な問題）がある。巡回セールスマン問題（全部の街を最短で回る順番）が代表だ。
そこで、解き方を場面で使い分ける。
- 厳密解法 … 必ず最適な答えを出す。ただし問題が大きいと時間がかかりすぎる。
- メタヒューリスティック … 最適とは限らないが、そこそこ良い答え（近似解）を速く出す。大きな問題向き。
詳しく：厳密解法とメタヒューリスティックだけ覚えれば戦える
ここが記事の心臓部。まずは2系統の使い分け。
解き方の使い分け
| 系統 | 特徴 | 向く場面 |
|---|---|---|
| 厳密解法 | 必ず最適解を出す | 小さめの問題 |
| メタヒューリスティック | 近似解を高速に出す（最適とは限らない） | 大きな・難しい問題 |
いちばん大事なのが、メタヒューリスティックが出すのは「近似解」だということ。最適解である保証はないが、現実的な時間で「かなり良い答え」を出せる。大きな問題ではこちらが頼りになる。つまり、最適解の保証よりも「現実的な時間で良い答え」を優先するのがメタヒューリスティックだ。
代表的なメタヒューリスティックを押さえる。
代表的なメタヒューリスティック
| 手法 | 何をまねている |
|---|---|
| 遺伝的アルゴリズム（GA） | 生物の進化（交配・突然変異・選択） |
| 焼きなまし法（SA） | 金属を熱してゆっくり冷ます過程 |
| 粒子群最適化（PSO） | 鳥や魚の群れの動き |
遺伝的アルゴリズム（GA）は、良い答えどうしを「交配」させ、たまに「突然変異」を起こして、世代を重ねて良くしていく。焼きなまし法（SA）は、最初は「多少悪くなる動き」も受け入れて広く探し、だんだん受け入れを厳しくして良い答えに落ち着く（金属の焼きなましのイメージ）。
なお、「GAが常に最速・最良」とは限らない。問題に応じて手法を選ぶのがポイントだ。
わかりやすく言い換えると
要するに、最適化は「条件のなかでいちばん良い答えを探す宝さがし」だ。
①厳密解法 … 地図をすみずみ全部しらべる（必ず宝にたどり着くが、広いと時間がかかる）
②メタヒューリスティック … 勘とコツでアタリをつけて速く探す（完璧ではないが、広い土地でも現実的な時間で良い答えにたどり着く）
GAは「良い者どうしをかけ合わせて世代交代」、SAは「最初は大胆に、だんだん慎重に探す」イメージ。大きな問題ほど、この「近似で速く」の出番になる、というわけだ。
試験のツボ
🔴 一番出る：メタヒューリスティックは近似解
①最適解である保証はない（近似解）
②そのかわり大きな問題でも高速に良い答えを出せる
🔴 次に出る：厳密解法との使い分け
①厳密解法＝必ず最適解（小さめの問題向き）
②メタヒューリスティック＝近似解を高速（大きな問題向き）
🟡 押さえると安定：代表的な手法
①遺伝的アルゴリズム（GA）＝進化をまねる
②焼きなまし法（SA）＝金属を冷ます過程をまねる
よくある間違い
①「メタヒューリスティックは必ず最適解を出す」→ ✗ 出すのは近似解。最適である保証はない。
②「遺伝的アルゴリズム（GA）が常に最速・最良の手法である」→ ✗ 問題に応じて手法を選ぶ。SAやPSOが向く場合もある。
③「厳密解法はどんな大きな問題でも一瞬で解ける」→ ✗ 大きいと組み合わせが爆発し、時間がかかりすぎることがある。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（メタヒューリスティックの性質）
メタヒューリスティックに関する次の記述のうち、正しいものはどれか。
- 最適とは限らない近似解を高速に出す手法で、大きな問題に特に向いている
- つねに最適解を出すことが保証されており、厳密解法とまったく同じである
- 小さな問題でしか使えず、大きな問題ではまったく役に立たない手法である
- 計算をせずに答えを丸暗記するだけで、新しい問題には対応できない手法だ
解答は 1 だぜ。
メタヒューリスティックは最適とは限らない近似解を高速に出す手法で、組み合わせが爆発する大きな問題に向いている。最適解の保証はないが、現実的な時間で良い答えが出せるんだ。
選択肢2は「つねに最適解・厳密解法と同じ」が誤り。選択肢3は「大きな問題で役立たない」が逆。選択肢4は「丸暗記」が誤りだぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 近似解を高速・大きな問題向き |
| 2 | ✗ | 最適解の保証はない |
| 3 | ✗ | 大きな問題でこそ役立つ |
| 4 | ✗ | 丸暗記ではなく探索する |
オリジナル問題2（厳密解法との使い分け）
厳密解法とメタヒューリスティックの使い分けに関する次の記述のうち、正しいものはどれか。
- 厳密解法は近似解しか出せず、メタヒューリスティックだけが最適解を出せる
- どちらも性能はまったく同じで、問題の大きさによる使い分けは不要である
- 厳密解法は必ず最適解を出すが大きな問題だと時間がかかり、近似解は高速だ
- 厳密解法は大きな問題ほど速く、メタヒューリスティックは小さな問題専用だ
解答は 3 だぜ。
厳密解法は必ず最適解を出すが、大きな問題だと時間がかかる。一方メタヒューリスティックは近似解を高速に出すから、大きな問題向きだ。問題の大きさで使い分けるんだな。
選択肢1は厳密解法と近似解法が逆。選択肢2は「使い分け不要」が誤り。選択肢4は「厳密解法が大きいほど速い」が逆だぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 厳密解法が最適解を出す |
| 2 | ✗ | 大きさで使い分ける |
| 3 | ✓ | 厳密＝最適だが遅い・近似＝高速 |
| 4 | ✗ | 厳密解法は大きいと遅くなる |
オリジナル問題3（代表的な手法）
メタヒューリスティックの代表的な手法に関する次の記述のうち、正しいものはどれか。
- 遺伝的アルゴリズムは、文字を1つずつ照合する検索だけに使う手法である
- 遺伝的アルゴリズムは進化を、焼きなまし法は金属を冷ます過程をまねる
- 焼きなまし法は、データを必ず昇順に並べ替えるためだけの手法のことだ
- どの手法も乱数を一切使わず、つねに同じ手順だけで答えを出すものである
解答は 2 だぜ。
遺伝的アルゴリズム（GA）は生物の進化を、焼きなまし法（SA）は金属を冷ます過程をまねている。自然や物理の現象を計算に持ち込んで、良い答えを探すんだ。
選択肢1は「文字照合の検索」が誤り。選択肢3は「並べ替え専用」が誤り。選択肢4は「乱数を使わない」が誤りだぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | GAは進化をまねる最適化手法 |
| 2 | ✓ | GA＝進化・SA＝焼きなましをまねる |
| 3 | ✗ | SAは並べ替え専用ではない |
| 4 | ✗ | 乱数を使う探索が多い |
まとめ
押さえどころ
- 🔴 メタヒューリスティック ＝ 近似解を高速に出す（最適保証なし）。大きな・難しい問題向き。
- 🔴 厳密解法との使い分け ＝ 厳密解法は必ず最適解だが大きい問題は遅い、近似解は高速。
- 🟡 代表手法 ＝ 遺伝的アルゴリズム（進化）・焼きなまし法（金属を冷ます過程）をまねる。
次に学ぶ
- OR・線形計画法（シンプレックス） ── 厳密解法の代表である線形計画法。最適化の「必ず解ける側」を押さえると全体像がつかめる。
- 計算量（NP困難） ── なぜ大きな問題で近似が必要になるのか、その理由を与える考え方。最適化とセットで理解したい。
執筆: SikakuQuest編集部