(57)【要約】【課題】探索過程における状態のエネルギー分布をボルツマン分布に近づけることにより、遷移候補探索の並列化による収束特性の変化、解の精度の悪化を抑制すること。【解決手段】遷移制御部２０は、乱数生成部が発生した独立な複数の乱数を用いて計算される熱励起エネルギーとそれと同数の状態遷移に対するエネルギー変化とを比較しそれぞれの遷移の受け入れの可否を決定した結果をもとに第１の選択回路により状態遷移の候補群から１つの中間候補をランダムに選択し、第２の選択回路により複数の中間候補から何れか１つの状態遷移をランダムに選択する。【選択図】図１
2020061012.tif 000002
【特許請求の範囲】
【請求項１】
評価関数についてエネルギーの基底状態探索を行う最適化装置において、
前記エネルギーを表す評価関数に含まれる複数の状態変数の値をそれぞれ保持する状態保持部と、
前記複数の状態変数の値の何れかが変化することに応じて状態遷移が起こる場合、前記エネルギーの変化値を複数の状態遷移のそれぞれに対して計算する計算部と、
温度を示す温度値を制御する温度制御部と、
乱数生成部が発生した独立な複数の乱数を用いて計算される熱励起エネルギーとそれと同数の状態遷移に対するエネルギー変化とを比較して得られる、それぞれの遷移の受け入れの可否に基づき状態遷移の候補群から１つの中間候補をランダムに選択する複数の第１の選択回路と、複数の前記中間候補から何れか１つの状態遷移をランダムに選択する第２の選択回路を有する遷移制御部と、
を有する最適化装置。
【請求項２】
前記複数の第１の選択回路、前記第２の選択回路がそれぞれ２分木により構成された第１部分セレクタツリー、第２部分セレクタツリーからなる請求項１記載の最適化装置。
【請求項３】
前記第１部分セレクタツリーは、２つの入力のうちの１つを選択用乱数により選択して出力する複数のセレクタを有し、前記第２部分セレクタツリーは、１以上の前記セレクタを有する、請求項２記載の最適化装置。
【請求項４】
前記状態保持部は、前記遷移制御部により選択された前記１つの状態遷移に基づいて、前記複数の状態変数の値の何れかを変化させる、請求項１記載の最適化装置。
【請求項５】
前記計算部が計算した複数のエネルギーに基づいて、前記複数のエネルギーのうち、最低の前記エネルギーに対応する前記複数の状態変数の値を出力するエネルギー比較部、
を更に有する請求項１記載の最適化装置。
【請求項６】
評価関数についてエネルギーの基底状態探索を行う最適化装置の制御方法において、
最適化装置が有する状態保持部が、エネルギーを表す評価関数に含まれる複数の状態変数の値をそれぞれ保持し、
前記最適化装置が有する計算部が、前記複数の状態変数の値の何れかが変化することに応じて状態遷移が起こる場合、前記エネルギーの変化値を複数の状態遷移のそれぞれに対して計算し、
前記最適化装置が有する温度制御部が、温度を示す温度値を制御し、
前記最適化装置が有する遷移制御部が、乱数生成部が発生した独立な複数の乱数を用いて計算される熱励起エネルギーとそれと同数の状態遷移に対するエネルギー変化とを比較しそれぞれの遷移の受け入れの可否を決定した結果をもとに第１の選択回路により状態遷移の候補群から１つの中間候補をランダムに選択し、第２の選択回路により複数の前記中間候補から何れか１つの状態遷移をランダムに選択する、
最適化装置の制御方法。
【請求項７】
状態のエネルギーに応じた確率で、状態空間の中から状態を選び出して出力するサンプリング装置において、
前記エネルギーを表す評価関数に含まれる複数の状態変数の値をそれぞれ保持する状態保持部と、
前記複数の状態変数の値の何れかが変化することに応じて状態遷移が起こる場合、前記エネルギーの変化値を複数の状態遷移のそれぞれに対して計算する計算部と、
温度を示す温度値を制御する温度制御部と、
乱数生成部が発生した独立な複数の乱数を用いて計算される熱励起エネルギーとそれと同数の状態遷移に対するエネルギー変化とを比較して得られる、それぞれの遷移の受け入れの可否に基づき状態遷移の候補群から１つの中間候補をランダムに選択する複数の第１の選択回路と、複数の前記中間候補から何れか１つの状態遷移をランダムに選択する第２の選択回路を有する遷移制御部と、
を有するサンプリング装置。
【請求項８】
前記複数の第１の選択回路、前記第２の選択回路がそれぞれ２分木により構成された第１部分セレクタツリー、第２部分セレクタツリーからなる請求項７記載のサンプリング装置。
【請求項９】
前記第１部分セレクタツリーは、２つの入力のうちの１つを選択用乱数により選択して出力する複数のセレクタを有し、前記第２部分セレクタツリーは、１以上の前記セレクタを有する、請求項８記載のサンプリング装置。
【請求項１０】
前記状態保持部は、前記遷移制御部により選択された前記１つの状態遷移に基づいて、前記複数の状態変数の値の何れかを変化させる、請求項７記載のサンプリング装置。
【請求項１１】
前記計算部が計算した複数のエネルギーに基づいて、前記複数のエネルギーのうち、最低の前記エネルギーに対応する前記複数の状態変数の値を出力するエネルギー比較部、
を更に有する請求項７記載のサンプリング装置。
【請求項１２】
状態のエネルギーに応じた確率で、状態空間の中から状態を選び出して出力するサンプリング装置の制御方法において、
最適化装置が有する状態保持部が、エネルギーを表す評価関数に含まれる複数の状態変数の値をそれぞれ保持し、
前記最適化装置が有する計算部が、前記複数の状態変数の値の何れかが変化することに応じて状態遷移が起こる場合、前記エネルギーの変化値を複数の状態遷移のそれぞれに対して計算し、
前記最適化装置が有する温度制御部が、温度を示す温度値を制御し、
前記最適化装置が有する遷移制御部が、乱数生成部が発生した独立な複数の乱数を用いて計算される熱励起エネルギーとそれと同数の状態遷移に対するエネルギー変化とを比較しそれぞれの遷移の受け入れの可否を決定した結果をもとに第１の選択回路により状態遷移の候補群から１つの中間候補をランダムに選択し、第２の選択回路により複数の前記中間候補から何れか１つの状態遷移をランダムに選択する、
サンプリング装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、評価関数についてエネルギーの基底状態探索を行う最適化装置および最適化装置の制御方法に関する。また、状態のエネルギーに応じた確率で、状態空間の中から状態を選び出して出力するサンプリング装置およびサンプリング装置の制御方法に関する。
【背景技術】
【０００２】
現在の社会ではあらゆる分野で情報処理が行われている。これらの情報処理はコンピュータなどの演算装置を用いて行われており、様々なデータを演算、加工し、意味のある結果を得ることにより、予測、決定、制御などが行われる。これらの情報処理の１つの分野として最適化問題があり重要な分野となっている。例えば、ある処理を行う場合に必要な資源やコストを最小化する問題、またはその処理による効果を最大化する解を求める問題などである。これらの問題が非常に重要であるのは明らかであろう。
【０００３】
最適化問題の代表的なものとして線形計画問題がある。これは複数の連続変数の線形和で表される評価関数を、線形和で表される制約条件の下で最大化または最小化する変数の値を求めるものであり、製品の生産計画など様々な分野で利用されている。この線形計画問題には単体法や内点法といった優れた解法が知られており、何十万以上の変数を持つ問題でも効率的に解くことができる。
【０００４】
一方最適化問題には、変数が連続値ではなく離散的な値を取るものも多く知られている。例えば、複数の都市を順番に回り元に戻るときの最短経路を求める巡回セールスマン問題や、ナップザックに異なる品物を詰めるときその価値の和が最大となるような組み合わせを求めるナップザック問題などが挙げられる。このような問題は、離散最適化問題、組み合わせ最適化問題などと呼ばれ、最適解を得るのが非常に難しいことが知られている。
【０００５】
離散最適化問題を解くのが難しい最大の原因は、各変数が離散値しか取れないため、評価関数が改善される方向に変数を連続的に変化させることで最適解に到達させるという手法が使えないことである。そして本来の最適値を与える変数の値（最適解、大域解）以外に、局所的に評価関数の極値を与える値（極小（大）解、局所解）が非常に多数存在することである。このため最適解を確実に得るにはしらみつぶしのような方法を取らざるを得ず、計算時間が非常に長くなる。離散最適化問題には計算量理論でＮＰ（Non-deterministic Polynomial）困難問題と呼ばれる、最適解を求めるための計算時間が問題の大きさ（すなわち変数の数）に対して指数的に増加すると予想される問題が多い。上記巡回セールスマン問題やナップザック問題もＮＰ困難問題である。
【０００６】
以上述べたように、離散最適化問題の最適解を確実に求めることは非常に困難である。このため実用上重要な離散最適化問題にはその問題に固有な性質を利用した解法が考え出されている。上記のように多くの離散最適化問題では厳密解を得るには指数関数的に増大する計算時間がかかると予想されるため、実用的な解法の多くは近似解法であり、最適解ではないものの評価関数の値が最適値に近い値となる解を得ることができるものである。
【０００７】
これらの問題に特化した近似解法に対して、問題の性質を用いることなく解くため広範囲な問題を扱える近似解法も知られている。これらはメタヒューリスティックな解法と呼ばれ、疑似焼き鈍し法（シミュレーテッド・アニーリング法、ＳＡ法）、遺伝的アルゴリズム、ニューラルネットワークなどが挙げられる。これらの方法は、問題の性質をうまく利用した解法よりは効率が悪い可能性があるが、厳密解を得る解法よりは高速に解を得ることが期待できる。
【０００８】
以下、疑似焼き鈍し法について説明する。
疑似焼き鈍し法はモンテカルロ法の一種であり、乱数値を用いて確率的に解を求める方法である。以下では最適化したい評価関数の値を最小化する問題を例に説明し、評価関数の値をエネルギーと呼ぶことにする。最大化の場合は、評価関数の符号を変えればよい。
【０００９】
各変数に離散値の１つを代入した初期状態からはじめ、現在の状態（変数の値の組み合わせ）から、それに近い状態（例えば１つの変数だけ変化させた状態）を選び、その状態遷移を考える。その状態遷移に対するエネルギーの変化を計算し、その値に応じてその状態遷移を採択して状態を変化させるか、採択せずに元の状態を保つかを確率的に決める。エネルギーが下がる場合の採択確率をエネルギーが上がる場合より大きく選ぶと、平均的にはエネルギーが下がる方向に状態変化が起こり、時間の経過とともにより適切な状態へ状態遷移することが期待できる。そして最終的には最適解または最適値に近いエネルギーを与える近似解を得られる可能性がある。もし、これを決定論的にエネルギーが下がる場合に採択、上がる場合に不採択とすれば、エネルギーの変化は時間に対して広義単調減少となるが、局所解に到達したらそれ以上変化が起こらなくなってしまう。上記のように離散最適化問題には非常に多数の局所解が存在するために、状態が、多くの場合あまり最適値に近くない局所解に捕まってしまう。したがって、採択するかどうかを確率的に決定することが重要である。
【００１０】
疑似焼き鈍し法においては、状態遷移の採択（受入）確率を次のように決めれば、時刻（反復回数）無限大の極限で状態が最適解に到達することが証明されている。
状態遷移に伴うエネルギー変化値（ΔＥ）に対して、その状態遷移の受入確率ｐは式（１）で表される次の関数ｆ（ｘ）により決める。式（２）はメトロポリス法である。式（３）はギブス法である。
【００１１】
【数１】
2020061012.tif 000003
【００１２】
【数２】
2020061012.tif 000004
【００１３】
【数３】
2020061012.tif 000005
【００１４】
ここでＴは温度値と呼ばれるパラメータで次のように変化させる。
すなわち、温度値Ｔを次式で表されるように反復回数ｔに対数的に減少させる。
【００１５】
【数４】
2020061012.tif 000006
【００１６】
ここでＴ０は初期温度値であり問題に応じて十分大きく取る必要がある。
（１）〜（３）の式で表される受入確率を用いた場合、十分な反復後に定常状態に達したとすると、各状態の占有確率は熱力学における熱平衡状態に対するボルツマン分布に従う。そして、高い温度から徐々に下げていくとエネルギーの低い状態の占有確率が増加するため、十分温度が下がるとエネルギーの低い状態が得られるはずである。この様子が材料を焼き鈍したときの状態変化とよく似ているため、この方法は疑似焼き鈍し法と呼ばれるのである。このとき、エネルギーが上がる状態遷移が確率的に起こることは、物理学における熱励起に相当する。
【００１７】
上記のように疑似焼き鈍し法では、反復回数を無限に取れば最適解が得られるが、現実には有限の反復回数で解を得る必要があるため、最適解を確実に求めることはできない。また上の式では温度の下がり方が非常にゆっくりであるため、有限時間では十分に温度が下がらない。したがって実際の疑似焼き鈍し法では対数的な温度変化ではなくより早く温度を下げることが多い。
【００１８】
図１４に疑似焼き鈍し法による最適化装置の概念的構成を示す。ただし、下記説明では、状態遷移の候補を複数発生させる場合についても述べているが、本来の基本的な疑似焼き鈍し法は遷移候補を１つずつ発生させるものである。
【００１９】
最適化装置１０には、まず現在の状態Ｓ（複数の状態変数の値）を保持する状態保持部１１がある。また、複数の状態変数の値の何れかが変化することによる現在の状態Ｓからの状態遷移が起こった場合の、各状態遷移のエネルギー変化値｛ΔＥｉ｝を計算する評価関数計算部１２がある。そして、最適化装置１０には、温度値Ｔを制御する温度制御部１３、状態変化を制御するための遷移制御部１４がある。遷移制御部１４は、温度値Ｔとエネルギー変化値｛ΔＥｉ｝と乱数値とに基づいて、エネルギー変化値｛ΔＥｉ｝と熱励起エネルギーとの相対関係によって複数の状態遷移の何れかを受け入れるか否かを確率的に決定するものである。更に、最適化装置１０には、状態遷移により生じた各状態のうち、最低エネルギー状態Ｓを特定するエネルギー比較部１５がある。
【００２０】
一回の反復における動作は次のようなものである。まず、遷移制御部１４は、状態保持部１１に保持された現在の状態Ｓから次の状態への状態遷移の候補（候補番号｛Ｎｉ｝）を１つまたは複数発生する。評価関数計算部１２は、現在の状態Ｓと状態遷移の候補を用いて候補に挙げられた各状態遷移に対するエネルギー変化値｛ΔＥｉ｝を計算する。遷移制御部１４は、温度制御部１３で発生した温度値Ｔと遷移制御部１４内の乱数生成部で生成した確率変数（乱数値）を用い、各状態遷移のエネルギー変化値｛ΔＥｉ｝に応じて、上記の式（１）〜（３）の受入確率でその状態遷移を許容する。そして、遷移制御部１４は、各状態遷移を受け入れるか否か（以下状態遷移の可否という場合もある）を示す遷移可否｛ｆｉ｝を出力する。許容された状態遷移が複数ある場合には、遷移制御部１４は、乱数値を用いてランダムにそのうちの１つを選択する。そして、遷移制御部１４は、選択した状態遷移の遷移番号Ｎと、遷移可否Ｆを出力する。許容された状態遷移が存在した場合、採択された状態遷移に応じて状態保持部１１に記憶された状態変数の値が更新される。
【００２１】
初期状態からはじめて、温度制御部１３で温度値を下げながら上記反復を繰り返し、一定の反復回数に達したときや、エネルギーが一定の値を下回るなどの終了判定条件が満たされたときに、動作が終了する。最適化装置１０が出力する答えは終了時の状態である。ただし、実際には有限の反復回数では温度値が０にならないため、終了時においても状態の占有率はボルツマン分布などで表される分布を持っており、必ずしも最適値や良い解になっているとは限らない。したがって、反復の途中でこれまでに得られたエネルギーが最低の状態を保持し、最後にそれを出力するのが現実的な解法となる。
【００２２】
ここで、遷移制御部１４により、（１）〜（３）の式で表される受入確率で状態遷移を許容するメカニズムについてはこれまで説明していないのでこれを補足する。
受入確率ｐで１を、（１−ｐ）で０を出力する回路は、２つの入力ａ，ｂを持ち、ａ＞ｂのとき１を出力し、ａ＜ｂのとき０を出力する比較器の入力ａに受入確率ｐを、入力ｂに区間［０，１）の値を取る一様乱数を入力することで実現することができる。したがってこの比較器の入力ａに、エネルギー変化値と温度値Ｔにより（１）の式を用いて計算される受入確率ｐの値を入力すれば、上記の機能を実現することができる。
【００２３】
すなわちｆを（１）の式で用いる関数、ｕを区間［０，１）の値を取る一様乱数とするとき、ｆ（ΔＥ／Ｔ）がｕより大きいとき１を出力する回路で、上記の機能を実現できる。
【００２４】
このままでもよいのであるが、次のような変形を行っても同じ機能が実現できる。２つの数に同じ単調増加関数を作用させても大小関係は変化しない。したがって比較器の２つの入力に同じ単調増加関数を作用させても出力は変わらない。この単調増加関数としてｆの逆関数ｆ−１を採用すると、−ΔＥ／Ｔがｆ−１（ｕ）より大きいとき１を出力する回路、またはΔＥ／Ｔがｆ−１（ｕ）以下のとき１を出力する回路でよいことがわかる。更に温度値Ｔが正であることから−ΔＥがＴｆ−１（ｕ）より大きいとき１を出力する回路、またはΔＥがＴｆ−１（ｕ）以下のとき１を出力する回路でよい。遷移制御部１４は、一様乱数ｕを生成し、上記のｆ−１（ｕ）の値に変換する変換テーブルを用いて、ｆ−１（ｕ）の値を出力する。メトロポリス法が適用される場合、ｆ−１（ｕ）は、式（５）で与えられる。また、ギブス法が適用される場合、ｆ−１（ｕ）は、式（６）で与えられる。
【００２５】
【数５】
2020061012.tif 000007
【００２６】
【数６】
2020061012.tif 000008
【００２７】
これまでの説明で、状態遷移の受け入れをメトロポリス基準などで行うマルコフ過程を用いることで最適化装置が得られることを示したが、このマルコフ過程で発生される状態そのものを出力することで、ボルツマン分布に従う状態を発生するサンプリング装置が得られる。サンプリング装置は、機械学習などでの期待値計算に用いることができる。
【先行技術文献】
【特許文献】
【００２８】
【特許文献１】特開２０１７−２１９９４８号公報
【特許文献２】特開２０１６−５１３５０号公報
【発明の概要】
【発明が解決しようとする課題】
【００２９】
上記のように、遷移制御部は、温度値Ｔとエネルギー変化値｛ΔＥｉ｝と乱数値とに基づき、エネルギー変化値｛ΔＥｉ｝と熱励起エネルギーとの相対関係によって対象となる遷移を受け入れて良いかどうかを決定する。基本的な疑似焼き鈍し法では最初から適切な方法で遷移候補を１つに絞ってから、遷移を受け入れるかどうか決定する。この場合には探索過程における状態のエネルギー分布は、温度変化が十分ゆっくりであればその温度におけるボルツマン分布に漸近することが保証される。しかしながら、候補を１つに絞ることにより一回の探索ステップで受け入れ可能な遷移を見つける確率は低くなってしまうため、良い解を求めるのに必要とされるステップ数が非常に大きくなってしまうという問題がある。
【００３０】
より速く良い解を得るためには、まず、複数の状態遷移のそれぞれに対して、上記受け入れ基準により受け入れるか否かを確率的に決定し、許容された状態遷移が複数ある場合には、ランダムにそのうちの１つを選択するという構成にする。
【００３１】
この時、状態遷移の受け入れ可否を確率的に決定する際に用いられる乱数値は、全ての状態遷移に対して独立となるように生成されることが理論上望ましい。しかし、回路規模の制約や動作速度向上のためなどにより、遷移制御部は、幾つかの状態遷移候補に対し乱数値を共用して、状態遷移の受け入れ可否を決定することがある。この場合、遷移制御部による状態遷移の候補の選択方法によっては、各温度における各状態の占有確率がボルツマン分布から大きくずれてしまう場合がある。その結果として、最適解への収束性が変化し、解の品質が悪化することがある。
【００３２】
また温度一定とした状態遷移を繰り返す過程により得られた状態を用いてサンプリングを行う場合、このボルツマン分布からのずれのために、ボルツマン分布を仮定しているアプリケーションに適用した場合に誤差が大きくなってしまう可能性がある。
【００３３】
１つの側面では、本発明は、複数の状態遷移を同時に遷移候補とする並列化を用いたマルコフ過程探索において、探索過程における状態のエネルギー分布をできるだけボルツマン分布に近づけることにより最適解への収束性を保証し、解の品質の悪化を抑制する最適化装置および最適化装置の制御方法を提供することを目的とする。また、発生する状態のエネルギー分布がボルツマン分布に近い分布となるサンプリング装置およびサンプリング装置の制御方法を提供することを目的とする。
【００３４】
上記説明でわかるように、マルコフ過程を用いボルツマン分布に従う最適化装置は、サンプリング装置として用いることができるため、以下では簡単のため最適化装置として説明を行う。
【００３５】
また、マルコフ過程を用いた最適化装置、サンプリング装置として、上で説明した疑似焼き鈍し法だけでなく、複数の温度に対するマルコフ過程状態遷移を同時に行うレプリカ交換法（交換モンテカルロ法ともいう）も有力な方法であり、本発明をそのまま適応可能である。しかしながら簡単のため以下では疑似焼き鈍し法で説明を行う。
【課題を解決するための手段】
【００３６】
１つの態様では、最適化装置が提供される。最適化装置は、状態保持部と計算部と温度制御部と遷移制御部とを有する。状態保持部は、エネルギーを表す評価関数に含まれる複数の状態変数の値をそれぞれ保持する。計算部は、複数ある状態変数Ｓの値の中で遷移制御部から入力される候補番号Ｎｉの状態遷移が生じた際に変化するエネルギーの変化分ΔＥｉを計算して出力する。温度制御部は、温度を示す温度値Ｔを制御する。遷移制御部は、温度制御部から入力される温度値Ｔと、状態遷移の候補となる候補番号Ｎｉが状態遷移を起こした場合のΔＥｉをもとに、状態遷移の可否Ｆと１つの状態遷移を決定し、その遷移候補番号Ｎを決定する。この遷移の可否判定には、温度値Ｔの大きさに応じた乱数を生成し、適用する遷移受け入れ基準に応じて式（５）または（６）に従った判定を行う。受け入れを許容された複数の状態遷移の候補から状態遷移する遷移番号を決定する方法として２段階のセレクタを用いる。第１部分セレクタ群は、遷移候補の部分集合から１つの中間候補をランダムに選択するもので、同じセレクタに入る遷移候補の遷移可否の判定に用いる乱数は全て独立なものが供給される。異なる第１部分セレクタに入る遷移候補の遷移可否の判定に用いる乱数は共用することができる。第２部分セレクタは、１段目で得られた中間候補から１つの遷移候補をランダムに選択する。
【００３７】
上記２段階のセレクタ群のいずれも２進木からなるセレクタツリーを用いた場合には、ｎ段（ｎは２以上の整数）のセレクタツリーを用い、互いに異なる乱数生成部が生成した乱数値に対応する状態遷移の候補群から１つの中間候補を、ｎ段のセレクタツリーのうち第１段目から第ｍ段目（ｍは１以上ｎ未満の整数）の複数の第１部分セレクタツリーのそれぞれにより選択し、ｎ段のセレクタツリーのうちの第ｍ＋１段目以降の第２部分セレクタツリーにより、複数の中間候補から何れか１つの状態遷移を選択する構成となる。
【００３８】
また、１つの態様では、最適化装置の制御方法が提供される。
【発明の効果】
【００３９】
探索過程における状態のエネルギー分布が理論的に予想されるボルツマン分布に十分近づくことで本来の収束性が保証され、並列化に伴う解の品質の悪化が抑制されることが期待される。また、分布のずれがないため収束特性の理論解析や、シミュレーション、並列化を行わない時との比較検討が容易になり、温度スケジューリングなどの調整も容易となる。またサンプリングでの応用については、課題を解決するための手段にて記載の構成において温度値を一定とした解探索を行うことで、正しいボルツマン分布により近い解が得られる。
【図面の簡単な説明】
【００４０】
【図１】第１の実施の形態の遷移制御部の例を示す図である。
【図２】部分セレクタ部の回路構成例を示す図である。
【図３】遷移制御部の動作フローを示す図である。
【図４】第２の実施の形態の遷移制御部の例を示す図である。
【図５】部分セレクタ部の例を示す図である。
【図６】選択回路部の例（その１）を示す図である。
【図７】セレクタの例を示す図である。
【図８】選択回路部の例（その２）を示す図である。
【図９】第１部分セレクタの例を示す図である。
【図１０】第２部分セレクタの例を示す図である。
【図１１】遷移制御部の比較例を示す図である。
【図１２】熱雑音の共用による分布のずれの例を示す図である。
【図１３】ボルツマン分布に対するずれの改善例を示す図である。
【図１４】疑似焼き鈍し法による最適化装置の概念的構成を示す図である。
【発明を実施するための形態】
【００４１】
以下、本実施の形態について図面を参照して説明する。
［第１の実施の形態］
第１の実施の形態を説明する。
【００４２】
図１は、第１の実施の形態の遷移制御部の例を示す図である。
遷移制御部２０は、複数の状態変数のそれぞれの状態遷移のエネルギー変化値｛ΔＥｉ｝に応じて、上記の式（１）〜（３）の受入確率でその状態遷移を許容する。そして、遷移制御部２０は、各状態遷移を受け入れるか否かを示す遷移可否｛ｆｉ｝を出力する。許容された状態遷移が複数ある場合には、遷移制御部２０は、乱数値を用いてランダムにそのうちの１つを選択する。遷移制御部２０は、選択した状態遷移の遷移番号（インデックスと称する）と、遷移可否Ｆとを出力する。
【００４３】
このように、遷移制御部２０は、複数の状態変数のそれぞれに対して並列探索を行うことで、遷移確率を高めることができる。例えば、状態変数Ｎ個の疑似焼き鈍し法による最適化装置１０での並列探索時の状態の遷移確率は、遷移確率が十分小さい時、式（７），（８）で示されるように、状態変数１つの時の遷移確率の約Ｎ倍になる。
【００４４】
【数７】
2020061012.tif 000009
【００４５】
【数８】
2020061012.tif 000010
【００４６】
ここで、Ｎは状態変数の数である。Ａ（ΔＥｉ）は、ｉ番目の変数の遷移の受入確率であり、十分小さい。Ｐｓｉｎｇｌｅは、１つの状態変数単体で探索する場合の遷移確率である。Ｐｐａｒａｌｌｅｌは、Ｎ個の状態変数に対して並列探索したときの遷移確率である。
【００４７】
並列探索を行うため、遷移制御部２０は、次の回路構成を有する。一例として、状態変数の数を３２個として説明する。１つの状態変数は、１ビットで表されるものとする。この場合、状態変数は「ビット」や「スピンビット」などと呼ばれてもよい。この例では遷移候補としていずれか１つのビットのみが反転するものを対象とするので、遷移候補の数はビット数と同じ３２個であり、遷移候補の番号も反転するビットの番号と同じに取ることができる。以下の説明では遷移番号は反転ビット番号と同じものとしている。
【００４８】
また、この例では複数の遷移候補から１つの遷移を選び出す選択回路として２進木を用いている。
遷移制御部２０は、熱雑音生成回路２１，２２，２３，２４、比較回路部２５，２６，２７，２８およびセレクタ部３０を有する。
【００４９】
熱雑音生成回路２１は、比較回路部２５に熱雑音を供給する。熱雑音生成回路２２は、比較回路部２６に熱雑音を供給する。熱雑音生成回路２３は、比較回路部２７に熱雑音を供給する。熱雑音生成回路２４は、比較回路部２８に熱雑音を供給する。
【００５０】
熱雑音は、前述の熱励起エネルギーに相当し、Ｔｆ−１（ｕ）により計算される。ｆ−１（ｕ）として、適用法則に応じて式（５），（６）の何れかが用いられる。温度値Ｔとして、熱雑音生成回路２１，２２，２３，２４のそれぞれには、温度制御部１３から共通の温度値Ｔが供給される。一様乱数ｕとして、熱雑音生成回路２１，２２，２３，２４のそれぞれには、乱数生成部（図示を省略している）により生成された独立な一様乱数ｕが供給される。図１の例では、遷移制御部２０は、４つの独立な乱数が生成される。
【００５１】
比較回路部２５，２６，２７，２８は、複数の状態変数のそれぞれが遷移した場合のエネルギー変化値｛ΔＥｉ｝を、評価関数計算部１２から受け付ける。比較回路部２５，２６，２７，２８は、｛ΔＥｉ｝に基づいて各状態遷移を受け入れるか否かを判定し、遷移可否｛ｆｉ｝を出力する。比較回路部２５，２６，２７，２８のそれぞれは、８（＝３２／４）個の比較器を有する。比較回路部２５，２６，２７，２８に含まれる全ての比較器の合計数は３２個となる。
【００５２】
具体的には、比較回路部２５は、比較器Ｃ０，Ｃ１，…，Ｃ７を有する。比較回路部２６は、比較器Ｃ８，Ｃ９，…，Ｃ１５を有する。比較回路部２７は、比較器Ｃ１６，Ｃ１７，…，Ｃ２３を有する。比較回路部２８は、比較器Ｃ２４，Ｃ２５，…，Ｃ３１を有する。比較器Ｃｉ（図１の例ではｉは０以上３１以下の整数）は、ΔＥｉを受け付け、ΔＥｉに基づく判定に応じて遷移可否ｆｉを出力する。比較器Ｃｉによる判定では、エネルギー変化値ΔＥｉと、熱雑音との比較を行う。
【００５３】
比較器Ｃ０，…，Ｃ７は、熱雑音生成回路２１により生成された熱雑音を共用して、状態遷移の可否の判定を行う。熱雑音生成回路２１は、熱雑音生成回路２１に対応する乱数生成部により生成された乱数値ｕを用いて、比較器Ｃ０，…，Ｃ７に対して同じ熱雑音を供給するとも言える。
【００５４】
比較器Ｃ８，…，Ｃ１５は、熱雑音生成回路２２により生成された熱雑音を共用して、状態遷移の可否の判定を行う。比較器Ｃ１６，…，Ｃ２３は、熱雑音生成回路２３により生成された熱雑音を共用して、状態遷移の可否の判定を行う。比較器Ｃ２４，…，Ｃ３１は、熱雑音生成回路２４により生成された熱雑音を共用して、状態遷移の可否の判定を行う。図１の例では、８個の比較器に対して、１つの熱雑音（あるいは、１つの乱数値）が共用される。８個の状態遷移、あるいは、８個のエネルギー変化値に対して１つの熱雑音（あるいは、１つの乱数値）が共用されるとも言える。
【００５５】
セレクタ部３０は、所定数のエネルギー変化値に対して共用される乱数値および温度値に基づく熱励起エネルギー（熱雑音）とエネルギー変化値との相対関係に応じた複数の状態遷移の候補の何れか１つを選択し、出力する。セレクタ部３０は、当該選択を行うためのｎ段（ｎは２以上の整数）のセレクタツリーを有する。図１の例では、ｎ＝５である。
【００５６】
セレクタツリーの第１段目（１ｓｔ）は、部分セレクタ部３０ａ，３０ｂを有する。セレクタツリーの第２段目（２ｎｄ）は、部分セレクタ部３０ｃを有する。セレクタツリーの第３段目（３ｒｄ）は、部分セレクタ部３０ｄを有する。セレクタツリーの第４段目（４ｔｈ）は、部分セレクタ部３０ｅを有する。セレクタツリーの第５段目（５ｔｈ）は、部分セレクタ部３０ｆを有する。
【００５７】
部分セレクタ部３０ａ，３０ｂ，…，３０ｆのそれぞれは、例えば、２つの入力のうちの１つを選択用乱数により選択して出力する複数のセレクタを有する。セレクタ３１は、複数のセレクタのうちの１つであり、他のセレクタもセレクタ３１と同様の構成である。セレクタ３１に対する２つの入力はｉとｊの遷移番号を特定するための識別値Ｎｉ，Ｎｊと遷移可否情報ｆｉ，ｆｊである。セレクタ３１の出力は遷移可否情報ｆｉ，ｆｊの論理和として得られる可否情報ｆｏと、ｉとｊのうち選択された方の遷移番号を特定するための識別値Ｎｏである。そして、遷移可否情報ｆｉ，ｆｊのいずれか一方が１（受け入れ可）、他方が０（受け入れ不可）の場合は受け入れ可の方を必ず選択し、両方が１の場合には選択用信号により一方を選択する。両方０の場合はどのように選んでも良い。そして選択結果により選ばれた遷移の識別値Ｎｏを生成し出力する。この場合、初段のセレクタにより１ビットの識別値が生成され、段を経る毎に、識別値のビット長が１ビットずつ増し、最終段（部分セレクタ部３０ｆのセレクタ）では、５ビットのインデックスが生成されて、出力される。
【００５８】
具体的には図１の例では１段目の部分セレクタ部３０ａ，３０ｂでは番号が８離れた遷移同士比較するので、インデックスのビット３を生成する。同様に２段目ではビット４、３段目ではビット０、４段目ではビット１、５段目ではビット２を生成し、それを選択された方の識別値に加えたものを出力してゆけば、最終的に選択された遷移番号を表すインデックスが得られる。
【００５９】
図１ではセレクタ３１以外のセレクタが略記されている。図１では黒い丸印で表された箇所が、１つのセレクタに相当する。部分セレクタ部３０ａ，３０ｂ，３０ｃのそれぞれは、８個のセレクタを有する。部分セレクタ部３０ｄは、４個のセレクタを有する。部分セレクタ部３０ｅは、２個のセレクタを有する。
【００６０】
図１で示されるように、遷移制御部２０は、状態遷移の並列探索、および、熱雑音共用を行い、全比較器出力をセレクタの２進木構造を用いてノックダウン方式（あるいはトーナメント方式とも呼ばれる）で、状態遷移の候補を１つに絞り込む。遷移制御部２０は、セレクタ部３０におけるｎ段のセレクタツリーの初期のステージで熱雑音を共用する候補同士が当たらないように構成されている。この例では１段目と２段目が４つの独立な乱数を用いて、４つの遷移候補から１つの中間候補を選択する第１部分セレクタ群を構成する。また３〜５段目で８つの中間候補から１つの遷移を選択する第２部分セレクタを構成する。
【００６１】
次に、部分セレクタ部３０ａにおけるセレクタを明記した回路構成例を説明する。
図２は、部分セレクタ部の回路構成例を示す図である。
部分セレクタ部３０ａは、セレクタ３１に相当するセレクタ３１ａ０，３１ａ１，…，３１ａ７を有する。
【００６２】
セレクタ３１ａ０には、比較器Ｃ０により出力された遷移可否（または遷移可否情報）ｆ０と識別値、比較器Ｃ８により出力された遷移可否ｆ８と識別値が入力される。セレクタ３１ａ１には、比較器Ｃ１により出力された遷移可否ｆ１と識別値、比較器Ｃ９により出力された遷移可否ｆ９と識別値が入力される。セレクタ３１ａ２には、比較器Ｃ２により出力された遷移可否ｆ２と識別値、比較器Ｃ１０により出力された遷移可否ｆ１０と識別値が入力される。セレクタ３１ａ３には、比較器Ｃ３により出力された遷移可否ｆ３と識別値、比較器Ｃ１１により出力された遷移可否ｆ１１と識別値が入力される。セレクタ３１ａ４には、比較器Ｃ４により出力された遷移可否ｆ４と識別値、比較器Ｃ１２により出力された遷移可否ｆ１２と識別値が入力される。セレクタ３１ａ５には、比較器Ｃ５により出力された遷移可否ｆ５と識別値、比較器Ｃ１３により出力された遷移可否ｆ１３と識別値が入力される。セレクタ３１ａ６には、比較器Ｃ６により出力された遷移可否ｆ６と識別値、比較器Ｃ１４により出力された遷移可否ｆ１４と識別値が入力される。セレクタ３１ａ７には、比較器Ｃ７により出力された遷移可否ｆ７と識別値、比較器Ｃ１５により出力された遷移可否ｆ１５と識別値が入力される。セレクタ３１ａ０，…，３１ａ７のそれぞれの出力は、部分セレクタ部３０ｃにおける互いに異なる８個のセレクタに入力される。
【００６３】
部分セレクタ部３０ｂ，…，３０ｆも、部分セレクタ部３０ａと同様に、セレクタ３１に相当するセレクタにより実現される。特に、部分セレクタ部３０ｂの８個のセレクタのそれぞれには、部分セレクタ部３０ａの８個のセレクタと同様に、互いに異なる熱雑音により決定された２つの遷移可否が入力される。部分セレクタ部３０ａの８個のセレクタの出力は、部分セレクタ部３０ｃにおける互いに異なる８個のセレクタに入力される。
【００６４】
このため、図１の例では、５段のセレクタツリーの初段から２段目までは、熱雑音を共用する候補同士が当たることはない。５段のセレクタツリーの３段目以降から熱雑音を共用する候補同士が当たり得る。
【００６５】
次に、遷移制御部２０の動作フローを説明する。
図３は、遷移制御部の動作フローを示す図である。
（Ｓ１）遷移制御部２０は、複数の状態遷移のそれぞれに対応するエネルギー変化値｛ΔＥｉ｝を受け付ける。
【００６６】
（Ｓ２）遷移制御部２０は、エネルギー変化値｛ΔＥｉ｝と熱雑音から、それぞれの状態遷移の可否を決定する。このとき、所定数のエネルギー変化値に対して熱雑音が共用されて、各状態遷移の可否が決定される。
【００６７】
（Ｓ３）遷移制御部２０は、遷移可となった候補の中から、実際に採用する遷移を１つ選択する。遷移制御部２０は、選択した状態遷移に対応するインデックスと、遷移可否Ｆとを出力する。
【００６８】
そして、状態保持部１１は、遷移制御部２０により選択された１つの状態遷移に基づいて、状態保持部１１により保持される状態変数の値を変化させる。評価関数計算部１２は、今回の状態遷移後の状態のエネルギーを計算し、エネルギー比較部１５に出力する。また、評価関数計算部１２は、複数の状態遷移のそれぞれに対応するエネルギー変化値を計算し、遷移制御部２０に出力する。遷移制御部２０は、ステップＳ１〜Ｓ３を繰り返し実行する。例えば、温度の変更回数をＮ１、温度毎の状態遷移の試行回数をＮ２とすると、繰り返しの回数はＮ１＊Ｎ２である。エネルギー比較部１５は、評価関数計算部１２が計算したエネルギーに基づいて、それまでの反復で得られた複数のエネルギーのうち、最低のエネルギーおよびそれに対応する状態変数の値を保持し、反復が終了した時それを解として出力する。
【００６９】
ステップＳ３では、遷移制御部２０は、互いに異なる乱数生成部が生成した乱数値に対応する状態遷移の候補群から１つの中間候補を、第１部分セレクタ、すなわちｎ段のセレクタツリーのうち第１段目から第ｍ段目（ｍは１以上ｎ未満の整数）の複数の第１部分セレクタツリー（複数の第１の選択回路の一例）のそれぞれにより選択する。図１の例では、遷移制御部２０は、第１段目から第２段目までの８個の第１部分セレクタツリーを有する。遷移制御部２０は、第２部分セレクタ、すなわちｎ段のセレクタツリーのうちの第ｍ＋１段目以降の第２部分セレクタツリー（第２の選択回路の一例）により、複数の中間候補から何れか１つの状態遷移を選択する。図１の例では、遷移制御部２０は、第３段目から第５段目までの第２部分セレクタツリーを有する。第１部分セレクタツリーのそれぞれにより選択される中間候補は計８個となり、当該８個の中間候補のうちの１つが第２部分セレクタツリーにより選択される。このように、遷移制御部２０は、セレクタツリーの少なくとも１段目（初期のステージ）では、熱雑音を共用する候補同士が当たらないようにする。
【００７０】
例えば、初期のステージで熱雑音を共用する候補同士が当たるようにする選択方法も考えられる。しかし、当該選択方法を用いると、図１１，１２で後述されるように、各温度における各状態の占有確率がボルツマン分布から大きくずれてしまい、収束特性の変化や解の品質の悪化が生じる。熱雑音の共用により、遷移確率が低い状態変数が遷移候補になる時は、同じ山（熱雑音を共用する比較器の集合）から多くの候補が立つ可能性が高まり、初期ステージで熱雑音を共用する候補同士が当たると、遷移確率が低い遷移候補が選ばれにくくなるためである。
【００７１】
そこで、遷移制御部２０は、上記のように、セレクタ部３０において、ｎ段のセレクタツリーの初期のステージで熱雑音を共用する候補同士が当たらないようにすることで、各温度における各状態の占有確率のボルツマン分布からのずれを低減できる。その結果、最適化装置１０による収束特性の変化や解の品質の悪化を抑制できる。
【００７２】
ここで、マルコフ過程を用いボルツマン分布に従う最適化装置１０は、サンプリング装置として用いることができる。すなわち、サンプリング装置は、最適化装置１０と同じ構成により実現することができる。サンプリング装置は、状態のエネルギーに応じた確率で、状態空間の中から状態を選び出して出力する。
【００７３】
［第２の実施の形態］
次に、第２の実施の形態を説明する。
第２の実施の形態では、１０２４個の状態変数を用いる場合を例示する。最適化装置１０における状態変数の数が多いほど、より大規模な最適化問題の演算に最適化装置１０を利用できる。
【００７４】
図４は、第２の実施の形態の遷移制御部の例を示す図である。
この例では、遷移制御部４０は、１６個の比較器で１つの熱雑音を共用する。すなわち、１６個の比較器で、１つの乱数値が共用される。図４では、１つの熱雑音生成回路と１６個の比較器とを合わせて、「ｒａｎｄ０」のように「ｒａｎｄ」の文字列と、数値（例えば、「０」）との組み合わせにより略記している。以下では、１つの熱雑音生成回路と１６個の比較器とを合わせた回路を、「比較ブロック」と称する。遷移制御部４０は、６４個の比較ブロックを有する。
【００７５】
遷移制御部４０は、１０段のセレクタツリーを有する。１０段のセレクタツリーは、部分セレクタ部５０ａおよび部分セレクタ部５０ｂを有する。
部分セレクタ部５０ａは、第１段目から第６段目までのセレクタ群である。部分セレクタ部５０ａでは、独立熱雑音の候補同士のみが当たる。部分セレクタ部５０ｂは、第７段目から第１０段目までのセレクタ群である。部分セレクタ部５０ｂでは、共用熱雑音の候補同士が当たり得る。
【００７６】
遷移制御部４０は、状態遷移の並列探索、および、熱雑音共用を行い、全比較器出力をセレクタの２進木構造を用いてノックダウン方式（あるいはトーナメント方式）で１つに絞り込む。図４の例では、セレクタの記載を省略している。
【００７７】
図５は、部分セレクタ部の例を示す図である。
部分セレクタ部５０ａは、６３個の選択回路部を有する。１つの選択回路部は、１６個のセレクタを有する。
【００７８】
部分セレクタ部５０ａは、第１段目の３２個の選択回路部５１ａ０，５１ａ１，…，５１ａ３１を有する。選択回路部５１ａ０には、比較ブロックｒａｎｄ０の１６個の遷移可否ｆ０〜ｆ１５と、比較ブロックｒａｎｄ１の１６個の遷移可否ｆ１６〜ｆ３１とが入力される。選択回路部５１ａ１には、比較ブロックｒａｎｄ２の１６個の遷移可否ｆ３２〜ｆ４７と、比較ブロックｒａｎｄ３の１６個の遷移可否ｆ４８〜ｆ６３とが入力される。以降同様にして、選択回路部５１ａ２，…，５１ａ３１のそれぞれには、２つの比較ブロックからの遷移可否が入力される。
【００７９】
部分セレクタ部５０ａは、第２段目の１６個の選択回路部５２ａ０，５２ａ１，…，５２ａ１５を有する。選択回路部５２ａ０には、選択回路部５１ａ０からの１６個の遷移可否と識別値、選択回路部５１ａ１からの１６個の遷移可否と識別値が入力される。選択回路部５２ａ１には、選択回路部５１ａ２からの１６個の遷移可否と識別値、選択回路部５１ａ３からの１６個の遷移可否と識別値が入力される。以降同様にして、選択回路部５２ａ２，…，５２ａ１５のそれぞれには、第１段目の２つの選択回路部からの遷移可否と識別値が入力される。
【００８０】
部分セレクタ部５０ａは、第３段目の８個の選択回路部５３ａ０，５３ａ１，…，５３ａ７を有する（図５では、選択回路部５３ａ２以降を省略している）。選択回路部５３ａ０には、選択回路部５２ａ０からの１６個の遷移可否と識別値、選択回路部５２ａ１からの１６個の遷移可否と識別値が入力される。選択回路部５３ａ１には、選択回路部５２ａ２からの１６個の遷移可否と識別値、選択回路部５２ａ３からの１６個の遷移可否と識別値が入力される。以降同様にして、選択回路部５３ａ２，…，５３ａ７のそれぞれには、第２段目の２つの選択回路部からの遷移可否と識別値が入力される。
【００８１】
部分セレクタ部５０ａは、第４段目の４個の選択回路部５４ａ０，５４ａ１，５４ａ２，５４ａ３を有する（図５では、選択回路部５４ａ２，５４ａ３を省略している）。選択回路部５４ａ０には、選択回路部５３ａ０からの１６個の遷移可否と識別値、選択回路部５３ａ１からの１６個の遷移可否と識別値が入力される。選択回路部５４ａ１には、選択回路部５３ａ２からの１６個の遷移可否と識別値、選択回路部５３ａ３からの１６個の遷移可否と識別値が入力される。以降同様にして、選択回路部５４ａ２，５４ａ３のそれぞれには、第３段目の２つの選択回路部からの遷移可否と識別値が入力される。
【００８２】
部分セレクタ部５０ａは、第５段目の２個の選択回路部５５ａ０，５５ａ１を有する。選択回路部５５ａ０には、選択回路部５４ａ０からの１６個の遷移可否と識別値、選択回路部５４ａ１からの１６個の遷移可否と識別値が入力される。選択回路部５５ａ１には選択回路部５４ａ２からの１６個の遷移可否と識別値、選択回路部５４ａ３からの１６個の遷移可否と識別値が入力される。
【００８３】
部分セレクタ部５０ａは、第６段目の１個の選択回路部５６ａ０を有する。選択回路部５６ａ０には、選択回路部５５ａ０からの１６個の遷移可否と識別値、選択回路部５５ａ１からの１６個の遷移可否と識別値が入力される。
【００８４】
図６は、選択回路部の例（その１）を示す図である。
ここでは、選択回路部５１ａ０の回路構成例を説明するが、選択回路部５１ａ１，…，５１ａ３１も同様の回路構成である。比較ブロックｒａｎｄ０は、比較器Ｃ０，Ｃ１，…，Ｃ１５を有するものとする。比較ブロックｒａｎｄ１は、比較器Ｃ１６，Ｃ１７，…，Ｃ３１を有するものとする。
【００８５】
選択回路部５１ａ０は、１６個のセレクタ１００，１００ａ，…，１００ｎ，１００ｏを有する。セレクタ１００，…，１００ｏのそれぞれには、比較ブロックｒａｎｄ０に属する１つの比較器からの遷移可否と識別値、および、比較ブロックｒａｎｄ１に属する１つの比較器からの遷移可否と識別値が、入力される。
【００８６】
例えば、セレクタ１００には、比較器Ｃ０により出力された遷移可否ｆ０と識別値、比較器Ｃ１６により出力された遷移可否ｆ１６と識別値が入力される。セレクタ１００ａには、比較器Ｃ１により出力された遷移可否ｆ１と識別値、比較器Ｃ１７により出力された遷移可否ｆ１７と識別値が入力される。以降同様にして、セレクタ１００ｂ，…，１００ｏに対しても、互いに異なる熱雑音を使用する２つの比較器により出力された２つの遷移可否と識別値が入力される。
【００８７】
このように、部分セレクタ部５０ａの第１段目の選択回路部５１ａ０，…，５１ａ３１の各セレクタについて、独立熱雑音の候補同士しか当たらないようにする。
図７は、セレクタの例を示す図である。
【００８８】
ここでは、セレクタ１００を例示する。ただし、他のセレクタもセレクタ１００と同様の構成である。セレクタ１００は、２つの入力を受け付ける。入力は、遷移可否ｆｉと識別値Ｎｉの組，および、遷移可否ｆｊと識別値Ｎｊの組を示す２つの信号である。セレクタ１００には、候補選択用乱数も入力される。セレクタ１００は、候補選択用乱数に基づいて、遷移可否ｆｉ，ｆｊの何れか１つを選択し、選択した方を示す遷移可否ｆｏおよび選択した遷移可否に対応する識別値Ｎｏを出力する。セレクタ１００は、遷移可否ｆｉ，ｆｊの何れか一方のみが遷移可を示す場合、遷移可である方を優先して選択する。セレクタ１００による選択方法は、前述のセレクタ３１による選択方法と同様である。
【００８９】
図８は、選択回路部の例（その２）を示す図である。
ここでは、選択回路部５２ａ０の回路構成例を説明するが、選択回路部５２ａ１，…，５６ａ０も同様の回路構成である。選択回路部５２ａ０は、１６個のセレクタ２００，２００ａ，…，２００ｎ，２００ｏを有する。セレクタ２００，…，２００ｏのそれぞれには、選択回路部５１ａ０により出力された１６個の遷移可否と識別値のうちの１つと、選択回路部５１ａ１により出力された１６個の遷移可否と識別値のうちの１つとが入力される。このように、部分セレクタ部５０ａの第２段目以降の選択回路部の各セレクタについても、独立熱雑音の候補同士しか当たらないようにする。
【００９０】
遷移制御部４０におけるセレクタ部５０の上記回路構成によれば、遷移制御部４０は、次の１６個の第１部分セレクタツリーを有すると言える。
図９は、第１部分セレクタの例を示す図である。
【００９１】
遷移制御部４０は、１６個の第１部分セレクタツリーＴ０，Ｔ１，…，Ｔ１５を有する。第１部分セレクタツリーＴ１，…，Ｔ１５は、複数の第１の選択回路の一例である。以下では、第１部分セレクタツリーＴ０に着目して説明するが、第１部分セレクタツリーＴ１，…，Ｔ１５も、第１部分セレクタツリーＴ０と同様のセレクタ構成である。第１部分セレクタツリーＴ０に接続される比較器Ｃ０，Ｃ１６，Ｃ３２，Ｃ４８，…，Ｃ１００８（６４個の比較器）は、それぞれ異なる比較ブロック（比較ブロックｒａｎｄ０，…，ｒａｎｄ６３）に属する。
【００９２】
第１部分セレクタツリーＴ０は、第１段目のセレクタ１００，１０１，…，１３１、第２段目のセレクタ２００，２０１，…，２１５、第３段目のセレクタ３００，３０１，…，３０７（セレクタ３０７の図示を省略している）、第４段目のセレクタ４００，４０１，…，４０３（セレクタ４０３の図示を省略している）、第５段目のセレクタ５００，５０１および第６段目のセレクタ６００を有する。
【００９３】
セレクタ１００には、比較器Ｃ０により出力された遷移可否ｆ０と識別値、比較器Ｃ１６により出力された遷移可否ｆ１６と識別値が入力される。セレクタ１０１には、比較器Ｃ３２により出力された遷移可否ｆ３２と識別値、比較器Ｃ４８により出力された遷移可否ｆ４８と識別値が入力される。セレクタ１０２には、比較器Ｃ６４により出力された遷移可否ｆ６４と識別値、比較器Ｃ８０により出力された遷移可否ｆ８０と識別値が入力される。以降同様にして、独立熱雑音で決定された候補同士が、第１段目のセレクタ１０３，…，１３１に入力される。セレクタ１００，…，１３１の数は３２個である。
【００９４】
セレクタ２００には、セレクタ１００により選択された遷移可否と識別値、セレクタ１０１により選択された遷移可否と識別値が入力される。セレクタ２０１には、セレクタ１０２により選択された遷移可否と識別値、セレクタ１０３により選択された遷移可否と識別値が入力される。セレクタ２０２には、セレクタ１０４により選択された遷移可否と識別値、セレクタ１０５により選択された遷移可否と識別値が入力される。以降同様にして、独立熱雑音で決定された候補同士の絞込み結果が、第２段目のセレクタ２０３，…，２１５に入力される。セレクタ２００，…，２１５の数は１６個である。
【００９５】
セレクタ３００には、セレクタ２００により選択された遷移可否と識別値、セレクタ２０１により選択された遷移可否と識別値が入力される。セレクタ３０１には、セレクタ２０２により選択された遷移可否と識別値、セレクタ２０３により選択された遷移可否と識別値が入力される。以降同様にして、独立熱雑音で決定された候補同士の絞込み結果が、第３段目のセレクタ３０２，…，３０７に入力される。セレクタ３００，…，３０７の数は８個である。
【００９６】
セレクタ４００には、セレクタ３００により選択された遷移可否と識別値、セレクタ３０１により選択された遷移可否と識別値が入力される。セレクタ４０１には、セレクタ３０２により選択された遷移可否と識別値、セレクタ３０３により選択された遷移可否と識別値が入力される。以降同様にして、独立熱雑音で決定された候補同士の絞込み結果が、第４段目のセレクタ４０２，４０３に入力される。セレクタ４００，４０１，４０２，４０３の数は４個である。
【００９７】
セレクタ５００には、セレクタ４００により選択された遷移可否と識別値、セレクタ４０１により選択された遷移可否と識別値が入力される。セレクタ５０１には、セレクタ４０２により選択された遷移可否と識別値、セレクタ４０３により選択された遷移可否と識別値が入力される。
【００９８】
セレクタ６００には、セレクタ５００により選択された遷移可否と識別値、セレクタ５０１により選択された遷移可否と識別値が入力される。セレクタ６００は、２つの入力から１つの中間候補を選択し、選択した中間候補を出力する。
【００９９】
第１部分セレクタツリーＴ０，Ｔ１，…，Ｔ１５によれば、独立熱雑音で決定された候補同士の絞込み結果として、１６個の中間候補が出力される。１６個の中間候補は、部分セレクタ部５０ｂにおける第２部分セレクタツリーにより、１つの候補に絞り込まれる。
【０１００】
図１０は、第２部分セレクタの例を示す図である。
部分セレクタ部５０ｂは、第２部分セレクタツリーＴ２０を有する。第２部分セレクタツリーＴ２０は、第２の選択回路の一例である。ここで、第２部分セレクタツリーＴ２０におけるセレクタの段数を、第１部分セレクタツリーＴ０，…，Ｔ１５における第６段目に後続する段数として記載する。
【０１０１】
第２部分セレクタツリーＴ２０は、第７段目のセレクタ７００，７０１，…，７０７、第８段目のセレクタ８００，８０１，８０２，８０３、第９段目のセレクタ９００，９０１および第１０段目のセレクタ１０００を有する。
【０１０２】
セレクタ７００，…，７０７のそれぞれには、選択回路部５６ａ０に属する２つのセレクタにより出力された中間候補が、２つずつ入力される。
セレクタ８００，８０１，８０２，８０３のそれぞれには、前段の２つのセレクタにより選択された中間候補が、２つずつ入力される。例えば、セレクタ８００には、前段のセレクタ７００により選択された中間候補と、セレクタ７０１により選択された中間候補とが入力される。
【０１０３】
セレクタ９００，９０１のそれぞれには、前段の２つのセレクタにより選択された中間候補が、２つずつ入力される。例えば、セレクタ９００には、前段のセレクタ８００により選択された中間候補と、セレクタ８０１により選択された中間候補とが入力される。
【０１０４】
セレクタ１０００には、セレクタ９００により選択された中間候補と、セレクタ９０１により選択された中間候補とが入力される。セレクタ１０００は、２つの中間候補から１つの状態遷移を選択し、選択した１つの状態遷移を出力する。
【０１０５】
第２部分セレクタツリーＴ２０の各セレクタでは、熱雑音を共用して遷移可否が決定された候補同士が当たり得る。
なお、セレクタ部５０に属する各セレクタは、遷移可否ｆｉの生成と識別値の選択と共に、選択した方の状態変数を識別する識別値を１ビット生成し出力することにより、段を経る毎に、識別値のビット長が１ビットずつ増し、最終段（セレクタ１０００）では、１０ビットのインデックスが生成されて、出力される。
【０１０６】
以上のように、遷移制御部４０は、セレクタツリーの少なくとも１段目（初期のステージ）では、熱雑音を共用する候補同士が当たらないようにする。
ここで、例えば、次のように、初期のステージで熱雑音を共用する候補同士が当たるようにする選択方法も考えられる。
【０１０７】
図１１は、遷移制御部の比較例を示す図である。
比較例でも、第２の実施の形態と同様に、状態変数の数を１０２４個とし、１６個の比較器によって熱雑音を共用するものとする。比較例の遷移制御部は、セレクタ部９０を有する。セレクタ部９０のセレクタツリーでは、第１段目から第４段目までのセレクタにおいて、熱雑音を共用して遷移可否が決定された候補同士が当たる。しかし、この場合、各温度における各状態の占有確率がボルツマン分布から大幅にずれてしまい、解の品質が悪化する。具体的には次の通りである。
【０１０８】
図１２は、熱雑音の共用による分布のずれの例を示す図である。
グラフＧ１０は、熱雑音の共用によるボルツマン分布からのずれを表す。グラフＧ１０の横軸は温度である。グラフＧ１０の縦軸はエネルギー（平均エネルギー）である。
【０１０９】
系列Ｇ１１は、熱雑音を共用しない場合の温度とエネルギーとの関係を表す。系列Ｇ１１は、各温度での各状態の占有確率がボルツマン分布に従う場合の温度とエネルギーとの関係であると言える。
【０１１０】
系列Ｇ１２は、図１１の比較例に対応する、熱雑音を共用する場合の温度とエネルギーとの関係を表す。系列Ｇ１２によれば、熱雑音の共用により、取り得る状態の平均エネルギーが、ボルツマン分布に対して期待される平均エネルギーよりも大幅に低くなっていることが分かる。このように、複数の状態変数で表される状態が、ボルツマン分布に従って生成されていないと、最適化装置１０により求められた解の品質が悪化する。あるいは、解の導出に対して信頼される分布（すなわち、ボルツマン分布）に従って状態が生成されないので、解の信頼性が低下するとも言える。
【０１１１】
熱雑音の共用によりボルツマン分布とのずれが生じる理由として、次の理由が考えられる。熱雑音の共用により、遷移確率が低い状態変数が遷移候補になる時は、同じ山（熱雑音を共用する比較器の集合）から多くの候補が立つ可能性が高まる。このため、初期ステージで熱雑音を共用する候補同士が当たると、遷移確率が低い遷移候補が選ばれにくくなり、当該遷移候補による遷移後の状態の占有確率がボルツマン分布から乖離する。
【０１１２】
そこで、遷移制御部４０は、上記のように、セレクタ部５０において、ｎ段のセレクタツリーの初期のステージでは、熱雑音を共用しない候補同士が当たるようにし、熱雑音を共用する候補同士が当たらないようにする。
【０１１３】
図１３は、ボルツマン分布に対するずれの改善例を示す図である。
グラフＧ２０は、第２の実施の形態におけるボルツマン分布に対するずれの改善例を表す。グラフＧ２０の横軸は温度である。グラフＧ２０の縦軸はエネルギー（平均エネルギー）である。
【０１１４】
グラフＧ２０には、図１２で例示した系列Ｇ１１，Ｇ１２も記されている。系列Ｇ２１は、初段（第１段目）だけ独立熱雑音の候補同士が当たるようにした場合の温度と平均エネルギーとの関係を示す。系列Ｇ２２は、第１段目から第２段目までを独立熱雑音の候補同士が当たるようにした場合の温度と平均エネルギーとの関係を示す。系列Ｇ２３は、第１段目から第３段目までを独立熱雑音の候補同士が当たるようにした場合の温度と平均エネルギーとの関係を示す。系列Ｇ２４は、第１段目から第４段目までを独立熱雑音の候補同士が当たるようにした場合の温度と平均エネルギーとの関係を示す。
【０１１５】
系列Ｇ２１によれば、初段を独立熱雑音の候補同士が当たるようにするだけでも、系列Ｇ１２よりボルツマン分布からのずれは低減される。更に、初段だけでなく、第２段目、第３段目、第４段目と、共通熱雑音の候補同士を当てない初期ステージの段数を増やすほど、ボルツマン分布からのずれは大きく改善される。本例の場合、共通熱雑音の候補同士を当てない初期ステージの段数を４段以上とすることで、ボルツマン分布からのずれは、１／１０以下に改善する。こうして、ボルツマン分布からのずれを低減することで、収束特性の変化、解の品質が悪化することを抑制できる。また、解の信頼性の低下を抑制できる。
【０１１６】
例えば、２のｋ乗個（ｋは１以上の整数）のエネルギー変化値（あるいは比較器）に対して熱雑音（または乱数値）を共用する場合を考える。この場合、ｎ段のセレクタツリーのうち、第１段目から第ｎ−ｋ段目までを独立熱雑音の候補同士を当てるようにし、共用熱雑音の候補同士を当てないようにする。これにより、同じ山から立った候補同士（共用熱雑音の候補同士）が当たる確率を最小限にでき、ボルツマン分布からのずれの改善効果が最大になると考えられる。
【０１１７】
上記の例では、遷移制御部２０，４０に用いられるセレクタとして、２入力に対して１つを選択し出力するセレクタを例示したが、３以上の入力に対して１つを選択し出力するセレクタでもよい。この場合も、当該セレクタによるセレクタツリーの少なくとも初段において、独立熱雑音の候補同士を当てることで、収束特性の変化、解の品質の悪化を抑制できる。例えば、ｑ個（ｑは３以上の整数）の入力に対して１つを選択し出力するセレクタを用い、ｑのｋ乗個のエネルギー変化値に対して熱雑音（または乱数値）を共用してもよい。この場合にも、ｎ段のセレクタツリーのうち第１段目から第ｎ−ｋ段目までを独立熱雑音の候補同士を当てるようにし、共用熱雑音の候補同士を当てないようにしてもよい。
【０１１８】
上記第１および第２の実施の形態においては、第１および第２部分セレクタはバイナリツリーで構成されているが、受け入れ可となった遷移候補からランダムに確実に１つを選択しその遷移番号を出力できるものであれば他の構成方法でも同様の効果が得られる。
【０１１９】
また、本発明は、温度をゆっくり下げる疑似焼き鈍し法だけでなく、複数の温度に対する探索を行うレプリカ交換を用いる最適化装置、サンプリング装置でも全く同様に用いることができる。
【符号の説明】
【０１２０】
２０  遷移制御部
２１，２２，２３，２４  熱雑音生成回路
２５，２６，２７，２８  比較回路部
３０  セレクタ部
３０ａ，３０ｂ，３０ｃ，３０ｄ，３０ｅ，３０ｆ  部分セレクタ部
３１  セレクタ
【図１】
2020061012.tif 000011
【図２】
2020061012.tif 000012
【図３】
2020061012.tif 000013
【図４】
2020061012.tif 000014
【図５】
2020061012.tif 000015
【図６】
2020061012.tif 000016
【図７】
2020061012.tif 000017
【図８】
2020061012.tif 000018
【図９】
2020061012.tif 000019
【図１０】
2020061012.tif 000020
【図１１】
2020061012.tif 000021
【図１２】
2020061012.tif 000022
【図１３】
2020061012.tif 000023
【図１４】
2020061012.tif 000024