ビジネス・アナリティクス - 最適化とアルゴリズム


最適化とアルゴリズム


IBM東京基礎研究所における最適化・アルゴリズムの研究は非常に長い伝統を持っています。我々はこれまで、大規模で複雑な現実世界の問題を、各種の最適化手法を適用することで解決してきました。1990年代から継続して取り組んでいる代表的な事例には、鉄鋼業における最適化とロジスティックスの最適化があります。これらの問題は、制約が非常に多くて複雑であること、また組合せ的に解空間のサイズが大きくなることから、汎用的な最適化手法ではうまく解決できません。お客様の課題を正確に把握し、整理して最適化問題として扱えるようにモデル化し、問題の性質や構造をうまく利用して効率的なアルゴリズムを設計することが必要になります。またIBM ILOG CPLEXなどの最適化ソルバーの性能は、近年非常に高くなっており、既存のツールを部分的にうまく使っていくことが、開発スピードの観点でも重要になっています。

また、近年では最適化の前提となる情報が確定していない、確率的なシステムの最適化に取り組んでいます。本来確率的であるのに確定的な値として取り扱って最適化をしても、現実においては改善につながらないことがあります。入力情報を確率的なものとして扱いつつ、数理計画やマルコフ決定過程などで最適化しやすいようにモデル化します。具体的な応用先には、仮想化環境における計算機資源の割り当て最適化や、発電計画や蓄電池の充放電計画の最適化などがあります。仮想機械の資源使用量や、消費電力量などは確定しておらず、これらの予測値を確率的な入力として最適化します。また、先進的な基礎研究として、リスクを考慮した最適化に関する研究を進めています(T. Osogami, "Iterated risk measures for risk-sensitive Markov decision processes with discounted cost," UAI 2011)。期待値や期待効用では表現できないリスク嗜好を表現するにはどのようなリスク指標を使えば良いか、またそのようなリスク指標に基づいて効率的に最適化をするためのアルゴリズムについて研究をしています。

最近の主要な研究成果としては、ランダムウォークの解析技術の開発があります(T. Osogami and R. Raymond, "Semidefinite optimization for transient analysis of queues," ACM SIGMETRICS 2010 参照)。我々は、半正定値計画・双対理論・最適性条件などの最適化理論を駆使して、ランダムウォークの性質を解析する手法を提案しました。基本的な確率過程であるランダムウォークの解析結果は待ち行列解析、アルゴリズムの性能解析、実験計画など多くの応用があります。また、ランダムウォークの新しい解析手法は、より複雑な確率過程の解析への応用も期待されます。提案手法によって、ランダムウォークが所定の領域を通過する確率の上下界を、大偏差定理やマルチンゲールを用いる従来手法よりも高精度で求められることが示されました。また、提案手法は解析的な上下界を求めることができ、これまでほとんど何も知られていなかった、待ち行列の過渡状態における性質を明らかにすることにも成功しました(T. Osogami and R. Raymond, "Simple bounds for a transient queue," IEEE/IFIP DSN 2011 参照)。我々は、本提案手法を拡張することで、確率的なシステムを最適化することができると考えており、基礎研究を継続しています。

ランダムウォークの性質を半正定値計画で解析

図1. ランダムウォークの性質を半正定値計画で解析

その他の最近の研究成果としては、最短経路問題の研究が挙げられます。特に、道路ネットワークに代表されるような疎なグラフにおける全点対間最短経路問題に対して、SIMD (Single Instruction Multiple Data) 命令を利用した高速なアルゴリズムを開発しました (H.Yanagaisawa, IPDPS 2010 参照) 。提案手法は、ダイクストラ法を繰り返し適用する方法に比べて数十倍以上の高速化を実現しています。密なグラフではなく疎なグラフに対して SIMD 命令を活用して高速化した研究はこれが世界最初のものです。

疎なグラフにおける全点対間最短経路問題の解法

図2. 疎なグラフにおける全点対間最短経路問題の解法

図形充填問題に対しても近年主要な研究成果を挙げています。二次元の図形や三次元の物体を障害物と衝突しないようにうまく配置する問題ですが、これはたとえばワイヤーハーネスの配置問題など広い産業応用を持ちます。これに対しては、図形や物体を円や球の集合で近似してから、円や球の集合の配置を求めるという汎用的な解法の研究などを行っています。特に円や球で図形を近似する方法は、図形の連続的な角度の回転も扱うことができる点で優れています(T.Imamichi and H.Nagamochi, SLS2007)。

図形を円の集合で近似して配置を計算

図3. 図形を円の集合で近似して配置を計算

また、図形充填問題に対する最適化手法を用いて、モアレ・ムラが極めて少ない液晶ディスプレイを作るためのドットパターンの生成に成功しました(T. Imamichi et al., “Nonlinear Optimization to Generate Non-overlapping Random Dot Patterns,” WSC 2011)。規則的なドットパターンでは強いモアレ縞が出現してしまい、擬似乱数や超一様数列に基づくドットパターンでは輝度ムラが発生してしまいます。10年前に私達は、超一様分布列と分子動力学的モデルを組み合わせることで、超高品質のドットパターンの生成に成功していました。今回、図形充填問題に対する最適化手法を用いることで、更に高品質のドットパターンをより高速に生成できることを示しました。

高品質なドットパターン作成の例

図4. 高品質なドットパターン作成の例


詳細情報へのリンク