JP7137064B2 - 最適化装置及び最適化装置の制御方法 - Google Patents

Description

本発明は、最適化装置及び最適化装置の制御方法に関する。

ノイマン型コンピュータが不得意とする多変数の最適化問題を解く方法として、イジング型のエネルギー関数を用いた最適化装置（イジングマシンまたはボルツマンマシンと呼ばれる場合もある）がある。最適化装置は、計算対象の問題を、磁性体のスピンの振る舞いを表すモデルであるイジングモデルに置き換えて計算する。

最適化装置は、たとえば、ニューラルネットワークを用いてモデル化することもできる。その場合、イジングモデルに含まれる複数のスピンに対応した複数のビットのそれぞれが、他のビットの値と、他のビットと自身のビットとの相互作用の大きさを示す重み値（結合係数とも呼ばれる）とに応じて０または１を出力するニューロンとして機能する。最適化装置は、たとえば、シミュレーテッド・アニーリングなどの確率的探索法により、上記のようなエネルギー関数（コスト関数、目的関数とも呼ばれる）の値（以下エネルギーという）の最小値が得られる状態（各ビットの値の組み合わせ）を、解として求める。

従来、デジタル回路を用いてシミュレーテッド・アニーリングを行うことでエネルギーが最小となる状態を計算する最適化装置がある（たとえば、特許文献１参照）。従来の最適化装置は、一度に１つのビットの値だけ変化するとしてエネルギー変化を計算し、そのエネルギー変化に対して温度に対応するノイズ値を加えた値に応じてビットの変化を許容するか否かを決定する。エネルギーが増加するビットの値の変化も所定の確率で許容され、温度が低くなるにつれてその確率は低くなる。

ところで、最適化問題には、全ビットの中で値が１になるビットの数をｋ（＞１）個とする制約（ｋ－ｈｏｔ制約）をもつものがある。たとえば、多くのパーティショニング問題（グラフ分割問題など、与えられたＮ個の選択肢から最適なｋ個を選ぶ、という問題）、交通量最適化問題などは、ｋ－ｈｏｔ制約をもつ。

特開２０１８－０４１３５１号公報 特開２０１６－１０３２８２号公報 特開平１０－２４７１８６号公報 特開平８－５０５７２号公報

上記のように、従来の最適化装置では一度に変化するビットの数は１つである。つまり、従来の最適化装置は、ハミング距離＝１の状態遷移を繰り返しながらエネルギーが最小となる基底状態の探索を行う。そのため、従来の最適化装置では、ｋ－ｈｏｔ制約を満たさない状態への遷移も発生し、遷移が起こりうる状態の数（探索空間）がｋ－ｈｏｔ制約を満たす状態の数よりも大きい。また、ｋ－ｈｏｔ制約項のために生じるエネルギー障壁のために状態遷移に時間がかかる。以上のことから、従来の最適化装置では、ｋ－ｈｏｔ制約をもつ最適化問題の計算（基底状態の探索）に時間がかかるという問題がある。

１つの側面では、本発明は、ｋ－ｈｏｔ制約をもつ最適化問題の計算時間を短縮可能な最適化装置及び最適化装置の制御方法を提供することを目的とする。

１つの実施態様では、計算対象の問題を変換したイジングモデルに含まれるＮ個（Ｎ＞２）のスピンに対応するＮ個のビットのうち、値が１であるｋ個（ｋ＞１）の第１のビットの何れかについての第１のローカルフィールド値と、生成した第１の乱数に基づいて選択した値が０である第２のビットについての第２のローカルフィールド値と、第１の記憶部に保持される前記ｋ個の第１のビットの何れかと前記第２のビットとの間の相互作用の大きさを示す第１の重み値とに基づいて、前記ｋ個の第１のビットの何れかの値と前記第２のビットの値とがそれぞれ変化することによる前記イジングモデルの第１のエネルギー変化をそれぞれ算出するｋ個の第１の算出回路と、前記Ｎ個のビットのうち、値が０である（Ｎ－ｋ）個の第３のビットの何れかについての第３のローカルフィールド値と、生成した第２の乱数に基づいて選択した値が１である第４のビットについての第４のローカルフィールド値と、第２の記憶部に保持される前記（Ｎ－ｋ）個の第３のビットと前記第４のビットとの間の相互作用の大きさを示す第２の重み値とに基づいて、前記（Ｎ－ｋ）個の第３のビットの何れかの値と前記第４のビットの値とがそれぞれ変化することによる前記イジングモデルの第２のエネルギー変化をそれぞれ算出する（Ｎ－ｋ）個の第２の算出回路と、入力される温度パラメータと、乱数とに基づいて決定される熱励起エネルギーと、前記ｋ個の第１の算出回路がそれぞれ出力する前記第１のエネルギー変化と、前記（Ｎ－ｋ）個の第２の算出回路がそれぞれ出力する前記第２のエネルギー変化とのそれぞれの大小関係に基づいて、値の更新を許容するビットを識別する第１のビット識別情報を出力する選択回路と、前記第１のビット識別情報に対応するビットの値に基づいて、前記第２のビットを識別する第２のビット識別情報、または、前記第４のビットを識別する第３のビット識別情報の何れかを出力する識別情報計算部と、前記第１のビット識別情報、及び、前記識別情報計算部が出力する前記第２のビット識別情報、または、前記第３のビット識別情報に基づいて、前記第１のビット識別情報に対応するビットの値、及び、前記第２のビット識別情報に対応するビットの値、または、前記第３のビット識別情報に対応するビットの値をそれぞれ更新する更新部と、を有する最適化装置が提供される。

また、１つの実施態様では、最適化装置の制御方法が提供される。

１つの側面では、ｋ－ｈｏｔ制約をもつ最適化問題の計算時間を短縮できる。

第１の実施の形態の最適化装置の一例を示す図である。 第２の実施の形態の最適化装置の一例を示す図である。 ΔＥ算出部の一例を示す図である。 ｈ伝搬制御部の一例を示す図である。 ｈ伝搬制御部の他の例を示す図である。 選択回路の一例を示す図である。 識別情報計算部の一例を示す図である。 第２の実施の形態の最適化装置の一例の処理の流れを示すフローチャートである。 第２の実施の形態の最適化装置を用いた場合の計算短縮効果を表すシミュレーション結果を示す図である。

以下、発明を実施するための形態を、図面を参照しつつ説明する。
以下に示す最適化装置は、ｋ－ｈｏｔ制約を満たす状態以外の状態の探索を除外することで、ｋ－ｈｏｔ制約をもつ最適化問題の計算時間を短縮するものである。

計算対象の問題を変換したイジングモデルに含まれる複数のスピン（スピン数＝Ｎ（Ｎ＞２））に対応するＮ個のビットの値を、状態変数であるｘ_１～ｘ_Ｎで表す場合、値が１になる状態変数の数がｋ（＞１）個であるときにｋ－ｈｏｔ制約が満たされる。

たとえば、説明を簡略化するためにＮ＝３、ｋ＝２とした場合、（ｘ_１，ｘ_２，ｘ_３）＝（０，１，１），（１，０，１），（１，１，０）という状態は、２－ｈｏｔ制約を満たす。一方、（ｘ_１，ｘ_２，ｘ_３）＝（０，０，０），（０，０，１），（０，１，０），（１，０，０），（１，１，１）という状態は、２－ｈｏｔ制約を満たさない。

ｋ－ｈｏｔ制約を満たすある状態から、ｋ－ｈｏｔ制約を満たす別の状態に遷移させるためには、最適化装置は、１回の状態更新処理において値が１のビットと値が０のビットをそれぞれ１つずつ変化させることになる。つまり、最適化装置は、ハミング距離＝２の状態遷移を発生させることになる。

ｋ－ｈｏｔ制約は、以下の式（１）で表すことができる。

ｘ_ｉは、インデックス（ビット識別情報）＝ｉに対応するビットの値を表す状態変数である。
ｋ－ｈｏｔ制約を考慮した最適化問題のエネルギー関数は、以下の式（２）のように表すことができる。

式（２）において、右辺の１項目はコスト関数、２項目はｋ－ｈｏｔ制約を考慮したｋ－ｈｏｔ制約項、３項目以降はその他の制約を考慮した制約項を表す。ｋ－ｈｏｔ制約が満たされない場合に、エネルギーが小さくなる、ということが起きないように、λ_１（制約重み）として十分大きな値が用いられることになる。

一方、重み値を用いたイジング型のエネルギー関数Ｅ（ｘ）は、たとえば、以下の式（３）で定義される。

右辺の１項目は、イジングモデルに含まれる全ビットから選択可能な２つのビットの全組み合わせについて、漏れと重複なく、２つのビットの値（０または１）と重み値との積を積算したものである。ｘ_ｊは、インデックス＝ｊに対応するビットの値を表す状態変数であり、Ｗ_ｉｊは、インデックス＝ｉ，ｊに対応するビットの相互作用の大きさを示す重み値である。なお、Ｗ_ｉｉ＝０である。また、Ｗ_ｉｊ＝Ｗ_ｊｉであることが多い（つまり、重み値による係数行列は対称行列である場合が多い）。

右辺の２項目は、全ビットのそれぞれのバイアス値とビットの値との積の総和を求めたものである。ｂ_ｉは、インデックス＝ｉに対応するビットのバイアス値を示している。
ｋ－ｈｏｔ制約を満たす状態以外についても探索が行われる場合、式（３）のＷ_ｉｊを表現するためのビット数は、式（２）のλ_１の値が大きいほど大きくなる。λ_１は、たとえば、上記のＮ（問題のサイズに相当する）や、Ｗ_ｉｊとのバランスをみて決定される。たとえば、最初はＷ_ｉｊの最大値の１０倍程度のλ_１を用いてＷ_ｉｊやｂ_ｉが計算され、エネルギーの最小化が行われる。収束解がｋ－ｈｏｔ制約を満たしていなければ、ｋ－ｈｏｔ制約を満たすようになるまで、λ_１の値が増加される。

一方、ｋ－ｈｏｔ制約を満たす状態のみの探索が行われる場合、式（２）の右辺の２項目のｋ－ｈｏｔ制約項をなくせるため、Ｗ_ｉｊを表現するためのビット数を少なくできる。

ところで、式（３）において、ｘ_ｉの値が変化して１－ｘ_ｉとなると、ｘ_ｉの増加分は、Δｘ_ｉ＝（１－ｘ_ｉ）－ｘ_ｉ＝１－２ｘ_ｉと表せる。この値の変化に伴うエネルギー変化（ΔＥ_ｉ）は、以下の式（４）で表される。

式（４）において、ｘ_ｉが１から０に変化するとき、Δｘ_ｉは－１となり、ｘ_ｉが０から１に変化するとき、Δｘ_ｉは１となる。なお、ｈ_ｉはローカルフィールド値（局所場）と呼ばれ、Δｘ_ｉに応じてｈ_ｉに符号（＋１または－１）を乗じたものがΔＥ_ｉである。

ｘ_ｊが０から１に変化するときのｈ_ｉの変化分は、Δｈ_ｉ ^（ｊ）＝＋Ｗ_ｉｊ、ｘ_ｊが１から０に変化するときのｈ_ｉの変化分は、Δｈ_ｉ ^（ｊ）＝－Ｗ_ｉｊである。同様に、ｘ_ｉが変化したときのインデックス＝ｊに対応するビットについてのｈ_ｊの変化分は、Δｈ_ｊ ^（ｉ）＝Δｘ_ｉＷ_ｉｊ、と表せる。

したがって、ｘ_ｉ，ｘ_ｊが両方変化したときのエネルギー変化は、以下の式（５）で表せる。

前述のように、ｋ－ｈｏｔ制約を満たすある状態から、ｋ－ｈｏｔ制約を満たす別の状態に遷移するには、値が１のビットと値が０のビットをそれぞれ１つずつ変化させることになる。インデックス＝ｉに対応するビットの値が１から０に変化するとともにインデックス＝ｊに対応するビットの値が０から１に変化する場合のエネルギー変化をΔＥ_ｊと表記すると、Δｘ_ｉ＝－１、Δｘ_ｊ＝１であるため、式（５）からΔＥ_ｊは以下の式（６）で表せる。

以下に示す最適化装置は、式（６）で表されるエネルギー変化の計算を行う回路を含む。
（第１の実施の形態）
図１は、第１の実施の形態の最適化装置の一例を示す図である。

最適化装置１０は、Ｎ個のΔＥ算出回路（たとえば、図１のΔＥ算出回路１１ｉ，１１ｊ，１１Ｎを含む）、選択回路１２、識別情報計算部１３、更新部１４、乱数生成回路１５ａ，１５ｂを有する。

Ｎ個のΔＥ算出回路のうち、ｋ個（ｋ＞１）のΔＥ算出回路（図１の例ではΔＥ算出回路１１ｉ，１１Ｎなど）は、以下のような処理を行う。
ｋ個のΔＥ算出回路のそれぞれには、Ｎ個のビットのうち、値が１であるｋ個のビットの何れかについてのローカルフィールド値（たとえば、ｈ_ｉ，ｈ_Ｎ）が供給される。さらにｋ個のΔＥ算出回路のそれぞれには、生成した乱数（ｎ）に基づいて選択した値が０であるビット（インデックス＝ｎに対応するビット）についてのローカルフィールド値（ｈ_ｎ）が供給される。なお、図１では、ローカルフィールド値を計算する回路や、ローカルフィールド値のΔＥ算出回路への伝搬制御を行う回路などについては、図示が省略されている。

また、ｋ個のΔＥ算出回路のそれぞれは、ｋ個のビットの何れかと、インデックス＝ｎに対応するビットとの間の相互作用の大きさを示す重み値を記憶する記憶部（たとえば、記憶部１１ｉａ，１１Ｎａ）を有する。そして、ｋ個のΔＥ算出回路のそれぞれは、供給される２つのローカルフィールド値と重み値とに基づいて、ｋ個のビットの何れかと、インデックス＝ｎに対応するビットの値がそれぞれ変化することによるイジングモデルのエネルギー変化を算出する。

たとえば、ｋ個のΔＥ算出回路のうちの１つであるΔＥ算出回路１１ｉには、値が１であるインデックス＝ｉに対応するビットについてのｈ_ｉと、ｈ_ｎが供給される。また、ΔＥ算出回路１１ｉの記憶部１１ｉａは、Ｗ_ｎｉを記憶する。そして、ΔＥ算出回路１１ｉは、ｈ_ｉ，ｈ_ｎ，Ｗ_ｎｉに基づいて、インデックス＝ｉに対応するビットと、インデックス＝ｎに対応するビットとがそれぞれ変化することによるエネルギー変化（ΔＥ_ｉ）を算出する。ΔＥ_ｉは、式（６）において、ｈ_ｊ＝ｈ_ｎ、Ｗ_ｉｊ＝Ｗ_ｎｉ（ただし、Ｗ_ｎｉ＝Ｗ_ｉｎ）の場合であるから、ΔＥ_ｉ＝ｈ_ｉ－ｈ_ｎ＋Ｗ_ｎｉと表せる。

同様に、ｋ個のΔＥ算出回路のうちの１つであるΔＥ算出回路１１Ｎには、値が１であるインデックス＝Ｎに対応するビットについてのｈ_Ｎと、ｈ_ｎが供給される。また、ΔＥ算出回路１１Ｎの記憶部１１Ｎａは、Ｗ_ｎＮを記憶する。そして、ΔＥ算出回路１１Ｎは、ｈ_Ｎ、ｈ_ｎ、Ｗ_ｎＮに基づいて、インデックス＝Ｎに対応するビットと、インデックス＝ｎに対応するビットとがそれぞれ変化することによるエネルギー変化（ΔＥ_Ｎ）を算出する。ΔＥ_Ｎは、式（６）において、ｈ_ｊ＝ｈ_ｎ、Ｗ_ｉｊ＝Ｗ_ｎＮ（ただし、Ｗ_ｎＮ＝Ｗ_Ｎｎ）の場合であるから、ΔＥ_Ｎ＝ｈ_Ｎ－ｈ_ｎ＋Ｗ_ｎＮと表せる。

一方、Ｎ個のΔＥ算出回路のうち、（Ｎ－ｋ）個のΔＥ算出回路（図１の例ではΔＥ算出回路１１ｊなど）は、以下のような処理を行う。
（Ｎ－ｋ）個のΔＥ算出回路のそれぞれには、Ｎ個のビットのうち、値が０であるビットについてのローカルフィールド値（たとえば、ｈ_ｊ）が供給される。さらに、（Ｎ－ｋ）個のΔＥ算出回路のそれぞれには、生成した乱数（ｍ）に基づいて選択した値が１であるビット（インデックス＝ｍに対応するビット）についてのローカルフィールド値（ｈ_ｍ）が供給される。なお、ｍは、ｎとは異なるシードを用いて生成される乱数である。

また、（Ｎ－ｋ）個のΔＥ算出回路のそれぞれは、値が０の（Ｎ－ｋ）個のビットの何れかと、インデックス＝ｍに対応するビットとの間の相互作用の大きさを示す重み値を記憶する記憶部（たとえば、記憶部１１ｊａ）を有する。そして、（Ｎ－ｋ）個のΔＥ算出回路のそれぞれは、供給される２つのローカルフィールド値と重み値とに基づいて、（Ｎ－ｋ）個のビットの何れかと、インデックス＝ｍに対応するビットとがそれぞれ変化することによるイジングモデルのエネルギー変化を算出する。

たとえば、ΔＥ算出回路１１ｊには、値が０であるインデックス＝ｊに対応するビットについてのｈ_ｊと、ｈ_ｍが供給される。また、ΔＥ算出回路１１ｊの記憶部１１ｊａは、Ｗ_ｍｊを記憶する。そして、ΔＥ算出回路１１ｊは、ｈ_ｊ、ｈ_ｍ、Ｗ_ｍｊに基づいて、インデックス＝ｊに対応するビットと、インデックス＝ｍに対応するビットとがそれぞれ変化することによるエネルギー変化（ΔＥ_ｊ）を算出する。ΔＥ_ｊは、式（６）において、ｈ_ｉ＝ｈ_ｍ、Ｗ_ｉｊ＝Ｗ_ｍｊの場合であるから、ΔＥ_ｊ＝－ｈ_ｊ＋ｈ_ｍ＋Ｗ_ｍｊと表せる。

なお、Ｎ個のΔＥ算出回路は、たとえば、加算器や減算器を用いて実現される。また、ΔＥ算出回路が有する記憶部は、たとえば、レジスタやＳＲＡＭ（Static Random Access Memory）などを用いて実現される。

選択回路１２は、熱励起エネルギーと、Ｎ個のΔＥ算出回路がそれぞれ出力するエネルギー変化との大小関係に基づいて、値の更新を許容するビットを識別するインデックス＝ｌを出力する。熱励起エネルギーは、乱数と、図示しない制御部から入力される温度パラメータ（Ｔ）に基づいて決定される。

シミュレーテッド・アニーリングが行われる場合、Ｔは、たとえば、制御部によって、イジングモデルの状態を更新する処理が、所定回数繰り返されるごとに、値が小さくなるように制御される。なお、上記のような選択回路１２の機能を実行する回路例については後述する。

識別情報計算部１３は、選択回路１２が出力するインデックス＝ｌに対応するビットの値（ｘ_ｌ）に基づいて、インデックス＝ｍまたはインデックス＝ｎの何れかを出力する。ｍ，ｎは、乱数生成回路１５ａ，１５ｂから供給される。ｘ_ｌが０である場合、値が１であるビットのインデックス＝ｍが出力される。ｘ_ｌが１である場合、値が０であるビットのインデックス＝ｎが出力される。識別情報計算部１３は、たとえば、セレクタによって実現できる。

なお、図１の例では、識別情報計算部１３は、インデックス＝ｌも出力しているが、選択回路１２が出力するインデックス＝ｌが直接、更新部１４に供給される場合には、識別情報計算部１３は、インデックス＝ｌを出力しなくてもよい。

更新部１４は、Ｎ個のビットの値（ｘ_１～ｘ_Ｎ）の値を保持する記憶部１４ａを有している。記憶部１４ａは、たとえば、レジスタやＳＲＡＭなどを用いて実現される。更新部１４は、インデックス＝ｌ、及び、インデックス＝ｍまたはインデックス＝ｎに基づいて、ｘ_ｌ及び、インデックス＝ｍに対応するビットの値（ｘ_ｍ）またはインデックス＝ｎに対応するビットの値（ｘ_ｎ）をそれぞれ更新する。

なお、図１では図示が省略されているが、インデックス＝ｌ，ｍ，ｎは、さらに、各ビットについてのローカルフィールド値を更新するために用いられる。
乱数生成回路１５ａは、ｘ_１～ｘ_Ｎに基づいて、Ｎ個のビットのうち、値が０のビットのインデックスの１つである乱数（ｎ）を出力する。乱数生成回路１５ａは、たとえば、ｘ_１～ｘ_Ｎのうち、値が０である（Ｎ－ｋ）個のビットのインデックスを出力する回路と、出力された（Ｎ－ｋ）個のインデックスのうちの何れか１つを、乱数を用いて選択する回路と、その乱数を生成する回路により実現される。乱数を生成する回路としては、たとえば、ＬＦＳＲ（Linear Feedback Shift Register）がある。

乱数生成回路１５ｂは、ｘ_１～ｘ_Ｎに基づいて、Ｎ個のビットのうち、値が１のビットのインデックスの１つである乱数（ｍ）を出力する。乱数生成回路１５ｂは、たとえば、ｘ_１～ｘ_Ｎのうち、値が１であるｋ個のビットのインデックスを出力する回路と、出力されたｋ個のインデックスのうちの何れか１つを、乱数を用いて選択する回路と、その乱数を生成する回路により実現される。

以下、最適化装置１０の動作例を説明する。
まず、初期設定が行われる。初期設定は、たとえば、図示しない制御部の制御のもとｘ_１～ｘ_Ｎを全て０に設定した後に、乱数を用いて、ｋ個のビットの値を１に設定し、その他のビットの値を０に設定する処理やローカルフィールド値の初期設定を含む。

その後、乱数生成回路１５ａ，１５ｂは、ｎ，ｍを出力する。これによって、図１では図示が省略されているが、ｈ_ｎを更新する回路から、ｋ個のΔＥ算出回路に対してｈ_ｎが供給され、ｈ_ｍを更新する回路から、Ｎ－ｋ個のΔＥ算出回路に対してｈ_ｍが供給される。

また、全ての重み値を記憶している記憶部（図示せず）から、値が１のビットのそれぞれと、インデックス＝ｎに対応するビットとの間の相互作用の大きさを示す重み値のそれぞれが、ｋ個のΔＥ算出回路のうち、対応するΔＥ算出回路の記憶部に供給される。たとえば、図１に示すようにＷ_ｎｉは、ΔＥ算出回路１１ｉの記憶部１１ｉａに供給され、Ｗ_ｎＮは、ΔＥ算出回路１１Ｎの記憶部１１Ｎａに供給される。

また、全ての重み値を記憶している記憶部から、値が０のビットのそれぞれと、インデックス＝ｍに対応するビットとの間の相互作用の大きさを示す重み値のそれぞれが、（Ｎ－ｋ）個のΔＥ算出回路のうち、対応するΔＥ算出回路の記憶部に供給される。たとえば、図１に示すようにＷ_ｍｊは、ΔＥ算出回路１１ｊの記憶部１１ｊａに供給される。

そして、ｋ個のΔＥ算出回路と（Ｎ－ｋ）個のΔＥ算出回路は、前述のようなエネルギー変化を算出し、選択回路１２は、Ｎ個のビットの中から、値の更新を許容するビットを識別するインデックス＝１を出力する。

識別情報計算部１３は、ｘ_ｌが０である場合、乱数生成回路１５ｂから供給されるｍをインデックスとして出力し、ｘ_ｌが１である場合、乱数生成回路１５ａから供給されるｎを、インデックスとして出力する。

更新部１４は、インデックス＝ｌ、及び、インデックス＝ｍまたはインデックス＝ｎに基づいて、ｘ_ｌ及び、ｘ_ｍまたはｘ_ｎをそれぞれ更新する。
図１には、状態の更新例が示されている。たとえば、初期設定処理により、ｘ_１～ｘ_Ｎのうち、ｘ_ｉ，ｘ_Ｎを含むｋ個が１、ｘ_１，ｘ_ｊを含む（Ｎ－ｋ）個が０である状態（初期状態）となっている。選択回路１２が出力するインデックス＝ｌがインデックス＝ｉと等しい場合、識別情報計算部１３は、ｘ_ｉが１であるため、ｎをインデックスとして出力する。ｎ＝１である場合、更新部１４は、ｘ_１を０から１に更新するとともに、ｘ_ｉを１から０に更新する。インデックス＝ｌがインデックス＝ｊと等しい場合、識別情報計算部１３は、ｘ_ｊが０であるため、ｍをインデックスとして出力する。ｍ＝Ｎの場合、更新部１４は、ｘ_Ｎを１から０に更新するとともに、ｘ_ｊを０から１に更新する。

何れの場合も、値が１である１つのビットと、値が０である１つのビットとがそれぞれ更新されるため、更新後の状態もｋ－ｈｏｔ制約を満たす。このように、ｋ－ｈｏｔ制約を満たした状態間での遷移が可能となる。

なお、ｘ_ｉが１から０に更新された場合、ΔＥ算出回路１１ｉは、（Ｎ－ｋ）個のΔＥ算出回路の１つとなる。そして、乱数生成回路１５ａ，１５ｂにて新たにｎ，ｍが生成された後、ΔＥ算出回路１１ｉにはｈ_ｍが供給され、記憶部１１ｉａにはＷ_ｍｉが記憶される。また、ｘ_ｊが０から１に更新された場合、ΔＥ算出回路１１ｊは、ｋ個のΔＥ算出回路の１つとなる。そして、乱数生成回路１５ａ，１５ｂにて新たにｎ，ｍが出力された後、ΔＥ算出回路１１ｊにはｈ_ｎが供給され、記憶部１１ｊａにはＷ_ｎｊが記憶される。

上記のように、Ｎ個のΔＥ算出回路のうち、ｈ_ｍ，ｈ_ｎが供給されるΔＥ算出回路は、ｘ_１～ｘ_Ｎが更新されるたびに変わる。また、ΔＥ算出回路内の記憶部に記憶される重み値も更新される。

ｈ_ｍ，ｈ_ｎの供給先の変更や、重み値の更新が行われた後、同様に、Ｎ個のΔＥ算出回路にてエネルギー変化が計算される。その後、選択回路１２、識別情報計算部１３、更新部１４にて上記と同様の処理が行われる。このような状態更新処理が所定の繰り返し回数、繰り返されたのちに得られた状態（ｘ_１～ｘ_Ｎ）が、たとえば、最適化問題に対する解として出力される。

なお、更新部１４は、ｘ_ｌ及び、ｘ_ｍまたはｘ_ｎが変化することによるエネルギー変化に基づいてエネルギーを更新してもよい。また、更新部１４は、各更新時点での最小エネルギーとその最小エネルギーが得られたときの状態（最小エネルギー時の状態）とを保持するようにしてもよい。その場合、更新部１４は、状態更新処理が所定の繰り返し回数、繰り返されたときに保持している最小エネルギー時の状態を、解として出力してもよい。

以上のように、第１の実施の形態の最適化装置１０は、全ビット（Ｎ個のビット）の中で、値が０と１のビットがそれぞれ１つずつ共に変化するときのエネルギー変化に基づいて、どの２つのビットの遷移を許容するかを決定する。そして最適化装置１０は、一度の状態更新処理において、その決定した２つのビットの値を更新する。これによって、ｋ－ｈｏｔ制約を満たさない状態遷移が抑制され、探索空間を小さくできる。このため、基底状態の探索を高速化することができる。

たとえば、Ｎ＝１０２４で、ｋ＝３２の場合、全状態数が２^１０２４、すなわちほぼ１０^３０７であるのに対して、ｋ－ｈｏｔ制約を満たす状態数は、１０２４！／（１０２４－３２）！（“！”は階乗を表す）、すなわちほぼ１０^９６となる。つまり、２^１０２４の状態を探索する場合に比べて、探索する状態数が１／１０^２１１と少なくなる。

また、最適化装置１０によれば、式（２）の右辺の２項目のｋ－ｈｏｔ制約項をなくせるため、ｋ－ｈｏｔ制約項のために生じるエネルギー障壁を小さくでき、状態遷移の時間を短縮できる。

また、前述のように式（２）の右辺の２項目のｋ－ｈｏｔ制約項をなくせるため、重み値を表現するためのビット数を減らせることができ、重み値を記憶しておくためのハードウェア量を削減できる。

たとえば、最適化装置１０が交通量最適化問題を計算するとき、Ｎ＝１６、λ_１＝１００とした場合、重み値の範囲は、４≦Ｗ_ｉｊ≦２１４となる。これに対して、式（２）の右辺の２項目のｋ－ｈｏｔ制約項をなくせる場合（つまりλ_１＝０の場合）、重み値の範囲は、４≦Ｗ_ｉｊ≦１４となる。つまり、重み値を表現するためのビット数を、８ビットから４ビットに減少させることができる。また、問題の規模が大きくなって、たとえば、Ｎ＝１０２４、λ_１＝１００００である場合、重み値の範囲は、４≦Ｗ_ｉｊ≦２０１０８となる。これに対して、λ_１＝０の場合、重み値の範囲は、４≦Ｗ_ｉｊ≦１０８となる。つまり、重み値を表現するためのビット数を、１６ビットから７ビットに減少させることができる。

このように、問題の規模が大きくなるほど、重み値のビット数の削減効果はより顕著となる。
なお、Ｎ－ｋ＞２またはｋ＞２である場合、（Ｎ－ｋ）ｋ＞Ｎとなり、ｋ－ｈｏｔ制約を満たす状態は、一般的にＮよりも大きい。しかし、上記の最適化装置１０では、乱数であるｎ，ｍを用いて、Ｎ通りの状態遷移候補から１つの状態遷移が実施されるため、Ｎビットに対応した最適化装置１０を用いた処理が可能である。

（第２の実施の形態）
図２は、第２の実施の形態の最適化装置の一例を示す図である。
最適化装置２０は、ΔＥ算出部２１、選択回路２２、識別情報計算部２３、更新部２４、乱数生成回路２５ａ，２５ｂ、制御部２６を有する。

ΔＥ算出部２１は、ハミング距離＝２の状態遷移によってｋ－ｈｏｔ制約を満たすある状態からｋ－ｈｏｔ制約を満たす別の状態に遷移するときのエネルギー変化（ΔＥ_１～ΔＥ_Ｎ）を算出する。

選択回路２２は、熱励起エネルギーと、ΔＥ_１～ΔＥ_Ｎとの大小関係に基づいて、Ｎ個のビットのうち、値の更新を許容する１つのビットを識別するインデックス＝ｌを出力する。熱励起エネルギーは、乱数と、制御部２６から入力されるＴに基づいて決定される。なお、熱励起エネルギーと、ΔＥ_１～ΔＥ_Ｎとの大小関係によっては、Ｎ個のビットのうち、１つも更新が許容されない場合がある。選択回路２２は、更新が許容されたか否かを示すフラグについても出力するものとする。

識別情報計算部２３は、選択回路２２が出力するインデックス＝ｌに対応するビットの値（ｘ_ｌ）に基づいて、インデックス＝ｍまたはインデックス＝ｎの何れかを出力する。ｎ，ｍは、乱数生成回路２５ａ，２５ｂから供給される。ｘ_ｌが０である場合、値が１であるビットのインデックス＝ｍが出力される。ｘ_ｌが１である場合、値が０であるビットのインデックス＝ｎが出力される。以下では、識別情報計算部２３は、選択回路２２から供給されるインデックス＝ｌとフラグについても出力するものとする。インデックス＝ｌ，ｍ，ｎは、ΔＥ算出部２１に供給され、エネルギー変化を計算するために用いられる各ビットについてのローカルフィールド値を更新する際に用いられる。

なお、フラグが更新を許容しないことを示す値である場合、識別情報計算部２３は、たとえば、インデックス＝ｌ，ｍ，ｎを無効な値（たとえば、０）とする。
更新部２４は、Ｎ個のビットの値（ｘ_１～ｘ_Ｎ）の値を保持する記憶部２４ａを有している。記憶部２４ａは、たとえば、レジスタやＳＲＡＭなどを用いて実現される。更新部２４は、フラグが更新を許容する旨の値である場合、ｘ_ｌ及び、ｘ_ｍまたはｘ_ｎをそれぞれ更新する。なお、更新部２４は、ｘ_ｌ及び、ｘ_ｍまたはｘ_ｎが変化することによるエネルギー変化に基づいてエネルギーを更新してもよい。また、更新部２４は、各更新時点での最小エネルギーとその最小エネルギーが得られたときの状態（最小エネルギー時の状態）とを保持するようにしてもよい。また、更新部２４は、ｘ_１～ｘ_ＮをΔＥ算出部２１に供給する。ｘ_１～ｘ_Ｎを用いたΔＥ算出部２１の処理の例については後述する。

乱数生成回路２５ａは、ｘ_１～ｘ_Ｎに基づいて、Ｎ個のビットのうち、値が０のビットのインデックスの１つである乱数（ｎ）を出力する。乱数生成回路２５ａは、たとえば、ｘ_１～ｘ_Ｎのうち、値が０である（Ｎ－ｋ）個のビットのインデックスを出力する回路と、出力された（Ｎ－ｋ）個のインデックスのうちの何れか１つを、乱数を用いて選択する回路と、その乱数を生成する回路により実現される。乱数を生成する回路としては、たとえば、ＬＦＳＲがある。

乱数生成回路２５ｂは、ｘ_１～ｘ_Ｎに基づいて、Ｎ個のビットのうち、値が１のビットのインデックスの１つである乱数（ｍ）を出力する。乱数生成回路２５ｂは、たとえば、ｘ_１～ｘ_Ｎのうち、値が１であるｋ個のビットのインデックスを出力する回路と、出力されたｋ個のインデックスのうちの何れか１つを、乱数を用いて選択する回路と、その乱数を生成する回路により実現される。

制御部２６は、最適化装置２０の後述する初期設定処理を行う。また、制御部２６は、イジングモデルの状態を更新する処理が所定回数繰り返されるごとに、たとえば、制御装置２７によって指定される温度スケジュールにしたがってＴの値を小さくしていく。

さらに、制御部２６は、状態更新処理が所定の繰り返し回数、繰り返されたのちに、記憶部２４ａに保持されている状態（ｘ_１～ｘ_Ｎ）を取得し、たとえば、最適化問題に対する解として制御装置２７に送信する。なお、制御部２６は、更新部２４の記憶部２４ａが、最小エネルギーや最小エネルギー時の状態を保持している場合には、状態更新処理が所定の繰り返し回数、繰り返されたのちに、それらの情報を取得して、制御装置２７に送信してもよい。

制御部２６は、たとえば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの特定用途の電子回路にて実現できる。なお、制御部２６は、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）などのプロセッサであってもよい。その場合、プロセッサは、図示しないメモリに記憶されたプログラムを実行することで、上記の処理を行う。

（ΔＥ算出部２１の例）
図３は、ΔＥ算出部の一例を示す図である。
ΔＥ算出部２１は、記憶部２１ａ、選択回路２１ｂ１～２１ｂＮ，２１ｃ１～２１ｃＮ、ｈ更新回路２１ｄ１～２１ｄＮ、ｈ伝搬制御部２１ｅ、ΔＥ算出回路２１ｆ１～２１ｆＮを有する。

記憶部２１ａは、イジングモデルに含まれる全スピンに対応する全ビットの間の相互作用の大きさを示す重み値（Ｗ_１１～Ｗ_ＮＮ）を格納している。Ｗ_１１～Ｗ_ＮＮは、初期設定処理時に、制御部２６によって記憶部２１ａに記憶される。記憶部２１ａは、たとえば、レジスタやＳＲＡＭなどを用いて実現される。

選択回路２１ｂ１～２１ｂＮのそれぞれは、識別情報計算部２３が出力するインデックス＝ｌ及び、インデックス＝ｍまたはインデックス＝ｎに基づいて、記憶部２１ａに格納されている重み値のうち、２つを選択して出力する。

たとえば、選択回路２１ｂｉはＷ_１ｉ～Ｗ_Ｎｉの中から、Ｗ_ｌｉ及び、Ｗ_ｍｉまたはＷ_ｎｉを選択して出力する。なお、インデックス＝ｌ及び、インデックス＝ｍまたはインデックス＝ｎのうち、ｌが先に選択回路２１ｂｉに供給される場合、選択回路２１ｂｉは、Ｗ_ｌｉをＷ_ｍｉまたはＷ_ｎｉよりも先に出力する。ｍまたはｎが先に選択回路２１ｂｉに供給される場合、選択回路２１ｂｉは、Ｗ_ｍｉまたはＷ_ｎｉをＷ_ｌよりも先に出力する。同様に選択回路２１ｂｊはＷ_１ｊ～Ｗ_Ｎｊの中から、Ｗ_ｌｊ及び、Ｗ_ｍｊまたはＷ_ｎｊを選択して出力する。

選択回路２１ｃ１～２１ｃＮのそれぞれは、１～Ｎのインデックスの何れかに対応するビットの値（ｘ_１～ｘ_Ｎ）とｎ，ｍとを選択信号として入力する。そして、選択回路２１ｃ１～２１ｃＮのそれぞれは、入力したビットの値が０であればそのビットと、インデックス＝ｍに対応するビットとの間の相互作用の大きさを示す重み値を選択する。また、選択回路２１ｃ１～２１ｃＮのそれぞれは、入力したビットの値が１であればそのビットと、インデックス＝ｎに対応するビットとの間の相互作用の大きさを示す重み値を選択する。そして、選択回路２１ｃ１～２１ｃＮのそれぞれは、選択した重み値を、ΔＥ算出回路２１ｆ１～２１ｆＮの記憶部２１ｆ１ａ～２１ｆＮａの何れかに供給する。

たとえば、選択回路２１ｃｉは、ｘ_ｉが０であれば、Ｗ_１ｉ～Ｗ_Ｎｉの中からＷ_ｍｉを選択してΔＥ算出回路２１ｆｉの記憶部２１ｆｉａに供給し、ｘ_ｉが１であれば、Ｗ_１ｉ～Ｗ_Ｎｉの中からＷ_ｎｉを選択して記憶部２１ｆｉａに供給する。選択回路２１ｃｊは、ｘ_ｊが０であれば、Ｗ_１ｊ～Ｗ_Ｎｊの中からＷ_ｍｊを選択してΔＥ算出回路２１ｆｊの記憶部２１ｆｊａに供給し、ｘ_ｊが１であれば、Ｗ_１ｊ～Ｗ_Ｎｊの中からＷ_ｎｊを選択して記憶部２１ｆｊａに供給する。

ｈ更新回路２１ｄ１～２１ｄＮのそれぞれは、図示を省略しているが保持部（たとえば、レジスタ）を有し、ｈ_１～ｈ_Ｎの何れかの保持及び更新を行う。
たとえば、ｈ更新回路２１ｄｉは、選択回路２１ｂｉが選択したＷ_ｌｉ及び、Ｗ_ｍｉまたはＷ_ｎｉを用いて、ｈ_ｉを更新する。選択回路２１ｂｉがＷ_ｌｉとＷ_ｍｉを選択する場合（ｘ_ｌ＝０の場合）、ｈ更新回路２１ｄｉは、ｈ_ｉ－Ｗ_mｉ＋Ｗ_ｌｉを計算することで、ｈ_ｉを更新する。選択回路２１ｂｉがＷ_ｌｉとＷ_ｎｉを選択する場合（ｘ_ｌ＝１の場合）、ｈ更新回路２１ｄｉは、ｈ_ｉ－Ｗ_ｌｉ＋Ｗ_ｎｉを計算することで、ｈ_ｉを更新する。ｈ更新回路２１ｄｊは、選択回路２１ｂｊが選択したＷ_ｌｊ及び、Ｗ_ｍｊまたはＷ_ｎｊを用いて、ｈ_ｊを更新する。選択回路２１ｂｊがＷ_ｌｊとＷ_ｍｊを選択する場合（ｘ_ｌ＝０の場合）、ｈ更新回路２１ｄｊは、ｈ_ｊ－Ｗ_mｊ＋Ｗ_ｌｊを計算することで、ｈ_ｊを更新する。選択回路２１ｂｊがＷ_ｌｊとＷ_ｎｊを選択する場合（ｘ_ｌ＝１の場合）、ｈ更新回路２１ｄｊは、ｈ_ｊ－Ｗ_ｌｊ＋Ｗ_ｎｊを計算することで、ｈ_ｊを更新する。

ｈ_１～ｈ_Ｎの初期値は、たとえば、バイアス値（ｂ_１～ｂ_Ｎ）であり、初期設定処理時に、制御部２６によって設定される。ｈ更新回路２１ｄ１～２１ｄＮは、たとえば、加算器や減算器を用いて実現される。

また、ｈ更新回路２１ｄ１～２１ｄＮのそれぞれは、更新するローカルフィールド値がどのビットについてのものであるかを示すインデックスを保持しており、そのインデックスを出力する。

ｈ伝搬制御部２１ｅは、ｘ_１～ｘ_Ｎ、インデックス＝１～Ｎ、及び、乱数生成回路２５ａ，２５ｂが出力するｍ，ｎに基づいて、ｈ_ｍ，ｈ_ｎの伝搬先（供給先）を制御する。
図４は、ｈ伝搬制御部の一例を示す図である。

図４では、ｈ伝搬制御部２１ｅの一部（インデックス＝ｉ，ｍ，ｎに対応するビットについてのｈ_ｊ，ｈ_ｍ，ｈ_ｎの伝搬制御を行う部分）が示されている。ｈ伝搬制御部２１ｅは、ＥｘＮＯＲ（排他的否定論理和）回路３０ｉ，３０ｍ，３０ｎ，３１ｉ，３１ｍ，３１ｎ、スイッチ３２ｉ，３２ｍ，３２ｎ，３３ｉ，３３ｍ，３３ｎ、セレクタ３４ｉ、ｈ_ｍ伝搬バス３５、ｈ_ｎ伝搬バス３６を有する。

ＥｘＮＯＲ回路３０ｉ，３１ｉの一方の入力端子には、インデックス＝ｉが入力され、ＥｘＮＯＲ回路３０ｍ，３１ｍの一方の入力端子には、インデックス＝ｍが入力され、ＥｘＮＯＲ回路３０ｎ，３１ｎの一方の入力端子には、インデックス＝ｎが入力される。ＥｘＮＯＲ回路３０ｉ，３０ｍ，３０ｎの他方の入力端子には、乱数生成回路２５ｂが出力するｍが入力され、ＥｘＮＯＲ回路３１ｉ，３１ｍ，３１ｎの他方の入力端子には、乱数生成回路２５ａが出力するｎが入力される。

スイッチ３２ｉ，３３ｉの一方の端子にはｈ_ｉが供給され、スイッチ３２ｍ，３３ｍの一方の端子にはｈ_ｍが供給され、スイッチ３２ｎ，３３ｎの一方の端子にはｈ_ｎが供給される。スイッチ３２ｉ，３２ｍ，３２ｎの他方の端子はｈ_ｍ伝搬バス３５に接続され、スイッチ３３ｉ，３３ｍ，３３ｎの他方の端子はｈ_ｎ伝搬バス３６に接続されている。

スイッチ３２ｉは、ＥｘＮＯＲ回路３０ｉが出力する制御信号が１の場合にオンし、制御信号が０の場合にオフする。スイッチ３３ｉは、ＥｘＮＯＲ回路３１ｉが出力する制御信号が１の場合にオンし、制御信号が０の場合にオフする。スイッチ３２ｍは、ＥｘＮＯＲ回路３０ｍが出力する制御信号が１の場合にオンし、制御信号が０の場合にオフする。スイッチ３３ｍは、ＥｘＮＯＲ回路３１ｍが出力する制御信号が１の場合にオンし、制御信号が０の場合にオフする。スイッチ３２ｎは、ＥｘＮＯＲ回路３０ｎが出力する制御信号が１の場合にオンし、制御信号が０の場合にオフする。スイッチ３３ｎは、ＥｘＮＯＲ回路３１ｎが出力する制御信号が１の場合にオンし、制御信号が０の場合にオフする。

スイッチ３２ｉ，３２ｍ，３２ｎ，３３ｉ，３３ｍ，３３ｎは、たとえば、トランスファーゲートである。
セレクタ３４ｉの一方の入力端子はｈ_ｍ伝搬バス３５に接続され、他方の入力端子はｈ_ｎ伝搬バス３６に接続されている。セレクタ３４ｉの出力端子はΔＥ算出回路２１ｈｉに接続されている。セレクタ３４ｉは、選択信号として供給されるｘ_ｉが０の場合、ｈ_ｍ伝搬バス３５に伝搬されるローカルフィールド値を出力し、ｘ_ｉが１の場合、ｈ_ｎ伝搬バス３６に伝搬されるローカルフィールド値を出力する。なお、図４では図示が省略されているが、セレクタ３４ｉと同様のセレクタがΔＥ算出回路２１ｈｉ以外の各ΔＥ算出回路にも接続されている。

このようなｈ伝搬制御部２１ｅでは、乱数生成回路２５ｂからｍが入力されると、ＥｘＮＯＲ回路３０ｍは、両入力が等しいため、１を出力する。これにより、スイッチ３２ｍはオンし、ｈ_ｍがｈ_ｍ伝搬バス３５に伝搬される。また、乱数生成回路２５ａからｎが入力されると、ＥｘＮＯＲ回路３１ｎは、両入力が等しいため、１を出力する。これにより、スイッチ３３ｎはオンし、ｈ_ｎがｈ_ｎ伝搬バス３６に伝搬される。ＥｘＮＯＲ回路３０ｉ，３０ｎ，３１ｉ，３１ｍは、両入力が異なるため、０を出力する。これにより、スイッチ３２ｉ，３２ｎ，３３ｉ，３３ｍはオフする。セレクタ３４ｉに供給されるｘ_ｉが０の場合、ｈ_ｍがΔＥ算出回路２１ｈｉに供給され、ｘ_ｉが１の場合、ｈ_ｎがΔＥ算出回路２１ｈｉに供給される。

図５は、ｈ伝搬制御部の他の例を示す図である。
図５に示すｈ伝搬制御部２１ｅａは、図４に示したスイッチ３２ｉ，３２ｍ，３２ｎ，３３ｉ，３３ｍ，３３ｎの代わりに、トライステートバッファ３２ｉａ，３２ｍａ，３２ｎａ，３３ｉａ，３３ｍａ，３３ｎａが用いられている。トライステートバッファ３２ｉａ，３２ｍａ，３２ｎａ，３３ｉａ，３３ｍａ，３３ｎａのそれぞれは、制御信号が１の場合に、入力信号（ローカルフィールド値）を出力し、制御信号が０の場合は、出力端子をハイインピーダンス状態とする。その他のｈ伝搬制御部２１ｅａの動作については、図４に示したｈ伝搬制御部２１ｅの動作と同じである。

図３の説明に戻る。ΔＥ算出回路２１ｆ１～２１ｆＮは、ローカルフィールド値と重み値とを用いて、ハミング距離＝２の状態遷移によってｋ－ｈｏｔ制約を満たすある状態からｋ－ｈｏｔ制約を満たす別の状態に遷移するときのΔＥ_１～ΔＥ_Ｎを算出する。

ΔＥ算出回路２１ｆ１～２１ｆＮのそれぞれには、ｈ更新回路２１ｄ１～２１ｄＮの何れかから、ｈ_１～ｈ_Ｎの何れかが直接供給される。さらに、値が０のビットについてのローカルフィールド値がｈ更新回路２１ｄ１～２１ｄＮの何れかから供給されるΔＥ算出回路には、ｈ伝搬制御部２１ｅによってｈ_ｍが供給される。また、値が１のビットについてのローカルフィールド値がｈ更新回路２１ｄ１～２１ｄＮの何れかから供給されるΔＥ算出回路には、ｈ伝搬制御部２１ｅによってｈ_ｎが供給される。また、ΔＥ算出回路２１ｆ１～２１ｆＮのそれぞれには、ｘ_１～ｘ_Ｎの何れかが供給される。

また、ΔＥ算出回路２１ｆ１～２１ｆＮは、式（６）の計算をするための重み値を保持する記憶部２１ｆ１ａ～２１ｆＮａを有する。記憶部２１ｆ１ａ～２１ｆＮａに保持される重み値は、前述の選択回路２１ｃ１～２１ｃＮによって選択される。

たとえば、ｘ_ｉが１から０に更新され、ｘ_ｎが０から１に更新される場合、ΔＥ_ｉは、式（６）において、ｈ_ｊ＝ｈ_ｎ、Ｗ_ｉｊ＝Ｗ_ｎｉ（ただし、Ｗ_ｎｉ＝Ｗ_ｉｎ）の場合であるため、ΔＥ_ｉ＝ｈ_ｉ－ｈ_ｎ＋Ｗ_ｎｉと表せる。一方、ｘ_ｉが０から１に更新され、ｘ_ｍが１から０に更新される場合、ΔＥ_ｉは、式（６）において、ｈ_ｉ＝ｈ_ｍ、ｈ_ｊ＝ｈ_ｉの場合であるため、ΔＥ_ｉ＝－ｈ_ｉ＋ｈ_ｍ＋Ｗ_ｍｉと表せる。

このため、ΔＥ算出回路２１ｆｉは、現在のｘ_ｉが１の場合、ΔＥ_ｉ＝ｈ_ｉ－ｈ_ｎ＋Ｗ_ｎｉを出力し、現在のｘ_ｉが０の場合、ΔＥ_ｉ＝－ｈ_ｉ＋ｈ_ｍ＋Ｗ_ｍｉを出力する。
ΔＥ算出回路２１ｆ１～２１ｆＮは、たとえば、加算器、減算器、セレクタを用いて実現される。また、記憶部２１ｆ１ａ～２１ｆＮａは、たとえば、レジスタやＳＲＡＭなどを用いて実現される。

（選択回路２２の一例）
図６は、選択回路の一例を示す図である。
選択回路２２は、符号反転部２２ａ、オフセット加算部２２ｂ、乱数発生回路２２ｃ、選択法則適用部２２ｄ、乗算器２２ｅ、比較部２２ｆ、セレクタ２２ｇを有する。

符号反転部２２ａは、ΔＥ_１，ΔＥ_２，…，ΔＥ_Ｎのそれぞれに－１を掛けて符合を反転させる。
オフセット加算部２２ｂは、符号反転部２２ａの出力値（－ΔＥ_１～－ΔＥ_Ｎ）のそれぞれに、オフセット値を加える。オフセット加算部２２ｂは、後述するセレクタ２２ｇが出力するフラグが更新を許容しないことを示すとき（つまり状態遷移が生じないとき）、オフセット値を増加していく。一方、オフセット加算部２２ｂは、フラグが、更新を許容することを示すとき（つまり状態遷移が生じるとき）には、オフセット値を０にする。オフセット値が大きくなると状態遷移が許容されやすくなり、現在の状態が局所解にある場合、その局所解からの脱出が促進される。

乱数発生回路２２ｃは、０以上、１以下の一様乱数（ｒ）を発生する。
選択法則適用部２２ｄは、シミュレーテッド・アニーリングを行うための選択法則（メトロポリス法またはギブス法）に基づいた値を出力する。

シミュレーテッド・アニーリングが行われる場合、あるエネルギー変化を引き起こす状態遷移の許容確率Ａ（ΔＥ，Ｔ）を以下の式（７）、式（８）のように決めれば、時刻（反復回数）無限大の極限で状態が最適解に到達することが証明されている。

式（７）、式（８）においてＴは、前述の温度パラメータである。
式（７）で表される許容確率Ａ（ΔＥ，Ｔ）を用いた場合、十分な反復後に定常状態に達したとすると、各状態の占有確率は熱力学における熱平衡状態に対するボルツマン分布にしたがう。そして、高い温度から徐々に下げていくとエネルギーの低い状態の占有確率が増加するため、十分温度が下がるとエネルギーの低い状態が得られるはずである。この様子が材料を焼き鈍したときの状態変化とよく似ているため、この方法はシミュレーテッド・アニーリングと呼ばれるのである。このとき、エネルギーが上がる状態遷移が確率的に起こることは、物理学における熱励起に相当する。

許容確率Ａ（ΔＥ，Ｔ）でΔＥを引き起こす状態遷移を許容することを示すフラグ（＝１）を出力する回路は、式（７）、式（８）のｆ（－ΔＥ／Ｔ）と、一様乱数ｒとの比較結果に基づいた値を出力する比較器によって実現できる。

ただ、次のような変形を行っても同じ機能が実現できる。２つの数に同じ単調増加関数を作用させても大小関係は変化しない。したがって比較器の２つの入力に同じ単調増加関数を作用させても比較器の出力は変わらない。たとえば、ｆ（－ΔＥ／Ｔ）に作用させる単調増加関数としてｆ（－ΔＥ／Ｔ）の逆関数ｆ^－１（－ΔＥ／Ｔ）、一様乱数に作用させる単調増加関数としてｆ^－１（－ΔＥ／Ｔ）の－ΔＥ／Ｔをｒとしたｆ^－１（ｒ）を用いることができる。その場合、上記の比較器と同様の機能を有する回路は、－ΔＥ／Ｔがｆ^－１（ｒ）より大きいとき１を出力する回路でよいことがわかる。さらにＴが正であることから、その回路は、－ΔＥがＴ・ｆ^－１（ｒ）より大きいとき１を出力する回路でよい。

選択法則適用部２２ｄは、入力される一様乱数を上記のｆ^－１（ｒ）の値に変換する変換テーブルを用いて、ｆ^－１（ｒ）の値を出力する。メトロポリス法が適用される場合、ｆ^－１（ｒ）は、ｌｏｇ（ｒ）である。変換テーブルは、たとえば、ＲＡＭ（Random Access Memory）、フラッシュメモリなどのメモリに記憶されている。

乗算器２２ｅは、Ｔと、ｆ^－１（ｒ）との積（Ｔ・ｆ^－１（ｒ））を出力する。Ｔ・ｆ^－１（ｒ）は、熱励起エネルギーに相当する。
比較部２２ｆは、ΔＥ_１～ΔＥ_Ｎのそれぞれについてのオフセット加算部２２ｂによる加算結果と、Ｔ・ｆ^－１（ｒ）とを比較し、Ｔ・ｆ^－１（ｒ）より大きい加算結果に対するフラグとして、１を出力する。また、比較部２２ｆは、Ｔ・ｆ^－１（ｒ）以下の加算結果に対するフラグとして、０を出力する。

セレクタ２２ｇは、ΔＥ_１～ΔＥ_Ｎのそれぞれについてのフラグに基づいて、更新が許容されたビットのインデックス＝ｌとフラグを出力する。更新が許容されたビットが複数ある場合、乱数に基づいて、そのうちの１つのビットのインデックスが、インデックス＝ｌとして出力される。更新が許容されたビットがない場合についても、何れかのビットのインデックスが出力される。その場合、セレクタ２２ｇが出力するフラグは０となる。

たとえば、セレクタ２２ｇは、インデックス＝ｌとして、ｌ番目のビットの値が１で、他のビットの値が０であるＮビット値を出力する。
なお、図１に示した第１の実施の形態の最適化装置１０の選択回路１２についても、図６に示すような回路を用いて実現できる。

（識別情報計算部２３の一例）
図７は、識別情報計算部の一例を示す図である。
識別情報計算部２３は、セレクタ２３ａにより実現できる。セレクタ２３ａの一方の入力端子には、乱数生成回路２５ｂよりｍが入力され、他方の入力端子には、乱数生成回路２５ａよりｎが入力される。セレクタ２３ａは、更新部２４から供給されるｘ_ｌが０である場合、ｍを出力し、ｘ_ｌが１である場合、ｎを出力する。

（最適化装置２０の全体動作例）
図８は、第２の実施の形態の最適化装置の一例の処理の流れを示すフローチャートである。

まず、制御部２６は、最適化装置２０の初期設定処理を行う（ステップＳ１）。初期設定処理として、たとえば、以下の処理が行われる。制御部２６は、制御装置２７から受信したＷ_１１～Ｗ_ＮＮをΔＥ算出部２１の記憶部２１ａに記憶する。また、制御部２６は、制御装置２７から受信したｈ_１～ｈ_Ｎの初期値（たとえば、バイアス値）をΔＥ算出部２１のｈ更新回路２１ｄ１～２１ｄＮに設定する。さらに、制御部２６は、制御装置２７から受けたアニーリング条件に基づいて、選択回路２２に温度パラメータの初期値を設定する。また、制御部２６は、ｘ_１～ｘ_Ｎ（全て０）を、記憶部２４ａに記憶する。その後、制御部２６は、乱数を用いて、ｘ_１～ｘ_Ｎのうちｋ個の値を１とする。たとえば、制御部２６は、更新部２４にｋ個の状態変数を１つずつ０から１に更新させ、それに伴いｈ更新回路２１ｄ１～２１ｄＮにｈ_１～ｈ_Ｎを更新させる。なお、制御部２６が、ｈ_１～ｈ_Ｎを更新して、更新後のｈ_１～ｈ_Ｎをｈ更新回路２１ｄ１～ｄ１ｄＮに設定してもよい。

上記のような初期設定処理が終了した後、乱数生成回路２５ａ，２５ｂは、ｘ_１～ｘ_Ｎに基づいて、ｎ，ｍを生成する（ステップＳ２）。
ΔＥ算出部２１の選択回路２１ｃ１～２１ｃＮは、ｘ_１～ｘ_Ｎとｎ，ｍに基づいて、ΔＥ_１～ΔＥ_Ｎの計算に用いられる重み値を選択して、記憶部２１ｆ１ａ～２１ｆＮａに供給する（ステップＳ３）。

ΔＥ算出部２１のｈ伝搬制御部２１ｅは、ｘ_１～ｘ_Ｎ、インデックス＝１～Ｎ、及び、乱数生成回路２５ａ，２５ｂが出力するｍ，ｎに基づいて、ｈ_ｍ，ｈ_ｎの伝搬を行う（ステップＳ４）。前述のｈ伝搬制御部２１ｅの処理により、ΔＥ算出回路２１ｆ１～２１ｆＮのうち、値が０であるビットについてのローカルフィールド値がｈ更新回路２１ｄ１～ｄ１ｄＮの何れかから直接供給されるΔＥ算出回路には、ｈ伝搬制御部２１ｅによってｈ_ｍが供給される。また、値が１であるビットについてのローカルフィールド値がｈ更新回路２１ｄ１～ｄ１ｄＮの何れかから直接供給されるΔＥ算出回路には、ｈ伝搬制御部２１ｅによってｈ_ｎが供給される。

その後、ΔＥ算出回路２１ｆ１～２１ｆＮによる前述したようなΔＥ_１～ΔＥ_Ｎの計算が行われる（ステップＳ５）。そして、図６に示したような選択回路２２において、オフセット値の加算が行われたのち（ステップＳ６）、インデックス＝ｌの選択が行われる（ステップＳ７）。識別情報計算部２３は、前述の処理により、ｘ_ｌに応じて、インデックス＝ｍまたはインデックス＝ｎを出力する（ステップＳ８）。

その後、更新部２４は、記憶部２４ａに記憶されているｘ_ｌ及び、ｘ_ｍまたはｘ_ｎを更新し（ステップＳ９）、ΔＥ算出部２１のｈ更新回路２１ｄ１～２１ｄＮは、ｘ_ｌ及び、ｘ_ｍまたはｘ_ｎの更新に伴ってｈ_１～ｈ_Ｎを更新する（ステップＳ１０）。

その後、制御部２６は、状態の更新処理回数が、所定回数Ｎ１に達したか否か判定する（ステップＳ１１）。更新処理回数が所定回数Ｎ１に達していない場合には、ステップＳ２～Ｓ１０の処理が繰り返される。

更新処理回数が所定回数Ｎ１に達した場合、制御部２６は、Ｔの変更回数（温度変更回数）が、所定回数Ｎ２に達したか否かを判定する（ステップＳ１２）。
温度変更回数が所定回数Ｎ２に達していない場合、制御部２６は、Ｔを変更する（温度を下げる）（ステップＳ１３）。所定回数Ｎ１，Ｎ２、Ｔの値の変更の仕方（一度に値をどのくらい小さくするかなど）は、アニーリング条件に基づいて決定される。ステップＳ１３の処理後、ステップＳ２からの処理が繰り返される。

温度変更回数が所定回数Ｎ２に達している場合、制御部２６は、そのときの各ビットの値（変数ｘ_ｉ（ｉ＝１～Ｎ））を記憶部２４ａから取得して、解（計算結果）として制御装置２７に送信（出力）する（ステップＳ１４）。なお、制御部２６には、表示装置が接続されていてもよい。その場合、制御部２６は、表示装置に、計算結果が表示されるようにしてもよい。

また、更新部２４が、インデックス＝ｌとインデックス＝ｍまたはインデックス＝ｎに対応する２つのビットの値が変化することによるエネルギー変化に基づいてエネルギーを更新してもよい。また、更新部２４は、各更新時点での最小エネルギーとその最小エネルギーが得られたときの状態（最小エネルギー時の状態）とを保持するようにしてもよい。その場合、制御部２６は、温度変更回数が所定回数Ｎ２に達したときに、更新部２４が保持している最小エネルギー時の状態を取得して、解として出力してもよい。

以上のような、第２の実施の形態の最適化装置２０においても、第１の実施の形態の最適化装置１０と同様の効果が得られる。
図９は、第２の実施の形態の最適化装置を用いた場合の計算短縮効果を表すシミュレーション結果を示す図である。

横軸は状態の更新処理の繰り返し回数を表し、縦軸は正解に達したレプリカ数（最適化装置２０の数）を表す。
計算対象の問題は、車が８台、ルート数が８本の（６４ビットのイジングモデルで表せる）交通量最適化問題である。

図９には、比較のために、第２の実施の形態の最適化装置２０を用いた場合のシミュレーション結果４０とともに、ハミング距離＝１の遷移を繰り返しながらエネルギーを最小化する従来の最適化装置を用いた場合のシミュレーション結果４１が示されている。

図９のように、第２の実施の形態の最適化装置２０では、従来の最適化装置と比較して解の収束時間が１００倍以上短くなる。
以上、実施の形態に基づき、本発明の最適化装置及び最適化装置の制御方法の一観点について説明してきたが、これらは一例にすぎず、上記の記載に限定されるものではない。

１０ 最適化装置
１１ｉ，１１ｊ，１１Ｎ ΔＥ算出回路
１１ｉａ，１１ｊａ，１１Ｎａ，１４ａ 記憶部
１２ 選択回路
１３ 識別情報計算部
１４ 更新部
１５ａ，１５ｂ 乱数生成回路

Claims (5)

1. 計算対象の問題を変換したイジングモデルに含まれるＮ個（Ｎ＞２）のスピンに対応するＮ個のビットのうち、値が第１の値であるｋ個（ｋ＞１）の第１のビットの何れかについての第１のローカルフィールド値と、生成した第１の乱数に基づいて選択した値が第２の値である第２のビットについての第２のローカルフィールド値と、第１の記憶部に保持される前記ｋ個の第１のビットの何れかと前記第２のビットとの間の相互作用の大きさを示す第１の重み値とに基づいて、前記ｋ個の第１のビットの何れかの値と前記第２のビットの値とがそれぞれ変化することによる前記イジングモデルの第１のエネルギー変化をそれぞれ算出するｋ個の第１の算出回路と、
   前記Ｎ個のビットのうち、値が前記第２の値である（Ｎ－ｋ）個の第３のビットの何れかについての第３のローカルフィールド値と、生成した第２の乱数に基づいて選択した値が前記第１の値である第４のビットについての第４のローカルフィールド値と、第２の記憶部に保持される前記（Ｎ－ｋ）個の第３のビットと前記第４のビットとの間の相互作用の大きさを示す第２の重み値とに基づいて、前記（Ｎ－ｋ）個の第３のビットの何れかの値と前記第４のビットの値とがそれぞれ変化することによる前記イジングモデルの第２のエネルギー変化をそれぞれ算出する（Ｎ－ｋ）個の第２の算出回路と、
   入力される温度パラメータと、乱数とに基づいて決定される熱励起エネルギーと、前記ｋ個の第１の算出回路がそれぞれ出力する前記第１のエネルギー変化と、前記（Ｎ－ｋ）個の第２の算出回路がそれぞれ出力する前記第２のエネルギー変化とのそれぞれの大小関係に基づいて、値の更新を許容するビットを識別する第１のビット識別情報を出力する選択回路と、
   前記第１のビット識別情報に対応するビットの値に基づいて、前記第２のビットを識別する第２のビット識別情報、または、前記第４のビットを識別する第３のビット識別情報の何れかを出力する識別情報計算部と、
   前記第１のビット識別情報、及び、前記識別情報計算部が出力する前記第２のビット識別情報、または、前記第３のビット識別情報に基づいて、前記第１のビット識別情報に対応するビットの値、及び、前記第２のビット識別情報に対応するビットの値、または、前記第３のビット識別情報に対応するビットの値をそれぞれ更新する更新部と、
   を有する最適化装置。
2. 前記Ｎ個のビットのうちｋ個が、値が前記第１の値である前記ｋ個の第１のビット、前記Ｎ個のビットのうちの（Ｎ－ｋ）個が、値が前記第２の値である前記（Ｎ－ｋ）個の第３のビットとして初期設定される、請求項１に記載の最適化装置。
3. 前記第１の乱数と、前記第２の乱数と、前記Ｎ個のビットの値と、前記Ｎ個のビットのそれぞれを識別するビット識別情報とに基づいて、前記第２のローカルフィールド値を、前記ｋ個の第１の算出回路のそれぞれに伝搬し、前記第４のローカルフィールド値を、前記（Ｎ－ｋ）個の第２の算出回路に伝搬する伝搬制御部を有する請求項１または２に記載の最適化装置。
4. 前記第１の乱数と、前記第２の乱数と、前記Ｎ個のビットの何れかの値とに基づいて、前記第１の重み値を前記第１の記憶部に供給し、前記第２の重み値を前記第２の記憶部にそれぞれ供給する複数の選択回路を有する、請求項１乃至３の何れか一項に記載の最適化装置。
5. 計算対象の問題を変換したイジングモデルに含まれるＮ個（Ｎ＞２）のスピンに対応するＮ個のビットのうち、値が第１の値であるｋ個（ｋ＞１）の第１のビットの何れかについての第１のローカルフィールド値と、生成した第１の乱数に基づいて選択した値が第２の値である第２のビットについての第２のローカルフィールド値と、第１の記憶部に保持される前記ｋ個の第１のビットの何れかと前記第２のビットとの間の相互作用の大きさを示す第１の重み値とに基づいて、前記ｋ個の第１のビットの何れかの値と前記第２のビットの値とがそれぞれ変化することによる前記イジングモデルの第１のエネルギー変化をそれぞれ算出するｋ個の第１の算出回路と、前記Ｎ個のビットのうち、値が前記第２の値である（Ｎ－ｋ）個の第３のビットの何れかについての第３のローカルフィールド値と、生成した第２の乱数に基づいて選択した値が前記第１の値である第４のビットについての第４のローカルフィールド値と、第２の記憶部に保持される前記（Ｎ－ｋ）個の第３のビットと前記第４のビットとの間の相互作用の大きさを示す第２の重み値とに基づいて、前記（Ｎ－ｋ）個の第３のビットの何れかの値と前記第４のビットの値とがそれぞれ変化することによる前記イジングモデルの第２のエネルギー変化をそれぞれ算出する（Ｎ－ｋ）個の第２の算出回路と、入力される温度パラメータと、乱数とに基づいて決定される熱励起エネルギーと、前記ｋ個の第１の算出回路がそれぞれ出力する前記第１のエネルギー変化と、前記（Ｎ－ｋ）個の第２の算出回路がそれぞれ出力する前記第２のエネルギー変化とのそれぞれの大小関係に基づいて、値の更新を許容するビットを識別する第１のビット識別情報を出力する選択回路と、前記第１のビット識別情報に対応するビットの値に基づいて、前記第２のビットを識別する第２のビット識別情報、または、前記第４のビットを識別する第３のビット識別情報の何れかを出力する識別情報計算部と、前記第１のビット識別情報、及び、前記識別情報計算部が出力する前記第２のビット識別情報、または、前記第３のビット識別情報に基づいて、前記第１のビット識別情報に対応するビットの値、及び、前記第２のビット識別情報に対応するビットの値、または、前記第３のビット識別情報に対応するビットの値をそれぞれ更新する更新部と、制御部と、を有する最適化装置における前記制御部が、
   前記Ｎ個のビットのうちｋ個が、値が前記第１の値である前記ｋ個の第１のビット、前記Ｎ個のビットのうちの（Ｎ－ｋ）個が、値が前記第２の値である前記（Ｎ－ｋ）個の第３のビットとなるように、初期設定を行い、
   前記温度パラメータの大きさを制御する、
   最適化装置の制御方法。

Images