(57)【要約】  【課題】  多値最適化問題を効率的に最適化する組合せ最適化システム及び組合せ最適化方法を提供する。  【解決手段】  組合せ最適化システム１０は、多値最適化問題を入力する入力部１１と、ｈａｌｆ−ｈｏｔ制約を用いて多値最適化問題を２値表現した評価関数を生成する評価関数生成部１２と、評価関数を用いて最適化を行うイジングマシン１３と、評価関数生成部１２及びイジングマシン１３からなる半減化部１５を制御して、評価関数の生成と最適化とを繰り返すことで、多値最適化問題の最適解を求める最適化制御部１４とを備えている。【選択図】  図１
2020160685.tif 000002
【特許請求の範囲】
【請求項１】
多値最適化問題を入力する入力部（１１）と、
前記多値最適化問題の半分の状態を選択する半減化を行う半減化部（１５）と、
前記半減化を繰り返すことで前記多値最適化問題の最適解を求める最適化制御部（１４）と、
を備えた組合せ最適化システム。
【請求項２】
前記半減化部（１５）は、
ｈａｌｆ−ｈｏｔ制約を用いて前記多値最適化問題を２値表現した評価関数を生成する評価関数生成部（１２）と、
前記評価関数を最適化する処理を行うことで前記半減化を行うイジングマシン（１３）と、
を備え、
前記最適化制御部（１４）は、前記評価関数生成部（１２）を制御して、前記半減化部（１３）で選択された半分の状態を半減化するための評価関数を生成させる、請求項１に記載の組合せ最適化システム。
【請求項３】
前記入力部（１１）は、前記イジングマシンでの処理が複数回行われる大規模多値最適化問題を前記多値最適化問題として入力し、
前記半減化部（１５）は、さらに、前記評価関数についてｈａｌｆ−ｈｏｔ制約を満たす２値化した部分問題を生成する部分問題生成部（１６）を備え、
前記イジングマシン（１３）は、前記部分問題を最適化する処理を行い、
前記半減化部（１５）は、さらに、前記部分問題生成部（１６）で更に部分問題を生成して前記イジングマシン（１３）で当該部分問題を最適化する処理を行うか、前記半減化を終了するかを判断する半減化制御部（１７）を備える、請求項２に記載の組合せ最適化システム。
【請求項４】
前記部分問題生成部（１６）は、前記半減化で選択されている選択状態と前記半減化で選択されていない非選択状態とを各１つずつ抽出し、前記部分問題として、抽出された前記選択状態又は前記非選択状態がそれぞれ前記非選択状態又は前記選択状態に遷移する遷移状態と、抽出された前記選択状態又は前記非選択状態が遷移しない維持状態とからなる２値最適化問題を生成する、請求項３に記載の組合せ最適化システム。
【請求項５】
多値最適化問題を入力する入力工程と、
前記多値最適化問題の半分の状態を選択する半減化を行う半減化工程を含み、
前記半減化工程を繰り返すことで前記多値最適化問題の最適解を求める、組合せ最適化方法。
【請求項６】
前記半減化工程は、
ｈａｌｆ−ｈｏｔ制約を用いて前記多値最適化問題を２値表現した評価関数を生成する評価関数生成工程と、
イジングマシンで前記評価関数を最適化する処理を行うことで前記半減化を行うイジングマシン工程と、
を含み、
前記評価関数生成工程は、前記半減化で選択された半分の状態を半減化するための評価関数を生成する、請求項５に記載の組合せ最適化方法。
【請求項７】
前記入力工程は、前記イジングマシンでの処理が複数回行われる大規模多値最適化問題を前記多値最適化問題として入力し、
前記半減化工程は、
前記多値最適化問題についてｈａｌｆ−ｈｏｔ制約を満たす２値化した部分問題を生成する部分問題生成工程と、
前記イジングマシンで前記部分問題を最適化するイジングマシン工程と、
前記部分問題生成工程で更に部分問題を生成して前記イジングマシン工程で当該部分問題を最適化する処理を行うか、前記半減化を終了するかを判断する工程と、
を含む、請求項６に記載の組合せ最適化方法。
【請求項８】
前記部分問題生成工程は、前記半減化で選択されている選択状態と前記半減化で選択されていない非選択状態とを各１つずつ抽出し、前記部分問題として、抽出された前記選択状態又は前記非選択状態がそれぞれ前記非選択状態又は前記選択状態に遷移する遷移状態と、抽出された前記選択状態又は前記非選択状態が遷移しない維持状態とからなる２値最適化問題を生成する、請求項７に記載の組合せ最適化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、組合せ最適化問題（以下、単に「最適化問題」という。）の最適化を行う組合せ最適化システム及び組合せ最適化方法に関するものである。
【背景技術】
【０００２】
組合せ最適化問題に特化したハードウェア（以下、「専用マシン」という。）として、Ｄ−Ｗａｖｅ（登録商標）の量子アニーリングマシン、富士通のデジタルアニーラ（登録商標）、日立のＣＭＯＳアニーリング等がある。これらの専用マシンは２値変数によって定義された評価関数の最適化を通常のコンピュータよりも高速に実行することができる。しかし、実場面では多値変数によって定義された評価関数の最適化、即ち多値変数の最適化問題（以下、「多値最適化問題」という。）を解くことが要求されることが多い。２値変数しか扱えない専用マシンを用いて多値最適化問題を解く方法として広く使われているのは、ｏｎｅ−ｈｏｔ表示を用いて多値最適化問題を２値表現した上で、専用マシンを用いて最適化を行う方法である（例えば、非特許文献１）。
【０００３】
ｏｎｅ−ｈｏｔ表示では、多値最適化問題の多値変数の各々がとり得る状態の数だけ２値変数を割り当てる。図７は、下式（１）に示す１次元のＰｏｔｔｓモデルのエネルギーを最小化する問題をｏｎｅ−ｈｏｔ制約を利用して２値表現した様子を示す図である。
【数１】
2020160685.tif 000003
【０００４】
また、この場合の評価関数は下式（２）のようになる。
【数２】
2020160685.tif 000004
【０００５】
ここで、式（１）のＳｉはＱ個の状態を取ることができ、式（１）は、ハミルトニアンＨ０が最も小さくなるように各多値変数についてＱ個の中から１個の状態を選択する最適化問題である。式（２）の評価関数では、各多値変数でｘｉ（ｑ）＝１となる状態が選択されたとみなし、右辺第１項は隣接多値変数で同じ状態が選択された場合の寄与を表し、右辺第２項は各多値変数の状態を１つだけ選択した場合に評価関数が低くなるように追加された制約項（ｏｎｅ−ｈｏｔ制約）である。
【０００６】
図７に示すように、ｏｎｅ−ｈｏｔ表示する際の２値変数はＮＱ個存在し、ｏｎｅ−ｈｏｔ制約は縦方向の２値変数の中で「１」が１個だけ表れるように制限する。
【０００７】
式（２）を一般化すると、下式（３）のとおりである。
【数３】
2020160685.tif 000005
ここで、式（３）の右辺第１項及び第２項は、解きたい問題を表現した部分であり、右辺第３項は、制約条件である。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Andrew Lucas, “Ising formulations of many NP problems”, Department of Physics, Harvard University, Cambridge, MA, USA 02138
【発明の概要】
【発明が解決しようとする課題】
【０００９】
多値最適化問題は２値変数の最適化問題より本質的に難しい問題が多く、ｏｎｅ−ｈｏt制約と専用マシンとを組合せただけでは多値最適化問題を高精度に解くことは困難である。そこで、本発明は、多値変数を効率的に最適化する組合せ最適化システム及び組合せ最適化方法を提供することを目的する。
【課題を解決するための手段】
【００１０】
上記の目的を達成するために、本発明の一態様の組合せ最適化システム（１０）は、多値最適化問題を入力する入力部（１１）と、前記多値最適化問題の半分の状態を選択する半減化を行う半減化部（１５）と、前記半減化を繰り返すことで前記多値最適化問題の最適解を求める最適化制御部（１４）とを備えた構成を有している。
【００１１】
この構成により、半減化によって選択肢を徐々に狭めていくことで、全体の処理コストを低減して効率的に最適化を行うことができる。
【００１２】
また、本発明の一態様の組合せ最適化方法は、多値最適化問題を入力する入力工程と、前記多値最適化問題の半分の状態を選択する半減化を行う半減化工程を含み、前記半減化工程を繰り返すことで前記多値最適化問題の最適解を求める。
【００１３】
この構成によっても、半減化によって選択肢を徐々に狭めていくことで、全体の処理コストを低減して効率的に最適化を行うことができる。
【図面の簡単な説明】
【００１４】
【図１】図１は、本発明の第１の実施の形態の組合せ最適化システムの構成を示すブロック図である。
【図２】図２は、本発明の第１の実施の形態の組合せ最適化方法のフローチャートである。
【図３】図３は、本発明の第２の実施の形態の組合せ最適化システムの構成を示すブロック図である。
【図４】図４は、本発明の第２の実施の形態の組合せ最適化システムにおいて、ある多値変数の状態１と状態４が暫定解として選択されている様子を示す図である。
【図５】図５は、本発明の第２の実施の形態の組合せ最適化システムにおいて、状態１から状態２を遷移先の候補とする様子を示す図である。
【図６】図６は、本発明の第２の実施の形態の組合せ最適化システムにおいて、ｈａｌｆ−ｈｏｔ制約を満たす２値の部分問題の生成を示す図である。
【図７】図７は、１次元のＰｏｔｔｓモデルをｏｎｅ−ｈｏｔ制約を利用して２値表現した様子を示す図である。
【発明を実施するための形態】
【００１５】
以下、図面を参照して本発明の実施の形態を説明する。なお、以下に説明する実施の形態は、本発明を実施する場合の一例を示すものであって、本発明を以下に説明する具体的構成に限定するものではない。本発明の実施にあたっては、実施の形態に応じた具体的構成が適宜採用されてよい。
【００１６】
（第１の実施の形態）
図１は、本発明の実施の形態の組合せ最適化システム１０の構成を示すブロック図である。組合せ最適化システム１０は、入力部１１と、評価関数生成部１２と、イジングマシン１３と、最適化制御部１４とを備えている。本実施の形態では、評価関数生成部１２とイジングマシン１３とからなる構成を半減化部１５という。
【００１７】
入力部１１には、多値最適化問題が入力される。具体的には、入力部１１には、多値最適化問題として、例えば｛Ｊｉｊ（ｑｑ’）｝行列が入力される。
【００１８】
評価関数生成部１２は、入力部１１に入力された多値最適化問題である｛Ｊｉｊ（ｑｑ’）｝行列について、ｈａｌｆ−ｈｏｔ制約を用いて２値表現した評価関数を生成する。上記のように、Ｐｏｔｔｓモデルのｏｎｅ−ｈｏｔ制約を課した評価関数が式（２）であるのに対して、評価関数生成部１２は、Ｐｏｔｔｓモデルのｈａｌｆ−ｈｏｔ制約を課した評価関数として、下式（４）の評価関数を生成する。
【数４】
2020160685.tif 000006
この式（４）の右辺第２項がｈａｌｆ−ｈｏｔ制約に相当する。
【００１９】
イジングマシン１３は、評価関数生成部１２において生成された評価関数を用いてアニーリングを行う専用マシンである。なお、ここでのアニーリングは、シミュレーテッド・アニーリングであっても量子アニーリングであってもよい。上述のように、評価関数生成部１２では、ｈａｌｆ−ｈｏｔ制約を用いて２値表現された評価関数が生成されるので、イジングマシン１３がこの評価関数を用いて最適化を行う（即ち、この評価関数を最小化するイジングマシン処理を行う）ことで、多値最適化問題の半分の状態が選択されることになる。
【００２０】
最適化制御部１４は、上記の評価関数生成部１２及びイジングマシン１３の処理を繰り返すことで、最終的に１つの最適解を得る。最適化制御部１４は、イジングマシン１３によって選択された半分の選択肢を評価関数生成部１２に戻して、評価関数生成部１２に再度評価関数を生成させる。イジングマシン１３は、評価関数生成部１２にて新たな評価関数が生成されると、その評価関数を用いてさらに最適化を行う。これによって、更に半分の状態が選択されることになる。
【００２１】
最適化制御部１４は、これをイジングマシン１３において１つの状態が選択されるまで繰り返す。イジングマシン１３において、変数の最適な１つの組合せ（最適解）が得られ場合には、最適化制御部１４は、この最適解を出力する。
【００２２】
このように、本実施の形態の組合せ最適化システム１０では、評価関数生成部１２が多値最適化問題の評価関数としてｈａｌｆ−ｈｏｔ制約を用いて２値表現した評価関数を生成するとともに、イジングマシン１３がその評価関数を用いて半分の状態を選択し、最適化制御部１４が評価関数生成部１２を制御して更に評価関数を生成させるという処理を繰り返すことで、最終的に最適な組合せを得る構成とすることにより、計算コスト（計算量及び／又は計算時間）を大幅に削減できる。
【００２３】
本実施の形態の組合せ最適化システム１０において計算コストを削減できる点について、Ｐｏｔｔｓモデルである強磁性モデルのエネルギーを最小化する多値最適化問題の処理時間を例に説明する。多値最適化問題ＪｉｊがＪｉｊ＝Ｊ＞０を満たす場合は、この強磁性モデルは、全結合強磁性Ｐｏｔｔｓモデルとなり、全ての多値変数が同じ状態になった場合に式（２）のエネルギーが最小となる。
【００２４】
この強磁性モデルは自明な最適解をもつが、シミュレーテッド・アニーリングや量子アニーリングを用いて最適化した場合は、途中で１次相転移が発生してしまい、最適解を得る為に必要な時間はＱ≧３で多値変数の数：Ｎに対して指数関数的に増加してしまう。これに対して、本実施の形態の組合せ最適化システム１０では、２次相転移しか発生せず、各最適化の処理時間がＮに対して多項式的な増加に緩和されるため、全体として処理時間を短くすることができる。
【００２５】
ここで、式（２）及び式（３）を一般化すると以下の式（５）及び式（６）となる。
【数５】
2020160685.tif 000007
【数６】
2020160685.tif 000008
本実施の形態の組合せ最適化システム１０によれば、一般的に式（５）で表される評価関数が、評価関数生成部１２にて式（６）のように生成される。
【００２６】
図２は、本発明の実施の形態の組合せ最適方法のフローチャートである。入力部１１に多値最適化問題（例えば、｛Ｊｉｊ（ｑｑ’）｝行列）が与えられると（ステップＳ２１）、評価関数生成部１２は、この多値最適化問題についての評価関数を生成する（ステップＳ２２）。このとき、評価関数生成部１２は、上述のように、この多値最適化問題についてｈａｌｆ−ｈｏｔ制約を用いて２値表現した評価関数を生成する。
【００２７】
次に、イジングマシン１３は、評価関数生成部１２にて生成された評価関数を用いて、各多値変数の半分の状態を選択することで、選択肢を半分に絞り込む（ステップＳ２３）。そして、最適化制御部１４は、この多値最適化問題が最適化されたか、即ち最適な１つの状態の組合せ（最適解）が選択されたか否かを判断する（ステップＳ２４）。
【００２８】
最適化されていない場合には（ステップＳ２４でＮＯ）、最適化制御部１４は、選択されて残っている変数の状態について、再度、評価関数生成部１２にて評価関数を生成させる（ステップＳ２２）。このステップＳ２４とステップＳ２３とを繰り返して、最終的に１つの状態が残った場合、即ち多値最適化問題の最適解が得られた場合には（ステップＳ２４でＹＥＳ）、最適化制御部１４は、この最適解を出力して（ステップＳ２５）、処理を終了する。評価関数生成部１２にて多値最適化問題についてｈａｌｆ−ｈｏｔ制約を用いて２値表現した評価関数を生成してイジングマシン１３で最適化の処理を行うステップＳ２２〜Ｓ２３は、本発明の半減化工程に相当する。
【００２９】
以上のように、本実施の形態の組合せ最適化システム１０によれば、イジングマシン１３では、選択肢を半分にするという最適化を行うので、イジングマシン１３における各回の最適化処理が簡単になり、全体として処理コストを低減できる。
【００３０】
（第２の実施の形態）
図３は、第２の実施の形態の組合せ最適化システムの構成を示すブロック図である。本実施の形態の組合せ最適化システム１０´は、第１の実施の形態の組合せ最適化システム１０と比較して、部分問題生成部１６及び半減化制御部１７が追加され、評価関数生成部１２、部分問題生成部１６、イジングマシン１３、及び半減化制御部１７で半減化部１５が構成される。その他の構成は第１の実施の形態と同様である。
【００３１】
入力部１１に入力された多値最適化問題の変数規模が大きく、その評価関数をイジングマシン１３で一度に処理しきれない、又はイジングマシンでの処理が複数回行われる場合には（この場合の多値最適化問題を「大規模多値最適化問題」ともいう。）、部分問題生成部１６は評価関数の２値化した部分問題を生成する。イジングマシン（１３）は、部分問題生成部１６で生成された部分問題を最適化する処理を行う。
【００３２】
半減化制御部１７は、部分問題生成部１６で再度他の２値化した部分問題を生成して、イジングマシン１３で当該部分問題を最適化する処理を行うか（即ち、部分問題の生成及び最適化を繰り返すか）、評価関数についての半減化を終了するかを判断する。半減化制御部１７が半減化を終了する条件として、例えば、（１）一定の処理時間が経過した、（２）一定の回数繰り返した、（３）一定回数以上で評価値の改善がない、（４）一定水準以上の評価値に到達した等であってよい。すなわち、半減化部１５において２値化した部分問題の生成及び最適化の処理をいつまで行うかは、上記の（１）、（２）のようにあらかじめ決定しておいてもよいし、（３）、（４）のように最適化の結果に従って決定してもよい。
【００３３】
イジングマシン１３は、部分問題生成部１６にて生成された部分問題を最適化する処理を行う。半減化制御部１７は、イジングマシン１３での最適化によって十分な精度の解が得られているか否かを判断する。半減化制御部１７は、十分な解が得られたと判断した場合、又は生成されたすべての部分問題を最適化した場合には、選択された半分の選択肢を最適化制御部１４に出力する。
【００３４】
最適化制御部１４の機能は、第１の実施の形態と同じである。すなわち、最適化制御部１４は、半減化部１５によって選択された半分の選択肢を評価関数生成部１２に戻して、評価関数生成部１２に再度評価関数を生成させる。最適化制御部１４は、これを半減化部１５において１つの状態が選択されるまで繰り返す。半減化部１５において、変数の最適な１つの組合せ（最適解）が得られ場合には、最適化制御部１４は、この最適解を出力する。
【００３５】
図４〜６は、変数規模の大きい多値最適化問題の部分問題を解く場合の処理を説明する図である。この例では、部分問題生成部１６は、各多値変数に対して現在選択されている状態（選択状態）と現在選択されていない状態（非選択状態）を各１個ランダムに選び、それら２つの状態間を遷移するか否かの２値問題に変換する。
【００３６】
図４〜６は、４状態の多値問題を２値問題に変換する例を示している。まず、部分問題生成部１６は、図４に示すように、ある多値変数の状態１と状態４が暫定解として選択されている場合において、ｈａｌｆ−ｈｏｔ制約を満たす２値問題に変換するために、まず状態１及び状態４のいずれか、並びに状態２及び状態３のいずれかをランダムに選択して抽出する。いま、状態１と状態２が抽出された場合、図５に示すように、状態１から状態２を遷移先の候補とする。
【００３７】
部分問題生成部１６は、図４の状態を維持する維持状態、又は図５の状態に遷移する遷移状態との２状態を２値変数とする。部分問題生成部１６は、すべての多値変数に対して同様の処理を適用することで、図６に示すように、ｈａｌｆ−ｈｏｔ制約を満たす２値の部分問題を生成する。これによって、専用マシンであるイジングマシン１３で解く部分問題は、ｈａｌｆ−ｈｏｔ制約を満たす解のみを含むことになり、専用マシンのハードウェアリソースを有効に活用できるようになる。また、ｈａｌｆ−ｈｏｔ制約のパラメータであるλ（式（４）参照）が不要になり、無駄なパラメータ調整をしなくてもよくなる。２値化した部分問題の全変数をイジングマシン１３で取り扱いできない場合は、図６に示すように２値化した部分問題の中から部分的な変数を取り出して、イジングマシンで解く部分問題を生成すればよい。
【産業上の利用可能性】
【００３８】
以上のように、本発明は、半減化によって選択肢を徐々に狭めていくことで、全体の処理コストを低減して効率的に最適化を行うことができるという効果を有し、組合せ最適化問題の最適化を行う組合せ最適化システム等として有用である。
【符号の説明】
【００３９】
１０、１０´  組合せ最適解システム、１１  入力部、１２  評価関数生成部、
１３  イジングマシン、１４  最適化制御部、１５  半減化部、１６  部分問題生成部
【図１】
2020160685.tif 000009
【図２】
2020160685.tif 000010
【図３】
2020160685.tif 000011
【図４】
2020160685.tif 000012
【図５】
2020160685.tif 000013
【図６】
2020160685.tif 000014
【図７】
2020160685.tif 000015