「数理最適化」とは――4つの応用事例、実問題適用への手順、機械学習との違い、使い分け方:リクルート事例で分かる数理最適化入門(1)
リクルートにおける数理最適化の応用事例の紹介を通じて、数理最適化とは何か、どのようにビジネスに応用できるのかを紹介する連載。初回は、数理最適化の概要、リクルートにおける4つの応用事例、実問題適用への手順、機械学習との違い、使い分け方などについて。
近年多くの企業で、ビジネスでのデータ活用が当たり前になっています。中でも機械学習を用いた成功事例については、耳にしている読者の方も多いと思います。一方で、同じくデータ活用の技術である「数理最適化」は、さまざまな領域で成果を上げているにもかかわらず、その実態について知っている人はあまり多くないようです。
本連載ではリクルートにおける数理最適化の応用事例の紹介を通じて、数理最適化とは何か、どのようにビジネスに応用できるのかを紹介します。読者の皆さんがデータ活用の手法の一つとして数理最適化を利用できるようになるきっかけになれば幸いです。
数理最適化とは
数理最適化とは「現実の問題を数式(数理モデル)として定義し、制約条件を満たしつつ、コストの最小化や利益が最大化されるような変数の値を求める手法」のことです。ここでいう、「最小化or最大化したい対象であるコストや利益などの数値を数式で表したもの」を、数理最適化では「目的関数」といいます。
数理最適化を現実の問題に適用するには、まず最適化したい現実の問題に関して「目的関数」と「制約条件」を数理モデルとして定式化します。その後、その数理モデルを解くのに適した最適化アルゴリズムを選択し、目的関数を最大化or最小化する変数の値を算出します。
数理最適化では、一度定式化すれば、新たなデータが与えられるたびにアルゴリズムによって最適な変数の値を自動で算出できます。そのため、人間が毎回データを見てからしていた意思決定を自動化、支援する手法として、ビジネスや社会で幅広く利用されています。
リクルートでの数理最適化応用事例4選
数理最適化のビジネスへの応用について具体的なイメージを持てるように、ここからはリクルートで数理最適化を利用した事例の一部を紹介します。なお事例の詳細は後の連載でまた紹介するので、本稿では概要までとします。
ユーザーへのレコメンドメールの最適化
リクルートでは、各サービスのユーザーに対してお薦めの商品やイベントをお知らせするメールコンテンツを配信しています。
コンテンツに関しては、各ユーザーの最も関心の高いメールを配信したい一方で、各サービスが持つ「最大配信可能メール数」「一定期間優先して配信したいコンテンツ」といった事業制約を守る必要があります。そのため、単純にユーザーごとに最も関心が高そうなコンテンツをメールで配信する手法を採ることができません。そこで、事業制約を満たした上で最適なメールの配信内容を算出するのに数理最適化が利用されました。
- やりたいことの例:さまざまな事業制約(最大配信数、優先配信期間など)を満たしつつ、ユーザーに最適なメールを配信する
- 変数の例:各ユーザーへの配信メールの種類、配信時間
- 目的関数の例:ユーザーのメール開封率の最大化、コンテンツへの送客数最大化
- 制約条件の例:特定のコンテンツの最大メール配信数、一定期間集中配信したい優先コンテンツ
フリーペーパーの配車スケジュール最適化
リクルートではフリーペーパーを配るラックを各地域に配置しています。複数のトラックで多くのラックを巡る必要があるので、効率的に巡回するルートを決めることが重要な問題です。従来は人手によってトラックの配車スケジュールを決めていましたが、この問題を解くためのヒューリスティックソルバーを開発しています。
- やりたいこと:ラックへの最適なトラックの割り当てと配送経路を決定する
- 変数の例:トラックのラック割り当て、配送経路
- 目的関数の例:トラックの燃料、合計配送距離、合計配送時間
- 制約条件:訪問可能時間、トラックごとの稼働可能時間、トラックの荷物重量制限など
キッチンの最適調理順レコメンド
関連記事
- 無償で利用できる「数理、データサイエンス、AI」の教材を公開 東京大学
東京大学の数理・情報教育研究センターは「数理・データサイエンス・AIモデルカリキュラム」に準拠した教材の無償公開を開始した。クリエイティブ・コモンズ・ライセンス(CC BY-NC-SA)で利用できる。 - NVIDIAのGPU4基で「1秒間に1兆の解を探索」 広島大学の研究グループが高速探索手法を開発
広島大学大学院の教授である中野浩嗣氏らの研究チームは、組み合わせ最適化問題の解を高速に探索する新しい計算方式「アダプティブ・バルク・サーチ」を開発した。著名な組み合わせ最適化問題である「最大カット問題」「巡回セールスマン問題」「ランダム問題」について、いずれも1秒以内で最適解が得られたという。 - 東芝が組み合わせ最適化問題の新アルゴリズムを開発、世界最速をうたう
東芝は、FPGAやGPUなどを用いた従来型コンピュータだけで、量子コンピュータよりも10倍速く「組み合わせ最適化問題」の解を得られるアルゴリズムを開発した。従来型コンピュータを使って、低コストで大規模な問題にも対応できる。
Copyright © ITmedia, Inc. All Rights Reserved.