JP2005285090A - 多目的最適化装置、多目的最適化方法および多目的最適化プログラム - Google Patents

Abstract

【課題】 最適化対象が不確実性を伴う場合でも、多様性を有する適切なパレート最適個体を短時間で得ることが可能な多目的最適化装置、多目的最適化方法および多目的最適化プログラムを提供する。
【解決手段】 多目的進化型アルゴリズム部２は、個体のパラメータの組を適応度推定部３の探索履歴記憶装置３１に与えるとともに最適化対象６に与える。最適化対象６は、個体のパラメータの組に基づいて適応度のサンプル値の組を出力する。探索履歴記憶装置３１は、個体のパラメータの組およびサンプル値の組を探索履歴として記憶する。適応度推定モジュール３０は、探索履歴記憶装置３１に記憶される探索履歴に基づいて真の適応度の推定値の組を算出し、推定値の組を多目的進化型アルゴリズム部２に与える。多目的進化型アルゴリズム部２は、複数組の推定値に基づいて遺伝的アルゴリズムにしたがってパレート最適個体集合を求める。
【選択図】 図１

Description

本発明は、最適化対象のパラメータを最適化する多目的最適化装置、多目的最適化方法および多目的最適化プログラムに関する。

従来、多目的最適化問題と呼ばれる問題クラスが存在する。例えば、ある製品のコストを最小化し、性能を最大化するという問題を考えた場合、これは２つの目的関数の多目的最適化問題となる。この場合、コストおよび性能が２つの目的関数となる。一般的には、コストを下げると性能が悪化し、性能を上げるとコストがかさむというトレードオフの関係が生じるために、多目的最適化問題の解は一つではない。

図３６は多目的最適化問題をエンジンの最適化に適用した例を示す図である。多目的最適化問題をエンジンの燃費およびトルクの最適化に適用する場合、燃費およびトルクが２つの目的関数ｆ₁，ｆ₂である。この場合、燃料噴射量、点火時期等のパラメータを調整することにより目的関数ｆ₁，ｆ₂の値を最適化する。

解Ａは、燃費が解Ｂに比べて優れているが、トルクが解Ｂに比べて劣っている。このように、エンジンの燃費とエンジンのトルクとはトレードオフの関係を有するため、複数の最適解が存在する。使用者は、複数の最適解から目的に合った解を選択することができる。例えば、スポーツ走行に適した自動二輪車に用いるエンジンには解Ａを選択し、ロングツーリングに適した自動二輪車に用いるエンジンには解Ｂを選択する。

一般に多目的最適化問題は、Ｎ個のパラメータについてＭ個の目的関数の値を、各パラメータの制約条件の範囲で最小化する問題と定義される。目的関数の値を最大化する場合は、目的関数に負の符号を付けて目的関数の値を最小化する問題に変換することとする。

このような多目的最適化問題は、一般的に単一の最適解を持たず、パレート最適解と呼ばれる概念で定義される最適解集合を持つ。ここで、パレート最適解とは、ある目的関数の値を改善するためには、少なくとも１つの他の目的関数の値を改悪せざるを得ない解のことをいい、以下のように定義される（例えば、非特許文献１参照）。

〔定義１〕あるｐ個の目的関数ｆ_k（ｋ＝１，・・・，ｐ）の２つの解ｘ１，ｘ２∈Ｆに関して、ｆ_k（ｘ１）≦ｆ_k（ｘ２）（∀ｋ＝１，・・・，ｐ）∧ｆ_k（ｘ１）＜ｆ_k（ｘ２）（∃ｋ＝１，・・・，ｐ）のとき、ｘ１はｘ２に優越するという。ここで、Ｆは解の集合である。

〔定義２〕ある解ｘ０が他のすべての解ｘ∈Ｆに優越するとき、ｘ０は最適解である。

〔定義３〕ある解ｘ０に優越する解ｘ∈Ｆが存在しないとき、ｘ０はパレート最適解（または非劣解）である。

パレート最適解集合を求めることは、目的関数のトレードオフに関して最適な解の集合を求めることになる。

図３７はパレート最適解について説明するための図である。図３７は２つの目的関数ｆ₁，ｆ₂の例を示す。解ａについての目的関数ｆ₁の値ｆ₁（ａ）は解ｂについての目的関数ｆ₁の値ｆ₁（ｂ）よりも小さく、解ａについての目的関数ｆ₂ の値ｆ₂（ａ）は解ｂについての目的関数ｆ₂の値ｆ₂（ｂ）よりも小さい。したがって、解ａは解ｂに優越する。

同様に、解ａは解ｃ，ｄに優越する。解ａに優越する解は存在しない。同様に、解ｅ，ｆに優越する解も存在しない。したがって、解ａ，ｅ，ｆはパレート最適解である。

なお、解ｇは、弱パレート最適解である。弱パレート最適解とは、ある目的関数についてのみパレート最適解に優越されないパレート解である。弱パレート最適解は、合理的な解ではなく、本来求める必要のない解である。

多目的最適化問題の解法は多数提案されている。最近注目されている方法に多目的進化型アルゴリズム（ＭＯＥＡｓ：Multiple Objective Evolutionary Algorithm）がある。この方法の最大の特徴は、進化型アルゴリズムの多点探索を利用してパレート最適解集合を一度に求めることである。得られたパレ一ト最適解集合は、その中から目的に合致した解を探す意志決定、またはパレ一ト最適解集合（パレート境界）の形状からの知見の獲得等に用いられる。

進化型アルゴリズムとして遺伝的アルゴリズム（ＧＡ：Genetic Algorithm）を多目的最適化問題に適用する研究が数多く行われている。遺伝的アルゴリズムは、生物の適応進化を模倣した計算手法である。遺伝的アルゴリズムでは、解の候補を個体と呼ぶ。また、目的関数は適応関数と呼び、適応度関数の値を適応度と呼ぶ。

この遺伝的アルゴリズムは、自然進化に見られる過程（染色体の選択、交叉および突然変異）をヒントにして、Ｊ．Ｈｏｌｌａｎｄにより提案されたアルゴリズムである。設計変数を遺伝子とみなして、初期設計の個体集合をランダムに生成し、各個体の適応度を評価する。適応度の良い個体ほど親として選択される可能性が高くなるように親を選択する。そして、交叉（遺伝子の入れ換え）および突然変異（遺伝子のランダムな変化）により子孫を作る。さらに、評価、選択、交叉および突然変異により世代を繰り返し、最適解を探索する。

具体的には、ＦｏｎｓｅｃａらのＭＯＧＡ（Multiple Objective Genetic Algorithm：例えば、非特許文献１参照）、ＤｅｂらのＮＳＧＡ−ＩＩ（Non-Dominated Sorting Genetic Algorithm-II：例えば、非特許文献２参照）、ＺｉｔｚｌｅｒらのＳＰＥＡ２（Strength Pareto Evolutionary Algorithm ２： 例えば、非特許文献３参照）等が提案されている。特に、ＮＳＧＡ−ＩＩおよびＳＰＥＡ２は優秀な多目的進化型アルゴリズムとして知られている。

多目的進化型アルゴリズムは、実応用として、超音速旅客機の翼形状を求める問題、車体またはエンジン等のパラメ一タ最適化等に用いられている。

また、不確実性を伴う適応度関数の最適化のために、探索履歴を用いて真の適応度を推定するＭＦＥＧＡ（Memory-based Fitness Estimation Genetic Algorithm）が佐野、喜多らにより提案されている（例えば、非特許文献４参照）。ここで、ＭＦＥＧＡでは、過去に得られた個体の適応度のサンプル値を探索履歴として保存し、探索履歴を参照して真の適応度を推定する。ＭＦＥＧＡは、不確実性を持つ問題に関して、同一個体の適応度を複数回サンプリングする方法および通常の遺伝的アルゴリズムに比べて優秀な探索性能を持つことが報告されている。
C.M.fonseca，p.J.Flemimg:genetic algorithms for multiobjective optimization：formulation,discussion and generalization，of the 5th international conference on genetic algorithms，pp.416-423(1993) K.Deb，S.Agrawal，A.Pratab，and T.Meyarivan:A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization:NSGA-II，KanGAL report 20001，Indian Institute of Technology，Kanpur，India(20OO) E.Zitzler,M.Laumanns,L.Thiele:SPEA2:Improving the Performance of the Strength Pareto Evolutionary A1gorithm,Technical Report 103,Computer Engineering and Communication Networks Lab(TIK),Swiss Federal Institute of Technology(ETH)Zurich(2001) 佐野，喜多：探索履歴を利用した遺伝的アルゴリズムによる不確実関数の最適化，電学論Ｃ １２２巻６号，ＰＰ−１００１−１００８（２００２） K.Ikeda, H.Kita, and S.Kobayashi : Failuer of Pareto-Based MOEAs, Does Non-Dominated Really Mean Near to Optimal？ Congress on Evolutionary Computation, pp.957-962(2001) M.D.Berg, et.al. : Computational Geometry : Algorithms and Applications, Springer-Verlag (1997) 今井浩、今井桂子，計算幾何学，情報数学講座１２，共立出版（１９９４） E.Zitzler, K.Deb, L,Thiele : Comparison of Mu1tiobjective Evo1utionary Algorithms : Empirical Results, Evolutionary Computation 8(2), pp.173-195 (2000)

しかしながら、上記非特許文献１〜非特許文献３に提案された遺伝的アルゴリズムは、いずれもベンチマ一ク問題または確率要素を含まない理想モデルのように、何度実行しても同じ解が得られるシミュレーションに適用されている。実システムまたは確率要素を含むシミュレーションのように、個体の適応度がノイズを伴う問題、いわゆる不確実性を持つ問題に上記の遺伝的アルゴリズムが適用された例は報告されていない。その理由としては次の２点が挙げられる。

第１に、最適化対象がノイズを伴うために、個体の評価ごとに最適化対象から得られる個体の適応度が変化し、進化が良好に進まないことが挙げられる。すなわち、ノイズにより適応度が悪化することにより、本来ならば良い適応度が得られるはずの個体が淘汰される。あるいは、ノイズにより適応度が向上することにより、本来ならば悪い適応度が得られるはずの個体が生き残る。このような現象が発生することにより、個体の正常な進化ができない。

第２に、得られるパレート最適解集合の形状が不明瞭であることが挙げられる。すなわち、得られる適応度がノイズを伴うために、例えば２目的最適化問題において適応度を適応度関数空間の平面にプロットした場合に、パレート境界が形成されない。したがって、従来の遺伝的アルゴリズムを意志決定または知見の獲得に用いることは困難である。

多目的最適化が必要とされる実システムおよび確率要素を含むシミュレーションとしては、例えば、交通流シミュレータを用いた信号切り替えルールの最適化およびモータの制御パラメータの最適化が挙げられる。信号切り替えルールの最適化は、２つの幹線道路の交差点およびその付近の信号を上手く切り替えて、どちらの道路も渋滞を起こさないようにすることを目的とする。モータの制御パラメータの最適化は、モータの即応性の向上およびオーバシュート量の減少を両立させることを目的とする。

しかし、交通流シミュレータの場合には、通行する車の速度および台数がランダムに与えられ、モータの場合には、センサの測定誤差等が生じるために、同一の個体（すなわちルールおよび制御パラメータ）を用いて適応度を算出しても、その都度異なる適応度が得られることになる。そのため、上記の２つの問題が生じることになる。

このような不確実性を伴う問題は、多目的最適化だけでなく、単目的最適化にとっても、非常に困難な問題である。進化型計算法においては、ノイズを統計的に処理するいくつかの方法が提案されている。最も一般的な方法は、個体を複数回サンプリングする方法である。この方法では、サンプリング回数をｎとするとノイズの分散をｎ^-0.5に低減することができる。しかしながら、この方法は、時間のかかる実システムまたは大規模シミュレーションの最適化においては、評価時間がｎ倍になるので好ましくはない。

また、非特許文献４において提案されたＭＦＥＧＡは、単目的最適化問題に対して優秀な探索性能を発揮しているが、多目的最適化問題への応用については十分に検討されていない。

本発明の目的は、最適化対象が不確実性を伴う場合でも、多様性を有する適切なパレート最適個体を短時間で得ることが可能な多目的最適化装置、多目的最適化方法および多目的最適化プログラムを提供することである。

（１）第１の発明に係る多目的最適化装置は、最適化対象に個体のパラメータの組を与え、複数の目的に対応する複数の適応度関数についての適応度のサンプル値の組を最適化対象から受ける多目的最適化装置であって、個体のパラメータの組および最適化対象から出力される適応度のサンプル値の組を記憶する記憶部と、記憶部に記憶された複数の個体に対応する複数組のサンプル値に基づいて注目個体に対応する真の適応度の推定値の組を求める推定部と、推定部により求められた推定値に基づいて新たな個体を生成し、生成された個体のパラメータの組を最適化対象および記憶部に与えるとともに、推定部により求められた複数組の推定値に基づいて評価用個体集合を多目的進化型アルゴリズムに従って評価することによりパレート最適個体集合を求める演算部とを備え、推定部は、記憶部に記憶された各個体に対応するサンプル値の組に重み付けを行い、重み付けられた複数組のサンプル値の線形和を求めることにより、注目個体に対応する適応度の推定値の組を求め、各個体の重みは、パラメータ空間上で注目個体とその個体との距離を含む関数であり、演算部は、複数の適応度関数の各々について評価用個体集合の複数の個体に対応する推定値の優劣を比較し、複数の適応度関数の各々についての比較結果に重み付けを行い、複数の適応度関数について重み付けられた複数の比較結果の線形和に基づいて評価用個体集合の複数の個体のランク付けを行い、適応度関数空間上で評価用個体集合の最上位ランクの個体の分布における疎の程度を表す分布指標に基づいて新たな個体を生成するものである。

その多目的最適化装置においては、個体のパラメータの組および最適化対象から出力される適応度のサンプル値の組が記憶部に記憶される。記憶部に記憶された複数の個体に対応する複数組のサンプル値に基づいて注目個体に対応する真の適応度の推定値の組が推定部により求められる。推定値に基づいて演算部により新たな個体が生成され、生成された個体のパラメータの組が最適化対象および記憶部に与えられる。また、求められた複数組の推定値に基づいて評価用個体集合が多目的進化型アルゴリズムに従って演算部により評価される。それにより、パレート最適個体集合が求められる。

この場合、記憶部に記憶された各個体に対応するサンプル値の組に重み付けが行われ、重み付けられた複数組のサンプル値の線形和が求められることにより、注目個体に対応する適応度の推定値の組が求められる。

各個体の重みはパラメータ空間上で注目個体とその個体との距離を含む関数であるので、真の適応度からの誤差が十分に小さい推定値を得ることができる。したがって、最適化対象から出力されるサンプル値が不確実性を有する場合でも、適切なパレート最適個体集合を得ることができる。

また、複数の適応度関数の各々について評価用個体集合の複数の個体に対応する推定値の優劣が比較され、複数の適応度関数の各々についての比較結果に重み付けが行われる。そして、複数の適応度関数について重み付けられた複数の比較結果の線形和に基づいて評価用個体集合の複数の個体のランク付けが行われる。

それにより、弱パレート最適個体を淘汰することができる。また、最適化対象の不確実性により適応度のサンプル値がノイズを含む場合に、弱パレート最適個体がパレート最適個体と個体と判定されることが防止される。したがって、最適化対象が不確実性を有する場合でも、複数の適応度間の関係を考慮した合理的なパレート最適個体を求めることが可能となる。

さらに、適応度関数空間上での最上位ランクの個体の分布において、疎の程度を表す分布指標に基づいて新たな個体が生成される。それにより、適応度関数空間上の広い範囲に偏りのなく個体を容易に生成することが可能となる。したがって、多様性を有するパレート最適個体を短時間で得ることができる。

（２）推定部は、記憶部に記憶された複数の個体をｈ_lとし、注目個体ｘに対応するサンプル値の組をＦ（ｘ）とし、パラメータ空間上で注目個体から距離ｄ_l離れた個体に対応するサンプル値の組をＦ（ｈ_l）とし、ｋ’を係数とし、ｌ＝１，…，Ｈとし、ｎを自然数とした場合に、

で表される推定式により注目個体ｘに対応する真の適応度の推定値の組ｆ’（ｘ）を算出してもよい。

この場合、パラメータ空間上で注目個体と他の個体との距離を考慮して真の適応度からの誤差がより小さい推定値を得ることができる。

（３）ｎは１であってもよい。この場合、推定値の算出において、パラメータ空間上で注目個体から遠く離れた他の個体の影響が小さくなる。それにより、真の適応度からの誤差が十分に小さい推定値を得ることができる。

（４）ｎは３であってもよい。この場合、推定値の算出において、パラメータ空間上で注目個体から遠く離れた他の個体の影響が大幅に小さくなる。それにより、真の適応度からの誤差がさらに十分に小さい推定値を得ることができる。

（５）演算部は、ｐ個の目的に対応するｐ個の適応度関数のうち一の適応度関数についての個体ｘ１およびｘ２に対応する適応度の推定値をｆ_k（ｘ１）およびｆ_k（ｘ２）とし、ｐ個の適応度関数のうち他の適応度関数についての個体ｘ１およびｘ２に対応する適応度の推定値をｆ_j（ｘ１）およびｆ_j（ｘ２）とし、ｋおよびｊを１，・・・，ｐとし、ｋはｊとは異なり、α_kjを重みとし、次式で表されるｇ_k（ｘ１，ｘ２）がｋ＝１，・・・，ｐのすべてに関してｇ_k（ｘ１，ｘ２）≦０を満足しかつｋ＝１，・・・，ｐの少なくとも１つに関してｇ_k（ｘ１，ｘ２）＜０の関係を有する場合に、個体ｘ１が個体ｘ２に優越すると判定してもよい。

（６）複数の目的が２以上のｍ目的である場合に、分布指標はｍ個の目的に対応する適応度関数空間上で注目個体に隣接するｍ個の個体が形成する単体の大きさであり、演算部は、単体の大きさに基づいて疎の程度が最も高い個体を選択し、選択された個体を用いて新たな個体を生成してもよい。

この場合、適応度関数空間上での最上位ランクの個体の分布において、分布指標に基づいて個体が疎らな領域に新たな個体を容易に生成することが可能となる。それにより、多様性の高いパレート最適個体を容易に得ることができる。

（７）複数の目的が２目的である場合に、単体の大きさは適応度関数空間上で注目個体に隣接する２個体を結ぶ直線の長さで表され、複数の目的が３目的である場合に、単体の大きさは適応度関数空間上で注目個体に隣接する３個体を頂点とする三角形の面積で表され、複数の目的が４目的である場合に、単体の大きさは適応度関数空間上で注目個体に隣接する４個体を頂点とする三角錐の体積で表されてもよい。

この場合、最上位ランクの個体の分布において個体が疎らな領域を目的の数に応じて容易に判定することができる。

（８）複数の目的が４以上のｍ目的である場合に、単体の大きさは適応度関数空間上で注目個体に隣接するｍ個の個体が形成する単体の底（ｍ−１）次元面積×高さ／ｍにより表されてもよい。

この場合、最上位ランクの個体の分布において個体が疎らな領域を目的の数に応じて容易に判定することができる。

（９）複数の目的が３以上の目的である場合に、単体はドローネ三角形分割法により形成されてもよい。この場合、分布指標である単体の大きさを容易に算出することができる。

（１０）演算部は、生成された新たな個体が評価用個体集合の個体と異なる場合に、新たな個体を評価用個体集合の下位ランクの個体と置換してもよい。

この場合、パレート最適個体の探索初期には、緩やかに悪い個体を減少させることができ、パレート最適個体の探索後期には、パレート最適個体の多様性を維持することができる。

（１１）演算部は、生成された新たな個体が評価用個体集合の個体と重複する場合に、新たな個体に最下位ランクを付与してもよい。

この場合、パレート最適個体の探索初期には、緩やかに悪い個体を減少させることができ、パレート最適個体の探索後期には、パレート最適個体の多様性を維持することができる。

（１２）演算部は、評価用個体集合の各個体を１回ずつ評価してもよい。この場合、個体の再評価が行われないので、実システムまたは大規模シミュレーションのように１個体の評価に時間を要する場合でも、最適化時間の短縮が可能となる。

（１３）推定部は、記憶部に記憶されるサンプル値の組の量が所定の記憶容量に達した場合に、最適化対象から出力されるサンプル値の組の記憶を終了してもよい。

この場合、記憶部に記憶された所定量のサンプル値の組を用いて適応度の推定値の組が求められる。それにより、最適化時間の短縮が可能となる。

（１４）演算部は、推定部により求められた推定値の組に基づいてパレート最適個体を表示してもよい。

この場合、使用者は、パレート最適個体を視覚的に認識することができるので、種々の意思決定を容易に行うことができる。

（１５）演算部は、多目的進化型アルゴリズムとして遺伝的アルゴリズムを用いて評価用個体集合の個体を評価してもよい。

この場合、遺伝的アルゴリズムに基づいて世代交代を行うことにより、最適なパレート最適個体を容易に得ることができる。

（１６）最適化対象は、機器の複数の性能を評価するための評価システムを含み、パラメータの組は、評価システムのための制御用パラメータの組を含み、複数の適応度関数は評価システムの評価により得られる複数の性能であり、適応度の組は複数の性能の値であってもよい。

この場合、評価システムに制御用パラメータの組が与えられる。評価システムにより制御用パラメータの組に基づいて機器の性能が評価され、複数の性能に対応するサンプル値の組が出力される。この多目的最適化装置によれば、評価システムが不確実性を伴う場合でも、多様性を有する適切な制御用パラメータの組の集合をパレート最適個体として短時間で得ることができる。

（１７）機器はエンジンであってもよい。この場合、評価システムにエンジン制御用パラメータの組が与えられる。評価システムによりエンジン制御用パラメータの組に基づいてエンジンの性能が評価され、複数の性能に対応するサンプル値の組が出力される。この多目的最適化装置によれば、評価システムが不確実性を伴う場合でも、多様性を有する適切なエンジン制御用パラメータの組の集合をパレート最適個体として短時間で得ることができる。

（１８）機器はモータであってもよい。この場合、評価システムにモータ制御用パラメータの組が与えられる。評価システムによりモータ制御用パラメータの組に基づいてモータの性能が評価され、複数の性能に対応するサンプル値の組が出力される。この多目的最適化装置によれば、評価システムが不確実性を伴う場合でも、多様性を有する適切なモータ制御用パラメータの組の集合をパレート最適個体として短時間で得ることができる。

（１９）評価システムは、パラメータの組に基づいて機器を制御するとともに機器の動作により発生される複数の性能の値をサンプル値として出力する機器評価装置であってもよい。

この場合、機器評価装置に制御用パラメータの組が与えられる。機器評価装置により制御用パラメータの組に基づいて機器の性能が評価され、複数の性能に対応するサンプル値の組が出力される。この多目的最適化装置によれば、機器評価装置が不確実性を伴う場合でも、多様性を有する適切な制御用パラメータの組の集合をパレート最適個体として短時間で得ることができる。

（２０）評価システムは、パラメータの組に基づいて機器の動作をシミュレーションすることにより複数の性能を評価し、評価された複数の性能の値をサンプル値の組として出力する機器シミュレータであってもよい。

この場合、機器シミュレータに制御用パラメータの組が与えられる。機器シミュレータにより制御用パラメータの組に基づいて機器の動作がシミュレーションされることにより複数の性能が評価され、評価された複数の性能に対応するサンプル値の組が出力される。この多目的最適化装置によれば、機器シミュレータが不確実性を伴う場合でも、多様性を有する適切な制御用パラメータの組の集合をパレート最適個体として短時間で得ることができる。

（２１）第２の発明に係る多目的最適化方法は、最適化対象に個体のパラメータの組を与え、最適化対象から出力される複数の目的に対応する複数の適応度関数についての適応度のサンプル値の組に基づいてパラメータを最適化する多目的最適化方法であって、個体のパラメータの組および最適化対象から出力される適応度のサンプル値の組を記憶部に記憶するステップと、記憶部に記憶された複数の個体に対応する複数組のサンプル値に基づいて注目個体に対応する真の適応度の推定値の組を求めるステップと、求められた推定値に基づいて新たな個体を生成し、生成された個体のパラメータの組を最適化対象および記憶部に与えるとともに、求められた複数組の推定値に基づいて評価用個体集合を多目的進化型アルゴリズムに従って評価することによりパレート最適個体集合を求めるステップとを備え、推定値の組を求めるステップは、記憶部に記憶された各個体に対応するサンプル値の組に重み付けを行い、重み付けられた複数組のサンプル値の線形和を求めることにより、注目個体に対応する適応度の推定値の組を求めるステップを含み、各個体の重みは、パラメータ空間上で注目個体とその個体との距離を含む関数であり、パレート最適個体を求めるステップは、複数の適応度関数の各々について評価用個体集合の複数の個体に対応する推定値の優劣を比較し、複数の適応度関数の各々についての比較結果に重み付けを行い、複数の適応度関数について重み付けられた複数の比較結果の線形和に基づいて評価用個体集合の複数の個体のランク付けを行うステップと、適応度関数空間上で評価用個体集合の最上位ランクの個体の分布における疎の程度を表す分布指標に基づいて新たな個体を生成するステップとを含むものである。

その多目的最適化方法においては、個体のパラメータの組および最適化対象から出力される適応度のサンプル値の組が記憶部に記憶される。記憶部に記憶された複数の個体に対応する複数組のサンプル値に基づいて注目個体に対応する真の適応度の推定値の組が求められる。推定値に基づいて新たな個体が生成され、生成された個体のパラメータの組が最適化対象および記憶部に与えられる。また、求められた複数組の推定値に基づいて評価用個体集合が多目的進化型アルゴリズムに従って評価される。それにより、パレート最適個体集合が求められる。

この場合、記憶部に記憶された各個体に対応するサンプル値の組に重み付けが行われ、重み付けられた複数組のサンプル値の線形和が求められることにより、注目個体に対応する適応度の推定値の組が求められる。

各個体の重みはパラメータ空間上で注目個体とその個体との距離を含む関数であるので、真の適応度からの誤差が十分に小さい推定値を得ることができる。したがって、最適化対象から出力されるサンプル値が不確実性を有する場合でも、適切なパレート最適個体集合を得ることができる。

また、複数の適応度関数の各々について評価用個体集合の複数の個体に対応する推定値の優劣が比較され、複数の適応度関数の各々についての比較結果に重み付けが行われる。そして、複数の適応度関数について重み付けられた複数の比較結果の線形和に基づいて評価用個体集合の複数の個体のランク付けが行われる。

それにより、弱パレート最適個体を淘汰することができる。また、最適化対象の不確実性により適応度のサンプル値がノイズを含む場合に、弱パレート最適個体がパレート最適個体と個体と判定されることが防止される。したがって、最適化対象が不確実性を有する場合でも、複数の適応度間の関係を考慮した合理的なパレート最適個体を求めることが可能となる。

さらに、適応度関数空間上での最上位ランクの個体の分布において、疎の程度を表す分布指標に基づいて新たな個体が生成される。それにより、適応度関数空間上の広い範囲に偏りのなく個体を容易に生成することが可能となる。したがって、多様性を有するパレート最適個体を短時間で得ることができる。

（２２）第３の発明に係る多目的最適化プログラムは、最適化対象に個体のパラメータの組を与え、最適化対象から出力される複数の目的に対応する複数の適応度関数についての適応度のサンプル値の組に基づいてパラメータを最適化する、コンピュータにより実行可能な多目的最適化プログラムであって、個体のパラメータの組および最適化対象から出力される適応度のサンプル値の組を記憶部に記憶する処理と、記憶部に記憶された複数の個体に対応する複数組のサンプル値に基づいて注目個体に対応する真の適応度の推定値の組を求める処理と、求められた推定値に基づいて新たな個体を生成し、生成された個体のパラメータの組を最適化対象および記憶部に与えるとともに、求められた複数組の推定値に基づいて評価用個体集合を多目的進化型アルゴリズムに従って評価することによりパレート最適個体集合を求める処理とをコンピュータに実行させ、推定値の組を求める処理は、記憶部に記憶された各個体に対応するサンプル値の組に重み付けを行い、重み付けられた複数組のサンプル値の線形和を求めることにより、注目個体に対応する適応度の推定値の組を求める処理を含み、各個体の重みは、パラメータ空間上で注目個体とその個体との距離を含む関数であり、パレート最適個体を求める処理は、複数の適応度関数の各々について評価用個体集合の複数の個体に対応する推定値の優劣を比較し、複数の適応度関数の各々についての比較結果に重み付けを行い、複数の適応度関数について重み付けられた複数の比較結果の線形和に基づいて評価用個体集合の複数の個体のランク付けを行う処理と、適応度関数空間上で評価用個体集合の最上位ランクの個体の分布における疎の程度を表す分布指標に基づいて新たな個体を生成する処理とを含むものである。

その多目的最適化プログラムにおいては、個体のパラメータの組および最適化対象から出力される適応度のサンプル値の組が記憶部に記憶される。記憶部に記憶された複数の個体に対応する複数組のサンプル値に基づいて注目個体に対応する真の適応度の推定値の組が求められる。推定値に基づいて新たな個体が生成され、生成された個体のパラメータの組が最適化対象および記憶部に与えられる。また、求められた複数組の推定値に基づいて評価用個体集合が多目的進化型アルゴリズムに従って評価される。それにより、パレート最適個体集合が求められる。

この場合、記憶部に記憶された各個体に対応するサンプル値の組に重み付けが行われ、重み付けられた複数組のサンプル値の線形和が求められることにより、注目個体に対応する適応度の推定値の組が求められる。

各個体の重みはパラメータ空間上で注目個体とその個体との距離を含む関数であるので、真の適応度からの誤差が十分に小さい推定値を得ることができる。したがって、最適化対象から出力されるサンプル値が不確実性を有する場合でも、適切なパレート最適個体集合を得ることができる。

また、複数の適応度関数の各々について評価用個体集合の複数の個体に対応する推定値の優劣が比較され、複数の適応度関数の各々についての比較結果に重み付けが行われる。そして、複数の適応度関数について重み付けられた複数の比較結果の線形和に基づいて評価用個体集合の複数の個体のランク付けが行われる。

それにより、弱パレート最適個体を淘汰することができる。また、最適化対象の不確実性により適応度のサンプル値がノイズを含む場合に、弱パレート最適個体がパレート最適個体と個体と判定されることが防止される。したがって、最適化対象が不確実性を有する場合でも、複数の適応度間の関係を考慮した合理的なパレート最適個体を求めることが可能となる。

さらに、適応度関数空間上での最上位ランクの個体の分布において、疎の程度を表す分布指標に基づいて新たな個体が生成される。それにより、適応度関数空間上の広い範囲に偏りのなく個体を容易に生成することが可能となる。したがって、多様性を有するパレート最適個体を短時間で得ることができる。

本発明によれば、最適化対象が不確実性を伴う場合でも、多様性を有する適切なパレート最適個体を短時間で得ることが可能となる。

（１）第１の実施の形態
まず、本発明の第１の実施の形態に係る多目的最適化装置を図１に基づき説明する。

（ａ）多目的最適化装置の機能的な構成
図１は本発明の第１の実施の形態に係る多目的最適化装置の機能的な構成を示すブロック図である。

図１の多目的最適化装置１は、多目的進化型アルゴリズムとして多目的遺伝的アルゴリズム（ＧＡ）を利用して多目的最適化問題のパレート最適個体集合を算出する。この多目的最適化装置１は、最適化対象６に接続される。

最適化対象６は、機器の性能を評価する評価システムである。評価システムは、実システムを評価する評価装置または確率要素を含むシミュレータである。実システムは、例えばエンジンまたはモータであり、評価装置は、例えばエンジン評価装置またはモータ評価装置である。また、シミュレータは、例えばエンジンシミュレータまたはモータシミュレータである。本実施の形態では、最適化対象６はエンジン評価装置である。

多目的最適化装置１は、多目的進化型アルゴリズム部２、適応度推定部３、出力インタフェース４および入力インタフェース５を含む。適応度推定部３は、適応度推定モジュール３０および探索履歴記憶装置３１を含む。

多目的進化型アルゴリズム部２および適応度推定部３の適応度推定モジュール３０は、後述するＣＰＵ１０１（図２）が多目的最適化プログラムを実行することにより実現される。探索履歴記憶装置３１は、後述する外部記憶装置１０６（図２）により構成される。

使用者１０は、多目的進化型アルゴリズム部２に複数の適応度関数（目的関数）を設定する。本実施の形態では、複数の適応度関数としては、燃費、トルク、エンジンの排気ガスに含まれるＣＯ（一酸化炭素）、ＨＣ（炭化水素）、ＮＯ_x （窒素酸化物）等の成分の濃度等のうち複数が設定される。

ここで、トレードオフの関係としては、トルクと燃費、トルクとＣＯ濃度、トルクとＨＣ濃度、燃費とＮＯ_x 濃度、ＣＯ濃度とＮＯ_x 濃度、ＨＣ濃度とＮＯ_x 濃度等が挙げられる。

また、多目的遺伝的アルゴリズムの個体とは、多目的最適化問題の解の候補であり、複数のパラメータの組および複数の適応度を有する。パラメータは、調整可能な値であり、遺伝的アルゴリズムでは、遺伝子と呼ばれる。パラメータとしては、燃料噴射量、燃料噴射時期、点火時期、スロットル開度等が挙げられる。適応度は、適応度関数の値である。以下、多目的遺伝的アルゴリズムの個体を単に個体と呼ぶ。

多目的進化型アルゴリズム部２は、後述する適応度推定モジュール３０により算出された真の適応度の推定値を受け、個体のパラメータの組を適応度推定部３の探索履歴記憶装置３１に与えるとともに出力インタフェース４を介して最適化対象６に与える。

最適化対象６は、多目的最適化装置１から与えられた個体のパラメータの組に基づいて適応度のサンプル値の組を出力する。最適化対象６から出力される各サンプル値は、後述するように、真の適応度およびノイズ成分を含む。サンプル値の詳細については、後述する。

最適化対象６から出力されるサンプル値の組は、入力インタフェース５を介して適応度推定部３の探索履歴記憶装置３１に入力される。探索履歴記憶装置３１は、個体のパラメータの組およびサンプル値の組を探索履歴として記憶する。以下、探索履歴に含まれる個体のパラメータおよびサンプル値の各組を履歴データと呼ぶ。

適応度推定モジュール３０は、探索履歴記憶装置３１に記憶される探索履歴の履歴データに基づいて真の適応度の推定値の組を算出し、推定値の組を多目的進化型アルゴリズム部２に与える。以下、真の適応度の推定値を単に適応度の推定値または推定値と呼ぶ。

多目的進化型アルゴリズム部２は、複数組の推定値に基づいて遺伝的アルゴリズムにしたがって複数の個体を発生して多点探索を行い、適応度関数をパレート最適性で評価することにより、パレート最適個体集合を同時に求める。また、多目的進化型アルゴリズム部２は、求められたパレート最適個体集合を使用者１０に提示する。

このように、多目的進化型アルゴリズム部２および適応度推定部３は、協働することにより個体のパラメータの最適化を行う。

多目的進化型アルゴリズム部２および適応度推定部３の詳細な動作については後述する。

（ｂ）多目的最適化装置のハードウエア構成
図２は図１の多目的最適化装置１のハードウエア構成を示すブロック図である。

多目的最適化装置１は、ＣＰＵ（中央演算処理装置）１０１、ＲＯＭ（リードオンリメモリ）１０２、ＲＡＭ（ランダムアクセスメモリ）１０３、入力装置１０４、表示装置１０５、外部記憶装置１０６、記録媒体駆動装置１０７および入出力インタフェース１０８を含む。

入力装置１０４は、キーボード、マウス等からなり、各種指令および各種データを入力するために用いられる。ＲＯＭ１０２にはシステムプログラムが記憶される。記録媒体駆動装置１０７は、ＣＤ（コンパクトディスク）ドライブ、ＤＶＤ（デジタルバーサタイルディスク）ドライブ、フレキシブルディスクドライブ等からなり、ＣＤ、ＤＶＤ、フレキシブルディスク等の記録媒体１０９に対してデータの読み書きを行う。

記録媒体１０９には、多目的最適化プログラムが記録されている。外部記憶装置１０６は、ハードディスク装置等からなり、記録媒体駆動装置１０７を介して記録媒体１０９から読み込まれた多目的最適化プログラムおよび各種データを記憶する。ＣＰＵ１０１は、外部記憶装置１０６に記憶された多目的最適化プログラムをＲＡＭ１０３上で実行する。

表示装置１０５は、液晶表示パネル、ＣＲＴ（陰極線管）等からなり、パレート最適個体集合等の各種画像を表示する。入出力インタフェース１０８は、図１の出力インタフェース４および入力インタフェース５を含む。この入出力インタフェース１０８には最適化対象６が無線通信または有線通信により接続される。入出力インタフェース１０８は、最適化対象６から出力されるサンプル値の組を外部記憶装置１０６に転送するとともに、多目的最適化プログラムにより生成された個体のパラメータの組を最適化対象６に与える。

なお、多目的最適化プログラムを記録する記録媒体１０９として、ＲＯＭ等の半導体メモリ、ハードディスク等の種々の記録媒体を用いることができる。また、多目的最適化プログラムを通信回線等の通信媒体を介して外部記憶装置１０６にダウンロードし、ＲＡＭ１０３上で実行してもよい。

ここで、記録媒体１０９は、コンピュータで読み取り可能な記録媒体であれば、電子的読み取り方式、磁気的読み取り方式、光学的読み取り方式またはその他のあらゆる読み取り方式の記録媒体を含むものである。例えば、上記のＣＤ、ＤＶＤおよびフレキシブルディスクの他、ＣＤＶ（コンパクトディスクビデオ）等の光学的読取方式記録媒体、ＲＡＭ、ＲＯＭ等の半導体記録媒体、ハードディスク等の磁気記録型記録媒体、ＭＯ（光磁気ディスク）等の磁気記憶型／光学的読取方式記録媒体を用いることができる。

（ｃ）最適化対象の構成
図３は最適化対象６の構成の一例を示すブロック図である。図３の最適化対象６はエンジン評価装置である。

最適化対象６は、エンジン６１、ＥＣＵ（エンジン制御ユニット）６２、排気ガス分析計６３、コントローラ６４、スロットルユニット６５およびダイナモ６６を含む。

ＥＣＵ６２は、多目的最適化装置１からシリアル通信によりパラメータの組を受ける。本例では、パラメータの組は、点火時期および燃料噴射時期である。ＥＣＵ６２は、パラメータの組に基づいてエンジン６１の点火時期および燃料噴射時期を制御する。エンジン６１からコントローラ６４に回転数、空燃比等のエンジン情報が与えられる。

コントローラ６４は、エンジン情報に基づいてスロットルユニット６５およびダイナモ６６を制御する。スロットルユニット６５は、エンジン６１の吸入空気量を調整することによりエンジン６１の出力トルクを制御する。ダイナモ６６は、負荷トルクを制御する。

排気ガス分析計６３は、エンジン６１からの排気ガス中の成分を分析し、ＨＣ濃度およびＮＯ_x濃度をサンプル値の組としてシリアル通信により多目的最適化装置１に出力する。

図４はＨＣ濃度、ＮＯ_x濃度およびＣＯ濃度と空燃比との関係を示す図である。

燃料が完全に燃焼すれば、排気ガスに二酸化炭素と水とが含まれる。しかし、運転状態が変化すると燃焼状態も変化し、排気ガスにＣＯ、ＨＣおよびＮＯ_xが含まれる。

図４に示すように、空燃比が小さいと、ＨＣ濃度およびＮＯ_x 濃度が低くなる。ＮＯ_x 濃度は空燃比が理論空燃比（１４．７）よりやや小さいときに最大となり、それ以外の領域では減少する。理論空燃比付近では、ＨＣ濃度とＮＯ_x 濃度はトレードオフの関係を有し、ＣＯ濃度とＮＯ_x 濃度とはトレードオフの関係を有する。

図３の最適化対象６は、多目的最適化装置１から個体のパラメータの組として点火時期および燃料噴射時期を受け、サンプル値の組としてＨＣ濃度およびＮＯ_x 濃度を出力する。

（ｄ）多目的最適化装置の全体処理
図５および図６は図１の多目的最適化装置１の全体処理を示すフローチャートである。

図５に示すように、最適化処理が開始されると、多目的進化型アルゴリズム部２は、初期個体集合として親個体集合Ｐを各パラメータの定められた範囲内でランダムに生成することにより親個体集合Ｐを初期化し、生成された親個体集合Ｐの各個体のパラメータの組を最適化対象６に順次与える（ステップＳ１）。それにより、最適化対象６から適応度のサンプル値の組が順次出力される。

なお、事前知識として知られているパレート最適個体が存在する場合は、そのパレート最適個体を初期個体集合の一部として用いてもよい。それにより、パレート最適個体の探索の収束性の向上が期待できる。

適応度推定部３の探索履歴記憶装置３１は、最適化対象６から親個体集合Ｐの各個体に対応するサンプル値の組を取得し、親個体集合Ｐのパラメータの組およびサンプル値の組を探索履歴として記憶する（ステップＳ２）。

次に、適応度推定部３の適応度推定モジュール３０は、探索履歴記憶装置３１に記憶された複数の個体に対応するサンプル値の組に基づいて親個体集合Ｐの各個体の適応度の推定値の組を算出する（ステップＳ３）。適応度の推定値の算出方法については後述する。

次に、多目的進化型アルゴリズム部２は、適応度の推定値の組に基づく優劣比較およびパレートランキングにより親個体集合Ｐをランクごとの個体集合に分割する（ステップＳ４）。パレートランキングについては後述する。

次に、多目的進化型アルゴリズム部２は、親個体集合Ｐの各ランクの個体集合に混雑度ソートを行う（ステップＳ５）。それにより、各ランクの個体が混雑度（混雑距離）の大きい順に並べられる。混雑度ソートについては後述する。そして、より上位のランクでより大きな混雑度を有する所定数の個体が選択され、他の個体が削除される。

さらに、多目的進化型アルゴリズム部２は、親個体集合Ｐの最上位ランク（ランク１）の個体集合から特定の３つの親個体を選択するとともに、３つの親個体に交叉操作を施すことにより子個体集合Ｃを生成し、生成された子個体集合Ｃの各個体のパラメータの組を最適化対象６に順次与える（ステップＳ６）。それにより、最適化対象６から適応度のサンプル値の組が順次出力される。

ここで、交叉操作とは、個体の遺伝子を掛け合わせることにより新たな個体を生成することをいう。特定の親個体の選択方法については後述する。

適応度推定部３の探索履歴記憶装置３１は、最適化対象６から出力される子個体集合Ｃの各個体に対応する適応度のサンプル値の組を取得し、各個体に対応するパラメータの組およびサンプル値の組を探索履歴として記憶する（ステップＳ７）。

次いで、多目的進化型アルゴリズム部２は、子個体集合Ｃと親個体集合Ｐとから個体集合Ｆを生成する（ステップＳ８）。

適応度推定部３の適応度推定モジュール３０は、探索履歴記憶装置３１に記憶された複数組のサンプル値に基づいて個体集合Ｆの各個体に対応する適応度の推定値の組を算出する（ステップＳ９）。

多目的進化型アルゴリズム部２は、適応度の推定値の組に基づく優劣比較およびパレートランキングにより個体集合Ｆをランクごとの個体集合に分割し、子個体集合Ｃにおいて親個体集合Ｐの個体と重複する個体に最下位ランクを付与する（ステップＳ１０）。

次に、多目的進化型アルゴリズム部２は、個体集合Ｆの各ランクの個体集合に混雑度ソートを行って新たな親個体集合Ｐを生成する（ステップＳ１１）。それにより、各ランクの個体が混雑度（混雑距離）の大きい順に並べられる。混雑度ソートについては後述する。そして、より上位のランクでより大きな混雑度を有する所定数の個体が選択され、他の個体が削除される。

その後、多目的進化型アルゴリズム部２は、世代数が所定の終了条件に到達したか否かを判定する（ステップＳ１２）。

ここで、世代とは、個体集合から親個体を選択する選択ステップ、交叉操作により新たな子個体を生成する交叉ステップおよび親個体と子個体とを入れ替える世代交代ステップから構成される。世代数が所定の終了条件に到達していないと判定した場合には、ステップＳ６に移行する。世代数が所定の終了条件に到達したと判定した場合には、多目的進化型アルゴリズム部２は、ステッブＳ１１で生成された親個体集合Ｐをパレート最適個体集合として使用者１０に提示し、処理を終了する。

（ｅ）多目的最適化装置の各処理の具体例
図７〜図１２は多目的最適化装置１の各処理の具体例を示す模式図である。

図７〜図１２には、２つのパラメータｘ₁，ｘ₂および２つの適応度関数ｆ₁，ｆ₂の例が示される。図３の最適化対象６の場合には、パラメータｘ₁，ｘ₂は点火時期および燃料噴射時期であり、適応度関数ｆ₁，ｆ₂はＨＣ濃度およびＮＯ_x 濃度である。

（ｅ−１）親個体集合の初期化
図７は初期化により生成される親個体集合を示す模式図であり、（ａ）は適応度関数空間における親個体集合を示し、（ｂ）はパラメータ空間における親個体集合を示す。初期化においては、図７に示すように、適応度関数空間およびパラメータ空間に複数の個体がランダムに生成される。

（ｅ−２）個体の評価方法
多目的最適化問題においては、個体が複数の適応度関数に対応する適応度を有するため、単純な値の大小では個体の優劣を比較できない。本実施の形態では、以下に説明する優劣比較、パレートランキングおよび混雑度ソートを用いて個体を評価する。

（ｅ−２−１）優劣比較
図５のステップＳ４および図６のステップＳ１０における優劣比較について説明する。この優劣比較には、以下に示すα優越戦略（α-domination strategy）が用いられる。なお、α優越戦略の詳紬については、例えば、非特許文献５に掲載されている。

図８はα優越戦略を説明するための模式図である。ここで、一般に、α優越は、次のように定義される。

あるｐ個の目的度関数ｆ_k（ｋ＝１，・・・，ｐ）の２つの解ｘ１，ｘ２∈Ｆに対して次式（８）で表されるｇ_k（ｘ１，ｘ２）が次の関係を有する場合、解ｘ１は解ｘ２にα優越する。

ｇ_k（ｘ１，ｘ２）≦０（∀ｋ＝１，・・・，ｐ）∧ｇ_k（ｘ１，ｘ２）＜０（∃ｋ＝１，・・・，ｐ）

上式において、ｆ_k（ｘ１）およびｆ_j（ｘ１）はそれぞれ解ｘ１に対応する目的度関数ｆ_kおよびｆ_jの値であり、ｆ_k（ｘ２）およびｆ_j（ｘ２）はそれぞれ解ｘ２に対応する目的度関数ｆ_kおよびｆ_jの値である。多目的遺伝的アルゴリズムでは、解ｘ１および解ｘ２が個体に相当し、目的関数ｆ_kおよびｆ_jが適応度関数に相当する。

ここで、図８において、個体Ｉ３に注目する。一般的な優越比較によれば、個体Ｉ３から適応度関数ｆ₁に平行に延びる直線Ｌ１１および個体Ｉ３から適応度関数ｆ₂に平行に延びる直線Ｌ１２で個体Ｉ３が他の個体に優越する領域が定められる。すなわち、個体Ｉ３は、直線Ｌ１１よりも上でかつ直線Ｌ１２より右の領域にある他の個体Ｉ６，Ｉ７，Ｉ８に優越する。個体Ｉ２，Ｉ４は、個体Ｉ３により優越されない。

個体Ｉ２は、適応度関数ｆ₁に関しては個体Ｉ３によりもわずかに優れているが、適応度関数ｆ₂に関しては個体Ｉ３よりもかなり劣っている。個体Ｉ４は、適応度関数ｆ₂に関しては個体Ｉ３によりもわずかに優れているが、適応度関数ｆ₁に関しては個体Ｉ３よりもかなり劣っている。このような個体Ｉ２，Ｉ４の適応度が不確実性（例えばノイズ）を有する場合には、個体Ｉ２，Ｉ４は個体Ｉ３により優越される可能性がある。

これに対して、α優越戦略によれば、個体Ｉ３から適応度関数ｆ₁の軸に近づくように傾斜した直線Ｌ１および個体Ｉ３から適応度関数ｆ₂の軸に近づくように傾斜した直線Ｌ２により個体Ｉ３が他の個体に優越する領域が定められる。すなわち、個体Ｉ３は、直線Ｌ１よりも上側でかつ直線Ｌ２より右側の領域にある個体Ｉ２，Ｉ４，Ｉ６，Ｉ７，Ｉ８に優越する。α優劣戦略によれば、個体Ｉ２，Ｉ４はパレート最適個体から排除される。

本実施の形態では、α優越戦略により複数の適応度の推定値の重み付線形和に基づいて個体の優劣比較が行われる。α優越戦略によれば、ある個体の１つの適応度が１悪くなれば、他の適応度はα悪くなる。すなわち、優劣比較において、１つの適応度の優劣が他の適応度の優劣に影響を与える。それにより、次のように、複数の適応度間の関係を考慮した合理的な解を求めることが可能となる。

弱パレート最適個体は、複数の適応度のうち少なくとも１つが他の個体に優越されない（すなわち少なくとも１つの適応度があるパレート最適解と等しい）解である。このような弱パレート最適個体は、ある適応度関数について最適解を有するが、残りの適応度関数についてはパレート最適個体に劣る。したがって、弱パレート最適個体は、合理的な解とは言えず、本来は求める必要の無い解である。そこで、α優越戦略を導入することにより、弱パレート最適個体を淘汰することができる。

また、適応度が不確実性を伴っている場合、弱パレート最適個体が不確実性によりパレート最適個体となる現象が生じる。弱パレート最適個体が不確実性によりパレート最適個体と判定されると、いつまでも淘汰されることなく個体集合中に存続することとなり、パレート最適個体の探索が停滞する原因となる。そこで、α優越戦略を導入することにより、このようなパレート最適個体と判定される弱パレート最適個体を淘汰することが可能となる。

図９はα優劣戦略による個体の優劣比較を説明するための模式図である。

図９において、個体Ｉ３は個体Ｉ２，Ｉ４，Ｉ５，Ｉ６，Ｉ７に優越しており、個体Ｉ６は個体Ｉ８に優越しており、個体Ｉ７は個体Ｉ８に優越している。個体Ｉ１，Ｉ３，Ｉ５を優越する個体はない。よって、個体Ｉ１，Ｉ３，Ｉ５パレート最適個体である。

（ｅ−２−２）パレートランキング
次に、図５のステップＳ４および図６のステップＳ１０のパレートランキングについて説明する。図１０はパレートランキングを説明するための図である。パレートランキングでは、各個体のランク付けに基づいてパレート最適個体集合を求める。

ｐ_i個の個体に優越されている個体ｘ_iのランクｒ（ｘ_i）は次式で与えられる。

ｒ（ｘ_i）＝１＋ｐ_i
ここでは、ランク１を最上位ランクとし、それ以上の数値のランクは数値が大きくなるほど下位のランクとなることにする。

図１０において、個体Ｉ１，Ｉ３，Ｉ５は他の個体に優越されていない。したがって、個体Ｉ１，Ｉ３，Ｉ５のランクは１である。個体Ｉ２，Ｉ４は１つの個体Ｉ３に優越されている。したがって、個体Ｉ２，Ｉ４のランクは２である。同様にして、個体Ｉ６のランクは６であり、個体Ｉ７のランクは５であり、個体Ｉ８のランクは８である。

（ｅ−２−３）混雑度ソート
次に、図５のステップＳ５および図６のステップＳ１１における混雑度ソートについて説明する。図１１は混雑度ソートを説明するための模式図である。

混雑度ソートでは、同じランクの各注目個体について、それに隣接する２つの個体を結ぶ線を対角線とする長方形を想定し、長方形の縦および横の辺の長さの合計で混雑度（混雑距離）を表す。混雑度の値が小さいほど注目個体は混雑した領域に存在する。同じランクの両端の個体には最大の混雑度を与える。

図１１において、個体Ｉ３の混雑度は、隣接する個体Ｉ１，Ｉ５が作る長方形ｓ１の縦および横の辺の合計で表される。個体Ｉ１の混雑度は、隣接する個体Ｉ９，Ｉ３が作る長方形ｓ２の縦および横の辺の合計で表される。個体Ｉ５の混雑度は、隣接する個体Ｉ３，Ｉ１０が作る長方形ｓ３の縦および横の辺の合計で表される。

図１２は多目的進化型アルゴリズム部２による混雑度ソートの処理を示すフローチャートである。

まず、多目的進化型アルゴリズム部２は、個体集合を適応度関数ごとにソートし、適応度関数ごとに同一ランク内で各注目個体に隣接する２つの個体を調べる（ステップＳ３１）。

次に、多目的進化型アルゴリズム部２は、各注目個体に隣接する２つの個体間の数学的距離を適応度関数ごとに算出し、各注目個体についての複数の適応度関数における数学的距離の合計を混雑度として算出する（ステップＳ３２）。ここで、数学的距離としてはユークリッド距離を用いる。

その後、多目的進化型アルゴリズム部２は、各ランクの個体集合の個体を混雑度の値の大きい順にソートする（ステップＳ３３）。

（ｅ−３）探索履歴による推定値の算出
次に、図５のステップＳ３および図６のステップＳ９における推定値の算出について説明する。

図１３は適応度推定部３の適応度推定モジュール３０による推定値の算出を説明するための模式図である。

図１の探索履歴記憶装置３１には、多目的進化型アルゴリズム部２から与えられる個体のパラメータの組および最適化対象６から出力される適応度のサンプル値の組が探索履歴ＨＳとして順次記憶される。図１３においては、個体ごとにパラメータｘ₁，ｘ₂の組およびサンプル値Ｆ₁，Ｆ₂の組が探索履歴ＨＳとして記憶されている。

適応度推定モジュール３０は、探索履歴ＨＳに基づいて各個体に対応する真の適応度を推定値として算出する。各個体に対応するパラメータの組および推定値の組は、推定結果Ｅとして図１の探索履歴記憶装置３１に記憶される。

図１３に示すように、探索履歴記憶装置３１には、個体ごとにパラメータｘ₁，ｘ₂の組および推定値ｆ₁’，ｆ₂'の組が推定結果Ｅとして記憶されている。

また、適応度推定モジュール３０は、各個体のパラメータの組および推定値の組に基づいて適応度関数空間およびパラメータ空間上のパレート最適個体集合を図２の表示装置１０５の画面に表示することができる。

図１３においては、適応度関数ｆ₁，ｆ₂からなる適応度関数空間上およびパラメータｘ₁，ｘ₂からなるパラメータ空間上にパレート最適個体集合が表示されている。パレート最適個体集合が形成する境界をパレート境界と呼ぶ。

このように、探索履歴記憶装置３１に記憶された探索履歴ＨＳを用いて個体の適応度を推定する方法をメモリベース適応度推定法（Memory-based Fitness Estimated Method：ＭＦＥＭ)と呼ぶ（非特許文献５参照）。

注目個体の推定値を算出する場合、一般に注目個体と探索履歴ＨＳの個体とは異なる探索点である。また、不確実な環境を想定するため、最適化対象６に同じパラメータの組を与えても、異なるサンプル値の組が出力される。したがって、探索履歴ＨＳのサンプル値の組から注目個体の推定値の組を算出するためには適応度関数の性質に何らかの仮定を設ける必要がある。ＭＦＥＭでは、適応度関数が注目個体からの数学的距離に応じてランダムに変動すると考えて不確実な環境をモデル化している。

注目個体をｘとし、その注目個体ｘの真の適応度をｆ（ｘ）とする。パラメータ空間において注目個体ｘから距離ｄだけ離れた個体ｈの適応度ｆ（ｈ）を考える。適応度ｆ（ｈ）の期待値がｆ（ｘ）であり、適応度ｆ（ｈ）の分散が距離ｄに比例して増大する正規分布に従うモデルは次式（１）で表される。

ｆ（ｈ）〜Ｎ（ｆ（ｘ），ｋｄ） …（１）
上式（１）において、ｋは距離による重みを決定する正の定数であり、Ｎ（ｆ（ｘ），ｋｄ）は平均がｆ（ｘ）でかつ分散がｋｄである正規分布の確率密度関数を表す。

ここで、真の適応度ｆ（ｘ）には、平均０および分散σ_E ² でかつ個体の位置に無関係な正規分布に従うノイズδが加わるものとする。この場合、個体ｘに対応するサンプル値Ｆ（ｘ）は次式のように定義される。

Ｆ（ｘ）＝ｆ（ｘ）＋δ …（２）
図１４は正規分布に従うノイズδを伴うサンプル値を示す模式図である。ここで、サンプル値Ｆ（ｘ）は適応度関数ｆ₁についてのサンプル値Ｆ₁（ｘ）および適応度関数ｆ₂についてのサンプル値Ｆ₂（ｘ）の組であり、真の適応度ｆ（ｘ）は適応度関数ｆ₁についての真の適応度ｆ₁（ｘ）および適応度関数ｆ₂についての真の適応度ｆ₂（ｘ）の組である。また、ノイズδは適応度関数ｆ₁についてのノイズδ₁および適応度関数ｆ₂についてのノイズδ₂の組である。ノイズδ_i（ｉ＝１，２）は次式で表される。

δ_i〜Ｎ（０，σ_Ei ² ） （ｉ＝１，２）
上式において、Ｎ（０，σ_Ei ² ）は平均０および分散σ_E ²である正規分布の確率密度関数を表す。

適応度推定部３は、サンプル値Ｆ（ｘ）の期待値を最小にするパレート最適個体集合を求める。このとき、個体ｈに対応するサンプル値Ｆ（ｈ）は、次式（３．１）および（３．２）としてモデル化される。

Ｆ（ｈ）〜Ｎ（ｆ（ｘ），ｋｄ＋σ_E ² ） …（３．１）
ｄ＝｜ｈ−ｘ｜・・・（３．２）
上式（３．１）において、Ｎ（ｆ（ｘ），ｋｄ＋σ_E ² ）は平均がｆ（ｘ）でありかつ分散がｋｄ＋σ_E ² である正規分布の確率密度関数を表す。

図１５は不確実な適応度関数のモデルを示す模式図である。このモデルでは、注目個体ｘから遠く離れるほどサンプル値Ｆ（ｈ）が大きく不規則に変化するものと仮定している。

このモデルに基づいて探索履歴ＨＳを用いた最尤法により真の適応度ｆ（ｘ）の推定値を算出する。

探索履歴ＨＳに記憶された個体ｈ_l（ｌ＝１，…，Ｈ）、個体ｈ_lのサンプル値Ｆ（ｈ_l）および注目個体ｘから個体ｈ_lまでの距離ｄ_l（ｌ＝１，…，Ｈ）を考えると、サンプル値Ｆ（ｈ_l），…，Ｆ（ｈ_H）が得られる確率は次式により表わすことができる。

ここで、ｐ（Ｆ（ｈ_l），ｄ_l）は、サンプル値Ｆ（ｈ_l）が得られる確率を表す確率密度関数であり、次式で表すことができる。

ここで、ｋ’＝ｋ／σ_E ² である。本実施の形態においては、定数ｋ’は事前実験にて求めるものとする。非特許文献４には、探索中に定数ｋ’を推定する方法が提案されている。提案された方法により定数ｋ’を求めてもよい。

上記式（４）および（５）を真の適応度ｆ（ｘ）の尤度と考え、最尤法を用いる。それにより、真の適応度ｆ（ｘ）の推定値ｆ’（ｘ）は、次式（６）に示すように、距離ｄ_lを含む関数により重み付けされた加重平均の式で表すことができる。

図１６は適応度推定部３の適応度推定モジュール３０による推定値の算出処理を示すフローチャートである。

まず、適応度推定モジュール３０は、多目的進化型アルゴリズム部２において親個体集合Ｐが初期化されたことを確認する（ステップＳ４１）。次に、適応度推定モジュール３０は、探索履歴記憶装置３１の探索履歴ＨＳをすべてクリアする（ステップＳ４２）。

その後、適応度推定モジュール３０は、最適化対象６から出力されるサンプル値の組を探索履歴記憶装置３１に探索履歴ＨＳとして記憶する（ステップＳ４３）。次いで、適応度推定モジュール３０は、探索履歴記憶装置３１の探索履歴ＨＳに基づいて上記式（６）より各個体に対応する真の適応度の推定値の組を算出する（ステップＳ４４）。

適応度推定モジュール３０は、多目的進化型アルゴリズム部２の処理が終了したか否かを判定する（ステップＳ４５）。

多目的進化型アルゴリズム部２の処理が終了していない場合には、ステップＳ４３に戻ってステップＳ４３〜Ｓ４５の処理を繰り返す。多目的進化型アルゴリズム部２の処理が終了した場合には、推定値の算出処理を終了する。

（ｅ−４）親個体の選択から世代交代までの方法
次に、図６のステップＳ６の特定の親個体の選択からステップＳ１１の世代交代までの方法を説明する。図１７は特定の親個体の選択から世代交代までの方法を説明するための模式図である。

図１７（ａ）に示すように、パレートランキングにより親個体集合Ｐがランク付けされる。図１７（ｂ）に示すように、親個体集合Ｐのランク１の個体集合について、適応度関数空間における隣接する各２つの個体間のユークリッド距離を分布指標として算出する。本実施の形態では、適応度関数空間は、２つの適応度関数ｆ₁およびｆ₂からなる。

ユークリッド距離が最大となる２つの個体Ｉａ，Ｉｂのうちいずれか１つの個体を第１の親個体Ｉａとして確率１／２でランダムに選択する。さらに、第２の親個体Ｉｃおよび第３の親個体Ｉｄを親個体集合Ｐからランダム選択で選択する。

本実施の形態においては、分布指標のユークリッド距離Ｌは、図１７（ｆ）に示すように、隣接する２つの個体をｘおよびｙとすると、次式により求められる。

Ｌ＝［｛ｆ₁（ｘ）−ｆ₁（ｙ）｝² ＋｛ｆ₂（ｘ）−ｆ₂（ｙ）｝² ］^1/2 …（７）
次いで、図１７（ｃ）に示すように、第１、第２および第３の親個体Ｉａ，Ｉｃ，Ｉｄから子個体集合Ｃを生成する。さらに、図１７（ｄ）に示すように、子個体集合Ｃおよび親個体集合Ｐから個体集合Ｆを生成し、個体集合Ｆに上記のα優越戦略を用いたパレートランキングを行う。このとき、子個体集合Ｃにおいて親個体集合Ｐに含まれる個体に重複する個体がある場合には、その個体に最下位ランクを付与する。

その後、図１７（ｅ）に示すように、個体集合Ｆに混雑度ソートを行い、個体のランクおよび各ランク内の混雑度に基づいて所定数の個体を選択し、残りの個体を削除する。それにより、新たな親個体集合Ｐを生成する。このようにして、世代交代が行われる。

図１８は子個体集合Ｃの生成処理を説明するための模式図である。図１８（ａ）はパラメータ空間上の親個体集合Ｐを示し、図１８（ｂ）はパラメータ空間上の子個体集合Ｃを示す。子個体集合Ｃの個体Ｉ２１のパラメータｘ₁，ｘ₂が親個体集合Ｐの個体Ｉ１１のパラメータｘ₁，ｘ₂と一致する場合には、個体Ｉ２１には最下位ランクが付与される。同様に、子個体集合Ｃの個体Ｉ２２のパラメータｘ₁，ｘ₂が親個体集合Ｐの個体Ｉ１２のパラメータｘ₁，ｘ₂と一致する場合には、個体Ｉ２２には最下位ランクが付与される。

なお、特定の親個体の選択方法は、本実施の形態に限定されず、ランク１の個体集合からユークリッド距離Ｌが最大となる２つの個体を第１および第２の親個体として選択し、第３の親個体を親個体集合Ｐからランダム選択、ルーレット選択またはトーナメント選択等の方法により選択してもよい。

図１９は多目的進化型アルゴリズム部２による特定の親個体の選択処理を示すフローチャートである。

まず、多目的進化型アルゴリズム部２は、親個体集合Ｐから選択されたランク１の個体集合を適応度関数ごとにソートする（ステップＳ５１）。

次に、多目的進化型アルゴリズム部２は、ランク１の個体集合において隣接する２つの個体間のユークリッド距離を算出する（ステップＳ５２）。

さらに、多目的進化型アルゴリズム部２は、最大のユークリッド距離を与える２つの個体のうち１つの個体を第１の親個体として確率１／２でランダムに選択し、第２の親個体および第３の親個体を親個体集合Ｐからランダム選択で選択する（ステップＳ５３）。

本実施の形態では、第１、第２および第３の親個体から交叉操作により子個体が生成される。交叉操作としては、例えば、ＵＮＤＸ（単峰性正規分布交叉：Unimodal Normal Distribution Crossover）が用いられる。

図２０はＵＮＤＸによる子個体の生成処理を示す模式図である。ＵＮＤＸでは、第１の親個体Ｐ１、第２の親個体Ｐ２および第３の親個体Ｐ３の位置関係に基づいて定められる正規分布乱数に従って子個体Ｃ１を生成する。この場合、第１の親個体Ｐ１と第２の親個体Ｐ２とを結ぶ軸ＡＸの周辺の正規分布に従って子個体Ｃ１が生成されるので、子個体Ｃ１が第１〜第３の親個体Ｐ１〜Ｐ３から遠くに離れた位置に生成されることがない。

（ｆ）第１の実施の形態の効果
本実施の形態に係る多目的最適化装置１においては、上式（６）により探索履歴記憶装置３１に記憶された各個体に対応するサンプル値の組に重み付けが行われ、重み付けられた複数組のサンプル値の線形和を用いて注目個体に対応する適応度の推定値の組が求められる。

各個体の重みは、パラメータ空間上で注目個体とその個体との距離を含む関数であるので、真の適応度からの誤差が十分に小さい推定値を得ることができる。したがって、最適化対象から出力されるサンプル値が不確実性を有する場合でも、適切なパレート最適個体集合を得ることができる。

また、α優越戦略により複数の適応度関数の各々について個体集合の複数の個体に対応する推定値の優劣が比較され、複数の適応度関数の各々についての比較結果に重み付けが行われる。そして、複数の適応度関数について重み付けられた複数の比較結果の線形和に基づいて個体集合の複数の個体のランク付けが行われる。それにより、最適化対象が不確実性を有する場合でも、複数の適応度間の関係を考慮した合理的なパレート最適個体を求めることが可能となる。

さらに、適応度関数空間上での最上位ランクの個体の分布において、隣接する個体間の距離を分布指標として用いることにより、疎らな領域に新たな子個体を容易に生成することができる。それにより、最上位ランクの個体を適応度関数空間上の広い領域に偏りなく分布するように生成することが可能となる。したがって、多様性を有するパレート最適個体を容易に得ることができる。

さらに、生成された新たな子個体が親個体集合の個体と重複する場合に、新たな子個体に最下位ランクが付与される。それにより、パレート最適個体の探索初期には、緩やかに悪い個体を減少させることができ、パレート最適個体の探索後期には、パレート最適個体の多様性を維持することができる。

また、適応度推定部３により算出された推定値の組に基づいてパレート最適個体が表示装置１０５の画面上に表示される。それにより、使用者は、パレート最適個体を視覚的に認識することができるので、種々の意思決定を容易に行うことができる。

（２）第２の実施の形態
次に、本発明の第２の実施の形態に係るに多目的最適化装置について説明する。本実施の形態に係る多目的最適化装置は、図１および図２に示した構成を有する。また、本実施の形態に係る多目的最適化装置の全体処理は、図５および図６に示した処理と同様である。

本実施の形態が第１の実施の形態と異なるのは、図５のステップＳ３および図６のステップＳ９における推定値の算出方法および図６のステップＳ６における特定の親個体の選択方法である。

（ａ）推定値の算出
本実施の形態では、真の適応度ｆ（ｘ）の推定値ｆ’（ｘ）は、改良された推定式により算出される。

上式（９）に示すように、推定値ｆ’（ｘ）はパラメータ空間上の距離ｄ_lの３乗を含む関数により重み付けされた加重平均の式で表される。

上式（９）によれば、注目個体から探索履歴ＨＳ内の個体までの距離が短いほど重みが大きくなる。一方、注目個体から探索履歴ＨＳ内の個体までの距離が長くなると、極端に重みが小さくなる。したがって、注目個体から離れた個体は推定値ｆ’（ｘ）の算出にほとんど寄与しない。

図２１は探索履歴記憶装置３１に記憶された探索履歴に基づく個体の探索を示す模式図である。図２１（ａ）は単目的最適化における探索初期の個体集合を示し、図２１（ｂ）は多目的最適化における探索初期の個体集合を示し、図２１（ｃ）は単目的最適化における探索後期の個体集合を示し、図２１（ｄ）は多目的最適化における探索後期の個体集合を示す。

図２１（ａ），（ｃ）の縦軸は適応度関数ｆを示し、横軸はパラメータｘを示す。図２１（ｂ），（ｄ）の縦軸は適応度関数ｆ₂を示し、横軸は適応度関数ｆ₁を示す。

探索初期には、図２１（ａ），（ｂ）に示すように複数の個体が分散している。探索後期には、単目的最適化では、図２１（ｃ）に示すように個体があるパラメータの値の近傍に集中し、多目的最適化では、図２１（ｄ）に示すように複数の個体がパレート最適個体集合を形成する。

このように、多目的最適化では、個体が適応度関数空間の広い範囲に分散するので、式（９）を用いることにより、注目個体から遠く離れた個体の寄与が小さくなるので、推定値の精度が高くなる。

（ｂ）特定の親個体の選択から世代交代までの方法
図２２は親個体の選択から世代交代までの方法を説明するための模式図である。本実施の形態では、３つの適応度関数ｆ₁，ｆ₂，ｆ₃の例が示される。

図２２（ａ）に示すように、パレートランキングにより親個体集合Ｐがランク付けされている。図２２（ｂ）に示すように、親個体集合Ｐのランク１の個体集合について、適応度関数空間における隣接する各３つの個体が形成する三角形の面積を分布指標として算出する。

三角形の形成には、ドローネ三角形分割（Delaunay Triangulation）の方法を用いる（非特許文献６参照）。

ここで、ドローネ三角形分割について簡単に説明する。ドローネ三角形分割は、計算幾何学（Computational Geometry）の中で重要な概念であるボロノイ図（Voronoi Diagram）の双対図形である。平面（空間）上の点集合の三角形分割の中で、種々の意味で最適な三角形分割として知られており、コンピュータグラフィクスにおけるメッシュ生成または有限要素法等にも用いられる。ドローネ三角形分割は、分割された三角形の最小角を最大にする分割方法であり、アルゴリズムとして逐次添加法、分割統治法または幾何変換を用いる方法等がある。なお、ドローネ三角形分割の詳細については、例えば非特許文献７に記載されている。

最大の三角形の面積を与える３つの個体ＩＡ，ＩＢ，ＩＣのうちいずれか１つの個体を第１の親個体ＩＡとして確率１／３でランダムに選択する。さらに、第２の親個体ＩＤおよび第３の親個体ＩＥを親個体集合Ｐからランダム選択で選択する。

次いで、図２２（ｃ）に示すように、第１、第２および第３の親個体ＩＡ，ＩＤ，ＩＥから子個体集合Ｃを生成する。さらに、図２２（ｄ）に示すように、子個体集合Ｃおよび親個体集合Ｐから個体集合Ｆを生成し、個体集合Ｆに上記のα優越戦略を用いたパレートランキングを行う。このとき、子個体集合Ｃにおいて親個体集合Ｐに含まれる個体に重複する個体がある場合には、その個体に最下位ランクを付与する。

その後、図２２（ｅ）に示すように、個体集合Ｆに混雑度ソートを行い、個体のランクおよび各ランク内の順位に基づいて所定数の個体を選択し、残りの個体を削除する。それにより、新たな親個体集合Ｐを生成する。このようにして、世代交代が行われる。

なお、特定の親個体の選択方法は、本実施の形態に限定されず、最大の三角形の面積を与える３つの個体を第１、第２および第３の親個体として選択してもよく、あるいは最大の三角形の面積を与える３つの個体のうち２つを第１および第２の親個体として選択し、第３の親個体を親個体集合Ｐからランダム選択、ルーレット選択またはトーナメント選択等の方法により選択してもよい。

また、パラメータが３つ以上の場合には、多親拡張された交叉方法、例えばＵＮＤＸ−ｍ等を用いてもよい。

図２４は多目的進化型アルゴリズム部２による特定の親個体の選択処理を示すフローチャートである。

まず、多目的進化型アルゴリズム部２は、親個体集合Ｐから選択されたランク１の個体集合をｆ_i−ｆ_j平面に正射影する（ステップＳ６１）。ここで、ｆ_iおよびｆ_jは適応度関数である。ｉ，ｊ＝１，２，３であり、かつｉ≠ｊであり、それらの組み合わせは世代ごとに変化させる。

次に、多目的進化型アルゴリズム部２は、正射影した個体集合のドローネ三角形分割を行う（ステップＳ６２）。

さらに、多目的進化型アルゴリズム部２は、ドローネ三角形分割されたランク１の個体集合に適応度関数ｆ_kの成分を高さ成分として与え、複数の三角形を３次元空間上に展開する（ステップＳ６３）。ここで、ｋ≠ｉ，ｊである。

次いで、多目的進化型アルゴリズム部２は、３次元空間上に展開された複数の三角形の面積をそれぞれ算出する（ステップＳ６４）。

面積最大の三角形を形成する３つの個体のうち１つの個体を第１の親個体として確率１／３でランダムに選択し、親個体集合Ｐから２つの個体を第２の親個体および第３の親個体としてランダム選択で選択する（ステップＳ６５）。

（ｃ）第２の実施の形態の効果
本実施の形態に係る多目的最適化装置１においては、上式（９）により探索履歴記憶装置３１に記憶された各個体に対応するサンプル値の組に重み付けが行われ、重み付けられた複数組のサンプル値の線形和を用いて注目個体に対応する適応度の推定値の組が求められる。

各個体の重みは、パラメータ空間上で注目個体とその個体との距離の３乗を含む関数であるので、パラメータ空間上で注目個体から遠く離れた他の個体の影響が十分に小さくなる。それにより、真の適応度からの誤差が十分に小さい推定値を得ることができる。したがって、最適化対象から出力されるサンプル値が不確実性を有する場合でも、適切なパレート最適個体集合を得ることができる。

また、適応度関数空間上での最上位ランクの個体の分布において、隣接する３つの個体を頂点とする三角形の面積を分布指標として用いることにより、疎らな領域に新たな子個体を容易に生成することができる。それにより、最上位ランクの個体を適応度関数空間上の広い領域に偏りなく分布するように生成することが可能となる。したがって、多様性を有するパレート最適個体を容易に得ることができる。

（３）他の実施の形態
（ａ）拡張された推定式
上記の推定式（４）および（９）を一般化すると、次式のようになる。

上式（１０）において、ｎは任意の自然数である。第１の実施の形態の推定式（４）はｎ＝１の場合を示し、第２の実施の形態の推定式（９）はｎ＝３の場合を示す。ｎ＝３が好ましいが、ｎが他の自然数であってもよい。

このように、注目個体の真の適応度の推定値は、ノイズ成分を有する適応度のサンプル値を用いずに、探索履歴ＨＳにおける他の個体の推定値の重み付け線形和により算出される。それにより、サンプル値が不確実性を有する場合でも、パレート最適個体を安定に探索することができる。

また、パラメータ空間上で注目個体と他の個体との距離のｎ乗の関数を含む重みが用いられるので、推定値の算出が広範囲に広がる他の個体の影響を大きく受けることが防止される。したがって、推定値を高精度に算出することができる。

（ｂ）親個体の選択
第１の実施の形態で示されるように、２目的最適化問題では、特定の親個体の選択のための分布指標として個体間の距離が用いられる。また、第２の実施の形態で示されるように、３目的最適化問題では、特定の親個体の選択のための分布指標として３つの個体が形成する三角形の面積が用いられる。

特定の親個体の選択のための分布指標をｍ目的最適化問題に拡張した場合、分布指標は、適応度関数空間上で隣接するｍ個の個体が形成する単体(simplex)の大きさである。ｍは２以上の自然数である。上記の単体は、ドローネ三角形分割により形成することができる。

図２４はｍ目的最適化問題に拡張された分布指標を示す図である。図２４に示すように、２目的の場合には、分布指標は隣接する２つの個体間を結ぶ直線の長さであり、３目的の場合には、分布指標は隣接する３つの個体を頂点とする三角形の面積であり、４目的の場合には、分布指標は隣接する４つの個体を頂点とする三角錐の体積である。分布指標は４次元単体の大きさであり、底体積×高さ÷４により算出される。５目的の場合には、分布指標は５次元単体の大きさであり、底４次元面積×高さ÷５により算出される。（ｍ＋１）目的の場合には、分布指標はｍ次元単体の大きさであり、底（ｍ−１）次元面積×高さ÷ｍにより算出される。

このように、分布指標に基づいて特定の親個体を選択することにより、適応度関数空間上で分布が疎らな領域で積極的な個体の探索が行われる。それにより、広い領域で個体の探索が行われるので、推定値を高精度に算出することができるとともに、適応度関数空間上の広い領域で均等にパレート最適個体を見出すことができる。

（ｃ）エンジンシミュレータへの適応例
図２５は多目的最適化装置をエンジンシミュレータに適用した例を示すブロック図である。

図２５の最適化対象６ａはエンジンシミュレータである。エンジンシミュレータは、例えばパーソナルコンピュータからなる。この最適化対象６ａは、多目的最適化装置１から与えられるパラメータの組に基づいてエンジンの動作のシミュレーションを行い、シミュレーション結果を適応度のサンプル値の組として多目的最適化装置１に出力する。

本実施の形態では、複数の適応度関数としては、燃費、トルク、エンジンの排気ガスに含まれるＣＯ（一酸化炭素）、ＨＣ（炭化水素）、ＮＯ_x （窒素酸化物）等の成分の濃度等のうち複数が設定される。

また、パラメータとしては、燃料噴射量、燃料噴射時期、点火時期、スロットル開度等が挙げられる。

図２５の多目的最適化装置１によれば、適応度関数の組およびパラメータの組を設定することにより、パレート最適個体集合を効率良く求めることができる。

（ｄ）モータ評価装置への適応例
図２６は多目的最適化装置をモータ評価装置に適用した例を示すブロック図である。

図２６の最適化対象６ｂはモータ評価装置である。モータ評価装置は、モータ、制御回路および各種検出回路により構成される。この最適化対象６ｂは、多目的最適化装置１から与えられる個体のパラメータの組に基づいてモータを制御するとともにモータの複数の性能項目を測定し、測定結果を適応度のサンプル値の組として多目的最適化装置１に出力する。

複数の適応度関数としては、立ち上がり時間、整定時間、オーバーシュート量、消費電流等のうち複数が設定される。

また、パラメータとしては、ＰＩＤ（比例積分微分：Proportional Integral Derivative）ゲイン、駆動電流等が挙げられる。

ここで、トレードオフの関係としては、立ち上がり時間とオーバーシュート量、立ち上がり時間と消費電流、整定時間とオーバーシュート量等が挙げられる。

図２６の多目的最適化装置１によれば、適応度関数の組およびパラメータの組を設定することにより、パレート最適個体集合を効率良く求めることができる。

また、パレート最適個体集合をリアルタイムに算出することにより実環境に即したモータのリアルタイム制御を行うことも可能である。

（ｅ）モータシミュレータへの適応例
図２７は多目的最適化装置をモータシミュレータに適用した例を示すブロック図である。

図２７の最適化対象６ｃはモータシミュレータである。モータシミュレータは、例えばパーソナルコンピュータからなる。この最適化対象６ｃは、多目的最適化装置１から与えられるパラメータの組に基づいてモータの動作のシミュレーションを行い、シミュレーション結果を適応度のサンプル値の組として多目的最適化装置１に出力する。

複数の適応度関数としては、立ち上がり時間、整定時間、オーバーシュート量、消費電流等のうち複数が設定される。また、パラメータとしては、ＰＩＤゲイン、駆動電流等が挙げられる。

図２７の多目的最適化装置１によれば、適応度関数の組およびパラメータの組を設定することにより、パレート最適個体集合を効率良く求めることができる。

（ｆ）多目的進化型アルゴリズムの他の例
上記実施の形態では、多目的進化型アルゴリズムとして遺伝的アルゴリズム（ＧＡ）を用いているが、これに限定されず、遺伝的アルゴリズムの代わりに、進化戦略（ＥＳ：Evolution Strategy）等の同様のアイデアに基づく計算法を用いてもよい。

なお、ＧＡ、ＥＳ等の計算法は、進化アルゴリズム（ＥＡｓ：Evolutionary Algorithms）または進化計算（Evolutionary Computation）と総称される。

（ｇ）４以上の目的への適用
上記実施の形態では、２目的および３目的の最適化を例に挙げて説明したが、本発明は、４以上の目的の最適化にも同様に適用することができる。この場合、トレードオフの関係を有する４以上の適応度関数が設定される。

（ｈ）世代交代方法
上記の図６のステップＳ１０において、子個体集合Ｃのうち親個体集合Ｐの個体と重複しない個体を親個体集合Ｐの下位の個体と入れ換えることにより新たな親個体集合Ｐを生成してもよい。

この場合、パレート最適個体の探索初期には、緩やかに悪い個体を減少させることができるとともに、パレート最適個体の探索後期には、パレート最適個体の多様性を維持することができる。

（ｉ）親個体の再評価
上記実施の形態においては、親個体の再評価を行っているが、実システムまたは大規模シミュレーションにおいて個体の評価回数に制限がある場合には、子個体のみ再評価してもよい。それにより、評価回数を低減することが可能になる。

（ｊ）サンプル値の取得の制限
探索履歴記憶装置３１に記憶されるサンプル値の量が所定の記憶容量に達した時点で探索履歴記憶装置３１へのサンプル値の取得を終了してもよい。それにより、以後は探索履歴記憶装置３１に記憶された探索履歴ＨＳに基づいて推定値を算出し、算出された推定値に基づいてパレート最適個体の探索を進めることが可能になる。

（ｋ）ランク付け
上記実施の形態では、パレートランキングにより複数の個体のランク付けが行われているが、これに限定されず、非優越ソート等の他の方法を用いて複数の個体がランク付けされてもよい。

（ｌ）各部の実現方法
上記実施の形態では、多目的進化型アルゴリズム部２、適応度推定モジュール３０および探索履歴記憶部３１がＣＰＵ１０１およびプログラムにより実現されるが、多目的進化型アルゴリズム部２、適応度推定モジュール３０および探索履歴記憶部３１の一部または全てが電子回路等のハードウエアにより実現されてもよい。

（４）実施例１および比較例１
以下の実施例１では、第１の実施の形態に係る多目的最適化装置によりベンチマーク問題を実行した。また、比較例１では、選択オペレータを除いて第１の実施の形態に係る多目的最適化装置と同様の多目的最適化装置によりベンチマーク問題を実行した。

図２８は比較例１および実施例１の多目的最適化の条件を示す図である。図２８（ａ）は比較例１の多目的最適化の条件を示し、図２８（ｂ）は実施例１の多目的最適化の条件を示し、図２８（ｃ）は比較例１および実施例１において実行するベンチマーク問題を示す。

図２８（ａ）に示すように、比較例１において、個体集合サイズは１００であり、世代数は３０であり、評価回数は３０００である。ただし、評価回数は親個体の再評価を含む。また、比較例１では、選択オペレータとしてバイナリトーナメント選択を用い、交叉オペレータとしてＵＮＤＸを用いる。

図２８（ｂ）に示すように、実施例１において、個体集合サイズは１００であり、世代数は３００であり、評価回数は３０００である。また、実施例１では、選択オペレータとして第１の実施の形態の選択方法（図１７に示した特定の親個体の選択方法）を用い、交叉オペレータとしてＵＮＤＸを用いる。さらに、図１７に示した世代交代方法を用いた。

比較例１および実施例１において、定数ｋ'（＝（ｋ₁ ，ｋ₂ ）は予備実験にて決定し、ｋ₁＝ｋ₂＝１０００とする。また、実施例１のα優越戦略におけるα（＝（α₁₂ ，α₂₁ ）は０．１とする。

ここで、評価回数とは、（世代数×子個体の数＋初期個体集合の個体の数）で求められる。

実施例１および比較例１では、ベンチマーク問題として図２８（ｃ）に示す２問題ＺＤＴ１およびＺＤＴ２を用いた（非特許文献８参照）。

ＺＤＴ１は、パレート最適解集合が凸型のパレート境界を有する２目的最適化問題である。ＺＤＴ２は、パレート最適解集合が凹型のパレート境界を有する２目的最適化問題である。ここで、ＺＤＴ１およびＺＤＴ２を２変数２目的関数の最小化問題とした。また、それぞれの目的関数には適当なノイズを加える。なお、このＺＤＴ１，ＺＤＴ２は弱パレート最適解を持つ。

図２９は比較例１および実施例１において５０世代目に得られたパレート最適個体集合を示す図である。図２９（ａ）は、サンプル値がノイズを含まない状態で比較例１の最適化により得られたパレート最適個体集合を示し、丸印は真の適応度であり、実線はパレート境界である。図２９（ｂ）は、サンプル値がノイズを含む状態で比較例１の最適化により得られたパレート最適解集合を示し、丸印はノイズを有さない真の適応度であり、菱形は推定値であり、実線はパレート境界である。図２９（ｃ）は、サンプル値がノイズを含む状態で実施例１の最適化により得られたパレート最適個体集合を示し、丸印はノイズを有さない真の適応度であり、菱形は推定値であり、実線はパレート境界である。

サンプル値がノイズを含まない状態で比較例１により最適化を行うと、図２９（ａ）に示すように、真の適応度および推定値が凸型および凹型のパレート境界に沿った形状を有する。

しかしながら、サンプル値がノイズを含む状態で比較例１により最適化を行うと、図２９（ｂ）に示すように、真の適応度および推定値が共にバラバラに散在し、パレート境界に到達しない個体が多く存在し、さらに弱パレート最適個体がパレート最適個体となっている様子がわかる。

これに対して、サンプル値がノイズを含む状態で実施例１により最適化を行うと、図２９（ｃ）に示すように、真の適応度および推定値が共にほとんど偏りない分布で凸型および凹型のパレート境界に到達しており、さらに弱パレート最適個体が排除されている様子がわかる。

このように、第１の実施の形態に係る多目的最適化装置によれば、α優越戦略を用いることにより、弱パレート最適解を持つ２目的最適化問題においても、弱パレート最適個体を排除するとともに、パレート最適個体集合における推定値を高精度に算出することができる。それにより、真の適応度および推定値をパレート境界に到達させることが可能となる。

（５）実施例２および比較例２
以下の実施例２では、第２の実施の形態に係る多目的最適化装置によりベンチマーク問題を実行した。また、比較例２では、選択オペレータを除いて第２の実施の形態に係る多目的最適化装置と同様の多目的最適化装置によりベンチマーク問題を実行した。

図３０は比較例２および実施例２の多目的最適化の条件を示す図である。図３０（ａ）は比較例２の多目的最適化の条件を示し、図３０（ｂ）は実施例２の多目的最適化の条件を示し、図３０（ｃ）は比較例２および実施例２において実行するベンチマーク問題を示す。

図３０（ａ）に示すように、比較例２において、個体集合サイズは１００であり、世代数は３０であり、評価回数は３０００である。ただし、評価回数は親個体の再評価を含む。また、比較例２では、選択オペレータとしてバイナリトーナメント選択を用い、交叉オペレータとしてＵＮＤＸを用いる。

図３０（ｂ）に示すように、実施例２において、個体集合サイズは１００であり、世代数は３００であり、評価回数は３０００である。また、実施例２では、選択オペレータとして第２の実施の形態の選択方法（図２２に示した特定の親個体の選択方法）を用い、交叉オペレータとしてＵＮＤＸを用いる。さらに、図２２に示した世代交代方法を用いた。

比較例２および実施例２において、定数ｋ'（＝ｋ₁ ，ｋ₂ ，ｋ₃ ）は予備実験にて決定し、ｋ₁ ＝ｋ₂ ＝ｋ₃ ＝１０００００とする。また、実施例２のα優越戦略におけるα（＝α₁₂ ＝α₂₃ ＝α₃₁ ）は０．１とする。

実施例２および比較例２では、ベンチマーク問題として図３０（ｃ）に示す２問題ＤＴＬＺ２を用いた。

ＤＴＬＺ２は、パレート最適解集合が凹型のパレート境界を有する３目的最適化問題である。ここで、ＤＴＬＺ２を３変数３目的関数の最小化問題とした。また、それぞれの目的関数には適当なノイズを加える。

図３１は比較例２および実施例２において得られたパレート最適個体集合を示す図である。図３１（ａ）は、サンプル値がノイズを含まない状態で比較例２の最適化により得られたパレート最適個体集合を示し、丸印は真の適応度であり、実線はパレート境界である。図３１（ｂ）は、サンプル値がノイズを含む状態で比較例２の最適化により得られたパレート最適解集合を示し、丸印はノイズを有さない真の適応度であり、菱形は推定値であり、実線はパレート境界である。図３１（ｃ）は、サンプル値がノイズを含む状態で実施例２の最適化により得られたパレート最適個体集合を示し、丸印はノイズを有さない真の適応度であり、菱形は推定値であり、実線はパレート境界である。

サンプル値がノイズを含まない状態で比較例２により最適化を行うと、図３１（ａ）に示すように、真の適応度および推定値が凹型のパレート境界に沿った形状を有する。

しかしながら、サンプル値がノイズを含む状態で比較例２により最適化を行うと、図３１（ｂ）に示すように、真の適応度および推定値が共にバラバラに散在し、パレート境界に到達しない個体が多く存在する。

これに対して、サンプル値がノイズを含む状態で実施例２により最適化を行うと、図３１（ｃ）に示すように、真の適応度および推定値が共にほとんど偏りない分布で凹型のパレート境界に到達している。

このように、第２の実施の形態に係る多目的最適化装置によれば、上記の特定の親個体の選択方法および世代交代方法を用いることにより、３目的最適化問題においても、パレート最適個体集合における推定値を高精度に算出することができる。それにより、真の適応度および推定値をパレート境界に到達させることが可能となる。

（６）実施例３
以下の実施例３では、図１の多目的最適化装置１により図３の最適化対象６の多目的最適化を実行した。

多目的最適化装置１からパラメータとして点火時期および燃料噴射時期を最適化対象６のＥＣＵ６２に与える。最適化対象６のコントローラ６４により車速および空燃比を一定に制御し、多目的最適化装置１から与えられるパラメータに基づいてＥＣＵ６２により点火時期および燃料噴射時期を変化させ、排気ガス分析計６３によりＨＣ濃度およびＮＯ_x濃度を分析する。分析されたＨＣ濃度およびＮＯ_x濃度はサンプル値として多目的最適化装置１に出力される。

図３２は実施例３の多目的最適化の条件を示す図である。図３２に示すように、実施例３において、個体集合サイズは５０であり、子個体集合サイズは１０であり、世代数は２３であり、評価回数は２８０である。また、実施例３では、選択オペレータとして第１の実施の形態の選択方法（図１７に示した特定の親個体の選択方法）を用い、交叉オペレータとしてＵＮＤＸを用いる。定数ｋ’（＝ｋ₁ ＝ｋ₂ ）は１０００００であり、世代交代方法としては第１の実施の形態の方法（図１７に示した世代交代方法）を用いる。

図３３は実施例３において得られたサンプル値および推定値を示す図である。図３３の縦軸はＮＯ_x濃度であり、横軸はＨＣ濃度である。縦軸および横軸の値は正規化された値である。丸印は２３世代（２８０個体）のサンプル値を示し、菱形印は最終世代の推定値を示す。

図３４は実施例３において得られた最終世代のパレート最適個体の推定値を適応度関数空間上に示す図である。図３４の縦軸はＮＯ_x濃度であり、横軸はＨＣ濃度である。縦軸および横軸の値は正規化された値である。

図３５は実施例３において得られた最終世代のパレート最適個体のパラメータをパラメータ空間上に示す図である。図３５の縦軸は燃料噴射時期であり、横軸は点火時期である。縦軸および横軸の値は正規化された値である。

図３４および図３５では、推定値とパラメータとの関係が容易にわかるように、複数のパレート最適個体が３つの系列１〜３に分類されている。菱形印は系列１のパレート最適個体を示し、四角印は系列２のパレート最適個体を示し、三角印は系列３のパレート最適個体を示す。

系列１はＨＣ濃度が良くＮＯ_x濃度が悪い領域であり、系列２はＨＣ濃度とＮＯ_x濃度とが平衡する領域であり、系列３はＨＣ濃度が悪くＮＯ_x濃度が良い領域である。図３５から、噴射時期を早く点火時期の値を小さくするとＨＣ濃度が改善され、噴射時期を遅く点火時期の値を大きくするとＮＯ_x濃度が改善されることがわかる。

（７）請求項の構成要素と実施の形態の各部との対応
上記実施の形態では、探索履歴記憶装置３１が記憶部に相当し、適応度推定モジュール３０が推定部に相当し、多目的進化型アルゴリズム部２が演算部に相当する。

本発明は、実システムまたは不確実性を有するシミュレーション等の最適化対象のパラメータを最適化するため等に利用することができる。

本発明の第１の実施の形態に係る多目的最適化装置の機能的な構成を示すブロック図である。 図１の多目的最適化装置のハードウエア構成を示すブロック図である。 最適化対象の構成の一例を示すブロック図である。 ＨＣ濃度、ＮＯ_x濃度およびＣＯ濃度と空燃比との関係を示す図である。 図１の多目的最適化装置の全体処理を示すフローチャートである。 図１の多目的最適化装置の全体処理を示すフローチャートである。 初期化により生成される親個体集合を示す模式図である。 α優越戦略を説明するための模式図である。 α優劣戦略による個体の優劣比較を説明するための模式図である。 パレートランキングを説明するための図である。 混雑度ソートを説明するための模式図である。 多目的進化型アルゴリズム部による混雑度ソートの処理を示すフローチャートである。 適応度推定部の適応度推定モジュールによる推定値の算出を説明するための模式図である。 正規分布に従うノイズを伴うサンプル値を示す模式図である。 不確実な適応度関数のモデルを示す模式図である。 適応度推定部の適応度推定モジュールによる推定値の算出処理を示すフローチャートである。 特定の親個体の選択から世代交代までの方法を説明するための模式図である。 子個体集合の生成処理を説明するための模式図である。 多目的進化型アルゴリズム部による特定の親個体の選択処理を示すフローチャートである。 ＵＮＤＸによる子個体の生成処理を示す模式図である。 探索履歴記憶装置に記憶された探索履歴に基づく個体の探索を示す模式図である。 親個体の選択から世代交代までの方法を説明するための模式図である。 多目的進化型アルゴリズム部による親個体の選択処理を示すフローチャートである。 ｍ目的最適化問題に拡張された分布指標を示す図である。 多目的最適化装置をエンジンシミュレータに適用した例を示すブロック図である。 多目的最適化装置をモータ評価装置に適用した例を示すブロック図である。 多目的最適化装置をモータシミュレータに適用した例を示すブロック図である。 比較例１および実施例１の多目的最適化の条件を示す図である。 比較例１および実施例１において５０世代目に得られたパレート最適個体集合を示す図である。 比較例２および実施例２の多目的最適化の条件を示す図である。 比較例２および実施例２において得られたパレート最適個体集合を示す図である。 実施例３の多目的最適化の条件を示す図である。 実施例３において得られたサンプル値および推定値を示す図である。 実施例３において得られた最終世代のパレート最適個体の推定値を適応度関数空間上に示す図である。 実施例３において得られた最終世代のパレート最適個体のパラメータをパラメータ空間上に示す図である。 多目的最適化問題をエンジンの最適化に適用した例を示す図である。 パレート最適解について説明するための図である。

符号の説明

１ 多目的最適化装置
２ 多目的進化型アルゴリズム部
３ 適応度推定部
４ 出力インタフェース
５ 入力インタフェース
６ 最適化対象
１０ 使用者
３０ 適応度推定モジュール
３１ 探索履歴記憶装置
６１ エンジン
６２ ＥＣＵ（エンジン制御ユニット）
６３ 排気ガス分析計
６４ コントローラ
６５ スロットルユニット
６６ ダイナモ
１０１ ＣＰＵ（中央演算処理装置）
１０２ ＲＯＭ（リードオンリメモリ）
１０３ ＲＡＭ（ランダムアクセスメモリ）
１０４ 入力装置
１０５ 表示装置
１０６ 外部記憶装置
１０７ 記録媒体駆動装置
１０８ 入出力インタフェース
１０９ 記録媒体
Ｃ 子個体集合
ｄ_l 距離
ｆ₁，ｆ₂ 適応度関数
Ｆ 個体集合
ＨＳ 探索履歴
Ｉ１，Ｉ２，Ｉ３，Ｉ４，Ｉ５，Ｉ６，Ｉ７，Ｉ８，Ｉ９，Ｉ１０，Ｉ１１，Ｉ１２，Ｉ２１，Ｉ２２ 個体
Ｌ１，Ｌ２，Ｌ１１，Ｌ１２ 直線
Ｐ 親個体集合
Ｐ１ 第１の親個体
Ｐ２ 第２の親個体
Ｐ３ 第３の親個体
ｓ１，ｓ２，ｓ３ 長方形
ｘ₁，ｘ₂ パラメータ

Claims (22)

1. 最適化対象に個体のパラメータの組を与え、複数の目的に対応する複数の適応度関数についての適応度のサンプル値の組を前記最適化対象から受ける多目的最適化装置であって、
   個体のパラメータの組および前記最適化対象から出力される適応度のサンプル値の組を記憶する記憶部と、
   前記記憶部に記憶された複数の個体に対応する複数組のサンプル値に基づいて注目個体に対応する真の適応度の推定値の組を求める推定部と、
   前記推定部により求められた推定値に基づいて新たな個体を生成し、生成された個体のパラメータの組を前記最適化対象および前記記憶部に与えるとともに、前記推定部により求められた複数組の推定値に基づいて評価用個体集合を多目的進化型アルゴリズムに従って評価することによりパレート最適個体集合を求める演算部とを備え、
   前記推定部は、
   前記記憶部に記憶された各個体に対応するサンプル値の組に重み付けを行い、重み付けられた複数組のサンプル値の線形和を求めることにより、注目個体に対応する適応度の推定値の組を求め、各個体の前記重みは、パラメータ空間上で注目個体とその個体との距離を含む関数であり、
   前記演算部は、
   前記複数の適応度関数の各々について前記評価用個体集合の複数の個体に対応する推定値の優劣を比較し、前記複数の適応度関数の各々についての比較結果に重み付けを行い、前記複数の適応度関数について重み付けられた複数の比較結果の線形和に基づいて前記評価用個体集合の複数の個体のランク付けを行い、
   適応度関数空間上で前記評価用個体集合の最上位ランクの個体の分布における疎の程度を表す分布指標に基づいて新たな個体を生成することを特徴とする多目的最適化装置。
2. 前記推定部は、前記記憶部に記憶された複数の個体をｈ_lとし、注目個体ｘに対応するサンプル値の組をＦ（ｘ）とし、パラメータ空間上で注目個体から距離ｄ_l離れた個体に対応するサンプル値の組をＦ（ｈ_l）とし、ｋ’を係数とし、ｌ＝１，…，Ｈとし、ｎを自然数とした場合に、
   

   

   で表される推定式により注目個体ｘに対応する真の適応度の推定値の組ｆ’（ｘ）を算出することを特徴とする請求項１記載の多目的最適化装置。
3. 前記ｎは１であることを特徴とする請求項２記載の多目的最適化装置。
4. 前記ｎは３であることを特徴とする請求項２記載の多目的最適化装置。
5. 前記演算部は、ｐ個の目的に対応するｐ個の適応度関数のうち一の適応度関数についての個体ｘ１およびｘ２に対応する適応度の推定値をｆ_k（ｘ１）およびｆ_k（ｘ２）とし、ｐ個の適応度関数のうち他の適応度関数についての個体ｘ１およびｘ２に対応する適応度の推定値をｆ_j（ｘ１）およびｆ_j（ｘ２）とし、ｋおよびｊを１，…，ｐとし、ｋはｊとは異なり、α_kjを重みとし、次式で表されるｇ_k（ｘ１，ｘ２）がｋ＝１，・・・，ｐのすべてに関してｇ_k（ｘ１，ｘ２）≦０を満足しかつｋ＝１，・・・，ｐの少なくとも１つに関してｇ_k（ｘ１，ｘ２）＜０の関係を有する場合に、個体ｘ１が個体ｘ２に優越すると判定することを特徴とする請求項１〜４のいずれかに記載の多目的最適化装置。
   

   
6. 前記複数の目的が２以上のｍ目的である場合に、前記分布指標はｍ個の目的に対応する適応度関数空間上で注目個体に隣接するｍ個の個体が形成する単体の大きさであり、
   前記演算部は、前記単体の大きさに基づいて疎の程度が最も高い個体を選択し、選択された個体を用いて新たな個体を生成することを特徴とする請求項１〜５のいずれかに記載の多目的最適化装置。
7. 前記複数の目的が２目的である場合に、前記単体の大きさは適応度関数空間上で注目個体に隣接する２個体を結ぶ直線の長さで表され、前記複数の目的が３目的である場合に、前記単体の大きさは適応度関数空間上で中膜個体に隣接する３個体を頂点とする三角形の面積で表され、前記複数の目的が４目的である場合に、前記単体の大きさは適応度関数空間上で注目個体に隣接する４個体を頂点とする三角錐の体積で表されることを特徴とする請求項６記載の多目的最適化装置。
8. 前記複数の目的が４以上のｍ目的である場合に、前記単体の大きさは適応度関数空間上で注目個体に隣接するｍ個の個体が形成する単体の底（ｍ−１）次元面積×高さ／ｍにより表されることを特徴とする請求項６記載の多目的最適化装置。
9. 前記複数の目的が３以上の目的である場合に、前記単体はドローネ三角形分割法により形成されることを特徴とする請求項６記載の多目的最適化装置。
10. 前記演算部は、生成された新たな個体が前記評価用個体集合の個体と異なる場合に、前記新たな個体を前記評価用個体集合の下位ランクの個体と置換することを特徴とする請求項１〜９のいずれかに記載の多目的最適化装置。
11. 前記演算部は、生成された新たな個体が前記評価用個体集合の個体と重複する場合に、前記新たな個体に最下位ランクを付与することを特徴とする請求項１〜９のいずれかに記載の多目的最適化装置。
12. 前記演算部は、前記評価用個体集合の各個体を１回ずつ評価することを特徴とする請求項１〜１１のいずれかに記載の多目的最適化装置。
13. 前記推定部は、前記記憶部に記憶されるサンプル値の組の量が所定の記憶容量に達した場合に、前記最適化対象から出力されるサンプル値の組の記憶を終了することを特徴とする請求項１〜１２のいずれかに記載の多目的最適化装置。
14. 前記演算部は、前記推定部により求められた推定値の組に基づいて前記パレート最適個体を表示することを特徴とする請求項１〜１３のいずれかに記載の多目的最適化装置。
15. 前記演算部は、前記多目的進化型アルゴリズムとして遺伝的アルゴリズムを用いて前記評価用個体集合の個体を評価することを特徴とする請求項１〜１４のいずれかに記載の多目的最適化装置。
16. 前記最適化対象は、機器の複数の性能を評価するための評価システムを含み、前記パラメータの組は、前記評価システムのための制御用パラメータの組を含み、前記複数の適応度関数は前記評価システムの評価により得られる前記複数の性能であり、前記適応度の組は前記複数の性能の値であることを特徴とする請求項１〜１５のいずれかに記載の多目的最適化装置。
17. 前記機器はエンジンであることを特徴とする請求項１６記載の最適化装置。
18. 前記機器はモータであることを特徴とする請求項１６記載の最適化装置。
19. 前記評価システムは、前記パラメータの組に基づいて前記機器を制御するとともに前記機器の動作により発生される複数の性能の値をサンプル値として出力する機器評価装置であることを特徴とする請求項１６記載の機器最適化装置。
20. 前記評価システムは、前記パラメータの組に基づいて前記機器の動作をシミュレーションすることにより複数の性能を評価し、評価された複数の性能の値をサンプル値の組として出力する機器シミュレータであることを特徴とする請求項１６記載の機器最適化装置。
21. 最適化対象に個体のパラメータの組を与え、前記最適化対象から出力される複数の目的に対応する複数の適応度関数についての適応度のサンプル値の組に基づいてパラメータを最適化する多目的最適化方法であって、
    個体のパラメータの組および前記最適化対象から出力される適応度のサンプル値の組を記憶部に記憶するステップと、
    前記記憶部に記憶された複数の個体に対応する複数組のサンプル値に基づいて注目個体に対応する真の適応度の推定値の組を求めるステップと、
    求められた前記推定値に基づいて新たな個体を生成し、生成された個体のパラメータの組を前記最適化対象および前記記憶部に与えるとともに、求められた複数組の推定値に基づいて評価用個体集合を多目的進化型アルゴリズムに従って評価することによりパレート最適個体集合を求めるステップとを備え、
    推定値の組を求める前記ステップは、
    前記記憶部に記憶された各個体に対応するサンプル値の組に重み付けを行い、重み付けられた複数組のサンプル値の線形和を求めることにより、注目個体に対応する適応度の推定値の組を求めるステップを含み、各個体の前記重みは、パラメータ空間上で注目個体とその個体との距離を含む関数であり、
    前記パレート最適個体を求める前記ステップは、
    前記複数の適応度関数の各々について前記評価用個体集合の複数の個体に対応する推定値の優劣を比較し、前記複数の適応度関数の各々についての比較結果に重み付けを行い、前記複数の適応度関数について重み付けられた複数の比較結果の線形和に基づいて前記評価用個体集合の複数の個体のランク付けを行うステップと、
    適応度関数空間上で前記評価用個体集合の最上位ランクの個体の分布における疎の程度を表す分布指標に基づいて新たな個体を生成するステップとを含むことを特徴とする多目的最適化方法。
22. 最適化対象に個体のパラメータの組を与え、前記最適化対象から出力される対応する複数の適応度関数についての適応度のサンプル値の組に基づいてパラメータを最適化するコンピュータにより実行可能な多目的最適化プログラムであって、
    個体のパラメータの組および前記最適化対象から出力される適応度のサンプル値の組を記憶部に記憶する処理と、
    前記記憶部に記憶された複数の個体に対応する複数組のサンプル値に基づいて注目個体に対応する真の適応度の推定値の組を求める処理と、
    求められた前記推定値に基づいて新たな個体を生成し、生成された個体のパラメータの組を前記最適化対象および前記記憶部に与えるとともに、求められた複数組の推定値に基づいて評価用個体集合を多目的進化型アルゴリズムに従って評価することによりパレート最適個体集合を求める処理とをコンピュータに実行させ、
    推定値の組を求める前記処理は、
    前記記憶部に記憶された各個体に対応するサンプル値の組に重み付けを行い、重み付けられた複数組のサンプル値の線形和を求めることにより、注目個体に対応する適応度の推定値の組を求める処理を含み、各個体の前記重みは、パラメータ空間上で注目個体とその個体との距離を含む関数であり、
    前記パレート最適個体を求める前記処理は、
    前記複数の適応度関数の各々について前記評価用個体集合の複数の個体に対応する推定値の優劣を比較し、前記複数の適応度関数の各々についての比較結果に重み付けを行い、前記複数の適応度関数について重み付けられた複数の比較結果の線形和に基づいて前記評価用個体集合の複数の個体のランク付けを行う処理と、
    適応度関数空間上で前記評価用個体集合の最上位ランクの個体の分布における疎の程度を表す分布指標に基づいて新たな個体を生成する処理とを含むことを特徴とする多目的最適化プログラム。

Images