(57)【要約】【課題】３値以上の値をもつ変数を扱う最適化装置の回路規模の増大を抑制する。【解決手段】算出回路１１ｂ１〜１１ｂＮは、それぞれｍ値（ｍは３以上の正の整数）の変数を用いて状態が表される複数のニューロンのうち、状態が更新された第１のニューロンの状態変化方向と、第１のニューロンと第２のニューロンとの間の相互作用の大きさを示す重み係数と、に基づいて、第２のニューロンの状態が、正負両方向に２ｎ（ｎは０以上の整数）変化することによる２つのエネルギー変化を算出する。状態遷移判定回路１１ｃ１〜１１ｃＮは、熱励起エネルギーと、上記２つのエネルギー変化との大小関係に基づいて、２つのエネルギー変化をもたらす第２のニューロンの状態の更新をそれぞれ許容するか否かを判定し、更新を許容するか否かの判定結果を出力するとともに、第２のニューロンの状態が上限値を超えるまたは下限値を下回る更新を制限する。【選択図】図１
2020035179.tif 000002
【特許請求の範囲】
【請求項１】
計算対象の問題を変換したイジングモデルに含まれる複数のスピンに対応し、それぞれｍ値（ｍは３以上の正の整数）の変数を用いて状態が表される複数のニューロンのうち、状態が更新された第１のニューロンの状態変化方向と、前記第１のニューロンと第２のニューロンとの間の相互作用の大きさを示す重み係数と、に基づいて、前記第２のニューロンの状態が、正負両方向に２ｎ（ｎは０以上の整数）変化することによる前記イジングモデルの２つのエネルギー変化を算出する算出回路と、
乱数と温度パラメータとに基づいて決定される熱励起エネルギーと、前記２つのエネルギー変化との大小関係に基づいて、前記２つのエネルギー変化をもたらす前記第２のニューロンの状態の更新をそれぞれ許容するか否かを判定し、更新を許容するか否かの判定結果を出力するとともに、前記第２のニューロンの状態が上限値を超えるまたは下限値を下回る更新を制限する状態遷移判定回路と、
をそれぞれが有し、互いに異なる前記第２のニューロンについての前記判定結果をそれぞれ出力する複数のイジング装置と、
前記複数のイジング装置のそれぞれが出力する前記判定結果に基づいて、更新を許容する前記第２のニューロンを１つ選択するとともに、前記状態変化方向を選択する更新ニューロン選択回路と、
前記更新ニューロン選択回路が選択した前記第２のニューロンの状態を、前記状態変化方向に基づいて更新する状態更新回路と、
を有する最適化装置。
【請求項２】
前記状態遷移判定回路は、前記第２のニューロンの状態が、正または負方向に前記２ｎ変化することにより前記上限値を超える、または前記下限値を下回る場合、前記２つのエネルギー変化のうち、前記上限値を超える、または前記下限値を下回る前記第２のニューロンの状態の変化による第１のエネルギー変化を、所定の正の値に変更した上で、前記第１のエネルギー変化をもたらす前記第２のニューロンの状態の更新を許容するか否かを判定する、
請求項１に記載の最適化装置。
【請求項３】
前記状態遷移判定回路は、前記第２のニューロンの状態が、正または負方向に前記２ｎ変化することにより前記上限値を超える、または前記下限値を下回る場合、前記２つのエネルギー変化をもたらす前記第２のニューロンの状態の更新をそれぞれ許容するか否かの前記判定結果のうち、前記上限値を超える、または前記下限値を下回る前記第２のニューロンの状態の変化による更新を許容するか否かの第１の判定結果を、更新を許容しないことを示す値に変更する、
請求項１に記載の最適化装置。
【請求項４】
前記算出回路は、前記第１のニューロンの状態が、正または負方向に前記２ｎ変化したときに、所定のビット幅をもつ前記重み係数を、前記ｎのビット数分、左シフトした値を用いて、前記２つのエネルギー変化を算出する、
請求項１乃至３の何れか一項に記載の最適化装置。
【請求項５】
前記複数のニューロンのそれぞれについての前記ｎの値を、個々に設定する制御部を有する、
請求項１乃至４の何れか一項に記載の最適化装置。
【請求項６】
計算対象の問題を変換したイジングモデルに含まれる複数のスピンに対応し、それぞれｍ値（ｍは３以上の正の整数）の変数を用いて状態が表される複数のニューロンのうち、状態が更新された第１のニューロンの状態変化方向と、前記第１のニューロンと第２のニューロンとの間の相互作用の大きさを示す重み係数と、に基づいて、前記第２のニューロンの状態が、正負両方向に２ｎ（ｎは０以上の整数）変化することによる前記イジングモデルの２つのエネルギー変化を算出する算出回路と、
乱数と温度パラメータとに基づいて決定される熱励起エネルギーと、前記２つのエネルギー変化との大小関係に基づいて、前記２つのエネルギー変化をもたらす前記第２のニューロンの状態の更新をそれぞれ許容するか否かを判定し、更新を許容するか否かの判定結果を出力するとともに、前記第２のニューロンの状態が上限値を超えるまたは下限値を下回る更新を制限する状態遷移判定回路と、
をそれぞれが有し、互いに異なる前記第２のニューロンについての前記判定結果をそれぞれ出力する複数のイジング装置と、
前記複数のイジング装置のそれぞれが出力する前記判定結果に基づいて、更新を許容する前記第２のニューロンを１つ選択するとともに、前記状態変化方向を選択する更新ニューロン選択回路と、
前記更新ニューロン選択回路が選択した前記第２のニューロンの状態を、前記状態変化方向に基づいて更新する状態更新回路と、
を有する最適化装置に対して、
制御装置が、前記重み係数、前記上限値及び前記下限値を設定し、
前記制御装置が、前記温度パラメータの大きさを制御する、
最適化装置の制御方法。
【請求項７】
計算対象の問題を変換したイジングモデルに含まれる複数のスピンに対応し、それぞれｍ値（ｍは３以上の正の整数）の変数を用いて状態が表される複数のニューロンのうち、状態が更新された第１のニューロンの状態変化方向と、前記第１のニューロンと第２のニューロンとの間の相互作用の大きさを示す重み係数と、に基づいて、前記第２のニューロンの状態が、正負両方向に２ｎ（ｎは０以上の整数）変化することによる前記イジングモデルの２つのエネルギー変化を算出する算出回路と、
乱数と温度パラメータとに基づいて決定される熱励起エネルギーと、前記２つのエネルギー変化との大小関係に基づいて、前記２つのエネルギー変化をもたらす前記第２のニューロンの状態の更新をそれぞれ許容するか否かを判定し、更新を許容するか否かの判定結果を出力するとともに、前記第２のニューロンの状態が上限値を超えるまたは下限値を下回る更新を制限する状態遷移判定回路と、
をそれぞれが有し、互いに異なる前記第２のニューロンについての前記判定結果をそれぞれ出力する複数のイジング装置と、
前記複数のイジング装置のそれぞれが出力する前記判定結果に基づいて、更新を許容する前記第２のニューロンを１つ選択するとともに、前記状態変化方向を選択する更新ニューロン選択回路と、
前記更新ニューロン選択回路が選択した前記第２のニューロンの状態を、前記状態変化方向に基づいて更新する状態更新回路と、
を有する最適化装置に対して、
前記重み係数、前記上限値及び前記下限値を設定し、
前記温度パラメータの大きさを制御する、
処理をコンピュータに実行させる最適化装置の制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適化装置、最適化装置の制御方法及び最適化装置の制御プログラムに関する。
【背景技術】
【０００２】
従来、ノイマン型コンピュータが不得意とする多変数の最適化問題を、イジング型のエネルギー関数を用いた最適化装置（イジングマシンまたはボルツマンマシンと呼ばれる場合もある）によって計算する方法がある。最適化装置は、計算対象の問題を、磁性体のスピンの振る舞いを表すモデルであるイジングモデルに置き換えて計算する。
【０００３】
最適化装置は、たとえば、ニューラルネットワークを用いて問題をモデル化することもできる。その場合、イジングモデルに含まれる複数のスピンに対応した複数のビットのそれぞれが、他のビットの値と、他のビットと自身のビットとの相互作用の大きさを示す重み値（結合係数とも呼ばれる）とに応じて０または１を出力するニューロンとして機能する。最適化装置は、たとえば、シミュレーテッド・アニーリングなどの確率的探索法により、イジングモデルのエネルギー関数の値（以下エネルギーという）の最小値が得られる各ニューロンの状態の組み合わせを、解として求める。
【０００４】
従来、デジタル回路を用いてシミュレーテッド・アニーリングを行うことでエネルギーが最小となる各ニューロンの状態の組み合わせを計算する最適化装置がある（たとえば、特許文献１参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１８−０４１３５１号公報
【特許文献２】特開２０１６−０５１３１４号公報
【特許文献３】特開２００６−０７２６９１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところで、最適化問題の中には、整数計画問題などのように、変数が０と１の２値ではなく３値以上の値をとるものも多い。
しかし、従来の最適化装置で３値以上の値をもつ変数を用いてニューロンの状態を表す場合、１つの変数を複数ビットを用いて表現することにより、ニューロンの状態を更新するか否かを決めるイジングモデルのエネルギー変化を算出するための回路規模が増大してしまう問題がある。
【０００７】
１つの側面では、本発明は、３値以上の値をもつ変数を扱う最適化装置の回路規模の増大を抑制可能な最適化装置、最適化装置の制御方法及び最適化装置の制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
１つの実施態様では、計算対象の問題を変換したイジングモデルに含まれる複数のスピンに対応し、それぞれｍ値（ｍは３以上の正の整数）の変数を用いて状態が表される複数のニューロンのうち、状態が更新された第１のニューロンの状態変化方向と、前記第１のニューロンと第２のニューロンとの間の相互作用の大きさを示す重み係数と、に基づいて、前記第２のニューロンの状態が、正負両方向に２ｎ（ｎは０以上の整数）変化することによる前記イジングモデルの２つのエネルギー変化を算出する算出回路と、乱数と温度パラメータとに基づいて決定される熱励起エネルギーと、前記２つのエネルギー変化との大小関係に基づいて、前記２つのエネルギー変化をもたらす前記第２のニューロンの状態の更新をそれぞれ許容するか否かを判定し、更新を許容するか否かの判定結果を出力するとともに、前記第２のニューロンの状態が上限値を超えるまたは下限値を下回る更新を制限する状態遷移判定回路と、をそれぞれが有し、互いに異なる前記第２のニューロンについての前記判定結果をそれぞれ出力する複数のイジング装置と、前記複数のイジング装置のそれぞれが出力する前記判定結果に基づいて、更新を許容する前記第２のニューロンを１つ選択するとともに、前記状態変化方向を選択する更新ニューロン選択回路と、前記更新ニューロン選択回路が選択した前記第２のニューロンの状態を、前記状態変化方向に基づいて更新する状態更新回路と、を有する最適化装置が提供される。
【０００９】
また、１つの実施態様では、最適化装置の制御方法が提供される。また、１つの実施態様では、最適化装置の制御プログラムが提供される。
【発明の効果】
【００１０】
１つの側面では、本発明は、３値以上の値をもつ変数を扱う最適化装置の回路規模の増大を抑えることができる。
【図面の簡単な説明】
【００１１】
【図１】第１の実施の形態の最適化装置の一例を示す図である。
【図２】第１の実施の形態の最適化装置の動作の一例の流れを示すフローチャートである。
【図３】第２の実施の形態の最適化装置の一例を示す図である。
【図４】１つ目のΔＥ変更部の一例を示す図である。
【図５】２つ目のΔＥ変更部の一例を示す図である。
【図６】遷移可否決定部の一例を示す図である。
【図７】第２の実施の形態の最適化装置の動作の一例の流れを示すフローチャートである。
【図８】第３の実施の形態の最適化装置の一例を示す図である。
【図９】１つ目の定義域確認部の一例を示す図である。
【図１０】２つ目の定義域確認部の一例を示す図である。
【図１１】第３の実施の形態の最適化装置の動作の一例の流れを示すフローチャートである。
【図１２】第４の実施の形態の最適化装置の一例を示す図である。
【図１３】ローカルフィールド更新部においてシフト動作が行われる部分の例を示す図である。
【図１４】第４の実施の形態の最適化装置の動作の一例の流れを示すフローチャートである。
【図１５】制御装置のハードウェア例を示す図である。
【図１６】制御装置による最適化装置の制御方法の一例の流れを示すフローチャートである。
【発明を実施するための形態】
【００１２】
以下、発明を実施するための形態を、図面を参照しつつ説明する。
以下に示す最適化装置は、計算対象の問題を変換したイジングモデルに含まれる複数のスピンに対応する複数のニューロンのそれぞれの状態の組み合わせのうち、エネルギー関数が最小値となるときの状態の組み合わせを探索するものである。各ニューロンは、ｍ値（ｍは３以上の整数）の変数を用いて状態が表される。また、変数は所定のビット幅をもち、変化する際には、正または負方向に２ｎ（ｎは０以上の整数）変化するものとする。
【００１３】
イジング型のエネルギー関数Ｅ（ｘ）は、たとえば、以下の式（１）で定義される。
【００１４】
【数１】
2020035179.tif 000003
【００１５】
右辺の１項目は、全ニューロンから選択可能な２つのニューロンの全組み合わせについて、漏れと重複なく、２つのニューロンの状態と結合係数との積を積算したものである。ｘｉは、ｉ番目のニューロンの状態を表す変数（状態変数とも呼ばれる）、ｘｊは、ｊ番目のニューロンの状態を示す変数であり、Ｗｉｊは、ｉ番目とｊ番目のニューロンの相互作用の大きさを示す重み係数である。なお、Ｗｉｉ＝０である。また、Ｗｉｊ＝Ｗｊｉであることが多い（つまり、重み係数による係数行列は対称行列である場合が多い）。また重み係数Ｗｉｊは、所定のビット幅（たとえば、１６ビット、３２ビット、６４ビット、１２８ビットなど）をもつ。
【００１６】
右辺の２項目は、全ニューロンのそれぞれのバイアス係数とニューロンの状態を表す変数との積の総和を求めたものである。ｂｉは、ｉ番目のニューロンのバイアス係数を示している。
【００１７】
また、変数ｘｉがｍ値の場合、変数ｘｉが上限または下限に達していない場合、変数ｘｉの変化分Δｘｉは、±２ｎである。
変数ｘｉの正方向及び負方向の変化に伴うエネルギー変化ΔＥｉ±は、以下の式（２）で表される。
【００１８】
【数２】
2020035179.tif 000004
【００１９】
式（２）のようにエネルギー変化ΔＥｉ±は、ｉ番目のニューロンの状態変化方向（正または負）によって、２つの値をもつ。
なお、式（２）において、ｈｉはローカルフィールド（局所場）と呼ばれる。
【００２０】
（第１の実施の形態）
図１は、第１の実施の形態の最適化装置の一例を示す図である。
第１の実施の形態の最適化装置１０は、Ｎ個のニューロンに関する計算を行うＮ個のイジング装置１１ａ１，１１ａ２，…，１１ａＮ、更新ニューロン選択回路１２、状態更新回路１３、制御部１４を有する。イジング装置１１ａ１〜１１ａＮのそれぞれは、１チップの半導体集積回路であってもよいし、１チップの半導体集積回路の中に、イジング装置１１ａ１〜１１ａＮが含まれていてもよい。
【００２１】
イジング装置１１ａ１は、Ｎ個のニューロンのうち、１番目のニューロン（識別情報ＩＤ＝１のニューロン）に関する計算を行う。イジング装置１１ａ１は、算出回路１１ｂ１、状態遷移判定回路１１ｃ１を有する。
【００２２】
算出回路１１ｂ１は、Ｎ個のニューロンのうち、状態が更新されたニューロンの状態変化方向ＤＲとそのニューロンの識別情報ＩＤとを更新ニューロン選択回路１２から受ける。そして、算出回路１１ｂ１は、識別情報ＩＤで識別されるニューロンと１番目のニューロンとの間の相互作用の大きさを示す重み係数と、状態変化方向ＤＲに基づいて、エネルギー変化ΔＥ１＋，ΔＥ１−を算出する。エネルギー変化ΔＥ１＋，ΔＥ１−は、１番目のニューロンの状態が、正負両方向に２ｎ変化することによるイジングモデルの２つのエネルギー変化である。
【００２３】
図１の例では、算出回路１１ｂ１は、レジスタ１１ｂ１１、ローカルフィールド更新部１１ｂ１２、エネルギー変化算出部１１ｂ１３を有する。
レジスタ１１ｂ１１は、Ｎ個の重み係数Ｗ１１，Ｗ１２，…，Ｗ１Ｎを記憶する。なお、重み係数Ｗ１１，Ｗ１２，…，Ｗ１Ｎは、ＳＲＡＭ（Static Random Access Memory）などのメモリに記憶されていてもよい。なお、全ての重み係数Ｗ１１〜ＷＮＮが１つのメモリに記憶されていてもよい。
【００２４】
ローカルフィールド更新部１１ｂ１２は、状態が更新されたニューロンの識別情報ＩＤから、そのニューロンと１番目のニューロンとの間の相互作用の大きさを示す重み係数を選択する。そして、ローカルフィールド更新部１１ｂ１２は、選択した重み係数と、状態が更新されたニューロンの状態変化方向ＤＲに基づいて、ローカルフィールドｈ１を更新する。なお、ローカルフィールドｈ１の初期値は、たとえば、バイアス係数ｂ１である。
【００２５】
ニューロン（ｊ番目のニューロン）の状態が、正方向に２ｎ変化したときのローカルフィールドｈ１の変化分は、＋２ｎＷ１ｊ、負方向に２ｎ変化したときのローカルフィールドｈ１の変化分は、−２ｎＷ１ｊと表せる。
【００２６】
したがって、ローカルフィールド更新部１１ｂ１２は、重み係数Ｗ１ｊをｎビット左シフトした値を、現在のローカルフィールドｈ１に対して、状態変化方向ＤＲに応じて加算するか減算することで、ローカルフィールドｈ１を更新することができる。このような、ローカルフィールド更新部１１ｂ１２は、たとえば、セレクタ、加算器（または減算器）、シフト演算回路を用いて実現できる。なお、ｎ＝０の場合には、シフト演算回路は不要である。
【００２７】
エネルギー変化算出部１１ｂ１３は、式（２）に基づいて、エネルギー変化ΔＥ１＋，ΔＥ１−を算出する。エネルギー変化算出部１１ｂ１３は、たとえば、シフト演算回路、符号反転回路を用いて実現できる。なお、ｎ＝０の場合には、シフト演算回路は不要である。
【００２８】
状態遷移判定回路１１ｃ１は、熱励起エネルギーと、エネルギー変化ΔＥ１＋，ΔＥ１−との大小関係に基づいて、エネルギー変化ΔＥ１＋，ΔＥ１−をもたらす１番目のニューロンの状態の更新をそれぞれ許容するか否かを判定する。そして、状態遷移判定回路１１ｃ１は、更新を許容するか否かの判定結果を出力する。また、状態遷移判定回路１１ｃ１は、１番目のニューロンの状態が上限値を超えるまたは下限値を下回る更新を制限する。つまり、状態遷移判定回路１１ｃ１は、１番目のニューロンの状態の定義域外となる更新が生じないようにする。なお、各ニューロンの状態を表す変数の定義域は、たとえば、問題の種類や最適化装置１０のハードウェア上の制約などによって決定される。
【００２９】
熱励起エネルギーは、たとえば、後述の乱数発生回路が生成した乱数と、制御部１４から入力される温度パラメータＴとに基づいて決定される。
また、上限値や下限値を含む制限情報ＬＭＴは、制御部１４から供給される。状態遷移判定回路１１ｃ１は、１番目のニューロンの状態が、正または負方向に２ｎ変化することにより上限値を超えるまたは下限値を下回る場合、たとえば、エネルギー変化ΔＥ１＋またはエネルギー変化ΔＥ１−を、十分に大きな所定の正の値に変更する。これによって、状態遷移判定回路１１ｃ１は、１番目のニューロンの状態の更新が許容されないようにする。この所定の正の値は、たとえば、エネルギー変化を所定の正の値に変更したときの、更新を許容するか否かの判定結果の値の検出結果に基づいて決定されるようにしてもよい。
【００３０】
また、状態遷移判定回路１１ｃ１は、１番目のニューロンの状態が、正または負方向に２ｎ変化することにより上限値を超えるまたは下限値を下回る場合、更新を許容するか否かの判定結果を、更新を許容しないことを示す値に変更してもよい。
【００３１】
このような状態遷移判定回路１１ｃ１の回路例については、第２の実施の形態以降において説明する。
他のイジング装置１１ａ２〜１１ａＮについても、２〜Ｎ番目のニューロンに関して、イジング装置１１ａ１と同様の処理を行う。
【００３２】
たとえば、イジング装置１１ａ２の算出回路１１ｂ２は、レジスタ１１ｂ２１、ローカルフィールド更新部１１ｂ２２、エネルギー変化算出部１１ｂ２３を有する。レジスタ１１ｂ２１は、Ｎ個の重み係数Ｗ２１，Ｗ２２，…，Ｗ２Ｎを記憶する。ローカルフィールド更新部１１ｂ２２は、状態が更新されたニューロンの識別情報ＩＤから、そのニューロンと２番目のニューロンとの間の相互作用の大きさを示す重み係数を選択する。そして、ローカルフィールド更新部１１ｂ２２は、選択した重み係数と、状態が更新されたニューロンの状態変化方向ＤＲに基づいて、ローカルフィールドｈ２を更新する。エネルギー変化算出部１１ｂ２３は、式（２）に基づいて、エネルギー変化ΔＥ２＋，ΔＥ２−を算出する。そしてイジング装置１１ａ２の状態遷移判定回路１１ｃ２は、熱励起エネルギーと、エネルギー変化ΔＥ２＋，ΔＥ２−との大小関係に基づいて、エネルギー変化ΔＥ２＋，ΔＥ２−をもたらす２番目のニューロンの状態の更新をそれぞれ許容するか否かを判定する。そして、状態遷移判定回路１１ｃ２は、更新を許容するか否かの判定結果を出力する。また、状態遷移判定回路１１ｃ２は、２番目のニューロンの状態が上限値を超えるまたは下限値を下回る更新を制限する。
【００３３】
イジング装置１１ａＮの算出回路１１ｂＮは、レジスタ１１ｂＮ１、ローカルフィールド更新部１１ｂＮ２、エネルギー変化算出部１１ｂＮ３を有する。レジスタ１１ｂＮ１は、Ｎ個の重み係数ＷＮ１，ＷＮ２，…，ＷＮＮを記憶する。ローカルフィールド更新部１１ｂＮ２は、更新ニューロンの識別情報ＩＤから、状態が更新されたニューロンとＮ番目のニューロンとの間の相互作用の大きさを示す重み係数を選択する。そして、ローカルフィールド更新部１１ｂＮ２は、選択した重み係数と、状態が更新されたニューロンの状態変化方向ＤＲに基づいて、ローカルフィールドｈＮを更新する。エネルギー変化算出部１１ｂＮ３は、式（２）に基づいて、エネルギー変化ΔＥＮ＋，ΔＥＮ−を算出する。そしてイジング装置１１ａＮの状態遷移判定回路１１ｃＮは、熱励起エネルギーと、エネルギー変化ΔＥＮ＋，ΔＥＮ−との大小関係に基づいて、エネルギー変化ΔＥＮ＋，ΔＥＮ−をもたらすＮ番目のニューロンの状態の更新をそれぞれ許容するか否かを判定する。そして、状態遷移判定回路１１ｃＮは、更新を許容するか否かの判定結果を出力する。また、状態遷移判定回路１１ｃＮは、Ｎ番目のニューロンの状態が上限値を超えるまたは下限値を下回る更新を制限する。
【００３４】
更新ニューロン選択回路１２は、イジング装置１１ａ１〜１１ａＮのそれぞれが出力する判定結果に基づいて、更新を許容するニューロンを１つ選択するとともに、状態変化方向ＤＲを選択する。更新ニューロン選択回路１２は選択した更新を許容するニューロンの識別情報ＩＤと、状態変化方向ＤＲを出力する。
【００３５】
状態更新回路１３は、更新ニューロン選択回路１２が選択したニューロンの状態を、状態変化方向ＤＲに基づいて正または負方向に２ｎ、変化（更新）させる。状態更新回路１３は、記憶部（たとえば、レジスタ）を有しており、Ｎ個のニューロンの状態を保持している。
【００３６】
制御部１４は、制御装置１５（たとえば、ＰＣ（Personal Computer））との間で情報の送受信を行う。たとえば、制御部１４は、制御装置１５からイジングモデルを表現する重み係数Ｗｉｊを受け、イジング装置１１ａ１〜１１ａＮに対して、重み係数ｉｊを設定する（レジスタ１１ｂ１１〜１１ｂＮ１に記憶する）。また、制御部１４は、ローカルフィールドｈｉの初期値（たとえば、バイアス係数ｂｉ）を制御装置１５から受け、イジング装置１１ａ１〜１１ａＮに対して、設定してもよい。
【００３７】
また、制御部１４は、制御装置１５から、アニーリング条件（温度パラメータＴの最大値、最小値、温度パラメータＴの値の下げ方についての情報など）を受け、アニーリング条件に基づいて、イジング装置１１ａ１〜１１ａＮに対して、温度パラメータＴを設定する。制御部１４は、アニーリング条件に基づいて、温度パラメータＴの値を徐々に小さくしていく。また、制御部１４は、前述の制限情報ＬＭＴを制御装置１５から受け、イジング装置１１ａ１〜１１ａＮに対して、各ニューロンの状態の上限値と下限値を含む制限情報ＬＭＴを設定する。また、制御部１４は、たとえば、温度パラメータＴの値を所定回数、小さくした場合（または温度パラメータＴが最小値に達した場合）の状態更新回路１３に保持されている各ニューロンの状態を解として制御装置１５に送信する。
【００３８】
制御部１４は、たとえば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡなどの特定用途の電子回路にて実現できる。なお、制御部１４は、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）などのプロセッサであってもよい。その場合、プロセッサは、図示しないメモリに記憶されたプログラムを実行することで、上記のような制御部１４の処理を行う。制御部１４の機能は、制御装置１５に含まれていてもよい。
【００３９】
以下、第１の実施の形態の最適化装置１０の動作例を示す。
図２は、第１の実施の形態の最適化装置の動作の一例の流れを示すフローチャートである。
【００４０】
まず、制御部１４は、制御装置１５から受けた重み係数Ｗｉｊ、ローカルフィールドｈｉの初期値、温度パラメータＴの初期値、制限情報ＬＭＴを、イジング装置１１ａ１〜１１ａＮに設定する（ステップＳ１）。
【００４１】
ローカルフィールド更新部１１ｂ１２〜１１ｂＮ２は、２回目以降の更新処理では前述の処理により、ローカルフィールドｈｉを更新する（ステップＳ２）。
エネルギー変化算出部１１ｂ１３〜１１ｂＮ３のそれぞれは、式（２）に基づいて、２つのエネルギー変化ΔＥｉ＋，ΔＥｉ−を算出する（ステップＳ３）。
【００４２】
状態遷移判定回路１１ｃ１〜１１ｃＮのそれぞれは、前述の処理により、エネルギー変化ΔＥｉ＋，ΔＥｉ−をもたらす各ニューロンの状態の更新をそれぞれ許容するか否かを判定する（ステップＳ４）。また、ステップＳ４の処理では、状態遷移判定回路１１ｃ１〜１１ｃＮのそれぞれは、前述の処理により、各ニューロンの状態が定義域外となる更新を制限する。
【００４３】
更新ニューロン選択回路１２は、イジング装置１１ａ１〜１１ａＮのそれぞれが出力する判定結果に基づいて、更新を許容するニューロンを１つ選択するとともに、状態変化方向ＤＲを選択する（ステップＳ５）。
【００４４】
状態更新回路１３は、更新ニューロン選択回路１２が選択したニューロンの状態を、状態変化方向ＤＲに基づいて更新する（ステップＳ６）。
制御部１４は、ステップＳ２〜Ｓ６の更新処理が所定回数Ｎ１、繰り返されたか否かを判定する（ステップＳ７）。更新処理が所定回数Ｎ１、繰り返されていない場合には、ステップＳ２〜Ｓ６の更新処理が繰り返される。
【００４５】
更新処理が所定回数Ｎ１、繰り返された場合、制御部１４は、温度パラメータＴの変更回数（温度変更回数）が、所定回数Ｎ２に達したか否かを判定する（ステップＳ８）。
温度変更回数が所定回数Ｎ２に達していない場合、制御部１４は、温度パラメータＴを変更する（温度を下げる）（ステップＳ９）。所定回数Ｎ１，Ｎ２、温度パラメータＴの値の変更の仕方（一度に値をどのくらい小さくするかなど）は、アニーリング条件に基づいて決定される。ステップＳ９の処理後、ステップＳ２からの処理が繰り返される。
【００４６】
温度変更回数が所定回数Ｎ２に達している場合、制御部１４は、そのとき状態更新回路１３に保持されている各ニューロンの状態を、解（計算結果）として制御装置１５に送信（出力）する（ステップＳ１０）。
【００４７】
以上のような第１の実施の形態の最適化装置１０では、３値以上の値をもつ各ニューロンの状態の許容する変化を±２ｎ（ｎは０以上の整数）とすることで、イジングモデルのエネルギー変化を算出する回路の構成が簡素化され回路規模の増大を抑えられる。また、小さい回路規模で、３値以上の値をもつニューロンの状態を扱えることで、最適化装置１０によって解くことができる問題の範囲を広げることができる。
【００４８】
なお、ニューロンごとに、ｎの値は異なっていてもよい。
（第２の実施の形態）
図３は、第２の実施の形態の最適化装置の一例を示す図である。図３において、図１に示した第１の実施の形態の最適化装置１０の要素と同じ要素については同一符号が付されている。
【００４９】
第２の実施の形態の最適化装置２０において、イジング装置２１ａ１の状態遷移判定回路２１ｂ１は、ΔＥ変更部２１ｂ１１，２１ｂ１２、遷移可否決定部２１ｂ１３，２１ｂ１４を有する。
【００５０】
ΔＥ変更部２１ｂ１１は、変数ｘ１が＋２ｎ変化することにより上限値を超える場合、エネルギー変化ΔＥ１＋を所定の正の値ΔＥｍａｘに変更する。
ΔＥ変更部２１ｂ１２は、変数ｘ１が−２ｎ変化することにより下限値を下回る場合、エネルギー変化ΔＥ１−を所定の正の値ΔＥｍａｘに変更する。
【００５１】
正の値ΔＥｍａｘは、この値が遷移可否決定部２１ｂ１３，２１ｂ１４に供給された場合に、変数ｘ１の更新が許容される確率がほぼゼロになるように、十分大きな値である。
図４は、１つ目のΔＥ変更部の一例を示す図である。図４では、ΔＥ変更部２１ｂ１１の例が示されている。
【００５２】
ΔＥ変更部２１ｂ１１は、２ｎ加算部３０、比較回路３１、セレクタ３２を有する。
２ｎ加算部３０は、状態更新回路１３から供給される現在の変数ｘ１に２ｎを加算する。
【００５３】
比較回路３１は、制限情報ＬＭＴに含まれる変数ｘ１の上限値ｘ１ｍａｘと、２ｎ加算部３０における加算結果とを比較する。そして、比較回路３１は、加算結果が上限値ｘ１ｍａｘを超える場合には１を出力し、それ以外の場合には０を出力する。
【００５４】
セレクタ３２は、エネルギー変化ΔＥ１＋と、制限情報ＬＭＴに含まれる正の値ΔＥｍａｘを入力し、比較回路３１の出力が１の場合には、正の値ΔＥｍａｘを出力し、比較回路３１の出力が０の場合には、エネルギー変化ΔＥ１＋を出力する。
【００５５】
図５は、２つ目のΔＥ変更部の一例を示す図である。図５では、ΔＥ変更部２１ｂ１２の例が示されている。
ΔＥ変更部２１ｂ１２は、２ｎ減算部３３、比較回路３４、セレクタ３５を有する。
【００５６】
２ｎ減算部３３は、状態更新回路１３から供給される現在の変数ｘ１から２ｎを減算する。
比較回路３４は、制限情報ＬＭＴに含まれる変数ｘ１の下限値ｘ１ｍｉｎと、２ｎ減算部３３における減算結果とを比較する。そして、比較回路３４は、減算結果が下限値ｘ１ｍｉｎを下回る場合には１を出力し、それ以外の場合には０を出力する。
【００５７】
セレクタ３５は、エネルギー変化ΔＥ１−と、制限情報ＬＭＴに含まれる所定の正の値ΔＥｍａｘを入力し、比較回路３４の出力が１の場合には、正の値ΔＥｍａｘを出力し、比較回路３４の出力が０の場合には、エネルギー変化ΔＥ１−を出力する。
【００５８】
図３の遷移可否決定部２１ｂ１３は、エネルギー変化ΔＥ１＋または正の値ΔＥｍａｘと、熱励起エネルギーとの大小関係に基づいて、エネルギー変化ΔＥ１＋をもたらす１番目のニューロンの状態の更新を許容するか否かを判定する。
【００５９】
遷移可否決定部２１ｂ１４は、エネルギー変化ΔＥ１−または正の値ΔＥｍａｘと、熱励起エネルギーとの大小関係に基づいて、エネルギー変化ΔＥ１−をもたらす１番目のニューロンの状態の更新を許容するか否かを判定する。
【００６０】
図６は、遷移可否決定部の一例を示す図である。
遷移可否決定部２１ｂ１３は、符号反転部４０、加算器４１、乱数発生回路４２、選択法則適用部４３、乗算器４４、比較回路４５を有する。
【００６１】
符号反転部４０は、ΔＥ変更部２１ｂ１１が出力するエネルギー変化ΔＥ１＋または正の値ΔＥｍａｘに−１を掛けて符合を反転させる。
加算器４１は、符号反転部４０の出力値に、後述するオフセット生成回路２３が生成するオフセット値ｏｆｆを加える。
【００６２】
乱数発生回路４２は、０以上、１以下の一様乱数ｒを発生する。
選択法則適用部４３は、シミュレーテッド・アニーリングを行うための選択法則（メトロポリス法またはギブス法）に基づいた値を出力する。
【００６３】
シミュレーテッド・アニーリングが行われる場合、あるエネルギー変化ΔＥを引き起こす状態遷移の許容確率Ａ（ΔＥ，Ｔ）を以下の式（３）のように決めれば、時刻（反復回数）無限大の極限で状態が最適解に到達することが証明されている。
【００６４】
【数３】
2020035179.tif 000005
【００６５】
式（３）においてＴは、前述の温度パラメータＴである。
式（３）で表される許容確率Ａ（ΔＥ，Ｔ）を用いた場合、十分な反復後に定常状態に達したとすると、各状態の占有確率は熱力学における熱平衡状態に対するボルツマン分布にしたがう。そして、高い温度から徐々に下げていくとエネルギーの低い状態の占有確率が増加するため、十分温度が下がるとエネルギーの低い状態が得られるはずである。この様子が材料を焼き鈍したときの状態変化とよく似ているため、この方法はシミュレーテッド・アニーリングと呼ばれるのである。このとき、エネルギーが上がる状態遷移が確率的に起こることは、物理学における熱励起に相当する。
【００６６】
許容確率Ａ（ΔＥ，Ｔ）でエネルギー変化ΔＥを引き起こす状態遷移を許容することを示すフラグ情報（＝１）を出力する回路は、式（３）のｆ（−ΔＥ／Ｔ）と、一様乱数ｒとの比較結果に基づいた値を出力する比較器によって実現できる。
【００６７】
ただ、次のような変形を行っても同じ機能が実現できる。２つの数に同じ単調増加関数を作用させても大小関係は変化しない。したがって比較器の２つの入力に同じ単調増加関数を作用させても比較器の出力は変わらない。たとえば、ｆ（−ΔＥ／Ｔ）に作用させる単調増加関数としてｆ（−ΔＥ／Ｔ）の逆関数ｆ−１（−ΔＥ／Ｔ）、一様乱数ｒに作用させる単調増加関数としてｆ−１（−ΔＥ／Ｔ）の−ΔＥ／Ｔをｒとしたｆ−１（ｒ）を用いることができる。その場合、上記の比較器と同様の機能を有する回路は、−ΔＥ／Ｔがｆ−１（ｒ）より大きいとき１を出力する回路でよいことがわかる。さらに温度パラメータＴが正であることから、その回路は、−ΔＥがＴ・ｆ−１（ｒ）より大きいとき１を出力する回路でよい。
【００６８】
図６の選択法則適用部４３は、入力される一様乱数ｒを上記のｆ−１（ｒ）の値に変換する変換テーブルを用いて、ｆ−１（ｒ）の値を出力する。メトロポリス法が適用される場合、ｆ−１（ｒ）は、ｌｏｇ（ｒ）である。変換テーブルは、たとえば、ＲＡＭ（Random Access Memory）、フラッシュメモリなどのメモリに記憶されている。
【００６９】
乗算器４４は、制御部１４から供給される温度パラメータＴと、ｆ−１（ｒ）との積（Ｔ・ｆ−１（ｒ））を出力する。Ｔ・ｆ−１（ｒ）は、熱励起エネルギーに相当する。
比較回路４５は、加算器４１による加算結果と、Ｔ・ｆ−１（ｒ）とを比較し、加算結果が、Ｔ・ｆ−１（ｒ）より大きい場合、フラグ情報ＦＬＧ１＋として１を出力し、Ｔ・ｆ−１（ｒ）より小さい場合、フラグ情報ＦＬＧ１＋として０を出力する。
【００７０】
遷移可否決定部２１ｂ１４についても遷移可否決定部２１ｂ１３と同様の回路構成となる。
イジング装置２１ａ１〜２１ａＮのうち、イジング装置２１ａ１以外についても、イジング装置２１ａ１と同様の構成を有し、２〜Ｎ番目のニューロンに対して同様の処理を行う。
【００７１】
たとえば、イジング装置２１ａＮの状態遷移判定回路２１ｂＮは、ΔＥ変更部２１ｂＮ１，２１ｂＮ２、遷移可否決定部２１ｂＮ３，２１ｂＮ４を有する。
ΔＥ変更部２１ｂＮ１は、変数ｘＮが＋２ｎ変化することにより上限値を超える場合、エネルギー変化ΔＥＮ＋を所定の正の値ΔＥｍａｘに変更する。
【００７２】
ΔＥ変更部２１ｂＮ２は、変数ｘＮが−２ｎ変化することにより下限値を下回る場合、エネルギー変化ΔＥＮ−を所定の正の値ΔＥｍａｘに変更する。
遷移可否決定部２１ｂＮ３は、エネルギー変化ΔＥＮ＋または正の値ΔＥｍａｘと、熱励起エネルギーとの大小関係に基づいて、エネルギー変化ΔＥＮ＋をもたらすＮ番目のニューロンの状態の更新を許容するか否かを判定する。
【００７３】
遷移可否決定部２１ｂＮ４は、エネルギー変化ΔＥＮ−または正の値ΔＥｍａｘと、熱励起エネルギーとの大小関係に基づいて、エネルギー変化ΔＥＮ−をもたらすＮ番目のニューロンの状態の更新を許容するか否かを判定する。
【００７４】
更新ニューロン選択回路２２は、図１に示した更新ニューロン選択回路１２と同様に、イジング装置２１ａ１〜２１ａＮのそれぞれが出力する判定結果（フラグ情報）に基づいて、更新を許容するニューロンを１つ選択するとともに、状態変化方向ＤＲを選択する。そして、更新ニューロン選択回路２２は選択した更新を許容するニューロンの識別情報ＩＤと、状態変化方向ＤＲを出力する。第２の実施の形態の最適化装置２０では、更新ニューロン選択回路２２は、さらに、選択した更新を許容するニューロンについてのフラグ情報ＦＬＧについても出力する。
【００７５】
第２の実施の形態の最適化装置２０は、オフセット値ｏｆｆを生成するオフセット生成回路２３を有する。オフセット生成回路２３は、更新ニューロン選択回路２２から供給されるフラグ情報ＦＬＧが、状態遷移を許容しないことを示すとき（つまり状態遷移が生じないとき）、オフセット値ｏｆｆを増加していく。一方、オフセット生成回路２３は、フラグ情報ＦＬＧが、状態遷移を許容することを示すとき（つまり状態遷移が生じるとき）には、オフセット値ｏｆｆを０にリセットする。オフセット値ｏｆｆが大きくなると状態遷移が許容されやすくなり、現在の状態が局所解にある場合、その局所解からの脱出が促進される。
【００７６】
以下、第２の実施の形態の最適化装置２０の動作例を示す。
図７は、第２の実施の形態の最適化装置の動作の一例の流れを示すフローチャートである。
【００７７】
まず、制御部１４は、制御装置１５から受けた重み係数Ｗｉｊ、ローカルフィールドｈｉの初期値、温度パラメータＴの初期値、制限情報ＬＭＴを、イジング装置２１ａ１〜２１ａＮに設定する（ステップＳ２０）。第２の実施の形態の最適化装置２０において、制限情報ＬＭＴは、正の値ΔＥｍａｘと、各変数ｘｉの定義域（上限値と下限値）を含む。
【００７８】
ステップＳ２１，Ｓ２２の処理は、図２に示したステップＳ２，Ｓ３の処理と同じである。
ステップＳ２２の処理後、状態遷移判定回路２１ｂ１〜２１ｂＮのそれぞれは、更新する場合に定義域外となる変数ｘｉについてのエネルギー変化ΔＥｉ＋またはエネルギー変化ΔＥｉ−を正の値ΔＥｍａｘに変更する（ステップＳ２３）。
【００７９】
そして、状態遷移判定回路２１ｂ１〜２１ｂＮのそれぞれは、エネルギー変化ΔＥｉ＋，ΔＥｉ−をもたらす各ニューロンの状態の更新をそれぞれ許容するか否かを判定する（ステップＳ２４）。ステップＳ２４の処理には、前述のオフセット値ｏｆｆの加算処理なども含まれる。
【００８０】
以降のステップＳ２５〜Ｓ３０の処理は、図２に示したステップＳ５〜Ｓ１０の処理と同じである。
以上のような第２の実施の形態の最適化装置２０では、第１の実施の形態の最適化装置１０と同様の効果が得られる。また、最適化装置２０は、更新する場合に定義域外となる変数ｘｉについてのエネルギー変化ΔＥｉ＋またはエネルギー変化ΔＥｉ−を、正の値ΔＥｍａｘに変更することで、変数ｘｉが定義域外となる更新が抑制される。
【００８１】
（第３の実施の形態）
図８は、第３の実施の形態の最適化装置の一例を示す図である。図８において、図１、図３に示した最適化装置１０，２０の要素と同じ要素については同一符号が付されている。
【００８２】
第３の実施の形態の最適化装置５０において、イジング装置５１ａ１の状態遷移判定回路５１ｂ１は、遷移可否決定部５１ｂ１１，５１ｂ１２、定義域確認部５１ｂ１３，５１ｂ１４を有する。
【００８３】
遷移可否決定部５１ｂ１１は、エネルギー変化ΔＥ１＋と、熱励起エネルギーとの大小関係に基づいて、エネルギー変化ΔＥ１＋をもたらす１番目のニューロンの状態の更新を許容するか否かを判定する。
【００８４】
遷移可否決定部５１ｂ１２は、エネルギー変化ΔＥ１−と、熱励起エネルギーとの大小関係に基づいて、エネルギー変化ΔＥ１−をもたらす１番目のニューロンの状態の更新を許容するか否かを判定する。
【００８５】
遷移可否決定部５１ｂ１１，５１ｂ１２の回路構成は、図６に示した遷移可否決定部２１ｂ１３の回路構成と同じである。
定義域確認部５１ｂ１３は、変数ｘ１が＋２ｎ変化することにより上限値を超える場合、更新を許容するか否かの判定結果を示すフラグ情報を０（更新を許容しないことを示す）にする。
【００８６】
定義域確認部５１ｂ１４は、変数ｘ１が−２ｎ変化することにより下限値を下回る場合、更新を許容するか否かの判定結果を示すフラグ情報を０にする。
図９は、１つ目の定義域確認部の一例を示す図である。図９では、定義域確認部５１ｂ１３の例が示されている。
【００８７】
定義域確認部５１ｂ１３は、２ｎ加算部６０、比較回路６１、ＡＮＤ（論理積）回路６２を有する。
２ｎ加算部６０は、状態更新回路１３から供給される現在の変数ｘ１に２ｎを加算する。
【００８８】
比較回路６１は、制限情報ＬＭＴに含まれる変数ｘ１の上限値ｘ１ｍａｘと、２ｎ加算部６０における加算結果とを比較する。そして、比較回路６１は、加算結果が上限値ｘ１ｍａｘを超える場合には０を出力し、それ以外の場合には１を出力する。
【００８９】
ＡＮＤ回路６２の一方の入力端子には、遷移可否決定部５１ｂ１１が出力するフラグ情報ＦＬＧ１ａが入力され、他方の入力端子には、比較回路６１の出力が入力される。そして、ＡＮＤ回路６２は、比較回路６１の出力が１の場合には、フラグ情報ＦＬＧ１ａの値（０または１）を出力し、比較回路６１の出力が０の場合には、フラグ情報ＦＬＧ１ａの値によらず０を出力する。
【００９０】
図１０は、２つ目の定義域確認部の一例を示す図である。図１０では、定義域確認部５１ｂ１４の例が示されている。
定義域確認部５１ｂ１４は、２ｎ減算部６３、比較回路６４、ＡＮＤ回路６５を有する。
【００９１】
２ｎ減算部６３は、状態更新回路１３から供給される現在の変数ｘ１から２ｎを減算する。
比較回路６４は、制限情報ＬＭＴに含まれる変数ｘ１の下限値ｘ１ｍｉｎと、２ｎ減算部６３における減算結果とを比較する。そして、比較回路６４は、減算結果が下限値ｘ１ｍｉｎを下回る場合には０を出力し、それ以外の場合には１を出力する。
【００９２】
ＡＮＤ回路６５の一方の入力端子には、遷移可否決定部５１ｂ１２が出力するフラグ情報ＦＬＧ１ｂが入力され、他方の入力端子には、比較回路６４の出力が入力される。そして、ＡＮＤ回路６５は、比較回路６４の出力が１の場合には、フラグ情報ＦＬＧ１ｂの値（０または１）を出力し、比較回路６４の出力が０の場合には、フラグ情報ＦＬＧ１ｂの値によらず０を出力する。
【００９３】
イジング装置５１ａ１〜５１ａＮのうち、イジング装置５１ａ１以外についても、イジング装置５１ａ１と同様の構成を有し、２〜Ｎ番目のニューロンに対して同様の処理を行う。
【００９４】
たとえば、イジング装置５１ａＮの状態遷移判定回路５１ｂＮは、遷移可否決定部５１ｂＮ１，５１ｂＮ２、定義域確認部５１ｂＮ３，５１ｂＮ４を有する。
遷移可否決定部５１ｂＮ１は、エネルギー変化ΔＥＮ＋と、熱励起エネルギーとの大小関係に基づいて、エネルギー変化ΔＥＮ＋をもたらすＮ番目のニューロンの状態の更新を許容するか否かを判定する。
【００９５】
遷移可否決定部５１ｂＮ２は、エネルギー変化ΔＥＮ−と、熱励起エネルギーとの大小関係に基づいて、エネルギー変化ΔＥＮ−をもたらすＮ番目のニューロンの状態の更新を許容するか否かを判定する。
【００９６】
定義域確認部５１ｂＮ３は、変数ｘＮが＋２ｎ変化することにより上限値を超える場合、更新を許容するか否かの判定結果を示すフラグ情報を０にする。
定義域確認部５１ｂＮ４は、変数ｘＮが−２ｎ変化することにより下限値を下回る場合、更新を許容するか否かの判定結果を示すフラグ情報を０にする。
【００９７】
以下、第３の実施の形態の最適化装置５０の動作例を示す。
図１１は、第３の実施の形態の最適化装置の動作の一例の流れを示すフローチャートである。
【００９８】
まず、制御部１４は、制御装置１５から受けた重み係数Ｗｉｊ、ローカルフィールドｈｉの初期値、温度パラメータＴの初期値、制限情報ＬＭＴを、イジング装置５１ａ１〜５１ａＮに設定する（ステップＳ４０）。第３の実施の形態の最適化装置５０において、制限情報ＬＭＴは、各変数ｘｉの定義域（上限値と下限値）を含む。
【００９９】
ステップＳ４１，Ｓ４２の処理は、図２に示したステップＳ２，Ｓ３の処理と同じである。
ステップＳ４２の処理後、状態遷移判定回路５１ｂ１〜５１ｂＮのそれぞれは、エネルギー変化ΔＥｉ＋，ΔＥｉ−をもたらす各ニューロンの状態の更新をそれぞれ許容するか否かを判定する（ステップＳ４３）。ステップＳ４３の処理には、前述のオフセット値ｏｆｆの加算処理なども含まれる。
【０１００】
その後、状態遷移判定回路５１ｂ１〜５１ｂＮのそれぞれは、更新する場合に定義域外となる変数ｘｉについてのフラグ情報を０にする（ステップＳ４４）。
以降のステップＳ４５〜Ｓ５０の処理は、図２に示したステップＳ５〜Ｓ１０の処理と同じである。
【０１０１】
以上のような第３の実施の形態の最適化装置５０では、第１の実施の形態の最適化装置１０と同様の効果が得られる。また、最適化装置５０は、更新する場合に定義域外となる変数ｘｉについてのフラグ情報を０にすることで、変数ｘｉが定義域外となる更新が確実に抑制される。
【０１０２】
（第４の実施の形態）
図１２は、第４の実施の形態の最適化装置の一例を示す図である。図１２において、図１、図３、図８に示した最適化装置１０，２０，５０の要素と同じ要素については同一符号が付されている。
【０１０３】
第４の実施の形態の最適化装置７０は、算出回路７１ｂ１〜７１ｂＮや状態更新回路７２に供給するシフト量ｎ１〜ｎＮを保持するシフト量保持部７３ａ１〜７３ａＮを有する。シフト量ｎ１〜ｎＮは、Ｎ個のニューロンのそれぞれの状態の変化幅を決める値であり、０以上の値である。たとえば、１番目のニューロンの状態の変化幅は±２ｎ１、Ｎ番目のニューロンの状態の変化幅は±２ｎＮと表せる。シフト量ｎ１〜ｎＮはそれぞれ異なっていてもよい。
【０１０４】
シフト量保持部７３ａ１〜７３ａＮは、たとえば、レジスタやＳＲＡＭなどである。
イジング装置７１ａ１〜７１ａＮの算出回路７１ｂ１〜７１ｂＮに含まれるローカルフィールド更新部７１ｂ１１〜７１ｂＮ１のそれぞれには、シフト量ｎ１〜ｎＮが供給される。そして、ローカルフィールド更新部７１ｂ１１〜７１ｂＮ１のそれぞれは、状態が更新されたニューロンについてのシフト量を用いて、ローカルフィールドを更新する。
【０１０５】
図１３は、ローカルフィールド更新部においてシフト動作が行われる部分の例を示す図である。図１３では、ローカルフィールド更新部７１ｂ１１〜７１ｂＮ１のうち、ｉ番目のニューロンについてのローカルフィールドを更新するローカルフィールド更新部７１ｂｉ１の一部が示されている。
【０１０６】
ローカルフィールド更新部７１ｂｉ１は、不一致回路８０、選択回路８１、シフト演算回路８２を有する。
不一致回路８０は、ｉ番目のニューロンの識別情報ＩＤ（＝ｉ）と、状態が更新されたニューロンの識別情報ＩＤ（＝ｊ）とが不一致の場合に、１を出力し、一致している場合に０を出力する。
【０１０７】
たとえば、不一致回路８０は、ｉ番目のニューロンとｊ番目のニューロンの識別情報ＩＤを１ビットずつ比較し、全てのビットが一致している場合に０を出力し、それ以外の場合には１を出力する。
【０１０８】
図１３には、不一致回路８０の回路例が示されている。不一致回路８０は、ｋ個のＥｘＯＲ（排他的論理和）回路８０ａ１，８０ａ２，…，８０ａｋと、複数のＯＲ（論理和）回路（たとえば、ＯＲ回路８０ｂ１〜８０ｂｍ，８０ｃ）を有する。
【０１０９】
ＥｘＯＲ回路８０ａ１〜８０ａｋは、それぞれｋビットからなるｉ番目のニューロンとｊ番目のニューロンの識別情報ＩＤを１ビットずつ比較し、両者が一致していれば０を出力し、異なっていれば１を出力する。たとえば、ＥｘＯＲ回路８０ａ１は、ｉ番目のニューロンとｊ番目のニューロンのそれぞれの識別情報ＩＤの最下位ビット（ｉ１とｊ１）同士を比較し、両者が一致していれば０を出力し、異なっていれば１を出力する。ＥｘＯＲ回路８０ａｋは、ｉ番目のニューロンとｊ番目のニューロンのそれぞれの識別情報ＩＤの最上位ビット（ｉｋとｊｋ）同士を比較し、両者が一致していれば０を出力し、異なっていれば１を出力する。
【０１１０】
ＯＲ回路８０ｂ１〜８０ｂｍは、ＥｘＯＲ回路８０ａ１〜８０ａｋの出力を２つずつ受け、両者の論理和を出力する。たとえば、ＯＲ回路８０ｂ１は、ＥｘＯＲ回路８０ａ１，８０ａ２の出力を受け、両者の論理和を出力する。
【０１１１】
図示が省略されているが、ＯＲ回路８０ｂ１〜８０ｂｍの出力は、２つずつ次の段の複数のＯＲ回路の何れかに入力され、またその段の複数のＯＲ回路の出力が２つずつ、次の段の複数のＯＲ回路の何れかに入力される、という処理がｋの値に応じて繰り返される。そして、最後段のＯＲ回路８０ｃの出力が、不一致回路８０の出力となる。
【０１１２】
選択回路８１は、不一致回路８０の出力が１の場合に、重み係数Ｗｉｊを選択して出力し、不一致回路８０の出力が０の場合に、０を選択して出力する。
シフト演算回路８２は、選択回路８１の出力が０の場合には０を出力し、選択回路８１の出力が重み係数Ｗｉｊの場合には、重み係数Ｗｉｊをｎｊビット分、左シフトした値（Ｗｉｊ＊（１＜＜ｎｊ）＝２ｎｊＷｉｊ）を出力する。状態変化方向ＤＲに応じて、２ｎｊＷｉｊに対し１または−１を掛けたものが、ローカルフィールドｈｉの変化分となる。
【０１１３】
図１２において、イジング装置７１ａ１〜７１ａＮの算出回路７１ｂ１〜７１ｂＮに含まれるエネルギー変化算出部７１ｂ１２〜７１ｂＮ２のそれぞれには、シフト量ｎ１〜ｎＮのうち何れか１つが供給される。たとえば、エネルギー変化算出部７１ｂ１２は、シフト量ｎ１を受け、式（２）より、ΔＥ１＋＝−２ｎ１ｈ１、ΔＥ１−＝２ｎ１ｈ１を算出する。エネルギー変化算出部７１ｂＮ２は、シフト量ｎＮを受け、式（２）より、ΔＥＮ＋＝−２ｎＮｈＮ、ΔＥＮ−＝２ｎＮｈＮを算出する。
【０１１４】
状態遷移判定回路７１ｃ１〜７１ｃＮは、第２の実施の形態の最適化装置２０の状態遷移判定回路２１ｂ１〜２１ｂＮまたは第３の実施の形態の最適化装置５０の状態遷移判定回路５１ｂ１〜５１ｂＮとほぼ同じである。ただ、ΔＥ変更部２１ｂ１１，２１ｂ１２〜２１ｂＮ１，２１ｂＮ２や、定義域確認部５１ｂ１３，５１ｂ１４〜５１ｂＮ３，５１ｂＮ４では、前述のように現在のニューロンの状態に対して、２ｎの加算または減算が行われる（図４、図５、図９、図１０参照）。このため、状態遷移判定回路７１ｃ１〜７１ｃＮのそれぞれには、シフト量ｎとして、シフト量ｎ１〜ｎＮのうちの何れか１つが供給される。
【０１１５】
状態更新回路７２には、シフト量ｎ１〜ｎＮが供給され、更新ニューロン選択回路２２が出力した識別情報ＩＤに対応するシフト量を１つ選択する。そして、状態更新回路７２は、選択したシフト量（以下ではｎｓとする）と、状態変化方向ＤＲに基づいて、識別情報ＩＤで表されるニューロンの状態を、正または負方向に２ｎｓ、変化させる。
【０１１６】
制御部７４は、制御部１４と同様の機能を有するとともに、シフト量保持部７３ａ１〜７３ａＮに、シフト量ｎ１〜ｎＮを設定する。制御部７４は、ニューロンの状態の更新処理の際にシフト量ｎ１〜ｎＮを変化させてもよい。これにより最適解への収束速度を制御することができる。たとえば、制御部７４は、全ニューロンの状態が所定回数の更新処理を行っても変化しない場合（現在の状態が局所解にある場合）、シフト量ｎ１〜ｎＮを大きくすることで、エネルギー変化の絶対値が大きくなり、局所解からの脱出が促進される。これにより、収束速度を加速させることができる。
【０１１７】
以下、第４の実施の形態の最適化装置７０の動作例を示す。
図１４は、第４の実施の形態の最適化装置の動作の一例の流れを示すフローチャートである。
【０１１８】
まず、制御部７４は、制御装置１５から受けた重み係数Ｗｉｊ、ローカルフィールドｈｉの初期値、温度パラメータＴの初期値、制限情報ＬＭＴをイジング装置７１ａ１〜７１ａＮに対して設定する。また、制御部７４は、制御装置１５から受けたシフト量ｎ１〜ｎＮを、シフト量保持部７３ａ１〜７３ａＮに対して設定する（ステップＳ６０）。その後のステップＳ６１〜Ｓ６９の処理は、設定されたシフト量ｎ１〜ｎＮが用いられる点以外、図２に示したステップＳ２〜Ｓ１０と同じである。なお、制御部７４は、たとえば、ステップＳ６８の処理後などに、シフト量ｎ１〜ｎＮの大きさを変更してもよい。
【０１１９】
以上のような第４の実施の形態の最適化装置７０では、第１の実施の形態の最適化装置１０と同様の効果が得られる。また、最適化装置７０では、制御部７４がＮ個のニューロンのそれぞれについてのシフト量ｎ１〜ｎＮを、個々に設定するため、状態の変化幅をニューロンごとに変えることができる。また、制御部７４は、ニューロンの状態の更新処理の際にシフト量ｎ１〜ｎＮを変化させることもできるようになり、最適解への収束速度を制御することができる。
【０１２０】
ところで、上記の第１乃至第４の実施の形態の最適化装置１０，２０，５０，７０において制御部１４，７４の機能は、たとえば、ＰＣなどの制御装置内のプロセッサが制御プログラムを実行することで実現してもよい。
【０１２１】
図１５は、制御装置のハードウェア例を示す図である。
制御装置９０は、ＣＰＵ９１、ＲＡＭ９２、ＨＤＤ（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）、ＤＶＤ及びＤＶＤ−Ｒ／ＲＷが含まれる。プログラムは、可搬型の記録媒体に記録されて配布されることがある。その場合、可搬型の記録媒体から他の記録媒体（たとえば、ＨＤＤ９３）にプログラムをコピーして実行してもよい。
【０１３８】
以上、実施の形態に基づき、本発明の最適化装置、最適化装置の制御方法及び最適化装置の制御プログラムの一観点について説明してきたが、これらは一例にすぎず、上記の記載に限定されるものではない。
【符号の説明】
【０１３９】
１０  最適化装置
１１ａ１〜１１ａＮ  イジング装置
１１ｂ１〜１１ｂＮ  算出回路
１１ｂ１１〜１１ｂＮ１  レジスタ
１１ｂ１２〜１１ｂＮ２  ローカルフィールド更新部
１１ｂ１３〜１１ｂＮ３  エネルギー変化算出部
１１ｃ１〜１１ｃＮ  状態遷移判定回路
１２  更新ニューロン選択回路
１３  状態更新回路
１４  制御部
２０  制御装置
【図１】
2020035179.tif 000006
【図２】
2020035179.tif 000007
【図３】
2020035179.tif 000008
【図４】
2020035179.tif 000009
【図５】
2020035179.tif 000010
【図６】
2020035179.tif 000011
【図７】
2020035179.tif 000012
【図８】
2020035179.tif 000013
【図９】
2020035179.tif 000014
【図１０】
2020035179.tif 000015
【図１１】
2020035179.tif 000016
【図１２】
2020035179.tif 000017
【図１３】
2020035179.tif 000018
【図１４】
2020035179.tif 000019
【図１５】
2020035179.tif 000020
【図１６】
2020035179.tif 000021