(57)【要約】【課題】本発明では、進化的最適化法を提案する。【解決手段】第１のステップでは、複数の個体の初期母集団が設定され、オリジナルの適合度関数が適用される。次に、親として高い評価品質値を持つ子母集団個体が選択される。第３のステップで、親が複製され、複数の子母集団個体が生成される。子母集団個体の品質は、適合度関数を使用して評価され、選択的にオリジナルのまたは近似的な適合度関数が使用される。最後に、この方法は、停止条件が満たされるまで選択ステップに戻る。  子母集団個体の品質を評価するステップでは、さらに、クラスタ内のすべてのλ個の子母集団個体をグループ化し、クラスタ毎に１つまたは複数の子母集団個体を選択し、その結果、ξ個の選択された子母集団個体が全部得られ、オリジナルの適合度関数を使用してξ個の選択された子母集団個体を評価し、近似的適合度関数を使用して残りλ−ξ個の子母集団個体を評価する。【選択図】図３
2005209211.tif 000002
【特許請求の範囲】
【請求項１】
個体の初期母集団を設定し、オリジナルの適合度関数を適用するステップと、
高い評価品質値を持つ子母集団個体を親として選択するステップと、
親を複製して複数の子母集団個体を生成するステップと、
適合度関数を使用して前記子母集団個体の品質を評価し、選択的にオリジナルのまたは近似的な適合度関数を使用するステップと、
停止条件が満たされるまで前記選択するステップに戻るステップと、を含み、
前記評価は、
クラスタ内のλ個のすべての子母集団個体をグループ化するステップと、
クラスタ毎に、１つまたは複数の子母集団個体を選択し、全部でξ個の子母集団個体を選択するステップと、
前記オリジナルの適合度関数を使用してξ個の選択された前記子母集団個体を評価するステップと、
近似的適合度関数を使用して、残りのλ−ξ個の選択された子母集団個体を評価するステップと、
を含む進化的最適化方法。
【請求項２】
前記近似的適合度関数は、複数のニューラル・ネットワークからなるニューラル・ネットワーク・アンサンブルである請求項１に記載の方法。
【請求項３】
前記オリジナルの適合度関数による評価のため選択された前記子母集団個体は、クラスタ中心に最も近い個体である請求項１から２のいずれかに記載の方法。
【請求項４】
Ｋ−Ｍｅａｎｓ法を使用して、すべての子母集団をクラスタにグループ化する、請求項１から３のいずれかに記載の方法。
【請求項５】
前記ニューラル・ネットワーク・アンサンブル内の各ニューラル・ネットワークの出力に重みを付け、組み合わせることで、前記ニューラル・ネットワーク・アンサンブルの最終出力を得る、請求項２から４のいずれかに記載の方法。
【請求項６】
局所探索を行う遺伝的アルゴリズム（ＧＡ）を使用して前記ニューラル・ネットワーク・アンサンブルを生成する、請求項２から５のいずれかに記載の方法。
【請求項７】
進化戦略を使用し、予想される予測誤差を最小にすることにより前記ニューラル・ネットワーク・アンサンブルの重みを最適化する、請求項２から６のいずれかに記載の方法。
【請求項８】
前記ニューラル・ネットワーク・アンサンブルにおけるニューラル・ネットワークの差異を引き出し、該差異が所定のしきい値よりも大きいとき、関連する個体に対応する適合値を、前記オリジナルの適合度関数を使用して評価されている、クラスタ中心に最も近い個体の値で置き換える、請求項２から７のいずれかに記載の方法。
【請求項９】
コンピューティング・デバイス上で実行されたときに請求項１から８のいずれかに記載の方法を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、進化的計算の分野に関するものであり、特に、進化的アルゴリズム（ＥＡ）において適合度評価の回数を減らすことに関するものである。
【背景技術】
【０００２】
複雑な現実世界の最適化問題を解くために進化的アルゴリズムを適用する際に多くの困難が生じうる。主要な問題のうちの１つは、進化的アルゴリズムは、通常、よい解を得るために適合度評価を何回も行う必要があるという点である。残念ながら、適合度評価は時間がかかることが多い。例えば空気力学的設計の最適化についていうと、三次元数値流体力学（ＣＦＤ）シミュレーションに基づく所定の設計を１回評価するのに、高性能コンピュータであっても、数時間はかかる。
【０００３】
この説明で使用されている背景技術の引用文献は、取りまとめて、説明の最後に表として記載してある。
【０００４】
本明細書で背景技術を引用している場合（角括弧内）、対応する文書は本明細書に引用するものと理解されたい。
【０００５】
進化的計算は多くの場合時間がかかるという状況を多少とも緩和するため、計算を効率よく行うモデルをセットアップし、適合度関数を近似することができる。このようなモデルは、近似モデル、メタ・モデル、またはサロゲートと呼ばれることが多い（この話題の概要については［８］を参照）。近似モデルでオリジナルの適合度関数を完全に置き換えることができれば理想的であるが、研究により、一般に、進化的アルゴリズムが正しく収束するようにするためには近似モデルとオリジナルの適合度関数を組み合わせる必要があることが示されている。この目的のために、［６］で進化制御とも呼ばれている、オリジナルの適合度関数を使用していくつかの個体を再評価する作業が重要である。
【０００６】
世代ベースまたは個体ベースの進化制御を実装することができる。世代ベースのアプローチ［１４、２、６、７］では、近似モデルを使用していくつかの世代を評価し、オリジナルの適合度関数を使用して残りを評価する。個体ベースの進化制御では、近似モデルを使用して各世代の個体の一部を評価し、オリジナルの適合度関数を使用して残りを評価する［６、３、１７、１］。一般的にいって、世代ベースのアプローチは、個体が同時に並行して評価される場合に好適であり、その場合、最適化プロセスの持続時間は必要な世代の数に大きく依存する。それと対照的に、個体ベースのアプローチは、評価回数が限られている場合、例えば、適合度評価のために実験を行う必要がある場合に好適である。
【０００７】
他方、個体ベースの進化制御は、再評価する必要のある個体を選択する際に柔軟性を発揮する。［６］では、個体をランダムに選択するのではなく近似モデルに従って最良の個体を選択することを推奨している。［３］では、推定関数値だけでなく推定誤差をも考慮している。基本的な考え方は、推定誤差の大きな個体は再評価の対象として選択される可能性が高いというものである。他の不確定性の尺度も、［１］において提案されている。
【０００８】
［９］では、遺伝的アルゴリズム（ＧＡ）の母集団を複数のクラスタにグループ化し、適合度関数を使用してそれぞれのクラスタの代表するただ１つの個体を評価する。同じクラスタ内の他の個体は、代表する個体までのユークリッド距離に応じて推定される。明らかに、この種の推定は非常に粗いものであり、適合度ランドスケープの局所的特徴は完全に無視される。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
従来技術を鑑みて、本発明の目的は、進化的アルゴリズムを補助する適合度評価用の計算効率のよいモデルを提案することである。この目的は、独立請求項の特徴を用いて達成される。有利な特徴については、従属請求項において定義される。
【課題を解決するための手段】
【００１０】
提案されている発明では、母集団を複数のクラスタにグループ化し、オリジナルの適合度関数を使用して、クラスタ中心に最も近い個体のみを評価する。本発明の他の態様では、距離ベースの推定法［９］とは対照的に、評価される個体（クラスタの中心）を使用してニューラル・ネットワーク・アンサンブルを作成し、さらにそれを使用して、残りの個体の適合度値を推定することができる。ニューラル・ネットワークの構造とパラメータは両方とも、例えば、ラマルク遺伝による進化的アルゴリズム（ＥＡ）を使用して最適化することができる。
【００１１】
適合度評価の回数を減らすために、本発明では、進化的アルゴリズムを補助する適合度評価用に作成することができる計算効率のよいモデルを提案する。
【００１２】
本発明では、メタ・モデルを使用して適合度評価の必要な回数を減らす方法を提案する。これは、メタ・モデルを利用した進化的計算における３つの態様を扱う。
【００１３】
１つ目は、オリジナルの時間のかかる適合度関数で評価すべき個体およびメタ・モデルを使用して評価すべき個体を決定する方法である。本発明では、Ｋ−Ｍｅａｎｓアルゴリズムを使用するクラスタリング法を使用する。
【００１４】
２つ目は、メタ・モデルの品質を改善する方法である。単一のニューラル・ネットワークの代わりにニューラル・ネットワーク・アンサンブルが使用されている。その一方で、ニューラル・ネットワークの構造およびパラメータは両方とも、ラマルク進化的アルゴリズムを使用してオンラインで最適化される。最後に、標準的な進化戦略（ＥＳ）を使用してアンサンブル・メンバの重みが最適化される。
【００１５】
３つ目は、メタ・モデルの大きな予測誤差を検出する方法である。本発明では、アンサンブル・メンバの出力の差異を利用する。
【００１６】
本発明の第１の態様では進化的最適化法が提案されている。第１のステップでは、複数の個体の初期母集団が設定され、オリジナルの適合度関数が適用される。次に、高い評価品質値を持つ子母集団個体が親として選択される。第３のステップで、親が複製され、複数の子母集団個体が生成される。子母集団個体の品質は、適合度関数を使用して評価され、選択的にオリジナルのまたは近似的な適合度関数が使用される。最後に、この方法は、停止条件が満たされるまで選択ステップに戻り続ける。子母集団個体の品質を評価するステップでは、さらに、クラスタ内のすべてのλ個の子母集団個体をグループ化し、クラスタ毎に１つまたは複数の子母集団個体を選択し、その結果、ξ個の選択された子母集団個体が全部得られ、オリジナルの適合度関数を使用してξ個の選択された子母集団個体を評価し、近似的適合度関数を使用して残りλ−ξ個の子母集団個体を評価する。
【００１７】
近似的適合度関数は、例えば、複数のニューラル・ネットワークを含むニューラル・ネットワーク・アンサンブルとすることもできる。
【００１８】
オリジナルの適合度関数による評価のために選択される子母集団個体は、例えば、クラスタ中心に最も近い個体とすることができる。
【００１９】
Ｋ−Ｍｅａｎｓ法は、すべての子母集団を複数のクラスタにグループ分けする場合に使用できる。
【００２０】
さらに、ネットワーク・アンサンブル内の各ニューラル・ネットワークの出力に重みを付け、組み合わせることで、ニューラル・ネットワーク・アンサンブルの最終出力を得ることができる。
【００２１】
局所的探索を行う遺伝的アルゴリズム（ＧＡ）も、ニューラル・ネットワーク・アンサンブルを生成するために使用できる。
【００２２】
進化戦略（ＥＳ）は、予想される予測誤差を最小にすることによりアンサンブルの重みを最適化するために使用することができる。
【００２３】
アンサンブルにおけるニューラル・ネットワークの差異を引き出し、その差異が所定のしきい値よりも大きい場合、当該個体の対応する適合値をクラスタ中心に最も近い個体の値で置き換えることができる。
【００２４】
前記差異を使用して、オリジナルの関数を使用して評価される各クラスタ内の個体の数を制御することができる。
【００２５】
オリジナルの適合度関数を使用して評価すべき個体の数は、差異が高ければ増やし、差異が低ければ減らすことができる。
【００２６】
本発明の他の態様によれば、コンピューティング・デバイス上で稼働しているときに上述のような方法を実装するコンピュータ・ソフトウェア・プログラム製品が提案されている。
【００２７】
本発明の他の態様では、タービン動翼、静翼、および後置静翼の度流体力学的または空気力学的設計および車両の空気力学的特性の最適化のために、本発明の進化的最適化法の使用が提案されている。
【００２８】
本発明の他の利点は、従属請求項だけでなく、図面に示されている本発明の２つの好ましい実施形態の説明からも理解される。
【発明を実施するための最良の形態】
【００２９】
近似的モデルが進化にかかわる場合、進化的アルゴリズムが適切に収束することを保証するためオリジナルの適合度関数を使用して再評価すべき個体を決定する必要がある。
【００３０】
本発明の第１の実施形態では、Ｋ−Ｍｅａｎｓ法を適用して、母集団の個体を複数のクラスタにグループ化する。クラスタ化毎に、コストの高いオリジナルの適合度関数を使用して、例えば、クラスタ中心に最も近い個体のみを評価する。他の個体の適合度については、ニューラル・ネットワーク・アンサンブルを使用して推定し、さらにこれを使用して、可能な重大な予測誤差を検出する。３つのテスト関数のシミュレーション結果から、提案されている発明は、近似モデルによる最良の個体のみが再評価される戦略よりも優れたパフォーマンスを示すことがわかる。
【００３１】
Ｋ−Ｍｅａｎｓアルゴリズムを使用した母集団クラスタリング
類似のパターン（データ項目）をグループ化する様々なクラスタリング手法が提案されている［４］。これらのクラスタリング手法はすべて、本発明とともに使用することができる。一般に、以下のように分割することができる。
【００３２】
−  階層型クラスタリング・アルゴリズム
−  分割型クラスタリング・アルゴリズム
階層型アルゴリズムでは、入れ子になったパターンのグループを表すツリーを構成するが、分割型クラスタリング・アルゴリズムでは、パターンの単一分割を生成する。
【００３３】
分割型クラスタリング法の中で、Ｋ−Ｍｅａｎｓは最も単純で、最も一般的に使用されているクラスタリング・アルゴリズムである。平方誤差基準を採用し、その計算複雑度は、ｎをパターンの数とすると、Ｏ（ｎ）である。
【００３４】
図１は、そのようなものとして知られている母集団クラスタリングのアルゴリズムを示す。標準的な停止基準は、平方誤差の減少が最小になったときである。
【００３５】
Ｋ−Ｍｅａｎｓクラスタリング・アルゴリズムの主要な問題は、初期分割が適切に選ばれないと局所的な最小値に収束する場合があるという点である。そのうえ、あらかじめクラスタの数を指定する必要があり、これは分割型クラスタリング・アルゴリズムの一般的な問題点である［４］。
【００３６】
与えられたクラスタの有効性を評価するために、シルエット法［１６］を使用することができる。シルエット手法では、与えられたクラスタ、Ｘｊ、ｊ＝１，．．．，ｋについてクラスタＸｊのｉ番目のメンバ（ｘｉｊ，ｉ＝１，．．．ｎｊ）を品質尺度（シルエット幅）に割り当てる。
【数１】
2005209211.tif 000003
【００３７】
ただし、ａｉは、ｘｉｊとＸｊ内の他のすべてのメンバの間の平均距離であり、ｂｉはａｉ，ｉ＝１，２，．．．，ｎｊの最小値を表し、ｎｊはクラスタＸｊ内のパターンの数であり、当然、各パターンがただ１つのクラスタに属していればｎ１＋．．．＋ｎｋはｎに等しく、ｎはクラスタ化すべきパターンの数である。
【００３８】
ｓｉｊは−１と１との間の値を持つことはわかるであろう。ｓｉｊが１に等しい場合、ｓｉｊは適切なクラスタ内にあることを意味する。ｓｉｊが０の場合、ｘｉｊはさらに最近隣接クラスタ内にグループ化できることを示し、ｘｉｊが−１の場合、ｘｉｊは間違ったクラスタ内にある可能性が非常に高いことを示唆する。したがって、大域的なシルエット幅は、すべてのパターンのシルエット幅の総和をとることにより求めることができる。
【数２】
2005209211.tif 000004
【００３９】
したがって、この値を使用して、クラスタの適切な個数を決定することができる。
【００４０】
進化的アルゴリズムを使用したニューラル・ネットワーク・アンサンブルの構成
母集団が複数のクラスタにグループ化された後、オリジナルの適合度関数を使用して、各クラスタ中心に最も近い個体のみを評価する。また多少クラスタの中心にある複数の個体を選択できることにも注意されたい。
【００４１】
［９］では、他のすべての個体の適合度値は、クラスタ中心までのユークリッド距離に基づいて推定される。明らかに、この簡略化された推定では、評価されたクラスタ中心から抽出可能な適合度ランドスケープの局所的特徴を無視している。
【００４２】
［６、７］では、最適化の際に生成されたデータを使用して、標準のニューラル・ネットワークが構築されている。ニューラル・ネットワーク・モデルは、オフラインで学習が行われ、さらに、新しいデータが利用可能になると更新される。１つ問題が生じる可能性があるが、それは、サンプル数が増えると、学習効率が低下する場合があるという点である。学習効率を改善するのに、ニューラル・ネットワークの重み付き学習［７］およびオフライン構造最適化が有望であることが示されている。
【００４３】
本発明では、以下の２つの態様において、近似品質をさらに改善できる。
【００４４】
−  第１に、ニューラル・ネットワークの構造最適化はオンラインで実行され、最近の２つの世代で生成されたデータのみが使用される（Ｓ２１）。このため、ランドスケープの局所的特徴を反映する近似モデルを用意することが可能である。
【００４５】
−  第２に、単一のニューラル・ネットワークの代わりにアンサンブルを使用することで、ニューラル・ネットワークの一般化特性を改善する（Ｓ２２）。
【００４６】
ニューラル・ネットワーク・アンサンブルを使用する利点は、まだ見えないデータに対するアンサンブルのメンバの挙動の多様性が基になっている。一般に、まだ見えていないデータに対する多様な挙動は、以下のアプローチにより得られる。
【００４７】
−  様々な初期ランダム重みを使用すること
−  ネットワーク・アーキテクチャを変更すること
−  異なる学習アルゴリズムを採用すること
−  与えられた学習データを操作することにより異なる学習データを供給すること
−  異なるソースからデータを生成すること
−  アンサンブル・メンバ間に多様性［１２］、非相関［１５］、または負の相関［１０、１１］を助長すること。
【００４８】
本発明では、遺伝的アルゴリズム（ＧＡ）を使用して、ニューラル・ネットワーク・アンサンブル（Ｓ２２）を生成することができ、これにより、２種類の多様性のソースが得られる。ニューラル・ネットワークのアーキテクチャおよび最終的な重みは両方とも異なる。ニューラル・ネットワークの目標は、局所的適合度ランドスケープを学習することなので、本発明の最適化の方法では、すべてのデータを使用する代わりに２つの最近の世代で生成されたデータのみを使用する。
【００４９】
母集団内のλ個の個体はξ個のクラスタにグループ化されると仮定すると、ξ個の新しいデータがそれぞれの世代で生成される。したがって、進化的なニューラル・ネットワークの世代に対する適合度関数は、以下のように表すことができる。
【数３】
2005209211.tif 000005
【００５０】
ただし、０．５≦α≦１は最新のデータを重視する係数、ｙｉｄ（ｔ）、ｉ＝１，．．．，ξは現在の世代内で生成されたデータであり、ｙｉｄ（ｔ−１）、ｉ＝１，．．．，ξは、最後の世代で生成されたデータであり、ｙｉはｉ番目のデータ・セットのネットワーク出力である。
【００５１】
Ｎ個のニューラル・ネットワークが与えられたとすると、アンサンブルの最終出力は、アンサンブルのメンバの重み付き出力を平均することにより求めることができる。
【数４】
2005209211.tif 000006
【００５２】
ただし、ｙ（ｋ）およびｗ（ｋ）は、アンサンブル内のｋ番目のネットワークの出力および重みである。この場合、アンサンブルの予想誤差は以下の式で与えられる。
【数５】
2005209211.tif 000007
【００５３】
ただし、Ｃｉｊは、アンサンブル内のネットワークｉとネットワークｊとの間の誤差相関行列である（Ｓ２３）。
【数６】
2005209211.tif 000008
【００５４】
ただし、Ｅ（．）は数学的期待値を表す。
【００５５】
以下のようなアンサンブルの予想される予測誤差を最小にする重みの最適な集合が存在することが示されている［１３］。
【数７】
2005209211.tif 000009
【００５６】
ただし、１≦ｉ，ｊ、ｋ≦Ｎである。
【００５７】
しかし、誤差相関行列の信頼できる推定は、アンサンブル内の異なるネットワークの予測誤差には強い相関性がある場合が多いため、わかりやすくはない。
【００５８】
この問題を解決するためにいくつか方法が提案されている［５、１８、１９］。遺伝的プログラミングは、［１９］では最適なアンサンブル・サイズ探索に適用されているが、［１８］では重みを最適化するため再帰的最小二乗法が採用されている。［１８］では、アンサンブル・メンバとして最終的母集団内のニューラル・ネットワークの最適な部分集合を探索する場合に遺伝的アルゴリズム（ＧＡ）も使用される。
【００５９】
カノニカルな進化戦略（ＥＳ）を使用して、最適な重みを見つけて（Ｓ２４）、式５の期待誤差を最小にすることができる。
【００６０】
ニューラル・ネットワーク・アンサンブルを構築するアルゴリズムおよび進化的最適化アルゴリズムがそれぞれ図２および図３にスケッチとして示されている。
【００６１】
実験設定
シミュレーションでは、３つのよく知られているテスト関数、Ａｃｋｌｅｙ関数、Ｒｏｓｅｎｂｒｏｃｋ関数、およびＳｐｈｅｒｅ関数について最適化ランを数回実行する。
【００６２】
テスト関数の次元は３０に設定されている。標準（５、３０）の進化戦略（ＥＳ）をすべてのシミュレーションで使用する。
【００６３】
近似的適合度モデルにより進化的最適化を実装するために、クラスタの個数およびアンサンブル内のニューラル・ネットワークの個数など、いくつかの重要なパラメータを決定しなければならない。
【００６４】
第１の課題は、クラスタの個数である。この数は、クラスタリング・アルゴリズムのパフォーマンス、近似モデルの品質、および最終的には進化的アルゴリズムの収束特性に関係している。
【００６５】
３０次元Ａｃｋｌｅｙ関数上の適合度近似に使用される単一のニューラル・ネットワークのみを使って予備的最適化ランを数回実行する。クラスタリング・アルゴリズムでは、進化的アルゴリズムは、オリジナルの適合度関数を使用して母集団の約三分の一が再評価された場合正しく収束することができることがわかっている。再評価された固体の個数が母集団の三分の一よりもかなり少ない場合、進化的アルゴリズムのパフォーマンスは予測できないものとなる、つまり、進化的アルゴリズムは誤った最小値に収束する場合がある。
【００６６】
その後、クラスタの個数が母集団の三分の一に設定されている場合、クラスタリング・パフォーマンスは再評価される。図４は、クラスタの数が１０に設定され、母集団サイズが３０次元Ａｃｋｌｅｙ関数で３０である場合の大域的シルエット幅を示す。このクラスタリング・パフォーマンスは許容可能であることは理解できるであろう。
【００６７】
次に、シミュレーションを実行して、アンサンブル・サイズを調査する。これまで、アンサンブル・サイズはほとんどのアプリケーションにおいて発見的手法により決定されてきた。［１９］において、最適なサイズは５から７までの間とわかっている。アンサンブル・サイズを大きくすると計算コストが増大するという事実を考慮し、２つのケースを比較すると、３０次元Ａｃｋｌｅｙ関数について最適化ランの最初の２０世代で集められた２００個のサンプルでは３と５である。
【００６８】
アンサンブルの出力と単一ネットワークの出力が図５にプロットされており、図５（ａ）ではアンサンブル・サイズは３、図５（ｂ）ではアンサンブル・サイズは５である。図の右下部分に置かれる点が多いほど、アンサンブルの効果が高いことに注意されたい。この図から、アンサンブル・サイズを３から５に変更しても、パフォーマンスの著しい改善はなかったことがわかる。したがって、アンサンブル・サイズは３に固定する。
【００６９】
アンサンブルを使用しても予測精度は著しく向上していないように見える。そのため、アンサンブルを採用する動機には問題がある。以下の段落では、アンサンブルが重要なのは予測を改善することができるというだけではないことを示す。
【００７０】
本発明により最適化にアンサンブルを導入することについて等しく重要な理由として、アンサンブル・メンバの異なる挙動、つまり、アンサンブル内のメンバの差異に基づいて予測精度を推定することが挙げられる。これを明らかにするために、図６（ａ）では、アンサンブル・メンバの予測の標準偏差とアンサンブルの推定誤差との関係を示している。これらのデータは、さらに、Ａｃｋｌｅｙ関数の進化的ランの最初の２０世代で集められる。さらに関数評価を実行して、予測誤差を求める。もちろん、これらはニューラル・ネットワーク学習でも最適化でも使用されない。標準偏差が小さければ必ず予測誤差が小さいとはいえないが、標準偏差が大きいと予測誤差は大きい場合がほとんどであることがわかる。大きな偏差と大きな予測誤差とのこのような緊密な相関関係を基に、モデル誤差を予測する試行を行う。標準偏差がしきい値（この例では１）よりも大きい場合、モデル予測はクラスタ中心に最も近い個体の適合度で置き換えられ、これは、非常に粗いが、実現可能な近似である。
【００７１】
最後に、母集団サイズが（３、１５）である標準的な進化戦略（ＥＳ）を使用して、アンサンブル・メンバの重みを最適化する。重みが最適化されている拡張アンサンブル法（ＧＥＭ）の予測および基本アンサンブル法（ＢＥＭ）の予測が図６（ｂ）に示されている。ＧＥＭを使用することで予測精度が向上していることがわかる。
【００７２】
最適化の結果
本発明の進化的最適化法は、３つの関数、Ａｃｋｌｅｙ関数、Ｒｏｓｅｎｂｒｏｃｋ関数、およびＳｐｈｅｒｅ関数の最適化に適用する。適合度評価の最大回数は、すべてのシミュレーションにおいて２０００回に設定されている。
【００７３】
図７、８、および９は、３つのテスト関数に関する１０回のランの箱ひげ図である。わかりやすくするため、図に示されているデータ点は、オリジナル・データから均等に抽出された２０個だけである。これらの図から、平均すると、提案されたアルゴリズムを使用した最適化の結果は、すべてのテスト関数に対するふつうの進化戦略と比べるとかなりよいことが明らかにわかる。その一方で、これらは、母集団のクラスタリングは実装されていない［６］で報告されている結果と比べてもかなりよい。上述のように、クラスタリングが使用されていない場合、クラスタリング・アルゴリズムは、オリジナルの適合度関数を使用して母集団の三分の一のみが再評価された場合、正しく収束しない。しかしながら、Ａｃｋｌｅｙ関数の場合、提案された方法を使用した１０回のランのうちの１つの結果は、平均パフォーマンスよりもかなり劣り、普通のＥＳを使用した場合の平均的結果と比べてもわずかに劣る（図７（ａ）参照）。
【００７４】
図１０、１１、および１２では、ニューラル・ネットワーク・アンサンブルを使用する利点を示すために３つのテスト関数に対し単一のニューラル・ネットワーク（大きな予測誤差の改善策が含まれていない）のみを使用した結果の箱ひげ図を示している。同様に、図をわかりやすくするため２０個のデータ点のみが表示されている。図７、８、および９に示されている結果と比較すると、これらはかなり悪い。Ｒｏｓｅｎｂｒｏｃｋ関数では、いくつかのランは発散すらしてしまうが、これは主に、モデル予測のパフォーマンスが悪いせいである。
【００７５】
進化的計算で適合度評価を低減する新しい方法を提示する。それぞれの世代において、母集団はいくつかのグループにクラスタ化され、各クラスタ中心に最も近い個体のみが評価される。その後、評価された個体からのデータを使用してニューラル・ネットワーク・アンサンブルを構築する。予測品質をさらに高めるために、標準ＥＳを使用してアンサンブルの重みを最適化する。
【００７６】
本発明では、さらに、アンサンブル・メンバの出力の標準偏差を利用してアンサンブルに含まれる情報を活用する。アンサンブル・メンバが著しく不一致の場合、予測誤差が大きい確率が非常に高く、アンサンブル予測は個体のクラスタ中心の適合度値で置き換えられる。テスト関数に関するシミュレーション結果から、提案されたアルゴリズムは非常に有望であることが示唆される。
【００７７】
現在、制御すべき個体の数は固定されている。［７］で提案されているように、制御頻度の適応を行うことで、パフォーマンスをさらに改善することが可能である。１つの可能性として、大域的シルエット幅を使用してクラスタリング・アルゴリズムのパフォーマンスを最適化するため個体の数を決定することが挙げられる。
【００７８】
本発明の態様は以下のとおりである。
【００７９】
−  個体ベースの評価制御に関して、再評価のため個体を選択するのにＫ−Ｍｅｎａｓ法が使用される。
【００８０】
予測品質を改善するために、−単一モデルではなく、アンサンブルが使用される。そのうえ、ＥＳは、推定予測誤差に基づいてオンラインでアンサンブルの重みを最適化するために使用される。
【００８１】
−  本発明の主要な貢献の１つは、アンサンブル・メンバの差異を利用して大きな予測誤差を検出することである。このような誤差が検出された後、メタ・モデルの予測は破棄され、当該個体の適合度はクラスタ中心に最も近い個体の適合度で置き換えられる。
【００８２】
以下の表は、この説明で使用されている略語をまとめたものである。
【表１】
2005209211.tif 000010
【００８３】
以下の文献は、この説明で引用されている背景技術をまとめたものである。
【００８４】
［１］Ｊ．Ｂｒａｎｋｅ  ａｎｄ  Ｃ．Ｓｃｈｍｉｄｔ．Ｆａｓｔ  ｃｏｎｖｅｒｇｅｎｃｅ  ｂｙ  ｍｅａｎｓ  ｏｆ  ｆｉｔｎｅｓｓ  ｅｓｔｉｍａｔｉｏｎ。Ｓｏｆｔ  Ｃｏｍｐｕｔｉｎｇ、２００３年。
【００８５】
［２］Ｍ．Ａ．Ｅｌ−Ｂｅｌｔａｇｙ，Ｐ．Ｂ．Ｎａｉｒ，ａｎｄ  Ａ．Ｊ．Ｋｅａｎｅ．Ｍｅｔａｍｏｄｅｌｉｎｇ  ｔｅｃｈｎｉｑｕｅｓ  ｆｏｒ  ｅｖｏｌｕｔｉｏｎａｒｙ  ｏｐｔｉｍｉｚａｔｉｏｎ  ｏｆ  ｃｏｍｐｕｔａｔｉｏｎａｌｌｙ  ｅｘｐｅｎｓｉｖｅ  ｐｒｏｂｌｅｍｓ：ｐｒｏｍｉｓｅｓ  ａｎｄ  ｌｉｍｉｔａｔｉｏｎｓ。Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｇｅｎｅｔｉｃ  ａｎｄ  Ｅｖｏｌｕｔｉｏｎａｒｙ  Ｃｏｎｆｅｒｅｎｃｅ、１９６ページ〜２０３ページ、Ｏｒｌａｎｄｏ、１９９９年。Ｍｏｒｇａｎ  Ｋａｕｆｍａｎｎ。
【００８６】
［３］Ｍ．Ｅｍｍｅｒｉｃｈ，Ａ．Ｇｉｏｔｉｓ，Ｍ．Ｏｚｄｅｎｉｒ，Ｔ．Ｂａｃｋ，ａｎｄ  Ｋ．Ｇｉａｎｎａｋｏｇｌｏｕ．Ｍｅｔａｍｏｄｅｌ  ａｓｓｉｓｔｅｄ  ｅｖｏｌｕｔｉｏｎ  ｓｔｒａｔｅｇｉｅｓ。Ｉｎ  Ｐａｒａｌｌｅｌ  Ｐｒｏｂｌｅｍ  Ｓｏｌｖｉｎｇ  ｆｒｏｍ  Ｎａｔｕｒｅ。ｎｕｍｂｅｒ  ２４３９  ｉｎ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ。３７１ページ〜３８０ページ。Ｓｐｒｉｎｇｅｒ。２００２年。
【００８７】
［４］Ａ．Ｋ．Ｊａｉｎ，Ｍ．Ｎ．Ｍｕｒｔｙ，ａｎｄ  Ｐ．Ｊ．Ｆｌｙｎｎ．Ｄａｔａ  ｃｌｕｓｔｅｒｉｎｇ：Ａ  ｒｅｖｉｅｗ。ＡＣＭ  Ｃｏｍｐｕｔｉｎｇ  Ｓｕｒｖｅｙｓ、３１（３）：２６４ページ〜３２３ページ、１９９９年９月。
【００８８】
［５］Ｄ．Ｊｉｍｅｎｅｚ．Ｄｙｎａｍｉｃａｌｌｙ  ｗｅｉｇｈｔｅｄ  ｅｎｓｅｍｂｌｅ  ｎｅｕｒａｌ  ｎｅｔｗｏｒｋｓ  ｆｏｒ  ｃｌａｓｓｉｆｉｃａｔｉｏｎ。Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｉｎｔ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｎｅｕｒａｌ  Ｎｅｔｗｏｒｋｓ、７５３ページ〜７５６ページ、Ａｎｃｈｏｒａｇｅ、１９９８年。ＩＥＥＥ  Ｐｒｅｓｓ。
【００８９】
［６］Ｙ．Ｊｉｎ，Ｍ．Ｏｌｈｏｆｅｒ，ａｎｄ  Ｂ．Ｓｅｎｄｈｏｆｆ．Ｏｎ  ｅｖｏｌｕｔｉｏｎａｒｙ  ｏｐｔｉｍｉｚａｔｉｏｎ  ｗｉｔｈ  ａｐｐｒｏｘｉｍａｔｅ  ｆｉｔｎｅｓｓ  ｆｕｎｃｔｉｏｎｓ。Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｇｅｎｅｔｉｃ  ａｎｄ  Ｅｖｏｌｕｔｉｏｎａｒｙ  Ｃｏｍｐｕｔａｔｉｏｎ  Ｃｏｎｆｅｒｅｎｃｅ、７８６ページ〜７９２ページ。Ｍｏｒｇａｎ  Ｋａｕｆｍａｎｎ、２０００年。
【００９０】
［７］Ｙ．Ｊｉｎ，Ｍ．Ｏｌｈｏｆｅｒ，ａｎｄ  Ｂ．Ｓｅｎｄｈｏｆｆ．Ａ  ｆｒａｍｅｗｏｒｋ  ｆｏｒ  ｅｖｏｌｕｔｉｏｎａｒｙ  ｏｐｔｉｍｉｚａｔｉｏｎ  ｗｉｔｈ  ａｐｐｒｏｘｉｍａｔｅ  ｆｉｔｎｅｓｓ  ｆｕｎｃｔｉｏｎｓ。ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｅｖｏｌｕｔｉｏｎａｒｙ  Ｃｏｍｐｕｔａｔｉｏｎ、６（５）：４８１ページ〜４９４ページ、２００２年。
【００９１】
［８］Ｙ．Ｊｉｎ  ａｎｄ  Ｂ．Ｓｅｎｄｈｏｆｆ．Ｆｉｔｎｅｓｓ  ａｐｐｒｏｘｉｍａｔｉｏｎ  ｉｎ  ｅｖｏｌｕｔｉｏｎａｒｙ  ｃｏｍｐｕｔａｔｉｏｎ−Ａ  ｓｕｒｖｅｙ。Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｇｅｎｅｔｉｃ  ａｎｄ  Ｅｖｏｌｕｔｉｏｎａｒｙ  Ｃｏｍｐｕｔａｔｉｏｎ  Ｃｏｎｆｅｒｅｎｃｅ、１１０５ページ〜１１１２ページ、２００２年。
【００９２】
［９］Ｈ．−Ｓ．Ｋｉｍ  ａｎｄ  Ｓ．−Ｂ．Ｃｈｏ．Ａｎ  ｅｆｆｉｃｉｅｎｔ  ｇｅｎｅｔｉｃ  ａｌｇｏｒｉｔｈｍｓ  ｗｉｔｈ  ｌｅｓｓ  ｆｉｔｎｅｓｓ  ｅｖａｌｕａｔｉｏｎ  ｂｙ  ｃｌｕｓｔｅｒｉｎｇ。Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＥＥＥ  Ｃｏｎｇｒｅｓｓ  ｏｎ  Ｅｖｏｌｕｔｉｏｎａｒｙ  Ｃｏｍｐｕｔａｔｉｏｎ、８８７ページ〜８９４ページ。ＩＥＥＥ、２００１年。
【００９３】
［１０］Ｙ．Ｌｉｕ  ａｎｄ  Ｘ．Ｙａｏ．Ｎｅｇａｔｉｖｅｌｙ  ｃｏｒｒｅｌａｔｅｄ  ｎｅｕｒａｌ  ｎｅｔｗｏｒｋｓ  ｃａｎ  ｐｒｏｄｕｃｅ  ｂｅｓｔ  ｅｎｓｅｍｂｌｅ。Ａｕｓｔｒａｌｉａｎ  Ｊｏｕｒｎａｌ  ｏｆ  Ｉｎｔｅｌｌｉｇｅｎｔ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｙｓｔｅｍ、４（３−４）：１７６ページ〜１８５ページ、１９９７年。
【００９４】
［１１］Ｙ．Ｌｉｕ，Ｘ．Ｙａｏ，ａｎｄ  Ｔ．Ｈｉｇｕｃｈｉ．Ｅｖｏｌｕｔｉｏｎａｒｙ  ｅｎｓｅｍｂｌｅｓ  ｗｉｔｈ  ｎｅｇａｔｉｖｅ  ｃｏｒｒｅｌａｔｉｏｎ  ｌｅａｒｎｉｎｇ。ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｅｖｏｌｕｔｉｏｎａｒｙ  Ｃｏｍｐｕｔａｔｉｏｎ、４（４）：３８０ページ〜３８７ページ、２０００年
［１２］Ｄ．Ｗ．Ｏｐｉｔｚ  ａｎｄ  Ｊ．Ｗ．Ｓｈａｖｌｉｋ．Ｇｅｎｅｒａｔｉｎｇ  ａｃｃｕｒａｔｅ  ａｎｄ  ｄｉｖｅｒｓｅ  ｍｅｍｂｅｒｓ  ｏｆ  ａ  ｎｅｕｒａｌ  ｎｅｔｗｏｒｋ  ｅｎｓｅｍｂｌｅ。Ｉｎ  Ａｄｖａｎｃｅｓ  ｉｎ  Ｎｅｕｒａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｙｓｔｅｍｓ、第８巻、５３５ページ〜５４１ページ、Ｃａｍｂｒｉｄｇｅ、ＭＡ、１９９６年。ＭＩＴ  Ｐｒｅｓｓ。
【００９５】
［１３］Ｍ．Ｐ．Ｐｅｒｒｏｎｅ  ａｎｄ  Ｌ．Ｎ．Ｃｏｏｐｅｒ．Ｗｈｅｎ  ｎｅｔｗｏｒｋｓ  ｄｉｓａｇｒｅｅ：Ｅｎｓｅｍｂｌｅ  ｍｅｔｈｏｄｓ  ｆｏｒ  ｈｙｂｒｉｄ  ｎｅｕｒａｌ  ｎｅｔｗｏｒｋｓ。Ｉｎ  Ｒ．Ｊ．Ｍａｍｍｏｎｅ，ｅｄｉｔｏｒ，Ａｒｔｉｆｉｃｉａｌ  Ｎｅｕｒａｌ  Ｎｅｔｗｏｒｋｓ  ｆｏｒ  Ｓｐｅｅｃｈ  ａｎｄ  Ｖｉｓｉｏｎ、１２６ページ〜１４２ページ。Ｃｈａｐｍａｎ  ＆  Ｈａｌｌ、Ｌｏｎｄｏｎ、１９９３年。
【００９６】
［１４］Ａ．Ｒａｔｌｅ．Ａｃｃｅｌｅｒａｔｉｎｇ  ｔｈｅ  ｃｏｎｖｅｒｇｅｎｃｅ  ｏｆ  ｅｖｏｌｕｔｉｏｎａｒｙ  ａｌｇｏｒｉｔｈｍｓ  ｂｙ  ｆｉｔｎｅｓｓ  ｌａｎｄｓｃａｐｅ  ａｐｐｒｏｘｉｍａｔｉｏｎ。Ｉｎ  Ａ．Ｅｉｂｅｎ，Ｔｈ．Ｂａｃｋ，Ｍ．Ｓｃｈｏｅｎａｕｅｒ，ａｎｄ  Ｈ．−Ｐ．Ｓｃｈｗｅｆｅｌ，ｅｄｉｔｏｒｓ、Ｐａｒａｌｌｅｌ  Ｐｒｏｂｌｅｍ  Ｓｏｌｖｉｎｇ  ｆｒｏｍ  Ｎａｔｕｒｅ、第Ｖ巻、８７ページ〜９６ページ、１９９８年。
【００９７】
［１５］Ｂ．Ｅ．Ｒｏｓｅｎ．Ｅｎｓｅｍｂｌｅ  ｌｅａｒｎｉｎｇ  ｕｓｉｎｇ  ｄｅｃｏｒｒｅｌａｔｅｄ  ｎｅｕｒａｌ  ｎｅｔｗｏｒｋｓ。Ｃｏｎｎｅｃｔｉｏｎ  Ｓｃｉｅｎｃｅ、８（３−４）：３７３−３８４、１９９６。
【００９８】
［１６］Ｐ．Ｊ．Ｒｏｕｓｓｅｅｕｗ．Ｓｉｌｈｏｕｅｔｔｅｓ：Ａ  ｇｒａｐｈｉｃａｌ  ａｉｄ  ｔｏ  ｔｈｅ  ｉｎｔｅｒｐｒｅｔａｔｉｏｎ  ａｎｄ  ｖａｌｉｄａｔｉｏｎ  ｏｆ  ｃｌｕｓｔｅｒ  ａｎａｌｙｓｉｓ。Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  ａｎｄ  Ａｐｐｌｉｅｄ  Ｍａｔｈｅｍａｔｉｃｓ、２０：５３ページ〜６５ページ、１９８７年。
【００９９】
［１７］Ｈ．Ｕｌｍｅｒ，Ｆ．Ｓｔｒｅｉｃｈｅｒ，ａｎｄ  Ａ．Ｚｅｌｌ．Ｍｏｄｅｌ−ａｓｓｉｓｔｅｄ  ｓｔｅａｄｙ−ｓｔａｔｅ  ｅｖｏｌｕｔｉｏｎ  ｓｔｒａｔｅｇｉｅｓ。Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｇｅｎｅｔｉｃ  ａｎｄ  Ｅｖｏｌｕｔｉｏｎａｒｙ  Ｃｏｍｐｕｔａｔｉｏｎ  Ｃｏｎｆｅｒｅｎｃｅ、ＬＮＣＳ  ２７２３、６１０ページ〜６２１ページ、２００３年。
【０１００】
［１８］Ｘ．Ｙａｏ  ａｎｄ  Ｙ．Ｌｉｕ．Ｍａｋｉｎｇ  ｕｓｅ  ｏｆ  ｐｏｐｕｌａｔｉｏｎ  ｉｎｆｏｒｍａｔｉｏｎ  ｉｎ  ｅｖｏｌｕｔｉｏｎａｒｙ  ａｒｔｉｆｉｃｉａｌ  ｎｅｕｒａｌ  ｎｅｔｗｏｒｋｓ。ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｓｙｓｔｅｍｓ，Ｍａｎ，ａｎｄ  Ｃｙｂｅｒｎｅｔｉｃｓ−Ｐａｒｔ  Ｂ：Ｃｙｂｅｒｎｅｔｉｃｓ、２８（３）：４１７ページ〜４２５ページ、１９９８年。
【０１０１】
［１９］Ｂ．−Ｔ．Ｚｈａｎｇ  ａｎｄ  Ｊ．Ｇ．Ｊｏｕｎｇ．Ｂｕｉｌｄｉｎｇ  ｏｐｔｉｍａｌ  ｃｏｍｍｉｔｔｅｅ  ｏｆ  ｇｅｎｅｔｉｃ  ｐｒｏｇｒａｍｓ。Ｉｎ  Ｐａｒａｌｌｅｌ  Ｐｒｏｂｌｅｍ  Ｓｏｌｖｉｎｇ  ｆｒｏｍ  Ｎａｔｕｒｅ、第ＶＩ巻、２３１ページ〜２４０ページ。Ｓｐｒｉｎｇｅｒ、２０００年。
【図面の簡単な説明】
【０１０２】
【図１】母集団クラスタリング用の知られているＫ−Ｍｅａｎｓアルゴリズムを示す図。
【図２】本発明によるニューラル・ネットワーク・アンサンブルを構成するためのアルゴリズムを示す図。
【図３】本発明により提案される進化的最適化アルゴリズムを示す図。
【図４】クラスタの数が１０に設定され、母集団サイズが３０次元Ａｃｋｌｅｙ関数で３０である場合の大域的シルエット幅を示す図。
【図５】アンサンブル・サイズが３（ａ）とアンサンブル・サイズが５（ｂ）のアンサンブル出力を示す図。
【図６】予測誤差と標準偏差の比較（ａ）およびＢＥＭの予測誤差とＧＥＭの予測誤差の比較（ｂ）を示す図。
【図７】提案されているアルゴリズム（ａ）および普通のＥＳ（ｂ）に対する、（ａ）と（ｂ）と縮尺が同じでない、３０次元Ａｃｋｌｅｙ関数の最適化結果の箱ひげ図。
【図８】提案されているアルゴリズム（ａ）および普通のＥＳ（ｂ）に対する、３０次元Ｒｏｓｅｎｂｒｏｃｋ関数の最適化結果の箱ひげ図。
【図９】提案されているアルゴリズム（ａ）および普通のＥＳ（ｂ）に対する、（ａ）と（ｂ）と縮尺が同じでない、３０次元Ｓｐｈｅｒｅ関数の最適化結果の箱ひげ図。
【図１０】単一ネットワークを持つ３０次元Ａｃｋｌｅｙ関数に対する結果を示す図。
【図１１】単一ネットワークを持つ３０次元Ｒｏｓｅｎｂｒｏｃｋ関数に対する結果を示す図。
【図１２】単一ネットワークを持つ３０次元ＳＰＨ関数に対する結果を示す図。
【図１】
2005209211.tif 000011
【図２】
2005209211.tif 000012
【図３】
2005209211.tif 000013
【図４】
2005209211.tif 000014
【図５】
2005209211.tif 000015
【図６】
2005209211.tif 000016
【図７】
2005209211.tif 000017
【図８】
2005209211.tif 000018
【図９】
2005209211.tif 000019
【図１０】
2005209211.tif 000020
【図１１】
2005209211.tif 000021
【図１２】
2005209211.tif 000022