JP4178403B2 - 大域解探索装置 - Google Patents

Description

本発明は、多数の局所解の中から大域解を探索するための大域解探索装置に関する。

ある事象の最適化問題では、事象のモデルを表す目的関数を構築し、この目的関数の大域的最小値（または大域的最大値）となるような大域解を探索することで、事象の最適化を図っている。この大域解とは、目的関数にある多数の局所解（局所的な最小値または最大値）の中で最も最小または最大となる値を解とするものであり、例えば、電力系統運用の最適潮流計算、エネルギー・マネージメントシステム等の最適化手法では、大域解を探索することで省エネルギー、コストダウンに寄与する。

近年、このような最も良い解である大域解を効率的に求める手法が注目されている。
従来技術では、大域解を求める手法は決定論的方法としてトンネリング・アルゴリズムとその変種などが知られ、またメタ解法として遺伝的アルゴリズム、タブサーチ、Particle Swarm Optimization等が知られている。

上記従来技術のうち、例えば、メタ解法は短時間にできる限り良い解を求めることができるため、一般的に実用的であると言われている。しかし、高次元問題に対してメタ解法は収束性が悪くなる場合があり、局所解さえも得られない時がある。
これに対し、計算効率に問題があるものの高次元問題の大域解をシステマティックに求める手法が非特許文献１に開示されている。

この非特許文献１に開示された大域解探索方法について説明する。
ここに説明の前提として安定平衡点とは、換言すれば沈点、吸収点、シンク(sink)、アトラクタ(attractor)とも呼ばれるものであり、例えば目的関数ｃ（ｘ、ｙ）のような二次元変数に対する解曲線であるならば、解曲線の局所域での谷底の最低点に相当する。
また、タイプ２不安定平衡点とは、換言すれば、源点、湧き出し点、ソース(source)、リペラ(repellor)とも呼ばれるものであり、例えば目的関数ｃ（ｘ、ｙ）のような二次元変数に対する解曲線であるならば、解曲線の局所域での山頂の最高点に相当する。
また、タイプ１不安定平衡点とは、換言すれば、鞍点、サドル(saddle)とも呼ばれるものであり、例えば目的関数ｃ（ｘ、ｙ）のような二次元変数に対する解曲線であるならば、解曲線の局所域での山頂間の鞍部に相当する。

この大域解探索方法では目的関数の最小の大域解を求めるものとして説明する。
まず目的関数から勾配系微分方程式を導出する（勾配系微分方程式導出手順）。
次に、任意の初期値から勾配系微分方程式を解いて安定平衡点を探索する（安定平衡点探索手順）。求められた安定平衡点は目的関数の複数の局所解の中の１つであり、局所的最小値である。
次に、この安定平衡点探索手順で探索した局所的最小値のスタビリティ・バウンダリー（Stability boundary：安定境界）上にあるタイプ１不安定平衡点を、多数の任意の初期値から勾配系微分方程式をマイナス時間（０秒からマイナス無限大秒）の方向に解くことにより探索する（従来型タイプ１不安定平衡点探索手順）。
次に、この従来型タイプ１不安定平衡点探索手順で探索したタイプ１不安定平衡点の不安定固有ベクトル上の任意の点を勾配系微分方程式の初期値とし、上記の安定平衡点探索手順に戻り、次の安定平衡点を探索する（新規安定平衡点探索手順）。
以下、従来型タイプ１不安定平衡点探索手順と新規安定平衡点探索手順とを繰り返して探索した複数の局所的最小値の内、最も小さな最小値を大域的最小値とし、目的関数の大域解とする。

上記した従来技術では、従来型タイプ１不安定平衡点探索手順に特徴がある。この点について図を参照しつつ説明する。図７は従来技術の大域解探索方法におけるタイプ１不安定平衡点を探索する方法を説明する説明図である。図７において、
（１）●は、目的関数から計算した勾配系微分方程式の安定平衡点（局所的最小値の１つ）を表し、
（２）○は、安定平衡点●のスタビリティ・バウンダリー上にあるタイプ１不安定平衡点を表し、
（３）○から出ている矢印の線はタイプ１不安定平衡点の不安定多様体（もしくは安定平衡点●の安定多様体）を表し、
（４）○に向かっている矢印の線はタイプ１不安定平衡点の安定多様体を表す。

従来技術のタイプ１不安定平衡点を探索する方法では安定平衡点●を中心として、できるだけ多くの近傍点（図７の＋）の初期値を設定し、これら全部の初期値について勾配系微分方程式をマイナス時間方向に積分することによりタイプ１不安定平衡点○を試行錯誤的（総当たり的）に探索していた。

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: Fundamental Theory and Applications,

従来技術の大域解探索方法では、特にタイプ１不安定平衡点を探索する方法に関し、以下の２つの課題があった。
（課題１）図７の＋で示す様に勾配系微分方程式を解く初期値は安定平衡点●付近の任意の近傍点（例えば、図７では円（ε−ｂａｌｌ）上にある点）としている。従って、目的関数の状態量が高次となると設定する初期値の数は多くなる。例えば三次元では球（ε−ｂａｌｌ）上にある点となり、初期値の数が増大する。また、微分方程式の解がタイプ１不安定平衡点に到達する場合は、少なくとも設定した初期値の１つはタイプ１不安定平衡点の不安定多様体上に設定される必要があるが、初期値をうまく設定しないと不安定多様体上から外れて、タイプ１不安定平衡点に到達しない。
（課題２）仮に多くの初期値の中の１つがタイプ１不安定平衡点の不安定多様体上に設定された場合においても、その積分の過程で積分のステップ時間の幅により積分値は不安定多様体上から外れ、積分の結果がタイプ１不安定平衡点に到達できないことがある。
総じて、タイプ１不安定平衡点の探索が難しく、この点で大域解の探索出に時間を要するという問題点がある。

この発明は上記課題を解決するためになされたものであり、その目的は、安定平衡点からタイプ１不安定平衡点への探索と、また、このタイプ１不安定平衡点から新規な安定平衡点への探索を順次交互に行って多数の安定平衡点を効率よく探索して目的関数の大域解を求めるような大域解探索装置を提供することにある。

本発明の大域解探索装置は、
中央処理部と、中央処理部に接続される記憶部と、中央処理部に接続される入力部と、中央処理部に接続される出力部と、を有し、大域解の探索対象となる目的関数、および、この目的関数から導出された勾配系微分方程式を用いて大域解を探索する大域解探索装置であって、
中央処理部は、
入力部からの操作により、任意の定数・変数・次数を設定し、関数を選択して組み合わせ、または、予め登録された関数を選択して、大域解の探索対象となる目的関数を登録する目的関数登録手段と、
入力部からの操作により、任意の定数・変数・次数を設定し、または、予め登録された関数を選択して、登録された目的関数のパラメータ付けされた勾配系微分方程式を登録する勾配系微分方程式登録手段と、
任意の初期値を代入して勾配系微分方程式を解き、以下得られた解を代入して勾配系微分方程式を解いていき局所的に最小の解である安定平衡点を探索する初回安定平衡点探索手段と、
勾配系微分方程式の一の定数をパラメータとし、パラメータ付けされた勾配系微分方程式に対して探索した安定平衡点を初期値として代入して勾配系微分方程式のパラメータを変動させて平衡点をトレースさせていく連続法により他の平衡点を探索し、勾配系微分方程式のヤコビアンに対してこの探索した平衡点およびパラメータを代入し、この探索した平衡点における勾配系微分方程式のヤコビアンの固有値を算出し、これら固有値のうち１つの固有値の実数部がマイナスである平衡点をタイプ１不安定平衡点とし、このようなタイプ１不安定平衡点を探す探索を、全ての定数について行うタイプ１不安定平衡点探索手段と、
タイプ１不安定平衡点を始点とする２つの不安定固有ベクトル上の任意の点にある値を勾配系微分方程式の初期値として代入して勾配系微分方程式を解き、以下得られた解を代入して勾配系微分方程式を解いていき局所的に最小の解である新たな安定平衡点を探索する新規安定平衡点探索手段と、
探索開始から所定期間が経過したか否かを判断し、所定期間が経過していない場合は新たな安定平衡点を初期値として上記のタイプ１不安定平衡点探索手段と新規安定平衡点探索手段とを交互に繰り返し機能させて安定平衡点を探索させる判断手段と、
探索された全ての安定平衡点の値を目的関数に代入して最小の解を大域解とする大域解探索手段と、
大域解を記憶部に登録して出力部により出力させる出力手段と、
からなることを特徴とする。

以上のような本発明によれば、安定平衡点からタイプ１不安定平衡点への探索と、また、このタイプ１不安定平衡点から新規な安定平衡点への探索を順次交互に行って多数の安定平衡点を効率よく探索して目的関数の大域解を求めるような大域解探索装置を提供することができる。

以下、本発明を実施するための最良の形態の大域解探索装置について説明する。また、大域解探索方法、大域解探索プログラム、および、記録媒体についても説明する。
まず、大域解探索方法について図を参照しつつ説明する。図１は本形態の大域解探索方法を説明するフローチャートである。この大域解探索方法は、コンピュータを用いて実現される。大域解探索方法では、大域的に多数の局所的最小値を多数有するような目的関数の中で最小値を決定する大域的最小値探索、また、大域的に多数の局所的最大値を多数有するような目的関数の中で最大値を決定する大域的最大値探索があるが、本形態では大域的最小値探索を説明する。

ステップＳ１は、大域解の探索対象となる目的関数を登録する手順（目的関数登録手順）である。
コンピュータに対し、例えば、任意の定数・変数・次数の設定や関数を選択して組み合わせたり、あるいは、予め登録された関数を選択するなどして、今回使用する目的関数を登録する。
本形態では説明の具体化により理解を容易にするため、例えば、次式数１のような目的関数（１）を例に挙げて説明する。

ここで、各定数ａ〜ｆは、具体的にはａ＝４，ｂ＝−２．１，ｃ＝１／３，ｄ＝−４，ｅ＝４，ｆ＝１である。

ステップＳ２は上記の目的関数からパラメータ付けされた勾配系微分方程式を導出し、この導出された勾配系微分方程式を登録する手順（勾配系微分方程式登録手順）である。
この場合もコンピュータに対し、例えば、任意の定数・変数・次数を設定したり、あるいは、予め登録された関数を選択するなどして、今回使用できる勾配系微分方程式を登録する。
先の目的関数（１）の勾配系微分方程式は、次の数２のような方程式となる。

ステップＳ３は任意の初期値から勾配系微分方程式を解いて安定平衡点を探索する手順（初回安定平衡点探索手順）である。
この手順では、ｘ、ｙに初期値を与えて所定増減量でｘ、ｙの値を変化させて上記の勾配系微分方程式（２．１）式および（２．２）式をそれぞれ解き、充分時間が経過した後の最終値の点、つまり安定平衡点へ収束させるような手順である。勾配系微分方程式では、任意の初期値から出発した解軌道は安定平衡点に必ず収束する。この安定平衡点は目的関数のいずれかの局所的最小値（谷底）に相当する。

この勾配系微分方程式の解が安定平衡点へ収束していく挙動を図２の初期値から安定平衡点への探索を示すＸ−Ｙ平面図を用いて説明する。この初期値は任意であるが、例えば、本形態では（０．５， ０．５）に設定して、勾配系微分方程式を解くと、解軌道は、充分に時間が経過した後では図２で示すように、ｚ_Ｓ ^１＝（０．０８９８， ０．７１２７）に収束していく。安定平衡点であるｚ_Ｓ ^１は、目的関数（１）の局所的最小値の１つである。

続いて、ステップＳ４〜Ｓ７で勾配系微分方程式に対してこの安定平衡点を初期値として連続法により探索した平衡点のうち１つの固有値の実数部がマイナスである平衡点をタイプ１不安定平衡点とする手順（タイプ１不安定平衡点探索手順）を行う。
まずステップＳ４では勾配系微分方程式の一の定数をパラメータと仮定する手順（パラメータ仮定手順）を行う。ここでは、まず、ｂ〜ｆは定数として固定したまま、定数ａをパラメータと仮定する。

続いて、ステップＳ５ではパラメータ付けされた勾配系微分方程式に対して、ステップＳ３で探索した安定平衡点を初期値として連続法により他の平衡点を探索する手順（平衡点探索手順）を行う。ここで平衡点としたのは、探索直後では安定平衡点か、タイプ１不安定平衡点か、タイプ２不安定平衡点かが不明なためである。
連続法では平衡点を初期値とし、パラメータを変動させて平衡点をトレースさせていくものである。トレースについて図を参照しつつ説明する。図３Ａはパラメータａに対するｘの動きを示す図、図３Ｂはパラメータａに対するｙの動きを示す図である。図３Ａ，図３Ｂで示すように、先のステップ３（初回安定平衡点探索手順）で求めた安定平衡点（局所的最小値の１つ）であるｚ_Ｓ ^１＝（０．０８９８，０．７１２７）を初期値とし、また、パラメータａの初期値を４とする。
図３Ａ，図３Ｂで示すように、パラメータａの値を変えると、目的関数（１）を０にする値も変化していき、このような解をプロットしていくものである。そしてａ＝４の時に０となる他のｘ、ｙがある場合には、他の平衡点を探索したこととなる。連続法によりａ＝４において、平衡点ｚ_ｄ ^１＝（１．１０９２， ０．７６８３）， 平衡点ｚ_Ｓ ^２＝（１．７０３６， ０．７９６１）が探索された。

続いて、ステップＳ６では、探索した平衡点の固有値を算出し、この固有値からタイプ１不安定平衡点であるか否かを、探索の結果得られた全ての平衡点について判断する手順（平衡点判断手順）である。
例えば、探索された平衡点ｚ_ｄ ^１＝（１．１０９２， ０．７６８３）， 平衡点ｚ_Ｓ ^２＝（１．７０３６， ０．７９６１）の場合、勾配系微分方程式（２．１）（２．２）のヤコビアンを用いて固有値を算出する。ヤコビアンは次の数３のようになる。

このヤコビアン（３）にａ〜ｆの値および平衡点ｚ_ｄ ^１、または、ａ〜ｆの値および平衡点ｚ_Ｓ ^２を代入すると、それぞれ数値であらわされる行列となる。このような行列に周知の方法で固有値、固有ベクトルを算出できる。ここに全ての固有値の実数部がマイナスである平衡点は安定平衡点であり、全ての固有値の実数部がプラスである平衡点はタイプ２不安定平衡点であり、固有値の実数部の一つがマイナスである平衡点はタイプ１不安定平衡点であると判断できる。先に探索したｚ_ｄ ^１、または、ｚ_Ｓ ^２の固有値、固有ベクトルは以下のように判断される。

（ａ）ｚ_ｄ ^１の固有値と固有ベクトル
固有値７．９０２６、固有値−２０．３６９１であり、タイプ１不安定平衡点である。
固有値７．９０２６に対応する固有ベクトル（−０．９９９４，−０．０３５４）となり、また、固有値−２０．３６９１に対応する固有ベクトル（０．０３５４， −０．９９９４）となる。

（ｂ）ｚ_Ｓ ^２の固有値と固有ベクトル
固有値−１８．８１６５、固有値−２２．６９８６であり、安定平衡点である。
固有値−１８．８１６５に対応する固有ベクトル（−０．９６３６，−０．２６７３）であり、また、固有値−２２．６９８６に対応する固有ベクトル（０．２６７３，−０．９６３６）である。
このようにステップＳ４〜ステップＳ６で一のパラメータについて平衡点の探索が行われる。

ステップＳ７は全ての定数をパラメータとして連続法による平衡点の探索を行ったかを判断する手順（パラメータ判断手順）である。連続法により平衡点探索が行われていない場合には残る定数ｂ〜ｆそれぞれについて同様にステップＳ４〜ステップＳ６が繰り返し行われてそれぞれ連続法により平衡点が探索されて、一の安定平衡点についてパラメータ依存性により依存する他の全ての平衡点を探索する。そして、探索された平衡点は固有値により安定平衡点、タイプ１不安定平衡点、タイプ２不安定平衡点であるか否かについて判断される。ステップＳ４〜ステップＳ７により全てのパラメータについて連続法による平衡点の探索を行った結果を、表１，図４にそれぞれ示す。表１は平衡点の探索結果であり、図４は探索途中の安定平衡点とタイプ１不安定平衡点を示すＸ−Ｙ平面図である。図４において、●は安定平衡点、○はタイプ１不安定平衡点を示す。

ここに、
ode：パラメータ付けされた勾配系微分方程式を解く。Ordinary Differential Equationの略である。
cm：連続法を解く。Continuation Methodの略である。
また、タイプ２不安定平衡点は連続法による平衡点の探索の結果得られるが、探索方法には直接関係無い。
このようにステップＳ４〜ステップＳ７の手順を行うことにより、タイプ１不安定平衡点ｚ_ｄ ^１ ，ｚ_ｄ ^３ ，ｚ_ｄ ^６ ，ｚ_ｄ ^７ が探索された。また、これ以外に安定平衡点ｚ_Ｓ ^１ ，ｚ_Ｓ ^２ ，ｚ_Ｓ ^３ も探索された。このうちタイプ１不安定平衡点を利用する。

続いて、ステップＳ８はタイプ１不安定平衡点を始点とする２つの不安定固有ベクトル上の任意の点にある値を勾配系微分方程式の初期値として勾配系微分方程式を解いて新たな安定平衡点を探索する手順（新規安定平衡点探索手順）である。
タイプ１不安定平衡点ｚ_ｄ ^１＝（１．１０９２， ０．７６８３）を例にとると、２つの初期値ｚ_０ ^１は下式により算出される。

ここで、不安定固有ベクトルは固有値がプラスの固有ベクトルであり、ν_ｄ ^１＝（−０．９９９４， −０．０３５４）はｚ_ｄ ^１の不安定固有ベクトル、εは任意の小さな値（ここではε＝０．０１）である。
この手順ではｘ、ｙに初期値ｚ_０ ^１を与えて所定増減量でｘ、ｙの値を変化させて上記の勾配系微分方程式（２．１）式（２．２）式を解き、充分時間が経過した後の最終値の点、つまり安定平衡点へ収束させる。
以上、ステップＳ９では探索を終了するための所定条件を満たか否かについて判定し、所定条件を満たさない場合にはステップＳ４〜Ｓ８を繰り返して安定平衡点の探索を続ける手順（判断手順）である。ここに所定条件とは、例えば、新たな安定平衡点が見つからないと判断される場合や、探索に所定期間経過（例えば１日など）した場合である。これら所定条件を満たす場合には強制的に終了されるものである。このようにしてステップＳ４〜ステップＳ９までの手順が繰り返し行われ、目的関数（１）の複数の安定平衡点とタイプ１不安定平衡点とを交互に探索していく。目的関数（１）の場合の全部の探索結果を表２，図５に示す。表２は平衡点の探索結果であり、図５は探索終了時の安定平衡点とタイプ１不安定平衡点を示すＸ−Ｙ平面図である。図５において、●は安定平衡点、○はタイプ１不安定平衡点を示す。

ステップＳ１０は探索された全ての安定平衡点の値を目的関数に代入して最小または最大の解を大域解とする手順（大域解探索手順）である。表３に目的関数(1)の局所的最小値と目的関数値を示す。

表３からも明らかなように目的関数(1)の大域的最小値はｚ_ｓ ^１＝（０．０８９８， ０．７１２７）及びｚ_ｓ ^３＝（−０．０８９８， −０．７１２７）のときの−１．０３１６である。本手順では、このようにして大域的最小値を選択し、大域解とする。
大域解探索方法はこれら手順を有するものである。

続いて、大域解探索装置について図を参照しつつ説明する。図６は、本形態の大域解探索装置の構成図である。
大域解探索装置は、データ処理部１、入力部２、出力部３、を備えている。データ処理部１は、さらに中央処理部１０、記憶部２０を備える。

データ処理部１は、例えば、コンピュータ本体であり、中央処理部１０はＭＰＵに相当し、記憶部２０はメモリ・ハードディスク等の内部記憶装置に加えて、ＦＤ（Flexible Disc）・ＭＯ（Magnet Optical Disc）等の外部記憶装置も含める。
入力部２は、キーボードに加え、データを転送する他のコンピュータ・外部記憶装置も含める。
出力部３は、ディスプレイ・プリンタに加え、データ転送する他のコンピュータ・外部記憶装置も含める。
また、データ処理部１、入力部２、出力部３が共にコンピュータである場合には、ＬＡＮ構成を採用しても良い。

このような大域解探索装置では、中央処理部１０は、基本的には初回安定平衡点探索手段１１、タイプ１不安定平衡点探索手段１２、新規安定平衡点探索手段１３、判断手段１４、大域解探索手段１５として機能することで探索を行うことができる。

以下詳細に説明する。
中央処理部１０は、大域解の探索対象となる目的関数を登録する目的関数登録手段として機能する。入力部２を操作して上記のステップＳ１の目的関数登録手順と同様の登録を行わせる。登録した目的関数は記憶部２０で登録する。
中央処理部１０は、目的関数からパラメータ付けされた勾配系微分方程式を導出し、この導出された勾配系微分方程式を登録する勾配系微分方程式手段として機能する。入力部２を操作して上記のステップＳ２の勾配系微分方程式登録手順と同様の登録を行わせる。登録した目的関数は記憶部２０で登録する。

中央処理部１０は、任意の初期値から勾配系微分方程式を解いて安定平衡点を探索する手段（初回安定平衡点探索手段１１）として機能する。上記のステップＳ３の初回安定平衡点探索手順と同様の探索を行わせる。
これら初回安定平衡点探索手段１１により安定平衡点が探索される。
中央処理部１０は、勾配系微分方程式に対して安定平衡点を初期値として連続法により探索した平衡点のうち１つの固有値の実数部がマイナスである平衡点をタイプ１不安定平衡点とする手段（タイプ１不安定平衡点探索手段１２）として機能する。
詳しくは上記のステップＳ４のパラメータ仮定手順と同様のパラメータ仮定手段（勾配系微分方程式の一の定数をパラメータと仮定する手段）として機能する。
そして、上記のステップＳ５の平衡点探索手順と同様の平衡点探索手段（パラメータ付けされた勾配系微分方程式に対して、探索した安定平衡点を初期値として連続法により他の平衡点を探索する手段）として機能する。
そして、上記のステップＳ６の平衡点判断手順と同様の平衡点判断手段（探索した平衡点の固有値を算出し、この固有値からタイプ１不安定平衡点であるか否かを、全ての平衡点について判断する手段）として機能する。
そして、上記のステップＳ７のパラメータ判断手順と同様のパラメータ判断手段（全ての定数をパラメータとして連続法による平衡点の探索を行ったかを判断する手段）として機能する。
これらタイプ１不安定平衡点探索手段１２によりタイプ１不安定平衡点が探索される。

続いて、中央処理部１０は、上記のステップＳ８の新規安定平衡点探索手順と同様の新規安定平衡点探索手段（タイプ１不安定平衡点を始点とする２つの不安定固有ベクトル上の任意の点にある値を勾配系微分方程式の初期値として勾配系微分方程式を解いて新たな安定平衡点を探索する手段）１３として機能する。
続いて、中央処理部１０は、上記のステップＳ９の判断手順と同様の判断手段（探索を終了するための所定条件を満たか否かについて判定し、所定条件を満たさない場合にはステップＳ４〜Ｓ８を繰り返して安定平衡点の探索を続ける手段）１４として機能する。
続いて、中央処理部１０は、上記のステップＳ１０の大域解探索手順と同様の大域解探索手段（探索された全ての安定平衡点の値を目的関数に代入して最小または最大の解を大域解とする手段）１５として機能する。大域解は、記憶部２０に登録された上で、出力部３（プリンタ・ディスプレイ・外部記憶装置など）へ出力され、ディスプレイ表示・印刷出力がなされる。
大域解探索装置はこのような装置である。

また、大域解探索プログラムは、上記の初回安定平衡点探索手段、タイプ１不安定平衡点探索手段、新規安定平衡点探索手段、判断手段、および、大域解探索手段としてコンピュータなどを大域解探索装置として機能させるプログラムである。このような大域解探索プログラムが記録された記録媒体（例えば、ＣＤ−ＲＯＭ，ＭＯ，ＦＤ，ＨＤというような磁気，光，光磁気により記録再生される媒体）を用いて大域解探索装置に大域解探索プログラムをインストールしてもよく、また、インターネット等のネットワーク・ＬＡＮ７を介して大域解探索装置に大域解探索プログラムをインストールしても良い。

以上本発明の大域解探索装置について説明した。また、大域解探索方法、大域解探索プログラム、および、記録媒体についても説明した。本発明では二次元関数について説明したが、安定平衡点とを交安定平衡点からタイプ１不安定平衡点への探索と、また、このタイプ１不安定平衡点から新規な安定平衡点への探索とは、従来技術のように総当たり的な探索とならずに、探索が確実に行われるため、高次元である場合には特に探索時間を短縮できるという利点がある。
また、本発明の大域解探索装置に関し、探索される大域解は大域的最小値であるものとして説明した。しかしながら、大域解が大域的最大値である場合にも同様にして解くことができる。目的関数と勾配系微分方程式にマイナスを掛ければ大域的最小値を探索することに帰着するためである。このように本発明では大域的最大値を探索することもできる。

本発明を実施するための最良の形態の大域解探索方法を説明するフローチャートである。 初期値から安定平衡点への探索を示すＸ−Ｙ平面図である。 パラメータａに対するｘの動きを示す図である。 パラメータａに対するｙの動きを示す図である。 探索途中の安定平衡点とタイプ１不安定平衡点を示すＸ−Ｙ平面図である。 探索終了時の安定平衡点とタイプ１不安定平衡点を示すＸ−Ｙ平面図である。 本発明を実施するための最良の形態の大域解探索装置の構成図である。 従来技術の大域解探索方法におけるタイプ１不安定平衡点を探索する方法を説明する説明図である。

符号の説明

１ データ処理部
１０ 中央処理部
１１ 初回安定平衡点探索手段
１２ タイプ１不安定平衡点探索手段
１３ 新規安定平衡点探索手段
１４ 判断手段
１５ 大域解探索手段
２０ 記憶部
２ 入力部
３ 出力部

Claims (1)

1. 中央処理部と、中央処理部に接続される記憶部と、中央処理部に接続される入力部と、中央処理部に接続される出力部と、を有し、大域解の探索対象となる目的関数、および、この目的関数から導出された勾配系微分方程式を用いて大域解を探索する大域解探索装置であって、
   中央処理部は、
   入力部からの操作により、任意の定数・変数・次数を設定し、関数を選択して組み合わせ、または、予め登録された関数を選択して、大域解の探索対象となる目的関数を登録する目的関数登録手段と、
   入力部からの操作により、任意の定数・変数・次数を設定し、または、予め登録された関数を選択して、登録された目的関数のパラメータ付けされた勾配系微分方程式を登録する勾配系微分方程式登録手段と、
   任意の初期値を代入して勾配系微分方程式を解き、以下得られた解を代入して勾配系微分方程式を解いていき局所的に最小の解である安定平衡点を探索する初回安定平衡点探索手段と、
   勾配系微分方程式の一の定数をパラメータとし、パラメータ付けされた勾配系微分方程式に対して探索した安定平衡点を初期値として代入して勾配系微分方程式のパラメータを変動させて平衡点をトレースさせていく連続法により他の平衡点を探索し、勾配系微分方程式のヤコビアンに対してこの探索した平衡点およびパラメータを代入し、この探索した平衡点における勾配系微分方程式のヤコビアンの固有値を算出し、これら固有値のうち１つの固有値の実数部がマイナスである平衡点をタイプ１不安定平衡点とし、このようなタイプ１不安定平衡点を探す探索を、全ての定数について行うタイプ１不安定平衡点探索手段と、
   タイプ１不安定平衡点を始点とする２つの不安定固有ベクトル上の任意の点にある値を勾配系微分方程式の初期値として代入して勾配系微分方程式を解き、以下得られた解を代入して勾配系微分方程式を解いていき局所的に最小の解である新たな安定平衡点を探索する新規安定平衡点探索手段と、
   探索開始から所定期間が経過したか否かを判断し、所定期間が経過していない場合は新たな安定平衡点を初期値として上記のタイプ１不安定平衡点探索手段と新規安定平衡点探索手段とを交互に繰り返し機能させて安定平衡点を探索させる判断手段と、
   探索された全ての安定平衡点の値を目的関数に代入して最小の解を大域解とする大域解探索手段と、
   大域解を記憶部に登録して出力部により出力させる出力手段と、
   からなることを特徴とする大域解探索装置。

Images