ホーム
超ロバストをさぐる 1
Bell不等式による量子性判定での超ロバスト性
CFTP を用いた Perfect Sampling
制御における(超)ロバスト性
超ロバストとKM2O-ランジュヴァン方程式論に基づく時系列解析
ロバスト符号化
超ロバストをさぐる 2
ロバスト構造化文書処理技術
幾何計算に求められるロバスト性
ロバスト分子計算
統計的諸手法に現れるロバスト性の概念
超ロバスト並列処理の未来に向けて
超ロバストとは何か?
ロバストと超ロバスト
発端:超ロバスト幾何計算
超ロバストとメタヒューリスティクス
超ロバスト制御の可能性
ロバスト構造化文書処理技術がもたらすもの
実験数学-時系列データの超ロバストな評価法
統計から見た超ロバスト
組合せ最適化と超ロバスト
分子計算機と超ロバスト
超ロバスト並列処理

超ロバストとメタヒューリスティックス

ヒューリスティックスを組み合わせて超ロバスト化

組み合わせ最適化という分野がある。その中でも比較的難しい問題、つまり最適解を見つけるのが難しい問題に関して、なるべくいい解を見つけるという方法論の1つがヒューリスティックス。

なるべくいい解を見つけようという精神の中にもいろいろな方法がある。

  • すべての問題についてある程度いい解を出そうという解法
  • だいたいの問題についてかなりいい解を出そうという解法
  • 最悪の場合でも最低限の解を出そうという解法...etc.

非常に危険な事態でも飛行機が落ちないようにする方法もあれば、非常に運の悪い場合は落ちてしまうけれども、大体の場合には大丈夫という方法もある。
ヒューリスティックスは、ある特定の問題に対して、その特徴をつかんでうまく解くというオーダーメイド的な手法。つまりどんな場合にも適用できるというものではないし、最適解かどうかの保証もない。

ヒューリスティックスの例としては、「やきなまし法」や「遺伝アルゴリズム」、「タブー探索法」などがある。もう少し簡単な例を考えよう。

例えばテーマパークにある巨大迷路の中を、マップなしで歩く場合を考える。たいていの迷路は入り口から入って右か左の壁つたいに歩けば出口にたどりつける。ただし、この方法は迷路の中に、外側の壁から離れた島があってその中に出口があるとか、逆に入り口がある、といった場合には失敗する。そういう意味でこれはヒューリスティックな歩き方といえる。

ちなみに、迷路の歩き方を見つけるもっと確実な方法は、マップを作っていくこと。袋小路を塗りつぶしていくことで、正しい経路がわかる。現実的な時間内に、最適解や「良さの保証がある」解が出せるアルゴリズムが分かっている問題にはヒューリスティックスは不要。

ヒューリスティックスは1つの問題を見てその固有の特徴をどんどん使っていって非常に専用化したアルゴリズムを作っていく。理論的な保証はできないけれど、その問題については性能のいいものができる(計算機実験などでよい結果が出ることが示せるというものが多い)。しかし問題が少し違うものにになると、また最初から作り直さなければならない。

メタヒューリスティックスは、そういうヒューリスティックスを上から眺めて、いろんなものに対してうまくいくヒューリスティックスを作ろう、という考え方。固有の問題に対するアプローチを突き詰めるのではなく、いろんな問題について(もちろん組み合わせ最適化の理論で扱える性質を持った問題に限るが)、スケジューリング問題であろうとほかのタイプの問題であろうと、その枠組みにポンと突っ込んだらなんらかの答えを返してくれる、そういう枠組み。

そこで求められる超ロバストは、「どんな問題にも対応でき」、「最適解に近い解が得られること」。非常に多くの問題が扱えて、かなりいい解が出せる手法を作ろうと考えている。

ホーム > 3-basic.html