写真，職位は取材当時のものです．

組合せ最適化問題とメタ戦略

永田先生が取り組まれている最適化問題とはどのような問題ですか？

最適化問題とは与えられた条件を満たす解の中で最も良いものを見つける問題です．特に最適な組み合わせを見つけることを「組合せ最適化問題」と呼びます．例えば，自宅から学校までの最短経路を求める問題は最短経路問題と呼ばれる組合せ最適化問題です．N個の点（交差点など）と任意の2点間に距離が定義されている時，指定したスタート点からゴール点へ至る最短経路を見つける問題として定式化されます．この問題の最適解（最短経路）は動的計画法と呼ばれる手法を用いることで，Nが100万くらいであっても高速に最適解を得ることができます．

最適解の発見にかなりの時間がかかってしまう組合せ最適化問題も多いと聞きますが．

例えば，巡回セールスマン問題は，全ての点を辿る巡回路の中で最も短いものを見つける問題ですが，Nが100程度でも現実的な計算時間で最適解を発見することが困難です．そこで，近似解（条件を満たす解の中でなるべく良い解）を見つけるための近似解法が用いられます．近似解法の一つとして，近年，メタ戦略に基づく解法が広く使われるようになっています．

メタ戦略とは何ですか？

メタ戦略とは探索的/ヒューリスティックな手法に基づいて短時間で高精度の近似解を求める近似解法の枠組みです．近年，計算機の性能向上に伴い，大規模な組合せ最適化問題に対してメタ戦略に基づく解法を用いて短時間に高精度の近似解を得ることが可能になってきています．

高性能メタ戦略アルゴリズムの開発

永田先生は高性能メタ戦略アルゴリズムを開発されているそうですね．

本研究室ではオペレーションズ・リサーチの世界で古くから研究されている巡回セールスマン問題，車両配送問題（宅配便の配送計画），ジョブショップスケジューリング問題（工場の作業工程のスケジューリング），時間割作成問題などの基本的な組合せ最適化問題に対して，高性能メタ戦略アルゴリズムを開発してきました．これらの問題は現実の問題を単純化してモデル化した組合せ最適化問題で，いずれも問題規模が大きくなると最適解を求めることが事実上不可能となる，いわゆるNP困難問題です．

なんだか聞くだけでも難しそうな問題ですね．

これらの問題には組合せ最適化問題の本質的な難しさがモデル化されており，ここで開発された強力な近似解法は同種のより複雑な問題に対する近似解法を構成する際のひな形として用いることができます．また，代表的な組合せ最適化問題にはベンチマーク問題が整備されており，開発した近似最適化手法が他手法に比べてどのくらい優れているか比較することができます．本研究室では代表的組合せ最適化問題に対してベンチマーク問題の既知最良解を更新するような高性能メタ戦略アルゴリズムを考案しました．下図は巡回セールスマン問題とジョブショップスケジューリング問題のベンチマーク問題に対して得られた新しい最良解を示しています．

 10万点巡回セールスマン問題と300作業ジョブショップスケジューリング問題に対して更新した最良解

既知最良解の更新が永田先生の研究のすごいところですね．

私の研究の面白さは，対象とする最適化問題の特徴や問題の本質的な難しさを解決するアイデアを解法に盛り込むことで，飛躍的に解法の性能が向上するところにあると考えています．また，考案した解法を計算機上に実装する際，アルゴリズムやデータ構造の工夫により計算効率が大きく変わるので，効率的な実装法を開発することも研究上の楽しさの一つですね．巡回セールスマン問題のような有名な問題のベンチマーク問題に対しては非常に多くの解法が適用されており，既知最良解を更新することは非常に困難なチャレンジですが，このような問題に対して既知最良解を更新することに研究のやりがいを感じます．

汎用的なメタ戦略アルゴリズムをめざして

永田先生の研究の展望をお聞かせ下さい．

メタ戦略を探索エンジンとした最適化システムの一般的な問題点として汎用性と拡張性の低さが指摘されています．優れたメタ戦略アルゴリズムを構築するためには問題の性質をうまく取り込んだ設計が必要となるため，メタ戦略の専門家が問題ごとに専用アルゴリズムを考案しているのが現状です．また，実務レベルの複雑性を持った実問題は完全にモデル化すること自体が難しく，メタ戦略の専門家が最適化システムを構築したとしても，システムの運用に伴い新たな制約の追加や目的関数の変更といった要望が出てくるのが普通です．しかし，利用者が変更に応じて適切にアルゴリズムを修正することは容易ではありません．これらの問題点に対処するため，今後の研究では（ある問題クラスの範囲で与えられた）任意の組合せ最適化問題に対し，その問題に適したメタ戦略アルゴリズムを自動的に構成する機能を持つ汎用的な近似最適化法（自動メタ戦略構成システム）を構築していきたいと考えています．