(57)【要約】【課題】最適解の探索速度の低下を抑制する。【解決手段】複数の算出回路（算出回路１１ｃ１〜１１ｃ６など）のそれぞれは、イジングモデルに含まれる複数のスピンに対応する複数のビットのうち、ｎ（ｎは２以上の整数）個のビットの各々についてのローカルフィールド値、ビットの値、ビット間の相互作用の大きさを示す重み値、に基づいて、ｎ個のビットの値が変化することによるエネルギー変化を算出する。更新ビット選択回路１２は、入力される温度パラメータＴと、乱数とに基づいて決定される熱励起エネルギーと、上記の各算出回路が出力するエネルギー変化との大小関係に基づいて、更新を許容するｎ個のビットを選択し、更新回路１３は、そのｎ個のビットの値を変化させるとともに、その変化に基づいて、上記第１のローカルフィールド値を含む複数のビットの各々についての第２のローカルフィールド値を更新する。【選択図】図１
2020021209.tif 000002
【特許請求の範囲】
【請求項１】
計算対象の問題を変換したイジングモデルに含まれる複数のスピンに対応する複数のビットのうち、ｎ（ｎは２以上の整数）個のビットの各々についての第１のローカルフィールド値と、前記ｎ個のビットの各々の値と、前記ｎ個のビットの間の相互作用の大きさを示す重み値と、に基づいて、前記ｎ個のビットの値が変化することによる前記イジングモデルの第１のエネルギー変化を、それぞれ算出する複数の第１の算出回路と、
入力される温度パラメータと、乱数とに基づいて決定される熱励起エネルギーと、前記複数の第１の算出回路がそれぞれ出力する前記第１のエネルギー変化との大小関係に基づいて、更新を許容する前記ｎ個のビットを選択し、選択した前記ｎ個のビットの第１の識別情報を出力する更新ビット選択回路と、
前記更新ビット選択回路が出力する前記第１の識別情報により識別される前記ｎ個のビットの値を変化させるとともに、前記ｎ個のビットの値の変化に基づいて、前記第１のローカルフィールド値を含む前記複数のビットの各々についての第２のローカルフィールド値を更新する更新回路と、
を有する最適化装置。
【請求項２】
前記複数の第１の算出回路のそれぞれは、前記重み値を記憶する記憶部を備えている、請求項１に記載の最適化装置。
【請求項３】
前記複数のビットのうち、１つのビットについての第３のローカルフィールド値と、前記１つのビットの値と、前記１つのビットの値が変化するときの前記イジングモデルの第２のエネルギー変化を、それぞれ算出する複数の第２の算出回路を、有し、
前記更新ビット選択回路は、前記複数の第１の算出回路がそれぞれ出力する前記第１のエネルギー変化と、前記複数の第２の算出回路がそれぞれ出力する前記第２のエネルギー変化と、前記熱励起エネルギーとの大小関係に基づいて、更新を許容する前記ｎ個のビットまたは前記１つのビットを選択し、選択した前記ｎ個のビットの前記第１の識別情報または前記１つのビットの第２の識別情報を出力し、
前記更新回路は、前記第１の識別情報または前記第２の識別情報により識別される前記ｎ個のビットまたは前記１つのビットの値を変化させるとともに、前記ｎ個のビットまたは前記１つのビットの値の変化に基づいて、前記第１のローカルフィールド値または前記第３のローカルフィールド値を含む前記複数のビットの各々についての前記第２のローカルフィールド値を更新する、請求項１または２に記載の最適化装置。
【請求項４】
所定期間における前記ｎ個のビットの更新回数が閾値以上である場合、前記複数の第１の算出回路の機能をオフにする制御部を有する、請求項３に記載の最適化装置。
【請求項５】
前記複数の第１の算出回路は、前記ｎ個のビットの値が順に変化することによる前記イジングモデルの前記第１のエネルギー変化をそれぞれ算出し、
前記更新回路は、前記更新ビット選択回路が出力する前記第１の識別情報により識別される前記ｎ個のビットの値を順に変化させるとともに、順に変化した前記ｎ個のビットの値の変化に基づいて、前記第１のローカルフィールド値を含む前記複数のビットの各々についての前記第２のローカルフィールド値を更新する、請求項１乃至４の何れか一項に記載の最適化装置。
【請求項６】
前記複数の第１の算出回路は、前記ｎ個のビットのうち、ｎ−１個のビットが変化することによって得られる前記第１のローカルフィールド値の更新後の値をそれぞれ算出し、
前記更新回路は、前記第１の識別情報に基づいて、前記複数の第１の算出回路がそれぞれ算出した前記更新後の値の何れかを選択し、選択した前記更新後の値を用いて前記第２のローカルフィールド値を更新する、
請求項１乃至４の何れか一項に記載の最適化装置。
【請求項７】
前記複数の第１の算出回路は、前記ｎ個のビットのうち、ｎ−１個のビットが順に変化することによって得られる前記第１のローカルフィールド値の更新後の値をそれぞれ算出する、
請求項６に記載の最適化装置。
【請求項８】
計算対象の問題を変換したイジングモデルに含まれる複数のスピンに対応する複数のビットのうち、ｎ（ｎは２以上の整数）個のビットの各々についての第１のローカルフィールド値と、前記ｎ個のビットの各々の値と、前記ｎ個のビットの間の相互作用の大きさを示す重み値と、に基づいて、前記ｎ個のビットの値が変化することによる前記イジングモデルの第１のエネルギー変化を、それぞれ算出する複数の第１の算出回路と、
入力される温度パラメータと、乱数とに基づいて決定される熱励起エネルギーと、前記複数の第１の算出回路がそれぞれ出力する前記第１のエネルギー変化との大小関係に基づいて、更新を許容する前記ｎ個のビットを選択し、選択した前記ｎ個のビットの第１の識別情報を出力する更新ビット選択回路と、
前記更新ビット選択回路が出力する前記第１の識別情報により識別される前記ｎ個のビットの値を変化させるとともに、前記ｎ個のビットの値の変化に基づいて、前記第１のローカルフィールド値を含む前記複数のビットの各々についての第２のローカルフィールド値を更新する更新回路と、
を有する最適化装置に対して、
制御装置が、前記重み値を設定し、
前記制御装置が、前記温度パラメータの大きさを制御する、
最適化装置の制御方法。
【請求項９】
計算対象の問題を変換したイジングモデルに含まれる複数のスピンに対応する複数のビットのうち、ｎ（ｎは２以上の整数）個のビットの各々についての第１のローカルフィールド値と、前記ｎ個のビットの各々の値と、前記ｎ個のビットの間の相互作用の大きさを示す重み値と、に基づいて、前記ｎ個のビットの値が変化することによる前記イジングモデルの第１のエネルギー変化を、それぞれ算出する複数の第１の算出回路と、
入力される温度パラメータと、乱数とに基づいて決定される熱励起エネルギーと、前記複数の第１の算出回路がそれぞれ出力する前記第１のエネルギー変化との大小関係に基づいて、更新を許容する前記ｎ個のビットを選択し、選択した前記ｎ個のビットの第１の識別情報を出力する更新ビット選択回路と、
前記更新ビット選択回路が出力する前記第１の識別情報により識別される前記ｎ個のビットの値を変化させるとともに、前記ｎ個のビットの値の変化に基づいて、前記第１のローカルフィールド値を含む前記複数のビットの各々についての第２のローカルフィールド値を更新する更新回路と、
を有する最適化装置に対して、
前記重み値を設定し、
前記温度パラメータの大きさを制御する、
処理をコンピュータに実行させる最適化装置の制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適化装置、最適化装置の制御方法及び最適化装置の制御プログラムに関する。
【背景技術】
【０００２】
ノイマン型コンピュータが不得意とする多変数の最適化問題を解く方法として、イジング型のエネルギー関数を用いた最適化装置（イジングマシンまたはボルツマンマシンと呼ばれる場合もある）がある。最適化装置は、計算対象の問題を、磁性体のスピンの振る舞いを表すモデルであるイジングモデルに置き換えて計算する。
【０００３】
最適化装置は、たとえば、ニューラルネットワークを用いてモデル化することもできる。その場合、イジングモデルに含まれる複数のスピンに対応した複数のビットのそれぞれが、他のビットの値と、他のビットと自身のビットとの相互作用の大きさを示す重み値（結合係数とも呼ばれる）とに応じて０または１を出力するニューロンとして機能する。最適化装置は、たとえば、シミュレーテッド・アニーリングなどの確率的探索法により、上記のようなエネルギー関数（コスト関数、目的関数とも呼ばれる）の値（以下エネルギーという）の最小値が得られる各ビットの値の組み合わせを、解として求める。
【０００４】
従来、デジタル回路を用いてシミュレーテッド・アニーリングを行うことでエネルギーが最小となる各ビットの値の組み合わせを計算する最適化装置がある（たとえば、特許文献１，２及び非特許文献１参照）。従来の最適化装置は、一度に１ビットだけ変化するとしてエネルギー変化を計算し、そのエネルギー変化に対して温度に対応するノイズ値を加えた値に応じてビットの変化を許容するか否かを決定する。エネルギーが増加するビットの変化も所定の確率で許容され、温度が低くなるにつれてその確率は低くなる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１７−２１９９４８号公報
【特許文献２】特開２０１８−０４１３５１号公報
【非特許文献】
【０００６】
【非特許文献１】Satoshi Matsubara et al., “Ising-Model Optimizer with Parallel-Trial Bit-Sieve Engine”, CISIS-2017, Pages 432-438
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来の最適化装置は、一度に１ビットだけ変化を許容して確率的探索を行う。そのため、温度が低くなるアニーリング終盤のように、変化するビットが得られる確率が小さい状況では、最適解の探索速度が低下する問題がある。
【０００８】
１つの側面では、本発明は、最適解の探索速度の低下を抑制する最適化装置、最適化装置の制御方法及び最適化装置の制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
１つの実施態様では、計算対象の問題を変換したイジングモデルに含まれる複数のスピンに対応する複数のビットのうち、ｎ（ｎは２以上の整数）個のビットの各々についての第１のローカルフィールド値と、前記ｎ個のビットの各々の値と、前記ｎ個のビットの間の相互作用の大きさを示す重み値と、に基づいて、前記ｎ個のビットの値が変化することによる前記イジングモデルの第１のエネルギー変化を、それぞれ算出する複数の第１の算出回路と、入力される温度パラメータと、乱数とに基づいて決定される熱励起エネルギーと、前記複数の第１の算出回路がそれぞれ出力する前記第１のエネルギー変化との大小関係に基づいて、更新を許容する前記ｎ個のビットを選択し、選択した前記ｎ個のビットの第１の識別情報を出力する更新ビット選択回路と、前記更新ビット選択回路が出力する前記第１の識別情報により識別される前記ｎ個のビットの値を変化させるとともに、前記ｎ個のビットの値の変化に基づいて、前記第１のローカルフィールド値を含む前記複数のビットの各々についての第２のローカルフィールド値を更新する更新回路と、を有する最適化装置が提供される。
【００１０】
また、１つの実施態様では、最適化装置の制御方法が提供される。また、１つの実施態様では、最適化装置の制御プログラムが提供される。
【発明の効果】
【００１１】
１つの側面では、最適解の探索速度の低下を抑制することが可能となる。
【図面の簡単な説明】
【００１２】
【図１】第１の実施の形態の最適化装置の一例を示す図である。
【図２】更新ビット選択回路の一例を示す図である。
【図３】Ｎ２：１セレクタの一例を示す図である。
【図４】第１の実施の形態の最適化装置の動作の一例の流れを示すフローチャートである。
【図５】第２の実施の形態の最適化装置の一例を示す図である。
【図６】ハミング距離が３の近傍状態のエネルギー変化を算出する演算部の一例を示す図である。
【図７】第３の実施の形態の最適化装置におけるＮ３：１セレクタの一例を示す図である。
【図８】第４の実施の形態の最適化装置の一例を示す図である。
【図９】第４の実施の形態の最適化装置の動作の一例の流れを示すフローチャートである。
【図１０】制御装置のハードウェア例を示す図である。
【図１１】制御装置による最適化装置の制御方法の流れを示すフローチャートである。
【発明を実施するための形態】
【００１３】
以下、発明を実施するための形態を、図面を参照しつつ説明する。
以下に示す最適化装置は、イジングモデルに含まれる複数のスピンに対応する複数のビットの各々の値の現在の組み合わせ（現在の状態）に対して、ハミング距離がｎ（ｎは２以上の正の整数）の近傍状態の探索を可能とするものである。
【００１４】
なお、最適化装置は、イジングモデルの基底状態（イジング型のエネルギー関数が最小値となるときの各ビットの値）を探索することで、巡回セールスマン問題などの最適化問題を計算する。イジング型のエネルギー関数Ｅ（ｘ）は、たとえば、以下の式（１）で定義される。
【００１５】
【数１】
2020021209.tif 000003
【００１６】
右辺の１項目は、イジングモデルに含まれる全ビットから選択可能な２つのビットの全組み合わせについて、漏れと重複なく、２つのビットの値（０または１）と結合係数との積を積算したものである。ｘｉは、ｉ番目のビットの値を表す変数（状態変数とも呼ばれる）、ｘｊは、ｊ番目のビットの値を表す変数であり、Ｗｉｊは、ｉ番目とｊ番目のビットの相互作用の大きさを示す重み値である。なお、Ｗｉｉ＝０である。また、Ｗｉｊ＝Ｗｊｉであることが多い（つまり、重み値による係数行列は対称行列である場合が多い）。
【００１７】
右辺の２項目は、全ビットのそれぞれのバイアス係数とビットの値との積の総和を求めたものである。ｂｉは、ｉ番目のビットのバイアス係数を示している。
また、変数ｘｉの値が変化して１−ｘｉとなると、変数ｘｉの増加分は、Δｘｉ＝（１−ｘｉ）−ｘｉ＝１−２ｘｉと表せる。スピン反転（値の変化）に伴うエネルギー変化ΔＥｉは、以下の式（２）で表される。
【００１８】
【数２】
2020021209.tif 000004
【００１９】
式（２）において、変数ｘｉが１から０に変化するとき、Δｘｉは−１となり、変数ｘｉが０から１に変化するとき、Δｘｉは１となる。なお、ｈｉはローカルフィールド（局所場）と呼ばれ、Δｘｉに応じてローカルフィールドｈｉに符号（＋１または−１）を乗じたものがエネルギー変化ΔＥｉである。変数ｘｊが０から１に変化するときのローカルフィールドｈｉの変化分は、Δｈｉ（ｊ）＝＋Ｗｉｊ、変数ｘｊが１から０に変化するときのローカルフィールドｈｉの変化分は、Δｈｉ（ｊ）＝−Ｗｉｊである。同様に、変数ｘｉが変化したときのｊ番目のビットについてのローカルフィールドｈｊの変化分は、Δｈｊ（ｉ）＝ΔｘｉＷｉｊ、と表せる。
【００２０】
したがって、変数ｘｉ，ｘｊの値が順に変化したときの（ハミング距離が２の近傍状態の）エネルギー変化は、以下の式（３）で表せる。なお、Ｗｉｊ＝Ｗｊｉが成立する場合において、エネルギー変化は変数ｘｉ，ｘｊが変化する順番には依存しない。したがって変数ｘｉ，ｘｊの順で変化した場合も変数ｘｊ，ｘｉの順で変化した場合も同じエネルギー変化が得られるが、その後の選択操作が確率的な動作であるためエネルギー変化が同じでも別の事象として取り扱う。
【００２１】
【数３】
2020021209.tif 000005
【００２２】
以下では、まず、ハミング距離が２の近傍状態の探索を可能とする第１の実施の形態の最適化装置を説明する。
（第１の実施の形態）
図１は、第１の実施の形態の最適化装置の一例を示す図である。
【００２３】
最適化装置１０は、演算部１１、更新ビット選択回路１２、更新回路１３を有する。
演算部１１は、Ｎ個のビットの値（変数ｘ１，ｘ２，…，ｘＮ）と各ビットについてのローカルフィールドｈ１，ｈ２，…，ｈＮを保持する保持部１１ａと、マトリクス状に配置されたＮ×Ｎ個の算出回路を有する。Ｎは、計算対象の問題を変換したイジングモデルに含まれるスピン数に対応したビット数である。
【００２４】
保持部１１ａは、たとえば、レジスタやＳＲＡＭ（Static Random Access Memory）などである。
Ｎ×Ｎ個の算出回路のうち、マトリクスの対角部分に配置されている算出回路１１ｂ１，１１ｂ２，…，１１ｂＮは、現在の状態からハミング距離が１の近傍状態に遷移した場合のエネルギー変化を算出する。
【００２５】
たとえば、算出回路１１ｂ１は、１番目のビット（変数ｘ１）の値と１番目のビットについてのローカルフィールドｈ１の値に基づいて、式（２）により、変数ｘ１が変化することによるイジングモデルのエネルギー変化ΔＥ１を算出する。算出回路１１ｂ１は、たとえば、変化前の変数ｘ１が１のとき、ローカルフィールドｈ１に＋１を掛けた値をエネルギー変化ΔＥ１として出力し、変化前の変数ｘ１が０のとき、ローカルフィールドｈ１に−１を掛けた値をエネルギー変化ΔＥ１として出力する。算出回路１１ｂ１は、変化前の変数ｘ１の値に応じて、ローカルフィールドｈ１に＋１を掛けるか−１を掛けるか選択するセレクタと乗算器を用いて実現できる。算出回路１１ｂ２〜１１ｂＮについても同様である。
【００２６】
なお、最適化装置１０が常にハミング距離＝２の近傍状態の探索を行う場合には、算出回路１１ｂ１〜１１ｂＮはなくてもよい。
Ｎ×Ｎ個の算出回路のうち、算出回路１１ｂ１〜１１ｂＮ以外の算出回路（算出回路１１ｃ１，１１ｃ２，１１ｃ３，１１ｃ４，１１ｃ５，１１ｃ６など）は、現在の状態からハミング距離が２の近傍状態に遷移した場合のエネルギー変化を算出する。
【００２７】
たとえば、算出回路１１ｃ１は、１番目のビットと２番目のビット（変数ｘ１，ｘ２）の値が順に変化することによるイジングモデルのエネルギー変化ΔＥ１２を算出する。算出回路１１ｃ１は、変数ｘ１，ｘ２と１番目のビットと２番目のビットについてのローカルフィールドｈ１，ｈ２の値と、重み値Ｗ１２に基づいて、式（３）により、変数ｘ１と変数ｘ２が順に変化することによるイジングモデルのエネルギー変化ΔＥ１２を算出する。重み値Ｗ１２は、算出回路１１ｃ１内の記憶部１１ｃ１１（レジスタやＳＲＡＭなど）に記憶されている。
【００２８】
算出回路１１ｃ１は、たとえば、変化前の変数ｘ１が１のとき、ローカルフィールドｈ１に＋１を掛け、変化前の変数ｘ１が０のとき、ローカルフィールドｈ１に−１を掛けることで、−Δｘ１ｈ１を計算する。同様に、算出回路１１ｃ１は、変化前の変数ｘ２が１のとき、ローカルフィールドｈ２に＋１を掛け、変化前の変数ｘ２が０のとき、ローカルフィールドｈ２に−１を掛けることで、−Δｘ２ｈ２を計算する。さらに、算出回路１１ｃ１は、変化前の変数ｘ１，ｘ２の値に応じて、重み値Ｗ１２に−１か＋１を掛ける。そして、算出回路１１ｃ１は、３つの乗算結果を加算することで、ΔＥ１２を算出する。このような算出回路１１ｃ１は、セレクタと乗算器と加算器を用いて実現できる。他の算出回路（算出回路１１ｃ２〜１１ｃ６など）についても同様である。
【００２９】
なお、上記のＮ×Ｎ個の算出回路の配置は、あくまで一例である。たとえば、算出回路１１ｂ１〜１１ｂＮは、マトリクスの対角部分に配置されていなくてもよく、一行または一列に揃えて配置されていてもよい。
【００３０】
更新ビット選択回路１２は、温度パラメータＴと、Ｎ×Ｎ個の算出回路がそれぞれ出力するエネルギー変化ΔＥ１，ΔＥ１２，…，ΔＥＮを入力する。そして、更新ビット選択回路１２は、温度パラメータＴと乱数とに基づいて決定される熱励起エネルギーと、エネルギー変化ΔＥ１，ΔＥ１２，…，ΔＥＮとの大小関係に基づいて、更新を許容する２つのビット（または１つのビット）を選択する。さらに、更新ビット選択回路１２は、選択した２つのビット（または１つのビット）の識別情報を出力する。更新ビット選択回路１２の例については後述する。
【００３１】
更新回路１３は、更新ビット選択回路１２が出力する識別情報により識別される２つのビットの値を順に変化させるとともに、２つのビットの値の変化に基づいて、ローカルフィールドｈ１〜ｈＮの値を更新する。なお、更新回路１３は、更新ビット選択回路１２が出力する識別情報が１つのビットに関するものである場合、その識別情報により識別される１つのビットの値を変化させ、そのビットの値の変化に基づいて、ローカルフィールドｈ１〜ｈＮの値を更新する。更新後の各値は、保持部１１ａに保持される。
【００３２】
たとえば、更新ビット選択回路１２がｋ番目のビットとｌ番目のビットを識別する識別情報を出力した場合、更新回路１３は、以下のように２つのビットの値を順に変化させるとともに、ローカルフィールドｈ１〜ｈＮの値を更新する。
【００３３】
ｋ≠ｌの場合、更新回路１３は、ｋ番目のビット（変数ｘｋ）の値を１−ｘｋに変える。そして、更新回路１３は、ローカルフィールドｈｉ（ｉ＝１，２，…，Ｎ（ただしｉ≠ｋ））を、ｈｉ＋Ｗｋｉ・Δｘｋに更新する（Δｘｋ＝１−２ｘｋ）。また、更新回路１３は、ｌ番目のビット（変数ｘｌ）の値を１−ｘｌに変える。そして、更新回路１３は、更新されたローカルフィールドｈｉ（ｉ＝１〜Ｎ（ただしｉ≠ｌ））を、さらに、ｈｉ＋Ｗｌｉ・Δｘｌに更新する（Δｘｌ＝１−２ｘｌ）。
【００３４】
ｋ＝ｌの場合、更新回路１３は、変数ｘｋを１−ｘｋに変える。そして、更新回路１３は、ローカルフィールドｈｉ（ｉ＝１〜Ｎ（ただしｉ≠ｋ））を、ｈｉ＋Ｗｋｉ・Δｘｋに更新する。
【００３５】
このような各ローカルフィールドｈｉ（ｉ＝１〜Ｎ）を計算する処理は、以下の式（４）で表されるように、並列処理が可能である。
【００３６】
【数４】
2020021209.tif 000006
【００３７】
なお、更新回路１３は、上記のような更新処理を行うために、たとえば、現在の変数ｘｉ（ｉ＝１〜Ｎ）とローカルフィールドｈｉの値を、保持部１１ａから取得し、重み値Ｗｋｉ，Ｗｌｉを、算出回路内の記憶部（たとえば、記憶部１１ｃ１１）から取得する。更新回路１３は、セレクタと乗算器と加算器を用いて実現できる。
【００３８】
制御部１４は、最適化装置１０の外部の制御装置２０（たとえば、ＰＣ（Personal Computer））との間で情報の送受信を行う。たとえば、制御部１４は、制御装置２０からイジングモデルを表現する重み値Ｗｉｊやバイアス係数ｂｉを受け、重み値Ｗｉｊを演算部１１の算出回路１１ｃ１の記憶部１１ｃ１１などに記憶する。また、制御部１４は、変数ｘｉ（ｉ＝１〜Ｎ）の初期値（たとえば、全て０）を保持部１１ａに設定するとともに、変数ｘｉの初期値と重み値Ｗｉｊとバイアス係数ｂｉに基づいてローカルフィールドｈｉの初期値を計算し、保持部１１ａに設定してもよい。また、制御部１４は、制御装置２０から、アニーリング条件（温度パラメータＴの最大値、最小値、温度パラメータＴの値の下げ方についての情報など）を受け、アニーリング条件に基づいて、更新ビット選択回路１２に温度パラメータＴを設定する。制御部１４は、アニーリング条件に基づいて、温度パラメータＴの値を徐々に小さくしていく。また、制御部１４は、温度パラメータＴの値を所定回数、小さくした場合（または温度パラメータＴが最小値に達した場合）の各ビットの値（変数ｘｉ（ｉ＝１〜Ｎ））を保持部１１ａから取得し、解として制御装置２０に送信する。
【００３９】
制御部１４は、たとえば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの特定用途の電子回路にて実現できる。なお、制御部１４は、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）などのプロセッサであってもよい。その場合、プロセッサは、図示しないメモリに記憶されたプログラムを実行することで、上記の処理を行う。また、制御部１４の機能は、制御装置２０に含まれていてもよい。
【００４０】
図２は、更新ビット選択回路の一例を示す図である。
更新ビット選択回路１２は、符号反転部１２ａ、オフセット加算部１２ｂ、乱数発生回路１２ｃ、選択法則適用部１２ｄ、乗算器１２ｅ、比較部１２ｆ、セレクタ１２ｇを有する。
【００４１】
符号反転部１２ａは、エネルギー変化ΔＥ１，ΔＥ１２，…，ΔＥＮのそれぞれに−１を掛けて符合を反転させる。
オフセット加算部１２ｂは、符号反転部１２ａの出力値（−ΔＥ１，−ΔＥ１２，…，−ΔＥＮ）のそれぞれに、オフセット値を加える。オフセット加算部１２ｂは、後述するセレクタ１２ｇが出力するステータス信号に含まれるフラグが、状態遷移を許容しないことを示すとき（つまり状態遷移が生じないとき）、オフセット値を増加していく。一方、オフセット加算部１２ｂは、フラグが、状態遷移を許容することを示すとき（つまり状態遷移が生じるとき）には、オフセット値を０にする。オフセット値が大きくなると状態遷移が許容されやすくなり、現在の状態が局所解にある場合、その局所解からの脱出が促進される。
【００４２】
乱数発生回路１２ｃは、０以上、１以下の一様乱数ｒを発生する。
選択法則適用部１２ｄは、シミュレーテッド・アニーリングを行うための選択法則（メトロポリス法またはギブス法）に基づいた値を出力する。
【００４３】
シミュレーテッド・アニーリングが行われる場合、あるエネルギー変化ΔＥを引き起こす状態遷移の許容確率Ａ（ΔＥ，Ｔ）を以下の式（５）のように決めれば、時刻（反復回数）無限大の極限で状態が最適解に到達することが証明されている。
【００４４】
【数５】
2020021209.tif 000007
【００４５】
式（５）においてＴは、前述の温度パラメータＴである。
式（５）で表される許容確率Ａ（ΔＥ，Ｔ）を用いた場合、十分な反復後に定常状態に達したとすると、各状態の占有確率は熱力学における熱平衡状態に対するボルツマン分布にしたがう。そして、高い温度から徐々に下げていくとエネルギーの低い状態の占有確率が増加するため、十分温度が下がるとエネルギーの低い状態が得られるはずである。この様子が材料を焼き鈍したときの状態変化とよく似ているため、この方法はシミュレーテッド・アニーリングと呼ばれるのである。このとき、エネルギーが上がる状態遷移が確率的に起こることは、物理学における熱励起に相当する。
【００４６】
許容確率Ａ（ΔＥ，Ｔ）でエネルギー変化ΔＥを引き起こす状態遷移を許容することを示すフラグ（＝１）を出力する回路は、式（５）のｆ（−ΔＥ／Ｔ）と、一様乱数ｒとの比較結果に基づいた値を出力する比較器によって実現できる。
【００４７】
ただ、次のような変形を行っても同じ機能が実現できる。２つの数に同じ単調増加関数を作用させても大小関係は変化しない。したがって比較器の２つの入力に同じ単調増加関数を作用させても比較器の出力は変わらない。たとえば、ｆ（−ΔＥ／Ｔ）に作用させる単調増加関数としてｆ（−ΔＥ／Ｔ）の逆関数ｆ−１（−ΔＥ／Ｔ）、一様乱数ｒに作用させる単調増加関数としてｆ−１（−ΔＥ／Ｔ）の−ΔＥ／Ｔをｒとしたｆ−１（ｒ）を用いることができる。その場合、上記の比較器と同様の機能を有する回路は、−ΔＥ／Ｔがｆ−１（ｒ）より大きいとき１を出力する回路でよいことがわかる。さらに温度パラメータＴが正であることから、その回路は、−ΔＥがＴ・ｆ−１（ｒ）より大きいとき１を出力する回路でよい。
【００４８】
選択法則適用部１２ｄは、入力される一様乱数ｒを上記のｆ−１（ｒ）の値に変換する変換テーブルを用いて、ｆ−１（ｒ）の値を出力する。メトロポリス法が適用される場合、ｆ−１（ｒ）は、ｌｏｇ（ｒ）である。変換テーブルは、たとえば、ＲＡＭ（Random Access Memory）、フラッシュメモリなどのメモリに記憶されている。
【００４９】
乗算器１２ｅは、制御部１４から供給される温度パラメータＴと、ｆ−１（ｒ）との積（Ｔ・ｆ−１（ｒ））を出力する。Ｔ・ｆ−１（ｒ）は、熱励起エネルギーに相当する。
比較部１２ｆは、エネルギー変化ΔＥ１，ΔＥ１２，…，ΔＥＮのそれぞれについてのオフセット加算部１２ｂによる加算結果と、Ｔ・ｆ−１（ｒ）とを比較し、Ｔ・ｆ−１（ｒ）より大きい加算結果に対するフラグとして、１を出力する。また、比較部１２ｆは、Ｔ・ｆ−１（ｒ）より小さい加算結果に対するフラグとして、０を出力する。
【００５０】
セレクタ１２ｇは、エネルギー変化ΔＥ１，ΔＥ１２，…，ΔＥＮのそれぞれについてのフラグに基づいて、状態遷移が許容された２つのビット（または１つのビット）の識別情報とフラグを含むステータス信号を出力する。このようなセレクタ１２ｇは、Ｎ２：１セレクタにより実現される。なお、エネルギー変化ΔＥ１，ΔＥ１２，…，ΔＥＮのそれぞれについてのフラグが全て０である場合には、セレクタ１２ｇが出力するステータス信号に含まれるフラグも０である。
【００５１】
図３は、Ｎ２：１セレクタの一例を示す図である。
Ｎ２：１セレクタであるセレクタ１２ｇは、Ｎ個のＮ：１セレクタ１２ｇａ１，１２ｇａ２，…，１２ｇａＮと、１つのＮ：１セレクタ１２ｇｂを有する。
【００５２】
Ｎ：１セレクタ１２ｇａ１〜１２ｇａＮのそれぞれは、Ｎ個のフラグを受ける。たとえば、Ｎ：１セレクタ１２ｇａ１は、エネルギー変化ΔＥ１，ΔＥ２１，…，ΔＥＮ１についてのフラグｆｇ１，ｆｇ２１，…，ｆｇＮ１を受ける。そして、Ｎ：１セレクタ１２ｇａ１は、フラグｆｇ１〜ｆｇＮ１のうち、値が１であるフラグを優先的に１つ選択し、選択したフラグとそのフラグに対応した識別情報を出力する。つまり、識別情報は、Ｎ：１セレクタ１２ｇａ１により生成される。このように識別情報を生成するＮ：１セレクタの例については、たとえば、特許文献２に開示されている。Ｎ：１セレクタ１２ｇａ２〜１２ｇａＮについても同様である。
【００５３】
Ｎ：１セレクタ１２ｇｂは、Ｎ：１セレクタ１２ｇａ１〜１２ｇａＮが出力するフラグと識別情報とを受け、値が１であるフラグを優先的に１つ選択する。そして、Ｎ：１セレクタ１２ｇｂは、選択したフラグｆｇｋｌとフラグｆｇｋｌに対応した識別情報（ｉｎｄｅｘ（ｋ，ｌ））を含むステータス信号（ｓｔａｔｕｓ）を出力する。
【００５４】
以下、第１の実施の形態の最適化装置１０の動作例を示す図である。
図４は、第１の実施の形態の最適化装置の動作の一例の流れを示すフローチャートである。
【００５５】
まず、制御部１４は、制御装置２０から受けた重み値Ｗｉｊを演算部１１の算出回路１１ｃ１の記憶部１１ｃ１１などに記憶する（ステップＳ１）。
また、制御部１４は、制御装置２０から受けたアニーリング条件に基づいて、更新ビット選択回路１２に温度パラメータＴの初期値を設定する（ステップＳ２）。
【００５６】
Ｎ×Ｎの算出回路の各々は、自身が担当するエネルギー変化の計算に用いる変数ｘｉとローカルフィールドｈｉの値を、保持部１１ａから読み出す（ステップＳ３）。
そして、Ｎ×Ｎの算出回路の各々は、前述のように、エネルギー変化ΔＥｉｊ、またはエネルギー変化ΔＥｉを計算する（ステップＳ４）。
【００５７】
更新ビット選択回路１２は、Ｎ×Ｎの算出回路の各々から、エネルギー変化ΔＥｉｊ、またはエネルギー変化ΔＥｉを受け、それらの符号を反転させた値に対して、オフセット値を加算する（ステップＳ５）。
【００５８】
そして、更新ビット選択回路１２は、前述の処理により、状態遷移を許容するビットを識別する識別情報（ｉｎｄｅｘ（ｋ，ｌ））を選択する（ステップＳ６）。
更新回路１３は、更新ビット選択回路１２が選択し、出力した識別情報により識別される２つまたは１つのビット（変数ｘｉ（ｉ＝ｋ，ｌ））の値を変化させる。また、更新回路１３は、その変化に基づいて、ローカルフィールドｈｉ（ｉ＝１〜Ｎ）の値を、前述の処理により更新する（ステップＳ７）。
【００５９】
更新後の変数ｘｉとローカルフィールドｈｉの各値は、保持部１１ａに書き込まれる（ステップＳ８）。
制御部１４は、ステップＳ３〜Ｓ８の更新処理が所定回数Ｎ１、繰り返されたか否かを判定する（ステップＳ９）。更新処理が所定回数Ｎ１、繰り返されていない場合には、ステップＳ３〜Ｓ８の更新処理が繰り返される。
【００６０】
更新処理が所定回数Ｎ１、繰り返された場合、制御部１４は、温度パラメータの変更回数（温度変更回数）が、所定回数Ｎ２に達したか否かを判定する（ステップＳ１０）。
温度変更回数が所定回数Ｎ２に達していない場合、制御部１４は、温度パラメータを変更する（温度を下げる）（ステップＳ１１）。所定回数Ｎ１，Ｎ２、温度パラメータの値の変更の仕方（一度に値をどのくらい小さくするかなど）は、アニーリング条件に基づいて決定される。ステップＳ１１の処理後、ステップＳ３からの処理が繰り返される。
【００６１】
温度変更回数が所定回数Ｎ２に達している場合、制御部１４は、そのときの各ビットの値（変数ｘｉ（ｉ＝１〜Ｎ））を保持部１１ａから取得して、解（計算結果）として制御装置２０に送信（出力）する（ステップＳ１２）。
【００６２】
以上のような第１の実施の形態の最適化装置１０によれば、２つのビットの値が順に変化することによるエネルギー変化に基づいて、２つのビットの値の更新の可否を決定するため、ハミング距離が２の近傍状態の探索が可能となる。これにより、温度が低くなるアニーリング終盤のように、変化するビットが得られる確率が小さい状況でも、最適解の探索速度が低下することを抑制できる。また、探索速度の低下を抑制できることにより、上記のように更新処理回数や温度変更回数などが決まっている場合には、それらの回数の範囲内で得られる解の正解率を高めることができる。
【００６３】
また、重み値Ｗｉｊは、記憶部１１ｃ１１などとは別のメモリに記憶しておいてもよいが、エネルギー変化ΔＥｉｊを算出する回路内の記憶部１１ｃ１１などに記憶しておくことで、エネルギー変化ΔＥｉｊを算出する際のメモリアクセスを減らすことができる。
【００６４】
（第２の実施の形態）
前述のようにＮ×Ｎ個の算出回路のうち、対角部分以外の算出回路は、２つのビットが順に変化するときのエネルギー変化ΔＥｉｊを算出する。このエネルギー変化ΔＥｉｊを計算する途中に、対角部分以外の算出回路は、まず１つのビットが変化したときのローカルフィールドの値を算出することもできる。ｉ番目のビット（変数ｘｉ）の値が変化したときの、各ビットについてのローカルフィールドｈ１（ｉ），ｈ２（ｉ），…，ｈＮ（ｉ）の値は、以下の式（６）のように表せる。
【００６５】
【数６】
2020021209.tif 000008
【００６６】
以下に示す第２の実施の形態の最適化装置のＮ×Ｎ個の算出回路は、上記のローカルフィールドｈ１（ｉ），ｈ２（ｉ），…，ｈＮ（ｉ）（ｉ＝１〜Ｎ）の値を算出する機能を有する。
【００６７】
図５は、第２の実施の形態の最適化装置の一例を示す図である。図５において、図１に示した要素と同じ要素については同一符号が付されている。
第２の実施の形態の最適化装置３０は、演算部３１と更新回路３２が、第１の実施の形態の最適化装置１０と異なっている。
【００６８】
最適化装置３０において、演算部３１のＮ×Ｎ個の算出回路は、ローカルフィールドｈ１（ｉ），ｈ２（ｉ），…，ｈＮ（ｉ）の値を算出し、さらにローカルフィールドｈ１（ｉ），ｈ２（ｉ），…，ｈＮ（ｉ）の値から、エネルギー変化ΔＥ１，ΔＥ１２，…，ΔＥＮを算出する。
【００６９】
Ｎ×Ｎ個の算出回路のうち、マトリクスの対角部分に配置されている算出回路３１ａ１，３１ａ２，…，３１ａＮは、ローカルフィールドｈ１（１），ｈ２（２），…，ｈＮ（Ｎ）の値を出力する。重み値Ｗｉｉ＝０であるため、式（６）より、ローカルフィールドｈ１（１），ｈ２（２），…，ｈＮ（Ｎ）の値は、算出回路３１ａ１，３１ａ２，…，３１ａＮが保持部１１ａから読み出した現在のローカルフィールドｈ１，ｈ２，…，ｈＮの値と同じである。このため、算出回路３１ａ１，３１ａ２，…，３１ａＮは、第１の実施の形態の最適化装置１０における算出回路１１ｂ１，１１ｂ２，…，１１ｂＮと同様に、ローカルフィールドｈｉの値と、変数ｘｉの値に基づいて、エネルギー変化ΔＥｉを算出する。
【００７０】
なお、最適化装置３０が常にハミング距離＝２の近傍状態の探索を行う場合には、算出回路３１ａ１〜３１ａＮはなくてもよい。
Ｎ×Ｎ個の算出回路のうち、算出回路３１ａ１〜３１ａＮ以外（算出回路３１ｂ１，３１ｂ２，３１ｂ３，３１ｂ４，３１ｂ５，３１ｂ６など）は、ローカルフィールドｈｊ（ｉ）（ｉ≠ｊ）の値を算出する。
【００７１】
たとえば、算出回路３１ｂ１は、保持部１１ａから読み出した変数ｘ１の値に応じて＋１または−１となるΔｘ１を、記憶している重み値Ｗ１２に掛けることで、Δｘ１Ｗ１２を求める。さらに、算出回路３１ｂ１は、保持部１１ａから読み出したローカルフィールドｈ２の値に、Δｘ１Ｗ１２を加算することで、ローカルフィールドｈ２（１）の値を算出する。
【００７２】
また、Ｎ×Ｎ個の算出回路のうち、算出回路３１ａ１〜３１ａＮ以外は、ローカルフィールドｈｊ（ｉ）（ｉ≠ｊ），ｈｉ、変数ｘｉ，ｘｊの値から、以下の式（７）により、エネルギー変化ΔＥｉｊ（ｉ≠ｊ）を算出する。
【００７３】
ΔＥｉｊ＝−Δｘｉｈｉ−Δｘｊｈｊ（ｉ）              （７）
たとえば、算出回路３１ｂ１は、保持部１１ａから読み出したローカルフィールドｈ１の値に−Δｘ１を掛け、−Δｘ１ｈ１を求める。さらに、算出回路３１ｂ１は、保持部１１ａから読み出した変数ｘ２の値に応じて＋１または−１となる−Δｘ２を、算出したローカルフィールドｈ２（１）の値に掛けることで、−Δｘ２ｈ２（１）を求める。そして、算出回路３１ｂ１は、−Δｘ１ｈ１と−Δｘ２ｈ２（１）を加算することで、エネルギー変化ΔＥ１２を算出する。
【００７４】
このような算出回路３１ｂ１は、セレクタと乗算器と加算器を用いて実現できる。他の算出回路（算出回路３１ｂ２〜３１ｂ６など）についても同様である。
更新回路３２は、第１の実施の形態の最適化装置３０の更新回路１３と同様に、更新ビット選択回路１２が出力する識別情報により識別されるビットの値を変化させるとともに、ローカルフィールドｈ１〜ｈＮの値を更新する。
【００７５】
ただ、更新回路３２は、識別情報に基づいて、Ｎ×Ｎ個の算出回路が算出したローカルフィールドｈ１（ｉ），ｈ２（ｉ），…，ｈＮ（ｉ）（ｉ＝１〜Ｎ）の値の何れかを選択し、選択した値を用いて、ローカルフィールドｈ１〜ｈＮの値を更新する。
【００７６】
たとえば、更新ビット選択回路１２がｋ番目のビットとｌ番目のビットを識別する識別情報を出力した場合、更新回路３２は、以下のように２つのビットの値を順に変化させるとともに、ローカルフィールドｈ１〜ｈＮの値を更新する。
【００７７】
ｋ≠ｌの場合、更新回路３２は、ｋ番目のビット（変数ｘｋ）の値を１−ｘｋに変え、ｌ番目のビット（変数ｘｌ）の値を１−ｘｌに変える。また、更新回路３２は、ローカルフィールドｈｉ（ｉ＝１，２，…，Ｎ）を、ｈｉ（ｋ）＋Ｗｌｉ・Δｘｌに更新する（Δｘｌ＝１−２ｘｌ）。
【００７８】
ｋ＝ｌの場合、更新回路３２は、変数ｘｋを１−ｘｋに変える。そして、更新回路３２は、ローカルフィールドｈｉを、ｈｉ（ｋ）に更新する。
更新回路３２は、上記のような更新処理を行う際に、ローカルフィールドｈ１（ｉ），ｈ２（ｉ），…，ｈＮ（ｉ）の値を用いるため、重み値Ｗｋｉの読み出しが不要になり、第１の実施の形態の最適化装置１０よりも、メモリアクセスを減らすことができる。
【００７９】
第２の実施の形態の最適化装置３０による計算処理の流れは、図４に示したような処理の流れとほぼ同様である。ただ、図４のステップＳ３とステップＳ４の処理の間に、上記のようなローカルフィールドｈ１（ｉ），ｈ２（ｉ），…，ｈＮ（ｉ）を算出する処理が追加される。
【００８０】
以上のような第２の実施の形態の最適化装置３０によれば、第１の実施の形態の最適化装置１０と同様の効果が得られるとともに、上記のように、メモリアクセスを減らすことができる。
【００８１】
（第３の実施の形態）
上記の説明では、ハミング距離が２の近傍状態の探索を可能とする最適化装置１０，３０を説明したが、ハミング距離が３以上の近傍状態の探索を可能とする最適化装置に拡張することもできる。
【００８２】
変数ｘｉ，ｘｊ，ｘｋ，…（ｉ≠ｊ≠ｋ…）の値が順に変化する場合のエネルギー変化ΔＥｉｊｋ…は、以下の式（８）のように表せる。
ΔＥｉｊｋ…＝−Δｘｉｈｉ−Δｘｊｈｊ（ｉ）−Δｘｋｈｋ（ｉｊ）−…          （８）
式（８）においてローカルフィールドｈｊ（ｉ），ｈｋ（ｉｊ）は、以下の式（９）により算出できる。
【００８３】
【数７】
2020021209.tif 000009
【００８４】
なお、ｈｊ（ｉ）は、ｈｊ（ｉ）＝ｈｊ＋ΔｘｉＷｉｊと表せ、ｈｋ（ｉｊ）は、ｈｋ（ｉｊ）＝ｈｋ＋ΔｘｉＷｉｋ＋ΔｘｊＷｊｋと表せる。そのため、たとえば、変数ｘｉ，ｘｊ，ｘｋの値が順に変化したときの（ハミング距離が３の近傍状態の）エネルギー変化は、変化前の変数ｘｉ，ｘｊ，ｘｋの値と、重み値Ｗｉｊ，Ｗｉｋ，Ｗｊｋ、ローカルフィールドｈｉ，ｈｊ，ｈｋから算出できる。以下、ハミング距離が３の近傍状態のエネルギー変化を算出する演算部の一例を示す。
【００８５】
図６は、ハミング距離が３の近傍状態のエネルギー変化を算出する演算部の一例を示す図である。
演算部４０は、各々エネルギー変化ΔＥ１１１〜ΔＥＮＮＮの何れかを算出するＮ３個の算出回路を有し、たとえば、図６に示されているように、Ｎ３個の算出回路は、３次元アレイ状に配置されている。
【００８６】
Ｎ個の算出回路群４１ａ１，４１ａ２，…，４１ａＮのうち、算出回路群４１ａ１は、変数ｘｉ，ｘｊ，ｘ１の値が順に変化したときのエネルギー変化ΔＥｉｊ１をそれぞれ算出するＮ×Ｎ個の算出回路（算出回路４１ｂ１，４１ｂ２，４１ｂ３など）を有する。Ｎ×Ｎ個の算出回路には、最後に変化する変数ｘ１とローカルフィールドｈ１の組のほか、１番目に変化する変数ｘｉとローカルフィールドｈｉの組と、２番目に変化する変数ｘｊとローカルフィールドｈｊの組が、図１に示したような保持部１１ａから読み出される。
【００８７】
たとえば、算出回路４１ｂ３は、変数ｘ１，ｘ３，ｘ５と、ローカルフィールドｈ１，ｈ３，ｈ５の値を用いてエネルギー変化ΔＥ３５１を算出する。式（８）より、ΔＥ３５１＝−Δｘ３ｈ３−Δｘ５ｈ５（３）−Δｘ１ｈ１（３５）と表せ、ｈ５（３）は、ｈ５（３）＝ｈ５＋Δｘ３Ｗ３５と表せ、ｈ１（３５）は、ｈ１（３５）＝ｈ１＋Δｘ３Ｗ３１＋Δｘ５Ｗ５１と表せる。したがって、算出回路４１ｂ３は、重み値Ｗ３１，Ｗ３５，Ｗ５１を保持しておけば、変数ｘ１，ｘ３，ｘ５と、ローカルフィールドｈ１，ｈ３，ｈ５の値から、エネルギー変化ΔＥ３５１を算出することができる。
【００８８】
他の算出回路群４１ａ２〜４１ａＮについてもそれぞれＮ×Ｎ個の算出回路を有し、エネルギー変化ΔＥｉｊ２〜ΔＥｉｊＮを算出する。
なお、エネルギー変化ΔＥｉｊｋ（ｉ＝ｊ＝ｋ）は、１つの変数ｘｉが１回だけ変化したときのエネルギー変化ΔＥｉと同じであるため、エネルギー変化ΔＥｉｊｋ（ｉ＝ｊ＝ｋ）を算出する算出回路は、エネルギー変化ΔＥｉ＝−Δｘｉｈｉを算出する回路でよい。たとえば、エネルギー変化ΔＥ１１１を算出する算出回路４１ｂ１は、ΔＥ１＝−Δｘ１ｈ１を算出する回路でよい。
【００８９】
また、エネルギー変化ΔＥｉｊｋ（ｉ＝ｊ≠ｋまたはｉ≠ｊ＝ｋ）は、１つの変数ｘｋが１回だけ変化したときのエネルギー変化ΔＥｋと同じである。ハミング距離が１の近傍状態のエネルギー変化ΔＥｉを算出する回路を既に設けている場合、エネルギー変化ΔＥｉｊｋ（ｉ＝ｊ≠ｋまたはｉ≠ｊ＝ｋ）を算出する算出回路の代りに、ハミング距離が２の近傍状態のエネルギー変化を算出する回路を設けてもよい。たとえば、エネルギー変化ΔＥ２１１を算出する算出回路４１ｂ２は、ΔＥ２１＝−Δｘ２ｈ２−Δｘ１ｈ１−Δｘ２・Δｘ１・Ｗ２１を算出する回路でよい。
【００９０】
第３の実施の形態の最適化装置では、前述の更新ビット選択回路１２の代りに、Ｎ３のエネルギー変化ΔＥｉｊｋ〜ΔＥｉｊｋと熱励起エネルギーとの大小関係に基づいて、更新を許容する３つのビットの識別情報を出力する更新ビット選択回路が用いられる。その更新ビット選択回路に含まれるセレクタとして、たとえば、以下のようなＮ３：１セレクタが用いられる。
【００９１】
図７は、第３の実施の形態の最適化装置におけるＮ３：１セレクタの一例を示す図である。
Ｎ３：１セレクタ５０は、エネルギー変化ΔＥ１１１〜ΔＥＮＮＮのそれぞれを引き起こす状態遷移を許容するか否かを示すＮ３個のフラグｆｇ１１１〜ｆｇＮＮＮのうち、値が１であるフラグを優先的に１つ選択する。そして、Ｎ３：１セレクタ５０は、選択したフラグｆｇｉｊｋと、フラグｆｇｉｊｋに対応した識別情報（ｉｎｄｅｘ（ｉ，ｊ，ｋ））を含むステータス信号（ｓｔａｔｕｓ）を出力する。
【００９２】
Ｎ３：１セレクタ５０は、セレクタ群５１ａ１，５１ａ２，…，５１ａＮとＮ：１セレクタ５２を有する。
セレクタ群５１ａ１〜５１ａＮのそれぞれは、Ｎ×Ｎのフラグのうち、値が１であるフラグを優先的に１つ選択し、選択したフラグとそのフラグに対応した識別情報を出力する。たとえば、セレクタ群５１ａ１は、Ｎ：１セレクタ５１ｂ１，５１ｂ２，…，５１ｂＮ，５１ｃＮを有する。
【００９３】
Ｎ：１セレクタ５１ｂ１〜５１ｂＮのそれぞれは、Ｎ個のフラグのうち、値が１であるフラグを優先的に１つ選択し、選択したフラグとそのフラグに対応した識別情報を出力する。たとえば、Ｎ：１セレクタ５１ｂ１は、エネルギー変化ΔＥｉ１１（ｉ＝１〜Ｎ）についてのフラグｆｇｉ１１（ｉ＝１〜Ｎ）のうち、値が１であるフラグを優先的に１つ選択し、選択したフラグとそのフラグに対応した識別情報を出力する。なお、フラグｆｇｉ１１が全て０の場合には、出力されるフラグも０となる。
【００９４】
Ｎ：１セレクタ５１ｃＮは、Ｎ：１セレクタ５１ｂ１〜５１ｂＮが出力したフラグのうち、値が１であるフラグを優先的に１つ選択し、選択したフラグとそのフラグに対応した識別情報を出力する。なお、Ｎ：１セレクタ５１ｂ１〜５１ｂＮが出力したフラグが全て０である場合、出力されるフラグも０となる。
【００９５】
他のセレクタ群５１ａ２〜５１ａＮもセレクタ群５１ａ１と同様の構成である。
Ｎ：１セレクタ５２は、セレクタ群５１ａ１〜５１ａＮのそれぞれが出力するフラグのうち、値が１であるフラグを優先的に１つ選択し、選択したフラグｆｇｉｊｋとフラグｆｇｉｊｋに対応した識別情報（ｉｎｄｅｘ（ｉ，ｊ，ｋ））を含むステータス信号（ｓｔａｔｕｓ）を出力する。
【００９６】
図示を省略するが、第３の実施の形態の最適化装置における更新回路は、フラグｆｇｉｊｋが１の場合には、識別情報（ｉｎｄｅｘ（ｉ，ｊ，ｋ））により識別される変数ｘｉ，ｘｊ，ｘｋの値を変化させる。また、更新回路は、その変化に基づいて、ローカルフィールドｈ１〜ｈＮの値を更新する。
【００９７】
上記のような演算部４０や、Ｎ３：１セレクタ５０を用いることで、ハミング距離が３の近傍状態の探索を可能とする最適化装置を実現することができる。説明を省略するが、上記と同様の拡張により、ハミング距離ｎ＝４以上の近傍状態の探索を可能とする最適化装置も実現できる。
【００９８】
なお、Ｎｎ（第３の実施の形態の最適化装置ではｎ＝３）の算出回路は、順に変化するｎ個のビットのうち、ｎ−１個のビットが順に変化するときのローカルフィールドの値を算出してもよい。
【００９９】
たとえば、第３の実施の形態の最適化装置のＮ３個の算出回路は、式（９）で表される、ローカルフィールドｈ１（ｉｊ），ｈ２（ｉｊ），…，ｈＮ（ｉｊ）の値、すなわち、２つのビットが順に変化するときのローカルフィールドの値を算出してもよい。第２の実施の形態の最適化装置３０の更新回路３２と同様に、第３の実施の形態の最適化装置における更新回路（図示略）でも、ローカルフィールドｈ１〜ｈＮを更新する際にローカルフィールドｈ１（ｉｊ）〜ｈＮ（ｉｊ）を用いることで、メモリアクセスを減らせる。
【０１００】
（第４の実施の形態）
図８は、第４の実施の形態の最適化装置の一例を示す図である。
第４の実施の形態の最適化装置６０において、制御部６１は、第１の実施の形態の制御部１４と同様の機能を有するとともに、ハミング距離が２の近傍状態の探索機能をオンするかオフするか切り替える機能を有する。
【０１０１】
たとえば、制御部６１は、図８に示されているように、カウンタ６１ａ、比較回路６１ｂ、クロックカウンタ６１ｃを有する。
カウンタ６１ａは、更新ビット選択回路１２が出力するフラグｆｇが１になる回数（更新回数）をカウントする。
【０１０２】
比較回路６１ｂは、カウンタ６１ａのカウント値が、制御装置２０から供給される所定の閾値ｔｈ以上の場合、ハミング距離が２の近傍状態の探索機能をオフする制御信号ｃｎｔを演算部１１に供給する。カウンタ６１ａのカウント値が、制御装置２０から供給される所定の閾値ｔｈより小さい場合、ハミング距離が２の近傍状態の探索機能をオンする制御信号ｃｎｔを演算部１１に供給する。
【０１０３】
クロックカウンタ６１ｃは、クロック信号（図示略）をカウントし、所定カウント数ごとに、比較回路６１ｂをイネーブル状態にするとともに、カウンタ６１ａのカウント値をリセットする。
【０１０４】
つまり、制御部６１は、所定期間におけるビットの更新回数が、閾値ｔｈ以上である場合に、ハミング距離が２の近傍状態の探索機能をオフする。
制御信号ｃｎｔは、たとえば、演算部１１のＮ×Ｎ個の算出回路のうち、対角部分の算出回路１１ｂ１〜１１ｂＮ以外に供給される。そして、制御信号ｃｎｔが、ハミング距離が２の近傍状態の探索機能をオフすることを指示するものである場合、エネルギー変化ΔＥｉｊを算出する機能が無効になる。この場合、ハミング距離が２の近傍状態の探索が行われず、ハミング距離が１の近傍状態の探索が行われる。
【０１０５】
更新頻度が高い場合、ハミング距離が２の近傍状態の探索を行わなくても探索速度は悪化しない。そのため、上記のように、所定期間における更新回数が、閾値ｔｈ以上の場合には、ハミング距離が２の近傍状態の探索機能をオフすることで、最適化装置６０の消費電力を下げることが可能になる。
【０１０６】
図９は、第４の実施の形態の最適化装置の動作の一例の流れを示すフローチャートである。
ステップＳ２０〜Ｓ２７の処理は、図４に示したステップＳ１〜Ｓ８の処理と同じである。図９の例では、ステップＳ２８の処理において、制御部６１は、上記のような、ハミング距離が２の近傍状態の探索機能をオンするかオフするか切り替える処理を行う。なお、ステップＳ２８の処理は、前述のように比較回路６１ｂがイネーブル状態になると行われる処理であり、各繰り返し処理において毎回行われるわけではない。
【０１０７】
ハミング距離が２の近傍状態の探索機能がオフする場合には、次回のステップＳ２３の処理では、ΔＥｉｊの計算は行われない。
ステップＳ２９〜Ｓ３２の処理は、図４に示したステップＳ９〜Ｓ１２の処理と同じである。
【０１０８】
以上のような、第４の実施の形態の最適化装置６０によれば、第１の実施の形態の最適化装置１０と同様の効果が得られるとともに、上記のように所定期間における更新回数が、閾値ｔｈ以上の場合には、消費電力を下げることが可能となる。
【０１０９】
なお、上記のようなハミング距離が２の近傍状態の探索機能をオンするかオフするか切り替える機能を有する制御部６１を、第２の実施の形態の最適化装置３０に適用することも可能である。また、第３の実施の形態の最適化装置における図示しない制御部に、ハミング距離が３の近傍状態の探索機能をオンするかオフするか切り替える機能を持たせることも可能である。
【０１１０】
ところで、上記の第１乃至第４の実施の形態の最適化装置（最適化装置１０，３０，６０など）において制御部１４，６１は、前述のようにＡＳＩＣやＦＰＧＡなどの特定用途の電子回路、またはプロセッサであってもよいし、制御装置２０に含まれていてもよい。
【０１１１】
制御部１４，６１がＰＣなどの制御装置２０に含まれる場合、制御部１４，６１の機能は、制御装置２０内のプロセッサが制御プログラムを実行することで実現される。
図１０は、制御装置のハードウェア例を示す図である。
【０１１２】
制御装置７０は、ＣＰＵ７１、ＲＡＭ７２、ＨＤＤ（Hard Disk Drive）７３、画像信号処理部７４、入力信号処理部７５、媒体リーダ７６、通信インタフェース７７及びインタフェース７８を有する。上記ユニットは、バスに接続されている。
【０１１３】
ＣＰＵ７１は、プログラムの命令を実行する演算回路を含むプロセッサである。ＣＰＵ７１は、ＨＤＤ７３に記憶されたプログラム（たとえば、前述の制御プログラム）やデータの少なくとも一部をＲＡＭ７２にロードし、プログラムを実行する。なお、ＣＰＵ７１は複数のプロセッサコアを備えてもよく、制御装置７０は複数のプロセッサを備えてもよく、前述の処理を複数のプロセッサまたはプロセッサコアを用いて並列に実行してもよい。
【０１１４】
ＲＡＭ７２は、ＣＰＵ７１が実行するプログラムやＣＰＵ７１が演算に用いるデータを一時的に記憶する揮発性の半導体メモリである。なお、制御装置７０は、ＲＡＭ以外の種類のメモリを備えてもよく、複数個のメモリを備えてもよい。
【０１１５】
ＨＤＤ７３は、ＯＳ（Operating System）やミドルウェアやアプリケーションソフトウェアなどのソフトウェアのプログラム、及び、データを記憶する不揮発性の記憶装置である。プログラムには、たとえば、前述の制御部１４，６１の動作を制御装置７０に実行させる制御プログラムが含まれる。なお、制御装置７０は、フラッシュメモリやＳＳＤ（Solid State Drive）などの他の種類の記憶装置を備えてもよく、複数の不揮発性の記憶装置を備えてもよい。
【０１１６】
画像信号処理部７４は、ＣＰＵ７１からの命令にしたがって、制御装置７０に接続されたディスプレイ７４ａに画像（たとえば、最適化問題の計算結果を表す画像）を出力する。ディスプレイ７４ａとしては、ＣＲＴ（Cathode Ray Tube）ディスプレイ、液晶ディスプレイ（ＬＣＤ：Liquid Crystal Display）、プラズマディスプレイ（ＰＤＰ：Plasma Display Panel）、有機ＥＬ（ＯＥＬ：Organic Electro-Luminescence）ディスプレイなどを用いることができる。
【０１１７】
入力信号処理部７５は制御装置７０に接続された入力デバイス７５ａから入力信号を取得し、ＣＰＵ７１に出力する。入力デバイス７５ａとしては、マウスやタッチパネルやタッチパッドやトラックボールなどのポインティングデバイス、キーボード、リモートコントローラ、ボタンスイッチなどを用いることができる。また、制御装置７０に、複数の種類の入力デバイスが接続されていてもよい。
【０１１８】
媒体リーダ７６は、記録媒体７６ａに記録されたプログラムやデータを読み取る読み取り装置である。記録媒体７６ａとして、たとえば、磁気ディスク、光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）、半導体メモリなどを使用できる。磁気ディスクには、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤが含まれる。光ディスクには、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）が含まれる。
【０１１９】
媒体リーダ７６は、たとえば、記録媒体７６ａから読み取ったプログラムやデータを、ＲＡＭ７２やＨＤＤ７３などの他の記録媒体にコピーする。読み取られたプログラムは、たとえば、ＣＰＵ７１によって実行される。なお、記録媒体７６ａは、可搬型記録媒体であってもよく、プログラムやデータの配布に用いられることがある。また、記録媒体７６ａやＨＤＤ７３を、コンピュータ読み取り可能な記録媒体ということがある。
【０１２０】
通信インタフェース７７は、ネットワーク７７ａに接続され、ネットワーク７７ａを介して他の情報処理装置と通信を行うインタフェースである。通信インタフェース７７は、スイッチなどの通信装置とケーブルで接続される有線通信インタフェースでもよいし、基地局と無線リンクで接続される無線通信インタフェースでもよい。
【０１２１】
インタフェース７８は、最適化装置７８ａと通信を行うインタフェースである。前述の制御部１４，６１の機能を、制御装置７０が行う場合、最適化装置７８ａは、たとえば、図１や図９に示した最適化装置１０，６０から、制御部１４，６１を除いた装置である。
【０１２２】
図１１は、制御装置による最適化装置の制御方法の流れを示すフローチャートである。
制御装置７０は、重み値の設定を行う（ステップＳ４０）。ステップＳ４０の処理では、制御装置７０は、最適化装置７８ａに重み値を送信し、図１に示した演算部１１の対角部分以外の算出回路に、重み値を記憶させる。
【０１２３】
また、制御装置７０は、最適化装置７８ａに温度パラメータＴの初期値を送信する（ステップＳ４１）。
その後、制御装置７０は、たとえば、最適化装置７８ａが前述の更新処理を行うたびに送信する信号を受信し、更新処理が所定回数Ｎ１、繰り返されたか否かを判定する（ステップＳ４２）。更新処理が所定回数Ｎ１、繰り返されていない場合には、ステップＳ４２の処理が繰り返される。
【０１２４】
更新処理が所定回数Ｎ１、繰り返された場合、制御装置７０は、温度パラメータＴの変更回数（温度変更回数）が、所定回数Ｎ２に達したか否かを判定する（ステップＳ４３）。
【０１２５】
温度変更回数が所定回数Ｎ２に達していない場合、制御装置７０は、温度パラメータＴを変更する（温度を下げる）（ステップＳ４４）。ステップＳ４４の処理では、制御装置７０は、前回送信した値よりも小さい温度パラメータＴの値を、最適化装置７８ａに送信する。所定回数Ｎ１，Ｎ２、温度パラメータの値の変更の仕方（一度に値をどのくらい小さくするかなど）は、アニーリング条件に基づいて決定される。ステップＳ４４の処理後、ステップＳ４２からの処理が繰り返される。
【０１２６】
温度変更回数が所定回数Ｎ２に達している場合、制御装置７０は、そのときの各ビットの値（変数ｘｉ（ｉ＝１〜Ｎ））を最適化問題の計算結果として最適化装置７８ａから受信する（ステップＳ４５）。
【０１２７】
その後、制御装置７０は、受信した計算結果を、たとえば、図１０に示したディスプレイ７４ａに表示し（ステップＳ４６）、最適化装置７８ａの制御を終える。
なお、前述のように、上記の制御装置７０の処理内容は、コンピュータにプログラムを実行させることで実現できる。
【０１２８】
プログラムは、コンピュータ読み取り可能な記録媒体（たとえば、記録媒体７６ａ）に記録しておくことができる。記録媒体として、たとえば、磁気ディスク、光ディスク、光磁気ディスク、半導体メモリなどを使用できる。磁気ディスクには、ＦＤおよびＨＤＤが含まれる。光ディスクには、ＣＤ、ＣＤ−Ｒ（Recordable）／ＲＷ（Rewritable）、ＤＶＤおよびＤＶＤ−Ｒ／ＲＷが含まれる。プログラムは、可搬型の記録媒体に記録されて配布されることがある。その場合、可搬型の記録媒体から他の記録媒体（たとえば、ＨＤＤ５３）にプログラムをコピーして実行してもよい。
【０１２９】
以上、実施の形態に基づき、本発明の最適化装置、最適化装置の制御方法及び最適化装置の制御プログラムの一観点について説明してきたが、これらは一例にすぎず、上記の記載に限定されるものではない。
【符号の説明】
【０１３０】
１０  最適化装置
１１  演算部
１１ａ  保持部
１１ｂ１〜１１ｂＮ，１１ｃ１〜１１ｃ６  算出回路
１１ｃ１１  記憶部
１２  更新ビット選択回路
１３  更新回路
１４  制御部
２０  制御装置
ｈ１〜ｈＮ  ローカルフィールド
Ｔ  温度パラメータ
Ｗ１２，Ｗ１Ｎ，Ｗ２１，Ｗ２Ｎ，ＷＮ１，ＷＮ２  重み値
ｘ１〜ｘＮ  変数
ΔＥ１，ΔＥ１２〜ΔＥＮ  エネルギー変化
【図１】
2020021209.tif 000010
【図２】
2020021209.tif 000011
【図３】
2020021209.tif 000012
【図４】
2020021209.tif 000013
【図５】
2020021209.tif 000014
【図６】
2020021209.tif 000015
【図７】
2020021209.tif 000016
【図８】
2020021209.tif 000017
【図９】
2020021209.tif 000018
【図１０】
2020021209.tif 000019
【図１１】
2020021209.tif 000020