AIを活用した組合せ最適化、カギの一つは強化学習
2023.10.24公開 2024.11.13更新
株式会社Laboro.AI リードマーケター 熊谷勇一
執行役員 マーケティング部長 和田 崇
概 要
ビジネス上のタスクを完了させる方法に複数の組合せから選ばなくてはならない場合、その選択は、意思決定者の経験や知識に基づいた「ビジネス勘」に依存することが少なくありません。しかしAIを活用した「組合せ最適化」で、組合せの数が膨大であっても、最適な解を十分に短時間で導き出すことを実現する例が増えています。
Laboro.AIの「最適化領域のカスタムAI開発」はこちら
目 次
・組合せ最適化とは
・組合せ最適化の仕組み
・強化学習の活用
・組み合わせ最適化の精度を上げる方法
・ビジネスにおける組合せ最適化の活用事例
・路線におけるダイヤの復旧
・物流における経路の最適化
・AIを使うかどうかの判断も重要
組合せ最適化とは
組合せ最適化とは、条件を満たす解の中で一番良いものを求める「最適化問題」 の中でも、膨大な数の組合せから、条件を満たす組合せや、最も良い組合せを探索することです。
例えば、公共交通機関のダイヤや物流の配送ルートの策定をする場合、取れる選択肢が増えるとそれらの組み合わせの数は膨大になり、すべてを比較・検討して最適な解を見いだすのは困難になります。さらに、利用者数や道路状況など刻一刻と変わる要素を考慮に入れると、困難さはさらに上がります。
そこでAIを活用した組合せ最適化が注目されており、それによって最適解を見いだせれば、まずは生産性の向上や業務時間の削減といった効率化が狙えます。さらに、その業務が進化することによって、新しい価値を生み出せて、ビジネスモデルそのものが進化するという、イノベーションを起こせる可能性も出てきます。
有名な組合せ最適化に、「巡回セールスマン問題（Travelling Salesman Problem）」があります。巡回セールスマン問題は、「セールスマンがいくつかの都市を一度ずつすべて訪問して出発点に戻ってくるときに、移動距離が最小になる経路」を求める問題のことです。名前の通り、セールス担当者がとし訪問先の都市を巡る経路の探索や配送ルートの策定において役立つのはもちろんですし、例えば「ある都市には何時までに行かなければならない」「都市Aは都市Bの後に訪問しなければならない」といった制約条件を設定し、ある程度複雑な問題に対応することもできます。
そうした複雑な条件はなく、都市数をnとすると、可能な経路の総数はn!/2n通り存在します。nが小さいときには、すべての組合せを調べることができるので最短経路も分かります。しかしnが大きくなると、この組合せの総数は爆発的に増加しすべてを調べることは事実上不可能になります。例えば、例えば、5都市の場合は12通り、7都市で360通りですが、10都市で181,440通り、 30都市で4.42×10の30乗通りになってしまいます。そこから最適解を見つけるための計算は膨大になります。
この問いに対する答えを導くための最もシンプルな方法は、各経路の距離を一つずつ計算し、比較することで移動距離が最小となるものを導くものです。しかし上述の通り、すべての経路の組み合わせを合算すると膨大な数になるため、人間による計算で解くのは現実的ではありません。
そのため、AIが近年注目されています。コンピュータによる計算は人間による計算に比べて速度と正確性の面ではるかに優れていますが、コンピュータを組合せ最適化に使える前提は、制約条件が何であるかを明確にしており、何を計算すれば良いかが分かっていることです。逆に言えば、制約条件が複雑すぎたりその数が多すぎたりすると、そもそも何を計算すれば良いのかが分からず、問題を解けなくなってしまいます。そうした場合に検討に入れたいのが、後述もする強化学習を用いたアプローチです。AIが自律的に試行錯誤し、最適解を探索することによって、より優れた解を目指せます
参考：京都大学大学院情報学研究科 永持研究室「簡単そうで難しい組合せ最適化」
組合せ最適化の仕組み
そもそも組合せ最適化は、数理最適化問題の一種として知られる問題解決手法です。数理最適化問題とは、特定の制約条件を満たした上で値を最小、あるいは最大化できる解を求めるための問いで、AIの問題解決能力の根幹につながるものとしても知られています。
AIで組合せ最適化を扱う際の流れは、データをインプットし、機械学習によってそれを分析し、最適な組合せを導くことです。そのために必要なのがアルゴリズム、つまり正しい解を導くための手順です。アルゴリズムを適切に改善することができれば、従来の何百倍、あるいは何万倍のスピードで、正しい答えを導くことができます。
近年は教師なし学習を用いた、アルゴリズムの自律的な発見と改良が可能なディープラーニングや強化学習の手法が発展を遂げていることにより、組合せ最適化問題に対して高度な解答が行えるようになってきている点も、注目すべきでしょう。
参考：梅⾕俊治「問題解決に役⽴つ組合せ最適化とアルゴリズム」
強化学習の活用
組合せ最適化問題に強化学習を適用することの利点は二つ挙げられます。
１点目は、解きたい最適化問題の場合の数が膨大になっても、強化学習では最適化に要する時間（推論時間）が大きくなりにくいという点です。強化学習では、エージェントが環境の状態に応じて取った行動に対して報酬を与え、そうして変わった環境を基にエージェントがまた行動をして報酬を得る、と繰り返して学習が進みます。
つまり、学習内容を次の推論に生かすことができるため、問題を解くためにかかる時間が場合の数に比例して増えないことが期待でき、それを示す研究も報告されています。
そうした強化学習の強みを、巡回セールスマン問題に適用してみましょう。例えば訪問すべき都市が頻繁に変わり、最適化問題がたびたび発生するような制約があるとします。このような条件下で強化学習を適用することで、最適化問題を一から解いていくのではなく、すでに解答済みの出力データを応用し、新しい巡回経路の開拓にかかる計算時間を大幅に削減できる可能性があります。
２点目は、強化学習を用いるとさまざまな最適化問題に対してほぼ一つの枠組みでアルゴリズムを構築することが可能になる点です。数理最適化アルゴリズムでは問題ごとに職人技による定式化やアルゴリズム開発が必要になるケースが一般的です。一方、強化学習では共通したフレームワークや技法を用いて、必要に応じた問題ごとのチューニングによって対応できます。つまり、過去に対応した最適化問題のアルゴリズムを別の問題にも当てはめ、一から計算する手間を省くことができるわけです。
強化学習を適用するコツとしては、学習を促進する報酬の設計、最適化途中の価値関数の設計、高速なサンプリングのための実装上の工夫といったことが挙げられます。逆に言えば、そうしたコツを踏まえず、強化学習を単に導入するだけでは、期待しているようなパフォーマンスを得られないこともあるため、運用に関するノウハウを何かしらの方法で確保する必要があります。
組合せ最適化の精度を上げる方法
組合せ最適化の精度を高めるための余地は、さまざまなところに残されています。どんなAIを使うのか、どんな計算機を用いるのかなどによって、処理速度の限界は大きく変化します。
例えば2023年に早稲田大学の研究グループは、イジング計算機を使って組合せ最適化問題を効率よく、高い精度で解くことのできる手法を発表しました。イジング計算機は、組合せ最適化問題の解答に特化した計算機として国内外で知られており、一般ユーザーもクラウドを介して利用ができるソリューションです。新しいアルゴリズムを使ってイジング計算機で問題を解くことにより、効率化を実現しています。
出典：早稲田大学「制約をもつ組合せ最適化問題をイジング計算機で効率的かつ高精度に解くための新たな手法を開発」
ビジネスにおける組合せ最適化の活用事例
組合せ最適化による恩恵は、すでにさまざまな領域で現れています
路線におけるダイヤの復旧
2023年に小田急電鉄が実証実験した、ダイヤが乱れた場合の復旧ダイヤの作成には、強化学習が活用されました。駅間の停車時間の最小化、旅客流動の最大化、制限速度の考慮や折り返し運転実施の有無など、多岐にわたる運行条件を数式に置き換えて計算する必要があるため計算量が膨大になってしまうためです。
強化学習はこのような大規模な組合せ最適化問題へ対処することもできます。強化学習済みのAIに現在の路線状況を与えることで、AIは復旧のためのルート最適化計画を提案し、鉄道職員はそれに基づいてダイヤ構築を進めることができました。従来はダイヤ作成の知見が豊富な職員にこの業務が属人化していましたが、強化学習の活用により、属人化の解消と、作業の短縮につながっています。
出典：日本経済新聞「鉄道の復旧ダイヤ、数分で作成 「スジ屋」に迫るAI」
物流における経路の最適化
ITの中でAI・機械学習と同様に注目を集めている技術に量子コンピューティングがあり、機械学習と組み合わせた「量子機械学習」によって学習能力の向上が考えられています。そうした量子コンピューティングを活用した事例も出てきています。
日野自動車の子会社であるNLJは、量子コンピューターを用いた組合せ最適化ソリューションの提供を物流向けに進めています。積載貨物の組み合わせ最適化を40秒で実施し、これまでは2時間かかっていた積載計算の負担を大幅に削減できました。
また、量子コンピューターによって導き出される計算結果も非常に信頼のおけるものです。同ソリューションの導入によって、これまで3台のトラックで輸送していたものを、ダブル連結トラック1台で運ぶことが可能となり、輸送コストの削減に貢献しています。
物流業界は特に人材不足が著しい業界であるため、組合せ最適化の活用による業務自動化
は、新しいトレンドとなって広く受け入れられるようになるでしょう。
出典：ニュースイッチ「トラック積載貨物を最適化、量子計算活用して40秒で組み合わせ導き出すシステムがすごい」
AIを使うかどうかの判断も重要
配送・物流ルートの決定、人員シフトの決定、製造計画の策定など、ビジネス上でもさまざまな組合せ最適化問題が存在し、そのためにAIを導入している例が増えており、組合せ最適化にAIを活用するのは有用だと言える状況ができてきています。
とはいえ、組合せ最適化はあらゆる問題を解決してくれるわけではありません。場合によっては他の手法を用いた方が短時間で解決につながったり、信頼できる答えが得られたりすることもあります。組合せ最適化問題を解くに当たっては、本コラムで取り上げた強化学習や数理最適化の他に、メタヒューリスティクスやルールベースを加えた四つのアプローチが考えられます。どれかが優れているということではなく、解決したい問題の内容や難易度に合わせて使い分けることが重要です。「なんとなくこのアプローチが良さそうだ」と思われている場合でも、さまざまな視点から検討をすると「実は他のアプローチの方が問題解決に最も役立った」となることが少なくありません。重要なのは、AIのプロフェッショナルとの協業により、ビジネス課題に合わせた最適なソリューション選びとそれを実行できる体制を準備しておき、単なる課題解決にとどまらず、あくまでビジネス成果を追求していくことです。
Laboro.AIでは、これまで数多くの最適化プロジェクトに取り組んできました。その知見を活かし、強化学習や数理最適化など、問題の性質や条件に合わせて様々なアプローチを検討しながらオーダーメイドで開発を行い、 ビジネス成果に向かって伴走します。
Laboro.AIの「最適化領域のカスタムAI開発」はこちら
執筆者
マーケティング部 リードマーケター 熊谷勇一
中央大学文学部卒業、北陸先端科学技術大学院大学情報科学研究科博士前期課程修了。日本経済新聞社など日経ブランド企業で16年以上、雑誌、書籍、ウェブサイト、動画などの編集・執筆を手掛けた後、2022年からLaboro.AIに参画。
執行役員 マーケティング部長 和田 崇
立教大学大学院経営学修士（マーケティング論・消費者行動論）。立教大学大学院ビジネスデザイン研究科博士後期課程中退。KDDI株式会社に入社、コンシューマ向け商品・サービスのクロスメディアによるプロモーション施策の立案・企画運営に携わったのち、全国漁業協同組合連合会を経て、2019年にLaboro.AIに参画。マーケティング／ブランディング業務に従事する傍ら、NewsPicksプロピッカーとして活動するほか、日経クロストレンドなどメディア寄稿多数。
