(57)【要約】【課題】多次元の探索空間内におけるパラメータの最適値の探索においても、少ない評価回数で最適解を得ることが可能なパラメータ最適化装置を提供する。【解決手段】パラメータ最適化装置１は、探索空間Ｓ内に最適値算出対象のパラメータを要素とする複数の個体を生成させる初期化手段２と、試行により個体の評価値Ｑを算出する評価値算出手段３と、複数の個体の中から評価値が悪い個体を選択する単点選択手段６ａ、６ｂと、単点選択手段により選択された個体に含まれるパラメータを評価値が良い個体に含まれるパラメータに所定の割合αで近づける個体変位手段７ａ、７ｂと、終了判定条件を満たしたと判定すると良い評価値を有する個体に含まれるパラメータを最適値として出力する終了判定手段４とを備え、評価値算出手段３は、個体変位手段７ａ、７ｂにより変位された個体が送られてきた場合にはその個体についてのみ評価値を算出する。【選択図】図１
2007233676.tif 000002
【特許請求の範囲】
【請求項１】
システムの動作に係るパラメータの最適値を算出するパラメータ最適化装置であって、
最適値算出の対象とされるパラメータの上限値および下限値を境界とする探索空間内に前記パラメータを要素とする複数の個体を生成させる初期化手段と、
試行により前記個体の評価値を算出する評価値算出手段と、
前記複数の個体の中から評価値の悪い個体を選択する単点選択手段と、
前記単点選択手段により選択された前記個体に含まれるパラメータを良い評価値を有する個体に含まれるパラメータに所定の割合で近づけて、変位された前記個体を前記評価値算出手段に送る個体変位手段と、
設定された終了判定条件を満たしたか否かを判定し、前記終了判定条件を満たしたと判定するとその時点で良い評価値を有する個体に含まれるパラメータを前記パラメータの最適値として出力する終了判定手段と
を備え、
前記評価値算出手段は、前記個体変位手段により変位された個体が送られてきた場合にはその個体についてのみ評価値を算出することを特徴とするパラメータ最適化装置。
【請求項２】
前記初期化手段は、前記最適値算出の対象とされるパラメータの数をｎとした場合に前記複数の個体を２ｎ個発生させ、かつ、前記パラメータの上限値および下限値を境界とするｎ次元の探索空間の各頂点に対応するパラメータをそれぞれの個体に重複しないように割り当てることを特徴とする請求項１に記載のパラメータ最適化装置。
【請求項３】
前記初期化手段は、前記最適値算出の対象とされるパラメータの数をｎとした場合に前記複数の個体を２個以上２ｎ個未満発生させ、かつ、前記パラメータの上限値および下限値を境界とするｎ次元の探索空間の各頂点のいずれかに対応するパラメータをそれぞれ個体に重複しないように割り当てることを特徴とする請求項１に記載のパラメータ最適化装置。
【請求項４】
前記単点選択手段は、各個体について、その個体と前記良い評価値を有する個体との探索空間上のユークリッド距離でその個体の評価値を重み付けして変位基準値を算出し、その変位基準値が悪い個体を選択することを特徴とする請求項１から請求項３のいずれか一項に記載のパラメータ最適化装置。
【請求項５】
前記単点選択手段と前記個体変位手段との処理内容をそれぞれ所定の割合で切り替える切替手段を備え、
前記単点選択手段は、前記切替手段の切り替えに応じて、前記複数の個体の中から前記良い評価値を有する個体以外の個体の中から任意に１個体を選択し、
前記個体変位手段は、前記単点選択手段により選択された個体を、探索空間内の前記良い評価値を有する個体から所定のユークリッド距離内の任意に選択された位置に変位させて前記評価値算出手段に送ることを特徴とする請求項１から請求項４のいずれか一項に記載のパラメータ最適化装置。
【請求項６】
システムの動作に係るパラメータの最適値を算出するパラメータ最適化装置であって、
最適値算出の対象とされるパラメータの上限値および下限値を境界とする探索空間内に前記パラメータを要素とする複数の個体を生成させる初期化手段と、
試行により前記個体の評価値を算出する評価値算出手段と、
前記複数の個体の中から個体を選択する単点選択手段と、
前記単点選択手段により選択された前記個体を変位させると共に、前記評価値算出手段に送る個体変位手段と、
設定された終了判定条件を満たしたか否かを判定し、前記終了判定条件を満たしたと判定するとその時点で良い評価値を有する個体に含まれるパラメータを前記パラメータの最適値として出力する終了判定手段と
を備え、
前記単点選択手段は、悪い評価値を有する個体を選択し、または良い評価値を有する個体以外の個体の中から任意に１個体を選択し、
前記個体変異手段は、前記単点選択手段により選択された前記個体に含まれるパラメータを良い評価値を有する個体に含まれるパラメータに所定の割合で近づけることで変位させ、または前記単点選択手段により選択された個体を、探索空間内の前記良い評価値を有する個体から所定のユークリッド距離内の任意に選択された位置に変位させることを特徴とするパラメータ最適化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パラメータ最適化装置に係り、特に、試行を繰り返してパラメータの最適解を得るパラメータ最適化装置に関する。
【背景技術】
【０００２】
近年、システムの最適制御等の分野でシステムの動作に係るパラメータの最適値を算出する手法として遺伝的アルゴリズムが注目されている。最も基本的な遺伝的アルゴリズムでは、初期化過程で複数の個体を生成させた後、各個体についての評価値の算出過程やルーレット選択等の選択過程、個体同士の交叉過程、各個体についての突然変異過程が世代ごとに繰り返される。そして、設定された評価値以上の評価値を有する個体が現れた等の終了判定条件が満たされた時点で前記進化過程を終了し、その時点で最良の評価値を有する個体に要素として含まれるパラメータをパラメータの最適値として出力する。
【０００３】
しかし、実システムのオンライン最適化を行う場合、時間的な制限から、最適値を算出するために必要な評価値の算出回数すなわち評価回数が限定されてしまう。そのため、評価値が未だ十分に良くなっていない段階でパラメータの最適値を出力しなければならず、パラメータの最適化が十分に行われないという問題がある。
【０００４】
このような問題を解決する手法として、特許文献１では遺伝的アルゴリズムによる探索と直交計画法に基づく要因分析とを併用して探索範囲を狭め、また、特許文献２では統計モデルを利用して探索範囲を狭めて、より少ない試行回数や評価回数でパラメータの最適化を行うパラメータ最適化装置が提案されている。
【特許文献１】特開平１０−１４９３４５号公報
【特許文献２】特開２００４−３３４７１４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１に記載のパラメータ最適化装置では、直交計画法による同一の因子数の単因子要因分析を複数回繰り返して行うので試行回数が増加するため、必ずしもより少ない試行回数でパラメータの最適値が求められるとは限らない。
【０００６】
また、特許文献２に記載のパラメータ最適化装置では、探索範囲を変更するたびに初期個体が生成され遺伝的アルゴリズムによる進化過程が始まるため、評価回数を十分に効率良く低減させることができるとは必ずしも言い切れない。
【０００７】
さらに、従来のパラメータ最適化に用いられる遺伝的アルゴリズムでは、生成させる個体数は、通常、最適化を行う作業者が経験的に或いは直観的に比較的大きい数に決定している。そのため、必要以上に多くの試行回数や評価回数を要し、処理時間の短縮を妨げていた。
【０００８】
本発明は、前記事情に鑑みてなされたものであり、多次元の探索空間内におけるパラメータの最適値の探索においても、少ない評価回数で最適解を得ることが可能なパラメータ最適化装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
前記の問題を解決するために、第１の発明は、
システムの動作に係るパラメータの最適値を算出するパラメータ最適化装置であって、
最適値算出の対象とされるパラメータの上限値および下限値を境界とする探索空間内に前記パラメータを要素とする複数の個体を生成させる初期化手段と、
試行により前記個体の評価値を算出する評価値算出手段と、
前記複数の個体の中から評価値の悪い個体を選択する単点選択手段と、
前記単点選択手段により選択された前記個体に含まれるパラメータを良い評価値を有する個体に含まれるパラメータに所定の割合で近づけて、変位された前記個体を前記評価値算出手段に送る個体変位手段と、
設定された終了判定条件を満たしたか否かを判定し、前記終了判定条件を満たしたと判定するとその時点で良い評価値を有する個体に含まれるパラメータを前記パラメータの最適値として出力する終了判定手段と
を備え、
前記評価値算出手段は、前記個体変位手段により変位された個体が送られてきた場合にはその個体についてのみ評価値を算出することを特徴とする。
【００１０】
第２の発明は、第１の発明のパラメータ最適化装置において、前記初期化手段は、前記最適値算出の対象とされるパラメータの数をｎとした場合に前記複数の個体を２ｎ個発生させ、かつ、前記パラメータの上限値および下限値を境界とするｎ次元の探索空間の各頂点に対応するパラメータをそれぞれの個体に重複しないように割り当てることを特徴とする。
【００１１】
第３の発明は、第１の発明のパラメータ最適化装置において、前記初期化手段は、前記最適値算出の対象とされるパラメータの数をｎとした場合に前記複数の個体を２個以上２ｎ個未満発生させ、かつ、前記パラメータの上限値および下限値を境界とするｎ次元の探索空間の各頂点のいずれかに対応するパラメータをそれぞれ個体に重複しないように割り当てることを特徴とする。
【００１２】
第４の発明は、第１から第３のいずれかの発明のパラメータ最適化装置において、前記単点選択手段は、各個体について、その個体と前記良い評価値を有する個体との探索空間上のユークリッド距離でその個体の評価値を重み付けして変位基準値を算出し、その変位基準値が悪い個体を選択することを特徴とする。
【００１３】
第５の発明は、第１から第４のいずれかの発明のパラメータ最適化装置において、
前記単点選択手段と前記個体変位手段との処理内容をそれぞれ所定の割合で切り替える切替手段を備え、
前記単点選択手段は、前記切替手段の切り替えに応じて、前記複数の個体の中から前記良い評価値を有する個体以外の個体の中から任意に１個体を選択し、
前記個体変位手段は、前記単点選択手段により選択された個体を、探索空間内の前記良い評価値を有する個体から所定のユークリッド距離内の任意に選択された位置に変位させて前記評価値算出手段に送ることを特徴とする。
【００１４】
第６の発明は、
システムの動作に係るパラメータの最適値を算出するパラメータ最適化装置であって、
最適値算出の対象とされるパラメータの上限値および下限値を境界とする探索空間内に前記パラメータを要素とする複数の個体を生成させる初期化手段と、
試行により前記個体の評価値を算出する評価値算出手段と、
前記複数の個体の中から個体を選択する単点選択手段と、
前記単点選択手段により選択された前記個体を変位させると共に、前記評価値算出手段に送る個体変位手段と、
設定された終了判定条件を満たしたか否かを判定し、前記終了判定条件を満たしたと判定するとその時点で良い評価値を有する個体に含まれるパラメータを前記パラメータの最適値として出力する終了判定手段と
を備え、
前記単点選択手段は、悪い評価値を有する個体を選択し、または良い評価値を有する個体以外の個体の中から任意に１個体を選択し、
前記個体変異手段は、前記単点選択手段により選択された前記個体に含まれるパラメータを良い評価値を有する個体に含まれるパラメータに所定の割合で近づけることで変位させ、または前記単点選択手段により選択された個体を、探索空間内の前記良い評価値を有する個体から所定のユークリッド距離内の任意に選択された位置に変位させることを特徴とするパラメータ最適化装置。
【発明の効果】
【００１５】
第１の発明によれば、最適値算出の対象とされるパラメータの上限値および下限値を境界とする探索空間内にそれらのパラメータを要素とする個体を複数生成させる。そして、それらの個体を１つずつ探索空間の内側に向かうように方向性を持たせて変位させるように挟み撃ち探索を行わせることができる。
【００１６】
従来の遺伝的アルゴリズムを用いた最適値探索では、例えば特許文献１、２に記載のパラメータ最適化装置のように探索範囲を狭める制限を課したとしても、基本的には複数の個体が一斉に探索空間内をランダムに変位し、探索空間内をくまなく探索しようとする。そのため、好適なパラメータの最適値を得る可能性が高くなるとしても、評価値のピークから遠ざかり評価値を下げるような変位を行った個体についても評価値の算出を行わなければならず、必ずしも少ない評価回数で最適解を得ることができなくなる。
【００１７】
しかし、第１の発明では、前記のように個体を１つずつ探索空間の内側に向かうように方向性を持たせて変位させ、最適値を囲い込むように探索領域を狭めながら効率良くパラメータの最適値の探索を行って、少ない評価回数で最適解を得ることが可能となる。その結果、実システムのオンライン最適化を行う際の時間的な制限をクリアすることができ、かつ、好適な評価値を有する個体を獲得して好適なパラメータの最適値を得ることが可能となる。
【００１８】
第２の発明によれば、パラメータの数がｎ個の場合に２ｎ個の個体を生成させ、ｎ次元の探索空間の各頂点に重複しないように配置することで、探索空間自体を探索領域とする探索領域が最も広い状態から徐々に探索領域を狭めながら最適解を囲い込むようにして探索することができる。そのため、前記第１の発明の効果に加え、パラメータの最適値を確実に得ることが可能となる。
【００１９】
また、従来の遺伝的アルゴリズムを用いる場合のように、作業者の経験や直観に依存することなく生成させる個体数を決定することが可能となるとともに、必要以上に多くの個体を生成させて評価回数が増大することが防止され、処理時間の短縮を図ることが可能となる。
【００２０】
第３の発明によれば、パラメータの数がｎ個の場合に、生成させる個体を２個以上２ｎ個未満とすることも可能である。このように構成し、各個体をｎ次元の探索空間の各頂点に重複しないように配置すれば、前記第２の発明の場合よりも、初期状態ですべての個体について行う評価回数をさらに減らすことが可能となる。
【００２１】
第４の発明によれば、例えば、最良の評価値を有する個体と他の各個体とのユークリッド距離が等しい場合には、最も悪い評価値を有する個体が最も悪い変位基準値を有する個体として選択され、最良の評価値を有する個体の方向に引き寄せられるため、その個体が速やかにより良い評価値を有するようになる可能性が高くなる。
【００２２】
また、例えば、最良の評価値を有する個体以外の各個体の評価値が等しい評価値を有する場合には、最良の評価値を有する個体から最も遠い個体が最も悪い変位基準値を有する個体として選択され、最良の評価値を有する個体の方向に引き寄せられる。評価値が単峰性関数で表される場合には、後述する図５に示すように、評価値が最も良い個体とそれから最も遠い個体との間に最適解があり、最も遠い個体を最良の評価値を有する個体の側に引き寄せることで最も遠い個体の評価値が速やかに改善する可能性が高くなる。
【００２３】
さらに、評価値が多峰性関数で表される場合には、後述する図６に示すように、最良の評価値を有する個体から最も遠い個体は、最適解ではなく局所解の近傍にいる可能性がある。しかし、最も遠い個体を最良の評価値を有する個体の側に近づけることで、前記最も遠い個体が最適解側に引き寄せられ、その個体を最適解の探索に参加させるようにすることができ、評価値が速やかに改善する可能性が高くなる。
【００２４】
このように、単点選択手段で変位基準値が最悪の個体を選択し、その個体を最良の評価値を有する個体の側に引き寄せるようにすることで、評価値を速やかに改善させる可能性を向上させることが可能となる。そのため、より少ない評価回数で最適解を得る確率を高めることが可能となり、前記各発明の効果をより効率良く発揮させることが可能となる。
【００２５】
第５の発明によれば、挟み撃ち探索では良い評価値を有する個体は、他の個体の評価値が自らの評価値以上になるまで探索空間内でその位置を変えないため、最適解の近くにいる可能性が高いにもかかわらず最適解に近づくことができないが、他の個体を用いて良い評価値を有する個体の近傍を探索することが可能となる。
【００２６】
そのため、近傍探索により良い評価値を有する個体の近傍に強制的に変位させられた個体の評価値が良い評価値を上回る可能性が生じる。このように、近傍探索を行うことで評価値を速やかに向上させる確率が高くなり、前記各発明の効果をより効果的に発揮させることが可能となる。
【００２７】
第６の発明によれば、パラメータの最適値算出のための世代交代において、挟み撃ち探索と近傍探索とを例えば所定の割合でランダムに切り替えて行うことで、前記各発明において述べた挟み撃ちの効果と近傍探索の効果をともに奏することが可能となり、前記各発明の効果をより効果的に発揮させることが可能となる。
【発明を実施するための最良の形態】
【００２８】
以下、本発明に係るパラメータ最適化装置の実施の形態について、図面を参照して説明する。
【００２９】
パラメータ最適化装置１は、図１に示すように、初期化手段２と、評価値算出手段３と、終了判定手段４と、切替手段５と、単点選択手段６ａ、６ｂと、個体変位手段７ａ、７ｂとを備えている。本実施形態では、パラメータ最適化装置１は、ＣＰＵやＲＯＭ、ＲＡＭ、入出力インターフェース等がバスに接続された汎用コンピュータで構成されている。
【００３０】
初期化手段２は、システムの動作に係るパラメータのうち最適値算出の対象としてｎ個のパラメータＰ１〜Ｐｎが設定されると、仮想的にそれらのパラメータＰ１〜Ｐｎの上限値および下限値を境界とするｎ次元の直方体状の探索空間Ｓを設定するようになっている。ここで、n次元の直方体とは、例えばｎ＝１であれば１次元の直線、ｎ＝２であれば２次元の矩形、ｎ＝３であれば３次元の直方体、ｎが４以上の場合はｎ次元のいわゆる超直方体を表す。
【００３１】
また、本実施形態では、初期化手段２は、最適値算出の対象とされるパラメータＰ１〜Ｐｎを要素とする２ｎ個の個体Ｉ１、Ｉ２、…をＲＡＭ上に生成させるようになっている。個体は、具体的には、図２に示すように、最適値算出の対象とされるｎ個のパラメータＰ１〜Ｐｎを含む数値列である。
【００３２】
初期化手段２は、個体の生成の際、それらの個体Ｉ１、Ｉ２、…をｎ次元の探索空間Ｓの各頂点に重複しないように配置するように生成するようになっている。すなわち、ｎ次元の探索空間Ｓの各頂点に対応するパラメータＰ１〜Ｐｎの上限値および下限値が、個体Ｉ１、Ｉ２、…に互いに重複しないように割り当てるようになっている。
【００３３】
ｎ＝２の場合を例に具体的に説明すると、初期化手段２は、図３に示すように、パラメータＰ１、Ｐ２の上限値Ｐ１max、Ｐ２maxおよび下限値Ｐ１min、Ｐ２minを境界とする矩形状の探索領域Ｓを設定する。そして、探索領域Ｓの４つの頂点に個体Ｉ１〜Ｉ４がそれぞれ重複しないように配置されるように、個体Ｉ１〜Ｉ４に要素として含まれる各パラメータＰ１、Ｐ２の初期値としてそれぞれ（Ｐ１max，Ｐ２max）、（Ｐ１max，Ｐ２min）、（Ｐ１min，Ｐ２max）、（Ｐ１min，Ｐ２min）を割り当てるようになっている。
【００３４】
評価値算出手段３は、初期化手段２により２ｎ個の個体が前記要領で生成されると、それらの個体に基づいて試行を行うようになっている。この場合、試行は、図１に示すように、与えられたシステムのモデルＭに各個体に含まれるパラメータＰ１〜Ｐｎをそれぞれ適用してシミュレーションを行ったり、或いは実機やシステムに各個体に含まれるパラメータＰ１〜Ｐｎを適用したりして行われる。
【００３５】
また、各個体についてシミュレーション結果Ｒや実機等による結果Ｒが得られると、評価値算出手段３は、初期化手段２によって生成されたすべての個体について評価関数Ｑ＝ｆ（Ｒ）に従って評価値Ｑを算出するようになっている。評価値Ｑの算出において教師データＤＴが必要な場合にはあらかじめ教師データＤＴが評価値算出手段３に入力される。
【００３６】
一方、評価値算出手段３は、後述する個体変位手段７ａ、７ｂから処理された個体が送られてきた場合には、その個体についてのみ試行により評価値Ｑを算出し、既に評価値Ｑが算出されている他の個体については試行を行わないようになっている。
【００３７】
終了判定手段４は、設定された終了判定条件を満たしたか否かを判定し、終了判定条件が満たされたと判定すると、その時点で最良の評価値Ｑを有する個体に含まれるパラメータＰ１〜Ｐｎをパラメータの最適値Ｐ１suit〜Ｐｎsuitとして出力するようになっている。
【００３８】
終了判定条件として設定される条件は、求められるパラメータの最適値の精度や処理時間等によって適宜設定される。例えば、
（Ａ）設定された評価値以上の評価値を有する個体が現れた、
（Ｂ）全個体の評価値の平均値が設定された閾値を超えた、
（Ｃ）世代数が設定された数に達した、
（Ｄ）処理時間が設定された時間に達した、
等の条件が設定される。
【００３９】
切替手段５は、終了判定手段４が設定された終了判定条件を満たしていないと判定した場合に、次に行われる単点選択および個体変位において、挟み撃ち探索を行うか近傍探索を行うかを設定された割合に応じてランダムに切り替えるようになっている。割合は、例えば、挟み撃ち探索７０％、近傍探索３０％のように設定される。
【００４０】
単点選択手段６ａおよび個体変位手段７ａでは、切替手段５の切り替えに応じて前記挟み撃ち探索が行われるようになっている。ここで、挟み撃ち探索とは、全個体中で最も悪い評価値Ｑを有する個体に含まれるパラメータを最も良い評価値Ｑを有する個体に含まれるパラメータに所定の割合で近づけて探索領域を狭めて最適解の探索を行うことをいう。
【００４１】
単点選択手段６ａは、図４に示すように、各個体の評価値に基づいて全個体の中から◎で表される最も良い評価値Ｑbestを有する個体Ｉbestと●で表される最も悪い評価値Ｑworstを有する個体Ｉworstとを選択するようになっている。最も悪い評価値を有する個体が複数存在する場合には、それらの個体の中からランダムに１つの個体が選択されるようになっている。最も良い評価値を有する個体が複数存在する場合も同様である。
【００４２】
個体変位手段７ａは、単点選択手段６ａで選択された個体Ｉworstに含まれるパラメータ（Ｐ１worst，Ｐ２worst）を個体Ｉbestに含まれるパラメータ（Ｐ１best，Ｐ２best）に所定の割合αで近づけて探索空間Ｓ内で変位させ、探索領域Ｓａを狭めるようになっている。
【００４３】
この場合、個体Ｉworstは座標（Ｐ１´，Ｐ２´）に変位され、座標（Ｐ１´，Ｐ２´）は、
Ｐ１´＝Ｐ１worst＋α（Ｐ１best−Ｐ１worst）    …（１）
Ｐ２´＝Ｐ２worst＋α（Ｐ２best−Ｐ２worst）    …（２）
により算出される。
【００４４】
なお、割合αは、例えば、世代を通して一定の値であってもよく、また、世代が進むに従って小さい値となるように設定されてもよい。また、図４以下では、探索が進み各個体が探索空間Ｓの内部に進入した状態が示されている。
【００４５】
ここで、単点選択手段６ａで、評価値が最も悪い個体を選択する代わりに、各個体と最も良い評価値Ｑbestを有する個体Ｉbestとの探索空間Ｓ上でのユークリッド距離Ｌを算出し、各個体の評価値Ｑを各ユークリッド距離Ｌで重み付けして算出された変位基準値ＷＱに基づいて変位基準値ＷＱが最も悪い個体を選択するように構成することも可能である。
【００４６】
この場合、例えば評価値Ｑが同一の値である場合、ユークリッド距離が大きい個体の変位基準値ＷＱが悪くなるように重み付けされる。すなわち、評価値Ｑが小さい値であるほど良い個体であることを表す場合は、変位基準値ＷＱを、例えば、
ＷＱ＝Ｑ×Ｌ    …（３）
で定義し、評価値Ｑが大きい値であるほど良い個体であることを表す場合は、変位基準値ＷＱを、例えば、
ＷＱ＝１／Ｑ×Ｌ    …（４）
で定義する。変位基準値ＷＱが前記（３）式や（４）式で定義される場合には、変位基準値ＷＱが小さい値であるほど良い個体であると評価される。
【００４７】
また、単点選択手段６ａで変位基準値ＷＱが最も悪い個体が選択される場合、個体変位手段７ａは、変位基準値ＷＱが最も悪い個体を最も良い評価値Ｑを有する個体Ｉbestに近づけるようになる。
【００４８】
例えば、図５に示すように、探索空間Ｓ内で評価値Ｑが単峰性関数で表され、評価値が最も良い個体Ｉbest以外の個体の評価値Ｑが同一の場合、個体Ｉbestからのユークリッド距離が最も遠い個体Ｉfarを個体Ｉbestに近づけると、他の個体を個体Ｉbestに近づける場合と比較して、最も大きく評価値Ｑが向上する可能性が高い。そのため、変位基準値ＷＱに基づいて変位させる個体を選択このように構成すれば、評価値Ｑが速やかに向上する可能性が高くなる。
【００４９】
また、図６に示すように、探索空間Ｓ内で評価値Ｑが多峰性関数で表され、評価値が最も良い個体Ｉbest以外の個体の評価値Ｑが同一の場合には、個体Ｉbestからのユークリッド距離が最も遠い個体Ｉfarは最適解Ａではなく局所解Ｂの近傍にいる可能性がある。その場合、個体Ｉfarを個体Ｉbestに近づけることで、個体Ｉfarが最適解Ａ側に引き寄せられ、個体Ｉfarを最適解Ａの探索に参加させることができる。そのため、変位基準値ＷＱに基づいて変位させる個体を選択このように構成すれば、やはり評価値Ｑが速やかに向上する可能性が高くなる。
【００５０】
一方、単点選択手段６ｂおよび個体変位手段７ｂでは、切替手段５の切り替えに応じて前記近傍探索が行われるようになっている。ここで、近傍探索とは、最も良い評価値Ｑを有する個体Ｉbestの近傍に最適解が存在する可能性が高いことから、個体Ｉbestの近傍については探索領域を拡大し、個体Ｉbest以外の個体を個体Ｉbestの近傍に変位させて最適解を探索することをいう。
【００５１】
単点選択手段６ｂは、図７に示すように、各個体の評価値に基づいて全個体の中から◎で表される最も良い評価値Ｑbestを有する個体Ｉbestを選択し、さらに、個体Ｉbest以外の個体の中からランダムに１つの個体Ｉrを選択するようになっている。
【００５２】
個体変位手段７ａは、単点選択手段６ａで選択された個体Ｉrを、個体Ｉbestから所定のユークリッド距離内の任意の位置に変位させ、個体Ｉrに含まれるパラメータ（Ｐ１r，Ｐ２r）をその任意の位置の座標（Ｐ１´，Ｐ２´）で置き換えるようになっている。
【００５３】
ここで、個体Ｉbestの近傍を画する前記所定のユークリッド距離として、本実施形態では、最も良い評価値Ｑを有する個体Ｉbestと最も悪い評価値Ｑを有する個体Ｉworstとの間のユークリッド距離の１／３の距離が用いられるようになっている。
【００５４】
なお、これ以外にも、例えば、前記１／３を別の比率に設定したり、個体Ｉbestと最も悪い変位基準値ＷＱを有する個体Ｉfarとの間のユークリッド距離を基準としたり、或いは個体Ｉbestと任意に選択された個体Ｉrとの間のユークリッド距離をそのまま前記所定のユークリッド距離とすることも可能である。また、前記所定のユークリッド距離は、例えば、世代を通して一定の距離であってもよく、また、世代が進むに従って小さい距離となるように設定されてもよい。
【００５５】
本実施形態では、単点選択手段６ａおよび個体変位手段７ａの処理または単点選択手段６ｂおよび個体変位手段７ｂの処理が終了した時点で世代交代が行われたとして、世代が次の世代に移る。
【００５６】
単点選択手段６ａおよび個体変位手段７ａの処理または単点選択手段６ｂおよび個体変位手段７ｂの処理が終了すると、変位された個体が前記評価値算出手段３に送られるようになっている。また、前記終了判定条件が満たされて最良の評価値Ｑを有する個体に含まれるパラメータＰ１〜Ｐｎがパラメータの最適値Ｐ１suit〜Ｐｎsuitとして出力されるまで、前記処理が繰り返されるように構成されている。
【００５７】
次に、本実施形態に係るパラメータ最適化装置１の作用について説明する。
【００５８】
パラメータ最適化装置１では、システムの動作に係るパラメータとして最適値の算出が必要なｎ個のパラメータＰ１〜Ｐｎが設定されると、初期化手段２によりパラメータＰ１〜Ｐｎの上限値および下限値を境界とするｎ次元の直方体状の探索空間Ｓを仮想的に設定される。そして、そのｎ次元の探索空間Ｓの各頂点に、ｎ個のパラメータＰ１〜Ｐｎを要素とする２ｎ個の個体Ｉ１、Ｉ２、…が重複しないように割り当てられる。
【００５９】
そして、評価値算出手段３で、これらの初期個体としての個体Ｉ１、Ｉ２、…についてそれぞれシミュレーションや実機を用いた教師ありまたは教師なしの施行が行われ、各個体に対して評価値Ｑが算出される。この場合、試行は各個体につき１回ずつ、計２ｎ回の試行が行われる。
【００６０】
終了判定条件を満たしていなければ、切替手段５が設定された割合で挟み撃ち探索を行うか近傍探索を行うかを決め、単点選択手段６ａおよび個体変位手段７ａで挟み撃ち探索が行われ、単点選択手段６ｂおよび個体変位手段７ｂで近傍探索が行われる。このようにして世代交代が行われ、個体変位の過程で探索空間Ｓ内で変位された個体が評価値算出手段３に送られる。
【００６１】
評価値算出手段３は、今度は、個体変位手段７ａ、７ｂから送られてきた個体についてのみ試行を行い、その個体の評価値Ｑを算出する。他の個体については改めて評価値Ｑが算出されることはなく、既に算出された評価値Ｑが用いられる。その際、個体変位手段７ａ、７ｂから送られてきた個体の評価値Ｑが、それまでの最も良い評価値を有する個体Ｉbestの評価値Ｑbestを上回れば、個体変位手段７ａ、７ｂから送られてきた個体がその世代の個体の中で最も良い評価値を有する個体Ｉbestとなる。
【００６２】
以上の過程が繰り返されながら、終了判定手段４が設定された終了判定条件を満たしたと判定した時点で最良の評価値Ｑを有する個体に含まれるパラメータＰ１〜Ｐｎをパラメータの最適値Ｐ１suit〜Ｐｎsuitとして出力する。
【００６３】
この過程の中で、各個体は、初期化状態で配置された探索空間Ｓの各頂点から世代が進むにつれて挟み撃ち探索により探索空間Ｓの内側にしだいに変位して、囲い込むようにして探索領域Ｓａを狭めていく。そのため、前記所定の割合αを比較的小さな値に設定し、探索領域を少しずつ狭めながら最適解を囲い込んでいくことで確実に評価値Ｑを改善していくことが可能である。
【００６４】
一方、挟み撃ち探索では、最も良い評価値Ｑを有する個体Ｉbestは、他の個体が変位により評価値Ｑを改善して個体Ｉbestの評価値Ｑ以上になるまで探索空間Ｓ内でその位置を変えない。これは遺伝的アルゴリズムにおけるエリート保存の手法に類似している。しかし、そのために個体Ｉbestは最適解の近くにいる可能性が高いにもかかわらず、最適解に近づくことができない。
【００６５】
そのため、近傍探索により他の個体を個体Ｉbestの近傍に強制的に変位させることで、変位させられた個体の評価値Ｑが個体Ｉbestの評価値Ｑbestを上回る可能性が生じる。このように、近傍探索を行えば、評価値Ｑが速やかに向上する可能性が高まる。
【００６６】
ここで、本実施形態に係るパラメータ最適化と従来の遺伝的アルゴリズムを用いたパラメータ最適化とを比較する実験結果について述べる。実験は、評価関数が下記の（５）式で表される５次元のrastringin関数で与えられるシステムにおいて、本実施形態および従来ともパラメータｘiの数が５、個体数２５＝３２として行った。
【００６７】
【数１】
2007233676.tif 000003
【００６８】
すなわち、本実施形態に係るパラメータ最適化では、パラメータｘ１〜ｘ５について上限値５．１２および下限値−５．１２を重複しないように組み合わせた３２個の個体が生成される。また、遺伝的アルゴリズムを用いたパラメータ最適化では、パラメータｘ１〜ｘ５としてそれぞれ下限値から上限値までの数値範囲の中からランダムに選ばれた数値を要素とする個体が３２個生成される。
【００６９】
なお、本実施形態において、前記割合α＝０．４、挟み撃ち探索と近傍探索との割合を７０％と３０％とし、変位基準値ＷＱを用いた単点選択を行い、近傍探索では個体Ｉbestと個体Ｉworstとのユークリッド距離の１／３を用いた。
【００７０】
また、評価回数Ｎが３０回に達した時点で最良の個体の評価値f(x)を出力し、また新たに個体を初期化して評価回数Ｎが３０回に達するまで計算を行う実験を１００回繰り返し、それらの評価値の平均値を評価回数Ｎが３０回の場合の評価値f(x)としてグラフにプロットする。同様にして、６０回、９０回、…と計算を繰り返し、それぞれ１００回分の平均値を評価値f(x)としてプロットした。
【００７１】
従って、例えば、３０回の評価回数における評価値f(x)を算出するために用いられた個体が、引き続き６０回の評価回数における評価値f(x)の算出に用いられるわけではない。なお、１つの試行につき１つの評価値Ｑが算出されるから、評価回数Ｎと試行回数とは同一の数となる。
【００７２】
比較実験の結果を図８に示す。図では、本実施形態に係るパラメータ最適化による結果が■で示され、従来の遺伝的アルゴリズムによるパラメータ最適化の結果が◆で示されている。
【００７３】
本実施形態に係るパラメータ最適化では、初期化手段２で生成された３２個の個体については、すべての試行が終了するまで評価値f(x)を算出しない仕様となっている。そのため、評価回数Ｎすなわち試行回数が３０回の段階では評価値f(x)として０が出力される。
【００７４】
しかし、評価回数が６０回の段階で、すでに遺伝的アルゴリズムを用いた場合の同じ評価回数における評価値f(x)を上回っている。また、遺伝的アルゴリズムを用いた場合の評価回数９００回の評価値f(x)が、本実施形態に係るパラメータ最適化では既に３００回の段階で達成されている。
【００７５】
なお、本実施形態では、１世代目で評価回数が３２回かかるが、２世代目以降は１世代につき評価回数は１回である。従って、例えば、評価回数が６０回の段階とは、従来の遺伝的アルゴリズムでは２世代目の途中の段階に相当するが、本実施形態では２９世代目の段階に相当する。
【００７６】
以上のように、本実施形態に係るパラメータ最適化装置１によれば、最適値算出の対象とされるパラメータの上限値および下限値を境界とする探索空間内にそれらのパラメータを要素とする個体を複数生成させる。そして、それらの個体を１つずつ探索空間の内側に向かうように方向性を持たせて変位させるように挟み撃ち探索を行わせることができる。
【００７７】
そのため、最適値を囲い込むように探索領域を狭めながら効率良くパラメータの最適値の探索を行って、少ない評価回数で最適解を得ることが可能となる。その結果、実システムのオンライン最適化を行う際の時間的な制限をクリアすることができ、かつ、好適な評価値を有する個体を獲得して好適なパラメータの最適値を得ることが可能となる。
【００７８】
一方、従来の遺伝的アルゴリズムを用いた最適値探索では、例えば特許文献１、２に記載のパラメータ最適化装置のように探索範囲を狭める制限を課したとしても、基本的には複数の個体が一斉に探索空間内をランダムに変位し、探索空間内をくまなく探索しようとする。そのため、好適なパラメータの最適値を得る可能性が高くなるとしても、評価値のピークから遠ざかり評価値を下げるような変位を行った個体についても評価値の算出を行わなければならず、必ずしも少ない評価回数で最適解を得ることができなくなる。
【００７９】
また、本実施形態に係るパラメータ最適化装置１において、パラメータの数がｎ個の場合に２ｎ個の個体を生成させ、ｎ次元の探索空間の各頂点に重複しないように配置することで、探索空間自体を探索領域とする探索領域が最も広い状態から徐々に探索領域を狭めながら最適解を囲い込むようにして探索することができる。
【００８０】
そのため、パラメータの最適値を確実に得ることが可能となる。また、従来の遺伝的アルゴリズムを用いる場合のように、作業者の経験や直観に依存することなく生成させる個体数を決定することが可能となるとともに、必要以上に多くの個体を生成させて評価回数が増大することが防止され、処理時間の短縮を図ることが可能となる。
【００８１】
なお、本実施形態では、パラメータの数がｎ個の場合に、初期化手段２で２ｎ個の個体を生成させ、ｎ次元の探索空間の各頂点に重複しないように配置する場合について説明したが、生成させる個体を２個以上２ｎ個未満とすることも可能である。生成させる個体数を減らすことで、初期状態ですべての個体について行う評価回数をさらに減らすことができる。
【００８２】
この場合も、各個体はｎ次元の探索空間の各頂点に重複しないように配置することが好ましい。また、このように個体数を減らして挟み撃ち探索のみを行うと、初期状態で個体が配置されない探索空間Ｓの頂点を含む図９に斜線を付して示される領域Ｓｂについては、パラメータの最適値の探索が行われなくなる。そのため、このように個体数を減らして生成させる場合には必ず近傍探索を行うように構成される。
【図面の簡単な説明】
【００８３】
【図１】本実施形態に係るパラメータ最適化装置の構成を示すブロック図である。
【図２】本実施形態で用いられる個体の構成を説明する図である。
【図３】探索空間の構成およびその各頂点に配置された個体を説明する図である。
【図４】探索空間内において挟み撃ち探索で変位された個体を説明する図である。
【図５】評価値が最も良い個体からの距離が最も遠い個体を説明する図である。
【図６】評価値が最も良い個体からの距離が最も遠い個体を説明する図である。
【図７】探索空間内において近傍探索で変位された個体を説明する図である。
【図８】本実施形態に係るパラメータ最適化と遺伝的アルゴリズムを用いたパラメータ最適化との比較実験の結果を表すグラフである。
【図９】生成される個体数を減らした場合に挟み撃ち探索で探索が行われない領域を示す図である。
【符号の説明】
【００８４】
１  パラメータ最適化装置
２  初期化手段
３  評価値算出手段
４  終了判定手段
５  切替手段
６ａ、６ｂ  単点選択手段
７ａ、７ｂ  個体変位手段
Ｐ１〜Ｐｎ  パラメータ
Ｐ１max〜Ｐｎmax  パラメータの上限値
Ｐ１min〜Ｐｎmin  パラメータの下限値
Ｐ１suit〜Ｐｎsuit  パラメータの最適値
ｎ  パラメータの数
Ｓ  探索空間
Ｉ１、Ｉ２、…  個体
Ｉbest  良い評価値を有する個体
Ｉworst  悪い評価値を有する個体
Ｉfar  変位基準値が悪い個体
Ｑ  評価値
ＷＱ  変位基準値
Ｌ  ユークリッド距離
α  割合
【図１】
2007233676.tif 000004
【図２】
2007233676.tif 000005
【図３】
2007233676.tif 000006
【図４】
2007233676.tif 000007
【図５】
2007233676.tif 000008
【図６】
2007233676.tif 000009
【図７】
2007233676.tif 000010
【図８】
2007233676.tif 000011
【図９】
2007233676.tif 000012