(57)【要約】【課題】最適化問題の解の精度の悪化を抑制する。【解決手段】演算部１１は、計算対象の最適化問題を変換したイジングモデルを表すイジングモデル情報と、温度パラメータとに基づいてイジングモデルの基底状態を探索し、制御部１２は、演算部１１におけるイジングモデルのエネルギーの分解能Ｒと、温度パラメータが最低値Ｔｍｉｎのときのイジングモデルの状態遷移の許容確率を表す基準値Ａｍｉｎとに基づいて最低値Ｔｍｉｎを決定し、イジングモデル情報に基づいてエネルギーの変化分の最大値を決定し、基準値Ａｍｉｎよりも大きく温度パラメータが最高値Ｔｍａｘのときの許容確率を表す基準値Ａｍａｘと、決定したエネルギーの変化分の最大値とに基づいて最高値Ｔｍａｘを決定し、演算部１１に最低値Ｔｍｉｎと最高値Ｔｍａｘとを送信する。【選択図】図１
2020046718.tif 000002
【特許請求の範囲】
【請求項１】
計算対象の最適化問題を変換したイジングモデルを表すイジングモデル情報と、温度パラメータとに基づいて前記イジングモデルの基底状態を探索する演算部と、
前記演算部における前記イジングモデルのエネルギーの分解能と、前記温度パラメータが最低値のときの前記イジングモデルの状態遷移の許容確率を表す第１の基準値とに基づいて前記最低値を決定し、前記イジングモデル情報に基づいて前記エネルギーの変化分の最大値を決定し、前記第１の基準値よりも大きく前記温度パラメータが最高値のときの前記許容確率を表す第２の基準値と、前記最大値とに基づいて前記最高値を決定し、前記演算部に前記最低値と前記最高値とを送信する制御部と、
を有する最適化装置。
【請求項２】
前記制御部は、前記イジングモデル情報に含まれる重み係数の絶対値の総和を、前記イジングモデルの全ビット数で割ることで前記最大値を決定する、請求項１に記載の最適化装置。
【請求項３】
前記制御部は、前記イジングモデル情報に含まれる重み係数の絶対値の総和を、前記イジングモデルの全ビット数で割った値に、前記イジングモデル情報に含まれる全ビットのそれぞれについてのバイアス係数の絶対値のうちの最大の値を加算することで、前記最大値を決定する、請求項１に記載の最適化装置。
【請求項４】
前記制御部は、前記イジングモデルに含まれる全ビットのそれぞれが変化するときの前記変化分の第１の最大値を、前記全ビットのそれぞれについて計算し、前記全ビットのそれぞれについて計算した前記第１の最大値の中で最大の値を示すものを、前記最大値として決定する、請求項１に記載の最適化装置。
【請求項５】
前記演算部は、前記温度パラメータの値の下げ方を示す温度下降制御情報を受け、前記温度下降制御情報に基づいて、前記最高値から前記最低値まで、前記温度パラメータの値を小さくしていくことで、シミュレーテッド・アニーリング法による前記基底状態の探索を行う、請求項１乃至４の何れか一項に記載の最適化装置。
【請求項６】
前記演算部は、レプリカ交換法により前記基底状態の探索を行い、
前記制御部は、前記最高値から前記最低値まで、前記演算部に含まれるレプリカ数分の、前記温度パラメータの値を含む温度スケジュール情報を決定し、前記温度スケジュール情報を前記演算部に送信する、請求項１乃至４の何れか一項に記載の最適化装置。
【請求項７】
計算対象の最適化問題を変換したイジングモデルを表すイジングモデル情報と、温度パラメータとに基づいて前記イジングモデルの基底状態を探索する演算部と、
制御部と、を有する最適化装置の前記制御部が、
前記演算部における前記イジングモデルのエネルギーの分解能と、前記温度パラメータが最低値のときの前記イジングモデルの状態遷移の許容確率を表す第１の基準値とに基づいて前記最低値を決定し、
前記イジングモデル情報に基づいて前記エネルギーの変化分の最大値を決定し、
前記第１の基準値よりも大きく前記温度パラメータが最高値のときの前記許容確率を表す第２の基準値と、前記最大値とに基づいて前記最高値を決定し、
前記演算部に前記最低値と前記最高値とを送信する、
最適化装置の制御方法。
【請求項８】
計算対象の最適化問題を変換したイジングモデルを表すイジングモデル情報と、温度パラメータとに基づいて前記イジングモデルの基底状態を探索する演算部を有する最適化装置の前記演算部における前記イジングモデルのエネルギーの分解能と、前記温度パラメータが最低値のときの前記イジングモデルの状態遷移の許容確率を表す第１の基準値とに基づいて前記最低値を決定し、
前記イジングモデル情報に基づいて前記エネルギーの変化分の最大値を決定し、
前記第１の基準値よりも大きく前記温度パラメータが最高値のときの前記許容確率を表す第２の基準値と、前記最大値とに基づいて前記最高値を決定し、
前記演算部に前記最低値と前記最高値とを送信する、
処理をコンピュータに実行させる最適化装置の制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適化装置、最適化装置の制御方法及び最適化装置の制御プログラムに関する。
【背景技術】
【０００２】
従来、ノイマン型コンピュータが不得意とする多変数の最適化問題を、イジング型のエネルギー関数を用いた最適化装置（イジングマシンまたはボルツマンマシンと呼ばれる場合もある）によって計算する方法がある。最適化装置は、計算対象の問題を、磁性体のスピンの振る舞いを表すモデルであるイジングモデルに置き換えて計算する。
【０００３】
最適化装置は、たとえば、ニューラルネットワークを用いて問題をモデル化することもできる。その場合、イジングモデルに含まれる複数のスピンに対応した複数のビットのそれぞれが、他のビットの値と、他のビットと自身のビットとの相互作用の大きさを示す重み係数（結合係数とも呼ばれる）とに応じて０または１を出力するニューロンとして機能する。最適化装置は、たとえば、シミュレーテッド・アニーリングやレプリカ交換法（交換モンテカルロ法などとも呼ばれる）などの確率的探索法により、イジングモデルのエネルギー関数の値の最小値が得られる各ビットの値を、解として求める。以下、エネルギー関数の値をエネルギーと呼ぶことにする。
【０００４】
シミュレーテッド・アニーリングやレプリカ交換法では、エネルギー変化ΔＥを引き起こす状態遷移（ビットの値の反転）を許容する確率Ａを、たとえば、以下の式（１）のように決めることで、時刻無限大の極限で状態が最適解に到達する。
【０００５】
Ａ＝ｆ（−ΔＥ／Ｔ）＝ｍｉｎ［１，ｅｘｐ（−ΔＥ／Ｔ）］            （１）
式（１）においてＴは温度を表すパラメータである。シミュレーテッド・アニーリングでは、温度の初期値は問題に応じて十分大きく、確率的探索のある反復回数ごとに小さくなるように制御される。レプリカ交換法では、異なる温度が設定された複数のレプリカを用いて、各レプリカ内では温度が固定の状態で確率的探索が行われる。そして、ある反復回数ごとに、レプリカ間のエネルギー差と温度差に応じて、レプリカ間で状態（各ビットの値）が交換される。なお、レプリカ間で、状態の代りに温度を交換してもよい。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平５−１２０２５２号公報
【特許文献２】特開平８−１５３０８５号公報
【特許文献３】特開２０１６−５１３５０号公報
【特許文献４】特開２０１６−１０３２８２号公報
【非特許文献】
【０００７】
【非特許文献１】K. Hukushima and K. Nemoto, "Exchange Monte Carlo Method and Application to Spin Glass Simulations," J. Phys. Soc. Jpn., 1996, Volume 65, pp. 1604-1611
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、計算対象の最適化問題ごとに、取り得るエネルギーの変化分が異なるために、従来の最適化装置では、適切な範囲で温度を設定することが難しい。適切な範囲で温度が設定されなかった場合には、状態遷移の許容確率が適切に設定されず、状態遷移が頻繁に起こりすぎる、または状態遷移がまったく起こらない、という状況が生じる可能性がある。これにより、最適解への収束が困難になるため、解の精度が悪化するという問題があった。
【０００９】
１つの側面では、本発明は、最適化問題の解の精度の悪化を抑制可能な最適化装置、最適化装置の制御方法及び最適化装置の制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
１つの実施態様では、計算対象の最適化問題を変換したイジングモデルを表すイジングモデル情報と、温度パラメータとに基づいて前記イジングモデルの基底状態を探索する演算部と、前記演算部における前記イジングモデルのエネルギーの分解能と、前記温度パラメータが最低値のときの前記イジングモデルの状態遷移の許容確率を表す第１の基準値とに基づいて前記最低値を決定し、前記イジングモデル情報に基づいて前記エネルギーの変化分の最大値を決定し、前記第１の基準値よりも大きく前記温度パラメータが最高値のときの前記許容確率を表す第２の基準値と、前記最大値とに基づいて前記最高値を決定し、前記演算部に前記最低値と前記最高値とを送信する制御部と、を有する最適化装置が提供される。
【００１１】
また、１つの実施態様では、最適化装置の制御方法が提供される。また、１つの実施態様では、最適化装置の制御プログラムが提供される。
【発明の効果】
【００１２】
１つの側面では、本発明は、最適化問題の解の精度の悪化を抑制できる。
【図面の簡単な説明】
【００１３】
【図１】第１の実施の形態の最適化装置の一例を示す図である。
【図２】計算対象の最適化問題の違いによるエネルギー変化の違いの例を示す図である。
【図３】第２の実施の形態の最適化装置の一例を示す図である。
【図４】シミュレーテッド・アニーリング法により基底状態の探索を行う演算部の一例を示す図である。
【図５】演算回路の一例を示す図である。
【図６】温度パラメータＴの制御例を示す図である。
【図７】第３の実施の形態の最適化装置の一例を示す図である。
【図８】レプリカ交換法により基底状態の探索を行う演算部の一例を示す図である。
【図９】第３の実施の形態の最適化装置の制御部の動作の流れの一例を示すフローチャートである。
【図１０】第４の実施の形態の最適化装置の一例を示す図である。
【図１１】第５の実施の形態の最適化装置の一例を示す図である。
【図１２】第６の実施の形態の最適化装置の一例を示す図である。
【図１３】第６の実施の形態の最適化装置の制御部の動作の流れの一例を示すフローチャートである。
【図１４】第７の実施の形態の最適化装置の一例を示す図である。
【図１５】第７の実施の形態の最適化装置の制御部の動作の流れの一例を示すフローチャートである。
【図１６】制御装置のハードウェア例を示す図である。
【発明を実施するための形態】
【００１４】
以下、発明を実施するための形態を、図面を参照しつつ説明する。
以下に示す最適化装置は、計算対象の最適化問題を変換したイジングモデルの全スピンに対応する全ビットのそれぞれの値の組み合わせのうち、エネルギー関数が最小値となるときの各ビットの値（イジングモデルの基底状態）を探索するものである。
【００１５】
イジング型のエネルギー関数Ｅ（ｘ）は、たとえば、以下の式（２）で定義される。
【００１６】
【数１】
2020046718.tif 000003
【００１７】
右辺の１項目は、イジングモデルの全ビットの全組み合わせについて、漏れと重複なく、２つのビットの値（０または１）と重み係数との積を積算したものである。ｘｉは、ｉ番目のビットの値を表す変数（状態変数とも呼ばれる）、ｘｊは、ｊ番目のビットの値を表す変数であり、Ｗｉｊは、ｉ番目とｊ番目のビットの相互作用の大きさを示す重み係数である。なお、Ｗｉｉ＝０である。また、Ｗｉｊ＝Ｗｊｉであることが多い（つまり、重み係数による係数行列は対称行列である場合が多い）。また重み係数Ｗｉｊは、所定のビット幅（たとえば、１６ビット、３２ビット、６４ビット、１２８ビットなど）をもつ。
【００１８】
右辺の２項目は、全ビットのそれぞれのバイアス係数とビットの値を表す変数との積の総和を求めたものである。ｂｉは、ｉ番目のビットのバイアス係数を示している。
また、変数ｘｉが変化して１−ｘｉとなると、変数ｘｉの増加分は、Δｘｉ＝（１−ｘｉ）−ｘｉ＝１−２ｘｉと表せる。ビットの値の反転に伴うエネルギー変化（エネルギーの変化分）ΔＥｉは、以下の式（３）で表される。
【００１９】
【数２】
2020046718.tif 000004
【００２０】
式（３）において、変数ｘｉが１から０に変化するとき、Δｘｉは−１となり、変数ｘｉが０から１に変化するとき、Δｘｉは１となる。なお、ｈｉはローカルフィールド（局所場）と呼ばれ、Δｘｉに応じてローカルフィールドｈｉに符号（＋１または−１）を乗じたものがエネルギー変化ΔＥｉである。
【００２１】
また、変数ｘｊが０から１に変化したときのローカルフィールドｈｉの変化分Δｈｉは、＋Ｗｉｊ、変数ｘｊが１から０に変化したときの変化分Δｈｉは、−Ｗｉｊと表せる。
（第１の実施の形態）
図１は、第１の実施の形態の最適化装置の一例を示す図である。
【００２２】
第１の実施の形態の最適化装置１０は、たとえば、１チップまたは複数チップの半導体集積回路（たとえば、ＦＰＧＡ（Field Programmable Gate Array）など）である。最適化装置１０は、演算部１１と制御部１２を有する。
【００２３】
演算部１１は、イジングモデルを表すイジングモデル情報と、温度パラメータＴとに基づいて、イジングモデルの基底状態を探索する。演算部１１が用いるイジングモデル情報には、重み係数群Ｗ、バイアス係数群ｂが含まれる。さらに、図１の例では、演算部１１には、イタレーション回数Ｎｉｔが供給されている。
【００２４】
基底状態を探索する方法として、たとえば、シミュレーテッド・アニーリングやレプリカ交換法などの確率的探索法が用いられる。演算部１１は、前述の式（１）に示した確率で状態遷移を許容してビットの値の更新を行う処理を、イタレーション回数Ｎｉｔ、繰り返したときの各ビットの値（状態ｘｏｕｔ）を基底状態の探索結果（解）として出力する。また、演算部１１は、そのときのエネルギーＥを出力する。
【００２５】
演算部１１は、イジングモデル情報やイタレーション回数Ｎｉｔを、たとえば、図示しない制御装置（たとえば、ＰＣ（Personal Computer））から取得する。
制御部１２は、イジングモデル情報のほか、演算部１１におけるイジングモデルのエネルギーの分解能Ｒと、イジングモデルの状態遷移の許容確率の基準値Ａｍｉｎ，Ａｍａｘとを、たとえば、図示しない制御装置から取得する。分解能Ｒは、エネルギー変化の最小値を示し、演算部１１のハードウェアに依存する値である。演算部１１のハードウェアに応じた適切な分解能Ｒが、たとえば、制御装置により設定される。
【００２６】
基準値Ａｍｉｎは、温度パラメータＴの最低値Ｔｍｉｎのときの許容確率を表す値である。低温時（温度パラメータＴが小さいとき）にはエネルギーが増加する方向への状態遷移の許容確率が十分低くなるように、基準値Ａｍｉｎとして、十分小さい値（たとえば、０．００１など）が設定される。基準値Ａｍａｘは、基準値Ａｍｉｎより大きく、温度パラメータＴの最高値Ｔｍａｘのときの許容確率を表す値である。高温時（温度パラメータＴが大きいとき）には全ての状態（エネルギーが大きく増加する方向も含む）への状態遷移の許容確率が十分に高くなるように、基準値Ａｍａｘとして、平均的な値（たとえば、０．２５、０．５、０．７５など）が設定される。
【００２７】
最低値Ｔｍｉｎは、以下の式（４）で表せる。
Ｔｍｉｎ＝−Ｒ／ｌｎ（Ａｍｉｎ）            （４）
制御部１２は、分解能Ｒと基準値Ａｍｉｎに基づいて式（４）を計算することで、最低値Ｔｍｉｎを決定する。
【００２８】
一方、最高値Ｔｍａｘは、以下の式（５）で表せる。
Ｔｍａｘ＝−ｍａｘ（ΔＥ）／ｌｎ（Ａｍａｘ）          （５）
式（５）において、ｍａｘ（ΔＥ）は、エネルギー変化ΔＥの最大値を表す。
【００２９】
制御部１２は、イジングモデル情報に基づいて、ｍａｘ（ΔＥ）を決定する。
前述の式（３）において、バイアス係数ｂｉに対して重み係数Ｗｉｊが支配的であるとすると、ｍａｘ（ΔＥ）は以下の式（６）で近似できる。
【００３０】
【数３】
2020046718.tif 000005
【００３１】
式（６）において、Ｎは、イジングモデルの全ビット数である。つまり、ｍａｘ（ΔＥ）は、重み係数Ｗｉｊの絶対値の総和を、全ビット数Ｎで割った値により近似される。
制御部１２は、たとえば、イジングモデル情報に含まれる重み係数群Ｗと、全ビット数Ｎとに基づいて、式（６）を計算することでｍａｘ（ΔＥ）を決定する。そして、制御部１２は、ｍａｘ（ΔＥ）と、基準値Ａｍａｘに基づいて、式（５）を計算することで、最高値Ｔｍａｘを決定する。
【００３２】
たとえば、重み係数Ｗｉｊを符号付き１６ビットで全て最大値とし、イジングモデルの全ビット数Ｎを１０２４とし、バイアス係数ｂｉを無視すると、ｍａｘ（ΔＥ）は、１０２４×２１５＝３３５５４４３２となる。Ａｍａｘ＝０．７５とした場合、式（５）より、Ｔｍａｘ＝−３３５５４４３２／ｌｎ（０．７５）＝１１６６３７２０２となる。なお、実際には、重み係数Ｗｉｊが全て最大値となることはないため、最高値Ｔｍａｘは上記の値より小さい。
【００３３】
また、ビット間の相互作用の有無のみが考慮される最適化問題では、重み係数Ｗｉｊは、１、０、−１の何れかである。この場合、ｍａｘ（ΔＥ）は、１０２４×１＝１０２４となり、Ａｍａｘ＝０．７５とした場合、最高値Ｔｍａｘは３５６０程度となる。
【００３４】
このように、計算対象の最適化問題によって、最高値Ｔｍａｘは大きく異なる。
なお、ｍａｘ（ΔＥ）の他の算出方法（バイアス係数ｂｉを用いる方法など）については、後述する。
【００３５】
制御部１２は、決定した最低値Ｔｍｉｎと最高値Ｔｍａｘとを、たとえば、温度スケジュール情報Ｔｓｃの一部として演算部１１に送信する。
演算部１１が、シミュレーテッド・アニーリング法により基底状態の探索を行う場合には、温度スケジュール情報Ｔｓｃとして、さらに、温度パラメータＴの値の下げ方を示す情報も演算部１１に供給される。なお、制御部１２が直接、所定の温度スケジュールにしたがって、温度パラメータＴを最高値Ｔｍａｘから最低値Ｔｍｉｎまで、小さくするように制御してもよい。
【００３６】
演算部１１が、レプリカ交換法により基底状態の探索を行う場合、制御部１２は、最高値Ｔｍａｘから最低値Ｔｍｉｎまで、演算部１１に含まれるレプリカ数分の温度パラメータＴの値を含む温度スケジュール情報Ｔｓｃを決定し、演算部１１に送信する。
【００３７】
制御部１２は、たとえば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡなどの特定用途の電子回路にて実現できる。なお、制御部１２は、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）などのプロセッサであってもよい。その場合、プロセッサは、図示しないメモリに記憶されたプログラムを実行することで、上記のような処理を行う。
【００３８】
以下、第１の実施の形態の最適化装置１０の動作例を説明する。
図１には、最適化装置１０の制御部１２の動作の流れの一例が示されている。制御部１２は、イジングモデル情報（全ビット数Ｎ、重み係数群Ｗ）、イタレーション回数Ｎｉｔ、分解能Ｒ、基準値Ａｍｉｎ，Ａｍａｘなどの情報を、たとえば、図示しない制御装置から取得する（ステップＳ１）。そして、制御部１２は、前述のＴｍｉｎ決定処理（ステップＳ２）、Ｔｍａｘ決定処理（ステップＳ３）を行い、最低値Ｔｍｉｎ、最高値Ｔｍａｘを含む温度スケジュール情報Ｔｓｃを、演算部１１に送信する（ステップＳ４）。なお、ステップＳ２，Ｓ３の処理の順序は逆でもよい。
【００３９】
その後、演算部１１は、温度スケジュール情報Ｔｓｃによって決まる温度パラメータＴと、イジングモデル情報に基づいて、イジングモデルの基底状態を探索する。たとえば、演算部１１は、前述の式（１）に示した確率で状態遷移を許容してビットの値の更新を行う処理を、イタレーション回数Ｎｉｔ、繰り返したときの各ビットの値（状態ｘｏｕｔ）を基底状態の探索結果（解）として出力する。また、演算部１１は、そのときのエネルギーＥを出力する。
【００４０】
図２は、計算対象の最適化問題の違いによるエネルギー変化の違いの例を示す図である。図２において、横軸は状態ｘを表し、縦軸はエネルギーＥ（ｘ）を表す。
たとえば、ある最適化問題では、エネルギーＥ（ｘ）は波形１５ａで表され、別の最適化問題では、エネルギーＥ（ｘ）は波形１５ｂで表される。波形１５ａ，１５ｂからわかるように、取り得るエネルギーＥ（ｘ）の変化分は、波形１５ａよりも波形１５ｂのほうが大きい。
【００４１】
このため、両方の最適化問題を解く際に、同じ温度パラメータＴを用いた場合、エネルギーＥ（ｘ）が波形１５ａで表される最適化問題を解く際には、状態遷移が頻繁に起こりすぎる可能性がある。または、エネルギーＥ（ｘ）が波形１５ｂで表される最適化問題を解く際には、状態遷移がまったく起こらない可能性がある。これにより、最適解への収束が困難になるため、解の精度が悪化する。
【００４２】
第１の実施の形態の最適化装置１０は、イジングモデル情報から、取り得るエネルギーの変化分を決定し、その変化分に基づいて基底状態の探索時の温度パラメータＴの範囲を決定する。これにより、計算対象の最適化問題に応じた温度パラメータＴの範囲で演算部１１が演算を行うことが可能になる。このため、状態遷移の許容確率が適切になり最適化問題の解の精度の悪化を抑制できる。
【００４３】
（第２の実施の形態）
図３は、第２の実施の形態の最適化装置の一例を示す図である。
第２の実施の形態の最適化装置２０は、演算部２１、制御部２２を有する。
【００４４】
演算部２１は、イジングモデル情報と、温度パラメータＴとに基づいて、シミュレーテッド・アニーリング法により、イジングモデルの基底状態を探索する。演算部２１が用いるイジングモデル情報には、重み係数群Ｗ、バイアス係数群ｂ、各ビットの初期値ｘｉｎｉが含まれる。さらに、図３の例では、演算部２１には、イタレーション回数Ｎｉｔと、温度パラメータＴの値の下げ方を示す温度下降制御情報Ｔｄが供給されている。イジングモデル情報や、イタレーション回数Ｎｉｔ、温度下降制御情報Ｔｄは、たとえば、ＰＣなどの制御装置から供給される。
【００４５】
演算部２１は、前述の式（１）に示した確率で状態遷移を許容してビットの値の更新を行う処理を、イタレーション回数Ｎｉｔ、繰り返したときの各ビットの値（状態ｘｏｕｔ）を基底状態の探索結果（解）として出力する。また、演算部２１は、そのときのエネルギーＥを出力する。演算部２１の回路例については後述する。
【００４６】
制御部２２は、情報取得部２２ａ、Ｔｍａｘ計算部２２ｂ、Ｔｍｉｎ計算部２２ｃ、送信部２２ｄを有する。
情報取得部２２ａは、たとえば、ＰＣなどの制御装置から供給される、重み係数群Ｗ、全ビット数Ｎ、前述した基準値Ａｍｉｎ，Ａｍａｘ、分解能Ｒを取得する。
【００４７】
Ｔｍａｘ計算部２２ｂは、重み係数群Ｗと、全ビット数Ｎとに基づいて、前述の式（６）を計算することで、ｍａｘ（ΔＥ）を決定し、ｍａｘ（ΔＥ）と、基準値Ａｍａｘに基づいて、式（５）を計算することで、温度パラメータＴの最高値Ｔｍａｘを決定する。
【００４８】
Ｔｍｉｎ計算部２２ｃは、分解能Ｒと基準値Ａｍｉｎに基づいて前述の式（４）を計算することで、最低値Ｔｍｉｎを決定する。
送信部２２ｄは、最低値Ｔｍｉｎ、最高値Ｔｍａｘを演算部２１に送信する。
【００４９】
（演算部２１の例）
図４は、シミュレーテッド・アニーリング法により基底状態の探索を行う演算部の一例を示す図である。
【００５０】
演算部２１は、記憶部２１ａ、演算回路部２１ｂ、選択回路部２１ｃ、状態更新部２１ｄ、エネルギー更新部２１ｅ、制御回路２１ｆを有する。
記憶部２１ａは、重み係数群Ｗ（重み係数Ｗ１１〜ＷＮＮ）を記憶する。記憶部２１ａは、たとえば、レジスタやＳＲＡＭ（Static Random Access Memory）などである。
【００５１】
演算回路部２１ｂは、バイアス係数群ｂや記憶部２１ａに記憶された重み係数群Ｗを取得し、状態更新部２１ｄから全ビットのうち更新された更新ビットの値を受け、選択回路部２１ｃから更新ビットを識別するｉｎｄｅｘを受ける。そして、演算回路部２１ｂは、それらに基づいて、Ｎ個のビットの何れか１つが変化することによるイジングモデルのエネルギー変化をＮ個のビットのそれぞれについて算出する。さらに、演算回路部２１ｂは、熱励起エネルギーと、Ｎ個のビットのそれぞれについて算出したエネルギー変化との大小関係に基づいて、各ビットについて更新を許容するか否かを判定する。そして、演算回路部２１ｂは、Ｎ個のビットのそれぞれについての更新を許容するか否かの判定結果を示すフラグ情報と、エネルギー変化を出力する。
【００５２】
熱励起エネルギーは、たとえば、後述の乱数発生回路が生成した乱数と、制御回路２１ｆから供給される温度パラメータＴとに基づいて決定される。
図４の例では、演算回路部２１ｂは、Ｎ個の演算回路２１ｂ１，２１ｂ２，…，２１ｂＮを有する。
【００５３】
演算回路２１ｂ１は、ｉｎｄｅｘ＝１のビットが変化することによるイジングモデルのエネルギー変化を算出し、熱励起エネルギーと、その算出したエネルギー変化との大小関係に基づいて、更新を許容するか否かを判定する。そして、演算回路２１ｂ１は、フラグ情報と、エネルギー変化とを出力する。演算回路２１ｂ２〜２１ｂＮは、ｉｎｄｅｘ＝２〜Ｎのビットについて、演算回路２１ｂ１と同様の処理を行う。
【００５４】
演算回路２１ｂ１〜２１ｂＮの回路例については後述する。
選択回路部２１ｃは、フラグ情報に基づいて、乱数を用いて、更新を許容する１つの許容ビットを選択し、選択した許容ビットについてのフラグ情報、エネルギー変化、その許容ビットを識別するｉｎｄｅｘを出力する。選択回路部２１ｃは、ｉｎｄｅｘを自身で生成してもよいし、演算回路２１ｂ１〜２１ｂＮがそれぞれｉｎｄｅｘを保持している場合には、演算回路２１ｂ１〜２１ｂＮから各ｉｎｄｅｘを取得し、選択した許容ビットのｉｎｄｅｘを出力してもよい。
【００５５】
状態更新部２１ｄは、各ビットの値を保持し、選択回路部２１ｃが出力するフラグ情報と、ｉｎｄｅｘとに基づいて、保持内容を更新する。状態更新部２１ｄには、各ビットの初期値ｘｉｎｉが設定され、制御回路２１ｆの制御のもと、ビットの値の更新を行う処理が、イタレーション回数Ｎｉｔ、繰り返されたときの各ビットの値（状態ｘｏｕｔ）を基底状態の探索結果として出力する。
【００５６】
エネルギー更新部２１ｅは、選択回路部２１ｃが出力するフラグ情報と、エネルギー変化とに基づいて、イジングモデルのエネルギーを更新する。エネルギー更新部２１ｅは、制御回路２１ｆの制御のもと、ビットの値の更新を行う処理が、イタレーション回数Ｎｉｔ、繰り返されたときのエネルギーＥを出力する。
【００５７】
制御回路２１ｆは、温度パラメータＴの最高値Ｔｍａｘ、最低値Ｔｍｉｎ、温度下降制御情報Ｔｄに基づいて、演算回路部２１ｂに供給する温度パラメータＴを制御する。また、制御回路２１ｆは、ビットの値の更新を行う処理が、イタレーション回数Ｎｉｔ、繰り返されたか否かを判定する。そして、制御回路２１ｆは、ビットの値の更新を行う処理が、イタレーション回数Ｎｉｔ、繰り返されたときに、状態更新部２１ｄに保持している各ビットの値を出力させ、エネルギー更新部２１ｅにそのときのエネルギーＥを出力させる。
【００５８】
（演算回路の一例）
図５は、演算回路の一例を示す図である。図５では、図４に示した演算回路２１ｂ１の例が示されている。図４に示した他の演算回路についても同様の回路により実現できる。
【００５９】
演算回路２１ｂ１は、ΔＥ計算部３０、状態遷移判定部３１を有する。
ΔＥ計算部３０は、選択回路３０ａ，３０ｂ、乗算器３０ｃ、加算器３０ｄ、レジスタ３０ｅ、乗算器３０ｆ、選択回路３０ｇを有する。
【００６０】
選択回路３０ａは、図４に示した選択回路部２１ｃから供給されるｉｎｄｅｘ＝ｊに基づき、記憶部２１ａに格納されている重み係数Ｗ１ｊ（ｊ＝１〜Ｎ）のうち１つを選択して出力する。
【００６１】
たとえば、ｉｎｄｅｘ＝Ｎが選択回路３０ａに入力されたとき、選択回路３０ａは、重み係数Ｗ１Ｎを選択する。
選択回路３０ｂは、ｉｎｄｅｘ＝ｊのビットの変化分Δｘｊの演算を実現するものである。ｉｎｄｅｘ＝ｊのビットの値である変数ｘｊが１から０に変化するとき、Δｘｊは−１となり、変数ｘｊが０から１に変化するとき、Δｘｊは１となる。選択回路３０ｂは、状態更新部２１ｄから供給される変数ｘｊ（ｉｎｄｅｘ＝ｊのビットの更新値）が０のときには、−１を選択して出力し、変数ｘｊが１のときには、１を選択して出力する。
【００６２】
乗算器３０ｃは、選択回路３０ａが出力する重み係数Ｗ１ｊと、選択回路３０ｂが出力する値との積を出力する。
加算器３０ｄは、乗算器３０ｃが出力する値と、レジスタ３０ｅに格納されている値とを加算して出力する。
【００６３】
レジスタ３０ｅは、図示しないクロック信号に同期して、加算器３０ｄが出力する値（ローカルフィールドｈ１）を取り込む。レジスタ３０ｅは、たとえば、フリップフロップである。なお、レジスタ３０ｅに格納されるローカルフィールドｈ１の初期値はバイアス係数ｂ１である。
【００６４】
乗算器３０ｆは、レジスタ３０ｅが出力するローカルフィールドｈ１と選択回路３０ｇが出力する値との積を出力する。この積が、エネルギー変化ΔＥ１である。
選択回路３０ｇは、−Δｘ１の演算を実現するものである。選択回路３０ｇは、たとえば、状態更新部２１ｄに保持されている現在の変数ｘ１が０のときは、−１を出力し、現在の変数ｘ１が１のときは１を出力する。
【００６５】
状態遷移判定部３１は、符号反転部３１ａ、オフセット加算部３１ｂ、乱数発生回路３１ｃ、選択法則適用部３１ｄ、乗算器３１ｅ、比較回路３１ｆを有する。
符号反転部３１ａは、エネルギー変化ΔＥ１に−１を掛けて符号を反転させる。
【００６６】
オフセット加算部３１ｂは、符号反転部３１ａの出力値（−ΔＥ１）に、オフセット値を加える。オフセット加算部３１ｂは、前述の選択回路部２１ｃから供給されるフラグ情報であるｆｌｇｊが、状態遷移を許容しないことを示すとき（つまり状態遷移が生じないとき）、オフセット値を増加していく。一方、オフセット加算部３１ｂは、ｆｌｇｊが、状態遷移を許容することを示すとき（つまり状態遷移が生じるとき）には、オフセット値を０にする。オフセット値が大きくなると状態遷移が許容されやすくなり、現在の状態が局所解にある場合、その局所解からの脱出が促進される。
【００６７】
乱数発生回路３１ｃは、０以上、１以下の一様乱数ｒを発生する。
選択法則適用部３１ｄは、シミュレーテッド・アニーリングを行うための選択法則（たとえば、メトロポリス法）に基づいた値を出力する。
【００６８】
シミュレーテッド・アニーリングが行われる場合、前述のように、あるエネルギー変化ΔＥを引き起こす状態遷移を許容する確率Ａを、たとえば、式（１）のように決めることで、時刻無限大の極限で状態が最適解に到達することが証明されている。
【００６９】
式（１）で表される確率Ａを用いた場合、十分な反復後に定常状態に達したとすると、各状態の占有確率は熱力学における熱平衡状態に対するボルツマン分布にしたがう。そして、高い温度から徐々に下げていくとエネルギーの低い状態の占有確率が増加するため、十分温度が下がるとエネルギーの低い状態が得られるはずである。この様子が材料を焼き鈍したときの状態変化とよく似ているため、この方法はシミュレーテッド・アニーリングと呼ばれるのである。このとき、エネルギーが上がる状態遷移が確率的に起こることは、物理学における熱励起に相当する。
【００７０】
確率Ａでエネルギー変化ΔＥを引き起こす状態遷移を許容することを示すフラグ情報（＝１）を出力する回路は、式（１）のｆ（−ΔＥ／Ｔ）と、一様乱数ｒとの比較結果に基づいた値を出力する比較器によって実現できる。
【００７１】
ただ、次のような変形を行っても同じ機能が実現できる。２つの数に同じ単調増加関数を作用させても大小関係は変化しない。したがって比較器の２つの入力に同じ単調増加関数を作用させても比較器の出力は変わらない。たとえば、ｆ（−ΔＥ／Ｔ）に作用させる単調増加関数としてｆ（−ΔＥ／Ｔ）の逆関数ｆ−１（−ΔＥ／Ｔ）、一様乱数ｒに作用させる単調増加関数としてｆ−１（−ΔＥ／Ｔ）の−ΔＥ／Ｔをｒとしたｆ−１（ｒ）を用いることができる。その場合、上記の比較器と同様の機能を有する回路は、−ΔＥ／Ｔがｆ−１（ｒ）より大きいとき１を出力する回路でよいことがわかる。さらに温度パラメータＴが正であることから、その回路は、−ΔＥがＴ・ｆ−１（ｒ）より大きいとき１を出力する回路でよい。
【００７２】
選択法則適用部３１ｄは、入力される一様乱数ｒを上記のｆ−１（ｒ）の値に変換する変換テーブルを用いて、ｆ−１（ｒ）の値を出力する。メトロポリス法が適用される場合、ｆ−１（ｒ）は、ｌｎ（ｒ）である。変換テーブルは、たとえば、ＲＡＭ（Random Access Memory）、フラッシュメモリなどのメモリに記憶されている。
【００７３】
乗算器３１ｅは、制御回路２１ｆから供給される温度パラメータＴと、ｆ−１（ｒ）との積（Ｔ・ｆ−１（ｒ））を出力する。Ｔ・ｆ−１（ｒ）は、熱励起エネルギーに相当する。
【００７４】
比較回路３１ｆは、オフセット加算部３１ｂによる加算結果と、Ｔ・ｆ−１（ｒ）とを比較し、加算結果が、Ｔ・ｆ−１（ｒ）より大きい場合、フラグ情報としてｆｌｇ１＝１を出力し、Ｔ・ｆ−１（ｒ）より小さい場合、ｆｌｇ１＝０を出力する。
【００７５】
以下、第２の実施の形態の最適化装置２０の動作例を説明する。
制御部２２の情報取得部２２ａは、イジングモデル情報（全ビット数Ｎ、重み係数群Ｗ）、分解能Ｒ、基準値Ａｍｉｎ，Ａｍａｘを、たとえば、図示しない制御装置から取得する。そして、Ｔｍａｘ計算部２２ｂとＴｍｉｎ計算部２２ｃは、情報取得部２２ａが取得した情報に基づいて、温度パラメータＴの最高値Ｔｍａｘと最低値Ｔｍｉｎとを決定し、送信部２２ｄは、最高値Ｔｍａｘと最低値Ｔｍｉｎを演算部２１に送信する。
【００７６】
その後、演算部２１は、前述の式（１）に示した確率で状態遷移を許容してビットの値の更新を行う処理を、イタレーション回数Ｎｉｔ、繰り返す。演算部２１の制御回路２１ｆは、ビットの更新を行う処理が、所定回数（＜Ｎｉｔ）、繰り返されるごとに、温度パラメータＴの値を温度下降制御情報Ｔｄに基づいて小さくしていく。温度パラメータＴの初期値は最高値Ｔｍａｘであり、終値は最低値Ｔｍｉｎである。
【００７７】
図６は、温度パラメータＴの制御例を示す図である。図６において、横軸は更新処理回数を表し、縦軸は温度パラメータＴの値を表している。
温度パラメータＴは、最高値Ｔｍａｘからビットの値の更新を行う処理の回数（更新処理回数）が大きくなるごとに小さくなっている。更新処理回数が大きいほど、温度パラメータＴが下がる度合いが小さくなり、最低値Ｔｍｉｎに達したときに、制御回路２１ｆによる温度パラメータＴの制御が終わる。なお、図６では更新処理回数が増えるとともに、連続的に温度パラメータＴが減少しているように見えるが、前述のように各温度パラメータＴの値で、所定回数の更新処理が行われる。
【００７８】
演算部２１は、ビットの値の更新を行う処理が、イタレーション回数Ｎｉｔ、繰り返されたときの各ビットの値（状態ｘｏｕｔ）を基底状態の探索結果として出力する。また、演算部２１は、そのときのエネルギーＥを出力する。
【００７９】
以上のような第２の実施の形態の最適化装置２０は、イジングモデル情報から、取り得るエネルギーの変化分を決定し、その変化分に基づいて基底状態の探索時の温度パラメータＴの範囲を決定する。これにより、計算対象の最適化問題に応じた温度パラメータＴの範囲で演算部１１がシミュレーテッド・アニーリング法を用いた演算を行うことが可能になる。このため、状態遷移の許容確率が適切になり最適化問題の解の精度の悪化を抑制できる。
【００８０】
（第３の実施の形態）
図７は、第３の実施の形態の最適化装置の一例を示す図である。図７において、図３に示した要素と同じ要素については同一符号が付されている。
【００８１】
第３の実施の形態の最適化装置４０は、演算部４１、制御部４２を有する。
演算部４１は、イジングモデル情報と、温度パラメータＴとに基づいて、レプリカ交換法により、イジングモデルの基底状態を探索する。演算部４１は、それぞれ同じＮ個のビットについての前述の更新処理を行う複数のレプリカを有する。各レプリカには、異なる温度パラメータＴが設定され、更新処理が所定回数に達するごとに、レプリカ間のエネルギー差と温度差（温度パラメータＴの値の差）に応じて、レプリカ間で状態または温度パラメータＴの値が交換される。
【００８２】
演算部４１が用いるイジングモデル情報には、重み係数群Ｗ、バイアス係数群ｂ、各ビットの初期値ｘｉｎｉが含まれる。さらに、図７の例では、演算部４１には、イタレーション回数Ｎｉｔが供給されている。イジングモデル情報や、イタレーション回数Ｎｉｔは、たとえば、ＰＣなどの制御装置から供給される。
【００８３】
演算部４１は、たとえば、各レプリカにおいて、前述の更新処理を、イタレーション回数Ｎｉｔ、繰り返したとき、最低のエネルギーＥを示したレプリカにおいて、最低のエネルギーＥを示したときの各ビットの値（状態ｘｏｕｔ）を基底状態の探索結果として出力する。また、演算部４１は、その最低のエネルギーＥを出力する。演算部４１の回路例については後述する。
【００８４】
制御部４２の情報取得部４２ａは、第２の実施の形態の最適化装置２０の制御部２２の情報取得部２２ａが取得する情報のほか、演算部４１のレプリカ数ｎを取得する。レプリカ数ｎも、たとえば、ＰＣなどの制御装置から供給される。
【００８５】
さらに、制御部４２は、第２の実施の形態の最適化装置２０の制御部２２と異なり、Ｔｓｃ計算部４２ｂを有する。
Ｔｓｃ計算部４２ｂは、情報取得部４２ａが取得したレプリカ数ｎと、Ｔｍａｘ計算部２２ｂとＴｍｉｎ計算部２２ｃが決定した温度パラメータＴの最高値Ｔｍａｘと最低値Ｔｍｉｎとを受ける。そして、Ｔｓｃ計算部４２ｂは、レプリカ数ｎ、最高値Ｔｍａｘ、最低値Ｔｍｉｎに基づいて、最高値Ｔｍａｘから最低値Ｔｍｉｎの範囲で、ｎ個の温度パラメータＴ１，Ｔ２，Ｔ３，…，Ｔｎを含む温度スケジュール情報Ｔｓｃを計算する。
【００８６】
温度パラメータＴ１〜Ｔｎは、たとえば、Ｔ１＝Ｔｍｉｎ、Ｔ２＝２×（Ｔｍａｘ−Ｔｍｉｎ）／（Ｔｎ−１）、Ｔ３＝３×（Ｔｍａｘ−Ｔｍｉｎ）／（Ｔｎ−１）、…、Ｔｎ＝Ｔｍａｘなどのように計算される。
【００８７】
なお、温度パラメータＴ１〜Ｔｎは等差数列または等比数列になるように生成されてもよい。
送信部４２ｃは、温度スケジュール情報Ｔｓｃを演算部４１に送信する。
【００８８】
（演算部４１の例）
図８は、レプリカ交換法により基底状態の探索を行う演算部の一例を示す図である。
演算部４１は、ｎ個のレプリカ４１ａ１，４１ａ２，…，４１ａｎと、交換制御部４１ｂを有する。
【００８９】
レプリカ４１ａ１〜４１ａｎの各々は、図４に示したような記憶部２１ａ、演算回路部２１ｂ、選択回路部２１ｃ、状態更新部２１ｄ、エネルギー更新部２１ｅを有する。レプリカ４１ａ１〜４１ａｎには、同じ重み係数群Ｗが記憶され、同じバイアス係数群ｂ、同じ初期値ｘｉｎｉが設定される。しかし、レプリカ４１ａ１〜４１ａｎには、交換制御部４１ｂによって、それぞれ異なる温度パラメータＴ（温度パラメータＴ１〜Ｔｎの何れか）が設定され、レプリカ４１ａ１〜４１ａｎは、その温度パラメータＴを用いてビットの値を更新する処理を行う。
【００９０】
なお、レプリカ４１ａ１〜４１ａｎの各々は、現時点におけるエネルギーの最低値と、その最低値が得られたときの状態を保持する。
交換制御部４１ｂは、温度スケジュール情報Ｔｓｃに基づいて、ｎ個のレプリカ４１ａ１〜４１ａｎに、それぞれ異なる温度パラメータＴを設定する。また、交換制御部４１ｂは、たとえば、レプリカ４１ａ１〜４１ａｎでの更新処理回数が所定回数に達するたびに、レプリカ４１ａ１〜４１ａｎにおけるエネルギーを観測する。そして、交換制御部４１ｂは、レプリカ４１ａ１〜４１ａｎのうちの２つにおけるエネルギーと温度パラメータを用い、以下の式（７）で表される交換確率に基づいて２つのレプリカに設定された温度パラメータＴを交換する。なお、交換制御部４１ｂは、温度パラメータＴの代りに、２つのレプリカの状態を交換してもよい。
【００９１】
ｐｉｊ＝ｆ（（１／Ｔｉ−１／Ｔｊ）（Ｅｉ−Ｅｊ））            （７）
式（７）において、Ｔｉは、レプリカ４１ａ１〜４１ａｎのうち、ｉ番目のレプリカに設定された温度パラメータであり、Ｔｊは、レプリカ４１ａ１〜４１ａｎのうち、ｊ番目のレプリカに設定された温度パラメータである。また、Ｅｉは、レプリカ４１ａ１〜４１ａｎのうち、ｉ番目のレプリカにおけるエネルギー、Ｅｊは、レプリカ４１ａ１〜４１ａｎのうち、ｊ番目のレプリカにおけるエネルギーである。また、式（７）において、関数ｆは、たとえば、式（１）と同じものであり、式（１）のｍｉｎ［１，ｅｘｐ（−ΔＥ／Ｔ）］の−ΔＥ／Ｔの代りに、（１／Ｔｉ−１／Ｔｊ）（Ｅｉ−Ｅｊ）が用いられる。
【００９２】
このような交換を行ってもそれぞれの温度パラメータＴの値における状態の確率分布はその温度パラメータＴの値に対するボルツマン分布に収束する。なお、交換が行われる２つのレプリカは、交換確率が小さくなりすぎないように、設定される温度パラメータＴの値が近いものが選択される。
【００９３】
交換制御部４１ｂは、レプリカ４１ａ１〜４１ａｎにおけるビットの値の更新処理の回数が、イタレーション回数Ｎｉｔに達したとき、レプリカ４１ａ１〜４１ａｎの各々におけるエネルギーの最低値と、その最低値が得られたときの状態を取得する。そして、交換制御部４１ｂは、レプリカ４１ａ１〜４１ａｎの各々におけるエネルギーの最低値のうち、最も低いエネルギーＥと、そのエネルギーＥが得られたときの状態ｘｏｕｔを出力する。
【００９４】
以下、第３の実施の形態の最適化装置４０の動作例を説明する。
図９は、第３の実施の形態の最適化装置の制御部の動作の流れの一例を示すフローチャートである。
【００９５】
最適化装置４０の制御部４２の情報取得部４２ａは、イジングモデル情報（全ビット数Ｎ、重み係数群Ｗ）、レプリカ数ｎ、分解能Ｒ、基準値Ａｍｉｎ，Ａｍａｘを、たとえば、図示しない制御装置から取得する（ステップＳ１０）。そして、Ｔｍａｘ計算部２２ｂとＴｍｉｎ計算部２２ｃは、情報取得部２２ａが取得した情報に基づいて、温度パラメータＴの最高値Ｔｍａｘと最低値Ｔｍｉｎとを決定する（ステップＳ１１，Ｓ１２）。その後、Ｔｓｃ計算部４２ｂは、レプリカ数ｎ、最高値Ｔｍａｘ、最低値Ｔｍｉｎに基づいて、最高値Ｔｍａｘから最低値Ｔｍｉｎの範囲で、ｎ個の温度パラメータＴ１，Ｔ２，Ｔ３，…，Ｔｎを含む温度スケジュール情報Ｔｓｃを計算する（ステップＳ１３）。そして、送信部４２ｃは、温度スケジュール情報Ｔｓｃを演算部４１に送信する（ステップＳ１４）。
【００９６】
これにより制御部４２の処理が終了する。その後、演算部４１の処理が行われる。なお、ステップＳ１１，Ｓ１２は処理の順序が逆であってもよい。
演算部４１の各レプリカ４１ａ１〜４１ａｎは、前述の式（１）に示した確率で状態遷移を許容してビットの値の更新を行う処理を、イタレーション回数Ｎｉｔ、繰り返す。交換制御部４１ｂは、レプリカ４１ａ１〜４１ａｎでの更新処理回数が所定回数に達するたびに、式（７）で表される交換確率に基づいて２つのレプリカに設定された温度パラメータＴを交換する。そして、交換制御部４１ｂは、レプリカ４１ａ１〜４１ａｎでの更新処理回数が、イタレーション回数Ｎｉｔに達したとき、レプリカ４１ａ１〜４１ａｎの各々におけるエネルギーの最低値と、その最低値が得られたときの状態を取得する。そして、交換制御部４１ｂは、レプリカ４１ａ１〜４１ａｎの各々におけるエネルギーの最低値のうち、最も低いエネルギーＥと、そのエネルギーＥが得られたときの状態ｘｏｕｔを出力する。
【００９７】
以上のような第３の実施の形態の最適化装置４０は、イジングモデル情報から、取り得るエネルギーの変化分を決定し、その変化分に基づいて基底状態の探索時の温度パラメータＴの範囲を決定する。これにより、計算対象の最適化問題に応じた温度パラメータＴの範囲で演算部４１が、レプリカ交換法を用いた演算を行うことが可能になる。このため、状態遷移の許容確率が適切になり最適化問題の解の精度の悪化を抑制できる。
【００９８】
（第４の実施の形態）
図１０は、第４の実施の形態の最適化装置の一例を示す図である。図１０において、図３に示した要素と同じ要素については同一符号が付されている。
【００９９】
第４の実施の形態の最適化装置５０において、制御部５１の情報取得部５１ａは、分解能Ｒ及び基準値Ａｍｉｎ，Ａｍａｘと、イジングモデル情報として、全ビット数Ｎ、重み係数群Ｗのほか、バイアス係数群ｂを、たとえば、図示しない制御装置から取得する。
【０１００】
そして、Ｔｍａｘ計算部５１ｂは、重み係数群Ｗと、全ビット数Ｎと、バイアス係数群ｂとに基づいて、以下の式（８）を計算することで、ｍａｘ（ΔＥ）を決定する。
【０１０１】
【数４】
2020046718.tif 000006
【０１０２】
式（８）において、ｍａｘ（｜ｂ｜）は、イジングモデル情報に含まれる全ビットのそれぞれについてのバイアス係数の絶対値のうち、最大の値を示す。
その後、Ｔｍａｘ計算部５１ｂは、決定したｍａｘ（ΔＥ）と、基準値Ａｍａｘに基づいて、式（５）を計算することで、温度パラメータＴの最高値Ｔｍａｘを決定する。
【０１０３】
最適化装置５０のその他の要素は、第２の実施の形態の最適化装置２０と同じである。
バイアス係数群ｂも考慮してｍａｘ（ΔＥ）を決定することで、より高精度なｍａｘ（ΔＥ）が得られる。そして、そのｍａｘ（ΔＥ）を用いて温度パラメータＴの最高値Ｔｍａｘを決定することで、計算対象の最適化問題に応じた温度パラメータＴの範囲をより適切に設定可能になる。
【０１０４】
（第５の実施の形態）
図１１は、第５の実施の形態の最適化装置の一例を示す図である。図１１において、図７に示した要素と同じ要素については同一符号が付されている。
【０１０５】
第５の実施の形態の最適化装置６０において、制御部６１の情報取得部６１ａは、分解能Ｒ、基準値Ａｍｉｎ，Ａｍａｘ、レプリカ数ｎ、全ビット数Ｎ及び重み係数群Ｗのほか、バイアス係数群ｂを、たとえば、図示しない制御装置から取得する。
【０１０６】
そして、Ｔｍａｘ計算部６１ｂは、重み係数群Ｗと、全ビット数Ｎと、バイアス係数群ｂとに基づいて、前述の式（８）を計算することで、ｍａｘ（ΔＥ）を決定する。
その後、Ｔｍａｘ計算部６１ｂは、決定したｍａｘ（ΔＥ）と、基準値Ａｍａｘに基づいて、式（５）を計算することで、温度パラメータＴの最高値Ｔｍａｘを決定する。
【０１０７】
最適化装置６０のその他の要素は、第３の実施の形態の最適化装置４０と同じである。
上記のような第５の実施の形態の最適化装置６０でも、第４の実施の形態の最適化装置５０と同様の効果が得られる。
【０１０８】
（第６の実施の形態）
図１２は、第６の実施の形態の最適化装置の一例を示す図である。図１２において、図１０に示した要素と同じ要素については同一符号が付されている。
【０１０９】
第６の実施の形態の最適化装置７０は、図１０に示した最適化装置５０とほぼ同様の構成であるが、制御部７１のＴｍａｘ計算部７１ａは、各ビットについてのエネルギー変化の最大値を、以下の式（９）により計算する。
【０１１０】
【数５】
2020046718.tif 000007
【０１１１】
式（９）において、ｍａｘ（ΔＥｉ）は、ｉ番目（ｉ＝１〜Ｎ）のビットについての、エネルギー変化の最大値を表す。式（５）の計算に用いるｍａｘ（ΔＥ）は、全ビットのそれぞれが変化するときのエネルギー変化の最大値のうち、最大の値を示すものであり、以下の式（１０）のように表せる。
【０１１２】
【数６】
2020046718.tif 000008
【０１１３】
Ｔｍａｘ計算部７１ａは、全ビットについてのエネルギー変化の最大値（ｍａｘ（ΔＥｉ））からｍａｘ（ΔＥ）を計算し、決定したｍａｘ（ΔＥ）と、基準値Ａｍａｘに基づいて、式（５）を計算することで、温度パラメータＴの最高値Ｔｍａｘを決定する。
【０１１４】
最適化装置７０のその他の要素は、第４の実施の形態の最適化装置５０と同じである。
図１３は、第６の実施の形態の最適化装置の制御部の動作の流れの一例を示すフローチャートである。
【０１１５】
最適化装置７０の制御部７１の情報取得部５１ａは、イジングモデル情報（全ビット数Ｎ、重み係数群Ｗ、バイアス係数群ｂ）、分解能Ｒ、基準値Ａｍｉｎ，Ａｍａｘを、たとえば、図示しない制御装置から取得する（ステップＳ２０）。そして、Ｔｍｉｎ計算部２２ｃは、分解能Ｒと基準値Ａｍｉｎに基づいて前述の式（４）を計算することで、最低値Ｔｍｉｎを決定する（ステップＳ２１）。
【０１１６】
Ｔｍａｘ計算部７１ａは、最高値Ｔｍａｘの決定処理（ステップＳ２２）として、以下のステップＳ２２ａ，Ｓ２２ｂ，Ｓ２２ｃの処理を行う。Ｔｍａｘ計算部７１ａは、各ビットについてのエネルギー変化の最大値（ｍａｘ（ΔＥｉ））を計算し（ステップＳ２２ａ）、各ビットについてのエネルギー変化の最大値（ｍａｘ（ΔＥｉ））からｍａｘ（ΔＥ）を計算する（ステップＳ２２ｂ）。そして、Ｔｍａｘ計算部７１ａは、決定したｍａｘ（ΔＥ）と、基準値Ａｍａｘに基づいて、温度パラメータＴの最高値Ｔｍａｘを計算する（ステップＳ２２ｃ）。
【０１１７】
そして、送信部２２ｄは、最低値Ｔｍｉｎと最高値Ｔｍａｘを演算部２１に送信する（ステップＳ２３）。
これにより制御部７１の処理が終了する。その後、前述の演算部２１の処理が行われる。なお、ステップＳ２１，Ｓ２２は処理の順序が逆であってもよい。
【０１１８】
上記のような第６の実施の形態の最適化装置７０は、各ビットについてのエネルギー変化の最大値からｍａｘ（ΔＥ）を決定することで、より高精度なｍａｘ（ΔＥ）が得られる。そして、そのｍａｘ（ΔＥ）を用いて温度パラメータＴの最高値Ｔｍａｘを決定することで、計算対象の最適化問題に応じた温度パラメータＴの範囲をより適切に設定可能になる。
【０１１９】
（第７の実施の形態）
図１４は、第７の実施の形態の最適化装置の一例を示す図である。図１４において、図１１に示した要素と同じ要素については同一符号が付されている。
【０１２０】
第７の実施の形態の最適化装置８０は、図１１に示した最適化装置５０とほぼ同様の構成であるが、制御部８１のＴｍａｘ計算部８１ａは、各ビットについてのエネルギー変化の最大値を、前述の式（９）により計算する。そして、Ｔｍａｘ計算部８１ａは、式（５）の計算に用いるｍａｘ（ΔＥ）を、前述の式（１０）により計算し、ｍａｘ（ΔＥ）と、基準値Ａｍａｘに基づいて、式（５）を計算することで、温度パラメータＴの最高値Ｔｍａｘを決定する。
【０１２１】
最適化装置８０のその他の要素は、第５の実施の形態の最適化装置６０と同じである。
図１５は、第７の実施の形態の最適化装置の制御部の動作の流れの一例を示すフローチャートである。
【０１２２】
最適化装置８０の制御部８１の情報取得部６１ａは、分解能Ｒ、基準値Ａｍｉｎ，Ａｍａｘ、レプリカ数ｎ、全ビット数Ｎ及び重み係数群Ｗのほか、バイアス係数群ｂを、たとえば、図示しない制御装置から取得する（ステップＳ３０）。そして、Ｔｍｉｎ計算部２２ｃは、分解能Ｒと基準値Ａｍｉｎに基づいて前述の式（４）を計算することで、最低値Ｔｍｉｎを決定する（ステップＳ３１）。
【０１２３】
Ｔｍａｘ計算部８１ａは、最高値Ｔｍａｘの決定処理（ステップＳ３２）として、以下のステップＳ３２ａ，Ｓ３２ｂ，Ｓ３２ｃの処理を行う。Ｔｍａｘ計算部８１ａは、各ビットについてのエネルギー変化の最大値（ｍａｘ（ΔＥｉ））を計算し（ステップＳ３２ａ）、各ビットについてのエネルギー変化の最大値（ｍａｘ（ΔＥｉ））からｍａｘ（ΔＥ）を計算する（ステップＳ３２ｂ）。そして、Ｔｍａｘ計算部８１ａは、決定したｍａｘ（ΔＥ）と、基準値Ａｍａｘに基づいて、温度パラメータＴの最高値Ｔｍａｘを計算する（ステップＳ３２ｃ）。
【０１２４】
その後、Ｔｓｃ計算部４２ｂは、レプリカ数ｎ、最高値Ｔｍａｘ、最低値Ｔｍｉｎに基づいて、最高値Ｔｍａｘから最低値Ｔｍｉｎの範囲で、ｎ個の温度パラメータＴ１，Ｔ２，Ｔ３，…，Ｔｎを含む温度スケジュール情報Ｔｓｃを計算する（ステップＳ３３）。そして、送信部４２ｃは、温度スケジュール情報Ｔｓｃを演算部４１に送信する（ステップＳ３４）。
【０１２５】
これにより制御部８１の処理が終了する。その後、演算部４１の処理が行われる。なお、ステップＳ３１，Ｓ３２は処理の順序が逆であってもよい。
上記のような第７の実施の形態の最適化装置８０でも、第６の実施の形態の最適化装置７０と同様の効果が得られる。
【０１２６】
なお、上記の最適化装置７０，８０では、制御部７１，８１は、バイアス係数群ｂの影響を考慮してｍａｘ（ΔＥ）を決定したが、バイアス係数群ｂに対して重み係数群Ｗが支配的な場合には、バイアス係数群ｂの影響を考慮しなくてもよい。
【０１２７】
ところで、上記の最適化装置１０，２０，４０，５０，６０，７０，８０において制御部１２，２２，４２，５１，６１，７１，８１の機能は、たとえば、ＰＣなどの制御装置内のプロセッサが制御プログラムを実行することで実現してもよい。
【０１２８】
図１６は、制御装置のハードウェア例を示す図である。
制御装置９０は、ＣＰＵ９１、ＲＡＭ９２、ＨＤＤ（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）、ＤＶＤ及びＤＶＤ−Ｒ／ＲＷが含まれる。プログラムは、可搬型の記録媒体に記録されて配布されることがある。その場合、可搬型の記録媒体から他の記録媒体（たとえば、ＨＤＤ９３）にプログラムをコピーして実行してもよい。
【０１３９】
以上、実施の形態に基づき、本発明の最適化装置、最適化装置の制御方法及び最適化装置の制御プログラムの一観点について説明してきたが、これらは一例にすぎず、上記の記載に限定されるものではない。
【符号の説明】
【０１４０】
１０  最適化装置
１１  演算部
１２  制御部
【図１】
2020046718.tif 000009
【図２】
2020046718.tif 000010
【図３】
2020046718.tif 000011
【図４】
2020046718.tif 000012
【図５】
2020046718.tif 000013
【図６】
2020046718.tif 000014
【図７】
2020046718.tif 000015
【図８】
2020046718.tif 000016
【図９】
2020046718.tif 000017
【図１０】
2020046718.tif 000018
【図１１】
2020046718.tif 000019
【図１２】
2020046718.tif 000020
【図１３】
2020046718.tif 000021
【図１４】
2020046718.tif 000022
【図１５】
2020046718.tif 000023
【図１６】
2020046718.tif 000024