1．は
じ め に
人工知能は 1950 年代半ばからの第一次ブームに始ま り，第二次ブーム，第三次ブームと変遷してきている． ブームのたびごとに問題を解くための主要な技術や応用 分野は大きく変化してきた [寺野 18]． 本稿で取り上げる問題解決，探索，制約充足，最適化 などの研究課題は第一次ブームのときから主要な研究課 題となっていたものであり，伝統的な人工知能の教科書 では第 1 章や第 2 章で説明されるような基礎的な課題で ある． これらの基礎的な課題は第二次ブームや第三次ブーム の新しい技術で解決されるわけではない．これらの課題 は依然として広い応用分野をもっており，今でも手法の 改良が進められている．また，その課題の解決技術や応 用分野もそれ自身で新しい技術に発展するだけでなく， 第二次ブームや第三次ブームの技術と融合して新しい展 開を見せているものもある． 本稿では，これらの基礎技術の概要説明と現在の研究 の動向や話題に触れることを目的としている． 第 2 章では問題解決の変遷を述べ，第 3 章では探索に よる問題解決の概説とゲームにおける探索手法の遷移を 説明する．第 4 章では探索の応用分野の一つである制約 充足問題と，近年，研究が活発に行われる充足可能性問 題を説明し，第 5 章では機械学習において重要な技術で ある最適化について紹介する．2．
問 題 解 決
2･1 問題解決の変遷 i．第一次 AI ブーム 人工知能という用語は 1956 年のダートマス会議で決 められたことはよく知られている．この会議ではコン ピュータの知能化のためにさまざまな課題─コンピュー タ，自然言語処理，ニューラルネットワーク，計算の理 論，抽象化，創造性など─が話し合われた [マコーダッ ク 79]．この会議において，サイモンとニューウェルは Logic Theorist（LT）という世界で最初の人工知能シス テムを紹介した．LT は論理式に推論規則を適用するこ とで定理証明を行うプログラムであり，組合せ爆発を防 ぐためにヒューリスティクスを利用した探索による問題 解決を行っている．しかし，その能力の高さにもかかわ らず，コンピュータプログラムで知能を実現することに よる違和感もあり，LT の評価は高いものではなかった． その翌年，サイモンとニューウェルは汎用問題解決器 GPS（General Problem Solver）という，問題を一般的 なアルゴリズムで解決するプログラムを発表した． GPSは解決したい問題を「状態」の集合と「オペレー タ」で表現している． ● 状態 ● オペレータ ・ 適用条件：当該オペレータを適用するために「状 態」が満たすべき条件． ・ 適用効果：当該オペレータを適用した場合の「状 態」の変化． GPSは初期状態 S とゴール状態 G が与えられたとき に，S と G の差異を小さくするようにオペレータを選問題解決，探索，最適化の基礎と展開
Fundamentals and Development of Problem Solving, Search and
Optimization
新田 克己
産業技術総合研究所，国立情報学研究所Katsumi Nitta National Institute of Advanced Industrial Science and Technology. / National Institute of Informatics. [email protected]
小野 功
東京工業大学情報理工学院Isao Ono School of Computing, Tokyo Institute of Technology. [email protected]
Keywords:
problem solving, search, constraint satisfaction problem, satifiability problem, optimization. 「人工知能の今」〔第 2 回〕択する．そのオペレータを適用するための前提条件 c が 満たされているときはオペレータを適用して状態を更新 する．c が満たされていないときは c をサブゴールとし てサブゴールを満たすように新たなオペレータを選択す る．このように GPS は複雑な問題を解決するために， その問題を，より簡単な下位レベルの問題の解決結果を 利用する，というように問題を分割する探索手法である． GPSのように，当時は，人間の思考は特定の個別知 識に依存せず，問題を定式化し，一般的な問題解決のア ルゴリズムを適用することによって知的な処理が実現で きると考えられ，ゲームやパズルなどの研究がなされた． ii．第二次 AI ブーム 1960年代後半になり，医療診断や設計などのさまざ まなエキスパートシステムが開発され始める．多くのシ ステムは知識ベースと推論機構によるアーキテクチャ （知識ベースシステム）の形をとり，専門分野の知識や 専門家のヒューリスティックな知識を利用して問題を解 決するようになる．我が国の第五世代コンピュータプロ ジェクトをはじめとして海外でも人工知能の大型プロ ジェクトがスタートしたが，知識ベースの構築や管理の コストの高さや記号処理による知識処理の限界のため， 世界が閉じていない分野での実用的なエキスパートシス テムの開発が疑問視されるようになった． iii．第三次 AI ブーム 2010年代になり，インターネットが発展して大量の データが容易に入手できるようになったことや検索技術 の発達やさまざまな機械学習技術の発達のため，問題 解決の枠組みが大きく変化した．特に深層学習（Deep Learning）の技術の進歩により，音声認識や画像認識な どの認識技術の精度が高くなったことや言語生成の能力 が向上したことで，知識ベースシステムでは実現できな かった機能が実現できるようになり，応用分野が格段に 広がった．
3．
探 索
ゲームやパズル，プランニング，制約充足問題など多 くの問題は状態空間の中で初期状態から最終状態に至る までの探索問題として捉えることができる． グラフや木構造の探索にはさまざまな手法が開発され ている [太原 88, 石塚 96, Winston 77]．本章ではその主 なものを簡単に説明する． 3･1 知識を用いない探索 深さ優先探索は現在の状態（節点）から始まる探索を できるだけ深める探索方法であり，幅優先探索は初期状 態（初期節点）に近い状態（節点）から探索を行う方法 である． 木の平均分岐数を b，一番浅い解の深さを d，探索木 の最大深さを m とするとき，それぞれの探索法の解に 至るまでの時間計算量と空間計算量は表 1 のようにな る． 幅優先探索は複数の解が存在する場合に，最も初期 状態に近い（最も浅い）解が検出できる．しかし，解に 達するまでに状態の記憶量が膨大になるという問題があ る．一方，深さ優先探索は解が見つかるまでの記憶量が 少ない反面，解が存在しない先への探索が深く進行しす ぎる可能性がある．また，解が見つかったとしても最も 浅い解とは限らない．そこで深さ優先探索の利点を生か しながらその問題点を改良する手法が研究されている． 深さ優先探索において，ある程度深く探索して解が見つ からない場合は，その節点の探索を打ち切って，別の節 点から深さ優先探索を再開する方法が深さ制限探索であ る．また，探索深さの制限を最初は 1 とし，解が見つか らないときは深さの制限を 2 とする，というように深さ を一つずつ増やしていきながら深さ制限探索を行う方法 が反復深化探索である． 3･2 知識を用いた探索 木を探索するにあたり，各節点 n の良さを評価する評 価関数（ヒューリスティック関数）f（n）があれば質の 高い解の探索を行うことができる．評価関数は問題のク ラスによって異なる関数が用いられる． § 1 山登り法 各節点からゴール節点へのコストが推定できるとき， コストが現在のコストより小さくなる方向に探索を進め る方法を山登り法という．初期節点からゴール節点まで の経路において，コストが常に小さくなっていくような 問題のクラスでは山登り法はゴール節点に達することが できる．しかし，途中に評価値が局所的に最大（極大） になるような問題では，そこから探索が進めなくなる， という問題がある． § 2 最良優先探索とA＊アルゴリズム 初期節点 S からある節点 n まで探索が進んだとき，そ こまでのコストを g（n）とし，n からゴール節点 G まで の最適コストを h（n）とし，h（n）の推定値を h（n）と する． 節点 n にいるとき，S から n までに展開したすべての 節点 niにおける h（n i）を保存しておき，次に探索する 節点を選択するときに，h（n）が最小になる節点を選択 する方法を最良優先探索という．最良優先探索は記憶量 が膨大になるため，有望な少数の節点のみを保存するよ うにして記憶量を削減する探索法をビーム探索という． Sから n を通過して G に至るまでの全コスト f（n）は 表 1 探索法の比較O(bd+1) O(bm) O(bd)
f （n）＝ g（n）＋h（n） となる．この f（n）に基づいて次に探索すべき節点を選 択する方法をA アルゴリズムという． h（n）の推測値 h（n）の値が常に h（n） h（n） になっているときは，次に探索すべき節点を f（n）＝g（n） ＋h（n）に基づいて選択することによって，最適コスト の経路を見つけることができる．この探索手法をA * アル ゴリズムという． 3･3 確 率 的 な 探 索 前 2 節では探索空間をシステマティックに生成できる 場合の探索方法を述べた．しかし，組合せ爆発により膨 大な探索空間が存在する問題や無限の連続空間が存在す る問題では，システマティックな探索手法はとれない． 一般的な応用問題では，このような空間の探索をする必 要があることが多い．このような場合，現在の状態に隣 接する状態を局所的に探索する最適化問題として扱わ れ，大局的な最適解を求めるために確率的な探索手法が 用いられる． § 1 シミュレーテッドアニーリング 山登り法では，現在の節点の評価値 E（x）と隣接する 節点の評価値 E（x）を比較し，ΔE＝E（x）－E（x）が正
ならば隣接する節点に移動した．それに対し，シミュレー テッドアニーリング（Simulated Annealing：SA）は自 然界に存在する熱揺らぎの現象をコンピュータ上で擬似 的に模倣し，温度を徐々に冷却する（熱揺らぎを徐々に 収束させる）ことによって，評価値が局所的最適に陥る のを防ぐ手法である．SA では以下の受理関数で与えら れる確率で xに移動するかどうかを決定する．
accept（ΔE, T）＝ min（1, exp（－（ΔE）/T））
Tは遷移の確率を決定する温度パラメータである．T は当初は大きい値をとり，評価値が現在より悪化しても 次の節点に高い確率で遷移するが，徐々に T の値を小さ くして（Tk＋1＝αTk）収束に向かう（αは 1 未満の定数）． § 2 遺伝的アルゴリズム 遺伝的アルゴリズム（Genetic Algorithm：GA）は， ランダムに生成された複数の状態の集合を個体群とす る．あらかじめ定義された適合度関数を個々の個体に適 用してランク付けを行い，ランクが上位の個体間で交 を行い，さらに突然変異を行う操作を繰り返すことに よって，次に移行すべき適切な状態を選択する． § 3 量子アニーリング 近年話題となっている量子アニーリングは SA の熱 揺らぎの代わりに量子揺らぎを導入して最適化を行う 方法である．門脇正史氏と西脇秀稔氏により考案され [Kadowaki 98]，2011 年に D-wave System 社により，
世界初の量子アニーリングマシン D-wave が発表された [Hauke 19]． 量子アニーリングでは温度の代わりに量子効果の強さ を徐々に低下させる．量子効果が強いときにはすべての 値の組合せの重ね合わせとなっているが，量子効果を弱 めていくと値の組合せが限定され収束に向かう． 後述する制約充足問題や組合せ最適化問題では膨大な パラメータの組合せを計算する必要がある．従来の解法 では，探索技法を用いてこれらの組合せを一つ一つ試す 必要があるが，量子アニーリングでは量子が 0 と 1 の間 の中間状態をもつことを利用し，パラメータの組合せを 1回で計算することが可能になる． 3･4 敵 対 探 索 囲碁や将棋やチェスのような対戦ゲームはプレーヤが 二人おり，交互に着手することで盤面状態が変化する． 各盤面状態を一つの節点で表現し，一手を打つことによ り盤面状態が変化することを木構造で表現できる（図 1）． この図は，A という状態のときに，オペレータ O1の手 を打つと B という状態になり，オペレータ O2の手を打 つと C という状態になる，ことを示している．状態 B においては相手の打つ手によって状態が D, E, F のいず れかになり，状態 C においては相手の打つ手によって状 態が G または H になる．さらに状態 D において再び自 分に手番が戻ってきたときに，自分の打つ手によって状 態が I か J か K になる． § 1 ミニマックス法 ゲームにおいて良い手を選ぶにはなるべく先まで先読 みを行い，その結果を利用して次の一手を選択する必要 がある．図 1 は 3 手先の I, J, K, …, S までの状況の評価 値を数値として示している．数値が大きければ自分に有 利であり，数値が小さければ相手が有利な状況である． 図 1 を使って次の手を選ぶには，3 手先から 1 手ずつ戻 りながら次の手の評価値を計算することになる． 例えば状態 D においては自分の手番であり，3 種類の 候補手により I, J, K に遷移するが，その中で評価が一番 図 1 ゲーム木
高い K を選択することになり，その結果，D の評価値 は K の評価値と同じ 5 となる．同様に E と F の評価値 は 6 と 7 になる．次にもう一手戻って，状態 B の評価 値を考える．B において相手が最善手を打つならば，D, E, Fのうちで（自分にとって）一番評価値が低い手を打 つから，B の評価値は D の評価値と同じ 5 となる． さらに一手戻って，状態 A では自分の手番であるか ら，B の評価値 5 と C の評価値 4 の大きいほうが選ばれ， 結局，次の一手は O1となる． このように，先読みしたゲーム木の末端の各状態の評 価値を用い，最大評価値（MAX）と最小評価値（MIN） を交互に選んで上位に伝搬することによって，次の手を 選択することができる．これをミニマックス法という． ゲームの戦略の中でミニマックス法は慎重な戦略である といえる． § 2 アルファベータ法 先読みの手数を大きくするとゲーム木は膨大になる． 膨大な状態数の場合に，ミニマックス法で次の手を選択 するには枝刈りによってむだな評価値計算を削除するこ とが必要となる．図 1 において F の評価値を計算する場 合に M の値が 7 と判明した段階で F の評価値は 7 以上 となることが確定し，D と E の評価値がそれぞれ 5 と 6だから F の値は B の値に採用されない．その結果，N の評価値は不要となる（ベータカット）． 同様に，G の評価が 4 とわかった段階で C の評価値 は 4 以下であることが確定し，B の評価値 5 より小さい ことが確定しているから，A の評価値計算に C の評価 値は採用されない．したがって，H の評価値は不要であ る（アルファカット）．アルファカットとベータカット によって，不要な評価値計算を削除する方法をアルファ ベータ法という．各節点が理想的な順番にソートされて いる場合は，アルファベータ法によってもとの節点数の 平方根の数まで探索数が減少する． § 3 モンテカルロ探索 囲碁のように分岐数が多く，評価関数の設定が難しい ようなゲームでは深い先読みをすることができず，ミニ マックス法による次の手を選択することも難しい．この ような場合には，相互にランダムに手を打ち合って最終 状態に至る（「プレイアウト」という）実行例を多数集め， 勝率の高い手を選択するモンテカルロ法の手法を用いる ことができる．1 回の探索で実行できるプレイアウトの 総数には上限があるため，まず以下の評価式（信頼上限 （Upper Confidence Bound））で可能な手（i）の評価を
行う． wi ＋ 2lnN ni ni この式で wiは i での勝利数，niは i でのプレイアウト 数，N はプレイアウトの総数である．すなわち，少ない プレイアウトで高い評価値が得られる手を有望な手とみ なし，多くのプレイアウトを割り当てる．プレイアウトの 総数がしきい値を超えたところで探索を 1 段階進める． 3･5 探 索 と ゲ ー ム 人工知能研究の初期からゲームは挑戦すべきターゲッ トとして人を惹きつけてきた．ゲームプログラムでは ゲーム木の探索において，枝刈りなどを行って，効率良 く探索を行うことが重要である．しかしながら，場面の 多様さはチェスで 10120，将棋で 10220，囲碁で 10360と 大きく異なっており，それに対応してこの三つのゲーム へは異なったアプローチがなされた． § 1 チェス サイモンが 1957 年に「チェスプログラムは 10 年以 内に人間のチャンピオンより強くなる」と宣言したよう に，古くから多くのチェスプログラムがつくられてきた． そのアプローチの大半はミニマックス法を中心とした探 索手法と，各局面の評価関数の関数の改良である．1966 年の Greenblatt program の rating は 1 640 であった が，1977 年のミネソタオープンで CHESS 4.5 は rating 2 271を達成し，1988 年の Deep Thought の rating は
2 745というように着実にチェスプログラムは進歩し てきた（rating は 2 000 を超えると超上級者レベル， 2 500を超えるとグランドマスターレベル，2 700 を超え るとスーパーグランドマスタークラスである）．しかし， Deep Thoughtはチャンピオンのカスパロフには 0 勝 2 敗という成績であり，まだチャンピオンの能力とは差 があった．その後，1997 年に Deep Blue が初めてカス パロフに勝利し，「人工知能が人間のチャンピオンを破っ た」として大きなインパクトを与えた [カスパロフ 17]． Deep Blueは並列コンピュータにより，14 手の先読み を行い，ミニマックス法により最適な手を選択する，と いうものであった．チェスは各場面での平均の分岐数が 35であり，14 手先読みをするには，3514＝4.1×1021の 盤面の評価を必要とする．それまでにもチェスを強くす るためにさまざまな知識処理技法が試みられてきたが， なかなかチャンピオンレベルに届かなかった．そのよう な状況で，結局はシンプルな探索技法がチャンピオンレ ベルになったことは「探索の復権」という意味もあった． § 2 将棋 将棋では保木邦仁氏が開発した Bonanza が，盤面の 評価関数を 6 万局の棋譜から機械学習で求める手法を 採用し，職人芸でつくっていた評価関数を上回ったこと から，その後の将棋プログラムの開発に大きな影響を与 えた．また，それまでのコンピュータ将棋では，ゲー ム木を削減するために選択的枝刈りを行っていたが， Bonanzaでは枝刈りをせずに全解の探索を行っている． 2013年の第 2 回電王戦ではプロ棋士 5 名と 5 種類のコ ンピュータプログラムが対戦し，プロが 1 勝 3 敗 1 分と いう成績であった．さらに 2014 年の第 3 回電王戦では プロ棋士が 1 勝 4 敗となり，コンピュータ将棋が名人ク
ラスになったことが示された． § 3 囲碁 囲碁においては，2006 年に開発された Crazy Stone は勝率の高い手に多くのプレイアウトを割り当てる「モ ンテカルロ探索」を採用して，第 1 回 UEC 杯コンピュー タ囲碁大会で優勝した． その後，モンテカルロ探索の効率化に関する研究が進 み，プロ棋士相手に 4 子のハンディ程度に棋力が向上し たものの，プロのレベルに達するにはまだ時間がかかる ものと予想された． し か し，2015 年 に 深 層 学 習 に よ る 囲 碁 シ ス テ ム AlphaGoがプロ棋士のファン・フィと対戦し 5 勝 0 敗 で勝利し，さらに 2016 年 3 月に世界チャンピオンのイ・ セドルに 4 勝 1 敗と勝利して，コンピュータ囲碁に大 きなインパクトを与えた．AlphaGo では深層学習とモ ンテカルロ探索と強化学習の技術が使われている．深層 ニューラルネットワークは盤面情報を入力すると，次の 手に選択する確率と，その場面からプレーヤが勝利する 確率を出力する．このニューラルネットワークは自分と の対戦をし，強化学習をすることで訓練されていく．そ れぞれの局面においてニューラルネットワークにガイド されたモンテカルロ木探索が行われ，各着手の確率が出 力される． その後，AlphaGo の新しいバージョンの AlphaGo Zeroは人間の棋譜を使わずに自己対戦で学習を行い， AlphaGoに 100 戦全勝するまでに進化した [Silver 17]．
4．
制約充足問題（CSP）
4･1 CSP と は制約充足問題（Constraint Satisfaction Problem：CSP） とは，変数集合 X＝{X1, X2, …, Xm}とそれぞれの変数 Xi が取り得る値の範囲 Diの集合 D＝{D1, D2, …, Dm}と変 数の取り得る値の制約 Cjの集合 C＝{C1, C2, …, Cn}が与 えられたとき，すべての制約条件を満足するように変数 に値を割り当てる問題である． CSPは，n クイーン問題，クロスワードパズル，グラフ 彩色問題のような単純な問題から，大規模なプランニン グやスケジューリング問題など多くの応用をもつ問題の クラスである． 例えば互いに隣接する三つの土地 A1, A2, A3を三色 （r, g, b）で塗り分ける CSP を考える．A1には b が使えず， A2には r が使えないものとする．これは以下のように定 式化することができる． 変数集合：{A1, A2, A3} 値域集合： D1＝{r, g}, D2＝{g, b}, D3＝{r, g, b} 制約集合： C12＝{（r, g），（r, b），（g, b）} C23＝{（g, r），（g, b），（b, r），（b, g）} C13＝{（r, g），（r, b），（g, r），（g, b）} それを充足するのは以下の三つの変数割当て（A1, A2, A3） である． （r, g, b），（r, b, g），（g, b, r） 4･2 CSP の 解 法 CSPの解法の代表的なものとして制約伝搬法（局所整 合アルゴリズム）と木構造探索法を紹介する． § 1 制約伝搬法による CSP の解法 CSPが与えられたとき，その局所的な制約条件から冗 長な値の組を削除することができる．局所的な制約条件 の代表的なものが節点整合，辺整合，路整合である． i．節点整合 変数 Xiが節点整合であるとは，Xiのとり得る値のす べてが Xiに関する制約を満たすことである．例えば，
X1に関して D1＝{a, b, c, d}，C12＝{（a, b），（b, c），（c, a）}，
C13＝{（a, c），（d, d）}とする．C12と C13を満たす X1の 値は {a} だけであるから，D1を削減して D1＝{a} とする と X1は節点整合となる． ii．辺整合 制約 Cijが辺整合であるとは，Xiのとり得る値のすべ てについて，Cijを満たす Xjの値が存在することである．
例えば，D1＝ {a, b, c, d}，D2＝ {a, b, c, d}，C12＝ {（a, b），
（b, c），（c, a）}とすると，X1＝ d のとき，X2に対応する 値がないから，D1＝{a, b, c, d} は辺整合ではない．D1＝ {a, b, c}とすることによって辺整合となる． iii．路整合 経路 XiXjXkが路整合であるとは，Diの任意の値 uと Dkの任意の値 v について，Dj中に Cij, Cjkを満たす 値が存在することである． これらの局所整合をとるためのアルゴリズムが開発さ れており，それらを利用して局所整合をとることで各変 数のとり得る値を絞り込むことができる．その結果，次 項で紹介する木構造探索の効率を高めることができる． § 2 木構造探索による CSP の解法 制約充足問題は木構造の深さ優先探索により解くこと ができる．例えば，図 2 はまず変数 A1に一つの値 1 を 割り当て，次に A2に 1 を割り当て，さらに A3に 1 を割 り当てて，制約を満たさない場合はバックトラックして， A2に 0 を割り当てるという深さ優先探索により下位を 求めていく様子が示されている．変数に値を割り当てな がら，制約条件をチェックし，制約条件の違反が見つか るとバックトラックが行われる． 深さ優先探索を効率的に行うため，探索を一段進める たびに変数に割り当てられた値のチェックを行い，将来む だな割当てをしないように枝の刈込みをする手法がある． 今までに値が割り当てられた任意の変数 Xiとまだ割
り当てられていない任意の変数 Xjについて，Xjが Xiに 辺整合するように Djを絞り込む操作を前方チェッキン グといい，それに加えてまだ値が割り当てられていない 任意の変数間の辺整合をチェックする方法をルックア ヘッドという． バックトラックをする際に，単に深さ優先の順序でも との変数割当ての位置に戻るのではなく，行き詰まりの 原因となった変数割当てを特定し，その変数割当てまで 一挙にバックトラックを行う方法の一つをルックバック という． 4･3 充足可能性問題（SAT） § 1 SAT とは 充足可能性問題（satisfiability problem：SAT）とは， 与えられた命題論理式中の命題変数に真（True）または 偽（False）を割り当てることによってその命題を真に できるか，という CSP の一つである． 以下の命題論理式を考える．
（A1 A2）（¬A1¬A2）（A2 A3）
A1＝真，A2＝偽，A3＝真と割り当てるとこの命題論理 式は真となるから，この論理式で表される SAT 問題の 解答は YES である． この命題論理式のように，節（リテラルを論理和（） で結合したもの）を論理積（）で結合した形を連言標 準形という．以下の SAT ソルバーの説明は問題が連言 標準形で与えられていることを前提としている． § 2 SAT ソルバー SAT問題を解決する SAT ソルバーの代表的な手法は DPLL（Davis-Putnuam-Logemann-Loveland）手法であ る．DPLLはCSPと同じように木の深さ優先探索である． 各変数に一つずつ真または偽の値を割り当てていき，充 足できない節が見つかればバックトラックが行われる． 節 Xi Xjにおいて，Xi＝偽という割当てが行われた とき，この節を充足するためには Xj＝真が確定する（単 位伝搬）．リテラルが一つだけからなる節があれば，そ のリテラル L に対して L＝真が確定し，L を含む他の節 も真となるので命題論理式から除去する．また，他の節 の中にある ¬L を消去する．また，命題論理式の中に L か ¬L の一方しか現れないようなリテラル L があれば， L（または ¬L）を含む節を除去する．命題論理式の中 で L と ¬L の両方が現れるリテラル L があるときは，L＝ 真の場合と L ＝偽の場合に分岐する．L ＝真の場合は， Lを含むすべての節を除去し，その他の節の中の ¬L を 消去する．逆に，L ＝偽の場合は，¬L を含むすべての 節を除去し，その他の節の中の L を消去する． このような操作を繰り返して命題論理式が空になった らもとの命題論理式は充足可能であったことになる． DPLLは深さ優先探索に単位伝搬を組み込むことに より探索空間を大きく減少させることができるが，さ らに矛盾からの節の学習を組み込んだ手続きを CDCL （Conflict Driven Clause Learning）という．CDCL では，
矛盾が発生したときにその原因を解析し，例えば Xi＝ 真，Xj＝真を割り付けたことが矛盾が生じた原因だとす ると，¬（Xi Xj）＝¬ Xi ¬ Xjを新しい節として論理式に 追加する． SAT ソルバーは CDCL によって飛躍的に性能を向上 させ，106以上の変数を含むような大規模な問題を解く ことが可能になっている．推論，制約充足，機械学習， 最適化，診断，設計，検査，認識，プランニングなどの AIの技術が SAT ソルバーの効率に影響を与え，また， 逆にこれらの AI の問題が高速 SAT ソルバーによって 解決されている [井上 06]．SAT 技術の進化については [番原 16] に詳細な解説がなされている． § 3 SAT ソルバーのコンテスト 1992年から SAT ソルバーの国際的なコンテストが開 催され，ベンチマーク問題に対して，正解数と正解を得 るまでの計算時間を競っている．解けない問題について は制限時間の 2 倍の時間をペナルティとして実行時間に 加える．SAT Competition 2018 では Main Track に 41 のソルバーが参加した．そのスコアの上位のもののソル バー名と解けた問題数を表 2 に示す [SAT 2018]．
5．
最 適 化
最適化は，人工知能分野において広く利用されている 重要な基盤技術の一つである．最適化問題は，ある制約 のもとで目的関数を最小化する問題であり，以下のよう 図 2 木の探索と CPS 表 2 SAT Competition 2018 の結果UNSAT Solver Name Verified 96 94 99 93 SAT Solved 135 134 125 133 125 99 MapleLCMDistChronoBT MapleLCM Scavelfix2 MapleCM cms55-main-all4fixed MapleCM ordUIP
に定式化される． minimize：f（x） （1） subject to：x ∈ S （2） ここで，x は決定変数，f（x）は目的関数，S は実行可 能解集合，x ∈ S は制約と呼ばれる．例えば，深層学習 やサポートベクタマシンなどの機械学習手法は，過去に 観測されたデータ（入力と出力の組）から適切な仮説を 学習するため，入力に対する出力値と予測結果の誤差を 測るための損失関数を目的関数として最小化する．損失 関数としては，判別問題やランキング問題で用いられる 0－1 損失，回帰問題で用いられる 2 乗損失などがある [金森 15]．また，3･3 節で述べたように，探索において も最適化技術は重要な役割を果たしている． 本章では，まず，最適化の基礎として，機械学習の分 野で基盤技術となっている制約なし連続最適化問題およ び制約付き連続最適化問題における最適性条件と代表的 な勾配法のアルゴリズムを紹介する＊1．次に，深層学習 などでよく用いられるオンライン最適化のための勾配法 を紹介する．最後に，勾配法が適用できないブラックボッ クス関数最適化に適用可能な直接探索法を紹介する．本 問題は，近年，機械学習手法のハイパーパラメータ最適 化に現れる問題として注目されている． 5･1 制約なし連続最適化問題の最適性条件 本節では，制約なし連続最適化問題 minimize：f（x） （3） の最適性の 1 次の必要条件，1 次の十分条件，2 次の十 分条件を紹介する． 1 次の必要条件：x＊∈ Rnで 1 回微分可能な関数 f： RnR1において，x＊が局所最適解であれば，∇f（x＊） ＝ 0 が成り立つ． 1 次の十分条件：関数 f：RnR1は x＊∈ Rnで 1 回微 分可能で，かつ凸関数であるとする．このとき 1 次 の必要条件が成立するならば，x＊は最適解である． 2 次の十分条件：x＊∈ Rnで 2 回微分可能な関数 f： RnR1において，1 次の必要条件を満足し，かつ ∇2（xf ＊）が正定値であれば，x＊は局所最適解である． 5･2 制約なし連続最適化のための勾配法 本節では，目的関数の勾配を用いて反復的に目的関数 値の改善を行う勾配法を紹介する． § 1 勾配法の一般的な手順 勾配法の一般的な手順を以下に示す． （1）初期点 x0を決め，k＝0 とする．その他，必要な 変数を初期化する． （2）停止条件を満たせば xkを出力して停止する． （3）探索方向 dkを決定する． （4）dk 方向でのステップ幅αkを求める． （5）xk＋1＝xk＋αkdkを求める． （6）k k＋1 として，ステップ 2 へ． ステップ（4）は直線探索と呼ばれる．直線探索の方 法としては，Armijo 条件に基づく直線探索などがある． § 2 勾配法の収束性と収束率 勾配法の収束の良さを表す性質として大域的収束性と 局所的収束性がある．大域的収束性とは，任意の初期点 から出発したとき，生成される点列が x＊に収束する性 質である．ただし，∥∇f（xk）∥0 が成り立つ場合も大 域的収束するという．局所的収束性とは，初期点を x＊ の十分近くに選べば x＊に収束する性質である． 勾配法の収束の速さを表す性質として 1 次収束，超 1 次収束，2 次収束があり，後者ほど収束が速いことを表す． 点列 xkが x＊に収束するとき，整数 k 0 がとれて ∥xk＋1－x＊∥ ck∥xk－x＊∥ γ （kk） （4） が成り立つとする．ある定数 ck∈（0, 1）がとれてγ＝ 1 のとき，点列 xkは x＊に 1 次収束するという．{ck}が 0 に収束する数列であり， γ＝1 のとき，点列 xkは x＊に超 1次収束するという．ある定数 ck∈（0, 1）がとれてγ＝ 2のとき，点列 xkは x＊に 2 次収束するという． § 3 代表的な勾配法 代表的な制約なし連続最適化のための勾配法として は，最急降下法，共役勾配法，ニュートン法，準ニュー トン法，信頼領域法などがある．以下では，最急降下法， ニュートン法，準ニュートン法を紹介する． i．最急降下法 最急降下法は，k 反復目における探索方向として，f（xk） の 1 次モデルを局所的に最小にする方向 dk＝－∇（xf k） を用いる．最急降下法は，ある仮定のもとで大域的に 1 次収束する． ii．ニュートン法 ニュートン法は，k 反復目における探索方向として， f （xk）の 2 次モデル f （xk＋d）≈ f（xk）＋ f（xk）Td＋ dT 2（x）df 1 2 を最小化する方向 d＝－∇2（xf k）－1∇f（xk） （5） を用いる．式（5）はニュートン方向と呼ばれる．ヘッ セ 行列∇2（xf k） が 正定値ならば，∇f（xk）Td＜ 0 とな るので，ニュートン方向は目的関数の降下方向になる． ニュートン法は，ある仮定のもとで局所的に 2 次収束す る．しかし，一般に，ヘッセ行列が正定値である保証が ない． ＊1 証明やアルゴリズムの詳細は文献 [穴井 13, 金森 16, Luenberger 08, 矢部 06] などを参照されたい．
iii．準ニュートン法 準ニュートン法は，k 反復目における探索方向として， ∇2f（xk）を適当な正定値対称行列 Bkで近似した 2 次モ デル Q（d）＝f（xk）＋ f（xk）Td＋ dTBkd 1 2 を最小化する方向 d＝－Bk－1∇f（xk）を用いる．∇2（xf k） の情報を Bkに取り込むためには，セカント条件 Bk＋1sk＝ ykを満たす必要がある．ここで，sk＝xk＋1－xk，yk＝ ∇（xf k＋1）－∇（xf k）である．これは Bk＋1が sk 方向で ∇2（xf k＋1）を近似することを課す条件である．セカント 条件を満たす Bkの更新式として以下の BFGS 公式が広 く用いられている． Bk＋1＝Bk－ ． Bks（Bk ksk）T ＋ ykyTk sT kBksk sTkyk （6） 準ニュートン法は，ある仮定のもとで局所的に超 1 次収 束する． 5･3 制約付き連続最適化問題の最適性条件 本節では，制約付き連続最適化問題 minimize：f（x）， （7）
subject to：h（x）＝0 （i＝1, …, m）， i （8） g（x） 0 （ j＝1, …, r） j （9） の 1 次の必要条件，1 次の十分条件，2 次の十分条件を 紹介する． 1 次の必要条件：x＊が局所最適解であり，スレイター の制約想定＊2，または，x＊において 1 次独立制約想定 （LICQ）＊3が成り立つとき，ラグランジュ関数 L（x, λ, μ）＝ f（x）＋ m i＝1 λih（x）i r j＝1 μjg（x）j ＋ について，式（11）～（12）を満たすベクトルλ＊∈ Rm と μ＊∈ Rrが存在する． ∇xL（x＊, λ＊, μ＊）＝∇ λL（x＊, λ＊, μ＊）＝ 0， （10） ∇μL（x＊, λ＊, μ＊） 0, μ＊ 0， （11） μ＊ jg（xj ＊）＝0 （j＝1, …, r）． （12） 式（12）を相補性条件と呼ぶ．1 次の必要条件は KKT 条件（Karush-Kuhn-Tucker 条件）とも呼ばれ，KKT 条件を満たす（x＊, λ＊, μ＊）は KKT 点と呼ばれる． 1 次の十分条件：f と gj（ j＝1, …, r）は凸関数であり， hi （i＝1, …, m）は 1 次関数であるとする．そのとき， （x＊, λ＊, μ＊）が KKT 点であれば，x＊は最適解である． 2 次の十分条件：（x＊, λ＊, μ＊）を KKT 点とし，狭義の 相補性が成り立つと仮定する．狭義の相補性とは， 式（12），かつすべての j に対してμ＊j－g（xj ＊）＞ 0 が成り立つことである．さらに x＊において LICQ が成り立つとする．そのとき，0 でない任意のベク トル d∈V（x＊）＝{d ∈ Rn｜∇h i （x＊）Td＝0（i＝1, …, m），∇g（xj ＊）Td＝0（ j∈A（x＊））}に対して， dT∇2 xL（x＊, λ＊, μ＊）d ＞ 0 が成り立てば，x＊は局所最適解である． 5･4 制約付き連続最適化のための勾配法 代表的な制約付き連続最適化のための反復法として， 内部ペナルティ関数法，外部ペナルティ関数法，乗数法， 逐次 2 次計画法などがある．ここでは，最も有力な手法 の一つである逐次 2 次計画法を紹介する． i．逐次 2 次計画法 逐次 2 次計画法は，各反復において最適性条件と等価 な 2 次計画問題を逐次解くことで原問題の最適解を求め る．手順を以下に示す． （1）解 x0と n 次正定値対称行列 B0を初期化し，k＝0 とする． （2）2 次計画部分問題 minimize： f（x ）Td dTB k k ＋ d， 1 2 （13） subject to：h（xi k）＋∇h（xi k）Td＝ 0， （14） g（xj k）＋∇g（xj k）Td 0 （15） を解いて，d とラグランジュ乗数ベクトルλk＋1，μk＋1 を求める．ここで，i＝1, …, m，j＝1, …, r である． （3）｜d｜が十分に 0 に近ければ xkを出力して終了する． （4）f（x）にペナルティ関数を足したメリット関数を 用いた直線探索によってステップ幅αkを決定し， xk＋1＝xk＋αkdとする． （5）式（6）の ykを式（16），（17）の ˆykで置き換えた パウエルの修正 BFGS 公式に従って Bk＋1を求める． ˆyk＝ yk, sTkyk≥γsTkBksk, βkyk＋（1－βk）Bksk, otherwise, （16） βk＝ ． （1－γ）sTk sT k Bksk sT kBksk－ yk （17） ここで，γ（0 ＜γ＜ 1）はユーザパラメータである． （6）k＝k＋1 としてステップ（2）へ． ＊2 h（i＝1, …, m）が 1 次関数，gi （ j＝1, …, r）が凸関数であり，i h（xi 0）＝0（i＝1, …, m）かつ g（xj 0）＜ 0（ j＝1, …, r）となる点 x0が存在することである． ＊3 実行可能解 x において，∇h（x）i （i＝1, …, m）と∇g（x）j （ j∈ A（x））が 1 次独立であることである．A（x）＝{ j｜g（x）＝ 0} は，j 点 x における有効集合と呼ばれる．
5･5 オンライン最適化のための勾配法 機械学習，深層学習などでしばしば現れる目的関数 f （x）＝ n fi （x） i＝1 （18） をオンラインで最適化するための勾配法として，最急降 下法を拡張した確率的勾配降下法 [海野 15] と，その改 良版である AdaGrad [Duchi 11]，RMSProp [Tieleman 12]，Adam [Kingma 14] などがある．以下では，確率 的勾配降下法と Adam を紹介する． § 1 確率的勾配降下法 確率的勾配降下法は，目的関数 f （x）＝ n fi （x） i＝1 が与えられたとき，勾配∇（x）をf ∇f（x）で近似して最i 急降下法の反復を繰り返す手法である．これにより，1 反復の計算量を小さくすることができ，毎反復厳密に ∇（x）を計算する場合よりも早く良好な解を得ることがf できることが多い．以下に手順を示す． （1）解 x0を初期化し，k＝0 とする． （2）停止条件を満たせば xkを出力して終了する． （3）fiをランダムにシャッフルする． （4）i＝1, …, n について以下を実行する． a xk＋1＝ xk＋η∇f（xi k）． b k k＋1． （5）ステップ（2）へ． 上記のように，f（x）をランダムにシャッフルするこi とにより，確率的に局所最適解にはまりにくくなること が知られる．∇f（x）を複数の∇f（x）を用いて近似するi 方法をミニバッチ法と呼ぶ． § 2 Adam
Adam（Adaptive Moment Estimation）は，確率的 勾配降下法の収束の遅さを改善するために提案された手 法である．Adam では，式（19）の勾配の指数移動平均 mk＋1と，式（20）の勾配の 2 乗の指数移動平均 vk＋1に 基づいて修正された勾配を用いて式（21）のように xk を更新する． mk＋1＝β1mk＋（1－β1）∇（xf k）， （19） vk＋1＝β2vk＋（1－β2（）∇（xf k））2， （20） xk＋1＝xk－α ． mk＋1（1－/ β1k＋1） vk＋1（1－/ β2k＋1）＋ε （21） ここで，v＝[v1, …, vn]T，w＝[w1, …, wn]Tとしたとき， v2＝[v2 1, …, v2n]T，√v＝[√v1, …, √vn]T，v/w＝[v1/ w1, …, vn/wn]Tである．α，β1，β2，εはユーザパラメータであり， それぞれ推奨値が与えられている [Kingma 14]． 5･6 ブラックボックス関数最適化のための直接探索法 ブラックボックス関数最適化は，関数形が陽に与えら れないブラックボックス関数 f（x）の最小値を求める問 題である．f（x）に関する解析的な仮定や勾配は利用で きず，f（x）の値のみが利用できる．f（x）の値のみを 用いる最適化手法は直接探索法と呼ばれる．代表的な直 接探索法としては，Nelder-Mead 法 [Nelder 65]，実数 値遺伝アルゴリズム [秋本 09, 小野 00]，差分進化 [Storn 97]，粒子群最適化 [Kennedy 95]，CMA-ES [Hansen 06]， 自然進化戦略 [Fukushima 11, Glasmachers 10, Wierstra 08]，ベイズ的最適化 [Bergstra 11, Contal 14, Hutter 11, Shahriari 15, Snoek 12]などがある．以下では，自然進 化戦略とベイズ的最適化を紹介する．
§ 1 自然進化戦略
自然進化戦略（Natural Evolution Strategies：NESs） は，有力な進化計算手法の一つである．NESs は，勾配 が計算できない目的関数 f（x）を直接最適化する代わり に，確率分布 p（x｜）を考え，p（x｜）に従って生成さ れる解 x の期待評価値 J（ ）＝ f（x）p（x｜ ）dxθ θ を自然勾配法 [Amari 98] により最適化する．更新式は 以下のとおりである． k＋1＝k－ηF－1（ k）∇θJ（k） （22） ここで，F（）はフィッシャー情報行列である． 確率分布 p（x｜）として平均 m，分散共分散行列 C の多変量正規分布 p（x｜ ＝（m, C））を用いると，式（22） は以下のように書き換えられる． mk＋1＝mk－η Ex[ f（x k] ≈ mk－η k λ （xf i） （xi－m ） ） （x－m ） i＝1 λ （23） mk＋1＝mk－ηEx[ f（x k] ≈ mk－η k λ （xf i） （xi－m ） ） （x－m ） i＝1 λ （24） Ck＋1＝Ck－ηEx[f（x）（（x－m ）k（x－m ）kT－Ck）] （xi－m ） （（xi－m ）k kT－Ck） ≈ mk－η λ （xf i） i＝1 λ （25） Ck＋1＝Ck－ηEx[f（x）（（x－m ）k（x－m ）kT－Ck）] （xi－m ） （（xi－m ）k kT－Ck） ≈ mk－η λ （xf i） i＝1 λ （26） ここで，λは式（23），（25）右辺の期待値をサンプル平 均で近似する際のサンプル数であり，ユーザパラメータ である．NESs では，f（xi）の単調増加変換に対してロ バストにするため，－f（xi）/λを正規化された重み wiで 置き換える． mk＋1＝mk＋ w（xi i－m ）k λ i＝1 η （27） Ck＋1＝Ck＋ w（ xi（ i－m ）k（xi－m ）kT－Ck） λ i＝1 η （28） この工夫は fitness shaping [Wierstra 08] と呼ばれる．さ らに，C の正定値性を保証するための exponential update
[Glasmachers 10]，収束性を向上させるための distance weight [Fukushima 11]，探索状況に応じた学習率切替 え [Fukushima 11] などの工夫が提案されている． § 2 ベイズ的最適化 ベイズ的最適化は，解の評価に時間がかかるブラック ボックス関数最適化において，ランダムサーチやグリッ ドサーチよりも少数のサンプルで良質な解が得られると して，近年注目を集めている手法である． ベイズ的最適化は，計算コストが高い目的関数を直 接最適化する代わりに，計算コストが低い確率的回帰モ デルと獲得関数（acquisition function）を用いて，有 望解の生成と評価，および有望解に基づくモデルの更 新を繰り返すことにより解の探索を行う．確率的回帰モ デル M は，これまでサンプルした解およびその観測さ れた目的関数値の履歴 Hn＝{（xk, yk）}nk＝1から，未観測 の解 x の目的関数値 f（x）の予測値とその不確かさを返 す．確率回帰モデル M としては，ガウス過程（Gaussian process）[Snoek 12] がよく用いられる．その他，Tree Parzen Estimator（TPE）[Bergstra 11]， ラ ン ダ ム フォレスト [Hutter 11] を利用する手法が提案されてい る．獲得関数 a（x; M）は，確率的回帰モデルから得ら れる未観測の解 x の予測値と不確かさの情報から，探 索（exploration）と活用（exploitation）のトレードオ フを考慮して，解 x の有望度を返す関数である．獲得関 数としては，Expected Improvement（EI）[Snoek 12]， Upper Confidence Bound（UCB）[Snoek 12]，Mutual Information（MI）[Contal 14] などが提案されている． EIは評価値の改善量の期待値が最も高い解を最も有望 とする．UCB は評価値の信頼区間を考慮して活用と探 索のトレードオフをとる解を最も有望とする．MI は， 相互情報量に基づく方法であり，EI，UCB よりも優れ た性能を示すことが知られる． ベイズ的最適化の流れを以下に示す． （1）履歴 Hn，確率的回帰モデル M を初期化し，n＝1 とする． （2）獲得関数 a（x; M）を最大化する解を有望解 xn＋1 とする：xn＋1＝argmaxx a（x; M） （3）有望解 xn＋1を評価する：yn＋1＝ f（xn＋1） （4）履歴 Hn＋1＝Hn∪{（xn＋1, yn＋1）}を用いてモデル M を更新する． （5） 停 止 条 件 を 満 た せ ば 終 了 し， さ も な け れ ば n n＋1 としてステップ 2 へ．
6．お
わ り に
人工知能の古くからの研究課題であり最も基本的な問 題解決，探索，制約充足問題，最適化について，その基 本的な知識の概説と最近の話題や研究動向について紹介 した．ゲームの項目で紹介したように，従来は探索技術 を使って解決を目指してきた問題が，ニューラルネット ワークや機械学習と探索技術を組み合わせて問題を図る など，基本技術が他の技術と融合して発展していく事例 が見られた．また，SAT ソルバーのように基本問題の解 法が着実に進化していく様子が見られた． 今後もこれらの基本技術を用いないと解決できない実 問題がある限り，これらの課題の重要性は変わらず，技 術は大きく進化していくと思われる． 謝 辞 本稿を執筆するにあたり，助言をくださった井上克巳 国立情報学研究所教授，寺野隆雄東京工業大学名誉教授， 小長谷明彦東京工業大学教授に感謝いたします．◇ 参 考 文 献 ◇
[秋本 09] 秋本洋平，永田裕一，佐久間淳，小野 功，小林重信：適 応的実数値交 AREX の提案と評価，人工知能学会誌，Vol. 24, No. 6, pp. 446-458（2009）[Amari 98] Amari, S.: Natural gradient works efficiently in learning, Neural Computation, Vol. 10, No. 2, pp. 251-276 （1998）
[穴井 13] 穴井宏和：数理最適化の実践ガイド，講談社（2013） [番原 16] 番原睦則，鍋島英知：SAT 技術の進化，情報処理，Vol.
57, No. 8, pp. 704-709（2016）
[Bergstra 11] Bergstra, J. S., Bardenet, R., Bengio, Y. and Kegl, B.: Algorithms for hyper-parameter optimization, Advances in
Neural Information Processing Systems 24（NIPS 2011）, pp.
2546-2554（2011）
[Contal 14] Contal, E., Perchet, V. and Vayatis, N.: Gaussian process optimization with mutual information, Proc. the 31st
Int. Conf. on Machine Learning（ICML）, pp. 253-261（2014）
[Duchi 11] Duchi, J., Hazan, E. and Singer, Y.: Adaptive subgradient methods for online learning and stochastic optimization, J. Machine Learning Research, 12:2121-2159 （2011）
[Feigenbaum 63] Edward A.: Feigenbaum and Julian Feldman :
Computers and Thought, McCraw-Hill（1963）
[Ferrucci 13] Ferrucci, D., Levas, A., Bagchi, S., Gondek, D. and Watson, M. E. T.: Beyond jeopardy!, Artificial Intelligence, pp. 93-105（2013）
[Fukushima 11] Fukushima, N., Nagata, Y., Kobayashi, S. and Ono, I.: Proposal of distance-weighted exponential natural evolution strategies, Proc. IEEE Congress on Evolutionary
Computing（CEC）, pp. 164-171（2011）
[太原 88] 太原育夫：人工知能の基礎知識，近代科学社（1988） [Glasmachers 10] Glasmachers, T., Schaul, T. , Sun, Y., Wierstra,
D. and Schmidhuber, J.: Exponential natural evolution strategies, Proc. Genetic and Evolutionary Computation
Conference（GECCO）, pp. 393-400（2010）
[Hansen 06] Hansen, N.: The CMA Evolution Strategy:
A Comparing Review, Towards a New Evolutionary
Computation, pp. 75-102（2006）
[Hauke19] Hauke, P., Katzgraber, H. G., Lechner, W., Nishimori, H. and William, D.: Oliver, Perspectives of Quantum Annealing:
Methods and Implementations, arXiv:1903.06559[quantph]
（2019）
[Hutter 11] Hutter, f., Hoos, H. H. and Leyton-Brown, K.: Sequential model-based optimization for general algorithm configuration, Proc. 5th Learning and Intelligent Optimization （LION5）, pp. 507-523（2011）
[井上 06] 井上克巳：SAT と AI，情報処理，Vol. 57, No. 8, pp. 720-723（2016）
[石塚 96] 石塚 満：知識の表現と高速推論，丸善（1996） [Kadowaki 98] Kadowaki, T. and Nishimori, H.: Phys. Rev. E, Vol.
58, No. 5, pp. 5355-5363（1998） [金森 15] 金森敬文：統計的学習理論，講談社（2015） [金森 16] 金森敬文，鈴木大慈，竹内一郎，佐藤一誠：機械学習の ための連続最適化，講談社（2016） [カスパロフ 17] ガルリ・カスパロフ 著，羽生善治 解説，染田屋茂 訳：人工知能の思考を読む（Deep Thinking），日経 BP 社（2017） [Kennedy 95] Kennedy, J. and Eberhart, R. : Particle swarm
optimization, Proc. IEEE Int. Conf. on Neural Networks, pp. 1942-1948（1995）
[Kingma 14] Kingma, D. P. and Ba, J.: Adam: A Method for
Stochastic Optimization, arXiv:1412.6980[cs.LG]（2014）
[Luenberger 08] Luenberger, D. G. and Ye, Y.: Linear and
Nonlinear Programming, 3rd Edition, Springer（2008）
[マコーダック 79] マコーダック， P. 著，黒川利明 訳：コンピュー タは考える（Machines Who Think），培風館（1975）
[Nelder 65] Nelder, J. A. and Mead, R.: A simplex method for function minimization, The Computer Journal, Vol. 7, Issue 4, pp. 308-313（1965）
[小野 00] 小野 功，山村雅幸，喜多 一：実数値 GA とその応用，人 工知能学会誌，Vol. 15, No. 2, pp. 259-266（2000）
[SAT 2018] SAT Competition 2018, http://sat2018. forsyte.tuwien.ac.at/
[Shahriari 15] Shahriari, B., Swersky, K., Wang, Z., Adams, R. P. and Freitas, N.: Taking the human out of the loop: A review of Bayesian optimization, Proc. IEEE, Vol. 104, Issue 1, pp. 148-175（2015）
[Silver 17] Silver, D., Schrittwieser, J., Simonyam, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Lai, M., Bolton, A., Chen, Y., Lillicrap, T., Sifre, L., van den Driessche, G., Graepel, T. and Hassabis, D.: Mastering the game of go without human knowledge, Nature, Vol. 550, pp. 354-359（2017）
[Snoek 12] Snoek, J., Larochelle, H. and Adams, R. P.: Practical Bayesian optimization of machine learning algorithms,
Advances in Neural Information Processing Systems 25（NIPS
2012）, pp. 2951-2959（2012）
[Storn 97] Storn, R. and Price, K. : Differential evolution ? A simple and efficient heuristic for global optimization over continuous spaces, J. Global Optimization, Vol. 11, Issue 4, pp. 341-359（1997）
[寺野 18] 寺野隆雄：第三次人工知能ブームを超えて─鉄鋼業に おけるシステム化を考える─，ふぇらむ，Vol. 23, No. 12, pp. 11-20（2018）
[Tieleman 12] Tieleman, T. and Hinton, G.: Lecture 6.5 - RMSProp, COURSERA: Neural Networks for Machine Learning, Technical report（2012）
[海野 15] 海野裕也，岡野原大輔，得居誠也，徳永拓之：オンライ ン機械学習，講談社（2015）
[Wierstra 08] Wierstra, D., Schaul, T., Peters, J. and Schmidhuber, J.: Natural evolution strategies, Proc. 2008
IEEE Congress on Evolutionary Computation, pp. 3381-3387
（2008）
[Winston 77] Winston, H., Patric: Artificial Intelligence, Addison-Wesley（1977） [矢部 06] 矢部 博：工学基礎最適化とその応用，数理工学社（2006） 2019年 4 月 1 日 受理
