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