(57)【要約】  【課題】  制約条件付きの目的関数の複数局所最適解、または、大域最適解という解を探索できるような解探索方法、解探索装置、解探索プログラムおよび記録媒体を提供する。  【解決手段】  任意の初期値から勾配系微分方程式を解いて初回の局所最適解を探索する初回局所最適解探索手順（ステップＳ３）と、局所最適解から分界点を探索する分界点探索手順（ステップＳ４〜Ｓ８）と、安定境界上の分解点を用いて新たな局所最適解を探索する新規局所最適解探索手順（ステップＳ９）と、所定条件を満たすか否かを判断し、所定条件に満たない場合は新たな局所最適解を初期値として上記の分界点探索手順および新規局所最適解探索手順を繰り返し行わせて制約条件を満たす複数の局所最適解を探索させる判断手順と（ステップＳ１０）、最適な解を求解する最適解求解手順（ステップＳ１１）と、を有するような解探索方法、解探索装置、解探索プログラムおよび記録媒体とした。【選択図】  図１
2006171948.tif 000002
【特許請求の範囲】
【請求項１】
複数の局所最適解または大域最適解の探索対象となる目的関数、および、この目的関数から導出された勾配系微分方程式を用いて、制約条件を満たしつつ複数の局所最適解または大域最適解を探索する解探索方法であって、
任意の初期値から勾配系微分方程式を解いて初回の局所最適解を探索する初回局所最適解探索手順と、
勾配系微分方程式の平衡点を表現する非線形代数方程式を導出する非線形代数方程式導出手順と、
非線形代数方程式をパラメータ化してパラメータ化非線形代数方程式を導出するパラメータ化非線形代数方程式導出手順と、
パラメータ化非線形代数方程式に対して連続法を用いて平衡点を探索する平衡点探索手順と、
平衡点の安定性を評価する安定性評価手順と、
得られた平衡点が安定境界上の分解点であるか否かを確認する確認手順と、
安定境界上の分解点を用いて新たな局所最適解を探索する新規局所最適解探索手順と、
所定条件を満たすか否かを判断し、所定条件に満たない場合は新たな局所最適解を初期値として上記の非線形代数方程式導出手順、パラメータ化非線形代数方程式導出手順、平衡点探索手順、安定性評価手順、確認手順、新規局所最適解探索手順を繰り返し行わせて制約条件を満たす複数の局所最適解を探索させる判断手順と、
最適な解を求解する最適解求解手順と、
を有することを特徴とする解探索方法。
【請求項２】
複数の局所最適解または大域最適解の探索対象となる目的関数、および、この目的関数から導出された勾配系微分方程式を用いて、制約条件を満たしつつ複数の局所最適解または大域最適解を探索する解探索装置であって、
任意の初期値から勾配系微分方程式を解いて初回の局所最適解を探索する初回局所最適解探索手段と、
勾配系微分方程式の平衡点を表現する非線形代数方程式を導出する非線形代数方程式導出手段と、
非線形代数方程式をパラメータ化してパラメータ化非線形代数方程式を導出するパラメータ化非線形代数方程式導出手段と、
パラメータ化非線形代数方程式に対して連続法を用いて平衡点を探索する平衡点探索手段と、
平衡点の安定性を評価する安定性評価手段と、
得られた平衡点が安定境界上の分解点であるか否かを確認する確認手段と、
安定境界上の分解点を用いて新たな局所最適解を探索する新規局所最適解探索手段と、
所定条件を満たすか否かを判断し、所定条件に満たない場合は新たな局所最適解を初期値として上記の非線形代数方程式導出手段、パラメータ化非線形代数方程式導出手段、平衡点探索手段、安定性評価手段、確認手段、新規局所最適解探索手段を繰り返し機能させて制約条件を満たす複数の局所最適解を探索させる判断手段と、
最適な解を求解する最適解求解手段と、
を有することを特徴とする解探索装置。
【請求項３】
複数の局所最適解または大域最適解の探索対象となる目的関数、および、この目的関数から導出された勾配系微分方程式を用いて、制約条件を満たしつつ複数の局所最適解または大域最適解を探索する解探索プログラムであって、
任意の初期値から勾配系微分方程式を解いて初回の局所最適解を探索する初回局所最適解探索手段と、
勾配系微分方程式の平衡点を表現する非線形代数方程式を導出する非線形代数方程式導出手段と、
非線形代数方程式をパラメータ化してパラメータ化非線形代数方程式を導出するパラメータ化非線形代数方程式導出手段と、
パラメータ化非線形代数方程式に対して連続法を用いて平衡点を探索する平衡点探索手段と、
平衡点の安定性を評価する安定性評価手段と、
得られた平衡点が安定境界上の分解点であるか否かを確認する確認手段と、
安定境界上の分解点を用いて新たな局所最適解を探索する新規局所最適解探索手段と、
所定条件を満たすか否かを判断し、所定条件に満たない場合は新たな局所最適解を初期値として上記の非線形代数方程式導出手段、パラメータ化非線形代数方程式導出手段、平衡点探索手段、安定性評価手段、確認手段、新規局所最適解探索手段を繰り返し機能させて制約条件を満たす複数の局所最適解を探索させる判断手段と、
最適な解を求解する最適解求解手段と、
としてコンピュータに機能させるようなプログラムであることを特徴とする解探索プログラム。
【請求項４】
複数の局所最適解または大域最適解の探索対象となる目的関数、および、この目的関数から導出された勾配系微分方程式を用いて、制約条件を満たしつつ複数の局所最適解または大域最適解を探索するための解探索プログラムがコンピュータに読み取り可能に記録された記録媒体であって、
任意の初期値から勾配系微分方程式を解いて初回の局所最適解を探索する初回局所最適解探索手段と、
勾配系微分方程式の平衡点を表現する非線形代数方程式を導出する非線形代数方程式導出手段と、
非線形代数方程式をパラメータ化してパラメータ化非線形代数方程式を導出するパラメータ化非線形代数方程式導出手段と、
パラメータ化非線形代数方程式に対して連続法を用いて平衡点を探索する平衡点探索手段と、
平衡点の安定性を評価する安定性評価手段と、
得られた平衡点が安定境界上の分解点であるか否かを確認する確認手段と、
安定境界上の分解点を用いて新たな局所最適解を探索する新規局所最適解探索手段と、
所定条件を満たすか否かを判断し、所定条件に満たない場合は新たな局所最適解を初期値として上記の非線形代数方程式導出手段、パラメータ化非線形代数方程式導出手段、平衡点探索手段、安定性評価手段、確認手段、新規局所最適解探索手段を繰り返し機能させて制約条件を満たす複数の局所最適解を探索させる判断手段と、
最適な解を求解する最適解求解手段と、
としてコンピュータに機能させるようなプログラムを記録したことを特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の局所最適解、または、これら局所最適解の中で最も最適な大域最適解を探索するための解探索方法、解探索装置、解探索プログラムおよび記録媒体に関する。
【背景技術】
【０００２】
ある事象についての制約条件付きの最適化問題では、一般的に以下のような手順で問題を解く。
（１）事象のモデルを表す目的関数と制約条件とを構築する。
（２）制約条件を満たしつつ、この目的関数の局所的な最小値もしくは最大値である最適解（以下、局所最適解という）、また、この目的関数の大域的な最小値もしくは最大値である最適解（以下、大域最適解という）を探索する。
ここに大域最適解とは、多数の局所最適解の中で最も最小または最大となる値を解とするものである。
これら局所最適解や大域最適解を用いて事象の最適化を図る。
【０００３】
続いてある事象についての制約条件付きの最適化問題について解析的に説明する。ここでは制約条件のある非線形最適化問題を考える。この非線形最適化問題における目的関数および制約条件は次式のようになる。
【０００４】
【数１】
2006171948.tif 000003
【０００５】
続いて上記の制約条件を満たす目的関数の局所最適解と大域最適解とについて定義する。まず、局所最適解は以下のように定義される。上記数１の各式の実行可能領域を表す制約集合は次式のように表される。
【０００６】
【数２】
2006171948.tif 000004
【０００７】
この場合の局所最適解ｘ0は以下のように定義される。
【０００８】
【数３】
2006171948.tif 000005
【０００９】
同様に大域最適解ｘ0は以下のように定義される。
【００１０】
【数４】
2006171948.tif 000006
【００１１】
これら局所最適解や大域最適解を用いて事象の最適化を図ることとなる。このような非線形最適化問題を解くことにより、例えば、電力系統運用の最適潮流計算、エネルギー・マネージメントシステム、水処理プラント等の最適化手法では、大域最適解を探索することで省エネルギー、コストダウンに寄与する。
【００１２】
さて、従来技術では、複数の局所最適解、大域最適解を効率的に探索する手法として、例えば、非特許文献１の方法が開示されている。計算効率に問題があるものの高次元問題の大域最適解をシステマティックに求める手法である。
【００１３】
この非特許文献１に開示された大域最適解探索方法について概略説明する。
ここに説明の前提として安定平衡点とは、換言すれば沈点、吸収点、シンク(sink)、アトラクタ(attractor)とも呼ばれるものであり、例えば目的関数ｃ（ｘ、ｙ）のような二次元変数に対する解曲線であるならば、解曲線の局所域での谷底の最低点に相当する。
また、タイプ２不安定平衡点とは、換言すれば、源点、湧き出し点、ソース(source)、リペラ(repellor)とも呼ばれるものであり、例えば目的関数ｃ（ｘ、ｙ）のような二次元変数に対する解曲線であるならば、解曲線の局所域での山頂の最高点に相当する。
また、タイプ１不安定平衡点とは、換言すれば、鞍点、サドル(saddle)とも呼ばれるものであり、例えば目的関数ｃ（ｘ、ｙ）のような二次元変数に対する解曲線であるならば、解曲線の局所域での山頂間の鞍部に相当する。
【００１４】
この大域最適解の探索方法では目的関数の最小の大域最適解を求めるものとして説明する。
まず目的関数から勾配系微分方程式を導出する（勾配系微分方程式導出手順）。
次に、任意の初期値から勾配系微分方程式を解いて安定平衡点を探索する（安定平衡点探索手順）。求められた安定平衡点は目的関数の複数の局所解の中の１つであり、局所的最小値である。
次に、この安定平衡点探索手順で探索した局所的最小値の安定境界（スタビリティ・バウンダリー：Stability boundary）上にあるタイプ１不安定平衡点を、多数の任意の初期値から勾配系微分方程式をマイナス時間（０秒からマイナス無限大秒）の方向に解くことにより探索する（従来型タイプ１不安定平衡点探索手順）。
次に、この従来型タイプ１不安定平衡点探索手順で探索したタイプ１不安定平衡点の不安定固有ベクトル上の任意の点を勾配系微分方程式の初期値とし、上記の安定平衡点探索手順に戻り、次の安定平衡点を探索する（新規安定平衡点探索手順）。
以下、従来型タイプ１不安定平衡点探索手順と新規安定平衡点探索手順とを繰り返して探索した複数の局所的最小値の内、最も小さな最小値を大域的最小値とし、目的関数の大域最適解とする。
【００１５】
上記した従来技術では、従来型タイプ１不安定平衡点探索手順に特徴がある。この点について図を参照しつつ説明する。図８は従来技術の大域最適解探索方法におけるタイプ１不安定平衡点を探索する方法を説明する説明図である。図８において、
（１）●は、目的関数から計算した勾配系微分方程式の安定平衡点（局所的最小値の１つ）を表し、
（２）○は、安定平衡点●の安定境界上にあるタイプ１不安定平衡点を表し、
（３）○から出ている矢印の線はタイプ１不安定平衡点の不安定多様体（もしくは安定平衡点●の安定多様体）を表し、
（４）○に向かっている矢印の線はタイプ１不安定平衡点の安定多様体を表す。
【００１６】
従来技術のタイプ１不安定平衡点を探索する方法では安定平衡点●を中心として、できるだけ多くの近傍点（図８の＋）の初期値を設定し、これら全部の初期値について勾配系微分方程式をマイナス時間方向に積分することによりタイプ１不安定平衡点○を試行錯誤的（総当たり的）に探索していた。
非特許文献１はこのようなものである。
【００１７】
また、非特許文献２では、離散勾配系のカオスを用いた大域的最適化について言及している。
さらにまた、メタ解法として遺伝的アルゴリズム、タブサーチ、Particle Swarm Optimization等も最適解を効率的に探索する手法として知られている。
【００１８】
【非特許文献１】Hsiao-Dong Chiang and Chia-Chi Chu、 "A Systematic Search Method for Obtaining Multiple Local Optimal Solutions of Nonlinear Programming Problems、" IEEE Transactions on Circuits and Systems - I、 vol. 43、 No. 2、 pp. 99-109、 Feb. 1996.
【非特許文献２】増田和明、相吉英太郎、“離散勾配系のカオスを用いた大域的最適化へのアプローチ”、平成16年電気学会全国大会、4-S19-3、 p.9-12、 2004
【発明の開示】
【発明が解決しようとする課題】
【００１９】
従来技術の非特許文献１の複数局所最適解、大域最適解探索方法は、制約条件を扱えないため、上記のような制約条件付きの最適化問題では適用できなかった。
また、メタ解法では、得られた最適解の最適性は数学的には保証せず、局所最適解でさえ与えないおそれがあり、適用しづらいものであった。
【００２０】
この発明は上記課題を解決するためになされたものであり、その目的は、制約条件付きの目的関数の複数局所最適解、または、大域最適解という解を探索できるような解探索方法、解探索装置、解探索プログラムおよび記録媒体を提供することにある。
【課題を解決するための手段】
【００２１】
本発明の解探索方法は、
複数の局所最適解または大域最適解の探索対象となる目的関数、および、この目的関数から導出された勾配系微分方程式を用いて、制約条件を満たしつつ複数の局所最適解または大域最適解を探索する解探索方法であって、
任意の初期値から勾配系微分方程式を解いて初回の局所最適解を探索する初回局所最適解探索手順と、
勾配系微分方程式の平衡点を表現する非線形代数方程式を導出する非線形代数方程式導出手順と、
非線形代数方程式をパラメータ化してパラメータ化非線形代数方程式を導出するパラメータ化非線形代数方程式導出手順と、
パラメータ化非線形代数方程式に対して連続法を用いて平衡点を探索する平衡点探索手順と、
平衡点の安定性を評価する安定性評価手順と、
得られた平衡点が安定境界上の分解点であるか否かを確認する確認手順と、
安定境界上の分解点を用いて新たな局所最適解を探索する新規局所最適解探索手順と、
所定条件を満たすか否かを判断し、所定条件に満たない場合は新たな局所最適解を初期値として上記の非線形代数方程式導出手順、パラメータ化非線形代数方程式導出手順、平衡点探索手順、安定性評価手順、確認手順、新規局所最適解探索手順を繰り返し行わせて制約条件を満たす複数の局所最適解を探索させる判断手順と、
最適な解を求解する最適解求解手順と、
を有することを特徴とする。
【００２２】
また、本発明の解探索装置は、
複数の局所最適解または大域最適解の探索対象となる目的関数、および、この目的関数から導出された勾配系微分方程式を用いて、制約条件を満たしつつ複数の局所最適解または大域最適解を探索する解探索装置であって、
任意の初期値から勾配系微分方程式を解いて初回の局所最適解を探索する初回局所最適解探索手段と、
勾配系微分方程式の平衡点を表現する非線形代数方程式を導出する非線形代数方程式導出手段と、
非線形代数方程式をパラメータ化してパラメータ化非線形代数方程式を導出するパラメータ化非線形代数方程式導出手段と、
パラメータ化非線形代数方程式に対して連続法を用いて平衡点を探索する平衡点探索手段と、
平衡点の安定性を評価する安定性評価手段と、
得られた平衡点が安定境界上の分解点であるか否かを確認する確認手段と、
安定境界上の分解点を用いて新たな局所最適解を探索する新規局所最適解探索手段と、
所定条件を満たすか否かを判断し、所定条件に満たない場合は新たな局所最適解を初期値として上記の非線形代数方程式導出手段、パラメータ化非線形代数方程式導出手段、平衡点探索手段、安定性評価手段、確認手段、新規局所最適解探索手段を繰り返し機能させて制約条件を満たす複数の局所最適解を探索させる判断手段と、
最適な解を求解する最適解求解手段と、
を有することを特徴とする。
【００２３】
また、本発明の解探索プログラムは、
複数の局所最適解または大域最適解の探索対象となる目的関数、および、この目的関数から導出された勾配系微分方程式を用いて、制約条件を満たしつつ複数の局所最適解または大域最適解を探索する解探索プログラムであって、
任意の初期値から勾配系微分方程式を解いて初回の局所最適解を探索する初回局所最適解探索手段と、
勾配系微分方程式の平衡点を表現する非線形代数方程式を導出する非線形代数方程式導出手段と、
非線形代数方程式をパラメータ化してパラメータ化非線形代数方程式を導出するパラメータ化非線形代数方程式導出手段と、
パラメータ化非線形代数方程式に対して連続法を用いて平衡点を探索する平衡点探索手段と、
平衡点の安定性を評価する安定性評価手段と、
得られた平衡点が安定境界上の分解点であるか否かを確認する確認手段と、
安定境界上の分解点を用いて新たな局所最適解を探索する新規局所最適解探索手段と、
所定条件を満たすか否かを判断し、所定条件に満たない場合は新たな局所最適解を初期値として上記の非線形代数方程式導出手段、パラメータ化非線形代数方程式導出手段、平衡点探索手段、安定性評価手段、確認手段、新規局所最適解探索手段を繰り返し機能させて制約条件を満たす複数の局所最適解を探索させる判断手段と、
最適な解を求解する最適解求解手段と、
としてコンピュータに機能させるようなプログラムであることを特徴とする。
【００２４】
また、本発明の記録媒体は、
複数の局所最適解または大域最適解の探索対象となる目的関数、および、この目的関数から導出された勾配系微分方程式を用いて、制約条件を満たしつつ複数の局所最適解または大域最適解を探索するための解探索プログラムがコンピュータに読み取り可能に記録された記録媒体であって、
任意の初期値から勾配系微分方程式を解いて初回の局所最適解を探索する初回局所最適解探索手段と、
勾配系微分方程式の平衡点を表現する非線形代数方程式を導出する非線形代数方程式導出手段と、
非線形代数方程式をパラメータ化してパラメータ化非線形代数方程式を導出するパラメータ化非線形代数方程式導出手段と、
パラメータ化非線形代数方程式に対して連続法を用いて平衡点を探索する平衡点探索手段と、
平衡点の安定性を評価する安定性評価手段と、
得られた平衡点が安定境界上の分解点であるか否かを確認する確認手段と、
安定境界上の分解点を用いて新たな局所最適解を探索する新規局所最適解探索手段と、
所定条件を満たすか否かを判断し、所定条件に満たない場合は新たな局所最適解を初期値として上記の非線形代数方程式導出手段、パラメータ化非線形代数方程式導出手段、平衡点探索手段、安定性評価手段、確認手段、新規局所最適解探索手段を繰り返し機能させて制約条件を満たす複数の局所最適解を探索させる判断手段と、
最適な解を求解する最適解求解手段と、
としてコンピュータに機能させるようなプログラムを記録したことを特徴とする。
【発明の効果】
【００２５】
以上のような本発明によれば、制約条件付きの目的関数の複数局所最適解、または、大域最適解という解を探索できるような解探索方法、解探索装置、解探索プログラムおよび記録媒体を提供することができる。
【発明を実施するための最良の形態】
【００２６】
以下、本発明を実施するための最良の形態の解探索方法、解探索装置、解探索プログラム、および、記録媒体について説明する。
まず、解探索方法について図を参照しつつ説明する。図１は本形態の解探索方法を説明するフローチャートである。
この解探索方法は、コンピュータを用いて実現される。解探索方法では、目的関数の多数の局所的最適解（最大値または最小値）を探索する局所的最適解探索や、この局所的最適解探索により求められた局所的最適解（局所最大値または局所最小値）の中で最も最適な解である大域最適解（最大値または最小値）を決定する大域的最適解探索があるが、本形態では大域的最適解探索を説明する。この大域的最適解探索では、複数の局所的最適解も併せて探索される。
【００２７】
ステップＳ１は、大域最適解の探索対象となる目的関数および制約条件を登録する手順（関数・条件登録手順）である。
この場合、目的関数および制約条件の設計はオペレータが行うものであり、コンピュータに対し、例えば、任意の定数・変数・次数の設定や関数を選択して組み合わせたり、あるいは、予め登録された関数を選択するなどして、今回使用する目的関数および制約条件を登録する。
本形態では、例えば、次式のような目的関数および制約条件を例に挙げて説明を具体化して説明する。なお、制約条件を特に上限値と下限値の制約条件（以下、上下限制約条件という）とする。目的関数および上下限制約条件は次式のようになる。
【００２８】
【数５】
2006171948.tif 000007
【００２９】
ステップＳ２は上記の目的関数から勾配系微分方程式を導出し、この導出された勾配系微分方程式を登録する手順（勾配系微分方程式登録手順）である。
この場合も勾配系微分方程式の導出自体はオペレータが立式するものであり、コンピュータに対しては、例えば、任意の定数・変数・次数を設定したり、あるいは、予め登録された関数を選択するなどして、今回使用できる勾配系微分方程式を登録する。
先の数５の目的関数の勾配系微分方程式は、次の数６のような方程式となる。非特許文献２によると、目的関数と上下限制約条件より次式のような勾配系微分方程式が導出されることが知られている。
【００３０】
【数６】
2006171948.tif 000008
【００３１】
ここでｃｉおよびｆｉは次式のように表される。
【００３２】
【数７】
2006171948.tif 000009
【００３３】
また、上記の数６を別の表で記述すると次式のようになる。
【００３４】
【数８】
2006171948.tif 000010
【００３５】
ステップＳ３は任意の初期値から勾配系微分方程式を解いて始めの局所最適解を探索する手順（初回局所最適解探索手順）である。
任意の初期値から上記数６の勾配系微分方程式を解くことにより、はじめの局所最適解ｘＳ１の探索を行う。例えば、オイラー法、ルンゲクッタ法など周知の方法にて微分方程式を解くことが出来る。
【００３６】
続くステップＳ４，５，６，７，８は探索した局所最適解から分界点を探索する手順（分界点探索手順）である。詳しくは、既知の局所最適解が含まれる安定領域Ａ（stability region Ａ）の境界は安定境界∂Ａ（stability boundary ∂Ａ）であるが、この安定境界∂Ａ（stability boundary ∂Ａ）上にある分解点の探索を行う。ここで、局所最適解の安定領域Ａ（stability region Ａ）は次式で定義される。
【００３７】
【数９】
2006171948.tif 000011
【００３８】
ここでｔは時間、Φ(ｘ、t)は軌道を表す。この安定領域Ａ（stability region）の境界を安定境界（stability boundary）とよぶ。
【００３９】
ステップＳ４は、勾配系微分方程式の平衡点を表現する非線形代数方程式を導出し、この導出された非線形代数方程式を登録する手順（非線形代数方程式導出手順）である。
この場合も非線形代数方程式の導出自体はオペレータが立式するものであり、コンピュータに対しては、例えば、任意の定数・変数・次数を設定したり、あるいは、予め登録された関数を選択するなどして、今回使用できる非線形代数方程式を登録する。具体的には上記数６の勾配系微分方程式の左辺をゼロとおいて、平衡点を表現する次式のような非線形代数方程式を導出する。
【００４０】
【数１０】
2006171948.tif 000012
【００４１】
ステップＳ５は、非線形代数方程式をパラメータ化してパラメータ化非線形代数方程式を導出し、この導出されたパラメータ化非線形代数方程式を登録する手順である（パラメータ化非線形代数方程式導出手順）。
この場合もパラメータ化非線形代数方程式の導出自体はオペレータが立式するものであり、コンピュータに対しては、例えば、任意の定数・変数・次数を設定したり、あるいは、予め登録された関数を選択するなどして、今回使用できるパラメータ化非線形代数方程式を登録する。具体的には非線形代数方程式の一の定数をパラメータと仮定してパラメータ化非線形代数方程式を導出する手順である。例えば、パラメータをａとすると次式のように表される。
【００４２】
【数１１】
2006171948.tif 000013
【００４３】
ステップＳ６は、初期値をｘＳ１とし、パラメータ化非線形代数方程式に対して連続法を用いて平衡点を探索する手順である（平衡点探索手順）。この計算は、コンピュータにより行われるものであり、連続法を用いてパラメータ化非線形代数方程式（上記の数１１）で同一パラメータａに対するｘＳ１以外の平衡点を探索する手順である。ここで得られたｘＳ１以外の平衡点の集合をＥ(ｘＳ１)とする。
【００４４】
ステップＳ７は、平衡点の安定性を評価する手順である（安定性評価手順）。先のステップ６で得られたｘＳ１以外の解の集合Ｅ(ｘＳ１)の要素であって、勾配系微分方程式(上記の数６)の平衡点についての安定性の評価を固有値計算にて行う。勾配系微分方程式(上記の数６)のヤコビアンＪを次式に示す。
【００４５】
【数１２】
2006171948.tif 000014
【００４６】
このヤコビアンＪを用いて、Ｅ(ｘＳ１)の要素である平衡点の安定性を評価する。固有値の全ての実数部が負であれば、この平行点は安定平衡点、すなわち、局所最適解である。一方固有値の全ての実数部が負でなければ、不安定平衡点とする。実数部が正である固有値がｋ個あれば、この不安定平衡点をタイプk不安定平衡点とする。特にタイプ１不安定平衡点は安定平衡点の安定境界（stability boundary）上に位置するため、分解点とよぶ。
【００４７】
ステップＳ８は、得られた平衡点が安定境界（stability boundary）上の分解点であるか否かをことを確認する手順である（確認手順）。先のステップで局所最適解に相当する安定平衡点と、それ以外のタイプk不安定平衡点が得られたが、その内のタイプ１不安定平衡点を選び、これらタイプ１不安定平衡点が本当に安定境界（stability boundary）上の分解点であるか否かを確認する。
ここで、次式で表される初期値ｘ’０を設定する。
【００４８】
【数１３】
2006171948.tif 000015
【００４９】
ここで、εは小さな正の数字、νはｘｄ１の規格化された不安定ベクトルを表す。ｘｄ１とｘＳ１との関係は、先の図８でのタイプ１不安定平衡点○と安定平衡点●との関係に相当する。この初期値ｘ’０ からの軌道がｘＳ１に収束するならば、つまりｘｄ１がｘＳ１の安定境界（stability boundary）上に位置するというものであり、分界点であることを確認することができる。
そして、これは集合Ｅ(ｘＳ１)の全ての要素について行われ、ステップ６、７で確認されたｘＳ１の安定境界（stability boundary）上の分解点を特にｘｄ１j、 j=1、…、mとする。
これらステップＳ４，５，６，７，８により分界点探索手順が終了する。
【００５０】
ステップＳ９は、安定境界上の分界点を用いて新たな局所最適解を探索する手順（新規局所最適解探索手順）である。
先にタイプ１不安定平衡点である分界点が探索されたが、これら分界点を利用する。数６の勾配系微分方程式において、不安定平衡点上にある既知の分解点ｘｄ１を用いて次式で表される初期値を設定する。
【００５１】
【数１４】
2006171948.tif 000016
【００５２】
この初期値を数６の勾配系微分方程式の初期値として勾配系微分方程式を解いて新たな安定平衡点を探索する。
【００５３】
ステップＳ１０では探索を終了するための所定条件を満たか否かについて判定し、所定条件を満たさない場合にはステップＳ４〜Ｓ９を繰り返して安定平衡点である局所最適解の探索を続ける手順（判断手順）である。ここに所定条件とは、例えば、新たな安定平衡点である局所最適解が見つからないと判断される場合や、探索に所定期間経過（例えば１日など）した場合である。これら所定条件を満たす場合には強制的に終了されるものである。このようにしてステップＳ４〜ステップＳ９までの手順が繰り返し行われ、目的関数の複数の安定平衡点とタイプ１不安定平衡点とを探索していき、最終的に、局所最適解ｘＳj、 j=1、…、ｌを求める。
【００５４】
ステップＳ１１は、複数局所最適解または大域最適解を求解する手順（最適解求解手順）である。最適解が複数局所最適解で良い場合、そのまま複数局所最適解を最適解とするが、最適解が大域最適解である場合、得られた複数局所最適解が制約条件を満たす目的関数内の全ての局所最適解であれば、次式を満たすかどうかを確認する。
【００５５】
【数１５】
2006171948.tif 000017
【００５６】
つまり、探索された全ての局所最適解を目的関数に代入して最も目的関数値が小さい局所最適解を上限値と下限値の制約条件を有する非線連続型目的関数の大域最適解ｘs、globalとする。
解探索方法はこれら手順を有するものである。
【００５７】
以上の本形態によれば、従来技術の非特許文献１では扱うことができなかった制約条件を考慮した目的関数の複数局所最適解、大域最適解を探索することができる。また、得られた複数局所最適解、大域最適解の最適性は数学的には保証される。
【００５８】
続いて、大域最適解探索装置について図を参照しつつ説明する。図２は、本形態の解探索装置の構成図である。
解探索装置は、データ処理部１、入力部２、出力部３、を備えている。データ処理部１は、さらに中央処理部１０、記憶部２０を備える。
【００５９】
データ処理部１は、例えば、コンピュータ本体であり、中央処理部１０はＣＰＵやＭＰＵに相当し、記憶部２０はメモリ・ハードディスク等の内部記憶装置に加えて、ＦＤ（Fleｘible Disc）・ＭＯ（Magnet Optical Disc）等の外部記憶装置も含める。
入力部２は、キーボードに加え、データを転送する他のコンピュータ・外部記憶装置も含める。
出力部３は、ディスプレイ・プリンタに加え、データ転送する他のコンピュータ・外部記憶装置も含める。
また、データ処理部１、入力部２、出力部３が共にコンピュータである場合には、ＬＡＮ構成を採用しても良い。
【００６０】
このような大域最適解探索装置では、中央処理部１０は、基本的には関数・条件登録手段１０１、勾配系微分方程式登録手段１０２、初回局所最適解探索手段１０３、非線形代数方程式導出手段１０４、パラメータ化非線形代数方程式導出手段１０５、平衡点探索手段１０６、安定性評価手段１０７、確認手段１０８、新規局所最適解探索手段１０９、判断手段１１０、最適解求解手段１１１として機能することで探索を行うことができる。
【００６１】
以下詳細に説明する。
中央処理部１０は、大域最適解の探索対象となる目的関数および制約条件を登録する関数・条件登録手段１０１として機能する。入力部２を操作して上記のステップＳ１の関数・条件登録手順と同様の登録を行わせる。登録した目的関数・制約条件は記憶部２０で登録する。
中央処理部１０は、目的関数から導出された勾配系微分方程式を登録する勾配系微分方程式登録手段１０２として機能する。入力部２を操作して上記のステップＳ２の勾配系微分方程式登録手順と同様の登録を行わせる。登録した目的関数は記憶部２０で登録する。
【００６２】
中央処理部１０は、任意の初期値から勾配系微分方程式を解いて始めの局所最適解を探索する初回局所最適解探索手段１０３として機能する。上記のステップＳ３の初回局所最適解探索手順と同様の探索を行わせる。これら初回局所最適解探索手段１０３により局所最適解が探索される。
中央処理部１０は、勾配系微分方程式の平衡点を表現する非線形代数方程式を登録する非線形代数方程式導出手段１０４として機能する。上記のステップＳ４の勾配系微分方程式導出手順と同様の導出・登録を行わせる。
【００６３】
中央処理部１０は、非線形代数方程式をパラメータ化したパラメータ化非線形代数方程式を登録するパラメータ化非線形代数方程式導出手段１０５として機能する。上記のステップＳ５のパラメータ化非線形代数方程式導出手順と同様の導出・登録を行わせる。
中央処理部１０は、初期値をｘＳ１とし、パラメータ化非線形代数方程式に対して連続法を用いて平衡点を導出する平衡点探索手段１０６として機能する。上記のステップＳ６の平衡点探索手順と同様に平衡点を探索する。
【００６４】
中央処理部１０は、平衡点の安定性を評価する安定性評価手段１０７として機能する。上記のステップＳ７の安定性評価手順と同様に評価する。
中央処理部１０は、得られた平衡点が安定境界上の分解点であるか否かを確認する確認手段１０８として機能する。上記のステップＳ８の確認手順と同様に確認する。
中央処理部１０は、不安定平衡点を用いて新たな局所最適解を探索する新規局所最適解探索手段１０９として機能する。上記のステップＳ９の新規局所最適解探索手順と同様に探索する。
【００６５】
中央処理部１０は、探索を終了するための所定条件を満たか否かについて判定し、所定条件を満たさない場合には新たな安定平衡点を初期値として上記の非線形代数方程式導出手段１０４、パラメータ化非線形代数方程式導出手段１０５、平衡点導出手段１０６、安定性評価手段１０７、確認手段１０８、新規局所最適解探索手段１０９を繰り返し行わせて全領域について複数の局所最適解を探索させる判断手段１１０として機能する。上記のステップＳ１０の判断手順と同様に判断する。
中央処理部１０は、複数局所最適解または大域最適解を求解する最適解求解手段１１１として機能する。上記のステップＳ１１の最適解求解手順と同様に求解する。
このような複数の局所最適解や解を大域最適解は、記憶部２０に登録された上で、出力部３（プリンタ・ディスプレイ・外部記憶装置など）へ出力され、ディスプレイ表示・印刷出力がなされる。
解探索装置はこのような装置である。
【００６６】
また、解探索プログラムは、基本的には関数・条件登録手段、勾配系微分方程式登録手段、初回局所最適解探索手段、非線形代数方程式導出手段、パラメータ化非線形代数方程式導出手段、平衡点探索手段、安定性評価手段、確認手段、新規局所最適解探索手段、判断手段、最適解求解手段としてコンピュータなどを解探索装置として機能させるプログラムである。このような解探索プログラムが記録された記録媒体（例えば、ＣＤ−ＲＯＭ、ＭＯ、ＦＤ、ＨＤというような磁気、光、光磁気により記録再生される媒体）を用いて解探索装置に解探索プログラムをインストールしてもよく、また、インターネット等のネットワーク・ＬＡＮを介して解探索装置に解探索プログラムをインストールしても良い。
以上本発明の解探索方法、解探索装置、解探索プログラムおよび記録媒体について説明した。
【実施例１】
【００６７】
続いて、具体的な目的関数と上下限制約条件による、複数局所最適解、大域最適解の探索方法の実施例について図を参照しつつ説明する。図３、図４、図５、図６、図７は解探索を説明する説明図である。なお、解探索手順は図１に沿って説明する。
この実施例では分界点・局所最適解が解るような具体的な関数および上下制約条件を決定しておき、本発明の探索法により解が求められるか否かを検証する。
【００６８】
ステップＳ１は、大域最適解の探索対象となる目的関数および制約条件を登録する手順（関数・条件登録手順）である。
本形態では、例えば、次式のような目的関数および制約条件を例に挙げて説明を具体化して説明する。目的関数および上下限制約条件は次式のようになる。
【００６９】
【数１６】
2006171948.tif 000018
【００７０】
ここで各係数は、k8 = 1/50、k7 = 17/500、k6 = -479/500、k5 = -166/125、k4 = 1888/125、k3 = 8261/500、k2 = -43299/500、k1 = -16479/250、k0 = 3078/25、p = -4、q = 3とする。このような制約条件付きの目的関数は図３に示すようになる。なお、検証用に予め求められた、上下制約条件を満たす目的関数の局所最適解は、ｘＳ１ = 1.9251、ｘＳ２ = -2.4662、ｘＳ３ = -4である。また、分解点は、ｘｄ１ = -0.3602、ｘd2 = -3.5697である。このような目的関数および制約条件を登録する。
【００７１】
ステップＳ２は上記の目的関数から勾配系微分方程式を導出し、この導出された勾配系微分方程式を登録する手順（勾配系微分方程式登録手順）である。
先の数１６の目的関数の勾配系微分方程式は、次の数１７のような方程式となる。
【００７２】
【数１７】
2006171948.tif 000019
【００７３】
ステップＳ３は任意の初期値から勾配系微分方程式を解いて始めの局所最適解を探索する手順（初回局所最適解探索手順）である。
図４に示すように、任意の初期値をｘ０=2.5とし、数１７の勾配系微分方程式を解くと、はじめの局所最適解ｘＳ１=1.9252が得られる。この局所最適解ｘＳ１における目的関数はＥ(ｘＳ１)=-76.1575となる。
【００７４】
続くステップＳ４，５，６，７，８は探索した局所最適解から分界点を探索する手順（分界点探索手順）である。詳しくは、既知の局所最適解が含まれる安定領域Ａ（stability region Ａ）の境界である安定境界∂Ａ（stability boundary ∂Ａ）上にある分解点の探索を行う。
【００７５】
ステップＳ４は、勾配系微分方程式の平衡点を表現する非線形代数方程式を導出し、この導出された勾配系微分方程式を登録する手順（勾配系微分方程式導出手順）である。
具体的には上記数１７の勾配系微分方程式の左辺をゼロとおいて、平衡点を表現する次式のような非線形代数方程式を導出する。
【００７６】
【数１８】
2006171948.tif 000020
【００７７】
ステップＳ５は、非線形代数方程式をパラメータ化してパラメータ化非線形代数方程式を導出し、この導出されたパラメータ化非線形代数方程式を登録する手順である（パラメータ化非線形代数方程式導出手順）。具体的には数１８の非線形代数方程式を展開し、ｘの０次の項(ｋ１ｐｑ)にパラメータａをかけてパラメータ化非線形代数方程式を導出する手順である。このパラメータ化非線形代数方程式は次式のように表される。
【００７８】
【数１９】
2006171948.tif 000021
【００７９】
なお、本実施例１ではｘの０次の項(ｋ１ｐｑ)にａをかけ、パラメータ化を行うものであるが、パラメータ化はこれに限定されるものではなく、他にも多くのパラメータ化手法がある。このようなパラメータ化手法は適宜選択される。
また、ａ＝１の条件における数１９のパラメータ化非線形代数方程式の解が、数１７の勾配系微分方程式の平衡点である。
【００８０】
ステップＳ６は、初期値をｘＳ１とし、パラメータ化非線形代数方程式に対して連続法を用いて平衡点を探索する手順である（平衡点探索手順）。
図５で示すように、初期値をｘＳ１＝1.9252、ａ＝1とし、連続法を用いて数１９のパラメータ化非線形代数方程式のパラメータａ＝1に対するｘＳ１以外の解を導出すると平衡点Ｅ(ｘＳ１)={-0.3602}が得られる。
【００８１】
ステップＳ７は、平衡点の安定性を評価する手順である（安定性評価手順）。先のステップ６で得られたｘＳ１以外の解の集合Ｅ(ｘＳ１)={-0.3602}の要素である、勾配系微分方程式(上記の数１７)の平衡点の安定性の評価を固有値計算にて行う。勾配系微分方程式(上記の数１７のヤコビアンＪを次式に示す。
【００８２】
【数２０】
2006171948.tif 000022
【００８３】
このヤコビアンＪを用いて、Ｅ(ｘＳ１)の要素である平衡点−0.3602の安定性を評価する。固有値は上記係数とｘに平衡点−0.3602を代入して求める。平衡点−0.3602の固有値は2258.2であり、また、固有ベクトルはv=1となる。
従って、実数部が正である固有値が１個あるため、この不安定平衡点ｘｄ１はタイプ１不安定平衡点、すなわち分解点である。
【００８４】
ステップＳ８は、得られた平衡点が安定境界上の分解点であるか否かをことを確認する手順である（確認手順）。
次式で表されるような初期値ｘ’０を設定する。
【００８５】
【数２１】
2006171948.tif 000023
【００８６】
εを0.01とすると、初期値はｘ’0=-0.3502となる。そしてεを増やして行けば軌道はｘＳ１に収束し、ｘｄ１はｘＳ１の安定境界上の分解点である。以上のステップにより、既に得られている局所最適解ｘＳ１の安定境界上にある分解点ｘｄ１の探索を行った。これを図６に示す。
これらステップＳ４，５，６，７，８により分界点探索手順が終了する。
【００８７】
ステップＳ９は、不安定平衡点を用いて新たな局所最適解を探索する手順（新規局所最適解探索手順）である。
先に分界点ｘｄ１が探索されたが、数１７の勾配系微分方程式において、既知の分解点ｘｄ１を用いて不安定平衡点上に次式で表される初期値を設定する。
【００８８】
【数２２】
2006171948.tif 000024
【００８９】
この初期値を勾配系微分方程式の初期値として勾配系微分方程式を解いて新たな安定平衡点ｘＳ２を探索する。図７に示すように、局所最適解ｘＳ２=-2.4662が得られる。この局所最適解ｘＳ２における目的関数はＥ(ｘＳ２)=-15.9978となる。
【００９０】
ステップＳ１０では探索を終了するための所定条件を満たか否かについて判定し、所定条件を満たさない場合にはステップＳ４〜Ｓ９を繰り返して安定平衡点である局所最適解の探索を続ける手順（判断手順）である。このようにしてステップＳ４〜ステップＳ９までの手順が繰り返し行われ、目的関数の複数の安定平衡点とタイプ１不安定平衡点とを探索していく。
最終的に、他の局所最適解ｘＳ３=-4を求める。
【００９１】
ステップＳ１１は、複数局所最適解または大域最適解を求解する手順（最適解求解手順）である。最終的に次表で示すような３つの局所最適解を得た。
【００９２】
【表１】
2006171948.tif 000025
【００９３】
表１の示す値が、制約条件を満たす目的関数の局所最適解の全てである。従って、ｘＳ１=1.9251が制約条件を満たす目的関数の大域最適解である。
【図面の簡単な説明】
【００９４】
【図１】本発明を実施するための最良の形態の解探索方法を説明するフローチャートである。
【図２】本発明を実施するための最良の形態の解探索装置の構成図である。
【図３】解探索を説明する説明図である。
【図４】解探索を説明する説明図である。
【図５】解探索を説明する説明図である。
【図６】解探索を説明する説明図である。
【図７】解探索を説明する説明図である。
【図８】従来技術の大域最適解探索方法におけるタイプ１不安定平衡点を探索する方法を説明する説明図である。
【符号の説明】
【００９５】
１  データ処理部
１０  中央処理部
１０１  関数・条件登録手段
１０２  勾配系微分方程式登録手段
１０３  初回局所最適解探索手段
１０４  非線形代数方程式導出手段
１０５  パラメータ化非線形代数方程式導出手段
１０６  平衡点探索手段
１０７  安定性評価手段
１０８  確認手段
１０９  新規局所最適解探索手段
１１０  判断手段
１１１  最適解求解手段
２０  記憶部
２  入力部
３  出力部
【図１】
2006171948.tif 000026
【図２】
2006171948.tif 000027
【図３】
2006171948.tif 000028
【図４】
2006171948.tif 000029
【図５】
2006171948.tif 000030
【図６】
2006171948.tif 000031
【図７】
2006171948.tif 000032
【図８】
2006171948.tif 000033