組合せ最適化【ビジネス成長のためのAI用語】

2023.10.24
株式会社Laboro.AI　リードマーケター　熊谷勇一

用語解説

組合せ最適化とは、条件を満たす解の中で一番良いものを求める「最適化問題」 の中でも、膨大な数の組合せから、条件を満たす組合せや、最も良い組合せを探索することです。

有名な組合せ最適化に、巡回セールスマン問題があります。巡回セールスマン問題は、「セールスマンがいくつかの都市を一度ずつすべて訪問して出発点に戻ってくるときに、移動距離が最小になる経路」を求める問題のことです。

都市数をnとすると、可能な経路の総数はn!/2n通り存在します。nが小さいときには、すべての組合せを調べることができるので最短経路も分かります。しかしnが大きくなると、この組合せの総数は爆発的に増加しすべてを調べることは事実上不可能になります。例えば、例えば、5都市の場合は12通り、7都市で360通りですが、10都市で181,440通り、 30都市で4.42×10の30乗通りになってしまいます。そこから最適解を見つけるための計算は膨大になります。

応用&詳細解説

そこで、計算量が膨大になってしまう問題を解決するアプローチの一つとして、 組合せ最適化問題にもAI技術を活用する方法も生まれています。具体的には、強化学習とディープラーニングを組み合わせた深層強化学習を用いて問題を解く方法であり、応用例も出てきています。

例えば、2023年に小田急電鉄が実証実験した、ダイヤが乱れた場合の復旧ダイヤの作成には、強化学習が活用されました。駅間の停車時間の最小化、旅客流動の最大化、制限速度の考慮や折り返し運転実施の有無など、多岐にわたる運行条件を数式に置き換えて計算する必要があるため計算量が膨大になってしまうためです。

最適化問題に強化学習を適用することの利点としては２点挙げられます。１点目は、解きたい最適化問題の場合の数が膨大になっても、強化学習では最適化に要する時間（推論時間）が大きくなりにくいという点です。強化学習では、エージェントが環境の状態に応じて取った行動に対して報酬を与え、そうして変わった環境を基にエージェントがまた行動をして報酬を得る、と繰り返して学習が進みます。つまり、学習内容を次の推論に生かすことができるため、問題を解くためにかかる時間が場合の数に比例して増えるわけではないことが期待でき、それを示す研究も報告されています。その結果、巡回セールスマン問題で言えば、訪問しなければならない都市が頻繁に変わり、その度に最適化が必要になるような状況においては、強化学習を適用する意味が出てくると考えられます。

２点目は、強化学習を用いるとさまざまな最適化問題に対してほぼ一つの枠組みでアルゴリズムを構築することが可能になる点です。数理最適化アルゴリズムでは問題ごとに職人技による定式化やアルゴリズム開発が必要になることが多い一方、強化学習では共通したフレームワークや技法を使った上で、必要に応じて問題ごとにチューニングすることで対応できます。強化学習を適用するコツとしては、学習を促進する報酬の設計、最適化途中の価値関数の設計、高速なサンプリングのための実装上の工夫といった事が挙げられます。

ビジネス成長に向けたポイント

配送・物流ルートの決定、人員シフトの決定、製造計画の策定など、ビジネス上でも様々な組合せ最適化問題が存在しています。組合せ最適化問題を解くに当たっては、上記の強化学習と数理最適化の他にもルールベースを加えた三つのアプローチが考えられます。どれかが優れているということではなく、解決したい問題の内容や難易度に合わせて使い分けることが重要です。「なんとなくこのアプローチが良さそうだ」と思われている場合でも、さまざまな視点から検討をすると「実は他のアプローチの方が 問題解決に最も役立った」となることが少なくありません。

Laboro.AIでは、これまで強化学習を使った最適化問題プロジェクトにも取り組んできており、それを基にした「組合せ最適化ソリューション」を開発しました。本ソリューションの提供に当たっては、問題の性質や条件に合わせ、強化学習に加えて適宜、数理最適化などのアプローチ も検討しながらオーダーメイドで開発を行い、 ビジネス成果に向かって伴走します。

参考
Laboro.AI「強化学習 x 最適化　組合せ最適化ソリューション」
京都大学大学院情報学研究科 永持研究室「簡単そうで難しい組合せ最適化」
日本経済新聞「鉄道の復旧ダイヤ、数分で作成　「スジ屋」に迫るAI」