(57)【要約】【課題】ｋ−ｈｏｔ制約をもつ最適化問題の計算時間を短縮する。【解決手段】ｋ個（ｋ＞１）のΔＥ算出回路（ΔＥ算出回路１１ｉ，１１Ｎなど）のそれぞれは、イジングモデルのＮ個のビットのうち、値＝１のｋ個のビットの何れかと、乱数（ｎ）に基づき選択した値＝０のビットとが変化することによるエネルギー変化を算出し、（Ｎ−ｋ）個のΔＥ算出回路（ΔＥ算出回路１１ｊなど）のそれぞれは、値＝０の（Ｎ−ｋ）個のビットの何れかと、乱数（ｍ）に基づき選択した値＝１のビットとが変化することによるエネルギー変化を算出し、選択回路１２は、各エネルギー変化と熱励起エネルギーとの大小関係に基づいて、更新を許容するビットの識別情報（ｌ）を出力し、識別情報計算部１３は、ｌに対応するビットの値に基づき、乱数に基づき選択したビットの何れかの識別情報（ｎまたはｍ）を出力し、更新部１４は、ｌ及びｎまたはｍに対応するビットの値を更新する。【選択図】図１
2020064535.tif 000002
【特許請求の範囲】
【請求項１】
計算対象の問題を変換したイジングモデルに含まれるＮ個（Ｎ＞２）のスピンに対応するＮ個のビットのうち、値が１であるｋ個（ｋ＞１）の第１のビットの何れかについての第１のローカルフィールド値と、生成した第１の乱数に基づいて選択した値が０である第２のビットについての第２のローカルフィールド値と、第１の記憶部に保持される前記ｋ個の第１のビットの何れかと前記第２のビットとの間の相互作用の大きさを示す第１の重み値とに基づいて、前記ｋ個の第１のビットの何れかの値と前記第２のビットの値とがそれぞれ変化することによる前記イジングモデルの第１のエネルギー変化をそれぞれ算出するｋ個の第１の算出回路と、
前記Ｎ個のビットのうち、値が０である（Ｎ−ｋ）個の第３のビットの何れかについての第３のローカルフィールド値と、生成した第２の乱数に基づいて選択した値が１である第４のビットについての第４のローカルフィールド値と、第２の記憶部に保持される前記（Ｎ−ｋ）個の第３のビットと前記第４のビットとの間の相互作用の大きさを示す第２の重み値とに基づいて、前記（Ｎ−ｋ）個の第３のビットの何れかの値と前記第４のビットの値とがそれぞれ変化することによる前記イジングモデルの第２のエネルギー変化をそれぞれ算出する（Ｎ−ｋ）個の第２の算出回路と、
入力される温度パラメータと、乱数とに基づいて決定される熱励起エネルギーと、前記ｋ個の第１の算出回路がそれぞれ出力する前記第１のエネルギー変化と、前記（Ｎ−ｋ）個の第２の算出回路がそれぞれ出力する前記第２のエネルギー変化とのそれぞれの大小関係に基づいて、値の更新を許容するビットを識別する第１のビット識別情報を出力する選択回路と、
前記第１のビット識別情報に対応するビットの値に基づいて、前記第２のビットを識別する第２のビット識別情報、または、前記第４のビットを識別する第３のビット識別情報の何れかを出力する識別情報計算部と、
前記第１のビット識別情報、及び、前記識別情報計算部が出力する前記第２のビット識別情報、または、前記第３のビット識別情報に基づいて、前記第１のビット識別情報に対応するビットの値、及び、前記第２のビット識別情報に対応するビットの値、または、前記第３のビット識別情報に対応するビットの値をそれぞれ更新する更新部と、
を有する最適化装置。
【請求項２】
前記Ｎ個のビットのうちｋ個が、値が１である前記ｋ個の第１のビット、前記Ｎ個のビットのうちの（Ｎ−ｋ）個が、値が０である前記（Ｎ−ｋ）個の第３のビットとして初期設定される、請求項１に記載の最適化装置。
【請求項３】
前記第１の乱数と、前記第２の乱数と、前記Ｎ個のビットの値と、前記Ｎ個のビットのそれぞれを識別するビット識別情報とに基づいて、前記第２のローカルフィールド値を、前記ｋ個の第１の算出回路のそれぞれに伝搬し、前記第４のローカルフィールド値を、前記（Ｎ−ｋ）個の第２の算出回路に伝搬する伝搬制御部を有する請求項１または２に記載の最適化装置。
【請求項４】
前記第１の乱数と、前記第２の乱数と、前記Ｎ個のビットの何れかの値とに基づいて、前記第１の重み値を前記第１の記憶部に供給し、前記第２の重み値を前記第２の記憶部にそれぞれ供給する複数の選択回路を有する、請求項１乃至３の何れか一項に記載の最適化装置。
【請求項５】
計算対象の問題を変換したイジングモデルに含まれるＮ個（Ｎ＞２）のスピンに対応するＮ個のビットのうち、値が１であるｋ個（ｋ＞１）の第１のビットの何れかについての第１のローカルフィールド値と、生成した第１の乱数に基づいて選択した値が０である第２のビットについての第２のローカルフィールド値と、第１の記憶部に保持される前記ｋ個の第１のビットの何れかと前記第２のビットとの間の相互作用の大きさを示す第１の重み値とに基づいて、前記ｋ個の第１のビットの何れかの値と前記第２のビットの値とがそれぞれ変化することによる前記イジングモデルの第１のエネルギー変化をそれぞれ算出するｋ個の第１の算出回路と、前記Ｎ個のビットのうち、値が０である（Ｎ−ｋ）個の第３のビットの何れかについての第３のローカルフィールド値と、生成した第２の乱数に基づいて選択した値が１である第４のビットについての第４のローカルフィールド値と、第２の記憶部に保持される前記（Ｎ−ｋ）個の第３のビットと前記第４のビットとの間の相互作用の大きさを示す第２の重み値とに基づいて、前記（Ｎ−ｋ）個の第３のビットの何れかの値と前記第４のビットの値とがそれぞれ変化することによる前記イジングモデルの第２のエネルギー変化をそれぞれ算出する（Ｎ−ｋ）個の第２の算出回路と、入力される温度パラメータと、乱数とに基づいて決定される熱励起エネルギーと、前記ｋ個の第１の算出回路がそれぞれ出力する前記第１のエネルギー変化と、前記（Ｎ−ｋ）個の第２の算出回路がそれぞれ出力する前記第２のエネルギー変化とのそれぞれの大小関係に基づいて、値の更新を許容するビットを識別する第１のビット識別情報を出力する選択回路と、前記第１のビット識別情報に対応するビットの値に基づいて、前記第２のビットを識別する第２のビット識別情報、または、前記第４のビットを識別する第３のビット識別情報の何れかを出力する識別情報計算部と、前記第１のビット識別情報、及び、前記識別情報計算部が出力する前記第２のビット識別情報、または、前記第３のビット識別情報に基づいて、前記第１のビット識別情報に対応するビットの値、及び、前記第２のビット識別情報に対応するビットの値、または、前記第３のビット識別情報に対応するビットの値をそれぞれ更新する更新部と、制御部と、を有する最適化装置における前記制御部が、
前記Ｎ個のビットのうちｋ個が、値が１である前記ｋ個の第１のビット、前記Ｎ個のビットのうちの（Ｎ−ｋ）個が、値が０である前記（Ｎ−ｋ）個の第２のビットとなるように、初期設定を行い、
前記温度パラメータの大きさを制御する、
最適化装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適化装置及び最適化装置の制御方法に関する。
【背景技術】
【０００２】
ノイマン型コンピュータが不得意とする多変数の最適化問題を解く方法として、イジング型のエネルギー関数を用いた最適化装置（イジングマシンまたはボルツマンマシンと呼ばれる場合もある）がある。最適化装置は、計算対象の問題を、磁性体のスピンの振る舞いを表すモデルであるイジングモデルに置き換えて計算する。
【０００３】
最適化装置は、たとえば、ニューラルネットワークを用いてモデル化することもできる。その場合、イジングモデルに含まれる複数のスピンに対応した複数のビットのそれぞれが、他のビットの値と、他のビットと自身のビットとの相互作用の大きさを示す重み値（結合係数とも呼ばれる）とに応じて０または１を出力するニューロンとして機能する。最適化装置は、たとえば、シミュレーテッド・アニーリングなどの確率的探索法により、上記のようなエネルギー関数（コスト関数、目的関数とも呼ばれる）の値（以下エネルギーという）の最小値が得られる状態（各ビットの値の組み合わせ）を、解として求める。
【０００４】
従来、デジタル回路を用いてシミュレーテッド・アニーリングを行うことでエネルギーが最小となる状態を計算する最適化装置がある（たとえば、特許文献１参照）。従来の最適化装置は、一度に１つのビットの値だけ変化するとしてエネルギー変化を計算し、そのエネルギー変化に対して温度に対応するノイズ値を加えた値に応じてビットの変化を許容するか否かを決定する。エネルギーが増加するビットの値の変化も所定の確率で許容され、温度が低くなるにつれてその確率は低くなる。
【０００５】
ところで、最適化問題には、全ビットの中で値が１になるビットの数をｋ（＞１）個とする制約（ｋ−ｈｏｔ制約）をもつものがある。たとえば、多くのパーティショニング問題（グラフ分割問題など、与えられたＮ個の選択肢から最適なｋ個を選ぶ、という問題）、交通量最適化問題などは、ｋ−ｈｏｔ制約をもつ。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１８−０４１３５１号公報
【特許文献２】特開２０１６−１０３２８２号公報
【特許文献３】特開平１０−２４７１８６号公報
【特許文献４】特開平８−５０５７２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記のように、従来の最適化装置では一度に変化するビットの数は１つである。つまり、従来の最適化装置は、ハミング距離＝１の状態遷移を繰り返しながらエネルギーが最小となる基底状態の探索を行う。そのため、従来の最適化装置では、ｋ−ｈｏｔ制約を満たさない状態への遷移も発生し、遷移が起こりうる状態の数（探索空間）がｋ−ｈｏｔ制約を満たす状態の数よりも大きい。また、ｋ−ｈｏｔ制約項のために生じるエネルギー障壁のために状態遷移に時間がかかる。以上のことから、従来の最適化装置では、ｋ−ｈｏｔ制約をもつ最適化問題の計算（基底状態の探索）に時間がかかるという問題がある。
【０００８】
１つの側面では、本発明は、ｋ−ｈｏｔ制約をもつ最適化問題の計算時間を短縮可能な最適化装置及び最適化装置の制御方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
１つの実施態様では、計算対象の問題を変換したイジングモデルに含まれるＮ個（Ｎ＞２）のスピンに対応するＮ個のビットのうち、値が１であるｋ個（ｋ＞１）の第１のビットの何れかについての第１のローカルフィールド値と、生成した第１の乱数に基づいて選択した値が０である第２のビットについての第２のローカルフィールド値と、第１の記憶部に保持される前記ｋ個の第１のビットの何れかと前記第２のビットとの間の相互作用の大きさを示す第１の重み値とに基づいて、前記ｋ個の第１のビットの何れかの値と前記第２のビットの値とがそれぞれ変化することによる前記イジングモデルの第１のエネルギー変化をそれぞれ算出するｋ個の第１の算出回路と、前記Ｎ個のビットのうち、値が０である（Ｎ−ｋ）個の第３のビットの何れかについての第３のローカルフィールド値と、生成した第２の乱数に基づいて選択した値が１である第４のビットについての第４のローカルフィールド値と、第２の記憶部に保持される前記（Ｎ−ｋ）個の第３のビットと前記第４のビットとの間の相互作用の大きさを示す第２の重み値とに基づいて、前記（Ｎ−ｋ）個の第３のビットの何れかの値と前記第４のビットの値とがそれぞれ変化することによる前記イジングモデルの第２のエネルギー変化をそれぞれ算出する（Ｎ−ｋ）個の第２の算出回路と、入力される温度パラメータと、乱数とに基づいて決定される熱励起エネルギーと、前記ｋ個の第１の算出回路がそれぞれ出力する前記第１のエネルギー変化と、前記（Ｎ−ｋ）個の第２の算出回路がそれぞれ出力する前記第２のエネルギー変化とのそれぞれの大小関係に基づいて、値の更新を許容するビットを識別する第１のビット識別情報を出力する選択回路と、前記第１のビット識別情報に対応するビットの値に基づいて、前記第２のビットを識別する第２のビット識別情報、または、前記第４のビットを識別する第３のビット識別情報の何れかを出力する識別情報計算部と、前記第１のビット識別情報、及び、前記識別情報計算部が出力する前記第２のビット識別情報、または、前記第３のビット識別情報に基づいて、前記第１のビット識別情報に対応するビットの値、及び、前記第２のビット識別情報に対応するビットの値、または、前記第３のビット識別情報に対応するビットの値をそれぞれ更新する更新部と、を有する最適化装置が提供される。
【００１０】
また、１つの実施態様では、最適化装置の制御方法が提供される。
【発明の効果】
【００１１】
１つの側面では、ｋ−ｈｏｔ制約をもつ最適化問題の計算時間を短縮できる。
【図面の簡単な説明】
【００１２】
【図１】第１の実施の形態の最適化装置の一例を示す図である。
【図２】第２の実施の形態の最適化装置の一例を示す図である。
【図３】ΔＥ算出部の一例を示す図である。
【図４】ｈ伝搬制御部の一例を示す図である。
【図５】ｈ伝搬制御部の他の例を示す図である。
【図６】選択回路の一例を示す図である。
【図７】識別情報計算部の一例を示す図である。
【図８】第２の実施の形態の最適化装置の一例の処理の流れを示すフローチャートである。
【図９】第２の実施の形態の最適化装置を用いた場合の計算短縮効果を表すシミュレーション結果を示す図である。
【発明を実施するための形態】
【００１３】
以下、発明を実施するための形態を、図面を参照しつつ説明する。
以下に示す最適化装置は、ｋ−ｈｏｔ制約を満たす状態以外の状態の探索を除外することで、ｋ−ｈｏｔ制約をもつ最適化問題の計算時間を短縮するものである。
【００１４】
計算対象の問題を変換したイジングモデルに含まれる複数のスピン（スピン数＝Ｎ（Ｎ＞２））に対応するＮ個のビットの値を、状態変数であるｘ１〜ｘＮで表す場合、値が１になる状態変数の数がｋ（＞１）個であるときにｋ−ｈｏｔ制約が満たされる。
【００１５】
たとえば、説明を簡略化するためにＮ＝３、ｋ＝２とした場合、（ｘ１，ｘ２，ｘ３）＝（０，１，１），（１，０，１），（１，１，０）という状態は、２−ｈｏｔ制約を満たす。一方、（ｘ１，ｘ２，ｘ３）＝（０，０，０），（０，０，１），（０，１，０），（１，０，０），（１，１，１）という状態は、２−ｈｏｔ制約を満たさない。
【００１６】
ｋ−ｈｏｔ制約を満たすある状態から、ｋ−ｈｏｔ制約を満たす別の状態に遷移させるためには、最適化装置は、１回の状態更新処理において値が１のビットと値が０のビットをそれぞれ１つずつ変化させることになる。つまり、最適化装置は、ハミング距離＝２の状態遷移を発生させることになる。
【００１７】
ｋ−ｈｏｔ制約は、以下の式（１）で表すことができる。
【００１８】
【数１】
2020064535.tif 000003
【００１９】
ｘｉは、インデックス（ビット識別情報）＝ｉに対応するビットの値を表す状態変数である。
ｋ−ｈｏｔ制約を考慮した最適化問題のエネルギー関数は、以下の式（２）のように表すことができる。
【００２０】
【数２】
2020064535.tif 000004
【００２１】
式（２）において、右辺の１項目はコスト関数、２項目はｋ−ｈｏｔ制約を考慮したｋ−ｈｏｔ制約項、３項目以降はその他の制約を考慮した制約項を表す。ｋ−ｈｏｔ制約が満たされない場合に、エネルギーが小さくなる、ということが起きないように、λ１（制約重み）として十分大きな値が用いられることになる。
【００２２】
一方、重み値を用いたイジング型のエネルギー関数Ｅ（ｘ）は、たとえば、以下の式（３）で定義される。
【００２３】
【数３】
2020064535.tif 000005
【００２４】
右辺の１項目は、イジングモデルに含まれる全ビットから選択可能な２つのビットの全組み合わせについて、漏れと重複なく、２つのビットの値（０または１）と重み値との積を積算したものである。ｘｊは、インデックス＝ｊに対応するビットの値を表す状態変数であり、Ｗｉｊは、インデックス＝ｉ，ｊに対応するビットの相互作用の大きさを示す重み値である。なお、Ｗｉｉ＝０である。また、Ｗｉｊ＝Ｗｊｉであることが多い（つまり、重み値による係数行列は対称行列である場合が多い）。
【００２５】
右辺の２項目は、全ビットのそれぞれのバイアス値とビットの値との積の総和を求めたものである。ｂｉは、インデックス＝ｉに対応するビットのバイアス値を示している。
ｋ−ｈｏｔ制約を満たす状態以外についても探索が行われる場合、式（３）のＷｉｊを表現するためのビット数は、式（２）のλ１の値が大きいほど大きくなる。λ１は、たとえば、上記のＮ（問題のサイズに相当する）や、Ｗｉｊとのバランスをみて決定される。たとえば、最初はＷｉｊの最大値の１０倍程度のλ１を用いてＷｉｊやｂｉが計算され、エネルギーの最小化が行われる。収束解がｋ−ｈｏｔ制約を満たしていなければ、ｋ−ｈｏｔ制約を満たすようになるまで、λ１の値が増加される。
【００２６】
一方、ｋ−ｈｏｔ制約を満たす状態のみの探索が行われる場合、式（２）の右辺の２項目のｋ−ｈｏｔ制約項をなくせるため、Ｗｉｊを表現するためのビット数を少なくできる。
【００２７】
ところで、式（３）において、ｘｉの値が変化して１−ｘｉとなると、ｘｉの増加分は、Δｘｉ＝（１−ｘｉ）−ｘｉ＝１−２ｘｉと表せる。この値の変化に伴うエネルギー変化（ΔＥｉ）は、以下の式（４）で表される。
【００２８】
【数４】
2020064535.tif 000006
【００２９】
式（４）において、ｘｉが１から０に変化するとき、Δｘｉは−１となり、ｘｉが０から１に変化するとき、Δｘｉは１となる。なお、ｈｉはローカルフィールド値（局所場）と呼ばれ、Δｘｉに応じてｈｉに符号（＋１または−１）を乗じたものがΔＥｉである。
【００３０】
ｘｊが０から１に変化するときのｈｉの変化分は、Δｈｉ（ｊ）＝＋Ｗｉｊ、ｘｊが１から０に変化するときのｈｉの変化分は、Δｈｉ（ｊ）＝−Ｗｉｊである。同様に、ｘｉが変化したときのインデックス＝ｊに対応するビットについてのｈｊの変化分は、Δｈｊ（ｉ）＝ΔｘｉＷｉｊ、と表せる。
【００３１】
したがって、ｘｉ，ｘｊが両方変化したときのエネルギー変化は、以下の式（５）で表せる。
【００３２】
【数５】
2020064535.tif 000007
【００３３】
前述のように、ｋ−ｈｏｔ制約を満たすある状態から、ｋ−ｈｏｔ制約を満たす別の状態に遷移するには、値が１のビットと値が０のビットをそれぞれ１つずつ変化させることになる。インデックス＝ｉに対応するビットの値が１から０に変化するとともにインデックス＝ｊに対応するビットの値が０から１に変化する場合のエネルギー変化をΔＥｊと表記すると、Δｘｉ＝−１、Δｘｊ＝１であるため、式（５）からΔＥｊは以下の式（６）で表せる。
【００３４】
【数６】
2020064535.tif 000008
【００３５】
以下に示す最適化装置は、式（６）で表されるエネルギー変化の計算を行う回路を含む。
（第１の実施の形態）
図１は、第１の実施の形態の最適化装置の一例を示す図である。
【００３６】
最適化装置１０は、Ｎ個のΔＥ算出回路（たとえば、図１のΔＥ算出回路１１ｉ，１１ｊ，１１Ｎを含む）、選択回路１２、識別情報計算部１３、更新部１４、乱数生成回路１５ａ，１５ｂを有する。
【００３７】
Ｎ個のΔＥ算出回路のうち、ｋ個（ｋ＞１）のΔＥ算出回路（図１の例ではΔＥ算出回路１１ｉ，１１Ｎなど）は、以下のような処理を行う。
ｋ個のΔＥ算出回路のそれぞれには、Ｎ個のビットのうち、値が１であるｋ個のビットの何れかについてのローカルフィールド値（たとえば、ｈｉ，ｈＮ）が供給される。さらにｋ個のΔＥ算出回路のそれぞれには、生成した乱数（ｎ）に基づいて選択した値が０であるビット（インデックス＝ｎに対応するビット）についてのローカルフィールド値（ｈｎ）が供給される。なお、図１では、ローカルフィールド値を計算する回路や、ローカルフィールド値のΔＥ算出回路への伝搬制御を行う回路などについては、図示が省略されている。
【００３８】
また、ｋ個のΔＥ算出回路のそれぞれは、ｋ個のビットの何れかと、インデックス＝ｎに対応するビットとの間の相互作用の大きさを示す重み値を記憶する記憶部（たとえば、記憶部１１ｉａ，１１Ｎａ）を有する。そして、ｋ個のΔＥ算出回路のそれぞれは、供給される２つのローカルフィールド値と重み値とに基づいて、ｋ個のビットの何れかと、インデックス＝ｎに対応するビットの値がそれぞれ変化することによるイジングモデルのエネルギー変化を算出する。
【００３９】
たとえば、ｋ個のΔＥ算出回路のうちの１つであるΔＥ算出回路１１ｉには、値が１であるインデックス＝ｉに対応するビットについてのｈｉと、ｈｎが供給される。また、ΔＥ算出回路１１ｉの記憶部１１ｉａは、Ｗｎｉを記憶する。そして、ΔＥ算出回路１１ｉは、ｈｉ，ｈｎ，Ｗｎｉに基づいて、インデックス＝ｉに対応するビットと、インデックス＝ｎに対応するビットとがそれぞれ変化することによるエネルギー変化（ΔＥｉ）を算出する。ΔＥｉは、式（６）において、ｈｊ＝ｈｎ、Ｗｉｊ＝Ｗｎｉ（ただし、Ｗｎｉ＝Ｗｉｎ）の場合であるから、ΔＥｉ＝ｈｉ−ｈｎ＋Ｗｎｉと表せる。
【００４０】
同様に、ｋ個のΔＥ算出回路のうちの１つであるΔＥ算出回路１１Ｎには、値が１であるインデックス＝Ｎに対応するビットについてのｈＮと、ｈｎが供給される。また、ΔＥ算出回路１１Ｎの記憶部１１Ｎａは、ＷｎＮを記憶する。そして、ΔＥ算出回路１１Ｎは、ｈＮ、ｈｎ、ＷｎＮに基づいて、インデックス＝Ｎに対応するビットと、インデックス＝ｎに対応するビットとがそれぞれ変化することによるエネルギー変化（ΔＥＮ）を算出する。ΔＥＮは、式（６）において、ｈｊ＝ｈｎ、Ｗｉｊ＝ＷｎＮ（ただし、ＷｎＮ＝ＷＮｎ）の場合であるから、ΔＥＮ＝ｈＮ−ｈｎ＋ＷｎＮと表せる。
【００４１】
一方、Ｎ個のΔＥ算出回路のうち、（Ｎ−ｋ）個のΔＥ算出回路（図１の例ではΔＥ算出回路１１ｊなど）は、以下のような処理を行う。
（Ｎ−ｋ）個のΔＥ算出回路のそれぞれには、Ｎ個のビットのうち、値が０であるビットについてのローカルフィールド値（たとえば、ｈｊ）が供給される。さらに、（Ｎ−ｋ）個のΔＥ算出回路のそれぞれには、生成した乱数（ｍ）に基づいて選択した値が１であるビット（インデックス＝ｍに対応するビット）についてのローカルフィールド値（ｈｍ）が供給される。なお、ｍは、ｎとは異なるシードを用いて生成される乱数である。
【００４２】
また、（Ｎ−ｋ）個のΔＥ算出回路のそれぞれは、値が０の（Ｎ−ｋ）個のビットの何れかと、インデックス＝ｍに対応するビットとの間の相互作用の大きさを示す重み値を記憶する記憶部（たとえば、記憶部１１ｊａ）を有する。そして、（Ｎ−ｋ）個のΔＥ算出回路のそれぞれは、供給される２つのローカルフィールド値と重み値とに基づいて、（Ｎ−ｋ）個のビットの何れかと、インデックス＝ｍに対応するビットとがそれぞれ変化することによるイジングモデルのエネルギー変化を算出する。
【００４３】
たとえば、ΔＥ算出回路１１ｊには、値が０であるインデックス＝ｊに対応するビットについてのｈｊと、ｈｍが供給される。また、ΔＥ算出回路１１ｊの記憶部１１ｊａは、Ｗｍｊを記憶する。そして、ΔＥ算出回路１１ｊは、ｈｊ、ｈｍ、Ｗｍｊに基づいて、インデックス＝ｊに対応するビットと、インデックス＝ｍに対応するビットとがそれぞれ変化することによるエネルギー変化（ΔＥｊ）を算出する。ΔＥｊは、式（６）において、ｈｉ＝ｈｍ、Ｗｉｊ＝Ｗｍｊの場合であるから、ΔＥｊ＝−ｈｊ＋ｈｍ＋Ｗｍｊと表せる。
【００４４】
なお、Ｎ個のΔＥ算出回路は、たとえば、加算器や減算器を用いて実現される。また、ΔＥ算出回路が有する記憶部は、たとえば、レジスタやＳＲＡＭ（Static Random Access Memory）などを用いて実現される。
【００４５】
選択回路１２は、熱励起エネルギーと、Ｎ個のΔＥ算出回路がそれぞれ出力するエネルギー変化との大小関係に基づいて、値の更新を許容するビットを識別するインデックス＝ｌを出力する。熱励起エネルギーは、乱数と、図示しない制御部から入力される温度パラメータ（Ｔ）に基づいて決定される。
【００４６】
シミュレーテッド・アニーリングが行われる場合、Ｔは、たとえば、制御部によって、イジングモデルの状態を更新する処理が、所定回数繰り返されるごとに、値が小さくなるように制御される。なお、上記のような選択回路１２の機能を実行する回路例については後述する。
【００４７】
識別情報計算部１３は、選択回路１２が出力するインデックス＝ｌに対応するビットの値（ｘｌ）に基づいて、インデックス＝ｍまたはインデックス＝ｎの何れかを出力する。ｍ，ｎは、乱数生成回路１５ａ，１５ｂから供給される。ｘｌが０である場合、値が１であるビットのインデックス＝ｍが出力される。ｘｌが１である場合、値が０であるビットのインデックス＝ｎが出力される。識別情報計算部１３は、たとえば、セレクタによって実現できる。
【００４８】
なお、図１の例では、識別情報計算部１３は、インデックス＝ｌも出力しているが、選択回路１２が出力するインデックス＝ｌが直接、更新部１４に供給される場合には、識別情報計算部１３は、インデックス＝ｌを出力しなくてもよい。
【００４９】
更新部１４は、Ｎ個のビットの値（ｘ１〜ｘＮ）の値を保持する記憶部１４ａを有している。記憶部１４ａは、たとえば、レジスタやＳＲＡＭなどを用いて実現される。更新部１４は、インデックス＝ｌ、及び、インデックス＝ｍまたはインデックス＝ｎに基づいて、ｘｌ及び、インデックス＝ｍに対応するビットの値（ｘｍ）またはインデックス＝ｎに対応するビットの値（ｘｎ）をそれぞれ更新する。
【００５０】
なお、図１では図示が省略されているが、インデックス＝ｌ，ｍ，ｎは、さらに、各ビットについてのローカルフィールド値を更新するために用いられる。
乱数生成回路１５ａは、ｘ１〜ｘＮに基づいて、Ｎ個のビットのうち、値が０のビットのインデックスの１つである乱数（ｎ）を出力する。乱数生成回路１５ａは、たとえば、ｘ１〜ｘＮのうち、値が０である（Ｎ−ｋ）個のビットのインデックスを出力する回路と、出力された（Ｎ−ｋ）個のインデックスのうちの何れか１つを、乱数を用いて選択する回路と、その乱数を生成する回路により実現される。乱数を生成する回路としては、たとえば、ＬＦＳＲ（Linear Feedback Shift Register）がある。
【００５１】
乱数生成回路１５ｂは、ｘ１〜ｘＮに基づいて、Ｎ個のビットのうち、値が１のビットのインデックスの１つである乱数（ｍ）を出力する。乱数生成回路１５ｂは、たとえば、ｘ１〜ｘＮのうち、値が１であるｋ個のビットのインデックスを出力する回路と、出力されたｋ個のインデックスのうちの何れか１つを、乱数を用いて選択する回路と、その乱数を生成する回路により実現される。
【００５２】
以下、最適化装置１０の動作例を説明する。
まず、初期設定が行われる。初期設定は、たとえば、図示しない制御部の制御のもとｘ１〜ｘＮを全て０に設定した後に、乱数を用いて、ｋ個のビットの値を１に設定し、その他のビットの値を０に設定する処理やローカルフィールド値の初期設定を含む。
【００５３】
その後、乱数生成回路１５ａ，１５ｂは、ｎ，ｍを出力する。これによって、図１では図示が省略されているが、ｈｎを更新する回路から、ｋ個のΔＥ算出回路に対してｈｎが供給され、ｈｍを更新する回路から、Ｎ−ｋ個のΔＥ算出回路に対してｈｍが供給される。
【００５４】
また、全ての重み値を記憶している記憶部（図示せず）から、値が１のビットのそれぞれと、インデックス＝ｎに対応するビットとの間の相互作用の大きさを示す重み値のそれぞれが、ｋ個のΔＥ算出回路のうち、対応するΔＥ算出回路の記憶部に供給される。たとえば、図１に示すようにＷｎｉは、ΔＥ算出回路１１ｉの記憶部１１ｉａに供給され、ＷｎＮは、ΔＥ算出回路１１Ｎの記憶部１１Ｎａに供給される。
【００５５】
また、全ての重み値を記憶している記憶部から、値が０のビットのそれぞれと、インデックス＝ｍに対応するビットとの間の相互作用の大きさを示す重み値のそれぞれが、（Ｎ−ｋ）個のΔＥ算出回路のうち、対応するΔＥ算出回路の記憶部に供給される。たとえば、図１に示すようにＷｍｊは、ΔＥ算出回路１１ｊの記憶部１１ｊａに供給される。
【００５６】
そして、ｋ個のΔＥ算出回路と（Ｎ−ｋ）個のΔＥ算出回路は、前述のようなエネルギー変化を算出し、選択回路１２は、Ｎ個のビットの中から、値の更新を許容するビットを識別するインデックス＝１を出力する。
【００５７】
識別情報計算部１３は、ｘｌが０である場合、乱数生成回路１５ｂから供給されるｍをインデックスとして出力し、ｘｌが１である場合、乱数生成回路１５ａから供給されるｎを、インデックスとして出力する。
【００５８】
更新部１４は、インデックス＝ｌ、及び、インデックス＝ｍまたはインデックス＝ｎに基づいて、ｘｌ及び、ｘｍまたはｘｎをそれぞれ更新する。
図１には、状態の更新例が示されている。たとえば、初期設定処理により、ｘ１〜ｘＮのうち、ｘｉ，ｘＮを含むｋ個が１、ｘ１，ｘｊを含む（Ｎ−ｋ）個が０である状態（初期状態）となっている。選択回路１２が出力するインデックス＝ｌがインデックス＝ｉと等しい場合、識別情報計算部１３は、ｘｉが１であるため、ｎをインデックスとして出力する。ｎ＝１である場合、更新部１４は、ｘ１を０から１に更新するとともに、ｘｉを１から０に更新する。インデックス＝ｌがインデックス＝ｊと等しい場合、識別情報計算部１３は、ｘｊが０であるため、ｍをインデックスとして出力する。ｍ＝Ｎの場合、更新部１４は、ｘＮを１から０に更新するとともに、ｘｊを０から１に更新する。
【００５９】
何れの場合も、値が１である１つのビットと、値が０である１つのビットとがそれぞれ更新されるため、更新後の状態もｋ−ｈｏｔ制約を満たす。このように、ｋ−ｈｏｔ制約を満たした状態間での遷移が可能となる。
【００６０】
なお、ｘｉが１から０に更新された場合、ΔＥ算出回路１１ｉは、（Ｎ−ｋ）個のΔＥ算出回路の１つとなる。そして、乱数生成回路１５ａ，１５ｂにて新たにｎ，ｍが生成された後、ΔＥ算出回路１１ｉにはｈｍが供給され、記憶部１１ｉａにはＷｍｉが記憶される。また、ｘｊが０から１に更新された場合、ΔＥ算出回路１１ｊは、ｋ個のΔＥ算出回路の１つとなる。そして、乱数生成回路１５ａ，１５ｂにて新たにｎ，ｍが出力された後、ΔＥ算出回路１１ｊにはｈｎが供給され、記憶部１１ｊａにはＷｎｊが記憶される。
【００６１】
上記のように、Ｎ個のΔＥ算出回路のうち、ｈｍ，ｈｎが供給されるΔＥ算出回路は、ｘ１〜ｘＮが更新されるたびに変わる。また、ΔＥ算出回路内の記憶部に記憶される重み値も更新される。
【００６２】
ｈｍ，ｈｎの供給先の変更や、重み値の更新が行われた後、同様に、Ｎ個のΔＥ算出回路にてエネルギー変化が計算される。その後、選択回路１２、識別情報計算部１３、更新部１４にて上記と同様の処理が行われる。このような状態更新処理が所定の繰り返し回数、繰り返されたのちに得られた状態（ｘ１〜ｘＮ）が、たとえば、最適化問題に対する解として出力される。
【００６３】
なお、更新部１４は、ｘｌ及び、ｘｍまたはｘｎが変化することによるエネルギー変化に基づいてエネルギーを更新してもよい。また、更新部１４は、各更新時点での最小エネルギーとその最小エネルギーが得られたときの状態（最小エネルギー時の状態）とを保持するようにしてもよい。その場合、更新部１４は、状態更新処理が所定の繰り返し回数、繰り返されたときに保持している最小エネルギー時の状態を、解として出力してもよい。
【００６４】
以上のように、第１の実施の形態の最適化装置１０は、全ビット（Ｎ個のビット）の中で、値が０と１のビットがそれぞれ１つずつ共に変化するときのエネルギー変化に基づいて、どの２つのビットの遷移を許容するかを決定する。そして最適化装置１０は、一度の状態更新処理において、その決定した２つのビットの値を更新する。これによって、ｋ−ｈｏｔ制約を満たさない状態遷移が抑制され、探索空間を小さくできる。このため、基底状態の探索を高速化することができる。
【００６５】
たとえば、Ｎ＝１０２４で、ｋ＝３２の場合、全状態数が２１０２４、すなわちほぼ１０３０７であるのに対して、ｋ−ｈｏｔ制約を満たす状態数は、１０２４！／（１０２４−３２）！（“！”は階乗を表す）、すなわちほぼ１０９６となる。つまり、２１０２４の状態を探索する場合に比べて、探索する状態数が１／１０２１１と少なくなる。
【００６６】
また、最適化装置１０によれば、式（２）の右辺の２項目のｋ−ｈｏｔ制約項をなくせるため、ｋ−ｈｏｔ制約項のために生じるエネルギー障壁を小さくでき、状態遷移の時間を短縮できる。
【００６７】
また、前述のように式（２）の右辺の２項目のｋ−ｈｏｔ制約項をなくせるため、重み値を表現するためのビット数を減らせることができ、重み値を記憶しておくためのハードウェア量を削減できる。
【００６８】
たとえば、最適化装置１０が交通量最適化問題を計算するとき、Ｎ＝１６、λ１＝１００とした場合、重み値の範囲は、４≦Ｗｉｊ≦２１４となる。これに対して、式（２）の右辺の２項目のｋ−ｈｏｔ制約項をなくせる場合（つまりλ１＝０の場合）、重み値の範囲は、４≦Ｗｉｊ≦１４となる。つまり、重み値を表現するためのビット数を、８ビットから４ビットに減少させることができる。また、問題の規模が大きくなって、たとえば、Ｎ＝１０２４、λ１＝１００００である場合、重み値の範囲は、４≦Ｗｉｊ≦２０１０８となる。これに対して、λ１＝０の場合、重み値の範囲は、４≦Ｗｉｊ≦１０８となる。つまり、重み値を表現するためのビット数を、１６ビットから７ビットに減少させることができる。
【００６９】
このように、問題の規模が大きくなるほど、重み値のビット数の削減効果はより顕著となる。
なお、Ｎ−ｋ＞２またはｋ＞２である場合、（Ｎ−ｋ）ｋ＞Ｎとなり、ｋ−ｈｏｔ制約を満たす状態は、一般的にＮよりも大きい。しかし、上記の最適化装置１０では、乱数であるｎ，ｍを用いて、Ｎ通りの状態遷移候補から１つの状態遷移が実施されるため、Ｎビットに対応した最適化装置１０を用いた処理が可能である。
【００７０】
（第２の実施の形態）
図２は、第２の実施の形態の最適化装置の一例を示す図である。
最適化装置２０は、ΔＥ算出部２１、選択回路２２、識別情報計算部２３、更新部２４、乱数生成回路２５ａ，２５ｂ、制御部２６を有する。
【００７１】
ΔＥ算出部２１は、ハミング距離＝２の状態遷移によってｋ−ｈｏｔ制約を満たすある状態からｋ−ｈｏｔ制約を満たす別の状態に遷移するときのエネルギー変化（ΔＥ１〜ΔＥＮ）を算出する。
【００７２】
選択回路２２は、熱励起エネルギーと、ΔＥ１〜ΔＥＮとの大小関係に基づいて、Ｎ個のビットのうち、値の更新を許容する１つのビットを識別するインデックス＝ｌを出力する。熱励起エネルギーは、乱数と、制御部２６から入力されるＴに基づいて決定される。なお、熱励起エネルギーと、ΔＥ１〜ΔＥＮとの大小関係によっては、Ｎ個のビットのうち、１つも更新が許容されない場合がある。選択回路２２は、更新が許容されたか否かを示すフラグについても出力するものとする。
【００７３】
識別情報計算部２３は、選択回路２２が出力するインデックス＝ｌに対応するビットの値（ｘｌ）に基づいて、インデックス＝ｍまたはインデックス＝ｎの何れかを出力する。ｎ，ｍは、乱数生成回路２５ａ，２５ｂから供給される。ｘｌが０である場合、値が１であるビットのインデックス＝ｍが出力される。ｘｌが１である場合、値が０であるビットのインデックス＝ｎが出力される。以下では、識別情報計算部２３は、選択回路２２から供給されるインデックス＝ｌとフラグについても出力するものとする。インデックス＝ｌ，ｍ，ｎは、ΔＥ算出部２１に供給され、エネルギー変化を計算するために用いられる各ビットについてのローカルフィールド値を更新する際に用いられる。
【００７４】
なお、フラグが更新を許容しないことを示す値である場合、識別情報計算部２３は、たとえば、インデックス＝ｌ，ｍ，ｎを無効な値（たとえば、０）とする。
更新部２４は、Ｎ個のビットの値（ｘ１〜ｘＮ）の値を保持する記憶部２４ａを有している。記憶部２４ａは、たとえば、レジスタやＳＲＡＭなどを用いて実現される。更新部２４は、フラグが更新を許容する旨の値である場合、ｘｌ及び、ｘｍまたはｘｎをそれぞれ更新する。なお、更新部２４は、ｘｌ及び、ｘｍまたはｘｎが変化することによるエネルギー変化に基づいてエネルギーを更新してもよい。また、更新部２４は、各更新時点での最小エネルギーとその最小エネルギーが得られたときの状態（最小エネルギー時の状態）とを保持するようにしてもよい。また、更新部２４は、ｘ１〜ｘＮをΔＥ算出部２１に供給する。ｘ１〜ｘＮを用いたΔＥ算出部２１の処理の例については後述する。
【００７５】
乱数生成回路２５ａは、ｘ１〜ｘＮに基づいて、Ｎ個のビットのうち、値が０のビットのインデックスの１つである乱数（ｎ）を出力する。乱数生成回路２５ａは、たとえば、ｘ１〜ｘＮのうち、値が０である（Ｎ−ｋ）個のビットのインデックスを出力する回路と、出力された（Ｎ−ｋ）個のインデックスのうちの何れか１つを、乱数を用いて選択する回路と、その乱数を生成する回路により実現される。乱数を生成する回路としては、たとえば、ＬＦＳＲがある。
【００７６】
乱数生成回路２５ｂは、ｘ１〜ｘＮに基づいて、Ｎ個のビットのうち、値が１のビットのインデックスの１つである乱数（ｍ）を出力する。乱数生成回路２５ｂは、たとえば、ｘ１〜ｘＮのうち、値が１であるｋ個のビットのインデックスを出力する回路と、出力されたｋ個のインデックスのうちの何れか１つを、乱数を用いて選択する回路と、その乱数を生成する回路により実現される。
【００７７】
制御部２６は、最適化装置２０の後述する初期設定処理を行う。また、制御部２６は、イジングモデルの状態を更新する処理が所定回数繰り返されるごとに、たとえば、制御装置２７によって指定される温度スケジュールにしたがってＴの値を小さくしていく。
【００７８】
さらに、制御部２６は、状態更新処理が所定の繰り返し回数、繰り返されたのちに、記憶部２４ａに保持されている状態（ｘ１〜ｘＮ）を取得し、たとえば、最適化問題に対する解として制御装置２７に送信する。なお、制御部２６は、更新部２４の記憶部２４ａが、最小エネルギーや最小エネルギー時の状態を保持している場合には、状態更新処理が所定の繰り返し回数、繰り返されたのちに、それらの情報を取得して、制御装置２７に送信してもよい。
【００７９】
制御部２６は、たとえば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの特定用途の電子回路にて実現できる。なお、制御部２６は、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）などのプロセッサであってもよい。その場合、プロセッサは、図示しないメモリに記憶されたプログラムを実行することで、上記の処理を行う。
【００８０】
（ΔＥ算出部２１の例）
図３は、ΔＥ算出部の一例を示す図である。
ΔＥ算出部２１は、記憶部２１ａ、選択回路２１ｂ１〜２１ｂＮ，２１ｃ１〜２１ｃＮ、ｈ更新回路２１ｄ１〜２１ｄＮ、ｈ伝搬制御部２１ｅ、ΔＥ算出回路２１ｆ１〜２１ｆＮを有する。
【００８１】
記憶部２１ａは、イジングモデルに含まれる全スピンに対応する全ビットの間の相互作用の大きさを示す重み値（Ｗ１１〜ＷＮＮ）を格納している。Ｗ１１〜ＷＮＮは、初期設定処理時に、制御部２６によって記憶部２１ａに記憶される。記憶部２１ａは、たとえば、レジスタやＳＲＡＭなどを用いて実現される。
【００８２】
選択回路２１ｂ１〜２１ｂＮのそれぞれは、識別情報計算部２３が出力するインデックス＝ｌ及び、インデックス＝ｍまたはインデックス＝ｎに基づいて、記憶部２１ａに格納されている重み値のうち、２つを選択して出力する。
【００８３】
たとえば、選択回路２１ｂｉはＷ１ｉ〜ＷＮｉの中から、Ｗｌｉ及び、ＷｍｉまたはＷｎｉを選択して出力する。なお、インデックス＝ｌ及び、インデックス＝ｍまたはインデックス＝ｎのうち、ｌが先に選択回路２１ｂｉに供給される場合、選択回路２１ｂｉは、ＷｌｉをＷｍｉまたはＷｎｉよりも先に出力する。ｍまたはｎが先に選択回路２１ｂｉに供給される場合、選択回路２１ｂｉは、ＷｍｉまたはＷｎｉをＷｌよりも先に出力する。同様に選択回路２１ｂｊはＷ１ｊ〜ＷＮｊの中から、Ｗｌｊ及び、ＷｍｊまたはＷｎｊを選択して出力する。
【００８４】
選択回路２１ｃ１〜２１ｃＮのそれぞれは、１〜Ｎのインデックスの何れかに対応するビットの値（ｘ１〜ｘＮ）とｎ，ｍとを選択信号として入力する。そして、選択回路２１ｃ１〜２１ｃＮのそれぞれは、入力したビットの値が０であればそのビットと、インデックス＝ｍに対応するビットとの間の相互作用の大きさを示す重み値を選択する。また、選択回路２１ｃ１〜２１ｃＮのそれぞれは、入力したビットの値が１であればそのビットと、インデックス＝ｎに対応するビットとの間の相互作用の大きさを示す重み値を選択する。そして、選択回路２１ｃ１〜２１ｃＮのそれぞれは、選択した重み値を、ΔＥ算出回路２１ｆ１〜２１ｆＮの記憶部２１ｆ１ａ〜２１ｆＮａの何れかに供給する。
【００８５】
たとえば、選択回路２１ｃｉは、ｘｉが０であれば、Ｗ１ｉ〜ＷＮｉの中からＷｍｉを選択してΔＥ算出回路２１ｆｉの記憶部２１ｆｉａに供給し、ｘｉが１であれば、Ｗ１ｉ〜ＷＮｉの中からＷｎｉを選択して記憶部２１ｆｉａに供給する。選択回路２１ｃｊは、ｘｊが０であれば、Ｗ１ｊ〜ＷＮｊの中からＷｍｊを選択してΔＥ算出回路２１ｆｊの記憶部２１ｆｊａに供給し、ｘｊが１であれば、Ｗ１ｊ〜ＷＮｊの中からＷｎｊを選択して記憶部２１ｆｊａに供給する。
【００８６】
ｈ更新回路２１ｄ１〜２１ｄＮのそれぞれは、図示を省略しているが保持部（たとえば、レジスタ）を有し、ｈ１〜ｈＮの何れかの保持及び更新を行う。
たとえば、ｈ更新回路２１ｄｉは、選択回路２１ｂｉが選択したＷｌｉ及び、ＷｍｉまたはＷｎｉを用いて、ｈｉを更新する。選択回路２１ｂｉがＷｌｉとＷｍｉを選択する場合（ｘｌ＝０の場合）、ｈ更新回路２１ｄｉは、ｈｉ−Ｗmｉ＋Ｗｌｉを計算することで、ｈｉを更新する。選択回路２１ｂｉがＷｌｉとＷｎｉを選択する場合（ｘｌ＝１の場合）、ｈ更新回路２１ｄｉは、ｈｉ−Ｗｌｉ＋Ｗｎｉを計算することで、ｈｉを更新する。ｈ更新回路２１ｄｊは、選択回路２１ｂｊが選択したＷｌｊ及び、ＷｍｊまたはＷｎｊを用いて、ｈｊを更新する。選択回路２１ｂｊがＷｌｊとＷｍｊを選択する場合（ｘｌ＝０の場合）、ｈ更新回路２１ｄｊは、ｈｊ−Ｗmｊ＋Ｗｌｊを計算することで、ｈｊを更新する。選択回路２１ｂｊがＷｌｊとＷｎｊを選択する場合（ｘｌ＝１の場合）、ｈ更新回路２１ｄｊは、ｈｊ−Ｗｌｊ＋Ｗｎｊを計算することで、ｈｊを更新する。
【００８７】
ｈ１〜ｈＮの初期値は、たとえば、バイアス値（ｂ１〜ｂＮ）であり、初期設定処理時に、制御部２６によって設定される。ｈ更新回路２１ｄ１〜２１ｄＮは、たとえば、加算器や減算器を用いて実現される。
【００８８】
また、ｈ更新回路２１ｄ１〜２１ｄＮのそれぞれは、更新するローカルフィールド値がどのビットについてのものであるかを示すインデックスを保持しており、そのインデックスを出力する。
【００８９】
ｈ伝搬制御部２１ｅは、ｘ１〜ｘＮ、インデックス＝１〜Ｎ、及び、乱数生成回路２５ａ，２５ｂが出力するｍ，ｎに基づいて、ｈｍ，ｈｎの伝搬先（供給先）を制御する。
図４は、ｈ伝搬制御部の一例を示す図である。
【００９０】
図４では、ｈ伝搬制御部２１ｅの一部（インデックス＝ｉ，ｍ，ｎに対応するビットについてのｈｊ，ｈｍ，ｈｎの伝搬制御を行う部分）が示されている。ｈ伝搬制御部２１ｅは、ＥｘＮＯＲ（排他的否定論理和）回路３０ｉ，３０ｍ，３０ｎ，３１ｉ，３１ｍ，３１ｎ、スイッチ３２ｉ，３２ｍ，３２ｎ，３３ｉ，３３ｍ，３３ｎ、セレクタ３４ｉ、ｈｍ伝搬バス３５、ｈｎ伝搬バス３６を有する。
【００９１】
ＥｘＮＯＲ回路３０ｉ，３１ｉの一方の入力端子には、インデックス＝ｉが入力され、ＥｘＮＯＲ回路３０ｍ，３１ｍの一方の入力端子には、インデックス＝ｍが入力され、ＥｘＮＯＲ回路３０ｎ，３１ｎの一方の入力端子には、インデックス＝ｎが入力される。ＥｘＮＯＲ回路３０ｉ，３０ｍ，３０ｎの他方の入力端子には、乱数生成回路２５ｂが出力するｍが入力され、ＥｘＮＯＲ回路３１ｉ，３１ｍ，３１ｎの他方の入力端子には、乱数生成回路２５ａが出力するｎが入力される。
【００９２】
スイッチ３２ｉ，３３ｉの一方の端子にはｈｉが供給され、スイッチ３２ｍ，３３ｍの一方の端子にはｈｍが供給され、スイッチ３２ｎ，３３ｎの一方の端子にはｈｎが供給される。スイッチ３２ｉ，３２ｍ，３２ｎの他方の端子はｈｍ伝搬バス３５に接続され、スイッチ３３ｉ，３３ｍ，３３ｎの他方の端子はｈｎ伝搬バス３６に接続されている。
【００９３】
スイッチ３２ｉは、ＥｘＮＯＲ回路３０ｉが出力する制御信号が１の場合にオンし、制御信号が０の場合にオフする。スイッチ３３ｉは、ＥｘＮＯＲ回路３１ｉが出力する制御信号が１の場合にオンし、制御信号が０の場合にオフする。スイッチ３２ｍは、ＥｘＮＯＲ回路３０ｍが出力する制御信号が１の場合にオンし、制御信号が０の場合にオフする。スイッチ３３ｍは、ＥｘＮＯＲ回路３１ｍが出力する制御信号が１の場合にオンし、制御信号が０の場合にオフする。スイッチ３２ｎは、ＥｘＮＯＲ回路３０ｎが出力する制御信号が１の場合にオンし、制御信号が０の場合にオフする。スイッチ３３ｎは、ＥｘＮＯＲ回路３１ｎが出力する制御信号が１の場合にオンし、制御信号が０の場合にオフする。
【００９４】
スイッチ３２ｉ，３２ｍ，３２ｎ，３３ｉ，３３ｍ，３３ｎは、たとえば、トランスファーゲートである。
セレクタ３４ｉの一方の入力端子はｈｍ伝搬バス３５に接続され、他方の入力端子はｈｎ伝搬バス３６に接続されている。セレクタ３４ｉの出力端子はΔＥ算出回路２１ｈｉに接続されている。セレクタ３４ｉは、選択信号として供給されるｘｉが０の場合、ｈｍ伝搬バス３５に伝搬されるローカルフィールド値を出力し、ｘｉが１の場合、ｈｎ伝搬バス３６に伝搬されるローカルフィールド値を出力する。なお、図４では図示が省略されているが、セレクタ３４ｉと同様のセレクタがΔＥ算出回路２１ｈｉ以外の各ΔＥ算出回路にも接続されている。
【００９５】
このようなｈ伝搬制御部２１ｅでは、乱数生成回路２５ｂからｍが入力されると、ＥｘＮＯＲ回路３０ｍは、両入力が等しいため、１を出力する。これにより、スイッチ３２ｍはオンし、ｈｍがｈｍ伝搬バス３５に伝搬される。また、乱数生成回路２５ａからｎが入力されると、ＥｘＮＯＲ回路３１ｎは、両入力が等しいため、１を出力する。これにより、スイッチ３３ｎはオンし、ｈｎがｈｎ伝搬バス３６に伝搬される。ＥｘＮＯＲ回路３０ｉ，３０ｎ，３１ｉ，３１ｍは、両入力が異なるため、０を出力する。これにより、スイッチ３２ｉ，３２ｎ，３３ｉ，３３ｍはオフする。セレクタ３４ｉに供給されるｘｉが０の場合、ｈｍがΔＥ算出回路２１ｈｉに供給され、ｘｉが１の場合、ｈｎがΔＥ算出回路２１ｈｉに供給される。
【００９６】
図５は、ｈ伝搬制御部の他の例を示す図である。
図５に示すｈ伝搬制御部２１ｅａは、図４に示したスイッチ３２ｉ，３２ｍ，３２ｎ，３３ｉ，３３ｍ，３３ｎの代わりに、トライステートバッファ３２ｉａ，３２ｍａ，３２ｎａ，３３ｉａ，３３ｍａ，３３ｎａが用いられている。トライステートバッファ３２ｉａ，３２ｍａ，３２ｎａ，３３ｉａ，３３ｍａ，３３ｎａのそれぞれは、制御信号が１の場合に、入力信号（ローカルフィールド値）を出力し、制御信号が０の場合は、出力端子をハイインピーダンス状態とする。その他のｈ伝搬制御部２１ｅａの動作については、図４に示したｈ伝搬制御部２１ｅの動作と同じである。
【００９７】
図３の説明に戻る。ΔＥ算出回路２１ｆ１〜２１ｆＮは、ローカルフィールド値と重み値とを用いて、ハミング距離＝２の状態遷移によってｋ−ｈｏｔ制約を満たすある状態からｋ−ｈｏｔ制約を満たす別の状態に遷移するときのΔＥ１〜ΔＥＮを算出する。
【００９８】
ΔＥ算出回路２１ｆ１〜２１ｆＮのそれぞれには、ｈ更新回路２１ｄ１〜２１ｄＮの何れかから、ｈ１〜ｈＮの何れかが直接供給される。さらに、値が０のビットについてのローカルフィールド値がｈ更新回路２１ｄ１〜２１ｄＮの何れかから供給されるΔＥ算出回路には、ｈ伝搬制御部２１ｅによってｈｍが供給される。また、値が１のビットについてのローカルフィールド値がｈ更新回路２１ｄ１〜２１ｄＮの何れかから供給されるΔＥ算出回路には、ｈ伝搬制御部２１ｅによってｈｎが供給される。また、ΔＥ算出回路２１ｆ１〜２１ｆＮのそれぞれには、ｘ１〜ｘＮの何れかが供給される。
【００９９】
また、ΔＥ算出回路２１ｆ１〜２１ｆＮは、式（６）の計算をするための重み値を保持する記憶部２１ｆ１ａ〜２１ｆＮａを有する。記憶部２１ｆ１ａ〜２１ｆＮａに保持される重み値は、前述の選択回路２１ｃ１〜２１ｃＮによって選択される。
【０１００】
たとえば、ｘｉが１から０に更新され、ｘｎが０から１に更新される場合、ΔＥｉは、式（６）において、ｈｊ＝ｈｎ、Ｗｉｊ＝Ｗｎｉ（ただし、Ｗｎｉ＝Ｗｉｎ）の場合であるため、ΔＥｉ＝ｈｉ−ｈｎ＋Ｗｎｉと表せる。一方、ｘｉが０から１に更新され、ｘｍが１から０に更新される場合、ΔＥｉは、式（６）において、ｈｉ＝ｈｍ、ｈｊ＝ｈｉの場合であるため、ΔＥｉ＝−ｈｉ＋ｈｍ＋Ｗｍｉと表せる。
【０１０１】
このため、ΔＥ算出回路２１ｆｉは、現在のｘｉが１の場合、ΔＥｉ＝ｈｉ−ｈｎ＋Ｗｎｉを出力し、現在のｘｉが０の場合、ΔＥｉ＝−ｈｉ＋ｈｍ＋Ｗｍｉを出力する。
ΔＥ算出回路２１ｆ１〜２１ｆＮは、たとえば、加算器、減算器、セレクタを用いて実現される。また、記憶部２１ｆ１ａ〜２１ｆＮａは、たとえば、レジスタやＳＲＡＭなどを用いて実現される。
【０１０２】
（選択回路２２の一例）
図６は、選択回路の一例を示す図である。
選択回路２２は、符号反転部２２ａ、オフセット加算部２２ｂ、乱数発生回路２２ｃ、選択法則適用部２２ｄ、乗算器２２ｅ、比較部２２ｆ、セレクタ２２ｇを有する。
【０１０３】
符号反転部２２ａは、ΔＥ１，ΔＥ２，…，ΔＥＮのそれぞれに−１を掛けて符合を反転させる。
オフセット加算部２２ｂは、符号反転部２２ａの出力値（−ΔＥ１〜−ΔＥＮ）のそれぞれに、オフセット値を加える。オフセット加算部２２ｂは、後述するセレクタ２２ｇが出力するフラグが更新を許容しないことを示すとき（つまり状態遷移が生じないとき）、オフセット値を増加していく。一方、オフセット加算部２２ｂは、フラグが、更新を許容することを示すとき（つまり状態遷移が生じるとき）には、オフセット値を０にする。オフセット値が大きくなると状態遷移が許容されやすくなり、現在の状態が局所解にある場合、その局所解からの脱出が促進される。
【０１０４】
乱数発生回路２２ｃは、０以上、１以下の一様乱数（ｒ）を発生する。
選択法則適用部２２ｄは、シミュレーテッド・アニーリングを行うための選択法則（メトロポリス法またはギブス法）に基づいた値を出力する。
【０１０５】
シミュレーテッド・アニーリングが行われる場合、あるエネルギー変化を引き起こす状態遷移の許容確率Ａ（ΔＥ，Ｔ）を以下の式（７）、式（８）のように決めれば、時刻（反復回数）無限大の極限で状態が最適解に到達することが証明されている。
【０１０６】
【数７】
2020064535.tif 000009
【０１０７】
【数８】
2020064535.tif 000010
【０１０８】
式（７）、式（８）においてＴは、前述の温度パラメータである。
式（７）で表される許容確率Ａ（ΔＥ，Ｔ）を用いた場合、十分な反復後に定常状態に達したとすると、各状態の占有確率は熱力学における熱平衡状態に対するボルツマン分布にしたがう。そして、高い温度から徐々に下げていくとエネルギーの低い状態の占有確率が増加するため、十分温度が下がるとエネルギーの低い状態が得られるはずである。この様子が材料を焼き鈍したときの状態変化とよく似ているため、この方法はシミュレーテッド・アニーリングと呼ばれるのである。このとき、エネルギーが上がる状態遷移が確率的に起こることは、物理学における熱励起に相当する。
【０１０９】
許容確率Ａ（ΔＥ，Ｔ）でΔＥを引き起こす状態遷移を許容することを示すフラグ（＝１）を出力する回路は、式（７）、式（８）のｆ（−ΔＥ／Ｔ）と、一様乱数ｒとの比較結果に基づいた値を出力する比較器によって実現できる。
【０１１０】
ただ、次のような変形を行っても同じ機能が実現できる。２つの数に同じ単調増加関数を作用させても大小関係は変化しない。したがって比較器の２つの入力に同じ単調増加関数を作用させても比較器の出力は変わらない。たとえば、ｆ（−ΔＥ／Ｔ）に作用させる単調増加関数としてｆ（−ΔＥ／Ｔ）の逆関数ｆ−１（−ΔＥ／Ｔ）、一様乱数に作用させる単調増加関数としてｆ−１（−ΔＥ／Ｔ）の−ΔＥ／Ｔをｒとしたｆ−１（ｒ）を用いることができる。その場合、上記の比較器と同様の機能を有する回路は、−ΔＥ／Ｔがｆ−１（ｒ）より大きいとき１を出力する回路でよいことがわかる。さらにＴが正であることから、その回路は、−ΔＥがＴ・ｆ−１（ｒ）より大きいとき１を出力する回路でよい。
【０１１１】
選択法則適用部２２ｄは、入力される一様乱数を上記のｆ−１（ｒ）の値に変換する変換テーブルを用いて、ｆ−１（ｒ）の値を出力する。メトロポリス法が適用される場合、ｆ−１（ｒ）は、ｌｏｇ（ｒ）である。変換テーブルは、たとえば、ＲＡＭ（Random Access Memory）、フラッシュメモリなどのメモリに記憶されている。
【０１１２】
乗算器２２ｅは、Ｔと、ｆ−１（ｒ）との積（Ｔ・ｆ−１（ｒ））を出力する。Ｔ・ｆ−１（ｒ）は、熱励起エネルギーに相当する。
比較部２２ｆは、ΔＥ１〜ΔＥＮのそれぞれについてのオフセット加算部２２ｂによる加算結果と、Ｔ・ｆ−１（ｒ）とを比較し、Ｔ・ｆ−１（ｒ）より大きい加算結果に対するフラグとして、１を出力する。また、比較部２２ｆは、Ｔ・ｆ−１（ｒ）以下の加算結果に対するフラグとして、０を出力する。
【０１１３】
セレクタ２２ｇは、ΔＥ１〜ΔＥＮのそれぞれについてのフラグに基づいて、更新が許容されたビットのインデックス＝ｌとフラグを出力する。更新が許容されたビットが複数ある場合、乱数に基づいて、そのうちの１つのビットのインデックスが、インデックス＝ｌとして出力される。更新が許容されたビットがない場合についても、何れかのビットのインデックスが出力される。その場合、セレクタ２２ｇが出力するフラグは０となる。
【０１１４】
たとえば、セレクタ２２ｇは、インデックス＝ｌとして、ｌ番目のビットの値が１で、他のビットの値が０であるＮビット値を出力する。
なお、図１に示した第１の実施の形態の最適化装置１０の選択回路１２についても、図６に示すような回路を用いて実現できる。
【０１１５】
（識別情報計算部２３の一例）
図７は、識別情報計算部の一例を示す図である。
識別情報計算部２３は、セレクタ２３ａにより実現できる。セレクタ２３ａの一方の入力端子には、乱数生成回路２５ｂよりｍが入力され、他方の入力端子には、乱数生成回路２５ａよりｎが入力される。セレクタ２３ａは、更新部２４から供給されるｘｌが０である場合、ｍを出力し、ｘｌが１である場合、ｎを出力する。
【０１１６】
（最適化装置２０の全体動作例）
図８は、第２の実施の形態の最適化装置の一例の処理の流れを示すフローチャートである。
【０１１７】
まず、制御部２６は、最適化装置２０の初期設定処理を行う（ステップＳ１）。初期設定処理として、たとえば、以下の処理が行われる。制御部２６は、制御装置２７から受信したＷ１１〜ＷＮＮをΔＥ算出部２１の記憶部２１ａに記憶する。また、制御部２６は、制御装置２７から受信したｈ１〜ｈＮの初期値（たとえば、バイアス値）をΔＥ算出部２１のｈ更新回路２１ｄ１〜２１ｄＮに設定する。さらに、制御部２６は、制御装置２７から受けたアニーリング条件に基づいて、選択回路２２に温度パラメータの初期値を設定する。また、制御部２６は、ｘ１〜ｘＮ（全て０）を、記憶部２４ａに記憶する。その後、制御部２６は、乱数を用いて、ｘ１〜ｘＮのうちｋ個の値を１とする。たとえば、制御部２６は、更新部２４にｋ個の状態変数を１つずつ０から１に更新させ、それに伴いｈ更新回路２１ｄ１〜２１ｄＮにｈ１〜ｈＮを更新させる。なお、制御部２６が、ｈ１〜ｈＮを更新して、更新後のｈ１〜ｈＮをｈ更新回路２１ｄ１〜ｄ１ｄＮに設定してもよい。
【０１１８】
上記のような初期設定処理が終了した後、乱数生成回路２５ａ，２５ｂは、ｘ１〜ｘＮに基づいて、ｎ，ｍを生成する（ステップＳ２）。
ΔＥ算出部２１の選択回路２１ｃ１〜２１ｃＮは、ｘ１〜ｘＮとｎ，ｍに基づいて、ΔＥ１〜ΔＥＮの計算に用いられる重み値を選択して、記憶部２１ｆ１ａ〜２１ｆＮａに供給する（ステップＳ３）。
【０１１９】
ΔＥ算出部２１のｈ伝搬制御部２１ｅは、ｘ１〜ｘＮ、インデックス＝１〜Ｎ、及び、乱数生成回路２５ａ，２５ｂが出力するｍ，ｎに基づいて、ｈｍ，ｈｎの伝搬を行う（ステップＳ４）。前述のｈ伝搬制御部２１ｅの処理により、ΔＥ算出回路２１ｆ１〜２１ｆＮのうち、値が０であるビットについてのローカルフィールド値がｈ更新回路２１ｄ１〜ｄ１ｄＮの何れかから直接供給されるΔＥ算出回路には、ｈ伝搬制御部２１ｅによってｈｍが供給される。また、値が１であるビットについてのローカルフィールド値がｈ更新回路２１ｄ１〜ｄ１ｄＮの何れかから直接供給されるΔＥ算出回路には、ｈ伝搬制御部２１ｅによってｈｎが供給される。
【０１２０】
その後、ΔＥ算出回路２１ｆ１〜２１ｆＮによる前述したようなΔＥ１〜ΔＥＮの計算が行われる（ステップＳ５）。そして、図６に示したような選択回路２２において、オフセット値の加算が行われたのち（ステップＳ６）、インデックス＝ｌの選択が行われる（ステップＳ７）。識別情報計算部２３は、前述の処理により、ｘｌに応じて、インデックス＝ｍまたはインデックス＝ｎを出力する（ステップＳ８）。
【０１２１】
その後、更新部２４は、記憶部２４ａに記憶されているｘｌ及び、ｘｍまたはｘｎを更新し（ステップＳ９）、ΔＥ算出部２１のｈ更新回路２１ｄ１〜２１ｄＮは、ｘｌ及び、ｘｍまたはｘｎの更新に伴ってｈ１〜ｈＮを更新する（ステップＳ１０）。
【０１２２】
その後、制御部２６は、状態の更新処理回数が、所定回数Ｎ１に達したか否か判定する（ステップＳ１１）。更新処理回数が所定回数Ｎ１に達していない場合には、ステップＳ２〜Ｓ１０の処理が繰り返される。
【０１２３】
更新処理回数が所定回数Ｎ１に達した場合、制御部２６は、Ｔの変更回数（温度変更回数）が、所定回数Ｎ２に達したか否かを判定する（ステップＳ１２）。
温度変更回数が所定回数Ｎ２に達していない場合、制御部２６は、Ｔを変更する（温度を下げる）（ステップＳ１３）。所定回数Ｎ１，Ｎ２、Ｔの値の変更の仕方（一度に値をどのくらい小さくするかなど）は、アニーリング条件に基づいて決定される。ステップＳ１３の処理後、ステップＳ２からの処理が繰り返される。
【０１２４】
温度変更回数が所定回数Ｎ２に達している場合、制御部２６は、そのときの各ビットの値（変数ｘｉ（ｉ＝１〜Ｎ））を記憶部２４ａから取得して、解（計算結果）として制御装置２７に送信（出力）する（ステップＳ１４）。なお、制御部２６には、表示装置が接続されていてもよい。その場合、制御部２６は、表示装置に、計算結果が表示されるようにしてもよい。
【０１２５】
また、更新部２４が、インデックス＝ｌとインデックス＝ｍまたはインデックス＝ｎに対応する２つのビットの値が変化することによるエネルギー変化に基づいてエネルギーを更新してもよい。また、更新部２４は、各更新時点での最小エネルギーとその最小エネルギーが得られたときの状態（最小エネルギー時の状態）とを保持するようにしてもよい。その場合、制御部２６は、温度変更回数が所定回数Ｎ２に達したときに、更新部２４が保持している最小エネルギー時の状態を取得して、解として出力してもよい。
【０１２６】
以上のような、第２の実施の形態の最適化装置２０においても、第１の実施の形態の最適化装置１０と同様の効果が得られる。
図９は、第２の実施の形態の最適化装置を用いた場合の計算短縮効果を表すシミュレーション結果を示す図である。
【０１２７】
横軸は状態の更新処理の繰り返し回数を表し、縦軸は正解に達したレプリカ数（最適化装置２０の数）を表す。
計算対象の問題は、車が８台、ルート数が８本の（６４ビットのイジングモデルで表せる）交通量最適化問題である。
【０１２８】
図９には、比較のために、第２の実施の形態の最適化装置２０を用いた場合のシミュレーション結果４０とともに、ハミング距離＝１の遷移を繰り返しながらエネルギーを最小化する従来の最適化装置を用いた場合のシミュレーション結果４１が示されている。
【０１２９】
図９のように、第２の実施の形態の最適化装置２０では、従来の最適化装置と比較して解の収束時間が１００倍以上短くなる。
以上、実施の形態に基づき、本発明の最適化装置及び最適化装置の制御方法の一観点について説明してきたが、これらは一例にすぎず、上記の記載に限定されるものではない。
【符号の説明】
【０１３０】
１０  最適化装置
１１ｉ，１１ｊ，１１Ｎ  ΔＥ算出回路
１１ｉａ，１１ｊａ，１１Ｎａ，１４ａ  記憶部
１２  選択回路
１３  識別情報計算部
１４  更新部
１５ａ，１５ｂ  乱数生成回路
【図１】
2020064535.tif 000011
【図２】
2020064535.tif 000012
【図３】
2020064535.tif 000013
【図４】
2020064535.tif 000014
【図５】
2020064535.tif 000015
【図６】
2020064535.tif 000016
【図７】
2020064535.tif 000017
【図８】
2020064535.tif 000018
【図９】
2020064535.tif 000019