(57)【特許請求の範囲】
【請求項１】
空気力学的または流体力学的構造を表すスプラインコード化された構造を進化的に最適化する、コンピュータによって実行される方法であって、
制御点および節点を表す複数の目的パラメータと、該目的パラメータの突然変異の分散である該突然変異のステップサイズを表す少なくとも一つの戦略パラメータと、を含むパラメータセットを使用して、最適化すべきスプラインコード化構造を記述するステップを含み、
新たな制御点を挿入する前記パラメータセットの位置を求め、該位置に新たな制御点を挿入するステップ(S13)、こうして挿入された制御点の近隣の制御点の戦略パラメータ値の重み付け平均を求め、該重みづけ平均値を戦略パラメータの値として前記挿入された制御点の戦略パラメータとして挿入するステップ(S16)、および該パラメータセットを確率分布の乱数を加えることにより突然変異させるステップ(S19)を含む、前記パラメータセットの子を作るステップ(S3)と、
前記子の個体である子個体の目的パラメータによりコード化された構造の質を適合度関数を用いて評価するステップ(S20)と、
前記評価にしたがって最良の子個体をｎ個選択するステップ(S22)を含み、該選択された子個体が予め決められた終了条件を満たすとき最適化を停止し（S23）、該選択された子個体が前記終了条件を満たさないときは、組換えと呼ばれるオペレータを適用して前記選択された子個体を繁殖させ(S24)、次の世代として上記ステップ(S19)、ステップ(S20)およびステップ(S22)を繰り返すようにした、最適化方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、進化戦略に基づく最適化方法、進化戦略に基づいてスプラインコード化された構造を最適化するための方法、そのような方法を実行するためのコンピュータソフトウエア、及びそのような方法を空気力学的または流体力学的構造の形状の最適化のために利用することに関する。
【０００２】
【従来の技術】
進化戦略の分野では、自然の進化の基本原理を用いて技術的構造を生成または最適化する。基本的操作は突然変異と組換えであり、これらの方法を用いて構造またはパラメータを変更する。望ましくない変更を排除し、システム全体の質を向上させる変更を継続するために、選択操作が用いられる。進化戦略の原理は、例えば「Rechenberg, Ingo (1994) "Evolutionsstrategie", Friedrich Fromman Holzboog Verlag」に見られる。
【０００３】
まず図１で進化戦略の既知のサイクルを説明する。
【０００４】
ステップS1では最適化すべき目的パラメータを個体または染色体と呼ばれるベクトル内の実数としてコード化する。あるいは、１つの個体を複数のベクトルまたは染色体で構成してもよい。このような個体をいくつか生成して最初の親世代とし、この世代の各個体の質（適合度）を評価する。ステップS2では突然変異及び組換えと呼ばれるオペレータを適用して親を繁殖させる。こうしてステップS3では新しい世代が生まれる。これは子世代と呼ばれる。ステップS4では最適化の目的である適合度関数を用いて子個体の質を評価する。最後にステップS5では計算した質の値に基づいて最良の子個体を（確率的に）選択し（最適者生存）、ステップS6の終了条件が満たされなければこれらを次の世代サイクルの親として用いる。
【０００５】
特にこの応用では実数ベクトル（目的パラメータ）が、二次元または高次元の物体を記述するスプラインのコード化を表現する。このパラメータベクトルからスプラインコード化された構造への写像は、遺伝子型（つまりパラメータベクトル）−表現型（つまり二次元または高次元の物体）写像と呼ばれるのが普通である。ステップS4で適合度を決定するため、まず遺伝子型を表現型に写像し、次に表現型の質を導く。一例は、翼の外形を決定するスプラインを記述する実数値ベクトル（遺伝子型）による翼のパラメータ表示（表現型）である。最後に、翼の質を、例えば計算流体力学から既知の方法によって、決定することができる。
【０００６】
ステップS2の繁殖のための突然変異オペレータは、パラメータセット（いわゆる染色体）の既存の要素に正規またはガウス分布の乱数を加えることによって実現する。突然変異のステップサイズは正規またはガウス確率密度関数の分散を変更することによって制御できる。これらの分散は戦略パラメータと呼ばれる。高次元の場合、戦略パラメータは高次元ガウス確率密度関数の共分散行列の要素のすべてまたは一部で構成することができる。この戦略パラメータによって突然変異を制御する方法が特に進化戦略を遺伝的アルゴリズム（ＧＡ）や遺伝的プログラミング（ＧＰ）などの他の進化的アルゴリズムから区別する。
【０００７】
アルゴリズムの収束には戦略パラメータの適切な値が重要である。適切な値は問題と解空間における実際の位置に依存する。突然変異の幅をオンラインで適応させるには、様々な適応戦略を用いる。単純な方法は1/5ルール（Rechenberg参照）やいわゆる変異ステップサイズ制御がある。より複雑な方法の例は、非ランダム適応法や共分散行列適応などがある。
【０００８】
進化戦略は、上述の突然変異オペレータのステップサイズの適応または自己適応の可能性のため、実数値パラメータ最適化問題については遺伝的アルゴリズムや遺伝的プログラミングなどの他の進化的アルゴリズムよりも性能の良いことが示されている。
【０００９】
進化戦略の設計最適化への応用における既知の問題は、モデルを記述するパラメータ（いわゆる目的パラメータ）の個数が進化戦略において固定されていることである。従って、最適化の最中に目的パラメータによって表現されている表現型を自動的に精密化することは不可能である。
【００１０】
数学的には、突然変異操作ステップは以下の式(１)で表現できる。
【００１１】
【数１】
0004334178.tif 000002
【００１２】
0004334178.tif 000003
【００１３】
より一般的には、突然変異操作は以下の式(２)で表現できる。
【００１４】
【数２】
0004334178.tif 000004
【００１５】
【数３】
0004334178.tif 000005
【００１６】
0004334178.tif 000006
【００１７】
共分散行列Σは局所質関数に適応させる必要がある。図３(c)は戦略パラメータ（共分散行列Σ）の局所質関数への自己適応を示す。特に、図３(c)は繁殖過程の４サイクルの結果を示し、三次元の表面が質関数を表す。この方向とステップサイズに関する局所質関数への戦略パラメータの自己適応によって、局所関数の絶対極大に向かう良好な収束を達成することができる。
【００１８】
【発明が解決しようとする課題】
本発明の目的は、進化戦略における、特に戦略パラメータセットの自己適応特性の文脈における、可変パラメータセット長の問題を扱うことである。換言すれば、本発明は最適化の最中にパラメータによって記述された表現型を自動的に精密化するための技法を提案する。
【００１９】
【課題を解決するための手段】
本発明によれば、進化過程中の記述パラメータセットのサイズを適応させることができる。例えば、最初は非常に小さなパラメータセットを用いて最適形状の大まかな近似を見つけることができる。これは非常に迅速に達成できる。最適化の最中に、パラメータセットを拡張してさらに複雑な形状を記述することができる。しかし、パラメータセットは、新たな目的パラメータと適切な戦略パラメータを挿入する変更だけでなく、パラメータをいくつか除去することによっても変更できる。これは例えば、ある目的パラメータがそれ以上の最適化にあまり役立たないと判明した場合にあり得ることである。
【００２０】
パラメータセット内の目的パラメータの個数を増やすときは、関連する戦略パラメータの個数も新たな戦略パラメータを挿入することによって増やす必要がある。従って、本発明は新たに挿入された戦略パラメータの値を推定するための方法を提案する。
【００２１】
そこで本発明の第一の側面により、進化戦略に基づく最適化方法を提案する。これによれば、最適化すべきモデル、構造、形状または設計を目的パラメータを含むパラメータセットによって記述し、目的パラメータを突然変異させたり組換えたりすることによってパラメータセットの子を作る。そして、子の質を評価する。パラメータセットはさらに、関連する目的パラメータの突然変異の分散を表す戦略パラメータを少なくとも１つ含む。これにより、目的パラメータの個数も関連する戦略パラメータの個数も最適化過程の最中に適応させることができる。
【００２２】
目的パラメータと戦略パラメータは、選択的に挿入し、あるいは除去することができる。
【００２３】
新たに挿入された戦略パラメータの値は、相関する目的パラメータの戦略パラメータの情報に基づいて推定することができる。
【００２４】
目的パラメータと関連する戦略パラメータの挿入や除去の位置及び/または時期は、ランダム関数によって決めることができる。
【００２５】
目的パラメータセットと関連する戦略パラメータの変更は、評価ステップの結果に影響を与えないように行うことができ、従って、パラメータの変更は選択的に中立にできる。
【００２６】
本発明のもう１つの側面によると、進化戦略に基づく最適化方法を提案する。これによれば、目的パラメータと戦略パラメータの個数及び/または位置によって定義されたパラメータセットの構造を突然変異させてこれらの子を作ることができる。
【００２７】
本発明のさらにもう１つの側面によると、スプラインコード化された問題の最適化の方法を提案する。この場合の目的パラメータは制御点と節点を含むことができ、そこに新しい制御点と戦略パラメータを挿入することができる。
【００２８】
新たに挿入された戦略パラメータの値は、近隣の制御点の戦略パラメータの値に基づいて推定することができる。
【００２９】
本発明のもう１つの側面によると、進化戦略に基づいてスプラインコード化された形状を最適化するための方法を提案する。これによれば、最適化すべきモデル、構造、形状または設計を、スプラインコード化された形状の制御点と節点を表す目的パラメータと、関連の目的パラメータの突然変異の分散を表す少なくとも１つの戦略パラメータとからなるパラメータセットによって記述する。目的パラメータと戦略パラメータを突然変異させてパラメータセットの子を作る。最後に、子の質を評価する。突然変異のステップは、制御点挿入位置の決定、制御点の挿入、節点ベクトルの調整、挿入された制御点のための適切な戦略パラメータの挿入、変更された制御点の戦略パラメータ値の加重平均の算出、挿入された戦略パラメータの値としての加重平均の割当て、というステップを含む。
【００３０】
本発明のもう１つの側面によると、上述の方法を実行するためのコンピュータソフトウエアを提案する。
【００３１】
最後に、本発明はこのような方法を空気力学的または流体力学的構造の形状の最適化のために使用することを提案する。
【００３２】
【発明の実施の形態】
進化戦略の原理はすでに図１から３で説明した。本発明と進化戦略の従来技術の間の全般的な差異は、遺伝子型の構造すなわち戦略パラメータを含むパラメータセットの構造を突然変異させることができる、という点である。換言すれば、パラメータセットの戦略パラメータと目的パラメータの個数の両方を変えることができる。従って、最適化過程は比較的少数のパラメータで開始することができ、パラメータセットの複雑さを最適化過程の最中に調整することができる。
【００３３】
図４と図５において、既存のパラメータセットに新たな目的パラメータを挿入する場所及び/または時点は、例えばランダム関数を用いて定義することができる。新たな目的パラメータを挿入するときは、対応する戦略パラメータの場所に新たな戦略パラメータを挿入することによって前の「染色体」（目的パラメータと戦略パラメータからなるパラメータセット）を拡張して新しい染色体にする。図４に示した概念は、いわゆる個別変異ステップサイズ適応を指す。ここで、近隣の目的パラメータと戦略パラメータも変更後に変化するかもしれない、ということに注意する。
【００３４】
共分散行列の構造突然変異を図５に図式的に示す。この具体化による戦略パラメータは共分散行列として表現される（前述の式(３)を参照）。古い染色体に新たな目的パラメータを挿入して染色体を拡大するとき、共分散行列Σは新たな行と新たな列の挿入によって適応され、こうして、拡大された新しい共分散行列Σ' が生じる。この表現によるパラメータセットは目的パラメータセットと戦略パラメータ（例えば共分散行列Σ）から構成される。ここで、共分散行列の近隣の行と列も変更によって影響を受けるかもしれない、ということに注意する。
【００３５】
本発明は例えばスプラインコード化された問題の最適化の分野に応用される。スプラインコード化された問題の例を図１０と図１１に示す。典型的な場合、このようなスプラインコード化された問題では、形状のすべての属性をパラメータセット（制御点、節点、これらが目的パラメータと戦略パラメータを構成する）にコード化する。コード化されない属性は表現されず、最適化の対象にならない。従って、属性はパラメータセットのパラメトリック記述に含まれていないかぎり最適化中に進化できない。
【００３６】
本発明はパラメトリック記述のオンライン変更（遺伝子型の構造の変更）を許すので、コード内に、従って形状（表現型）内にも、新たな属性を挿入できる。ここで、パラメータセットは新たな目的パラメータと戦略パラメータの挿入によって拡大できるだけでなく、これらのパラメータの除去によって縮小もできる、ということに注意する。これは例えば、ある目的パラメータがそれ以上の最適化に余り役立たないと判明した場合にあり得る。
【００３７】
すでに述べたように、他の進化的アルゴリズムと比較した進化戦略の主な長所の１つは、さらなる探索にとって好ましい方向とステップサイズを表現できる戦略パラメータの使用である。戦略パラメータも最適化の最中に進化戦略において質関数の局所特性に適応させる（突然変異させる）ことができる。新たな構成要素（スプラインコード化された問題の場合は新たな制御点）をコードに挿入したり、コードを変更したりするときは、新たに挿入された戦略パラメータの値を計算する必要がある。
【００３８】
本発明によれば、新たに挿入された戦略パラメータの値を決定するとき、相関する構成要素の情報、例えば相関する目的パラメータに関連する相関パラメータの情報を用いる。
【００３９】
スプラインコード化された構造の場合、新たな点の戦略パラメータは近隣の点の戦略パラメータに似ているのが普通である。従って、スプラインコード化された構造の場合、戦略パラメータ値は近隣の制御点の戦略パラメータ値から推定することができる。
【００４０】
従って、スプラインコード化された問題または構造のための最適化過程は以下のように簡単に表現することができる。
【００４１】
・幾何学的形状（例えば翼などの流体力学的または空気力学的物体）の最初のスプラインコード化（目的パラメータセット）と最初の戦略パラメータセット （例えば共分散行列）を定義する。
【００４２】
・最適化のための標準的な進化戦略のステップを実行する。
【００４３】
・追加の突然変異オペレータとして、または例えば現行コードでの改善の停滞のようなあらかじめ決めた尺度によって、スプラインコードに新たな制御点（新たなパラメータ）を（場合によってはランダムに）導入する。
【００４４】
・既存の戦略パラメータに基づいて新たな戦略パラメータ値を推定する。
【００４５】
・最適化のための標準的進化戦略を継続する。
【００４６】
この過程は例えばスプラインコード化された問題に役立つ。この過程について図６に沿って説明する。
【００４７】
ステップS11では、問題の初期コードを例えば制御点と節点で表現して設定する。ステップS12では、コードを突然変異させるかどうか決定する。この決定は例えばランダム関数によってまたは最適化の進展に依存する関数によって促すことができる。ステップS12の結果が肯定（yes）の場合、ステップS13で新しい制御点を挿入すべきかどうか決定する。もし決定ステップS13の答えが肯定なら （これもランダム関数に基づいてまたはスプラインコードに関するある種の感度分析に基づいて決めることができる）、新たに挿入すべき制御点の位置をステップS14で見つける必要がある。従って、パラメータセット内の新たに挿入された点の位置を表す新たに挿入すべき点の指標iをステップS14で見つける必要があり、新たな制御点をステップS15で指標iの位置に挿入する。最後にステップS16では、対応して挿入すべき戦略パラメータstratiの値を計算する。新たに挿入された戦略パラメータstratiの値は、近隣の戦略パラメータstrati-1とstrati+1の値の関数f(strati-1,strati+1)であるか、または、より一般にすべての古い戦略パラメータの部分集合の関数である。
【００４８】
ステップS13で新たな制御点を挿入せずにコードを突然変異させると決定した場合は、ステップS17で除去位置を選ぶ必要があり、対応する制御点をステップS18で除去する。
【００４９】
最後にステップS19で、制御点、節点、戦略パラメータを含むパラメータセットを突然変異させる。この突然変異ステップS19で生じた構造を、次にステップS20で評価する。評価にはいわゆる適合度関数を用い、例えばスプラインコード化された形状の流体力学的特性を測定する。
【００５０】
ステップS21では、すべての個体すなわちすべてのパラメータセット（目的パラメータと戦略パラメータからなる）を突然変異させたかどうかを判定する。答えが否定（no）なら、ステップS12に戻る。
【００５１】
ステップ S21での判定が肯定なら、ステップS19で生成してステップS20で評価したｍ個の個体のうち最良の個体ｎ個をステップS22で選ぶ（「最適者の生存」）。これは（ｎ,ｍ）選択に対応するが、（ｎ＋Ｍ）選択やトーナメント選択など他の選択方法を適用することもできる。選択過程の後は、あらかじめ決めておいた基準が満たされた場合にはステップS23で最適化を止め、あるいは繁殖ステップS24と新たな突然変異ステップS11で新たな生成を始める。
【００５２】
図７は本発明による突然変異が可能な様々な階層を示す。
【００５３】
ステップS19でのパラメータセット（目的パラメータS25 と戦略パラメータS26）の突然変異は既に知られている。しかし、本発明によれば、例えばパラメータセットの目的パラメータと戦略パラメータの個数と位置などの構造も、ステップ S27（図６のS12からS18で構成）で突然変異させることができる。
【００５４】
図８は図６で示した最適化過程を要約する。遺伝子型をまずステップS13aで新たな目的パラメータの挿入により拡張する。この新たなパラメータの値をステップS13bで既存の目的パラメータ値から推定する。これは例えば、遺伝子型の拡張後の表現型の初期変動を最小化するためである。新たな目的パラメータの位置と値をS13aとS13bで計算した後、新たな目的パラメータの値の推定（ステップS13b）に用いた目的パラメータに対応する現在の戦略パラメータを用いて新たな戦略パラメータの位置と値を計算する。
【００５５】
最後に、新たな目的パラメータについて最適化した戦略パラメータで遺伝子型を拡張したものを生成する。
【００５６】
本発明をスプラインコード化された構造に適用する簡単な例を図９と図１０に示す。この場合の問題は、一定個数（図９）及び可変個数（図１０）の辺を持つ多角形で円を近似することである。本発明（図１０）の利点は、この単純な最適化過程を、例えば三角形など、パラメータの少ない構造で開始し、その後、最適化の最中にパラメータ数を増やすことができる、という点である。発育を繰り返すため、進化は図９のような膠着状態に陥らない。図９では自由度が大きすぎて戦略パラメータが適応できない。
【００５７】
このようなスプラインコード化された構造のための突然変異過程は以下のように要約できる。
【００５８】
１．単純な構造（少数の目的パラメータ）に基づき、制御点挿入位置を決定する。
２．決定した挿入位置に制御点を挿入する。
３．挿入した制御点に応じて節点ベクトルを変更する。
４．新しい制御点に対する新しい戦略パラメータの値を計算するため、近隣制御点の戦略パラメータの加重平均を計算する。
５．この加重平均の値を新たに挿入された戦略パラメータの値として割り当てる。
【００５９】
この記述によれば、本発明は最適戦略パラメータを既存の戦略パラメータから推定できるようなすべての構造コード化に適用することができる。
【００６０】
図１１は戦略パラメータの推定と本発明の翼設計への応用を視覚化している。ここで、R5は翼を示す。R6は、翼を近似するスプラインの制御多角形を示す。R9は既存の制御点を示し、この制御点R9の周りの楕円面R10は戦略パラメータによる確率密度分布の視覚化であり、変更が予想される部分である。R7は新たに挿入された制御点であり、灰色部分で示した戦略パラメータR8を持つ。
【００６１】
本発明の翼形状以外への応用例は、ガスタービンの圧縮機ブレードやタービンブレード（固定翼と回転翼）、その他の空気力学的または流体力学的構造である。他の応用分野は、建築、土木工学、コンピュータサイエンス、翼設計、エンジンバルブ設計、スケジューリング問題である。
【図面の簡単な説明】
【図１】進化的アルゴリズムを説明する図である。
【図２】進化パラメータ値の影響を示すグラフである。
【図３】戦略パラメータと進化戦略過程の方向とステップサイズの間の関係を示す図である。
【図４】戦略パラメータの個別ステップサイズ適応のための構造突然変異を示す図である。
【図５】戦略パラメータの共分散行列適応のための構造突然変異を示す図である。
【図６】戦略パラメータと目的パラメータの挿入や除去によってパラメータセットの構造を適応させる過程の流れ図である。
【図７】突然変異の様々な階層を示す図である。
【図８】パラメータセットの構造の突然変異を示す流れ図である。
【図９】本発明の応用例であるスプラインコード化された形状の最適化を示す図である。
【図１０】本発明の応用例であるスプラインコード化された形状の最適化を示す図である。
【図１１】空気力学的または流体力学的物体の形状の最適化への本発明の応用を示す図である。
【符号の説明】
S1        親世代を生成するステップ
S2        親を繁殖させるステップ
S3        子世代を生成するステップ
S4        子個体の質を評価するステップ
S5        最良の子個体を選択するステップ
【図１】
0004334178.tif 000007
【図２】
0004334178.tif 000008
【図３】
0004334178.tif 000009
【図４】
0004334178.tif 000010
【図５】
0004334178.tif 000011
【図６】
0004334178.tif 000012
【図７】
0004334178.tif 000013
【図８】
0004334178.tif 000014
【図９】
0004334178.tif 000015
【図１０】
0004334178.tif 000016
【図１１】
0004334178.tif 000017