JP7736178B2 - 重み係数算出装置および重み係数算出方法 - Google Patents

Description

本発明は、組合せ最適化問題におけるエネルギーを表す式に含まれる各制約項の重み係数を算出する重み係数算出装置、重み係数算出方法、および、重み係数算出プログラムに関する。

組合せ最適化問題を解く際に、イジングモデルやＱＵＢＯ（Quadratic Unconstrained Binary Optimization ）のエネルギー関数が利用されている。

イジングモデルは、個々のスピンによって磁性体の振る舞いを表す統計力学上のモデルであるが、組合せ最適化問題の求解にも適用可能である。イジングモデルでは、個々のスピンの状態は、“１”または“－１”で表される。

イジングモデルにおけるエネルギー関数は、以下の式（１）のように表される。

式（１）におけるｉ，ｊは、いずれもスピンを表す変数である。また、式（１）におけるｓ_ｉは、スピンｉの状態を表す変数であり、ｓ_ｊは、スピンｊの状態を表す変数である。式（１）におけるｈ_ｉは、スピンｉに対応する定数である。ｉの取り得る値毎に、ｈ_ｉは定数として定められる。式（１）におけるＪ_ｉｊは、スピンｉおよびスピンｊの組合せに対応する定数である。ｉの取り得る値とｊの取り得る値の組合せ毎に、Ｊ_ｉｊは定数として定められる。

ＱＵＢＯは、個々のスピンの状態を“１”または“０”で表すモデルである。

ＱＵＢＯにおけるエネルギー関数は、以下の式（２）のように表される。

式（２）におけるｉ，ｊは、いずれもスピンを表す変数である。また、式（２）におけるｓ_ｉは、スピンｉの状態を表す変数であり、ｓ_ｊは、スピンｊの状態を表す変数である。式（２）におけるＱ_ｉｊは、スピンｉおよびスピンｊの組合せに対応する定数である。ｉの取り得る値とｊの取り得る値の組合せ毎に、Ｑ_ｉｊは定数として定められる。

イジングモデルやＱＵＢＯのエネルギー関数は、シミュレーテッドアニーリングを実行する求解装置に入力される。求解装置は、シミュレーテッドアニーリングによって、組合せ最適化問題の解に該当する各スピンの状態を求める。

以下、ＱＵＢＯのエネルギー関数を求める場合を例にして説明する。ただし、イジングモデルのエネルギー関数を求めることも、下記の説明と同様に説明可能である。

ＱＵＢＯのエネルギー関数は、組合せ最適化問題におけるエネルギーを表す式を変形することによって求められる。この式は、１つ以上の目的関数と１つ以上の制約項の重み付け和を、エネルギーとして表す。１つの制約項は、１つの制約を表す。１つ以上の各目的関数と１つ以上の各制約項には、それぞれ、重み係数が定められている。また、個々の目的関数や個々の制約項は、それ自体で、ＱＵＢＯのエネルギー関数の形式に変形可能である。

例えば、以下に示す式（３）は、組合せ最適化問題におけるエネルギーを表す式の一例である。

Ｅ＝Ｗ_１（目的関数１）＋Ｗ_２（目的関数２）＋Ｗ_３（制約項１）＋Ｗ_４（制約項２）
＋Ｗ_５（制約項３＋制約項４）
・・・（３）

Ｗ_１，Ｗ_２，Ｗ_３，Ｗ_４，Ｗ_５は、それぞれ重み係数である。

式（３）において、Ｗ_５（制約項３＋制約項４）は、複数の制約項（制約項３と制約項４）が共通の重み係数Ｗ_５に関連付けられていることを表している。

式（３）に例示するようなエネルギーを表す式が、ＱＵＢＯのエネルギー関数に変形される。そして、ＱＵＢＯのエネルギー関数は求解装置に入力される。求解装置は、組合せ最適化問題の解に該当する各スピンの状態を求める。

ＱＵＢＯのエネルギー関数に変形されるエネルギーを表す式の具体例を以下に示す。ここでは、都市数が４個である場合の巡回セールスマン問題を例にする。図７は、この巡回セールスマン問題における各スピンの状態の一例を示す模式図である。本例では、エネルギーを表す式は、以下に示す式（４）のように表される。

式（４）の右辺第１項は、目的関数である。本例では、目的関数の重み係数は１である。目的関数におけるｄ_ｉｊは、２つの都市間の距離を表す。式（４）の右辺第２項から第９項までは、制約項である。各制約項には共通の重み係数Ａが定められている。本例の目的関数は、ＱＵＢＯのエネルギー関数の形式になっている。また、８個の各制約項はそれぞれ、それ自体で、ＱＵＢＯのエネルギー関数の形式に変形することができる。

右辺第２項は、図７に示す第１列において１つのスピンだけが１になるという制約である。右辺第３項は、図７に示す第２列において１つのスピンだけが１になるという制約である。右辺第４項は、図７に示す第３列において１つのスピンだけが１になるという制約である。右辺第５項は、図７に示す第４列において１つのスピンだけが１になるという制約である。

右辺第６項は、図７に示す第１行において１つのスピンだけが１になるという制約である。右辺第７項は、図７に示す第２行において１つのスピンだけが１になるという制約である。右辺第８項は、図７に示す第３行において１つのスピンだけが１になるという制約である。右辺第９項は、図７に示す第４行において１つのスピンだけが１になるという制約である。

制約項の値が０に近いほど、その制約項が表す制約がより満たされていることになる。

一般的に、制約項の重み係数の値によっては、求解装置によって得られた解が、制約項が表す制約を満たさない場合がある。そこで、一般的に、シミュレーテッドアニーリングと、制約項の重み係数の修正とを繰り返すことによって、解が制約を満たすような制約項の重み係数を決定している。図８は、制約項の重み係数の決定の一般的な処理経過の例を示すフローチャートである。なお、目的関数の重み係数は、オペレータが固定値として定めているものとする。

まず、各制約項の重み係数を初期化する（ステップＳ１０１）。そして、シミュレーテッドアニーリングを実行し、組合せ最適化問題の解を得る（ステップＳ１０２）。次に、各制約項が示す制約を満たす解が得られたか否かを判定する（ステップＳ１０３）。得られた解において、満たされていない制約があるならば（ステップＳ１０３のＮｏ）、手動または自動で、制約項の重み係数を修正する（ステップＳ１０４）。そして、ステップＳ１０２以降の処理を繰り返す。各制約項が示す制約を全て満たす解が得られたならば（ステップＳ１０３のＹｅｓ）、その時点で得られている各制約項の重み係数を、各制約項の重み係数として決定する。

なお、目的関数の重み係数は、オペレータによって適宜決定されてよい。例えば、式（３）に示す例において、オペレータが、目的関数１が重要であると判断した場合には、オペレータが、目的関数１の重み係数Ｗ_１を大きな値に設定すればよい。

また、特許文献１には、エネルギー関数を、制約条件を表す制約項と、コスト関数を表すコスト項とに分けて定義し、制約項の重み係数の値をパラメータ更新則によって調節して、シミュレーテッドアニーリングを行うことが記載されている。

特開平８－１５３０８５号公報

前述のように、シミュレーテッドアニーリングと、制約項の重み係数の修正とを繰り返しながら、制約を満たす解を得ることができる制約項の重み係数を決定する場合、シミュレーテッドアニーリングを繰り返すことになる。そのため、この方法では、制約項の重み係数の決定に時間がかかる。

そこで、本発明は、組合せ最適化問題のエネルギーを表す式の制約項の重み係数を高速に算出することができる重み係数算出装置、重み係数算出方法、および、重み係数算出プログラムを提供することを目的とする。

本発明による重み係数算出装置は、組合せ最適化問題におけるエネルギーを表す式に含まれる各制約項が入力される入力手段と、制約項毎に、制約項が表す制約に関連する個々のスピンに関連する他の全ての制約が満たされている場合に、前記制約項が表す前記制約が満たされている確率である自動成立率を算出する自動成立率算出手段と、制約項毎に、制約項が表す制約が満たされなくなった場合のエネルギー増加量である制約破壊時のエネルギー増加量を決定するエネルギー増加量決定手段と、制約項毎に、制約項が表す制約に関連するスピンの数を導出するスピン数導出手段と、制約項毎に、前記自動成立率が大きく、前記制約破壊時のエネルギー増加量が大きく、前記スピンの数が多いほど、制約項に対応する重み係数が小さくなるように、制約項に対応する重み係数を算出する重み係数算出手段とを備えることを特徴とする。

本発明による重み係数算出方法は、コンピュータが、組合せ最適化問題におけるエネルギーを表す式に含まれる各制約項の入力を受け付け、制約項毎に、制約項が表す制約に関連する個々のスピンに関連する他の全ての制約が満たされている場合に、前記制約項が表す前記制約が満たされている確率である自動成立率を算出する自動成立率算出処理を実行し、制約項毎に、制約項が表す制約が満たされなくなった場合のエネルギー増加量である制約破壊時のエネルギー増加量を決定するエネルギー増加量決定処理を実行し、制約項毎に、制約項が表す制約に関連するスピンの数を導出するスピン数導出処理を実行し、制約項毎に、前記自動成立率が大きく、前記制約破壊時のエネルギー増加量が大きく、前記スピンの数が多いほど、制約項に対応する重み係数が小さくなるように、制約項に対応する重み係数を算出する重み係数算出処理を実行することを特徴とする。

本発明による重み係数算出プログラムは、組合せ最適化問題におけるエネルギーを表す式に含まれる各制約項が入力される入力手段を備えるコンピュータに、制約項毎に、制約項が表す制約に関連する個々のスピンに関連する他の全ての制約が満たされている場合に、前記制約項が表す前記制約が満たされている確率である自動成立率を算出する自動成立率算出処理、制約項毎に、制約項が表す制約が満たされなくなった場合のエネルギー増加量である制約破壊時のエネルギー増加量を決定するエネルギー増加量決定処理、制約項毎に、制約項が表す制約に関連するスピンの数を導出するスピン数導出処理、および、制約項毎に、前記自動成立率が大きく、前記制約破壊時のエネルギー増加量が大きく、前記スピンの数が多いほど、制約項に対応する重み係数が小さくなるように、制約項に対応する重み係数を算出する重み係数算出処理を実行させる。

本発明によれば、組合せ最適化問題のエネルギーを表す式の制約項の重み係数を高速に算出することができる。

本発明の実施形態の重み係数算出装置の構成例を示すブロック図である。 複数のスピンに対して定められた制約の例を示す模式図である。 １となっているスピンの数がｎ－ａよりも１減少したときのエネルギー増加量、および、１となっているスピンの数がｎ＋ｂよりも１増加したときのエネルギー増加量を示す模式図である。 本発明の実施形態の処理経過の例を示すフローチャートである。 本発明の実施形態の重み係数算出装置に係るコンピュータの構成例を示す概略ブロック図である。 本発明の重み係数算出装置の概要を示すブロック図である。 巡回セールスマン問題における各スピンの状態の一例を示す模式図である。 制約項の重み係数の決定の一般的な処理経過の例を示すフローチャートである。

以下、本発明の実施形態を図面を参照して説明する。

以下の説明では、組合せ最適化問題のエネルギーを表す式から、ＱＵＢＯのエネルギー関数を求める場合を例にして説明する。ただし、イジングモデルのエネルギー関数を求める場合も同様である。

図１は、本発明の実施形態の重み係数算出装置の構成例を示すブロック図である。本実施形態の重み係数算出装置１０は、入力部１と、制約特定部２と、自動成立率算出部３と、エネルギー増加量決定部４と、スピン数導出部５と、重み係数算出部６とを備える。

入力部１には、ＱＵＢＯのエネルギー関数に変形される組合せ最適化問題のエネルギーを表す式における、各目的関数および各制約項が入力される。入力される制約項の個数は１個以上である。目的関数の重み係数は、オペレータによって適宜決定されうるので、目的関数は、入力されなくてもよい。

また、共通の重み係数に関連付けられる複数の制約項が存在する場合、その複数の制約項を指定する情報も、入力部１に入力される。共通の重み係数に関連付けられる複数の制約項が２組以上存在していてもよい。

既に説明したように、１つの制約項は、１つの制約を表す。

入力部１に入力される各目的関数および各制約項はそれぞれ、それ自体で、ＱＵＢＯのエネルギー関数の形式に変形可能である。

入力部１は、各目的関数および各制約項、および、共通の重み係数に関連付けられる複数の制約項が存在する場合にその複数の制約項を指定する情報が入力される入力デバイスである。例えば、入力部１は、記録媒体に記録された目的関数、各制約項、および、共通の重み係数に関連付けられる複数の制約項が存在する場合にその複数の制約項を指定する情報を読み込むデータ読み込み装置等の入力デバイスであってもよい。ただし、上記のように、目的関数は、入力部１に入力されなくてもよい。

制約特定部２は、入力された制約項毎に、制約項が表す制約の内容を特定する。

自動成立率算出部３は、制約毎に（換言すれば、制約項毎に）、自動成立率を算出する。自動成立率とは、制約項が表す制約に関連する個々のスピンに関連する他の全ての制約が満たされている場合に、その制約項が表す制約が満たされている確率である。

スピンと制約とが関連しているとは、その制約が満たされるか否かを判定する際に、そのスピンの状態が参照されるということである。

図２は、複数のスピンに対して定められた制約の例を示す模式図である。各制約Ｃ_１～Ｃ_６の内容は、入力された各制約項に基づいて、制約特定部２によって特定される。本例では、制約Ｃ_１～Ｃ_６がいずれも、１つのスピンだけが１になるという制約であるものとする。以下、１つのスピンだけが１になるという制約を、one-hot 制約と記す。

制約Ｃ_１の自動成立率を例にして説明する。制約Ｃ_１に関連する個々のスピンは、スピン１～４である（図２参照）。その個々のスピンに関連する他の全ての制約は、スピン１に関連する制約Ｃ_２，Ｃ_３、スピン２に関連する制約Ｃ_４、スピン３に関連する制約Ｃ_５、および、スピン４に関連する制約Ｃ_６である（図２参照）。従って、制約Ｃ_１の自動成立率は、制約Ｃ_２～Ｃ_６が全て満たされている場合に、制約Ｃ_１が満たされている確率である。

自動成立率算出部３は、自動成立率を０以上１以下の範囲の値として算出する。

以下、自動成立率の算出対象となる制約を対象制約と記す。また、対象制約に関連する個々のスピンに関連する他の全ての制約をそれぞれ関連制約と記す。自動成立率算出部３は、対象制約の自動成立率を算出するときに、全ての関連制約が満たされているものとして、対象制約に関連する個々のスピン毎に、スピンが１になる確率をそれぞれ算出する。自動成立率算出部３は、その個々のスピンが１になる確率に基づいて、対象制約の自動成立率を算出する。

図２を参照して具体的に説明する。対象制約が制約Ｃ_１であるとする。このとき、制約Ｃ_２～Ｃ_６が関連制約となる。自動成立率算出部３は、関連制約Ｃ_２～Ｃ_６が全て満たされているときに、スピン１が１になる確率（ｓ_１＝１になる確率）、スピン２が１になる確率（ｓ_２＝１になる確率）、スピン３が１になる確率（ｓ_３＝１になる確率）、および、スピン４が１になる確率（ｓ_４＝１になる確率）をそれぞれ算出する。そして、自動成立率算出部３は、算出した上記の確率に基づいて、対象制約の自動成立率を算出する。

具体的な計算例を以下に示す。関連制約Ｃ_２～Ｃ_６は満たされているものとする。制約Ｃ_２に関連するスピンの数は２個である。従って、制約Ｃ_２が満たされているときにｓ_１＝１になる確率は、１／２＝０．５である。また、制約Ｃ_３に関連するスピンの数は４個である。従って、制約Ｃ_３が満たされているときにｓ_１＝１になる確率は、１／４＝０．２５である。制約Ｃ_２，Ｃ_３が満たされているときにｓ_１＝１になる確率は、上記の２つの確率の平均値であり、（０．５＋０．２５）／２＝０．３７５である。

また、制約Ｃ_４に関連するスピンの数は４個である。従って、制約Ｃ_４が満たされているときにｓ_２＝１になる確率は、１／４＝０．２５である。同様に、制約Ｃ_５が満たされているときにｓ_３＝１になる確率も０．２５である。制約Ｃ_６が満たされているときにｓ_４＝１になる確率も０．２５である。

本例では、自動成立率算出部３は、上記のように、対象制約に関連する個々のスピン毎に、スピンが１になる確率を計算する。

次に、自動成立率算出部３は、以下のように、対象制約Ｃ_１の自動成立率を算出する。対象制約Ｃ_１は、one-hot 制約である。従って、自動成立率算出部３は、まず、ｓ_１＝１、かつ、ｓ_２＝ｓ_３＝ｓ_４＝０となる確率を求める。自動成立率算出部３は、この確率を０．３７５＊（１－０．２５）^３＝０．１５８２と算出する。

次に、自動成立率算出部３は、ｓ_２＝１、かつ、ｓ_１＝ｓ_３＝ｓ_４＝０となる確率を求める。自動成立率算出部３は、この確率を（１－０．３７５）＊０．２５＊（１－０．２５）^２＝０．０８７８９と算出する。

自動成立率算出部３は、ｓ_３＝１、かつ、ｓ_１＝ｓ_２＝ｓ_４＝０となる確率、および、ｓ_４＝１、かつ、ｓ_１＝ｓ_２＝ｓ_３＝０となる確率も、それぞれ、上記と同様に、０．０８７８９と算出する。

従って、自動成立率算出部３は、対象制約Ｃ_１（one-hot 制約）が満たされる確率を、０．１５８２＋０．０８７８９＋０．０８７８９＋０．０８７８９＝０．４２２と算出する。

自動成立率算出部３は、対象制約に関連する個々のスピン毎に、スピンが１になる確率を計算することによって、対象制約が任意の制約の場合でも、自動成立率を算出することができる。

上記の説明では、対象制約が制約Ｃ_１である場合を例にして説明した。前述のように、自動成立率算出部３は、制約毎に（制約項毎）に、自動成立率を算出する。

一般的に、制約項の重み係数がより大きければ、その制約項が表す制約はより満たされやすくなる。また、制約項の重み係数がより小さければ、その制約項が表す制約はより満たされにくくなる。自動成立率が高いということは、制約が満たされやすいということであるので、重み係数を小さくしても、制約を満たすことができる。従って、後述の重み係数算出部６は、０以上１以下の範囲の値である自動成立率が大きいほど、重み係数が小さくなるように、重み係数を決定する。

エネルギー増加量決定部４は、制約毎に（換言すれば、制約項毎に）、制約破壊時のエネルギー増加量を決定する。制約破壊時のエネルギー増加量とは、制約項が表す制約が満たされなくなった場合のエネルギー増加量である。

ただし、エネルギー増加量決定部４は、「１となっているスピンの数が第１の所定値以上第２の所定値以下である」という制約、「１となっているスピンの数が所定値以上である」という制約、および、「１となっているスピンの数が所定値以下である」という制約に関して、制約破壊時のエネルギー増加量を算出する。エネルギー増加量決定部４は、その他の制約に関しては、制約破壊時のエネルギー増加量を一律に“１”に決定する。なお、制約項毎の制約の内容は、制約特定部２によって特定されている。

以下、エネルギー増加量決定部４が、「１となっているスピンの数が第１の所定値以上第２の所定値以下である」という制約に関して、制約破壊時のエネルギー増加量を決定する動作の例を説明する。以下、この制約を表す制約項のエネルギーが最小になるときの、１となっているスピンの数をｎ個とする。また、第１の所定値をｎ－ａとし、第２の所定値をｎ＋ｂとする。

図３は、１となっているスピンの数がｎ－ａよりも１減少したときのエネルギー増加量、および、１となっているスピンの数がｎ＋ｂよりも１増加したときのエネルギー増加量を示す模式図である。図３に示すグラフにおいて、横軸は、制約に関連するスピンのうち１となっているスピンの数を示す。また、縦軸は、制約を表す制約項に基づいて定まるエネルギーを示す。

図３に示すように、１となっているスピンの数がｎ－ａよりも１減少したときのエネルギー増加量をＥ_ａと記す。また、１となっているスピンの数がｎ＋ｂよりも１増加したときのエネルギー増加量をＥ_ｂと記す。エネルギー増加量決定部４は、この制約を表す制約項に基づいて、エネルギー増加量Ｅ_ａ，Ｅ_ｂを算出することができる。

また、エネルギー増加量決定部４は、着目している制約項に関して、制約に関連する個々のスピン毎に、関連する他の制約に基づいて、スピンが１になる確率をそれぞれ算出する。エネルギー増加量決定部４は、その確率に基づいて、１となっているスピンの数がｎ－ａ未満になる確率、および、１となっているスピンの数がｎ＋ｂを超える確率をそれぞれ算出する。１となっているスピンの数がｎ－ａ未満になる確率をＰ_ａと記す。１となっているスピンの数がｎ＋ｂを超える確率をＰ_ｂと記す。

エネルギー増加量決定部４は、Ｅ_ａ，Ｅ_ｂ，Ｐ_ａ，Ｐ_ｂを用いて、以下の式（５）によって、「１となっているスピンの数が第１の所定値以上第２の所定値以下である」という制約における制約破壊時のエネルギー増加量を決定する。

（Ｅ_ａ－Ｅ_ｂ）＊Ｐ_ａ／（Ｐ_ａ＋Ｐ_ｂ）＋Ｅ_ｂ ・・・（５）

式（５）によって得られた値が、「１となっているスピンの数が第１の所定値以上第２の所定値以下である」という制約における制約破壊時のエネルギー増加量である。

また、確率Ｐ_ａが０である場合には、エネルギー増加量決定部４は、制約破壊時のエネルギー増加量をＥ_ｂに決定する。

確率Ｐ_ｂが０である場合には、エネルギー増加量決定部４は、制約破壊時のエネルギー増加量をＥ_ａに決定する。

また、「１となっているスピンの数が所定値以上である」という制約に対しては、エネルギー増加量決定部４は、１となっているスピンの数が所定値となっている状態から、１となっているスピンの数が所定値より１少ない状態に変化したときのエネルギー増加量を、制約破壊時のエネルギー増加量として決定する。

また、「１となっているスピンの数が所定値以下である」という制約に対しては、エネルギー増加量決定部４は、１となっているスピンの数が所定値となっている状態から、１となっているスピンの数が所定値より１多い状態に変化したときのエネルギー増加量を、制約破壊時のエネルギー増加量として決定する。

制約破壊時のエネルギー増加量が大きい制約項が表す制約は、シミュレーテッドアニーリング実行時に満たされやすい。従って、制約破壊時のエネルギー増加量が大きい制約項に関しては、重み係数を小さくしても、その制約項が表す制約を満たすことができる。従って、後述の重み係数算出部６は、制約破壊時のエネルギー増加量が大きいほど、重み係数が小さくなるように、重み係数を決定する。

スピン数導出部５は、制約毎に（換言すれば、制約項毎に）、制約に関連するスピンの数を導出する。スピン数導出部５は、制約項に基づいて、その制約項が表す制約に関連するスピンの数を導出すればよい。

制約に関連するスピンの数が多いほど、シミュレーテッドアニーリング実行時に、その制約に関連するスピンが選択され、その選択されたスピンがフリップする確率が高くなる。その結果、その制約は満たされやすい。従って、制約に関連するスピンの数が多いほど、重み係数を小さくしても、制約を満たすことができる。従って、後述の重み係数算出部６は、制約に関連するスピンの数が多いほど、重み係数が小さくなるように、重み係数を決定する。

重み係数算出部６は、制約毎に（換言すれば、制約項毎に）、制約項に対応する重み係数を算出する。重み係数算出部６は、着目している制約項に関して求めた自動成立率、制約破壊時のエネルギー増加量、および、スピンの数に基づいて、その制約項に対応する重み係数を算出する。

前述のように、重み係数算出部６は、０以上１以下の範囲の値である自動成立率が大きいほど、重み係数が小さくなるように、重み係数を決定する。また、重み係数算出部６は、制約破壊時のエネルギー増加量が大きいほど、重み係数が小さくなるように、重み係数を決定する。重み係数算出部６は、制約に関連するスピンの数が多いほど、重み係数が小さくなるように、重み係数を決定する。

具体的には、重み係数算出部６は、以下の式（６）の計算によって、制約項毎に、制約項に対応する重み係数を算出する。

重み係数＝（１－自動成立率）／（制約破壊時のエネルギー増加量＊スピンの数）
・・・（６）

また、重み係数算出部６は、共通の重み係数に関連付けられる複数の制約項が存在する場合、その複数の制約項それぞれに対して式（６）で算出した重み係数の平均値を、その複数の制約項に関連付けられる共通の重み係数として決定する。

例えば、式（３）に示す制約項１、制約項２、制約項３、制約項４が入力され、共通の重み係数に関連付けられる複数の制約項として制約項３および制約項４を指定する情報が入力されたとする。この場合、重み係数算出部６は、制約項１に関して式（６）で算出した値を、制約項１に対応する重み係数Ｗ_３として決定する。同様に、重み係数算出部６は、制約項２に関して式（６）で算出した値を、制約項２に対応する重み係数Ｗ_４として決定する。重み係数算出部６は、制約項３および制約項４に共通の重み係数Ｗ_５を決定する場合、制約項３に関して式（６）で算出した重み係数と、制約項４に関して式（６）で算出した重み係数の平均値を算出し、その平均値を重み係数Ｗ_５として決定する。

制約特定部２、自動成立率算出部３、エネルギー増加量決定部４、スピン数導出部５、および、重み係数算出部６は、例えば、重み係数算出プログラムに従って動作するコンピュータのＣＰＵ（Central Processing Unit ）によって実現される。例えば、ＣＰＵが、コンピュータのプログラム記憶装置等のプログラム記録媒体から重み係数算出プログラムを読み込み、その重み係数算出プログラムに従って、制約特定部２、自動成立率算出部３、エネルギー増加量決定部４、スピン数導出部５、および、重み係数算出部６として動作すればよい。

次に、処理経過について説明する。図４は、本実施形態の処理経過の例を示すフローチャートである。既に説明した事項については、詳細な説明を省略する。

まず、入力部１に、組合せ最適化問題のエネルギーを表す式における各制約項が入力される（ステップＳ１）。ステップＳ１において、エネルギーを表す式における各目的関数も併せて入力部１に入力されてもよい。また、共通の重み係数に関連付けられる複数の制約項が存在する場合、その複数の制約項を指定する情報も、入力部１に入力される。

次に、制約特定部２が、制約項毎に、制約項が表す制約の内容を特定する（ステップＳ２）。

次に、自動成立率算出部３が、制約項毎に、自動成立率を算出する（ステップＳ３）。

また、エネルギー増加量決定部４が、制約項毎に、制約破壊時のエネルギー増加量を決定する（ステップＳ４）。

また、スピン数導出部５が、制約項毎に、制約項が表す制約に関連するスピンの数を導出する（ステップＳ５）。

ステップＳ３，Ｓ４，Ｓ５の実行順序は、限定されない。また、自動成立率算出部３、エネルギー増加量決定部４、および、スピン数導出部５が、ステップＳ３，Ｓ４，Ｓ５を並列に実行してもよい。

次に、重み係数算出部６が、制約項毎に、自動成立率、制約破壊時のエネルギー増加量、および、スピンの数に基づいて、制約項に対応する重み係数を算出する（ステップＳ６）。

また、共通の重み係数に関連付けられる複数の制約項が存在する場合、重み係数算出部６は、その複数の制約項それぞれに対して算出した重み係数の平均値を、その複数の制約項に関連付けられる共通の重み係数として決定する（ステップＳ７）。共通の重み係数に関連付けられる複数の制約項が存在しない場合、重み係数算出部６は、ステップＳ７を実行せずに、ステップＳ６で処理を終了してよい。

重み係数算出部６は、最終的に決定した個々の制約項に対応する個々の重み係数を、例えば、ディスプレイ装置（図示略）に表示してもよい。ただし、個々の制約項に対応する個々の重み係数の出力態様は、上記の例に限定されない。

本実施形態によれば、組合せ最適化問題のエネルギーを表す式における各制約項が重み係数算出装置１０に入力される。また、共通の重み係数に関連付けられる複数の制約項が存在する場合、その複数の制約項を指定する情報も、重み係数算出装置１０に入力される。重み係数算出装置１０は、入力された情報に基づいて、入力された各制約項に対応する重み係数を算出する。このとき、重み係数算出装置１０は、満たされやすい制約を表す制約項に関して、重み係数が小さくなるように、重み係数を算出する。一般的に、制約項の重み係数がより小さければ、その制約項が表す制約はより満たされにくくなる。しかし、本実施形態の重み係数算出装置１０は、満たされやすい制約を表す制約項に関して、重み係数が小さくなるように重み係数を算出するので、重み係数が小さくても、制約を満たすことができる。

また、上記のように、本実施形態の重み係数算出装置１０は、入力された情報に基づいて、入力された各制約項に対応する重み係数を算出するので、シミュレーテッドアニーリングを含む繰り返し処理（図８を参照）を行わずに、各制約項の重み係数を算出することができる。従って、組合せ最適化問題のエネルギーを表す式の各制約項の重み係数を高速に算出することができる。

組合せ最適化問題のエネルギーを表す式の各目的関数および各制約項は、組合せ最適化問題に応じて、予め定められる。そして、本実施形態の重み係数算出装置１０により、各制約項の重み係数が決定される。また、オペレータは、各目的関数の重み係数を適宜、決定すればよい。その結果、各目的関数および各制約項、並びに、各目的関数の重み係数および各制約項の重み係数が定まった状態になる。すなわち、エネルギーを表す式が定まる。従って、エネルギーを表す式をＱＵＢＯのエネルギー関数に変形することができ、そのエネルギー関数を、シミュレーテッドアニーリングを実行する求解装置に入力することで、組合せ最適化問題の解に該当する各スピンの状態を得ることができる。

図５は、本発明の実施形態の重み係数算出装置１０に係るコンピュータの構成例を示す概略ブロック図である。コンピュータ１０００は、ＣＰＵ１００１と、主記憶装置１００２と、補助記憶装置１００３と、インタフェース１００４と、入力デバイス１００５とを備える。

本発明の実施形態の重み係数算出装置１０は、コンピュータ１０００によって実現される。重み係数算出装置１０の動作は、重み係数算出プログラムの形式で補助記憶装置１００３に記憶されている。ＣＰＵ１００１は、その重み係数算出プログラムを補助記憶装置１００３から読み出して、主記憶装置１００２に重み係数算出プログラムを展開し、その重み係数算出プログラムに従って、上記の実施形態で説明した処理を実行する。

補助記憶装置１００３は、一時的でない有形の媒体の例である。一時的でない有形の媒体の他の例として、インタフェース１００４を介して接続される磁気ディスク、光磁気ディスク、ＣＤ－ＲＯＭ（Compact Disk Read Only Memory ）、ＤＶＤ－ＲＯＭ（Digital Versatile Disk Read Only Memory ）、半導体メモリ等が挙げられる。また、プログラムが通信回線によってコンピュータ１０００に配信される場合、配信を受けたコンピュータ１０００がそのプログラムを主記憶装置１００２に展開し、そのプログラムに従って上記の実施形態で説明した処理を実行してもよい。

また、各構成要素の一部または全部は、汎用または専用の回路（circuitry ）、プロセッサ等やこれらの組合せによって実現されてもよい。これらは、単一のチップによって構成されてもよいし、バスを介して接続される複数のチップによって構成されてもよい。各構成要素の一部または全部は、上述した回路等とプログラムとの組合せによって実現されてもよい。

各構成要素の一部または全部が複数の情報処理装置や回路等により実現される場合には、複数の情報処理装置や回路等は集中配置されてもよいし、分散配置されてもよい。例えば、情報処理装置や回路等は、クライアントアンドサーバシステム、クラウドコンピューティングシステム等、各々が通信ネットワークを介して接続される形態として実現されてもよい。

次に、本発明の概要について説明する。図６は、本発明の重み係数算出装置の概要を示すブロック図である。本発明の重み係数算出装置は、入力手段７１と、自動成立率算出手段７３と、エネルギー増加量決定手段７４と、スピン数導出手段７５と、重み係数算出手段７６とを備える。

入力手段７１（例えば、入力部１）には、組合せ最適化問題におけるエネルギーを表す式に含まれる各制約項が入力される。

自動成立率算出手段７３（例えば、自動成立率算出部３）は、制約項毎に、制約項が表す制約に関連する個々のスピンに関連する他の全ての制約が満たされている場合に、その制約項が表す制約が満たされている確率である自動成立率を算出する。

エネルギー増加量決定手段７４（例えば、エネルギー増加量決定部４）は、制約項毎に、制約項が表す制約が満たされなくなった場合のエネルギー増加量である制約破壊時のエネルギー増加量を決定する。

スピン数導出手段７５（例えば、スピン数導出部５）は、制約項毎に、制約項が表す制約に関連するスピンの数を導出する。

重み係数算出手段７６（例えば、重み係数算出部６）は、制約項毎に、自動成立率と、制約破壊時のエネルギー増加量と、スピンの数とに基づいて、制約項に対応する重み係数を算出する。

そのような構成によって、組合せ最適化問題のエネルギーを表す式の制約項の重み係数を高速に算出することができる。

自動成立率算出手段７３が、制約項毎に、制約項が表す制約に関連する個々のスピンに関連する他の全ての制約が満たされている場合に、その制約項が表す制約に関連する個々のスピンが１になる確率をそれぞれ算出し、個々のスピンが１になる確率に基づいて、自動成立率を算出する構成であってもよい。

重み係数算出手段７６が、共通の重み係数に関連付けられる複数の制約項が存在する場合に、その複数の制約項それぞれに対して算出した重み係数の平均値を、その複数の制約項に関連付けられる共通の重み係数として決定する構成であってもよい。

以上、実施形態を参照して本願発明を説明したが、本願発明は上記の実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。

産業上の利用の可能性

本発明は、組合せ最適化問題におけるエネルギーを表す式に含まれる各制約項の重み係数を算出する重み係数算出装置に好適に適用される。

１ 入力部
２ 制約特定部
３ 自動成立率算出部
４ エネルギー増加量決定部
５ スピン数導出部
６ 重み係数算出部
１０ 重み係数算出装置

Claims (9)

1. 組合せ最適化問題におけるエネルギーを表す式に含まれる各制約項が入力される入力手段と、
   制約項毎に、制約項が表す制約に関連する個々のスピンに関連する他の全ての制約が満たされている場合に、前記制約項が表す前記制約が満たされている確率である自動成立率を算出する自動成立率算出手段と、
   制約項毎に、制約項が表す制約が満たされなくなった場合のエネルギー増加量である制約破壊時のエネルギー増加量を決定するエネルギー増加量決定手段と、
   制約項毎に、制約項が表す制約に関連するスピンの数を導出するスピン数導出手段と、
   制約項毎に、前記自動成立率が大きく、前記制約破壊時のエネルギー増加量が大きく、前記スピンの数が多いほど、制約項に対応する重み係数が小さくなるように、制約項に対応する重み係数を算出する重み係数算出手段とを備える
   ことを特徴とする重み係数算出装置。
2. 前記自動成立率算出手段は、
   制約項毎に、制約項が表す制約に関連する個々のスピンに関連する他の全ての制約が満たされている場合に、前記制約項が表す前記制約に関連する個々のスピンが１になる確率をそれぞれ算出し、前記個々のスピンが１になる確率に基づいて、前記自動成立率を算出する
   ことを特徴とする請求項１に記載の重み係数算出装置。
3. 前記重み係数算出手段は、
   共通の重み係数に関連付けられる複数の制約項が存在する場合に、前記複数の制約項それぞれに対して算出した重み係数の平均値を、前記複数の制約項に関連付けられる共通の重み係数として決定する
   請求項１または請求項２に記載の重み係数算出装置。
4. コンピュータが、
   組合せ最適化問題におけるエネルギーを表す式に含まれる各制約項の入力を受け付け、
   制約項毎に、制約項が表す制約に関連する個々のスピンに関連する他の全ての制約が満たされている場合に、前記制約項が表す前記制約が満たされている確率である自動成立率を算出する自動成立率算出処理を実行し、
   制約項毎に、制約項が表す制約が満たされなくなった場合のエネルギー増加量である制約破壊時のエネルギー増加量を決定するエネルギー増加量決定処理を実行し、
   制約項毎に、制約項が表す制約に関連するスピンの数を導出するスピン数導出処理を実行し、
   制約項毎に、前記自動成立率が大きく、前記制約破壊時のエネルギー増加量が大きく、前記スピンの数が多いほど、制約項に対応する重み係数が小さくなるように、制約項に対応する重み係数を算出する重み係数算出処理を実行する
   ことを特徴とする重み係数算出方法。
5. 前記コンピュータが、
   前記自動成立率算出処理で、
   制約項毎に、制約項が表す制約に関連する個々のスピンに関連する他の全ての制約が満たされている場合に、前記制約項が表す前記制約に関連する個々のスピンが１になる確率をそれぞれ算出し、前記個々のスピンが１になる確率に基づいて、前記自動成立率を算出する
   請求項４に記載の重み係数算出方法。
6. 前記コンピュータが、
   前記重み係数算出処理で、
   共通の重み係数に関連付けられる複数の制約項が存在する場合に、前記複数の制約項それぞれに対して算出した重み係数の平均値を、前記複数の制約項に関連付けられる共通の重み係数として決定する
   請求項４または請求項５に記載の重み係数算出方法。
7. 組合せ最適化問題におけるエネルギーを表す式に含まれる各制約項が入力される入力手段を備えるコンピュータに、
   制約項毎に、制約項が表す制約に関連する個々のスピンに関連する他の全ての制約が満たされている場合に、前記制約項が表す前記制約が満たされている確率である自動成立率を算出する自動成立率算出処理、
   制約項毎に、制約項が表す制約が満たされなくなった場合のエネルギー増加量である制約破壊時のエネルギー増加量を決定するエネルギー増加量決定処理、
   制約項毎に、制約項が表す制約に関連するスピンの数を導出するスピン数導出処理、および、
   制約項毎に、前記自動成立率が大きく、前記制約破壊時のエネルギー増加量が大きく、前記スピンの数が多いほど、制約項に対応する重み係数が小さくなるように、制約項に対応する重み係数を算出する重み係数算出処理
   を実行させるための重み係数算出プログラム。
8. 前記コンピュータに、
   前記自動成立率算出処理で、
   制約項毎に、制約項が表す制約に関連する個々のスピンに関連する他の全ての制約が満たされている場合に、前記制約項が表す前記制約に関連する個々のスピンが１になる確率をそれぞれ算出させ、前記個々のスピンが１になる確率に基づいて、前記自動成立率を算出させる
   請求項７に記載の重み係数算出プログラム。
9. 前記コンピュータに、
   前記重み係数算出処理で、
   共通の重み係数に関連付けられる複数の制約項が存在する場合に、前記複数の制約項それぞれに対して算出した重み係数の平均値を、前記複数の制約項に関連付けられる共通の重み係数として決定させる
   請求項７または請求項８に記載の重み係数算出プログラム。