(57)【要約】【課題】求解対象の問題毎に適切な温度範囲を自動的に設定可能にすること。【解決手段】最適化装置１０は、基底状態の探索を実行して複数個の局所解を出力する。情報処理装置２０は、初期温度計算部２２と温度補正部２３とを有する。初期温度計算部２２は、自ニューロン以外の複数の他のニューロンとの接続の有無を示す重み値から得られたエネルギー増分の最大値に基づいて初期温度を計算する。温度補正部２３は、最適化装置１０が出力する複数個の局所解を対応するエネルギーの昇順に並べた結果について、各局所解に対応する各状態変数の間を１ビット変化させた複数の状態変数の各々に対応する各エネルギー値の上昇値のうち、最大の上昇値に基づいて補正温度を算出する。【選択図】図１
2020173579.tif 000002
【特許請求の範囲】
【請求項１】
基底状態の探索を実行して複数個の局所解を出力する最適化装置と、
自ニューロン以外の複数の他のニューロンとの接続の有無を示す重み値から得られたエネルギー増分の最大値に基づいて初期温度を計算する初期温度計算部と、前記最適化装置が出力する前記複数個の局所解を対応するエネルギーの昇順に並べた結果について、各局所解に対応する各状態変数の間を１ビット変化させた複数の状態変数の各々に対応する各エネルギー値の上昇値のうち、最大の上昇値に基づいて補正温度を算出する温度補正部とを備える情報処理装置と、
を有する最適化システム。
【請求項２】
前記初期温度計算部は、バイアス値と前記重み値とから得られた前記エネルギー増分の最大値に基づいて前記初期温度を計算する、請求項１記載の最適化システム。
【請求項３】
前記温度補正部は、エネルギーの大きい方の局所解からエネルギーの小さい方の局所解へ、各局所解に対応する各状態変数の間を１ビット変化させた前記複数の状態変数の各々に対応する各エネルギー値の上昇値のうち、最大の上昇値に基づいて補正温度を算出する、請求項１または２記載の最適化システム。
【請求項４】
前記温度補正部は、１ビット変化させる状態変数を選択する際に、変化させる候補の状態変数のうち、当該状態変数の変化に応じたエネルギー値の上昇値が最小になる状態変数を選択する、請求項３記載の最適化システム。
【請求項５】
前記初期温度計算部は、前記最大値に基づいて、前記エネルギー増分が前記最大値となる状態変数の変化が第１の確率で許容されるように前記初期温度を計算し、
前記温度補正部は、前記最大の上昇値に基づいて、エネルギー値の上昇値が前記最大の上昇値となる状態変数の変化が第２の確率で許容されるように前記補正温度を算出する、
請求項１乃至４の何れか１項に記載の最適化システム。
【請求項６】
前記温度補正部は、前記最適化装置により前回の補正温度を用いて出力された前記複数個の局所解に基づいて今回の補正温度を算出する、請求項１乃至５の何れか１項に記載の最適化システム。
【請求項７】
前記初期温度および前記補正温度は、前記最適化装置に設定される温度範囲のうちの最高温度であり、
前記初期温度計算部は、前記最適化装置におけるエネルギーの分解能に基づいて前記温度範囲のうちの最低温度を計算する、
請求項１乃至６の何れか１項に記載の最適化システム。
【請求項８】
情報処理装置の初期温度計算部が、自ニューロン以外の複数の他のニューロンとの接続の有無を示す重み値から得られたエネルギー増分の最大値に基づいて初期温度を計算し、
最適化装置が、基底状態の探索を実行して複数個の局所解を出力し、
前記情報処理装置の温度補正部が、前記最適化装置が出力する前記複数個の局所解を対応するエネルギーの昇順に並べた結果について、各局所解に対応する各状態変数の間を１ビット変化させた複数の状態変数の各々に対応する各エネルギー値の上昇値のうち、最大の上昇値に基づいて補正温度を算出する、
最適化システムの制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は最適化システムおよび最適化システムの制御方法に関する。
【背景技術】
【０００２】
ノイマン型コンピュータが不得意とする多変数の最適化問題を解く方法として、イジング型のエネルギー関数（コスト関数や目的関数とも呼ばれる）を用いた最適化装置（イジングマシンやボルツマンマシンとも呼ばれる）がある。最適化装置は、計算対象の問題を、磁性体のスピンの振る舞いを表すモデルであるイジングモデルに置き換えて計算する。
【０００３】
最適化装置は、例えば、ニューラルネットワークを用いてモデル化することもできる。その場合、イジングモデルに含まれる複数のスピンに対応した複数のビットのそれぞれが、他のビットと自身のビットとの相互作用の大きさに対応する重み係数（結合係数とも呼ばれる）とに応じて０または１を出力するニューロンとして機能する。最適化装置は、例えば疑似焼き鈍し法（シミュレーテッド・アニーリング）などの確率的探索法により、上記のようなエネルギー関数の値（エネルギーと言う）の最小値が得られる各ビットの値の組合せを、最適解として求める。
【０００４】
疑似焼き鈍し法では、パラメータとして温度が用いられる（例えば、特許文献１〜３参照）。また、デジタル回路を用いて疑似焼き鈍し法を行うことでエネルギーが最小となる各ビットの値の組合せを計算する最適化装置が提案されている（例えば、特許文献４参照）。提案の最適化装置は、一度に１ビットだけ変化するとしてエネルギー変化を計算し、エネルギー変化と温度に対応するノイズ値との比較に応じてビットの変化を許容するか否かを決定する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平５−１２０２５２号公報
【特許文献２】国際公開第２０１４／１９２１５３号
【特許文献３】特開２０１６−５１３５０号公報
【特許文献４】特開２０１８−６３６２６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
最適化装置で演算対象となる問題では、問題毎に取り得るエネルギーの範囲が異なるために適切な温度範囲を決定することが容易でない。例えば、温度が高過ぎて状態遷移が頻繁に起こり過ぎたり、温度が低過ぎて状態遷移が全く起こらなかったりすることがある。このように、最適化装置に設定する温度が適切でないと最適解への収束が困難になる。
【０００７】
１つの側面では、本発明は、求解対象の問題毎に適切な温度範囲を自動的に設定可能にする最適化システムおよび最適化システムの制御方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
１つの態様では、最適化システムが提供される。この最適化システムは、最適化装置と情報処理装置とを有する。最適化装置は、基底状態の探索を実行して複数個の局所解を出力する。情報処理装置は、初期温度計算部と温度補正部とを備える。初期温度計算部は、自ニューロン以外の複数の他のニューロンとの接続の有無を示す重み値から得られたエネルギー増分の最大値に基づいて初期温度を計算する。温度補正部は、最適化装置が出力する複数個の局所解を対応するエネルギーの昇順に並べた結果について、各局所解に対応する各状態変数の間を１ビット変化させた複数の状態変数の各々に対応する各エネルギー値の上昇値のうち、最大の上昇値に基づいて補正温度を算出する。
【０００９】
また、１つの態様では、最適化システムの制御方法が提供される。
【発明の効果】
【００１０】
１つの側面では、求解対象の問題毎に適切な温度範囲を自動的に設定することが可能となる。
【図面の簡単な説明】
【００１１】
【図１】第１の実施の形態の最適化システムの例を示す図である。
【図２】第２の実施の形態の最適化システムの例を示す図である。
【図３】最適化装置に対する温度設定例を示す図である。
【図４】状態遷移の例を示す図である。
【図５】情報処理装置の機能例を示す図である。
【図６】重み行列の例を示す図である。
【図７】局所解の例を示す図である。
【図８】ビットの変化とエネルギーの変化との関係の例を示す図である。
【図９】最適化システムの動作例を示す図である。
【図１０】情報処理装置による制御例を示すフローチャートである。
【図１１】Ｔｍａｘ補正例を示すフローチャートである。
【図１２】Ｔｍａｘ［ｋ］算出例を示すフローチャートである。
【図１３】複数の局所解からＴｍａｘを算出する具体例を示す図である。
【発明を実施するための形態】
【００１２】
以下、本実施の形態について図面を参照して説明する。
［第１の実施の形態］
第１の実施の形態を説明する。
【００１３】
図１は、第１の実施の形態の最適化システムの例を示す図である。
最適化システム１は、最適化装置１０および情報処理装置２０を有する。
最適化装置１０は、計算対象の問題を変換したイジングモデルに含まれる複数のスピンに対応する複数の状態変数のそれぞれの値の組合せ（状態）のうち、エネルギー関数が最小値となるときの各状態変数の値（基底状態）を探索する。状態変数の値は「ビット」とも呼ばれる。
【００１４】
イジング型のエネルギー関数Ｅ（ｘ）は、例えば以下の式（１）で定義される。
【００１５】
【数１】
2020173579.tif 000003
【００１６】
右辺第１項は、全状態変数から選択可能な２つの状態変数の全組合せについて、漏れと重複なく、２つの状態変数の値と重み係数との積を積算したものである。ｘｉは、ｉ番目の状態変数である。ｘｊは、ｊ番目の状態変数である。Ｗｉｊは、ｉ番目の状態変数とｊ番目の状態変数との間の重み（例えば、結合の強さ）を示す重み値である。なお、Ｗｉｊ＝Ｗｊｉ、Ｗｉｉ＝０である。すなわち、重み行列Ｗ＝｛Ｗｉｊ｝は対角成分が０の対称行列である。
【００１７】
右辺第２項は、全状態変数のそれぞれのバイアス値と状態変数の値との積の総和である。ｂｉは、ｉ番目の状態変数に対するバイアス値を示す。
例えば、イジングモデルにおけるスピンの「−１」は、状態変数の値「０」に対応する。イジングモデルにおけるスピンの「＋１」は、状態変数の値「１」に対応する。
【００１８】
状態変数ｘｉの値が変化して１−ｘｉとなると、状態変数ｘｉの増加分は、Δｘｉ＝（１−ｘｉ）−ｘｉ＝１−２ｘｉと表せる。したがって、エネルギー関数Ｅ（ｘ）に対して、スピン反転（値の変化）に伴うエネルギー変化ΔＥｉは、式（２）で表される。
【００１９】
【数２】
2020173579.tif 000004
【００２０】
ｈｉはローカルフィールド（局所場）と呼ばれ、式（３）で表される。
【００２１】
【数３】
2020173579.tif 000005
【００２２】
最適化装置１０では、各状態変数の値は「ニューロン」と呼ばれる演算処理回路の単位によって保持される。例えば、最適化装置１０はＮ（Ｎは２以上の整数）個のニューロンを有し、Ｎ個のニューロンによりＮ個の状態変数の値を保持する。例えば、ニューロン間の接続関係は、各ニューロンをノード、ニューロン間の接続関係をエッジとしたグラフ１１により表される。例えば、あるニューロンを示すノード１１ａは、接続関係を有する他のニューロンを示すノードとエッジで結ばれる。あるニューロンは、他の全てのニューロンと接続関係をもつこともあるし（全結合）、他の一部のニューロンと接続関係をもつこともある。行列Ｗは、グラフ１１に対応するニューロン間の接続関係（エッジの重みを含む）を表す。Ｗｉｊは、自ニューロン（ｉ番目のニューロン）と自ニューロン以外の複数の他のニューロン（ｉ番目以外のｊ番目のニューロン）との接続の有無を示す重み値であると言える。
【００２３】
最適化装置１０は、基底状態の探索を実行して複数個の局所解を出力する。
ここで、最適化装置１０は、エネルギーＥを最小化する基底状態の探索に、例えば最急降下法を用いることが考えられる。しかし、最急降下法では、一旦、局所解に陥ると脱出できなくなる。そこで、最適化装置１０では、状態変数の値の変化を許容するか否かの決定において、メトロポリス法やギブス法が用いられる。すなわち、最適化装置１０は、ある状態から当該状態よりもエネルギーの低い他の状態への遷移を探索する近傍探索において、エネルギーが下がる状態だけでなく、エネルギーが上がる状態への遷移を確率的に許容する。例えば、メトロポリス法では、エネルギー変化ΔＥの状態変数の値の変化を受け入れる確率（遷移受入確率）Ａは、式（４）で表される。
【００２４】
【数４】
2020173579.tif 000006
【００２５】
式（４）におけるＡ＝ｅｘｐ（−ΔＥ／Ｔ）に対して、両辺の自然対数を取って変形すると式（５）を得る。
【００２６】
【数５】
2020173579.tif 000007
【００２７】
したがって、最適化装置１０は、一様乱数ｕ（０＜ｕ≦１）に対して、エネルギー変化ΔＥが式（６）を満たす場合に、該当の状態変数の値の変化を許容する。
【００２８】
【数６】
2020173579.tif 000008
【００２９】
情報処理装置２０は、最適化装置１０の動作を制御するための各種のパラメータを最適化装置１０に設定する。例えば、シミュレーテッド・アニーリング（ＳＡ：Simulated Annealing）やその応用となるレプリカ交換法では、異なる温度や異なる初期状態などでの各試行において、複数の状態変数の何れかの値を更新する更新処理が多数回繰り返される。例えば、情報処理装置２０により最適化装置１０に設定されるパラメータには、最適化装置１０の起動１回当たりの更新処理のイタレーション数ｍ、更新処理の総イタレーション数Ｍ（Ｍ＞ｍ）、温度、重み行列Ｗおよびバイアス値ｂ＝｛ｂｉ｝などがある。温度は、最高温度Ｔｍａｘおよび最低温度Ｔｍｉｎにより指定される。また、情報処理装置２０は、最高温度Ｔｍａｘから最低温度Ｔｍｉｎまでの温度の下げ方を示す温度スケジュールを最適化装置１０に設定する。
【００３０】
情報処理装置２０は、記憶部２１と初期温度計算部２２と温度補正部２３とを有する。
記憶部２１は、ＲＡＭ（Random Access Memory）などの揮発性記憶装置でもよいし、ＨＤＤ（Hard Disk Drive）やフラッシュメモリなどの不揮発性記憶装置でもよい。初期温度計算部２２および温度補正部２３は、ＣＰＵ（Central Processing Unit）、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＦＰＧＡ（Field Programmable Gate Array）などにより実現される。
【００３１】
記憶部２１は、最適化装置１０に入力する重み行列Ｗおよびバイアス値ｂを記憶する（図１ではバイアス値の図示を省略している）。重み行列Ｗおよびバイアス値ｂは、問題に応じて定められる。
【００３２】
初期温度計算部２２は、重み値から得られたエネルギー増分の最大値に基づいて初期温度Ｔ１における最高温度Ｔｍａｘを計算する。また、初期温度計算部２２は、エネルギーの分解能（すなわち、最適化装置１０において計算可能なエネルギー増分の最小値）に基づいて初期温度Ｔ１における最低温度Ｔｍｉｎを計算する。
【００３３】
まず、初期温度計算部２２による最低温度Ｔｍｉｎの計算方法を説明する。
初期温度計算部２２は、最低温度Ｔｍｉｎを式（５）に基づいて決定する。例えば、初期温度計算部２２は、エネルギーの分解能が１の場合（すなわち、Ｅが整数値の場合）、ΔＥ＝１の時の遷移受入確率Ａ＝ａ１になる温度として、最低温度Ｔｍｉｎを計算する。遷移受入確率Ａ＝ａ１は、初期温度計算部２２に予め与えられる（ａ１を任意に設定可能にすることもできる）。一例では、ａ１＝０．００１であり、この場合、Ｔｍｉｎ＝０．１４５程度である。ただし、最低温度Ｔｍｉｎは記憶部２１に予め格納されてもよい。その場合、初期温度計算部２２は、最低温度Ｔｍｉｎとして記憶部２１に予め格納された値を用いることができる。
【００３４】
次に、初期温度計算部２２による最高温度Ｔｍａｘの計算方法を説明する。
初期温度計算部２２は、最高温度Ｔｍａｘをエネルギー変化ΔＥが取り得る最大値ｍａｘ（ΔＥ）に基づいて計算する。例えば、初期温度計算部２２は、最大値ｍａｘ（ΔＥ）を取り得る場合の遷移受入確率Ａ＝ａ２になるように最高温度Ｔｍａｘを調整する。遷移受入確率Ａ＝ａ２は、初期温度計算部２２に予め与えられる（ａ２を任意に設定可能にすることもできる）。
【００３５】
具体的には、まず、初期温度計算部２２は、次のように、エネルギー増分の最大値ｍａｘ（ΔＥ）を計算する。式（２）、（３）によれば、ｍａｘ（ΔＥ）は、式（７）で表される。
【００３６】
【数７】
2020173579.tif 000009
【００３７】
ここで、ｍａｘ（ｈｉ）は、ローカルフィールドｈｉの最大値を示す。ローカルフィールドｈｉに関して、重み値Ｗｉｊは、バイアス値ｂｉよりも支配的である場合が多い（例えば、｜Ｗｉｊ｜は｜ｂｉ｜に比べて大きいことが多い）。重み値Ｗｉｊがバイアス値ｂｉよりも支配的である場合、ｍａｘ（ｈｉ）は、式（８）で表される。
【００３８】
【数８】
2020173579.tif 000010
【００３９】
ここで、式（８）の右辺は、重み行列Ｗの行方向の重み値の絶対値和の平均を示す（Ｗは対称行列なので列方向の重み値の絶対値和の平均と考えてもよい）。当該平均は、式（２）、（３）から、取り得るｈｉの最大値のビット平均（状態変数単位の平均）とみなすことができる。
【００４０】
式（５）、（７）、（８）から、式（９）を得る。初期温度計算部２２は、初期温度における最高温度Ｔｍａｘを、式（９）により求める。例えば、Ａ＝ａ２＝０．２５といった値とすることが考えられる。
【００４１】
【数９】
2020173579.tif 000011
【００４２】
なお、初期温度計算部２２は、重み値Ｗｉｊに加え、バイアス値ｂｉを考慮して、初期温度における最高温度Ｔｍａｘを求めてもよい。その場合、ｍａｘ（ΔＥ）は、式（７）、（８）に代えて、式（１０）で表される。
【００４３】
【数１０】
2020173579.tif 000012
【００４４】
式（５）、（１０）から、式（１１）を得る。初期温度計算部２２は、最高温度Ｔｍａｘを、式（１１）により求めてもよい。
【００４５】
【数１１】
2020173579.tif 000013
【００４６】
このように、初期温度計算部２２は、バイアス値と重み値とから得られたエネルギー増分の最大値に基づいて初期温度（Ｔｍａｘ）を計算してもよい。
初期温度計算部２２は、上記のようにして求めた最高温度Ｔｍａｘおよび最低温度Ｔｍｉｎを、初期温度Ｔ１として最適化装置１０に入力する。
【００４７】
情報処理装置２０は、最適化装置１０を起動し、最適化装置１０に入力したパラメータに基づく基底状態の探索を実行させる。情報処理装置２０は、最適化装置１０による、今回のｍ回の更新処理の結果として、最適化装置１０が出力する複数個の局所解を取得する。今回のｍ回の更新処理の結果として得られた複数個の局所解は最適化装置１０により保持される（次回起動時に保持された局所解が利用される）。なお、最適化装置１０が１回の起動当たり１個の局所解のみを出力する場合、情報処理装置２０は、最適化装置１０を複数回起動して複数個の局所解を取得してもよい。
【００４８】
温度補正部２３は、最適化装置１０が出力する複数個の局所解に基づいて、次回の最適化装置１０の起動前に、最適化装置１０に入力する温度を補正する。温度補正部２３により補正される温度は、最高温度Ｔｍａｘである。温度補正部２３は、最低温度Ｔｍｉｎを終始固定とする（エネルギーの分解能は変わらないため）。
【００４９】
温度補正部２３は、複数個の局所解を対応するエネルギーの昇順に並べた結果について、各局所解に対応する各状態変数の間を１ビット変化させた複数の状態変数の各々に対応する各エネルギー値の上昇値のうち、最大の上昇値に基づいて補正温度を算出する。より具体的には、温度補正部２３は、エネルギーの大きい方の局所解からエネルギーの小さい方の局所解へ、各局所解に対応する各状態変数の間を１ビットずつ変化させる過程で得られる、複数の状態変数の各々に対応する各エネルギー値の上昇値を求める。そして、温度補正部２３は、当該各エネルギー値の上昇値のうちの最大の上昇値に基づいて補正温度を算出する。
【００５０】
例えば、温度補正部２３は、最適化装置１０から局所解Ｘ１，Ｘ２，…を取得する。各局所解に対応するエネルギーＥ（Ｘ）は、式（１）により計算される。温度補正部２３は、各局所解とともに各局所解に対応するエネルギーを最適化装置１０から取得してもよい。局所解Ｘ（状態Ｘ）は、Ｎ個の状態変数の値（あるいはＮ個のビット）によって表される。例えば、局所解Ｘ１，Ｘ２，…に対して、Ｅ（Ｘ１）は、Ｅ（Ｘ２）の次に大きいとする。すなわち、局所解Ｘ１，Ｘ２を対応するエネルギーの昇順に並べると局所解Ｘ２，Ｘ１となる。
【００５１】
また、一例として、局所解Ｘ１と局所解Ｘ２との間で異なるビットの数は５であるとする。局所解Ｘ１のうち、局所解Ｘ２と異なるビットを抜き出したビット集合をＸ１’と表す。局所解Ｘ２のうち、局所解Ｘ１と異なるビットを抜き出したビット集合をＸ２’と表す。Ｘ１’＝「００１１０」である。Ｘ２’＝「１１００１」である。ビット集合Ｘ１’，Ｘ２’における同じ桁のビット同士は、局所解Ｘ１，Ｘ２でも同じ桁のビット同士である。
【００５２】
系列３０は、局所解Ｘ１，Ｘ２に対応する各状態変数の間を１ビット変化させた複数の状態変数の各々に対応する各エネルギー値の上昇値のうち、最大の上昇値Ｄｍａｘを例示する。例えば、温度補正部２３は、局所解Ｘ１のうち、局所解Ｘ２と異なるビットを１ビットずつ変化させて、局所解Ｘ１から局所解Ｘ２への遷移をシミュレートする。温度補正部２３は、式（２）、（３）に基づいて、１ビット変化させたときのエネルギー変化ΔＥを、各ビット変化に対して計算する。
【００５３】
系列３０の例では、局所解Ｘ１，Ｘ２の間で異なるビットの数は５なので、温度補正部２３は、５回のビット変化を行い、その過程で５個のΔＥを得る。このとき、温度補正部２３は、次に変化させるビットを、貪欲法（greedy algorithm）によって選択してもよいし、ランダムに選択してもよい。貪欲法では、温度補正部２３は、候補となるビットのうちΔＥが最小になるビットを選択する。
【００５４】
例えば、温度補正部２３は、Ｘ１’＝「００１１０」から１ビットずつ順番に変化させることで、「０１１１０」、「０１１００」、「１１１００」、「１１１０１」、Ｘ２’＝「１１００１」の各ビット集合を得る。なお、これらの各ビット集合の表記では、局所解Ｘ１，Ｘ２で共通するビットの表記が省略されている。温度補正部２３は、各ビット変化に対して、ΔＥを計算する。例示したビット変化のうち、「１１１００」から「１１１０１」に変化したときのΔＥが系列３０における最大の上昇値Ｄｍａｘであるとする。温度補正部２３は、系列３０について、ｍａｘ（ΔＥ）＝Ｄｍａｘとして、式（５）を変形した式（１２）により、最高温度Ｔｍａｘを算出する。
【００５５】
【数１２】
2020173579.tif 000014
【００５６】
なお、エネルギーの上昇値Ｄｍａｘの遷移を許容する遷移受入確率Ａ＝ａ３は、温度補正部２３に対して予め定められる（ａ３を任意に設定可能にすることもできる）。一例では、ａ３＝０．３６７８５である（この場合、ＴｍａｘはＤｍａｘとほぼ同じ値となる）。なお、Ｔｍａｘが０以下となる場合（すなわち、Ｄｍａｘ≦０の場合）は、温度補正部２３は、最高温度Ｔｍａｘとして前回のＴｍａｘの値を使用する。
【００５７】
局所解がＸ１，Ｘ２の２個であれば、温度補正部２３は、局所解Ｘ１，Ｘ２に対して求めた最高温度Ｔｍａｘを補正後の最高温度Ｔｍａｘとして決定してよい。一方、局所解の数が３個以上の場合、温度補正部２３は、同様にして、第１の局所解と、第１の局所解の次にエネルギーの大きな第２の局所解に対し、第２の局所解から第１の局所解への遷移をシミュレートして、当該遷移の過程における最大のΔＥ（最大のエネルギー上昇値）を得る。そして、温度補正部２３は、第２の局所解から第１の局所解への遷移に対して、最高温度Ｔｍａｘの候補値を計算する。温度補正部２３は、こうして２つの局所解の組毎に求めた最高温度Ｔｍａｘの候補値のうちの最大値を、補正後の最高温度Ｔｍａｘとして決定する。なお、温度補正部２３は、２つの局所解の組毎に求めた最高温度Ｔｍａｘの候補値の平均値を、補正後の最高温度Ｔｍａｘとして決定してもよい。
【００５８】
温度補正部２３は、上記のようにして求めた最高温度Ｔｍａｘと、最低温度Ｔｍｉｎとを補正温度Ｔ２として最適化装置１０に入力する。なお、Ｔｍｉｎが変更されないので、温度補正部２３は、補正温度Ｔ２としてＴｍａｘのみを最適化装置１０に入力してもよい。
【００５９】
情報処理装置２０は、最適化装置１０を起動し、最適化装置１０に入力したパラメータに基づく基底状態の探索を実行させる。情報処理装置２０は、最適化装置１０による、次回のｍ回（あるいはｍ’（≠ｍ）回）のイタレーションの結果として、最適化装置１０が出力する複数個の局所解を取得して、上記の方法により温度補正を再度行ってもよい。情報処理装置２０は、温度補正を所定回数だけ行った後は、それ以降は温度補正を行わずに、最適化装置１０による基底状態の探索を継続させてもよい。こうして、最適化装置１０による総イタレーション数Ｍ回の更新処理が完了すると、情報処理装置２０は、最小エネルギーとなった状態を最適化装置１０から取得し、最適化問題の解として出力する。
【００６０】
最適化システム１によれば、初期温度計算部２２により、自ニューロン以外の複数の他のニューロンとの接続の有無を示す重み値から得られたエネルギー増分の最大値に基づいて初期温度が計算される。最適化装置１０により、基底状態の探索を実行して複数個の局所解が出力される。温度補正部２３により、最適化装置１０が出力する複数個の局所解を対応するエネルギーの昇順に並べた結果について、各局所解に対応する各状態変数の間を１ビット変化させた複数の状態変数の各々に対応する各エネルギー値の上昇値のうち、最大の上昇値に基づいて補正温度が算出される。
【００６１】
これにより、求解対象の問題毎に適切な温度範囲を自動的に設定することが可能となる。ここで、最適化装置１０で演算対象となる問題では、問題毎に取り得るエネルギーの範囲が異なるために適切な温度範囲を決定することが容易でない。例えば、温度が高過ぎて状態遷移が頻繁に起こり過ぎたり、温度が低すぎて状態遷移が全く起こらなかったりすることがある。このように、最適化装置１０に設定する温度範囲が適切でないと最適解への収束が難しくなる。また、問題毎に取り得るエネルギーの範囲は、実際に問題を解いてみないと分からない。
【００６２】
これに対し、最適化システム１では、情報処理装置２０により、問題毎に適切な温度範囲が自動的に設定される。このため、新規の問題を解くためのユーザによるパラメータのチューニング作業を不要にできる。適切な温度によって、「状態遷移が頻繁に起こり過ぎる」、あるいは、「状態遷移が全く起こらない」という状況を防ぎ、最適解への収束を容易にすることができる。情報処理装置２０により、局所解からの脱出を適切に促進するような温度パラメータを設定することで、最適化装置１０による演算の実行時間を短縮できる。
【００６３】
［第２の実施の形態］
次に、第２の実施の形態を説明する。
図２は、第２の実施の形態の最適化システムの例を示す図である。
【００６４】
最適化システム２は、最適化装置４０および情報処理装置５０を有する。
最適化装置４０は、ＳＡの手法を用いて、最適化問題に対する解の探索を行う。全体制御部４１、入力部４２、メモリ４３ａ，４３ｂ，４３ｃ，４３ｄ，４３ｅ，４３ｆ，４３ｇ、データフロー制御部４４を有する。また、最適化装置４０は、ＦＩＦＯ（First In / First Out）メモリ（以下、単にＦＩＦＯと言う）４５ａ，４５ｂ，４５ｃ、演算部４６、更新対象選択部４７、乱数生成部４８、出力部４９を有する。最適化装置４０は、例えば、１チップの半導体集積回路により実現できる。
【００６５】
また、最適化装置４０は、情報処理装置５０に接続される。情報処理装置５０は、ＣＰＵ５１、メモリ５２およびバス５３を有する。ＣＰＵ５１およびメモリ５２は、バス５３に接続される。また、最適化装置４０は、バス５３に接続される。
【００６６】
ＣＰＵ５１は、メモリ５２に記憶されているデータを読み出し、バス５３を介して最適化装置４０に当該データを供給する処理や、最適化装置４０が出力するデータを、バス５３を介してメモリ５２に格納する処理などを行う。ＣＰＵ５１は、メモリ５２に記憶されたプログラムを実行する。
【００６７】
メモリ５２は、計算対象の最適化問題によって決まる定数である、バイアスおよび複数の重み係数を記憶する。また、メモリ５２は、状態、エネルギー、最小のエネルギー、状態遷移の促進に用いられるオフセットの初期値などのデータを記憶する。例えば、オフセットは、式（６）の判定において、式（６）の右辺（−ΔＥ）に加算されることがある。メモリ５２は、ＳＤＲＡＭ（Synchronous Dynamic Random Access Memory）などの揮発性の記憶装置、または、フラッシュメモリ、ＥＥＰＲＯＭ（Electrically Erasable Programmable Read Only Memory）やＨＤＤなどの不揮発性の記憶装置である。
【００６８】
最適化装置４０では、全体制御部４１、データフロー制御部４４、演算部４６および更新対象選択部４７により、複数の状態に対する基底状態の探索の演算（複数の試行）が並行して実行される。例えば、データフロー制御部４４、演算部４６および更新対象選択部４７それぞれは、複数の回路部と回路部間に設けられたレジスタとを有し、複数の回路部およびレジスタを用いて、複数の状態（すなわち、各試行）に対する演算をパイプライン処理する。データフロー制御部４４、演算部４６および更新対象選択部４７の構成例については特許第６４６５２２３号公報を参考にできる。
【００６９】
最適化装置４０では、データフロー制御部４４、演算部４６および更新対象選択部４７により、Ｎ個のニューロン、および、Ｎ個のニューロンのうち更新対象のビット（状態変数）を保持するニューロンを選択する構成がデジタル回路によって実現される。最適化装置４０は、Ｎ個のニューロンのセットを複数実現し、パイプライン処理によって、当該複数のセットに対する複数の試行を並列に実行する。
【００７０】
最適化装置４０において、全体制御部４１は、最適化装置４０の起動や終了を制御する。また、全体制御部４１は、データフロー制御部４４に対して、最適化装置４０の１回の起動当たりのイタレーション数ｍを指定する。
【００７１】
入力部４２は、メモリ５２から読み出されたデータを受け、データフロー制御部４４に供給する。
メモリ４３ａ〜４３ｇは、コンテキスト情報を記憶する。７つのメモリ４３ａ〜４３ｇのそれぞれは、例えば１種類のコンテキスト情報を記憶する。メモリ４３ａは各試行における現在の状態を記憶し、メモリ４３ｂは各試行における現在のエネルギーを記憶する。メモリ４３ｃは各試行における現在の最小エネルギーを記憶する。メモリ４３ｄは各試行における現在の最小エネルギーの状態を記憶する。メモリ４３ｅは各試行における現在の温度を記憶する。メモリ４３ｆは各試行における現在のオフセットを記憶する。メモリ４３ｇは、各試行における現在のバイアス（ローカルフィールド）を記憶する。
【００７２】
メモリ４３ａ〜４３ｇは、例えば、ＲＡＭなどの揮発性の記憶装置、または、フラッシュメモリなどの不揮発性の記憶装置である。
なお、メモリ４３ａ〜４３ｇの代わりに、１つのメモリが用いられてもよい。
【００７３】
データフロー制御部４４は、メモリ４３ａ〜４３ｇが保持するコンテキスト情報について、スピン情報と更新対象のエネルギーの変化値とに基づいて、各試行におけるビットの更新制御を繰り返す。
【００７４】
ＦＩＦＯ４５ａは、データフロー制御部４４が出力するデータを所定のクロックサイクル分保持した後、出力する。ＦＩＦＯ４５ｂは、演算部４６が出力するデータを所定のクロックサイクル分保持した後、出力する。ＦＩＦＯ４５ｃは、更新対象選択部４７が出力するデータを所定のクロックサイクル分保持した後、出力する。上記所定のクロックサイクルは、ＦＩＦＯ４５ａ，４５ｂ，４５ｃのエントリ数（ｄｅｐｔｈと呼ばれる場合もある）に依存する。
【００７５】
なお、ＦＩＦＯ４５ａ〜４５ｃは、それぞれ異なるエントリ数を有していてもよい。また、ＦＩＦＯ４５ａ〜４５ｃのうち、１つ、２つまたは全ては無くてもよい。
演算部４６は、乱数生成部４８にて生成された一様乱数ｕ（０＜ｕ≦１）、重み係数、スピン情報、更新制御によって更新された現在の状態および温度Ｔに基づいて、例えばメトロポリス法の場合、式（６）により、複数のエネルギーの変化値の候補を計算する。式（６）を満たすΔＥが、エネルギーの変化値の候補となる。なお、スピン情報は、更新対象のビットの情報である。
【００７６】
更新対象選択部４７は、乱数生成部４８が生成した乱数に基づいて、演算部４６が計算した複数のエネルギーの変化値の候補から、更新対象のエネルギーの変化値を１つ選択する。
【００７７】
乱数生成部４８は、演算部４６と更新対象選択部４７に供給する乱数を生成する。乱数生成部４８は、異なるシードに基づいて複数の乱数を生成してもよい。乱数生成部４８は、例えば、ＬＦＳＲ（Linear Feedback Shift Register）などにより実現できる。
【００７８】
出力部４９は、データフロー制御部４４が生成したデータを最適化装置４０の外部（例えば、メモリ５２）に出力する。
最適化装置４０は、例えば、レプリカ交換法により、ある最適化問題に対するｎ個の状態を並列に処理する。レプリカ交換法では、温度の異なる複数のレプリカを用意し、各レプリカで温度固定として、ＳＡと同じ動作により状態を更新する。そして、一定回数、状態を更新したらレプリカ間のエネルギー差と温度差とに応じてレプリカ間の状態を入れ替えることで、局所解からの脱出を容易にする。最適化装置４０は、ｎ個のレプリカを並列に処理することで、最適化装置４０の１回の起動当たり、ｎ個の局所解を出力する。
【００７９】
図３は、最適化装置に対する温度設定例を示す図である。
ＣＰＵ５１は、最適化装置４０に設定する温度範囲として、最高温度Ｔｍａｘおよび最低温度Ｔｍｉｎを決定する。また、ＣＰＵ５１は、最高温度Ｔｍａｘから最低温度Ｔｍｉｎまでの温度の下げ方（温度スケジュール）を、最適化装置４０に設定する。
【００８０】
図３（Ａ）は、ＳＡにおける温度設定例のグラフ６１を示す。グラフ６１の横軸はビット状態更新回数を示す。グラフ６１の縦軸は温度を示す。ＳＡでは、例えば、ビット状態更新回数ｒに対して、Ｔｒ＋１＝Ｔｒ×ｄｅｃａｙ（ｒ＝１，２，…）とする。ここで、ｄｅｃａｙは、０＜ｄｅｃａｙ＜１の実数であり、例えば、Ｔｍａｘ，Ｔｍｉｎおよびビット状態更新回数ｒから計算される。
【００８１】
図３（Ｂ）は、レプリカ交換法における温度設定例のグラフ６２を示す。グラフ６２の横軸はビット状態更新回数を示す。グラフ６２の縦軸は温度を示す。グラフ６２は、一例として、レプリカ数８の場合である。レプリカ交換法では、ＴｍａｘとＴｍｉｎとの間の温度を個別指定する、あるいは、温度間の間隔（等差や等比など）を指定する。このように、レプリカ交換法では、あるレプリカに対して温度を一定として、一定回数、状態を更新したらレプリカ間のエネルギー差と温度差とに応じて、レプリカ間の状態を入れ替える。ただし、状態に代えて、温度を入れ替えてもよい。
【００８２】
図４は、状態遷移の例を示す図である。
最適化装置４０で演算対象となる問題では、問題毎に取り得るエネルギーの範囲が異なるために適切な温度範囲を決定することが容易でない。
【００８３】
図４（Ａ）は、温度が高過ぎる場合の状態遷移例のグラフ７１を示す。グラフ７１の横軸は状態Ｘを示す。グラフ７１の縦軸はエネルギーＥ（Ｘ）を示す。温度Ｔが高過ぎると、温度Ｔに応じた熱ノイズ（−ｌｎ（ｕ）×Ｔ）に対して、式（６）により、状態遷移が頻繁に発生する。
【００８４】
図４（Ｂ）は、温度が低過ぎる場合の状態遷移例のグラフ７２を示す。グラフ７２の横軸は状態Ｘを示す。グラフ７２の縦軸はエネルギーＥ（Ｘ）を示す。温度Ｔが低過ぎると、温度Ｔに応じた熱ノイズに対して、式（６）により、状態遷移がほとんど起こらない。
【００８５】
このように、最適化装置４０に設定する温度範囲が適切でないと最適解への収束が難しくなる。また、問題毎に取り得るエネルギーの範囲は、実際に問題を解いてみないと分からない。そこで、情報処理装置５０は、最適化装置４０に設定する温度を求解対象の問題毎に適切に設定可能にする機能を提供する。
【００８６】
図５は、情報処理装置の機能例を示す図である。
ＣＰＵ５１は、メモリ５２に記憶されたプログラムを実行することで、制御部５１１、初期温度計算部５１２、温度補正部５１３およびセレクタ５１４の機能を発揮する。制御部５１１、初期温度計算部５１２、温度補正部５１３およびセレクタ５１４は、ＡＳＩＣやＦＰＧＡなどのハードウェアにより実現されてもよい。
【００８７】
制御部５１１は、最適化装置４０の起動および終了を制御する。制御部５１１は、最適化装置４０の総イタレーション数Ｍを分割して、最適化装置４０を複数回起動する。最適化装置４０の起動１回当たりのイタレーション数はｍである。制御部５１１は、初期温度計算部５１２や温度補正部５１３による最適化装置４０に対するパラメータの設定を制御する。
【００８８】
初期温度計算部５１２は、ある最適化問題に関して、最適化装置４０が最初に起動される前に、メモリ５２に記憶された重み行列Ｗおよびバイアス値ｂを読み出す。初期温度計算部５１２は、重み行列Ｗおよびバイアス値ｂに基づいて、初期温度Ｔｓ＝｛Ｔｍａｘ，Ｔｍｉｎ｝を計算する。例えば、初期温度計算部５１２は、エネルギーの分解能が１の場合（エネルギーが整数の場合）、ΔＥ＝１のときの遷移受入確率Ａが例えば０．００１になるＴｍｉｎとして、式（５）により、Ｔｍｉｎ＝０．１４５を求める。
【００８９】
また、重み行列Ｗがバイアス値ｂよりも支配的である場合、初期温度計算部５１２は、式（８）、（９）によりＴｍａｘを計算する。あるいは、重み行列Ｗに加えて、バイアス値ｂも考慮する場合、初期温度計算部５１２は、式（１０）、（１１）によりＴｍａｘを計算する。
【００９０】
このように、初期温度計算部５１２は、重み行列Ｗおよびバイアス値ｂから計算される、状態におけるビット変化に伴うエネルギー変化の最大値に基づいて、エネルギー増分が当該最大値となる状態変数（ビット）の変化が第１の確率で許容されるように初期温度Ｔｓにおける最高温度Ｔｍａｘを計算する。第１の確率（式（９）、（１１）のＡ）として、状態変数の変化を許容し過ぎず、状態変数の変化を制限し過ぎない適度な値（一例では０．２５）が初期温度計算部５１２に予め与えられる。
【００９１】
初期温度計算部５１２は、重み行列Ｗ、バイアス値ｂおよびイタレーション数ｍを最適化装置４０に入力する。また、初期温度計算部５１２は、初期温度Ｔｓ＝｛Ｔｍａｘ，Ｔｍｉｎ｝を、セレクタ５１４に供給する。
【００９２】
温度補正部５１３は、該当の最適化問題に関して、最適化装置４０の２回目以降の起動前に、最適化装置４０に設定する温度を補正する。温度補正部５１３は、最低温度Ｔｍｉｎについては、初期温度計算部５１２により計算されたＴｍｉｎをそのまま用いる。
【００９３】
一方、最高温度Ｔｍａｘについて、温度補正部５１３は次のように、補正後の最高温度を計算する。温度補正部５１３は、最適化装置４０が出力するｎ個の局所解を取得する。温度補正部５１３は、局所解Ｘに対応するエネルギーＥを最適化装置４０から取得してもよいし、局所解Ｘに対応するエネルギーＥを式（１）により計算してもよい。温度補正部５１３は、局所解間の異なるビットに着目し、一方の局所解から他方の局所解へ１ビットずつ近づけていき、１ビット遷移したときの最大エネルギー上昇量（エネルギー値の最大の上昇値）を算出する。温度補正部５１３は、算出された最大エネルギー上昇量から式（１２）を用いて、補正後の最高温度Ｔｍａｘを決定する。
【００９４】
このように、温度補正部５１３は、一方の局所解から他方の局所解への１ビット遷移により得られたエネルギー値の最大の上昇値に基づいて、エネルギーの上昇値が当該最大の上昇値となる状態変数（ビット）の変化が第２の確率で許容されるように補正後の温度（補正温度）Ｔｓにおける最高温度Ｔｍａｘを算出する。第２の確率（式（１２）のＡ）として、状態変数の変化を許容し過ぎず、状態変数の変化を制限し過ぎない適度な値（一例では、０．３６７８５）が温度補正部５１３に予め与えられる。第２の確率は、第１の確率と同じでもよいし異なっていてもよい。
【００９５】
温度補正部５１３は、補正後の温度（補正温度）Ｔｓ＝｛Ｔｍａｘ，Ｔｍｉｎ｝を、セレクタ５１４に供給する。
セレクタ５１４は、ある最適化問題に対して、最適化装置４０が最初に起動される場合には、初期温度計算部５１２から供給された温度（初期温度）Ｔｓを、最適化装置４０に入力する。セレクタ５１４は、当該最適化問題に対して、最適化装置４０が２回目以降に起動される場合には、温度補正部５１３から供給された温度（補正温度）Ｔｓを、最適化装置４０に入力する。これにより、最適化装置４０が最初に起動される場合と、２回目以降に起動される場合とで、最適化装置４０に設定される温度範囲が変更される。
【００９６】
ここで、初期温度計算部５１２が用いる式（８）の右辺の値（Σｉｊ｜Ｗｉｊ｜）／Ｎについて補足する。
図６は、重み行列の例を示す図である。
【００９７】
重み行列Ｗ＝｛Ｗｉｊ｝は、対角成分が０の対称行列である。重み行列Ｗは、状態を表すビットの数がＮ個のとき、Ｎ×Ｎ行列となる。正方形８１は重み行列Ｗを表す。ｉ＝０，ｉ＝１，…，ｉ＝Ｎ−１は、行番号を示す。
【００９８】
（Σｉｊ｜Ｗｉｊ｜）／Ｎは、行方向の重み値の絶対値和の平均を示す。当該平均は、式（２）、（３）で示されるΔＥの計算式により、取り得るｈｉの最大値のビット平均とみなすことができる。なお、重み行列Ｗは、対称行列なので、（Σｉｊ｜Ｗｉｊ｜）／Ｎは列方向の重み値の絶対値和の平均と考えても同じである。
【００９９】
次に、補正温度の計算において、温度補正部５１３が取得する局所解の例を説明する。
図７は、局所解の例を示す図である。
温度補正部５１３は、最適化装置４０からｎ個の局所解を取得する。例えば、温度補正部５１３は、最適化装置４０から取得した局所解のうち、良い解（エネルギーが低い解）を上位ｎ個だけ取得してもよい。
【０１００】
温度補正部５１３は、ｎ個の局所解をエネルギーの昇順に並べ、隣り合う２個の局所解間において、エネルギーの高い方の局所解から、エネルギーの低い方の局所解へ、異なるビットを１ビットずつ選択して、状態を変化させていく。例えば、グラフ９１は、状態ＸとエネルギーＥ（Ｘ）との関係を示す。グラフ９１の横軸は状態Ｘを示す。グラフ９１の縦軸はエネルギーＥ（Ｘ）を示す。局所解Ｘａ，Ｘｂは、ｎ個の局所解をエネルギーの昇順に並べたときに隣り合う２個の局所解である。Ｅ（Ｘａ）＞Ｅ（Ｘｂ）とする。
【０１０１】
図８は、ビットの変化とエネルギーの変化との関係の例を示す図である。
グラフ９２は、局所解Ｘａ，Ｘｂ間において異なるビットの変化とエネルギー変化との関係の例を示す。グラフ９２の横軸は状態Ｘを示す。グラフ９２の縦軸はエネルギーＥ（Ｘ）を示す。ここで、局所解Ｘａと局所解Ｘｂとの間で異なるビットの数は９であるとする。局所解Ｘａのうち局所解Ｘｂと異なるビットを抜き出したビット集合をＸａ’と表す。局所解Ｘｂのうち局所解Ｘａと異なるビットを抜き出したビット集合をＸｂ’と表す。Ｘａ’＝「００１１０１１１０」である。Ｘｂ’＝「１１００１０００１」である。ビット集合Ｘａ’，Ｘｂ’における同じ桁のビット同士は、局所解Ｘａ，Ｘｂでも同じ桁のビット同士である。
【０１０２】
局所解Ｘａ，Ｘｂの間で異なるビットの数は９なので、温度補正部５１３は、９回のビット変化を行い、その過程で９個のΔＥを得る。このとき、温度補正部５１３は、次に変化させるビットを、貪欲法によって選択してもよいし、ランダムに選択してもよい。貪欲法では、温度補正部５１３は、１ビット変化させる候補のビット（状態変数）のうちエネルギー値の上昇値ΔＥが最小になるビットを選択する。例えば、温度補正部５１３は、候補のビットの全てでΔＥが正となる場合は、エネルギー上昇値の最も低いビットを選択する。基底状態の探索では、エネルギー変化の小さい状態がエネルギー変化の大きい状態よりも遷移先として優先的に選択されるため、変化させるビットをランダムに選択するよりも、貪欲法を用いる方が局所解間の遷移をより適切にシミュレートできる。
【０１０３】
例えば、温度補正部５１３は、Ｘａ’＝「００１１０１１１０」から１ビットずつ順番に変化させることで、「０１１１０１１１０」、「０１１１１１１１０」、「０１０１１１１１０」、「１１０１１１１１０」、「１１００１１１１０」、「１１００１１１１１」、「１１００１１１０１」、「１１００１０１０１」、Ｘｂ’＝「１１００１０００１」の各ビット集合を得る。なお、これらの各ビット集合の表記では、局所解Ｘａ，Ｘｂで共通するビットの表記が省略されている。
【０１０４】
温度補正部５１３は、各ビット変化に対して、ΔＥを計算する。例示したビット変化のうち、「１１００１１１１１」から「１１００１１１０１」に変化したときのΔＥが、最大値Ｄｍａｘであるとする。温度補正部５１３は、ｍａｘ（ΔＥ）＝Ｄｍａｘとして、式（１２）により、局所解Ｘａ，Ｘｂに対する最高温度Ｔｍａｘの候補値を算出する。例えば、遷移受入確率Ａ＝０．３６７８５でエネルギーの上昇値Ｄｍａｘの遷移を許容するとした場合、ＴｍａｘはＤｍａｘとほぼ同じ値になる。
【０１０５】
温度補正部５１３は、エネルギーの昇順に並べたときに隣り合う他の局所解の組についても同様にして最高温度Ｔｍａｘの候補値を計算する。温度補正部５１３は、エネルギーの昇順に並べたときに隣り合う局所解の組毎に計算した最高温度Ｔｍａｘの候補値のうちの最高値を、補正後の最高温度Ｔｍａｘとして決定する。なお、Ｔｍａｘが０以下となる場合は、温度補正部５１３は、最高温度Ｔｍａｘとして前回のＴｍａｘの値を使用する。
【０１０６】
図９は、最適化システムの動作例を示す図である。
（Ｓ１）ＣＰＵ５１は、初期温度Ｔｓ＝｛Ｔｍａｘ，Ｔｍｉｎ｝を算出する。ＣＰＵ５１は、最適化装置４０への初期温度Ｔｓの設定を行う。ＣＰＵ５１は、最適化装置４０を起動する。
【０１０７】
（Ｓ２）最適化装置４０は、入力されたパラメータを用いて基底状態の探索を行い、複数個の局所解を出力する。なお、最適化装置４０は、ステップＳ２の結果取得された途中状態を保持する（次回起動時に保持した途中状態から基底状態の探索を行う）。最適化装置４０は、動作を終了する。
【０１０８】
（Ｓ３）ＣＰＵ５１は、最適化装置４０から出力された複数個の局所解（Ｘ，Ｅ）を取得する。ＣＰＵ５１は、最高温度Ｔｍａｘの補正、および、最適化装置４０への補正後の温度（補正温度）Ｔｓの設定を行う。前述のように、最低温度Ｔｍｉｎについては、ステップＳ１で算出された値が用いられる。ＣＰＵ５１は、最適化装置４０を起動する。
【０１０９】
（Ｓ４）最適化装置４０は、入力されたパラメータを用いて基底状態の探索を行い、複数個の局所解を出力する。なお、最適化装置４０は、ステップＳ４の結果取得された途中状態を保持する。最適化装置４０は、動作を終了する。
【０１１０】
（Ｓ５）ＣＰＵ５１は、最適化装置４０から出力された複数個の局所解（Ｘ，Ｅ）を取得する。ＣＰＵ５１は、最高温度Ｔｍａｘの補正、および、最適化装置４０への補正後の温度（補正温度）Ｔｓの設定を行う。前述のように、最低温度Ｔｍｉｎについては、ステップＳ１で算出された値が用いられる。ＣＰＵ５１は、最適化装置４０を起動する。
【０１１１】
（Ｓ６）最適化装置４０は、入力されたパラメータを用いて基底状態の探索を行い、複数個の局所解を出力する。なお、最適化装置４０は、ステップＳ６の結果取得された途中状態を保持する。最適化装置４０は、動作を終了する。
【０１１２】
（Ｓ７）ＣＰＵ５１は、最適化装置４０から出力された複数個の局所解（Ｘ，Ｅ）を取得する。最適化装置４０から取得された局所解のうち、ＣＰＵ５１は、最小エネルギーに対応する解を、最適化問題に対する解として出力する。
【０１１３】
なお、ステップＳ２，Ｓ４，Ｓ６それぞれにおけるイタレーション数はｍである。ただし、ステップＳ２，Ｓ４，Ｓ６におけるイタレーション数は、異なってもよい。また、ＣＰＵ５１は、最適化装置４０の起動毎に、温度補正を行ってもよい。あるいは、ＣＰＵ５１は、総イタレーション数Ｍの前の方の段階では最適化装置４０の起動毎に温度補正を行うが、総イタレーション数Ｍの後の方の段階では温度補正を行わないようにしてもよい。
【０１１４】
図１０は、情報処理装置による制御例を示すフローチャートである。
（Ｓ１０）制御部５１１は、イタレーションカウンタｉｔに０を代入する（ｉｔ＝０）。
【０１１５】
（Ｓ１１）初期温度計算部５１２は、今回の最適化問題に対応する重み行列Ｗ、バイアス値ｂおよび１回起動当たりのイタレーション数ｍを最適化装置４０に設定する。
（Ｓ１２）初期温度計算部５１２は、重み行列Ｗおよびバイアス値ｂに基づいて、式（５）および式（１１）（あるいは式（９））により初期温度Ｔｓ＝（Ｔｍａｘ，Ｔｍｉｎ）を計算する。
【０１１６】
（Ｓ１３）セレクタ５１４は、温度Ｔｓを最適化装置４０に設定する。具体的には、セレクタ５１４は、今回の最適化問題に対する最適化装置４０の初回の起動の際には、初期温度計算部５１２から供給される初期温度Ｔｓを、最適化装置４０に設定する。また、セレクタ５１４は、今回の最適化問題に対する最適化装置４０の２回目以降の起動の際には、温度補正部５１３から供給される補正温度Ｔｓを、最適化装置４０に設定する。
【０１１７】
（Ｓ１４）制御部５１１は、最適化装置４０を起動する。
（Ｓ１５）制御部５１１は、最適化装置４０による演算の終了を待機する。
（Ｓ１６）温度補正部５１３は、ｎ個の局所解（Ｘ，Ｅ）を最適化装置４０から取得する。
【０１１８】
（Ｓ１７）温度補正部５１３は、Ｔｍａｘ補正の処理を実行する。Ｔｍａｘ補正の詳細は後述される。
（Ｓ１８）制御部５１１は、イタレーションカウンタｉｔにｍを加算する（ｉｔ＝ｉｔ＋ｍ）。
【０１１９】
（Ｓ１９）制御部５１１は、イタレーションカウンタｉｔ＞Ｍであるか否かを判定する。ｉｔ＞Ｍの場合、処理が終了する。処理が終了すると、制御部５１１は、最適化装置４０から最適化問題の解を取得する。ｉｔ≦Ｍの場合、ステップＳ１３に処理が進む。ここで、２回目以降にステップＳ１３が実行されるとき、最適化装置４０に設定される温度は、補正後の温度（補正温度）Ｔｓとなる。
【０１２０】
ステップＳ１３〜Ｓ１９で示されるように、温度補正部５１３は、最適化装置４０により前回の補正温度を用いて出力された複数個の局所解に基づいて今回の補正温度を算出することもある。このようにして、温度補正を繰り返し行うことで、より適切な温度を最適化装置４０に設定できる。
【０１２１】
図１１は、Ｔｍａｘ補正例を示すフローチャートである。
Ｔｍａｘ補正の処理は、ステップＳ１７に相当する。
（Ｓ２０）温度補正部５１３は、最適化装置４０からｎ個の局所解を取得する。
【０１２２】
（Ｓ２１）温度補正部５１３は、ｎ個の局所解を、局所解に対応するエネルギーの昇順にソートする。
（Ｓ２２）温度補正部５１３は、ｋに０を代入する（ｋ＝０）。ここで、ｋは、局所解を識別する識別番号である。ｋ＝０，１，２，…であり、ｋの番号が大きいほど、エネルギーが大きい局所解に相当する。
【０１２３】
（Ｓ２３）温度補正部５１３は、局所解［ｋ］と局所解［ｋ＋１］とを選択する。
（Ｓ２４）温度補正部５１３は、選択した局所解［ｋ］および局所解［ｋ＋１］に対して、Ｔｍａｘ［ｋ］算出を実行する。Ｔｍａｘ［ｋ］算出の詳細は後述される。ここで、最高温度候補Ｔｍａｘ［ｋ］は、最高温度Ｔｍａｘのｋ番目の候補値を示す。
【０１２４】
（Ｓ２５）温度補正部５１３は、ｋをインクリメントする（ｋ＝ｋ＋１）。
（Ｓ２６）温度補正部５１３は、ｋがｎ−１に等しい（ｋ＝＝ｎ−１）か否かを判定する。ｋがｎ−１に等しい場合、ステップＳ２７に処理が進む。ｋがｎ−１に等しくない場合、ステップＳ２３に処理が進む。
【０１２５】
（Ｓ２７）温度補正部５１３は、最高温度Ｔｍａｘ＝ｍａｘ（Ｔｍａｘ［ｋ］）（ｋ＝０，１，…，ｎ−２）を計算する。ここで、ｍａｘ（Ｔｍａｘ［ｋ］）は、Ｔｍａｘ［０］，Ｔｍａｘ［１］，…，Ｔｍａｘ［ｎ−２］のうちの最大値を表す。そして、Ｔｍａｘ補正が終了する。
【０１２６】
なお、ステップＳ２７において、Ｔｍａｘ≦０の場合、温度補正部５１３は、前回のＴｍａｘを用いる（この場合、補正を行わないと考えてもよい）。
図１２は、Ｔｍａｘ［ｋ］算出例を示すフローチャートである。
【０１２７】
Ｔｍａｘ［ｋ］算出の処理は、ステップＳ２４に相当する。
（Ｓ３０）温度補正部５１３は、解Ｃ＝局所解［ｋ＋１］とする。
（Ｓ３１）温度補正部５１３は、Ｄｍａｘ＝０とする。
【０１２８】
（Ｓ３２）温度補正部５１３は、解Ｃと局所解［ｋ］間の異なるビット集合Ｓを抽出する。
（Ｓ３３）温度補正部５１３は、解Ｃにおいて集合Ｓに属するビットのΔＥを式（２）、（３）を用いて算出する。温度補正部５１３は、解Ｃにおいて集合Ｓに属するビット毎に、ΔＥを計算する。
【０１２９】
（Ｓ３４）温度補正部５１３は、ΔＥが最小になるビットｓを選択する。例えば、集合Ｓに属する全てのビットに対してΔＥが正となる場合には、温度補正部５１３は、最もエネルギー上昇の低いビットｓを選択する。なお、温度補正部５１３は、貪欲法によりビットｓを選択する他にも、例えば、集合Ｓからランダムにビットｓを選択してもよい。温度補正部５１３は、Ｄ＝ΔＥ［ｓ］とする。ここで、ΔＥ［ｓ］は、解Ｃにおけるビットｓの反転に対するエネルギー変化を示す。
【０１３０】
（Ｓ３５）温度補正部５１３は、Ｄの最大値Ｄｍａｘを更新する。すなわち、温度補正部５１３は、Ｄｍａｘ＝ｍａｘ（Ｄ，Ｄｍａｘ）とする。ｍａｘ（Ｄ，Ｄｍａｘ）は、Ｄと現在のＤｍａｘのうち、大きい方を示す。
【０１３１】
（Ｓ３６）温度補正部５１３は、解Ｃのビットｓを反転させ、集合Ｓからビットｓを除外する。
（Ｓ３７）温度補正部５１３は、集合Ｓが空集合（すなわち、Ｓ＝＝｛｝）であるか否かを判定する。集合Ｓが空集合の場合、ステップＳ３８に処理が進む。集合Ｓが空集合でない場合、ステップＳ３３に処理が進む。ここで、ステップＳ３６において解Ｃのビットｓが反転されると、ローカルフィールドｈｉが変化するため、ビットｓを選択する前にステップＳ３３で再度ΔＥの算出が行われる。
【０１３２】
（Ｓ３８）温度補正部５１３は、最高温度候補Ｔｍａｘ［ｋ］＝Ｄｍａｘ／−ｌｎ（Ａ）を計算する。そして、Ｔｍａｘ［ｋ］算出が終了する。
図１３は、複数の局所解からＴｍａｘを算出する具体例を示す図である。
【０１３３】
図１３では５個の局所解［０］〜［４］に対して、温度補正部５１３がＴｍａｘを算出する例を示す。局所解［０］〜［４］は、識別番号が大きいほど、局所解に対応するエネルギーも大きい。
【０１３４】
温度補正部５１３は、エネルギーの昇順に並べたときに隣り合う局所解の組について、図１２で例示したＴｍａｘ［ｋ］算出を行う。すなわち、局所解［０］〜［４］に対して、図１１のステップＳ２４が４回実行される。ステップＳ２４ａは、局所解［０］，［１］に対するＴｍａｘ［０］算出の処理である。ステップＳ２４ｂは、局所解［１］，［２］に対するＴｍａｘ［１］算出の処理である。ステップＳ２４ｃは、局所解［２］，［３］に対するＴｍａｘ［２］算出の処理である。ステップＳ２４ｄは、局所解［３］，［４］に対するＴｍａｘ［３］算出の処理である。
【０１３５】
そして、温度補正部５１３は、最高温度候補Ｔｍａｘ［０］〜［３］に対して、図１１のステップＳ２７を実行する。すなわち、温度補正部５１３は、最高温度候補Ｔｍａｘ［０］〜［３］のうちの最大値を算出し、算出した最大値を補正後の最高温度Ｔｍａｘと決定する。また、温度補正部５１３は、最高温度候補Ｔｍａｘ［０］〜［３］の平均値を算出し、算出した平均値を補正後の最高温度Ｔｍａｘと決定してもよい。
【０１３６】
なお、第２の実施の形態の例では、１回の起動当たり、最適化装置４０が複数個の局所解を出力する例を示した。一方、最適化装置４０が１回の起動当たり１個の局所解のみを出力する場合、情報処理装置５０は、最適化装置４０を複数回起動して複数個の局所解を取得し、当該複数個の局所解に基づいて、温度補正を行ってもよい。
【０１３７】
このように、情報処理装置２０は、ニューロン間の重み値に応じた最大エネルギー上昇値から初期温度を求める。また、情報処理装置２０は、最適化装置４０から取得した、ある局所解から他の局所解へ１ビットずつ近づける過程で得られる最大エネルギー上昇値から補正温度を求める。
【０１３８】
第２の実施の形態の最適化システム２によれば、求解対象の問題毎に適切な温度範囲を自動的に設定することが可能となる。ここで、最適化装置４０で演算対象となる問題では、問題毎に取り得るエネルギーの範囲が異なるために適切な温度範囲を決定することが容易でない。例えば、図４で例示したように、温度が高過ぎて状態遷移が頻繁に起こり過ぎたり、温度が低すぎて状態遷移が全く起こらなかったりすることがある。このように、最適化装置４０に設定する温度範囲が適切でないと最適解への収束が難しくなる。また、問題毎に取り得るエネルギーの範囲は、実際に問題を解いてみないと分からない。
【０１３９】
これに対し、最適化システム２では、情報処理装置５０により、問題毎に適切な温度範囲が自動的に設定される。このため、新規の問題を解くためのユーザによるパラメータのチューニング作業を不要にできる。また、適切な温度を最適化装置４０に設定することで、「状態遷移が頻繁に起こり過ぎる」、あるいは、「状態遷移が全く起こらない」という状況を防ぎ、最適解への収束を容易にすることができる。更に、情報処理装置５０により、局所解からの脱出を適切に促進するような温度パラメータを設定することで、最適化装置４０による演算の実行時間を短縮できる。
【０１４０】
なお、第１の実施の形態の最適化装置１０および第２の実施の形態の最適化装置４０として、デジタル回路などを用いてＳＡを実行する装置の他、シミュレーテッド量子アニーリング（ＳＱＡ：Simulated Quantum Annealing）を実行する装置を用いてもよい。すなわち、情報処理装置２０，５０を、ＳＱＡにおける温度パラメータの決定に用いることもできる。
【符号の説明】
【０１４１】
１  最適化システム
１０  最適化装置
１１  グラフ
１１ａ  ノード
２０  情報処理装置
２１  記憶部
２２  初期温度計算部
２３  温度補正部
３０  系列
【図１】
2020173579.tif 000015
【図２】
2020173579.tif 000016
【図３】
2020173579.tif 000017
【図４】
2020173579.tif 000018
【図５】
2020173579.tif 000019
【図６】
2020173579.tif 000020
【図７】
2020173579.tif 000021
【図８】
2020173579.tif 000022
【図９】
2020173579.tif 000023
【図１０】
2020173579.tif 000024
【図１１】
2020173579.tif 000025
【図１２】
2020173579.tif 000026
【図１３】
2020173579.tif 000027