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