(57)【要約】  一つ以上のニューロンを含む複数の層から構成されるニューラルネットワークを用いた演算処理を実行する計算機であって、複数のノード及び複数のノード間を接続する一つ以上のエッジから構成されるグラフデータ、及びニューラルネットワークに入力される一つ以上の値を格納するサンプルデータを格納する記憶部と、グラフデータを用いて、ニューラルネットワークを構築する構築部と、を備え、構築部は、グラフデータに含まれる前記複数のノードに基づいて、複数の層の各々の一つ以上のニューロンを生成し、グラフデータに含まれる一つ以上のエッジに基づいて、複数の層の各々に含まれる一つ以上のニューロン間の接続を生成することによってニューラルネットワークを構築する。
2016174725.tif 000002
【特許請求の範囲】
【請求項１】
プロセッサ、及び前記プロセッサに接続されるメモリを備え、一つ以上のニューロンを含む複数の層から構成されるニューラルネットワークを用いた演算処理を実行する計算機であって、
一つの層に含まれる一つのニューロンと、他の層に含まれる少なくとも一つのニューロンとの間には接続が構成され、
前記一つの層に含まれる一つのニューロンに入力された値は、重みとともに、前記接続によって接続される前記他の層に含まれる少なくとも一つのニューロンに出力され、
前記計算機は、
複数のノード及び前記複数のノード間を接続する一つ以上のエッジから構成されるグラフデータ、及びニューラルネットワークに入力される一つ以上の値を格納するサンプルデータを格納する記憶部と、
前記グラフデータを用いて、前記ニューラルネットワークを構築する構築部と、
前記サンプルデータを前記ニューラルネットワークに入力することによって前記ニューラルネットワーク内の複数の接続の前記重みを決定する学習処理を実行する学習処理部と、
を備え、
前記構築部は、
前記グラフデータに含まれる前記複数のノードに基づいて、前記複数の層の各々の一つ以上のニューロンを生成し、
前記グラフデータに含まれる前記一つ以上のエッジに基づいて、前記複数の層の各々に含まれる前記一つ以上のニューロン間の前記接続を生成することによって前記ニューラルネットワークを構築し、
前記構築されたニューラルネットワークの情報を前記記憶部に格納することを特徴とする計算機。
【請求項２】
請求項１に記載の計算機であって、
前記複数の層は、複数のニューロンを含む入力層、前記複数のニューロンを含む一つ以上の中間層、及び前記一つ以上のニューロンを含む出力層を含み、
前記構築部は、
前記出力層の設定に関する第１の設定情報を含む定義情報を受け付け、
前記第１の設定情報に基づいて、前記出力層を生成し、
前記グラフデータに含まれる複数のノードの各々に対応するニューロンを含む前記入力層を生成し、
前記グラフデータに含まれる複数のノードの各々に対応するニューロンを含むマップグラフを一つ以上生成することによって中間層を生成することを特徴とする計算機。
【請求項３】
請求項２に記載の計算機であって、
前記定義情報は、一つの中間層に含まれる前記マップグラフの数に関する第２の設定情報を含み、
前記構築部は、
前記入力層、前記中間層、及び前記出力層を含む前記ニューラルネットワークを構成する場合に、前記第２の設定情報に基づいて前記マップグラフを一つ以上生成することによって前記中間層を生成し、
前記入力層に含まれる一つのニューロンを選択し、
前記グラフデータを参照して、前記選択されたニューロンに対応するノードとエッジを介して接続されるノードを特定し、
前記中間層に含まれ、かつ、前記特定されたノードに対応するニューロンと、前記選択されたニューロンとの間に前記接続を生成し、
前記一つ以上のマップグラフに含まれる複数のニューロンの各々と、前記出力層に含まれる全てのニューロンとの間に前記接続を生成することを特徴とする計算機。
【請求項４】
請求項３に記載の計算機であって、
前記グラフデータは、前記ノード間の相関関係に基づいて決定されたエッジのラベルを含み、
前記構築部は、一つのラベルと、当該ラベルが付与されたエッジに基づいて生成された前記複数の接続とを対応付けた重みテーブルを生成し、前記生成された重みテーブルを前記記憶部に格納し、
前記学習処理部は、
前記サンプルデータと前記重みテーブルを用いた誤差逆伝播処理を実行することによって、同一の前記ラベルが付与された前記接続の重みを決定し、
前記ラベルと前記接続の重みとを対応付けた情報を前記記憶部に格納することを特徴とする計算機。
【請求項５】
請求項３に記載の計算機であって、
前記計算機は、任意のデータの識別に用いる評価関数及び前記学習処理部が出力した学習済のニューラルネットワークを用いて任意のデータに対する識別処理を実行する識別処理部を備え、
前記ニューラルネットワークは、前記評価関数に対応するニューラルネットワークであり、
前記識別処理部は、
対象のデータの入力を受け付けた場合、前記ニューラルネットワークに前記対象のデータを入力することによって第１の演算処理を実行し、
前記第１の演算処理の出力値に基づいて、前記評価関数を用いた第２の演算処理を実行するか否かを判定し、
前記第２の演算処理を実行すると判定された場合、前記対象のデータを前記評価関数に入力することによって前記第２の演算処理を実行し、
前記第２の演算処理の出力値に基づいて、前記対象のデータの識別を行うことを特徴とする計算機。
【請求項６】
請求項５に記載の計算機であって、
前記対象のデータを解析し、前記解析の結果に基づいて、前記複数のノードを生成し、前記複数のノード間の相関関係に基づいて一つ以上のエッジを生成することによって前記グラフデータを生成し、前記記憶部に格納するグラフデータ生成部を備えることを特徴とする計算機。
【請求項７】
請求項６に記載の計算機であって、
前記複数のノード間の相関関係は、前記複数のノードの各々の配置、及び前記ノード間の距離であることを特徴とする計算機。
【請求項８】
プロセッサ、及び前記プロセッサに接続されるメモリを備える計算機が実行するニューラルネットワークを用いた演算方法であって、
前記ニューラルネットワークは、一つ以上のニューロンを含む複数の層から構成され、
一つの層に含まれる一つのニューロンと、他の層に含まれる少なくとも一つのニューロンとの間には接続が構成され、
前記一つの層に含まれる一つのニューロンに入力された値は、重みとともに、前記接続によって接続される前記他の層に含まれる少なくとも一つのニューロンに出力され、
前記メモリは、複数のノード及び前記複数のノード間を接続する一つ以上のエッジから構成されるグラフデータ、及びニューラルネットワークに入力される一つ以上の値を格納するサンプルデータを格納し、
前記ニューラルネットワークを用いた演算方法は、
前プロセッサが、前記グラフデータに含まれる前記複数のノードに基づいて、前記複数の層の各々の一つ以上のニューロンを生成する第１のステップと、
前記プロセッサが、前記グラフデータに含まれる前記一つ以上のエッジに基づいて、前記複数の層の各々に含まれる前記一つ以上のニューロン間の前記接続を生成することによって前記ニューラルネットワークを構築し、前記構築されたニューラルネットワークの情報を前記メモリに格納する第２のステップと、
前記プロセッサが、前記サンプルデータを前記ニューラルネットワークに入力することによって前記ニューラルネットワーク内の複数の接続の前記重みを決定する学習処理を実行し、前記学習処理の結果を前記メモリに格納する第３のステップと、
を含むことを特徴とするニューラルネットワークを用いた演算方法。
【請求項９】
請求項８に記載のニューラルネットワークを用いた演算方法であって、
前記複数の層は、複数のニューロンを含む入力層、前記複数のニューロンを含む一つ以上の中間層、及び前記一つ以上のニューロンを含む出力層を含み、
前記第１のステップは、
前記プロセッサが、前記出力層の設定に関する第１の設定情報を含む定義情報を受け付けるステップと、
前記プロセッサが、前記第１の設定情報に基づいて、前記出力層を生成するステップと、
前記プロセッサが、前記グラフデータに含まれる複数のノードの各々に対応するニューロンを含む前記入力層を生成するステップと、
前記プロセッサが、前記グラフデータに含まれる複数のノードの各々に対応するニューロンを含むマップグラフを一つ以上生成することによって中間層を生成するステップと、を含むことを特徴とするニューラルネットワークを用いた演算方法。
【請求項１０】
請求項９に記載のニューラルネットワークを用いた演算方法であって、
前記定義情報は、一つの中間層に含まれる前記マップグラフの数に関する第２の設定情報を含み、
前記第１のステップは、前記プロセッサが、前記入力層、前記中間層、及び前記出力層を含む前記ニューラルネットワークを構成する場合に、前記第２の設定情報に基づいて前記マップグラフを一つ以上生成することによって前記中間層を生成するステップを含み、
前記第２のステップは、
前記プロセッサが、前記入力層に含まれる一つのニューロンを選択するステップと、
前記プロセッサが、前記グラフデータを参照して、前記選択されたニューロンに対応するノードとエッジを介して接続されるノードを特定するステップと、
前記プロセッサが、前記中間層に含まれ、かつ、前記特定されたノードに対応するニューロンと、前記選択されたニューロンとの間に前記接続を生成するステップと、
前記プロセッサが、前記一つ以上のマップグラフに含まれる複数のニューロンの各々と、前記出力層に含まれる全てのニューロンとの間に前記接続を生成するステップと、を含むことを特徴とするニューラルネットワークを用いた演算方法。
【請求項１１】
請求項１０に記載のニューラルネットワークを用いた演算方法であって、
前記グラフデータは、前記ノード間の相関関係に基づいて決定されたエッジのラベルを含み、
前記第２のステップは、前記プロセッサが、一つのラベルと、当該ラベルが付与されたエッジに基づいて生成された前記複数の接続とを対応付けた重みテーブルを生成し、前記生成された重みテーブルを前記メモリに格納するステップを含み、
前記第３のステップは、
前記プロセッサが、前記サンプルデータと前記重みテーブルを用いた誤差逆伝播処理を実行することによって、同一の前記ラベルが付与された前記接続の重みを決定するステップと、
前記プロセッサが、前記ラベルと前記接続の重みとを対応付けた情報を前記メモリに格納するステップと、を含むことを特徴とするニューラルネットワークを用いた演算方法。
【請求項１２】
請求項１０に記載のニューラルネットワークを用いた演算方法であって、
前記ニューラルネットワークは、任意のデータの識別に用いる評価関数に対応するニューラルネットワークであり、
前記ニューラルネットワークを用いた演算方法は、
前記プロセッサが、対象のデータの入力を受け付けた場合、前記学習処理が実行されたニューラルネットワークに前記対象のデータを入力することによって第１の演算処理を実行するステップと、
前記プロセッサが、前記第１の演算処理の出力値に基づいて、前記評価関数を用いた第２の演算処理を実行するか否かを判定するステップと、
前記プロセッサが、前記第２の演算処理を実行すると判定された場合、前記対象のデータを前記評価関数に入力することによって前記第２の演算処理を実行するステップと、
前記プロセッサが、前記第２の演算処理の出力値に基づいて、前記対象のデータの識別を行うステップと、を含むことを特徴とするニューラルネットワークを用いた演算方法。
【請求項１３】
請求項１２に記載のニューラルネットワークを用いた演算方法であって、
前記プロセッサが、前記対象のデータを解析するステップと、
前記プロセッサが、前記解析の結果に基づいて、前記複数のノードを生成し、前記複数のノード間の相関関係に基づいて一つ以上のエッジを生成することによって前記グラフデータを生成し、前記メモリに格納するステップと、を含むことを特徴とするニューラルネットワークを用いた演算方法。
【請求項１４】
請求項１３に記載のニューラルネットワークを用いた演算方法であって、
前記複数のノード間の相関関係は、前記複数のノードの各々の配置、及び前記ノード間の距離であることを特徴とするニューラルネットワークを用いた演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ニューラルネットワークを用いた最適化問題の処理を実行する計算機及び演算方法に関する。
【背景技術】
【０００２】
社会インフラ及び都市等を効率的に設計、運用するため、実社会及びサイバー空間のデータを処理し、社会インフラ等の状態を解析し、若しくは予測し、又は、社会インフラ等を制御し、若しくは誘導する技術が注目されている。【０００３】
処理されるデータは、温度及び湿度等の環境のセンシングデータ、自動車等の機械のログデータ、並びにメール及びＳＮＳ等の人間又は組織のログデータから構成される。データを用いた処理は、社会を構成する要素（人、モノ、情報等）の最適な状態を探索する最適化処理である。【０００４】
最適化処理は、予め定義された評価関数の値（評価値）が最小、又は最大となる入力データの組み合わせを求める問題である。一般に、全ての入力データの組み合わせの中から、評価値が最小又は最大となる入力データの組み合わせを探索するためには、莫大な計算量を必要とする。この計算量は、探索数と、評価関数の計算量とを乗算することによって得られる。そこで、計算量を削減するために、近似解を求めて探索数を削減する計算方法が広く利用される。【０００５】
しかし、評価関数が非常に複雑な問題の場合、前述方法では、十分な処理の高速化が得られない。【０００６】
例えば、単位時間のピッキング数を最大とする倉庫レイアウトの問題の場合、評価関数は総棚数及び全ての棚が通路で到達できるか、渋滞の度合い等の合成関数となる。そのため、この評価関数の計算に莫大な計算量を必要とする。【０００７】
前述した課題に対して、ニューラルネットワーク（ＮＮ）を用いて計算方法を学習し、効率化を図ることによって処理の高速化する方法がある。特許文献１では、ニューラルネットワークを用いて、画像のフィルタ演算やＦＦＴを学習し、近似解であるが低電力で求める方法を提案している。また、特許文献２参照では、コンボリューショナルニューラルネットワーク（ＣＮＮ）による画像認識処理の高速化を行っている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】米国特許第８６５５８１５号明細書
【特許文献２】米国特許出願公開第２０１４／０１８０９８９号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、前述した２つの従来技術において用いられるニューラルネットワークでは、複雑な評価関数を学習することが困難であるという課題がある。複雑な評価関数では、経路問題等、入力データの要素間に複雑な相互関係を持つ問題を扱っているが、特許文献１では入力データがベクトル、特許文献２では入力データが画像（マトリクス）であるため、複雑な相互関係をニューラルネットワークの構造に反映することができない。【００１０】
特許文献１に記載の技術では、入力データがベクトルの場合、ニューラルネットワークの構造はベクトルの各要素とニューラルネットワークの第１層のシナプスは完全二部グラフで接続される。すなわち、入力データのある要素は、ニューラルネットワークの第１層の全てのシナプスと接続され、入力データの要素間の関係性はニューラルネットワークの内部構造に反映されない。これは、ニューラルネットワークの学習処理における収束性の大きな劣化の要因となる。【００１１】
また、特許文献２に記載の技術では、入力データがマトリクスの場合、入力に対し規定のウィンドウ内の各要素とニューラルネットワークの第１層のシナプス（特徴マップ）が接続される。前記ウィンドウの大きさは、画像のフィルタ演算のように３×３、５×５等のサイズであって、入力データの要素間の相互関係が均一な場合（例えば、画像は格子状になり、いずれの画素も上下左右の画素と相互関係を持つ）に適用ができる。しかし、入力データの要素間の相互関係が不均一な場合には、適用できない。例えば、ＳＮＳ等のスケールフリーグラフで、ほとんどの要素は少数の要素と相関関係を持つが、限られた要素（ハブと呼ばれる）は多数の要素と相関関係を持つ。【００１２】
したがって、従来技術では、前述の社会インフラ等の評価関数が複雑な最適化問題の処理の高速化を実現できない。【００１３】
本発明は、評価関数が複雑な最適化問題の処理の高速化を可能とする技術を提供することにある。
【課題を解決するための手段】
【００１４】
本願において開示される発明の代表的な一例を示せば以下の通りである。すなわち、プロセッサ、及び前記プロセッサに接続されるメモリを備え、一つ以上のニューロンを含む複数の層から構成されるニューラルネットワークを用いた演算処理を実行する計算機であって、一つの層に含まれる一つのニューロンと、他の層に含まれる少なくとも一つのニューロンとの間には接続が構成され、前記一つの層に含まれる一つのニューロンに入力された値は、重みとともに、前記接続によって接続される前記他の層に含まれる少なくとも一つのニューロンに出力され、前記計算機は、複数のノード及び前記複数のノード間を接続する一つ以上のエッジから構成されるグラフデータ、及びニューラルネットワークに入力される一つ以上の値を格納するサンプルデータを格納する記憶部と、前記グラフデータを用いて、前記ニューラルネットワークを構築する構築部と、前記サンプルデータを前記ニューラルネットワークに入力することによって前記ニューラルネットワーク内の複数の接続の前記重みを決定する学習処理を実行する学習処理部と、を備え、前記構築部は、前記グラフデータに含まれる前記複数のノードに基づいて、前記複数の層の各々の一つ以上のニューロンを生成し、前記グラフデータに含まれる前記一つ以上のエッジに基づいて、前記複数の層の各々に含まれる前記一つ以上のニューロン間の前記接続を生成することによって前記ニューラルネットワークを構築し、前記構築されたニューラルネットワークの情報を前記記憶部に格納することを特徴とする。
【発明の効果】
【００１５】
本発明によれば、評価関数が複雑な最適化問題において、複雑な相関関係を反映したニューラルネットワークを構築できる。これによって、最適化問題の処理の高速な演算が可能となる。前述した以外の課題、構成及び効果は、以下の実施例の説明によって明らかにされる。
【図面の簡単な説明】
【００１６】
【図１】実施例１の計算機システムの構成の一例を示す説明図である。
【図２】実施例１のニューラルネットワークの一例を示す説明図である。
【図３】実施例１のグラフデータの一例を示す説明図である。
【図４】実施例１のグラフデータの一例を示す説明図である。
【図５】実施例１のグラフデータの別例を示す説明図である。
【図６】実施例１の重みテーブルの一例を示す説明図である。
【図７】実施例１の計算機が実行する学習処理を説明するフローチャートである。
【図８】実施例１の計算機が実行するニューラルネットワークの構築処理を説明するフローチャートである。
【図９Ａ】実施例１の特徴マップグラフの構築の流れを示す説明図である。
【図９Ｂ】実施例１の特徴マップグラフの構築の流れを示す説明図である。
【図１０】実施例１の計算機によって構築されたニューラルネットワークの一例を示す説明図である。
【図１１】実施例１の計算機が実行する識別処理を説明するフローチャートである。
【図１２】実施例２の入力データｘからグラフデータへの変換を示す説明図である。
【図１３】実施例２の計算機が実行する最適化問題の処理を説明するフローチャートである。
【図１４】実施例３の棚配置レイアウト候補のセル表現及びグラフ化の一例を示す説明図である。
【図１５】実施例３の棚配置レイアウト候補のグラフにおけるエッジのラベルの割り当て方法の一例を示す説明図である。
【図１６】実施例３の棚配置レイアウト候補のグラフデータの一例を示す説明図である。
【図１７】実施例３の計算機が実行する最適レイアウト問題の処理を説明するフローチャートである。
【図１８】従来の計算機が実行する近似アルゴリズムに基づく最適化問題の処理を説明するフローチャートである。
【図１９】従来の計算機が実行する最適レイアウト問題の処理を説明するフローチャートである。
【発明を実施するための形態】
【実施例１】
【００１７】
実施例１では、グラフデータを入力としたニューラルネットワークの構築方法について説明する。【００１８】
図１は、実施例１の計算機システムの構成の一例を示す説明図である。【００１９】
図１に示すように、実施例１の計算機システム１００は、複数の計算機１０１、及びストレージシステム１０２から構成され、複数の計算機１０１とストレージシステム１０２とは、ネットワーク１０３を介して接続される。【００２０】
本実施例の計算機システム１００は、３つの計算機１０１−１、１０１−２、１０１−３を含む。なお、計算機１０１の数は、３つより小さくてもいし、また、３つより大きくてもよい。【００２１】
ネットワーク１０３は、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、及びＳＡＮ（Ｓｔｏｒａｇｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）等が考えられる。なお、本実施例はネットワーク１０３の種別に限定されない。また、複数の計算機１０１の各々を接続するネットワーク、及び複数の計算機１０１の各々とストレージシステム１０２とを接続するネットワークは、異なるネットワークであってもよい。【００２２】
計算機１０１は、ニューラルネットワークの構築処理、及びニューラルネットワークを用いた演算処理等を実行する。計算機１０１は、プロセッサ１１０、メモリ１１１、通信インタフェース１１２を備え、各構成はバス１１４を介して互いに接続される。【００２３】
プロセッサ１１０は、演算処理を実行する１つ以上のＣＰＵ１１５を含む。ＣＰＵ１１５は、メモリ１１１に格納されるプログラムを実行することによって、計算機１０１が有する機能を実現する。また、計算機１０１上で実行される処理は１つ以上のＣＰＵ１１５によって実行される。なお、１つのＣＰＵ１１５が複数の処理を実行してもよい。なお、ＣＰＵ１１５は、ＦＰＧＡ及びＧＰＵ等の演算器であってもよい。【００２４】
メモリ１１１は、ＣＰＵ１１５（プロセッサ１１０）が実行するプログラム及び当該プログラムによって使用される情報を格納する。また、メモリ１１１は、ＣＰＵ１１５が実行する１つの処理に対して割り当てられるメモリ空間を含む。なお、当該メモリ空間は、複数のメモリ１１１のメモリ領域上に確保されてもよいし、また、１つのメモリ１１１のメモリ領域上に確保されてもよい。また、メモリ１１１は、複数の処理のメモリ空間を含んでもよい。メモリ１１１に格納されるプログラム及び情報については後述する。【００２５】
通信インタフェース１１２は、ネットワーク１０３を介して外部装置と通信する。本実施例では、プロセッサ１１０は、通信インタフェース１１２を介して、他の計算機１０１又はストレージシステム１０２にアクセスする。【００２６】
ストレージシステム１０２は、計算機１０１が使用する各種データを格納する。ストレージシステム１０２は、プロセッサ１３０、メモリ１３１、通信インタフェース１３２、ディスクインタフェース１３３、及び複数のＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）１３４を備え、各構成はバス１３５を介して互いに接続される。【００２７】
プロセッサ１３０、メモリ１３１、及び通信インタフェース１３２は、プロセッサ１１０、メモリ１１１、及び通信インタフェース１１２と同一のものである。ディスクインタフェース１３３は、複数のＨＤＤ１３４と接続するためのインタフェースである。ＨＤＤ１３４は、各種データを格納する記憶装置である。【００２８】
ここで、計算機１０１のメモリ１１１に格納されるプログラム及び情報について説明する。【００２９】
メモリ１１１は、データ処理部１２０を実現するプログラムを格納する。データ処理部１２０を実行するＣＰＵ１１５は、学習処理、及び識別処理を実行する。学習処理では、ＣＰＵ１１５が、ニューラルネットワークを構築し、また、構築されたニューラルネットワーク内のニューロン間の接続（エッジ）の重みを決定する。識別処理では、ＣＰＵ１１５が、識別対象であるデータを、構築されたニューラルネットワークに入力することによって所定の識別を行う。【００３０】
なお、データ処理部１２０は、複数のプログラムモジュールから構成されてもよい。例えば、データ処理部１２０は、ニューラルネットワークを構築する構築部、学習処理を実行する学習処理部、及び識別処理を実行する識別処理部を含んでもよい。また、それぞれのプログラムモジュールを別々の計算機１０１が備える構成であってもよい。【００３１】
ここで、ニューラルネットワークについて説明する。図２は、実施例１のニューラルネットワークの一例を示す説明図である。【００３２】
図２に示すニューラルネットワーク２００は、入力層２０１、中間層２０２、及び出力層２０３の３層から構成される。各層は１つ以上のニューロン２１１から構成される。また、各層のニューロン２１１は、他の層の少なくとも１つのニューロン２１１と接続する。具体的には、入力層２０１のニューロン２１１は、中間層２０２の少なくとも１つのニューロン２１１と接続し、また、中間層２０２のニューロン２１１は、出力層２０３の少なくとも１つのニューロン２１１と接続する。以下の説明では、ニューロン２１１間の接続するエッジを接続２１２とも記載する。接続２１２はニューロン２１１間のデータの出力を表す。各ニューロン２１１に入力された値は、任意の重みとともに、接続２１２によって接続される他の層のニューロン２１１に出力される。重みは、ニューロン２１１間の接続の強さを表し、後述する学習処理によって決定される。以上が、ニューラルネットワークの説明である。図１の説明に戻る。【００３３】
メモリ１１１は、グラフデータ１２１、サンプルデータ１２２、及び重みテーブル１２３を格納する。【００３４】
グラフデータ１２１は、任意の要素に対応するノード、及びノード間を接続するエッジから構成されるグラフの構造を定義するデータである。グラフデータ１２１の詳細は図３を用いて後述する。サンプルデータ１２２は、ニューラルネットワークを用いた学習処理において用いられるデータである。重みテーブル１２３は、ニューラルネットワークの学習処理の処理結果である重みを管理する情報である。重みテーブル１２３の詳細は図６を用いて後述する。【００３５】
なお、グラフデータ１２１及びサンプルデータ１２２は、ストレージシステム１０２に格納される情報である。ＣＰＵ１１５が、ストレージシステム１０２からグラフデータ１２１及びサンプルデータ１２２を取得し、取得されたグラフデータ１２１及びサンプルデータ１２２をメモリ１１１にロードする。【００３６】
図３は、実施例１のグラフデータ１２１の一例を示す説明図である。【００３７】
グラフデータ１２１は、エッジＩＤ３０１、ノードＩＤ３０２、ラベル３０３、及びエッジ属性３０４を含む。【００３８】
エッジＩＤ３０１は、エッジの識別情報である。ノードＩＤ３０２は、エッジＩＤ３０１に対応するエッジを介して接続されるノードの識別情報である。なお、エッジに向きは後述するエッジ属性３０４にて管理される。ラベル３０３は、長さ、及び向き等に基づいてエッジを分類することによって付与されるエッジのラベルである。【００３９】
エッジ属性３０４は、エッジの属性情報である。本実施例では、エッジの長さ、エッジの方向等がエッジの属性情報として管理される。【００４０】
ここで、図３及び図４を用いてエッジのラベルについて説明する。図４は、実施例１のグラフの一例を示す説明図である。【００４１】
図４に示すグラフは、図３に示すグラフデータ１２１に対応するグラフである。図４に示すグラフは、３つのノードＩ０、Ｉ１、Ｉ２を含み、また、５つのエッジＥ０、Ｅ１、Ｅ２、Ｅ３、Ｅ４を含む。【００４２】
図３及び図４に示すように、エッジＥ０及びエッジＥ２は、エッジの長さが「１」であり、向きも同一の「南向き」である。エッジＥ１及びエッジＥ３は、エッジの長さが「１」であり、かつ、向きが「北向き」である。また、エッジ４は、エッジの長さが「２」であり、向きが「北向き」である。したがって、エッジＥ０及びエッジＥ２には、同じラベル「０」が付与され、また、エッジＥ１及びエッジＥ３についても同じラベル「１」が付与される。一方、エッジ４には、ラベル「２」が付与される。【００４３】
付与されるラベルの種類は、エッジの長さ及び向きのセットの組み合わせ以上の数が用意される。ここでは、前述の組み合わせの種類は、（長さ１、南向き）、（長さ１、北向き）、（長さ２、北向き）の３種類であるため、ラベルも０、１、２の３種類が用意され、組み合わせとラベルとが対応付けられる。【００４４】
なお、グラフデータ１２１は、ノードの構造を管理するデータと、エッジの構造を管理するデータとに分けて管理されてもよい。【００４５】
図５は、実施例１のグラフデータ１２１の別例を示す説明図である。【００４６】
図５に示すグラフデータ１２１は、エッジの構造情報５００及びノードの構造情報５１０を含む。エッジの構造情報５００のエッジＩＤ５０１、ノードＩＤ５０２、ラベル５０３、及びエッジ属性５０４は、エッジＩＤ３０１、ノードＩＤ３０２、ラベル３０３、及びエッジ属性３０４と同一のものである。【００４７】
ノードの構造情報５１０は、ノードＩＤ５１１、エッジＩＤ（流出）５１２、エッジＩＤ（流入）５１３、及びノード属性５１４を含む。ノードＩＤ５１１は、ノードＩＤ３０２と同一のものである。【００４８】
エッジＩＤ（流出）５１２は、ノードＩＤ５１１に対応するノードから流出するエッジの識別情報である。すなわち、ノードは、エッジＩＤ（流出）５１２に対応するエッジの始点となるノードである。エッジＩＤ（流入）５１３は、ノードＩＤ５１１に対応するノードに流入するエッジの識別情報である。すなわち、ノードは、エッジＩＤ（流入）５１３に対応するエッジの終点となるノードである。【００４９】
ノード属性５１４は、ノードの属性情報である。本実施例では、ノードの種類等がエッジの属性情報として管理される。例えば、倉庫のレイアウトを表すグラフデータの場合、ノードの種類は棚又は通路等を示す。【００５０】
図６は、実施例１の重みテーブル１２３の一例を示す説明図である。【００５１】
重みテーブル１２３は、ラベル６０１、重みラベル６０２、及びエッジ情報６０３を含む。ラベル６０１は、ラベル３０３と同一のものである。【００５２】
重みラベル６０２は、ニューラルネットワーク内のエッジの重みを分類することによって付与されるラベルである。重みラベル６０２は、ラベル６０１に対応するものである。すなわち、ラベル６０１はグラフデータ内のエッジのラベルであり、重みラベル６０２はニューラルネットワーク内のエッジのラベルである。【００５３】
エッジ情報６０３は、同一の重みラベル６０２が付与されるニューラルネットワーク内の接続の識別情報である。本実施例では、接続をマップエッジとも記載する。【００５４】
グラフデータ１２１においてノード間の相関関係（トポロジ）が同一、すなわち、長さ及び向き等が同一であるエッジから構成されたマップエッジは、学習処理における重みの修正時に、同様の修正が行われる。そのため、本実施例では、計算機１０１がノード間のトポロジを抽象化して管理する重みテーブル１２３を保持することによって、学習処理及び識別処理の高速化を実現する。【００５５】
ここで、ノード間のトポロジの抽象化について具体的に説明する。入力データ（グラフデータ）の要素（ノード）間の相関関係が同一の場合、ニューラルネットワーク内のエッジの重みも同一にすることによって、入力データの全ての要素間の相関関係、すなわち、トポロジを抽象化する。【００５６】
例えば、グラフデータとして、ノードが交差点を表し、エッジが交差点間のつながりを表す道路網を示すデータを考える。グラフデータの要素間の相関関係は、第１の交差点の北向きの距離１に第２の交差点があり、第１の交差点及び第２の交差点が第１のエッジで接続され、第３の交差点の北向きに距離１に第４の交差点があり、第３の交差点及び第４の交差点が第２のエッジで接続されているものとする。【００５７】
前述の４つの交差点は、それぞれ異なる地点の交差点を表すものであっても同様のトポロジを持つため、第１のエッジ及び第２のエッジは、ニューラルネットワークにおいて同様に扱うべきである。したがって、第１のエッジ及び第２のエッジには、エッジの属性（長さ１、北向き）に基づいて定められた同一のラベルが付与される。これによって、同一のラベルを持つエッジはニューラルネットワークの重みラベルも共有する。【００５８】
これによって、異なるノード間を接続するエッジであっても、ノード間のトポロジが同一である場合、それぞれのエッジを区別することなく扱うことができる。すなわち、ノード間のトポロジが抽象化される。【００５９】
次に、計算機１０１が実行する処理について説明する。まず、図７を用いて学習処理について説明する。図７は、実施例１の計算機１０１が実行する学習処理を説明するフローチャートである。【００６０】
計算機１０１は、処理開始の指示を受け付けた場合に以下で説明する処理を開始する。【００６１】
まず、ＣＰＵ１１５は、ストレージシステム１０２からグラフデータ１２１を取得し、メモリ１１１に格納する（ステップＳ７０１）。ＣＰＵ１１５は、取得されたグラフデータ１２１を用いてニューラルネットワークの構築処理を実行する（ステップＳ７０２）。ニューラルネットワークの構築処理の詳細は図８を用いて後述する。【００６２】
次に、ＣＰＵ１１５は、ストレージシステム１０２からサンプルデータ１２２を取得し、メモリ１１１に格納する（ステップＳ７０３）。【００６３】
次に、ＣＰＵ１１５は、誤差逆伝播処理のループ処理を開始する（ステップＳ７０４）。本ループ処理では、ＣＰＵ１１５は、ステップＳ７０４からステップＳ７０８の処理を繰り返し実行する。本ループ処理内で実行される誤差逆伝播処理によって算出される誤差が予め設定された閾値以下になった場合、又は、予め決められた回数だけ誤差逆伝播処理が実行された場合に、ループ処理が終了する。また、ＣＰＵ１１５は、サンプルデータのループ処理を開始する（ステップＳ７０５）。サンプルデータのループ処理では、ステップＳ７０３において取得された複数のサンプルデータに対し、１つのサンプルデータ毎にループ内部の処理を実行する。さらに、ＣＰＵ１１５は、１つのサンプルデータに対して誤差逆伝播処理を実行する（ステップＳ７０６）。【００６４】
誤差逆伝播処理では、ＣＰＵ１１５は、あるサンプルデータを入力とし、その入力に対するニューラルネットワークの出力結果と当該サンプルデータに対応する教師データとを比較し、２つのデータの誤差を削減するように、ニューラルネットワークの出力層に近い層（中間層）から順に入力層までの重みを更新する。すなわち、入力データが出力方向とは逆の方向に重みが更新される。【００６５】
サンプルデータのループ処理では、ＣＰＵ１１５が、複数のサンプルデータ１２２の各々に対して前述した処理を実行する。ステップＳ７０６の誤差逆伝播処理では、任意のサンプルデータに対する重みの更新が１回だけ行われる。【００６６】
一方、誤差逆伝播処理のループ処理では、誤差を最小にするためには、誤差逆伝播処理が複数回実行される。具体的には、ＣＰＵ１１５が、所定の条件を満たすまで、繰り返し、複数のサンプルデータ１２２の各々に対して誤差逆伝播処理を実行する。【００６７】
すなわち、誤差逆伝播処理のループ処理は、誤差逆伝播法による複数のサンプルデータの合計誤差の収束のために行われる。また、サンプルデータのループ処理は、複数のサンプルデータ１２２に対する重みの更新が行われる。【００６８】
次に、ＣＰＵ１１５は、全てのサンプルデータに対して誤差逆伝播処理が実行されたか否かを判定する（ステップＳ７０７）。【００６９】
全てのサンプルデータに対して誤差逆伝播処理が実行されていないと判定された場合、ＣＰＵ１１５は、ステップＳ７０５に戻り、同様の処理を実行する。【００７０】
全てのサンプルデータに対して誤差逆伝播処理が実行されたと判定された場合、ＣＰＵ１１５は、所定の条件を満たしたか否かを判定する（ステップＳ７０８）。【００７１】
所定の条件を満たしていないと判定された場合、ＣＰＵ１１５は、ステップＳ７０４に戻り、同様の処理を実行する。【００７２】
所定の条件を満たしたと判定された場合、ＣＰＵ１１５は、学習結果をメモリ１１１に格納する（ステップＳ７０９）。その後、ＣＰＵ１１５は、処理を終了する。なお、学習結果はストレージシステム１０２に格納されてもよい。【００７３】
学習結果には、構築されたニューラルネットワークの構成を示す情報、及びエッジのラベルと算出された重みとを対応付けた情報等の情報が含まれる。【００７４】
図８は、実施例１の計算機１０１が実行するニューラルネットワークの構築処理を説明するフローチャートである。図９Ａ及び図９Ｂは、実施例１の特徴マップグラフの構築の流れを示す説明図である。図１０は、実施例１の計算機１０１によって構築されたニューラルネットワークの一例を示す説明図である。【００７５】
ニューラルネットワークの構築処理では、グラフデータ１２１、ニューラルネットワークの構造に関するパラメタ、及び出力層の次元数（ノード数）等を含む定義情報が入力される。なお、ニューラルネットワークの構造に関するパラメタには、ニューラルネットワークの層の数、及び１つの中間層に含まれる特徴マップグラフの数等が含まれる。【００７６】
ここで、特徴マップグラフは、１つの中間層を構成するニューロン群を示す。すなわち、中間層は、１つ以上の特徴マップグラフを含む。後述するように特徴マップグラフは、複数のマップノードを含む。マップノードはニューロンに対応する。【００７７】
ＣＰＵ１１５は、ニューラルネットワークの入力層及び出力層を設定する（ステップＳ８０１）。【００７８】
具体的には、ＣＰＵ１１５は、グラフデータ１２１のノード群を入力層として設定する。すなわち、グラフデータ１２１の１つのノードが入力層の１つのニューロンとして設定される。また、ＣＰＵ１１５は、出力層の次元数と同数のノードを含む出力層を設定する。【００７９】
次に、ＣＰＵ１１５は、グラフデータ１２１を用いて特徴マップグラフを構築するループ処理を開始する（ステップＳ８０２）。特徴マップグラフを構築するループ処理は、指定されたニューラルネットワークの段数だけ繰り返し実行される。【００８０】
まず、ＣＰＵ１１５は、特徴マップグラフのマップノード（ニューロン）を生成する（ステップＳ８０３）。【００８１】
ここで、特徴マップグラフは、当該特徴マップグラフが含まれる中間層の前段の層に含まれる各マップノードに対し、重みテーブルに応じた特徴を示す。【００８２】
例えば、道路網において、重みテーブルが、距離が「１」である三叉路に発火する（北、南、西向きで距離１の関係に対して発火する等）場合、前段の層（例えば、入力層）に含まれる各ニューロンのうち、三叉路となっているニューロンに対応するマップノードが発火し、それ以外のマップノードは発火しない。ここで発火するとは、出力が正の大きな値をとることを表す。そのため、特徴マップグラフは三叉路の特徴を示したグラフとなる。このような特徴マップグラフを１つの層に複数生成し、また、複数の特徴マップグラフを含む層を用いてニューラルネットワークを構成することによって、複雑なトポロジを表現できる。すなわち、非線形な評価関数等の複雑な評価関数を表現できる。【００８３】
ステップＳ８０３では、具体的には、ＣＰＵ１１５が、特徴マップグラフの識別情報を割り当て、図９Ａに示すようにグラフデータ１２１に含まれるノードの数と同数のマップノードを生成する。すなわち、中間層のニューロンが生成される。このとき、グラフデータ１２１のノードと特徴マップグラフのマップノードとが一対一に対応付けられる。図９Ａでは、マップノードＦ０はノードＩ０に対応し、マップノードＦ１はノードＩ１に対応し、マップノードＦ２はノードＩ２に対応する。【００８４】
なお、１つの層に複数の特徴マップグラフを設定する必要がある場合、ＣＰＵ１１５は、前述と同様の手順にしたがって特徴マップグラフのマップノードを生成する。【００８５】
次に、ＣＰＵ１１５は、グラフデータ１２１に基づいて、グラフデータ１２１のノードと特徴マップグラフのマップノードとを接続するマップエッジを生成する（ステップＳ８０４）。【００８６】
具体的には、ＣＰＵ１１５は、グラフデータ１２１のノード間を接続するエッジを、グラフデータ１２１のノードと特徴マップグラフのノードとを接続するマップエッジとして生成する。すなわち、入力層のニューロンと、中間層のニューロンとを接続する接続が生成される。【００８７】
ＣＰＵ１１５は、まず、入力層に対応するグラフデータ９００に含まれる複数のマップノードの中から対象のマップノードを選択する。ＣＰＵ１１５は、グラフデータ９００に基づいて、対象のマップノードに対応するノードとエッジを介して接続されるノードを特定する。ＣＰＵ１１５は、特徴マップグラフに含まれ、かつ、特定されたノードに対応するマップノードと、対象のマップノードとの間にマップエッジを生成する。【００８８】
２つの中間層間のマップエッジを生成する場合にも同様の手順に基づいてマップエッジが生成される。すなわち、ＣＰＵ１１５は、入力側の中間層に含まれる複数のマップノードの中から対象のマップノードを選択する。ＣＰＵ１１５は、グラフデータ９００に基づいて、対象のマップノードに対応するノードとエッジを介して接続されるノードを特定する。ＣＰＵ１１５は、出力側の特徴マップグラフに含まれ、かつ、特定されたノードに対応するマップノードと、対象のマップノードとの間にマップエッジを生成する。【００８９】
例えば、グラフデータ１２１のエッジＥ０は、ノードＩ０からノードＩ１へ向かう辺であるため、ノードＩ０からノードＩ１に対応するノードＦ１にエッジを生成し、マップエッジＦＭ０＿Ｅ０としてメモリ１１１に一時的に保持する。また、グラフデータ１２１のエッジＥ１は、ノードＩ１からノードＩ０へ向かう辺であるため、ノードＩ１からノードＩ０に対応するノードＦ０にエッジを生成し、マップエッジＦＭ０＿Ｅ１としてメモリ１１１に一時的に保持する。他のマップエッジについても同様の処理が実行される。前述した処理によって図９Ｂに示すようなマップエッジが生成される。【００９０】
次に、ＣＰＵ１１５は、グラフデータと特徴マップグラフとの間を接続するマップエッジの重みについて重みテーブル１２３を生成する（ステップＳ８０５）。具体的には以下のような処理が実行される。【００９１】
まず、ＣＰＵ１１５は、空の重みテーブル１２３を生成する。ＣＰＵ１１５は、グラフデータ１２１のラベル３０３を参照して、ラベルの種別の数だけ、重みテーブル１２３にエントリを生成する。【００９２】
ＣＰＵ１１５は、生成された各エントリのラベル６０１にラベル３０３の値を設定する。また、ＣＰＵ１１５は、所定の基準にしたがって、各ラベルに対応付けた重みラベルを生成し、重みラベル６０２に生成された重みラベルを設定する。【００９３】
ＣＰＵ１１５は、ラベル３０３の値が同一であるエッジのエッジＩＤ３０１を取得し、取得されたエッジＩＤ３０１に対応するマップエッジを特定し、エッジ情報６０３に特定されたマップエッジの識別情報を設定する。以上がステップＳ８０５の処理の説明である。【００９４】
ＣＰＵ１１５は、指定されたニューラルネットワークの段数だけ層を生成したか否かを判定する（ステップＳ８０６）。【００９５】
指定されたニューラルネットワークの段数だけ層を生成していないと判定された場合、ＣＰＵ１１５は、ステップＳ８０２に戻り、同様の処理を繰り返し実行する。【００９６】
指定されたニューラルネットワークの段数だけ層を生成したと判定された場合、ＣＰＵ１１５は、出力層と、出力層の一つ前の中間層との間の接続を生成する（ステップＳ８０７）。その後、ＣＰＵ１１５は、ニューラルネットワークの構築処理を終了する。【００９７】
具体的には、ＣＰＵ１１５は、出力層の１つ前の中間層の特徴マップグラフに含まれる各マップノードに対して、一つのマップノードと、出力層に含まれる全てのニューロンとを接続するマップエッジを生成する。すなわち、出力層に含まれる各ニューロンと、出力層の１つ前の中間層の特徴マップグラフに含まれる各マップノード（ニューロン）とは完全二部グラフで接続される。【００９８】
以上の処理によって、図１０に示すようなニューラルネットワークが構築される。【００９９】
図１０のニューラルネットワークは、入力層であるグラフデータ９００、３つの中間層、及び出力層９２０から構成される。各中間層は２段の特徴マップグラフ９１０から構成される。また、グラフデータ９００に含まれるノードと特徴マップグラフ９１０−１に含まれるノードとを接続するエッジに対して重みテーブル１２３−１が、グラフデータ９００に含まれるノードから特徴マップグラフ９１０−２に含まれるノードへのエッジに対して重みテーブル１２３−２が生成される。また、特徴マップグラフ９１０−３には重みテーブル１２３−３、特徴マップグラフ９１０−４には重みテーブル１２３−４、特徴マップグラフ９１０−５には重みテーブル１２３−５、特徴マップグラフ９１０−６には重みテーブル１２３−６が生成される。【０１００】
構築されたニューラルネットワークの情報は、入力層のノード及びエッジの情報、各層の特徴量マップグラフ数、各特徴量マップグラフの重みテーブル、並びに出力層の重みテーブルという形式でメモリ１１１に格納される。なお、構築されたニューラルネットワークの情報は、ストレージシステム１０２に格納されてもよい。【０１０１】
次に、図１１を用いて識別処理について説明する。図１１は、実施例１の計算機１０１が実行する識別処理を説明するフローチャートである。【０１０２】
計算機１０１は、処理開始の指示を受け付けた場合、又は、識別対象のデータが入力された場合に以下で説明する処理を開始する。【０１０３】
まず、ＣＰＵ１１５は、ストレージシステム１０２からグラフデータ１２１を取得し、メモリ１１１に格納する（ステップＳ１１０１）。学習処理時に取得されたグラフデータ１２１のトポロジと、識別処理時に取得されたグラフデータ１２１のトポロジとは異なっていてもよい。【０１０４】
ＣＰＵ１１５は、取得されたグラフデータ１２１を用いてニューラルネットワークの再構築処理を実行する（ステップＳ１１０２）。ニューラルネットワークの再構築処理では、取得されたグラフデータ１２１を用いて図８と同様の処理が実行される。ただし、ステップＳ８０５の処理が一部異なる。【０１０５】
具体的には、ＣＰＵ１１５は、改めて重みラベルを生成することなく、学習処理において生成された重みラベルをメモリ１１１から取得し、取得された重みラベル用いて重みテーブル１２３を生成する。また、重みラベルに対応する重みは、学習処理において算出されているため、算出された値に基づいてニューラルネットワークの各エッジに重みが与えられる。【０１０６】
学習処理において、ノード間を接続するエッジの属性に基づいて重みラベルが割り当てられるため、異なるグラフデータ１２１であっても、同一の属性を有するエッジには同一の重みラベルが割り当てられる。そのため、学習結果を用いた処理が実行される。【０１０７】
次に、ＣＰＵ１１５は、ストレージシステム１０２等から対象のデータを取得し、メモリ１１１に格納する（ステップＳ１１０３）。【０１０８】
次に、ＣＰＵ１１５は、ニューラルネットワークを用いた信号伝播を行い（ステップＳ１１０４）、出力結果（出力ベクトル）をメモリ１１１に格納する（ステップＳ１１０５）。なお、出力結果はストレージシステム１０２に格納されてもよい。【０１０９】
実施例１によれば、ノード間の複雑な相互関係をグラフデータとして入力して、ニューラルネットワークを構築することによって、複雑な相互関係をニューラルネットワークの構造に反映できる。すなわち、複雑な評価関数を学習することが可能となる。
【実施例２】
【０１１０】
実施例２では、実施例１で説明したニューラルネットワークを用いた最適化問題の処理の高速化について説明する。以下、実施例１との差異を中心に実施例２について説明する。【０１１１】
実施例２の計算機システム１００の構成は実施例１の計算機システム１００と同一であるため説明を省略する。また、実施例２の計算機１０１及びストレージシステム１０２の構成は、実施例１の計算機１０１及びストレージシステム１０２と同一であるため説明を省略する。【０１１２】
一般的に、最適化問題は、入力データｘ１〜ｘｎ、評価関数ｆ（ｘ１、...、ｘｎ）とした場合、評価関数の値、すなわち、評価値を最大又は最小とする入力データｘ１〜ｘｎの値又は状態を決定する問題である。【０１１３】
このとき、入力データｘ１〜ｘｎの値の組み合わせが非常に多くなると、最適化問題にかかる計算量も非常に多くなる。そのため、計算量を削減するために近似アルゴリズムが用いられる。近似アルゴリズムは、例えば、モンテカルロ法、粒子法、遺伝的アルゴリズム、及びシミュレーテッドアニーリング等が上げられる。前述したような近似アルゴリズムは、入力データｘ１〜ｘｎの組み合わせを削減することによって、最適化問題にかかる計算量を削減している。【０１１４】
図１８は、従来の計算機が実行する近似アルゴリズムに基づく最適化問題の処理を説明するフローチャートである。ここでは、ｎ個の成分ｘｉから構成されるベクトルｘが入力データであり、かつ、評価関数ｆ（ｘ１、...、ｘｎ）を最小にする最適化問題を考える。なお、添字ｉは、１からｎまでの整数である。【０１１５】
計算機は、入力データｘの初期化した後（ステップＳ１８０１）、ステップＳ１８０２に進む。計算機は、入力データｘの値を用いて評価関数を計算する（ステップＳ１８０２）。具体的には、計算機は、入力データの各成分ｘｉの初期値を決定した後、各成分ｘｉの初期値を評価関数に代入することによって、評価値を算出する。【０１１６】
次に、計算機は、算出された評価値が現在の最小値より小さいか否かを判定する（ステップＳ１８０３）。なお、入力データｘの初期値を用いて評価値が算出された場合、この時点では最小値が存在しない。そのため、計算機は、ステップＳ１８０３の判定処理を実行することなくステップＳ１８０７に進む。【０１１７】
算出された評価値が現在の最小値以上であると判定された場合、計算機は、各成分ｘｉの値の組み合わせ（探索点）を決定する（ステップＳ１８０７）。その後、計算機は、ステップＳ１８０２に戻り、同様の処理を実行する。なお、探索点の決定方法は、用いられる近似アルゴリズムによって異なる。【０１１８】
算出された評価値が現在の最小値より小さいと判定された場合、計算機は、算出された評価値を最小値として更新する（ステップＳ１８０４）。【０１１９】
次に、計算機は、現在の最小値が閾値より小さいか否かを判定する（ステップＳ１８０５）。【０１２０】
現在の最小値が閾値以上であると判定された場合、計算機は、各成分ｘｉの値の組み合わせ（探索点）を決定する（ステップＳ１８０７）。現在の最小値が閾値より小さいと判定された場合、計算機は、評価値が最小となる各成分ｘｉの値の組み合わせを出力し（ステップＳ１８０６）、処理を終了する。【０１２１】
従来の近似アルゴリズムは、探索回数を削減するものである。しかし、対象となる問題が複雑な場合、探索点毎の評価関数の計算量も多くなり、最適化問題の処理の高速化の問題となる。【０１２２】
実施例２では、評価関数の演算処理をニューラルネットワークを用いて、高速化を行う例を示す。【０１２３】
まず、計算機１０１は、入力データｘをグラフデータに変換し、当該グラフデータを入力として実施例１の学習処理を実行する。ここで、入力データｘをグラフデータに変換する方法について説明する。【０１２４】
図１２は、実施例２の入力データｘからグラフデータへの変換を示す説明図である。図１２に示す例では、入力データｘが３次元のベクトルであるものとする。また、入力データｘの成分はｘ０、ｘ１、及びｘ２であるものとする。【０１２５】
計算機１０１は、入力データ１１００の各成分ｘ０、ｘ１、及びｘ２をノードとして定義する。計算機１０１は、３次元空間におけるベクトルｘの特性に基づいてノード間を接続するエッジを生成する。例えば、ベクトルｘの平均値が閾値より小さい場合にエッジを生成する方法、又は、３次元空間における基準点との間の距離（例えば、ユークリッド距離又はマンハッタン距離等）が閾値より小さい場合にエッジを生成する方法が考えられる。【０１２６】
また、学習処理におけるエッジのラベルの決定方法としては、例えば、距離に基づいてエッジを生成する方法を用いた場合、基準点と各座標との間の位置関係に基づいて決定することができる。【０１２７】
また、誤差逆伝播処理では、グラフデータに変換されたベクトルｘに対応する評価値を教師データとして用いて処理が実行される。なお、本実施例では、評価値の最小値を求める最適化問題であるため、評価値が閾値以下の場合教師データは「０」、評価値が閾値より大きい場合教師データは「１」であるものとする。このように定義することによって、評価値が閾値より小さい場合には、出力が「０」となるようにニューラルネットワークが構築される。【０１２８】
前述したような学習処理が終了した後、計算機１０１は、具体的な最適化問題の処理を開始する。図１３は、実施例２の計算機１０１が実行する最適化問題の処理を説明するフローチャートである。なお、従来の最適化問題の処理と同一のステップには同一の符号を付し、処理の説明を省略する。【０１２９】
計算機１０１は、入力データｘの初期化した後（ステップＳ１８０１）、ニューラルネットワークを用いて評価値を算出する（ステップＳ１３０１）。【０１３０】
具体的には、計算機１０１は、入力データの各成分の値を、当該成分ｘｉに対応するニューラルネットワーク内の入力層のノードに入力することによって、ニューラルネットワークを用いた演算処理を実行する。ニューラルネットワークを用いた評価値の算出処理は、一般的な評価関数の演算処理より計算量が少ないため、高速に行うことができる。【０１３１】
また、本実施例では、ニューラルネットワークを用いて算出された評価値が閾値より小さい場合、出力は「０」となる。【０１３２】
次に、計算機１０１は、ニューラルネットワークを用いて算出された評価値が「０」であるか否かを判定する（ステップＳ１３０２）。【０１３３】
ニューラルネットワークを用いて算出された評価値が「０」でないと判定された場合、計算機１０１は、ステップＳ１８０７に進む。【０１３４】
ニューラルネットワークを用いて算出された評価値が「０」であると判定された場合、計算機１０１は、入力データｘの値を用いて評価関数を計算する（ステップＳ１８０２）。【０１３５】
一般に、積和の演算処理の組み合わせであるニューラルネットワークの演算処理の方が複雑な評価関数を用いた演算処理より計算量が少ない。一方、ニューラルネットワークを用いて算出された評価値の精度は、評価関数を用いる場合と比べて低い。【０１３６】
そこで、実施例２では、ニューラルネットワークを用いた評価値の算出処理を一種のフィルタとして用いることによって、最適化問題の処理を高速化する。すなわち、評価値の値が「０」の場合にのみ評価関数を計算することによって、評価関数を用いた演算処理の実行回数を削減できる。【０１３７】
このように、実施例２では、ニューラルネットワークを用いた演算処理が粒度の荒い最適解の探索処理として扱われる。通常、粒度の異なる最適解の探索処理では、異なるアルゴリズムを構築する必要がある。しかし、実施例２では、同一のアルゴリズムを用いて、粒度の異なる最適解の探索処理を実現できる。
【実施例３】
【０１３８】
実施例３では、具体的な例として、倉庫の棚及び通路の最適レイアウト問題の処理の高速化について説明する。【０１３９】
実施例３の計算機システム１００の構成は実施例１の計算機システム１００と同一であるため説明を省略する。また、実施例３の計算機１０１及びストレージシステム１０２の構成は、実施例１の計算機１０１及びストレージシステム１０２と同一であるため説明を省略する。なお、実施例３では、データ処理部１２０が、入力データを解析し、解析の結果に基づいてグラフデータを生成する機能（グラフデータ生成部）を有する。なお、解析結果には、複数ノードの配置、及びノード間を接続するエッジの距離等が含まれる。【０１４０】
図１９は、従来の計算機が実行する最適レイアウト問題の処理を説明するフローチャートである。【０１４１】
計算機は、まず、初期レイアウト１９２０を受け付ける（ステップＳ１９０１）。ここで、初期レイアウト１９２０には、対象となる倉庫の形状、及び倉庫内の立ち入り禁止領域１９２１等の情報が含まれる。【０１４２】
次に、計算機は、初期レイアウト１９２０である倉庫の出入口を設定する（ステップＳ１９０２）。具体的には、計算機は、初期レイアウト１９２０内の所定の位置に所定の数の出入口１９２２を設定する。なお、出入口の数及び位置は予め与えられるものとする。出入口が設定されたレイアウトは、図１９に示すようなレイアウト１９３０になる。【０１４３】
次に、計算機は、レイアウト１９３０に対応する倉庫内に所定の位置に所定の数の棚１９２３を設定することによって、複数の棚配置レイアウト候補１９４０を生成する（ステップＳ１９０３）。【０１４４】
具体的には、計算機は、レイアウト１９３０を入力として、棚の数及び棚の配置が異なる複数の棚配置レイアウト候補１９４０を出力する。棚の配置方法は、例えば、シミュレーテッドアニーリング等の最適化手法を用いる。ここでは、棚の配置が異なるＮ個の棚配置レイアウト候補が出力されるものとする。ここで、棚配置の最適化の評価関数として、例えば、棚の数や配置の形状が考えられる。【０１４５】
次に、計算機は、棚配置レイアウト候補１９４０のループ処理を開始する（ステップＳ１９０４）。具体的には、計算機は、複数の棚配置レイアウト候補１９４０の中から、対象の棚配置レイアウト候補１９４０を選択する。【０１４６】
次に、計算機は、選択された棚配置レイアウト候補１９４０に対して通路の最適化処理を実行する（ステップＳ１９０５）。【０１４７】
ここでは、対象の棚配置レイアウト候補１９４０に対して、通路及び通路方向の最適化処理が実行される。計算機は、最適化処理の結果として、通路配置レイアウト候補１９５０を算出する。通路配置レイアウト候補１９５０の矢印１９２４は、通路及びその通路の方向を示す。１つの棚配置レイアウト候補１９４０に対して１つの通路配置レイアウト候補１９５０が出力される。【０１４８】
なお、通路及び通路方向とは、例えば、棚又は荷物を載せるカート等の通路及びその進行方向を示す。ここで、通路及び通路方向の最適化処理の評価関数は出入口及び各棚の経路長等が考えられる。また、評価値が最小となるレイアウトが通路配置レイアウト候補１９５０として出力されるものとする。【０１４９】
次に、計算機は、全ての棚配置レイアウト候補１９４０について通路の最適化処理が完了したか否かを判定する（ステップＳ１９０６）。【０１５０】
全ての棚配置レイアウト候補１９４０について通路の最適化処理が完了していないと判定された場合、計算機は、新たな棚配置レイアウト候補１９４０を選択し、同様の処理を実行する。一方、全ての棚配置レイアウト候補１９４０について通路の最適化処理が完了したと判定された場合、計算機は、Ｎ個の通路配置レイアウト候補１９５０の中から最適レイアウト１９６０を選択する（ステップＳ１９０７）。【０１５１】
具体的には、計算機は、棚配置の最適化の評価関数の値、すなわち、評価値に基づいて、通路配置レイアウト候補１９５０の中から最適レイアウト１９６０を選択し、選択された最適レイアウト１９６０を処理結果として出力する。【０１５２】
前述の最適レイアウト問題の処理では、棚配置レイアウト候補１９４０のループ処理、及び通路の最適化処理の２つの最適化が行われる。ここで、１つの棚配置レイアウト候補１９４０に対する通路の最適化処理は、評価関数の演算処理に相当する。そこで、本実施例では、通路の最適化処理に対してニューラルネットワークを用いた演算処理を適用することによって処理の高速化を実現する。【０１５３】
通路の最適化処理では、１つの棚配置レイアウト候補１９４０が計算機に入力され、計算機は、出力として１つの通路配置レイアウト候補１９５０を出力する。【０１５４】
実施例３の計算機１０１は、実施例１及び実施例２に示す最適化処理を実現するために、まず、入力された棚配置レイアウト候補１９４０をグラフデータに変換する。ここで、図１４から図１６を用いて、棚配置レイアウト候補１９４０をグラフデータに変換する方法について説明する。【０１５５】
図１４は、実施例３の棚配置レイアウト候補１９４０のセル表現及びグラフ化の一例を示す説明図である。図１５は、実施例３の棚配置レイアウト候補１９４０のグラフにおけるエッジのラベルの割り当て方法の一例を示す説明図である。図１６は、実施例３の棚配置レイアウト候補１９４０のグラフデータの一例を示す説明図である。【０１５６】
計算機１０１は、棚配置レイアウト候補１９４０を図１４に示すようなセルに分割する。また、計算機１０１は、各セルに、立ち入り禁止領域１９２１、出入口１９２２、棚１９２３及び通路１９２４に対応する値を設定する。ここでは、立ち入り禁止領域１９２１には「−１」、出入口１９２２には「０．５」、棚１９２３には「０」、また、通路１９２４には「１」が設定されるものとする。【０１５７】
以上の処理によって棚配置レイアウト候補１９４０を図１４に示すようなセルの集合として表現できる。【０１５８】
次に、計算機１０１は、セルの集合をグラフ化する。ここでは、セル１４１０−１及びセル１４１０−２に着目したセルの集合のグラフ化について説明する。【０１５９】
計算機１０１は、セル１４１０−１及びセル１４１０−２等の各セルに対応するノードを生成する。計算機１０１は、セル１４１０−１に対応するノード１４４０−１と他のノードとの間にエッジを生成し、また、セル１４１０−２に対応するノード１４１１−１と他のノードとの間にエッジを生成する。【０１６０】
本実施例では、セル１４１０−１から上下方向の２つ分のセルとセル１４１０−１との間でエッジが生成され、また、セル１４１０−１の左右方向の２つ分のセルとセル１４１０−１との間でエッジが生成される。また、本実施例では、セル１４１０−２から上方向に２つ分のセルとセル１４１０−２との間でエッジが生成され、また、セル１４１０−２の左右方向の２つ分のセルとセル１４１０−２との間でエッジが生成される。例えば、ノード１４４０−１とノード１４４０−２との間にエッジが生成され、また、ノード１４４０−１とノード１４４０−３との間にエッジが生成される。【０１６１】
以上の処理によって、セル１４１０−１に着目したセルの集合は、グラフ１（１４３０−１）に示すようなグラフに変換され、また、セル１４１０−２に着目したセルの集合は、グラフ２（１４３０−２）に示すようなグラフに変換される。【０１６２】
なお、ノード間を接続するエッジは、正方形、ひし形等の特定の形状、及び大きさ等を自由に設定できる。なお、本実施例では、値が「−１」であるセルとの間にはエッジは生成されないという禁止ルールが適用されているものとする。【０１６３】
次に、計算機１０１は、エッジにラベルを割り当てる。エッジに対するラベルの割り当てには予め定義されたラベル表１６００を使用する。図１６に示すラベル表１６００は、エッジの起点となるセルからエッジの終点となるセルの方向及び距離に応じて「１」から「８」の番号（ラベル）が割り当てられる。計算機１０１は、着目するセルと他のセルの方向及び距離に基づいて、エッジにラベルを割り当てる。【０１６４】
例えば、グラフ１（１４３０−１）の場合、エッジ１５１０−１は、ノード１４４０−１から「上方向」に「距離１」のノード１４４０−２と接続するエッジであるため、計算機１０１は、エッジ１５１０−１にラベル「１」を割り当てる。また、エッジ１５１０−２は、ノード１４４０−１から「上方向」に「距離２」のノード１４４０−２と接続するエッジであるため、計算機１０１は、エッジ１５１０−２にラベル「５」を割り当てる。一方、エッジ１５１０−３及びエッジ１５１０−４とは向きが逆のエッジ１５１０−３及びエッジ１５１０−４には別のラベルが割り当てられる。すなわち、エッジ１５１０−３は、ノード１４４０−２から「下方向」に「距離１」のノード１４４０−１と接続するエッジであるため、計算機１０１は、エッジ１５１０−３にラベル「２」を割り当てる。また、エッジ１５１０−４は、ノード１４４０−３から「下方向」に「距離２」のノード１４４０−１と接続するエッジであるため、計算機１０１は、エッジ１５１０−４にラベル「６」を割り当てる。【０１６５】
計算機１０１は、前述した処理を全てのエッジに対して実行する。以上のような処理を全てのセルに対して実行することによって、棚配置レイアウト候補１９４０が図１６に示すようなグラフデータに変換される。なお、図１６では図の煩雑さを避けるため、「距離２」であるエッジに割り当てられるラベル「５」、「６」、「７」及び「８」が割り当てられるエッジ、及びエッジによって接続されていないノードは省略している。【０１６６】
計算機１０１は、複数の棚配置レイアウト候補１９４０の各々の複数のグラフデータを入力データとして、ニューラルネットワークの構築処理を実行する。なお、ニューラルネットワークの構築処理は実施例１と同一の処理であるため説明を省略する。【０１６７】
図１７は、実施例３の計算機１０１が実行する最適レイアウト問題の処理を説明するフローチャートである。なお、従来の最適化問題の処理と同一のステップには同一の符号を付し、処理の説明を省略する。【０１６８】
計算機１０１は、ステップＳ１９０４において選択された棚配置レイアウト候補１９４０を入力として、ニューラルネットワークを用いて評価値を算出する（ステップＳ１７０１）。ここでは、実施例２のステップＳ１３０１と同様の処理が実行される。ただし、評価関数が異なる。本実施例では、ニューラルネットワークを用いて算出された評価値が閾値より小さい場合、出力は「０」となる。【０１６９】
次に、計算機１０１は、ニューラルネットワークを用いて算出された評価値が「０」であるか否かを判定する（ステップＳ１７０２）。【０１７０】
ニューラルネットワークを用いて算出された評価値が「０」でないと判定された場合、計算機１０１は、ステップＳ１９０６に進む。【０１７１】
ニューラルネットワークを用いて算出された評価値が「０」であると判定された場合、計算機１０１は、通路の最適化処理を実行する（ステップＳ１９０５）。【０１７２】
ここで、具体的な倉庫を例に、図１７を適用した場合の演算処理の精度及び速度について述べる。ここでは、縦が「２３」、横が「２３」の倉庫を想定する。また、ステップＳ１９０３において、「９２３」個の棚配置レイアウト候補１９４０が決定されたものとする。また、「９２３」個の棚配置レイアウト候補１９４０のうち、「２００」個の棚配置レイアウト候補１９４０を学習処理のサンプルデータとして計算機１０１に入力する。なお、残りの「７２３」個の棚配置レイアウト候補１９４０は、未知のデータとして扱う。【０１７３】
このとき、「２００」個のサンプルデータに対する学習精度は１００％であり、未知のデータを含めた全データに対する学習精度は９７％となる。【０１７４】
本実施例では評価関数の最小値を求める問題であるため、評価値の下から１０位のサンプルデータに着目した場合、当該サンプルデータは全てのニューラルネットワークにおいて評価値が低いと判定される。そのため、評価関数の最小値を求める問題に、ニューラルネットワークの出力を用いて、所定のデータに対する評価関数の演算処理をスキップしても最終的な出力結果は変わらない。したがって、本実施例の処理は、従来の最適化問題の処理と同一の最適レイアウト１９６０が出力される。したがって、演算結果は従来と同一の精度となる。【０１７５】
一方、通路の最適化処理が実行されたデータの数は「９２３」個の棚配置レイアウト候補１９４０のうちの３％程度となり、従来の処理より５倍の高速化が実現できる。【０１７６】
なお、本発明は上記した実施例に限定されるものではなく、様々な変形例が含まれる。また、例えば、上記した実施例は本発明を分かりやすく説明するために構成を詳細に説明したものであり、必ずしも説明した全ての構成を備えるものに限定されるものではない。また、各実施例の構成の一部について、他の構成に追加、削除、置換することが可能である。【０１７７】
また、上記の各構成、機能、処理部、処理手段等は、それらの一部又は全部を、例えば集積回路で設計する等によりハードウェアで実現してもよい。また、本発明は、実施例の機能を実現するソフトウェアのプログラムコードによっても実現できる。この場合、プログラムコードを記録した記憶媒体をコンピュータに提供し、そのコンピュータが備えるＣＰＵが記憶媒体に格納されたプログラムコードを読み出す。この場合、記憶媒体から読み出されたプログラムコード自体が前述した実施例の機能を実現することになり、そのプログラムコード自体、及びそれを記憶した記憶媒体は本発明を構成することになる。このようなプログラムコードを供給するための記憶媒体としては、例えば、フレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ハードディスク、ＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）、光ディスク、光磁気ディスク、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード、ＲＯＭなどが用いられる。【０１７８】
また、本実施例に記載の機能を実現するプログラムコードは、例えば、アセンブラ、Ｃ／Ｃ＋＋、ｐｅｒｌ、Ｓｈｅｌｌ、ＰＨＰ、Ｊａｖａ等の広範囲のプログラム又はスクリプト言語で実装できる。【０１７９】
さらに、実施例の機能を実現するソフトウェアのプログラムコードを、ネットワークを介して配信することによって、それをコンピュータのハードディスクやメモリ等の記憶手段又はＣＤ−ＲＷ、ＣＤ−Ｒ等の記憶媒体に格納し、コンピュータが備えるＣＰＵが当該記憶手段や当該記憶媒体に格納されたプログラムコードを読み出して実行するようにしてもよい。【０１８０】
上述の実施例において、制御線や情報線は、説明上必要と考えられるものを示しており、製品上必ずしも全ての制御線や情報線を示しているとは限らない。全ての構成が相互に接続されていてもよい。
【図１】
2016174725.tif 000003
【図２】
2016174725.tif 000004
【図３】
2016174725.tif 000005
【図４】
2016174725.tif 000006
【図５】
2016174725.tif 000007
【図６】
2016174725.tif 000008
【図７】
2016174725.tif 000009
【図８】
2016174725.tif 000010
【図９Ａ】
2016174725.tif 000011
【図９Ｂ】
2016174725.tif 000012
【図１０】
2016174725.tif 000013
【図１１】
2016174725.tif 000014
【図１２】
2016174725.tif 000015
【図１３】
2016174725.tif 000016
【図１４】
2016174725.tif 000017
【図１５】
2016174725.tif 000018
【図１６】
2016174725.tif 000019
【図１７】
2016174725.tif 000020
【図１８】
2016174725.tif 000021
【図１９】
2016174725.tif 000022
【国際調査報告】
2016174725.tif 000023
2016174725.tif 000024