(57)【要約】【課題】変数の最適化を効率的に行うことができる最適化装置、最適化方法および最適化プログラムを提供する。【解決手段】個体選択部５は個体集合記憶部４に記憶された複数の個体から所定数の親個体を選択する。個体生成部２は個体選択部５により選択された所定数の親個体から超球面上の交叉により複数の子個体を生成する。最適化対象８は最適化装置１から与えられた個体の決定変数ベクトルに基づいて状態量を出力する。適応度算出部６は最適化対象８から出力される状態量に基づいて適応度を算出し、算出された適応度を個体集合記憶部４に与える。個体集合記憶部４は適応度算出部６により算出された適応度の組および決定変数ベクトルを個体として記憶する。世代交代部３は個体集合記憶部４に記憶される複数の個体の適応度に基づいて個体集合記憶部４に記憶される個体集合を更新する。【選択図】図１
2006294002.tif 000002
【特許請求の範囲】
【請求項１】
最適化すべきＮ個の変数のうちｍ個の変数の２乗の総和が１となる拘束を有する場合に最適化対象にＮ個の変数を有する解候補を与え、Ｎ個の変数についての目的関数に対応する状態量を前記最適化対象から受ける最適化装置であって、
Ｎ個の変数の組により定義されるＮ次元変数空間上の点を表す変数ベクトルの集合を解候補の集合として記憶する解候補記憶部と、
前記解候補記憶部に記憶された解候補の集合から所定数の解候補を選択する解候補選択部と、
前記解候補選択部により選択された所定数の解候補に基づいて（ｍ−１）次元単位球面を含むＮ次元変数空間上に新たな解候補の集合を生成し、生成された解候補の集合を前記最適化対象および前記解候補記憶部に与える解候補生成部と、
前記最適化対象から出力される状態量の評価値を算出する評価値演算部と、
前記評価値演算部により算出される評価値に基づいて前記解候補記憶部に記憶される解候補の集合を更新する解候補集合更新部とを備え、
Ｎは２以上の自然数であり、前記ｍは前記Ｎ以下の自然数であることを特徴とする最適化装置。
【請求項２】
最適化対象に最適化すべきＮ個の変数を有する解候補を与え、ｍ個の変数に関して周期性を有する目的関数を含む前記Ｎ個の変数についての目的関数に対応する状態量を前記最適化対象から受ける最適化装置であって、
Ｎ個の変数の組により定義されるＮ次元変数空間上の点を表す変数ベクトルの集合を解候補の集合として記憶する解候補記憶部と、
前記解候補記憶部に記憶された解候補の集合から所定数の解候補を選択する解候補選択部と、
前記解候補選択部により選択された所定数の解候補に基づいてｍ個の変数をｍ個の１次元単位球面上の点に対応付けることによりＮ次元変数空間を［（Ｎ−ｍ）＋２ｍ］次元変数空間に拡張し、拡張された［（Ｎ−ｍ）＋２ｍ］次元変数空間上に解候補の集合を生成し、生成された解候補の集合をＮ次元変数空間上の点に再び対応付けることにより新たな解候補の集合を生成し、生成された解候補の集合を前記最適化対象および前記解候補記憶部に与える解候補生成部と、
前記最適化対象から出力される状態量の評価値を算出する評価値演算部と、
前記評価値演算部により算出される評価値に基づいて前記解候補記憶部に記憶される解候補の集合を更新する解候補集合更新部とを備え、
Ｎは１以上の自然数であり、前記ｍは前記Ｎ以下の自然数であることを特徴とする最適化装置。
【請求項３】
前記ｍ個の変数の各々をθとし、２次元平面上の点の第１および第２の座標をそれぞれｘおよびｙとした場合に、
前記解候補生成部は、前記解候補選択部により選択された所定数の解候補の前記変数θを（ｘ，ｙ）＝（ｃｏｓθ，ｓｉｎθ）の演算により第１および第２の座標（ｘ，ｙ）に置き換え、生成された各解候補の第１および第２の座標（ｘ，ｙ）を下記式により変数θCに変換することを特徴とする請求項２記載の最適化装置。
【数１】
2006294002.tif 000008
【請求項４】
前記解候補選択部は、前記周期関数の定義域を前記周期関数の周期に設定し、設定された定義域が２πになるように前記周期関数を変数軸の方向に拡大または縮小し、前記定義域の中心が前記変数軸の座標０に位置するように前記周期関数をシフトさせることを特徴とする請求項２または３記載の最適化装置。
【請求項５】
前記最適化対象は機器の性能を評価するための評価システムを含み、前記変数ベクトルは前記評価システムのための制御用パラメータを含み、前記状態量は前記評価システムの評価により得られる前記機器の性能であることを特徴とする請求項１〜４のいずれかに記載の最適化装置。
【請求項６】
前記評価システムは、前記制御用パラメータに基づいて前記機器を制御するとともに前記機器の動作により発生される前記機器の性能を状態量として出力する機器評価装置であることを特徴とする請求項５記載の最適化装置。
【請求項７】
前記評価システムは、前記制御用パラメータに基づいて前記機器の動作をシミュレーションすることにより前記機器の性能を評価し、評価された性能を状態量として出力する機器シミュレータであることを特徴とする請求項５記載の最適化装置。
【請求項８】
前記機器は内燃機関であり、前記制御用パラメータは前記内燃機関のクランク回転角度に基づくパラメータであり、前記状態量は前記パラメータについて周期的に変化する前記内燃機関の性能であることを特徴とする請求項６または７記載の最適化装置。
【請求項９】
前記内燃機関は燃料噴射装置を有し、前記クランク回転角度に基づくパラメータは前記燃料噴射装置の燃料噴射時期を含むことを特徴とする請求項８記載の最適化装置。
【請求項１０】
前記内燃機関は燃料噴射装置を有し、前記クランク回転角度に基づくパラメータは、複数の区間を含む一定期間内における前記燃料噴射装置による燃料噴射パターンであり、前記燃料噴射パターンは、前記燃料噴射装置による燃料噴射量の合計が一定となるような各区間の燃料噴射量からなるベクトルであり、前記状態量は前記パラメータについて周期的に変化する前記内燃機関の性能であることを特徴とする請求項８記載の最適化装置。
【請求項１１】
前記状態量は、排出ガス中の所定の成分の濃度、燃料消費量、出力トルク、スロットル弁の開度およびクランク回転速度のうち少なくとも１つを含むことを特徴とする請求項９または１０記載の最適化装置。
【請求項１２】
前記機器はロボットリンク機構であり、前記変数ベクトルは前記リンク機構の関節がなす角度を示すパラメータであり、前記状態量は前記パラメータについて周期的に変化する前記ロボットリンク機構の性能であることを特徴とする請求項６または７記載の最適化装置。
【請求項１３】
前記最適化対象は、道路に配置された複数の交通信号を含む交通システムの広域制御をシミュレーションする交通シミュレータであり、前記変数ベクトルは少なくとも１つ交通信号の点灯タイミングであり、前記状態量は前記道路を通過する車に関する情報を含むことを特徴とする請求項５記載の最適化装置。
【請求項１４】
前記最適化装置は、蛋白質の構造をシミュレーションする蛋白質シミュレータであり、前記変数ベクトルは蛋白質の共有結合間の二面角を表す方向ベクトルであり、前記状態量はエネルギーに関する情報であることを特徴とする請求項５記載の最適化装置。
【請求項１５】
前記最適化対象は、対象画像と参照画像とのマッチング処理を行う画像処理装置であり、前記変数ベクトルは前記参照画像に対する前記対象画像の方向ベクトルであり、前記状態量は前記対象画像と前記参照画像との誤差を示す情報であることを特徴とする請求項５記載の最適化装置。
【請求項１６】
最適化対象に最適化すべきＮ個の変数を有する変数を有する解候補を与え、ｍ個の変数の２乗の総和が１となる拘束を有する目的関数を含む前記Ｎ個の変数についての目的関数に対応する状態量を前記最適化対象から受ける最適化方法であって、
Ｎ個の変数の組により定義されるＮ次元変数空間上の点を表す変数ベクトルの集合を解候補の集合として記憶部に記憶するステップと、
前記記憶された解候補の集合から所定数の解候補を選択するステップと、
前記選択された所定数の解候補に基づいて（ｍ−１）次元単位球面を含むＮ次元変数空間上に新たな解候補の集合を生成し、生成された解候補の集合を前記最適化対象および前記記憶部に与えるステップと、
前記最適化対象から出力される状態量の評価値を算出するステップと、
前記算出される評価値に基づいて前記記憶部に記憶される解候補の集合を更新するステップとを備え、
Ｎは２以上の自然数であり、前記ｍは前記Ｎ以下の自然数であることを特徴とする最適化方法。
【請求項１７】
最適化対象に最適化すべきＮ個の変数を有する変数を有する解候補を与え、ｍ個の変数に関して周期性を有する目的関数を含む前記Ｎ個の変数についての目的関数に対応する状態量を前記最適化対象から受ける最適化方法であって、
Ｎ個の変数の組により定義されるＮ次元変数空間上の点を表す変数ベクトルの集合を解候補の集合として記憶部に記憶するステップと、
前記記憶された解候補の集合から所定数の解候補を選択するステップと、
前記選択された所定数の解候補に基づいてｍ個の変数をｍ個の１次元単位球面上の点に対応付けることによりＮ次元変数空間を［（Ｎ−ｍ）＋２ｍ］次元変数空間に拡張し、拡張された［（Ｎ−ｍ）＋２ｍ］次元変数空間上に解候補の集合を生成し、生成された解候補の集合をＮ次元変数空間上の点に再び対応付けることにより新たな解候補の集合を生成し、生成された解候補の集合を前記最適化対象および前記記憶部に与えるステップと、
前記最適化対象から出力される状態量の評価値を算出するステップと、
前記算出される評価値に基づいて前記記憶部に記憶される解候補の集合を更新するステップとを備え、
Ｎは１以上の自然数であり、前記ｍは前記Ｎ以下の自然数であることを特徴とする最適化方法。
【請求項１８】
最適化対象に最適化すべきＮ個の変数を有する変数を有する解候補を与え、ｍ個の変数の２乗の総和が１となる拘束を有する目的関数を含む前記Ｎ個の変数についての目的関数に対応する状態量を前記最適化対象から受けるコンピュータにより実行可能な最適化プログラムであって、
Ｎ個の変数の組により定義されるＮ次元変数空間上の点を表す変数ベクトルの集合を解候補の集合として記憶部に記憶する処理と、
前記記憶された解候補の集合から所定数の解候補を選択する処理と、
前記選択された所定数の解候補に基づいて（ｍ−１）次元単位球面を含むＮ次元変数空間上に新たな解候補の集合を生成し、生成された解候補の集合を前記最適化対象および前記記憶部に与える処理と、
前記最適化対象から出力される状態量の評価値を算出する処理と、
前記算出される評価値に基づいて前記記憶部に記憶される解候補の集合を更新する処理とを前記コンピュータに実行させ、
Ｎは２以上の自然数であり、前記ｍは前記Ｎ以下の自然数であることを特徴とする最適化プログラム。
【請求項１９】
最適化対象に最適化すべきＮ個の変数を有する変数を有する解候補を与え、ｍ個の変数に関して周期性を有する目的関数を含む前記Ｎ個の変数についての目的関数に対応する状態量を前記最適化対象から受けるコンピュータにより実行可能な最適化プログラムであって、
Ｎ個の変数の組により定義されるＮ次元変数空間上の点を表す変数ベクトルの集合を解候補の集合として記憶部に記憶する処理と、
前記記憶された解候補の集合から所定数の解候補を選択する処理と、
前記選択された所定数の解候補に基づいてｍ個の変数をｍ個の１次元単位球面上の点に対応付けることによりＮ次元変数空間を［（Ｎ−ｍ）＋２ｍ］次元変数空間に拡張し、拡張された［（Ｎ−ｍ）＋２ｍ］次元変数空間上に解候補の集合を生成し、生成された解候補の集合をＮ次元変数空間上の点に再び対応付けることにより新たな解候補の集合を生成し、生成された解候補の集合を前記最適化対象および前記記憶部に与える処理と、
前記最適化対象から出力される状態量の評価値を算出する処理と、
前記算出される評価値に基づいて前記記憶部に記憶される解候補の集合を更新する処理とを前記コンピュータに実行させ、
Ｎは１以上の自然数であり、前記ｍは前記Ｎ以下の自然数であることを特徴とする最適化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適化対象の変数を最適化する最適化装置、最適化方法および最適化プログラムに関する。
【背景技術】
【０００２】
工学においては、種々の最適化問題が存在する。例えば、エンジンの制御パラメータの最適化では、エンジンの状態量の評価値が最も高くなるように制御パラメータを最適化し、最適化された制御パラメータを最適解として求める。例えば、排出ガスの特定の成分の濃度が低減されるようにエンジンにおける燃料噴射時期を最適化する。最適化問題では、最適化されるべき変数を決定変数と呼ぶ。上記の例では、制御パラメータである燃料噴射時期が決定変数であり、排出ガスの特定の成分の濃度が状態量である。
【０００３】
最適化問題に遺伝的アルゴリズム（ＧＡ：Genetic Algorithm）等の進化型アルゴリズムを適用する研究が数多く行われている。
【０００４】
遺伝的アルゴリズムは、生物の適応進化を模倣した計算手法である。この遺伝的アルゴリズムでは、解の候補を個体と呼ぶ。遺伝的アルゴリズムを用いた最適化処理では、まず、初期の個体集合を生成し、各個体について適応度関数を用いて適応度の評価を行う。適応度が良い個体を良い個体とみなす。なお、以下では最小化問題を考え、決定変数は連続値をとるとする。したがって、適応度の値が小さいほど適応度が良いとみなす。
【０００５】
各個体の適応度に基づいて個体集合から所定数の個体を親個体として選択する。選択された親個体を部分的に組み合わせる交叉を行うことにより子個体を生成し、子個体の適応度を評価する。評価結果に基づいて子個体を親個体と入れ換えることにより次の世代の個体集合を生成する。このようにして世代交代を繰り返すことにより最も適応度の良い個体を最適個体として求める。最適個体が最適化問題の最適解となる。すなわち、遺伝的アルゴリズムでは、交叉により複数の個体を生成および評価する多点探索を行う。
【０００６】
工学の分野では、決定変数の変化により評価値が周期的に変化する最適化問題がある。例えば、エンジンまたはモータのように回転機構を有する装置では、回転軸の１回転ごとに状態量が周期的に変化する。また、交通信号の広域制御では、交通信号が周期的に点滅する。さらに、画像処理におけるパターンマッチングでは、テンプレートに対して対象画像を回転させつつ両者が一致するか否かを判定する場合に、テンプレートと対象画像とのマッチング量（一致の程度）が周期的に変化する。
【０００７】
また、蛋白質において共有結合で結合した二原子間の二面角は可変であり、結合が３６０度回転することにより元の二面角に一致する。さらに、ロボットのリンク機構が３６０度回転可能な場合、リンク機構は３６０度回転することにより元の姿勢に戻る。
【０００８】
したがって、回転機構を有する装置のタイミングの最適化、画像処理におけるパターンマッチング、蛋白質の構造の推定における二面角の最適化およびロボットのリンク機構の姿勢の最適化は、決定変数の変化により評価値が周期的に変化する最適化問題である。
【０００９】
目的関数（適応度関数）が周期的に変化する最適化問題は、次式により表すことができる。
【００１０】
【数１】
2006294002.tif 000003
【００１１】
上式（１）において、θは実数Ｒに属する決定変数であり、ｆ（θ）は周期的な目的関数（以下、周期関数と呼ぶ）であり、Ｎは任意の整数である。上式に示されるように、周期関数ｆ（θ）は周期２πを有する。最適解は周期関数ｆ（θ）の値を最小にする決定変数である。
【００１２】
ここで、上記の遺伝的アルゴリズムを用いて周期関数ｆ（θ）における決定変数を最適化することを考える。θmin を決定変数の最小値とし、θmax を決定変数の最大値とする。周期関数ｆ（θ）の定義域［θmin ，θmax ］を［−∞，＋∞］とした場合、全く等しい適応度を有する最適解（最適個体）が無数に存在する。そのため、交叉により多点探索を行う遺伝的アルゴリズムでは、無駄な探索を行う可能性がある。
【００１３】
そこで、周期関数ｆ（θ）の定義域［θmin ，θmax ］を適当な範囲に設定し、その定義域［θmin ，θmax ］内で決定変数を最適化することが考えられる。この場合、定義域［θmin ，θmax ］を２πの範囲となるように設定する。例えば、定義域［θmin ，θmax ］を［−π，π］に設定する。それにより、上式（１）は次式（２）に置き換えることができる。
【００１４】
【数２】
2006294002.tif 000004
【００１５】
上式（２）は、定義域［−π，π］で周期関数ｆ（θ）の値が最小となる決定変数θを最適解として求めることを意味する。遺伝的アルゴリズムでは、周期関数ｆ（θ）の値が適応度に相当する。すなわち、周期関数ｆ（θ）の値が小さいほど適応度が良い。
【００１６】
決定変数が２進コードにより表される遺伝的アルゴリズムはビットストリングＧＡと呼ばれ、決定変数が実数コード（浮動小数点表示）により表される遺伝的アルゴリズムは実数値ＧＡと呼ばれる。
【００１７】
ビットストリングＧＡでは、親個体の交叉により生成された子個体の決定変数は定義域を外れることはない。これに対して、実数値ＧＡでは、親個体の交叉により生成された子個体の決定変数が定義域を外れることがある。
【００１８】
例えば、ＵＮＤＸ（単峰性正規分布交叉：Unimodal Normal Disribution Crossover）と呼ばれる交叉方法およびＢＬＸ−α（ブレンド交叉：Blend Crossover）と呼ばれる交叉方法では、２つの親個体間の領域の外側にも子個体が生成される。すなわち、ＵＮＤＸおよびＢＬＸ−αは外挿性を有する交叉方法である。実数値ＧＡにおいて、外挿性を有する交叉方法を用いた場合には、親個体の交叉により生成された子個体の決定変数が定義域を外れる。そのため、定義域を外れた子個体に何らかの処理を行うことが必要となる。
【００１９】
その一方、実数値ＧＡでは、ビットストリングＧＡに比べて高い探索性能が得られるので、実数値ＧＡを用いることが望まれる。
【非特許文献１】友部，小野，小林：ＧＡによる蛋白質の構造決定に関する実験的考察，第２５回知能システムシンポジウム講演資料，ｐｐ．４３−４８（１９９８）
【非特許文献２】T. Back: Evolutionary Algorithms in Theory and Practice, Oxford (1996)
【発明の開示】
【発明が解決しようとする課題】
【００２０】
しかしながら、実数値ＧＡを用いて周期関数における決定変数を最適化する場合、以下に示すように、定義域の設定範囲により問題の性質が異なることになる。
【００２１】
図３５は周期関数の定義域の設定範囲の一例を示す模式図である。図３６は周期関数の定義域の設定範囲の他の例を示す模式図である。図３５および図３６の横軸は決定変数であり、縦軸は適応度（周期関数の値）である。なお、図３５および図３６において、黒丸印は個体を表している。
【００２２】
図３５および図３６においては、周期関数の値が最小となる決定変数の値を最適解として探索する。
【００２３】
図３５の例では、周期関数の値が定義域［−π ，π ］の中心部で最小となる。それにより、周期関数は単峰性の形状を有し、定義域［−π，π ］の中心部で最適解が探索される。
【００２４】
一方、図３６の例では、周期関数の値が定義域［−π ，π ］の一方の境界の近傍で最小となる。それにより、周期関数は二峰性の形状を有し、定義域［−π，π ］の一方の境界の近傍で最適解が探索され、定義域［−π ，π ］の他方の境界に定義域の設定に伴う局所解が現れる。
【００２５】
図３６のような場合、実数値ＧＡでは、サンプリングバイアスおよび進化的停滞という２つの問題が生じる。
【００２６】
図３７は実数値ＧＡの交叉による子個体の生起確率密度分布を示す模式図である。図３７の横軸は決定変数であり、縦軸は子個体の生起確率密度である。図３７において、Ｐ（θ）は子個体の生起確率密度分布である。定義域［−π，π］に一様に分布した親個体を用いて交叉を繰り返すと、図３７に示されるように、定義域［−π，π］の中心部に子個体が生成される確率が高く、定義域［−π，π］の境界付近に子個体が生成される確率は低くなる。この現象をサンプリングバイアスと呼ぶ。
【００２７】
したがって、定義域の設定範囲が適切でない場合には、定義域［−π，π］の境界付近に存在する最適解を発見することが困難となる。
【００２８】
図３８は進化的停滞を説明するための模式図である。図３８の横軸は決定変数であり、縦軸は適応度（周期関数の値）である。
【００２９】
図３８の例では、定義域［−π ，π ］の一方の境界の近傍に最適解が存在し、定義域［−π ，π］の他方の境界に局所解が表れる。この場合、最適解の近傍の親個体Ｐ１および局所解の近傍の親個体Ｐ２を用いて交叉を行うと、定義域［−π ，π］の中央部の適応度が悪い領域（周期関数の値が大きい領域）に子個体Ｃ１〜Ｃ７が生成される。このように、適応度が良い定義域［−π ，π］の境界近傍に子個体が生成されにくくなるため、最適解の探索が停滞し、探索効率が悪い。
【００３０】
上記のサンプリングバイアスを緩和するためにTsutsuiのＢＥＭ（Boundary Extension by Mirroring）に代表される境界法が提案されている。
【００３１】
図３９は境界法を説明するための模式図である。図３９の横軸は決定変数であり、縦軸は適応度（周期関数の値）である。なお、図３９において、黒丸印は個体を表している。
【００３２】
図３９に示すように、境界法では、予め定められた拡張率に基づいて定義域の境界近傍の領域が定義域の境界を中心として折り返されることにより、定義域が拡張される。それにより、定義域の境界付近でのサンプリングバイアスの影響が緩和される。その結果、最適解の発見の可能性が向上する。
【００３３】
しかしながら、境界法を用いた場合でも、局所解は依然として残るため、進化的停滞の問題を解決することはできない。
【００３４】
したがって、周期関数における決定変数の最適化に実数値ＧＡを用いる場合には、位相のつながりを考慮した交叉の工夫を施す必要がある。非特許文献１には、決定変数の定義域［−π，π］で親個体間のなす角度がπ以上となった場合には、補角領域に子個体を生成する方法が提案されている。
【００３５】
しかしながら、非特許文献１の方法によれば、親個体に対する補角領域の判定が必要となる。また、この方法は、多数の親個体を用いた交叉へ拡張することが困難である。そのため、周期関数における決定変数の最適化の処理が煩雑となる。
【００３６】
本発明の目的は、変数の最適化を効率的に行うことが可能な最適化装置、最適化方法および最適化プログラムを提供することである。
【課題を解決するための手段】
【００３７】
（１）第１の発明に係る最適化装置は、最適化すべきＮ個の変数のうちｍ個の変数の２乗の総和が１となる拘束を有する場合に最適化対象にＮ個の変数を有する解候補を与え、Ｎ個の変数についての目的関数に対応する状態量を最適化対象から受ける最適化装置であって、Ｎ個の変数の組により定義されるＮ次元変数空間上の点を表す変数ベクトルの集合を解候補の集合として記憶する解候補記憶部と、解候補記憶部に記憶された解候補の集合から所定数の解候補を選択する解候補選択部と、解候補選択部により選択された所定数の解候補に基づいて（ｍ−１）次元単位球面を含むＮ次元変数空間上に新たな解候補の集合を生成し、生成された解候補の集合を最適化対象および解候補記憶部に与える解候補生成部と、最適化対象から出力される状態量の評価値を算出する評価値演算部と、評価値演算部により算出される評価値に基づいて解候補記憶部に記憶される解候補の集合を更新する解候補集合更新部とを備え、Ｎは２以上の自然数であり、ｍはＮ以下の自然数である。
【００３８】
その最適化装置においては、最適化すべきＮ個の変数のうちｍ個の変数の２乗の総和が１となる拘束を有する場合に最適化対象にＮ個の変数を有する解候補が与えられ、Ｎ個の変数についての目的関数に対応する状態量が最適化対象から出力される。解候補記憶部には、Ｎ個の変数の組により定義されるＮ次元変数空間上の点を表す変数ベクトルの集合が解候補の集合として記憶される。
【００３９】
解候補記憶部に記憶された解候補の集合から所定数の解候補が解候補選択部により選択される。選択された所定数の解候補に基づいて（ｍ−１）次元単位球面を含むＮ次元変数空間上に新たな解候補の集合が解候補生成部により生成され、生成された解候補の集合が最適化対象および解候補記憶部に与えられる。
【００４０】
最適化対象から出力される状態量の評価値が評価値演算部により算出され、算出される評価値に基づいて解候補記憶部に記憶される解候補の集合が解候補集合更新部により更新される。上記の処理を繰り返すことにより最適解が得られる。
【００４１】
この場合、（ｍ−１）次元単位球面を含むＮ次元変数空間上に新たな解候補の集合が生成されるので、新たな解候補の生成が定義域の設定に依存しない。それにより、定義域の設定にかかわらず安定的に最適解を得ることができる。また、定義域を任意に設定することができるので、最適化処理が複雑化しない。
【００４２】
また、（ｍ−１）次元単位球面上で連続性を保持したまま解候補の探索が可能となる。したがって、サンプリングバイアスおよび進化的停滞が生じることが防止される。
【００４３】
これらの結果、最適化対象における変数を効率的に最適化することができる。
【００４４】
（２）第２の発明に係る最適化装置は、最適化対象に最適化すべきＮ個の変数を有する解候補を与え、ｍ個の変数に関して周期性を有する目的関数を含むＮ個の変数についての目的関数に対応する状態量を最適化対象から受ける最適化装置であって、Ｎ個の変数の組により定義されるＮ次元変数空間上の点を表す変数ベクトルの集合を解候補の集合として記憶する解候補記憶部と、解候補記憶部に記憶された解候補の集合から所定数の解候補を選択する解候補選択部と、解候補選択部により選択された所定数の解候補に基づいてｍ個の変数をｍ個の１次元単位球面上の点に対応付けることによりＮ次元変数空間を［（Ｎ−ｍ）＋２ｍ］次元変数空間に拡張し、拡張された［（Ｎ−ｍ）＋２ｍ］次元変数空間上に解候補の集合を生成し、生成された解候補の集合をＮ次元変数空間上の点に再び対応付けることにより新たな解候補の集合を生成し、生成された解候補の集合を最適化対象および解候補記憶部に与える解候補生成部と、最適化対象から出力される状態量の評価値を算出する評価値演算部と、評価値演算部により算出される評価値に基づいて解候補記憶部に記憶される解候補の集合を更新する解候補集合更新部とを備え、Ｎは１以上の自然数であり、ｍはＮ以下の自然数である。
【００４５】
その最適化装置においては、最適化対象に最適化すべきＮ個の変数を有する変数を有する解候補が与えられ、ｍ個の変数に関して周期性を有する目的関数を含むＮ個の変数についての目的関数に対応する状態量が最適化対象から出力される。解候補記憶部には、Ｎ個の変数の組により定義されるＮ次元変数空間上の点を表す変数ベクトルの集合が解候補の集合として記憶される。
【００４６】
解候補記憶部に記憶された解候補の集合から所定数の解候補が解候補選択部により選択される。選択された所定数の解候補に基づいてｍ個の変数がｍ個の１次元単位球面上の点に対応付けられることによりＮ次元変数空間が［（Ｎ−ｍ）＋２ｍ］次元変数空間に拡張され、拡張された［（Ｎ−ｍ）＋２ｍ］次元変数空間上に解候補の集合が生成され、生成された解候補の集合がＮ次元変数空間上の点に再び対応付けられることにより新たな解候補の集合が生成され、生成された解候補の集合が最適化対象および解候補記憶部に与えられる。
【００４７】
最適化対象から出力される状態量の評価値が評価値演算部により算出され、算出される評価値に基づいて解候補記憶部に記憶される解候補の集合が解候補集合更新部により更新される。上記の処理を繰り返すことにより最適解が得られる。
【００４８】
この場合、ｍ個の変数がｍ個の１次元単位球面上の点に対応付けられるので、新たな解候補の生成が定義域の設定に依存しない。それにより、定義域の設定にかかわらず安定的に最適解を得ることができる。また、定義域を任意に設定することができるので、最適化処理が複雑化しない。
【００４９】
また、ｍ個の１次元単位球面上で連続性を保持したまま解候補の探索が可能となる。したがって、サンプリングバイアスおよび進化的停滞が生じることが防止される。
【００５０】
これらの結果、最適化対象における周期関数の変数を効率的に最適化することができる。
【００５１】
（３）ｍ個の変数の各々をθとし、２次元平面上の点の第１および第２の座標をそれぞれｘおよびｙとした場合に、解候補生成部は、解候補選択部により選択された所定数の解候補の変数θを（ｘ，ｙ）＝（ｃｏｓθ，ｓｉｎθ）の演算により第１および第２の座標（ｘ，ｙ）に置き換え、生成された各解候補の第１および第２の座標（ｘ，ｙ）を下記式により変数θCに変換してもよい。
【００５２】
【数３】
2006294002.tif 000005
【００５３】
上式において、ｓｉｇｎ（ｙ）はｙが正のときに＋１となり、ｙが負のときに−１となる。
【００５４】
この場合、三角関数を用いた演算により所定数の解候補のｍ個の変数θの各々を容易に第１および第２の座標（ｘ，ｙ）に置き換えることができ、逆正接関数を用いた演算により新たな解候補の第１および第２の座標（ｘ，ｙ）を変数θに容易に変換することができる。
【００５５】
（４）解候補選択部は、周期関数の定義域を周期関数の周期に設定し、設定された定義域が２πになるように周期関数を変数軸の方向に拡大または縮小し、定義域の中心が変数軸の座標０に位置するように周期関数をシフトさせてもよい。
【００５６】
この場合、周期関数の周期が２πと異なる場合でも、周期関数の定義域を２πに変換することにより最適化対象における周期関数の変数を効率的に最適化することが可能となる。
【００５７】
（５）最適化対象は機器の性能を評価するための評価システムを含み、変数ベクトルは評価システムのための制御用パラメータを含み、状態量は評価システムの評価により得られる機器の性能であってもよい。
【００５８】
この場合、評価システムに制御用パラメータが与えられる。評価システムにより制御用パラメータに基づいて機器の性能が評価され、性能に対応する状態量が出力される。この最適化装置によれば、機器の性能が制御用パラメータについて周期性を有する場合に制御用パラメータを効率的に最適化することができる。
【００５９】
（６）評価システムは、制御用パラメータに基づいて機器を制御するとともに機器の動作により発生される機器の性能を状態量として出力する機器評価装置であってもよい。
【００６０】
この場合、機器評価装置に制御用パラメータが与えられる。機器評価装置により制御用パラメータに基づいて機器の動作が評価されることにより機器の性能が状態量として出力される。この最適化装置によれば、機器の性能が制御用パラメータについて周期性を有する場合に制御用パラメータを効率的に最適化することができる。
【００６１】
（７）評価システムは、制御用パラメータに基づいて機器の動作をシミュレーションすることにより機器の性能を評価し、評価された性能を状態量として出力する機器シミュレータであってもよい。
【００６２】
この場合、機器シミュレータに制御用パラメータが与えられる。機器シミュレータにより制御用パラメータに基づいて機器の動作がシミュレーションされることにより機器の性能が状態量として出力される。この最適化装置によれば、機器の性能が制御用パラメータについて周期性を有する場合に制御用パラメータを効率的に最適化することができる。
【００６３】
（８）機器は内燃機関であり、制御用パラメータは内燃機関のクランク回転角度に基づくパラメータであり、状態量はパラメータについて周期的に変化する内燃機関の性能であってもよい。
【００６４】
この場合、機器評価システムに内燃機関のクランク回転角度に基づくパラメータが与えられる。機器評価システムによりパラメータに基づいて内燃機関の動作が評価されることにより内燃機関の性能が状態量として出力される。この最適化装置によれば、内燃機関の性能がクランク回転角度に基づくパラメータについて周期性を有する場合にパラメータを効率的に最適化することができる。
【００６５】
（９）内燃機関は燃料噴射装置を有し、クランク回転角度に基づくパラメータは燃料噴射装置の燃料噴射時期を含んでもよい。
【００６６】
この場合、機器評価システムに内燃機関の制御用パラメータとして燃料噴射装置の燃料噴射時期が与えられる。機器評価システムにより制御用パラメータに基づいて燃料噴射装置の燃料噴射時期が制御されることにより内燃機関の性能が状態量として出力される。この最適化装置によれば、内燃機関の性能が燃料噴射装置の燃料噴射時期について周期性を有する場合にパラメータを効率的に最適化することができる。
【００６７】
（１０）内燃機関は燃料噴射装置を有し、クランク回転角度に基づくパラメータは、複数の区間を含む一定期間内における燃料噴射装置による燃料噴射パターンであり、燃料噴射パターンは、燃料噴射装置による燃料噴射量の合計が一定となるような各区間の燃料噴射量からなるベクトルであり、状態量はパラメータについて周期的に変化する内燃機関の性能であってもよい。
【００６８】
この場合、機器評価システムに内燃機関の制御用パラメータとして燃料噴射装置の燃料噴射パターンが与えられる。機器評価システムにより制御用パラメータに基づいて燃料噴射装置の燃料噴射パターンが制御されることにより内燃機関の性能が状態量として出力される。この最適化装置によれば、内燃機関の性能が燃料噴射装置の燃料噴射パターンについて周期性を有する場合にパラメータを効率的に最適化することができる。
【００６９】
（１１）状態量は、排出ガス中の所定の成分の濃度、燃料消費量、出力トルク、スロットル弁の開度およびクランク回転速度のうち少なくとも１つを含んでもよい。
【００７０】
この場合、機器評価システムによりクランク回転角度に基づくパラメータに基づいて内燃機関の動作が評価されることにより排出ガス中の所定の成分の濃度、燃料消費量、出力トルク、スロットル弁の開度およびクランク回転速度のうち少なくとも１つが状態量として出力される。この最適化装置によれば、排出ガス中の所定の成分の濃度、燃料消費量、出力トルク、スロットル弁の開度およびクランク回転速度のうち少なくとも１つがクランク回転角度に基づくパラメータについて周期性を有する場合にパラメータを効率的に最適化することができる。
【００７１】
（１２）機器はロボットリンク機構であり、変数ベクトルはリンク機構の関節がなす角度を示すパラメータであり、状態量はパラメータについて周期的に変化するロボットリンク機構の性能であってもよい。
【００７２】
この場合、機器評価システムにロボットリンク機構の関節がなす角度を示すパラメータが与えられる。機器評価システムによりパラメータに基づいてロボットリンク機構の動作が評価されることによりロボットリンク機構の性能が状態量として出力される。この最適化装置によれば、ロボットリンク機構の性能が関節がなす角度を示すパラメータについて周期性を有する場合にパラメータを効率的に最適化することができる。
【００７３】
（１３）最適化対象は、道路に配置された複数の交通信号を含む交通システムの広域制御をシミュレーションする交通シミュレータであり、変数ベクトルは少なくとも１つ交通信号の点灯タイミングであり、状態量は道路を通過する車に関する情報を含んでもよい。
【００７４】
この場合、交通シミュレータに少なくとも１つ交通信号の点灯タイミングが与えられる。交通シミュレータにより少なくとも１つ交通信号の点灯タイミングに基づいて交通システムの広域制御がシミュレーションされ、道路を通過する車に関する情報が出力される。この最適化装置によれば、道路を通過する車に関する情報が少なくとも１つ交通信号の点灯タイミングについて周期性を有する場合に少なくとも１つ交通信号の点灯タイミングを効率的に最適化することができる。
【００７５】
（１４）最適化装置は、蛋白質の構造をシミュレーションする蛋白質シミュレータであり、変数ベクトルは蛋白質の共有結合間の二面角を表す方向ベクトルであり、状態量はエネルギーに関する情報であってもよい。
【００７６】
この場合、蛋白質シミュレータに蛋白質の共有結合間の二面角を表す方向ベクトルが与えられる。蛋白質シミュレータにより方向ベクトルに基づいて蛋白質の構造がシミュレーションされ、エネルギーに関する情報が出力される。この最適化装置によれば、エネルギーに関する情報が蛋白質の共有結合間の二面角を表す方向ベクトルについて周期性を有する場合に方向ベクトルを効率的に最適化することができる。
【００７７】
（１５）最適化対象は、対象画像と参照画像とのマッチング処理を行う画像処理装置であり、変数ベクトルは参照画像に対する対象画像の方向ベクトルであり、状態量は対象画像と参照画像との誤差を示す情報であってもよい。
【００７８】
この場合、画像処理装置に参照画像に対する対象画像の方向ベクトルが与えられる。画像処理装置により方向ベクトルに基づいて対象画像と参照画像とのマッチング処理が行われ、対象画像と参照画像との誤差を示す情報が出力される。この最適化装置によれば、対象画像と参照画像との誤差を示す情報が参照画像に対する対象画像の方向ベクトルについて周期性を有する場合に方向ベクトルを効率的に最適化することができる。
【００７９】
（１６）第３の発明に係る最適化方法は、最適化すべきＮ個の変数のうちｍ個の変数の２乗の総和が１となる拘束を有する場合に最適化対象にＮ個の変数を有する解候補を与え、Ｎ個の変数についての目的関数に対応する状態量を最適化対象から受ける最適化方法であって、Ｎ個の変数の組により定義されるＮ次元変数空間上の点を表す変数ベクトルの集合を解候補の集合として記憶部に記憶するステップと、記憶された解候補の集合から所定数の解候補を選択するステップと、選択された所定数の解候補に基づいて（ｍ−１）次元単位球面を含むＮ次元変数空間上に新たな解候補の集合を生成し、生成された解候補の集合を最適化対象および記憶部に与えるステップと、最適化対象から出力される状態量の評価値を算出するステップと、算出される評価値に基づいて記憶部に記憶される解候補の集合を更新するステップとを備え、Ｎは２以上の自然数であり、ｍはＮ以下の自然数である。
【００８０】
その最適化方法においては、最適化対象に最適化すべきＮ個の変数を有する変数を有する解候補が与えられ、ｍ個の変数の２乗の総和が１となる拘束を有する目的関数を含むＮ個の変数についての目的関数に対応する状態量が最適化対象から出力される。記憶部には、Ｎ個の変数の組により定義されるＮ次元変数空間上の点を表す変数ベクトルの集合が解候補の集合として記憶される。
【００８１】
記憶部に記憶された解候補の集合から所定数の解候補が選択される。選択された所定数の解候補に基づいて（ｍ−１）次元単位球面を含むＮ次元変数空間上に新たな解候補の集合が生成され、生成された解候補の集合が最適化対象および記憶部に与えられる。
【００８２】
最適化対象から出力される状態量の評価値が算出され、算出される評価値に基づいて記憶部に記憶される解候補の集合が更新される。上記の処理を繰り返すことにより最適解が得られる。
【００８３】
この場合、（ｍ−１）次元単位球面を含むＮ次元変数空間上に新たな解候補の集合が生成されるので、新たな解候補の生成が定義域の設定に依存しない。それにより、定義域の設定にかかわらず安定的に最適解を得ることができる。また、定義域を任意に設定することができるので、最適化処理が複雑化しない。
【００８４】
また、（ｍ−１）次元単位球面上で連続性を保持したまま解候補の探索が可能となる。したがって、サンプリングバイアスおよび進化的停滞が生じることが防止される。
【００８５】
これらの結果、最適化対象における変数を効率的に最適化することができる。
【００８６】
（１７）第４の発明に係る最適化方法は、最適化対象に最適化すべきＮ個の変数を有する変数を有する解候補を与え、ｍ個の変数に関して周期性を有する目的関数を含むＮ個の変数についての目的関数に対応する状態量を最適化対象から受ける最適化方法であって、Ｎ個の変数の組により定義されるＮ次元変数空間上の点を表す変数ベクトルの集合を解候補の集合として記憶部に記憶するステップと、記憶された解候補の集合から所定数の解候補を選択するステップと、選択された所定数の解候補に基づいてｍ個の変数をｍ個の１次元単位球面上の点に対応付けることによりＮ次元変数空間を［（Ｎ−ｍ）＋２ｍ］次元変数空間に拡張し、拡張された［（Ｎ−ｍ）＋２ｍ］次元変数空間上に解候補の集合を生成し、生成された解候補の集合をＮ次元変数空間上の点に再び対応付けることにより新たな解候補の集合を生成し、生成された解候補の集合を最適化対象および記憶部に与えるステップと、最適化対象から出力される状態量の評価値を算出するステップと、算出される評価値に基づいて記憶部に記憶される解候補の集合を更新するステップとを備え、Ｎは１以上の自然数であり、ｍはＮ以下の自然数である。
【００８７】
その最適化方法においては、最適化対象に最適化すべきＮ個の変数を有する変数を有する解候補が与えられ、ｍ個の変数に関して周期性を有する目的関数を含むＮ個の変数についての目的関数に対応する状態量が最適化対象から出力される。記憶部には、Ｎ個の変数の組により定義されるＮ次元変数空間上の点を表す変数ベクトルの集合が解候補の集合として記憶される。
【００８８】
記憶部に記憶された解候補の集合から所定数の解候補が選択される。選択された所定数の解候補に基づいてｍ個の変数がｍ個の１次元単位球面上の点に対応付けられることによりＮ次元変数空間が［（Ｎ−ｍ）＋２ｍ］次元変数空間に拡張され、拡張された［（Ｎ−ｍ）＋２ｍ］次元変数空間上に解候補の集合が生成され、生成された解候補の集合がＮ次元変数空間上の点に再び対応付けられることにより新たな解候補の集合が生成され、生成された解候補の集合が最適化対象および記憶部に与えられる。
【００８９】
最適化対象から出力される状態量の評価値が算出され、算出される評価値に基づいて記憶部に記憶される解候補の集合が更新される。上記の処理を繰り返すことにより最適解が得られる。
【００９０】
この場合、ｍ個の変数がｍ個の１次元単位球面上の点に対応付けられるので、新たな解候補の生成が定義域の設定に依存しない。それにより、定義域の設定にかかわらず安定的に最適解を得ることができる。また、定義域を任意に設定することができるので、最適化処理が複雑化しない。
【００９１】
また、ｍ個の１次元単位球面上で連続性を保持したまま解候補の探索が可能となる。したがって、サンプリングバイアスおよび進化的停滞が生じることが防止される。
【００９２】
これらの結果、最適化対象における周期関数の変数を効率的に最適化することができる。
【００９３】
（１８）第５の発明に係る最適化プログラムは、最適化すべきＮ個の変数のうちｍ個の変数の２乗の総和が１となる拘束を有する場合に最適化対象にＮ個の変数を有する解候補を与え、Ｎ個の変数についての目的関数に対応する状態量を最適化対象から受けるコンピュータにより実行可能な最適化プログラムであって、Ｎ個の変数の組により定義されるＮ次元変数空間上の点を表す変数ベクトルの集合を解候補の集合として記憶部に記憶する処理と、記憶された解候補の集合から所定数の解候補を選択する処理と、選択された所定数の解候補に基づいて（ｍ−１）次元単位球面を含むＮ次元変数空間上に新たな解候補の集合を生成し、生成された解候補の集合を最適化対象および記憶部に与える処理と、最適化対象から出力される状態量の評価値を算出する処理と、算出される評価値に基づいて記憶部に記憶される解候補の集合を更新する処理とをコンピュータに実行させ、Ｎは２以上の自然数であり、ｍはＮ以下の自然数である。
【００９４】
その最適化プログラムにおいては、最適化対象に最適化すべきＮ個の変数を有する変数を有する解候補が与えられ、ｍ個の変数の２乗の総和が１となる拘束を有する目的関数を含むＮ個の変数についての目的関数に対応する状態量が最適化対象から出力される。記憶部には、Ｎ個の変数の組により定義されるＮ次元変数空間上の点を表す変数ベクトルの集合が解候補の集合として記憶される。
【００９５】
記憶部に記憶された解候補の集合から所定数の解候補が選択される。選択された所定数の解候補に基づいて（ｍ−１）次元単位球面を含むＮ次元変数空間上に新たな解候補の集合が生成され、生成された解候補の集合が最適化対象および記憶部に与えられる。
【００９６】
最適化対象から出力される状態量の評価値が算出され、算出される評価値に基づいて記憶部に記憶される解候補の集合が更新される。上記の処理を繰り返すことにより最適解が得られる。
【００９７】
この場合、（ｍ−１）次元単位球面を含むＮ次元変数空間上に新たな解候補の集合が生成されるので、新たな解候補の生成が定義域の設定に依存しない。それにより、定義域の設定にかかわらず安定的に最適解を得ることができる。また、定義域を任意に設定することができるので、最適化処理が複雑化しない。
【００９８】
また、ｍ次元単位球面上で連続性を保持したまま解候補の探索が可能となる。したがって、サンプリングバイアスおよび進化的停滞が生じることが防止される。
【００９９】
これらの結果、最適化対象における変数を効率的に最適化することができる。
【０１００】
（１９）第６の発明に係る最適化プログラムは、最適化対象に最適化すべきＮ個の変数を有する変数を有する解候補を与え、ｍ個の変数に関して周期性を有する目的関数を含むＮ個の変数についての目的関数に対応する状態量を最適化対象から受けるコンピュータにより実行可能な最適化プログラムであって、Ｎ個の変数の組により定義されるＮ次元変数空間上の点を表す変数ベクトルの集合を解候補の集合として記憶部に記憶する処理と、記憶された解候補の集合から所定数の解候補を選択する処理と、選択された所定数の解候補に基づいてｍ個の変数をｍ個の１次元単位球面上の点に対応付けることによりＮ次元変数空間を［（Ｎ−ｍ）＋２ｍ］次元変数空間に拡張し、拡張された［（Ｎ−ｍ）＋２ｍ］次元変数空間上に解候補の集合を生成し、生成された解候補の集合をＮ次元変数空間上の点に再び対応付けることにより新たな解候補の集合を生成し、生成された解候補の集合を最適化対象および記憶部に与える処理と、最適化対象から出力される状態量の評価値を算出する処理と、算出される評価値に基づいて記憶部に記憶される解候補の集合を更新する処理とをコンピュータに実行させ、Ｎは１以上の自然数であり、ｍはＮ以下の自然数である。
【０１０１】
その最適化プログラムにおいては、最適化対象に最適化すべきＮ個の変数を有する変数を有する解候補が与えられ、ｍ個の変数に関して周期性を有する目的関数を含むＮ個の変数についての目的関数に対応する状態量が最適化対象から出力される。記憶部には、Ｎ個の変数の組により定義されるＮ次元変数空間上の点を表す変数ベクトルの集合が解候補の集合として記憶される。
【０１０２】
記憶部に記憶された解候補の集合から所定数の解候補が選択される。選択された所定数の解候補に基づいてｍ個の変数がｍ個の１次元単位球面上の点に対応付けられることによりＮ次元変数空間が［（Ｎ−ｍ）＋２ｍ］次元変数空間に拡張され、拡張された［（Ｎ−ｍ）＋２ｍ］次元変数空間上に解候補の集合が生成され、生成された解候補の集合がＮ次元変数空間上の点に再び対応付けられることにより新たな解候補の集合が生成され、生成された解候補の集合が最適化対象および記憶部に与えられる。
【０１０３】
最適化対象から出力される状態量の評価値が算出され、算出される評価値に基づいて記憶部に記憶される解候補の集合が更新される。上記の処理を繰り返すことにより最適解が得られる。
【０１０４】
この場合、ｍ個の変数がｍ個の１次元単位球面上の点に対応付けられるので、新たな解候補の生成が定義域の設定に依存しない。それにより、定義域の設定にかかわらず安定的に最適解を得ることができる。また、定義域を任意に設定することができるので、最適化処理が複雑化しない。
【０１０５】
また、ｍ個の１次元単位球面上で連続性を保持したまま解候補の探索が可能となる。したがって、サンプリングバイアスおよび進化的停滞が生じることが防止される。
【０１０６】
これらの結果、最適化対象における周期関数の変数を効率的に最適化することができる。
【発明の効果】
【０１０７】
第１、第３および第５の発明によれば、（ｍ−１）次元単位球面を含むＮ次元変数空間上に新たな解候補の集合が生成されるので、新たな解候補の生成が定義域の設定に依存しない。それにより、定義域の設定にかかわらず安定的に最適解を得ることができる。また、定義域を任意に設定することができるので、最適化処理が複雑化しない。
【０１０８】
また、（ｍ−１）次元単位球面上で連続性を保持したまま解候補の探索が可能となる。したがって、サンプリングバイアスおよび進化的停滞が生じることが防止される。
【０１０９】
これらの結果、最適化対象における変数を効率的に最適化することができる。
【０１１０】
第２、第４および第６の発明によれば、ｍ個の変数がｍ個の１次元単位球面上の点に対応付けられるので、新たな解候補の生成が定義域の設定に依存しない。それにより、定義域の設定にかかわらず安定的に最適解を得ることができる。また、定義域を任意に設定することができるので、最適化処理が複雑化しない。
【０１１１】
また、ｍ個の１次元単位球面上で連続性を保持したまま解候補の探索が可能となる。したがって、サンプリングバイアスおよび進化的停滞が生じることが防止される。
【０１１２】
これらの結果、最適化対象における周期関数の変数を効率的に最適化することができる。
【発明を実施するための最良の形態】
【０１１３】
（１）第１の実施の形態
本実施の形態では、個体の交叉に後述する超球面上の交叉が用いられる。
【０１１４】
（ａ）最適化装置の機能的な構成
まず、本発明の第１の実施の形態に係る最適化装置を図１に基づき説明する。図１は本発明の第１の実施の形態に係る最適化装置の機能的な構成を示すブロック図である。
【０１１５】
図１の最適化装置１は、進化型アルゴリズムとして遺伝的アルゴリズム（ＧＡ）を利用して周期関数における決定変数の最適解を算出する。この最適化装置１は、最適化対象８に接続される。遺伝的アルゴリズムでは、最適解を最適個体と呼ぶ。
【０１１６】
最適化対象８は、機器の性能を評価する評価システムである。評価システムは、実システムを評価する評価装置またはシミュレータである。本実施の形態では、実システムはエンジンであり、最適化対象８はエンジン評価装置である。
【０１１７】
最適化装置１は、個体生成部２、世代交代部３、個体集合記憶部４、個体選択部５、適応度算出部６および入出力インタフェース７を含む。個体生成部２は、交叉部２１および正規化演算部２２を含む。
【０１１８】
個体生成部２、世代交代部３、個体選択部５および適応度算出部６は、後述するＣＰＵ１０１（図２）が最適化プログラムを実行することにより実現される。個体集合記憶部４は、後述する外部記憶装置１０６（図２）により構成される。
【０１１９】
使用者１０は、最適化装置１に適応度関数（目的関数）を設定する。適応度関数としては、排出ガス中のＣＯ（一酸化炭素）濃度、ＨＣ（炭化水素）濃度、ＮＯｘ（窒素酸化物）濃度、燃料消費量、出力トルク、スロットル弁の開度、エンジンの回転速度等を設定することができる。本実施の形態では、適応度関数としては、エンジンの排出ガス中のＨＣ濃度およびＮＯｘ濃度が用いられる。適応度は、適応度関数の値である。
【０１２０】
ここで、遺伝的アルゴリズムの個体とは、最適化問題の解の候補であり、１または複数の決定変数（制御パラメータ）および１または複数の適応度を有する。決定変数は、最適化されるべき変数である。１または複数の決定変数は決定変数ベクトルで表される。この場合、各決定変数は、決定変数ベクトルの要素である。遺伝的アルゴリズムでは、決定変数は遺伝子と呼ばれる。本実施の形態では、決定変数ベクトルは、複数の決定変数の２乗の総和が１となる拘束を有する。後述する例では、決定変数として、時間軸上の複数の区間における燃料噴射量が用いられる。
【０１２１】
個体集合記憶部４は、複数の個体を記憶する。ここで、各個体は、決定変数ベクトルおよび１または複数の適応度からなる。個体選択部５は、個体集合記憶部４に記憶された複数の個体から子個体の生成のために用いる所定数の個体を親個体として選択する。
【０１２２】
個体生成部２は、個体選択部５により選択された所定数の親個体から複数の子個体を生成し、子個体の決定変数ベクトルを個体集合記憶部４に与えるとともに入出力インタフェース７を介して最適化対象８に与える。個体生成部２の交叉部２１および正規化演算部２２の機能の詳細については後述する。
【０１２３】
最適化対象８は、最適化装置１から与えられた個体の決定変数ベクトルに基づいて状態量を出力する。状態量は、例えば、排出ガス中のＣＯ濃度、ＨＣ濃度、ＮＯｘ濃度、燃料消費量、出力トルク、スロットル弁の開度、エンジンの回転速度等の測定値である。本実施の形態では、状態量は、排出ガス中のＨＣ濃度およびＮＯｘ濃度の測定値である。
【０１２４】
最適化対象８から出力される状態量は、入出力インタフェース７を介して適応度算出部６に入力される。適応度算出部６は、状態量に基づいて適応度を算出し、算出された適応度を個体集合記憶部４に与える。後述する例では、適応度算出部６は、各区間の排出ガス中のＨＣ濃度およびＮＯｘ濃度の平均値を適応度としてそれぞれ算出する。個体集合記憶部４は、適応度算出部６により算出された適応度の組および決定変数ベクトルを個体として記憶する。
【０１２５】
世代交代部３は、個体集合記憶部４に記憶される複数の個体の適応度に基づいて個体集合記憶部４に記憶される個体集合を更新する。それにより、世代交代が行われる。
【０１２６】
このようにして、個体集合記憶部４には、最適個体を含む個体集合が記憶される。最適化装置１は、最適個体を含む個体集合を使用者１０に提示する。
【０１２７】
（ｂ）最適化装置のハードウエア構成
図２は図１の最適化装置１のハードウエア構成を示すブロック図である。
【０１２８】
最適化装置１は、ＣＰＵ（中央演算処理装置）１０１、ＲＯＭ（リードオンリメモリ）１０２、ＲＡＭ（ランダムアクセスメモリ）１０３、入力装置１０４、表示装置１０５、外部記憶装置１０６、記録媒体駆動装置１０７および入出力インタフェース７を含む。
【０１２９】
入力装置１０４は、キーボード、マウス等からなり、各種指令および各種データを入力するために用いられる。ＲＯＭ１０２にはシステムプログラムが記憶される。記録媒体駆動装置１０７は、ＣＤ（コンパクトディスク）ドライブ、ＤＶＤ（デジタルバーサタイルディスク）ドライブ、フレキシブルディスクドライブ等からなり、ＣＤ、ＤＶＤ、フレキシブルディスク等の記録媒体１０９に対してデータの読み書きを行う。
【０１３０】
記録媒体１０９には、最適化プログラムが記録されている。外部記憶装置１０６は、ハードディスク装置等からなり、記録媒体駆動装置１０７を介して記録媒体１０９から読み込まれた最適化プログラムおよび各種データを記憶する。ＣＰＵ１０１は、外部記憶装置１０６に記憶された最適化プログラムをＲＡＭ１０３上で実行する。
【０１３１】
表示装置１０５は、液晶表示パネル、ＣＲＴ（陰極線管）等からなり、個体集合等の各種画像を表示する。入出力インタフェース７には最適化対象８が無線通信または有線通信により接続される。入出力インタフェース７は、最適化対象８から出力される状態量を外部記憶装置１０６に転送するとともに、最適化プログラムにより生成された個体の適応度の組を最適化対象８に与える。
【０１３２】
なお、最適化プログラムを記録する記録媒体１０９として、ＲＯＭ等の半導体メモリ、ハードディスク等の種々の記録媒体を用いることができる。また、最適化プログラムを通信回線等の通信媒体を介して外部記憶装置１０６にダウンロードし、ＲＡＭ１０３上で実行してもよい。
【０１３３】
ここで、記録媒体１０９は、コンピュータで読み取り可能な記録媒体であれば、電子的読み取り方式、磁気的読み取り方式、光学的読み取り方式またはその他のあらゆる読み取り方式の記録媒体を含む。例えば、上記のＣＤ、ＤＶＤおよびフレキシブルディスクの他、ＣＤＶ（コンパクトディスクビデオ）等の光学的読取方式記録媒体、ＲＡＭ、ＲＯＭ等の半導体記録媒体、ハードディスク等の磁気記録型記録媒体、ＭＯ（光磁気ディスク）等の磁気記憶／光学的読取方式記録媒体を用いることができる。
【０１３４】
（ｃ）燃料噴射パターンの最適化への適用
図３は最適化装置を燃料噴射パターンの最適化に適用する方法を説明するための図である。
【０１３５】
燃料噴射量を一定としたまま、ある時間内で種々のパターンで燃料噴射を行うことを考える。この燃料噴射パターンの違いにより、燃料の壁面付着および燃焼状態が変化し、結果的に排出ガス中の有害成分の量に違いが生じる。
【０１３６】
図３の例では、燃料噴射時期を一定とした状態で燃料噴射開始時点０から燃料噴射終了時点ｔ２までを均等に５区間に分割している。ここで、燃料噴射量の合計は一定であるとする。
【０１３７】
各区間の重みをその都度正規化する方法で最適化を行うと、解は無限に存在することになる。そのため、個体の探索の効率が悪くなると考えられる。
【０１３８】
ある区間の燃料噴射量をｘi2（ｉ＝１，…，５）とすると、全区間の燃料噴射量の合計はｘ12＋…＋ｘ52＝１となる。それにより、燃料噴射量ベクトルｘは４次元単位球面上に分布する点であることがわかる。したがって、燃料噴射パターンの最適化に詳細を以下に述べる超球面上の交叉方法（ＵＮＤＸ−Ｈ）を適用することができる。その結果、燃料噴射パターンの最適化を効率的に行うことができる。
【０１３９】
（ｄ）最適化装置の全体処理
図４は図１の最適化装置１の全体処理を示すフローチャートである。図４に示すように、まず、個体生成部２は、予め定められた決定変数の範囲内で個体をランダムに生成することにより初期個体集合を生成し（ステップＳ１）、生成された初期個体集合の各個体の決定変数ベクトルを最適化対象８に順次出力する（ステップＳ２）。それにより、最適化対象８から状態量が順次出力される。
【０１４０】
適応度算出部６は、最適化対象８から出力される各個体に対応する状態量を取得し（ステップＳ３）、取得した状態量に基づいて各個体の適応度を算出する（ステップＳ４）。算出された各個体の適応度は、決定変数ベクトルとともに個体集合記憶部４に記憶される。
【０１４１】
次に、個体選択部５は、個体集合記憶部４に記憶される複数の個体から新たな子個体の生成に用いる所定数の個体を親個体として選択する（ステップＳ５）。本実施の形態では、３つの親個体が選択される。
【０１４２】
さらに、個体生成部２は、個体選択部５により選択された所定数の親個体を用いた交叉により複数の新たな子個体を生成する（ステップＳ６）。ここで、各区間の燃料噴射量を決定変数とする決定変数ベクトルは、決定変数の２乗の総和が１となる拘束を有するので、後述する超面上の交叉方法が用いられる。
【０１４３】
個体生成部２は、各子個体の決定変数ベクトルを最適化対象８に順次出力する（ステップＳ７）。それにより、最適化対象８から状態量が順次出力される。
【０１４４】
適応度算出部６は、最適化対象８から出力される各子個体に対応する状態量を取得し（ステップＳ８）、取得した状態量に基づいて各子個体の適応度を算出する（ステップＳ９）。算出された各子個体の適応度は、決定変数ベクトルとともに個体集合記憶部４に記憶される。
【０１４５】
世代交代部３は、各子個体および各親個体の適応度に基づいて子個体を親個体と入れ換えることにより個体集合記憶部４に記憶される個体集合を更新する（ステップＳ１０）。この場合、世代交代部３は、適応度の大小比較による選択、適応度の高さにより決定される確率による選択、およびランダム選択のうち少なくとも１つの方法で個体集合を更新する。それにより、世代交代が行われる。
【０１４６】
ここで、世代とは、個体集合から親個体を選択する選択ステップ、交叉により新たな子個体を生成する交叉ステップおよび親個体と子個体とを入れ換える世代交代ステップから構成される。世代交代により、個体集合に属する適応度の悪い個体が淘汰される。
【０１４７】
その後、個体生成部２は、世代数が所定の終了条件に到達したか否かを判定する（ステップＳ１１）。
【０１４８】
世代数が所定の終了条件に到達していないと判定した場合には、ステップＳ５に移行する。世代数が所定の終了条件に到達したと判定した場合には、個体生成部２は、個体集合記憶部４に記憶された最適個体を含む個体集合を使用者１０に提示し、処理を終了する。
【０１４９】
（ｅ）最適化処理の一例
図５は図１の最適化装置１による最適化処理の一例を示す模式図である。図５の最適化処理では、世代交代モデルとしてＭＧＧ（Minimal Generation Gap）を用いている。
【０１５０】
図５に示すように、交叉オペレータとしてＵＮＤＸ（単峰性正規分布交叉：Unimodal Normal Distribution Crossover）を用いる場合、個体集合Ｐから３つの親個体ｐ１，ｐ２，ｐ３を選択する。選択された３つの親個体に交叉を行うことにより複数の子個体ｃ１，ｃ２，ｃ３，ｃ４を生成する。親個体ｐ１，ｐ２，ｐ３および子個体ｃ１，ｃ２，ｃ３，ｃ４により家族個体集合Ｆが構成される。家族個体集合Ｆの各個体の適応度を得る。
【０１５１】
家族個体集合Ｆからエリート選択により最良の適応度を有する個体を選択し、選択された個体を個体集合Ｐ内の親個体と置き換える。図５の例では、子個体ｃ２がエリート個体として選択され、個体集合Ｐの親個体ｐ１と置き換えられる。また、家族個体集合Ｆの各個体の適応度に比例する確率でルーレットホイール選択を行い、選択された個体を個体集合Ｐ内の親個体と置き換える。図５の例では、ルーレットホイール選択により子個体ｃ３が選択され、個体集合Ｐの親個体ｐ２と置き換えられる。
【０１５２】
（ｆ）超球面上の交叉方法の基本概念
超球面上の交叉方法について説明する。ｎ次元実数空間Ｒn において、（ｎ−１）次元単位球面Ｓn-1 は次式のように定義される。
【０１５３】
Ｓn-1 ＝｛（ｘ1 ，ｘ2 ，...，ｘn ）∈Ｒn ｜ｘ12＋ｘ22＋...ｘn2＝１｝
上式において、ｎは２以上の任意の自然数であり、ｘ1，ｘ2，…，ｘnはｎ個の決定変数であり、ｎ次元決定変数ベクトルの要素である。すなわち、ｎ次元実数空間Ｒnはｎ個の決定変数により定義される。（ｎ−１）次元単位球面Ｓn-1 はｘ12＋ｘ22＋…＋ｘn2＝１の条件を満足する。
【０１５４】
例えば、２次元実数空間Ｒ2 において、１次元単位球面Ｓ1 はｘ12＋ｘ22＝１の条件を満足する単位円である。３次元実数空間Ｒ3 において、２次元単位球面Ｓ2 はｘ12＋ｘ22＋ｘ32＝１の条件を満足する単位球である。
【０１５５】
ｎ次元実数空間Ｒn の単位方向ベクトルを求める問題は、個体が（ｎ−１）次元単位球面Ｓn-1 に分布する問題として一般化できる。
【０１５６】
ここで、（ｎ−１）次元単位球面を超球面と呼ぶ。
【０１５７】
ここで、超球面上の交叉方法について説明する。図６ａ、図６ｂおよび図６ｃは超球面上の交叉方法を説明するための模式図である。本例では、交叉オペレータとして、ＵＮＤＸが用いられる。図６ａ、図６ｂおよび図６ｃの横軸は決定変数ｘ1、縦軸は決定変数ｘ2である。
【０１５８】
図６ａにおいて、決定変数ｘ1および決定変数ｘ2により定義される２次元実数空間Ｒ2 において、超球面としてｘ12＋ｘ22＝１の条件を満足する単位円ＵＣを設定する。
【０１５９】
図６ａに示すように、単位円ＵＣ上に３つの親個体Ｐ1，Ｐ2，Ｐ3が設定される。親個体Ｐ1，Ｐ2，Ｐ3は、決定変数ｘ1および決定変数ｘ2を要素とする２次元単位方向ベクトルである。ＵＮＤＸでは、３つの親個体Ｐ1，Ｐ2，Ｐ3の位置関係に基づいて定められる正規分布乱数に従って子個体を生成する。
【０１６０】
図６ｂに示すように、３つの親個体Ｐ1，Ｐ2，Ｐ3から複数の子個体Ｃ1’〜Ｃ5’が生成される。子個体Ｃ1’〜Ｃ5’は、決定変数ｘ1および決定変数ｘ2を要素とする２次元決定変数ベクトルである。
【０１６１】
次に、図６ｃに示すように、複数の子個体Ｃ1’〜Ｃ5’をそれぞれ正規化することにより単位円ＵＣに複数の子個体Ｃ1〜Ｃ5を得る。子個体Ｃ1〜Ｃ5は、決定変数ｘ1および決定変数ｘ2を要素とする２次元単位方向ベクトルである。
【０１６２】
本実施の形態において、ｎ次元実数空間Ｒn または２次元実数空間（２次元実数平面）Ｒ2 がＮ次元変数空間に相当し、（ｎ−１）次元単位球面Ｓn-1 、超球面または単位円が（ｍ−１）次元単位球面に相当し、ｎ個の決定変数ｘ１，ｘ２，…，ｘｎがＮ個の変数およびｍ個の変数に相当する。すなわち、本実施の形態では、Ｎ＝ｍ＝ｎである。なお、Ｎ個の変数がｎ個の決定変数以外の変数を含んでもよい。その場合には、Ｎ＞ｍ＝ｎとなる。
【０１６３】
（ｈ）超球面上の交叉方法の手順
図７は超球面上の交叉処理を示すフローチャートである。図７の交叉処理は、図１の個体選択部５、交叉部２１および正規化演算部２２により行われる。
【０１６４】
まず、交叉部２１は、個体集合を（ｎ−１）次元単位球面Ｓn-1 （超球面）上に配置する（ステップＳ２１）。超球面上に分布する個体集合は、個体集合記憶部４に記憶される。
【０１６５】
次に、個体選択部５は、（ｎ−１）次元単位球面Ｓn-1 （超球面）上に分布する個体集合から所定数の個体を親個体として選択する（ステップＳ２２）。
【０１６６】
次に、交叉部２１は、超球面上から選択された所定数の親個体に対してｎ次元実数空間Ｒn 上の点として交叉オペレータを適用することにより複数の子個体を生成する（ステップＳ２３）。各子個体は、ｎ次元実数空間Ｒn 上の決定変数ベクトルＸC’で表される。
【０１６７】
さらに、正規化演算部２２は、各子個体の決定変数ベクトルＸC’の大きさが０か否か、すなわち‖ＸC'‖＝０であるか否かを判定する（ステップＳ２４）。
【０１６８】
‖ＸC'‖＝０である場合には、ステップＳ２１に戻り、子個体を再度生成する。‖ＸC'‖＝０でない場合には、正規化演算部２２は、子個体の決定変数ベクトルＸC’に次式の正規化演算を行う（ステップＳ２５）。
【０１６９】
【数４】
2006294002.tif 000006
【０１７０】
上式により超球面上に子個体の決定変数ベクトルＸCが得られる。
【０１７１】
その後、個体選択部５は、必要数の個体が生成されたか否かを判定する（ステップＳ２６）。必要数の個体が生成されていない場合には、ステップＳ２１に戻り、ステップＳ２１〜Ｓ２６の処理を繰り返す。必要数の個体が生成された場合には、交叉処理を終了する。
【０１７２】
交叉オペレータとしてＵＮＤＸを用いた超球面上の交叉方法をＵＮＤＸ−Ｈ（UNDX for Hyper sphere）と呼ぶ。ＵＮＤＸ−Ｈにより超球面上の親個体から生成された子個体は超球面上に分布する。それにより、超球面上での連続性を保持したまま実数値ＧＡによる個体の探索が可能となる。
【０１７３】
なお、超球面上の交叉方法では、ＵＮＤＸに限らず、他の実数値ＧＡの交叉オペレータを用いることができる。例えば、交叉オペレータとして、ＢＬＸ−αを用いてもよい。ＢＬＸ−αでは、２つの親個体の位置関係から決まる一様分布により子個体を生成する。
【０１７４】
（ｈ）（ｎ−１）次元単位球面上の初期個体集合の生成
図８ａおよび図８ｂは（ｎ−１）次元単位球面上の初期個体集合の生成処理の一例を示す図である。図８ａおよび図８ｂでは、ｎ次元実数空間Ｒn が２次元実数空間Ｒ2 であり、（ｎ−１）次元単位球面Ｓn-1 が１次元単位球面Ｓ1 （単位円）である場合が示される。図８ａおよび図８ｂの横軸は決定変数ｘ1、縦軸は決定変数ｘ2である。
【０１７５】
図８ａに示すように、２次元実数空間Ｒ2 に複数の個体がランダムに生成される。この場合、複数の個体は２次元正規分布を有する。
【０１７６】
次に、図８ｂに示すように、上記の正規化演算により２次元実数空間Ｒ2 上の複数の個体が単位円上の個体に変換される。
【０１７７】
（ｉ）第１の実施の形態の効果
本実施の形態に係る最適化装置１においては、個体の交叉に超球面上の交叉が用いられる。この場合、超球面上の親個体から生成された子個体は超球面上に分布する。それにより、超球面上での連続性を保持したまま実数値ＧＡによる個体の探索が可能となる。
【０１７８】
また、個体を超球面に設定する操作および正規化演算により連続性を保持した交叉が行われるので、全決定変数の２乗和が１となる拘束条件を有する決定変数ベクトルの最適化の処理が煩雑とならない。
【０１７９】
これらの結果、全決定変数の２乗和が１となる拘束条件を有する決定変数ベクトルの最適化を効率的に行うことが可能となる。
【０１８０】
（２）第２の実施の形態
本実施の形態では、個体の交叉に後述する周期関数用の交叉が用いられる。
【０１８１】
（ａ）最適化装置の機能的な構成
次に、本発明の第２の実施の形態に係る最適化装置を図９に基づき説明する。図９は本発明の第２の実施の形態に係る最適化装置の機能的な構成を示すブロック図である。
【０１８２】
図９の最適化装置１が図１の最適化装置１と異なるのは、個体生成部２の構成である。図９の最適化装置１の他の部分の構成は、図１の最適化装置１の対応する部分の構成と同様である。また、図９の最適化装置１のハードウエアの構成は、図２に示した構成と同様である。
【０１８３】
使用者１０は、最適化装置１に適応度関数（目的関数）を設定する。適応度関数としては、排出ガス中のＣＯ（一酸化炭素）濃度、ＨＣ（炭化水素）濃度、ＮＯｘ（窒素酸化物）濃度、燃料消費量、出力トルク、スロットル弁の開度、エンジンの回転速度等を設定することができる。本実施の形態では、適応度関数としては、エンジンの排出ガス中のＨＣ濃度およびＮＯｘ濃度が用いられる。適応度は、適応度関数の値である。
【０１８４】
また、本実施の形態では、決定変数として、燃料噴射時期、点火時期、吸気バルブタイミングおよび排気バルブタイミングが用いられる。すなわち、決定変数ベクトルの次数は４である。ここで、燃料噴射時期を決定変数とする適応度関数は周期関数である。
【０１８５】
最適化対象８から出力される状態量は、例えば、排出ガス中のＣＯ濃度、ＨＣ濃度、ＮＯｘ濃度、燃料消費量、出力トルク、スロットル弁の開度、エンジンの回転速度等の測定値である。本実施の形態では、状態量は、排出ガス中のＨＣ濃度およびＮＯｘ濃度の測定値である。
【０１８６】
図９に示すように、個体生成部２は、交叉部２１、三角関数演算部２３および逆正接関数演算部２４を含む。個体生成部２の詳細な動作については後述する。本実施の形態に係る最適化装置１においては、周期関数を有する個体の交叉として単位円上の交叉が行われる。
【０１８７】
本実施の形態において、燃料噴射時期、点火時期、吸気バルブタイミングおよび排気バルブタイミングがＮ個の変数に相当し、燃料噴射時期がｍ個の変数に相当する。すなわち、本実施の形態では、Ｎ＝４およびｍ＝１である。
【０１８８】
（ｂ）最適化対象の構成
図１０は最適化対象８の構成の一例を示すブロック図である。図１０の最適化対象８はエンジン評価装置である。
【０１８９】
最適化対象８は、ＥＣＵ（エンジン制御ユニット）８１、エンジン８２および排出ガス分析計８３を備える。
【０１９０】
エンジン８２の吸気ポート８４には燃料噴射装置８６および吸気バルブ８７が設けられ、排気ポート８５には排気バルブ８８が設けられている。また、シリンダヘッド８９には、点火プラグ９０が設けられている。
【０１９１】
ＥＣＵ８１は、最適化装置１からシリアル通信により決定変数ベクトルを受ける。本例では、決定変数ベクトルは、燃料噴射時期、点火時期、吸気バルブタイミングおよび排気バルブタイミングを要素として含む。ＥＣＵ８１は、クランクシャフト９１の回転角度（クランク回転角度）を示す信号を受け、決定変数ベクトルに基づいて燃料噴射装置８６の燃料噴射タイミング、点火プラグ９０の点火タイミング、吸気バルブ８７の開閉タイミング（吸気バルブタイミング）および排気バルブ８８の開閉タイミング（排気バルブタイミング）を制御する。
【０１９２】
排出ガス分析計８３は、エンジン８２からの排出ガス中の成分を分析し、ＨＣ濃度およびＮＯｘ濃度を示す排出ガスデータを状態量としてシリアル通信により最適化装置１に出力する。
【０１９３】
燃料噴射時期を決定変数とするＨＣ濃度およびＮＯｘ濃度は、周期７２０°の周期関数となる。
【０１９４】
図１０の最適化対象８は、最適化装置１から個体の決定変数ベクトルとして燃料噴射時期、点火時期、吸気バルブタイミングおよび排気バルブタイミングを受け、状態量としてＨＣ濃度およびＮＯｘ濃度を出力する。
【０１９５】
（ｃ）最適化装置の全体処理
図９の最適化装置１の全体処理を図４のフローチャートを用いて説明する。図４に示すように、まず、個体生成部２は、予め定められた決定変数の範囲内で個体をランダムに生成することにより初期個体集合を生成し（ステップＳ１）、生成された初期個体集合の各個体の決定変数ベクトルを最適化対象８に順次出力する（ステップＳ２）。それにより、最適化対象８から状態量が順次出力される。
【０１９６】
適応度算出部６は、最適化対象８から出力される各個体に対応する状態量を取得し（ステップＳ３）、取得した状態量に基づいて各個体の適応度を算出する（ステップＳ４）。算出された各個体の適応度は、決定変数ベクトルとともに個体集合記憶部４に記憶される。
【０１９７】
次に、個体選択部５は、個体集合記憶部４に記憶される複数の個体から新たな子個体の生成に用いる所定数の個体を親個体として選択する（ステップＳ５）。本実施の形態では、３つの親個体が選択される。
【０１９８】
さらに、個体生成部２は、個体選択部５により選択された所定数の親個体を用いた交叉により複数の新たな子個体を生成する（ステップＳ６）。ここで、燃料噴射時期を決定変数とする適応度関数は周期関数であるため、燃料噴射時期の要素については後述する交叉方法が用いられ、点火時期、吸気バルブタイミングおよび排気バルブタイミングの３つの要素についてはＵＮＤＸ等の一般的な交叉方法が用いられる。
【０１９９】
ここで、燃料噴射時期は角度で表される決定変数である。後述するように、角度は、２次元実数空間上で２つの直交する新たな決定変数に分解される。したがって、交叉前には決定変数ベクトルの次数は４であり、交叉時には決定変数ベクトルの次数は５となり、交叉後に決定変数ベクトルの次数は４に戻る。
【０２００】
個体生成部２は、各子個体の決定変数ベクトルを最適化対象８に順次出力する（ステップＳ７）。それにより、最適化対象８から状態量が順次出力される。
【０２０１】
適応度算出部６は、最適化対象８から出力される各子個体に対応する状態量を取得し（ステップＳ８）、取得した状態量に基づいて各子個体の適応度を算出する（ステップＳ９）。算出された各子個体の適応度は、決定変数ベクトルとともに個体集合記憶部４に記憶される。
【０２０２】
世代交代部３は、各子個体および各親個体の適応度に基づいて子個体を親個体と入れ換えることにより個体集合記憶部４に記憶される個体集合を更新する（ステップＳ１０）。この場合、世代交代部３は、適応度の大小比較による選択、適応度の高さにより決定される確率による選択、およびランダム選択のうち少なくとも１つの方法で個体集合を更新する。それにより、世代交代が行われる。世代交代により、個体集合に属する適応度の悪い個体が淘汰される。
【０２０３】
その後、個体生成部２は、世代数が所定の終了条件に到達したか否かを判定する（ステップＳ１１）。
【０２０４】
世代数が所定の終了条件に到達していないと判定した場合には、ステップＳ５に移行する。世代数が所定の終了条件に到達したと判定した場合には、個体生成部２は、個体集合記憶部４に記憶された最適個体を含む個体集合を使用者１０に提示し、処理を終了する。
【０２０５】
（ｄ）周期関数用の交叉方法の基本概念
次に、先に述べた超球面上の交叉方法を応用した周期関数用の交叉方法について説明する。２次元実数空間（２次元実数平面）Ｒ2 において、１次元単位球面Ｓ1 （単位円）は次式のように定義される。
【０２０６】
Ｓ1 ＝｛（ｘ，ｙ）∈Ｒ2 ｜ｘ2 ＋ｙ2 ＝１｝
上式において、ｘおよびｙは２次元実数平面Ｒ2の座標である。単位円Ｓ1 はｘ2＋ｙ2＝１の条件を満足する。
【０２０７】
ここで、角度θ∈［−π，π］を決定変数として有する周期関数ｆ（θ）について角度θを単位円Ｓ1 上の点として最適化することを考える。すなわち、決定変数を２次元実数平面Ｒ2 における単位方向ベクトルとして考える。
【０２０８】
図１１ａ、図１１ｂおよび図１１ｃは単位円上の交叉方法を説明するための模式図である。本例では、交叉オペレータとしてＵＮＤＸが用いられる。
【０２０９】
図１１ａにおいて、ｘ座標およびｙ座標を有する２次元実数平面Ｒ2 において、ｘ2＋ｙ2＝１の条件を満足する単位円ＵＣを設定する。各個体の決定変数ベクトルの角度θをｘ座標およびｙ座標に分解する。この場合、決定変数として角度θを有する各個体について単位円上の座標（ｘ，ｙ）を次式により算出する。
【０２１０】
（ｘ，ｙ）＝（ｃｏｓθ，ｓｉｎθ）
すなわち、ｘ座標で表される変数およびｙ座標で表される変数を要素とする新たな決定変数ベクトルを考える。この結果、算出された座標（ｘ，ｙ）に基づいて各個体の探索点は２次元実数平面Ｒ2 に設定される。
【０２１１】
図１１ａの例では、単位円ＵＣ上に３つの親個体Ｐ1，Ｐ2，Ｐ3が設定される。３つの親個体Ｐ1，Ｐ2，Ｐ3の決定変数は角度θ1，θ2，θ3である。ＵＮＤＸでは、３つの親個体Ｐ1，Ｐ2，Ｐ3の位置関係に基づいて定められる正規分布乱数に従って子個体を生成する。
【０２１２】
図１１ｂに示すように、３つの親個体Ｐ1，Ｐ2，Ｐ3のｘ座標およびｙ座標から複数の子個体Ｃ1〜Ｃ5が生成される。
【０２１３】
次に、図１１ｃに示すように、２次元実数平面Ｒ2 上の各子個体Ｃ1〜Ｃ5のｘ座標およびｙ座標について次式の逆正接関数により決定変数である角度θC1〜θC5をそれぞれ得る。次式では、複数の子個体Ｃ1〜Ｃ5の角度θC1〜θC5を角度θCとする。
【０２１４】
【数５】
2006294002.tif 000007
【０２１５】
上式において、ｓｉｇｎ（ｙ）はｙが正のときに＋１となり、ｙが負のときに−１となる。
【０２１６】
第２の実施の形態の交叉方法は、第１の実施の形態の交叉方法においてを超球面として単位円を用いた場合と等価である。本実施の形態では、最終的に決定変数として角度θを有する新しい個体（探索点）求める場合に、第１の実施の形態における正規化演算を行うことなく、逆正接関数を用いて直接決定変数である角度θが求められる。
【０２１７】
（ｅ）周期関数用の交叉方法の手順
図１２は単位円上の交叉処理を示すフローチャートである。図１２の交叉処理は、図９の個体選択部５、交叉部２１、三角関数演算部２３および逆正接関数演算部２４により行われる。
【０２１８】
まず、三角関数演算部２３は、各個体の決定変数である角度θを三角関数を用いた演算により２次元実数平面Ｒ2 上のｘ座標およびｙ座標に分解し（ステップＳ３１）、個体集合を単位円上に配置する（ステップＳ３２）。単位円上に分布する個体集合は、個体集合記憶部４に記憶される。
【０２１９】
次に、個体選択部５は、単位円上に分布する個体集合から所定数の個体を親個体として選択する（ステップＳ３３）。
【０２２０】
次に、交叉部２１は、単位円上から選択された所定数の親個体に対して２次元実数平面Ｒ2 上の点として交叉オペレータを適用することにより複数の子個体を生成する（ステップＳ３４）。
【０２２１】
逆正接関数演算部２４は、子個体のｘ座標およびｙ座標を上式の逆正接関数を用いた演算により角度に変換する（ステップＳ３５）。それにより、子個体の決定変数である角度θC が得られる。
【０２２２】
その後、個体選択部５は、必要数の個体が生成されたか否かを判定する（ステップＳ３６）。必要数の個体が生成されていない場合には、ステップＳ３１に戻り、ステップＳ３１〜Ｓ３６の処理を繰り返す。必要数の個体が生成された場合には、交叉処理を終了する。
【０２２３】
交叉オペレータとしてＵＮＤＸを用いた単位円上の交叉方法をＵＮＤＸ−Ｐ（UNDX for Periodic function）と呼ぶ。
【０２２４】
なお、単位円上の交叉方法では、ＵＮＤＸに限らず、他の実数値ＧＡの交叉オペレータを用いることができる。例えば、交叉オペレータとして、ＢＬＸ−αを用いてもよい。
【０２２５】
（ｆ）高次元の周期関数への単位円上の交叉方法の拡張
ｎ次元角度ベクトル（ｎ次元決定変数ベクトル）θ＝（θ1 ，θ2 ，…，θn ）についてのｎ次元の周期関数ｆ（θ）に単位円上の交叉方法を用いる方法を説明する。ｎは任意の自然数である。ここで、θ1 ，θ2 ，…，θnは決定変数である角度であり、ｎ次元決定変数ベクトルの要素である。
【０２２６】
決定変数である角度θi について（ｘi，ｙi）＝（ｃｏｓθi，ｓｉｎθi）から単位円上のｘi座標およびｙi座標をそれぞれ算出する。ここで、ｉ＝１，２，…，ｎである。それにより、各個体を２ｎ次元実数平面Ｒ２ｎにそれぞれ配置する。２ｎ次元実数平面Ｒ２ｎに分布する個体から親個体を選択し、選択された親個体に対してＵＮＤＸを行い、各子個体のｘi 座標およびｙi 座標をそれぞれ算出する。その後、各子個体のｘi 座標およびｙi 座標を逆正接関数を用いた演算により各子個体の決定変数である角度θCiに変換する。
【０２２７】
この場合、単位円が１次元単位球面に相当し、θ1，θ2，…，θnがｍ個の変数の組に相当し、ｎ次元実数空間Ｒn がＮ次元変数空間に相当し、２ｎ次元実数平面Ｒ２ｎが［（Ｎ−ｍ）＋２ｍ］次元変数空間に相当し、ｎ次元角度ベクトル（ｎ次元決定変数ベクトル）θ＝（θ1 ，θ2 ，…，θn ）が変数ベクトルに相当する。すなわち、本例では、Ｎ＝ｍ＝ｎである。
【０２２８】
図１３は単位円上の交叉方法をｎ次元角度ベクトルからなる決定変数ベクトルへ拡張する方法を示す模式図である。本例では、ｎ＝３である。
【０２２９】
図１３に示すように、決定変数である角度θ1 について（ｘ1，ｙ1）＝（ｃｏｓθ1，ｓｉｎθ1）から単位円上のｘ1座標およびｙ1座標をそれぞれ算出する。上記の単位円上の交叉方法により各子個体のｘ1座標およびｙ1座標をそれぞれ算出する。その後、各子個体のｘ1座標およびｙ1座標を逆正接関数により各子個体の決定変数である角度θC1を算出する。
【０２３０】
決定変数である角度θ2 について（ｘ2，ｙ2）＝（ｃｏｓθ2，ｓｉｎθ2）から単位円上のｘ2座標およびｙ2座標をそれぞれ算出する。上記の単位円上の交叉方法により各子個体のｘ2座標およびｙ2座標をそれぞれ算出する。その後、各子個体のｘ2座標およびｙ2座標を逆正接関数により各子個体の決定変数である角度θC2に変換する。
【０２３１】
決定変数である角度θ3 について（ｘ3，ｙ3）＝（ｃｏｓθ3，ｓｉｎθ3）から単位円上のｘ3座標およびｙ3座標をそれぞれ算出する。上記の単位円上の交叉方法により各子個体のｘ3座標およびｙ3座標をそれぞれ算出する。その後、各子個体のｘ3座標およびｙ3座標を逆正接関数により各子個体の決定変数である角度θC3に変換する。
【０２３２】
（３）他の実施の形態
（ａ）定義域の変換
１周期を表す定義域が［−π，π］でない次式の周期関数ｆ（φ）に上記第１および第２の実施の形態の交叉方法を適用する場合について説明する。
【０２３３】
ｆ（φ），φ∈［φmin，φmax］
上式において、φは決定変数であり、φminは定義域の最小値を示し、φmaxは定義域の最大値を示す。以下に、定義域［φmin，φmax］を定義域［−π，π］に変換する方法について説明する。
【０２３４】
図１４ａおよび図１４ｂは定義域の変換方法を説明するための模式図である。図１４ａの横軸は決定変数φであり、縦軸は周期関数ｆ（φ）の値である。図１４ｂの横軸は決定変数θであり、縦軸は周期関数ｆ（θ）の値である。
【０２３５】
個体選択部５は、図１４ａの定義域［φmin，φmax］を有する周期関数ｆ（θ）を定義域の大きさが２πとなるように、決定変数φの縮尺を調整するとともに、調整後の周期関数の定義域の中心が０となるように周期関数を横軸に沿って平行移動する。図１４ｂに示すように、縮尺の調整および平行移動後の決定変数θとする。それにより、定義域が［−π，π］である周期関数ｆ（θ）が得られる。このようにして、決定変数φから決定変数θへの変換を行う。
【０２３６】
その後、周期関数用の交叉を行い、交叉後に決定変数θから決定変数φへの逆変換を行う。
【０２３７】
（ｂ）エンジンシミュレータへの適応例
図１５は最適化装置をエンジンシミュレータに適用した例を示すブロック図である。
【０２３８】
図１５の最適化対象８ａはエンジンシミュレータである。エンジンシミュレータは、例えばパーソナルコンピュータからなる。この最適化対象８ａは、最適化装置１から与えられる決定変数ベクトルに基づいてエンジンの動作のシミュレーションを行い、シミュレーション結果を状態量として最適化装置１に出力する。
【０２３９】
決定変数として、例えば、燃料噴射時期、点火時期、吸気バルブタイミングおよび排気バルブタイミングが設定される。また、適応度関数としては、例えば、エンジンの排出ガスに含まれるＨＣ濃度およびＮＯｘ濃度が設定される。燃料噴射時期に対するＨＣ濃度およびＮＯｘ濃度は周期関数となる。
【０２４０】
本実施の形態では、排出ガスに含まれるＨＣ濃度およびＮＯｘ濃度のシミュレーション結果が最適化対象８ａから排出ガスデータとして出力される。
【０２４１】
図１５の最適化装置１によれば、適応度関数として周期関数を設定することにより、燃料噴射時期の最適化を効率的に行うことができる。
【０２４２】
（ｃ）ロボット評価装置への適応例
図１６は最適化装置をロボット評価装置に適用した例を示すブロック図である。
【０２４３】
図１６の最適化対象８ｂはロボット評価装置である。ロボット評価装置は、ＥＣＵ９１およびロボット９２を備える。
【０２４４】
ロボット９１は、例えば、２次元平面において関節数が４以上の冗長なアームを有する。また、ロボット９１は、３次元空間において関節数が７以上の冗長なアームを有してもよい。
【０２４５】
ロボット９１のアームの手先位置が定まったときに、各関節の角度は一意に決めることができない。したがって、目標関節角度の最適化が必要となる。ロボット９１のアームのリンク機構が１回転できる場合には、目標関節角度の最適化は、周期関数の最適化問題として考えることができる。
【０２４６】
決定変数ベクトルとしては、例えは、ロボット９１のリンク機構の目標関節角度が設定される。適応度関数としては、例えば、姿勢維持のための消費電力、開始姿勢から終了姿勢までの消費電力の積分値またはロボット９１のアームの移動経路に障害物が存在する場合の接触回数が設定される。
【０２４７】
図１６の最適化対象８ｂのＥＣＵ９１は、最適化装置１から個体の決定変数ベクトルとして目標関節角度を受け、ロボット９２のリンク機構を制御する。目標関節角度を決定変数ベクトルとする消費電力は周期関数となる。ロボット９２は、例えば特定のアーム先端位置に対する消費電力データを状態量として最適化装置１に出力する。
【０２４８】
図１６の最適化装置１によれば、適応度関数として周期関数を設定することにより、ロボット９２のリンク機構の目標関節角度の最適化を効率的に行うことができる。
【０２４９】
（ｄ）ロボットシミュレータへの適応例
図１７は最適化装置をロボットシミュレータに適用した例を示すブロック図である。
【０２５０】
図１７の最適化対象８ｃはロボットシミュレータである。ロボットシミュレータは、例えばパーソナルコンピュータからなる。この最適化対象８ｃは、最適化装置１から与えられる決定変数ベクトルに基づいてロボットの動作のシミュレーションを行い、シミュレーション結果を状態量として最適化装置１に出力する。
【０２５１】
決定変数ベクトルとしては、例えは、ロボットのリンク機構の目標関節角度が設定される。適応度関数としては、例えば、姿勢維持のための消費電力、開始姿勢から終了姿勢までの消費電力の積分値またはロボットのアームの移動経路に障害物が存在する場合の接触回数が設定される。
【０２５２】
本実施の形態では、特定のアーム先端位置に対する消費電力のシミュレーション結果が最適化対象８ｃから消費電力データとして出力される。
【０２５３】
図１７の最適化装置１によれば、適応度関数として周期関数を設定することにより、ロボットのリンク機構の目標関節角度の最適化を効率的に行うことができる。
【０２５４】
（ｅ）ロボットシミュレータへの適応例
図１８は最適化装置をロボットシミュレータに適用した例を示すブロック図である。
【０２５５】
図１８の最適化対象８ｄはロボットシミュレータである。ロボットシミュレータは、例えばパーソナルコンピュータからなる。この最適化対象８ｄは、最適化装置１から与えられる決定変数ベクトルに基づいてロボットの動作のシミュレーションを行い、シミュレーション結果を状態量として最適化装置１に出力する。
【０２５６】
二足歩行ロボットが歩行と同じ周期でアームを振る動作をシミュレートする。遊脚が着地した瞬間の時刻を０とし、反対の遊脚が着地した瞬間の時刻をＴ１とした場合にアームを振り出すタイミングの最適化は、周期Ｔ１の周期関数の最適化問題として考えることができる。
【０２５７】
また、決定変数ベクトルにアームの振りの速度を加えることにより、歩行の安定化指標を最大化するアームの振りのタイミングおよび歩行の効率を向上させるアームの振りのタイミングを最適化することができる。
【０２５８】
本実施の形態では、決定変数ベクトルとしてアームを振り出すタイミングおよび速度が最適化対象８ｄに入力され、歩行の安定化指標および歩行の効率のシミュレーション結果が最適化対象８ｄから安定化指標データおよび効率データとして出力される。
【０２５９】
図１８の最適化装置１によれば、適応度関数として周期関数を設定することにより、アームの振りのタイミングの最適化を効率的に行うことができる。
【０２６０】
（ｆ）蛋白質シミュレータへの適応例
図１９は最適化装置を蛋白質シミュレータに適用した例を示すブロック図である。
【０２６１】
図１９の最適化対象８ｅは蛋白質シミュレータである。蛋白質シミュレータは、例えばパーソナルコンピュータからなる。この最適化対象８ｅは、最適化装置１から与えられる決定変数ベクトルに基づいて蛋白質の構造のシミュレーションを行い、シミュレーション結果を状態量として最適化装置１に出力する。
【０２６２】
本実施の形態では、決定変数ベクトルとして蛋白質の二面角が最適化対象８ｅに入力され、エネルギーのシミュレーション結果が最適化対象８ｅからエネルギーデータとして出力される。
【０２６３】
図１９の最適化装置１によれば、適応度関数として周期関数を設定することにより、蛋白質の二面角の最適化を効率的に行うことができる。
【０２６４】
（ｇ）交通シミュレータへの適応例
図２０は最適化装置を交通シミュレータに適用した例を示すブロック図である。図２１は交通信号の広域制御を説明するための模式図である。
【０２６５】
図２０の最適化対象８ｆは交通シミュレータである。交通シミュレータは、例えばパーソナルコンピュータからなる。この最適化対象８ｆは、最適化装置１から与えられる決定変数ベクトルに基づいて交通信号の広域制御のシミュレーションを行い、シミュレーション結果を状態量として最適化装置１に出力する。
【０２６６】
交通信号の広域制御では、ある道路に設置された信号の点灯タイミングにより交通流が制御される。時々刻々と変化する交通量に対して信号の点灯タイミングを最適化することにより渋滞を最小限にすることができる。
【０２６７】
図２１に示す道路ＲＴでは、交通流は信号Ａ，Ｂの点灯タイミングにより制御されると考えられる。このとき、道路ＲＴを通過した車の台数または平均速度を最大にする信号Ｂの点灯タイミングを最適化することにより交通流を最適に制御することができる。
【０２６８】
信号Ａ，Ｂの点灯色は青、黄および赤の順に変化し、赤から再び青に戻る。このとき、信号Ａ，Ｂの１点灯サイクルに要する時間をｔ１とする。信号Ａの青の点灯開始タイミングを時刻０としたときに、信号Ｂの青の点灯開始タイミングを区間０からｔ１の定義域内で変更する。また、信号Ｂの青の点灯開始タイミングを時刻０にすることと、信号Ｂの青の点灯開始タイミングを時刻ｔ１にすることとは全く同じである。したがって、上記の交通流の制御は、信号Ｂの青の点灯開始タイミングを決定変数ベクトルとする周期関数の最適化問題と考えることができる。
【０２６９】
さらに、上り車線と下り車線とで交通量が異なる場合に、両方の車線の信号の点灯タイミングを最適化することは多目的の周期関数の最適化問題として考えることもできる。
【０２７０】
本実施の形態では、決定変数ベクトルとして信号Ｂの点灯開始のタイミングが最適化対象８ｅに入力され、交通量のシミュレーション結果が最適化対象８ｆから交通量データとして出力される。
【０２７１】
図２０の最適化装置１によれば、適応度関数として周期関数を設定することにより、信号の点灯タイミングの最適化を効率的に行うことができる。
【０２７２】
（ｈ）画像処理装置への適応例
図２２は最適化装置を画像処理装置に適用した例を示すブロック図である。図２３ａは２次元パターンマッチングを説明するための模式図である。図２３ｂは３次元パターンマッチングを説明するための模式図である。
【０２７３】
図２２の最適化対象８ｇは画像処理装置である。画像処理装置は、例えばパーソナルコンピュータからなる。この最適化対象８ｇは、最適化装置１から与えられる決定変数ベクトルに基づいてパターンマッチングを行い、マッチング量を状態量として最適化装置１に出力する。
【０２７４】
図２３ａにおいて、（ｘ，ｙ）は超球面上の交叉において求められる２次元単位方向ベクトルである。この２次元単位方向ベクトルがテンプレートＰＩの向きを表す。２次元パターンマッチングでは、まず、微分法等により対象画像ＰＯのエッジが抽出される。
【０２７５】
次に、決定変数ベクトルとしてテンプレートＰＩの座標、拡大率および２次元単位方向ベクトルが最適化対象８ｅに入力され、抽出された対象画像ＰＯのエッジに基づいて対象画像ＰＯとテンプレートＰＩとのマッチング量（一致の程度）が出力される。
【０２７６】
図２３ｂにおいて、（ｘ，ｙ，ｚ）は超球面上の交叉において求められる３次元単位方向ベクトルである。この３次元単位方向ベクトルがテンプレートＰｉの向きを表す。３次元パターンマッチングでは、まず、微分法等により対象画像Ｐｏのエッジが抽出される。
【０２７７】
次に、決定変数ベクトルとしてテンプレートＰｉの座標、拡大率および３次元単位方向ベクトルが最適化対象８ｅに入力され、抽出された対象画像Ｐｏのエッジに基づいて対象画像ＰｏとテンプレートＰｉとのマッチング量（一致度）が出力される。
【０２７８】
図２２の最適化装置１によれば、適応度関数として周期関数を設定することにより、パターンマッチングによる対象画像の姿勢推定を効率的に行うことができる。
【０２７９】
（ｉ）進化型アルゴリズムの他の例
上記実施の形態では、進化型アルゴリズムとして遺伝的アルゴリズム（ＧＡ）を用いているが、これに限定されず、遺伝的アルゴリズムの代わりに、進化戦略（ＥＳ：Evolution Strategy）等の同様のアイデアに基づく計算法を用いてもよい。
【０２８０】
なお、ＧＡ、ＥＳ等の計算法は、進化アルゴリズム（ＥＡｓ：Evolutionary Algorithms）または進化計算（Evolutionary Computation）と総称される。
【０２８１】
（ｊ）各部の実現方法
上記実施の形態では、個体生成部２、世代交代部３、個体選択部５および適応度算出部６がＣＰＵ１０１およびプログラムにより実現されるが、個体生成部２、世代交代部３、個体選択部５および適応度算出部６の一部または全てが電子回路等のハードウエアにより実現されてもよい。
【０２８２】
（４）実施例１および比較例１
第２の実施の形態における単位円上の交叉方法の有効性を確認するために、周期テスト関数による数値実験を行った。
【０２８３】
以下の実施例１では、第２の実施の形態に係る最適化装置１により周期テスト関数による最適化を行った。また、比較例１では、交叉オペレータを除いて第２の実施の形態に係る最適化装置と同様の最適化装置により周期テスト関数による最適化を行った。実施例１では、交叉オペレータとして単位円上の交叉方法（ＵＮＤＸ−Ｐ）を用いた。比較例１では、交叉オペレータとしてＵＮＤＸを用い、個体が定義域を外れた場合に個体を生成しなおす方法を採用した。まず、周期テスト関数および評価方法について説明する。
【０２８４】
実施例１および比較例１では、３種類の周期テスト関数ＴＦ−１、ＴＦ−２およびFletcher and Powell関数（以下、ＦＰと呼ぶ。）を用いた。
【０２８５】
図２４ａは周期テスト関数ＴＦ−１の概略形状を示す図、図２４ｂは周期テスト関数ＴＦ−２の概略形状を示す図、図２４ｃは周期テスト関数ＦＰの概略形状を示す図である。図２４ａ〜図２４ｃの直交する２つの横軸は変数ｘ1，ｘ2であり、縦軸は適応度（適応度関数ｆ（ｘ）の値）である。ここで、ｘ＝（ｘ1，ｘ2）である。
【０２８６】
図２５は実施例１および比較例１で用いられた３種類の周期テスト関数の詳細を示す図である。
【０２８７】
周期テスト関数ＴＦ−１は単峰性の形状を有し、周期テスト関数ＴＦ−２は多峰性の形状を有する。周期テスト関数ＴＦ−１および周期テスト関数ＴＦ−２はそれぞれｘi ＝２Ｎ＋１，Ｎ＝０，±１，±２，…のとき最小値０をとる周期２の周期関数である。変数の定義域をｘi ∈［０＋Ｌ，２＋Ｌ］とする。
【０２８８】
周期テスト関数ＦＰは最小値０をとる最適解α＝（α1 ，α2 ，…，αn ）と精度的に区別できない複数の最適解、および多数の局所解を有する周期２πの周期関数である。ここでは、図２５に示される周期テスト関数ＦＰの定数ａ、ｂおよびαとして非特許文献２記載された値を用いた。変数の定義域をｘi ∈［−π＋Ｌπ，π＋Ｌπ］とする。
【０２８９】
ここで、Ｌは定義域のオフセットであり、オフセットＬの範囲は［０，１］である。周期テスト関数ＴＦ−１および周期テスト関数ＴＦ−２では，Ｌ＝０のときに最適解は定義域の中央に位置し、オフセットＬが１に近づくほど最適解が定義域の境界に近づくことになる。周期テスト関数ＦＰでは、最適解および局所解の位置関係は複雑に変化すると予想される。
【０２９０】
実施例１および比較例１では，周期テスト関数ＴＦ−１の次元ｎを１０および２０とし、周期テスト関数ＴＦ−２の次元ｎを４および６とし、周期テスト関数ＦＰの次元ｎを６および９とし、オフセットＬが０、０．３、０．６および０．９の場合について、各々３０回の最適化を実施し（試行回数３０）、最適解を発見した回数および収束の様子を評価する。
【０２９１】
理想的には、適応度が０になる個体が最適解であるが、ここでは、個体の適応度が１．０×１０-7未満になったときに最適解を発見したものとする。
【０２９２】
遺伝的アルゴリズムの条件としては、個体集合サイズを１００とし、生成される子個体数を５０とする。世代交代モデルとしては図５に示したＭＧＧを用い、、選択方法としてはエリート選択およびルーレットホイール選択を用いる。周期テスト関数ＴＦ−１および周期テスト関数ＴＦ−２の評価回数を５．０×１０5 回とし、周期テスト関数ＦＰの評価回数を７．５×１０5 回とする。ここで、評価回数は、（世代数×子個体の数＋初期個体集合の個体の数）で求められる。
【０２９３】
図２６は実施例１および比較例１における周期テスト関数ＴＦ−１およびＴＦ−２に関する最適解発見回数を示す図である。
【０２９４】
図２６において、４つのオフセットＬでの最適解発見回数のうち最も少ない値に下線を付している。周期テスト関数ＴＦ−１およびＴＦ−２ともに、比較例１では、オフセットＬが１に近づくにしたがって（すなわち最適解の位置が定義域の境界に近づくにしたがって）最適解発見回数が減少する。これに対して、実施例１では、オフセットＬが１に近づいても（すなわち最適解の位置が定義域の境界に近づいても）最適解発見回数が減少せず、３０回の全ての試行で最適解が発見されている。
【０２９５】
周期テスト関数ＦＰ（ｎ＝６）に関しては、比較例１では、オフセットＬが１に近づくにしたがって最適解発見回数が減少する。これに対して、実施例１では、最適解発見回数がオフセットＬに全く影響を受けず、３０回の全ての試行で最適解が発見されている。
【０２９６】
周期テスト関数ＦＰ（ｎ＝９）に関しては、比較例１では、オフセットＬにより最適解発見回数が大きく変動している。これに対して、実施例１では、最適解発見回数がオフセットＬにほとんど影響を受けず、３０回のうち約半分の試行で最適解が発見されている。
【０２９７】
これらの結果、実施例１の最適化の安定性を確認することができた。
【０２９８】
図２７ａおよび図２７ｂはそれぞれ実施例１および比較例１における周期テスト関数ＴＦ−１の収束の様子を示す図である。図２７ａおよび図２７ｂは、次元ｎが２０の場合の結果を示す。図２８ａおよび図２８ｂはそれぞれ実施例１および比較例１における周期テスト関数ＴＦ−２の収束の様子を示す図である。図２８ａおよび図２８ｂは、次元ｎが６の場合の結果を示す。図２９ａおよび図２９ｂはそれぞれ実施例１および比較例１における周期テスト関数ＦＰの収束の様子を示す図である。図２９ａおよび図２９ｂは、次元ｎが９の場合の結果を示す。
【０２９９】
図２７ａ〜図２９ｂの横軸は評価回数を示し、縦軸は適応度を示す。適応度は最適解が発見された試行における適応度の平均を表している。実線はオフセットＬが０．０、点線はオフセットＬが０．３、一点鎖線はオフセットＬが０．６、破線はオフセットＬが０．９の場合を示す。
【０３００】
図２７ｂおよび図２８ｂに示すように、周期テスト関数ＴＦ−１およびＴＦ−２に関しては、比較例１では、オフセットＬが１に近づくにしたがって生成される個体の適応度が最適解（１．０×１０-7未満）に収束する速度が遅くなっていく。これに対して、図２７ａおよび図２８ａに示すように、実施例１では、周期テスト関数ＴＦ−１およびＴＦ−２のオフセットＬ（すなわち定義域）によらず生成される個体の適応度が同じ速度で最適解（１．０×１０-7未満）に収束している。
【０３０１】
周期テスト関数ＦＰに関しては、比較例１では、図２９ｂに示すように、試行ごとに得られる最適解の違いにより収束の速度が大きくばらつく。これに対して、実施例１では、図２９ａに示すように、評価回数２．０×１０5 回付近まではオフセットＬ（すなわち定義域）によらず生成される個体の適応度が同じ速度で収束している。それにより、生成される個体の適応度がいずれかの最適解の適応度近傍に収束するまでは安定した探索が行われていると考えられる。
【０３０２】
図３０は実施例１および比較例１における周期テスト関数ＦＰ（ｎ＝６）に関する代表的な解の位置および発見回数を示す図である。図３１は実施例１および比較例１における周期テスト関数ＦＰ（ｎ＝９）に関する代表的な解の位置および発見回数を示す図である。
【０３０３】
周期テスト関数ＦＰの最適化では、ｎ＝６のとき２個の最適解および３個の局所解が３０×８回の試行で得られた。また、ｎ＝９のとき８個の最適解および１８個の局所解が３０×８回の試行で得られた。
【０３０４】
図３０には、ｎ＝６の場合の２個の最適解Ｏｐｔ１，Ｏｐｔ２および１個の局所解Ｌｏｃ１が代表的に示される。図３１には、ｎ＝９の場合の８個の最適解Ｏｐｔ１〜Ｏｐｔ８および３個の局所解Ｌｏｃ１〜Ｌｏｃ３が代表的に示される。
【０３０５】
同じ解でも、オフセットＬ（定義域）により位置が異なるが、実質的に位置が等しい解は同じ解とみなしている。各オフセットＬで最も多く生成された解の発見回数に下線を付している。
【０３０６】
図３０および図３１に示すように、実施例１では、オフセットＬ（定義域）によらず発見される解の位置が安定している。これに対して、比較例１では、最適解の発見回数はオフセットＬ（定義域）に大きく依存し、あるオフセットＬ（定義域）では実施例１に比べて高い率で最適解が発見されるが、他のオフセットＬ（定義域）では実施例１に比べて低い率で最適解が発見される。これは、サンプリングバイアスにより定義域の中心付近にある最適解が得られやすくなるためと考えられる。
【０３０７】
ｎ＝９およびＬ＝０．６のとき、局所解Ｌｏｃ２は、定義域の下限（−π＋０．６π＝−１．２５６６３７）と等しい要素（ｘ3 ＝−１．２５６６３７）を有する。最適解Ｏｐｔ２は自明な最適解αであり、要素α3 ＝−１．２８３４１０＜ｘ3 を有する。それにより、局所解Ｌｏｃ２は、最適解Ｏｐｔ２近傍の強力な局所解となっている。したがって、局所解Ｌｏｃ２は位相の切断により発生した局所解であると考えられる。同様に、ｎ＝６の場合の３個の局所解のうちの２個の局所解およびｎ＝９の場合の１８個の局所解のうちの１３個の局所解は、定義域の境界に等しい要素を有し、位相の切断により発生したものである。
【０３０８】
以上より、周期関数における決定変数ベクトルの最適化に従来の交叉方法を用いると、定義域の設定により最適解および局所解の位置関係が複雑に変化する。また、位相の切断に起因する新たな局所解を多数生成することになる。その結果、定義域の設定が最適化の難易度に大きな影響を与えることがわかる。
【０３０９】
これに対して、周期関数における決定変数ベクトルの最適化に周期関数用の交叉方法を用いると、最適解および局所解の位置関係が定義域の設定により影響を受けない。また、位相の切断による新たな局所解を生成することもない。したがって、周期関数用の交叉方法は周期関数における決定変数ベクトルの最適化に有効であることがわかる。
【０３１０】
（５）実施例２
実施例２では、第２の実施の形態に係る最適化装置１を用いて多目的遺伝的アルゴリズムにより燃料噴射時期の最適化を行った。
【０３１１】
決定変数としては、点火時期、燃料噴射時期、吸気バルブタイミングおよび排気バルブタイミングを設定し、適応度関数としてＮＯｘ濃度およびＨＣ濃度を設定する。すなわち、実施例２の最適化問題は２目的４変数の多目的最適化問題である。ＨＣ濃度とＮＯｘ濃度とはトレードオフの関係を有する。すなわち、ＨＣ濃度を低くするとＮＯｘ 濃度が高くなり、ＮＯｘ 濃度を低くするとＨＣ濃度が高くなる。このような多目的最適化問題は、一般的に単一の最適解を持たず、パレート最適解と呼ばれる概念で定義される最適解集合を持つ。
【０３１２】
燃料噴射時期は、クランクシャフトの回転角度に関してどのタイミングで燃料噴射を行うかを決定するパラメータである。クランクシャフトの回転角度は０〜７２０°の範囲で定義する。このとき、燃料噴射時期が排出ガスに与える影響は、クランクシャフトの回転角度が０°のときと回転角度が７２０°のときとで等しい。したがって、燃料噴射時期を決定変数ベクトルとするＨＣ濃度およびＮＯｘ濃度は、周期７２０°の周期関数となることがわかる。
【０３１３】
本実施例２では、燃料噴射時期の最適化にのみ第２の実施の形態における単位円上の交叉方法（ＵＮＤＸ−Ｐ）を適用する。
【０３１４】
図３２および図３３は図３の最適化装置１により得られた最適個体を示す図である。図３２の横軸は点火時期を示し、縦軸は燃料噴射時期を示す。図３３の横軸は燃料噴射時期を示し、縦軸は吸気バルブタイミングを示す。
【０３１５】
本実施例２では多目的最適化を行っているため、複数のパレート最適個体が得られる。図３２および図３３において、燃料噴射時期が０であることと燃料噴射時期が１であることとは等しい。
【０３１６】
図３２および図３３に示すように、燃料噴射時期は０と１とをまたぐように分布している様子が見られる。それにより、定義域の境界近傍の最適個体を発見できることがわかる。
【０３１７】
図３４は実施例２において得られたＨＣ濃度およびＮＯｘ 濃度の関係を示す図である。図３４に示されるように、トレードオフの関係を有するＨＣ濃度およびＮＯｘ濃度についてパレート最適個体集合が得られることがわかる。
【０３１８】
（６）請求項の構成要素と実施の形態の各部との対応
上記実施の形態では、個体集合記憶部４が解候補記憶部に相当し、個体選択部５が解候補選択部に相当し、個体生成部２が解候補生成部に相当し、適応度算出部６が評価値演算部に相当し、世代交代部３が解候補集合更新部に相当する。
【０３１９】
また、決定変数が最適化すべき変数に相当し、個体が解候補に相当し、所定数の親個体が所定数の解候補に相当し、複数の子個体が新たな解候補に相当し、適応度が評価値に相当する。
【０３２０】
特に、第１の実施の形態において、ｎ次元実数空間Ｒn または２次元実数空間（２次元実数平面）Ｒ2 がＮ次元変数空間に相当し、（ｎ−１）次元単位球面Ｓn-1 、超球面または単位円が（ｍ−１）次元単位球面に相当し、ｎ個の決定変数ｘ１，ｘ２，…，ｘｎがＮ個の変数およびｍ個の変数に相当する。すなわち、第１の実施の形態では、Ｎ＝ｍ＝ｎである。
【０３２１】
また、第２の実施の形態において、単位円ＵＣが１次元単位球面に相当し、２次元実数空間（２次元実数平面）Ｒ２が２次元平面に相当し、θ1，θ2，…，θnがｍ個の変数の組に相当する。
【０３２２】
また、燃料噴射時期または燃料噴射パターンがクランク回転角度に基づくパラメータに相当し、対象画像ＰＯ，Ｐｏが対象画像に相当し、テンプレートＰＩ，Ｐｉが参照画像に相当し、マッチング量が誤差に相当する。
【産業上の利用可能性】
【０３２３】
本発明は、周期関数における変数の最適化等に利用することができる。
【図面の簡単な説明】
【０３２４】
【図１】本発明の第１の実施の形態に係る最適化装置の機能的な構成を示すブロック図である。
【図２】図１の最適化装置のハードウエア構成を示すブロック図である。
【図３】最適化装置を燃料噴射パターンの最適化に適用する方法を説明するための図である。
【図４】図１の最適化装置の全体処理を示すフローチャートである。
【図５】図１の最適化装置による最適化処理の一例を示す模式図である。
【図６ａ】超球面上の交叉方法を説明するための模式図である。
【図６ｂ】超球面上の交叉方法を説明するための模式図である。
【図６ｃ】超球面上の交叉方法を説明するための模式図である。
【図７】超球面上の交叉処理を示すフローチャートである。
【図８ａ】（ｎ−１）次元単位球面上の初期個体集合の生成処理の一例を示す図である。
【図８ｂ】（ｎ−１）次元単位球面上の初期個体集合の生成処理の一例を示す図である。
【図９】本発明の第２の実施の形態に係る最適化装置の機能的な構成を示すブロック図である。
【図１０】最適化対象の構成の一例を示すブロック図である。
【図１１ａ】単位円上の交叉方法を説明するための模式図である。
【図１１ｂ】単位円上の交叉方法を説明するための模式図である。
【図１１ｃ】単位円上の交叉方法を説明するための模式図である。
【図１２】単位円上の交叉処理を示すフローチャートである。
【図１３】単位円上の交叉方法をｎ次元角度ベクトルからなる決定変数ベクトルへ拡張する方法を示す模式図である。
【図１４ａ】定義域の調整方法を説明するための模式図である。
【図１４ｂ】定義域の調整方法を説明するための模式図である。
【図１５】最適化装置をエンジンシミュレータに適用した例を示すブロック図である。
【図１６】最適化装置をロボット評価装置に適用した例を示すブロック図である。
【図１７】最適化装置をロボットシミュレータに適用した例を示すブロック図である。
【図１８】最適化装置をロボットシミュレータに適用した例を示すブロック図である。
【図１９】最適化装置を蛋白質シミュレータに適用した例を示すブロック図である。
【図２０】最適化装置を交通シミュレータに適用した例を示すブロック図である。
【図２１】交通信号の広域制御を説明するための模式図である。
【図２２】最適化装置を画像処理装置に適用した例を示すブロック図である。
【図２３ａ】２次元パターンマッチングを説明するための模式図である。
【図２３ｂ】３次元パターンマッチングを説明するための模式図である。
【図２４ａ】周期テスト関数ＴＦ−１の概略形状を示す図である。
【図２４ｂ】周期テスト関数ＴＦ−２の概略形状を示す図である。
【図２４ｃ】周期テスト関数ＦＰの概略形状を示す図である。
【図２５】実施例１および比較例１で用いられた３種類の周期テスト関数の詳細を示す図である。
【図２６】実施例１および比較例１における周期テスト関数ＴＦ−１、ＴＦ−２およびＦＰに関する最適個体発見回数を示す図である。
【図２７ａ】実施例１および比較例１における周期テスト関数ＴＦ−１の収束の様子を示す図である。
【図２７ｂ】実施例１および比較例１における周期テスト関数ＴＦ−１の収束の様子を示す図である。
【図２８ａ】実施例１および比較例１における周期テスト関数ＴＦ−２の収束の様子を示す図である。
【図２８ｂ】実施例１および比較例１における周期テスト関数ＴＦ−２の収束の様子を示す図である。
【図２９ａ】実施例１および比較例１における周期テスト関数ＦＰの収束の様子を示す図である。
【図２９ｂ】実施例１および比較例１における周期テスト関数ＦＰの収束の様子を示す図である。
【図３０】実施例１および比較例１における周期テスト関数ＦＰ（ｎ＝６）に関する代表的な個体の位置および発見回数を示す図である。
【図３１】実施例１および比較例１における周期テスト関数ＦＰ（ｎ＝９）に関する代表的な個体の位置および発見回数を示す図である。
【図３２】図３の最適化装置により得られた最適個体を示す図である。
【図３３】図３の最適化装置により得られた最適個体を示す図である。
【図３４】実施例２において得られたＨＣ濃度およびＮＯx 濃度の関係を示す図である。
【図３５】周期関数の定義域の設定範囲の一例を示す模式図である。
【図３６】周期関数の定義域の設定範囲の他の例を示す模式図である。
【図３７】実数値の交叉による子個体の生起確率密度分布を示す模式図である。
【図３８】進化的停滞を説明するための模式図である。
【図３９】境界法を説明するための模式図である。
【符号の説明】
【０３２５】
１  最適化装置
２  個体生成部
３  世代交代部
４  個体集合記憶部
５  個体選択部
６  適応度算出部
７  入出力インタフェース
８  最適化対象
１０  使用者
２１  交叉部
２２  正規化演算部
２３  三角関数演算部
２４  逆正接関数演算部
８１  ＥＣＵ（エンジン制御ユニット）
８２  エンジン
８３  排気ガス分析計
８４  吸気ポート
８５  排気ポート
８６  燃料噴射装置
８７  吸気バルブ
８８  排気バルブ
８９  シリンダヘッド
９０  点火プラグ
１０１  ＣＰＵ（中央演算処理装置）
１０２  ＲＯＭ（リードオンリメモリ）
１０３  ＲＡＭ（ランダムアクセスメモリ）
１０４  入力装置
１０５  表示装置
１０６  外部記憶装置
１０７  記録媒体駆動装置
１０９  記録媒体
【図１】
2006294002.tif 000009
【図２】
2006294002.tif 000010
【図３】
2006294002.tif 000011
【図４】
2006294002.tif 000012
【図５】
2006294002.tif 000013
【図６ａ】
2006294002.tif 000014
【図６ｂ】
2006294002.tif 000015
【図６ｃ】
2006294002.tif 000016
【図７】
2006294002.tif 000017
【図８ａ】
2006294002.tif 000018
【図８ｂ】
2006294002.tif 000019
【図９】
2006294002.tif 000020
【図１０】
2006294002.tif 000021
【図１１ａ】
2006294002.tif 000022
【図１１ｂ】
2006294002.tif 000023
【図１１ｃ】
2006294002.tif 000024
【図１２】
2006294002.tif 000025
【図１３】
2006294002.tif 000026
【図１４ａ】
2006294002.tif 000027
【図１４ｂ】
2006294002.tif 000028
【図１５】
2006294002.tif 000029
【図１６】
2006294002.tif 000030
【図１７】
2006294002.tif 000031
【図１８】
2006294002.tif 000032
【図１９】
2006294002.tif 000033
【図２０】
2006294002.tif 000034
【図２１】
2006294002.tif 000035
【図２２】
2006294002.tif 000036
【図２３ａ】
2006294002.tif 000037
【図２３ｂ】
2006294002.tif 000038
【図２４ａ】
2006294002.tif 000039
【図２４ｂ】
2006294002.tif 000040
【図２４ｃ】
2006294002.tif 000041
【図２５】
2006294002.tif 000042
【図２６】
2006294002.tif 000043
【図２７ａ】
2006294002.tif 000044
【図２７ｂ】
2006294002.tif 000045
【図２８ａ】
2006294002.tif 000046
【図２８ｂ】
2006294002.tif 000047
【図２９ａ】
2006294002.tif 000048
【図２９ｂ】
2006294002.tif 000049
【図３０】
2006294002.tif 000050
【図３１】
2006294002.tif 000051
【図３２】
2006294002.tif 000052
【図３３】
2006294002.tif 000053
【図３４】
2006294002.tif 000054
【図３５】
2006294002.tif 000055
【図３６】
2006294002.tif 000056
【図３７】
2006294002.tif 000057
【図３８】
2006294002.tif 000058
【図３９】
2006294002.tif 000059