1
日本ソフトウェア科学会第 41 回大会 (2024 年度) 講演論文集

動的最適化の挑戦
丸山 宏

我々は最適化問題の系列 P1 , P2 , ..., Pt , Pt+1 , ... を考える．この系列の上で，様々な問題設定を考えることができる（例えば，最適化問題 Pt の最適解がわかっている場合に Pt+1 の解を効率よく求めるにはどうしたらよいか，など）．
本稿では，このような最適化問題の系列上での問題設定を動的最適化と呼び，このような一般的な枠組みにおいてどのような応用があるか，いくつかの例を提示し，さらに人工知能分野の研究においての位置付けを議論する．なお本
論文は機械学習工学研究会 2024 年夏合宿にて既発表のものを若干修正して再投稿するものである．

メタの最適化は，個別の値 x が与えられて初めて，そ1 はじめにの目的関数の値 u(x) が与えられる (例えば，実際に最適化問題は，人工知能の様々な場面で現れる．最モデル訓練を行って，あるいは外部のオラクルによっ短経路問題，制約充足問題などは最適化問題の１形態て)，という問題設定になる．これをブラックボックとして捉えられるし，深層学習や生成モデルの訓練ス最適化と呼ぶ．ブラックボックス最適化は，必ずしは，ロス関数を最小化する最適化問題として定式化さも機械学習の発展から生まれたものではない．以前

れる．

から，進化計算，実験計画法，多腕バンディッド問題

最適化問題を解く手法は，数理計画法とも呼ばれ，など様々な最適化問題が知られていたが，これらは上線形計画法が最もよく知られている．線形計画法は記の定義に従えばブラックボックス最適化問題とい実行可能空間と目的関数がどちらも線形の式で与ええる．

られる問題設定だが，これを非線形 (ただし凸空間)

ブラックボックス最適化は，目的関数 u(x) が計算に拡張した凸計画法，離散問題に適用できる整数計画可能であればその形には制限がないので，最適化問題法，連続変数と離散変数を同時に扱うことのできる混の利用範囲を飛躍的に広げた．しかし，そこでは目的合計画法などが研究・開発されてきた．さらに，それ関数が静的，すなわち u(x) の計算を何回行っても同らの手法を実問題に効率的に適用する商用ツールがじ x に対しては同じ u(x) が返されることが仮定され普及することによって，20 世紀終わり頃には，最適ていた．

化問題は一通りやり尽くされた感があった．

世の中の実問題には，目的関数が時と共に変化する

一方，2010 年代に入ってから，機械学習 (特に深ものが数多くある．動的最適化を考える第 1 のモチ層学習) の急速な発展に伴ってハイパーパラメタ・ベーションは，目的関数が静的であるという条件を外チューニングのために最適化の研究が再び脚光を浴したときに，どのような最適化問題が考えられるか，びることになった．ただし，今までの最適化問題が，を明らかにすることにある．

目的関数の形を事前に与えたのに対し，ハイパーパラ
Challenges of Dynamic Optimization
Hiroshi Maruyama, 花 王/東 大/Preferred Networks,
Kao Corp./U. Tokyo/Preferred Networks.

最適化問題は，実行可能空間が，網羅的に走査できるくらいのサイズであれば解くのは難しいことではない．実行可能空間のサイズはその次元数に対して指数関数的に増加するので，最適化問題をうまく解く

コツの１つは，「この範囲の外側には，最適解は存在• x̂t+1 ∈ Dt のとき，x̂t+1 = x̂tしない（だろう）」という知識を使って，できるだけつまり，最適化問題列 P̃ が単調のときは，実行可探索空間を狭くすることである．しかし，そのことに能空間の拡張された部分だけを探索して，今までの最よって，本来欲しかったはずの解を見過ごしてはなら

適解 ût と比較すれば良い．

ない．動的最適化問題を考える第 2 のモチベーショ
ンは，ある１つの最適化問題を解いたときに，実行可

例: 関東地方の最高峰は日光白根山 2578m である．
関東・東北地方の最高峰はどこか．

能空間を拡大することによって，よりよい解が見つか

この場合，関東 ⊂ 関東・東北であるから，東北地ることが期待できるとしたら，どのように行うべき方の山々と日光白根山を比較するだけでよい．関東

か，を考えることにある．

地方の他の山々は比較する必要がない．ドメインを東北まで広げても，関東の山々の高さは変わらないか

2 動的最適化問題

らである．

我々は，ドメイン D 上で目的関数 u(x)(x ∈ D) を最短経路問題におけるダイクストラ法など，部分問最大化する最適化問題 P = ⟨D, u⟩ を考える．目的関

題の最適解が，全体最適解の一部になるような動的計数を最大化する x を x̂ = argmaxx∈D u(x)，その時画法は，単調な動的最適化問題と位置づけることがでの目的関数の値を û = u(x̂) とする．最適化問題の列

きる．

P̃ = P1 , P2 , ..., Pt , Pt+1 , ... があったとする．ただし，Pt = ⟨Dt , ut ⟩ とする．

2. 2 ドメイン拡張の最適化

系列 P̃ 内の，それぞれの Pt がお互いに全く独立である最適化問題を解いたとき，最適解がドメインのあるならばこのような問題設定を考える必要がない．

境界付近にあるときなど，ドメインを拡張したらさらPt を個別に解く以外にはよい方策がないからである．に良い解を見つかるかもしれい，と思うことがある．

そこで，動的最適化の枠組みの中で，研究課題を考えドメインの拡張が許されるとき，どのようにドメインるには，系列 P̃ 内がどのような構造を持つか，に注を拡張すればよりよい解が得られるだろうか．

目する必要がある．系列 P̃ に構造を導入することに最適化問題の単調な列 P̃ があったとする．今が時よって，どのようなサブ問題が考えられるか，そのう

刻 t だとして，時刻 t + 1 のドメイン Dt+1 をある集

ちのいくつかの例を以下に示す．

合 D から自由に選べるとしたとき，どのような Dt+1を選べば ût+1 を最大化できるだろうか，という問題

2. 1 差分最適化
時刻 t の最適化問題 Pt = ⟨Dt , Ut ⟩ についてその解として，ドメイン拡張の最適化問題を定式化できる．
ここでdef⟨x̂t , ût ⟩ がわかっているときに，Pt+1 を効率よく解く• dD = Dt+∆t − Dt

ことができるか．

• dû = ût+∆t − ût

系 列 P̃ に 構 造 を 導 入 す る や り 方 の １ つ と し てdefとする．

単 調 性 と い う 概 念 を 定 義 す る ．最 適 化 問 題 の 列

単調な列 P̃ が微分可能であるとは，∆t → 0 のとP̃ = ⟨D1 , u1 ⟩, ⟨D2 , u2 ⟩, ... が単調であるとは，この列

dû
き，勾配 dDが計算可能であることをいう．時刻 t でが以下の２つの条件を満たすもの，とする．の勾配がわかっているとき，時刻 t + 1 での目的関数

1. Dt ⊂ Dt+1を最大化するためには，勾配が最大になる方向にドメ

2. ut+1 (x) = ut (x) for x ∈ Dt

イン Dt+1 をとる，という戦略が考えられる．

すなわち，実行可能空間は単調に増加し，今までの空例: 関東地方の最高峰は日光白根山 2578m である．

間における目的関数の値は変化しない (安定) とする．

隣接県を 1 つ追加して最高峰を最大にするには，どこの条件のもとで，以下を示すことができる．

• ût+1 ≥ ûtの県を追加すればよいか．
長野県を追加すれば，奥穂高岳 3190m になるが，静岡県または山梨県を追加すれば富士山 3776m にな作ることができる．また，ドメインの拡張においてる．したがって，静岡県または山梨県を追加するのがは，ドメインの次元を変化させる問題設定もあり (例最適である．

えば，制約充足問題において新たな変数を導入する，関連する問題として，ドメイン拡張によって最適性の向上ではなく，解のロバスト性を向上させる，といなど) 大変興味深い．動的最適化問題のタクソノミができれば，今後の研究が大いに進むだろう．

う設定もありうる．最適解に対する目的関数値 û = x̂がドメインや目的関数の小さな擾乱に対して大きく

3 動的最適化の応用動かないことをその解がロバストであるという．最3. 1 材料探索・創薬

適解のロバスト性を調べる手法を感度分析と呼び，機第一原理計算によるシミュレーションを，機械学習

械学習を含む様々な領域で研究されている．

によるサロゲートモデルによって何桁も高速化する技術が発展してきていることにより，材料探索や創薬

2. 3 非連続点の検出の世界で，今までに全く知られていない新しい材料やPt と Pt+1 の関係を調べるだけでなく，P̃ 全体の医薬が開発されることが期待されている．

性質を調べる問題設定も考えられる．例えば，P̃ のしかし，いかに高速化されたとしても可能な原子の中で，xˆt が非連続に動く場合，そのような臨界点を組み合わせ空間は膨大であり，やみくもな探索はいた事前に検出できるだろうか．

ずらに計算資源を浪費することになる．動的最適化

微分可能な最適化問題列 P̃ があったとする．このの研究の進展によって，見込みのありそうな部分空間

場合，ドメイン D を連続に変化させれば û は連続にを探索し，その結果に基づいて最適なドメイン拡張を変化するが，x̂ はそうとも限らない．ût+1 > ût なら提案できる一般的な手法が確立されれば，材料探索やば x̂t+1 は，Dt の外にあるので，x̂t が Dt の内部点創薬の研究が飛躍的に進むことが可能かもしれない．

である場合には，x̂t と x̂t+1 は離れた点にあることになる．

3. 2 アルゴリズムの探索

複雑系のシステムで，あるパラメタを変化させてテスト駆動開発や自動デバッグの文脈では，与えらいったときにシステムに非連続な変化が起きることれたテストセットを満たすプログラムを自動生成すを，事前に察知できるか，という問題については，る手法が研究されている．これも，可能な空間は膨大

Scheﬀer らによる興味深い論文 [1] があり，システムであるので，少しずつテストケースを加えて，既存のが臨界点に近づくと，システムの自己相関が大きくな(それまでのテストケースを満たす) コードを修正しるなど特有のシグナルが観測されることが示されてていく，という手法がとられる．この場合，ドメインいる．動的最適化の文脈で，このような非連続点の検D はプログラムコード全体の集合であり，u(x) がテ出ができるための条件は何か，などは大変興味深い問

ストスイートに相当する．ある時点のテストスイー

題と言えるだろう．

ト ut を満たすプログラム x̂t が知られているときに，

例: 関東地方の最高峰は日光白根山 2578m である．

新たに加えられたテストケースを加えた ut+1 を満た隣接地域を少しずつ追加する場合，白根山より高い地

す x̂t+1 を見つけるにはどうしたらよいか，という意

域が現れた瞬間に最高峰の位置 x̂ がジャンプして移味で，動的最適化問題の 1 形態といえる．

動する．このようなジャンプは，探索している地点の標高が 2578m に近づくと臨界点が近いことがわかる．

3. 3 科学法則の探索
科学の営みを AI で加速するにはどうしたらよい

2. 4 その他の問題設定か，という議論が活発になされている．例えば，AI目的関数 ut が時と共に変化する問題設定では，ut

ファインマン [2] は，ファインマン物理学の方程式をに様々な制約を置くことによって，様々なサブ問題を機械による探索で再発見しようという試みであるが，長さ・時間などの基本物理量が事前に与えられた空間ることによって探索を効率化する動的計画法は，部分の中を探索するため，今までの物理学の枠を超えた新問題の列を動的最適化問題と見做すこともできる．2

たな発見を求めるのには無理があった．動的最適化の章で議論したような動的最適化問題のテクニックが，研究が進めば，まだ知られていない基本物理量を仮定

既存の動的計画法に新たな知見をもたらすかもしれしてみる，など，ドメインを拡張して新たな法則を発ない．

見する，などということが可能になるかもしれない．

4. 2 ブラックボックス最適化
3. 4 政策の探索

1 章で，機械学習におけるハイパーパラメタのチュー政策は，それを実現する法体系が文書で表現されるニングが，ブラックボックス最適化に新たな光を与えのであれば，法律の可能空間をドメイン D とし，何たことを述べたが，ブラックボックス最適化のアイを善とするか (例えば「最大多数の最大幸福」) に関ディア自体は，古くから知られている．典型的には進する合意を目的関数 u とした最適化問題によって構化計算であるが，それ以外にも，直交表を用いる実験築できるはずである．しかし，実際に法律が制定され計画法や工場における品質管理に用いられるタグチたとして，その効果がどのように社会に現れるかを予メソッド，マーケティングに使われるコンジョイント測することが難しく，高度に技術的な政策決定以外に分析は，いずれも 2 変数間の不明な従属性が目的関数はほとんど用いられてこなかった．に与える影響を最短のステップで見つけ出して全体を大規模言語モデル (LLM) の登場によって，その条最適化する手法であり，ブラックボックス最適化の範件は変化するかもしれない．すなわち，LLM は様々疇である．また，多腕バンディッド問題や，オンライな人の価値観を内在していて，適切なプロンプト (例ン予測問題，ベイズ最適化，強化学習も，探索をしな

えば「あなたは 66 歳の男性で，…」のようなペルソがら目的関数の確率分布を推定することで最適化を行ナを指定する) を与えることで，そのような個別の価うという意味で，ブラックボックス最適化といえる．

値観を引き出すことができる．これらのペルソナを使って新法令に対する人々の反応をシミュレートで

4. 3 制御理論

きれば，政策決定はブラックボックス最適化問題とし制御理論は目標に対する現状の差を最小化する問て定式化できる．この場合，人々の価値観は時と共に題を継続的に解いている，という意味で，本稿の動的変化するので，価値観の変化を法令に反映させるため最適化の枠組みの 1 例と考えられるものである．制には動的最適化を行う必要がある．

御理論においては，通常ドメイン (入力変数の数や値の範囲) は変化しないものとして扱うが，一方で評価

4 関連領域

関数 u() は，外界の擾乱などによって変化するものと

4. 1 探索問題・制約充足問題して扱われる．また，入力変数に対してシステムの応最短経路問題などの探索問題は，経路の集合をド答が遅れるために，システムの時間軸上での動的な挙メインとする最適化問題として定式化できる．また，動を目的関数に反映させる必要がある．

3SAT 問題などの制約充足問題は，目的関数として制制御理論では，短い時間単位での振る舞いを線形と約を満たせば 1，そうでなければ 0 とする最適化問題

仮定することが多いが，ロボット等の制御で注目を浴と考えることができる．制約充足問題の 1 つのバリ

びている深層強化学習では任意の多次元非線形モデエーションとして，制約に重みを付け，満たしているルを扱えることで，より複雑でかつ各ステップで大き制約の重みの合計を最大化する問題があり，このような変化が起きる系の制御を可能にした．

な場合に制約を動的に出し入れする動的制約充足問
題があり，これは動的最適化の 1 形態といえる．
また，共通の部分問題の最適解を 1 回だけ計算す4. 4 ゲーム理論

ることがわかってきた．

複数のエージェントが，それぞれの時刻で何等かの今後，人間の知性を模倣する技術の開発が一段落す

打ち手を実行するゲームにおいては，一方のエージェると，より高次の知性を求めて探索・最適化の技術がントから見ると，1 手ごとに可能な打ち手の集合 D再発展するであろう．今までの探索・最適化の大きなと，打ち手 x の評価関数 u(x) が変化する動的最適化

ボトルネックは，探索空間 (ドメイン) が予め固定さ問題を解いている，と見ることもできる．ゲームにれて与えられていることにある．動的最適化は，ドメ

よっては，特定の盤面の評価関数がその前後の文脈インを拡張できる枠組みなので，現状の最適化におによって変化しないものがあり (例えばオセロのあるける問題に，1 つの突破口を与えるものとして期待し盤面では，先手必勝か，後手必勝か，あるいは引き分たい．

けかが決まっている)，そのようなゲームにおいては，謝辞

動的計画法で使われる，部分問題の計算を記憶してお本稿は，2024 年 2 月に箱根強羅温泉で行われた機械

くテクニックが使える．このように，様々な分野で研学習工学研究会 (MLSE) 冬合宿での議論が元になっ究されてきたテクニックを，動的最適化問題という枠たものである．特に，ドメインや目的関数の拡張を，組みで捉え直し，他の分野にも適用可能であるかどう最適化問題の列として定式化することは，今井健男氏かを考えるのも興味深い問いといえよう．の示唆によるところが大きい．議論に参加してくださった方々に感謝する．また，査読者のコメントは原

5 おわりに稿を改善するのに大いに役立った．ここに感謝する．

初期の人工知能研究においては，真の知性は理性的・論理的思考にあるという考え方から，探索や最適

参 考 文 献化問題のアルゴリズムが盛んに研究された．その後，[1] Scheﬀer, M., Bascompte, J., Brock, W. A.,
Brovkin, V., Carpenter, S. R., Dakos, V., Held, H.,
Van Nes, E. H., Rietkerk, M., and Sugihara, G.:
Early-warning signals for critical transitions, Nature, Vol. 461, No. 7260(2009), pp. 53–59.
[2] Udrescu, S.-M. and Tegmark, M.: AI Feynman: A physics-inspired method for symbolic regression, Science Advances, Vol. 6, No. 16(2020),
pp. eaay2631.

このようなアルゴリズミックな手法では，人間が子供でも簡単に行える画像認識や，言語の運用などが到底実現できないことがわかり，人工知能の冬が訪れた．
近年，大規模言語モデルの発展によって，画像認識や言語運用が人間並み (ヒューマン・パリティ) に行え