研究紹介: 組合せ最適化問題に対するメタヒューリスティクス

組合せ最適化問題と近似解法

組合せ最適化問題は、スケジューリングやネットワーク関連の最適化問題など、情報学・工学における基礎的な問題から実用的な応用問題にいたるまで、幅広い多くの重要な問題を含み、これらに対するアルゴリズムの設計・開発の研究は、数理情報学における重要な基礎分野のひとつである。しかし、その多くは、NP困難問題に代表されるように、厳密な最適解を効率的に求めることはきわめて困難である。
　このような問題に対する現実的手法として、よい解を速く求める近似解法がある。その基本戦略として欲張り法や局所探索法がよく知られているが、計算機の急速な進歩に伴い、これら基本戦略は通常極めて高速に実行できるようになった。そこで、これらの基本戦略よりももう少し時間をかけて、より精度の高い解を求めることに対する要求が高まってきた。この目的を実現するアルゴリズムの一般的枠組みを与えるのがメタヒューリスティクス（あるいはメタ戦略、メタ解法など）である。メタヒューリスティクスは、様々なアルゴリズムの総称であり、遺伝アルゴリズム、アニーリング法、タブー探索法など、近年話題になった多くのアルゴリズムを含んでいる。このような枠組みに基づいた高性能なアルゴリズムの設計や、役に立つ汎用解法の開発を目標に研究を進めている。具体的なテーマは以下のとおりである。

メタヒューリスティクスに基づく高性能アルゴリズムの設計

代表的な組合せ最適化問題は、様々な現実問題の基本的な構造や部分問題として現れる。よってこれらに対して精度の高い解を高速に求める高性能アルゴリズムの設計はきわめて重要な課題のひとつである。具体的には、一般化割当問題、集合被覆問題などを対象とし、排除連鎖法と呼ばれる高度な近傍操作、探索に必要なパラメータの適応的調整法、ラグランジュ緩和問題から得られる情報の探索への活用、大きな近傍を高速に探索するデータ構造の工夫などを行い、世界でもトップレベルの性能を得ることに成功している。また、100万変数を超えるかなり大規模な問題例に対しても適用可能な有用なアルゴリズムの設計も行っている。

メタヒューリスティクスに基づく汎用解法の開発

高性能アルゴリズムの開発で得られた知見を基盤として、より汎用性の高い問題に対して有用なアルゴリズムを開発することにも力を入れている。個々の問題に対してメタヒューリスティクスに基づくアルゴリズムを設計し、そのプログラムを用意するには、大きな労力と時間を要する。そこで、解きたい問題が現われるたびにそれ専用のアルゴリズムを開発するよりも、様々な問題を自然に定式化できる高い定式化能力を汎用的な問題に対するよいアルゴリズムをいくつか用意しておき、多くの問題を少数のアルゴリズムでまとめて扱うほうが便利であろうという方針である。具体的には、時間枠つき配送計画問題、２次元長方形配置問題、カッティングストック問題などに対して、従来とは異なる汎用化を考え、効率的アルゴリズムの開発を進めている。

木製パッキングパズル

組合せ最適化問題の難しさと面白さを専門外の人に実感してもらうことを目的に、図のような木製のパズルを作成した。２次元長方形配置問題の特別な場合で、もっとも基本的な「なるべく隙間なく詰め込む」パッキング問題である。長方形数９の小規模なものであってもかなり手ごわく、その難しさを十分実感できる。

メタヒューリスティクスはその性能の高さから大いに注目され、広く応用されているが、理論的性質は未解明の部分が非常に多い。このような理論面からの貢献も視野に入れつつ、理論と応用の両面からよい成果を出せるよう、今後も研究を進めて行きたいと考えている。

投稿者の所属・連絡先など

数理情報学専攻/自然情報学科数理情報系教授
yagiura “at” nagoya-u.jp
個人ホームページ: http://www.co.mi.i.nagoya-u.ac.jp/~yagiura/