• ホーム
  • 研究
  • 先人の知恵を礎に離散最適化を究め 現実の問題を解決に導く

先人の知恵を礎に離散最適化を究め 現実の問題を解決に導く

理工学部経営システム工学科
高澤 兼二郎准教授

  • 2019年6月6日 掲載
  • 教員紹介

多くの選択肢の中から最適な答えを求める「離散最適化」の研究を進める高澤兼二郎准教授。理論的な問題に対するアルゴリズムの構築を通じて、現実の諸問題を解決する手順を模索しています。

生活の中に存在する離散最適化の諸問題を追究

数学の理論に類する離散最適化の研究を進めています。離散最適化は、制約条件を満たす組合せの中から最も適切な解を求めるアルゴリズム(問題を解く手順)を見つける学問の分野です。日常の中でも自然と表れる問題で、身近な例では、カーナビや交通機関のルート探索、宅配業者の配送などに応用されています。

学生の頃から、いくつかの問題の解明に取り組んできました。離散最適化の世界は奥が深く、効率的に解が導き出せることがよく知られている問題もあれば、世界中の数学者が長い年月をかけて研究しても効率的に解を求められるのかどうかが解明できない未解決問題もあります。前者の代表例には「最小全域木問題」があり、未解決問題の一つには「巡回セールスマン問題」があります(図1、図2)。

図1 途中で断線することなく、全ての地点を 連結するルートを求める最小全域木問題を示 す概念図。解は複数存在する

図2 一巡して元に戻るルートを求める巡回セールス マン問題を示す概念図。訪れる地点の数が多くなる と複雑度が増し、計算しきれなくなる

図で示すと、どちらも複数の地点をつなぐ経路を求める問題で、あまり違いはないように見えますが、解くための考え方は大きく違ってきます。

ネットワーク構築などに使われる最小全域木問題は、複数の地点を漏れなく連結させることが目的なので、点から点へと枝を広げるようにルートをつなぎ、重複する経路を除いていけば、解が求められます。

一方、巡回セールスマン問題は、複数の地点を効率よく一巡りして始点に戻る最短経路を求める問題です。理論上は、全ての組合せをしらみつぶしに調べれば解けますが、通過する地点の数が30を超えると計算に要する時間が天文学的な値になり、この方法では、事実上、求解が不可能になるのです。

このように、定義や条件が少し異なるだけで問題の複雑さが増し、新たなアルゴリズムの設計が必要になるのが、離散最適化の興味深いところです。

先人が残した「巨人の肩」に立ち、知恵の蓄積に貢献したい

数学という学問は、あらかじめ決まっている一つの答えを計算することだと考えられがちですが、実はそうではありません。

まず、現実の問題をどのような数学的問題にモデル化・定式化するか、つまり、どのような離散最適化問題を解くべきかを考えるところから始まります。例えば、A地点からB地点への経路探索をするにしても、最短距離を移動したい場合と、移動コストを最小にしたい場合とでは結果が異なります。与えられた条件を満たす最適ルートが、同時に複数存在することもあります。

また、巡回セールスマン問題のように、最適解(条件を満たす最良の解)を求めるのは難しい場合は、近似解(最適とは断言できないが、条件に見合う解)を求める研究もあります。

いくつもの解が存在する中で、どの解を最終的な正解として選ぶのかは、判断する人次第になります。

学術研究の世界には「巨人の肩の上に立つ」という言葉があります。偉大な先人たちが築き上げてきた知恵の宝庫を礎にして、その上に新たな発見を積み重ねることを意味しています。

アルゴリズムの設計も同じで、全くのゼロの状態からアルゴリズムを作り上げるよりは、過去に解明されている手法を応用しながら、新たな手法の発見へとつなげていく研究が一般的です。私自身も、巨人の肩を借りながら、研究を一歩でも先に進め、知恵の蓄積に貢献していきたいと思っています。

学んだ知識を自分ごとに引き寄せ、実社会での問題を解決に導く

数学の理論的な問題は、解法が得られたからと言って、すぐに社会生活の役に立つことはあまりありません。しかし、実社会で起こるさまざまな問題を解決に導く原理原則を支えています。

お手本となる手順が明らかになっていれば、解決したい現象を数理モデル化して応用することで、複雑な問題も効率よく解決できるようになります。

例えば、ある学生は卒業論文のテーマとして、塾の講師の勤務シフトと生徒の通塾スケジュールをマッチングさせるプログラムを構築することに挑戦しました。自力でアルゴリズムを見いだせなくても、先人たちの知恵をひもとけば、何らかのヒントが見つかります。この例では、数学の専門書にも典型例が明示されている「ナース・スケジューリング問題」をアレンジすることで、解決の糸口としたのです。

大切なのは、基盤となる汎用的な知識を学ぶと同時に、それをどのように具体的な問題の解決につなげるかを自分の頭で論理的に考えることです。学生のうちに、実務での活用を想定して問題に取り組んだ経験は、社会での課題に向かい合う一助になるでしょう。その日を願って学生たちに寄り添いながら、未来への最適解を見つけるための手助けをすることも、私にとっての実践知だと考えています。

新たなチャレンジとして、応用範囲の広いゲーム理論に取り組む

近年は、離散最適化の研究を通じて得た経験や知見に基づき、「ゲーム理論」の研究に取り組んでいます。ゲーム理論とは、パズルゲームの解法や運用ではありません。主体となる対象(プレイヤー)が複数いて、個々の判断に基づいて行動する状態で、各プレイヤーがとる合理的な戦略について分析する学問分野です。

例えば、A地点からB地点まで自動車で移動したいとき、ほぼ同じ条件で行ける複数のルートがあるとします。できるだけ交通量が少ない道を選んで渋滞を避けたいけれど、他の人も同じことを考えて行動したら、結果的にその道は混雑してしまうので、他の人の行動も予測しながら、戦略的に自分の行動を決めることになります。

この問題の一つの最適解は、特定のプレイヤーだけが得をする結果ではなく、全体が最も効率的に行動できる方法です。それぞれの意思決定や行動原理を数理モデルで表し、全プレイヤーの満足度の和をできるだけ大きくするにはどのようにしたらよいのかを考え、分析します。

しかし、そのような最適解が理論的に導き出せても、実際の行動結果がその通りになるとは限りません。例えば、混雑時のエスカレーターは、片側を歩くよりも、全員がまったく動かずに乗っていた方が一定時間当たりの流通量は多くなります。しかし、自分自身の通過時間のみに関心がある各プレイヤーは、じっとしているよりも歩いた方が早く通り抜けられるように思えて、歩きだしてしまう。結果、最適な状態からは、悪化することになります。

こうしたことから、ゲーム理論では、特有の状況(解の概念)が生まれることがあります。その一つが「ナッシュ均衡」です。ナッシュ均衡とは、プレイヤー全員が「今の状態が最も合理的で、戦略を変えると自分の結果が悪化する」と判断して、誰もが戦略を変更しなくなる(均衡状態になる)状態です。最近の私の研究では、ある種のゲームに対して、ナッシュ均衡が存在することを証明しました。

ゲーム理論は、日常のさまざまな場面で応用性が高い理論です。スポーツはもちろん、ビジネス交渉での駆け引きなど、戦略的思考が必要な場面で有効です。ある状況における最適解を求める意味では、離散最適化の関連分野と言えるので、新たなチャレンジとして取り組んでいます。

最先端の研究に触れたいと、多くの数学者が集う欧 米で2年間研究に励んだ。写真はフランス南東部にあ るグルノーブルにて研究の打ち合わせをした際の一枚

最先端の研究に触れたいと、多くの数学者が集う欧 米で2年間研究に励んだ。写真はフランス南東部にあ るグルノーブルにて研究の打ち合わせをした際の一枚

理工学部経営システム工学科

高澤 兼二郎准教授

1982年東京生まれ。東京大学工学部計数工学科を卒業後、同大学院情報理工学系研究科修士課程、博士課程修了。博士(情報理工学)。京都大学数理解析研究所の助教を経て、2016年より法政大学理工学部経営システム工学科准教授に着任、現在に至る。日本オペレーションズ・リサーチ学会および日本応用数理学会所属。


ページトップへ