イベント / EVENT
平成18年度 第8回 Q&A
第8回 2007年2月14日(水)
最適化
--ものごとを効率的に行うには--
宇野 毅明(国立情報学研究所 情報学プリンシプル研究系)
講演当日に頂いたご質問への回答(全13件)
※回答が可能な質問のみ掲載しています。
一般の人が最適化アルゴリズムを活用したいときには、どのような方法があるのでしょうか?パソコンで応用する方法など、うまいアイディアがあればご教示ください。
*個人的には、株式売買最適化ができると嬉しいので、時系列的に変動するデータを相手にした最適行動選択モデル等があれば面白いのですが・・・。
「もの」に関する点では、「一般の人はプログラムを組まない」と思えば、やはり目的にあったソフトを購入するのが最も早いと思います。自分でモデル化をする、という目的であれば、簡単な最適化のソフトを使うのがよいと思います。「モデル化」に関しては、日常生活に出てくる問題は小規模で変則的なものが多く、抽象的な概念を導入しづらいので、むしろ「論理的な評価・推測・判断」を行う方法のほうが重要かもしれません。ご質問にあるような株式売買を個人単位で行う場合には、最も重要な要因は「株価変動の予測」と「投資行動の戦略」ですので、最適化の出番は少ないかもしれません。投資モデルに関しては、金融工学の教科書を紐解いていただければ、いくつか基本的なものが紹介されているかと思います。ただし、株式売買には「こうすればよい」という一般的な方法は、最適化も含めて存在しません。存在すると、みながその方法を採用して、株価が上がり、儲からなくなるからです。多くの金融モデルでは、「リスクを減らす」ことに主眼を置いていて、これは最適化できます(といっても過去のデータから得た予測が大きく外れなければ、ですが)。
状況が変化する時に最適の行動をするためには、未来予測をする必要があると思うがどんな考え方がありますか?(時々刻々変化する株式市場で、この株をいつ買い、いつ売ればよいか?)
株式売買に関しては、学問的な必勝法はありません。あれば、その方法が一般的になり、儲からなくなるからです。じゃんけんに必勝法がないのと似ています。予測に関しては、最適化より確率統計の技術が重要になります。良い確率統計のモデルを作ることが重要で、そのモデルを現実に当てはめ、実際の解を得るときに最適化が必要になるのであれば、そのときに初めて最適化の出番となるわけです。確率統計の教科書を参考にしてください。
"良い解のそばに良い解がある"ことが成り立つか否かを決定する要因・条件は何でしょうか。(ある条件の下で、"良い解のそばに〜"に妥当性があることを判定する基準/目安はどう見出せばよいのでしょうか?)
この問いに対する決定的な答えは、まだわかっていません。わかっていないので、最適化の問題は、学問的に難しいのです。学問的なアプローチとしては、こういう条件が成り立つような問題はどのような問題だろうか、ということを研究し、解明された範囲を広げていく、という作業をしています。その中でも、著名なものに分割可能性・直線性・凸性があります。分割可能性は、問題を分割してそれぞれの最適解を得たとき、両者を合わせたものが全体の最適解になるかどうか、ということ、直線性は、ある方向に沿って問題を徐々に大きくして解いていく、としたときに、ある大きさの問題が、それよりも小さな問題の最適解の情報から簡単に構築できるか、ということ、凸性は、2つの解の中間にある解は、2つの解の平均よりも悪くない、という性質です。これらの性質が成り立つものに関しては、ある程度簡単に、必ず、最適解が得られることがわかっています。
「良い解のそばに良い解がある」が成り立つ/成り立たないは、目的や制約のどのような点に着目すればわかるのか?
経験的には、「一部の変更が、全体に大きな影響を与えないこと」「変更が小さければ評価値の変化も小さい、といった連続的な傾向が見えること」といったことになります。理論的な解明は難しいので、本当に成り立つかどうかは、計算をしてシミュレートする必要があります。問題の解をいくつもつくり、この性質が成り立つかどうかを見てみる、という方法のようです。
今回の話で出てきた方法は、どのくらい実用化されているのでしょうか?
・採用社数、業界の種類。
・ソフトウエア出荷状況?、値段 など。
残念ながら、良い情報はありません。最適化は情報システムのごく一部ですし、自社部門が開発を行っていることも多く、どの会社がどのように使っているか、という情報を把握することは非常に難しいです。しかしながら、最適化を含む情報システムを作る会社がいくつもあり、そこがいくつもの納入実績を持つ、ということからは、少なくともマーケットが成り立つ程度の数、採用実績があると考えてよいと思います。特に、工場での工程管理(スケジューリング)のソフトに関しては、非常に多くの会社で使用されているはずです(少なくとも100はあるとおもいます)。値段はまちまちです。最適化システムを導入するうえで最も大変な作業は、会社のITシステムをどう使い、どのように最適化をするか、というところですので、そこにはコンサルタント業務が必要になります。何人かの人間がチームを組み、ソフトとハードを新たに導入してシステムを作る、ということになれば、何千万という価格になると思います。逆に、モデル化やデータの変形などの部分を自分でするということになれば、パッケージのソフトを使うことになると思います。私が聞いた中で最も安いものは、簡単な時間割作成ソフトや配送計画のソフトで10万円程度です。
「最適の選択」の決定過程には、プラスの面だけを比べる場合は簡単だが、マイナス面や組み合わせから生ずるトレードオフ、プラス・マイナスの評価法など、条件を加味する複雑な組み合わせになる。スーパーコンピュータでシュミレーション計算できるか。
トレードオフを評価する問題を「多目的最適化」といいます。例えば乗り換え案内で、時間と値段を気にするような場合です。技術的には、例えば、いくつか選択の候補を出すようなことは、通常の最適化に比べ、それほど難しくなることなく、行えます。むしろ大変なのは、選択を行う人間のほうです。評価の仕方の問題になります。時間と値段のトレードオフがあるときに、最終的にどの選択をするかは人間にかかってくるわけです。ここばかりは、コンピュータで自動的に選択するわけには行きませんし、そのようなことをしても、あまり喜ばれないと思います。評価の方法が問題となりますので、スーパーコンピュータのように計算がとても速くできる、ということはあまり手助けにはなりません。
(1)リンゴが好きか、ミカンが好きかは、脳が最適化処理をしているのでしょうか?そのメカニズムは?経験を積めば学習効果と言われますが、最初の好き嫌いはどうして決めているのでしょうか?生物の本能は最適化の成果?
(2)この宇宙は局所的に最適化を目指している(エネルギー最小化など)と思いますが、全体的にも最適化されているのでしょうか?セービング法でしょうか。
(1)分野違いですので断定はできませんが、こういった部分に関する脳の働きは、まだ良くわかっていないと思います。そもそも、なぜ人間が意思を持って生きているかがわかりませんので。ただし、本能の部分にある種の最適化の仕組みが入っている、という点は、説明力のある観察だと思います。個々の種が環境に応じて、自然淘汰で進化していく、というプロセスが、ある種の最適化のプロセスであるとみなすこともできますので、そういう意味では、本能の部分に、種が生き残るための良い戦略が入っていると考えられます。ただし、これは近代社会における人間には当てはまりません。近代社会は自然淘汰のプロセスから遠いところにありますし、自然淘汰で最適化されるには、近代社会になってからあまりに時間が短いです。
(2)「安定した状態に向かう傾向がある」という点では、安定度を指標とした最適化を行っているとみなせると思います。しかし、安定するために宇宙が存在しているわけではないので、そういう意味では、人間の言うところの「最適化」とは少々異なると思います。宇宙をシステムと見るならば、「物理法則」と「最初の状態」が与えられたときに、宇宙がどのように変化するのだろうか、という系(システム)としての宇宙を見るようなことになると思うのですが、局所的な変化が、というような議論は、このようなシステムとしての宇宙を語ることになるのだと思います。
宅急便などで、ばらばらな時間指定のある複数の荷物を配達するための最適ルートを求めるアルゴリズムについて。
研究者の数だけ解き方がありますので、これ1つというわけにはいかないのですが、講座で解説した局所探索はそのまま使えます。セービング法は、そのときに一番都合のいいところに入れても(つまり空き時間がなるべくないようなルートを作る)、後から次のお客を近くのルートに入れようとしても、時間の制約で遠くのルートに入れなければならなくなったりして、性能が悪くなります。局所探索の入れ替えて、評価して、よくなったら採用する、という方法はそのまま使えます。解の評価に、到着が早すぎて、指定の時刻までまつことが少なくなるようにする、という尺度を入れる必要がありますが、工夫をこらせばそれなりの解がそれなりの時間で出てくるそうです。時間の指定が入ると、人間にとっても難しくなりますので、人間の作業を自動化してより良い解を得るということはできるようです。
google など、検索エンジンの現況の評価について。
検索エンジンは、技術的にはデータベースと探索アルゴリズムですので、その面ではあまり最適化は関係ありません。欲しいページを見つける、と言うことに関しては、最適化より、「ページを評価する方法」が重要です。こちらは、きっと、文章理解を機械的に行う、という面が強く、言語学の分野になると思います。
囲碁では、俗手(イモ筋)の隣に良手(最適解)があるといわれていますが、セービング法の配送計画、性質と反対のように見えます。アルゴリズムの性質が正反対なのでしょうか?
いくつか考慮すべき点があるのですが、「俗手」は人間が判断することですので、まず、何が俗手かを数理的に明らかにすることが難しいです。それと、囲碁自体が非常に難しい問題です。理由は敵がいることで、配送計画や最短経路の問題では、配送をじゃまする敵がいるわけではなかったので、のびのびと最適化ができたわけです(敵のいない囲碁は簡単ですね)。囲碁のような、対戦型のゲームの戦略を最適化する場合、敵のいない最適化問題を解く戦略はまったく通用しません。対戦ゲームのコンピュータソフトを作る場合、やはり人間の戦略を学ぼうとすること、および、計算速度のメリットを生かした網羅的な探索を行う、という方法が主流です。
渡り鳥の雁行は長い歴史か、生物学的な理由か。気象学的な条件などで「効率的」「最適化」された行動と考えられるが、そうした自然現象を活用する方法はあるのか?今回、説明は人為的な条件ばかりなので、いささか不満が残ります。
私は生物は分野外ですので、雁行に関しては、生物の研究者に聞くのがよいと思います。ただし、進化のプロセスに関しては、最適化のプロセスのようなものだとみなすことができるので、その意味では、自然に学ぶところは有るかと思います。実際に「遺伝アルゴリズム」という、進化の過程をアイディアにした最適化の手法がありますが、自然界は個々の生き物がそれぞれ独立に作業するのに対して、コンピュータは1台で計算をするわけですから、1台で多くの個体の面倒を見なければいけない分、効率は落ちます(複数のコンピュータを使えば速くなりますが、複数のコンピュータを使えば、他の方法も速くなります)。自然界は自然界で動いており、目的を持っているわけではありませんので、最適化というよりは、コンピュータでシミュレーションしよう、という話になるのだと思います。そして、シミュレーションから、新たなモデルを導くような知見が得られば、それは有意義なことなのだと思います。人為的でない条件、というと、難しいのですが、例えば、天気の予測のようなものを想定していらっしゃるのでしょうか?これも、やはり最適化ではなく、確率・統計を用いた予測モデルとシミュレーションによる計算、がメインになります。シミュレーションは、物理的な条件と最初の状態を与えて、全体としてどのように変化していくかを観察する行為ですので、ぽんと最適解だけ得られればよい、という最適化とは目的が異なるようです。自然とのかかわり、ということであれば、例えば温暖化を防ぐための最適戦略、というような問題が考えられると思いますが、まずは、「温暖化を防ぐために、人間は何をできるか」というところを明らかにする必要があります。日本国民全員が車の使用をやめれば、CO2は劇的に減ると思いますが、それは現実的ではありません。そうなると、ここまでならできる、という条件をまず見つけ出し、経済的な損失が少なくなるよう、最大限にCO2の排出を抑えるようにモデルを作るわけですが、そうすると、やはり条件は人為的なものになってしまいます。最適化によって人間の行動が帰阪されてしまう、ということは、運用上よろしくありませんので、そういう意味では、現実的な問題の条件としては、人為的なものが多くなるのだと思います。
OS、インターネットブラウザー、メールソフトなどで動作する"最適化"は、本日の講義内容の観点で説明するとどうなりますか。
最適化という単語は、いろいろな分野で使われていますが、メールソフトにある「最適化」は、保存しているメールを圧縮して容量を小さくし、同時に検索用のデータを付加して検索を速くすること、ですので、講義で述べた最適化とは異なります。ブラウザの最適化は、「webページのレイアウトを、見やすくなるように最適化する」ことです。そういう意味では最適化問題なのですが、「見やすいとはどういうことなのか」が不透明です。レイアウトに関して、何かしっかりした評価値を与えられればいいのですが、現状としては、「このようにすると見やすい」ということが発見されていく段階だと思います。つまり、人間による試行錯誤がメインで、機械で自動化できるレベルではなく、むしろ人間の視認性に関する研究なのだと思います。
Excelの最適化ツールの使い方を教えてください。
Excelの追加機能の中にソルバーというものがあり、これが最適化のツールになります。詳細はすみません、実際にExcelの最適化ツールを使ってはいないので、解説はできないのですが、線形計画という種類の問題を解くことができるそうです。書籍や、web ページを参考にされれば、もっと詳しい使い方がわかると思います。
今回のテーマに対応して申し上げたい。人類が行きつづけていくうえからの"最適"とか"効率的"という言葉を考えるとさまざまな視点が求められる。安全、ユビキタス、・・・さまざまな立場から、政治にはマニフェスト、法テラス、どこまでデジタル化して(アナログをどう取り入れて)いけるのか、・・・・実に様々だ。取り上げたいものは、何だったのか、どうしぼったのか。もう少し分かりやすくしぼって欲しかった。
難しい問題ですね。取り上げたかったものは、最適化という学問分野と、そこにある技術の紹介です。通常、学問は「○○についての研究」というように、ある対象(生物とか、化学物質とか、文学とか人間とか)に対して、いろいろな手段や手法や実験を通して、そのいろいろな側面を明らかにしていく、というものだと思いますが、最適化の場合は、その研究対象自体が「手法・手段」ですので、混乱があるかと思います。研究や事業を行うときに使う「手法・手段」の研究をしているわけです。この説明はしっかりとすべきでした。申し訳ありません。学問の紹介は抽象的になりがちですし、学会などの紹介はおもしろくありませんので、その中から、一番日常に近い部分にある問題に対する、モデル化と手法を紹介しました。「立場」という点については、各々の分野で解く必要があるとわかった問題に対して、その解き方を研究する、というスタイルです。そういう意味では、デジタル化などが及ぼす社会への影響とは、関係が浅いです。また、政治や社会に影響を持つ問題の場合、だいたいは評価に人間的な要因が深く絡み、コンピュータで出した答えは参考程度にしかならない、という場合が多いようです。配送計画のように、効率が上がった分、人員は削減されるのか、という問題は、やはり企業のポリシーによると思います。給料を上げる選択肢もありますので。効率が社会に与える影響については、最適化の手法でなく、社会問題として捉えるべきだと思います。コンピュータを使った問題の解き方を通して、では、社会は見えませんので。
学問として、現実を追いかける形で発展したのですか?
そうだと思います。が、現実的でない方向に問題を抽象化して、数学的に面白い構造を探求する、という方向もありますし、それはそれでりっぱに発展しています。しかしながら、現実問題を扱うほうがうけがいい、という点もありますし、現実社会に直結することができますので、企業と共同研究を行う、といった点からは、この方面が発達しています。(それに、紹介する題材としても面白いです。)