(19)【発行国】日本国特許庁(JP)
(12)【公報種別】公開特許公報(A)
(11)【公開番号】2019145010
(43)【公開日】20190829
(54)【発明の名称】計算装置、計算プログラム、記録媒体及び計算方法
(51)【国際特許分類】
   G06N 99/00 20190101AFI20190802BHJP
【FI】
   !G06N99/00 180
【審査請求】未請求
【請求項の数】16
【出願形態】OL
【全頁数】25
(21)【出願番号】2018030873
(22)【出願日】20180223
(71)【出願人】
【識別番号】000003078
【氏名又は名称】株式会社東芝
【住所又は居所】東京都港区芝浦一丁目1番1号
(74)【代理人】
【識別番号】100108062
【弁理士】
【氏名又は名称】日向寺 雅彦
(72)【発明者】
【氏名】後藤 隼人
【住所又は居所】東京都港区芝浦一丁目1番1号 株式会社東芝内
(72)【発明者】
【氏名】辰村 光介
【住所又は居所】東京都港区芝浦一丁目1番1号 株式会社東芝内
(57)【要約】
【課題】最適化問題を高速に計算できる計算装置、計算プログラム、記録媒体及び計算方法を提供する。
【解決手段】実施形態によれば、計算装置は、処理手順を繰り返す処理部を含む。処理手順は第1、第2変数更新を含む。第1変数更新は、第1変数xに第1関数を加えて第1変数xを更新することを含む。第1変数xは、第1変数群{x}の1つである。第1関数の変数は、第2変数yを含む。第2変数yは、第2変数群{y}の1つである。第2変数更新は、第2変数yに第2、第3関数を加えて第2変数yを更新することを含む。第2関数の変数は、第1変数xを含む。第3関数の変数は、第1パラメータ群{J}、及び第1変数群{x}を含む。処理部は、少なくとも、処理手順を繰り返した後に得られる第1変数x、または、処理手順を繰り返した後に得られる第1変数xの関数を出力する。
【選択図】図1
【特許請求の範囲】
【請求項1】
処理手順を繰り返す処理部を備え、
前記処理手順は第1変数更新及び第2変数更新を含み、
前記第1変数更新は、前記第1変数更新前のi番目(iは1以上N以下の整数であり、前記Nは2以上の整数)の第1変数xに第1関数を加えて前記i番目の前記第1変数xを更新することを含み、前記i番目の前記第1変数xは、第1変数群{x}の1つであり、前記第1関数の変数は、前記i番目の第2変数yを含み、前記i番目の前記第2変数yは、第2変数群{y}の1つであり、
前記第2変数更新は、前記第2変数更新前の前記i番目の前記第2変数yに第2関数及び第3関数を加えて前記i番目の前記第2変数yを更新することを含み、前記第2関数の変数は、前記i番目の第1変数xを含み、前記第3関数の変数は、第1パラメータ群{J}の少なくとも一部及び前記第1変数群{x}の少なくとも一部を含み、
前記処理部は、少なくとも、前記処理手順を前記繰り返した後に得られる前記i番目の前記第1変数x、及び、前記処理手順を前記繰り返した後に得られる前記i番目の前記第1変数xの関数の少なくともいずれかを出力する、計算装置。
【請求項2】
前記第1関数は、前記第1変数群{x}から独立し、
前記第2関数は、前記第2変数群{y}から独立し、
前記第3関数は、前記第2変数群{y}から独立し、
前記処理手順の1つにおいて、前記第1変数更新後に前記第2変数更新が行われる、または、前記第2変数更新後に前記第1変数更新が行われる、請求項1記載の計算装置。
【請求項3】
前記第1関数は、前記第1変数群{x}から独立し、
前記第2関数は、前記第2変数群{y}から独立し、
前記第3関数は、前記第2変数群{y}から独立し、
前記第2変数更新は、第1サブ更新及び第2サブ更新を含み、
前記第1サブ更新は、前記第1サブ更新前の前記i番目の前記第2変数yに前記第2関数を加えて前記i番目の前記第2変数yを更新することを含み、
前記第2サブ更新は、前記第2サブ更新前の前記i番目の前記第2変数yに前記第3関数を加えて前記i番目の前記第2変数yを更新することを含み、
前記第1変数更新及び前記第1サブ更新を交互にM回(Mは1以上の整数)行った後、前記第2サブ更新を行う、または、前記第2サブ更新後、前記第1変数更新及び前記第1サブ更新を交互にM回行う、請求項1記載の計算装置。
【請求項4】
前記第3関数は、前記第1パラメータ群{J}の前記少なくとも一部と前記第1変数群{x}の前記少なくとも一部と積和演算を含む、請求項1〜3のいずれか1つに記載の計算装置。
【請求項5】
前記第2関数は、前記i番目の前記第1変数xを変数とする第4関数を含み、
前記第4関数は、前記第1変数xの非線形関数を含み、
前記第4関数は、演算パラメータpを含み、
前記演算パラメータpは、前記処理手順を繰り返すと変化し、
前記処理手順を繰り返した後の前記第4関数の実数根の数は、前記処理手順を繰り返す前の前記第4関数の実数根の数とは異なる、請求項1〜4のいずれか1つに記載の計算装置。
【請求項6】
前記処理手順を繰り返した後の前記第4関数の前記根の前記数は、2以上であり、
前記処理手順を繰り返した後の前記第4関数の前記根の1つは正であり、
前記処理手順を繰り返した後の前記第4関数の前記根の別の1つは負であり、
前記処理部は、少なくとも、前記処理手順を前記繰り返した後に得られる前記i番目の前記第1変数xiの符号を出力する、請求項1〜5のいずれか1つに記載の計算装置。
【請求項7】
前記第2関数は、前記i番目の第2パラメータhiを含み、
前記i番目の前記第2パラメータhiは、第2パラメータ群{h}の1つである、請求項1〜6のいずれか1つに記載の計算装置。
【請求項8】
前記第1変数更新は、前記第1変数更新前の前記i番目の前記第1変数xiを保持部から取得し、前記第1変数更新後の前記i番目の前記第1変数xiを前記保持部に保持させることを含み、
前記第2変数更新は、前記第2変数更新前の前記i番目の前記第2変数yiを前記保持部から取得し、前記第2変数更新後の前記i番目の前記第2変数yiを前記保持部に保持させることを含む、請求項1〜7のいずれか1つに記載の計算装置。
【請求項9】
前記第1変数更新は、前記i番目の前記第2変数yiを前記保持部から取得して前記第1関数を計算し、前記i番目の前記第1変数xiに前記第1関数を加えて前記i番目の前記第1変数xiを更新することをさらに含み、
前記第2変数更新は、前記i番目の前記第1変数xiを前記保持部から取得して前記第2関数を計算し、前記第1パラメータ群{J}の前記少なくとも一部及び前記第1変数群{x}の前記少なくとも一部を前記保持部から取得して前記第3関数を計算し、前記i番目の前記第2変数yiに前記第2関数及び前記第3関数を加えて前記i番目の前記第2変数yiを更新することをさらに含む、を含む、請求項8記載の計算装置。
【請求項10】
前記保持部をさらに備えた、請求項8または9に記載の計算装置。
【請求項11】
前記処理部は、第1計算部と、第2計算部と、を含み、
前記第1計算部は、前記第3関数の計算の一部を実施し、
前記第2計算部は、前記第3関数の前記計算の別の一部を実施し、
前記第1計算部における前記第3関数の前記計算の前記一部の前記実施の少なくとも一部と、前記第2計算部における前記第3関数の前記計算の前記別の一部の前記実施の少なくとも一部は、同時に行われる、請求項1〜10のいずれか1つに記載の計算装置。
【請求項12】
前記保持部は、第1保持領域及び第2保持領域を含み、
前記第1パラメータ群{J}は、第1計算使用部分と、第2計算使用部分と、を含み、前記第1計算使用部分は、前記第3関数の前記計算の前記一部で用いられ、前記第2計算使用部分は、前記第3関数の前記計算の前記別の一部で用いられ、
前記第1計算部は、前記第1計算使用部分を前記第1保持領域に保持させ、
前記第2計算部は、前記第2計算使用部分を前記第2保持領域に保持させる、請求項1〜11のいずれか1つに記載の計算装置。
【請求項13】
前記処理部は、第3計算部と、第4計算部と、を含み、
前記第3計算部は、前記第1変数更新の計算の一部及び前記第2関数の計算の一部を実施し、
前記第4計算部は、前記第1変数更新の計算の別の一部及び前記第2関数の前記計算の別の一部を実施し、
前記第1変数更新は、前記第1変数更新前のj番目(jは前記iとは異なり、1以上前記N以下の整数)の前記第1変数xjに前記第1関数を加えて前記j番目の前記第1変数xjを更新することを含み、前記j番目の前記第1変数xjは、前記第1変数群{x}の1つであり、前記第1関数の変数は、前記j番目の第2変数yjを含み、前記j番目の前記第2変数yjは、前記第2変数群{y}の1つであり、
前記第1変数更新の前記計算の前記一部は、前記i番目の前記第1変数xiの更新の計算を含み、
前記第1変数更新の前記計算の前記別の前記一部は、前記j番目の前記第1変数xjの更新の計算を含み、
前記第2関数の前記計算の前記一部は、前記i番目の前記第1変数xiを変数として含む前記第2関数の計算を含み、
前記第2関数の前記計算の前記別の前記一部は、j番目の前記第1変数xjを変数として含む前記第2関数の計算を含み、
前記第3計算部における前記実施の少なくとも一部と、前記第4計算部における前記実施の少なくとも一部は、同時に行われる、請求項1〜12のいずれか1つに記載の計算装置。
【請求項14】
コンピュータに、処理手順を繰り返させる計算プログラムであって、
前記処理手順は第1変数更新及び第2変数更新を含み、
前記第1変数更新は、前記第1変数更新前のi番目(iは1以上N以下の整数であり、前記Nは2以上の整数)の第1変数xに第1関数を加えて前記i番目の前記第1変数xを更新することを含み、前記i番目の前記第1変数xは、第1変数群{x}の1つであり、前記第1関数の変数は、前記i番目の第2変数yを含み、前記i番目の前記第2変数yは、第2変数群{y}の1つであり、
前記第2変数更新は、前記第2変数更新前の前記i番目の前記第2変数yに第2関数及び第3関数を加えて前記i番目の前記第2変数yを更新することを含み、前記第2関数の変数は、前記i番目の第1変数xを含み、前記第3関数の変数は、第1パラメータ群{J}の少なくとも一部及び前記第1変数群{x}の少なくとも一部を含み、
前記処理手順を前記繰り返した後に得られる前記i番目の前記第1変数x及び前記処理手順を前記繰り返した後に得られる前記i番目の前記第1変数xの関数少なくともいずれかを出力させる、計算プログラム。
【請求項15】
コンピュータに、処理手順を繰り返させる計算プログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記処理手順は第1変数更新及び第2変数更新を含み、
前記第1変数更新は、前記第1変数更新前のi番目(iは1以上N以下の整数であり、前記Nは2以上の整数)の第1変数xに第1関数を加えて前記i番目の前記第1変数xを更新することを含み、前記i番目の前記第1変数xは、第1変数群{x}の1つであり、前記第1関数の変数は、前記i番目の第2変数yを含み、前記i番目の前記第2変数yは、第2変数群{y}の1つであり、
前記第2変数更新は、前記第2変数更新前の前記i番目の前記第2変数yに第2関数及び第3関数を加えて前記i番目の前記第2変数yを更新することを含み、前記第2関数の変数は、前記i番目の第1変数xを含み、前記第3関数の変数は、第1パラメータ群{J}の少なくとも一部及び前記第1変数群{x}の少なくとも一部を含み、
前記処理手順を前記繰り返した後に得られる前記i番目の前記第1変数x及び前記処理手順を前記繰り返した後に得られる前記i番目の前記第1変数xの関数少なくともいずれかを出力させる、記録媒体。
【請求項16】
処理手順を繰り返し、
前記処理手順は第1変数更新及び第2変数更新を含み、
前記第1変数更新は、前記第1変数更新前のi番目(iは1以上N以下の整数であり、前記Nは2以上の整数)の第1変数xに第1関数を加えて前記i番目の前記第1変数xを更新することを含み、前記i番目の前記第1変数xは、第1変数群{x}の1つであり、前記第1関数の変数は、前記i番目の第2変数yを含み、前記i番目の前記第2変数yは、第2変数群{y}の1つであり、
前記第2変数更新は、前記第2変数更新前の前記i番目の前記第2変数yに第2関数及び第3関数を加えて前記i番目の前記第2変数yを更新することを含み、前記第2関数の変数は、前記i番目の第1変数xを含み、前記第3関数の変数は、第1パラメータ群{J}の少なくとも一部及び前記第1変数群{x}の少なくとも一部を含み、
前記処理手順を前記繰り返した後に得られる前記i番目の前記第1変数x及び前記処理手順を前記繰り返した後に得られる前記i番目の前記第1変数xの関数少なくともいずれかを出力する、計算方法。
【発明の詳細な説明】
【技術分野】
【0001】
本発明の実施形態は、計算装置、計算システム、計算プログラム、記録媒体及び計算方法に関する。
【背景技術】
【0002】
様々な社会課題において、最適化問題が生じる。最適化問題の1つの例として、イジング問題がある。大規模な最適化問題を高速に解くことが求められる。
【先行技術文献】
【非特許文献】
【0003】
【非特許文献1】T. Inagaki et al., Science 354, 603 (2016).
【非特許文献2】H. Goto, Sci. Rep. 6, 21686 (2016).
【非特許文献3】Y. Haribara et al., Quantum Sci. Technol. 2, 044002 (2017).
【発明の概要】
【発明が解決しようとする課題】
【0004】
本発明の実施形態は、最適化問題を高速に計算できる計算装置、計算プログラム、記録媒体及び計算方法を提供する。
【課題を解決するための手段】
【0005】
本発明の実施形態によれば、計算装置は、処理手順を繰り返す処理部を含む。前記処理手順は第1変数更新及び第2変数更新を含む。前記第1変数更新は、前記第1変数更新前のi番目(iは1以上N以下の整数であり、前記Nは2以上の整数)の第1変数xに第1関数を加えて前記i番目の前記第1変数xを更新することを含む。前記i番目の前記第1変数xは、第1変数群{x}の1つである。前記第1関数の変数は、前記i番目の第2変数yを含む。前記i番目の前記第2変数yは、第2変数群{y}の1つである。前記第2変数更新は、前記第2変数更新前の前記i番目の前記第2変数yに第2関数及び第3関数を加えて前記i番目の前記第2変数yを更新することを含む。前記第2関数の変数は、前記i番目の第1変数xを含む。前記第3関数の変数は、第1パラメータ群{J}の少なくとも一部及び前記第1変数群{x}の少なくとも一部を含む。前記処理部は、少なくとも、前記処理手順を前記繰り返した後に得られる前記i番目の前記第1変数x、及び、前記処理手順を前記繰り返した後に得られる前記i番目の前記第1変数xの関数の少なくともいずれかを出力する。
【図面の簡単な説明】
【0006】
【図1】実施形態に係る計算装置の例を示す模式図である。
【図2】実施形態に係る計算装置の動作を例示するフローチャートである。
【図3】実施形態に係る計算装置の動作の一部を例示するフローチャートである。
【図4】実施形態に係る計算装置の動作の一部を例示するフローチャートである。
【図5】実施形態に係る計算装置の動作の一部を例示するフローチャートである。
【図6】実施形態に係る計算装置の動作の一部を例示するフローチャートである。
【図7】実施形態に係る計算装置の動作の一部を例示するフローチャートである。
【図8】実施形態に係る計算装置の動作の一部を例示するフローチャートである。
【図9】実施形態に係る計算装置の動作の一部を例示するフローチャートである。
【図10】実施形態に係る計算装置の動作の一部を例示するフローチャートである。
【図11】実施形態に係る計算装置の例を示す模式図である。
【図12】実施形態に係る計算の特性を例示するグラフである。
【図13】計算結果を例示するグラフである。
【発明を実施するための形態】
【0007】
以下に、本発明の各実施の形態について図面を参照しつつ説明する。
本願明細書と各図において、既出の図に関して前述したものと同様の要素には同一の符号を付して詳細な説明は適宜省略する。
【0008】
(第1実施形態)
図1は、実施形態に係る計算装置の例を示す模式図である。
図1に示すように、本実施形態に係る計算装置110は、例えば、処理部20及び保持部10を含む。処理部20は、例えば、CPU(Central Processing Unit)などを含む。処理部20は、例えば電子回路などを含む。保持部10は、種々のデータを保持可能である。保持部10は、例えば、記憶部である。保持部10は、ROM(Read Only Memory)及びRAM32(Random Access Memory)の少なくともいずれかを含んでも良い。計算装置110は、計算システムでも良い。
【0009】
この例では、計算装置110に、取得部31が設けられている。取得部31は、例えば、種々のデータを入手可能である。取得部31は、例えば、I/Oポートなどを含む。取得部31は、出力部の機能を有しても良い。取得部31は、例えば、通信機能を有しても良い。
【0010】
図1に示すように、計算装置110は、操作部32及び表示部33などを含んでも良い。操作部32は、例えば、操作機能を有する装置(例えばキーボート、マウス、タッチ式入力パネル、または音声認識入力装置など)を含んでも良い。表示部33は、各種のディスプレイを含んでも良い。
【0011】
計算装置110に含まれる複数の要素において、無線及び有線の少なくともいずれかの方法により、互いに通信可能である。計算装置110に含まれる複数の要素が設けられる場所が、互いに異なっても良い。計算装置110として、例えば、汎用コンピュータが用いられても良い。計算装置110として、例えば、互いに接続された複数のコンピュータが用いられても良い。計算装置110の少なくとも一部(例えば、処理部20及び保持部10など)として、専用の回路が用いられても良い。計算装置110として、例えば、互いに接続された複数の回路が用いられても良い。
【0012】
計算装置110に含まれる複数の要素の例については、後述する。
【0013】
以下、実施形態に係る計算装置110において、実施される動作の例について説明する。
【0014】
図2は、実施形態に係る計算装置の動作を例示するフローチャートである。
図2に示すように、パラメータを設定する(ステップS201)。パラメータは、例えば、第1パラメータ群{J}を含む。パラメータは、例えば、第2パラメータ群{h}をさらに含んでも良い。これらのパラメータの例については、後述する。
【0015】
複数の変数を設定する(ステップS202)。変数は、例えば、第1変数群{x}及び第2変数群{y}を含む。ステップS202において、変数は適切な値に初期化される。初期化の例については、後述する。
【0016】
複数の変数の計算(例えば更新)を行う(ステップS210)。例えば、複数の変数の時間発展が計算される。例えば、第1変数群{x}が更新され、第2変数群{y}が更新される。これらの計算は、所定の条件(後述する)が満たされるまで繰り返される。ステップS210は、例えば、サブルーチンである。
【0017】
サブルーチン(変数の更新)の後に、例えば、関数を算出する(ステップS220)。例えば、第1変数群{x}に含まれる少なくとも1つの要素の関数が算出される。1つの例において、この関数は、第1変数群{x}に含まれる少なくとも1つの要素の符号である。
【0018】
この関数を出力する(ステップS230)。例えば、1つの例において、第1変数群{x}に含まれる少なくとも1つの要素の符号が出力される。ステップS230において、更新後の第1変数群{x}に含まれる少なくとも1つが出力されても良い。この場合、ステップS220は、省略されても良い。
【0019】
実施形態においては、上記の複数の変数の計算(ステップS210)において、例えば、第1変数群{x}の更新が、第2変数群{y}を用いて行われる。そして、第2変数群{y}の更新が、第1変数群{x}を用いて行われる。これらの更新が、複数回行われる。1つの例において、複数回の更新の1つにおいて、第1変数群{x}の更新の後に、第2変数群{y}の更新が行われる。別の1つの例において、例えば、複数回の更新の1つにおいて、第2変数群{y}の更新の後に、第1変数群{x}の更新が行われる。
【0020】
計算装置110により、最適化問題を高速に計算できる。最適化問題は、例えば、組み合わせ最適化問題(例えば離散最適化問題)である。例えば、大規模なイジング問題を高速に解くことができる。
【0021】
以下、計算装置110で実施される計算の例として、イジング問題について、説明する。
【0022】
例えば、イジングエネルギーEIsingは、以下の第1式で表される。
【0023】
【数1】

上記の第1式において、「N」はイジングスピンの数である。「s」は、i番目のイジングスピンである。例えば、「s」=±1である。「J」は、例えば、1つの行列である。上記の第1パラメータ群{J}の1つの例が、行列Jである。行列Jは、実対称行列である。実対称行列において、対角成分(対角要素)が全てゼロである。
【0024】
上記の第1式に関して、量子分岐マシンの古典モデル(以下、古典分岐マシンと呼ぶ)が提案されている。古典分岐マシンにおいては、運動方程式は、以下の第2〜第4式で与えられる。
【0025】
【数2】

【数3】

【数4】

第2〜第4式において、「N」は、例えば、イジングスピンの数に対応する。「D」は、例えば、「離調」に対応する。「c」は、定数である。「p」は、例えば、「ポンプレート」に対応する。「K」は、例えば、「カー係数」に対応する。これらの値は、例えば、予め設定されても良い。第2〜第4式において、第2パラメータ群{h}は設けられなくても良い。その場合は第3式および第4式の中の{h}の要素を含む項は無視される。
【0026】
上記の第2〜第4式において、p(t)をゼロから十分大きな値へ増加させた時の「x」の最終値の符号「±1」が、最適解(基底状態)のイジングスピン「s」となる。「a(t)」は、「p(t)」とともに増加するパラメータである。「a(t)」は、例えば、以下の第5式で表される。
【数5】
【0027】
上記の古典分岐マシンは、第2〜第4式において、「H」をハミルトニアンとしたハミルトン力学系であると見なすことができる。
【0028】
一方、シミュレーティッドアニーリングが知られている。この方法では、逐次更新アルゴリズムが採用される。逐次更新アルゴリズムにおいては、複数のスピンが、1つずつ更新される。このような逐次更新アルゴリズムは並列計算に向かない。
【0029】
これに対して、上記の古典分岐マシンの運動方程式をデジタル計算機で離散解法によって解くことが考えられる。このアルゴリズムは、シミュレーティッドアニーリングとは異なり、並列更新アルゴリズムである。並列更新アルゴリズムにおいては、複数の変数を同時に更新することができる。このため、並列計算による高速化が期待できる。
【0030】
上記の第2〜第5式を用いるアプローチには、以下の課題があると考えられる。最も計算量が大きい行列Jを用いた計算が、第1変数x及び第2変数yの両方の更新に必要となる。上記の運動方程式は、数値的に容易には解けないため、例えば、計算量が大きい離散解法(例えば4次のルンゲ・クッタ法など)が必要となる。
【0031】
これに対して、実施形態においては、第2〜第4式に示した連立常微分方程式ではなく、例えば、以下の第6〜第8式に示す連立常微分方程式を用いる。
【0032】
【数6】

【数7】

【数8】

第6〜第8式において、「N」は、例えば、イジングスピンの数に対応する。「D」は、例えば、「離調」に対応する。「c」は、定数である。「p」は、例えば、「ポンプレート」(例えば演算パラメータ)に対応する。「K」は、例えば、「カー係数」に対応する。これらの値は、例えば、予め設定されても良い。第6〜第8式において、第2パラメータ群{h}は設けられなくても良い。その場合は、第7式および第8式の中の{h}の要素を含む項は、無視される。
【0033】
最も計算量が大きい行列Jに関する積和演算は、第2変数yの更新にのみ行われ、第1変数xの更新では行われない。従って、計算量が削減される。これらの式において、第1変数xの時間微分は、第2変数yを含む。例えば、第1変数xの時間微分は、第1変数xを含まない。第2変数yの時間微分は、第1変数xを含む。例えば、第2変数yの時間微分は、第2変数yを含まない。ハミルトニアンにおいて、x及びyは、互いに分離されている。このため、計算量が小さく安定な離散解法が適用可能となる。例えば、シンプレクティック・オイラー法と呼ばれる方法が適用できる。上記の第6〜第8式においては、「x」の時間微分から「p」が消去されている。
【0034】
このような方法を用いた場合に、高い性能(例えば、高い精度)が維持できことが分かった。実施形態に係る計算装置では、上記の分離可能なハミルトニアンを持つハミルトン力学系(新しい古典分岐マシン)の運動方程式が、例えば、シンプレクティック・オイラー法で解かれる。実施形態に係る計算装置は、このような新しいアルゴリズムの計算が並列計算によって、できる限り高速に実行されるように構成される。
【0035】
実施形態において、例えば、「p(t)」をゼロから十分大きな値へ増加させた時の第1変数xの最終値の符号(「±1」)が、最適解(基底状態)のイジングスピンsとなる。
【0036】
例えば、第1変数xの及び第2変数yは、変数の設定(ステップS202)において、適切な値に、初期化される。例えば、これらの変数は、絶対値が0.1以下の乱数によって、ランダムに初期化される。
【0037】
以下、ステップS210(図2参照)のいくつかの例について説明する。
【0038】
図3は、実施形態に係る計算装置の動作の一部を例示するフローチャートである。
図3は、ステップS210を例示している。図3に示す式は、例である。図3に示すように、「t」、「p」及び「a」を初期化する(ステップS101)。1つの例において、「t」、「p」及び「a」は0とされる。「T」は、時刻tの最終値に対応する。「dt」は、時刻tの1ステップ当たりの増加量である。「dp」は、パラメータpの1ステップ当たりの増加量である。
【0039】
「t」が「T」よりも小さいときに、以下に説明する一連の処理を含むループの処理(手順を繰り替えし)が行われる(ステップS105)。例えば、「p」があらかじめ適切に設定された「P」よりも小さいときにループの処理が行われる、としても良い。
【0040】
i番目の第1変数xの更新が行われる(ステップS110)。例えば、更新前の第1変数xに、dt*D*yを加えて得られる値を、更新後の第1変数xとする。ここで、「*」は、積の記号である。
【0041】
i番目の第2変数yの更新が行われる(ステップS120)。この例では、第1変数群{x}に基づく更新(ステップS121)と、第1パラメータ{J}及び第1変数群{x}に基づく更新(ステップS122)と、が実施される。ステップS121とステップS122との順序は、入れ替えが可能である。ステップS121の少なくとも一部と、ステップS122の少なくとも一部と、が同時に行われても良い。ステップS121は、例えば第1サブ更新に対応する。ステップS122は、第2サブ更新に対応する。
【0042】
第1サブ更新では、例えば、更新前の第2変数yに、dt*[(p−D−x*x)*x−c*h*a]を加えて得られる値を、更新後の第2変数yとする。
【0043】
第2サブ更新では、例えば、更新前の第2変数yに、dt*c*Σ(Ji,j*x)を加えて得られる値を更新後の第2変数yとする。「Σ」は、jに関する和を表す。例えば、「dt*c*J」をJ行列としてもよい。この場合、「dt*c*」の演算を実際に行わなくても良い。
【0044】
更新のためのパラメータの変更処理を行う(ステップS130)。すなわち、更新前の「t」に「dt」を加えて得られる値を更新後の「t」とする。更新前の「p」に「dp」を加えて得られる値を更新後の「dp」とする。「a」は、例えば、p1/2である。
【0045】
そして、「t」が「T」よりも小さいときに、ステップS105に戻る(ステップS106)。例えば、「p」があらかじめ適切に設定された「P」よりも小さいときに、ステップS105に戻っても良い。
【0046】
「t」が「T」以上のときに、更新を終了し、図2に示すステップS220またはステップS230に進む。
【0047】
図4は、実施形態に係る計算装置の動作の一部を例示するフローチャートである。
図4は、ステップS210を例示している。図4に示す例では、1つの繰り返し処理において、ステップS110の前にステップS120が実施される。このように、ステップS110とステップS120とにおいて、順序は、任意である。
【0048】
1つの例において、「K」は1とする。例えば、「N」、「D」、「c」、「T」、「dt」及び「dp」は、予め適切な値に設定することができる。
【0049】
図3及び図4の例では、「p」の更新において、線形増加が適用される。実施形態において、「p」の更新には、任意の増加関数が用いられても良い。実施形態において、上記のように、2種類の更新方法がある。すなわち、1つの更新方法では、第1変数xの更新の後に、更新された第1変数xを用いて第2変数yを更新する。別の更新方法では、第2変数yの更新の後に、更新された第2変数yを用いて第1変数xを更新する。これらの2つの方法が、図3及び図4にそれぞれ対応する。
【0050】
このように、本実施形態に係る計算装置110において、処理部20(図1参照)は、処理手順(ステップS210:図2参照)を繰り返す。この処理手順は、例えば、第1変数更新(ステップS110)及び第2変数更新(ステップS120)を含む。
【0051】
第1変数更新は、第1変数更新前のi番目(iは1以上N以下の整数であり、Nは2以上の整数)の第1変数xに第1関数を加えてi番目の第1変数xを更新することを含む。i番目の第1変数xは、第1変数群{x}の1つである。第1関数の変数は、i番目の第2変数yを含む。i番目の第2変数yは、第2変数群{y}の1つである。
【0052】
第2変数更新は、第2変数更新前のi番目の第2変数yに第2関数及び第3関数を加えて、i番目の第2変数yを更新することを含む。第2関数の変数は、i番目の第1変数xを含む。第3関数の変数は、第1パラメータ群{J}の少なくとも一部及び第1変数群{x}の少なくとも一部を含む。
【0053】
そして、処理部20は、上記の処理手順を繰り返した後に得られるi番目の第1変数x、及び、処理手順を繰り返した後に得られるi番目の第1変数xの関数の少なくともいずれかを出力する。例えば、第1変数群{x}に含まれる任意の第1変数、及び、処理手順を繰り返した後に得られる任意の第1変数の関数の少なくともいずれかが出力される。例えば、第1変数群{x}に含まれる全ての第1変数、及び、処理手順を繰り返した後に得られる全ての第1変数のそれぞれの関数の少なくともいずれかが出力されても良い。
【0054】
実施形態において、上記の第1関数は、第1変数群{x}から独立している。第1変数群{x}の値を変更しても、第1関数の結果の値は変化しない。上記の第2関数は、第2変数群{y}から独立している。第2変数群{y}の値を変更しても、第2関数の結果の値は変化しない。上記の第3関数は、第2変数群{y}から独立している。第2変数群{y}の値を変更しても、第3関数の結果の値は変化しない。
【0055】
第1関数は、例えば、dt*D*yである(例えば、図3参照)。第2関数は、例えば、dt*[(p−D−x*x)*x−c*h*a]である(例えば、図3参照)。第3関数は、例えば、dt*c*Σ(Ji,j*x)である(例えば、図3参照)。
【0056】
実施形態において、繰り返して行われる上記の処理手順の1つにおいて、第1変数更新後に第2変数更新が行われても良い。または、第2変数更新後に第1変数更新が行われても良い。
【0057】
実施形態に係る計算装置で行われるアルゴリズムは、例えば、以下を含む。
例えば、行列J(第1パラメータ群{J}の1つの例)を取得する。または、行列Jを計算により定める。行列Jは、例えば、イジングモデルのパラメータである。このとき、ベクトルh(第2パラメータ群{h}の1つの例)をさらに取得しても良い。または、ベクトルhは、計算により定められても良い。2種類の変数(第1変数群{x}及び第2変数群{y})を用いる。一方の変数の更新には、他方の変数の値を用いる。一方の変数の更新において、その一方の変数の値を用いない。一方の変数の更新の後に、更新後のその一方の変数の値を用いて、他方を更新する。
【0058】
上記の第2関数は、例えば、i番目の第1変数xiの非線形関数である第4関数を含む。第4関数は演算パラメータ「p」も含む。2種類の変数の更新とともに「p」は変化する。
【0059】
2種類の変数の更新とともに「p」が変化すると、上記の第4関数の実数根の数が変化する。「関数の実数根」とは、関数の値がゼロとなる変数の値(実数)のことである。第2変数更新において第4関数のみを考慮した場合、第4関数の実数根は非線形力学系の固定点(fixed point)に対応する。(ハミルトン力学系では、固定点はハミルトニアンの極値に対応する。)よって、第4関数の実数根の数が変化することは、固定点の数が変化することに対応する。これは、非線形力学系の分岐現象に対応する。実施形態に係る計算装置で用いるアルゴリズムでは、変数の初期値が、初期の1つの安定固定点(stable fixed point)の近傍に設定される。「p」を変化させることで分岐(bifurcation)を起こす。分岐後の複数の安定な固定点(変数の値はこの複数の安定固定点のうちの1つの近傍へと変化する)と、解きたい組合せ最適化の離散変数と、を対応させる。これにより、分岐現象によって、その組合せ最適化問題を解く。例えば、上記の例では、分岐後の安定固定点における各xの値が、正負の2値であり、その符号と、イジングスピン(イジング問題の離散変数)と、が、対応付けられている。初期の安定固定点が原点であるため、各xの初期値と各yの初期値と、を原点の近傍(つまり、絶対値が0.1以下の小さな乱数)の値に設定する。
【0060】
第4関数は、例えば、dt*(p−D’−xi*xi)*xiである。「D’」は、0≦D’≦Dを満たす適切な定数である。初期時刻ではp=0であり、第4関数の根はxi=0の1つだけであるが。pがD’よりも大きくなると、根は3つとなり、そのうちの正負2つの根が、イジングスピンと対応付けられる。第2関数を、例えば、dt*[(p−D−xi*xi)*xi−c*hi*a]とした場合、第2関数は、dt*(p−D’−xi*xi)*xi+dt*[−(D−D’)*xi−c*hi*a]のように、第4関数と1次関数との和で表すことができる。従って、第2関数は第4関数を含む。
【0061】
上記の第4関数は、例えば、3次関数である。このような処理により、例えば、ニューラルネットワークで用いられている非線形関数(例えばシグモイド関数)を用いた計算よりも、計算が容易になる。
【0062】
実施形態においては、時間ステップ(例えば「dt」)を大きくすると、計算が高速になる。一方、時間ステップを過度に大きくすると、計算が不安定になる。このことを考慮して、計算の一部における時間ステップを大きくし、計算の別の一部では、時間ステップを小さくても良い。例えば、計算量の大きい、行列J及び第1変数xの積和演算を含む更新には、大きい時間ステップを適用しても良い。その他の更新には、小さい時間ステップを適用しても良い。これにより、さらなる高速化が可能である。
【0063】
以下、このような計算を行う場合の例について説明する。
図5は、実施形態に係る計算装置の動作の一部を例示するフローチャートである。
図5は、ステップS210を例示している。図5に示す例では、1つのループ(ステップS105〜ステップS106)の中に、小さいループ(ステップS107a〜ステップS107b)が設けられている。ステップS107aにおいて、ループ変数「m」は、1以上M以下である。小さいループの中において、ステップS110及びステップS121がM回繰り返される。ステップS110とステップS121の順序は、入れ替えが可能である。この後、ステップS122に進む。
【0064】
図5の例では、ステップS110及びステップS121の繰り返しの後に、ステップS122が実施される。
【0065】
図6は、実施形態に係る計算装置の動作の一部を例示するフローチャートである。
図6は、ステップS210を例示している。図6に示す例でも、1つのループ(ステップS105〜ステップS106)の中に、小さいループ(ステップS107c〜ステップS107d)が設けられている。ステップS107aにおいて、ループ変数「m」は、1以上M以下である。ステップS122が実施された後に、小さいループ(ステップS121及びステップS110の繰り返し)が実施される。小さいループの中において、ステップS121及びステップS110がM回繰り返される。ステップS121とステップS110の順序は、入れ替えが可能である。
【0066】
図5の例では、第1変数xの更新後に、第2変数yの更新が行われる。図6の例では、第2変数yの更新後に、第1変数xの更新が行われる。例えば、行列Jに関する積和演算を含まない更新の時間ステップ「dt’」は、「dt/M」とされる。一方、行列Jに関する積和演算を含む1回の更新(大きいループ)において、M回の小さいループ(行列Jに関する積和演算を含まない更新)を行う。上記により、例えば、大きなループの時間ステップdtを比較的大きな値にすることができる。例えば、高速な計算が可能となる。
【0067】
このように、実施形態の1の例では、上記の第2変数更新(ステップS120)は、第1サブ更新(ステップS121)及び第2サブ更新(ステップS122)を含む。
【0068】
第1サブ更新(ステップS121)は、第1サブ更新前のi番目の第2変数yに第2関数を加えてi番目の第2変数yを更新することを含む。第2サブ更新(ステップS122)は、第2サブ更新前のi番目の第2変数yに第3関数を加えてi番目の第2変数yを更新することを含む。この場合も、第2関数は、第2変数群{y}から独立している。第3関数は、第2変数群{y}から独立している。
【0069】
例えば、第1変数更新及び第1サブ更新を交互にM回(Mは1以上の整数)行った後に、第2サブ更新を行う。または、第2サブ更新後に、第1変数更新及び第1サブ更新を交互にM回行う。第1変数更新と第1サブ更新とを交互に行う順序は、入れ替えが可能である。
【0070】
第3関数は、例えば、第1パラメータ群{J}の上記の少なくとも一部と、第1変数群{x}の上記の少なくとも一部と、の積和演算を含む。
【0071】
1つの例において、上記の処理手順を繰り返した後の第4関数の実数根の数は、2以上である。処理手順を繰り返した後の第4関数の根の1つは正である。処理手順を繰り返した後の第4関数の根の別の1つは負である。処理部20(図1参照)は、例えば、処理手順を繰り返した後に得られるi番目の第1変数xの符号(すなわち±1)を出力する。
【0072】
既に説明したように、第2関数は、i番目の第2パラメータhを含んでも良い。i番目の第2パラメータhは、第2パラメータ群{h}の1つである。
【0073】
実施形態において、処理部20は、保持部10に保持されたデータを読み出し、データを更新し、更新されたデータを保持部10に保持させる。
【0074】
例えば、第1変数更新(ステップS110)は、第1変数更新前のi番目の第1変数xを保持部10から取得し、第1変数更新後のi番目の第1変数xを保持部10に保持させることを含む。第2変数更新(ステップS120)は、第2変数更新前のi番目の第2変数yを保持部10から取得し、第2変数更新後のi番目の第2変数yを保持部10に保持させることを含む。
【0075】
例えば、第1変数更新は、i番目の第2変数yを保持部10から取得して第1関数を計算し、i番目の第1変数xに第1関数を加えてi番目の第1変数xを更新することをさらに含んでも良い。例えば、第2変数更新は、i番目の1変数xを保持部10から取得して第2関数を計算し、第1パラメータ群{J}の上記の少なくとも一部及び第1変数群{x}の上記の少なくとも一部を保持部10から取得して第3関数を計算し、i番目の2変数yに第2関数及び第3関数を加えてi番目の第2変数yを更新することをさらに含んでも良い。
【0076】
実施形態において、例えば、行列Jが疎行列の場合、疎行列の圧縮形式を用いても良い。疎行列の圧縮形式には、例えば、COO(coordinate)形式またはCSR(compressed sparse row)形式などが適用できる。疎行列の圧縮形式を用いることで、例えば、メモリサイズを節約できる。疎行列の圧縮形式を用いることで、例えば、行列J及び第1変数xの積和演算を高速に実施できる。
【0077】
以下、定数「c」の例について述べる。例えば、離調「D」は、行列Jの最大固有値λmaxのc倍よりも大きくされる(例えば、非特許文献2参照)。「D」が大きすぎると、無駄な計算時間が生じる。このため、例えば、「D」がλmaxのc倍と実質的に等しいように設定する。この場合、c=D/λmaxとなる。一方、1つの例において、行列Jは、実対称行列である。この場合に、行例Jのサイズが十分大きい場合、λmaxは、2σ×N1/2と実質的に同じになる。この関係は、ランダム行列のウィグナーの半円則に基づく。「σ」は、行列Jの非対角成分の標準偏差である。この場合、c=D/(2σ×N1/2)と設定するとよい。この場合の計算例について、後述する。
【0078】
本実施形態において、精度を向上させる方法として、上記の非線形関数として用いられる関数を変更することが考えられる。例えば、以下の第9式及び第10式の関数を用いても良い。
【0079】
【数9】

【数10】

第10式において、「n」は、2以上の偶数である。このような関数を用いることで、例えば、イジング問題の解の精度を向上することができる。
【0080】
実施形態に係る計算装置110で実施される上記のアルゴリズムは、種々の構成により実施できる。計算装置110は、例えば、PCクラスタを含んでも良い。計算装置110は、例えば、GPU(Graphics Processing Unit)を含んでも良い。計算装置110は、例えば専用回路を含んでも良い。専用回路は、例えば、FPGA(field-programmable gate array)、ゲートアレイ、及び、ASIC(application specific integrated circuit)の少なくともいずれかを含んでも良い。計算装置110は、例えば、並列デジタル計算装置を含んでも良い。
【0081】
図7〜図10は、実施形態に係る計算装置の動作の一部を例示するフローチャートである。
これらの図は、ステップS210の別の例を示している。これらの図に示すように、図3〜図6の例において、ステップS110とステップS121とは、互いに入れ替えられても良い。
【0082】
図11は、実施形態に係る計算装置の例を示す模式図である。
図11に示すように、実施形態に係る計算装置111は、複数の回路(第1回路15A、第2回路15B及び第3回路15Cなど)を含む。これらの複数の回路のそれぞれは、例えば、1つのコンピュータである。これらの複数の回路のそれぞれは、例えば、1つの半導体回路でも良い。これらの複数の回路は、互いに通信(例えば、データの送受信)が可能である。計算装置111には、さらに制御回路部15Xが設けられている。制御回路部15Xにより、複数の回路における通信が制御される。
【0083】
例えば、複数の回路のそれぞれには、処理部及び保持部(記憶部)が設けられる。この他、制御部が設けられても良い。
【0084】
複数の回路(第1回路15A、第2回路15B及び第3回路15Cなど)により、並列計算が行われる。複数の回路の数は、任意である。
【0085】
例えば、第1回路15Aには、第1計算部20A及び第1保持領域10Aが設けられる。この例では、第1回路15Aは、第1制御部16Aをさらに含む。第2回路15Bには、第2計算部20B及び第2保持領域10Bが設けられる。この例では、第2回路15Bは、第2制御部16Bをさらに含む。このような構成は、第3回路15Cにも設けられる。
【0086】
処理部20は、上記の複数の計算部(第1計算部20A及び第2計算部20Bなど)を含む。例えば、第1計算部20Aは、第3関数の計算の一部を実施する。第2計算部20Bは、第3関数の計算の別の一部を実施する。これらの計算の少なくとも一部は、並列して実施される。例えば、第1計算部20Aにおける第3関数の計算の上記の一部の実施の少なくとも一部と、第2計算部20Bにおける第3関数の計算の別の一部の実施の少なくとも一部は、同時に行われる。並列計算により、計算が高速化できる。第3関数の計算量は多い。このため、第3関数の計算を並列化することにより、効果的に高速化が行われる。
【0087】
並列計算において、例えば、第1計算部20Aは、第3関数の計算の一部を実施するのに必要な、第1パラメータ群{J}の一部を、第1保持領域10Aに保持させる。このように、第1回路15Aのなかで、第3関数の計算の一部に必要な保持と処理が行われる。一方、第2計算部20Bは、第3関数の計算の別の一部を実施するのに必要な、第1パラメータ群{J}の別の一部を、第2保持領域10Bに保持させる。このように、第2回路15Bのなかで、第3関数の計算の別の一部に必要な保持と処理が行われる。
【0088】
例えば、第1パラメータ群{J}は、第1計算使用部分と、第2計算使用部分と、を含む。第1計算使用部分は、第3関数の計算の一部で用いられる。第2計算使用部分は、第3関数の計算の別の一部で用いられる。第1計算部20Aは、上記の第1計算使用部分を第1保持領域10Aに保持させる。第2計算部20Bは、上記の第2計算使用部分を第2保持領域10Bに保持させる。
【0089】
実施形態において、i番目及びj番目(「j」は「i」とは異なる)の、第1変数更新及び第1サブ更新(第2関数による更新)を並列計算しても良い。以下、この場合、処理部20に、第3計算部20C及び第4計算部20Dが設けられても良い。第3計算部20Cは、第1回路15Aに設けられる。第4計算部20Dは、第2回路15Bに設けられる。これらの計算部は、機能ブロックである。第3計算部20Cの少なくとも一部で実施される処理は、第1計算部20Aの少なくとも一部で実施されても良い。第4計算部20Dの少なくとも一部で実施される処理は、第2計算部20Bの少なくとも一部で実施されても良い。
【0090】
例えば、第3計算部20Cは、第1変数更新の計算の一部、及び、第2関数の計算(第1サブ更新)の一部を実施する。第4計算部20Dは、第1変数更新の計算の別の一部、及び、第2関数の計算(第1サブ更新)の別の一部を実施する。
【0091】
既に説明したように、第1変数更新は、第1変数更新前のi番目の第1変数xに第1関数を加えてi番目の第1変数xを更新することを含む。同様に、第1変数更新は、第1変数更新前のj番目(jはiとは異なり、1以上N以下の整数)の第1変数xに第1関数を加えてj番目の第1変数xを更新することをさらに含む。ここで、j番目の第1変数xは、第1変数群{x}の1つである。第1関数の変数は、j番目の第2変数yを含む。j番目の第2変数yは、第2変数群{y}の1つである。
【0092】
例えば、第1変数更新の計算の一部は、i番目の第1変数xの更新の計算を含む。第1変数更新の計算の別の一部は、j番目の第1変数xの更新の計算を含む。
【0093】
一方、第2関数の計算の一部は、i番目の第1変数xを変数として含む第2関数の計算を含む。第2関数の計算の別の一部は、j番目の第1変数xを変数として含む第2関数の計算を含む。
【0094】
第3計算部20Cにおける、第1変数更新の計算の一部、及び、第2関数の計算(第1サブ更新)の一部の実施の少なくとも一部と、第4計算部20Dにおける第1変数更新の計算の別の一部、及び、第2関数の計算(第1サブ更新)の別の一部の実施の少なくとも一部は、同時に行われても良い。このような並列計算により、高速に計算できる。
しても良い。
【0095】
以下、実施形態に係る計算装置の計算例について説明する。以下の計算例において、計算時間は、パラメータの設定の時間を含まない。計算時間は、パラメータの設定の後に、微分方程式を解くのに要した時間に対応する。
【0096】
第1計算例では、PCクラスタにより計算が行われる。第1計算例では、変数及びパラメータは、「float」(32ビット浮動小数点実数)として扱われる。計算コアの数を「Q」とする。「Q」は、Nの約数である。L=N/Qとする。
【0097】
PCクラスタで上記のアルゴリズムを並列して計算する際に、MPI(Message Passing Interface)が用いられる。MPIは、分散メモリ型並列計算に対応する。MPIにおいては、複数の計算コアのそれぞれは、L個の第1分割変数(x)と、L個の第2分割変数(y)と、の1つの組み合わせを処理する。
【0098】
例えば、i番目の計算コアは、{x|n=(i−1)L+1, …、 iL}、及び、{y|n=(i−1)L+1, …、 iL}を保持し、これらの更新を行う。
【0099】
i番目の計算コアは、{h|n=(i−1)L+1, …、 iL}、及び、{Jm,n|m=(i−1)L+1, …、 iL;n=1…N}も保持できる。{h|n=(i−1)L+1, …、 iL}、及び、{Jm,n|m=(i−1)L+1, …、 iL;n=1…N}は、{y|n=(i−1)L+1, …、 iL}の更新に用いられる。
【0100】
例えば、{y|n=(i−1)L+1, …、 iL}のそれぞれの更新には、{x|n=(1, …、 N}の全成分が用いられる。例えば、Allgather関数により、{x|n=1, …、 N}の情報が、全ての計算コアに供給される。すなわち、情報(データ)が共有される。
【0101】
実施形態において、複数の計算コアの間において、通信が行われる。すなわち、データの送受信が行われる。この通信において、{y|n=(i−1)L+1, …、 iL}に関する通信、及び、{Jm,n|m=(i−1)L+1, …、 iL;n=1…N}に関する通信は不要である。
【0102】
例えば、第1変数群{x}に関しての通信を行わず、第1パラメータ群{J}及び第1変数群{x}の積和演算を分割して並列して実施し、その結果を通信して第2変数群{y}の更新を行う方法が考えられる。この方法においては、第1パラメータ群{J}及び第1変数群{x}の積和演算を分割して実施する。
【0103】
以下、N=2000である場合(第1計算例)と、N=100000である場合(第2計算例)と、の計算の例について説明する。
【0104】
第1計算例(N=2000の場合)として、「K2000」問題(非特許文献1参照)の計算例について説明する。「K2000」問題は、N=2000の全結合イジングモデルである。行列Jの非対角成分は、±1のいずれかである。ベクトルhの成分は、すべてゼロである。従って、ベクトルhを含む項の計算は行われない。この場合において、行列Jの非対角成分の標準偏差σは、1である。このため、「c」をc=D/(2N1/2)に設定する。「K2000」問題における行列Jの実際の最大固有値は、88.813324である。一方、ランダム行列理論における理論値は、2σN1/2=89.442719であり、これらの値は、互いに非常に近い。
【0105】
以下に説明する第1計算例では、Q=25であり、dp*(T/dt)=D=2であり、T=50である。
【0106】
実施形態において、M=1で、dt=0.25の場合、計算時間は、7.6msである。このときに得られたイジングエネルギーの100回の平均値は、約−66086である。この値を「カット数」(第11式、第12式、及び、非特許文献1参照)に換算した値は、32523である。「カット数」が大きいことは、精度が高いことに対応する。
【0107】
実施形態において、M=5で、dt=0.5の場合、計算時間は、4.1msである。このときに得られたイジングエネルギーの100回の平均値は、約−66137である。この値を「カット数」に換算すると、32549である。M=5の場合における「dt」は、M=1の場合の「dt」の2倍にできる。M=5の場合の計算時間は、M=1の場合の計算時間の約半分になる。高速な計算が可能である。
【0108】
一方、非特許文献1によると、コヒーレントイジングマシンにおいて、5msにおける100回の「カット数」(非特許文献1参照)の平均値は、32457である。一方、非特許文献1によると、シミュレーティッドアニーリングにおいて、50msにおける100回の「カット数」の平均値は、32314である。このように、実施形態に係る計算により、コヒーレントイジングマシン及びシミュレーティッドアニーリングよりも短時間で、より高精度の解が得られる。
【0109】
図12は、実施形態に係る計算の特性を例示するグラフである。
図12は、計算により得られる「カット数」と、「c」と、の関係の例を示している。図12の縦軸は、「c/c」である。既に説明したように、c=D/(2N1/2)である。図12の縦軸は、カット数Nmcである。カット数Nmcは、以下の第11式及び第12式、で表される。
【0110】
【数11】
【0111】
【数12】
【0112】
図12に示すように、「c/c」cが、約1以上、約1.5以下のときに大きなカット数Nmcが得られる。
【0113】
以下、第2計算例(N=100000の場合)について説明する。第2計算例では、行列Jの非対角成分、及び、ベクトルhの成分は、「乱数」により設定される。「乱数」においては、−1〜1の値が一様に設定される。この場合の行列Jの非対角成分の標準偏差σは、1/(31/2)である。このため、c=31/2D/(2N1/2)と設定する。その他のパラメータに関しては、Q=1250であり、dp*(T/dt)=D=2であり、T=50であり、dt=0.5であり、M=5である。
【0114】
図13は、計算結果を例示するグラフである。
図13には、実施形態に係る計算での第2計算例の結果と、参考例に係る計算での第2計算例の結果と、が示されている。図13の横軸は、計算時間Tc(秒)である。縦軸は、イジングエネルギーの100回の平均値Vaveである。図13には、実施形態に係る計算結果110Eと、参考例の計算結果119Rと、が示されている。これらの計算例において、計算コアの数は、1250である。
【0115】
実施形態に係る計算結果110Eにおいて、「n」は第10式の非線形関数を用いた場合の第10式中の「n」の値を示している。計算結果110Eにおいて、「n」が書かれていない曲線は、第7式が用いられた場合に対応する。
【0116】
参考例の計算結果119Rでは、シミュレーティッドアニーリングによる計算が行われる。シミュレーティッドアニーリングでは、スピン反転によるエネルギー変化が、MPIにより、並列計算される。これらの計算においては、逆温度を線形に増加させている。参考例の計算結果119Rの複数の曲線において、増加率が互いに異なる。
【0117】
図13から分かるように、実施形態に係る計算結果110Eにおいて、最終的な平均値Vaveは、低い(絶対値が大きい)。これに対して、参考例の計算結果においては、最終的な平均値Vaveは十分に低くならない(絶対値が十分に大きくならない)。このように、実施形態においては、高い精度の計算結果が得られる。実施形態によれば、参考例(シミュレーティッドアニーリング)に比べて、同じ精度が得られるのに要する計算時間Tcは、1/10以下である。実施形態に係る計算は、参考例に比べて、10倍以上高速である。
【0118】
以下、本実施形態に係る計算の第3計算例について説明する。第3計算例では、GPUにより、上記の計算が行われる。この計算において、例えば、変数及びパラメータは、float(32ビット浮動小数点実数)として扱われる。
【0119】
この方法では、第1変数群{x}、第2変数群{y}、第1パラメータ群{J}及び第2パラメータ群{h}は、デバイス変数として定義される。第1パラメータ群{J}は、行列Jである。行列J及び第1変数xの積和演算を用いた第2変数yの更新は、行列ベクトル積関数により行われる。第1変数x及び第2変数yに関するその他の更新に関して、i番目の成分(x,y)の更新が1つのスレッドで行われる。
【0120】
第3計算例では、1つのGPUを用いて、第1計算例と同様の条件で、「K2000」問題が計算される。第3計算例の計算時間は、14.7ms、100回の「カット数」の平均値32549が得られる。第3計算例においても、参考例のシミュレーティッドアニーリングの結果よりも高速に計算できる。
【0121】
(第2実施形態)
第2実施形態は、第1実施形態に関して説明した計算が可能な回路を含む。
【0122】
(第3実施形態)
第3実施形態は、計算プログラムに係る。この計算プログラムは、コンピュータに、処理手順を繰り返させる。この処理手順は第1変数更新及び第2変数更新を含む。
【0123】
第1変数更新は、第1変数更新前のi番目(iは1以上N以下の整数であり、Nは2以上の整数)の第1変数xに第1関数を加えてi番目の第1変数xを更新することを含む。i番目の第1変数xは、第1変数群{x}の1つである。第1関数の変数は、i番目の第2変数yを含む。i番目の第2変数yは、第2変数群{y}の1つである。第2変数更新は、第2変数更新前のi番目の第2変数yに第2関数及び第3関数を加えてi番目の第2変数yを更新することを含む。第2関数の変数は、i番目の第1変数xを含む。第3関数の変数は、第1パラメータ群{J}の少なくとも一部及び第1変数群{x}の少なくとも一部を含む。計算プログラムは、コンピュータに、処理手順を繰り返した後に得られるi番目の第1変数x及び処理手順を繰り返した後に得られるi番目の第1変数xの関数少なくともいずれかを出力させる。
【0124】
本実施形態に係る計算プログラムには、第1実施形態及び第2実施形態に関して説明した処理が適用できる。
【0125】
(第4実施形態)
第4実施形態は、コンピュータ読み取り可能な記録媒体である。この記録媒体は、コンピュータに、処理手順を繰り返させるプログラムが記録されている。この処理手順は第1変数更新及び第2変数更新を含む。
【0126】
第1変数更新は、第1変数更新前のi番目(iは1以上N以下の整数であり、Nは2以上の整数)の第1変数xに第1関数を加えてi番目の第1変数xを更新することを含む。i番目の第1変数xは、第1変数群{x}の1つであり、第1関数の変数は、i番目の第2変数yを含む。i番目の第2変数yは、第2変数群{y}の1つである。第2変数更新は、第2変数更新前のi番目の第2変数yに第2関数及び第3関数を加えてi番目の第2変数yを更新することを含む。第2関数の変数は、i番目の第1変数xを含む。第3関数の変数は、第1パラメータ群{J}の少なくとも一部及び第1変数群{x}の少なくとも一部を含む。プログラムは、コンピュータに、処理手順を繰り返した後に得られるi番目の第1変数x及び処理手順を繰り返した後に得られるi番目の第1変数xの関数少なくともいずれかを出力させる。
【0127】
本実施形態に係る記録媒体には、第1実施形態及び第2実施形態に関して説明下処理が適用できる。
【0128】
(第5実施形態)
本実施形態は、計算方法に係る。計算方法は、処理手順を繰り返る。処理手順は第1変数更新及び第2変数更新を含む。
【0129】
第1変数更新は、第1変数更新前のi番目(iは1以上N以下の整数であり、Nは2以上の整数)の第1変数xに第1関数を加えてi番目の第1変数xを更新することを含む。i番目の第1変数xは、第1変数群{x}の1つである。第1関数の変数は、i番目の第2変数yを含む。i番目の第2変数yは、第2変数群{y}の1つである。第2変数更新は、第2変数更新前のi番目の第2変数yに第2関数及び第3関数を加えてi番目の第2変数yを更新することを含む。第2関数の変数は、i番目の第1変数xを含む。第3関数の変数は、第1パラメータ群{J}の少なくとも一部及び第1変数群{x}の少なくとも一部を含む。
【0130】
この計算方法は、処理手順を繰り返した後に得られるi番目の第1変数x及び処理手順を繰り返した後に得られるi番目の第1変数xの関数少なくともいずれかを出力する。
【0131】
上記の種々の情報(データ)の処理(指示)は、例えば、プログラム(ソフトウェア)に基づいて実行される。例えば、コンピュータが、このプログラムを記憶し、このプログラムを読み出すことにより、上記の種々の情報の処理が行われる。
【0132】
上記の種々の情報の処理は、コンピュータに実行させることのできるプログラムとして、磁気ディスク(フレキシブルディスク及びハードディスクなど)、光ディスク(CD−ROM、CD−R、CD−RW、DVD−ROM、DVD±R、DVD±RWなど)、半導体メモリ、または、他の記録媒体に記録されても良い。
【0133】
例えば、記録媒体に記録された情報は、コンピュータ(または組み込みシステム)により読み出されることが可能である。記録媒体において、記録形式(記憶形式)は任意である。例えば、コンピュータは、記録媒体からプログラムを読み出し、このプログラムに基づいてプログラムに記述されている指示をCPUで実行させる。コンピュータにおいて、プログラムの取得(または読み出し)は、ネットワークを通じて行われても良い。
【0134】
記録媒体からコンピュータ(または組み込みシステム)にインストールされたプログラムに基づいてコンピュータ上で稼働している種々のソフトウェアにおいて、上記の情報の処理の少なくとも一部が実施されても良い。このソフトウェアは、例えば、OS(オペレーティングシステム)などを含む。このソフトウェアは、例えば、ネットワーク上で動作するミドルウェアなどを含んでも良い。
【0135】
実施形態における記録媒体は、LANまたはインターネットなどにより得られたプログラムをダウンロードして記憶された記録媒体も含まれる。複数の記録媒体に基づいて、上記の処理が行われても良い。
【0136】
実施形態に係るコンピュータは、1つまたは複数の装置(例えばパーソナルコンピュータなど)を含む。実施形態に係るコンピュータは、ネットワークにより接続された複数の装置を含んでも良い。
【0137】
実施形態によれば、最適化問題を高速に計算できる計算装置、計算プログラム、記録媒体及び計算方法が提供できる。
【0138】
以上、例を参照しつつ、本発明の実施の形態について説明した。しかし、本発明は、これらの例に限定されるものではない。例えば、計算装置に含まれる処理部、取得部及び保持部などの各要素の具体的な構成に関しては、当業者が公知の範囲から適宜選択することにより本発明を同様に実施し、同様の効果を得ることができる限り、本発明の範囲に包含される。
【0139】
各例のいずれか2つ以上の要素を技術的に可能な範囲で組み合わせたものも、本発明の要旨を包含する限り本発明の範囲に含まれる。
【0140】
本発明の実施の形態として上述した計算装置、計算プログラム、記録媒体及び計算方法を基にして、当業者が適宜設計変更して実施し得る全ての計算装置、計算プログラム、記録媒体及び計算方法も、本発明の要旨を包含する限り、本発明の範囲に属する。
【0141】
本発明の思想の範疇において、当業者であれば、各種の変更例及び修正例に想到し得るものであり、それら変更例及び修正例についても本発明の範囲に属するものと了解される。
【0142】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【0143】
10…保持部、
10A、10B…第1、第2保持領域、
10Ap、10Bp…第1、第2保持回路、
15A〜15C…第1〜第3回路、
15X…制御回路部、
16A、16B…第1、第2制御部、
16X…回路、
20…処理部、
20A〜20D…第1〜第4計算部、
20Ap、20Bp…第1、第2処理回路、
31…取得部、
32…操作部、
33…表示部、
110、111…計算装置、
110E、119R…計算結果、
Nmc…カット数、
Tc…計算時間、
Vave…平均値
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】