(57)【要約】【課題】重み係数を記憶する記憶部の容量を削減する。【解決手段】記憶部１１ｂ１〜１１ｂｎは、複数のニューロンのうちの１つである対象ニューロンと結合する結合先ニューロンを示すｉｄを保持し、値が更新される更新対象ニューロンを示すｉｄｊと一致するｉｄを示す信号を出力する。記憶部１１ｃ１〜１１ｃｎは、対象ニューロンと結合先ニューロンとの間の結合の強さを示す重み係数を保持し、上記信号が示すｉｄに対応した重み係数を出力する。演算部１１ｄ１〜１１ｄｎは、記憶部１１ｃ１〜１１ｃｎが出力する重み係数と、更新対象ニューロンの値（ｘｊ）とを用いて、対象ニューロンの値の更新を確率的に許容し、対象ニューロンの値の更新を許容したか否かを示すｆ１〜ｆｎを出力する。更新制御回路１２は、ｆ１〜ｆｎに基づいて、更新対象ニューロンを決定し、ｘｊを更新するとともに、ｉｄｊを出力する。【選択図】図１
2020194442.tif 000002
【特許請求の範囲】
【請求項１】
最適化問題を変換したイジングモデルの複数のスピンに対応した複数のニューロンのうちの１つである対象ニューロンと結合する結合先ニューロンを示す結合先情報を保持し、値が更新される更新対象ニューロンを示す更新対象情報を受け、前記更新対象情報と一致する前記結合先情報を示す信号を出力する第１の記憶部と、
前記対象ニューロンと前記結合先ニューロンとの間の結合の強さを示す重み係数を保持し、前記第１の記憶部が出力する前記信号が示す前記結合先情報に対応した前記重み係数を出力する第２の記憶部と、
前記第２の記憶部が出力する前記重み係数と、前記更新対象ニューロンの値とを用いて、前記対象ニューロンの値の更新を確率的に許容し、前記対象ニューロンの値の更新を許容したか否かを示す判定結果を出力する演算部と、
をそれぞれが有し、それぞれが異なる前記対象ニューロンについての前記判定結果を出力する複数のニューロン回路と、
前記複数のニューロン回路から出力される複数の前記判定結果に基づいて、前記更新対象ニューロンを決定し、前記更新対象ニューロンの値を更新するとともに、前記更新対象情報を出力する更新制御回路と、
を有する最適化装置。
【請求項２】
前記第１の記憶部は、前記更新対象情報と一致する前記結合先情報を保持しているか否かを示す一致判定情報を出力し、
前記更新制御回路は、前記複数のニューロン回路のうち、前記更新対象情報と一致する前記結合先情報を保持していないことを示す前記一致判定情報を出力したニューロン回路が、前記対象ニューロンの値の更新を許容したことを示す前記判定結果を出力した場合、前記対象ニューロンを前記更新対象ニューロンの１つとして決定する、
請求項１に記載の最適化装置。
【請求項３】
前記第１の記憶部は連想メモリである、請求項１または２に記載の最適化装置。
【請求項４】
複数のニューロン回路のそれぞれが有する第１の記憶部が、最適化問題を変換したイジングモデルの複数のスピンに対応した複数のニューロンのうちの１つであり、前記複数のニューロン回路のそれぞれにおいて異なる対象ニューロンと結合する結合先ニューロンを示す結合先情報を保持し、値が更新される更新対象ニューロンを示す更新対象情報を受け、前記更新対象情報と一致する前記結合先情報を示す信号を出力し、
前記複数のニューロン回路のそれぞれが有する第２の記憶部が、前記対象ニューロンと前記結合先ニューロンとの間の結合の強さを示す重み係数を保持し、前記第１の記憶部が出力する前記信号が示す前記結合先情報に対応した前記重み係数を出力し、
前記複数のニューロン回路のそれぞれが有する演算部が、前記第２の記憶部が出力する前記重み係数と、前記更新対象ニューロンの値とを用いて、前記対象ニューロンの値の更新を確率的に許容し、前記対象ニューロンの値の更新を許容したか否かを示す判定結果を出力し、
更新制御回路が、前記複数のニューロン回路のそれぞれの前記演算部から出力される複数の前記判定結果に基づいて、前記更新対象ニューロンを決定し、前記更新対象ニューロンの値を更新するとともに、前記更新対象情報を出力する、
最適化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適化装置及び最適化方法に関する。
【背景技術】
【０００２】
ノイマン型コンピュータが不得意とする多変数の組合せ最適化問題を解く方法として、イジング型のエネルギー関数を用いた最適化装置（イジングマシンまたはボルツマンマシンと呼ばれる場合もある）がある。最適化装置は、計算対象の問題を、磁性体のスピンの振る舞いを表すモデルであるイジングモデルに置き換えて計算する。
【０００３】
最適化装置は、たとえば、ニューラルネットワークを用いてモデル化することもできる。その場合、イジングモデルに含まれる複数のスピンに対応した複数の状態変数のそれぞれが、他の状態変数の値と、他の状態変数と自身の状態変数との相互作用の大きさを示す重み係数とに応じて０または１を出力するニューロンとして機能する。最適化装置は、たとえば、シミュレーテッド・アニーリングなどの確率的探索法により、上記のようなエネルギー関数の値（以下エネルギーという）の最小値が得られる各状態変数の値の組合せを、解として求める。
【０００４】
従来、デジタル回路を用いてシミュレーテッド・アニーリングを行うことでエネルギーが最小となる各状態変数の値の組合せを計算する最適化装置があった（たとえば、特許文献１，２，３参照）。
【０００５】
また、ニューラルネットワークを用いた技術において、学習による発火状況に応じてニューロンを追加または削除する技術があった（たとえば、特許文献４参照）。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１７−２１９９５２号公報
【特許文献２】特開２０１８−１０４７４号公報
【特許文献３】国際公開第２０１５／１３２８８３号
【特許文献４】特開２００１−３３１８３９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、問題の規模の増大に応じて状態変数の数が増えると重み係数の数も増加する。特に、問題をイジングモデルに置き換える際の柔軟性に優れた、全状態変数間の相互作用を考慮可能な全結合型の最適化装置（たとえば、特許文献１，２）では、状態変数の数の増加とともに重み係数の数が急激に増加する。
【０００８】
このため、たとえば、１チップの半導体集積回路で最適化装置を実現する場合、重み係数を記憶する記憶部の容量が増加してしまう。最適化装置の外部のメモリに重み係数を記憶しておく方法や、複数チップを用いて最適化装置を構成する方法があるが、メモリからの重み係数の読み出しやチップ間の通信にかかる時間により計算速度が低下してしまう問題がある。
【０００９】
１つの側面では、重み係数を記憶する記憶部の容量を削減可能な最適化装置及び最適化方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
１つの実施態様では、最適化問題を変換したイジングモデルの複数のスピンに対応した複数のニューロンのうちの１つである対象ニューロンと結合する結合先ニューロンを示す結合先情報を保持し、値が更新される更新対象ニューロンを示す更新対象情報を受け、前記更新対象情報と一致する前記結合先情報を示す信号を出力する第１の記憶部と、前記対象ニューロンと前記結合先ニューロンとの間の結合の強さを示す重み係数を保持し、前記第１の記憶部が出力する前記信号が示す前記結合先情報に対応した前記重み係数を出力する第２の記憶部と、前記第２の記憶部が出力する前記重み係数と、前記更新対象ニューロンの値とを用いて、前記対象ニューロンの値の更新を確率的に許容し、前記対象ニューロンの値の更新を許容したか否かを示す判定結果を出力する演算部と、をそれぞれが有し、それぞれが異なる前記対象ニューロンについての前記判定結果を出力する複数のニューロン回路と、前記複数のニューロン回路から出力される複数の前記判定結果に基づいて、前記更新対象ニューロンを決定し、前記更新対象ニューロンの値を更新するとともに、前記更新対象情報を出力する更新制御回路と、を有する最適化装置が提供される。
【００１１】
また、１つの実施態様では最適化方法が提供される。
【発明の効果】
【００１２】
１つの側面では、重み係数を記憶する記憶部の容量を削減可能となる。
【図面の簡単な説明】
【００１３】
【図１】第１の実施の形態の最適化装置の一例を示す図である。
【図２】第２の実施の形態の最適化装置の一例を示す図である。
【図３】ニューロン回路の一例を示す図である。
【図４】ＣＡＭの一例を示す図である。
【図５】第２の実施の形態の最適化装置の一例の動作の流れを示すフローチャートである。
【図６】第３の実施の形態の最適化装置の一例を示す図である。
【図７】第３の実施の形態の最適化装置におけるＣＡＭの一例を示す図である。
【図８】第３の実施の形態の最適化装置における更新制御回路の一例を示す図である。
【図９】第３の実施の形態の最適化装置の一例の動作の流れを示すフローチャートである。
【発明を実施するための形態】
【００１４】
以下、発明を実施するための形態を、図面を参照しつつ説明する。
以下に示す最適化装置は、最適化問題を変換したイジングモデルの複数のスピンに対応した複数のニューロンのそれぞれの値（以下、ビット値という）の組合せのうち、エネルギーが最小となるときの各ニューロンのビット値の組合せを探索するものである。
【００１５】
イジング型のエネルギー関数Ｅ（ｘ）は、たとえば、以下の式（１）で定義される。
【００１６】
【数１】
2020194442.tif 000003
【００１７】
右辺の１項目は、全ニューロンの全組合せについて、漏れと重複なく、２つのニューロンのビット値（０または１）と重み係数との積を積算したものである。ｘｉは、識別情報（以下ｉｄと表記する）がｉのニューロンのビット値を表す変数（状態変数とも呼ばれる）、ｘｊは、ｉｄ＝ｊのニューロンのビット値を表す変数である。Ｗｉｊは、ｉｄ＝ｉ，ｊのニューロンの相互作用の大きさ（結合の強さ）を示す重み係数である。なお、Ｗｉｉ＝０である。また、Ｗｉｊ＝Ｗｊｉであることが多い（つまり、重み係数による係数行列は対称行列である場合が多い）。またＷｉｊは、所定のビット幅（たとえば、１６ビット、３２ビット、６４ビット、１２８ビットなど）をもつ。
【００１８】
右辺の２項目は、全ニューロンのそれぞれのバイアス係数とニューロンのビット値との積の総和を求めたものである。ｂｉは、ｉｄ＝ｉのニューロンのバイアス係数を示している。
【００１９】
また、ｘｉが変化して１−ｘｉとなると、ｘｉの増加分は、Δｘｉ＝（１−ｘｉ）−ｘｉ＝１−２ｘｉと表せる。スピン反転（ニューロンのビット値の変化）に伴うエネルギー変化（ΔＥｉ）は、以下の式（２）で表される。
【００２０】
【数２】
2020194442.tif 000004
【００２１】
式（２）において、ｘｉが１から０に変化するとき、Δｘｉは−１となり、ｘｉが０から１に変化するとき、Δｘｉは１となる。なお、ｈｉはローカルフィールド（局所場）と呼ばれ、Δｘｉに応じてｈｉに符号（＋１または−１）を乗じたものがΔＥｉである。ｈｉが０より小さければ、ｘｉを１から０へ更新することで、全エネルギーが減少し、ｈｉが０より大きければ、ｘｉを０から１へ更新することで、全エネルギーが減少する。
【００２２】
また、ｘｊが０から１に変化したときのｈｉの変化分（Δｈｉ）は、＋Ｗｉｊ、ｘｊが１から０に変化したときのΔｈｉは、−Ｗｉｊと表せる。したがって、状態遷移に伴って更新されたニューロンのビット値が１か０かによって、Ｗｉｊを元のｈｉに加算または減算することで、ｈｉの更新が可能である。
【００２３】
（第１の実施の形態）
図１は、第１の実施の形態の最適化装置の一例を示す図である。
第１の実施の形態の最適化装置１０は、ニューロン回路１１ａ１，１１ａ２，…，１１ａｎ、更新制御回路１２を有する。図１の例では、ニューロン回路１１ａ１〜１１ａｎには、ｎ個のニューロンの何れかを示すｉｄが割当てられている。図１の例では、ニューロン回路１１ａ１にはｉｄ＝１が割当てられ、ニューロン回路１１ａ２にはｉｄ＝２が割当てられ、ニューロン回路１１ａｎにはｉｄ＝ｎが割当てられている。
【００２４】
ニューロン回路１１ａ１は、記憶部１１ｂ１，１１ｃ１、演算部１１ｄ１を有する。
記憶部１１ｂ１は、複数の（ｎ個の）ニューロンのうちの１つである対象ニューロンと結合する結合先ニューロンを示す結合先情報を保持する。また、記憶部１１ｂ１は、値が更新される更新対象ニューロンを示す更新対象情報を受け、その更新対象情報と一致する結合先情報を示す信号を出力する。
【００２５】
図１には、記憶部１１ｂ１が保持している結合先情報の例が示されている。ニューロン回路１１ａ１における対象ニューロンは、ｉｄ＝１のニューロンであり、結合先情報はｉｄ＝１のニューロンと結合するニューロンを示す。図１の例では、ｉｄ＝１のニューロンと結合するニューロンのｉｄ（２，５，…，ｎ−１）が結合先情報として記憶部１１ｂ１に保持されている。記憶部１１ｂ１は、更新対象情報（ｉｄｊ）として、ｉｄｊ＝２を受けた場合、ｉｄｊ＝２と一致する結合先情報（ｉｄ＝２）を保持しているため、ｉｄ＝２を示す信号を出力する。記憶部１１ｂ１は、ｉｄｊ＝ｎを受けた場合、ｉｄｊ＝ｎと一致する結合先情報を保持していないため、結合先情報を示す信号を出力しない。
【００２６】
記憶部１１ｂ１は、たとえば、連想メモリ（ＣＡＭ：Content-Addressable Memory）などによって実現できる。記憶部１１ｂ１は、ＲＡＭ（Random Access Memory）や比較器などを用いて実現されるようにしてもよい。
【００２７】
記憶部１１ｃ１は、対象ニューロンと結合先ニューロンとの間の結合の強さを示す重み係数を保持し、記憶部１１ｂ１が出力する信号が示す結合先情報に対応した重み係数を出力する。
【００２８】
図１には、記憶部１１ｃ１が保持している重み係数の例が示されている。前述のようにｉｄ＝１のニューロンがｉｄ＝２，５，…，ｎ−１とニューロンと結合している場合、記憶部１１ｃ１は、重み係数としてＷ１２，Ｗ１５，…，Ｗ１，ｎ−１を保持する。記憶部１１ｃ１は、記憶部１１ｂ１がｉｄ＝２を示す信号を出力した場合、Ｗ１２を出力する。
【００２９】
記憶部１１ｃ１は、たとえば、ＲＡＭやレジスタなどによって実現できる。
結合先情報や重み係数は、たとえば、図示しない制御装置が、最適化問題を式（１）のようなエネルギー関数で表されるイジングモデルに変換することで得られる。そして、結合先情報や重み係数は、たとえば、最適化装置１０の初期設定処理時に、制御装置から最適化装置１０に供給され、記憶部１１ｂ１，１１ｃ１に書き込まれる。
【００３０】
演算部１１ｄ１は、記憶部１１ｃ１が出力する重み係数と、更新対象ニューロンのビット値とを用いて、対象ニューロンの値の更新を確率的に許容し、対象ニューロンの値の更新を許容したか否かを示す判定結果（ｆ１）を出力する。
【００３１】
たとえば、演算部１１ｄ１は、記憶部１１ｃ１が出力する重み係数と、更新対象ニューロンのビット値とを用いて、前述のローカルフィールド（ｈ１）を更新するとともに、式（２）に基づいて、エネルギー変化（ΔＥ１）を更新する。そして、演算部１１ｄ１は、温度パラメータと乱数とに基づいて決定される熱ノイズと、ΔＥ１とに基づいて、ｉｄ＝１のニューロンのビット値の更新を許容するか否かを判定する。温度パラメータは、たとえば、図示しない制御回路または更新制御回路１２から入力される。
【００３２】
前述のようにｉｄ＝ｉのニューロンについてのｈｉが０より小さくｘｉが１の場合、ｘｉを１から０へ更新することで、全エネルギーが減少する。また、ｈｉが０より大きくｘｉが０の場合、ｘｉを０から１へ更新することで、全エネルギーが減少する。これらに対して、ｈｉが０より小さくｘｉが０の場合、ｘｉを０から１へ更新することで、全エネルギーが増加する。また、ｈｉが０より大きくｘｉが１の場合、ｘｉを１から０へ更新することで、全エネルギーが増加する。
【００３３】
イジングモデルの状態が基底状態（最適解）ではない、局所解にトラップされることを防止するために、演算部１１ｄ１は、熱ノイズを用いて、エネルギーが増加する状態遷移も所定の確率で発生させる。熱ノイズは、温度パラメータが大きいほどノイズ幅が大きくなる。シミュレーテッド・アニーリングが行われる場合、温度パラメータは徐々に小さくなるように制御される。
【００３４】
演算部１１ｄ１は、ΔＥ１を計算する論理回路、ＬＦＳＲ（Linear Feedback Shift Registers）などの乱数生成器を用いて熱ノイズを生成する回路、比較器などにより実現される。
【００３５】
他のニューロン回路１１ａ２〜１１ａｎについても、ニューロン回路１１ａ１と同じ要素を有しており、それぞれ異なる対象ニューロンについての判定結果を出力する。たとえば、ｉｄ＝２が割当てられているニューロン回路１１ａ２は、記憶部１１ｂ２，１１ｃ２、演算部１１ｄ２を有し、ｉｄ＝２のニューロンのビット値の更新を許容するか否かを示す判定結果（ｆ２）を出力する。ｉｄ＝ｎが割当てられているニューロン回路１１ａｎは、記憶部１１ｂｎ，１１ｃｎ、演算部１１ｄｎを有し、ｉｄ＝ｎのニューロンのビット値の更新を許容するか否かを示す判定結果（ｆｎ）を出力する。
【００３６】
更新制御回路１２は、ニューロン回路１１ａ１〜１１ａｎが出力する判定結果（ｆ１〜ｆｎ）に基づいて、更新対象ニューロンを１つ決定し、更新対象ニューロンのビット値（ｘｊ）を更新するとともに、更新対象情報（ｉｄｊ）を出力する。
【００３７】
更新制御回路１２は、たとえば、更新が許容されたニューロンが複数ある場合、乱数に基づいて、１つを更新対象ニューロンとして選択する選択回路や、各ニューロンのビット値を保持するレジスタなどを用いて実現される。乱数に基づいて、１つを更新対象ニューロンとして選択する選択回路の例については、たとえば、特開２０１８−０４１３５１号公報の第５〜第７図に記載されている。
【００３８】
以下、第１の実施の形態の最適化装置１０の動作例を説明する。
まず、初期設定処理において、たとえば、図示しない制御装置から供給される結合先情報や重み係数が記憶部１１ｂ１〜１１ｂｎ，１１ｃ１〜１１ｃｎに書き込まれる。また、制御装置によって、各ニューロンについてのローカルフィールドの初期値が演算部１１ｄ１〜１１ｄｎに設定され、各ニューロンのビット値の初期値が更新制御回路１２の図示しないレジスタに設定される。また、シミュレーテッド・アニーリングが行われる場合、制御装置によって、アニーリング条件（温度パラメータの変化スケジュールや計算の反復回数など）の設定が行われる。
【００３９】
その後、演算部１１ｄ１〜１１ｄｎは、初期設定処理によって得られた各ニューロンのビット値やローカルフィールドの初期値に基づいてエネルギー変化を計算する。そして、演算部１１ｄ１〜１１ｄｎは、各ニューロンについて、計算したエネルギー変化と熱ノイズとに基づいて更新を許容するか否かを示す判定結果（ｆ１〜ｆｎ）を出力する。以下では、ｆｉ＝１の場合、ｉｄ＝ｉのニューロンの更新が許容されたものとする。
【００４０】
更新制御回路１２は、ニューロン回路１１ａ１〜１１ａｎが出力するｆ１〜ｆｎに基づいて、更新対象ニューロンを決定する。更新が許容されたニューロンが複数ある場合、更新制御回路１２は、たとえば、乱数に基づいて、１つを更新対象ニューロンとして決定する。そして、更新制御回路１２は、更新対象ニューロンのビット値（ｘｊ）を更新するとともに、更新対象情報（ｉｄｊ）を出力する。更新が許容されたニューロンが１つもない場合、ビット値の更新は行われない。
【００４１】
なお、演算部１１ｄ１〜１１ｄｎは、解が局所解に拘束されることを抑制するため、オフセット値をエネルギー変化に加えるとともに、ビット値の更新が生じない状況が発生するたびにそのオフセット値を増やし、更新を促進するようにしてもよい。
【００４２】
更新制御回路１２が、ｉｄｊを出力した場合、記憶部１１ｂ１〜１１ｂｎは、ｉｄｊと一致する結合先情報がある場合、その一致する結合先情報を示す信号を出力する。たとえば前述のようにｉｄｊ＝２で、記憶部１１ｂ１が、結合先情報としてｉｄ＝２を保持している場合、記憶部１１ｂ１は、ｉｄ＝２を示す信号を出力する。
【００４３】
そして、記憶部１１ｃ１〜１１ｃｎは、記憶部１１ｂ１〜１１ｂｎが出力する信号が示す結合先情報に対応した重み係数を出力する。
演算部１１ｄ１〜１１ｄｎは、記憶部１１ｃ１〜１１ｃｎが出力した重み係数と、ｘｊとに基づいてローカルフィールドを更新し、エネルギー変化についても更新する。その後、更新されたエネルギー変化と熱ノイズとに基づいたｆ１〜ｆｎの出力や更新対象ニューロンの決定、ｘｊの更新が繰り返される。
【００４４】
シミュレーテッド・アニーリングが行われる場合、熱ノイズを徐々に小さくしていきながら、上記の処理が所定回数繰り返される。そして、上記の処理が所定回数繰り返された後に得られた各ニューロンのビット値が最適化問題の解として出力される。なお、更新制御回路１２は、更新対象ニューロンが更新されることによるエネルギー変化を用いてエネルギーを更新するとともに、そのエネルギーがこれまでの最小値である場合、その最小値と最小値が得られたときの各ニューロンのビット値を保持してもよい。その場合、上記の処理の反復回数が所定回数に達した時点で保持されているエネルギーが最小値のときの各ニューロンのビット値が、解として出力されるようにしてもよい。
【００４５】
以上のような、第１の実施の形態の最適化装置１０では、記憶部１１ｃ１〜１１ｃｎには、結合のないニューロン間の重み係数については保持されていない。たとえば、ｉｄ＝１のニューロンとｉｄ＝ｎのニューロンが結合していない場合、重み係数（Ｗ１ｎ）は０である。この場合、式（１）において、ｉ＝１、ｊ＝ｎとすると、ｘ１，ｘｎの値によらず、Ｗ１ｎｘ１ｘｎ＝０であるので、Ｗ１ｎはエネルギーに影響を与えない。このため、記憶部１１ｃ１は、Ｗ１ｎを保持しなくてもよい。
【００４６】
このような重み係数を保持しないようにすることで、記憶部１１ｃ１〜１１ｃｎの容量を削減することができる。これにより、たとえば、１チップの最適化装置１０で、より大規模な最適化問題の計算が可能になる。
【００４７】
なお、各ニューロンの結合先は問題によって変わるが、問題に応じて記憶部１１ｂ１〜１１ｂｎ，１１ｃ１〜１１ｃｎの保持内容を変更することで、様々な結合状態に対応することができる。
【００４８】
（第２の実施の形態）
図２は、第２の実施の形態の最適化装置の一例を示す図である。
第２の実施の形態の最適化装置２０は、ニューロン回路２１ａ１，２１ａ２，…，２１ａｎ、更新制御回路２２、制御回路２３を有する。また、最適化装置２０は、制御装置２５と接続されている。
【００４９】
ニューロン回路２１ａ１〜２１ａｎは、図１に示したニューロン回路１１ａ１〜１１ａｎと同様の機能を行う。ニューロン回路２１ａ１〜２１ａｎの回路例については後述する。
【００５０】
更新制御回路２２は、図１に示した更新制御回路１２と同様の機能を行う。更新制御回路２２は、たとえば、各ニューロンのビット値を保持する保持部２２ａを有する。保持部２２ａは、たとえば、レジスタやＲＡＭなどによって実現できる。
【００５１】
制御回路２３は、制御装置２５から供給される情報に基づいて、最適化装置２０の初期設定処理などを行う。また、制御回路２３は、シミュレーテッド・アニーリングを行う場合、更新対象ニューロンを決定する処理がアニーリング条件に基づいた回数繰り返されるごとに、たとえば、温度パラメータの値を小さくしていく。
【００５２】
さらに、制御回路２３は、更新対象ニューロンを決定する処理が所定回数、繰り返された後、保持部２２ａに保持されている各ニューロンのビット値を取得し、最適化問題に対する解として制御装置２５に送信する。
【００５３】
なお、制御回路２３は、保持部２２ａが、エネルギーの最小値や最小値が得られたときの各ニューロンのビット値を保持している場合、更新対象ニューロンを決定する処理が所定回数、繰り返されたのちにそれらの情報を取得して、制御装置２５に送信してもよい。
【００５４】
制御回路２３は、たとえば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの特定用途の電子回路にて実現できる。なお、制御回路２３は、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）などのプロセッサであってもよい。その場合、プロセッサは、図示しないメモリに記憶されたプログラムを実行することで、上記の処理を行う。
【００５５】
また、制御回路２３の一部または全ての機能を行う要素が、更新制御回路２２または制御装置２５に含まれていてもよい。
制御装置２５は、ユーザによって入力された最適化問題の情報に基づいて、最適化問題をイジングモデルに変換する（式（１）のエネルギー関数に定式化する）。変換されたイジングモデルの情報は、重み係数とバイアス係数を含む。制御装置２５は、重み係数に基づいて、各ニューロンについての結合先のニューロンのｉｄを、結合先情報として最適化装置２０に送信する。また、制御装置２５は、ローカルフィールドの初期値（たとえば、バイアス係数）や、値が０ではない重み係数、アニーリング条件などについても最適化装置２０に送信する。さらに、制御装置２５は、最適化装置２０から解（各ニューロンのビット値）を受信した場合、解を図示しない表示装置に表示させてもよい。
【００５６】
制御装置２５は、たとえば、ＰＣ（Personal Computer）などのコンピュータであってもよいし、ＣＰＵやＤＳＰなどのプロセッサであってもよい。
（ニューロン回路２１ａ１〜２１ａｎの一例）
図３は、ニューロン回路の一例を示す図である。図３では、ニューロン回路２１ａ１の例を示しているが、他のニューロン回路２１ａ２〜２１ａｎについても同様の回路により実現される。
【００５７】
ニューロン回路２１ａ１は、ＣＡＭ３０、ＲＡＭ３１、演算部３２を有する。
ＣＡＭ３０は、ｉｄ＝１のニューロンと結合する結合先ニューロンを示すｉｄを保持する。また、ＣＡＭ３０は、値が更新される更新対象ニューロンを示すｉｄｊを受け、ｉｄｊと一致するｉｄを保持している場合、そのｉｄを示す信号を出力する。ＣＡＭ３０の例については後述する（図４参照）。
【００５８】
ＲＡＭ３１は、ｉｄ＝１のニューロンと結合先ニューロンとの間の結合の強さを示す重み係数を保持し、ＣＡＭ３０が出力する信号が示すｉｄに対応した重み係数を出力する。
演算部３２は、ΔＥ計算部３２ａ、状態遷移判定部３２ｂを有する。
【００５９】
ΔＥ計算部３２ａは、選択回路３２ａ１、乗算器３２ａ２、加算器３２ａ３、レジスタ３２ａ４、乗算器３２ａ５、選択回路３２ａ６を有する。
選択回路３２ａ１は、更新対象ニューロン（ｉｄ＝ｉｄｊのニューロン）のビット値の変化分の演算を実現するものである。更新対象ニューロンのビット値（ｘｊ）が、１から０に変化するとき、変化分（Δｘｊ）は−１となり、ｘｊが０から１に変化するとき、Δｘｊは１となる。選択回路３２ａ１は、更新制御回路２２から供給されるｘｊ（更新後の値）が０のときには、−１を選択して出力し、ｘｊが１のときには、１を選択して出力する。
【００６０】
乗算器３２ａ２は、ＲＡＭ３１が出力する重み係数と、選択回路３２ａ１が出力する値との積を出力する。図３の例では、乗算器３２ａ２には、重み係数Ｗ１ｊが入力されている。乗算器３２ａ２の出力は、ｘｊが変化したことによるローカルフィールド（ｈ１）の変化分（Δｈ１）を表す。
【００６１】
加算器３２ａ３は、乗算器３２ａ２が出力する値と、レジスタ３２ａ４に格納されている値とを加算して出力する。
レジスタ３２ａ４は、図示しないクロック信号に同期して、加算器３２ａ３が出力する値（ｈ１）を取り込む。レジスタ３２ａ４は、たとえば、フリップフロップである。なお、レジスタ３２ａ４に格納されるｈ１の初期値は、全ニューロンのビット値の初期値を０とした場合、バイアス係数（ｂ１）である。
【００６２】
乗算器３２ａ５は、レジスタ３２ａ４が出力するｈ１と選択回路３２ａ６が出力する値との積を出力する。この積が、式（２）において、ｉｄ＝１のニューロンのビット値が変化することによるエネルギー変化（ΔＥ１）である。
【００６３】
選択回路３２ａ６は、式（２）の−Δｘｉの演算を実現するものである。選択回路３２ａ６は、更新制御回路２２から供給されるｉｄ＝１のニューロンのビット値であるｘ１が０のときは−１を出力し、ｘ１が１のときは１を出力する。
【００６４】
状態遷移判定部３２ｂは、符号反転部３２ｂ１、オフセット加算部３２ｂ２、乱数発生回路３２ｂ３、選択法則適用部３２ｂ４、乗算器３２ｂ５、比較回路３２ｂ６を有する。
符号反転部３２ｂ１は、ΔＥ１に−１を掛けて符号を反転させる。
【００６５】
オフセット加算部３２ｂ２は、符号反転部３２ｂ１の出力値（−ΔＥ１）に、オフセット値を加える。オフセット加算部３２ｂ２は、更新制御回路２２から更新が許容されるニューロンがないことを示す信号（ｆｊ＝０）を受けたとき、オフセット値を増加していく。一方、オフセット加算部３２ｂ２は、更新制御回路２２から更新が許容されるニューロンがあることを示す信号（ｆｊ＝１）を受けたとき、オフセット値を０にする。オフセット値が大きくなるとニューロンのビット値の更新が許容されやすくなり、現在の状態（各ニューロンのビット値の組合せ）が局所解にある場合、その局所解からの脱出が促進される。
【００６６】
乱数発生回路３２ｂ３は、０以上、１以下の一様乱数ｒを発生する。
選択法則適用部３２ｂ４は、シミュレーテッド・アニーリングを行うための選択法則（メトロポリス法またはギブス法）に基づいた値を出力する。
【００６７】
シミュレーテッド・アニーリングが行われる場合、あるエネルギー変化を引き起こす状態遷移の許容確率Ａ（ΔＥ，Ｔ）を以下の式（３）、（４）のように決めれば、時刻（反復回数）無限大の極限で状態が最適解に到達することが証明されている。
【００６８】
【数３】
2020194442.tif 000005
【００６９】
【数４】
2020194442.tif 000006
【００７０】
式（３）、（４）においてＴは、前述の温度パラメータである。
式（３）、（４）で表される許容確率Ａ（ΔＥ，Ｔ）を用いた場合、十分な反復後に定常状態に達したとすると、各状態の占有確率は熱力学における熱平衡状態に対するボルツマン分布にしたがう。そして、高い温度から徐々に下げていくとエネルギーの低い状態の占有確率が増加するため、十分温度が下がるとエネルギーの低い状態が得られるはずである。この様子が材料を焼き鈍したときの状態変化とよく似ているため、この方法はシミュレーテッド・アニーリングと呼ばれるのである。このとき、エネルギーが上がる状態遷移が確率的に起こることは、物理学における熱励起に相当する。
【００７１】
許容確率Ａ（ΔＥ，Ｔ）でエネルギー変化を引き起こす状態遷移を許容することを示す判定結果（＝１）を出力する回路は、式（３）、（４）のｆ（−ΔＥ／Ｔ）と、一様乱数ｒとの比較結果に基づいた値を出力する比較器によって実現できる。
【００７２】
ただ、次のような変形を行っても同じ機能が実現できる。２つの数に同じ単調増加関数を作用させても大小関係は変化しない。したがって比較器の２つの入力に同じ単調増加関数を作用させても比較器の出力は変わらない。たとえば、ｆ（−ΔＥ／Ｔ）に作用させる単調増加関数としてｆ（−ΔＥ／Ｔ）の逆関数ｆ−１（−ΔＥ／Ｔ）、一様乱数（ｒ）に作用させる単調増加関数としてｆ−１（−ΔＥ／Ｔ）の−ΔＥ／Ｔをｒとしたｆ−１（ｒ）を用いることができる。その場合、上記の比較器と同様の機能を有する回路は、−ΔＥ／Ｔがｆ−１（ｒ）より大きいとき１を出力する回路でよいことがわかる。さらにＴが正であることから、その回路は、−ΔＥがＴ・ｆ−１（ｒ）より大きいとき１を出力する回路でよい。
【００７３】
選択法則適用部３２ｂ４は、入力されるｒを上記のｆ−１（ｒ）の値に変換する変換テーブルを用いて、ｆ−１（ｒ）の値を出力する。メトロポリス法が適用される場合、ｆ−１（ｒ）は、ｌｏｇ（ｒ）である。変換テーブルは、たとえば、ＲＡＭ、フラッシュメモリなどのメモリに記憶されている。
【００７４】
乗算器３２ｂ５は、制御回路２３から供給されるＴと、ｆ−１（ｒ）との積（Ｔ・ｆ−１（ｒ））を出力する。Ｔ・ｆ−１（ｒ）は、前述の熱ノイズ（熱励起エネルギー）に相当する。
【００７５】
比較回路３２ｂ６は、オフセット加算部３２ｂ２による加算結果と、Ｔ・ｆ−１（ｒ）とを比較する。そして、比較回路３２ｂ６は、加算結果が、Ｔ・ｆ−１（ｒ）より大きい場合、ｉｄ＝１のニューロンの更新を許容することを示す判定結果（ｆ１＝１）を出力し、Ｔ・ｆ−１（ｒ）より小さい場合、更新を許容しないことを示す判定結果（ｆ１＝０）を出力する。
【００７６】
（ＣＡＭ３０の一例）
図４は、ＣＡＭの一例を示す図である。
ＣＡＭ３０は、入力レジスタ３０ａ、一致判定回路３０ｂ１，３０ｂ２，３０ｂ３，…，３０ｂｍ、エンコーダ３０ｃを有する。
【００７７】
入力レジスタ３０ａは、更新対象ニューロンを示すｉｄｊを保持する。なお、図４の例では、全ニューロンの数であるｎが１０２４であるものとしている。その場合、ｉｄやｉｄｊのビット数は、図４に示すように１０ビットとなる。また、各ニューロンの結合数の最大値が、たとえば、３２の場合、一致判定回路３０ｂ１〜３０ｂｍは３２個、設けられる。
【００７８】
一致判定回路３０ｂ１〜３０ｂｍのそれぞれは、ＣＡＭ３０が含まれるニューロン回路２１ａ１に割当てられたｉｄ＝１のニューロンと結合するニューロンを示すｉｄを保持するレジスタを含む。さらに、一致判定回路３０ｂ１〜３０ｂｍのそれぞれは、保持しているｉｄと、入力レジスタ３０ａに保持されているｉｄｊとが一致する場合に１を出力し、不一致の場合に０を出力する。
【００７９】
エンコーダ３０ｃは、一致判定回路３０ｂ１〜３０ｂｍが出力する値をエンコードし、エンコード結果を出力する。
たとえば、図４の例では、一致判定回路３０ｂ２のレジスタに保持されているｉｄが、ｉｄｊと一致するため、一致判定回路３０ｂ２は１を出力している。この場合、エンコーダ３０ｃは、たとえば、“０１”を出力する。
【００８０】
ＣＡＭ３０が上記のようなエンコーダ３０ｃを有する場合、ＲＡＭ３１はデコーダ３１ａを有することになる。デコーダ３１ａは、エンコーダ３０ｃが出力するエンコード結果が示すｉｄに対応した重み係数が保持されている記憶領域を指定する信号を出力する。図４の例では、ＲＡＭ３１は、８ビットの重み係数を保持する記憶領域３１ｂ１，３１ｂ２，３１ｂ３，…，３１ｂｍを有する。
【００８１】
デコーダ３１ａによって、たとえば、記憶領域３１ｂ２を指定する信号が出力された場合、記憶領域３１ｂ２に保持されている重み係数（Ｗ１ｊ＝００１０００１１）が読み出される。
【００８２】
なお、ＣＡＭ３０は、エンコーダ３０ｃを含まなくてもよい。その場合、ＲＡＭ３１は、デコーダ３１ａを含まなくてもよい。また、その場合、ＲＡＭ３１は、一致判定回路３０ｂ１〜３０ｂｍが出力する値によって、記憶領域３１ｂ１〜３１ｂｍの何れかを指定して重み係数の読み出しを行う。
【００８３】
（第２の実施の形態の最適化装置２０の動作例（最適化方法の例））
図５は、第２の実施の形態の最適化装置の一例の動作の流れを示すフローチャートである。
【００８４】
最適化装置２０の動作が開始すると（たとえば電源投入時）、まず初期設定処理が行われる（ステップＳ１０）。初期設定処理では、制御回路２３は、たとえば、ＣＡＭ３０やＲＡＭ３１の保持内容、保持部２２ａの保持内容、レジスタ３２ａ４の保持内容などを全て、一旦、０に初期化する。さらに、制御回路２３は、制御装置２５から、各ニューロンの結合先ニューロンのｉｄと、値が０ではない重み係数とを受信し、対応するニューロン回路のＣＡＭ３０やＲＡＭ３１に書き込む。また、制御回路２３は、制御装置２５からローカルフィールドの初期値（たとえば、バイアス係数）を受信し、対応するニューロン回路のレジスタ３２ａ４に書き込む。また、制御回路２３は、アニーリング条件についても制御装置２５から受信する。
【００８５】
その後、制御回路２３は、反復回数を示す変数（ｔ）を０に設定する（ステップＳ１１）。
ニューロン回路２１ａ１〜２１ａｎのそれぞれは、初回は、初期設定処理によって得られた各ニューロンのビット値やローカルフィールドの初期値などに基づいてエネルギー変化や熱ノイズを計算する。そして、ニューロン回路２１ａ１〜２１ａｎのそれぞれは、エネルギー変化と熱ノイズに基づいて各ニューロンの更新可否（更新を許容するか否か）を判定する（ステップＳ１２）。ニューロン回路２１ａ１〜２１ａｎのそれぞれは、２回目以降は、更新された各ニューロンのビット値や、更新されたエネルギー変化に基づいて同様の処理を行う。
【００８６】
更新制御回路２２は、ニューロン回路２１ａ１〜２１ａｎが出力する判定結果（ｆ１〜ｆｎ）に基づいて、更新対象ニューロンを１つ決定し、そのビット値を更新する（ステップＳ１３）。更新が許容されたニューロンが複数ある場合、更新制御回路２２は、たとえば、乱数に基づいて、１つを更新対象ニューロンとして決定する。そして、更新制御回路２２は、決定した更新対象ニューロンを示すｉｄｊと更新後のビット値（ｘｊ）を、ニューロン回路２１ａ１〜２１ａｎのそれぞれに供給する（ステップＳ１４）。なお、更新制御回路２２は、更新が許容されたニューロンが１つもない場合、ビット値の更新は行わず、前述のオフセット値を増加させるために、ｆｊ＝０を出力する。
【００８７】
ニューロン回路２１ａ１〜２１ａｎのそれぞれが有するＣＡＭ３０が、ｉｄｊと一致するｉｄを保持している場合、そのｉｄに対応した重み係数がＲＡＭ３１から読み出される（ステップＳ１５）。ニューロン回路２１ａ１〜２１ａｎのそれぞれが有する演算部３２は、ＲＡＭ３１から重み係数が読み出された場合、その重み係数と、更新対象ニューロンのビット値（ｘｊ）に基づいて、エネルギー変化を更新する（ステップＳ１６）。
【００８８】
その後、制御回路２３は、反復回数を示すｔを＋１し（ステップＳ１７）、ｔが所定回数（ｋ）より大きいか否かを判定する（ステップＳ１８）。制御回路２３は、ｔがｋ以下である場合、ニューロン回路２１ａ１〜２１ａｎにステップＳ１２からの処理を繰り返させる。
【００８９】
なお、図５では図示が省略されているが、シミュレーテッド・アニーリングが行われる場合、制御回路２３は、ｔが所定回数増加するたびに、アニーリング条件にしたがって、温度パラメータの値を小さくしていく。
【００９０】
制御回路２３は、ｔがｋより大きい場合、保持部２２ａに保持されている各ニューロンのビット値を取得し、最適化問題に対する解として出力（制御装置２５に送信）し（ステップＳ１９）、最適化装置２０の動作を終了させる。
【００９１】
なお、制御回路２３は、保持部２２ａが、エネルギーの最小値や最小値が得られたときの各ニューロンのビット値を保持している場合には、更新対象ニューロンを決定する処理が所定回数、繰り返されたのちに、保持されている情報を取得する。そして、制御回路２３は、取得した情報を制御装置２５に送信してもよい。
【００９２】
以上のような、第２の実施の形態の最適化装置２０によれば、第１の実施の形態の最適化装置１０と同様の効果が得られる。すなわち、図４に示したような重み係数を記憶するＲＡＭ３１の容量を削減することができる。たとえば、各ニューロンの結合数の最大値が３２の場合、３２個分の重み係数を保持する容量のＲＡＭ３１を用いればよい。これにより、たとえば、１チップの最適化装置２０により、より大規模な最適化問題の計算が可能になる。
【００９３】
なお、ＣＡＭ３０は、一般的に遅延時間が少ないため、ＣＡＭ３０を追加したことによる計算時間の低下は少ない。
（第３の実施の形態）
図６は、第３の実施の形態の最適化装置の一例を示す図である。図６において、図３に示した要素と同じ要素については同一符号が付されている。なお、図６では、図２に示した制御回路２３については図示が省略されている。
【００９４】
第３の実施の形態の最適化装置４０において、ニューロン回路４１ａ１のＣＡＭ４２は、ｉｄｊに一致する結合先情報（ｉｄ）を保持しているか否かを示す一致判定情報（ＭＨＩＴ１）を出力する。以下では、ＣＡＭ４２は、ｉｄｊに一致するｉｄを保持している場合、ＭＨＩＴ１＝０を出力し、ｉｄｊに一致するｉｄを保持していない場合、ＭＨＩＴ１＝１を出力するものとする。
【００９５】
ニューロン回路４１ａ２〜４１ａｎについてもニューロン回路４１ａ１と同様の回路構成となっている。ニューロン回路４１ａ２〜４１ａｎは、ｉｄ＝２〜ｎのニューロンについての更新を許容するか否かの判定結果（ｆ２〜ｆｎ）を出力するとともに、ｉｄｊに一致するｉｄを保持しているか否かを示す一致判定情報（ＭＨＩＴ２〜ＭＨＩＴｎ）を出力する。
【００９６】
更新制御回路４３は、ニューロン回路４１ａ１〜４１ａｎのうち、値が１の一致判定情報を出力したニューロン回路が出力する判定結果が、ニューロンの更新を許容するものである場合、そのニューロンを更新対象ニューロンの１つとして決定する。
【００９７】
（第３の実施の形態の最適化装置４０におけるＣＡＭ４２の一例）
図７は、第３の実施の形態の最適化装置におけるＣＡＭの一例を示す図である。図７において、図４に示した要素と同じ要素については同一符号が付されている。
【００９８】
ＣＡＭ４２は、ＮＯＲ（否定論理和）回路４２ａを有する。ＮＯＲ回路４２ａは、一致判定回路３０ｂ１〜３０ｂｍのそれぞれの出力値の否定論理和であるＭＨＩＴ１を出力する。
【００９９】
図７に示すように、一致判定回路３０ｂ１〜３０ｂｍの全てに、ｉｄｊに一致するｉｄが保持されていない場合、一致判定回路３０ｂ１〜３０ｂｍの出力値は全て０となり、ＮＯＲ回路４２ａは、ＭＨＩＴ１＝１を出力する。一致判定回路３０ｂ１〜３０ｂｍの何れか、ｉｄｊに一致するｉｄが保持されている場合、一致判定回路３０ｂ１〜３０ｂｍの何れかの出力値は１となり、ＮＯＲ回路４２ａは、ＭＨＩＴ１＝０を出力する。
【０１００】
（第３の実施の形態の最適化装置４０における更新制御回路４３の一例）
図８は、第３の実施の形態の最適化装置における更新制御回路の一例を示す図である。
更新制御回路４３は、メモリ４３ａ、ｉｄ抽出回路４３ｂ、加算回路４３ｃ、ニューロン選択回路４３ｄ、結合ニューロン検出回路４３ｅ、ｉｄ有無検出回路４３ｆ、ビット値更新回路４３ｇを有する。
【０１０１】
メモリ４３ａは、各ニューロンを示すｉｄを記憶している。メモリ４３ａとして、たとえば、レジスタ、ＲＡＭ、フラッシュメモリなどの半導体記憶装置などを用いることができる。なお、ニューロン回路４１ａ１〜４１ａｎのそれぞれが自身のｉｄを保持しており、ｆ１〜ｆｎ及びＭＨＩＴ１〜ＭＨＩＴｎとともに、ｉｄを更新制御回路４３に供給する場合、メモリ４３ａはなくてもよい。
【０１０２】
ｉｄ抽出回路４３ｂは、ニューロン回路４１ａ１〜４１ａｎのそれぞれが出力する判定結果（ｆ１〜ｆｎ）のうち、値が１である判定結果を出力するニューロン回路に割当てられたｉｄを、メモリ４３ａから抽出して出力する。なお、ｉｄ抽出回路４３ｂは、ｆ１〜ｆｎが全て０の場合、ｆｊ＝０を出力し、ｆ１〜ｆｎのうち少なくとも１つの値が１の場合、ｆｊ＝１を出力する。
【０１０３】
加算回路４３ｃは、ｉｄ抽出回路４３ｂが抽出したｉｄが複数ある場合、複数のｉｄのうち、ニューロン選択回路４３ｄが出力するｉｄｊと、結合ニューロン検出回路４３ｅが出力するｉｄｃを削除する。
【０１０４】
ニューロン選択回路４３ｄは、加算回路４３ｃが出力するｉｄから、更新対象ニューロンを示すｉｄｊを選択する。たとえば、ニューロン選択回路４３ｄは、加算回路４３ｃが出力するｉｄが複数ある場合、そのうち１つをランダムに選択するか、値が最小（または最大）のｉｄを、ｉｄｊとして選択する。
【０１０５】
結合ニューロン検出回路４３ｅは、ニューロン回路４１ａ１〜４１ａｎのそれぞれが出力するＭＨＩＴ１〜ＭＨＩＴｎに基づいて、ｉｄｊで表される更新対象ニューロンと結合するニューロンを示すｉｄをメモリ４３ａから抽出して、ｉｄｃとして出力する。ＭＨＩＴ１〜ＭＨＩＴｎのうち、値が０の一致判定情報を出力するニューロン回路に割当てられたｉｄがｉｄｃとして出力される。すなわち、更新対象ニューロンと結合するニューロンのｉｄがｉｄｃとして出力される。
【０１０６】
ｉｄ有無検出回路４３ｆは、加算回路４３ｃが出力するｉｄの有無を検出する。ｉｄ有無検出回路４３ｆが出力する検出結果は、ビット値更新回路４３ｇに供給されるとともに、制御回路２３にも供給される。
【０１０７】
ビット値更新回路４３ｇは、各ニューロンのビット値を保持する図示しない保持部を有しており、ｉｄｊで示される更新対象ニューロンのビット値を更新（０から１または１から０に反転）し、更新後のビット値（ｘｊ）を出力する。また、ビット値更新回路４３ｇは、ｉｄ有無検出回路４３ｆが、ｉｄがないことを検出した場合、ビット値の更新を行わない。
【０１０８】
このような更新制御回路４３では、ＭＨＩＴ１〜ＭＨＩＴｎに基づいて検出される更新対象ニューロンと結合するニューロン以外については、更新が許容される。たとえば、ｆ１，ｆ２＝１の場合、ｉｄ抽出回路４３ｂは、ｉｄ＝１，２を出力する。そして、ニューロン選択回路４３ｄは、たとえば、ｉｄ＝１をｉｄｊとして出力する。これにより、ｉｄ＝１のニューロンのビット値が更新される。
【０１０９】
ｉｄ＝１のニューロンと、ｉｄ＝２のニューロンが結合していない場合、ＭＨＩＴ２＝１となる。このため、ｉｄｃとして、ｉｄ＝２は出力されない。このとき、加算回路４３ｃは、ｉｄ＝１，２のうち、ニューロン選択回路４３ｄが出力するｉｄ＝１を削除するため、ニューロン選択回路４３ｄは、ｉｄ＝２をｉｄｊとして出力する。これにより、ｉｄ＝２のニューロンのビット値が更新される。
【０１１０】
（第３の実施の形態の最適化装置４０の動作例（最適化方法の例））
図９は、第３の実施の形態の最適化装置の一例の動作の流れを示すフローチャートである。
【０１１１】
ステップＳ２０，Ｓ２１，Ｓ２２の処理は、図５に示したステップＳ１０〜Ｓ１２の処理と同じである。ステップＳ２３の処理では、図８に示した更新制御回路４３のニューロン選択回路４３ｄが更新対象ニューロンを１つ決定し、ビット値更新回路４３ｇが更新対象ニューロンのビット値（ｘｊ）を更新する。ステップＳ２４の処理では、ニューロン選択回路４３ｄが出力するｉｄｊと、ビット値更新回路４３ｇが出力するｘｊがニューロン回路４１ａ１〜４１ａｎのそれぞれに供給される。その後のステップＳ２５，Ｓ２６の処理は、図５に示したステップＳ１５，Ｓ１６の処理と同じである。
【０１１２】
ステップＳ２７の処理では、図８に示した更新制御回路４３の加算回路４３ｃは、ｉｄ抽出回路４３ｂが出力するｉｄから、ｉｄｃとｉｄｊを削除する。ステップＳ２８の処理では、ｉｄ有無検出回路４３ｆは、加算回路４３ｃが出力するｉｄがあるか否か（残っているか否か）を検出する。ｉｄが残っている場合、ステップＳ２３からの処理が繰り返される。ｉｄが残っていない場合、ステップＳ２９の処理が行われる。ステップＳ２９，Ｓ３０，Ｓ３１の処理は、図５に示したステップＳ１７〜Ｓ１９の処理と同じである。
【０１１３】
なお、図９でも図示が省略されているが、シミュレーテッド・アニーリングが行われる場合、制御回路２３は、ｔが所定回数増加するたびに、アニーリング条件にしたがって、温度パラメータの値を小さくしていく。
【０１１４】
以上のような、第３の実施の形態の最適化装置４０によれば、第２の実施の形態の最適化装置２０と同様の効果が得られる。また、最適化装置４０によれば、複数のニューロンのビット値の更新が許容された場合、結合がないニューロン同士についてはビット値を同時に更新することができる。なお、結合がないニューロン同士についてはビット値を同時に更新しても、最適解への収束性の悪化を招かない。
【０１１５】
また、上記のようなＭＨＩＴ１〜ＭＨＩＴｎを用いることで、値が０の重み係数を保持しなくても更新対象ニューロンと結合しないニューロンを検出することができる。
以上、実施の形態に基づき、本発明の最適化装置及び最適化方法の一観点について説明してきたが、これらは一例にすぎず、上記の記載に限定されるものではない。
【符号の説明】
【０１１６】
１０  最適化装置
１１ａ１〜１１ａｎ  ニューロン回路
１１ｂ１〜１１ｂｎ，１１ｃ１〜１１ｃｎ  記憶部
１１ｄ１〜１１ｄｎ  演算部
１２  更新制御回路
【図１】
2020194442.tif 000007
【図２】
2020194442.tif 000008
【図３】
2020194442.tif 000009
【図４】
2020194442.tif 000010
【図５】
2020194442.tif 000011
【図６】
2020194442.tif 000012
【図７】
2020194442.tif 000013
【図８】
2020194442.tif 000014
【図９】
2020194442.tif 000015