(57)【要約】【課題】多目的最適化へのファジィ選好の利用を改善する。【解決手段】本発明は、進化的アルゴリズムを用いた多目的問題の最適化のための方法を提供する。この方法は、初期個体群を親として生成するステップと、前記親を再生して、複数の子個体を生成するステップと、複数の目的関数の加重和から構成される適合度関数を用いて、前記子個体の品質を評価するステップと、最高の評価値を備える子を、次の進化サイクルの親として選択するステップと、を有する。前記最適化の間に、前記複数の目的関数の重みは、全ての重みのために予め決められた区間の中でそれぞれ動的に変動する。
2005515564.tif 000002
【特許請求の範囲】
【請求項１】
進化的アルゴリズムを用いた多目的問題の最適化のための方法であって、
初期個体群を親として生成するステップと、
前記親を再生して、複数の子個体を生成するステップと、
複数の目的関数の加重和から構成される適合度関数を用いて、前記子個体の品質を評価するステップと、
最高の評価値を備える子を、次の進化サイクルの親として選択するステップと、
を有し、
前記最適化の間に、前記複数の目的関数の重みは、全ての重みのために予め決められた区間の中でそれぞれ動的に変動することを特徴とする方法。
【請求項２】
言語的選好関係によって表される人間の選好はパラメータ化および実数化された選好関係に変換され、重み変動の許容範囲を定める前記区間を生成することを特徴とする、請求項１に記載の方法
【請求項３】
前記パラメータに特定の値を割り当てる代わりに、該パラメータに全ての許容値を取らせることにより、前記パラメータ化された選好関係は実数化された前記区間に変換されることを特徴とする、請求項２に記載の方法
【請求項４】
前記複数の目的関数の重みは、各世代の個々の子個体の間で、既定の区間内でランダムに再分配されることを特徴とする、請求項１乃至請求項３に記載の方法
【請求項５】
前記複数の目的関数の重みは、最適化の進行に伴い既定の区間内で段階的に変動されることを特徴とする、請求項１乃至請求項３に記載の方法
【請求項６】
前記重みは、周期関数にしたがって、前記区間内で変動することを特徴とする、請求項５に記載の方法
【請求項７】
前記子個体は、同じ世代では同じ重みを備えることを特徴とする、請求項５および請求項６に記載の方法。
【請求項８】
周期的な変動は、前記世代数に依存するサイン関数の形状を備えることを特徴とする、請求項５乃至請求項７に記載の方法。
【請求項９】
計算装置を実行するときに、上記請求項に記載の方法を実行することを特徴とする、コンピュータソフトウェアプログラム製品。
【請求項１０】
請求項１乃至請求項８に記載の方法を利用して、空気力学または流体力学的なボディ最適化する方法であって、前記別々の目的は、圧力損失、ナビエストークス方程式で計算される排気角度、および幾何学的拘束を含む、最適化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、進化的アルゴリズム（evolutionary algorithm）を用いた多目的問題（multi-objective problem）の最適化方法、および空気力学または流体力学によるボディの最適化のための該方法の利用に関する。本発明はさらに、当該方法を実装するコンピュータソフトウェアプログラム製品に関する。
【背景技術】
【０００２】
本発明の背景分野は進化的アルゴリズムである。そこで、図１を参照して始めに、進化的アルゴリズムに関する周知のサイクルを説明する。
【０００３】
ステップＳ１において、最適化される目的パラメータ（object parameter）は、「個体（individual）」と呼ばれる文字列（string）に符号化される。親個体としてこのような個体が複数生成され、この親世代の各個体の品質（適合度（fitness））が評価される。ステップＳ２において、突然変異（mutation）および交叉（recombination）と呼ばれる遺伝的演算子を適用することにより、親世代は再生成される。ステップS3によって再生成された新しい個体群は子（offspring）世代と呼ばれる。子世代の適合度は、ステップＳ４において、最適化の目的である適合度関数を用いて評価される。最後に、計算された適合度に依存して、ステップＳ５において最適な子個体が選択される（適者生存（survival of the fittest））。この最適な子個体は、ステップＳ６において終了条件が満たされないとき、次世代サイクルの親として用いられる。
【０００４】
各個体の適合度を評価する前に、進化的アルゴリズムで使われている符号化スキームに基づいて、逆に復号化する必要がある。ステップＳ２に注意すべきである。この進化的最適化のアルゴリズムは、以下の擬似コードで表現することができる：
【０００５】
t := 0
encode and initialize P(0)
decode and evaluate P(0)
do
recombine P(t)
mutate P(t)
decode P(t)
evaluate P(t)
P(t+1) := select P(t)
Encode P(t+1)
t := t + 1
until terminate
【０００６】
ここで、P(0)は初期個体群（t=0）を示し、P(t)はｔ番目の後継世代（t>0）の個体群を示し、ｔは世代数の指標を示す（ｔ∈Ｎ０）。
【０００７】
このような進化的アルゴリズムは、不連続でマルチモーダルな目的関数（objective function）に適切なロバスト最適化プログラム（optimizer）であることが知られている。ゆえに、進化的アルゴリズムは、例えば、予備的な（preliminary）タービン設計、タービンブレード設計、多原理（multi-disciplinary）ウイングプラットフォーム設計、および軍用機体の予備的な設計を含む、機械的および空気力学的な最適化問題にうまく適用されてきている。例えば、進化的アルゴリズムの詳細は、非特許文献１および非特許文献２で調べることが可能である。
【０００８】
本発明の枠組みでは、進化的アルゴリズムは多数の目的の同時最適化（simultaneous optimization）に適用される。この同時最適化は、実際的な工学および設計の問題における典型的な特徴である。多目的最適化（multi-objective optimization、MOO）の原理は、単目的（single-objective）最適化の原理とは異なる。単目的最適化において、最適な設計の解を見つけることが目標であり、目的関数の最小値または最大値に相当する。それと反対に、相反する目的を含む多目的最適化では、単一の最適解は存在しない。
【０００９】
異なる目的の間のインタラクションのために、パレート最適解（Pareto-optimal solutions）として知られる妥協解（compromise solutions）の集合が必要となる。「パレート最適化」および「パレートフロント（Pareto-front）」の定義は、非特許文献３で調べることができる。
【００１０】
これらのパレート最適解は、別の設計指針などを入れない限り等価であるので、多目的最適化の目的はできる限り多くのパレート最適解を見つけることになる。一度そのような解が見つかれば、通常は他の設計指針を含むさらに高いレベルの意思決定（decision making）を用いて、実施のために１つの解を選択する。
【００１１】
通常、多目的最適化では以下のような2つの目標がある：
（i）真のパレート最適解に近い解を見つけること
（ii）多様性のある解を見つけること
【００１２】
1番目の課題は、獲得した解において、最適条件を満たすことが望ましい。2番目の課題は、特定の目的関数に対してバイアスをかけないことが望ましい。
【００１３】
多目的最適化問題の取り扱いにおいて、一般的な探索および最適化方法は非効率的である。その理由は以下の通りである：
−一般的方法の大部分は、一度の実行では複数の解を発見することができない。これにより、所望のパレート最適解の数と同じ回数だけこの一般的方法を実行するよう要求される。
−これら一般的方法の複数回実行は、多様性のあるパレート最適解を発見するのを保障しない。
−一般的手法の大部分は、離散変数についての問題および複数の最適解を備える問題を効率的に処理することはできない。
【００１４】
これと反対に、過去数年間に渡る進化的探索アルゴリズムの研究は、上述の古典的方法の問題の大部分を解消するように、この進化的方法が効率的に使用可能であることを示してきた。この進化的方法は探索に個体群（a population of solutions）を使うので、原則的に複数のパレート最適解が一度の実行で発見可能である。多様性保持メカニズム（diversity-preserving mechanisms）の利用が進化的探索アルゴリズムに加えられ、多様性のあるパレート最適解を発見することが可能である。
【００１５】
多数の進化的多目的アルゴリズム（evolutionary multi-objective algorithm、ＥＭＯＡ）が提案されている。これまで、進化的多目的最適化への３つの主要なアプローチがある。これらのアプローチは、すなわち、線形結合アプローチ（aggregation approach）、個体群を基準とした（population-based）非パレートアプローチ（non-Pareto approach）、およびパレート型アプローチ（Pareto-based approach）である。近年、パレート型アプローチが進化的計算のコミュニティで注目を集めており、いくつかの有効なアルゴリズムが提案されている。
【００１６】
しかし残念なことに、パレート型アプローチは、非常に時間を消費することが多い。
【００１７】
これとは異なり、多目的最適化への加重線形結合アプローチ（weighted aggregation approach）は実施するのに大変容易であり、計算的に効率的である。
【００１８】
通常、重みが問題に特化した事前知識を用いて固定されている場合、線形結合アプローチはパレート解を1つだけ提供することができる。しかしながら、最適化の間に重みを変更することによって、この方法を用いて1つ以上のパレート解を発見することも可能である。異なる目的の重みは、１つ以上のパレート解を得るために染色体（chromosome）の中に符号化される。表現型適合度シェアリング（phenotypic fitness sharing）が重みの組み合わせの多様性を維持するために用いられ、アルゴリズムが適切に機能できるように交配制限（mating restriction）が要求される。
【００１９】
従来の線形結合アプローチの欠点が、最適化の簡易性および効率性を保ちつつ系統的に重みを変更することによって克服できることが発見されている。パレートフロントを求める最適化計算の間に重みを変更する方法として、３つの方法が提案されている。ランダム加重線形結合（randomly-weighted aggregation、ＲＷＡ）方法は、個体群内で分割して、重みが各世代で再分配される。対して、動的加重線形結合（dynamically-weighted aggregation、ＤＷＡ）方法は、進化が継続するときに重みを段階的に変更する。パレート最適フロントが凹型ならば、バンバン加重線形結合（bang-bang weighted aggregation、BWA）を用いることができる。選好を実現するために、ＲＷＡおよびＤＷＡの両方を用いることができる。
【００２０】
ランダム加重線形結合
進化的最適化の枠組みにおいて、最適化の一度の実行で複数のパレート最適解を得るために、通常、個体群（population）を利用する。個体群のｉ番目の個体が、世代ｔにおいて重みの組み合わせ（ｗ1i(ｔ)、ｗ2i(ｔ)）を備えるとすれば、進化的アルゴリズムは異なるパレート解を発見することが可能である。これを実現するために、重みの組み合わせは各個体に一様かつランダムに分配される必要があり、各世代で再分配が必要である：
ｗ1i(ｔ) ＝ rdm（P）／ P
ｗ2i(ｔ) ＝ 1.0 − ｗ1i(ｔ)
ここで、ｉは個体群ｉ番目の個体を示し（ｉ＝１，２，…，Ｐ）、Ｐは個体群のサイズであり（Ｐ∈Ｎ）、ｔは世代数の指標を示す（ｔ∈Ｎ０）。
【００２１】
関数rdm(P)は、［０、Ｐ］間の乱数値を等確率で生成する関数である。このように、各個体に一様に分配されたランダムな重みの組み合わせ（ｗ1i(ｔ)、ｗ2i(ｔ)）が獲得される。ここで、０ ≦ ｗ1i、ｗ2i ≦ １、およびｗ1i ＋ ｗ2i ＝ １である。ここで、重みの組み合わせは各世代で再生成されることに注意すべきである。
【００２２】
動的加重線形結合
動的加重線形結合（DWA）アプローチにおいて、全ての個体は同一の重みの組み合わせを備えており、この重みは一世代ごとに段階的に変更される。一度個体がパレートフロント上の任意の点に到達すると、パレートフロントが凸状の場合、重みを徐々にゆっくりと変更することでパレートフロントに沿って移動するよう維持される。パレートフロントが凹状の場合でも、異なった移動形態ではあるが、パレートフロントに沿って移動する。重みは次のように変更される：
ｗ1(ｔ) ＝ ｜sin（２πｔ／Ｆ）｜
ｗ2(ｔ) ＝ 1.0 − ｗ1(ｔ)
ここで、ｔは世代数である。ここでは、サイン関数が用いられる。サイン関数は０から１の間の平易な周期関数であるからである。この場合、重みｗ1(ｔ)およびｗ2(ｔ)は、一世代ごとに周期的に０から１へと変更する。変更周波数はFで調整可能である。アルゴリズムがパレートフロント上で解に収束することができるように、この周波数はあまり高くすべきではない。一方、全最適化の間に少なくとも2回は重みを０から１へ変更させるのが妥当であると思われる。
【００２３】
上述の方法では、全ての目的が同一の重要度であるとみなされている。この場合、重みはRWAおよびDWAによって０から１の間で変更され、すべてのパレート最適解を獲得する。しかしながら、多くの実世界アプリケーションにおいて、異なる目的は異なる重要度である場合がある。したがって、すべてのパレートフロントを獲得することが目標ではなく、パレートフロントのうち所望の部分のみを獲得することが目標である。各目的の重要度は、通常、人間のユーザによって選好（preferences）の見地から特定される。例えば、2つの目的を備える問題において、ユーザは一方の目的が他方より重要であると思うことが可能である。所望のパレート最適解を獲得するために、多目的最適化に選好が組み込まれる必要がある。重みを０から１の間で変更する代わりに、重みがWminからWmaxの間で変更される。ここで、０ ≦ Wmin ＜ Wmax ≦ １であり、WminおよびWmaxは選好によって定義される。通常、選好は最適化前、最適化中、または最適化後に組み込まれる。本発明において、選好は最適化前に組み込まれる。
【００２４】
非特許文献４で論じられるように、最適化前のファジィ選好の組み込みは以下の２つの方法で実現することができる。
−加重和（Weighted Sum）：選好を事前知識として使用して、各目的の重みを決定。それから重みを直接適用して、目的を合計してスカラーにする。この場合、ただ1つの解が獲得される。
【００２５】
−加重パレート方法（Weighted Pareto Method）：非ファジィ（non-fazzy）重みが加重パレート非優性（non-dominance）を定義するために用いられる：
【００２６】
【数１】
2005515564.tif 000003
【００２７】
ここで、Ｕ，Ｖは、
U := { ui | i = 1, 2, 3, …, k}   ただしui ∈ [0,1]
V := { vi | i = 1, 2, 3, …, k}   ただしvi ∈ [0,1]
である、また、
【数２】
2005515564.tif 000004
である。
【００２８】
ファジィ選好を多目的最適化（MOO）へ適用する一般的な手順が図２に示されている。選好がMOOに適用されるようになる前に、これらの選好はまずクリスプ重み（crisp weight）に変換されなければならないことが見受けられる。変換の手順は以下の通りである：
【００２９】
L個のエキスパート（インデックスｍ＝１，２，…，Lを備える）および選好関係（preference relation）Pｍが与えられる。ここでPｍは、（ｋ×ｋ）のマトリクスであり、その成分ｐijは、目的Oｊに対する目的Oｉの言語的選好（linguistic preference）を示す（インデックスｉ、ｊ＝１，２，…，ｋ）。その後、集団意思決定法（group decision making method）に基づき、共通の集合選好（collective preference）PCに結合される。該選好マトリクスPCの各要素は、以下の言語的条件（linguistic term）のうちの１つによって定義される：
【００３０】
“さらに大きな重要度（much more important）”（MMI）
“より大きな重要度（more important）”（MI）
“同じ重要度（equally important）”（EI）
“より小さな重要度（less important）”（LI）
“さらに小さな重要度（much less important）”（MLI）
【００３１】
簡潔にするために、集合選好を示す上付き文字ｃは、以下の文章では割愛される。
【００３２】
言語的条件を実数値を有する重みに変換する前に、これら言語的条件は、まず数値的な選好（numerical preference）に変換されるべきである。その終わりまでに、非特許文献４に示される、選好マトリクスの言語的選好ｐijを置換するための以下に示す評価を用いることが必要である。
ａがｂよりさらに小さな重要度（ＭＬＩ）である → ｐij＝α、ｐji＝β
ａがｂより小さな重要度（ＬＩ）である → ｐij＝γ、ｐji＝δ
ａがｂと同じ重要度（ＥＩ）である → ｐij＝ε、ｐji＝ε
【００３３】
パラメータ値は意思決定によって割り当てられる必要があり、言語的条件の翻訳能力（interpretability）を損なわないために以下の条件がみたされる必要がある：
α ＜ γ ＜ ε ＝ 0.5 ＜ δ ＜ β
α ＋ β ＝ １ ＝ γ ＋ δ
【００３４】
非特許文献４で用いられている６つの目的｛Ｏ１、Ｏ２、…、Ｏ６｝を備えるＭＯＯ問題について考察する。６つの目的のうち、Ｏ１およびＯ２、ならびにＯ３およびＯ４が、同じ重要度（ＥＩ）であると仮定する。したがって、Ｃ１：＝｛Ｏ１、Ｏ２｝、Ｃ２：＝｛Ｏ３、Ｏ４｝、Ｃ３：＝｛Ｏ５｝、およびＣ４：＝｛Ｏ６｝の４つの目的クラスが存在する。さらに、以下の選好関係が存在する：
Ｃ１がＣ２よりさらに大きな重要度（ＭＭＩ）である；
Ｃ１がＣ３より大きな重要度（ＭＩ）である；
Ｃ４がＣ１より大きな重要度（ＭＩ）である；
Ｃ３がＣ２よりさらに大きな重要度（ＭＭＩ）である。
【００３５】
上述の選好から、以下の選好マトリクスＰを容易に得ることができる：
【００３６】
【数３】
2005515564.tif 000005
【００３７】
上記ファジィ選好マトリクスＰから、以下のような実数値を有する選好関係マトリクスＲが得られる：
【００３８】
【数４】
2005515564.tif 000006
【００３９】
この関係マトリクスＲに基づいて、各目的の重みが次式から得られる：
【００４０】
【数５】
2005515564.tif 000007
ただし、
【数６】
2005515564.tif 000008
である。この例では以下のような結果となる：
Ｗ１ ＝ Ｗ２ ＝ （２―α）／（８＋２α）
Ｗ３ ＝ Ｗ４ ＝ ３α／（８＋２α）
Ｗ５ ＝ （１―α＋２γ）／（８＋２α）
Ｗ６ ＝ （３―α―２γ）／（８＋２α）
【００４１】
αおよびγは0から0.5の間で変化するので、ファジィ選好から単一値を有する重みの組み合わせに変換するために、αおよびγの値を発見的に特定する必要がある。その後、この重みの組み合わせが従来の加重線形結合（weighted aggregation）に適用され、解に到達する。
【００４２】
【非特許文献１】Dasgupta et al., “Evolutionary Algorithms in Engineering Applications”, Springer-Verlag, 1997
【非特許文献２】Miettinnen et al. , “Evolutionary Algorithms in Engineering and Computer Science”, John Wiley and Sons, 1999
【非特許文献３】D.A. Van Veldheizen and G.B. Lamont, “Multi Objective Evolutionary Algorithms: Analyzing the State of the Art”, Evolutionary Computation, 8(2), pp. 125-147, 2000
【非特許文献４】Cvetkovic et al., “Use of Preferences for GA-based Multi-Objective Optimization”, Proceedings of 1999 Genetic and Evolutionary Computation Conference, pp. 1504-1510, 1999
【非特許文献５】Jin et al., “Evolutionary Weighted Aggregation: Why does it Work and How?”, Proceedings of Genetic and Evolutionary Computation Conference, pp. 1042-1049, 2001
【発明の開示】
【発明が解決しようとする課題】
【００４３】
ファジィ選好を単一の重み組み合わせに変換するために、上述のαおよびγの値を特定する必要がある。一方、これらのパラメータの特定方法に明確なルールはない一方、大量の情報がこの処理中に損失されてしまう。このような短所を考慮して、多目的最適化へのファジィ選好の利用を改善することが本発明の目標である。
【課題を解決するための手段】
【００４４】
この目標は、独立項で特徴付けられる手段によって達成される。従属項は本発明の基本概念をさらに発展する。
【００４５】
本発明の主要な側面によると、例えば、ファジィ選好は、各重みが単一値のかわりに区間（interval）で記述される重み組み合わせに変換される。
【００４６】
さらなる本発明の趣旨、利点、および特徴は、以下の発明の詳細な説明および添付した図面を参照することによって、当業者に明らかになろう。
【発明を実施するための最良の形態】
【００４７】
基本発明によれば、言語的ファジィ選好は、各重みが区間（interval）で記述される重み組み合わせに変換される。
【００４８】
図３Ａ、図３Ｂ、図４Ａ、および図４Ｂは、パラメータ値がどのように重みに影響を与えるかを示している。これらの図から、パラメータ（α、γ）が許容範囲内で変動するとき重みも大きく変動することがわかる。このように、ファジィ選好から得られる重みは、［０，１］上の区間（interval）である。大変興味深いことに、区間値の重み組み合わせは、ＲＷＡおよびＤＷＡを用いた多目的最適化にうまく組み込まれることが可能である（非特許文献５参照）。
【００４９】
重みの最大値および最小値がＷmaxおよびＷminであるとする。パラメータが変動するとき、以下に示すＲＷＡを拡張した数式で、最適化アルゴリズムの間に重みは変動する：
ｗ1i(ｔ) ＝ｗ1min ＋ （ｗ1max  − ｗ1min ）・ rdm(P)／P
ここで、ｔは世代のインデックスである。
【００５０】
同様に、ＤＷＡを拡張することにより、所望のパレート解を発見するために、以下の形式で重みが変動される：
ｗ1i(ｔ) ＝ｗ1min ＋ （ｗ1max  − ｗ1min ）・ ｜sin（２πｔ／Ｆ）｜
ここでｔは世代のインデックスである。
【００５１】
このように、進化的アルゴリズムは、ファジィ選好を反映したパレート解の組を提供することができる。しかしながら、パレートフロントが凹型の場合、ＤＷＡは個体の振る舞いを制御することができないことは前述の通りである。それゆえに、ＤＷＡを用いたファジィ選好のＭＯＯへの組み込みは凸型のパレートフロントにしか適用することができない。これに対し、ＲＷＡ法は凸型と凹型のフロント両方に適用することができる。
【００５２】
基礎的な発明を示すために、ＲＷＡを用いた２つの目的の最適化の例を以下に示す。このシミュレーションにおいて、2つの異なるファジィ選好が扱われる：
１．目的１は目的２より大きな重要度である；
２．目的１は目的２より小さな重要度である。
【００５３】
第1の選好において、以下の選好マトリクスＰが得られる：
【００５４】
【数７】
2005515564.tif 000009
【００５５】
ここで0.5＜δ＜１、０＜γ＜0.5である。したがって、ＲＷＡを用いた2つの目的の重みは以下のように表される：
ｗ1i(ｔ) ＝ 0.5 ＋ 0.5 ・ rdm(P)／P
ｗ2i(ｔ) ＝ 1.0 − ｗ1i(ｔ)
【００５６】
同様に、第2の選好において、以下に示す重みが獲得される：
ｗ1i(ｔ) ＝ 0 ＋ 0.5 ・ rdm(P)／P
ｗ2i(ｔ) ＝ 1.0 − ｗ1i(ｔ)
【００５７】
以上をまとめると、本発明は、人間の選好で規定されるパレート最適解を獲得する方法を提案する。ファジィ選好を区間に基づいた重みに変換することが主要な概念である。ＲＷＡおよびＤＷＡを利用して、凸型のパレートフロントを用いた２つのテスト関数における好適な解を発見するのに成功することが示された。非特許文献４と比較すると、本発明による方法は、異なる目的のファジィ選好の組を与えられたら、１つのみでなく多数の解を発見することができる。これはファジィロジックの目的と一致している。
【００５８】
多くの技術、工業、およびビジネスアプリケーションが進化的最適化を適用可能である。アプリケーションの例はたとえば、非特許文献１または非特許文献２を参照されたい。
【図面の簡単な説明】
【００５９】
【図１】進化的ストラテジのサイクルを示す図である。
【図２】ファジィ選好をＭＯＯに適用する手順を示す概略図である。
【図３Ａ】パラメータαの変化に伴う重みＷ１の変化を示す図である。
【図３Ｂ】パラメータαの変化に伴う重みＷ２の変化を示す図である。
【図４Ａ】パラメータαおよびγの変化に伴う重みＷ３の変化を示す図である。
【図４Ｂ】パラメータαおよびγの変化に伴う重みＷ４の変化を示す図である。
【図１】
2005515564.tif 000010
【図２】
2005515564.tif 000011
【図３Ａ】
2005515564.tif 000012
【図３Ｂ】
2005515564.tif 000013
【図４Ａ】
2005515564.tif 000014
【図４Ｂ】
2005515564.tif 000015
【国際調査報告】
2005515564.tif 000016
2005515564.tif 000017
2005515564.tif 000018