ヒューリスティックな解法
～アニーリングマシンを更に深く知ろう～
概要
アニーリングマシンが行う計算は、メタヒューリスティックと呼ばれる分類に属します。これは、例えば、たくさんの組合せの中から効率よく良い答えを得たいという場合に有効なアプローチの1つです。組合せの候補が膨大すぎる場合には、答えの正確さを優先すると計算時間がかかりすぎることは学問上明らかになっているため、一番正しい解でなくとも、それなりに良い解を高速に見つけるためのアプローチが役に立ちます。一般的には、計算機では唯一の正解（厳密解）を導き出す手順やアルゴリズムを採用することが多いですが、それとは異なるヒューリスティックの特徴と、この観点におけるアニーリングマシンの意義について学習しましょう。
ヒューリスティックとメタヒューリスティック
ヒューリスティックとは発見的方法と訳され、ある問題に対して経験、発見を通して解を見つける、あるいは改善する方法を言います。中でも、多くの問題に適用できる汎用性を持つヒューリスティックのことをメタヒューリスティックと呼びます。アニーリングマシンはイジングモデルに定式化された色々な問題を解くことができるため、メタヒューリスティックであると言えます。ですが、これ以降は従来のコンピューティングと比較した性質についてお話しするため、ひとまとめにしてヒューリスティックと呼ぶことにします。
ヒューリスティックで広い世界の中からある程度高い山を見つける
ヒューリスティックは、ある程度よい解が得られるものの、最も良い解が得られるとは限りません。私達は学校の数学でたった一つの正解を見つけるための理論を学習してきました。ですから、ヒューリスティックという概念を受け入れることに抵抗感を感じる人もいるかもしれません。解の候補が連なって山々を形成していると想像してみてください。ただ一つしかないはずの正解を「厳密解」といい、厳密解は最も高い山の頂上です。学校の数学は最も高い頂上をめざす取り組みです。最も高い頂上を見つけるには山々を登って確かめるしかないのですが、ヒューリスティックでは広い世界の山々を俯瞰的に見ることで、高速にそこそこ高い頂上を探すことができます。最適化問題に置き換えて考えると、最短経路まで特定するには時間がかかるけれどごく短時間で大幅に経路を短くできると大きなメリットが得られるという状況においては、ヒューリスティックを適用することができます。
色々なヒューリスティック
シミュレーティドアニーリング法
その名が示す通り、CMOSアニーリングマシンの元となっているのがこのシミュレーティドアニーリング(SA)で、自然界における熱力学の知見を応用した方法でKirkpatrickにより1983年に提案されたものです。自然界に存在する物質の原子が、高温の状態ではエネルギーが高くランダムに散らばっている状態ですが徐々に温度を下げると粒子のエネルギーが低くなり、並びが整列された状態に到達します。アニーリングの日本語は焼き鈍しで、刀や鋳物を高温から冷ましていく過程で不純物のない丈夫な製品とする製造工程にもこの自然現象が応用されています。シミュレーティドアニーリングでは温度はパラメータとして探索に貢献します。
アントコロニー法
アリが巣から餌場への最短経路を探索することができる自然現象を参考にした最適化手法で、Marco Dorigoにより1992年に提案されました。アリは餌を見つけると道標フェロモンを散布します。そのフェロモンを手掛かりに他のアリが餌場へたどり着き、更に道標フェロモンを散布するため、次第に道標フェロモンの高濃度によって示される餌場までの最短経路が出来上がります。この現象をモデリングし、巡回セールスマン問題(TSP)などに応用する研究が盛んに進められてきました。
遺伝的アルゴリズム
遺伝的アルゴリズムは生物の選択・交叉・突然変異からなる進化過程を模倣したアルゴリズムで、1975年にJ.H.Hollandによって提案されました。ある個体群に対してアルゴリズムを適用することで良好な個体群を得るようにし、これが解となります。ナップザック問題やTSPなど様々に適用されています。
このような自然界が持つプロセスを情報処理に応用したものをナチュラルコンピューティングといいます。ナチュラルコンピューティングとヒューリスティックには重なるカテゴリが存在しており、上記の3つはいずれもそのカテゴリにあるといえます。
ヒューリスティック専用の計算機が登場したわけ
シミュレーティドアニーリングや遺伝的アルゴリズムは研究の歴史も長く、物流、金融、製造等々、幅広く活用されています。
アニーリングマシンはシミュレーティドアニーリングを応用した組合せ最適化専用ハードウェアです。では、既に使われているシミュレーティドアニーリングというヒューリスティックをなぜ今あらためてアニーリングマシンという手法で実現することになったのでしょうか。その背景にある要因の1つは、シミュレーティドアニーリングの重要性が高まり、一方で問題の規模が大きくなったため、ヒューリスティックを使っても性能要求を満たせないことが増えてきたということが挙げられます。そこで、ハードや専用のアルゴリズムを使って高速化できるアニーリングマシンがにわかに注目され始めたのです。また、実際に専用ハードウェアが誕生し始めたことがまさにもう1つの背景であるといえるでしょう。門脇・西森両氏の1998年の論文 ”Quantum annealing in the transverse Ising model”（PHYSICAL REVIEW）において量子ビットを2値スピンとしてイジングモデルの基底状態を導く量子アニーリングが提唱されたことで、まずはD-Waveから量子アニーリングマシンが発表され、半導体スピンでその理論を応用したCMOSアニーリングマシン、またその他の研究機関からも専用ハードウェアが相次いで発表されました。問題をイジングモデルに置き換えてアニーリング処理を行うという新しい理論が、ハードウェアとしての実現を可能にしたのです。イジングモデルのアニーリングでは、問題を二値変数に置き換える前処理の難しさはあるものの、その変換さえできれば、専用ハードウェアによる高速処理が可能となります。
また、イジングモデルの基底状態探索によるアニーリング専用ハードウェアの研究開発が進んだことで、今度はそれらをアルゴリズム化する研究開発が進み、それらのアルゴリズムを実務に適用する段階にまで進捗しました。ノイマン型コンピュータの発展がアルゴリズムの研究を促し、シミュレーティドアニーリングが成熟するとアニーリング専用ハードウェアが研究され、アニーリング専用ハードウェアの研究開発に触発されて新たなアルゴリズムが生み出される…これまでの経緯を振り返ると、ハードウェアとアルゴリズムは相互作用しあうことによって進化してきたといえ、今後もこの相互作用が技術の進歩を促すと考えられます。
アニーリングマシンは従来技術と共存し、要件に応じて選択しあるいは組み合わせて使っていくもの
ここまで、アニーリング専用ハードウェアはシミュレーティドアニーリングに基いた技術であり、厳密解を求めるアルゴリズムやソフトウェアとは異なる目的を持ち、異なる処理を行う技術であることを説明してきました。また、ハードウェアとして今世の中に広く浸透しているノイマン型コンピュータ上が汎用型コンピュータと呼ばれていることからわかるように、アニーリングマシンがノイマン型コンピュータに取って代わるものでないことも明確です。実際に課題を解決するにあたって、どのようなハードウェアやアルゴリズムを適用するべきかは、課題解決に必要なのは厳密解なのか、それともある程度よい解であれば足りるのか、その処理対象となるパラメータの規模と処理時間はどの程度を求めるのか、等々の要件に応じて適切に選択することが重要であり、その選択あるいは組合せ、それらを検証することの積み重ねによって価値を生み出してくのです。
まとめ
- ヒューリスティックは発見的手法と訳され、経験、発見を通じて問題の解を見つける、あるいは改善する手法である。ヒューリスティックとナチュラルコンピューティングには重なるカテゴリが存在し、アニーリングマシンはナチュラルコンピューティングとヒューリスティックの両方に属する。
- ヒューリスティックは厳密解を見つける方法ではなく、そこそこにいい解を見つけてくる。経路探索の問題でいえば、最も短い経路を求めることはできないが、最短経路に近付く良い経路を効率よく求めることができるため、それによる社会的価値が期待できる。
- ヒューリスティックなアルゴリズムは広く実用されているが、更に規模の大きな問題を解く要求が高まり、また、イジングモデルを用いた量子アニーリングの理論が発表されたことで、専用ハードウェアであるアニーリングマシンの開発が加速した。アルゴリズムとハードウェアの研究開発は相互作用しあいながら発展を続けている。
参考文献
メタヒューリスティクスとナチュラルコンピューティング（古川正志 他共著）コロナ社
