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

超ロバストとは何か?

組合せ最適化と超ロバスト

数理工学の中の研究分野の1つに、「組合せ最適化」という分野がある。簡単に言えば「たくさんの(有限個または可算無限個の)選択肢の組合せの中から、ある制約条件を満たし、最も望ましい組合せを選び出す」という問題と解法を指す。

組合せ最適化の問題例としてよく上げられるのは、複数の都市をすべて1度だけ回って最小限のコストで帰ってくる経路を求める、という「巡回セールスマン問題」だ。

制約条件を満たすすべての組合せ(この場合は一筆書きで元の場所に戻ってくる経路)を列挙する「総当たり法」では、都市数が増えると組合せの数が爆発的に増えて、計算可能な時間内に列挙できなくなる。どう工夫するか、というのがこの問題の肝で、さまざまな最適化手法を生み出し計算機理論を発展させる源となった。

問題の性格(数学的性質)によっては、総当りをせずに候補を絞り込める場合がある。逆に言えば、問題を解くのに便利ないい数学的性質をうまく見つけ出すことが、組合せ最適化の問題を解くカギになる。

一例として、線形計画問題(LP)については、効率のよい計算法(単体法など)が知られているが、大規模な問題を解くには組合せ最適化の考え方を使った改善策が欠かせない。

線形計画問題では、制約条件として与えられた式(等式や不等式)から、その条件を満たす解が存在する範囲(許容領域)を示す凸多面体を構成すると、その多面体の各頂点の座標が最適解の候補になる。(単に凸多面体と書いたが、3次元を超える場合を含むので、超多面体と書いたほうがよいかもしれない。)

左図は制約条件が4つの不等式で与えられ、その下で目的関数zを最大化する(x,y)を求めるという2変数の線形計画問題を示している。変数はxとyの2つなので許容領域は平面上に示せる。(0,0)、(0,2)、(2,3)、(3,0)の4つの頂点が最適解の候補で、この例ではすべての頂点について目的関数の値を計算すると(2,3)が最適と分かる。

この例では4つしか頂点がないが、変数や制約条件の数が多くなると頂点の数が爆発的に増える。すべての頂点について目的関数を計算して比較する、という方法では現実的な時間内に計算が終わらない。

単体法ではどこか1つの頂点から始め、より良い結果が得られる方向に頂点がないかどうかを順に探していく。

凸多面体グラフの枝(辺)には目的関数の値が改善される方向へ「向き」を与えられる。もしすべての枝について、どの部分グラフにも巡回がないように向きを与えられれば(これを「LP-向き付け」という)、目的関数の値が単調に改善される経路(複数)が得られて、各経路の終点が最適解の候補になる。つまり最適解の候補がうまく絞り込める。

ところがすべての問題について、常にLP-向き付けができるとは限らない。また、向き付けが可能かどうかを判定する方法がいくつか考案されているが決め手になるものはない。最近は元の多面体と双対な多面体(元の多面体の頂点が、双対な多面体では面に対応する)を考えて、それを構成する各面をある規則に沿って張る(シェリング)ことができるかどうか(シェラビリティー)を調べる、という研究が、重要な成果をあげつつある。


さまざまな組合せ最適化の問題について、幾何的に多面体を与えて、例えば向き付けをすることができれば、その向き付けを見ただけで、ある組合せ位相的性質を幾何的に実現できるかどうかが分かるようになるかもしれない。

多面体にはいろいろな表し方があり、表層的な性質を扱うのか、もう少し基本的な性質を扱うのかによってそれぞれを使い分ける。問題によって、優れた性質を扱える構造をうまく取り出すと、不要なものをきれいに落とすことができる。

いい性質を持った構造をうまく見つけ出す普遍的な方法論が導ければ、それが数学的な意味での超ロバストにつながるだろう。

ホーム > 8-basic.html