(57)【要約】【課題】小さな物量のハードウェアでも大規模演算を可能とする。【解決手段】制御回路１２は、複数のニューロン数よりも少ない演算処理回路１１ａ１〜１１ａｍのうちの一部の演算処理回路に複数のニューロンの一部である部分ニューロン群についての演算処理を実行させている間に、演算処理を休止中の演算処理回路１１ａｍに部分ニューロン群以外のニューロンについての演算処理に用いる情報を設定後、上記一部の演算処理回路のうちの演算処理回路１１ａ２に演算処理を休止させ、演算処理回路１１ａｍに部分ニューロン群以外のニューロンについての演算処理を開始させる。【選択図】図１
2020087009.tif 000002
【特許請求の範囲】
【請求項１】
計算対象の最適化問題を変換したイジングモデルの複数のニューロンの各々の値をそれぞれが保持するとともに、前記イジングモデルの情報と、更新対象ニューロンについての更新対象情報とに基づいて、前記ニューロンの値の更新を許容するか否かを判定する演算処理をそれぞれが行う、前記複数のニューロンの数よりも少ない複数の演算処理回路と、
前記複数の演算処理回路のうちの一部の演算処理回路に前記複数のニューロンの一部である部分ニューロン群についての前記演算処理を実行させている間に、前記複数の演算処理回路のうち、演算処理を休止中の第１の演算処理回路に前記部分ニューロン群以外のニューロンについての前記演算処理に用いる情報を設定後、前記一部の演算処理回路のうちの第２の演算処理回路に前記演算処理を休止させ、前記演算処理を休止中の第１の演算処理回路に前記部分ニューロン群以外のニューロンについての前記演算処理を開始させる制御回路と、
前記部分ニューロン群において、更新が許容されると判定された１または複数の更新許容ニューロンのうちから前記更新対象ニューロンを選択し、前記一部の演算処理回路のそれぞれが保持する前記ニューロンの値のうち、前記更新対象ニューロンの値を更新する更新ニューロン選択回路と、
を有する最適化装置。
【請求項２】
前記制御回路は、前記第２の演算処理回路が前記演算処理を休止する前に最後に計算したローカルフィールドと、前記第２の演算処理回路を休止する前に最後に更新された前記複数のニューロンの値を記憶部に記憶させた後に、前記第２の演算処理回路による前記演算処理を休止させる、請求項１に記載の最適化装置。
【請求項３】
前記第１の演算処理回路は、前記複数のニューロンの初期値に対して値が更新されたニューロンの情報と、前記部分ニューロン群以外のニューロンと前記複数のニューロンのそれぞれとの間の相互作用の大きさを示す重み係数とに基づいて、前記部分ニューロン群以外のニューロンについてのローカルフィールドを初期値から更新後、前記部分ニューロン群以外のニューロンについての前記演算処理を開始する、請求項１または２に記載の最適化装置。
【請求項４】
前記第１の演算処理回路は、前記部分ニューロン群以外のニューロンについての前回の前記演算処理が休止される前に最後に更新された前記複数のニューロンの値に対して値が更新されたニューロンの情報と、前記部分ニューロン群以外のニューロンと前記複数のニューロンのそれぞれとの間の相互作用の大きさを示す重み係数とに基づいて、前記部分ニューロン群以外のニューロンについての前回の前記演算処理が休止される前に最後に計算されたローカルフィールドを更新後、前記部分ニューロン群以外のニューロンについての前記演算処理を再開する、請求項１または２に記載の最適化装置。
【請求項５】
計算対象の最適化問題を変換したイジングモデルの複数のニューロンの数よりも少ない最適化装置が有する複数の演算処理回路のそれぞれが、前記複数のニューロンの各々の値を保持するとともに、前記イジングモデルの情報と、更新対象ニューロンについての更新対象情報とに基づいて、前記ニューロンの値の更新を許容するか否かを判定する演算処理を行い、
前記最適化装置が有する制御回路が、前記複数の演算処理回路のうちの一部の演算処理回路に前記複数のニューロンの一部である部分ニューロン群についての前記演算処理を実行させている間に、前記複数の演算処理回路のうち、演算処理を休止中の第１の演算処理回路に前記部分ニューロン群以外のニューロンについての前記演算処理に用いる情報を設定後、前記一部の演算処理回路のうちの第２の演算処理回路に前記演算処理を休止させ、前記演算処理を休止中の第１の演算処理回路に前記部分ニューロン群以外のニューロンについての前記演算処理を開始させ、
前記最適化装置が有する更新ニューロン選択回路が、前記部分ニューロン群において、更新が許容されると判定された１または複数の更新許容ニューロンのうちから前記更新対象ニューロンを選択し、前記一部の演算処理回路のそれぞれが保持する前記ニューロンの値のうち、前記更新対象ニューロンの値を更新する、
最適化装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適化装置及び最適化装置の制御方法に関する。
【背景技術】
【０００２】
ノイマン型コンピュータが不得意とする多変数の最適化問題を解く方法として、イジング型のエネルギー関数を用いた最適化装置（イジングマシンまたはボルツマンマシンと呼ばれる場合もある）がある。最適化装置は、計算対象の問題を、磁性体のスピンの振る舞いを表すモデルであるイジングモデルに置き換えて計算する。
【０００３】
最適化装置は、たとえば、ニューラルネットワークを用いてモデル化することもできる。その場合、最適化装置に含まれ、互いに結合される複数のユニット（ニューロン）のそれぞれが、他のニューロンの状態を表す状態変数（ビット）と、他のニューロンの状態変数（ビット）と自身のニューロンの状態変数（ビット）との結合の強さを示す重み係数（結合係数とも呼ばれる）とに応じて０または１を出力するニューロンとして機能する。最適化装置は、たとえば、シミュレーテッド・アニーリングなどの確率的探索法により、上記のようなエネルギー関数（コスト関数、目的関数とも呼ばれる）の最小値が得られる各ビットの状態の組み合わせを、解として求める。
【０００４】
なお、ニューラルネットワーク技術の例として、複数のニューラルネットワーク回路を接続してネットワーク規模の拡張を行うものがあった（たとえば、特許文献１参照）。また、ニューラルネットワークの接続情報を記憶装置に記憶し、その接続情報を書き換えることで、ニューラルネットワークの接続状態を変更して小規模なニューラルネットワークから大規模なニューラルネットワークまで対応させる技術があった。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平７−１９１９５１号公報
【特許文献２】特開平８−２２４４６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
確率的探索法により多数回の繰り返し演算を行う最適化装置を、ハードウェアで実現する場合、最適化問題が大規模になるほど（ニューロン数が増加するほど）ハードウェアの物量が増大してしまう問題がある。
【０００７】
１つの側面では、本発明は、小さな物量のハードウェアでも大規模演算が可能な最適化装置及び最適化装置の制御方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
１つの実施態様では、計算対象の最適化問題を変換したイジングモデルの複数のニューロンの各々の値をそれぞれが保持するとともに、前記イジングモデルの情報と、更新対象ニューロンについての更新対象情報とに基づいて、前記ニューロンの値の更新を許容するか否かを判定する演算処理をそれぞれが行う、前記複数のニューロンの数よりも少ない複数の演算処理回路と、前記複数の演算処理回路のうちの一部の演算処理回路に前記複数のニューロンの一部である部分ニューロン群についての前記演算処理を実行させている間に、前記複数の演算処理回路のうち、演算処理を休止中の第１の演算処理回路に前記部分ニューロン群以外のニューロンについての前記演算処理に用いる情報を設定後、前記一部の演算処理回路のうちの第２の演算処理回路に前記演算処理を休止させ、前記演算処理を休止中の第１の演算処理回路に前記部分ニューロン群以外のニューロンについての前記演算処理を開始させる制御回路と、前記部分ニューロン群において、更新が許容されると判定された１または複数の更新許容ニューロンのうちから前記更新対象ニューロンを選択し、前記一部の演算処理回路のそれぞれが保持する前記ニューロンの値のうち、前記更新対象ニューロンの値を更新する更新ニューロン選択回路と、を有する最適化装置が提供される。
【０００９】
また、１つの実施態様では、最適化装置の制御方法が提供される。
【発明の効果】
【００１０】
１つの側面では、小さな物量のハードウェアでも大規模演算が可能となる。
【図面の簡単な説明】
【００１１】
【図１】第１の実施の形態の最適化装置の一例を示す図である。
【図２】処理されるニューロンの入れ替え例を示す図である。
【図３】第２の実施の形態の最適化装置の一例を示す図である。
【図４】演算処理部の一例を示す図である。
【図５】演算処理回路の一例を示す図である。
【図６】第２の実施の形態の最適化装置の一例の流れを示すフローチャートである。
【図７】入れ替え処理時の各ニューロンの動作状態とアクティブにする制御信号との一例の関係を示す図である。
【図８】動作状態ａの一例を説明する模式図である。
【図９】動作状態ｂ〜ｄの一例を説明する模式図である。
【図１０】動作状態ｅの一例を説明する模式図である。
【発明を実施するための形態】
【００１２】
以下、発明を実施するための形態を、図面を参照しつつ説明する。
以下に示す最適化装置は、計算対象の最適化問題を変換したイジングモデルの複数のニューロンのそれぞれの値（以下、「ビット値」という）の組み合わせのうち、エネルギー関数が最小値となるときの各ニューロンのビット値（イジングモデルの基底状態）を探索するものである。
【００１３】
イジング型のエネルギー関数Ｅ（ｘ）は、たとえば、以下の式（１）で定義される。
【００１４】
【数１】
2020087009.tif 000003
【００１５】
右辺の１項目は、全ニューロンの全組み合わせについて、漏れと重複なく、２つのニューロンのビット値（０または１）と重み係数との積を積算したものである。ｘｉは、識別情報（以下インデックスという）がｉのニューロンのビット値を表す変数（状態変数とも呼ばれる）、ｘｊは、インデックス＝ｊのニューロンのビット値を表す変数である。Ｗｉｊは、インデックス＝ｉ，ｊのニューロンの相互作用の大きさを示す重み係数である。なお、Ｗｉｉ＝０である。また、Ｗｉｊ＝Ｗｊｉであることが多い（つまり、重み係数による係数行列は対称行列である場合が多い）。またＷｉｊは、所定のビット幅（たとえば、１６ビット、３２ビット、６４ビット、１２８ビットなど）をもつ。
【００１６】
右辺の２項目は、全ニューロンのそれぞれのバイアス係数とニューロンのビット値との積の総和を求めたものである。ｂｉは、インデックス＝ｉのニューロンのバイアス係数を示している。
【００１７】
また、ｘｉが変化して１−ｘｉとなると、ｘｉの増加分は、Δｘｉ＝（１−ｘｉ）−ｘｉ＝１−２ｘｉと表せる。スピン反転（ニューロンのビット値の変化）に伴うエネルギー変化（ΔＥｉ）は、以下の式（２）で表される。
【００１８】
【数２】
2020087009.tif 000004
【００１９】
式（２）において、ｘｉが１から０に変化するとき、Δｘｉは−１となり、ｘｉが０から１に変化するとき、Δｘｉは１となる。なお、ｈｉはローカルフィールド（局所場）と呼ばれ、Δｘｉに応じてｈｉに符号（＋１または−１）を乗じたものがΔＥｉである。つまり、ｈｉは、エネルギー変化ΔＥｉの大きさを示す。ｈｉが０より小さければ、ｘｉを１から０へ更新することで、全エネルギーが減少し、ｈｉが０より大きければ、ｘｉを０から１へ更新することで、全エネルギーが減少する。
【００２０】
また、ｘｊが０から１に変化したときのｈｉの変化分（Δｈｉ）は、＋Ｗｉｊ、ｘｊが１から０に変化したときのΔｈｉは、−Ｗｉｊと表せる。したがって、状態遷移にともなって更新されたニューロンのビット値が１か０かによって、Ｗｉｊを元のｈｉに加算または減算することで、ｈｉの更新が可能である。
【００２１】
（第１の実施の形態）
図１は、第１の実施の形態の最適化装置の一例を示す図である。
第１の実施の形態の最適化装置１０は、演算処理回路１１ａ１，１１ａ２，…，１１ａｍ、制御回路１２、更新ニューロン選択回路１３を有する。
【００２２】
演算処理回路１１ａ１〜１１ａｍのそれぞれは、複数のニューロンの各々のビット値を保持する。また、演算処理回路１１ａ１〜１１ａｍのそれぞれは、イジングモデル情報と、更新ニューロン選択回路１３から供給される更新対象ニューロンについての更新対象情報とに基づいて、ニューロンのビット値の更新を許容するか否かを判定する演算処理を行う。たとえば、演算処理回路１１ａ１〜１１ａｍのそれぞれは、まず、イジングモデル情報と更新対象情報とに基づいて、ローカルフィールドを計算する。イジングモデル情報は、前述の重み係数を含む。更新対象情報は、更新対象ニューロンのビット値とインデックスを含む。ローカルフィールドは、更新対象ニューロンのビット値が１か０かによって、演算処理回路１１ａ１〜１１ａｍのそれぞれが処理するニューロンと、更新対象ニューロンとの間の相互作用の大きさを示す重み係数を前の値に加算または減算することで更新されていく。そのため、ローカルフィールドの計算は、加算または減算を行う回路などを用いて実現できる。なお、演算処理回路１１ａ１〜１１ａｍのそれぞれは、式（２）に基づいて、エネルギー変化自体を計算してもよい。
【００２３】
そして、演算処理回路１１ａ１〜１１ａｍのそれぞれは、温度パラメータと、乱数とに基づいて決定される熱ノイズと、ローカルフィールドと、それぞれが保持するニューロンのビット値とに基づいて、そのニューロンのビット値の更新を許容するか否かを判定する。温度パラメータは、制御回路１２から入力される。
【００２４】
前述のようにインデックス＝ｉのニューロンについてのｈｉが０より小さくｘｉが１の場合、ｘｉを１から０へ更新することで、全エネルギーが減少する。また、ｈｉが０より大きくｘｉが０の場合、ｘｉを０から１へ更新することで、全エネルギーが減少する。これらに対して、ｈｉが０より小さくｘｉが０の場合、ｘｉを０から１へ更新することで、全エネルギーが増加する。また、ｈｉが０より大きくｘｉが１の場合、ｘｉを１から０へ更新することで、全エネルギーが増加する。
【００２５】
イジングモデルの状態が基底状態（最適解）ではない、局所解にトラップされることを防止するために、演算処理回路１１ａ１〜１１ａｍは、熱ノイズを用いて、エネルギーが増加する状態遷移も所定の確率で発生させる。
【００２６】
熱ノイズは、温度パラメータが大きいほどノイズ幅が大きくなる。シミュレーテッド・アニーリングが行われる場合、制御回路１２によって、温度パラメータは徐々に小さくなるように制御される。
【００２７】
上記の判定処理は、ＬＦＳＲ（Linear Feedback Shift Registers）などの乱数生成器を用いて熱ノイズを生成する回路や比較回路などにより実現される。
演算処理回路１１ａ１〜１１ａｍのそれぞれは、上記のような処理を含む演算処理を繰り返し行う。
【００２８】
なお、演算処理回路１１ａ１〜１１ａｍの数は、全ニューロンの数よりも少ない。このため、後述する制御回路１２によって、演算処理が行われるニューロンが入れ替えられる。
【００２９】
演算処理回路１１ａ１〜１１ａｍは、たとえば、１チップまたは複数チップの半導体集積回路（ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field-Programmable Gate Array）など）に含まれる。
【００３０】
制御回路１２は、制御信号ＣＮＴ１，ＣＮＴ２，…，ＣＮＴｍを出力し、制御信号ＣＮＴ１〜ＣＮＴｍによって、演算処理回路１１ａ１〜１１ａｍのそれぞれを以下のように制御する。制御回路１２は、演算処理回路１１ａ１〜１１ａｍのうちの一部の演算処理回路に、あるニューロン群（以下部分ニューロン群という）についての演算処理を実行させている間に、ある演算処理回路（以下第１演算処理回路という）による演算処理を休止させる。そして、制御回路１２は、第１演算処理回路に部分ニューロン群以外のあるニューロン（以下第１ニューロンという）についての演算処理に用いる情報を設定する。演算処理に用いる情報は、たとえば、全ニューロンのビット値の初期値に対してビット値が変更されたニューロンの情報と、第１ニューロンと全ニューロンのそれぞれとの間の相互作用の大きさを示す重み係数、部分ニューロン群以外のニューロンについてのローカルフィールドの初期値を含む。値が変更されたニューロンの情報は、そのニューロンのビット値とインデックスを含む。なお、過去に部分ニューロン群以外のニューロンについての演算処理が行われた場合には、演算処理に用いる情報は、前回、その演算処理が休止される前に最後に更新された全ニューロンのビット値に対して値が更新されたニューロンの情報を含む。また、その場合、演算処理が休止される前に最後に計算された第１ニューロンについてのローカルフィールドも、演算処理に用いる情報に含まれる。以上の情報は、記憶部１２ａに記憶されている。
【００３１】
制御回路１２は、演算処理に用いる情報の設定後に、演算処理を実行中の一部の演算処理回路のうちのある演算処理回路（以下第２演算処理回路という）に演算処理を休止させる。そして、制御回路１２は、休止中であった第１演算処理回路に上記一部の演算処理回路の１つとして、第１ニューロンについての演算処理を開始（または再開）させる。
【００３２】
なお、制御回路１２は、第２演算処理回路が演算処理を休止する前に最後に計算したローカルフィールドと、第２演算処理回路が演算処理を休止する前に最後に更新された全ニューロンのビット値を記憶部１２ａに記憶させる。たとえば、制御回路１２は、第２演算処理回路が演算処理を休止する前に最後に更新された部分ニューロン群のビット値を、演算処理を実行中の演算処理回路から取得する。そして、制御回路１２は、記憶部１２ａに記憶されている全ニューロンのうち部分ニューロン群のビット値を取得した値を用いて更新し、更新した全ニューロンのビット値を、現在の全ニューロンのビット値とは別に記憶部１２ａに記憶しておく。
【００３３】
以上のように、制御回路１２は、演算処理回路１１ａ１〜１１ａｍによって処理されるニューロンを入れ替える。
なお、制御回路１２は、演算処理回路１１ａ１〜１１ａｍによって処理されるニューロンを所定の順序で入れ替えてもよいし、乱数に基づいて入れ替えてもよい。
【００３４】
制御回路１２は、たとえば、ＡＳＩＣやＦＰＧＡなどの特定用途の電子回路にて実現できる。なお、制御回路１２は、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）などのプロセッサであってもよい。その場合、プロセッサは、記憶部１２ａに記憶されたプログラムを実行することで、上記のような制御回路１２の処理を行う。
【００３５】
記憶部１２ａは、全重み係数、全バイアス係数、全ニューロンのビット値、ローカルフィールドの初期値（たとえば、バイアス係数）を記憶する。また、記憶部１２ａは、第２演算処理回路が最後に計算したローカルフィールドや、第２演算処理回路が演算処理を休止する前に最後に更新された全ニューロンのビット値を記憶する。
【００３６】
なお、図１の例では、記憶部１２ａは制御回路１２の中に設けられているが、制御回路１２の外に設けられていてもよい。記憶部１２ａは、たとえば、ＳＤＲＡＭ（Synchronous Dynamic Random Access Memory）などの揮発性の記憶装置、または、フラッシュメモリ、ＥＥＰＲＯＭ（Electrically Erasable Programmable Read Only Memory）やＨＤＤ（Hard Disk Drive）などの不揮発性の記憶装置、またはこれらの組み合わせであってもよい。
【００３７】
更新ニューロン選択回路１３は、部分ニューロン群において、更新が許容されると判定された１または複数の更新許容ニューロンのうちから更新対象ニューロンを選択する。そして、更新ニューロン選択回路１３は、演算処理を実行中の演算処理回路のそれぞれが保持するニューロンのビット値のうち、更新対象ニューロンのビット値を更新する。また、更新ニューロン選択回路１３は、更新対象情報を、演算処理を実行中の演算処理回路に供給する。更新ニューロン選択回路１３は、たとえば、更新許容ニューロンが複数ある場合に、乱数に基づいて、１つを更新対象ニューロンとして選択する選択回路を用いて実現される。
【００３８】
以下、第１の実施の形態の最適化装置１０の動作例を説明する。
制御回路１２は、演算処理回路１１ａ１〜１１ａｍのうちの一部の演算処理回路に部分ニューロン群についての演算処理を実行させる。
【００３９】
たとえば、図１に示すように、制御回路１２は、まず演算処理回路１１ａ１〜１１ａｍのうち演算処理回路１１ａｍ以外に、ｍ−１個のニューロンを含む部分ニューロン群についての演算処理を実行させ、演算処理回路１１ａｍによる演算処理を休止させる。
【００４０】
その場合、制御回路１２は、演算処理回路１１ａ１〜１１ａｍのうち演算処理回路１１ａｍ以外のそれぞれには、記憶部１２ａに記憶されている、ｍ−１個のニューロンの何れかについての演算処理に用いるイジングモデル情報を設定する。
【００４１】
たとえば、以下では、ｍ−１個のニューロンのインデックスが１〜ｍ−１であるとする。このとき、演算処理回路１１ａ１がインデックス＝１のニューロンについての演算処理を行う場合、制御回路１２は、演算処理回路１１ａ１に、Ｗ１１〜Ｗ１（ｍ−１）を設定する。なお、制御回路１２は、インデックス＝１のニューロンについての演算処理を行う演算処理回路１１ａ１に、全ニューロンのそれぞれとインデックス＝１のニューロンとの間の相互作用の大きさを示す重み係数（Ｗ１１〜Ｗ１ｎ）を設定してもよい。なお、ｎは全ニューロン数である。
【００４２】
また、制御回路１２は、記憶部１２ａに記憶されているｍ−１個のニューロンのビット値の初期値と、ローカルフィールドの初期値を、演算処理回路１１ａ１〜１１ａｍのうち演算処理回路１１ａｍ以外のそれぞれに設定する。全ニューロンのビット値の初期値が０である場合には、式（２）より、ローカルフィールドの初期値はバイアス係数である。そして、演算処理回路１１ａ１〜１１ａｍのうち演算処理回路１１ａｍ以外のそれぞれは、ローカルフィールドの初期値と熱ノイズとｍ−１個のニューロンのビット値の初期値とに基づいて、ｍ−１個のニューロンのそれぞれについて、更新を許容するか否かを判定する。
【００４３】
更新ニューロン選択回路１３は、ｍ−１個のニューロンにおいて、更新が許容されると判定された１または複数の更新許容ニューロンのうちから更新対象ニューロンを選択する。そして、更新ニューロン選択回路１３は、演算処理回路１１ａ１〜１１ａｍのうち演算処理回路１１ａｍ以外が保持するニューロンのビット値のうち、更新対象ニューロンのビット値を更新する。また、更新ニューロン選択回路１３は、更新対象ニューロンのビット値とインデックスを、演算処理回路１１ａ１〜１１ａｍのうち演算処理回路１１ａｍ以外に供給する。図１の例では、インデックス＝ｊと、更新対象ニューロンのビット値であるｘｊが、演算処理回路１１ａ１，１１ａ２などに供給されている。
【００４４】
演算処理回路１１ａ１〜１１ａｍのうち演算処理回路１１ａｍ以外では、供給された更新対象情報とイジングモデル情報とに基づいて、ローカルフィールドの計算（更新）が行われる。たとえば、演算処理回路１１ａ１がインデックス＝１のビットについてのローカルフィールド（ｈ１）を更新する場合、演算処理回路１１ａ１は、更新後のｘｊが１のときには、元のｈ１にＷ１ｊを加算し、更新後のｘｊが０のときには元のｈ１からＷ１ｊを減算する。
【００４５】
また、演算処理回路１１ａ１〜１１ａｍのうち演算処理回路１１ａｍ以外は、更新されたローカルフィールドに基づいて、上記のような判定処理を再度行う。また、更新ニューロン選択回路１３は、更新対象ニューロンの選択、更新対象ニューロンの更新及び、更新対象ニューロンの情報の演算処理回路１１ａ１〜１１ａｍのうち演算処理回路１１ａｍ以外への供給を再度行う。
【００４６】
制御回路１２は、以上のような演算処理が所定回数繰り返されるごとに、温度パラメータを小さくしていく。そして、制御回路１２は、たとえば、演算処理を実行中の演算処理回路の何れにおいても、所定期間、ローカルフィールドの変化分が０のまま、もしくは、演算処理が所定回数（温度パラメータを変更する際の回数より多い）繰り返された場合、以下の処理を行う。
【００４７】
制御回路１２は、演算処理回路１１ａ１〜１１ａｍのうちの演算処理回路１１ａｍ以外に、演算処理を実行させている間に、演算処理回路１１ａｍに第１ニューロンについての演算処理に用いる情報を設定する。
【００４８】
図１の例では、インデックス＝１〜ｍ−１に含まれないインデックス＝８のニューロンについての演算処理に用いるＷ８１〜Ｗ８ｎが、演算処理回路１１ａｍに設定されている。また、制御回路１２は、ｈ８の初期値（全ニューロンのビット値の初期値が０である場合はバイアス係数（ｂ８））を、演算処理回路１１ａｍに設定する。また、演算処理回路１１ａｍがｈ８の初期値を現在の全ニューロンのビット値に応じて更新できるように、たとえば、制御回路１２は、全ニューロンのうち初期値と異なるニューロンの情報を演算処理回路１１ａｍに順に供給する。なお、ｈ８の更新中に、更新ニューロン選択回路１３が更新対象情報を出力した場合には、演算処理回路１１ａｍは、たとえば、制御回路１２から供給される情報を用いたｈ８の更新処理を中断する。そして、演算処理回路１１ａｍは、更新ニューロン選択回路１３から供給された更新対象情報を用いてｈ８を更新した後に、制御回路１２から供給される情報を用いたｈ８の更新を再開する。なお、演算処理回路１１ａｍは、更新ニューロン選択回路１３から供給される更新対象情報と、制御回路１２から供給される情報とを両方、同じタイミングで用いてｈ８を更新してもよい。たとえば、更新ニューロン選択回路１３が、インデックス＝１とｘ１＝１を出力し、制御回路１２が、インデックス＝２とｘ２＝１を出力した場合、演算処理回路１１ａｍは、ｈ８に対して、Ｗ８１＋Ｗ８２を加えることで同じタイミングでｈ８を更新できる。
【００４９】
なお、演算処理回路１１ａ１〜１１ａｍのうち演算処理を継続させる演算処理回路に、インデックス＝８のニューロンに関する重み係数が設定されていない場合には、制御回路１２の制御に基づいてその重み係数が設定される。
【００５０】
そして、制御回路１２は、演算処理を実行中の演算処理回路のうちの１つである、たとえば、演算処理回路１１ａ２に演算処理を休止させる。なお、制御回路１２は、演算処理回路１１ａ２が演算処理を休止する前に最後に計算したローカルフィールド（ｈ２）と、演算処理回路１１ａ２が演算処理を休止する前に最後に更新された全ニューロンのビット値を記憶部１２ａに記憶させる。
【００５１】
その後、制御回路１２は、休止中であった演算処理回路１１ａｍに、インデックス＝８のニューロンについての演算処理を開始させる。
その後は同様の処理が繰り返される。図１では、演算処理を休止中の演算処理回路１１ａ２にインデックス＝７のニューロンについての演算処理に用いる情報（Ｗ７１〜Ｗ７ｎなど）が設定される例が示されている。
【００５２】
なお、記憶部１２ａに記憶されたｈ２や全ニューロンのビット値は、インデックス＝２のニューロンについての演算処理が再度行われるときに、その演算処理を実行する演算処理回路に設定される。そして、上記のようなｈ８を更新する処理と同様の処理にてｈ２の更新が行われる。
【００５３】
なお、制御回路１２は、演算処理回路１１ａ１〜１１ａｍによって処理されるニューロンを、たとえば、所定の順序で入れ替える。
図２は、処理されるニューロンの入れ替え例を示す図である。
【００５４】
説明を簡略化するために、全ニューロン数は１０、演算処理回路１１ａ１〜１１ａｍの数は５であるとする（ｍ＝５）。なお、図２では、インデックス＝１〜１０のニューロンが、ニューロン１〜ニューロン１０と表記されている。
【００５５】
たとえば、制御回路１２は、初めは、演算処理回路１１ａ１〜１１ａ４に、ニューロン１〜４についての演算処理を実行させ、休止中の演算処理回路１１ａ５にニューロン１０についての演算処理に用いる情報を設定する。次に、制御回路１２は、演算処理回路１１ａ１〜１１ａ３，１１ａ５に、ニューロン１〜３，１０についての演算処理を実行させ、休止中の演算処理回路１１ａ４にニューロン９についての演算処理に用いる情報を設定する。その後、制御回路１２は、演算処理回路１１ａ１，１１ａ２，１１ａ４，１１ａ５に、ニューロン１，２，９，１０についての演算処理を実行させ、休止中の演算処理回路１１ａ３にニューロン８についての演算処理に用いる情報を設定する。
【００５６】
制御回路１２は、以上のような入れ替え処理を、たとえば、全てのニューロンについての演算処理が実施されるまで、もしくは、演算処理を実行中の演算処理回路の何れにおいても、所定期間、ローカルフィールドの変化分が０から変化しなくなるまで繰り返す。そして、制御回路１２は、上記の入れ替え処理が終了したときの各ニューロンのビット値を最適化問題の解として出力する。
【００５７】
以上のような、第１の実施の形態の最適化装置１０は、全ニューロン数より少ない演算処理回路の一部に一部のニューロンについての演算処理を実行させている間に、演算処理を休止中の演算処理回路に他のニューロンの演算処理に用いる情報を設定する。最適化装置１０は、その上で、演算処理を休止させる演算処理回路を入れ替えることで、他のニューロンについての演算処理が行えるようになるため、少物量で大規模演算が可能となる。
【００５８】
また、演算処理を休止中の演算処理回路への他のニューロンについての演算処理に用いる情報の設定は、他の演算処理回路が演算処理を実行中に行われるため、処理されるニューロンの入れ替えによる演算処理の中断が発生せず、計算時間の増加を抑えられる。
【００５９】
また、１チップでも大規模演算が可能になるため、多チップを用いる場合に発生するようなチップ間接続の複雑化などの問題が生じることがない。
なお、上記の説明では、演算処理を休止する演算処理回路を１つとしたが、複数としてもよい。その場合、処理されるニューロンと処理が休止されるニューロンが複数同時に入れ替えられるようにしてもよい。
【００６０】
（第２の実施の形態）
図３は、第２の実施の形態の最適化装置の一例を示す図である。
最適化装置２０は、制御回路２１、演算処理部２２を有する。
【００６１】
制御回路２１は、演算処理部２２に対して、各種制御信号を出力して、演算処理部２２における演算処理を制御する。また、制御回路２１は、記憶部２１ａを有しており、記憶部２１ａに記憶されている各種情報を演算処理部２２に供給するとともに、演算処理部２２にて得られた情報（計算結果や計算途中の情報）を記憶部２１ａに記憶させる。
【００６２】
また、制御回路２１は、制御装置２３（たとえば、ＰＣ（Personal Computer））との間で情報の送受信を行う。制御装置２３から制御回路２１に送られる情報としては、たとえば、全重み係数、全バイアス係数、全ニューロンのビット値の初期値、ローカルフィールドの初期値、温度パラメータをどのように変更するかについての温度変更スケジュールなどがある。制御回路２１が制御装置２３に送信する情報としては、たとえば、演算処理部２２によって得られた最適化問題の計算結果などがある。
【００６３】
制御回路２１は、たとえば、ＡＳＩＣやＦＰＧＡなどの特定用途の電子回路にて実現できる。なお、制御回路２１は、ＣＰＵやＤＳＰなどのプロセッサであってもよい。その場合、プロセッサは、たとえば、記憶部２１ａに記憶されたプログラムを実行することで各種の処理を行う。
【００６４】
記憶部２１ａは、全重み係数、全バイアス係数、全ニューロンのビット値、ローカルフィールドの初期値を記憶する。また、記憶部２１ａは、演算処理部２２にて得られた情報（計算結果や計算途中の情報）を記憶する。
【００６５】
なお、図３の例では、記憶部２１ａは制御回路２１の中に設けられているが、制御回路２１の外に設けられていてもよい。記憶部２１ａは、たとえば、ＳＤＲＡＭなどの揮発性の記憶装置、または、フラッシュメモリ、ＥＥＰＲＯＭやＨＤＤなどの不揮発性の記憶装置、またはこれらの組み合わせであってもよい。
【００６６】
演算処理部２２は、制御回路２１の制御のもと、イジングモデルの基底状態の探索を行う。
図４は、演算処理部の一例を示す図である。
【００６７】
演算処理部２２は、演算処理回路２２ａ１，２２ａ２，…，２２ａｍ、更新ニューロン選択回路２２ｂを有する。
演算処理回路２２ａ１〜２２ａｍのそれぞれは、複数のニューロンの各々のビット値を保持する。また、演算処理回路２２ａ１〜２２ａｍのそれぞれは、重み係数と、更新ニューロン選択回路２２ｂから供給される更新対象ニューロンのビット値とインデックスとに基づいて、ローカルフィールドを計算する。そして、演算処理回路２２ａ１〜２２ａｍのそれぞれは、温度パラメータと、乱数とに基づいて決定される熱ノイズと、ローカルフィールドと、ニューロンのビット値とに基づいて、そのニューロンのビット値の更新を許容するか否かを判定する。温度パラメータは、制御回路２１から供給される。演算処理回路２２ａ１〜２２ａｍのそれぞれは、上記のような処理を含む演算処理を繰り返し行う。以下では上記の演算処理の繰り返しをイタレーション動作と呼ぶ場合もある。
【００６８】
なお、演算処理回路２２ａ１〜２２ａｍの数は、全ニューロンの数よりも少ない。このため、制御回路２１によって、演算処理が行われるニューロンが入れ替えられる。
演算処理回路２２ａ１〜２２ａｍは、たとえば、１チップまたは複数チップの半導体集積回路（ＡＳＩＣやＦＰＧＡなど）に含まれる。
【００６９】
なお、図４には各種制御信号が示されている。制御信号は、制御回路２１内の図示しない制御信号生成回路にて生成される。記憶部２１ａには、制御信号ＣＳｉ，ＣＷｉｊが供給される。
【００７０】
制御信号ＣＳｉは、インデックス＝ｉ（ｉは１〜ｎの何れか）のニューロンについての演算処理に用いる情報のうち、重み係数以外を記憶部２１ａから読み出して、演算処理回路２２ａ１〜２２ａｍの何れかに設定するための制御信号である。読み出された情報の例については後述する。
【００７１】
制御信号ＣＷｉｊ（ｉ，ｊは１〜ｎの何れか）は、全重み係数の何れかを記憶部２１ａから読み出して、演算処理部２２に設定するための制御信号である。
また、演算処理回路２２ａ１〜２２ａｍには、制御信号ＣＮｉ，ＯＥｉが供給される。
【００７２】
制御信号ＣＮｉは、インデックス＝ｉのニューロンについての演算処理の実行と休止を制御する制御信号である。制御信号ＣＮｉがアクティブである場合、インデックス＝ｉのニューロンについての演算処理が実行され、制御信号ＣＮｉが非アクティブである場合（たとえば、値が０である場合）、インデックス＝ｉのニューロンについての演算処理が休止される。
【００７３】
制御信号ＯＥｉは、インデックス＝ｉのニューロンについての処理が休止される際に、演算処理を実行中の演算処理回路から各ニューロンのビット値を読み出すとともに、インデックス＝ｉのニューロンについてのローカルフィールドを読み出すための制御信号である。
【００７４】
また、更新ニューロン選択回路２２ｂには、制御信号ＥＸｉが供給される。
制御信号ＥＸｉは、更新対象ニューロンとして、インデックス＝ｉのニューロンを選択することを有効にするか否かを制御する制御信号である。制御信号ＥＸｉがアクティブである場合、更新対象ニューロンとして、インデックス＝ｉのニューロンを選択することが有効になる。
【００７５】
図５は、演算処理回路の一例を示す図である。図５では、演算処理回路２２ａ１の例を示しているが、他の演算処理回路２２ａ２〜２２ａｍについても、図５と同様の回路にて実現できる。
【００７６】
演算処理回路２２ａ１は、レジスタ３０、選択回路３１，３２、乗算回路３３、加算回路３４、レジスタ３５、ノイズ発生回路３６、加算回路３７、比較回路３８、排他的論理和回路であるＸＯＲ回路３９、レジスタ４０を有する。また、演算処理回路２２ａ１は、更新対象情報選択回路４１と情報読出回路４２とを有する。
【００７７】
レジスタ３０には、記憶部２１ａから読み出されたＷｉｊが設定（格納）される。
選択回路３１は、後述する更新対象情報選択回路４１が出力するインデックスに基づいて、レジスタ３０に格納されているＷｉｊのうち１つを選択して出力する。
【００７８】
更新対象ニューロンのビット値の更新前の値をｘｊｐとした場合、ｘｊｐがｘｊに変化したときのｈｉの変化分（Δｈｉ）は、Ｗｉｊ（１−２ｘｊｐ）と表せる。
選択回路３２は、上記の（１−２ｘｊｐ）の演算を実現するものであり、後述する更新対象情報選択回路４１が出力するニューロンのビット値に基づき、１または−１を選択して出力する。ニューロンのビット値が０のときには、選択回路３２は、−１を選択して出力し、ニューロンのビット値が１のときには、選択回路３２は、１を選択して出力する。
【００７９】
乗算回路３３は、選択回路３１が出力する重み係数と、選択回路３２が出力する値との積であるΔｈｉを出力する。
加算回路３４は、Δｈｉとレジスタ３５に格納されているｈｉとを加算することで、ｈｉを更新する。
【００８０】
レジスタ３５は、クロック信号ｃｌｋａ（たとえば、制御回路２１から供給される）に同期して、加算回路４５が出力するｈｉを取り込む。レジスタ３５は、たとえば、フリップフロップである。なお、レジスタ３５には、インデックス＝ｉのニューロンについての演算処理の初期化時に、ｈｉの初期値が、制御回路２１によって記憶部２１ａから読み出されて設定される。また、レジスタ３５には、インデックス＝ｉのニューロンについての演算処理の休止状態からの再開時に、最後に算出されたｈｉが、制御回路２１によって記憶部２１ａから読み出されて設定される。
【００８１】
ノイズ発生回路３６は、シミュレーテッド・アニーリングを行うために、温度パラメータ（Ｔ）と乱数とに基づいて熱ノイズを発生する。ノイズ発生回路３６として、たとえば、ＬＦＳＲなどを用いることができる。シミュレーテッド・アニーリングの際、Ｔは制御回路２１によって徐々に小さくなるように制御される。それに伴って、ノイズ発生回路３６が発生する熱ノイズのノイズ幅は徐々に小さくなる。
【００８２】
加算回路３７は、レジスタ３５が出力するローカルフィールドｈｉに、ノイズ発生回路３６が出力する熱ノイズを加算して出力する。
比較回路３８は、加算回路３７が出力する値が、閾値（たとえば、０）以上のときには０を出力し、閾値より小さいときには１を出力する。なお、比較回路３８には、制御回路２１から制御信号ＣＮｉが供給され、制御信号ＣＮｉが非アクティブの場合には、比較動作を行わないことで、インデックス＝ｉのニューロンについての演算処理が休止される。
【００８３】
ＸＯＲ回路３９は、比較回路３８が出力する値と、レジスタ４０に格納されている値（ｘｉ）とに基づきインデックス＝ｉのニューロンのビット値の更新を許容するか否かを示す値を出力する。たとえば、ＸＯＲ回路３９は、比較回路３８が出力する値と、レジスタ４０に格納されているｘｉが一致しているときは更新を許容しないことを示す０を出力し、異なるときは更新を許容することを示す１を出力する。ＸＯＲ回路３９の出力値は、更新ニューロン選択回路２２ｂに供給される。
【００８４】
レジスタ４０は、更新ニューロン選択回路２２ｂからクロック信号ｃｌｋｂが供給されたときに、比較回路３８が出力する値を、ｘｉとして取り込む。なお、レジスタ４０には、インデックス＝ｉのニューロンについての演算処理の初期化時に、ｘｉの初期値が、制御回路２１によって記憶部２１ａから読み出されて設定される。また、レジスタ４０には、インデックス＝ｉのニューロンについての演算処理の休止状態からの再開時に、最後に算出されたｘｉが、制御回路２１によって記憶部２１ａから読み出されて設定される。レジスタ４０が出力するｘｉは、更新ニューロン選択回路２２ｂに供給される。
【００８５】
更新対象情報選択回路４１には、更新ニューロン選択回路２２ｂが出力する更新対象ビットの値（ｘｊ）と更新対象ビットのインデックス＝ｊが供給される。また、更新対象情報選択回路４１には、演算処理回路２２ａ１が休止状態から復帰する際に、制御回路２１からｘｊａとインデックス＝ｊａが供給される。
【００８６】
演算処理回路２２ａ１が休止状態から復帰して、これまで選択されなかったインデックス＝ｉのニューロンについての処理が行われる場合、ｈｉの初期値を、現在の全ニューロンのビット値に応じて更新させることになる。または、演算処理回路２２ａ１が休止状態から復帰して、インデックス＝ｉのニューロンについての処理が再度行われる場合、前回の処理において最後に算出されたｈｉを、現在の全ニューロンのビット値に応じて更新させることになる。そのため、制御回路２１は、全ニューロンのビット値の初期値または前回のインデックス＝ｉのニューロンについての処理が休止される前に最後に更新された全ニューロンのビット値に対して、更新されたニューロンの情報を記憶部２１ａから読み出して更新対象情報選択回路４１に供給する。図５では、更新されたニューロンの情報は、値（ｘｊａ）とインデックス＝ｊａとして示されている。そして、更新対象情報選択回路４１は、インデックス＝ｊａを選択回路３１に供給し、ｘｊａを選択回路３２に供給する。これによって、ｈｉが更新される。このような処理は、更新された全ニューロンについて行われる。ただ、ｈｉの更新中に、更新ニューロン選択回路２２ｂがｘｊやインデックス＝ｊを出力した場合には、たとえば、更新対象情報選択回路４１は、ｘｊａとインデックス＝ｊａの選択を一時中断して、ｘｊとインデックス＝ｊを選択して出力する。
【００８７】
また、更新対象情報選択回路４１は、制御回路２１からｘｊａとインデックス＝ｊａが供給されない場合には、更新ニューロン選択回路２２ｂから供給されるｘｊとインデックス＝ｊとを選択して出力する。
【００８８】
情報読出回路４２は、制御信号ＯＥｉがアクティブの場合、レジスタ４０に保持されているｘｉを読み出し、制御回路２１に送信する。インデックス＝ｉが、後述する処理を休止するニューロンのインデックス＝Ｍの場合、情報読出回路４２は、ｘｉとともにレジスタ３５に保持されているｈｉ（＝ｈＭ）を読み出し、制御回路２１に送信する。なお、演算処理回路２２ａ１は、たとえば、現在どのニューロンについての演算処理を行っているかを識別するためのインデックスを保持するレジスタを有していてもよい。インデックスは、制御回路２１によって設定される。
【００８９】
更新ニューロン選択回路２２ｂは、演算処理回路２２ａ１〜２２ａｍのうち、演算処理を実行している演算処理回路が出力する１または複数の更新許容ニューロンのうちから更新対象ニューロンを選択する。そして、更新ニューロン選択回路２２ｂは、演算処理を実行中の演算処理回路のそれぞれが保持するニューロンのビット値のうち、更新対象ニューロンのビット値を更新する。たとえば、更新ニューロン選択回路２２ｂは、更新対象ニューロンについての演算処理を実行している演算処理回路に対して、上記のようなクロック信号ｃｌｋｂを供給する。なお、更新ニューロン選択回路２２ｂは、制御信号ＥＸｉが非アクティブになっているニューロンについては更新対象ニューロンとして選択しない。また、更新ニューロン選択回路２２ｂは、更新対象ニューロンのビット値とインデックスを、演算処理を実行中の演算処理回路に供給する。更新ニューロン選択回路２２ｂは、たとえば、更新許容ニューロンが複数ある場合に、乱数に基づいて、１つを更新対象ニューロンとして選択する選択回路などを用いて実現される。
【００９０】
以下、第２の実施の形態の最適化装置２０の動作例を説明する。
図６は、第２の実施の形態の最適化装置の一例の流れを示すフローチャートである。
まず、制御回路２１は、演算処理部２２において最初に処理させるニューロン群Ｌを指定する（ステップＳ１０）。ニューロン群Ｌのニューロン数は、ｍ−１以下である（ｍは演算処理回路２２ａ１〜２２ａｍの数）。なお、最初に処理させるニューロン群Ｌは制御装置２３が、最適化装置２０に対して指定してもよい。
【００９１】
ニューロン群Ｌの指定後、制御回路２１は、制御信号ＣＳｉ（Ｌ），ＣＷｉｊ（Ｌ）をアクティブにする（ステップＳ１１）。制御信号ＣＳｉ（Ｌ）は、ニューロン群Ｌに含まれるニューロンについての演算処理に用いられる制御信号ＣＳｉである。制御信号ＣＷｉｊ（Ｌ）は、ニューロン群Ｌに含まれるニューロンについての演算処理に用いられる制御信号ＣＷｉｊである。制御信号ＣＳｉ（Ｌ），ＣＷｉｊ（Ｌ）がアクティブとなることにより、演算処理回路２２ａ１〜２２ａｍのうち、ニューロン群Ｌに含まれるニューロン数と同数の動作予定の演算処理回路に、ｘｉ（Ｌ）、ｈｉ（Ｌ）、Ｗｉｊ（Ｌ）が設定される。ｘｉ（Ｌ）、ｈｉ（Ｌ）はニューロン群Ｌに含まれるニューロンのビット値の初期値と、ニューロン群Ｌに含まれるニューロンについてのローカルフィールドの初期値である。Ｗｉｊ（Ｌ）は、ニューロン群Ｌに含まれるニューロン間の相互作用の大きさを示す重み係数である。また、ステップＳ１１の処理では、温度パラメータの初期値も動作予定の演算処理回路に設定される。
【００９２】
その後、制御回路２１は、制御信号ＣＮｉ（Ｌ），ＥＸｉ（Ｌ）をアクティブにし、制御信号ＣＳｉ（Ｌ），ＣＷｉｊ（Ｌ）を非アクティブにする（ステップＳ１２）。制御信号ＣＮｉ（Ｌ）は、ニューロン群Ｌに含まれるニューロンについての演算処理の実行と休止を制御する制御信号ＣＮｉである。制御信号ＥＸｉ（Ｌ）は、ニューロン群Ｌに含まれるニューロンを、更新対象ニューロンとして選択することを有効にするか否かを制御する制御信号ＥＸｉである。制御信号ＣＮｉ（Ｌ），ＥＸｉ（Ｌ）がアクティブになることにより、ニューロン群Ｌに含まれるニューロンのそれぞれについてのイタレーション動作が、演算処理回路にて行われる。演算処理回路２２ａ１〜２２ａｍのうち、ニューロン群Ｌに含まれるニューロン数以外の演算処理回路はイタレーション動作を休止している。
【００９３】
その後、制御回路２１は、終了条件が満たされているか否かを判定する（ステップＳ１３）。制御回路２１は、たとえば、全ニューロンについての演算処理が実施され、最後に入れ替えられたニューロンを含むニューロン群についてのイタレーション動作において、所定期間、どのニューロンについてもΔｈｉが０の場合、終了条件が満たされたと判定する。または、制御回路２１は、全てのニューロンについての演算処理が実施された後に、所定期間、どのニューロンについてもΔｈｉが０となるまで、入れ替え処理を継続してもよい。Δｈｉは、たとえば、図５に示したような乗算回路３３の出力から検出できる。
【００９４】
終了条件が満たされる場合、ステップＳ２２の処理が行われる。
終了条件が満たされない場合、制御回路２１は、処理対象となるニューロンを入れ替えるか否かの入替条件が満たされているか否かを判定する（ステップＳ１４）。制御回路２１は、たとえば、所定期間、処理されているどのニューロンについてもΔｈｉが０のままである場合、入替条件が満たされたと判定する。または、制御回路２１は、イタレーション動作の回数が所定回数に達した場合に、入替条件が満たされたと判定してもよい。
【００９５】
入替条件が満たされない場合、ステップＳ２０の処理が行われる。
入替条件が満たされた場合、制御回路２１は、インデックス＝Ｋ，Ｍを指定する（ステップＳ１５）。インデックス＝Ｋは、入替対象のニューロン（処理が休止中のニューロン）のインデックスであり、インデックス＝Ｍは、被入替対象のニューロン（処理されているニューロン）のインデックスである。インデックス＝Ｋ，Ｍの選択順序については、制御装置２３によって予め指定されていてもよい。また、制御回路２１は、乱数に基づいて、インデックス＝Ｋ，Ｍを指定してもよい。
【００９６】
インデックス＝Ｋ，Ｍの指定後、制御回路２１は、制御信号ＣＳＫ，ＣＷｉｊ（Ａ，Ｋ），ＣＷｉｊ（Ｋ）をアクティブにする（ステップＳ１６）。制御信号ＣＳＫは、インデックス＝Ｋのニューロンについての演算処理に用いられる制御信号ＣＳｉである。制御信号ＣＷｉｊ（Ａ，Ｋ）は、インデックス＝Ｋのニューロンと処理が継続されるインデックス＝Ａのニューロンとの間の相互作用の大きさを示す重み係数（Ｗｉｊ（Ａ，Ｋ））を読み出し、演算処理部２２に設定するための制御信号ＣＷｉｊである。制御信号ＣＷｉｊ（Ｋ）は、インデックス＝Ｋのニューロンと他の全てのニューロンとの間の相互作用の大きさを示す重み係数（Ｗｉｊ（Ｋ））を読み出し、演算処理部２２に設定するための制御信号ＣＷｉｊである。制御信号ＣＳＫ，ＣＷｉｊ（Ｋ）がアクティブとなることにより、演算処理回路２２ａ１〜２２ａｍのうち、イタレーション動作を休止中の何れかの演算処理回路に、ｘｉ（Ｋ）、ｈＫ、Ｗｉｊ（Ｋ）が設定される。また、制御信号ＣＷｉｊ（Ａ，Ｋ）がアクティブとなることにより、演算処理回路２２ａ１〜２２ａｍのうち、イタレーション動作を継続する演算処理回路に、Ｗｉｊ（Ａ，Ｋ）が設定される。
【００９７】
ｘｉ（Ｋ）は、全ニューロンのビット値の初期値または前回インデックス＝Ｋのニューロンが処理されたときに最後に更新された全ニューロンのビット値に対して、ステップＳ１６の処理の時点で更新されているニューロンのビット値と、ｘＫを含む。制御回路２１は、ステップＳ１６の処理において、記憶部２１ａに記憶されている全ニューロンのビット値を、演算処理回路２２ａ１〜２２ｍのうち、動作中の演算処理回路のレジスタ（たとえば、図５のレジスタ４０）に保持されている値を用いて更新する。そして、制御回路２１は、更新した全ニューロンのビット値と、全ニューロンのビット値の初期値または前回インデックス＝Ｋのニューロンが処理されたときに最後に更新された全ニューロンとの差異に基づいて、ｘｉ（Ｋ）を決定する。ｘｉ（Ｋ）には、図５に示したｘｊａが含まれる。また、ｘＫは、たとえば、図５に示したレジスタ４０に設定される。なお、図５のインデックス＝ｊａなどについてもイタレーション動作を休止中の演算処理回路に設定される。
【００９８】
そして、イタレーション動作を休止中の演算処理回路は、たとえば、前述した図５の更新対象情報選択回路４１にて、制御回路２１により設定されたｘｊａやｊａを選択してｈｉ（ここでは、ｉ＝Ｋ）の更新を行う（ステップＳ１７）。制御回路２１は、ｘｉ（Ｋ）、ｈＫ、Ｗｉｊ（Ｋ）、Ｗｉｊ（Ａ，Ｋ）の設定後、制御信号ＣＳＫ，ＣＷｉｊ（Ａ，Ｋ），ＣＷｉｊ（Ｋ）を非アクティブにする。
【００９９】
その後、制御回路２１は、制御信号ＯＥＭをアクティブにする（ステップＳ１８）。制御信号ＯＥＭは、ステップＳ１５の処理で指定されたインデックス＝Ｍのニューロンについてのローカルフィールドと、演算処理を実行中の演算処理回路から各ニューロンのビット値を読み出すための制御信号である。制御信号ＯＥＭがアクティブとなることにより、ｈＭと、演算処理を実行中の演算処理回路から各ニューロンのビット値が読み出される。制御回路２１は、読み出された各ニューロンのビット値を用いて、記憶部２１ａに記憶されている全ニューロンのビット値を更新し、更新された全ニューロンのビット値（ｘｉ（Ｍ））を、読み出されたｈＭとともに記憶部２１ａに記憶する。
【０１００】
なお、制御信号ＯＥＭは、ｘｉ（Ｍ）とｈＭの記憶部２１ａへの記憶が完了した場合に、非アクティブとなる。
その後、制御回路２１は、制御信号ＣＮＫ，ＥＸＫをアクティブにし、制御信号ＣＮＭ，ＥＸＭを非アクティブにする（ステップＳ１９）。制御信号ＣＮＫは、インデックス＝Ｋのニューロンについての演算処理の実行と休止を制御する制御信号ＣＮｉである。制御信号ＥＸＫは、インデックス＝Ｋのニューロンを更新対象ニューロンとして選択することを有効にするか否かを制御する制御信号ＥＸｉである。制御信号ＣＮＫ，ＥＸＫがアクティブになることにより、インデックス＝Ｋのニューロンについてのイタレーション動作が、演算処理を休止中であった演算処理回路にて開始される。制御信号ＣＮＭは、インデックス＝Ｍのニューロンについての演算処理の実行と休止を制御する制御信号ＣＮｉである。制御信号ＥＸＭは、インデックス＝Ｍのニューロンを更新対象ニューロンとして選択することを有効にするか否かを制御する制御信号ＥＸｉである。制御信号ＣＮＭ，ＥＸＭが非アクティブになることにより、インデックス＝Ｍのニューロンについての演算処理を実行中であった演算処理回路が休止され、インデックス＝Ｍのニューロンについてのイタレーション動作が休止する。
【０１０１】
その後、ステップＳ１３の処理に戻る。
制御回路２１は、ステップＳ１４の処理にて、入替条件が満たされていないと判定した場合、温度パラメータの変更条件が満たされているか否かを判定する（ステップＳ２０）。制御回路２１は、たとえば、イタレーション動作の回数が所定回数に達した場合、温度パラメータの変更条件が満たされていると判定する。
【０１０２】
制御回路２１が温度パラメータの変更条件が満たされていないと判定した場合、ステップＳ１３からの処理が繰り返される。制御回路２１は、温度パラメータの変更条件が満たされていると判定した場合、温度パラメータの変更を行う（ステップＳ２１）。制御回路２１は、たとえば、制御装置２３から供給される温度変更スケジュールにしたがって、温度パラメータの値を小さくする。ステップＳ２１の処理後、ステップＳ１３からの処理が繰り返される。
【０１０３】
制御回路２１は、ステップＳ１３の処理にて、終了条件が満たされていると判定した場合、記憶部２１ａに記憶されている現在の全ニューロンのビット値を、最適化問題の解（計算結果）として出力し（ステップＳ２２）、処理を終える。制御回路２１が出力した計算結果は、たとえば、制御装置２３における表示装置などに表示される。
【０１０４】
以下、処理するニューロンの入れ替え処理についての一例を説明する。
図７は、入れ替え処理時の各ニューロンの動作状態とアクティブにする制御信号との一例の関係を示す図である。
【０１０５】
図７では、イタレーション動作が継続されるインデックス＝Ａのニューロンが“ニューロンＡ”、前述したインデックス＝Ｍのニューロンが“ニューロンＭ”、前述したインデックス＝Ｋのニューロンが“ニューロンＫ”と表記されている。
【０１０６】
動作状態ａでは、制御信号ＣＮＡ，ＣＮＭ，ＥＸＡ，ＥＸＭがアクティブになっており、ニューロンＡ，Ｍについてイタレーション動作が行われ、ニューロンＫについてはイタレーション動作が休止されている。
【０１０７】
動作状態ｂは、図６のステップＳ１６の処理時における動作状態である。ニューロンＡ，Ｍについてのイタレーション動作は継続している。さらに、動作状態ａにおいてアクティブになっている制御信号のほかに、制御信号ＣＷｉｊ（Ｋ），ＣＷｉｊ（Ａ，Ｋ），ＣＳＫがアクティブになっている。このとき、ニューロンＡについてのイタレーション動作を行っている演算処理回路にＷｉｊ（Ａ，Ｋ）が設定され、イタレーション動作を休止中の何れかの演算処理回路に、ｘｉ（Ｋ）、ｈＫ、Ｗｉｊ（Ｋ）が設定される。
【０１０８】
動作状態ｃは、図６のステップＳ１７の処理時における動作状態である。ニューロンＡ，Ｍについてのイタレーション動作は継続している。さらに、動作状態ｃでは、ニューロンＫについて、ローカルフィールド（ｈＫ）の更新が行われる。
【０１０９】
動作状態ｄは、図６のステップＳ１８の処理時における動作状態である。ニューロンＡ，Ｍについてのイタレーション動作は継続している。また、ｈＫの更新は継続されている。ただ、動作状態ｄでは、制御信号ＯＥＭがアクティブになっている。制御信号ＯＥＭがアクティブとなることにより、ｈＭと、ｘｉ（Ｍ）が記憶部２１ａに記憶される。制御信号ＯＥＭは、ｈＭと、ｘｉ（Ｍ）の記憶部２１ａへの記憶が終了すると、非アクティブとなる。
【０１１０】
動作状態ｅは、図６のステップＳ１９の処理時における動作状態である。ニューロンＡについてのイタレーション動作は継続している。一方、制御信号ＣＮＭ，ＥＸＭが非アクティブになり、制御信号ＣＮＫ，ＥＸＫがアクティブになることで、ニューロンＭについてのイタレーション動作は休止され、ニューロンＫについてのイタレーション動作が開始する。
【０１１１】
図８、図９、図１０は、動作状態ａ〜ｅの一例を説明する模式図である。
図８〜図１０の積算部５０，５１，５２，５３，５４は、たとえば、図５に示したｈｉを計算する部分に相当する。図８〜図１０の判定部６０，６１，６２，６３，６４は、たとえば、図５に示したｈｉに基づいてｘｉを出力する部分に相当する。なお、図８〜図１０では、更新ニューロン選択回路２２ｂなどについては図示が省略されている。また、以下では、説明を簡略化するため、全ニューロン数は８、演算処理回路２２ａ１〜２２ａｍの数は５つ（ｍ＝５）としている。
【０１１２】
図８は、動作状態ａの一例を説明する模式図である。
図８に示される動作状態ａでは、図７のニューロンＡまたはニューロンＭに相当するインデックス＝１〜４の４つのニューロンについてのイタレーション動作が行われている。ｈ１は、Ｗ１１〜Ｗ１４とｘ１〜ｘ４とを用いて更新され、ｈ２は、Ｗ２１〜Ｗ２４とｘ１〜ｘ４とを用いて更新され、ｈ３は、Ｗ３１〜Ｗ３４とｘ１〜ｘ４とを用いて更新され、ｈ４は、Ｗ４１〜Ｗ４４とｘ１〜ｘ４とを用いて更新される。
【０１１３】
図９は、動作状態ｂ〜ｄの一例を説明する模式図である。
動作状態ｂでは、図７に示したＷｉｊ（Ａ，Ｋ）として、Ｗ１８，Ｗ２８，Ｗ３８が、インデックス＝１〜３のニューロンについての演算処理を行っている演算処理回路に設定される。また、図７に示したｘｉ（Ｋ）として、ｘｉ（８）が、演算処理を休止中の演算処理回路に設定される。ｘｉ（８）は、全ニューロンのビット値の初期値または前回インデックス＝８のニューロンが処理されたときに最後に更新された全ニューロンのビット値に対して、動作状態ｂの時点で更新されているニューロンのビット値（ｘ１〜ｘ７の何れか）と、ｘ８を含む。さらに、図７に示したＷｉｊ（Ｋ）とｈＫとして、Ｗ８１〜Ｗ８８とｈ８が演算処理を休止中の演算処理回路に設定される。
【０１１４】
動作状態ｃでは、演算処理を休止中の演算処理回路において、設定されたｈ８の更新が行われる。
動作状態ｄでは、図７に示したｘｉ（Ｍ），ｈＭとして、ｘｉ（４），ｈ４が、記憶部２１ａに記憶される。
【０１１５】
図１０は、動作状態ｅの一例を説明する模式図である。
動作状態ｅでは、インデックス＝４のニューロンについてのイタレーション動作が休止され、インデックス＝８のニューロンについてのイタレーション動作が開始する。このとき、ｈ１は、Ｗ１１〜Ｗ１３，Ｗ１８と、ｘ１〜ｘ３，ｘ８を用いて更新され、ｈ２は、Ｗ２１〜Ｗ２３，Ｗ２８と、ｘ１〜ｘ３，ｘ８を用いて更新され、ｈ３は、Ｗ３１〜Ｗ３３，Ｗ３８とｘ１〜ｘ３，ｘ８を用いて更新される。また、ｈ８は、Ｗ８１〜Ｗ８３，Ｗ８８とｘ１〜ｘ３，ｘ８を用いて更新される。
【０１１６】
以上のような、第２の実施の形態の最適化装置２０によれば、第１の実施の形態の最適化装置１０と同様の効果が得られる。
また、演算処理回路２２ａ１〜２２ａｍは、制御回路２１の制御のもと、たとえば、図５に示したような回路を用いて、休止中のニューロンについての処理が開始（または再開）されるときに、記憶部２１ａに記憶していたローカルフィールドを更新する。たとえば、インデックス＝ｉのニューロンのｈｉの初期値は、全ニューロンのビット値の初期値に対して値が更新されたニューロンの情報と、インデックス＝ｉのニューロンと全ニューロンのそれぞれとについての重み係数とに基づいて更新される。または、インデックス＝ｉのニューロンについての前回の演算処理が休止される前に最後に計算されたｈｉは、その演算処理が休止される前に最後に更新された全ニューロンのビット値に対して値が更新されたニューロンの情報と、上記重み係数とに基づいて更新される。
【０１１７】
これにより、あるニューロンについての処理が休止中に更新されたニューロンのビット値を、そのニューロンの処理が開始（または再開）されるときのローカルフィールドに反映させることができる。
【０１１８】
以上、実施の形態に基づき、本発明の最適化装置及び最適化装置の制御方法の一観点について説明してきたが、これらは一例にすぎず、上記の記載に限定されるものではない。
【符号の説明】
【０１１９】
１０  最適化装置
１１ａ１〜１１ａｍ  演算処理回路
１２  制御回路
１２ａ  記憶部
１３  更新ニューロン選択回路
【図１】
2020087009.tif 000005
【図２】
2020087009.tif 000006
【図３】
2020087009.tif 000007
【図４】
2020087009.tif 000008
【図５】
2020087009.tif 000009
【図６】
2020087009.tif 000010
【図７】
2020087009.tif 000011
【図８】
2020087009.tif 000012
【図９】
2020087009.tif 000013
【図１０】
2020087009.tif 000014