数理最適化とは?最適化による効果や導入プロセスを紹介

  • HOME
  • 数理最適化とは?最適化による効果や導入プロセスを紹介

数理最適化とは?最適化による効果や導入プロセスを紹介

2019年12月25日 13:04

「AI」という言葉が当たり前に使われるようになってきた昨今ですが、AIと聞いてどのような問題解決の手法を連想されるでしょうか? 恐らく、多くの方はディープラーニングや深層強化学習などをイメージすると思います。 ただディープラーニングや深層強化学習がすべての課題に対し最適なソリューションかと言われると現実はそうではなく、学習しづらいことを無理やりデータから学習させようとすると、非現実的なデータ量が必要になったり、かといって限られたデータから学習させようとしても、いつまでたっても高精度なアウトプットは得られません。 そのようなケースにおいて、特に人の意思決定を肩代わりするようなアウトプットを得たい場合に非常に強力なソリューションになるのが「数理最適化」という手法です。 今回は、AIに興味があるなら知っておかないと損する数理最適化について、概要や導入の利点についてご紹介していきます。

数理最適化とは?

数理最適化とは、“データ”と“因果関係や規則(ルール)”がわかっていながら、 解決策が導き出せない現実の問題に対し、最適解を導き出す問題解決の手法です。 最適化ソリューションは意思決定支援の場で幅広く導入されています。 意思決定に求められることは分野や状況によって様々ですが、 その導入効果を大別すると、

  • 利益が増えた
  • 直接的にコストを削減できた
  • 間接的にコストを削減できた
  • 今まで出せなかった答えを導くことができた
  • 答えが出るまでの労力と時間を短縮できた


のように分けられます。

最適化のイメージ

ここではより具体的なイメージを持っていただくために数理最適化の世界の中では 有名な "ナップサック問題" を例として紹介します。

ナップサック問題の概要

容量(重量)制限のある袋にものを詰め込みます。 袋は無限にものを入れることが出来ませんので、どれを入れるかが重要になります。 最終的に入れることができたものの価値が高ければ嬉しいということです。しばしば 泥棒の意思決定に例えられる有名な問題です。 ナップサックに物を詰める泥棒

問題の整理

ここでは袋の重量制限を 10 kg としてものの価値と重さは以下のように考えます。 参考に単位重量あたりの価値(価値/重量)も出してみました。

  A B C D E
重量 1.8 5.8 7.3 4.1 8
価値 7 50 70 40 80
価値/重量 3.89 8.62 9.59 9.76 10.00


この問題を最適化問題として定式する必要があります。

答えを求める

この問題を最適化問題として解くと最適解は「 B と D を詰め込む(合計 90 )」と なります。ちなみに単位重量あたりの価値が大きいものから順に詰めていくという方法 (貪欲法)で行うと答えは「 A と E を詰め込む(合計 87)」と最適解になりません。

現実の問題はこの例のように簡単ではなく、評価(例では価値)やルール (例では重量制限のみ)が複数あったり、Aを取ったらDを取ってはならない、など詰め合せの組みあわせに関するルールが定められていたり複雑な要件が存在します。

最適化導入による効果

ここでは、実際の導入効果の例を具体的にご紹介いたします。 最適化導入による問題解決事例を随時更新しておりますので、興味のある方はこちらも併せてご覧ください。

利益が増えた

マーケティングの例

これまで統計解析やデータマイニングによってメディア・顧客間の感度分析はある程度できていたものの、具体的にどのタイミングにどのようなアクションをするかは、シミュレーションやときには属人的な勘によって実施しているというケースも少なくありません。 最適化を導入することによって、よりよい戦略を導くことができます。

ターゲティング

直接的にコストを削減できた

工場(製造業)の例

工場の生産計画は需要予測のブレや段取り替え時間、機械のトラブルといった様々な要因を考慮する必要があり、安全在庫や生産の決定は職人芸的な難しさがあり、多品種少量生産によってその複雑さは増すばかりです。最適化を導入することによって、多少のブレを許容できるロバストな生産計画を導くことが出来るため、 営業倉庫の費用等をカットすることができます。

物流(物流を伴う企業、メーカー、製造業等)の例

価格競争の波の中で、あらゆるところにメスを入れる必要も出てきます。 輸送費用はこれまで線形計画問題を用いて最適化シミュレーションを行って来たのでこれ以上コストカットは難しいというケースでも、倉庫の容量や輸送手段の選択肢、さらにはデポ設備を増やすことを新たに変数として加えることによって、更なるコストカットを実現することができます。

物流・ロジスティクス

間接的にコストを削減できた

シフトスケジューリングの例

24 時間体制で稼動し続ける工場の多くは、社員のシフトは月毎に決定しています。 シフト作成にあたっては、人員により担当できる機械やスキルに差があったり、各人の休暇希望日を考慮したりと、毎回作成に多大な時間を費やしていないでしょうか。最適化ソリューションを導入することで、作業習熟度などこれまでパラメータ化しずらかった要素を考慮した勤務表を作成することが出来るようになり、担当者の負荷は大きく軽減されます。

スケジューリング

今まで出せなかった答えを導くことができた

プラント運転計画の例

CO2 の削減及び環境コストの低減が各企業に求められる昨今において、コストと環境負荷を共に満足するような答えを捻出する必要性が高まっています。最適なプラントの運転計画について答えを導く際に、最適化ソリューションを活用することができます。

工場(化学プラント)の例

全ての機械の自動運転化に成功しても、取り扱う製品の数・需要の増加によってこれまでの運転計画作成ロジックでは上手く計画を作成できない恐れが出てきます。化学反応を伴うプロセス部分では非線形性が強く出てしまうのもその要因の一つです。非線形最適化問題も得意とする最適化ツールを導入することによって、材料の品質による歩留まりの変動を折り込んだ生産計画を立案することができます。

計画検討

最適化導入(最適化を用いたシステム開発)のプロセス

STEP1 問題の整理

まず現実の問題を整理します。 特に次の3つの点を整理することが重要です。

    (1) 何を意思決定するのか

    (2) 実務的なルール・制約は何か

    (3) 何を「最大化」or「最小化」or 「平準化」するか

STEP2 最適化モデルの構築<プロトタイピング>

STEP1で整理した問題を "数式" で表現、つまり最適化モデルを構築します。 最適化モデルにおいて、STEP1の (1) は "変数" 、(2) は "制約条件" 、(3) は "目的関数" に該当します。

STEP3 最適化モデルの検証

ツールなどを用いて得られた最適化モデルの最適解を検証します。 「数学的に最適解=現実の意思決定」とは限らないので、場合によっては STEP1に戻り、制約条件の再検討を行います。STEP1~STEP3を納得のいくまで、 何度も繰り返すことが重要です。

STEP4 システム化

プロトタイプの最適解に納得したらシステム化作業に移ります。作成した最適化モデルをexe や DLL 等の形式にできると、 他のシステムに組み込んだり、GUI 部分と並行して開発を進めることが可能です。

おわりに

AI活用が盛んな昨今、機械学習Deep Learning の技術が脚光を浴びていますが、数理計画・最適化も幅広く利用されているコア技術の一つです。ご興味がある方は当社最適化ソフトNumerical Optimizerについて活用事例などをご紹介しているページをご覧ください。ツールの無料体験やツールを用いた分析についてご相談いただけるセミナーを全国各地にて開催しておりますので、ぜひお気軽にお申し込みください。

NTTデータ数理システムでは、お客様のご要望に合わせた受託開発を承っております。「データはあるから何となく何かをやりたい…」というきっかけでも問題ございません。お客様が解きたい課題を弊社技術スタッフが一緒に課題整理を行いながら、ご要望に合わせたご利用形態でご提供いたします。 ぜひお気軽にお問い合わせ、ご相談いただけると幸いです。