(57)【特許請求の範囲】
【請求項１】
システムをモデル化する目標関数のｎ個の設計パラメータのパフォーマンスがｎ次元のサーチ空間を表現しており、（ｎ＋１）個の頂点の集合が前記サーチ空間に配置され、各頂点が前記パフォーマンスの１つに関連している前記システムを最適化するための方法であって、
前記集合内の各頂点の情報が、コンピュータ装置のメモリに格納されており、
各頂点の前記情報は、前記サーチ空間における当該頂点の第１の位置と、前記第１の位置におけるパフォーマンスとを含んでおり、
前記コンピュータ装置が、前記メモリに格納されたパフォーマンスに基づいて、前記集合内の頂点を最悪から最良のパフォーマンスに向かう順序でソートする工程と、
前記コンピュータ装置が、前記集合内の各頂点に関し、当該頂点の前記第１の位置におけるパフォーマンスよりも第２の位置におけるパフォーマンスが良好である場合には、前記当該頂点を前記第２の位置に試行移動する工程であって、前記試行移動は、前記メモリに格納された当該頂点の前記第１の位置を前記第２の位置に置き換えることと、前記メモリに格納された当該頂点の前記第１の位置におけるパフォーマンスを前記第２の位置におけるパフォーマンスに置き換えることとを含む、工程と、
前記コンピュータ装置が、終了条件に達するまで前記ソートする工程と前記試行移動する工程とをサイクルとして繰り返す工程と、を含むことを特徴とするシステムの最適化方法。
【請求項２】
請求項１に記載のシステムの最適化方法において、更に、前記コンピュータ装置が、試行移動対象の頂点を除いた集合に属する総ての頂点の重心を求め、前記重心を通して前記試行移動対象の頂点を反映させて該頂点の第２の位置を決定する工程を含むことを特徴とするシステムの最適化方法。
【請求項３】
請求項２に記載のシステムの最適化方法において、更に、前記コンピュータ装置が、前記試行移動対象の頂点の前記重心までの距離に、頂点の集合の空間エクステントを増加させる拡張係数を乗算する工程を含むことを特徴とするシステムの最適化方法。
【請求項４】
請求項１に記載のシステムの最適化方法において、更に、前記コンピュータ装置が、集合内の特定の頂点のパフォーマンスが最良のパフォーマンスである場合に該特定の頂点を最良の頂点とする工程を含むことを特徴とするシステムの最適化方法。
【請求項５】
請求項４に記載のシステムの最適化方法において、前記コンピュータ装置が、前記最良のパフォーマンスを有する頂点を前記重心から離れる方向に試行移動する工程を含むことを特徴とするシステムの最適化方法。
【請求項６】
請求項５に記載のシステムの最適化方法において、頂点を試行移動する距離が、該頂点から前記重心までの距離に拡張係数を乗じた距離に等しいことを特徴とするシステムの最適化方法。
【請求項７】
請求項１に記載のシステムの最適化方法において、更に、前記コンピュータ装置が、前記サーチ空間内の第１の頂点を任意の座標に位置付け、前記頂点の各座標を相応のステップサイズで増分して次の頂点の位置を決定し、前記集合の（ｎ＋１）個総ての頂点が前記サーチ空間内に位置付けるまで前記増分ステップを繰り返す工程を含むことを特徴とするシステムの最適化方法。
【請求項８】
請求項７に記載のシステムの最適化方法において、前記ステップサイズが対応の座標の対応の次元に比例することを特徴とするシステムの最適化方法。
【請求項９】
請求項４に記載のシステムの最適化方法において、更に、前記コンピュータ装置が、前記最良の頂点のパフォーマンスが前記サイクル中不変である場合に、前記最良の頂点以外の集合内の各頂点を前記最良の頂点に向かって試行移動する工程を含むことを特徴とするシステムの最適化方法。
【請求項１０】
請求項９に記載のシステムの最適化方法において、前記コンピュータ装置が、特定の頂点が移動する距離を、該特定の頂点から最良の頂点までの距離に収縮係数を乗じたものに等しくして頂点集合の空間エクステントを減少する工程を含むことを特徴とするシステムの最適化方法。
【請求項１１】
請求項１に記載のシステムの最適化方法において、更に、前記コンピュータ装置が、特定の頂点のパフォーマンスが最良のパフォーマンスである場合で且つ、該最良の頂点のパフォーマンスが予め定められた数の連続サイクルに亙って不変である場合に、該特定の頂点を最良の頂点とし、前記最良の頂点を除いて総ての頂点を削除し、前記最良の頂点の各座標を対応の現在のサイズで増分して次の頂点の位置を求め、前記集合の（ｎ＋１）個総ての頂点がサーチ空間内で再配置されるまで前記増分ステップを繰り返す工程を含むことを特徴とするシステムの最適化方法。
【請求項１２】
請求項１のシステムの最適化方法において、更に、前記コンピュータ装置が、サーチ空間における次元の数が予め定められた数よりも大きい場合に前記集合内の頂点の数を増加する工程を含むことを特徴とするシステムの最適化方法。
【請求項１３】
請求項１に記載のシステムの最適化方法において、該システムが更に複数の制約条件を有する場合に、更に、前記コンピュータ装置が、前記制約条件及び目標関数を、該目標関数を含むグループが最高のレベルを有するようにして複数個の一意的階層レベルに従いグループ化し、前記制約条件及び目標関数のグループ化に従い低レベルから高レベルの順序で特定の頂点のパフォーマンスを評価し、関連のレベルが最高レベルでない場合には評価されたパフォーマンスが負になると直ちに評価されたパフォーマンス及び関連のレベルを前記特定の頂点に割当て、その場合に、割当てられたパフォーマンスを前記目標関数で評価して前記サーチ空間を前記レベルに従い複数の区分に区分化する工程を含むことを特徴とするシステムの最適化方法。
【請求項１４】
請求項１３に記載のシステムの最適化方法において、更に、前記コンピュータ装置が、特定の区分内の特定の頂点のパフォーマンスが一層良好になる場合にのみ、該特定の区分内で該特定の頂点をパフォーマンスが一層良好になるように試行移動する工程を含むことを特徴とするシステムの最適化方法。
【請求項１５】
請求項１３に記載のシステムの最適化方法において、更に、前記コンピュータ装置が、各区分において特定の頂点が最良のパフォーマンスを有する場合に、該区分内の該特定の頂点を当該区分内の最良の頂点とし、各区分内の特定の頂点が最悪のパフォーマンスを有する場合に、該区分内の当該特定頂点を当該区分における最悪の頂点とする工程を含むことを特徴とするシステムの最適化方法。
【請求項１６】
請求項１５に記載のシステムの最適化方法において、更に、前記コンピュータ装置が、特定の頂点が高いレベルの区分内で最良の頂点となる場合にのみ、前記特定の頂点を低レベルの特定の区分から前記高レベルの区分に試行移動する工程を含むことを特徴とするシステムの最適化方法。
【請求項１７】
請求項１５に記載のシステムの最適化方法において、更に、前記コンピュータ装置が、特定の頂点のパフォーマンスが低レベルの区分内の最悪の頂点よりも良好である場合にのみ、該特定の頂点を、高レベルの特定の区分から前記低レベルの区分に試行移動する工程を含むことを特徴とするシステムの最適化方法。
【請求項１８】
請求項１３に記載のシステムの最適化方法において、更に、前記コンピュータ装置が、特定の頂点が任意の頂点の最良のパフォーマンスを有する場合に、該特定の頂点を総合的に最良の頂点とし、特定の頂点が任意の頂点の最悪のパフォーマンスを有する場合に、該特定の頂点を総合的に最悪の頂点とする工程を含むことを特徴とするシステムの最適化方法。
【請求項１９】
請求項１８に記載のシステムの最適化方法において、更に、前記コンピュータ装置が、特定の頂点が前記総合的に最良の頂点となる場合にのみ、該特定の頂点を低レベルの特定の区分から高レベルの区分に試行移動する工程を含むことを特徴とするシステムの最適化方法。
【請求項２０】
請求項１８に記載のシステムの最適化方法において、更に、前記コンピュータ装置が、特定の頂点のパフォーマンスが前記総合的に最悪の頂点よりも良好になる場合にのみ、特定の頂点を高レベルの特定の区分から低レベルの区分に試行移動する工程を含むことを特徴とするシステムの最適化方法。
【請求項２１】
請求項１３、１４、１５、１６、１７、１８、１９及び２０の何れかに記載のシステムの最適化方法において、前記区分が、独立のパフォーマンスを有する独立の制約された区分と、従属パフォーマンスを有する従属の制約された区分と、制約されていないパフォーマンスを有する制約されていない区分とを含むことを特徴とするシステムの最適化方法。
【請求項２２】
請求項１に記載のシステムの最適化方法において、更に、前記コンピュータ装置が、前記制約条件及び目標関数を、該目標関数を含むグループが最高のレベルを有するようにして複数個の一意的階層レベルに従いグループ化し、前記制約条件及び目標関数のグループ化に従い低レベルから高レベルの順序で特定の頂点のパフォーマンスを評価し、関連のレベルが最高レベルでない場合に評価されたパフォーマンスが負になると直ちに該評価されたパフォーマンス及び関連のレベルを前記特定の頂点に割当て、その場合に、割当てられたパフォーマンスを前記目標関数で評価して前記サーチ空間を前記レベルに従い複数の区分に区分化し、集合内の特定の頂点のパフォーマンスが最良のパフォーマンスである場合に該特定の頂点を最良の頂点とし、前記最良の頂点のパフォーマンスが前記サイクル中不変である場合に、前記最良の頂点を除き該最良の頂点と同じレベルにある各頂点を前記最良の頂点に向かって試行移動し、前記最良の頂点のパフォーマンスが前記サイクル中不変である場合に、前記最良の頂点のレベルよりも低いレベルにある集合内の各頂点を、前記最良の頂点を経て反映する工程を含むことを特徴とするシステムの最適化方法。
【請求項２３】
請求項２２に記載のシステムの最適化方法において、前記コンピュータ装置が、各頂点が試行移動され反映される距離に収縮係数を乗じて、頂点集合の空間エクステントを減少する工程を含むことを特徴とするシステムの最適化方法。
【請求項２４】
請求項１３に記載のシステムの最適化方法において、更に、前記コンピュータ装置が、頂点の試行移動中、グループ化及びレベルを動的に変更する工程を含むことを特徴とするシステムの最適化方法。
【請求項２５】
請求項１３に記載のシステムの最適化方法において、前記コンピュータ装置が、第１及び第２の位置における各頂点のパフォーマンス並びに制御パラメータに基づく関連の合格確率を各試行移動に対して求める工程を含むことを特徴とするシステムの最適化方法。
【請求項２６】
請求項１３に記載のシステムの最適化方法において、更に、前記コンピュータ装置が、試行移動対象の頂点を除き集合内の総ての頂点並びに該試行移動対象の頂点のレベルよりも低いレベルを有する頂点の重心を求め、前記試行移動対象の頂点を前記重心を経て反映して該頂点の第２の位置を求める工程を含むことを特徴とするシステムの最適化方法。
【発明の詳細な説明】
【０００１】
【発明の技術分野】
本発明は、一般に、複雑なシステムもしくは複雑系（以降、便宜上複雑系システムとも称する）を最適化する方法に係わり、特に、制約下にある連続した複雑系システムの最適化方法に関する。
【０００２】
【発明の背景】
発電プラント或るいは化学プラントのような複雑な物理系システムにおいては、例えば、費用、利益、生成物、廃棄物、品質及び効率のような種々な属性量を目標関数Ｆ（ｘ）によりモデル化することが可能である。ここで、ｘは該目標関数のパフォーマンスもしくは出力（振舞い、性能、挙動等の意味を包含する）を決定する設計パラメータ（入力パラメータ）を表す。これ等設計パラメータは探索空間、即ちサーチ空間を定義し、該サーチ空間において各設計パラメータｘに具体的な値を設定することによりそれぞれ対応のパフォーマンスが実現される。
【０００３】
複雑系システムのパフォーマンスの最適化は望ましいことであり、この最適化は、上記サーチ空間において最適なパフォーマンスを示す箇所を探知することにより実現可能である。ここで、最適化とは、典型例として、廃棄物を最小にし、生成物、品質及び効率を最大化することを意味する。
【０００４】
工学的複雑さに起因して、設計パラメータはまた制約関数Ｃ（ｘ）と称する物理的に顕現し得る制限もしくは制約条件に順応しなければならない場合があり、ここで、該制約関数は、上述の目標関数に従属することもあれば、また、目標関数から独立している場合もある。或る設計パラメータに対しては、パフォーマンスに関し実効解を得ることができないこともある。
【０００５】
多くの複雑な物理系システムにおいては、目標関数及び制約関数は非線形であって、微分不可能であり且つノイズを伴う。これが、目標関数の最適化を一層困難にしている。
【０００６】
形式的には、最適化問題は次のように記述することができる。即ち、最適化問題とは制約条件Ｃi（ｘ）≧０下にある目標関数Ｆ（ｘ）を最大化することであり、ここでｘは設計パラメータｘ1，ｘ2，ｘ3，..., ｘn の実数値のベクトルであって、総てのベクトルに対し、ｘ∈Ｒnで且つｉ＝１，..., m である。上記目標関数の最小化が要求される場合には、該目標関数に負の関数を乗じて最適化問題を目標関数の最大化問題に置き換える。同様にして、Ｃi（ｘ）≦０の形態にある制約条件もしくは制約関数も、Ｃi（ｘ）に負を乗算することにより正準形に改変する、即ち変換することができる。なお、以下の説明において、術語「良いパフォーマンス」及び「悪いパフォーマンス」は、最大化問題及び最小化問題双方に共通に用いる。
【０００７】
添付図面中、図１は、１つの例として化学プラント１００を単純化した形態で示す図である。このシステムは、クーラ（冷却塔）１０１及びヒータ（加熱塔）１０２を用いて、入力ストリーム（供給流動物）１０５から生成物１０３と廃棄物１０４とを分離する。このシステムは、蒸留もしくは精留塔内に復水器１０６、リボイラ１０７及び反応板もしくはプレート１０８を備えている。
【０００８】
システム１００は、特定の入力ストリーム（Ｉ）１１５に対し、生成物（Ｐ）１１３の量が最大で且つ廃棄物（ｗ）１１４が最小になるようにモデル化した目標関数Ｆ（ｘ）１１０で表される。設計パラメータ１１１、即ち、ベクトル量ｘには、入力ストリームにおける流速（流量）、適用される加熱及び冷却速度、各反応プレート上の各成分の液体及び蒸気組成及び蒸気圧等が含まれる。
【０００９】
設計パラメータｘは種々な制約や相関関係の影響、即ち、多くの種類の制約条件Ｃ（ｘ）１１６を受ける。例えば、組成及び流れ（フロー）は正でなければならず、温度は或る上限を越えてはならない等々である。更に複雑な制約条件として、成分が物理的にどのように相互作用するかが問題となる。例えば、蒸気及び液体組成間には、極めて非線形な温度関数で表される相関が存在する。システム１００を念入りに分析することにより、適切な目標関数Ｆ（ｘ）１１０及び制約関数Ｃ（ｘ）１１６を創成することが可能である。従って、特定の運転条件下で生成物を最大にし且つ廃棄物を最小にするように関数Ｆを最適化することが可能である。
【００１０】
制約された最適化関数の多くは、適応最適化方法を用いてサーチ空間で最適値（最適解）をサーチすることにより解くことができる。この場合、最適解は、往々にして、制約境界近傍に存在する。従って、このような制約空間でのサーチを回避するならば、これは、最適解に至る最適化のパス（経路）を阻害することになりかねない。
【００１１】
適応最適化方法についての最初の考え方は、Box によって提唱されたもので、"Evolutionary Operation: A Method for Increasing Industrial Productivity," International Conference on Statistical Quality Control, Paris, July 1955, reproduced in Applied Statistics, VI, pp, 3-22, 1657 に記述されている。Box は、「エボリューショナリーオペレーション（evolutionary operation）」と彼自身が称する考え方を提唱した。エボリューショナリーオペレーションは、観察にエラーが生じ易い現尺プロセス（full scale process）の経験的もしくは実験的最適化に属するものである。基本的な考え方は、プロセスの静的なオペレーションを、制御パラメータが僅に摂動する連続且つ系統立ったスキームに置き換えることにある。そして、このような摂動の作用もしくは効果を評価して、プロセスを改善の方向に遷移（シフト）する。Box は、出力に影響を与えるプロセスパラメータを系統的に調整することにより生産を増加することに関心を寄せていた。Box のエボリューショナリーオペレーションについての考え方は、コンピュータシステムを用いての最適化よりも寧ろプラントの管理者が従うべき運転手法の方に関連性がある。
【００１２】
1962 年に Spendley 等は、非線形数値最適化問題にシンプレックス法の適用を提唱している。"Sequential Application of Simplex Designs in Optimization and Evolutionary Optimization," Technometrics, November 1962を参照されたい。このシンプレックス法は、線形プログラミングのためのシンプレックス法と混同してはならない。
【００１３】
ここで、シンプレックス（単体）とは、サーチ空間における次元の数よりも１つ多いベルテックスもしくは頂点（vertex）を有する幾何学的構成体である。サーチ空間における次元の数をｋで表すと、シンプレックスは、当該空間における（ｋ＋１）個のベルテックス、即ち頂点により定義される。図２に示すように、二次元のシンプレックスは３個の頂点によって定義される。一次元、二次元及び三次元のシンプレックスは、それぞれ線、三角形及び四角形で表される。これに対して、複雑系においては、サーチ空間の次元は非常に大きく、例えば、次元の数は２０或るいはそれ以上になる。シンプレックス（単体）を可視化するのに頂点を結ぶ線分が用いられる。該線分にはそれ以外の機能はない。各頂点は、目標関数の制約関係及びシンプレックスに対する相対的価値を決定する目標関数Ｆ（ｘ）の関連のパフォーマンスの１つをグラフで表現するものである。
【００１４】
シンプレックス法では、サーチ空間におけるシンプレックスの動きに基づいて目標関数Ｆの最適解を求める。シンプレックスは、それぞれ頂点として評価されるシンプレックスのパフォーマンス並びに該シンプレックスの配向に基づく一連の論理的な動きで駆動される。シンプレックスの移動中、該シンプレックスは、目標関数Ｆによって定義されるサーチ空間の輪郭の間隔及び曲率の変化に応じて適応的にその形状を変えることができる。
【００１５】
図３に示すように、基本的なシンプレックス法３００は理解並びに適用が容易である。最適化は、初期試行で開始される。試行条件は、均等に拡張される。また、初期試行数は、設計パラメータの数に「１」を加えたものに等しい。初期試行で最初のシンプレックスが形成される。
【００１６】
基本的なシンプレックス法は以下に述べるようなルールを有する。第１番目のルールは、現在のシンプレックスにおいて最も悪いパフォーマンスを伴う試行を拒否するというものである。そこで、望ましからざる結果とは反対の方向でのサーチ空間への反映（３２０）により次のパフォーマンス値を求める。上記次続の試行で、シンプレックスにおける最も悪い試行が置換される（３３０）。この結果としてシンプレックスにおける次に悪いパフォーマンスが求められ、そこで次の試行が行われる。以下、この手法を繰り返す。このようにして、各ステップ毎にシンプレックスを最も悪いパフォーマンスから順次遠ざかる方向に動かす。このようにして、シンプレックスは、定常的に、一層良好なパフォーマンスに向かって移動することになる。
【００１７】
第２番目のルールは、一旦拒否したパフォーマンスには決して戻らないと言うものである。サーチ空間での反映演算でも最も悪いパフォーマンスが生ずる可能性がある。従ってこの第２番目のルールが無いとすれば、シンプレックスがパフォーマンス値間で単に振動するだけとなる事態が起こり得る。この問題は、２番目に悪いパフォーマンスを選択しそこから遠ざかる方向に移動することによってうまく回避できる。
【００１８】
上述の２つの主たるルールに加えて、付加的に２つの他のルールも用いられる。特定数のステップでシンプレックスに保留された試行を再評価する（３４０）。同じ設計パラメータが異なったパフォーマンス値をもたらすようなノイズが存在する場合には、この再評価ルールの適用で、シンプレックスが誤って悪いと判定されたパフォーマンス近傍に停留するのを回避することができる。試行においては、サーチ空間の制約境界が横切られることは決して無い。寧ろ、シンプレックスを制約境界から強制的に離れる方向に動かすために、非常に好ましくないパフォーマンスを適用することさえある。
【００１９】
各ステップにおける応答に応じ、変形シンプレックス法でシンプレックスの形状及びサイズ（大きさ）を調節することができる。この変形シンプレックス法はまた、可変サイズのシンプレックス法とも呼称される。先に述べた基本的なシンプレックス法のルールに、幾つかの新しいルールが付け加えられる。これら新しいルールでは、シンプレックスをパフォーマンスが良好になる方向に拡張もしくは膨張する。また反対に、シンプレックスの動きが悪いパフォーマンスになる方向にある場合には該シンプレックスを収縮する。膨張及び収縮という手法で、変形されたシンプレックスは成功裡に改善に向かう軌跡に沿って加速され磨き上げられて最適化される。従って、変形シンプレックス法では、通常、基本シンプレックス法と比べて一層迅速に最適なパフォーマンスに達することができると共に、最適なパフォーマンスを一層正確且つ精密に決定することができる。
【００２０】
Nelder 等は、"A Simplex Method For Function Minimization," Computer Jounal, Vol. 7, 1965 において、ｎ次元のサーチ空間をサーチ、即ち探索するために、「ｎ＋１」個の頂点から構成されるシンプレックスを用いて最適化を行うコンピュータ化された方法を提唱している。なお、これと関連して、Gill 等の Practical Optimization, Academic Press, London, 1981 をも参照されたい。
【００２１】
Nelder のシンプレックス法は、関数Ｆ（ｘ）のグラディエント或るいは二次近似に基づかないという点でその当時利用可能であった最適化法の殆どのものと異なっている。Nelder のシンプレックス法は、目標関数が定義されるものであり、且つサーチ空間に何らかの最適解が存在することを前提としている謂わば日和見的な方法である。サーチ空間の曲率が迅速に変化しつつある場合には、Nelder 法は特にうまく働く。サーチ空間が平滑で微分法が高速に働く事例では Nelder 法は極大近傍で比較的緩慢になる。また、Nelder 法では制約は、明示的に取り扱われていない。しかしながら、Nelder 法は、その当時から、罰金関数（penalty function）を用いることにより制約を取り扱うことができるように適応化されている。
【００２２】
罰金関数法では、制約条件に遭遇する都度、目標関数のパフォーマンスにペナルティ、即ち罰金値が加えられる。しかしながら、残念なのは、この罰金もしくはペナルティで目標関数の実際の値が変わってしまい、その結果として制約されていないサーチ空間の真の「形状」が変わってしまうことである。実際、追って詳述するように、罰金関数は、制約境界近傍でサーチ空間を「ワープ（warps）」する。この結果、境界近傍または境界で最適パフォーマンスを検知するのが非常に難しくなる。言うまでも無いことであるが、多くの実際的なシステムにおいて最適なパフォーマンスが境界または境界近傍で見出されることが予期されるところである。実際、良く知られているにように、高度に整調されたシステムは、その「縁辺領域」で動作することができる。
【００２３】
制約問題は、その本来の性質から、最適化プロセスの論理に大きな影響を与える。Box は、"A New Method of Constrained Optimization and Comparison with Other Methods," Computer Journal, Vol. 8, pp. 42-54, 1966 において「コンプレックス法」について述べている。このコンプレックス法は、制約（条件）を取り扱う変形シンプレックス法である。
【００２４】
しかしながら、コンプレックス法（変形シンプレックス法）へのこの転換は些細なことではない。何故ならば、制約条件下の最適化は制約のない最適化とは顕著に異なるからである。従って、シンプレックス法の制約条件付きバージョンであるこのコンプレックス法を展開する上で、 Box はシンプレックス法の細部の殆どを変更し、頂点の集まりのうち最悪のものを反映するという基本的原理のみを残している。この新しいプロセスでは、罰金関数を用いる方法とは異なった仕方で制約条件を評価し取り扱う。
【００２５】
即ち、罰金関数を用いる代わりに、Box は目標関数自体とは別個の制約条件付きのパフォーマンスを用いている。この制約条件付きのパフォーマンスは、制約のないパフォーマンスとは機能的に異なった意味もしくは値を有する。しかしながら、制約条件付きのパフォーマンスも制約のないパフォーマンスと全く同様に最適化することができる。
【００２６】
Box は、境界が容易に識別可能（例えば、ｘ2 ≧７）で且つ評価が目標関数Ｆに従属しない制約条件を独立もしくは明示的制約条件と定義している。これとは対照的に、従属もしくは暗示的制約条件は複雑な境界を有し目標関数Ｆの評価を必要とする。Box は、制約限界の丁度内側に独立パラメータ違反を設定することにより制約境界の極く近傍に留まることを試みている。従属制約違反が生ずると、被検下の頂点を重心に向かい２分の１だけ移動する。その結果から Box は、「制約境界問題においては、制約条件が目標関数の輪郭及びグラディエント（勾配）と同程度に重要である。」と結論している。
【００２７】
従来のシンプレックス法及びコンプレックス法と関連する１つの問題は、最悪のパフォーマンスを有する頂点に意識を集中するあまり、次元数に損失が生ずる傾向があるという点に見られる。このように頂点を「ラインアウト（line-out）」する傾向で、サーチ空間を動き回る能力、即ち徘徊能力は減退する。
【００２８】
従って、次元の数を失うことなく動作可能である最適化方法を提供することが望まれる。更にまた、この最適化方法は制約境界近傍で最適解を見出す能力を有するのが望ましい。加えるに、最適化方法は、多数の局所最適解が存在するようなグローバルな最適化問題に適用可能であることが望まれる。更に、該最適化方法は、例えば実時間制御システムにおいて動的に変化する環境に適応できることが望ましい。
【００２９】
【発明の概要】
本発明によれば、最適値もしくは最適解を探知するのを容易にするために、従来方法とは異なり制約された空間が利用される。このような本発明の最適化方法を実現する上での合理的根拠は、多くの最適解が制約条件境界近傍に存在するということにある。従来の最適化法におけるように制約された空間の回避を厳しくすると、これは最適解のサーチの障害となり得る。本発明の方法においては、集合の頂点は、従来法とは異なり、制約違反が禁止されたり厳しく罰せられる（罰金もしくはペナルティが課せられる）制約された空間に移動することが許されるばかりではなく時としては推奨される。
【００３０】
制約条件境界における不連続性は、サーチ空間のパフォーマンスを任意数の一意性のレベルに区分することにより処理される。この区分は、制約条件の１つまたは複数の階層レベルへのグループ化（群にすること）により実現される。その場合、各頂点を最低のレベルから始めて各レベルにおける制約条件のグループに順じ評価する。頂点の評価が負のパフォーマンスとなった場合には、第１のレベル及びその負のパフォーマンスを当該頂点に割り当てる。そうでない場合には、該頂点を次のレベルで評価する。このサイクルを続ける。頂点が、総ての制約条件レベルを考慮した後に負でないパフォーマンスを有している場合にのみ目標関数を評価する。これにより、サーチ空間を効果的に複数のレベルに区分することができる。
【００３１】
本発明の最適化方法における区分の仕方は、Box の明示的／暗示的な範疇化とは異なる。本発明方法は、実現可能な目標関数から独立している制約条件の各レベル毎に制約パフォーマンスを定義する。更にまた、制約条件のグループ化を、最適パフォーマンスのサーチ中動的に変更することができる。
【００３２】
特定レベルの制約条件に対する制約されたパフォーマンスは、当該レベルにおいて違反が生じた制約条件の或る種の組合せ、例えば総和である。制約条件の値が厳密に零よりも小さい場合に制約条件に違反が生じたと見做す。従って、定義により、違反が生じた制約条件の総和は負であり、正または実現可能な方向（実効方向）に向かって最大化される。
【００３３】
本発明方法においては、複数のパフォーマンスレベルと関連し、制約条件境界に跨がって移動する頂点の集合の順序化及び移動に関してルールの集合が定義される。これらルール及び複数の制約パフォーマンスレベルに由り、本発明方法は制約条件の不連続性に対して一層鈍感になり、最適解に向かい制約条件境界に沿う移動を大いに助勢することができる。
【００３４】
上述のような新規の制約条件取扱い方法に加えて、本発明の方法は、次元数の損失が減少するように改良される。従来の適応性シンプレックス法における１つの問題点は、１つの空間次元において幅が失われる傾向があることである。この次元数の損失で当該方向における移動が制約される。本発明方法は、頂点の集合を再ソートする以前に各頂点の移動を試みる。従来のシンプレックス及びコンプレックス法では、排他的に、現在最悪のパフォーマンスを示す頂点が集中的に取り扱われている。
【００３５】
更に具体的には、システムを最適化する方法を提案する。該システムをモデル化した目標関数の設計パラメータのパフォーマンスを多次元のサーチ空間に表現する。該サーチ空間に頂点の集合を配置する。各頂点はそれぞれ関連のパフォーマンスを有する。集合内の頂点は最悪から最良のパフォーマンスに向かう順序でソート（並べ替え）される。ソートされた集合内の各頂点は、該頂点の現在のパフォーマンスよりも次の位置のパフォーマンスの方が良好な場合に該次の位置に移動される。このソート及び移動は終了条件に達するまでサイクルとして（周期的に）繰り返される。
【００３６】
【好適な実施例の詳細な説明】
探索データ構造の最適化  本発明は、連続したサーチ空間に定義された制約条件下の目標関数を適応的に最適化するための改良された方法を提供するものである。図５に示すように、ｎ次元の目標関数Ｆは、ｎ次元のサーチ空間５００を定義する。従って、（ｎ＋１）個の頂点の集合が定義される。図５において、該頂点は参照数字５０１乃至５０３で例示してある。
【００３７】
実際の適用例においては、各頂点はデータ構造としてコンピュータのメモリ内にデータ要素５０９として格納される。以降の説明において、これらデータ要素に対する演算は、該データ要素に論理的に等価である頂点に対する演算であると解釈されたい。各目標関数及び各制約条件は、この頂点の集合を表すデータ要素の配列もしくはアレイに対し実現可能な、または場合により実現不可能なパフォーマンス値を与えるコンピュータプロセスとして実行することができる。
【００３８】
位置、パフォーマンス及びレベルを有する頂点の配列
配列もしくはアレイの各要素５０９は次の情報を格納している。即ち、座標５１０で表される位置、パフォーマンス５２０及びレベル５３０を格納している。位置座標は、サーチ空間５００における対応の頂点の位置を定義する。また、パフォーマンスは、頂点の位置で最適化されているシステムの値を定義する。なお、パフォーマンスがどのようにして決定されるかに関しては追って詳細に説明する。パフォーマンスは実現可能であり得ると共にまた、頂点の位置が１つまたは２つ以上の制約条件に違反する場合には、パフォーマンスは実現不可能であり得る。また、レベル値の使用に関しても追って説明する。概述すると、サーチ空間は動的に区分することができ、各区分は関連の一意的な階層レベルを有することができる。区分化は、制約条件及び目標関数をグループ化することにより実行される。
【００３９】
頂点の移動
本方法によれば、サーチ空間内の頂点は、目標関数のパフォーマンスが最適化されるような仕方でサーチ空間内で移動される。頂点のこの移動は、制約条件による制約を受け得る。追って詳述するように、このような制約条件をどのように取り扱うかが、本発明の改良された最適化方法が従来の適応性最適化方法と異なる所以である。
【００４０】
最良のパフォーマンスを有する頂点以外の制約条件下にない頂点の移動は次のように行われる。即ち、該頂点を、他の頂点の重心５５０を通して反映する。例えば、頂点５０４は、頂点５０１の新たな反映位置である。頂点が重心を通って移動する距離は、該頂点の元の位置から重心までの距離に拡張係数（ＥＦ）５４０、例えば、１.２５を乗じた距離に等しい。
【００４１】
最良のパフォーマンスを有する頂点の移動については、特殊ルールと関連し追って説明する。集合内の如何なる頂点も、試行移動中に現在の最良のパフォーマンスが一層良くなる時点で最良のパフォーマンスを示す頂点となり得る。従って、集合内の１つの頂点は常に、最良のパフォーマンスを示す頂点としてマークできる。
【００４２】
移動を実行した場合に、次の位置における頂点のパフォーマンスが、それより以前の位置における当該頂点のパフォーマンスよりも良好である場合には、該移動を成功と見做す。言い換えるならば、頂点は、パフォーマンスが一層良好になるサーチ空間内の位置に対してのみ移動することが許される。移動が成功である場合には、上記次の位置及び次のパフォーマンスが、当該頂点の元の位置及び元のパフォーマンスに取って代わる。そうでない場合には、この移動は無視され、当該頂点は元の位置に留どまることになる。
【００４３】
移動のサイクル
移動のサイクルとは、集合内の各頂点をそのパフォーマンスが改善されるように移動する試みのサイクルである。即ち、集合内の頂点は、そのパフォーマンスの改善順、即ち昇順で移動される。具体的には、最悪のパフォーマンスを示す頂点を最初に移動し、最良のパフォーマンスを示す頂点は最後に移動する。拡張係数（膨張係数とも称される）に由り、頂点は、それぞれの相対位置が分散する傾向を示す。従って、集合の空間的エクステント（範囲）は、移動が成功する都度増加する。
【００４４】
最良の頂点のパフォーマンスが或るサイクル中不変のままであった場合には、他の頂点を、或る収縮係数（ＣＦ）、例えば０.７５だけ、上記最良の頂点に向かって移動する。従ってこの場合には、集合の空間エクステント（空間量）は減少する。
【００４５】
頂点の集合には適応性があるので、高いパフォーマンスが示されるサーチ空間内の領域に向かって該集合は伸長する傾向を有する。このことについては追って図４を参照し説明する。従って、サーチは過去に成功した方向において一層活発になる。そしてこのことは、通常、未来における成功をも最も高い確率で約束する。しかしながら、この伸長する傾向は抑制しなければならい。然も無いと、頂点が所謂「ラインアウト（line-out）」して、次元の数が減少し、その結果、頂点の集合を適切に操作しサーチ空間を完全に包摂し尽くすことが不可能になるからである。
【００４６】
適応性サーチ法
図６は、本発明の方法６００の基本的ステップを示す。頂点６０１の集合は、サーチ空間５００内のそれぞれの位置に従って評価され、昇順に従いソートされる（ステップ６１０）。ここで昇順とは、最適化が最大化問題であるか最小化問題であるかに関係なく最悪から最良に至る順序を意味する。言い換えるならば、最大化の場合には、最大値が最良であり、最小化最適の場合には、最小値が最良である。
【００４７】
頂点は、それぞれのパフォーマンスの昇順（最悪から最良へ）で試行移動される（ステップ６２０）。ここで、試行移動とは、頂点を次の位置に条件的に移動し該次の位置で該頂点を評価することである。該次の位置でのパフォーマンスが良好であれば（ステップ６３０）、この試行移動（ステップ６４０）を受け入れる。最悪の頂点に続いて、次に悪い頂点を条件的に移動し、評価し、そして受け入れる。この手順を、集合内の最後の頂点が条件的に移動され、評価されて受け入れられるまで続ける。既述のように、このサイクルの終時においては、最後の頂点が最早や最良の頂点ではなくなる場合があり得る。
【００４８】
各頂点を条件的に移動し、評価し且つ受け入れるサイクル６５０が完了した後に、このサイクル中、総合的に最良のパフォーマンスに改善がみられなかった場合、最良の頂点以外の頂点を収縮係数に従い該最良の頂点に向かって収縮する（ステップ６７０）。このサイクルを、或る予め定められた終了条件、例えば、所定の繰り返し数に達するまで、又は最適化における増分的改善度（変化率）が或る所定の閾値よりも小さくなるまで繰り返す。収縮で、頂点の集合の空間エクステントが減少する。
【００４９】
図４は、本発明による二次元サーチ空間における頂点の三角形集合の９回の移動（１−９）を示す。三角形３及び４、５及び６並びに８及び９が重なり合っている点に注目されたい。また、最適状態に向かい拡張もしくは膨張し、次いで最適状態を中心に収縮する点に注目されたい。
【００５０】
先に述べたように、従来の適応性最適化のためのシンプレックス法及びコンプレックス法は、最悪のパフォーマンスを示す頂点に排他的に集注するので、１つの空間次元において幅を失う傾向を有する。これとは対照的に、本発明では、集合内の総ての頂点をそれぞれ最悪から最良に向かう順で移動するので、従来法とは異なり、次元の損失傾向は低減する。
【００５１】
頂点の集合は、収縮係数の値に対して比較的鈍感であるが、１よりも極く僅かに大きい拡張係数で、特に高次元数、例えば、ｎ＞２０のサーチ空間において最良の安定性が得られる。加えるに、サーチ空間の次元数が大きい、例えば、ｎ＞２０の場合には、頂点の数を増加することにより最適化が改善される。
【００５２】
サーチ空間における初期頂点集合の創成
サーチ空間において、頂点は最初に次のようにして創成される。単一の基本もしくはベース頂点をサーチ空間内のどの位置でも良い或る任意の位置に定義する。次いで、該ベース頂点の各座標を適当なステップサイズだけ増分することにより他の頂点を付加的に創成する。ここでステップサイズとは、集合に対し、各座標方向においてサーチ空間がどれほど大きいかを示す手助けとなる目盛り係数である。即ち、ステップサイズは、特定の次元の大きさ（サイズ）の或る端数に比例する。
【００５３】
特殊ルール
上述のサイクル中、移動すべき頂点が、最良のパフォーマンスを有する頂点である場合には、該最良の頂点を、図５に示すように、他の頂点の重心５５０を通るのではなく該重心５５０から離れている次の位置５０５に反映する。最良の頂点を移動する距離は、該最良の頂点から重心までの距離に拡張係数を乗じた距離に等しい。これにより、最適化プロセスは促進する。なお、サイクル中、該サイクルで最初に最良のパフォーマンスを示した頂点がサイクルの終わりに必ずしも最良であるとは限らないことに留意されたい。何故ならば、他の頂点がそのパフォーマンスを改善している可能性が有り得るからである。
【００５４】
頂点の集合が、所定回数の連続したサイクル、例えば連続１０サイクルに亙って収縮した場合、該集合をその現在のサイズで再生する。サーチ空間の各座標に対する現在のサイズは、最大値を有する集合の対応の座標と、最小値を有する集合の対応の座標との間の差として算出することができる。頂点の次の位置は、既述のように、各座標毎のステップサイズではなく、各座標毎の現在のサイズを用いて最良のパフォーマンスが得られる頂点から導出する。これにより、頂点が整列した集合の次元数を回復することができる。
【００５５】
集合が、最早や有意味に移動しない程小さいサイズに収縮した場合にも、同じ手法を用いることができる。このようなシチュエイションが生じた場合には、集合の元のステップサイズを用いるか或るいは各座標方向において現在のサイズを或るブースト係数（例えば、１.５）だけ増大することにより再生することができる。集合が収縮し続ける場合には、該集合が最適解に向かい収斂している蓋然性が高い。
【００５６】
制約条件の取り扱い
以上、本発明の方法を制約の無い系もしくはシステム（制約条件が課されていない系もしくはシステム）を前提として説明した。しかしながら、既に述べたように、実際上殆どの最適化問題は「制約」を受けている。即ち、設計パラメータと関連する総てのパフォーマンスが必ずしも常に実現可能なパフォーマンスとはならないという理由から制約を受けてると言える。例えば、殆どの化学プラントは、少例を挙げても、温度、圧力、容量及び時間の面で制約を受ける。
【００５７】
或る「パフォーマンス」が負である場合には、関連の制約条件Ｃiに対し「違反」が生じたと称する。従って、例えば制約関数Ｃi＝ｘ2 −５は、当該制約条件に関連するパフォーマンスが実現可能と見做されるためには、設計パラメータｘ2 は５より大きいかまたは５に等しくなければならない。この条件が満たされない場合には、パフォーマンスは実現不可能である。
【００５８】
サーチ空間の区分
本発明の一実施例においては、サーチ空間は、３種類の空間に区分される。即ち、独立制約空間と、従属制約空間と、目標関数の無制約空間とである。換言するならば、区分は、低レベルの独立制約条件から高レベルの従属制約条件、次いで最高レベルの無制約目標関数にグループ化することにより行う。
【００５９】
独立制約空間における頂点のパフォーマンスは、違反が生じた（負の）独立制約条件のパフォーマンスの総計をとることにより決定される。独立制約条件は目標関数から独立しており、設計パラメータにのみ依存（従属）する。
【００６０】
従属制約空間内の頂点のパフォーマンスは、違反が生じた（負の）従属制約条件のパフォーマンスの総計を求めることにより決定される。従属制約条件は設計パラメータを含む何らかの予備的計算を必要とし、またしばしば目標関数の評価を必要とし得る。
【００６１】
言うまでも無いことであるが、無制約空間におけるパフォーマンスは目標関数から直接導出される。
【００６２】
図７ａ及び図７ｂに示すように、無制約空間は通常、制約された（従属または独立の）もしくは「実現不可能な」パフォーマンス領域７０２と区別して、「実現可能な」パフォーマンス領域７０１と称する。以下、最も一般的な事例と関連して、「実現可能な」パフォーマンス及び「実現不可能な」パフォーマンスが如何に相対的であるか関して説明する。
【００６３】
図７ａには、２つの単純な独立制約条件ｘ1 ≧０及びｘ2 ≦４５１を示し、そして図７ｂには複雑な従属制約条件を示す。また、これら図には、局所最適解７０３、制約された大域最適解７０４、無制約大域最適解７０５及び偽最適解７０６が例示してある。なお、現実の高性能なシステムで往々にして遭遇するように、幾つかの最適解は制約境界近傍かまたは制約境界に存在していることに注目されたい。
【００６４】
独立した制約条件のパフォーマンスは評価が容易である。と言うのは、例えば下記のように、単に設計パラメータ上の制限に過ぎないからである。
２.０メータ ≦半径≦５.０メータ（半径がパラメータ）
０キロ      ≦重量≦２００キロ （重量がパラメータ）
【００６５】
他方、従属制約条件パフォーマンスは、何らかの予備計算を必要とし、目標関数の関数として定義ができる場合が多い。このことは、独立制約条件のパフォーマンスを区分して、目標関数から得られるパフォーマンスとは別個に評価することができるという点で実際的に有意味である。現実問題としても、目標関数を定義し得なかったり或るいは目標関数が物理的に無意味なパフォーマンスを生ぜしめるような設計パラメータのパフォーマンスに遭遇するのは異例ではない。例えば、負の重量とか負の領域とかがその例である。従って、目標関数自体を評価する前に総ての制約条件が満たされることを確保するのが肝要である。
【００６６】
従って、或る頂点が実現不可能な領域７０２に存在する場合には、該頂点のパフォーマンスは、違反が生じた制約条件の（負の）パフォーマンスの総和である。頂点をそれより良好なパフォーマンス位置に移動するためにこの負のパフォーマンスを最大化する。特に、パフォーマンスが改善される場合、即ち、負または正の度合いが減少する場合にのみ頂点を移動するか或るいは一層良いサーチ空間区分に移動する。例えば、頂点を、独立制約空間から従属制約空間に移動する。
これにより、頂点が最終的に実現可能領域７０１に戻る確率が増加する。
【００６７】
頂点が成功裡に独立制約空間から移動しても、該頂点の次の位置は依然として１つまたは複数の従属制約条件を違反している場合が有り得る。このような場合には、該頂点のパフォーマンスは、違反が生じた従属制約条件のパフォーマンスの総和で表される。この場合にも、該パフォーマンスを最大にして当該頂点を一層良好なパフォーマンス位置に移動する。
【００６８】
この場合、独立制約空間内の頂点は、従属制約空間内の頂点のパフォーマンスに対し相対的に「実現不可能」と見做されるパフォーマンスを有し、そして従属制約空間内の頂点のパフォーマンスは独立制約空間内の頂点のパフォーマンスに対し相対的に「実現可能」と見做す。更にまた、無制約空間内の頂点のパフォーマンスは、独立及び従属制約空間双方における頂点のパフォーマンスに対し相対的に「実現可能」と見做す。
【００６９】
制約境界
周知のように、制約境界もしくは実現可能領域と実現不可能領域との間のインタフェースは、往々にして、手強い問題を抱えた最適化法を呈する。主たる困難は、制約境界に鮮鋭な不連続を生ぜしめることなく、最適化サーチを実現可能にすることにある。本発明の方法において取り扱われる頂点は、制約境界における不連続に全く関与しない点に特殊性があることが明らかになるであろう。
【００７０】
内部及び外部罰金関数
既に述べたように、従来知られている或る解法では、実現可能なパフォーマンス空間が制約境界の近傍で「ワープ」するように罰金関数を定義することによりサーチ空間の連続性を強要する。罰金もしくはペナルティの値は、制約境界に接近するに伴い増加する。この罰金関数は内部罰金関数と外部罰金関数とを含むことができる。内部罰金関数は、実現可能領域から制約境界へ接近するパフォーマンスに対し罰金即ちペナルティを課す。その結果、実効的には、目標関数に付加項として刑罰関数が加えられて、制約境界近傍でパフォーマンス面が「ワープ」する。他方、「外部」刑罰関数の場合は、制約境界を横切った後においてのみ、最適化サーチが実現不可能な領域に更に進入するに伴い増加する量で罰金もしくはペナルティを加える。この外部罰金関数は、実現可能な領域における頂点のパフォーマンスには影響、即ちインパクトを与えない。
【００７１】
従来用いられている刑罰関数は通常、制約値の二乗に目盛り係数を乗じた積の総和のような制約条件の或る関数として定義されている。罰金、即ちペナルティは、頂点の集合を実現可能な最適方向に向かわせるように、サーチ空間を実効的にワープする目標関数のパフォーマンスに加えられる。
【００７２】
従来の罰金関数法には幾つかの問題点がある。最も顕著な問題点は、サーチ空間をワープすることにより最適解の位置が変わってしまうことである。また、ワープは鋭い稜線を有する非常に複雑な表面を生ぜしめる。この複雑もしくは難解な表面は、従来知られている殆どの最適化サーチプロセスの障害になっている。この理由から、罰金関数は、通常、増分的に増加する比較的小さい罰金から始めて幾つかの段階に亙り漸次適用されるのが一般である。
【００７３】
しかしながら、実際のシステムもしくは系において往々に遭遇するように最適位置が制約境界上に在るか或るいはその近傍に在る場合には、上記の方法を何度か繰り返して最適化ルーチンが真の最適解に実効的に「収斂する」ようにしなければならない場合がしばしばある。
【００７４】
外部罰金関数は、場合にも因るが、実現不可能な領域をワープするだけであるから、内部罰金関数よりも実効的である。しかしながら、外部罰金関数は、最適化サーチを制約境界の実現可能な側に強制的に保持するのが困難な時があり得る。また、目標関数が実現不可能な領域において未定義である場合には、外部罰金関数を使用することはできない。
【００７５】
本発明方法の１つの利点は、制約境界近傍でサーチ空間をワープする罰金関数を使用しないことにある。
【００７６】
罰金免責法
本発明は、集合の頂点が制約境界近傍または制約境界上の最適解に集束することを許容する付加的な移動ルールを提案するものである。特にこれ等のルールは、頂点が境界に沿って移動することを許容するばかりではなく該境界を越えて実現不可能領域に入り込むことさえも許容する。このように制約境界を越えて実現不可能領域に進入することは、後に、実現可能領域内で一層良好な最適解を見出すために推奨される場合さえある。
【００７７】
上記の付加的ルールを実現するために、本発明によれば、各区分内の最悪のパフォーマンスを有する頂点並びに各区分内で最良のパフォーマンスを有する頂点をマークする。更にまた、頂点集合の総合的に最悪のパフォーマンスを有する頂点並びに頂点集合の総合的に最良のパフォーマンスを有する頂点をマークする。このような区分ベースでのマーキングには、大きな計算オーバーヘッドが要求されるが、サーチのアグレッシブ度（積極性の度合）が減少する。他方、大域ベースでのマーキングでは計算オーバーヘッドは減少するがサーチのアグレッシブ度は大きくなる。
【００７８】
集合の総ての頂点が同じ区分内、即ち独立であれ従属であれ或るいは制約のない空間であれ、同じ区分内に存在する場合には、上に述べた特殊ルールと共に図６に示した方法に従って移動が行われる。
【００７９】
頂点の内の幾つかが異なった区分内にある場合には、低レベルの区分内の頂点だけを、それより高レベルの区分内で最良のパフォーマンスを有する頂点よりも良好なパフォーマンスを有する場合に、高レベルの区分に移動することができる。これにより、本発明の方法では、頂点集合は実現可能な最適解に向かう方向、即ち最適化方向に制約境界に沿って円滑に移動することができる。従来法ではこれは不可能である。従来法の場合には、制約境界近傍でひどい振動が生ずる。頂点のパフォーマンスが総合的に最良のパフォーマンスとなる場合にのみこの移動を許容することにより、サーチを一層アグレッシブにすることができる。
【００８０】
特定の区分内の頂点は同じ区分またはそれより高レベルの区分内の他の頂点の重心を通ってのみ移動する。従って、低レベルの区分内の頂点は重心の計算において考慮しない。このように、本発明の方法によれば、制約境界の「実現可能な」側に沿う方向に移動するという点で方向性が改善される。同じまたは高レベルの区分内に２つより少ない頂点しか存在しない場合には、低レベルの区分内の他の頂点を重心計算で考慮することができる。
【００８１】
高レベルの区分内の頂点は、次の位置の頂点のパフォーマンスが低レベルの区分内の最悪の頂点のパフォーマンスよりも良好である限り、通常のパフォーマンス判断基準を顧慮することなく該低レベルの区分内に自由に移動することができる。頂点のパフォーマンスが総合的に最悪のパフォーマンスを有する頂点よりも良好になった場合にのみ上記の移動を許容することによりサーチを一層アグレッシブにすることができる。しかしながら、集合の最良のパフォーマンスを有する頂点は、常に、移動前のパフォーマンスよりも良好でなければならないことを特記しておく。このように、本発明の方法には、制約境界に「跨がって」該境界を追跡する能力が与えられている。
【００８２】
サイクル中に総合的パフォーマンスが改善されなかったという理由から頂点の集合を収縮する場合には、総合的に最良の頂点を含む区分よりも低レベルの区分内の頂点を過剰に収縮する。このことは、これら頂点が、総合的に最良のパフォーマンスを有する頂点に向かって移動するのではなく、該総合的に最良のパフォーマンスを有する頂点を通って移動することを意味する。これにより、これら低レベルの頂点は制約境界を横切って実現可能方向に移動することができる。
【００８３】
上に述べた制約条件取り扱い手法は罰金関数法及び従来知られていた他の手法とは根本的に異なる。本発明の方法によれば、サーチ空間を変形する代わりに、最適化サーチで直接、歪みのない制約境界を取り扱うことができ、「アドオン」罰金関数の使用は要求されない。
【００８４】
パフォーマンスの一意的な階層レベル
上述のように、固定の独立／従属制約区分を用いる場合に、各評価は２つのインジケータによって定義される。即ち、下表Ａに示し且つ図５のデータ要素５０９に示すようにレベルとパフォーマンスにより決定される。
表Ａ
0004672184.tif 000002
【００８５】
或る１つの頂点のパフォーマンス５２０を決定するのにレベルとパフォーマンス双方を考慮することができる。階層は、下から上に向かい、先ずレベルにより、次いでレベル内のパフォーマンスによって定義される。即ち、独立のレベル、独立のパフォーマンス、従属レベル、従属パフォーマンス及び実現可能なパフォーマンスにより決定される。
【００８６】
２つの頂点のパフォーマンスを先ずそれらのレベルに従って比較する。因に、高レベルの区分内に在る頂点は常に「一層良好な」頂点である。更にまた、複数の頂点が同じレベルにある場合には、それらのパフォーマンス５２０を直接比較して一層良好な頂点を決定することができる。
【００８７】
汎用制約レベル
汎用制約レベルを用いて、目標関数及び制約条件は任意にグループ化される。
各グループは関連の階層レベルを有する。そこで、階層グループに従って頂点の評価を行う。これによりサーチ空間が区分化される。例えば、３つのグループ及び３つのレベルよりも多いグループ及びレベルが存在する場合には、区分の数は３よりも多くなる。多くの適用例において、区分の数が大きければ大きい程、固定の独立／従属未制約区分を凌駕する利点が得られる。更にまた、サーチを行いながら区分及びレベルを変更できる能力に由り、動的で適応性のあるサーチ技法が可能になる。
【００８８】
この場合、グループ化はユーザにより何らかのユーザインタフェースを介して変更したり、或るいはサーチプロセス自体により自動的に変えることが可能である。このような適応性プロセスにおいては、初期状態で各制約条件及び目標関数のパフォーマンスをそれ自身の区分及びレベルに割当て、然る後にサーチの進捗に伴いレベルを、例えば、「非常に能動的」、「能動的」、「それほど能動的ではない」及び「非能動的」区分に割当てることが可能である。また、区分自体を変えることなく該区分のレベルを変えることも可能である。
【００８９】
最適解サーチプロセスの種類、例えば、最急上昇勾配、共役勾配、可変計量及び逐次的な二次計画法（Press 外の Numerical Recipes in C, Cambridge University Press, 1992 参照）に関係なく、頂点のパフォーマンスを評価する仕方が、行われる判断を決定し、必然的に最適解への経路を決定する。最適化方法の本来的に逐次的な性質に由り、判断に変更があれば最適化経路も異なってくる。サーチプロセスの融通性が増せば追跡することができる経路が多くなり、従って該サーチプロセスが最適解に達する機会が改善される。
【００９０】
制約条件が「能動的」である場合には、本発明の一般制約レベル法での制約条件のランク付け及びグループ化はサーチプロセスの経路の変更に大きな影響を与え、それにより解の発見並びにシステムのパフォーマンスの改良を促進する。
【００９１】
以上に述べた最適化方法は、有らゆる種類の目標関数及び制約条件で実施可能である。しかしながら、本発明の方法は、目標関数Ｆ或るいは所与の制約条件Ｃi が極めて非線形或るいは微分不可能であるかまたはノイズが多い場合に、従来法よりも一層効率的且つ実効的である。現実の実際的なシステム、例えば化学プラントのような多くのシステムは制御中ノイズを受け、その結果、設計パラメータが同じであっても評価関数或るいは制約条件ＦまたはＣの評価を繰り返すと、その都度異なったパフォーマンスになることがしばしばである。
【００９２】
従来法では、最も悪いパフォーマンスを有する頂点が排他的に関心事となっている。その結果としてこれら従来法には、１つの空間次元において幅が無くなるという傾向がある。この次元数損失で、当該方向におけるサーチが制限され、解を見出す上に種々な困難に出会う。
【００９３】
本発明の方法による試行で総ての頂点は集合を再秩序化する前に移動される。
従って、本発明の方法によれば、より良好なパフォーマンスをもたらす一層実効的なサーチが実現されるという優れた効果が得られる。更にまた、制約条件をグループ化し、既述のルールを適用することにより、本発明の方法は、極めて高度に整調されたシステムにおける典型的な状況である制約境界の近傍で最適解を発見するのに優れている。更に、本発明の方法によれば、実時間ベースでの状態もしくは条件の変化に応答して制約条件を動的に変更することを可能にし、それによって、一層最適なパフォーマンスに至る新しい経路を実現することが可能である。
【００９４】
大域的最適化
以上、局所的最適解を見出すための謂わば「細部に亙る精緻な」サーチ技術について説明した。このような精緻なサーチと関連して知られている問題は、サーチ空間のどこかに一層良好な最適解が存在するかもしれないという問題である。
本発明によるサーチ方法は、サーチの精緻性もしくは繊細性を緩和することにより大域的最適化問題に適用することができる。この方法の目標は、典型的に多数の局所的最適解の中で大域的最適解を決定することである。
【００９５】
これは、例えば疑似アニーリング（simulated annealing）のような大域的サーチ ストラティジー（例えば、Press 外の Numerical Recipes in C, Cambridge University Press 1992 参照）を適用することにより達成できる。
【００９６】
本発明においては、現在の頂点を次の頂点で置換すべきか否かを決定するのに合格確率Ｐを用いる。次の頂点で一層良好なパフォーマンスが得られれば、Ｐ＝１とし、そうでない場合にはＰ＞０とする。後者の場合には、合格確率Ｐは現在の頂点及び次の頂点のパフォーマンス並びに付加的な制御パラメータ、例えば「温度」Ｔの関数である。
【００９７】
一般に、温度Ｔが低くなれば次の頂点の合格確率は小さくなる。サーチの遂行中、温度Ｔを段階的に下降する。言い換えるならば、頂点のパフォーマンスを時折退化する。温度が低ければ低い程、サーチ空間の悪いパフォーマンス部分で暴走もしくはエクスカーションが生ずる確率は少なくなる。このように、本発明の方法は、一層良好で一層大域的な最適解が得られるように、局所的最適解から離れる方向にアニーリングすることができる。本発明方法の新規性は、大域的サーチ判断を行うのに、従来用いられていたスカラーパフォーマンスではなく区分化されたパフォーマンスを用いる点に見られる。
【００９８】
以上、本発明を好適な実施例と関連して説明したが、本発明の精神及び範囲内で種々な他の適用及び変更が可能であることは理解されるべきである。従って、請求項の記述は本発明の真の精神及び範囲に包摂される総ての変形例や変更例を包含するように解釈されるべきであることを付記する。
【図面の簡単な説明】
【図１】  本発明方法により最適化されるシステム及びモデルのダイヤグラムである。
【図２】  サーチ空間及びシンプレックスを示すグラフである。
【図３】  シンプレックス法を図解するフローチャートである。
【図４】  サーチ空間を移動する頂点の集合をグラフで示す図である。
【図５】  頂点の膨張もしくは拡張する集合をグラフで示す図である。
【図６】  本発明による方法を図解するフローチャートである。
【図７ａ】  実現可能及び実現不可能な領域を有する区分されたサーチ空間をグラフで示す図である。
【図７ｂ】  実現可能及び実現不可能な領域を有する区分されたサーチ空間をグラフで示す図である。
【図１】
0004672184.tif 000003
【図２】
0004672184.tif 000004
【図３】
0004672184.tif 000005
【図４】
0004672184.tif 000006
【図５】
0004672184.tif 000007
【図６】
0004672184.tif 000008
【図７ａ】
0004672184.tif 000009
【図７ｂ】
0004672184.tif 000010