(57)【要約】【課題】状態に対する連続値の算出を効率的に行い、非線形組合せの最適化問題を効率的に解くことができる状態空間の探索装置を得る。【解決手段】着目状態評価部２により、着目状態に対して、内点法を用いた二次計画法により連続値の最適化を行い、最良解を最良解保存データベース８に保存し、次いで、隣接状態作成・評価部３により、着目状態から隣接状態を作り、この隣接状態に対して、最良解保存データベース８に保存された最良解を初期値としてＡｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法により連続値の最適化を行い、評価を行って、隣接状態データベース９に保存し、次いで、状態遷移部４により、隣接状態データベース９に保存された隣接状態の内、評価関数値の最もよいものを次ぎの着目状態として、着目評価部２と隣接状態作成・評価部３と状態遷移部４による処理を繰り返して、最適な状態を探索するようにした。【選択図】図１
2008059146.tif 000002
【特許請求の範囲】
【請求項１】
複数の離散値の組合せと、上記離散値の組合せに対応して決定される連続値とを併せ持つ状態からなる状態空間の中を、初期の着目状態から出発し、上記着目状態の組合せを変更して得られる隣接状態の中から遷移すべき状態を決定して次の着目状態とする処理を順次繰返し、評価関数値が最良の状態を探索する状態空間の探索装置において、上記着目状態に対して、内点法を用いた二次計画法により上記連続値の最適化を行う着目状態評価手段、及び上記隣接状態に対して、上記着目状態評価手段による連続値の最適化によって得られた解を初期値として、Ａｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法により上記連続値の最適化を行う隣接状態評価手段を備えたことを特徴とする状態空間の探索装置。
【請求項２】
上記隣接状態評価手段は、上記着目状態評価手段による上記連続値の最適化によって得られた解を初期値とする上記Ａｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法により、上記着目状態から最初に作成した第一の隣接状態に対して上記連続値の最適化を行い、上記着目状態から二番目以降に作成した第二の隣接状態に対しては、直前の上記Ａｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法による連続値の最適化によって得られた解を初期値として、上記Ａｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法により、上記連続値の最適化を行うことを特徴とする請求項１記載の状態空間の探索装置。
【請求項３】
上記隣接状態評価手段の上記Ａｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法は、上記隣接状態に対する連続値の最適化の際に、繰り返し計算によって上記連続値の最適化を行うとともに、この繰り返し計算回数が、所定の値を超えた場合には、上記Ａｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法を、上記内点法を用いた二次計画法に切替えて、上記隣接状態に対する連続値の最適化を行うことを特徴とする請求項１または請求項２記載の状態空間の探索装置。
【請求項４】
上記隣接状態評価手段は、ＣＰＵ上で動作し、上記複数の隣接状態に対する連続値の最適化が複数のＣＰＵ上で並列に実行されることを特徴とする請求項１〜請求項３のいずれかに記載の状態空間の探索装置。
【請求項５】
複数の離散値の組合せと、上記離散値の組合せに対応して決定される連続値とを併せ持つ状態からなる状態空間の中を、初期の着目状態から出発し、上記着目状態の組合せを変更して得られる隣接状態の中から遷移すべき状態を決定して次の着目状態とする処理を順次繰返し、評価関数値が最良の状態を探索する状態空間の探索方法において、上記着目状態に対して、内点法を用いた二次計画法により上記連続値の最適化を行う第一の手順、及び上記隣接状態に対して、上記第一の手順による連続値の最適化によって得られた解を初期値として、Ａｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法により上記連続値の最適化を行う第二の手順を含むことを特徴とする状態空間の探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、非線形組合せの最適解を求める状態空間の探索装置及び状態空間の探索方法に関するものである。
【背景技術】
【０００２】
従来の組合せ最適化手法として、例えば、非特許文献１には、タブーサーチ法を採用したものが記載されている。
非線形組合せ最適化問題は、組合せ最適化問題における各状態の連続変数を連続系最適化手法により決定する２重の最適化問題として扱うことが一般的であり、従来技術においても、組合せ最適化手法として非特許文献１に示されるようなタブーサーチ法や、連続系最適化手法として内点法を用いた二次計画法を採用している。
【０００３】
【非特許文献１】平成１２年度電気学会全国大会講演番号２６８、澤敏之他、「タブーサーチ法を用いた発電所の週間運用計画」
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、現実的な非線形組合せ最適化問題では、１つの状態（離散変数と連続変数の集合）に対して、その組合せ（離散変数）の１箇所以上を変更して得られる隣接状態の数は、数十から数百以上存在し、また１つの状態について連続系最適化手法で最適化すべき連続変数の数は、数千から数万、あるいはそれ以上存在することが一般的であり、内点法を用いた二次計画法を全ての状態に対する連続変数の最適化方法として適用する従来の技術では、個々の状態に対する連続変数の算出に多大な処理時間を要することとなり、その結果、状態空間の探索範囲が限られるという問題があった。
【０００５】
この発明は、上述のような課題を解決するためになされたものであり、状態に対する連続値（連続変数）の算出を効率的に行い、非線形組合せの最適化問題を効率的に解くことができる状態空間の探索装置及び状態空間の探索方法を得ることを目的にしている。
【課題を解決するための手段】
【０００６】
この発明に係わる状態空間の探索装置においては、複数の離散値の組合せと、離散値の組合せに対応して決定される連続値とを併せ持つ状態からなる状態空間の中を、初期の着目状態から出発し、着目状態の組合せを変更して得られる隣接状態の中から遷移すべき状態を決定して次の着目状態とする処理を順次繰返し、評価関数値が最良の状態を探索する状態空間の探索装置において、着目状態に対して、内点法を用いた二次計画法により連続値の最適化を行う着目状態評価手段、及び隣接状態に対して、着目状態評価手段による連続値の最適化によって得られた解を初期値として、Ａｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法により連続値の最適化を行う隣接状態作成・評価手段を備えたものである。
【発明の効果】
【０００７】
この発明は、以上説明したように、複数の離散値の組合せと、離散値の組合せに対応して決定される連続値とを併せ持つ状態からなる状態空間の中を、初期の着目状態から出発し、着目状態の組合せを変更して得られる隣接状態の中から遷移すべき状態を決定して次の着目状態とする処理を順次繰返し、評価関数値が最良の状態を探索する状態空間の探索装置において、着目状態に対して、内点法を用いた二次計画法により連続値の最適化を行う着目状態評価手段、及び隣接状態に対して、着目状態評価手段による連続値の最適化によって得られた解を初期値として、Ａｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法により連続値の最適化を行う隣接状態作成・評価手段を備えたので、解の精度を落とすことなく高速に状態の連続値を求めることが可能となり、限られた処理時間の中でより広範な状態空間を探索することができる。
【発明を実施するための最良の形態】
【０００８】
実施の形態１．
図１は、この発明の実施の形態１による状態空間探索装置を示すブロック図であり、タブーサーチ法を用いた状態空間探索装置２００が示されている。
図１において、入力情報１００として、状態空間探索装置２００において、状態空間探索を行う上で必要となる情報が、ＬＡＮなどの通信手段、あるいはＧＵＩ（Ｇｒａｐｈｉｃａｌ  Ｕｓｅｒ  Ｉｎｔｅｒｆａｃｅ）を通じて状態作成用データベース７に入力される。
状態作成データ読込み部１は、状態空間の探索の出発点となる状態を着目状態として初期設定する機構であり、状態作成用データベース７から、状態を作成するために必要となるデータを抽出し、初期の着目状態ならびに最良状態の評価関数値の初期値を設定すると共に、以降の着目状態評価部２から探索継続判定部５までの繰返し処理における繰返し回数カウンタＬの初期設定を行う。
ここで、状態空間は、複数の離散値からなる組合せと、この離散値の組合せに対応して決定される連続値とを併せ持つ状態からなる。例えば、離散値を設備の台数とすると、連続値はその設備の燃料費などであり、この連続値は、全体の設備の組み合せに対応して個々の設備の燃料費が決定される。状態空間の探索とは、全体の燃料費が最小となる状態、すなわち全体の評価関数値が最小の状態を探索するものである。
【０００９】
着目状態評価部２（着目状態評価手段、第一の手順）は、内点法を用いた二次計画法により着目状態における連続値の最適化（全体の組み合せに対応した個々の連続値の決定）を行うと共に、この着目状態の評価を行う（評価関数値を求める）機構であり、連続値の最適化結果を、後述する隣接状態作成・評価部３および状態遷移部４において使用するＡｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法の初期値として、Ａｃｔｉｖｅ−ｓｅｔ法初期値データベース９に保存する。
また、評価した着目状態がそれまでに探索した着目状態の中で最も良い評価関数値を持つ場合は、その着目状態を最良状態として最良解保存データベース８に保存する。
【００１０】
隣接状態作成・評価部３（隣接状態評価手段、第二の手順）は、タブーリストデータベース１１を参照し、着目状態から１箇所以上異なる組合せを持つ隣接状態の中から、タブーリストにより作成を禁止されていない隣接状態を作成して、Ａｃｔｉｖｅ−ｓｅｔ法初期値データベース９に保存されている初期値を用いて、隣接状態の連続値の最適化を行うと共に、隣接状態に対する評価を行う機構であり、着目状態から隣接状態へ状態遷移するために必要な隣接状態種別、組合せ変更箇所などの状態変更情報ならびに隣接状態の評価関数値を、隣接状態データベース１０に保存する。
【００１１】
状態遷移部４は、隣接状態データベース１０に保存されている隣接状態データのうち、評価関数値が最も良い隣接状態を次の着目状態に設定する機構である。また、着目状態から次の着目状態に遷移するために必要となる隣接状態種別、組合せ変更箇所などの状態変更情報をタブーリストデータベース１１に保存すると共に、それまでの探索において保存されていたタブーリストの更新を行う。
探索継続判定部５は、着目状態評価部２から探索継続判定部５までの繰返し処理における繰返し回数Ｌが、繰返し最大数ＬＭＡＸを超えたかどうかを判定する。
最適状態出力部６は、着目状態評価部２から探索継続判定部５までの繰返し処理の中で得られた最良状態を最良解保存データベース８から抽出し、最適解として出力情報１０１に出力する。
【００１２】
図２は、この発明の実施の形態１による状態空間探索装置の状態作成データ読込み部の処理を示すフローチャートである。
図３は、この発明の実施の形態１による状態空間探索装置の着目状態評価部の処理を示すフローチャートである。
図４は、この発明の実施の形態１による状態空間探索装置の隣接状態作成・評価部の処理を示すフローチャートである。
図５は、この発明の実施の形態１による状態空間探索装置の状態遷移部の処理を示すフローチャートである。
図６は、この発明の実施の形態１による状態空間探索装置の探索継続判定部の処理を示すフローチャートである。
図７は、この発明の実施の形態１による状態空間探索装置の最適状態出力部の処理を示すフローチャートである。
【００１３】
図８は、この発明の実施の形態１による状態空間探索装置の物理イメージを示す図である。
図８において、記憶媒体２０２は、７〜１１のデータベースを有している。ＣＰＵ２０１は、１〜６の各プログラムを有し、記憶媒体２０２と接続されている。
【００１４】
次に、状態作成データ読込み部１の処理について、図２のフローチャートを用いて説明する。
ステップＳ１１で、探索を行うためのデータを入力する。ステップＳ１２では、ステップＳ１１で入力したデータを元に着目状態の初期設定を行う。次いで、ステップＳ１３で、最良解の評価関数値を初期設定する（最小化問題であれば十分大きな値、最大化問題であれば十分小さな値を設定する）。次いで、ステップＳ１４で、着目状態評価部２から探索継続判定部５までの繰返し処理における繰返しカウンタＬを初期設定する。
【００１５】
次に、着目状態評価部２について、図３のフローチャートを用いて説明する。
ステップＳ２１で、内点法を用いた二次計画法により、着目状態の組み合せに対応して個々の連続値を決定する。ステップＳ２２で、内点法を用いた二次計画法で得られた解を、Ａｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法の初期値として保存する。
【００１６】
ここで、内点法ならびにＡｃｔｉｖｅ−ｓｅｔ法について説明する。
まず、内点法について説明する。内点法では、下記の標準形式の最適化問題を扱う。
Ｍｉｎ  ｆ（ｘ）                                （式１）
ｓ．ｔ．          ｇ（ｘ）        ＝  ０        （式２）
ｘ＋ｓ−ω      ＝  ０        （式３）
ｘ  ≧  ０                    （式４）
ｓ  ≧  ０                    （式５）
ただし、
ｓｉ：ｘの要素ｘｉの上限制約を等式制約に変換するために導入されたスラック変数
ω ：ｘの上限値
【００１７】
上記の標準形式には、関数型不等式制約が含まれないが、以下に示すように、スラック変数を導入することにより、関数型不等式制約は、関数型等式制約に変換可能であり、上記の標準形式は一般性を失わない。
ｈｍｉｎ≦ｈ（ｘ）≦ｈｍａｘ  →  ｈ（ｘ）−ｓ＝０，ｈｍｉｎ≦ｓ≦ｈｍａｘ
また、上記の標準形問題では、ｘの範囲を０≦ｘ≦ωとしているが（ｓに関しても同様）、これは、変数の座標原点をｘｍｉｎに移し、変数の伸縮を行うことにより実現できるため、一般性を失わない。上記問題の最適解においては、下記のＫＫＴ（Ｋａｒｕｓｈ−Ｋｕｈｎ−Ｔｕｃｋｅｒ）条件が満たされる必要がある。
【００１８】
【数１】
2008059146.tif 000003
【００１９】
ｇ（ｘ）      ＝  ０        （式７）
ｘ＋ｓ−ω    ＝  ０        （式８）
ｘｉλｘｉ      ＝  ０        （式９）
ｓｉλｓｉ      ＝  ０       （式１０）
ｘ    ≧  ０                （式１１）
ｓ    ≧  ０                （式１２）
λｘ   ≧  ０                （式１３）
λｓ   ≧  ０                （式１４）
ただし、
μ：ｇ（ｘ）＝０  に対応するラグランジュ乗数
ν：ｘ＋ｓ−ω＝０  に対応するラグランジュ乗数
λｘ：ｘの下限制約に対応するラグランジュ乗数
λｓ：ｓの下限制約に対応するラグランジュ乗数
【００２０】
内点法は、変数ｘ，ｓ，λｘ，λｓを非負の領域に留めながら、（式６），（式７），（式８），（式９），（式１０）を同時に満たすｘ，μ，ν，λｘ，λｓを解き、最適解を得る手法で、最適解の近似値を初期値として与える必要もなく、数万変数を超える大型問題に対しても数十回で収束するため、一般的には最も使い易い最適化手法である。
【００２１】
続いて、Ａｃｔｉｖｅ−ｓｅｔ法について説明する。
Ａｃｔｉｖｅ−ｓｅｔ法では、下記（式１５）に示す標準形式の最適化問題を扱う。
Ｍｉｎ  ｆ（ｘ）        （式１５）
ｓ．ｔ．      ｇｉ（ｘ）  ＝  ０  ，ｉ＝１，・・・・，Ｉ    
ｘｍｉｎ≦ｘ≦ｘｍａｘ
上記の標準形式には関数型不等式制約が含まれないが、前述の通り、スラック変数を導入することにより、関数型不等式制約は関数型等式制約に変換可能であり、上記の標準形式は一般性を失わない。また、上記の標準形式では制御変数ｘに上下限制約を与えているが、制約がない場合には、十分に小さなｘｍｉｎあるいは十分に大きなｘｍａｘを与えることが可能であり、上記の標準形式は一般性を失わない。上記問題の最適解においては、下記のＫＫＴ条件が満たされる必要がある。
【００２２】
∇ｆ  ＋  Σμｉ∇ｇｉ  ＋  λＵ  −  λＬ  ＝  ０    （式１６）
ｇｉ（ｘ）  ＝  ０                                   （式１７）
ｘｍｉｎ≦ｘ≦ｘｍａｘ                                  （式１８）
λＵ  ≧  ０                                          （式１９）
λＬ  ≧  ０                                          （式２０）
ただし、
λＵ  ：ｘの上限制約に関するラグランジュ乗数を格納するベクトルであり、最適解において上限制約が活性なｘの要素位置に非負の要素を持ち、その他の要素は０となる。
λＬ  ：ｘの下限制約に関するラグランジュ乗数を格納するベクトルであり、最適解において下限制約が活性なｘの要素位置に非負の要素を持ち、その他の要素は０となる。なお、ｘの上限制約と下限制約が同時に活性になることはないので、（λＵ−λＬ）をまとめてλと表すことも可能であり、この場合には、下限制約が活性な要素に関しては、非正の値を持つこととなる。（式１６）をλで表すと下記となる。
∇ｆ  ＋  Σμｉ∇ｇｉ  ＋  λ  ＝  ０             （式１６ａ）
【００２３】
Ａｃｔｉｖｅ−ｓｅｔ法では、最適解において活性となる不等式制約（標準形式の最適化問題を扱うので最適解において上下限制約が活性となる変数ｘの要素）を仮定し、その仮定の下で（式１６ａ）と（式１７）を同時に満たすｘ，μ，λを解き、ｘ，λが満たすべき不等式制約（（式１８）、（式１９）、（式２０））を満たしていれば、それを解とし、満たしていなければ、最適解において活性となる不等式制約の仮定を見直して、再度処理を繰返す最適化手法で、最適解において活性となる不等式制約をかなり正確に予測可能な場合には特に有効となる。
【００２４】
Ａｃｔｉｖｅ−ｓｅｔ法の繰返し計算回数は、ほぼ基本問題の最適解と、基本問題から僅かに条件の異なる最適化問題の最適解との活性となる不等式制約の相違箇所数（上下限に張付く変数の相違箇所数）となる。
また、Ａｃｔｉｖｅ−ｓｅｔ法では、上下限に張付く変数（固定値となり変数ではなくなる）を仮定するため、Ａｃｔｉｖｅ−ｓｅｔ法における繰返し１回あたりの処理時間は実質的に減少し、内点法における繰返し１回あたりの処理時間のほぼ（上下限に張付かない変数の数／変数の数）２倍となる。
内点法の繰返し計算回数は、一般的に４０回程度であることから、Ａｃｔｉｖｅ−ｓｅｔ法で扱う変数の半分が上下限に張付く変数と仮定すると、上記の活性となる不等式制約の相違箇所数（上下限に張付く変数の相違箇所数）が１６０以下の問題に対しては、Ａｃｔｉｖｅ−ｓｅｔ法が内点法に比べ、処理時間的に有利となる。
【００２５】
図３に戻り、ステップＳ２３は、着目状態、ならびにステップＳ２１で決定した着目状態に対する連続値から、着目状態に対する評価関数値を算出するステップである。
ステップＳ２４は、着目状態の評価関数値が、それまでの探索で保存された最良解の評価関数値よりも良い（最小化問題であれば小さい／最大化問題であれば大きい）かどうかを判定し、着目状態の評価関数値が最良解の評価関数値よりも良い場合は、ステップＳ２５に進み、良くない場合は、着目状態評価部２の処理を終了するように分岐する。ステップＳ２５では、着目状態とその評価関数値を最良解として保存する。
【００２６】
次に、隣接状態作成・評価部３について、図４のフローチャートを用いて説明する。
ステップＳ３１では、隣接状態数をカウントするためのカウンタＪの初期設定を行う。ステップＳ３２で、作成しようとする隣接状態、あるいは着目状態から隣接状態に遷移するための状態変更情報がタブーリストに登録されているかどうかを検索することにより、着目状態から隣接状態への遷移が禁止されていないかどうかを判定する。遷移が禁止されていれば、ステップＳ３７に進み、遷移可能であれば、ステップＳ３３に進むよう分岐する。
ステップＳ３３では、着目状態から１つ以上の組合せを変更して隣接状態を作成する。ステップＳ３４では、ステップＳ２２で保存した初期値を使用して、Ａｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法を行うことにより、隣接状態に対する連続値を最適化する。ステップＳ３５では、隣接状態の組合せ、ならびにステップＳ３４で算出した連続値から隣接状態の評価関数値を算出する。ステップＳ３６で、着目状態から隣接状態へ遷移するために必要となる状態変更情報、ならびに隣接状態の評価関数値を保存する。
ステップＳ３７で、隣接状態数のカウンタＪを１カウントアップした後、全ての隣接状態に対する処理を終了したかどうかを判定するステップＳ３８で、全ての隣接状態に対する処理を終了していれば、隣接状態作成・評価部３の処理を終了し、終了していなければ、ステップＳ３２に戻り、処理を継続するよう分岐する。
【００２７】
次いで、状態遷移部４について、図５のフローチャートを用いて説明する。
ステップＳ４１では、隣接状態作成・評価部３において保存した隣接状態のうち、最も評価関数値が良い状態を次の着目状態として設定する。ステップＳ４２では、着目状態から次の着目状態への遷移に必要となる隣接状態種別、状態変更箇所などの状態変更情報をタブーリストへ保存すると共に、タブーリストにすでに保存されている情報を更新する。
【００２８】
次に、探索継続判定部５について、図６のフローチャートを用いて説明する。
ステップＳ５１では、着目状態評価部２から探索継続判定部５までの繰返し処理に関する繰返し回数Ｌが、繰返し回数上限ＬＭＡＸより小さいかどうかを判定する。ＬがＬＭＡＸより小さい場合は、ステップＳ５２へ進み、ＬがＬＭＡＸ以上となる場合は、着目状態評価部２から探索継続判定部５までの繰返し処理を終了し、最適状態出力部６へと進むよう分岐する。ステップＳ５２では、繰返し回数Ｌを１カウントアップする。
【００２９】
次に、最適状態出力部６について、図７のフローチャートを用いて説明する。
ステップＳ６１で、状態作成データ読込み部１から探索継続判定部５までの処理で得られた最良解を最良解保存データベース８より抽出する。ステップＳ６２では、抽出した最良解を計算結果として出力情報１０１に出力する。
【００３０】
出力情報１０１は、状態作成データ読込み部１から最適状態出力部６に示す機構において得られた最適解を、状態空間探索装置が求められている形態で出力した出力結果である。
この出力結果は、例えば複数の需要家の電力需要および熱需要に対して、自然エネルギーや二次電池、ガスエンジンなどの電力供給設備を用いて電力の需要と供給量が一致するよう電力供給設備の起動・停止ならびに発電量を制御するのに用いられたり、ボイラなどの熱供給設備を用いて熱の需要と供給が一致するよう熱供給設備の起動・停止ならびに熱出力を制御するのに用いられる。
すなわち、これらのシステムに対して状態空間探索装置を適用した場合、ＧＵＩを介して運転員に対して最適解を表示する、あるいはＬＡＮなどの通信手段を介して電力供給設備、あるいは熱供給設備に対して起動・停止指令などの制御指令を出力するためなどに使用される。
【００３１】
図８は、状態空間探索装置のハードウェアと図１の各機能との関連を示すものであり、次にこの図８について説明する。
図１の状態作成データ読込み部１は、状態空間探索装置のＣＰＵ２０１上で動作するプログラムであり、状態作成用データベース７からＣＰＵ２０１上に状態を作成するために必要となる入力情報１００を呼び出すと共に、ＣＰＵ２０１において初期の着目状態を作成する。ここで、状態作成用データベース７は、ハードディスク、メモリなどに代表される記憶媒体２０２に形成されている。
【００３２】
図１の着目状態評価部２は、状態空間探索装置のＣＰＵ２０１上で動作するプログラムであり、内点法を用いた二次計画法により着目状態に関する連続値を決定し、その際に得られた計算結果をＡｃｔｉｖｅ−ｓｅｔ法初期値データベース９に保存すると共に、着目状態の評価関数値を算出する。また、最良解保存データベース８から、ＣＰＵ２０１上に、それまでの探索で得られた最良解を呼び出し、着目状態の評価関数値が呼び出した最良解の評価関数値よりも良いか否かを判定し、着目状態が最良解よりも良い解であれば、着目状態を最良解保存データベース８に保存する。ここで、最良解保存データベース８ならびにＡｃｔｉｖｅ−ｓｅｔ法初期値データベース９の各データベースは、ハードディスク、メモリなどに代表される記憶媒体２０２に形成されている。
【００３３】
図１の隣接状態作成・評価部３は、状態空間探索装置のＣＰＵ２０１上で動作するプログラムであり、タブーリストデータベース１１からＣＰＵ２０１上に、それまでの探索で設定されたタブーリストを呼び出して、着目状態に対する隣接状態として作成可能かどうかを判定し、作成可能な隣接状態である場合は、着目状態に対する隣接状態を作成した後、Ａｃｔｉｖｅ−ｓｅｔ法初期値データベース９から初期値を呼び出して、Ａｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法を行うことにより、隣接状態に対する連続値を決定すると共に隣接状態の評価関数値を計算する。
また、作成した隣接状態、着目状態から隣接状態へ遷移するための状態変更情報、ならびに隣接状態の評価関数値を隣接状態データベース１０に保存する。ここで、隣接状態データベース１０ならびにタブーリストデータベース１１は、ハードディスク、メモリなどに代表される記憶媒体２０２に形成されている。
【００３４】
図１の状態遷移部４は、状態空間探索装置のＣＰＵ２０１上で動作するプログラムであり、隣接状態データベース１０からＣＰＵ２０１上に、隣接状態作成・評価部３にて作成した隣接状態のうち最良の評価関数値を持つ状態を呼び出して、次の着目状態に設定する。また、着目状態から次の着目状態へ遷移するための状態変更情報を、タブーリストデータベース１１に保存すると共に、タブーリストデータベース１１に保存されているリスト情報を更新する。
【００３５】
図１の探索継続判定部５は、状態空間探索装置のＣＰＵ２０１上で動作するプログラムであり、着目状態評価部２から探索継続判定部５までの繰返し処理に関する繰返し回数Ｌが、繰返し回数上限ＬＭＡＸより小さいかどうかを判定すると共に、繰返し回数Ｌを１カウントアップする。
【００３６】
図１の最適状態出力部６は、状態空間探索装置のＣＰＵ２０１上で動作するプログラムであり、最良解保存データベース８に保存されている最良解を呼び出すと共に、最良解を計算結果として出力する。
【００３７】
なお、上述では、タブーサーチ法について説明したが、この発明はタブーサーチ法に限らず、問題空間探索法、ローカルサーチ法、遺伝アルゴリズム、シミュレーテッドアニーリングなど、初期の着目状態から出発し、着目状態の組合せを変更して得られる隣接状態の中から遷移すべき状態を決定して次の着目状態とすることを順次繰返し、評価関数値が最良の状態を探索する探索方式に適用できる。
これにより、処理速度の向上に非常に有効であり、従来技術に比べ、より広範な状態空間の探索が可能となる。
【００３８】
実施の形態１によれば、解の精度を落とすことなく高速に状態の連続値を求めることが可能となり、限られた処理時間の中で、より広範な状態空間を探索することができる。
【００３９】
実施の形態２．
図９は、この発明の実施の形態２による状態空間探索装置を示すブロック図である。
図９において、図１に構成で、隣接状態作成・評価部３が隣接状態作成・評価部３’に変っている。他の構成は図１と同じである。
【００４０】
図１０は、この発明の実施の形態２による状態空間探索装置の隣接状態作成・評価部の処理を示すフローチャートである。
図１０において、ステップＳ３１〜ステップＳ３３、ステップＳ３５〜ステップＳ３８は図４におけるものと同一の処理である。図１０では、図４のステップＳ３４に代えて、ステップＳ３４１、Ｓ３４２の処理が実行される。
【００４１】
図１１は、この発明の実施の形態２による状態空間探索装置の隣接状態作成・評価部の処理を説明する説明図である。
図１１において、着目状態から隣接状態２への状態変更箇所は４である。着目状態から隣接状態作成手順１により隣接状態１を作成し、この隣接状態１から隣接状態作成手順２により隣接状態２を作成する。隣接状態１から隣接状態２への状態変更箇所は２である。
ここで、隣接状態１、２は、ともにある着目状態に対する隣接状態。隣接状態１は、着目状態から２箇所の状態を１→２に変更した隣接状態。隣接状態２は、着目状態から２箇所の状態を１→２に変更し、さらに別の２箇所の状態１→０に変更した状態。隣接状態２に関する連続値を決定する場合、着目状態から隣接状態２への状態変更（連続値の上下限制約変更）箇所数４よりも、隣接状態１からの状態変更（連続値の上下限制約変更）箇所数２の方が少ない。
【００４２】
実施の形態２は、例えば図１１に示すような複数箇所を同時に変更する隣接状態を順次作成し、その連続値を決定する場合、前回作成した隣接状態の連続値を決定した際に保存した計算結果を用いて、次のＡｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法を行うようにする。
【００４３】
次に、図９の隣接状態作成・評価部３’の処理について、図１０のフローチャートを用いて説明する。
ステップＳ３１〜ステップＳ３３を図４と同様にして実行した後、ステップＳ３４１は、図９のＡｃｔｉｖｅ−ｓｅｔ法初期値データベース９より、ステップＳ２２で保存した初期値、あるいは後述するステップＳ３４２で保存した初期値、すなわち当該時点で最新の初期値を呼び出して、Ａｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法を行うことにより、隣接状態に対する連続値を計算する。
すなわち、着目状態から最初に作成した隣接状態（第一の隣接状態）に対しては、内点法を用いた二次計画法により連続値の最適化を行って得られた解をステップＳ２２で保存した初期値を用いて連続値の最適化を行う。また、着目状態から二番目以降に作成した隣接状態（第二の隣接状態）に対しては、直前のＡｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法による連続値の最適化によって得られた解を初期値として、連続値の最適化を行う。
ステップＳ３４２では、ステップＳ３４１で計算した二次計画法の計算結果を次のＡｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法を行うための初期値として、図９のＡｃｔｉｖｅ−ｓｅｔ法初期値データベース９に保存する。
次いで、ステップＳ３５〜ステップＳ３８を図４と同様に実行する。
【００４４】
実施の形態２によれば、例えば図１１に示すような複数箇所を同時に変更する隣接状態を順次作成し、その連続値を決定する場合、着目状態の連続値を決定した際に保存した計算結果を初期値とするよりも、前回作成した隣接状態の連続値を決定した際に保存した計算結果の方が、より最適解の条件に近くなると考えられ、その結果Ａｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法の繰返し回数が減ることにより、処理時間の短縮が図れるという効果が得られる。
【００４５】
実施の形態３．
図１２は、この発明の実施の形態３による状態空間探索装置の隣接状態作成・評価部の処理を示すフローチャートである。
図１２において、ステップＳ３１〜ステップＳ３３、ステップＳ３５〜ステップＳ３８は図４におけるものと同一の処理である。図１２では、図４のステップＳ３４に代えて、ステップＳ３４３の処理が実行される。
以下、前述した実施の形態１との差異に着目して説明する。
【００４６】
実施の形態３は、図１２のステップＳ３４３が実施の形態１と異なる。ステップＳ３４３では、ステップＳ２２で保存した初期値を使用して、Ａｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法を行うことにより、隣接状態に対する連続値を計算する。このＡｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法では、繰り返し計算によって連続値の最適化を行い、このＡｃｔｉｖｅ−ｓｅｔ法を用いた二次計画法における繰り返し計算回数が、所定の繰り返し回数上限を超える場合には、内点法を用いた二次計画法に切替えて隣接状態に対する連続値を計算する。
【００４７】
一般的な内点法の繰返し計算回数を４０回程度と仮定すると、基本問題の最適解を知っている状況において、基本問題に対する派生問題（基本問題から僅かに条件の異なる最適化問題）を解こうとするとき、基本問題の変数の数、基本問題の最適解と派生問題との上下限に張付く変数の相違箇所数、ならびに上下限に張付かない変数の数の関係が（式２１）を満たす場合には、内点法を用いるよりもＡｃｔｉｖｅ−ｓｅｔ法を用いて最適化する方が処理速度の面から有利となる。
ただし、上下限に張付く変数の相違箇所数と、上下限に張付かない変数の数は、基本問題の最適解と派生問題との条件の差異から想定される値であることから、上下限に張付く変数の相違箇所数ならびに上下限値に張付かない変数の数については、１〜２割程度の尤度を持つ必要がある。
【００４８】
（上下限に張付く変数の相違箇所数）×（上下限に張付かない変数の数／変数の数）２＜４０                          （式２１）
【００４９】
また、Ａｃｔｉｖｅ−ｓｅｔ法の繰返し回数が（式２２）の条件を満たす回数となった場合、前述の想定が外れたこととなり、この後どれだけの繰返し計算が必要となるかが不明となる。このような想定外の状況で処理時間が大幅に増加する危険を避けるため、Ａｃｔｉｖｅ−ｓｅｔ法の繰返し回数が（式２２）の条件を満たした時点で、Ａｃｔｉｖｅ−ｓｅｔ法による最適化を中止し、内点法による最適化に切替える。
【００５０】
繰返し回数＞４０×（変数の数／上下限に張付かない変数の数）２    （式２２）
【００５１】
実施の形態３によれば、以上のように構成することにより、上述のような想定外の状況に陥った場合でも、処理時間の大幅な増加を防ぐことができる。
【００５２】
実施の形態４．
図１３は、この発明の実施の形態４による状態空間探索装置を示すブロック図である。
図１３において、図１の構成で、隣接状態作成・評価部３が隣接状態振分け部３ａ〜隣接状態集約部３ｅに変っている。他の構成は図１と同じである。
【００５３】
図１４は、この発明の実施の形態４による状態空間探索装置の物理イメージを示す図である。
図１４において、２０２、１、２、４〜１１は図８におけるものと同一のものである。図１４では、隣接状態振分け部３ａ、隣接状態作成・評価部３ｂ、隣接状態集約部３ｅがＣＰＵ１（２０１）上で、隣接状態作成・評価部３ｃがＣＰＵ２（２０３）上で、隣接状態作成・評価部３ｄがＣＰＵ３（２０４）上でそれぞれ動作する。
以下、前述した実施の形態１との差異に着目して説明する。
【００５４】
実施の形態４は、図１３のように、３つのＣＰＵ２０１、２０３、２０４ならびに１つの記憶媒体２０２を持つハードウェア上で動作するタブーサーチ法を用いた状態空間探索装置についてのものである。また、図１４は、図１３の状態空間探索装置に関し、ハードウェアと図１３の各機能との関連を示している。
【００５５】
次に、各機能について、図１４に基き説明する。
状態作成データ読込み部１、着目状態評価部２、状態遷移部４、探索継続判定部５、ならびに最適状態出力部６は、実施の形態１に示すものと同じであり、ＣＰＵ１（２０１）上で動作するプログラムである。
【００５６】
隣接状態振分け部３ａは、着目状態に対して１箇所以上の組合せを変更して得られる複数の隣接状態について、各々の隣接状態をＣＰＵ１（２０１）、ＣＰＵ２（２０３）、あるいはＣＰＵ３（２０４）の何れのＣＰＵで作成して評価を行うかを決定し、各ＣＰＵに振分ける機構であり、ＣＰＵ１（２０１）上で動作する。
隣接状態作成・評価部３ｂは、ＣＰＵ１（２０１）上で動作するプログラムであり、隣接状態作成・評価部３ｃは、ＣＰＵ２（２０３）上で動作するプログラムであり、隣接状態作成・評価部３ｄは、ＣＰＵ３（２０４）上で動作するプログラムであり、それぞれ実施の形態１に示す隣接状態作成・評価部３と同様の動作をする。
隣接状態集約部３ｅは、ＣＰＵ１（２０１）上で動作するプログラムであり、隣接状態作成・評価部３ｂ、隣接状態作成・評価部３ｃ、ならびに隣接状態作成・評価部３ｄにおいて作成した隣接状態、着目状態から隣接状態へ遷移するための状態変更情報、ならびに隣接状態の評価関数値を隣接状態データベース１０に保存する。
【００５７】
実施の形態４によれば、以上のように構成することにより、複数のＣＰＵによる並列演算を行う場合でも、実施の形態１と同様の効果が得られる。
【産業上の利用可能性】
【００５８】
この発明は、ロジスティクス、ＬＳＩ最適配線決定などの各種最適化設計、電力系統における発電機起動停止問題や系統構成作成、ガスや水道の供給経路作成などの各種最適計画、最適制御に適用される。
【図面の簡単な説明】
【００５９】
【図１】この発明の実施の形態１による状態空間探索装置を示すブロック図である。
【図２】この発明の実施の形態１による状態空間探索装置の状態作成データ読込み部の処理を示すフローチャートである。
【図３】この発明の実施の形態１による状態空間探索装置の着目状態評価部の処理を示すフローチャートである。
【図４】この発明の実施の形態１による状態空間探索装置の隣接状態作成・評価部の処理を示すフローチャートである。
【図５】この発明の実施の形態１による状態空間探索装置の状態遷移部の処理を示すフローチャートである。
【図６】この発明の実施の形態１による状態空間探索装置の探索継続判定部の処理を示すフローチャートである。
【図７】この発明の実施の形態１による状態空間探索装置の最適状態出力部の処理を示すフローチャートである。
【図８】この発明の実施の形態１による状態空間探索装置の物理イメージを示す図である。
【図９】この発明の実施の形態２による状態空間探索装置を示すブロック図である。
【図１０】この発明の実施の形態２による状態空間探索装置の隣接状態作成・評価部の処理を示すフローチャートである。
【図１１】この発明の実施の形態２による状態空間探索装置の隣接状態作成・評価部の処理を説明する説明図である。
【図１２】この発明の実施の形態３による状態空間探索装置の隣接状態作成・評価部の処理を示すフローチャートである。
【図１３】この発明の実施の形態４による状態空間探索装置を示すブロック図である。
【図１４】この発明の実施の形態４による状態空間探索装置の物理イメージを示す図である。
【符号の説明】
【００６０】
１  状態作成データ読込み部、２  着目状態評価部、
３，３’，３ｂ，３ｃ，３ｄ  隣接状態作成・評価部、
３ａ  隣接状態振分け部、３ｅ  隣接状態集約部、
４  状態遷移部、５  探索継続判定部、６  最適状態出力部、
７  状態作成用データベース、８  最良解保存データベース、
９  Ａｃｔｉｖｅ−ｓｅｔ法初期値データベース、
１０  隣接状態データベース、１１  タブーリストデータベース、
１００  入力情報、１０１  出力情報、２００  状態探索装置、
２０１，２０３，２０４  ＣＰＵ、２０２  記憶媒体。
【図１】
2008059146.tif 000004
【図２】
2008059146.tif 000005
【図３】
2008059146.tif 000006
【図４】
2008059146.tif 000007
【図５】
2008059146.tif 000008
【図６】
2008059146.tif 000009
【図７】
2008059146.tif 000010
【図８】
2008059146.tif 000011
【図９】
2008059146.tif 000012
【図１０】
2008059146.tif 000013
【図１１】
2008059146.tif 000014
【図１２】
2008059146.tif 000015
【図１３】
2008059146.tif 000016
【図１４】
2008059146.tif 000017