Laboro.AI

強化学習 x 最適化

組合せ最適化
ソリューション

機械自らが試行錯誤を通して、
膨大な組合わせの中から最適なものを選択

  • 強化学習
  • スケジューリング
  • 工程最適化
  • 経路最適化

ソリューションについて

ソリューションの概要

『組合せ最適化ソリューション』は、大量の組合せの中から最も良いものを選択するという「組合せ最適化問題」を、強化学習技術を使って解決することを目指したソリューションです。

組合せ最適化問題の具体例としては、調理工程スケジューリング、配達経路最適化、アルバイトのシフト計画、船舶の積荷配置計画、製造組立ラインでの工程スケジュールといったものがありますが、これらの組合せ最適化問題に強化学習を用いるメリットとして、一般的な最適化手法と比べて学習データを活用するため最適化に要する時間を短縮できること、問題依存のチューニングの手間を低減できることの2点が挙げられます。これらのメリットについて、その背景と共に以下で説明します。

組合せ最適化問題とは

組合せ最適化問題とは、条件を満たす組合せの中からある値を最もよくするものを選択する問題です。ここでは、調理工程スケジューリング問題と配達経路選択問題を具体例に挙げて説明します。

調理工程スケジューリング問題

スケジューリング問題の例の一つに、調理工程の最適化があります。例えば、調理者1名が全部で4つの料理を作る場合には、各料理に“野菜を切る” “コンロで煮る”といった決められた調理手順があり、さらに調理器具としてコンロ、オーブン、包丁、まな板、炊飯器を1つずつ使用できることなどが想定されます。調理工程の最適化問題は、そうした制約条件のもとで、調理終了までの時間を最も短くする調理工程を選択する問題です。

制約条件を考慮すると、最適な調理工程は下図のようになります。この程度の大きさの問題なら簡単に解くことができる一方で、さらに多くの料理を多人数で作る場合などには、組合せの数が増え、より問題の難易度が上がっていくことになります。

配達経路最適化問題

配達経路選択問題の例の一つに、複数トラックでの配送ルートを決定する配達経路最適化問題が挙げられます。その問題設定は、配送対象の住宅に対して複数トラックで配送するという内容になり、制約条件としては、荷物のお届け日時の指定があるほか、トラックに一度に詰め込める荷物に制限があるといったことが考えられます。配達経路最適化問題は、そうした制約条件を満たして、配達時間を最小化する配達順序を決定する問題であり、配達対象の住宅の数が増え、トラックの台数も増えるなど、問題がより大きくなる場合には、最適化することが難しくなっていきます。

上で例とした調理工程スケジューリングや配達経路最適化の他にも、アルバイトのシフト計画、船舶の積荷配置計画、製造組立ラインでの工程スケジュールといった問題も考えられますが、これらは、これまで「数理最適化」と呼ばれる技術を使って解かれることが一般的でした。数理最適化による解法では、問題に応じて職人技とも呼べる定式化やアルゴリズム開発が必要になることが多く、開発に時間がかかる傾向がありました。また、せっかく開発したアルゴリズムが、問題のほんの少しの変更で使えなくなってしまうケースもあり、問題設定の変化に対するロバスト性に課題がある場合があります。

強化学習とは

強化学習とは、エージェントと呼ばれる主体が、試行錯誤を通して最適な行動を実現する機械学習手法の一つです。エージェントは、一連の行動を通して得られる報酬を最大化するように学習することで、自らの行動を最適化していきます。

強化学習のイメージを掴むため、ロボットの歩行制御を例として、ロボットができるだけ遠くまで歩けるよう制御を実現したいケースを考えた場合、強化学習の枠組みでは、ロボットがより遠くに歩けるほどより多くの報酬を与えます。機械が試行錯誤を通してより大きな報酬を得られるよう行動を学習していくため、学習するにつれてロボットはより遠くまで行ける良い歩き方を身につけていきます。良い歩き方を学習しさえすれば、似たような状況においては短い推論時間で歩行制御を行えるようになります。

仮にロボットの歩行制御を教師あり学習で行うとすると、ロボットの右足や左足をどう動かすのかといった行動一つ一つに良い/悪いといったラベルをつける必要がありますが、一方、強化学習では、歩いた距離という一連の行動を通して得られる報酬を設定すれば、あとは機械が自動で制御機能を獲得していくことが可能となります。

強化学習×最適化問題のメリット

近年のディープラーニングの発展に伴い、最適化問題を深層強化学習を用いて解くことが行われるようになってきており、応用例も出てくるようになりました。直近の例だと、米グーグルが強化学習を用いて半導体設計を行なったという事例があります。半導体の設計は、大量の論理回路を配置するパターンの中から、消費電力やチップの大きさといった条件を満たす配置パターンを選択するという組合わせ問題になります。今までは人間が数ヶ月かけて半導体回路の配置を設計していたのですが、グーグルは強化学習を用いることで最適な配置をわずか6時間以内に生成できる手法を編み出しました。この事例のように、強化学習を用いた最適化は今後発展が期待される領域の一つです。

最適化問題に強化学習を適用することのメリットとしては2点挙げられます。1点目は、最適化問題が大きくなっても、強化学習では最適化に要する時間(推論時間)が大きくなりにくいという点です。強化学習では、学習データを元にして様々なパターンを機械が自動で学び、その学んだことを生かすことができるため、推論時に問題を解くためにかかる時間がそこまで長くならないことが期待でき、それを示す研究も報告されています。その結果、頻繁に状況が変わり、その度に最適化が必要になるような状況においては強化学習を適用する意味が出てくると考えられます。

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

ソリューションご提供にあたって

本ソリューションは汎用的にご利用いただけるAIプロダクトとして販売するものではなく、貴社のビジネス課題をヒアリングの上、オーダーメイドで開発いたします。

Laboro.AIでは、強化学習を使った取り組みに積極的に取り組んでおり、工程スケジュール最適化などの領域で実績を積んでいます。本ソリューションの提供においては、問題の性質や条件に合わせ、強化学習に加えて適宜、数理最適化の技術も応用しながら高いビジネス成果へとつなげていくことを目指します。

(※ なお、組み合わせ最適化問題を強化学習で解く前提として、シミュレータ環境の設計が必須になる場合があります。シミュレータ環境の実装方法、最適な技術選択、問題に応じた技法のチューニングについては、 詳細をお伺いした後、弊社からご提案させていただきます。)

活用シーン

配達経路最適化

スケジュール最適化

ソリューションのポイント

最先端のアルゴリズム

最先端の画像分野の研究をキャッチアップし、最適なアルゴリズムを応用

導入時のフルサポート

導入時のコンサルティングの提供により、データやラベル、精度検証の方向性など、専門的知見でサポート

多様な導入オプション

オンプレ導入、API提供など、ご要望に合わせて柔軟な提供オプションをご用意

一覧に戻る