(57)【要約】【課題】評価関数がペナルティ関数項を含む最適化問題に対して計算時間を短縮する。【解決手段】第１評価関数計算部２１は評価関数のうちコスト関数項Ｅｉを、第２評価関数計算部２２は評価関数のうちペナルティ関数項Ｐｉを計算し、遷移制御部２３は、逆温度βｉとペナルティ係数αｉとの比とＰｉとの積とＥｉとに基づいて、複数の状態遷移の何れかを受け入れるか否かを確率的に決定し、交換制御部１２は、焼鈍部１１ａ１〜１１ａｎの各々に対し、上記比が焼鈍部１１ａ１〜１１ａｎの各々の間でそれぞれ異なるような、βｉとαｉをそれぞれ供給し、焼鈍部１１ａ１〜１１ａｎの各々からＥｉとＰｉを受け、βｉ、αｉ、Ｅｉ、Ｐｉに基づいた確率にしたがって、焼鈍部１１ａ１〜１１ａｎのうちの第１の焼鈍部と第２の焼鈍部に供給されるβｉとαｉの交換をそれぞれ行う。【選択図】図１
2019159637.tif 000002
【特許請求の範囲】
【請求項１】
エネルギーを表す評価関数に含まれる複数の状態変数の値をそれぞれ保持する状態保持部と、
前記複数の状態変数の値の何れかが変化する状態遷移が起こる場合、前記評価関数のうち、コスト関数項を複数の状態遷移のそれぞれに対して計算する第１計算部と、
前記複数の状態変数の値の何れかが変化する状態遷移が起こる場合、前記評価関数のうち、ペナルティ関数項を前記複数の状態遷移のそれぞれに対して計算する第２計算部と、
逆温度とペナルティ係数との比と前記ペナルティ関数項との積と、前記コスト関数項とに基づいて、前記複数の状態遷移の何れかを受け入れるか否かを確率的に決定する制御を行う遷移制御部と、
を各々が有する複数の焼鈍部と、
前記複数の焼鈍部の各々に対して、前記比が前記複数の焼鈍部の各々の間でそれぞれ異なるような、前記逆温度を示す温度情報と前記ペナルティ係数とをそれぞれ供給するとともに、前記複数の焼鈍部の各々から前記コスト関数項と前記ペナルティ関数項とを受け、前記逆温度と前記ペナルティ係数と前記コスト関数項と前記ペナルティ関数項とに基づいた確率にしたがって、前記複数の焼鈍部のうちの第１の焼鈍部と第２の焼鈍部に供給される前記逆温度の交換と、前記第１の焼鈍部と前記第２の焼鈍部に供給される前記ペナルティ係数の交換を行う交換制御部と、
を有する最適化装置。
【請求項２】
前記遷移制御部は、前記比と前記ペナルティ関数項との積と、前記コスト関数項との和である等価エネルギーの、前記複数の状態遷移による変化に基づいて、前記複数の状態遷移の何れかを受け入れるか否かを確率的に決定する制御を行う、請求項１に記載の最適化装置。
【請求項３】
前記交換制御部は、前記逆温度を示す前記温度情報とともに、前記逆温度が小さいほど、前記ペナルティ係数を前記逆温度で割った値を小さくする、前記ペナルティ係数を前記複数の焼鈍部の何れかに供給する、請求項１または２に記載の最適化装置。
【請求項４】
前記交換制御部は、前記複数の焼鈍部の各々に対して、同一逆温度を示す前記温度情報を供給するとともに、前記複数の焼鈍部の各々の間でそれぞれ異なる前記ペナルティ係数を供給する、請求項１または２に記載の最適化装置。
【請求項５】
前記ペナルティ係数は、前記逆温度と比例係数との積から定数を引いた値であり、前記第１計算部は、前記ペナルティ関数項と前記比例係数との積と、前記コスト関数項との和を計算する、請求項１または２に記載の最適化装置。
【請求項６】
前記交換制御部は、前記逆温度と前記ペナルティ係数とを独立に変化させて、前記複数の焼鈍部のそれぞれに割り当てる、請求項１または２に記載の最適化装置。
【請求項７】
複数の焼鈍部の各々に設けられる状態保持部は、エネルギーを表す評価関数に含まれる複数の状態変数の値をそれぞれ保持し、
前記複数の焼鈍部の各々に設けられる第１計算部は、前記複数の状態変数の値の何れかが変化する状態遷移が起こる場合、前記評価関数のうち、コスト関数項を複数の状態遷移のそれぞれに対して計算し、
前記複数の焼鈍部の各々に設けられる第２計算部は、前記複数の状態変数の値の何れかが変化する状態遷移が起こる場合、前記評価関数のうち、ペナルティ関数項を前記複数の状態遷移のそれぞれに対して計算し、
前記複数の焼鈍部の各々に設けられる遷移制御部は、逆温度とペナルティ係数との比と前記ペナルティ関数項との積と、前記コスト関数項とに基づいて、前記複数の状態遷移の何れかを受け入れるか否かを確率的に決定する制御を行い、
交換制御部は、前記複数の焼鈍部の各々に対して、前記比が前記複数の焼鈍部の各々の間でそれぞれ異なるような、前記逆温度を示す温度情報と前記ペナルティ係数とをそれぞれ供給するとともに、前記複数の焼鈍部の各々から前記コスト関数項と前記ペナルティ関数項とを受け、前記逆温度と前記ペナルティ係数と前記コスト関数項と前記ペナルティ関数項とに基づいた確率にしたがって、前記複数の焼鈍部のうちの第１の焼鈍部と第２の焼鈍部に供給される前記逆温度の交換と、前記第１の焼鈍部と前記第２の焼鈍部に供給される前記ペナルティ係数の交換を行う、
最適化装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適化装置及び最適化装置の制御方法に関する。
【背景技術】
【０００２】
現在の社会ではあらゆる分野で情報処理が行われている。これらの情報処理はコンピュータなどの演算装置で行われており、様々なデータを演算、加工し、意味のある結果を得ることにより、予測、決定、制御などが行われる。これらの情報処理の一つとして最適化というものがあり重要な分野となっている。例えばあることを行うのに必要な資源やコストを最小化したり、その効果を最大化する解を求める問題などであり、これらが非常に重要であるのは明らかであろう。
【０００３】
最適化問題の中でも離散最適化問題、組合せ最適化問題などと呼ばれている問題の多くは、変数が連続値ではなく離散的な値を取るため解くのが非常に難しいことが知られている。離散最適化問題を解くのを困難にしている最大の原因は、最適解ではないが局所的近傍のなかで最小値をとる局所解と呼ばれる状態が非常に多数存在することである。
【０００４】
離散最適化問題を解く効率の良い一般解法は存在しないため、問題に固有な性質を利用した近似解法や、問題の性質にあまり頼らないメタヒューリステックと呼ばれる方法を用いる必要がある。
【０００５】
以下に説明する内容は、後者のうちマルコフ連鎖モンテカルロ法を用いた解法に関するもので、特に交換モンテカルロ法、レプリカ交換法と呼ばれる広い意味での疑似焼き鈍し法に関するものである。
【０００６】
疑似焼き鈍し法は、乱数を用いて確率的に状態（変数ベクトルの値）を変化させることで最適解を求める方法である。以下では最適化したい評価関数の値を最小化する問題を例に説明し、評価関数の値をエネルギーと呼ぶことにする。最大化の場合は、評価関数の符号を変えればよい。
【０００７】
疑似焼き鈍し法においては、状態遷移の受け入れ（許容）確率を、その遷移に伴うエネルギー変化と温度を用いて次のように決めれば、時刻（反復回数）無限大の極限で状態が最適解に到達することが証明されている。
【０００８】
【数１】
2019159637.tif 000003
【０００９】
【数２】
2019159637.tif 000004
【００１０】
ここでＴは温度を表すパラメータであり、その初期値は問題に応じて十分大きくとり、十分ゆっくり下げていくことが望ましい。
上記のように疑似焼き鈍し法では、反復回数を無限に取れば最適解が得られるが、現実には有限の反復回数で解を得る必要があるため、最適解を確実に求めることはできない。また上記のように温度の下がり方が非常にゆっくりであるため、有限時間では十分に温度が下がらない。したがって実際の疑似焼き鈍し法では理論的に収束することが保証される温度変化ではなくより速く温度を下げることが多い。
【００１１】
実際の擬似焼き鈍し法では、初期状態から初めて、温度を下げながら上記反復が繰り返され、一定の反復回数に達したり、エネルギーが一定の値を下回るなどの終了判定条件が満たされたとき、動作が終了する。出力する答えは終了時の状態である。ただし、実際には有限の反復回数では温度が０にならないため、終了時においても状態の占有率はボルツマン分布などで表される分布をもっており、必ずしも最適値や良い解になっているとは限らない。したがって、反復の途中でこれまでに得られたエネルギーが最低の状態を保持し、最後にそれを出力するのが現実的な解法となる。
【００１２】
上記の説明からある程度想像できると思われるが、疑似焼き鈍し法は汎用的で非常に魅力的ではあるが、温度をゆっくり下げる必要があるため計算時間が比較的長くなってしまうという問題がある。さらにその温度の下げ方を問題に合わせて適切に調節することが難しいという問題もある。温度の下げ方が遅すぎると有限時間ではあまり温度が下がらないため、最終的な熱分布のエネルギー範囲が広いため良い解の占有確率が上がらない。逆に速く下げすぎると、局所解を脱出する前に温度が下がってしまい、悪い解に捕まったままになってしまうため、良い解が得られる確率が下がってしまう。
【００１３】
レプリカ交換法（例えば、非特許文献１参照）は複数の温度を用いたモンテカルロ探索を同時に行い、ある反復回数ごとに、それぞれ状態のエネルギーを比較し、適切な確率で２つの温度に対する状態を交換するという操作を行う方法である。
【００１４】
図５は、通常のレプリカ交換法を用いた最適化装置の構成例を示す図である。最適化装置５０は、通常の疑似焼き鈍し法を用いた最適化装置と異なり、複数のモンテカルロ探索部（図５では焼鈍部５１ａ１，５１ａ２，…，５１ａｉ，…，５１ａｎ）と、交換制御部５２とを有する。交換制御部５２は、焼鈍部５１ａ１〜５１ａｎに逆温度βｉ（Ｔの逆数）（１≦ｉ≦ｎ）を与える。
【００１５】
図５には、焼鈍部５１ａｉの例が示されている。他の焼鈍部も同様の構成である。焼鈍部５１ａｉは、状態保持部６０、評価関数計算部６１、遷移制御部６２を有する。
状態保持部６０は、評価関数に含まれる複数の状態変数の値を保持する。また、状態保持部６０は、状態遷移の可否を示すフラグｆと、そのフラグｆが示す状態変数の番号（インデックス）Ｎに基づいて、複数の状態変数の値（上記変数ベクトルの値）である状態ｓｉを更新する。
【００１６】
評価関数計算部６１は、状態変数の変化（状態遷移）に伴うエネルギーの変化を計算する。例えば、評価関数が２つの状態変数間の結合で表されるイジングモデルで表され、しかも一度に1つの状態変数の遷移のみを許す場合、評価関数計算部６１は、各状態変数の値と、状態変数間の結合の強さを示す結合係数と、番号Ｎと、フラグｆとに基づいて、複数の状態変数のそれぞれの変化（状態遷移）に伴うエネルギー変化を計算する。エネルギー変化ΔＥｉ，ｊは、ｊ番目の状態変数の変化に伴うエネルギー変化を示す。なお、計算したい最適化問題に応じた結合係数の値は、予めメモリまたはレジスタなどに記憶されている。評価関数がイジングモデルでない場合、及び一度に複数の状態変数の遷移を許す場合には、状態遷移の番号と変化する状態変数の番号は必ずしも一致しないが、状態遷移番号に対するエネルギー変化を適切に計算できればよい。
【００１７】
遷移制御部６２は、通常の擬似焼き鈍し法と同様に、エネルギー変化ΔＥｉ，ｊと交換制御部５２により割り当てられた逆温度βｉを用いて、ｊ番目の状態変数の状態遷移の受け入れ確率を以下の（式２）により決定することで、モンテカルロ探索を行う。
【００１８】
【数３】
2019159637.tif 000005
【００１９】
なお、（式２）において、関数ｆは（式１−１）と同じものであり、例えば（式１−２）のメトロポリス法のものが用いられる。遷移制御部６２は、上記の状態遷移の受け入れ確率に基づいて、状態遷移の可否を示すフラグｆと、そのフラグｆが示す状態遷移の番号を出力する。また、遷移制御部６２は、エネルギー変化ΔＥｉ，ｊに基づいて、エネルギーＥｉを更新して出力する。
【００２０】
交換制御部５２は、一定の反復回数ごとに各焼鈍部におけるエネルギーＥｉを観測し、焼鈍部５１ａ１〜５１ａｎのうちの２つにおけるエネルギーと温度を用い、以下の（式３）で表される交換確率に基づいて２つの焼鈍部に供給する逆温度βｉ，βｊを交換する。
【００２１】
【数４】
2019159637.tif 000006
【００２２】
なお、（式３）では、βｉを焼鈍部５１ａｉに与えられた逆温度、βｊを図示しないｊ番目の焼鈍部に与えられた逆温度、Ｅｉを焼鈍部５１ａｉにおけるエネルギー、Ｅｊをｊ番目の焼鈍部におけるエネルギーとしている。なお、（式３）において、関数ｆは（式１−１）と同じものであり、例えば（式１−２）のメトロポリス法のものが用いられる。
【００２３】
このような交換を行ってもそれぞれの温度の状態の確率分布はその温度に対するボルツマン分布に収束する。そして、この分布に収束するのに必要とされる緩和時間は、交換を行わない時より著しく短縮することができる。
【先行技術文献】
【特許文献】
【００２４】
【特許文献１】特開平１０−２４７１８６号公報
【特許文献２】特開平９−３４９５１号公報
【非特許文献】
【００２５】
【非特許文献１】Koji Hukushima and Koji Nemoto, "Exchange Monte Carlo Method and Application to Spin Glass Simulations", Journal of the Physical Society of Japan, June 1996, Vol.65, No.6, pp.1604-1608.
【非特許文献２】Zheng Zhu, Chao Fang and Helmut G. Katzgraber, "borealis - A generalized global update algorithm for Boolean optimization problems", arXiv:1605.09399v1 [physics.comp-ph], 30 May 2016.
【発明の概要】
【発明が解決しようとする課題】
【００２６】
上記のように、レプリカ交換法は最適化問題を解く場合に非常に強力な加速手段となるが、レプリカ交換法を用いればどのような問題も高速に解けるようになるわけではない。  通常の擬似焼き鈍し法やレプリカ交換法で最適化問題を解く場合、最小化すべき評価関数は、本来最小化したい数値を表すコスト関数項と、解が満たさなければならない制約条件に対する違反に対するペナルティ関数項からなる場合が多い。ペナルティ関数項の割合を小さくしすぎると、制約を満たさない解のエネルギーが最適解のエネルギーより小さくなってしまうため、問題に応じてある程度以上大きな値としなければならない。一方モンテカルロ探索のための状態遷移においては、制約を満たす状態だけを通って解が最適解に到達できる問題はほとんどない。そのため、解が制約を満たさない状態を経由することが必要になるが、ペナルティ関数項が大きい場合には、エネルギーの高い状態を経由するために大きな熱励起が必要になり、ほとんど遷移が起こらなくなってしまう。したがって、ペナルティ関数項をかなり大きくしなければ制約が満たされない問題では、最適解またはそれとエネルギーが近い解を得るのには非常に長い時間がかかってしまうことになり、レプリカ交換法による緩和時間が短縮があっても、実用的な時間では解けない場合がある。
【００２７】
本発明は、レプリカ交換法の概念を拡張することで、ペナルティ関数項を小さくできない場合でも良い解を短い時間で得ることを目指すものである。
なお、例えば、非特許文献２にはペナルティ関数項を変化させたレプリカ交換法を示唆する記述がある。しかしながらその具体的な実現方法は述べられていない。
【００２８】
１つの側面では、本発明は、評価関数がペナルティ関数項を含む最適化問題の計算時間を短縮可能な最適化装置及び最適化装置の制御方法を提供することを目的とする。
【課題を解決するための手段】
【００２９】
１つの実施態様では、エネルギーを表す評価関数に含まれる複数の状態変数の値をそれぞれ保持する状態保持部と、前記複数の状態変数の値の何れかが変化する状態遷移が起こる場合、前記評価関数のうち、コスト関数項を複数の状態遷移のそれぞれに対して計算する第１計算部と、前記複数の状態変数の値の何れかが変化する状態遷移が起こる場合、前記評価関数のうち、ペナルティ関数項を前記複数の状態遷移のそれぞれに対して計算する第２計算部と、逆温度とペナルティ係数との比と前記ペナルティ関数項との積と、前記コスト関数項とに基づいて、前記複数の状態遷移の何れかを受け入れるか否かを確率的に決定する制御を行う遷移制御部と、を各々が有する複数の焼鈍部と、前記複数の焼鈍部の各々に対して、前記比が前記複数の焼鈍部の各々の間でそれぞれ異なるような、前記逆温度を示す温度情報と前記ペナルティ係数とをそれぞれ供給するとともに、前記複数の焼鈍部の各々から前記コスト関数項と前記ペナルティ関数項とを受け、前記逆温度と前記ペナルティ係数と前記コスト関数項と前記ペナルティ関数項とに基づいた確率にしたがって、前記複数の焼鈍部のうちの第１の焼鈍部と第２の焼鈍部に供給される前記逆温度の交換と、前記第１の焼鈍部と前記第２の焼鈍部に供給される前記ペナルティ係数の交換を行う交換制御部と、を有する最適化装置が提供される。
【００３０】
また、１つの実施態様では、最適化装置の制御方法が提供される。
【発明の効果】
【００３１】
１つの側面では、本発明は、評価関数がペナルティ関数項を含む最適化問題に対して計算時間を短縮できる。
【図面の簡単な説明】
【００３２】
【図１】拡張したレプリカ交換法を用いた最適化装置の構成例を示す図である。
【図２】１０２４ビットのイジング評価関数に対するシミュレーション結果の例を示す図である。
【図３】４つの実施の形態におけるパラメータの決定方法をまとめた図である。
【図４】最適化装置の動作例を示すフローチャートである。
【図５】通常のレプリカ交換法を用いた最適化装置の構成例を示す図である。
【発明を実施するための形態】
【００３３】
図１に本発明で提案する拡張したレプリカ交換法を用いた最適化装置の構成例を示す。なお、以下の説明では、最適化装置１０の焼鈍部１１ａ１，１１ａ２，…，１１ａｉ，…，１１ａｎのそれぞれが計算する評価関数の数、及びそれらの線形和をとるためのパラメータの数をそれぞれ２として説明しているが、それぞれより大きな値であってもよい。
【００３４】
通常のレプリカ交換法との主な違いは、４つある。その１つ目は、交換制御部１２が、逆温度βｉ（１≦ｉ≦ｎ）とペナルティ係数αｉという２つのパラメータを焼鈍部１１ａ１〜１１ａｎのそれぞれに与えることである。２つ目は、焼鈍部１１ａ１〜１１ａｎのそれぞれは、２つの評価関数計算部（第１評価関数計算部及び第２評価関数計算部）をもち、２つの評価関数計算部は最小化したいコスト関数項Ｅｉと制約違反を表すペナルティ関数項Ｐｉをそれぞれ独立に計算することである。なお、Ｅｉは、背景技術の説明ではエネルギーを表す記号として用いているが、以下ではコスト関数項を表す記号として用いる。３つ目は、焼鈍部１１ａ１〜１１ａｎのそれぞれの遷移制御部はコスト関数項Ｅｉとペナルティ関数項Ｐｉと逆温度βｉとペナルティ係数αｉとから計算される等価エネルギーの変化を用いて遷移を許容するかどうかを決めることである。４つ目は、交換制御部１２は、一定の反復回数ごとに焼鈍部１１ａ１〜１１ａｎのそれぞれにおける状態のコスト関数項Ｅｉとペナルティ関数項Ｐｉを観測し、２つの焼鈍部のコスト関数項Ｅｉとペナルティ関数項Ｐｉと逆温度βｉとペナルティ係数αｉの関係に応じた確率で、両焼鈍部の互いの逆温度βｉを交換するとともに、互いのペナルティ係数αｉを交換することである。
【００３５】
図１には、焼鈍部１１ａｉの例が示されている。他の焼鈍部も同様の構成である。焼鈍部１１ａｉは、状態保持部２０、第１評価関数計算部２１、第２評価関数計算部２２、遷移制御部２３を有する。
【００３６】
状態保持部２０は、評価関数に含まれる複数の状態変数の値をそれぞれ保持する。また、状態保持部２０は、状態遷移の可否を示すフラグｆと、そのフラグｆが示す状態遷移の番号Ｎに基づいて、複数の状態変数の値である状態ｓｉを更新する。
【００３７】
第１評価関数計算部２１は、状態遷移が起こる場合、評価関数のうち、コスト関数項Ｅｉを複数の状態遷移のそれぞれに対して計算する。
第２評価関数計算部２２は、状態遷移が起こる場合、評価関数のうち、ペナルティ関数項Ｐｉを複数の状態遷移のそれぞれに対して計算する。第１評価関数計算部２１と第２評価関数計算部２２は、前述の評価関数計算部６１がエネルギー変化を計算するのと同様の処理により、コスト関数項Ｅｉまたはペナルティ関数項Ｐｉを計算する。第１評価関数計算部２１と第２評価関数計算部２２は、例えば、積和演算回路などの論理回路を用いて実現できる。
【００３８】
遷移制御部２３は、交換制御部１２から供給される逆温度βｉとペナルティ係数αｉとコスト関数項Ｅｉとペナルティ関数項Ｐｉとに基づいて、複数の状態遷移の何れかを受け入れるか否かを確率的に決定する制御を行う。遷移制御部２３は、以下の（式４）で表される等価エネルギーＥｅｑｉを用いて、通常のモンテカルロ反復を行う。
【００３９】
【数５】
2019159637.tif 000007
【００４０】
等価エネルギーＥｅｑｉの変化は以下の（式５）で表される。
【００４１】
【数６】
2019159637.tif 000008
【００４２】
したがって、状態遷移の受け入れ確率ｐは、以下の（式６）で表される。
【００４３】
【数７】
2019159637.tif 000009
【００４４】
交換制御部１２は、一定の反復回数ごとに各焼鈍部の状態のコスト関数項とペナルティ関数項を観測し、２つの焼鈍部のコスト関数項とペナルティ関数項と逆温度とペナルティ係数を用いて、以下の（式７）により求められる確率で２つの焼鈍部の逆温度βｉ，βｊとペナルティ係数αｉ，αｊを交換する。
【００４５】
【数８】
2019159637.tif 000010
【００４６】
なお、（式７）では、βｊを図示しないｊ番目の焼鈍部に与えられた逆温度、αｊをｊ番目の焼鈍部に与えられたペナルティ係数、Ｅｊをｊ番目の焼鈍部が計算したコスト関数項、Ｐｊをｊ番目の焼鈍部が計算したペナルティ関数項としている。なお、（式７）において、関数ｆは（式１−１）と同じものであり、例えば（式１−２）のメトロポリス法のものが用いられる。
【００４７】
なお、交換制御部１２は、（式７）で示される確率ｐｉｊを計算するための減算回路、加算回路、乗算回路及びｅｘｐ関数の計算回路のほか、乱数を生成する回路と、その乱数と確率ｐｉｊとの比較結果に基づいて交換可否を決定する回路などを用いて実現できる。
【００４８】
以下、最適化装置１０の動作原理及び効果を説明する。
以下では焼鈍部１１ａ１〜１１ａｎのそれぞれの状態（レプリカ）をｓｉ（１≦ｉ≦ｎ）と表記する。そして、等価エネルギーＥｅｑｉを上記（式４）とし、焼鈍部１１ａ１〜１１ａｎの全ての状態を１つにまとめた（直積）状態空間ｓ＝（ｓ１，ｓ２，…，ｓｎ）における全エネルギーを以下の（式８）のように定める。
【００４９】
【数９】
2019159637.tif 000011
【００５０】
（式８）において、βは状態空間ｓにおける逆温度を示す。遷移として各レプリカ内の状態変化Δｓｉと、レプリカ間の状態の交換のみを考慮した場合、前者に対する全エネルギー変化と温度の比は、以下の（式９）で表され、後者に対する全エネルギー変化と温度の比は、以下の（式１０）で表される。
【００５１】
【数１０】
2019159637.tif 000012
【００５２】
【数１１】
2019159637.tif 000013
【００５３】
これらを用いてメトロポリス法などで遷移を許容すれば、状態ｓは逆温度β、エネルギーＥで定まるボルツマン分布に収束する。このとき、各焼鈍部内の状態ｓｉに注目すると、逆温度βｉと等価エネルギーＥｅｑｉで定まるボルツマン分布に収束する。
【００５４】
前者の遷移と後者の遷移を同時に行う必要はない。別々にしても、有限回の反復でどの状態へも遷移できるし、ボルツマン分布における詳細平衡も成り立つからである。前者の遷移は各部分空間である状態ｓｉに対して独立であるのでレプリカごとに並列に行うことができる。
【００５５】
低温で局所解に陥ってしまった状態は、通常のレプリカ交換法と同様に高い温度に移ることにより遷移が起こりやすくなり、局所解からの脱出が容易になる。また、交換制御部１２は、高温ほど（βｉが小さいほど）、αｉ／βｉが小さくなるようにペナルティ係数αｉを選べば高い温度では超えなければならない障壁の高さが低くなるため、さらに局所解からの脱出が容易になる。したがって、通常の擬似焼き鈍し法及び通常のレプリカ交換法よりも、局所解からの脱出が促進されエネルギー降下が高速化され、高速なモンテカルロ探索が可能となる。つまり、最適化問題の計算時間が短縮される。
【００５６】
また、低温ではαｉ／βｉが十分大きくなるようにしておけば、低温では制約をみなさない解は許容されなくなる。したがって、低温の焼鈍部には、制約を満たしたうえでエネルギーの小さい望ましい解が集まりやすくなる。
【００５７】
上記説明では状態を交換するものとしているが、状態を交換する代わりに逆温度βｉとペナルティ係数αｉを交換しても効果は同じである。したがって、上記の動作は図１に示した最適化装置１０の動作と実質的に同じになっていることがわかる。
【００５８】
以上のことから図１に示したような最適化装置１０によれば、ペナルティ関数項Ｐｉの割合を大きくしなければ制約違反の解が出てしまうような問題に対しても、正しい解を得るための計算時間を短縮することが可能となることがわかる。
【００５９】
以下、実際のαｉ／βｉの定め方についての４つの実施の形態と、上記効果のソフトウェアシミュレーションによる実証例を説明する。なお、上記説明では、簡単のため、独立に計算する２つの評価関数が、コスト関数項のみからなるものとペナルティ関数項のみからなるものとしているが、線型独立であれば第３の実施の形態において示すように両方が混ざったものでもよい。
【００６０】
上記拡張したレプリカ交換法は、前述した４つの主な違いを除くと、通常のレプリカ交換方法とほぼ同じであり、その他の部分については、通常のレプリカ交換法を実現する構成に対して何ら変更を加えなくてもよい。したがって、レプリカ内で許されうる状態遷移の集合や、評価関数の関数形やその計算方法などにはまったく依存せずに、上記拡張したレプリカ交換法を適用することができる。
【００６１】
（第１の実施の形態）
第１の実施の形態においては、交換制御部１２は、逆温度βｉが大きくなるほどαｉ／βｉが大きくなるように逆温度βｉとペナルティ係数αｉを変化させるが、その変え方についてはそれ以上の制約はない。したがって、最適化装置１０の構成及び動作については、上記の説明通りである。
【００６２】
各レプリカに対する等価エネルギーＥｅｑｉは（式４）に示したようになるので、逆温度βｉの小さい（温度の高い）レプリカ内の状態遷移は逆温度βｉの大きいレプリカに比べて起こりやすい。
【００６３】
交換制御部１２は、上記の（式７）により表せる確率にしたがって逆温度βｉとペナルティ係数αｉの交換を一緒の組として交換する。これにより、コスト関数項Ｅｉ及びペナルティ関数項Ｐｉの小さな（望ましい）状態を取るレプリカに大きな逆温度βｉとペナルティ係数αｉが割り当てられるように交換が起こる。
【００６４】
逆温度βｉとペナルティ係数αｉとして例えば以下のようなものが用いられる。例えば逆温度βｉを等比数列となるように定めた場合、ペナルティ係数αｉとして、逆温度βｉより公比の大きな等比数列や、同じ公比の等比数列に単調増加数列（例えば等差数列）を掛けたものを用いればよい。
【００６５】
前述のように、有限温度のマルコフ連鎖モンテカルロ法において状態は収束しないので、モンテカルロ探索における最低エネルギーの状態を保持し、最終的な答としてそれを出力することになる。各レプリカは交換制御部１２の制御のもと、逆温度βｉとペナルティ係数αｉの組を交換しながらモンテカルロ探索を行うが、逆温度βｉが小さい時にはαｉ／βｉが小さいため制約を満たさない状態が最低エネルギーを取る可能性がある。この値は大域解の値におけるエネルギーより小さい可能性がある。
【００６６】
したがって、例えば交換制御部１２が行う最低エネルギーとなる状態の判定では、各温度での等価エネルギーＥｅｑｉではなく、別に定義された共通の評価関数が用いられる。制約違反の無い解を選ぶため、α／βが十分大きい評価関数が用いられる。もしくは、ペナルティ関数項Ｐｉが０となるものの中から、コスト関数項Ｅｉが最低になるものが選ばれる。この評価関数は、コスト関数項Ｅｉとペナルティ関数項Ｐｉの線型和を取るためのハードウェアのみで計算できる。
【００６７】
例えば、焼鈍部１１ａ１〜１１ａｎのそれぞれは、コスト関数項Ｅｉとペナルティ関数項Ｐｉと全ての焼鈍部に共通な十分大きいα／βを用いて等価エネルギーの計算を行い、最低の等価エネルギーとその時の状態を保持する。焼鈍部１１ａ１〜１１ａｎでの所定反復回数のモンテカルロ探索の終了時に、各焼鈍部に保持された最低の等価エネルギーとその時の状態を全て出力する、もしくはその中で等価エネルギーが最低のものを出力する。
【００６８】
図２は、１０２４ビットのイジング評価関数に対するシミュレーション結果の例を示す図である。横軸は反復回数、縦軸は最低エネルギーの平均値である。図２において、結果３０は、図５の最適化装置５０を用いた通常のレプリカ交換法によるシミュレーション結果を示し、結果３１は、図１の最適化装置１０を用いた拡張したレプリカ交換法によるシミュレーション結果を示している。
【００６９】
なお、レプリカ数（焼鈍部１１ａ１〜１１ａｎの数）は１００とし、逆温度βｉとペナルティ係数αｉとして、下記の値を用いた。
βｉ＝０．０１２５×２０ｉ／９９
αｉ＝βｉ×（０．１＋０．９×ｉ／９９）
通常のレプリカ交換法でも同じ逆温度βｉを用いたが、αｉ＝βｉである。
【００７０】
図２に示すように、近似解が得られるまでの反復回数で比較すると約２倍に高速化している。さらに正解に近いエネルギーに到達するまでの時間で比較すると数倍以上に高速化している。
【００７１】
（第２の実施の形態）
第２の実施の形態において、交換制御部１２は、逆温度βｉを全て同じ値βとし、ペナルティ係数αｉを変化させる。例えば交換制御部１２は、ペナルティ係数αｉを、等差数列、等比数列などとなるように定める。
【００７２】
第２の実施の形態において、各レプリカに対する等価エネルギーＥｅｑｉは、Ｅｅｑｉ（ｓｉ）＝Ｅ（ｓｉ）＋（αｉ／β）Ｐ（ｓｉ）で表されるため、ペナルティ係数αｉの小さいレプリカ内では、ペナルティ係数αｉの大きいレプリカ内よりも状態遷移が起こりやすい。したがって、ペナルティ係数αｉの小さいレプリカは通常のレプリカ交換法における高温のレプリカに相当する。
【００７３】
ペナルティ係数αｉが交換される確率は、ｐｉｊ＝ｆ（（αｉ−αｊ）（Ｐｉ−Ｐｊ））で表されるため、ペナルティ関数項Ｐｉの小さな（望ましい）状態を取るレプリカに大きなペナルティ係数αｉが割り当てられるように交換が起こる。
【００７４】
第２の実施の形態によれば、逆温度βｉを全て同じ値βとするため、第１の実施の形態に比べて交換の計算が簡単になるとともに、焼鈍部１１ａ１〜１１ａｎと交換制御部１２との間の通信量を低減できる。
【００７５】
（第３の実施の形態）
第３の実施の形態において、交換制御部１２は、ペナルティ係数αｉをαｉ＝ｃβｉ−ｄとなるように選ぶ。ｃとｄは所定の定数である。
【００７６】
この場合、（式７）より、交換の確率は、ｐｉｊ＝ｆ（（βｉ−βｊ）（Ｅｉ＋ｃＰｉ−Ｅｊ−ｃＰｊ））と表せる。
そして、第１評価関数計算部２１は、Ｅｉ＋ｃＰｉ（またはＥｊ＋ｃＰｊ）を計算し、第２評価関数計算部２２がＰｉ（またはＰｊ）を計算する。これにより、交換制御部１２は、逆温度βｉとペナルティ係数αｉの交換の際、第２評価関数計算部２２の計算結果の受信が不要になる。そのため、第１の実施の形態に比べ交換のための計算が簡単になるとともに、焼鈍部１１ａ１〜１１ａｎと交換制御部１２との間の通信量を低減できる。
【００７７】
（第４の実施の形態）
第４の実施の形態において、交換制御部１２は、逆温度βｉとペナルティ係数αｉを独立に変化させたものを、各レプリカに割り当てる。逆温度βｉの数をＮβ、ペナルティ係数αｉの数をＮαとすると、以下の（式１１）のようになる。
【００７８】
【数１２】
2019159637.tif 000014
【００７９】
同じペナルティ係数（で隣接する逆温度）のレプリカ間における交換の確率は、ｐｉｊ＝ｆ（（βｉ−βｊ）（Ｅｉ−Ｅｊ））と表される。同じ逆温度（で隣接するペナルティ係数）のレプリカ間における交換の確率はｐｉｊ＝ｆ（（αｉ−αｊ）（Ｐｉ−Ｐｊ））と表される。
【００８０】
交換制御部１２は、上記２種類の交換を、一定数の反復ごとに行うが、２つを連続して行っても交互に行ってもよい。コスト関数項Ｅｉ及びペナルティ関数項Ｐｉの小さな（望ましい）状態を取るレプリカに大きな逆温度βｉとペナルティ係数αｉが割り当てられるように交換が起こる。
【００８１】
この方法では、交換はやや複雑になるが、逆温度βｉとペナルティ係数αｉの関係に対する制約は無いため、自由度の高い設定が可能である。
図３は、４つの実施の形態におけるパラメータの決定方法をまとめた図である。
【００８２】
逆温度βｉとペナルティ係数αｉは、上記の４つの何れかの実施の形態の方法にしたがって決定される。
最後に、最適化装置１０の全体の動作の流れをフローチャートでまとまる。
【００８３】
図４は、最適化装置の動作例を示すフローチャートである。
交換制御部１２は、上記各実施の形態で説明したように決定したパラメータ（逆温度βｉとペナルティ係数αｉ）を、焼鈍部１１ａ１〜１１ａｎに供給する（ステップＳ１０）。焼鈍部１１ａ１〜１１ａｎの各々では、モンテカルロ探索が行われる（ステップＳ１１）。モンテカルロ探索は、前述のコスト関数項Ｅｉ及びペナルティ関数項Ｐｉの計算、遷移制御部２３による前述の処理（遷移制御）などを含む。
【００８４】
その後、交換制御部１２は、モンテカルロ探索の終了条件が満たされたか否か（例えば、終了条件となる反復回数に達したか否か）を判定する（ステップＳ１２）。
終了条件が満たされた場合、交換制御部１２は、前述のように最終解を出力し（ステップＳ１３）、処理を終了する。最終解は、例えば、最適化装置１０の外部の装置（例えば、コンピュータ）や、図示しないメモリなどに供給される。
【００８５】
一方、終了条件が満たされていない場合、交換制御部１２は反復回数が所定回数（終了条件の反復回数より小さい値）に達したか否かを判定する（ステップＳ１４）。反復回数が所定回数に達した場合、交換制御部１２は、前述の交換確率により、パラメータの交換処理を行い（ステップＳ１５）、その後、ステップＳ１１からの処理が繰り返される。反復回数が所定回数に達していない場合、ステップＳ１１からの処理が繰り返される。
【００８６】
以上、実施の形態に基づき、本発明の最適化装置及びその制御方法の一観点について説明してきたが、これらは一例にすぎず、上記の記載に限定されるものではない。
例えば、上記の説明では、交換制御部１２は逆温度βｉを焼鈍部１１ａ１〜１１ａｎに供給するとしたが、温度を焼鈍部１１ａ１〜１１ａｎに供給してもよい。その場合、焼鈍部１１ａ１〜１１ａｎは、変換テーブルなどを用いて温度を逆温度βｉに変換して用いてもよい。
【符号の説明】
【００８７】
１０  最適化装置
１１ａ１〜１１ａｎ  焼鈍部
１２  交換制御部
２０  状態保持部
２１  第１評価関数計算部
２２  第２評価関数計算部
２３  遷移制御部
Ｅｉ  コスト関数項
ｆ  フラグ
Ｎ  番号
Ｐｉ  ペナルティ関数項
ｓｉ  状態
αｉ  ペナルティ係数
βｉ  逆温度
【図１】
2019159637.tif 000015
【図２】
2019159637.tif 000016
【図３】
2019159637.tif 000017
【図４】
2019159637.tif 000018
【図５】
2019159637.tif 000019
【手続補正書】
【提出日】平成30年11月20日(2018.11.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
エネルギーを表す評価関数に含まれる複数の状態変数の値をそれぞれ保持する状態保持部と、
前記複数の状態変数の値の何れかが変化する状態遷移が起こる場合、前記評価関数のうち、コスト関数項を複数の状態遷移のそれぞれに対して計算する第１計算部と、
前記複数の状態変数の値の何れかが変化する状態遷移が起こる場合、前記評価関数のうち、ペナルティ関数項を前記複数の状態遷移のそれぞれに対して計算する第２計算部と、
逆温度とペナルティ係数との比と前記ペナルティ関数項との積と、前記コスト関数項とに基づいて、前記複数の状態遷移の何れかを受け入れるか否かを確率的に決定する制御を行う遷移制御部と、
を各々が有する複数の焼鈍部と、
前記複数の焼鈍部の各々に対して、前記比が前記複数の焼鈍部の間でそれぞれ異なる、逆温度を示す温度情報とペナルティ係数とをそれぞれ供給するとともに、前記複数の焼鈍部の各々から受けた、逆温度とペナルティ係数とコスト関数項とペナルティ関数項とに基づいた確率にしたがって、前記複数の焼鈍部のうち、第１の焼鈍部に供給される第１の逆温度と第２の焼鈍部に供給される第２の逆温度とを交換するとともに、前記第１の焼鈍部に供給される第１のペナルティ係数と前記第２の焼鈍部に供給される第２のペナルティ係数とを交換するか、または、前記第１の焼鈍部が保持する第１の複数の状態変数の値と前記第２の焼鈍部が保持する第２の複数の状態変数の値とを交換する交換制御部と、
を有する最適化装置。
【請求項２】
前記遷移制御部は、前記比と前記ペナルティ関数項との積と、前記コスト関数項との和である等価エネルギーの、前記複数の状態遷移による変化に基づいて、前記複数の状態遷移の何れかを受け入れるか否かを確率的に決定する制御を行う、請求項１に記載の最適化装置。
【請求項３】
前記交換制御部は、前記逆温度を示す前記温度情報とともに、前記逆温度が小さいほど、前記ペナルティ係数を前記逆温度で割った値を小さくする、前記ペナルティ係数を前記複数の焼鈍部の何れかに供給する、請求項１または２に記載の最適化装置。
【請求項４】
前記交換制御部は、前記複数の焼鈍部の各々に対して、同一逆温度を示す前記温度情報を供給するとともに、前記複数の焼鈍部の各々の間でそれぞれ異なる前記ペナルティ係数を供給する、請求項１または２に記載の最適化装置。
【請求項５】
前記ペナルティ係数は、前記逆温度と比例係数との積から定数を引いた値であり、前記第１計算部は、前記ペナルティ関数項と前記比例係数との積と、前記コスト関数項との和を計算する、請求項１または２に記載の最適化装置。
【請求項６】
前記交換制御部は、前記逆温度と前記ペナルティ係数とを独立に変化させて、前記複数の焼鈍部のそれぞれに割り当てる、請求項１または２に記載の最適化装置。
【請求項７】
エネルギーを表す評価関数に含まれる複数の状態変数の値を保持する状態保持部をそれぞれ備える複数の焼鈍部を有する最適化装置の制御方法において、
前記複数の焼鈍部の各々が有する第１計算部が、前記複数の状態変数の値の何れかが変化する状態遷移が起こる場合、前記評価関数のうち、コスト関数項を複数の状態遷移のそれぞれに対して計算し、
前記複数の焼鈍部の各々が有する第２計算部が、前記複数の状態変数の値の何れかが変化する状態遷移が起こる場合、前記評価関数のうち、ペナルティ関数項を前記複数の状態遷移のそれぞれに対して計算し、
前記複数の焼鈍部の各々が有する遷移制御部が、逆温度とペナルティ係数との比と前記ペナルティ関数項との積と、前記コスト関数項とに基づいて、前記複数の状態遷移の何れかを受け入れるか否かを確率的に決定する制御を行い、
前記最適化装置が有する交換制御部が、前記複数の焼鈍部に対して、前記比が前記複数の焼鈍部の各々の間でそれぞれ異なる、逆温度を示す温度情報とペナルティ係数とをそれぞれ供給するとともに、前記複数の焼鈍部の各々から受けた、逆温度とペナルティ係数とコスト関数項とペナルティ関数項とに基づいた確率にしたがって、前記複数の焼鈍部のうち、第１の焼鈍部に供給される第１の逆温度と第２の焼鈍部に供給される第２の逆温度とを交換するとともに、前記第１の焼鈍部に供給される第１のペナルティ係数と前記第２の焼鈍部に供給される第２のペナルティ係数とを交換するか、または、前記第１の焼鈍部が保持する第１の複数の状態変数の値と前記第２の焼鈍部が保持する第２の複数の状態変数の値とを交換する、
最適化装置の制御方法。