(57)【特許請求の範囲】
【請求項１】
空力学ボディ又は流体力学ボディについての多目的最適化をコンピュータで実施する方法であって、該コンピュータに実行される機能として、
ａ．親個体群として解の初期個体群を提供するステップ（３１０）と、
ｂ．前記親個体群を複数のクラスタに区分するステップ（３２０）と、
ｃ．クラスタｋ（ｋ＝１、...、Ｋ）ごとに、多目的問題についての固有値の比に基づいて収束基準（Ψ）を計算するステップ（３３０）と、
ｄ．各クラスタの前記収束基準（Ψ）が所与のしきい値（ρ）より大きいかどうかを検査するステップ（３４０）と、
ｅ．前記収束基準（Ψ）が前記所与のしきい値（ρ）以下である場合に、それぞれに規則性を取り込む決定論的モデルと各クラスタｋの個体群の局所ダイナミックスをシミュレートするガウスモデルからなる、Ｋ個のモデルをサンプリングして子孫を生成し（３５０）、その他の場合に、突然変異および交叉を使用して子孫を生成
するステップ（３６０）と、
ｆ．親と子孫とをマージするステップ（３７０）と、
ｇ．優越比較に基づいて各個体を選択するパレートベースの選択方法を使用して新しい親個体群を作成するステップ（３７０）と、
ｈ．停止判断基準が満足されるまで、前記新しい親個体群を使用して前記ステップｂ）からｇ）までを繰り返すステップと、
を含む方法。
【請求項２】
最適化が、２つの目的問題を含み、各クラスタの前記収束基準（Ψ）が、対応するクラスタの前記２つの問題についての、最大の固有値と２番目に大きい固有値との間の比によって決定される、請求項１に記載の方法。
【請求項３】
最適化が、３つの目的問題を含み、各クラスタの前記収束基準が、対応するクラスタの前記３つの問題についての、２番目に大きい固有値と３番目に大きい固有値との間の比によって決定される、請求項１に記載の方法。
【請求項４】
前記ガウスモデルの標準偏差が、次式
【数１】
0004790590.tif 000012
で求められ、ここで、ｄｉｋはクラスタｋ内のｉ番目の点からその基準ベクトルまでの距離であり、ｎは判断パラメータの個数であり、Ｎｋはｋ番目のクラスタ内の点の個数であり、ｋはｋ番目のクラスタのインデックスである、請求項１乃至３に記載の方法。
【請求項５】
前記親個体群をクラスタに区分する前記ステップが、局所的な主成分分析（ＰＣＡ）を使用する、請求項１に記載の方法。
【請求項６】
コンピュータでの実行時に請求項１乃至５のいずれかに記載の機能を提供するコンピュータ・プログラム。
【請求項７】
請求項６に記載のコンピュータ・プログラムを記憶されたコンピュータ読み取り可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多目的最適化問題を解く新しい個体群ベースのアルゴリズムに関する。このアルゴリズムは、遺伝学ベースの子孫生成（交叉および突然変異）をモデルベースの子孫生成技法と組み合わせる。このアルゴリズムは、自動化された形すなわちコンピューティング・デバイスで実行される。
【０００２】
本発明の通常の応用例は、設計の最適化、たとえば、空気力学的ボディまたは流体力学的ボディの最適化である。
【背景技術】
【０００３】
多目的最適化（multi-objective optimization：ＭＯＯ）または複数基準（multi-criterion）プログラミングは、たとえば空気力学的形状または流体力学的形状の設計など、さまざまな工学問題で遭遇する難しい問題の１つである。本発明は、連続探索空間での次の多目的最適化問題（multi-objective optimization problem：ＭＯＰ）に関する。  
min F(X)=(f1(X),…,fm(X))Ｔ; X∈Ω  
ここで、Ｘは、判断ベクトル（decision vector）であり、Ｆ（Ｘ）は、対応する目的ベクトル（objective vector）であり、Ω∈Ｒｎは、決定空間（decision space）である。多数の進化アルゴリズム（evolutionary algorithm：ＥＡ）が、過去１０年間にわたってＭＯＰに取り組むのにうまく使用されてきた。第二の個体群（second population）（またはアーカイブ（archive））の使用などの複数の重要な技法が、ＭＯＥＡの性能を大幅に改善できることが示されてきた。
【０００４】
単一の目的最適化と異なって、パレート最適解（Pareto-optimal solutions）の分布は、しばしば、高い度合の規則性を示す（用語「パレート最適解」は、ＭＯＯの分野で周知であり、たとえば、これならびに本明細書および特許請求の範囲で使用される他の用語については、http://ls11-www.cs.uni-dortmund.de/people/beyer/EA-glossary/の進化アルゴリズム（ＥＡ）の分野の用語の用語集を参照されたい）。これまでに、この規則性は、しばしば、進化的最適化の後に局所探索を導入することによって、暗黙のうちに活用されてきた。そのような規則性をさらに利用するステップが、パレート最適解の分布の規則性を取り込むモデルの使用である（非特許文献１を参照）。この論文（非特許文献１）では、線形モデルまたは二次（quadratic）モデルが奇数世代で使用され、交叉および突然変異が偶数世代で使用されて、子孫（offspring）を生成する。
【０００５】
本発明で使用されるモデルベースの子孫生成方法は、進化的計算コミュニティで分布推定アルゴリズム（estimation of distribution algorithm：ＥＤＡ）と呼ばれる大規模なクラスの探索アルゴリズムに密接に関連する。ＥＤＡは、まず、個体群（population）内の選択された解の分布を近似する確率モデルを構築する。次に、確率モデルからのサンプリングによって、新しい解を生成する。ＥＤＡは、単一の目的最適化問題にうまく使用されてきた。
【０００６】
ＥＤＡは、多目的最適化にも拡張されてきた。１つの既知の方法では、現在の個体群からの
【数１】
0004790590.tif 000002
個の最もよく機能する解がまず選択される（Ｎは集団の大きさであり、0.0＜τ＜1.0である）。次に、ランダム化ユークリッド・リーダー（randomization Euclidean leader）アルゴリズムを使用して、選択された点を複数のクラスタに区分することができる。各クラスタ内で、ガウス確率モデルを構築して、解の分布をシミュレートする。次に、
【数２】
0004790590.tif 000003
個の解を、これらのモデルから１つずつサンプリングする。このアルゴリズムは、離散問題と連続問題の両方を解くのに使用されてきた。
【０００７】
普通のＥＤＡと異なって、Aimin Zhou他によって提案された多目的アルゴリズム（非特許文献１）のモデルは、２つの部分すなわち決定論的部分および確率論的部分からなる。決定論的モデルは、個体群の分布の規則性を取り込むことを目指し、確率論的モデルは、個体の局所的なダイナミクスを記述することを試みる。次に、モデルベースの子孫生成方法が、交叉および突然変異とヒューリスティックな形でハイブリッド化される、すなわち、すべての奇数世代でモデルベースの方法が、すべての偶数世代で遺伝学ベースの方法が、子孫の生成に使用される。
【非特許文献１】Aimin Zhou、Qingfu Zhang、Yaochu Jin、Edward Tsang、and Tatsuya Okabe、「A model-based evolutionary algorithm for bi-objective optimization」、In Congress on Evolutionary Computation、Edinburg、U.K、2005年9月、IEEE
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明の目的は、多目的最適化問題を解く新しい個体群ベースのアルゴリズムを提供することである。
【課題を解決するための手段】
【０００９】
本発明は、Aimin Zhou他によって提案された方法（非特許文献１）をさらに展開する。第１に、モデルベースの方法および遺伝学ベースの方法を、収束基準（convergence criterion）に従って組み合わせる。個体群が収束されない時には、遺伝学ベースの手法を使用し、個体群が収束される時には、モデルベースの方法を使用して、子孫を生成する。考え方は、個体群がある度合の規則性を示す、すなわち、確率的意味で収束される時に限って、アルゴリズムが、モデルベースの子孫生成の使用から利益を得るということである。第２に、モデルの確率論的部分を構成するより洗練された方法を使用することができる。第３に、バイアスをかけられたガウス雑音（雑音の平均値が０ではない）ならびに白色ガウス雑音（雑音の平均値が０である）を、モデルの確率論的部分に好ましく使用することができる。
【００１０】
既存の分布推定アルゴリズム（ＥＤＡ）と異なって、本発明は、一態様で、決定論的部分および確率論的部分からなるモデルの使用を提案する。モデルの決定論的部分は、パレート最適解の分布の規則性を取り込み、確率論的部分は、個体群の局所力学をシミュレートする。決定論的モデルは、主曲線／主面（principal curve/surface）を使用して構成され、主曲線／主面は、複数の線形曲線または線形平面（linear curves or planes）によって近似することができる。このために、個体群は、まず、局所的な主成分分析（ＰＣＡ）法を使用して複数のクラスタに分割される。確率的モデルは、バイアスをかけられた雑音モデルまたはバイアスをかけていない雑音モデルとすることができる。雑音モデルの標準偏差が、クラスタ内のすべての解の基準ベクトルへの距離の標準偏差を計算することによって推定され、これは、Aimin Zhou他で報告された方法（非特許文献１）と完全に異なる。偏りのある雑音モデルが実施される場合、雑音の平均値（バイアス）は、現在の親世代の基準ベクトルと同一クラスタの以前の世代の親の基準ベクトル（reference ventor）との間の平均距離である。
【００１１】
本発明のもう１つの好ましい態様は、遺伝学ベースまたはモデルベースのどちらの子孫生成方法を使用しなければならないかを判定する収束基準の導入である。２目的（two-objective）の場合に、これは、たとえば、各クラスタ内の個体の最大の固有値と２番目に大きい固有値との間の比によって判定でき、３目的（three-objective）の場合、各クラスタ内の個体の２番目に大きい固有値と３番目に大きい固有値との間の比によって判定することができる。固有値は、決定空間（Ｘ）または目的空間（Ｆ）のいずれかで計算することができる。
【００１２】
本発明のさらなる態様および利点は、添付図面と共に、本発明の次の詳細な説明を検討する時に明白になる。
【発明を実施するための最良の形態】
【００１３】
Ａ．主曲線ベースの規則性のモデル化
図１に、二次元空間内の主曲線の例を示す。主曲線は、データ点の集合の中央を通る滑らかな一次元（１−Ｄ）曲線である。主面は、主曲線の二次元（２−Ｄ）版である。個体群Ｐ（ｔ）が、Ｋ個のクラスタ（部分個体群）Ｃｋ＝｛Ｘｉｋ｜ｉ＝１，…，Ｎｋ｝，ｋ＝１；…；Ｋに区分されると仮定する。この区分は、Nandakishore Kambhatla and Todd K.Leen.(Dimension reduction by local principal component analysis.Neural Computation,9(7):1493-1516, 1997年10月)に記載の局所的な主成分分析（局所ＰＣＡ）クラスタ化アルゴリズムを使用して得ることができる。局所ＰＣＡクラスタ化アルゴリズムは、データの分布を、基準点（ｋ平均クラスタ化でのクラスタ中心）ではなく線形曲線（基準ベクトル）によってよりよく記述できる時に、広く使用されているｋ平均クラスタ化法より有利である。ｋ番目のクラスタＣｋで、ｉ番目に大きい固有値が、λik(i=1, ・・・, n)であり、それに対応する正規化された固有ベクトルが、Ｖikであり、クラスタＣｋの平均値が、
【数３】
0004790590.tif 000004
（ｋ＝１，…，Ｋ）である。したがって、各点の第１および第２の固有ベクトルへの射影を、
【数４】
0004790590.tif 000005
として計算することができる。ここで、ｋ＝１，…，Ｋかつｉ＝１，…，Ｎｋである。
【００１４】
データの区分を用いると、線形モデルのグループを構築して、主曲線または主面を近似することができる。１つのモデルを、各データ・クラスタ内で構築することができる。ＭＯＰが２目的問題である場合に、クラスタＣｋ内で、一次元線形モデル（1-D linear model）が構築され、このモデルは、
【数５】
0004790590.tif 000006
の値を有する点を通る直線である。第１固有ベクトルが、向きを決定する。また、このモデルは、
【数６】
0004790590.tif 000007
によって記述することができる。ここで、潜在変数（latent variable）ｓはスカラ（scalar）である。
【００１５】
３つ以上の目的を有するＭＯＰについて、局所主曲線は、線形多様体になる。目的の個数がｍの場合に、パレート・フロント（Pareto front）が（ｍ−１）次元多様体であると仮定する。しかし、いくつかのたちの悪い問題について、ｍ目的問題の次元が、ｍ−１未満である場合がある。この場合に、
【数７】
0004790590.tif 000008
の値を有する点と最初の２つの固有ベクトルＶ１ｋおよびＶ２ｋとが、主面を近似する二次元平面（2-D plane）を決定することができる。
【数８】
0004790590.tif 000009
ここで潜在変数は、ベクトルｓ＝（ｓ１；ｓ２）Ｔである。
【００１６】
Ｂ．確率モデル
本発明では、確率が、規則性を取り込む決定論的モデルおよび個体群の局所ダイナミクスをシミュレートするガウス・モデルからなる。  
Ｈｋ＝Ｈｋ（ｓ）＋ζｋ    
ここで、Ｈｋ（ｓ）は、解の分布を記述する決定論的モデルであり、ζｋは、正規分布Ｎ（μ，（δｋ）２Ｉ）を有するランダム・ベクトルであり、μおよびδは、ガウス・モデルの平均値および標準偏差であり、Ｉは、ｎ×ｎ単位行列であり、ｋ＝１，…，Ｋである。ガウス・モデルは、平均値μに０がセットされる場合にはバイアスをかけられず、そうでない場合には、ガウス・モデルにバイアスがかけられる。バイアスされたガウス・モデルが使用される場合に、平均値は、この世代のｋ番目のクラスタの基準ベクトルと前の世代のｋ番目のクラスタの基準ベクトルとの間の平均距離を計算することによって得られる。
【００１７】
局所ＰＣＡクラスタ化処理では、点とｋ番目のクラスタの基準ベクトルとの間の距離（ｄｉｋによって表される）を計算する必要がある。したがって、ｄｉｋの標準偏差を計算し、ガウス・モデルの標準偏差  
【数９】
0004790590.tif 000010
として使用することができる。ここで、ｋ＝１，…，Ｋであり、ｎは判断パラメータの個数であり、Ｎｋは、ｋ番目のクラスタ内の点の個数である。
【００１８】
Ｃ．モデルからのサンプリングによる子孫生成
モデル構築ステージでは、Ｋ個のモデルを入手する。
Ｈｋ＝Ｈｋ（ｓ）＋ζｋ、ただし、ｓ∈[ｓｋｍｉｎ, ｓｋｍａｘ]  
ここで、ｋ＝１，…，Ｋである。
【００１９】
これらのモデルを用いて、モデルからのサンプリングによって子孫を作成することができる。このサンプリングは、非常に単純である。各モデルＨｋ；ｋ＝１，…，Ｋについて、各範囲［ｓｋｍｉｎ；ｓｋｍａｘ］内でＮｋ個（ｋ番目のクラスタ内の個体数）の潜在変数を均一に選択し、上の式のモデルから新しい解を作成することができる。
【００２０】
このアルゴリズムの外挿能力を改善するために、２つの極端でモデルを外挿することによって子孫を生成することもでき、図２を参照されたい。これは、［ｓｋｍｉｎ；ｓｋｍａｘ］という範囲内ではなく、
[ｓｋｍｉｎ−ε(ｓｋｍａｘ−ｓｋｍｉｎ); ｓｋｍａｘ＋ε(ｓｋｍａｘ−ｓｋｍｉｎ)]
という範囲内で新しい点を生成することによって実現することができる。上の式で、εは、延長比であり、この延長比は、ユーザによって定義される、アルゴリズムのパラメータである。適応戦略を使用してこのパラメータを判定することもでき、延長された範囲から生成される解がよい場合には、次の世代でεを増やすことができる。そうでない場合には、次の世代でこの比を減らすことができる。
【００２１】
Ｄ．収束基準
上で述べたように、提案されるアルゴリズムは、子孫の生成に、遺伝学ベースの方法またはモデルベースの方法のいずれかを使用する。遺伝学ベースの機構またはモデルベースの機構のどちらを使用しなければならないか、個体群の分布に依存する。言い換えると、個体群が収束していない時には、子孫は、伝統的な遺伝学ベースの作働遺伝子によって生成される。個体群が、ある度合の収束を示す時には、モデルを使用して子孫を生成する。
【００２２】
個体群が収束しているかどうかを検査する、異なる基準がある場合がある。多目的最適化での収束は、単一目的最適化での収束と非常に異なる。すなわち、収束した状況で、ＭＯＯ個体群の分布が、１つの点ではなく曲線または面になる場合がある。本発明では、ｋ番目のクラスタの収束基準を、次のように定義する。
【数１０】
0004790590.tif 000011
【００２３】
上の収束基準は、どの子孫生成戦略を使用しなければならないかを判定するために、クラスタ内の個体の収束の度合を測定するのに使用される。この定義は、固有値が個体群の分散を表し、固有値の平方根が異なる向きでの偏差を表すので、穏当である。
【００２４】
この収束基準は、決定空間（パラメータ空間）内または目的空間内のいずれかで計算することができる。
【００２５】
Ｅ．アルゴリズム・フレームワーク
提案されるアルゴリズム３００の主要なフレームワークを、図３を参照して説明するが、このフレームワークは、２目的問題または３目的問題について働く。
【００２６】
ステップ３１０で、時刻ｔ＝０の初期個体群を提供する。ステップ３２０で、この個体群をクラスタの集合に区分する。このために、局所的な主成分分析（ＰＣＡ）を使用することができる。
【００２７】
次に、ステップ３３０で、クラスタごとに収束比（convergence ratio）Ψを計算する。収束比が、定義されたしきい値ρ以下である場合に（これはステップ３４０で検査される）、このアルゴリズムは、ステップ３５０で、決定論的モデルおよび確率的モデルを生成し、これらのモデルから、モデルをサンプリングすることによって子孫を生成する。収束比がしきい値より大きい場合には、ステップ３６０で、突然変異および交叉などの遺伝子ベースの方法を使用して子孫を生成する。
【００２８】
その後、ステップ３７０で、生成された子孫と親とをマージする（merge）が、ここで、パレートベースの選択（Pareto-based selection）を使用して、新しい親個体群を作成する。パレートベースの選択方法は、まず、優越比較に基づいて各個体にランクを割り当てる。解Ｘのすべての目的が、解Ｙより悪くはなく、解Ｘの少なくとも１つの目的が、Ｙよりよい場合に、解Ｘは解Ｙに優越する。解が他のいずれの解によっても優越されない場合に、１のランクが割り当てられ、１つの解によって優越される場合に、２のランクが割り当てられ、以下同様である。選択中に、最低のランクを有する個体が優先される。パレートベースの選択方法の複数の変形形態が提案されている。本発明では、Deb他（A fast and elitist multi-objective genetic algorithm:NSGA-II.IEEE Transactions on Evolutionary Computation.6(2):182-197, 2002年）で提案された非優越ソートおよび混雑トーナメント選択（crowded tournament selection）を使用する。ステップ３８０で、終了基準または停止基準が満足されるかどうかを検査する。そうでない場合には、この手順はステップ３２０に戻り、今度は新たに作成された親個体群を使用する。そうである場合には、このアルゴリズムはステップ３９０で終了する。
【００２９】
説明したアルゴリズムは、擬似コードで次のように表すことができる。
【００３０】
初期化：ｔ＝０をセットし、Ｐ（ｔ）を初期化する
複製（reproduction）：
1.1  局所ＰＣＡを用いてＰ（ｔ）をクラスタＣｋ（ｋ＝１，…，Ｋ）に区分する
1.2  各クラスタＣｋ（ｋ＝１，…，Ｋ）について、
Ψ（ｋ）＜ρの場合、一次元線形モデルまたは二次元面表面モデル（2-D plane surface model）を構築し、新たなＮｋ個の解をサンプリングしてＰｓ（ｔ）に記憶する
その他の場合、Ｃｋ（で交差および突然変異を実行して、新たなＮｋ個の解を生成してＰｓ（ｔ）に記憶する
選択：Ｐｓ（ｔ）∪Ｐ（ｔ）からＰ（ｔ＋１）を選択する
停止条件：停止条件が満足される場合には停止する；その他の場合、ｔ＝ｔ＋１をセットし、ステップ１に進む
【００３１】
このアルゴリズムをAimin Zhou他によって考えられたアルゴリズム（非特許文献１）と区別するために、彼らの方法を、ハイブリッド戦略Ａを用いるモデルベースの進化アルゴリズム（ＭＥＡ／ＨＡ）と称し、本発明によって提案される方法を、ハイブリッド戦略Ｂを用いるモデルベースの進化アルゴリズム（ＭＥＡ／ＨＢ）と称する。
【００３２】
ＭＥＡ／ＨＡと同様に、シミュレートされた２進交叉（ＳＢＸ−ηｃ）およびシミュレートされた２進突然変異（ＳＢＭ−ηｍ）が、子孫生成の遺伝学ベースの方法として採用され、ここで、ηｃおよびηｍは、それぞれ２つの作働遺伝子の分布パラメータである。ＭＥＡ／ＨＡとＭＥＡ／ＨＢの間の差は、次のように要約することができる。
【００３３】
１．ＭＥＡ／ＨＡでは、モデルベースの方法と遺伝学ベースの方法が交互に使用されるが、ＭＥＡ／ＨＢでは、モデルベースの方法と遺伝学ベースの方法が、収束基準Ψ（ｋ）に従って適応式に使用される。これは、ＭＥＡ／ＨＢにおいて、開始ステージでは遺伝学ベースの子孫生成方法が主要な役割を演じるが、後のステージでは、モデルベースの方法が、子孫の生成に、よりしばしば使用されることを意味する。
【００３４】
２．ガウス・モデルの標準偏差を推定する新しい戦略が、ＭＥＡ／ＨＢで提案され、したがって、モデルによって生成される子孫が、より良い品質を有する。ＭＥＡ／ＨＡでの各クラスタ内でのＮｋ／３個の個体のみの生成ではなく、Ｎｋ個の新しい解のすべてが、ＭＥＡ／ＨＢではモデルから生成され、ここで、Ｎｋは、ｋ番目のクラスタ内の個体数である。
【００３５】
３．ＭＥＡ／ＨＡでは、雑音モデルが白色雑音である、すなわち、雑音の平均値に、必ず０がセットされる。ＭＥＡ／ＨＢでは、雑音を、白色雑音またはバイアスをかけられた雑音とすることができる。雑音モデルのバイアスは、「探索方向」をもたらし、その結果、探索を大幅に高速化できるようになる。
【図面の簡単な説明】
【００３６】
【図１】二次元空間内の主曲線の例を示す図である。
【図２】延長を伴うモデル・サンプリングの例を示す図である。
【図３】ハイブリッド・アルゴリズムのフレームワークを示す図である。
【符号の説明】
【００３７】
３１０  個体群を初期化するステップ
３２０  個体群を複数のクラスタに区分するステップ
３３０  収束比Ψを計算するステップ
３４０  Ψ＞ρかどうかを判定するステップ
３５０  決定論的モデルを生成し、確率的モデルを生成し、モデルをサンプリングすることによって子孫を生成するステップ
３６０  突然変異および交叉を使用して子孫を生成するステップ
３７０  生成された子孫と親とをマージし、パレートベースの選択を使用して、親個体群を作成するステップ
【図１】
0004790590.tif 000013
【図２】
0004790590.tif 000014
【図３】
0004790590.tif 000015