(57)【要約】【課題】問題に応じた適切な動作条件を自動的に設定可能にする。【解決手段】操作部１１に問題が入力され、演算部１３はイジングモデルの基底状態を探索し、管理部１２は、操作部１１から入力された問題をイジングモデルに変換し、変換したイジングモデルと初期動作条件とを演算部１３に入力し、初期動作条件を用いて演算部１３に基底状態を探索させた結果に基づいて、初期動作条件を変更した全体動作条件を用いて基底状態を演算部１３に探索させる。【選択図】図１
2019160169.tif 000002
【特許請求の範囲】
【請求項１】
問題が入力される操作部と、
イジングモデルの基底状態を探索する演算部と、
前記操作部から入力された前記問題を前記イジングモデルに変換し、変換した前記イジングモデルと初期動作条件とを前記演算部に入力し、前記初期動作条件を用いて前記演算部に前記基底状態を探索させた結果に基づいて、前記初期動作条件を変更した全体動作条件を用いて前記基底状態を前記演算部に探索させる、管理部と、
を有する最適化装置。
【請求項２】
前記演算部は、複数の第１の演算部を有し、
前記管理部は、前記複数の第１の演算部のそれぞれに、互いに異なる前記初期動作条件を入力し、前記複数の第１の演算部のそれぞれにおいて前記基底状態を探索させた結果に基づいた交換確率にしたがって、前記複数の第１の演算部のうち、第２の演算部と第３の演算部に入力する前記初期動作条件を交換する、
請求項１に記載の最適化装置。
【請求項３】
前記演算部は、複数の第１の演算部を有し、
前記管理部は、前記複数の第１の演算部のそれぞれに、互いに異なる前記初期動作条件を入力し、前記複数の第１の演算部のそれぞれにおいて前記基底状態を探索させた結果に基づいて、前記複数の第１の演算部のそれぞれに、前記初期動作条件を変更した、互いに異なる前記全体動作条件を入力する、
請求項１に記載の最適化装置。
【請求項４】
前記管理部は、前記問題を前記イジングモデルに変換する第１の管理部と、前記演算部が搭載された演算装置に実装され、前記初期動作条件を前記全体動作条件に変更する第２の管理部とを有する、
請求項１乃至３の何れか一項に記載の最適化装置。
【請求項５】
問題が入力される操作部と、イジングモデルの基底状態を探索する演算部と、前記演算部を管理する管理部とを有する最適化装置の制御方法において、
前記管理部が、
前記操作部から入力された前記問題を前記イジングモデルに変換し、
変換した前記イジングモデルと初期動作条件とを前記演算部に入力し、
前記初期動作条件を用いて前記演算部に前記基底状態を探索させた結果に基づいて、前記初期動作条件を変更した全体動作条件を用いて前記基底状態を前記演算部に探索させる、
最適化装置の制御方法。
【請求項６】
問題が入力される操作部と、イジングモデルの基底状態を探索する演算部と、前記演算部を管理する管理部とを有する最適化装置の制御プログラムにおいて、
前記管理部に、
前記操作部から入力された前記問題を前記イジングモデルに変換し、
変換した前記イジングモデルと初期動作条件とを前記演算部に入力し、
前記初期動作条件を用いて前記演算部に前記基底状態を探索させた結果に基づいて、前記初期動作条件を変更した全体動作条件を用いて前記基底状態を前記演算部に探索させる、
最適化装置の制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適化装置、最適化装置の制御方法及び最適化装置の制御プログラムに関する。
【背景技術】
【０００２】
ノイマン型コンピュータが不得意とする多変数の最適化問題を解く方法として、イジング型のエネルギー関数を用いた最適化装置（イジングマシンまたはボルツマンマシンと呼ばれる場合もある）がある。最適化装置は、計算対象の問題を、磁性体のスピンの振る舞いを表すモデルであるイジングモデルに置き換えて計算する。
【０００３】
最適化装置は、たとえば、ニューラルネットワークを用いてモデル化することもできる。その場合、最適化装置に含まれる複数のユニット（ビット）のそれぞれが、他のビットの状態と、他のビットと自身のビットとの結合の強さを示す重み係数（結合係数とも呼ばれる）とに応じて０または１を出力するニューロンとして機能する。最適化装置は、たとえば、シミュレーテッド・アニーリングなどの確率的探索法により、上記のようなエネルギー関数（コスト関数、目的関数とも呼ばれる）の最小値が得られる各ビットの状態の組み合わせ（基底状態）を、解として求める。
【０００４】
なお、最適化問題の計算の際には、最適化装置の動作条件の設定が行われる（たとえば、特許文献１，２参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１６−１０３２８２号公報
【特許文献２】米国特許出願公開第２００３／０１６９０４１号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、最適化装置の最適な動作条件は、計算対象の問題の種類ごとに様々であり、ユーザの入力に基づいて問題に応じた適切な動作条件を設定することは困難であった。
１つの側面では、本発明は、問題に応じた適切な動作条件を自動的に設定可能な最適化装置、最適化装置の制御方法及び最適化装置の制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
１つの実施態様では、問題が入力される操作部と、イジングモデルの基底状態を探索する演算部と、前記操作部から入力された前記問題を前記イジングモデルに変換し、変換した前記イジングモデルと初期動作条件とを前記演算部に入力し、前記初期動作条件を用いて前記演算部に前記基底状態を探索させた結果に基づいて、前記初期動作条件を変更した全体動作条件を用いて前記基底状態を前記演算部に探索させる、管理部と、を有する最適化装置が提供される。
【０００８】
また、１つの実施態様では、最適化装置の制御方法が提供される。また、１つの実施態様では、最適化装置の制御プログラムが提供される。
【発明の効果】
【０００９】
１つの側面では、本発明は、ユーザが問題の種類ごとに最適な動作条件を設定することなく、問題に応じた適切な動作条件を自動的に設定できる。
【図面の簡単な説明】
【００１０】
【図１】第１の実施の形態の最適化装置及びその制御方法の例を示す図である。
【図２】異なる温度が設定される複数のレプリカのノードの状態の交換の様子を示す図である。
【図３】交換モンテカルロ法を実現する第２の実施の形態の最適化装置の一例を示す図である。
【図４】第２の実施の形態の最適化装置の動作の一例の流れを示すフローチャートである。
【図５】第３の実施の形態の最適化装置の一例を示す図である。
【図６】第３の実施の形態の最適化装置の動作の一例の流れを示すフローチャートである。
【図７】アニーリング条件の変更例を示す図である。
【図８】第４の実施の形態の最適化装置の一例を示す図である。
【図９】コンピュータのハードウェア例を示す図である。
【発明を実施するための形態】
【００１１】
以下、発明を実施するための形態を、図面を参照しつつ説明する。
（第１の実施の形態）
以下に示す最適化装置は、イジングモデルの基底状態（イジング型のエネルギー関数が最小値となるときの各ニューロンの値）を探索することで、巡回セールスマン問題などの最適化問題を計算する。イジング型のエネルギー関数Ｅ（ｘ）は、たとえば、以下の式（１）で定義される。
【００１２】
【数１】
2019160169.tif 000003
【００１３】
右辺の１項目は、全ニューロン（全ビット）から選択可能な２つのニューロンの全組み合わせについて、漏れと重複なく、２つのニューロンの値（０または１）と重み係数との積を積算したものである。ｘｉは、ｉ番目のニューロンの値、ｘｊは、ｊ番目のニューロンの値であり、Ｗｉｊは、ｉ番目とｊ番目のニューロンの結合の強さを示す重み係数である。なお、Ｗｉｊ＝Ｗｊｉ、Ｗｉｉ＝０である。
【００１４】
右辺の２項目は、全ニューロンのそれぞれのバイアスとニューロンの値との積の総和を求めたものである。ｂｉは、ｉ番目のニューロンのバイアスを示している。
また、ｉ番目のニューロンのスピン反転（値の変化）に伴うエネルギー変化ΔＥｉは、以下の式（２）で表される。
【００１５】
【数２】
2019160169.tif 000004
【００１６】
式（２）において、ｉ番目のニューロンの値ｘｉが１のとき、２ｘｉ−１は１となり、値ｘｉが０のとき、２ｘｉ−１は−１となる。なお、以下の式（３）で表されるｈｉはローカルフィールド（局所場）と呼ばれ、値ｘｉに応じてローカルフィールドｈｉに符号（＋１または−１）を乗じたものがエネルギー変化ΔＥｉである。
【００１７】
【数３】
2019160169.tif 000005
【００１８】
図１は、第１の実施の形態の最適化装置及びその制御方法の例を示す図である。
最適化装置１０は、操作部１１、管理部１２、演算部１３、記憶部１４を有する。
操作部１１には、計算対象の問題が入力される。操作部１１には、たとえば、図示しない入力デバイスが接続され、ユーザによる入力デバイスの操作によって、問題が入力される。
【００１９】
管理部１２は、操作部１１から入力された問題をイジングモデルに変換する。管理部１２は、問題に応じて、たとえば、式（１）で定義されるイジング型のエネルギー関数Ｅ（ｘ）の重み係数Ｗｉｊとバイアスｂｉを求めることで、問題のイジングモデルへの変換を行う。
【００２０】
また、管理部１２は、変換したイジングモデルと、初期動作条件とを演算部１３に入力する。初期動作条件は、たとえば、演算部１３がシミュレーテッド・アニーリングを行う場合には、温度を下げていく際の初期温度、最終温度、冷却スケジュール（冷却速度など）、演算処理の繰り返し回数、値ｘｉの初期値などである。なお、シミュレーテッド・アニーリングでは、温度はノイズの幅で表される。温度が高いほどノイズの幅が広い。ノイズは乱数生成器（ＬＦＳＲ（Linear Feedback Shift Registers）など）によって生成できる。
【００２１】
また、管理部１２は、初期動作条件を用いて演算部１３にイジングモデルの基底状態を探索させた結果に基づいて、初期動作条件を変更した全体動作条件を演算部１３に入力し、入力した全体動作条件を用いて基底状態を演算部１３に探索させる。
【００２２】
上記のような管理部１２の処理は、たとえば、記憶部１４に記憶された制御プログラムを管理部１２が実行することで行われる。
管理部１２は、たとえば、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）などの演算処理装置としてのプロセッサである。ただし、管理部１２は、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの特定用途の電子回路を含んでもよい。なお、複数のプロセッサの集合を「マルチプロセッサ」または単に「プロセッサ」ということがある。
【００２３】
なお、操作部１１と管理部１２は、１つのコンピュータによっても実現できる。
演算部１３は、入力された初期動作条件または全体動作条件を用いて、イジングモデルの基底状態を探索する。演算部１３は、確率的探索法により、イジングモデルの基底状態を探索する。
【００２４】
たとえば、演算部１３は、まず、重み係数Ｗｉｊとバイアスｂｉと値ｘｉに基づいて、式（３）で表されるローカルフィールドｈｉを演算する。そして、演算部１３は、初期動作条件または全体動作条件で指定される温度にノイズ幅が対応するノイズ値（乱数）をローカルフィールドｈｉに加え、閾値との比較によってｉ番目のニューロンの値の更新の可否を判定する。また、演算部１３は、その判定結果に基づいてｉ番目のニューロンの値を更新または維持する。演算部１３は、このような演算処理を所定回数繰り返す。なお、演算部１３はシミュレーテッド・アニーリングを行う場合、初期動作条件または全体動作条件で指定される冷却スケジュールに基づいて、たとえば、上記所定回数よりも少ないある回数の繰り返し処理ごとに、温度を下げていく（ノイズ幅を小さくする）。また、演算部１３は、上記所定回数の繰り返し処理後に、式（１）に示したエネルギー関数Ｅ（ｘ）の値（以下、単にエネルギーという）を算出する。算出されたエネルギーと、各ニューロンの値は、探索結果として、管理部１２に供給される。
【００２５】
このような演算部１３は、たとえば、重み係数Ｗｉｊとバイアスｂｉと値ｘｉを保持するレジスタ、積和演算回路、乱数生成器（ＬＦＳＲなど）、比較器、セレクタなどの論理回路を用いて実現できる。
【００２６】
記憶部１４は、たとえば、最適化装置１０の制御プログラム、初期動作条件、全体動作条件などを記憶する。記憶部１４として、ＲＡＭ（Random Access Memory）などの揮発性メモリ、または、フラッシュメモリやＥＥＰＲＯＭ（Electrically Erasable Programmable Read Only Memory）などの不揮発性メモリやＨＤＤ（Hard Disk Drive）を用いることができる。
【００２７】
以下、第１の実施の形態の最適化装置１０の動作例を説明する。
計算対象の問題が操作部１１に入力されると、管理部１２は、その問題をイジングモデルに変換し、初期動作条件とともに演算部１３に入力する。なお、管理部１２は、初期動作条件を予め演算部１３に入力しておいてもよい。
【００２８】
演算部１３は、初期動作条件を用いて、イジングモデルの基底状態を探索する。管理部１２は、演算部１３における探索結果に基づいて、初期動作条件を変更した全体動作条件を演算部１３に入力する。たとえば、所定回数の繰り返し処理後のエネルギーが閾値以上の場合や、所定回数の繰り返し処理を複数回行ったときの各繰り返し処理後のエネルギーの変動が所定値より大きい場合、管理部１２は、初期動作条件を全体動作条件に変更する。
【００２９】
全体動作条件は、初期動作条件に対して、たとえば、初期温度、最終温度、冷却スケジュール、演算処理の繰り返し回数または値ｘｉの初期値が異なっている。
演算部１３は、全体動作条件を用いて、上記と同様にイジングモデルの基底状態を探索する。管理部１２は、全体動作条件を用いた演算部１３における探索結果に基づいて、その全体動作条件をさらに変更し、変更した全体動作条件を演算部１３に入力して、演算部１３に探索させてもよい。
【００３０】
たとえば、所定回数の繰り返し処理後のエネルギーが閾値未満となったときや、所定回数の繰り返し処理を複数回行ったときの各繰り返し処理後のエネルギーの変動が所定値より小さくなったとき、管理部１２は、そのときの各ニューロンの値を解として出力する。または、管理部１２は、計算開始から所定時間の経過後における各ニューロンの値を解として出力してもよい。
【００３１】
上記のような最適化装置１０によれば、管理部１２が演算部１３による探索結果に基づいて、初期動作条件から全体動作条件に動作条件を変更するため、問題に応じた適切な動作条件を自動的に設定可能となる。また、ユーザは計算対象の問題を操作部１１に入力すればよく、動作条件を設定しなくてもよい。これにより、ユーザの経験によらず、一定品質以上の解を得ることが可能となる。
【００３２】
（第２の実施の形態）
第２の実施の形態の最適化装置は、交換モンテカルロ法（レプリカ交換法または拡張アンサンブル法などとも呼ばれる）を実現する。
【００３３】
交換モンテカルロ法は、温度の異なる複数のネットワーク（以下レプリカと呼ぶ）により確率的探索を行いながら、温度が隣接して設定されているレプリカ間で各レプリカのエネルギーの差分に応じ、各レプリカのノードの状態を交換する方法である。なお、ノードの状態とは、前述の各ニューロンの値に相当する。
【００３４】
この方法により、解が局所解に陥ることが抑制され、より高速に解を最適解に収束させることが可能となる。なお、各レプリカのノードの状態を交換する代りに、各レプリカの温度を交換しても同様の効果が得られる。
【００３５】
図２は、異なる温度が設定される複数のレプリカのノードの状態の交換の様子を示す図である。
たとえば、図２では、複数（４つ）のレプリカが用意されており、各レプリカの温度はＴ１〜Ｔ４（Ｔ４＞Ｔ３＞Ｔ２＞Ｔ１）であるとする。交換モンテカルロ法では、温度が隣接して設定されているレプリカ同士で、所定の交換確率にしたがって、ノードの状態（または温度）が交換される。交換確率はｍｉｎ（１，Ｒ）とすることができ、Ｒは以下の式（４）で表される。
【００３６】
【数４】
2019160169.tif 000006
【００３７】
なお、式（４）において、Ｔｑ，Ｔｑ＋１は、温度が隣接して設定されているｑ番目のレプリカとｑ＋１番目のレプリカにおける温度をそれぞれ表している。また、Ｅｔｏｔａｌ（Ｘｑ），Ｅｔｏｔａｌ（Ｘｑ＋１）は、上記２つのレプリカのそれぞれの総エネルギーを表している。また、Ｘｑ，Ｘｑ+１は、それぞれ、ｑ番目及びｑ＋１番目のレプリカのノードの状態をすべて含んでいるものとする。
【００３８】
このような交換確率では、Ｔｑ＜Ｔｑ＋１で、且つ、Ｅｔｏｔａｌ（Ｘｑ）＞Ｅｔｏｔａｌ（Ｘｑ＋１）であるとき、Ｒは１を超えるので、式（４）より、交換確率は１となり、ノードの状態の交換が行われる。たとえば、温度がＴ１のレプリカと温度がＴ２のレプリカ間では、温度がＴ２のレプリカのエネルギーが、温度がＴ１のレプリカのエネルギーよりも小さいときには、ノードの状態の交換が行われる。
【００３９】
一方、Ｔｑ＜Ｔｑ＋１で、且つ、Ｅｔｏｔａｌ（Ｘｑ）＜Ｅｔｏｔａｌ（Ｘｑ＋１）であるとき、確率Ｒで、ノードの状態の交換が行われる。
たとえば、温度がＴ１のレプリカと温度がＴ２のレプリカ間では、温度がＴ２のレプリカのエネルギーが、温度がＴ１のレプリカのエネルギーよりも大きいときには、確率Ｒでノードの状態の交換が行われる。
【００４０】
図３は、交換モンテカルロ法を実現する第２の実施の形態の最適化装置の一例を示す図である。
最適化装置２０は、操作部２１と、管理部２２と、演算部２３ａ１，２３ａ２，・・・，２３ａｎを含む演算部２３、記憶部２４と、を有する。
【００４１】
操作部２１は、第１の実施の形態の最適化装置１０の操作部１１と同じである。
管理部２２は、イジングモデル変換部２２ａ、交換制御部２２ｂを有する。
イジングモデル変換部２２ａは、問題に応じて、たとえば、式（１）で定義されるイジング型のエネルギー関数Ｅ（ｘ）の重み係数Ｗｉｊとバイアスｂｉを求めることで、問題のイジングモデルへの変換を行う。
【００４２】
たとえば、巡回セールスマン問題の場合、重み係数Ｗｉｊとバイアスｂｉは、都市間の距離、制約条件（同じ都市への複数回訪問や、複数都市への同時訪問などを抑制するための条件）を反映するように決定される。
【００４３】
そして、イジングモデル変換部２２ａは、演算部２３ａ１〜２３ａｎのそれぞれにイジングモデル（重み係数Ｗｉｊやバイアスｂｉ）を入力する。なお、交換モンテカルロ法を実現するために、演算部２３ａ１〜２３ａｎのそれぞれには、互いに同じイジングモデルが与えられる。
【００４４】
交換制御部２２ｂは、初期動作条件を、演算部２３ａ１〜２３ａｎのそれぞれに入力する。演算部２３ａ１〜２３ａｎのそれぞれにおける初期動作条件は、交換モンテカルロ法において、上記の各レプリカに設定される初期温度（または各ニューロンの初期値（初期状態））である。また、演算部２３ａ１〜２３ａｎを含む演算部２３にとっての初期動作条件は、最高温度、最低温度、温度間隔、レプリカ数などである。なお、交換制御部２２ｂは、複数の初期動作条件の候補の中から、入力された問題に応じて適用する初期動作条件を選択してもよいし、入力された問題に関係なく、予め決められた初期動作条件を演算部２３ａ１〜２３ａｎのそれぞれに入力してもよい。
【００４５】
たとえば、演算部２３ａ１〜２３ａｎの順に温度が高くなるように設定される場合には、最高温度は演算部２３ａｎに設定され、最低温度は演算部２３ａ１に設定される。なお、レプリカ数は、ｎ個の演算部２３ａ１〜２３ａｎのうち、使用される演算部の数に相当する。
【００４６】
また、交換制御部２２ｂは、演算部２３ａ１〜２３ａｎのそれぞれにおける基底状態の探索結果に基づいて、初期動作条件を変更した全体動作条件を演算部２３ａ１〜２３ａｎに入力する。
【００４７】
たとえば、交換制御部２２ｂは、演算部２３ａ１〜２３ａｎのそれぞれにおける所定回数の繰り返し処理後のエネルギー（式（４）の、Ｅｔｏｔａｌ（Ｘｑ），Ｅｔｏｔａｌ（Ｘｑ＋１）など）を受ける。そして、交換制御部２２ｂは、前述のｍｉｎ（１，Ｒ）の交換確率にしたがって、温度が隣接して設定されている演算部のペアにおいて、その温度（または状態）を交換するようにして初期動作条件を変更する。そして、交換制御部２２ｂは、初期動作条件を変更することで得られた動作条件（全体動作条件）を演算部２３ａ１〜２３ａｎに入力する。
【００４８】
演算部２３ａ１〜２３ａｎのそれぞれは、入力されたイジングモデルの基底状態を探索する。たとえば、演算部２３ａ１〜２３ａｎのそれぞれは、まず、重み係数Ｗｉｊとバイアスｂｉと値ｘｉに基づいて、式（３）で表されるローカルフィールドｈｉを演算する。そして、演算部２３ａ１〜２３ａｎのそれぞれは、初期動作条件または全体動作条件により指定される温度にノイズ幅が対応するノイズ値を、ローカルフィールドｈｉに加え、閾値との比較によってｉ番目のニューロンの値の更新の可否を判定する。さらに、演算部２３ａ１〜２３ａｎのそれぞれは、その判定結果に基づいてｉ番目のニューロンの値を更新または維持する。演算部２３ａ１〜２３ａｎのそれぞれは、このような処理を所定回数繰り返す。また、演算部２３ａ１〜２３ａｎのそれぞれは、上記所定回数の繰り返し処理後に、式（１）に示したエネルギーを算出する。算出されたエネルギーと、各ニューロンの値は、探索結果として、管理部２２に供給される。
【００４９】
このような演算部２３ａ１〜２３ａｎのそれぞれは、第１の実施の形態の最適化装置１０の演算部１３と同様に、たとえば、レジスタ、積和演算回路、乱数生成器、比較器、セレクタなどの論理回路を用いて実現できる。
【００５０】
記憶部２４は、たとえば、最適化装置２０の制御プログラム、初期動作条件、全体動作条件などを記憶する。記憶部２４として、ＲＡＭなどの揮発性メモリ、または、フラッシュメモリやＥＥＰＲＯＭなどの不揮発性メモリやＨＤＤを用いることができる。
【００５１】
以下、記憶部２４に記憶された制御プログラムを実行することで実現される、第２の実施の形態の最適化装置２０の動作例を説明する。
図４は、第２の実施の形態の最適化装置の動作の一例の流れを示すフローチャートである。
【００５２】
操作部２１が、ユーザによる問題の入力を受け付けると（ステップＳ１０）、管理部２２のイジングモデル変換部２２ａは、その問題をイジングモデルへ変換する（ステップＳ１１）。そして、イジングモデル変換部２２ａは、演算部２３ａ１〜２３ａｎのそれぞれにイジングモデルを入力し、交換制御部２２ｂは、初期動作条件を、演算部２３ａ１〜２３ａｎのそれぞれに入力する（ステップＳ１２）。
【００５３】
管理部２２は、演算部２３ａ１〜２３ａｎのそれぞれに、初期動作条件、または、後述の処理で初期動作条件を変更した全体動作条件を用いて、イジングモデルの基底状態を探索させる（ステップＳ１３）。そして、管理部２２は、探索における繰り返し処理が予め決められた回数であるｍ１回、終了したか否かを判定する（ステップＳ１４）。たとえば、管理部２２は、演算部２３ａ１〜２３ａｎのそれぞれの動作に用いられるクロックのパルス数を計測し、ニューロンの値の更新可否が決定される一連の処理にかかるパルス数に基づいて、ｍ１回の繰り返し処理が終了したか否かを判定する。ｍ１回の繰り返し処理が終了していないと判定された場合、ｍ１回の繰り返し処理が終了するまで、ステップＳ１４の判定処理が継続される。
【００５４】
ｍ１回の繰り返し処理が終了したと判定した場合、管理部２２は、演算部２３ａ１〜２３ａｎのそれぞれにエネルギーを算出させ、その値を取得する（ステップＳ１５）。なお、管理部２２は、各ニューロンの値を探索結果として受けて、重み係数Ｗｉｊとバイアスｂｉとに基づいて、自身でエネルギーを算出してもよい。
【００５５】
そして、管理部２２は、演算部２３ａ１〜２３ａｎのそれぞれにおけるエネルギーのうちの最低値が、上記ステップＳ１５の処理が予め決められた回数であるｍ２回分行われる間、変化がないか否かを判定する（ステップＳ１６）。
【００５６】
最低値がｍ２回分の間に変化する場合、管理部２２は、温度が隣接して設定されている演算部のペアにおいて、前述の交換確率（ｍｉｎ（１，Ｒ））でその温度（または状態）を交換するようにして初期動作条件または全体動作条件を変更する（ステップＳ１７）。
そして、管理部２２は、初期動作条件または全体動作条件を変更することで得られた動作条件を演算部２３ａ１〜２３ａｎに与えて、再びステップＳ１３の探索を実行させる。
【００５７】
最低値がｍ２回分の間に変化しない場合、管理部２２は、その最低値を出力する演算部の状態（各ニューロンの値）を解として出力する（ステップＳ１８）。たとえば、管理部２２は、図示しない表示装置にその解を表示してもよい。
【００５８】
なお、管理部２２は、探索結果に基づいて、演算部２３にとっての初期動作条件（最高温度、最低温度、温度間隔、レプリカ数など）を変更してもよい。たとえば、予め決められたｍ３（＞ｍ２）回、ステップＳ１５の処理が行われても、ｍ２回分の間の最低値に変化がなくならない場合、管理部２２は、演算部２３にとっての初期動作条件を変更した全体動作条件を用いて演算部２３ａ１〜２３ａｎに探索させる。その全体動作条件を用いても、ｍ２回分の間の最低値に変化がなくならない場合、管理部２２は、さらに別の全体動作条件を用いて演算部２３ａ１〜２３ａｎに探索させてもよい。
【００５９】
上記のような最適化装置２０によれば、管理部２２が演算部２３ａ〜２３ａｎのそれぞれによる探索結果に基づいて、初期動作条件から全体動作条件に動作条件を変更するため、問題に応じた適切な動作条件を自動的に設定可能となる。また、ユーザは計算対象の問題を操作部２１に入力すればよく、動作条件を設定しなくてもよい。これにより、ユーザの経験によらず、一定品質以上の解を得ることが可能となる。
【００６０】
また、最適化装置２０は、交換モンテカルロ法を実現するため、解が局所解に陥ることが抑制され、より高速に解を最適解に収束させることが可能となる。
（第３の実施の形態）
図５は、第３の実施の形態の最適化装置の一例を示す図である。図５において、図３に示した第２の実施の形態の最適化装置２０と同じ要素については同一符号が付されている。
【００６１】
第３の実施の形態の最適化装置３０において、管理部３１のアニーリング条件設定部３１ａは、初期動作条件または全体動作条件として、アニーリング条件などを、演算部３２ａ１，３２ａ２，・・・，３２ａｎに入力する。アニーリング条件には、温度を下げていく際の初期温度、最終温度、冷却速度、各ニューロンの初期値などがある。アニーリング条件設定部３１ａは、演算部３２ａ１〜３２ａｎがそれぞれ異なるアニーリング条件でシミュレーテッド・アニーリングを行うように、演算部３２ａ１〜３２ａｎにアニーリング条件を入力する。
【００６２】
また、アニーリング条件設定部３１ａは、演算部３２ａ１〜３２ａｎにおける探索結果に基づいて、初期動作条件または全体動作条件を変更する。
演算部３２に含まれる演算部３２ａ１〜３２ａｎのそれぞれは、第２の実施の形態の最適化装置２０の演算部２３ａ１〜２３ａｎのそれぞれと同様の機能を有するとともに、上記アニーリング条件に基づいて、シミュレーテッド・アニーリングを行う。
【００６３】
以下、記憶部２４に記憶された制御プログラムを実行することで実現される、第３の実施の形態の最適化装置３０の動作例を説明する。
図６は、第３の実施の形態の最適化装置の動作の一例の流れを示すフローチャートである。
【００６４】
ステップＳ２０〜Ｓ２２の処理は、第２の実施の形態の最適化装置２０によるステップＳ１０〜Ｓ１２の処理とほぼ同じである。ただ、ステップＳ２２の処理では、管理部３１のアニーリング条件設定部３１ａは、冷却速度などのアニーリング条件を含む初期動作条件を、演算部３２ａ１〜３２ａｎに入力する。
【００６５】
ステップＳ２３〜Ｓ２６の処理は、第２の実施の形態の最適化装置２０によるステップＳ１３〜１６の処理とほぼ同じである。ただ、ステップＳ２３の処理では、演算部３２ａ１〜３２ａｎのそれぞれは、互いに異なるアニーリング条件を用いたシミュレーテッド・アニーリングを行うことで、イジングモデルの基底状態の探索を行う。
【００６６】
最低値がｍ２回分の間に変化する場合（ステップＳ２６：ＮＯ）、管理部３１は、初期動作条件または全体動作条件に含まれるアニーリング条件を変更する（ステップＳ２７）。そして、管理部３１は、初期動作条件または全体動作条件を変更することで得られた動作条件（全体動作条件）を演算部３２ａ１〜３２ａｎに与えて、再びステップＳ２３の探索を実行させる。
【００６７】
ステップＳ２８の処理は、第２の実施の形態の最適化装置２０によるステップＳ１８の処理と同じである。
図７は、アニーリング条件の変更例を示す図である。
【００６８】
管理部３１は、たとえば、複数種類のアニーリング条件のそれぞれについて、エネルギーを最小にする値（たとえば、初期温度や最終温度など）を順番に決定していく。管理部３１は、前述のステップＳ２２の処理において、たとえば、まず演算部３２ａ１〜３２ａｎに異なる初期温度を入力し、その他のアニーリング条件については同じ値を入力する。管理部３１は、図７に示すように、最も高い初期温度Ｔｓ１を演算部３２ａ１に入力し、その次に高い初期温度Ｔｓ２を演算部３２ａ２に入力し、最も低い初期温度Ｔｓｎを演算部３２ａｎに入力する。演算部３２ａ１〜３２ａｎに入力される最終温度Ｔｅは同じである。
【００６９】
このようなアニーリング条件を用いた探索により、初期温度Ｔｓ２を用いた演算部３２ａ２におけるエネルギーが、他の演算部におけるエネルギーの値よりも小さくなったとする。この場合、ステップＳ２７の処理では、管理部３１は、初期温度Ｔｓ２を全ての演算部３２ａ１〜３２ａｎに与え、演算部３２ａ１〜３２ａｎに異なる最終温度を与えるように、動作条件を変更する。
【００７０】
管理部３１は、図７に示すように、たとえば、最も高い最終温度Ｔｅ１を演算部３２ａ１に入力し、その次に高い最終温度Ｔｅ２を演算部３２ａ２に入力し、最も低い最終温度Ｔｅｎを演算部３２ａｎに入力する。そして、同様に管理部３１は、最もエネルギーが小さくなる最終温度を決定し、その後は決定した最終温度を用いて演算部３２ａ１〜３２ａｎに探索を行わせる。
【００７１】
管理部３１は、他のアニーリング条件についても同様に決定していき、たとえば、最後のアニーリング条件において異なる値を割り当てた演算部３２ａ１〜３２ａｎのうち、エネルギーが最低となる演算部の状態（各ニューロンの値）を解として出力する。
【００７２】
上記のような最適化装置３０においても、管理部３１が演算部３２ａ１〜３２ａｎのそれぞれによる探索結果に基づいて動作条件を変更するため、第２の実施の形態の最適化装置２０と同様の効果が得られる。
【００７３】
なお、管理部３１は、様々な動作条件による探索を、複数の演算部に並列に実行させて、動作条件を変更することなく、エネルギーが最小になる演算部の状態（各ニューロンの値）を解として出力してもよい。その場合、動作条件の変更が不要であるため、計算時間を短縮できるが、解の精度を上げるために、多数の動作条件による探索を、多数の演算部に並列に実行させることになり、演算部の数が多くなる。上記のように、管理部３１が、探索結果に基づいて動作条件を変更することで、一度に適用する動作条件を減らせるため、演算部の数の増加を抑制（ハードウェア量を小さく）できる。また、最適化装置３０は、複数の演算部３２ａ１〜３２ａｎを用いるため、動作条件の変更回数を抑えることができ、計算時間の増加を抑制できる。
【００７４】
また、管理部３１は、１つの演算部に探索を行わせ、その探索結果に基づいて動作条件を変更してもよい。その場合、動作条件の変更にかかる時間は増えるものの、演算部の数を減らせることができ、ハードウェア量を小さくできる。
【００７５】
（第４の実施の形態）
図８は、第４の実施の形態の最適化装置の一例を示す図である。図８において、図３に示した第２の実施の形態の最適化装置２０と同じ要素については同一符号が付されている。
【００７６】
第４の実施の形態の最適化装置４０は、管理部４１の一部の機能を、演算部４２ａが搭載される演算装置４２に実装している。図８の例では、管理部４１は、第１管理部４１ａ、第２管理部４１ｂを有し、第２管理部４１ｂが、演算装置４２に実装されている。
【００７７】
第１管理部４１ａは、問題のイジングモデルへの変換や、演算部４２ａによる探索で得られた解を出力する。
第２管理部４１ｂは、演算部４２ａへの初期動作条件の入力、及び探索結果に応じた動作条件の変更（初期動作条件から全体動作条件への変更など）を行う。つまり、第２管理部４１ｂは、第２の実施の形態の最適化装置２０の交換制御部２２ｂ、または、第３の実施の形態の最適化装置３０のアニーリング条件設定部３１ａと同様の、動作条件設定（または変更）機能を有する。
【００７８】
演算装置４２がＦＰＧＡである場合、たとえば、記憶部２４から、ＦＰＧＡの回路構成データとともに、初期動作条件や全体動作条件が、ＦＰＧＡに供給され、第２管理部４１ｂや演算部４２ａの機能を実現するための回路が構築される。演算装置４２を実現する装置がＡＳＩＣである場合、ＲＯＭやプルアップ／プルダウンなどを用いて固定論理を実現し、初期動作条件や全体動作条件を予め設定できる。
【００７９】
演算部４２ａは、第２の実施の形態の最適化装置２０の演算部２３、または、第３の実施の形態の最適化装置３０の演算部３２と同様の機能を有する。
上記のような最適化装置４０においても、第２及び第３の実施の形態の最適化装置２０，３０と同様の効果が得られるとともに、演算装置４２内のハードウェアにより動作条件を変更することが可能になるため、変更にかかる時間を短縮でき計算時間を短縮できる。
【００８０】
なお、演算装置４２に余裕があれば、問題をイジングモデルに変換する機能などについても演算装置４２に実装させてもよい。
ところで、上記各実施の形態において操作部１１，２１には、問題の代りに、その問題を変換したイジングモデルがユーザによって入力されてもよい。その場合、管理部１２，２２，３１，４１は問題のイジングモデルへの変換を行わなくてもよい。ただ、管理部１２，２２，３１，４１が問題のイジングモデルへの変換を行うことで、ユーザは問題を入力するだけでよいので利便性が高くなる。
【００８１】
また、上記の各実施の形態における操作部１１，２１、管理部１２，２２，３１、第１管理部４１ａの機能は、制御プログラムによって動作するコンピュータによって実現できる。以下、コンピュータのハードウェア例を示す。
【００８２】
（コンピュータのハードウェア例）
図９は、コンピュータのハードウェア例を示す図である。
コンピュータ５０は、ＣＰＵ５１、ＲＡＭ５２、ＨＤＤ５３、画像信号処理部５４、入力信号処理部５５、媒体リーダ５６及び通信インタフェース５７を有する。上記ユニットは、バスに接続されている。
【００８３】
ＣＰＵ５１は、プログラムの命令を実行する演算回路を含むプロセッサである。ＣＰＵ５１は、ＨＤＤ５３に記憶されたプログラム（たとえば、前述の制御プログラム）やデータの少なくとも一部をＲＡＭ５２にロードし、プログラムを実行する。なお、ＣＰＵ５１は複数のプロセッサコアを備えてもよく、コンピュータ５０は複数のプロセッサを備えてもよく、前述の処理を複数のプロセッサまたはプロセッサコアを用いて並列に実行してもよい。
【００８４】
ＲＡＭ５２は、ＣＰＵ５１が実行するプログラムやＣＰＵ５１が演算に用いるデータを一時的に記憶する揮発性の半導体メモリである。なお、コンピュータ５０は、ＲＡＭ以外の種類のメモリを備えてもよく、複数個のメモリを備えてもよい。
【００８５】
ＨＤＤ５３は、ＯＳ（Operating System）やミドルウェアやアプリケーションソフトウェアなどのソフトウェアのプログラム、及び、データを記憶する不揮発性の記憶装置である。プログラムには、たとえば、前述の管理部１２，２２，３１、第１管理部４１ａなどの動作をコンピュータ５０に実行させる制御プログラムが含まれる。なお、コンピュータ５０は、フラッシュメモリやＳＳＤ（Solid State Drive）などの他の種類の記憶装置を備えてもよく、複数の不揮発性の記憶装置を備えてもよい。
【００８６】
画像信号処理部５４は、ＣＰＵ５１からの命令にしたがって、コンピュータ５０に接続されたディスプレイ５４ａに画像（たとえば、最適化問題の計算結果を表す画像）を出力する。ディスプレイ５４ａとしては、ＣＲＴ（Cathode Ray Tube）ディスプレイ、液晶ディスプレイ（ＬＣＤ：Liquid Crystal Display）、プラズマディスプレイ（ＰＤＰ：Plasma Display Panel）、有機ＥＬ（ＯＥＬ：Organic Electro-Luminescence）ディスプレイなどを用いることができる。
【００８７】
入力信号処理部５５はコンピュータ５０に接続された入力デバイス５５ａから入力信号を取得し、ＣＰＵ５１に出力する。入力信号処理部５５は、前述の操作部１１，２１の機能を実現する。入力デバイス５５ａとしては、マウスやタッチパネルやタッチパッドやトラックボールなどのポインティングデバイス、キーボード、リモートコントローラ、ボタンスイッチなどを用いることができる。また、コンピュータ５０に、複数の種類の入力デバイスが接続されていてもよい。
【００８８】
媒体リーダ５６は、記録媒体５６ａに記録されたプログラムやデータを読み取る読み取り装置である。記録媒体５６ａとして、たとえば、磁気ディスク、光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）、半導体メモリなどを使用できる。磁気ディスクには、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤが含まれる。光ディスクには、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）が含まれる。
【００８９】
媒体リーダ５６は、たとえば、記録媒体５６ａから読み取ったプログラムやデータを、ＲＡＭ５２やＨＤＤ５３などの他の記録媒体にコピーする。読み取られたプログラムは、たとえば、ＣＰＵ５１によって実行される。なお、記録媒体５６ａは、可搬型記録媒体であってもよく、プログラムやデータの配布に用いられることがある。また、記録媒体５６ａやＨＤＤ５３を、コンピュータ読み取り可能な記録媒体ということがある。
【００９０】
通信インタフェース５７は、ネットワーク５７ａに接続され、ネットワーク５７ａを介して他の情報処理装置と通信を行うインタフェースである。通信インタフェース５７は、スイッチなどの通信装置とケーブルで接続される有線通信インタフェースでもよいし、基地局と無線リンクで接続される無線通信インタフェースでもよい。
【００９１】
なお、前述のように、上記の管理部１２，２２，３１、第１管理部４１ａなどの処理内容は、コンピュータ５０にプログラムを実行させることで実現できる。
プログラムは、コンピュータ読み取り可能な記録媒体（たとえば、記録媒体５６ａ）に記録しておくことができる。記録媒体として、たとえば、磁気ディスク、光ディスク、光磁気ディスク、半導体メモリなどを使用できる。磁気ディスクには、ＦＤおよびＨＤＤが含まれる。光ディスクには、ＣＤ、ＣＤ−Ｒ（Recordable）／ＲＷ（Rewritable）、ＤＶＤおよびＤＶＤ−Ｒ／ＲＷが含まれる。プログラムは、可搬型の記録媒体に記録されて配布されることがある。その場合、可搬型の記録媒体から他の記録媒体（たとえば、ＨＤＤ５３）にプログラムをコピーして実行してもよい。
【００９２】
以上、実施の形態に基づき、本発明の最適化装置、最適化装置の制御方法及び最適化装置の制御プログラムの一観点について説明してきたが、これらは一例にすぎず、上記の記載に限定されるものではない。
【符号の説明】
【００９３】
１０  最適化装置
１１  操作部
１２  管理部
１３  演算部
１４  記憶部
【図１】
2019160169.tif 000007
【図２】
2019160169.tif 000008
【図３】
2019160169.tif 000009
【図４】
2019160169.tif 000010
【図５】
2019160169.tif 000011
【図６】
2019160169.tif 000012
【図７】
2019160169.tif 000013
【図８】
2019160169.tif 000014
【図９】
2019160169.tif 000015