システムによる最適化を通じて、開発者がめざすもの 〜エレベーターの制御システムを例に〜

システム開発における「目的」のヒアリングの重要性

「現行の受発注管理システムが扱いづらく事務コストが過大化している」「業務フロー改革のため、新たな業務システムをフランチャイズ各店舗に導入したい」「特定スキルを持った人材のレジュメを、最適な方法で管理したい」…

システム開発は言うまでもなくお客様ありきのビジネスですが、システム投資を決断されるお客様の「目的」は様々です。ご依頼いただく段階で、要件や目的についてどの程度明文化されているかはお客様によりまちまちですが、

  • お客様が本当に求めているものは何か?

について「深く」掘り下げることは、システム開発者の役目であり、顧客を唸らせるようなシステムを開発するためには不可欠な工程です。

  • 要件定義では、お客様がやりたいと思っていることをマスター開発者が引き出す
    • 「システムでは出来ない」とお客様が思い込んでいることも含めて聞き出す。システムでできる領域についての線引きは、技術に通じたマスター開発者が行うのが良い
    • 最初は必要最小限の機能のみ実装し、後から機能拡張するスモールスタートの提案をすることも多い
  • 概要設計〜詳細設計では、具体的にどんな手段(パッケージ、アルゴリズム、etc.)を用いて目的を達成するか計画し、実装する

さて、上記のようにお客様の要望に応えようとするとき、いろいろなところで発想するのが「システムによる最適化」を含む開発アイデアです。 実際にそのアイデアを含む形で開発が出来るかどうかは、納品スケジュールやお客様の予算感にも依るのですが、まずは例を用いて「システムによる最適化とは何か?」説明してみたいと思います。

詳しくは後述しますが、近年HOTな機械学習においても、「最適化」の概念は必ず登場しますので、スキルアップをめざすエンジニアにとっては特に読む価値があるはずです。

以下はこの記事のアジェンダです。

  • 最適化を成り立たせる「目的関数」と「制約式」という思考法(パラダイム)を、エンジニア・非エンジニア問わず、理解できるよう紹介
  • システム開発においてお客様が求めるものを、「目的関数」に反映することができることを示す

システムによる最適化とは何か?

「一番良いのを頼む!」…とは少し前に流行した某ゲームの台詞ですが、最適化とはつまり「制約を満たす中で『一番良い解』を見つける」ことだと理解すれば概ね正しいようです。

解くべき問題を、変数と数式を組み合わせて記述したものを「最適化問題」と呼びますが、最適化問題とみなせるものの具体例には下記のようなものがあります。

  • 材料を組み合わせて製品を作る工場において、今期の利益を最大化する生産計画を立てたい(cf. 線形計画問題)
  • スタッフのタスクに対する向き・不向きを考慮しながら、チーム全体として作業コストが最小化するようにタスクを割り当てたい(cf.マッチング問題)
  • 職場の人員要件を満たす中で、もっともスタッフの負担が均等化するようなスケジュールを立てたい(cf. ナース・スケジューリング問題)

「システムによる最適化」というときには、例えばお客様の抱える問題を上記のような最適化問題によってモデリングすることを指すことがあります。その場合、開発の流れは下記のようになると考えられます。

  • 解きたい問題を変数と数式で表現し、「最適化問題」として定式化する
  • その問題を解くアルゴリズムをシステムに組み込む
    • 易しいものならフルスクラッチで実装しても良いし、既存のパッケージやソフトウェアを用いても良い
  • 想定される入力に対し、解がじゅうぶん高速に出力されるかどうかテスト
  • 得られた解(変数の値の組み合わせで表現されている)をわかりやすく出力するインタフェースを用意

一般論だけでは少々分かりにくいので、ここから先はごくシンプルな例として「エレベーターの制御システム開発」を取り、解説をしてみたいと思います。

エレベーターの制御システム – 待ち時間を最小化する最適解は?

例えば弊社がエレベーターの制御システムの開発を請け負ったとして、お客様から「利用者がボタンを押した時、エレベーターに乗るまでの待ち時間が少なくて済むような制御システムを実装してほしい。」とリクエストを受けたとします。 本記事では単純化のため、ある利用者がエレベーターに乗ってから次の利用者が乗るまでには十分な時間的猶予があるものとします。すると上記のリクエストは、「利用者のいないエレベーターはどの階に待機すべきか?」という問題を解決すれば良いことになります。 なるべく「次に乗る利用者」に近い階に待機するほど、待ち時間は短くなりますが、次に乗る利用者がどの階に現れるかはわかりません。どのようにして、「エレベーターの待機階」を決定すれば良いでしょうか?

ここでは問題を解きやすくするためにもう一つ仮定を置き、利用者の待ち時間は、「エレベーターの待機階」と「ボタンを押した階」の差に比例するものとします。 例えば「エレベーターが1階に待機していた場合、3階でボタンを押した利用者と、5階でボタンを押した利用者とでは、待ち時間は2倍異なる」ということですね。 また、エレベーターが1階先まで移動する時間を「1モーメント」という単位で呼ぶこととし、議論を続けます(1『秒』では短すぎるので…)。

最適化問題を構築するための発想 - 「待ち時間平均を最小化する」

ところで、「利用者がボタンを押した時、エレベーターに乗るまでの待ち時間が少なくて済むような制御システムを実装してほしい。」というお客様からのリクエストには、若干の曖昧さがあることがお分かりでしょうか。 エレベーターの利用者はいろいろな階からやって来るわけですから、「すべての利用者にとって待ち時間が短い」ということはありえません。5階建てのビルであれば、エレベーターを5階に待機させた時、5階の利用者は得をし、1階の利用者は損をすることになるでしょう。 ですのでここは、最適化の方針として「待ち時間平均を最小化する」ことを目的とすることにしましょう。「平均」を考えたいので、各階の利用者がそれぞれ何人くらいいるのかを、データとしてインプットする必要があります。そのようなデータ例として、下図のようなものが考えられます。

上図は、ある一定期間(ex. 1週間)における、テスト運用によって収集された利用者数のデータをイメージしています。期間内に各階から乗り込んだ利用者数を計測した情報を、データベースから取得できるものとして、以下の議論を続けます。

さて、「待ち時間平均を最小化する」という「目的」は、顧客が述べた「目的」をシステム開発者が解釈して、開発の俎上に乗せられるよう厳密化したものです。厳密に定義された目的は、しばしば数式で表すことが可能です。その数式は最適化の文脈で、「目的関数」と呼ばれるものです。 上図のデータを仮定する時の目的関数は、下図のうち「Minimize」の横に記載されている数式のようになります。

ここで||によって括られる部分は絶対値を取る処理であり、$x$は待機階を表す変数であることに注意してください(待機階は$x$階とする)。 待機階が3階の時は、$x=3$です。その時目的関数の第1項において、$84$という値(1階の利用者数)には$|x - 1| = 2$が掛かることになります。これは「$84$人が$2$モーメント待たされる」ことを意味し、1階の利用者全体でいうと$168$モーメントの損失が発生することを表しています。

実際に損失の値を計算した結果を下図に図示しました。考えうる解の一つとして「常に1階を待機階とする」場合の利用者の損失(待ち時間の総和)を求めたものです。

このことから、Minimizeの横に記されている目的関数全体を計算すれば、「エレベーターが$x$階に待機する場合の、利用者全体の損失の総和」が求まることがお分かりでしょう(上記の例では、$92 + 117 + 70 + 19 + 0 = 298$モーメントの損失)。

一方、subject to (〜に従う)の横に記された数式は、「$x$は$1, 2, 3, 4, 5$いずれかの値を取る」ことを意味するものです。すなわち、

  1. 5階建てのビルに関する問題なので、6階以上の階や、0階やマイナス1階に待機することはできない
  2. 待機階はいずれかの階とし、2.1523…階などの整数でない値を取ることはできない

ことを表します。2つ目の制約は最適化の分野で整数制約と呼ばれるものです。

今回は問題設定がシンプルかつ、問題の入力が小さいので、

  • 各階をエレベーターの待機階とした場合の損失の総和を求める
  • 最もその値が小さい階を採用することで最適な待機階を求める

ことで「システムによる待機階の最適化」が実現します(全列挙)。 論より証拠ですので、実際にそのようなコードをPythonで書いてみました。

このソースコードを実行すると、デモとして、上図の通りの利用者の分布(84, 19, 35, 39, 23)がデータとして入力された場合の処理を行い、その出力(最適な待機階)を返してくれます。

出力は、下記のスクリーンショットのようになります。

題材は5階建てのビルなのですが、待ち時間の平均を最小化するにはエレベーターが2階に待機するのがよい、という出力がもたらされました。中央に位置する3階ではないのは、1階の利用者が多いことを加味しての結果です。 また、最適解が「最も利用者数の少ない階」であることもある、という結果は少々意外性がありますよね。

さて、このようなコードをシステム内に組み込めば、「エレベーターが各階を待機階とする場合の損失の合計値を求め、それを最小とする解を待機階として用いる」ような「システムによるエレベーター制御の最適化」が実現することがお分かりかと思います。 ですが、望ましい「最適化」の方針はただ一つとは限りません。

ミニマックス戦略 – 上記とは異なる「最適化」の方針

ここまでは「待ち時間平均を最小化すればよい」という前提に則って議論を進めてきました。しかし、先述した顧客の「待ち時間最小化」のリクエストには、もう一つ別の解釈の仕方があります。

「利用者がボタンを押した時、エレベーターに乗るまでの待ち時間が少なくて済むような制御システムを実装してほしい。」

このリクエストは、「エレベーターの待ち時間でもっとも損をする利用者について、待ち時間を短くしてほしい。」と解釈することも出来ます。

上図のように、1階にエレベーターが待機していた場合、5階の利用者は$5 – 1 = 4$モーメントの待ち時間を我慢せねばなりません。勿論、最大多数である「1階にいる利用者」は待ち時間が$0$モーメントですので、その観点から言うと優れています。しかし、もしもお客様が「負担の均等化」を重視するのであれば、5階の利用者が負担を強いられるのは望ましい状態とは言えないでしょう。

また、この目的に関する最適な待機階は、利用者の分布にかかわらず常に「3階」となることはお分かりでしょう(まったく使われない階が存在しない限り…)。

「負担の均等化」はエレベーターの制御システムだとピンとこないかもしれませんが、これがもし「従業員のスケジューリング」に用いるシステムなら実感頂けるでしょう。5人のチームのうち1人が5時間残業するより、それぞれ1時間ずつ均等に残業するスケジューリングの方がまだ望ましいと、誰もが考えるはずです。

これもまた「システムによる最適化」の一例です。いずれも「最適化」には違いありませんが、お客様の求めるものによって、その目的(目的関数)が異なるという一例です。

なお、このような「『もっとも悪い状況』がもっともマシになるような選択肢」を選ぶ求解手法を、一般にミニマックス法と呼びます。

ミニマックス法の最も有名な応用例はアブストラクトゲーム、すなわち囲碁・将棋・チェスといったゲームのAIです。 例えば将棋や囲碁のAIを実装する時は、「相手がもっとも自分に不利な(損害を与える)手を打ってくると想定した上で、自らの損失(負ける確率)を最小化する」という思想をベースにすることが多いといいます。これは上述したミニマックス法の考え方に他なりません。

ミニマックス法の名前の由来は?

先ほどのエレベーターの制御システム最適化における「最大待ち時間の最小化」もやはり、目的関数を使って表すことが出来ます。その関数形を見れば、ミニマックス法の名前の由来がわかるでしょう。

とりあえず、おまじないのように「こんな数式になります」というものを書いてみました。目的関数のところが「min max」となっていて、これを和製英語で読み直すと「ミニマックス」となります。これがミニマックス法の名前の由来です。

ミニマックス法の目的関数に関する、少し踏み込んだ説明

※ この節は読まなくても、理解上差し支えありません。

先ほどの式における$x$は先ほどと同様に「エレベーターの待機階」を表し、新たな文字$a$は「利用者が乗ってくる階」を表します。よって$a$は$1, 2, 3, 4, 5$のいずれかですが、数式では集合の記号を使って$a \in {1, 2, 3, 4, 5}$と書きます。

この数式において「目的関数」に当たるのは上図の長方形で囲まれた部分です。 まずmaxと書かれているのがmax関数と呼ばれるもので、「maxの下にある文字(ここでは$a$)について、後ろの数式(ここでは$x-a$)を最大化するような値をとり、その時の値を返す」というものです。 上記の目的関数の説明は、プログラミングに親しい方なら、下記のコードの方がわかりやすいかもしれません。

例えば$x = 4$のときは、$a = 1$である場合に$|x-a|$は最大です。これを日本語に直すと、「エレベーターが4階に待機しているときは、(1〜5階のうち)1階から利用者が乗ってくる場合に、待ち時間は最大となる」ことを表しています。よって、$x = 4$のとき、目的関数はそのときの最大待ち時間である$|4 - 1| = 3$を返します。 すなわち、上記の目的関数は、先ほど述べた「もっとも悪い状況(における待ち時間)」を表す数式に他なりません。

そして目的関数の外にあるmin関数は、「$x$(エレベーターの待機階)を動かすことで、最も悪い状況における待ち時間を最も小さくしなさい」という「最適化を行うという命令」にあたるものです。

最初に述べた説明は平易なのに、数式に直すと随分とまどろっこしいと思われたことでしょう。「なぜわざわざ数式に直すのか」と思われる方もおられると思います。しかし、日本語で説明が可能 かつ 最適解を目視で見つけ出せるのは、せいぜい今回の問題くらいの単純なものに限られます。ほんの少しでも問題が複雑化したときは、少なからず数式の助けを得なければ、記述することも解くことも不可能です。

「平均待ち時間最小化」の最適化コードに関する「オチ」 -解析的に解ける問題について

「平均待ち時間を最小化」することを目的とした下記のコードは、問題のシンプルさゆえに、最適化のコードとしては短い、と書きました。

このコードが解いている問題は、数式で書くと、下式で表されるのでした。

実はこの問題は、上述したコードよりも、もっと簡単な方法で解けることが知られています。

上記の問題で扱う入力(各階利用者数)について、すべての階の利用者の総数を取ると、ちょうど200人になります。 この時、上記の目的関数 $84 \times |x - 1| + 19 \times |x - 2| + 35 \times |x - 3| + 39 \times |x - 4| + 23 \times |x - 5|$ を最小化するエレベーターの待機階$x$は、上記の利用者分布の中央値(median)だということが証明されています。

言い換えると、「下の階から利用者数を順にカウントした時、利用者総数200人についてちょうど半分にあたる、100人目の利用者がいる解が最適な待機階」だということが分かっているのです。 このことから、下記コードは先述のコードと全く同じ出力を返してくれます。

(もちろん、numpyやstatisticなどのmedian関数を用いても構いませんし、その場合、最適化部分は1行で書けます。)

このように、机上の数学だけで「解く」ことができ、計算機を用いた探索を用いる必要がない問題を「解析的に解ける問題」といいます。解析的に解かれた問題は、計算機による探索を必要とせず、最適解を出力することが出来ます。

上記の思考の流れは、実は「中央値を取るだけの処理」だった…ということに気づかず、最初のコードのように(若干でも)大掛かりな実装をしてしまうことは不要なコストです。お客様には金銭的負担を強いてしまうことになりますし、もちろんスタッフもその分だけ疲労してしまうでしょう。 上記のことから、「何が難しい問題で、何が(実は)易しい問題なのか」を見極めるには知識が必要で、きちんとした技術基盤をもった開発チームに依頼することが重要だということが、ほんの少しでも伝われば幸いです。

機械学習と(数理)最適化のかかわり

今回はオペレーションズ・リサーチという分野で主に研究される「最適化」に特化して、「システムによる最適化」を解説しました。 今回紹介ものは「数理最適化」と呼ばれることもある手法で、近年HOTになってきている機械学習とは似て非なるものです。

アルタスファイブでは、現在は機械学習を援用した案件を主に受注しています。しかし、機械学習を含むシステムを実装する際も、あらゆる機械学習手法は「最適化」の概念をどこかで用いているため、すべての機械学習パッケージはどこかに「最適化を行う処理」を含みます。下記はその一例です。

機械学習手法最適化を行う処理アルゴリズム例
形態素解析形態素間の費用総和を最小にする経路を求めるビタビアルゴリズム
ニューラルネットワーク訓練データに対し、損失が最小となるパラメータを求める確率的勾配降下法
回帰分析データを最もよく説明するよう、二乗誤差を最小化するパラメータの値を求める最小二乗法

上記の中には、解析的に解かれているものもあれば(最小二乗法)、解の最適性及び求解速度に関する性能保証がなされているもの(ビタビアルゴリズム)、解の品質に関する保証がないものもあります(確率的勾配降下法)。 (エンジニアリングに親しい方が比較的「よく聞く」であろう名前を優先して挙げているので、粒度が異なることはご容赦ください。) 大事なことは、上記のいずれの処理も「最適化」の発想をどこかに含んでいるということです。

パッケージやライブラリを使う時はデータを入力しさえすれば出力を得られるわけですが、ときには内部に手を入れることもあるため、雑学程度の知識を持っていることは重要です。

お客様の抱える問題に対して「最適な技術」でお応えできる、技術力の高い開発チームをお探しなら、ぜひ一度アルタスファイブにお問い合わせください。

また、上記の記述を読んでピンと来たエンジニアとの面談も大歓迎です。いつでもお問い合わせください。

最近の記事タグ

関連記事

\(^▽^*) 私たちと一緒に働いてみませんか? (*^▽^)/

少しでも興味をお持ちいただけたら、お気軽に、お問い合わせください。

採用応募受付へ

(採用応募じゃなく、ただ、会ってみたいという方も、大歓迎です。)