(57)【要約】【課題】極小値問題を回避しつつ最適値でネットワークが停止する解法により資源スケジュール問題を解くより良いシステムを提供する。【解決手段】複数の資源の好適なスケジュールを導出するシステムとして、複数の非線形素子による逆関数遅延ネットワークを用いた資源スケジュール算出部を含み、求める資源スケジュール問題のエネルギー関数と同じ次元のエネルギー関数を持つHC-ID モデルに従って動作する複数の非線形素子の出力を、資源の割り当て方として演算処理させ、少なくとも２種類以上の資源についての割り当て方を解探査結果として出力させるように、資源スケジュール算出部を動作させる。【選択図】図１
2014041413.tif 000002
【特許請求の範囲】
【請求項１】
非線形素子による逆関数遅延ネットワークを用いた資源スケジュール問題の解探査方法であって、
前記非線形素子を、求める資源スケジュール問題のエネルギー関数と同じ次元のエネルギー関数を持つHC-ID（Higher order Connections‐Inverse function Delayed network）モデルに従って動作処理させると共に、前記非線形素子の出力を資源の割り当て方と対応させ、少なくとも２種類以上の資源の割り当て方を、前記非線形素子による逆関数遅延ネットワークを用いて解を探査処理する
ことを特徴とする資源スケジュール問題の解探査方法。
【請求項２】
前記非線形素子の内部状態の時間に対する変化量が、複数の非線形素子の出力と非線形素子の組み合わせ毎に計算された荷重値の積の和を含む関数により決定される請求項１記載の資源スケジュール問題の解探査方法。
【請求項３】
前記複数の非線形素子の出力の積に関わる非線形素子の結合次数D が、資源スケジュール問題のコスト行列の次数d に対してD = 2d − 1 なる関係を持つことを特徴とする請求項２記載の資源スケジュール問題の解探査方法。
【請求項４】
前記非線形素子の出力の時間に対する変化量が、非線形素子の出力の関数g と非線形素子の内部状態の合成関数であることを特徴とする請求項３記載の資源スケジュール問題の解探査方法。
【請求項５】
前記HC-ID モデルによる非線形素子のもつ関係が、i 番目の非線形素子の内部状態ui と出力xi が、D を非線形素子の結合の次数，t を時刻，τu，τx ，w，h を係数，g を非線形素子の内部状態と出力に関する関数としたときに、下記式１を満たすことを特徴とする請求項４に記載の資源スケジュール問題の解探査方法。
【数１】
2014041413.tif 000019
【請求項６】
前記関数g の非線形素子の出力に関する微分値がマイナスの値となる領域を持つことを特徴とする請求項４または請求項５に記載の資源スケジュール問題の解探査方法。
【請求項７】
前記HC-IDモデルによる非線形素子のもつ関係が、i 番目の非線形素子の内部状態ui と出力xi が、D を非線形素子の結合の次数，t を時刻，τu，w，h，Δ を係数，g を非線形素子の内部状態と出力に関する関数としたときに、下記式２を満たすことを特徴とする請求項6 に記載の資源スケジュール問題の解探査方法。
【数２】
2014041413.tif 000020
【請求項８】
前記少なくとも２種類以上の割り当てるべき要素に、時間と場所が含まれることを特徴とする請求項６または請求項７に記載の資源スケジュール問題の解探査方法。
【請求項９】
前記資源スケジュール問題に関わるd 次元のコスト行列をb，ある資源の組み合わせを示す非線形素子の出力をx としたときに、複数の非線形素子の出力x の積xj1xj2・・・xjd を用いて算出されるxj1xj2・・・xjd(1- xj1xj2・・・xjd )b(j1,j2,・・・,jd) を全ての非線形素子の出力の組み合わせに対して足し合わせた項を、前記資源スケジューリング問題のエネルギー関数に含むことを特徴とする請求項６または請求項７記載の資源スケジュール問題の解探査方法。
【請求項１０】
前記資源スケジュール問題に関わる拘束条件を示す項を(Constraint Conditions)，d次元のコスト行列をb，ある資源の組み合わせを示す非線形素子の出力をx，B，C を係数，非線形素子の数をN，最適化要件のコストを示す項をCsol(x) としたときに、前記資源スケジューリング問題のエネルギー関数が下記式３であることを特徴とする請求項６または請求項７記載の資源スケジュール問題の解探査方法。
【数３】
2014041413.tif 000021
【請求項１１】
前記式３のエネルギー関数において、d次元のコスト行列をb，ある資源の組み合わせを示す非線形素子の出力をx，非線形素子の数をN としたときに最適化要件のコストを示す式が下記式４であることを特徴とする請求項１０記載の資源スケジュール問題の解探査方法。
【数４】
2014041413.tif 000022
【請求項１２】
複数の資源の好適なスケジュールを導出するシステムであって、
複数の非線形素子による逆関数遅延ネットワークを用いた資源スケジュール算出部を含み、
前記資源スケジュール算出部は、求める資源スケジュール問題のエネルギー関数と同じ次元のエネルギー関数を持つHC-ID モデルに従って動作する複数の非線形素子の出力を、資源の割り当て方として演算処理し、
少なくとも２種類以上の資源についての割り当て方を解探査結果として出力する
ことを特徴とする資源スケジュールシステム。
【請求項１３】
前記資源スケジュール算出部は、
前記求める資源スケジュール問題のエネルギー関数に関する設計内容を受け付けて、汎用化した資源スケジューリング問題のエネルギー関数に基づき、エネルギー関数式を作成処理する問題入力部と、
汎用化した HC-ID モデルのエネルギー関数と前記問題入力部が作成した前記エネルギー関数式を使用して両式のニューロン行列に対する偏微分が一致する荷重値を算出処理する荷重値算出部と、
前記荷重値算出部が算出した前記荷重値を使用して、汎用化したHC-ID モデルの状態更新式に従って状態更新を繰り返す非線形素子計算部と、
を含み、
少なくとも２種類以上の資源についての資源の割り当て方を、前記非線形素子計算部により解探査処理して求めて出力する
ことを特徴とする請求項１２記載の資源スケジュールシステム。
【請求項１４】
前記非線形素子の内部状態の時間に対する変化量が、複数の非線形素子の出力と非線形素子の組み合わせ毎に計算された荷重値の積の和を含む関数により決定される請求項１２または請求項１３に記載の資源スケジュールシステム。
【請求項１５】
前記複数の非線形素子の出力の積に関わる非線形素子の結合次数D が、資源スケジュール問題のコスト行列の次数d に対してD = 2d − 1 なる関係を持つことを特徴とする請求項１４記載の資源スケジュールシステム。
【請求項１６】
前記非線形素子の出力の時間に対する変化量が、非線形素子の出力の関数g と非線形素子の内部状態の合成関数であることを特徴とする請求項１５記載の資源スケジュールシステム。
【請求項１７】
前記HC-ID モデルによる非線形素子のもつ関係が、i 番目の非線形素子の内部状態ui と出力xi が、D を非線形素子の結合の次数，t を時刻，τu，τx ，w，h を係数，g を非線形素子の内部状態と出力に関する関数としたときに、下記式５を満たすことを特徴とする請求項１６に記載の資源スケジュールシステム。
【数５】
2014041413.tif 000023
【請求項１８】
前記関数g の非線形素子の出力に関する微分値がマイナスの値となる領域を持つことを特徴とする請求項１６または請求項１７に記載の資源スケジュールシステム。
【請求項１９】
前記HC-IDモデルによる非線形素子のもつ関係が、i 番目の非線形素子の内部状態ui と出力xi が、D を非線形素子の結合の次数，t を時刻，τu，w，h，Δ を係数，g を非線形素子の内部状態と出力に関する関数としたときに、下記式６を満たすことを特徴とする請求項１８に記載の資源スケジュールシステム。
【数６】
2014041413.tif 000024
【請求項２０】
前記少なくとも２種類以上の割り当てるべき要素に、時間と場所が含まれることを特徴とする請求項１８または請求項１９に記載の資源スケジュールシステム。
【請求項２１】
前記資源スケジュール問題に関わるd 次元のコスト行列をb，ある資源の組み合わせを示す非線形素子の出力をx としたときに、複数の非線形素子の出力x の積xj1xj2・・・xjd を用いて算出されるxj1xj2・・・xjd(1- xj1xj2・・・xjd )b(j1,j2,・・・,jd) を全ての非線形素子の出力の組み合わせに対して足し合わせた項を、前記資源スケジューリング問題のエネルギー関数に含むことを特徴とする請求項１７または請求項１９記載の資源スケジュールシステム。
【請求項２２】
前記資源スケジュール問題に関わる拘束条件を示す項を(Constraint Conditions)，d次元のコスト行列をb，ある資源の組み合わせを示す非線形素子の出力をx，B，C を係数，非線形素子の数をN，最適化要件のコストを示す項をCsol(x) としたときに、前記資源スケジューリング問題のエネルギー関数が下記式７であることを特徴とする請求項１８または請求項１９記載の資源スケジュールシステム。
【数７】
2014041413.tif 000025
【請求項２３】
前記式７のエネルギー関数において、d次元のコスト行列をb，ある資源の組み合わせを示す非線形素子の出力をx，非線形素子の数をN としたときに最適化要件のコストを示す式が下記式８であることを特徴とする請求項２２記載の資源スケジュールシステム。
【数８】
2014041413.tif 000026
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算処理により最適化問題の解を求める方法に関係し、特に複数の非線形素子を結合したニューラルネットワークにおいて、高次結合を持つニューラルネットワークを用いたHC-ID モデルにより、組み合わせ最適化問題である資源スケジュール問題を解決できるシステムおよびその方法に関する。
【背景技術】
【０００２】
最適化問題とは、制約条件の中で、目的とする関数の値を最大化、あるいは最小化するような解を探す問題である。工場の生産計画、物流の配送計画、最短経路探索、作業員のスケジュール問題など、現実世界の様々な問題を最適化問題として解くことで、企業活動などをより効率的に行える。このため、より最適な解を得る方法が求められている。
【０００３】
最適化問題はいくつかのクラスに分けられるが、企業活動に有益な問題の多くは組み合わせ最適化問題に属する。一般に 組み合わせ最適化問題は、問題サイズの増加に応じてその組み合わせ量が爆発的に増加する。このため、高速なコンピュータを用いても短時間で解を得ることは難しい。そのため、短時間でよりよい答えを求めるヒューリスティックな手法が用いられる。
【０００４】
しかしながら、ヒューリスティックな手法では、最適解を得られることは保証できない。また、大規模な問題に対して精度の高い答えを得るには計算量が多くなってしまうため、短時間でより良い解が得られ、加えて最終的に最適解を得られるような手法が必要とされている。ニューラルネットワークを用いて組み合わせ最適化問題を解く試みは、さまざまな問題に対応できる汎用性と並列処理による高速性が見込めるため有望である。
【０００５】
組み合わせ最適化問題には、最適値ではない極小値状態に陥ってしまい抜け出せなくなる極小値問題があり、ニューラルネットワークを用いた手法でも例外ではない。この極小値問題を克服するために様々なニューラルネットワークのモデルが多くの研究者らによって考案されている。ニューラルネットワークに関連する技術の成果は、例えば特許文献１ないし３に記載されている。
【０００６】
我々は、ニューラルネットワークのモデルを用いて、最適値でネットワークが停止するシンプルな方法を既に提案している (非特許文献１参照)。  
我々の考案した高次シナプス結合を持つネットワーク中でニューロンが負性抵抗を持つような状態遷移を行うHC-ID ネットワーク(Higher orderConnections-InversefunctionDelayednetwork : The Inverse function Delayed network with the Higher order synaptic Connections) モデルは、極小値問題を回避しつつ、最適値を得られるモデルである。
開示した非特許文献１には、HC-IDモデルのダイナミクスを単純化した離散高次結合ネットワークを用いた組み合わせ最適化問題の解法が記載されている。この解法では、多次元のシナプス結合を導入することにより、多次元のコスト関数をもつ最適化問題の探索が可能になっている。
【０００７】
以下、その解法について図２を用いて説明する。大まかには次のような流れで問題を解く。まず、問題の解状態をニューロンの状態で表し、ニューラルネットワーク全体のエネルギー関数を最適化問題のコスト関数にマッピングする。そして、ニューロンの状態更新を行う。状態更新を繰り返すとニューラルネットワークはエネルギー関数が小さくなる方向に順次進み、最もエネルギーの低いところで静止する。この状態のニューロンの状態が最適化問題の解となる。
【０００８】
３次までの高次結合を持つ高次結合ネットワークにおけるニューロンの状態更新式は以下の式１で表される。  
【数１】
2014041413.tif 000003
i はニューロンを示す番号，ui はニューロンの内部状態，xi はニューロンの出力，hiはバイアス値を示す実数である。w(i,j,…) は、j, k,…番目のニューロンから、i 番目のニューロンへのシナプス結合の荷重値を示す実数である。τuは内部状態の時定数，τxは出力の時定数である。gはニューロンの内部状態と出力に関する関数であり、例えば式２のようにニューロンの出力に関する微分値がマイナスの値となる領域を持つものが用いられる。  
【数２】
2014041413.tif 000004
ここで、β，αは定数である。
【０００９】
非特許文献１では、式１および式２で表されるHC-ID モデルの基本式を単純化した離散高次結合ネットワークを提案している。３次までの高次結合を持つHC-ID モデルの離散高次結合ネットワークにおけるニューロンの状態更新式は以下の式３で表される。  
【数３】
2014041413.tif 000005
i はニューロンを示す番号，ui はニューロンの内部状態，xi はニューロンの出力，hiはバイアス値を示す実数である。w(i,j,…) は、j, k,…番目のニューロンから、i 番目のニューロンへのシナプス結合の荷重値を示す実数である。τuは内部状態の時定数，Δは時間刻みを表す実数である。αは正の値を持つ実数で、ヒステリシスの大きさをコントロールするパラメータである。
【００１０】
本明細書では、式１，式２で示される基本式とそれを単純化したもの(式３)、また、オイラー法，ルンゲ=クッタ法などで基本式の微分方程式を近似的に計算するものを含めてHC-ID モデルとする。
【００１１】
３次の離散高次結合ネットワークのエネルギー関数は以下式４で表される。  
【数４】
2014041413.tif 000006
【００１２】
式３に従ってニューロンの状態を更新していけば、式４で示される離散高次結合ネットワークのエネルギー関数が最も小さな値を示すところで、各ニューロンの状態更新が収束する。この性質を用いて、最適化問題を解くことができる。
【００１３】
以下、組み合わせ最適化問題の一つである巡回セールスマン問題(TSP)を例に説明を行う。TSP は都市間の距離が与えられたときに、各都市を１回だけ訪れる経路のうち、移動総距離が最短になるようなものを探す問題である。  
まず最適化問題からエネルギー関数を作成する(図２，Ａ−１)。エネルギー関数は、その問題の解状態のときに最も値が小さくなるように設計する。例えば、巡回セールスマン問題(TSP) のエネルギー関数は以下式５のように表される。  
【数５】
2014041413.tif 000007
【００１４】
各項の係数A，B，C は定数であり、正の実数である。N は都市の数を示す。TSP では都市数N に対して、N2 のニューロン行列x を用いる。xij=1 ならば、そのニューロンは発火した状態であり、i 番目に都市j を訪問することを示す。d(i，j，k，l) はコスト行列で、ニューロン(i, j) と(k, l) が発火した場合のコストを表す。TSP では。d(i，j，k，l) は都市間の距離を表す２次元の行列となる。
【００１５】
上記式のうち、第１〜３項はTSP の拘束条件を表している。係数がA の項はニューロンの各行、各列でただ1 つのニューロンが発火しているときに0 となり、係数がB の項は全てのニューロンが0 か1 の値を取るときに0 となる。係数がC の項は、ある状態の解のコストを２乗した値になっており、TSP の最適化要件を表している。次に、式４と式５から、式３で表されるニューロンの状態更新式に必要な荷重値w(i，j，k，l)、およびバイアス値hi を求める(図２，Ａ−２，Ａ−３)。それらは、ニューラルネットワーク内の全てのニューロンに対して、HC-ID モデルのエネルギー関数(式４) と最適化問題のエネルギー関数(TSP では式５) のx に対する偏微分値が一致するように計算を行うことにより、求めることができる。荷重値とバイアス値は、問題として与えられたコスト行列d(i，j，k，l) とパラメータA，B，C の関数となる。
【００１６】
次に、荷重値とバイアス値を設定したニューラルネットワークにおいて、状態が収束するまで、式３に従って各ニューロンの状態更新を行う(図２，Ａ−３〜Ａ−６)。収束状態で得られる解のコストは、パラメータB ／4C より小さくなることが分かっている。また、B ／4C が最適解よりも小さな値の場合では、ニューラルネットワークが収束しない。非特許文献１に開示したように、最初は大きなコスト値を基にパラメータB，C を設定し、ニューロンの状態更新を行い、得られた解を基に再度パラメータを設定し、状態更新を行うという試行を繰り返すことでだんだんと最適値に近い解を得ることができる。ニューラルネットワークが収束しなくなったところで、その直前の試行で得られた解が最適解か、あるいはもっとも最適値に近い解である。以上のようにHC-ID モデルを用いて、組み合わせ最適化問題であるTSP を解くことができる。
【先行技術文献】
【特許文献】
【００１７】
【特許文献１】特開平８−５０５７１号公報
【特許文献２】特開平９−３４８６３号公報
【特許文献３】特開２０１１−１０７８８５号公報
【非特許文献】
【００１８】
【非特許文献１】曽田尚宏，早川吉弘，佐藤茂雄，中島康治，"4次形式のエネルギー関数に基づく組み合わせ最適化問題解探査法‐より大規模な問題への適用を目指して-"，信学技報，vol．NLP2010-101，no．2010-11，pp．11-16，2010
【発明の概要】
【発明が解決しようとする課題】
【００１９】
上述したように、組み合わせ最適化問題は、さまざまな企業活動などにおいて存在し、より最適な解をより短時間に求める方法が必要とされている。  
このなかで、組み合わせ最適化問題の１つである資源スケジュール問題を解くことは非常に求められる成果である。  
発明者らは、ニューラルネットワーク用いた解探索方法の中で、HC-ID モデルを提唱して、極小値問題を回避しつつ、最適値でネットワークが停止するシンプルな方法を提供した。
【００２０】
しかしながら、HC-ID モデルに基づくニューラルネットワークを用いた解法で、TSP などよりも複雑な組み合わせ最適化問題である資源スケジュール問題を解くためには、ニューロンの状態に何を割り当て、資源スケジューリング問題のエネルギー関数をどのように作成すれば良いかが分かっていない。また、その試みも発明者らが知る限り、成されていなかった。
【００２１】
また、別の側面から事後的に課題を見出せば、HC-ID モデルのエネルギー関数を、他のエネルギー関数にマッピングするためには、両関数の次元が同一である必要があった。他方、求めたいエネルギー関数の次元を、HC-ID モデルのエネルギー関数の次元に合わせるように設計することを行うのでは、求める適正解を損なってしまう課題が生ずる。  
これらのことをより端的に説明すると、求めたい資源スケジューリング問題の拘束条件やコスト行列を、今までは既知のHC-ID モデルのエネルギー関数の次元数に合わせて設計する必要があった。
【００２２】
本発明の目的は、HC-IDネットワークを用いた資源スケジュール問題を解くための汎用性を有するエネルギー関数に関する知見を提供して、その関数を用いた解探査を行う資源スケジュールシステム、および資源スケジュール問題の解探査方法を提供することである。
【課題を解決するための手段】
【００２３】
本発明に係る資源スケジュール問題の解探査方法は、非線形素子による逆関数遅延ネットワークを用いた資源スケジュール問題の解探査方法であって、前記非線形素子を、求める資源スケジュール問題のエネルギー関数と同じ次元のエネルギー関数を持つHC-IDモデルに従って動作処理させると共に、前記非線形素子の出力を資源の割り当て方と対応させ、少なくとも２種類以上の資源の割り当て方を、前記非線形素子による逆関数遅延ネットワークを用いて解を探査処理することを特徴とする。
【００２４】
また、本発明に係る資源スケジュールシステムは、資源スケジュール算出部を含み、前記資源スケジュール算出部は、求める資源スケジュール問題のエネルギー関数と同じ次元のエネルギー関数を持つHC-ID モデルに従って動作する複数の非線形素子の出力を計算処理し、前記非線形素子の出力を資源の割り当て方に対応させ、少なくとも２種類以上の資源の割り当て方を、前記複数の非線形素子による逆関数遅延ネットワークを用いた解の探査処理を行うことを特徴として、複数の資源の好適なスケジュールを導出する。
【発明の効果】
【００２５】
本発明によれば、資源スケジュール問題からエネルギー関数を得ることができ、得られたシナプスの荷重値に従ってニューラルネットワークの状態更新を行い、その収束状態を解釈する試作を繰り返すことで、資源スケジュール問題の解を得る資源スケジュールシステム、および資源スケジュール問題の解探査方法を提供できる。
【図面の簡単な説明】
【００２６】
【図１】本発明の一実施形態の資源スケジュールシステムを示す構成図である。
【図２】本発明で用いるHC-ID モデルを用いた解探査方法を示すフローチャートである。
【図３】本発明の一実施例の説明に用いるDSP の問題データの例を示す説明図である。
【図４】本発明の一実施例の説明に用いるDSP の問題データの例を示す説明図である。
【図５】本発明の一実施例の説明に用いるDSP の最適解の例を示す説明図である。
【発明を実施するための形態】
【００２７】
発明者の知見により、資源スケジュール問題に対して有効な 汎用性を有する新たな資源スケジュール問題のエネルギー関数を提供する。  
提供した汎用的なエネルギー関数を基に設計した 求める資源スケジュール問題のエネルギー関数と、それと同じ次元のHC-IDモデルのエネルギー関数とを対応させることで得られる荷重値を用いてニューラルネットワークの状態更新を行い、最適解を探索する。
【００２８】
以下の説明では、本発明が解決することを目標とする組み合わせ最適化問題である資源スケジュール問題の例を以下のように定式化する。
・ R1,R2,・・・,Rn ：n種類のスケジュールする資源。各資源は、それぞれ|R|個の要素を持つ。
・ (j1,j2,・・・,jn)：R1,R2,・・・,Rn からそれぞれj1,j2,・・・,jn番目の要素を選択した状態。これをスケジュール枠と呼ぶ。
・b：問題に合わせて設計するコスト行列。コスト行列の次元数をd とする。
【００２９】
上記の情報に加えて、拘束条件と最適化要件が与えられるものとする。解が最低限満たすべき要件を拘束条件と呼び、拘束条件を満たした上でさらにできるだけ満たすべき要件を最適化要件と呼ぶ。例えば、拘束条件には同じ日程の同じ時間枠に同一の資源を利用することはできない，など が挙げられる。また、最適化要件には、あるスケジュールのコストの総和などがある。
【００３０】
本説明では、資源スケジュール問題に対して、サイズが|R1|×|R2|×・・・×|Rn|= Nのニューロン行列x を用意する。各ニューロンの出力について、以下のように定める。
【００３１】
x (j1,j2,・・・,jn) = 1 ならば、スケジュール枠(j1,j2,・・・,jn)を解に持つ。ここで、ある資源がスケジュール枠(j1,j2,・・・,jn)で利用できない場合は、x(j1,j2,・・・,jn)を0 に固定して、そのニューロンの出力を変化させない。これにより一部の拘束条件を実装することができる。また、コスト行列b は問題に応じて設定する必要がある。例えば、前述のTSPでは、スケジュール枠(都市，順番) が２つ決定した場合に、２つの都市の距離を基にそのコストが決定できるため、コスト行列は２次元となる。
【００３２】
以上のように問題の解にニューロンの状態を割り当て、資源スケジュール問題のエネルギー関数を以下の式６、式７のように定義する。  
【数６】
2014041413.tif 000008
【数７】
2014041413.tif 000009
ここでB, C は正のパラメータである。また、d はコスト行列の次数である。また、b(i1,i2,・・・,id) はコスト行列b の成分であり、(i1,i2,・・・,id)番目のニューロンが全て発火したときのコストを示している。但し、エネルギー関数の対称性の観点から、b はb(i1,i2,・・・,id) = b(i2,i1,・・・,id) = ・・・ = b(i1d,・・・,i2,i1) を満たすような回転対称である必要がある。
【００３３】
式６のうち、第一項のConstraint Condition と第二項は拘束条件を表す関数であり、全ての拘束条件を満たしたときに値が0 になるように設定する。第三項は、最適化要件であるコストの２乗となっている。これにより、ESCH(x) は、状態x が拘束条件を満たし、かつ最適解を示す場合に最小となる。本エネルギー関数ESCH(x) は、コスト行列の次数d に対して、2d次式になっている。このことから、コスト行列の次数d と必要な高次結合ネットワークの次数D にはD = 2d−1 の関係が成り立つ。
【００３４】
上記説明した資源スケジューリング問題のエネルギー関数は、非特許文献１に示すような既存のエネルギー関数(式５) と比べて、より、自由に拘束条件を設定でき、さらに４次を超えたエネルギー関数を使用できるようなコスト行列の次元数に対しての拡張性も備えており、より汎用的である。
【００３５】
前述したように、資源スケジュール問題のエネルギー関数と離散高次結合ネットワークのx に対する偏微分が一致するように荷重値w とバイアス値h を求め、D 次までの高次結合を有するHC-ID モデルの状態更新式に従って各ニューロンが状態更新を行うことで、資源スケジュール問題の解を取り出すことができる。
【００３６】
D次までの高次結合を有するHC-ID モデルのエネルギー関数を式８に示す。  
【数８】
2014041413.tif 000010
【００３７】
また、D次までの高次結合を有するHC-ID モデルの状態更新式を式９に、さらに式９を離散化したものを式１０に示す。  
【数９】
2014041413.tif 000011
【数１０】
2014041413.tif 000012
【００３８】
［構成の説明］  
次に、本発明の一実施形態について図面を参照して詳細に説明する。図１に本説明で用いる資源スケジュールシステムの全体像を示す。図１を参照すると、本発明の実施の形態の資源スケジュールシステム１は、資源スケジュール算出部として、問題入力部１０、制御部２０、荷重値算出部３０、非線形素子計算部４０、および出力部５０を含み構成される。
【００３９】
問題入力部１０は、求める資源スケジュール問題のパラメータやコスト関数を入力として受け付け、汎用化した資源スケジューリング問題のエネルギー関数に従い、資源スケジュール問題の解にマッピング処理して、演算に用いるエネルギー関数を作成し、その荷重値やバイアス値の計算式と、コストデータとを荷重値算出部３０に提供する。換言すれば、問題入力部１０は、求めたい資源スケジューリング問題に従って設計された資源スケジュール問題のエネルギー関数を、入力されたパラメータやコスト関数に従い、次元を調整できる汎用化した資源スケジューリング問題のエネルギー関数に割り当て、演算に用いるエネルギー関数式を作成処理する。なお、パラメータやコスト関数などは、エネルギー関数の設計者から受け付けてもよいし、他の関数設計装置（システム）から受け付けてもよい。
【００４０】
制御部２０は、荷重値w の計算に必要なパラメータを荷重値算出部３０に提供し、また非線形素子計算部４０に状態更新を行うよう指示を出力する。また、ニューラルネットワークの収束を判定して、解探索の終了を決定処理する。あるいは荷重値w の計算に必要なパラメータの再設定を荷重値計算部３０に対して行う。
【００４１】
荷重値算出部３０は、汎用化したHC-ID モデルのエネルギー関数の式構造と、問題入力部１０から提供された計算式とコストデータならびに制御部２０から提供されたパラメータ値をもとに、両式の x に対する偏微分が一致するように荷重値w を算出処理し、非線形素子計算部４０に提供する。
【００４２】
非線形素子計算部４０は、荷重値算出部３０が算出した荷重値w を使用して、汎用化したHC-ID モデルの状態更新式に従って状態更新を繰り返し行う。
【００４３】
出力部５０は、制御部２０からの指示を受け取り、非線形素子計算部４０の状態を解析して、最適化問題の解としてユーザに提示する。
【００４４】
[動作の説明]  
以下、資源スケジューリング問題の一つである学位論文審査会スケジューリング問題(DSP) を例として本発明の動作を説明する。本発明による解の導出によれば、大学院などで行われている学位論文の審査会スケジュールを、審査員の負担を軽減する観点から最適化できる。
【００４５】
例えば東北大学電気系の審査会の場合では、３月卒業の為の修士論文審査は毎年論文本数が１００本以上あり、それぞれの審査会を通常３人から４人の審査員によって審査している。審査員は各研究室の教授・准教授が行っており、その人数は７０人以上いる。審査は予備日を含めて３〜４日間程度かけて行われ、審査可能な時間枠が予め与えられている。また複数の審査会場が設定されており、同じ時間で複数の審査を行うことが可能になっている。さらに各審査員は審査会と並行して授業や出張、学会などの予定があるため、全ての時間枠において審査可能ではない。
【００４６】
このようにDSP におけるスケジューリングの条件は非常に複雑であり、また問題規模も比較的巨大である。しかしながら、現状の東北大学電気系の審査会では、スケジューリングは事務担当者の経験と勘により作成されている。そのため担当者が変わってしまうと、物理的・時間的に矛盾のないスケジュールを作成することでさえ非常に困難であり、また出来上がったスケジュールが審査員の負担を軽減するという意味で最適化されているかどうかも分からない。またこの問題は大学における審査会のスケジューリングのみに留まらず、一般的な勤務シフト作成や面接のスケジューリングなどにも応用できると考えられる。
【００４７】
まず、本動作の説明で解く問題の定式化を行う。審査会は複数日・複数の時間枠で実施され、また同時間枠に複数の会場が用意される。審査員は１つの論文発表に対して複数人割り当てられ、また審査員によっては複数の論文を審査する必要がある。審査員各々には授業などの理由により審査を入れることができない時間枠が存在する。さらに審査員各々の他の予定や嗜好により、審査をスケジューリングして欲しくない時間枠も存在する。これらの要件を定式化すると、以下に挙げる集合・行列によって問題が記述できる。  
・ D ・・・ スケジュール可能な日程の集合(Day)  
・ T ・・・ スケジュール可能な時間枠の集合(Time)  
・ R ・・・ スケジュール可能な部屋の集合(Room)  
・ H ・・・ 審査すべき学位論文の集合(HonorsThesis)  
・ J ・・・ 審査員の集合(Judge)  
・ Jh ・・・ 学位論文h を審査すべき審査員の集合  
・ cs (j,d,t) ・・・ 審査員j がd 日目に時間t で審査する場合のコスト  
・ cd (r,s) ・・・ 審査員1 人が部屋r, s 間を移動するのにかかるコスト
【００４８】
なお、審査員j がd 日目に時間t での審査を行えない場合、cs (j,d,t) = 無限大 とする。問題入力部１０が受けとるデータは図３，図４ のようになる。また日程，時間枠，部屋の組み合わせを審査枠と名付け、(d, t, r) で表す。このとき、DSP ではまず以下の拘束条件を満足することが求められる。  
・ 拘束条件1 ： 全ての論文は１回ずつ審査される。  
・ 拘束条件2 ： 同日同時刻の同じ部屋で複数の論文を審査することはできない。  
・ 拘束条件3 ： 同じ審査員が審査する予定の論文については、同日同時刻に審査することはできない。  
・ 拘束条件4 ： 審査員によっては審査できない時間枠があり、その枠には審査をスケジュールすることができない。
【００４９】
以上の条件を満足した上で、以下の要件をできるだけ満たすのが最適なスケジュールである。  
・ 最適化要件1 ： 各審査員について、審査会が予定される日数は少ない方がよい。  
・ 最適化要件2 ： 各審査員について、１日のうちで審査会がスケジュールされる時間枠は連続しているほうがよい。  
・ 最適化要件3 ： 各審査員の部屋間の移動距離は少ない方がよい。  
・ 最適化要件4 ： 各審査員ができればスケジュールして欲しくないと考えている時間枠は、できるだけ避けた方がよい。
【００５０】
これらの要件は、各審査員の審査にかかる負担をできるだけ軽減することを目的とした最適化要件である。またこれらの要件をできるだけ満足することで、より効率的に審査会を遂行することができる。
【００５１】
前述した通り、本発明によると「問題入力部１０」は、資源スケジュール問題に対して、サイズが |R1|×|R2|×・・・×|Rn|= N のニューロン行列x を用いる。
【００５２】
DSP に対しては、サイズ|D|×|T|×|H|×|R|= N のニューロン行列x を用意する。
【００５３】
図３，図４に示す問題では、サイズ2 × 3 × 2 × 7 = 84 のニューロン行列を用意する。
【００５４】
ニューロン行列の各ニューロンx(d,t,h,r) の出力について、以下の式１１のように定める。  
【数１１】
2014041413.tif 000013
ここで、ある審査員j が審査枠(d, t, r) で審査できない場合、すなわちcs (j,d,t) = 無限大 の場合、xd,t,h,r = 0 に固定する。これにより拘束条件4 を実装することができる。
【００５５】
次に、DSP のコスト行列b を定義する。DSP のコスト行列は式１２〜式１４ で示すような１つの２次元行列で表すことができる。  
【数１２】
2014041413.tif 000014
ここでi, j はそれぞれ、ニューロンのインデックスを示しており、i = (d1, t1, h1, r1)，j = (d2, t2, h2, r2) である。また、σ はKronecker のσ関数であり、以下を満たす。  
【数１３】
2014041413.tif 000015
【００５６】
また、bF , bS は、それぞれ１次，２次のコスト行列であり、以下の式で表される。  
【数１４】
2014041413.tif 000016
ここでP1 〜 P4 は正の定数であり、最適化要件それぞれの重み付けをコントロールする。bF は、ある論文を審査する審査枠のコストを示しており、最適化要件4 に対応している。bS の係数P1，P2，P3 の項は、それぞれ最適化要件1，2，3 に対応している。
【００５７】
式１２〜式１４で定義したコスト行列を式７に代入すると、DSP における解状態のコストCsol(DSP)(x) が以下の式１５のように得られる。  
【数１５】
2014041413.tif 000017
以上と式６から、DSP のエネルギー関数は以下の式１６のように定義される。  
【数１６】
2014041413.tif 000018
ここでA1〜A3 は正の定数である。式１６の第１〜３項はそれぞれ拘束条件1〜3 に対応しており、これらの条件を満足した際に0 となる。
【００５８】
このように、本発明の解決手法により、資源スケジューリング問題の１つであるDSP についてエネルギー関数を定義することができた。資源スケジュール部は、図２のフローチャートに従い、このエネルギー関数と離散高次結合ネットワークのエネルギー関数の全てのニューロンに対する偏微分が一致するように荷重値およびバイアス値を求める式を作成して解の探索を行う。
【００５９】
また、問題入力部１０は、図３，図４で示すようなコスト情報cs (j,d,t) ,cd (r,s) を荷重値算出部３０に提供する。制御部２０は、A，B，C のパラメータを決定し、非線形素子計算部４０に状態更新指示を出力する。非線形素子計算部４０は、制御部２０からの指示にもとづき、荷重値算出部３０から提供される荷重値ならびにバイアス値を用いて式３による状態更新を繰り返す。  
ニューラルネットワークが収束した場合、制御部２０は、得られた途中解を基に再度パラメータP1〜P3，A1〜A3，B，C を設定し、再び荷重値とバイアス値算出から状態更新を行う。  
一定回数の状態更新を得ても、ニューラルネットワークが収束しない場合、その直前の試行で得られた解が、最適解か或いはもっとも最適値に近い解であるとして、解の探索を終了する。出力部５０は、非線形素子計算部４０の各ニューロンの出力x の状態から、DSP の解を出力する。得られる解は図５のようになる。
【００６０】
今回の実施例では、４種類の資源(時間枠×2，場所，教授，論文) の割り当て問題を示したが、２種類以上の資源の割り当てスケジュール問題に関して、本願発明は使用できる。  
例えば、本説明例では「いつ」にスケジュールを設定するかの選択肢に、D(日程)，T(時間枠) というものを用いたが、これにM(月) を追加して、月に関する拘束条件や最適化要件を追加することもできる。その場合、ニューロン行列のサイズがさらに|Month|倍され、x の添え字の次元を増やす。対応して式１６中のΣ記号の数を増やせばよい。
【００６１】
以上説明したように、本発明により、資源スケジュール問題に対して、極小値問題を回避しつつ最適値を得られるようになる。これまでの解法として、ヒューリスティックな手法、確率的に極小値を回避する手法などが多く報告されているが、それら手法で得られた解が、最適値なのか或いは最適値に対してどの程度乖離しているのかが判らず、非効率な解でも満足せざるを得なかった。  
そこで、上記詳説したように、本発明に係るHC-ID モデルを使った解探査では、HC-IDモデルの新たなエネルギー関数と資源スケジュール問題個々のエネルギー関数のマッピングを行い、所要な荷重値等を算定して解探索を行う。
【００６２】
本発明により、問題ごとに作成する資源スケジューリング問題のエネルギー関数についても、公知であったHC-IDモデルのエネルギー関数の次元に束縛されることなく、任意の次数を取ることができるようになった。このため、既存技術に対して、拘束条件やコスト行列をより自由に設計（反映）でき、多くの事象の資源スケジューリング問題をより適切な最適値を導出できるようになった。
【００６３】
本発明により、さまざまな資源スケジュール問題に対して最適値が算出できるようになり、多くの産業で効率的な資源スケジュールが可能となる。
【００６４】
また、資源スケジュール問題の拘束条件やコスト行列の次元を既存の手順と比べて自由に設定でき、より汎用的に資源スケジュール問題を解決できる。
【００６５】
なお、資源スケジューリングシステムの各部は、ハードウェアとソフトウェアの組み合わせを用いて実現すればよい。ハードウェアとソフトウェアとを組み合わせた一つの形態では、メモリに資源スケジューリングプログラムが展開され、プログラムに基づいてＣＰＵ等のハードウェアを動作させることによって、各部を各種手段として実現する。また、このプログラムは、記憶媒体に固定的に記録されて頒布されても良い。当該記録媒体に記録されたプログラムは、有線、無線、又は記録媒体そのものを介して、メモリに読込まれ、ＣＰＵ等を動作させる。この記録媒体を例示すれば、オプティカルディスクや磁気ディスク、半導体メモリ装置、ハードディスクなどが挙げられる。
【００６６】
上記実施形態を別の表現で説明すれば、資源スケジューリング装置として動作させる情報処理装置を、ＲＡＭに展開された資源スケジューリングプログラムに基づき、本発明に係る問題入力手段、制御手段、荷重値算出手段、非線形素子計算手段、および出力手段としてＣＰＵを動作させることで実現することが可能である。また、本システムを１ないし複数のネットワークサーバで実現してもよい。その際の演算処理は、分散処理を用いてもよい。
【００６７】
また実施形態を図示して説明したが、そのブロック構成の分離併合、手順の入れ替えなどの変更は本発明の趣旨および説明される機能を満たせば自由であり、上記説明が本発明を限定するものではない。例えば、上記実施形態では非線形素子をソフトウェアで実装するものとして説明したが、非線形素子を含むネットワークを、問題入力部や荷重値算出部などと別のハードウェアで構成しても良い。
【００６８】
このように、本発明の具体的な構成は前述の実施の形態に限られるものではなく、この発明の要旨を逸脱しない範囲の変更があってもこの発明に含まれる。
【産業上の利用可能性】
【００６９】
多くの産業において、資源スケジュール問題が存在する。それらの問題に対して、本願発明は最適解を示すことが可能となり、最も効率の良い運営が様々な産業で可能となる。
【符号の説明】
【００７０】
１    資源スケジュールシステム
１０  問題入力部（問題入力手段）
２０  制御部（制御手段）
３０  荷重値算出部（荷重値算出手段）
４０  非線形素子計算部（非線形素子計算手段）
５０  出力部（出力手段）
【図１】
2014041413.tif 000027
【図２】
2014041413.tif 000028
【図３】
2014041413.tif 000029
【図４】
2014041413.tif 000030
【図５】
2014041413.tif 000031