(57)【要約】【課題】複数の極値を備えた評価関数の最小値又は最大値を探索するときに、変数の最適値への到達確率を高めながら極力少ない回数で最適値へ到達できるようにした最適化装置及び最適化プログラムを提供する。【解決手段】複数の個体Ｋの変数ｘｉを探索空間Ｓ内の評価関数Ｈoptに沿って設定する（Ｓ１）。また、設定された複数の個体Ｋのうち少なくとも２つ以上の選定個体Ｋに引力を作用させる引力ポテンシャルｆijを導出し、複数の個体Ｋによる評価関数Ｈoptの評価値を加算した評価加算値、及び、導出された選定個体Ｋ間の引力ポテンシャルｆijを加算しこの加算値に選定個体Ｋの間に作用させる引力係数ｇ／２を乗算した引力値、を加算した実効評価値Ｈeffを極値化する。さらに、引力係数ｇ／２を初期値から徐々に大きくしながら実効評価値Ｈeffが極値化するように複数の個体Ｋの変数ｘｉを変化させる（Ｓ２，Ｓ５）。【選択図】図２
2018037003.tif 000002
【特許請求の範囲】
【請求項１】
１以上の次元を備えた探索空間（Ｓ）に複数の極値を備える評価関数（Ｈopt）に個体（Ｋ）を設定することに基づいて個体の変数（ｘｉ）または変数の最適値を導出する連続値最適化問題の大域的探索装置（１、１０１）であって、
複数の個体の変数を前記探索空間の中の評価関数に沿って設定する設定部（６）と、
前記設定部により設定される複数の個体のうち少なくとも２つ以上の選定個体に引力を作用させる引力ポテンシャルを導出し、前記複数の個体の変数による評価関数の評価値を加算した評価加算値、及び、導出された前記選定個体の間の引力ポテンシャルを加算しこの加算値に前記選定個体の間に作用させる引力係数（ｇ／２）とを乗算した引力値、を加算した実効評価値（Ｈeff）を極値化する極値化部（７）と、
前記引力係数を初期値から徐々に大きくしながら前記極値化部により実効評価値が極値化するように前記複数の個体の変数を変化させ、所定の終了条件を満たしたときにおける前記複数の個体の少なくとも一つの個体に基づいて、前記個体の変数、その変数の最適値、変数に対応した評価値、又は、評価値の最適値による各種値を導出する導出部（８）と、
を備える大域的探索装置。
【請求項２】
請求項１記載の大域的探索装置において、
前記変数の探索を開始する前に予め変数の推定解（ｘiz）が与えられている場合には、
前記設定部は、初期分布として前記探索空間の内部に限定された限定探索範囲（Ｓａ）であって当該推定解を含む限定探索範囲に前記個体の変数を設定する大域的探索装置。
【請求項３】
請求項１または２記載の大域的探索装置において、
前記設定部は、初期分布として前記探索空間に前記複数の個体の変数をランダムに設定する大域的探索装置。
【請求項４】
請求項１または２記載の大域的探索装置において、
前記設定部は、初期分布として少なくとも１つ以上の個体の少なくとも一つ以上の変数を前記探索空間の上限値又は下限値とし、その他の個体の変数をランダムに設定する大域的探索装置。
【請求項５】
請求項１または２記載の大域的探索装置において、
前記設定部は、初期分布として前記探索空間を分割した格子点位置になるように前記個体の変数を設定する大域的探索装置。
【請求項６】
請求項５記載の大域的探索装置において、
前記個体の変数が谷の生成に寄与する寄与度の高い前記個体の変数の分割数を寄与度の低い個体の変数よりも大きく設定する大域的探索装置。
【請求項７】
請求項５または６記載の大域的探索装置において、
前記設定部は、前記初期分布として少なくとも１つ以上の変数が上限値又は下限値となる個体を選定して設定する大域的探索装置。
【請求項８】
請求項３から７の何れか一項に記載の大域的探索装置において、
前記設定部は、前記探索空間を複数の部分空間（Ｓｃ、Ｓｄ）に分け、当該各部分空間にそれぞれ個体を設定し、
前記導出部は、前記極値化部により求められた実効評価値が所定終了条件を満たしたときにおける前記複数の個体の少なくとも一つの個体に基づいて前記各種値を導出する大域的探索装置。
【請求項９】
請求項１記載の大域的探索装置において、
前記変数の探索を開始する前に予め変数の推定解（ｘiz）が与えられている場合には、
前記設定部は、初期分布として前記推定解を含む空間に近いほど個体を密に分布させると共に前記推定解から遠ざかるほど個体の密度を減少させるように設定する大域的探索装置。
【請求項１０】
請求項１記載の大域的探索装置において、
前記変数の探索を開始する前に予め変数の推定解（ｘiz）が与えられている場合には、
前記設定部は、初期分布として前記推定解を含む空間に近い所定範囲（Ｓｂ）に個体を密に分布させると共にその他の個体を前記所定範囲の外にランダムに分布させ、その他の個体の少なくとも１つの個体の少なくとも一つ以上の変数を前記探索範囲の上限値又は下限値に設定する大域的探索装置。
【請求項１１】
請求項１から１０の何れか一項に記載の大域的探索装置において、
前記極値化部は、前記複数の個体に対し識別符号を順序付けて付し、順序が隣接する識別符号が付された個体を前記選定個体として引力値を導出し、順序が隣接しない識別符号が付された個体を前記選定個体とせず引力値を０とする大域的探索装置。
【請求項１２】
請求項５から７の何れか一項に記載の大域的探索装置において、
前記極値化部は、変数の数をＭ（但しＭは１以上の自然数）としたときに、前記格子点位置の個体と隣接する格子点位置の最大２×Ｍ個の個体を前記選定個体として引力値を導出し、その他の個体を選定個体とすることなく前記引力値を０とする大域的探索装置。
【請求項１３】
請求項１１または１２記載の大域的探索装置において、
前記極値化部が前記複数の個体の間の引力ポテンシャルを導出し引力値を導出するときには、前記複数の個体の間の距離が大きいほど大きな引力値とし距離が小さいほど小さな引力値とする大域的探索装置。
【請求項１４】
請求項１３記載の大域的探索装置において、
前記極値化部が前記複数の個体の間の引力ポテンシャルを導出し引力値を導出するときに、
【数２】
2018037003.tif 000021
の（２）式により導出する大域的探索装置。
【請求項１５】
請求項１１または１２記載の大域的探索装置において、
前記極値化部が前記複数の個体の間の引力ポテンシャルを導出し引力値を導出するときには、前記複数の個体の間の距離に依存しない一定の引力値とする大域的探索装置。
【請求項１６】
請求項１５記載の大域的探索装置において、
前記極値化部が前記複数の個体の間の引力ポテンシャルを導出し引力値を導出するときに、
【数３】
2018037003.tif 000022
の（３）式により導出する大域的探索装置。
【請求項１７】
請求項１から１６の何れか一項に記載の大域的探索装置において、
前記導出部は、少なくとも一つの個体の評価値に基づいて各種値を導出するときに、前記引力値を０として前記複数の個体の評価加算値による実効評価値を極値化して前記複数の個体の変数の実効評価値の最小値を導出し、当該実効評価値が最小値を満たす変数を最適値として導出する大域的探索装置。
【請求項１８】
請求項１から１７の何れか一項に記載の大域的探索装置において、
前記極値化部が、前記実効評価値を極値化するときには、
前記評価加算値及び前記引力値のそれぞれについて、当該値の解候補を求めた後、当該解候補を代入したときの微分値が当該評価関数の微分値と等しく、且つ、前記解候補を含む探索空間の内の全ての変数における評価値よりも大きな値を得る条件を満たす２次関数に置換し、当該２次関数の極値を次回の値の解候補として繰り返して更新する補助関数法を用い、
前記評価加算値と前記引力値とを加算した実効評価値を極値化する大域的探索装置。
【請求項１９】
請求項１４記載の大域的探索装置において、
前記極値化部が、前記実効評価値を極値化するときには、
前記評価加算値及び前記引力値のそれぞれについて、当該値の解候補を求めた後、当該解候補を代入したときの微分値が当該評価関数の微分値と等しく、且つ、前記解候補を含む探索空間の内の全ての変数における評価値よりも大きな値を得る条件を満たすリプシッツ定数を用いた２次関数に置換し、当該２次関数の極値を次回の値の解候補として繰り返して更新する補助関数法を用い、
前記評価加算値と前記引力値とを加算した実効評価値を極値化するものであり、
前記極値化部が、前記引力値について前記補助関数法を用いるときには前記２次関数のリプシッツ定数を４に固定して設定する大域的探索装置。
【請求項２０】
請求項１記載の大域的探索装置（１０１）であって、
前記導出部が、前記個体の変数又はその最適値として、未来時刻における最適経路（Ｒ１）を導出するときに、
前記設定部は、過去の最適経路（Ｒ０）を推定解とし、前記初期分布として前記推定解を含む領域に近いほど個体を密に分布させると共に前記推定解から遠ざかるほど個体の密度を減少させるように設定する大域的探索装置。
【請求項２１】
１以上の次元を備えた探索空間（Ｓ）に複数の極値を備える評価関数（Ｈopt）に個体（Ｋ）を設定することに基づいて個体の変数（ｘｉ）または変数の最適値を導出するプログラムであって、
大域的探索装置（１，１０１）に、
複数の個体の変数を前記探索空間の中の評価関数に沿って設定する手順と、
設定された複数の個体のうち少なくとも２つ以上の選定個体に引力を作用させる引力ポテンシャルを導出し、前記複数の個体の変数による評価関数の評価値を加算した評価加算値、及び、導出された前記選定個体の間の引力ポテンシャルを全て加算しこの加算値に前記選定個体の間に作用させる引力係数（ｇ／２）とを乗算した引力値、を加算した実効評価値（Ｈeff）を極値化する手順と、
前記引力係数を初期値から徐々に大きくしながら前記極値化部により実効評価値が極値化するように前記複数の個体の変数を変化させ、所定の終了条件を満たしたときにおける前記複数の個体の少なくとも一つの個体の評価値に基づいて、前記個体の変数、その変数の最適値、変数に対応した評価値、又は、評価値の最適値による各種値を導出する手順と、
を実行させるプログラム。
【請求項２２】
請求項２１記載のプログラムにおいて、
前記変数の探索を開始する前に予め変数の推定解（ｘiz）が与えられている場合には、
前記最適化装置が前記複数の個体の変数を設定する手順では、初期分布として前記探索空間に限定された限定探索範囲（Ｓａ）であって当該推定解を含む限定探索範囲に前記個体の変数を設定するプログラム。
【請求項２３】
請求項２１または２２記載のプログラムにおいて、
前記最適化装置が前記複数の個体の変数を設定する手順では、初期分布として前記探索空間に前記複数の個体の変数をランダムに設定するプログラム。
【請求項２４】
請求項２１または２２記載のプログラムにおいて、
前記最適化装置が前記複数の個体の変数を設定する手順では、初期分布として少なくとも１つ以上の個体の少なくとも一つ以上の変数を前記探索空間の上限値又は下限値とし、その他の個体の変数をランダムに設定するプログラム。
【請求項２５】
請求項２１または２２記載のプログラムにおいて、
前記最適化装置が前記複数の個体の変数を設定する手順では、初期分布として前記探索空間において全ての個体の変数を分割した格子点位置になるように前記個体の変数を設定するプログラム。
【請求項２６】
請求項２５記載のプログラムにおいて、
前記最適化装置が前記複数の個体の変数を設定する手順では、前記個体の変数が谷の生成に寄与する寄与度の高い前記個体の変数の分割数を寄与度の低い個体の変数よりも大きく設定するプログラム。
【請求項２７】
請求項２５または２６記載のプログラムにおいて、
前記最適化装置が前記複数の個体の変数を設定する手順では、前記初期分布として少なくとも１つ以上の変数が上限値又は下限値となる個体を選定して設定するプログラム。
【請求項２８】
請求項２３から２７の何れか一項に記載のプログラムにおいて、
前記探索空間を複数の部分空間（Ｓｃ、Ｓｄ）に分け、当該各部分空間にそれぞれ個体を設定し、前記極値化部により実効評価値を求め当該実効評価値が所定終了条件を満たしたときにおける前記複数の個体の少なくとも一つの個体の評価値に基づいて前記個体の変数又はその変数の最適値を導出するプログラム。
【請求項２９】
請求項２１記載のプログラムにおいて、
前記変数の探索を開始する前に予め変数の推定解（ｘiz）が与えられている場合には、
前記最適化装置が前記複数の個体の変数を設定する手順では、初期分布として前記推定解を含む空間に近いほど個体を密に分布させると共に前記推定解から遠ざかるほど個体の密度を減少させるように設定するプログラム。
【請求項３０】
請求項２１記載のプログラムにおいて、
前記変数の探索を開始する前に予め変数の推定解（ｘiz）が与えられている場合には、
前記最適化装置が前記複数の個体の変数を設定する手順では、初期分布として前記推定解を含む空間に近い所定範囲内に個体を密に分布させると共にその他の個体を前記所定範囲の外にランダムに分布させ、その他の個体の少なくとも１つの個体の少なくとも一つ以上の変数を前記探索範囲の上限値又は下限値に設定するプログラム。
【請求項３１】
請求項２１から３０の何れか一項に記載のプログラムにおいて、
前記実効評価値を極値化する手順では、前記複数の個体に対し識別符号を順序付けて付し、順序が隣接する識別符号が付された個体を前記選定個体として引力値を導出し、順序が隣接しない識別符号が付された個体を前記選定個体とせず引力値を０とするプログラム。
【請求項３２】
請求項２５から２７の何れか一項に記載のプログラムにおいて、
前記実効評価値を極値化する手順では、変数の数をＭ（但しＭは１以上の自然数）としたときに、前記格子点位置の個体と隣接する格子点位置の最大２×Ｍ個の個体を前記選定個体として引力値を導出し、その他の個体を選定個体とすることなく前記引力値を０とするプログラム。
【請求項３３】
請求項３１または３２記載のプログラムにおいて、
前記実効評価値を極値化する手順では、前記複数の個体の間の引力ポテンシャルを導出し引力値を導出するときには、前記複数の個体の間の距離が大きいほど大きな引力値とし距離が小さいほど小さな引力値とするプログラム。
【請求項３４】
請求項３３記載のプログラムにおいて、
前記実効評価値を極値化する手順では、前記複数の個体の間の引力ポテンシャルを導出し引力値を導出するときに、
【数２】
2018037003.tif 000023
の（２）式により導出するプログラム。
【請求項３５】
請求項３１または３２記載のプログラムにおいて、
前記実効評価値を極値化する手順において、前記複数の個体の間の引力ポテンシャルを導出するときには、前記複数の個体の間の距離に依存しない一定の引力値とする最適化プログラム。
【請求項３６】
請求項３５記載のプログラムにおいて、
前記実効評価値を極値化する手順では、前記複数の個体の間の引力ポテンシャルを導出し引力値を導出するときに、
【数３】
2018037003.tif 000024
の（３）式により導出するプログラム。
【請求項３７】
請求項２１から３６の何れか一項に記載のプログラムにおいて、
前記各種値を導出する手順では、少なくとも一つの個体の評価値に基づいて個体の変数を導出するときに、前記引力値を０として前記複数の個体の評価加算値による実効評価値を極値化して前記複数の個体の変数の実効評価値の最小値を導出し、当該実効評価値が最小値を満たす変数を最適値として導出するプログラム。
【請求項３８】
請求項２１から３７の何れか一項に記載のプログラムにおいて、
前記実効評価値を極値化する手順では、
前記評価加算値及び前記引力値のそれぞれについて、当該値の解候補を求めた後、当該解候補を代入したときの微分値が当該評価関数の微分値と等しく、且つ、前記解候補を含む探索空間の内の全ての変数における評価値よりも大きな値を得る条件を満たす２次関数に置換し、当該２次関数の極値を次回の値の解候補として繰り返して更新する補助関数法を用い、
前記評価加算値と前記引力値とを加算した実効評価値を極値化するプログラム。
【請求項３９】
請求項３４記載のプログラムにおいて、
前記実効評価値を極値化する手順では、
前記評価加算値及び前記引力値のそれぞれについて、当該値の解候補を求めた後、当該解候補を代入したときの微分値が当該評価関数の微分値と等しく、且つ、前記解候補を含む探索空間の内の全ての変数における評価値よりも大きな値を得る条件を満たすリプシッツ定数を用いた２次関数に置換し、当該２次関数の極値を次回の値の解候補として繰り返して更新する補助関数法を用い、
前記評価加算値と前記引力値とを加算した実効評価値を極値化するものであり、
前記引力値について前記補助関数法を用いるときには前記２次関数のリプシッツ定数を４に固定して設定するプログラム。
【請求項４０】
請求項２１記載のプログラムにおいて、
前記個体の変数又はその最適値を導出する手順では、未来時刻における最適経路（Ｒ１）を導出するものであって、
前記複数の個体の変数を設定する手順では、過去の最適経路（Ｒ０）を推定解とし、前記初期分布として前記推定解を含む領域に近いほど個体を密に分布させると共に前記推定解から遠ざかるほど個体の密度を減少させるように設定する最適化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、連続値最適化問題の大域的探索装置及びプログラムに関する。
【背景技術】
【０００２】
例えば、多次元の探索空間において変数、すなわちパラメータの最適値を求める手法が提案されている（例えば、特許文献１参照）。特許文献１記載の技術によれば、探索空間内に最適値算出対象のパラメータを要素とする複数の個体を生成し、これらの個体の評価値を算出し、個体の中から評価値の悪い個体を選択している。そして、この選択された個体を評価値の良い個体に所定の割合で近づけている。また、評価値の悪い個体を最良の評価値の個体から一定のユークリッド距離内にある任意の領域に移動させている。そして、より良い評価値の個体を選択し最良の評価値の個体を随時更新し、複数の個体の評価値を収束させ、終了判定条件を満たしたと判定した時点で最良の評価値を有する個体に含まれるパラメータをパラメータの最適値として出力している。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００７−２３３６７６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
特許文献１等に記載の技術を用いて、例えば、複数の極値（例えば極小値）を備えた評価関数の最小値又は最大値となる変数の最適値を探索するとき、当該変数の最適値への到達確率を高めるためには、複数の個体が最適な１カ所に収束する過程において可能な限り多くの極値（例えば、極小値）を探索することが望ましい。
【０００５】
しかしながら、特許文献１記載の技術を適用したとしても、複数の個体を互いに近づける収束過程において、個体の移動経路はその評価関数の形状とは無関係に決定されてしまう。このため、個体が収束過程において極値を通過するとは限らず、どの個体に収束させることが望ましいか正確に判断できなかったり最適値を通過してしまうことがある。個体の移動処理を極力細かくすることにより最適値への到達確率は高まるものの、個体の移動の回数が増加してしまい好ましくない。
【０００６】
本発明の目的は、複数の極値を備えた評価関数の最小値又は最大値を探索するときに、変数の最適値への到達確率を高めながら極力少ない回数で最適値へ到達できるようにした連続値最適化問題の大域的探索装置及びプログラムを提供することにある。
【課題を解決するための手段】
【０００７】
請求項１に記載した発明によれば、１以上の次元を備えた探索空間に複数の極値を備える評価関数に個体を設定することに基づいて個体の変数又は変数の最適値を導出する最適化装置を対象としている。
【０００８】
設定部は、複数の個体の変数を探索空間の中の評価関数に沿って設定する。また、極値化部は、設定部により設定される複数の個体のうち少なくとも２つ以上の選定個体に引力を作用させる引力ポテンシャルを導出し、複数の個体による評価関数の評価値を加算した評価加算値、及び、導出された選定個体の間の引力ポテンシャルを加算しこの加算値に選定個体の間に作用させる引力係数とを乗算した引力値、を加算した実効評価値を極値化する。そして導出部は、引力係数を初期値から徐々に大きくしながら極値化部により実効評価値が極値化するように複数の個体の変数を変化させ、所定の終了条件を満たしたときにおける複数の個体の少なくとも一つの個体の評価値に基づいて、個体の変数、その変数の最適値、変数に対応した評価値、又は、評価値の最適値を導出する。このような処理を行うことで、複数の極値を備えた評価関数の最小値又は最大値を探索するときに、変数の最適値への到達確率を高めながら極力少ない回数で最適値へ到達できる。
【図面の簡単な説明】
【０００９】
【図１Ａ】第１実施形態を示す連続値最適化問題の大域的探索装置の電気的構成図
【図１Ｂ】連続値最適化問題の大域的探索装置を機能的に示すブロック図
【図２】処理の流れを概略的に示すフローチャート
【図３Ａ】個体が探索空間内の最適解に収束するときの移動状態を示すイメージ図（その１）
【図３Ｂ】個体が探索空間内の最適解に収束するときの移動状態を示すイメージ図（その２）
【図３Ｃ】個体が探索空間内の最適解に収束するときの移動状態を示すイメージ図（その３）
【図３Ｄ】個体が探索空間内の最適解に収束するときの移動状態を示すイメージ図（その４）
【図４】第２実施形態の説明図であり個体の初期分布を示す図（その１）
【図５】個体の初期分布を示す図（その２）
【図６】個体の初期分布を示す図（その３）
【図７】個体の初期分布を示す図（その４）
【図８】個体の初期分布を示す図（その５）
【図９】個体の初期分布を示す図（その６）
【図１０】個体の初期分布を示す図（その７）
【図１１】個体の初期分布を示す図（その８）
【図１２】個体の初期分布を示す図（その９）
【図１３】個体の初期分布を示す図（その１０）
【図１４】第３実施形態の説明図であり個体の存在分布の例を示す図
【図１５】引力ポテンシャルを与える選定個体の例を示す説明図（その１）
【図１６】引力ポテンシャルを与える選定個体の例を示す説明図（その２）
【図１７】引力ポテンシャルを与える選定個体の例を示す説明図（その３）
【図１８】引力ポテンシャルを与える選定個体の例を示す説明図（その４）
【図１９】引力ポテンシャルを与える選定個体の例を示す説明図（その５）
【図２０Ａ】個体の移動過程を示す説明図（その１）
【図２０Ｂ】個体の移動過程を示す説明図（その２）
【図２０Ｃ】個体の移動過程を示す説明図（その３）
【図２０Ｄ】個体の移動過程を示す説明図（その４）
【図２１】第５実施形態の説明図であり補助関数法の原理を概略的に示す説明図
【図２２】リプシッツ定数の説明図（その１）
【図２３】リプシッツ定数の説明図（その２）
【図２４】処理の流れを概略的に示すフローチャート
【図２５】シミュレーションに用いた評価関数を示す図
【図２６】シミュレーションに用いた定数を示す図
【図２７】シミュレーション結果
【図２８】ある所定領域に収束する過程を示す図
【図２９】第６実施形態の説明図であり個体が収束した後の状態を示す説明図
【図３０】第７実施形態を示す電気的構成図
【図３１】ある時刻における移動体の最適経路を示す鳥瞰図（その１）
【図３２】ある時刻における移動体の最適経路を示す鳥瞰図（その２）
【発明を実施するための形態】
【００１０】
以下、本発明の連続値最適化問題の大域的探索装置及びプログラムの幾つかの実施形態について図面を参照して説明する。以下の実施形態中では、各実施形態間で同一機能または類似機能を備えた部分に同一符号を付して説明を行い、同一又は類似機能を備えた構成及びその作用、連携動作説明等を必要に応じて省略する。
【００１１】
（第１実施形態）
図１Ａ〜図３Ｄは第１実施形態の説明図を示している。最適化装置１は、ＣＰＵ２と、ＲＯＭ、ＲＡＭ等のメモリ３と、入出力インタフェース４とをバス接続して構成されたマイクロコンピュータ（以下マイコン）５、又は汎用コンピュータなどを用いて連続値最適化問題の大域的探索装置として構成される。以下、マイコン５が最適化処理を実行することとして説明を行う。マイコン５が、メモリ３に記憶された最適化プログラムを実行し、各種手順を実行することで最適化処理を実行する。メモリ３は非遷移的実体的記録媒体として用いられる。
【００１２】
ここで最適化処理とは、１以上のＭ（≧１）次元を備えたユークリッド空間からなる探索空間Ｓを想定し、この探索空間Ｓに予め定められる評価関数Ｈoptの最小値又は最大値、すなわち最適値を求める処理、又は／及び、評価関数Ｈoptが最適値となる変数ｘｉを求める処理を示す。以下では、評価関数Ｈoptの最小値を最適値として求めるための形態を示すが、最大値を最適値として求める処理に適用しても良い。評価関数Ｈoptは、１以上のＭ個の変数（パラメータ）に基づく数式による関数を示すものであり、例えば任意の多項式、有理関数、無理関数、指数関数、対数関数やその加減乗除等による組み合わせなどを挙げることができる。
【００１３】
図１Ｂに示すように、最適化装置１は、マイコン５により実現される機能ブロックとして、設定部６、極値化部７、及び導出部８などの各種機能ブロックを備えるものである。設定部６は、複数の個体Ｋの変数ｘｉを探索空間Ｓの内部の評価関数Ｈoptに沿って設定する。複数の個体ＫはそれぞれＭ次元の変数ｘｉを備える。
【００１４】
また極値化部７は、設定部６により設定された複数の個体Ｋのうち少なくとも２つ以上の選定個体Ｋに引力を作用させる引力ポテンシャルｆijを導出し、複数の個体Ｋの変数ｘｉによる評価関数Ｈoptの評価値Ｈopt（ｘｉ）を加算した評価加算値ΣＨopt（ｘｉ）、及び、導出された選定個体Ｋの間の引力ポテンシャルｆijを加算しこの加算値に選定個体Ｋの間に作用させる引力係数ｇ／２とを乗算した引力値、を加算した実効評価値Ｈeffを極値化、本実施形態では極小化する。
【００１５】
そして導出部８は、引力係数ｇ／２を初期値（例えば０）から徐々に大きくしながら極値化部７により実効評価値Ｈeffが極値化するように複数の個体Ｋの変数ｘｉを変化させ、所定の終了条件を満たしたときにおける複数の個体Ｋの少なくとも一つの個体Ｋの評価値に基づいて、個体Ｋの変数ｘｉを導出する。すると、複数の個体Ｋが評価関数Ｈoptの最小値の一点に収束しやすくなる。本実施形態では、この原理を利用し、ある個体Ｋの変数ｘｉを導出して解出力する。
【００１６】
図２に最適化処理の詳細な流れをフローチャートで示し、図３Ａ〜図３Ｄに探索処理のイメージ図を示している。これらの図３Ａ〜図３Ｄでは、探索空間Ｓを一次元のユークリッド空間とし、この評価関数Ｈoptが複数の極小値を備えた関数である場合にその中の最小値を探索する際の個体Ｋの移動状態のイメージ図を示している。
【００１７】
まずマイコン５は、図２のＳ１において評価関数Ｈoptに沿って個体Ｋを設定する。図３Ａには、Ｎ＝３個（Ｎ＞２）すなわち複数の個体Ｋ１〜Ｋ３を設定した状態を示している。以下、断らない限り、複数の個体Ｋ１〜Ｋ３のうちの一部又は全ての個体を個体Ｋと略して説明を行うと共に、特別な個体Ｋについては符号Ｋの後に添え字を付して説明を行う。
【００１８】
次に、マイコン５は、図２のＳ２において実効評価値Ｈeffを求め、この実効評価値Ｈeffを極小化するように個体Ｋの変数ｘｉを変化させて更新する。実効評価値Ｈeffは、前述したように複数の個体Ｋの変数ｘｉを評価関数Ｈoptに導入した評価値Ｈopt（ｘｉ）に基づく値であり、具体例としては下記のように表すことができる。
【００１９】
【数１】
2018037003.tif 000003
この（１）式のうち、Ｈeffは実効評価値を示しており、Ｈopt（ｘｉ）は評価関数Ｈoptの各個体Ｋの評価値を示している。また、ｇ／２は引力係数、ΣΣｆij（ｘｉ−ｘｊ）は引力ポテンシャルの加算値を示している。
【００２０】
（１）式の第１項は、複数の個体Ｋによる評価関数Ｈoptの評価値Ｈopt（ｘｉ）を加算した評価加算値、すなわち、評価関数Ｈoptに複数の個体Ｋの変数ｘｉを代入した評価値Ｈopt（ｘｉ）を加算した加算値を示しており、（１）式の第２項は、複数の個体Ｋ間の引力ポテンシャルｆijを加算し、この加算値に複数の個体Ｋの間に作用させる引力係数ｇ／２を乗算した引力値、を示している。この引力ポテンシャルｆijは、１つの個体Ｋが、他の全ての個体Ｋとの間で作用するように設定しても良いが、後述実施形態に示すように、全ての個体Ｋのうち一部を選定し当該選定個体Ｋを対象として引力ポテンシャルｆijを設定しても良い。また、この引力ポテンシャルｆijの関数は、後述実施形態に示すように、複数の個体Ｋ間の所謂ユークリッド距離が遠いほど引力値が大きくなる関数を適用しても良いし、ユークリッド距離に拘わらず引力値が一定値となるように設定しても良い。またこれに限られるものではなく、ユークリッド距離が遠いほど引力値が小さくなる関数を適用しても良い。マイコン５は、図２のＳ２においてこの評価加算値と引力値とを加算した実効評価値Ｈeffを導出し、実効評価値Ｈeffを小さくする個体Ｋの変数ｘｉを探索する。この探索方法としては、後述実施形態に示す補助関数法を用いることが望ましいが、極値を探索可能な方法であればどのような方法を用いて探索しても良い。
【００２１】
例えば、評価関数Ｈoptが図３Ａに示すように複数の極小値を備える関数であるときには、（１）式の第２項の引力係数ｇ／２を増加させると、個体Ｋを一点に収束させる引力が強くなり、個体Ｋは低い山から順に昇り、すなわち極大値を超えるように順に移動し、谷、すなわち極小値、を順に移動する。このため、例えば図３Ｂに示すように、個体Ｋ１は探索空間Ｓ内の変数ｘｉを例えば増加する方向に移動すると共に、個体Ｋ３は探索空間Ｓ内の変数ｘｉを例えば減少する方向に移動する。
【００２２】
次に、マイコン５は、図２のＳ３において状態更新回数ｔをインクリメントすることでｔ＝ｔ＋１とし、この状態更新回数ｔが所定上限回数τを超えたか否か、すなわち図２のＳ４においてｔ＝τ＋１であるか否かを判定する。本実施形態では、この図２のＳ４における所定上限回数τを超えたか否かの判定処理を所定の終了条件としている。マイコン５は、状態更新回数ｔが所定上限回数τ以下であり、この終了条件を満たしていないときには、Ｓ５において引力係数ｇ／２を例えば所定数だけ増加し、Ｓ２に戻り処理を繰り返す。マイコン５は、このように引力係数ｇ／２を徐々に大きくしながらＳ２〜Ｓ３の処理を繰り返すことで、図３Ｃに示すように、各個体Ｋは評価関数Ｈoptの極大値の大きな山を徐々に超えるようになる。これらの処理が繰り返されることにより、図３Ｄに示すように、複数の個体Ｋ１〜Ｋ３が評価関数Ｈoptの一点に収束するようになる。そして、マイコン５は、図２のＳ５において終了条件を満たしたときに例えば個体Ｋ１〜Ｋ３のうちの何れか一つの個体Ｋの変数ｘｉの解を出力する。これにより個体Ｋの変数ｘｉを解出力できる。
【００２３】
本実施形態によれば、引力係数ｇ／２を初期値から徐々に大きくしながら実効評価値Ｈeffが極値化するように複数の個体Ｋの変数ｘｉを変化させ、状態更新回数ｔが所定上限回数τを超えたときにおける複数の個体Ｋのうち少なくとも一つの個体Ｋに基づいて個体Ｋの変数ｘｉを導出している。またこのとき、評価関数Ｈoptの評価値が最も低くなる条件を満たす個体Ｋの変数ｘｉを解出力すると良い。これにより、変数ｘｉの最適値への到達確率を高めながら極力少ない回数で最適値へ到達できるようになる。
【００２４】
（第２実施形態）
図４から図１３は第２実施形態の追加説明図を示している。第２実施形態では、個体Ｋの変数ｘｉの初期分布の設定方法を説明する。前述実施形態に示したように、各個体ＫはＭ次元の変数ｘｉを備えているが、このＭ次元の変数ｘｉの初期分布を如何なる形態とするかに応じて、評価関数Ｈoptの谷の通過数、すなわち極値の通過数、及び、収束方法も変化する。
【００２５】
評価関数Ｈoptの評価値がどのような値で極値、最小値となるか予め把握することはできないため、マイコン５は、予め探索空間Ｓを満たすように個体Ｋを初期設定することが望ましい。個体Ｋの数を多くすれば精度が高くなるが、個体Ｋの数を多くすれば処理時間も大きくなる。このため、限られた数の個体Ｋを用いて処理を行うことが望ましく、この限られた個体Ｋの変数ｘｉの初期分布が最適値の探索処理に重要な要素を占めることになる。このためには、例えば図４から図１３に示すように、個体Ｋの変数ｘｉの初期分布を設定することが望ましい。
【００２６】
図４から図６、図８から図１３は、複数のそれぞれの個体ＫがＭ＝２次元の変数ｘｉを備えている場合の初期分布の例を示し、図７は複数のそれぞれの個体ＫがＭ＝３次元の変数ｘｉを備えている場合の初期分布の例を示している。
【００２７】
Ｍ＝２次元の探索空間Ｓを想定したときに、例えば図４に示すように、探索空間Ｓ内に複数の個体Ｋの変数ｘｉをランダムに設定すると良い。この場合、個体Ｋが一点に収束する過程において広範囲の極値を探索することができるようになる。この中でも図５の個体Ｋａ、Ｋｂに示すように、少なくとも１つ以上の個体Ｋａ、Ｋｂの変数ｘｉを探索空間Ｓの上限値又は下限値とすると良い。また、その他の個体Ｋの変数ｘｉをランダムに設定すると良い。このように設定することで、さらに広範囲の極値を探索できる。特に、探索空間Ｓの中で全ての変数ｘｉについて上限値又は下限値となるように個体Ｋａｍの変数ｘｉを設定することがさらに望ましい。
【００２８】
また、例えば図６に示すように、初期分布として探索空間Ｓを分割した格子点位置になるように個体Ｋの変数ｘｉを設定しても良い。この場合、図６にＭ＝２次元の例を示すように、隣接する個体Ｋの間を等分割して設定しても良いが、変数ｘｉ毎、すなわちｘｉ，１、ｘｉ，２毎に異なる分割数となるように設定しても良い。ここで「隣接」とはユークリッド距離が最も近い個体Ｋを意味する。また、例えば、複数の個体ＫがそれぞれＭ＝３次元の変数ｘｉを備えているときには、図７に示すように、個体Ｋが格子点位置に位置するように変数ｘｉを設定することで初期分布を構成すると良い。このように格子点位置に個体Ｋを初期分布させることで探索空間Ｓの内部における極値を網羅して探索できる。
【００２９】
さらに図８に示すように、個体Ｋの変数ｘｉが谷の生成に寄与する寄与度の高い個体Ｋの変数ｘｉ，２の分割数を寄与度の低い個体Ｋの変数ｘｉ，１よりも大きく設定するようにしても良い。寄与度は、予め実験やシミュレーション等に応じて設定したり、実際の問題に対する定性的な考察から設定する。図８の例では、変数ｘｉ，２の分割数を５とし、変数ｘｉ，１の分割数を２としている。すると、初期分布として設定する個体Ｋの数を削減しながら探索空間Ｓの内部における極値を網羅して探索できる。個体Ｋの数を削減できるため処理時間を削減できる。
【００３０】
また図９に示すように、例えば図６から図８のように設定されている場合、この中から少なくとも１つ以上の変数ｘｉが探索空間Ｓで上限値又は下限値となる個体Ｋだけを選定して設定しても良い。すると、個体Ｋの数を削減しながら広範囲において極値の探索を行うことができる。
【００３１】
また図１０に示すように、初期分布として探索空間Ｓを複数の部分空間Ｓｃ、Ｓｄに分けて各部分空間Ｓｃ、Ｓｄにそれぞれ個体Ｋを設定しても良い。このとき、各部分空間Ｓｃ、Ｓｄ毎に実効評価値Ｈeffを求め当該実効評価値Ｈeffが所定終了条件を満たしたときにおける複数の個体Ｋの少なくとも一つの個体Ｋに基づいて個体Ｋの変数ｘｉを導出するようにしても良い。これにより、より少ない個体Ｋの数で探索空間Ｓを網羅的に探索できる。この場合、部分空間Ｓｃ、Ｓｄ毎に異なる評価関数Ｈoptの最小値（最適値）を得る個体Ｋg1，Ｋg2の変数ｘｉを求めることができるが、最終的に部分空間Ｓｃ、Ｓｄ毎に得られた個体Ｋg1，Ｋg2の変数ｘｉの評価関数Ｈoptの評価値を比較し、この評価値の最小値を得る個体Ｋg1，Ｋg2の変数ｘｉを選定して解として導出すると良い。
【００３２】
これまで説明したように、収束過程において広範囲の極値を探索できるようにするため、探索空間Ｓの全てを極力網羅するように個体Ｋを広範囲に分布させることが望ましいが、例えば探索空間Ｓの内部に推定解が与えられる場合もある。
【００３３】
例えば、ある変数ｘｉが時間的に連続して変化することを考慮する。例えばマイコン５がこのような変数ｘｉ（ｔ）の解をある所定の時間毎に導出するときに、次回のタイミングにおける変数ｘｉ（ｔ＋１）の解を得るために今回の変数ｘｉ（ｔ）の解を推定解ｘizとして与えることで、次回のタイミングにおける変数ｘｉ（ｔ＋１）の解の導出処理を素早くしかも正確に行うことができる場合もある。
【００３４】
このような場合、図１１に示すように、初期分布として探索空間Ｓ内に限定された限定探索範囲Ｓａを設け、この限定探索範囲Ｓａとして推定解ｘizを含むように初期分布を設定することが望ましい。特にこの場合、例えば推定解ｘizから所定範囲（例えばｘｉ，１−α１＜変数ｘｉ，１＜ｘｉ，１＋β１、ｘｉ，２−α２＜変数ｘｉ，２＜ｘｉ，２＋β２；但し、α１、α２、β１、β２＞０）を満たすように限定探索範囲Ｓａを絞ることが望ましい。これにより、さらに少ない評価回数で変数ｘｉの最適解への到達確率を高めることができる。
【００３５】
さらに図１２に示すように、初期分布として推定解ｘizを含む空間に近いほど個体Ｋを密に分布させると共に推定解から遠ざかるほど個体Ｋの密度を減少させるように設定するようにしても良い。これにより、より少ない個体Ｋの数で変数ｘｉの最適解への到達確率を高めることができる。
【００３６】
さらに図１３に示すように、初期分布として推定解ｘizを含む空間に近い所定範囲Ｓｂ内に個体Ｋを密に分布させると共にその他の個体Ｋを所定範囲Ｓｂの外にランダムに分布させ、その他の個体Ｋのうち、少なくとも１つの個体Ｋａ、Ｋｂ、Ｋａｍの変数ｘｉを探索範囲Ｓの変数ｘｉの上限値又は下限値に設定するようにしても良い。これにより、変数ｘｉの推定解ｘizの付近を重点的に探索しながら広範囲を探索することができ、推定解ｘiz又はその周辺に解が存在していなかった場合においても、変数ｘｉの最適解への到達確率の低下を防ぐことができる。
【００３７】
（第３実施形態）
図１４から図２０Ｄは第３実施形態の追加説明図を示す。第３実施形態は、選定個体の選定方法について説明する。引力ポテンシャルｆijは（１）式に示したように、ｉ番目の個体Ｋとｊ番目の個体Ｋの差の関数として表すことができる。この場合、引力ポテンシャルｆijは、全ての２つの個体Ｋの組み合わせ数分の差分を求めて加算値を求めるようにすると良い。しかし図１４に示すように、多数の個体Ｋが一の谷Ｈ１の中で密に分布すると共に、他の個体Ｋｃが他の谷Ｈ２の中で疎に分布しているときには、密度が密に分布している谷Ｈ１の中の多数の個体Ｋの影響を受けやすくなる。
【００３８】
すると、図１４の矢印Ｙに示すように、本来評価値が最小値となり変数ｘｉが最適値となる個体Ｋｃが、他の多数の個体Ｋの影響を受けて谷Ｈ２を抜け出してしまうことがある。また例えば第２実施形態に初期分布を示したように、個体Ｋの密度がそのある所定の領域、空間毎にばらつくこともある。
【００３９】
このような場合を考慮し、全ての２つの個体Ｋの組み合わせに引力ポテンシャルｆijを与えてしまうと、個体Ｋの密度分布の影響が強くなることが想定されるような条件（例えば、評価関数Ｈoptの条件、又は／及び、個体Ｋの密度の初期分布の条件）を用いるときには、引力ポテンシャルｆijを与える個体Ｋを選定し、特定の選定個体Ｋの間にだけ引力ポテンシャルｆijを与えることが望ましい。
【００４０】
この場合、図１５に変数Ｍ＝１次元の例を示すように、マイコン５が特に複数の個体Ｋに対し識別符号（例えば１〜５）を順序付けて付し、順序が隣接する識別符号が付された個体Ｋを選定個体Ｋ１−Ｋ２、Ｋ２−Ｋ３、Ｋ３−Ｋ４、Ｋ４−Ｋ５として引力ポテンシャルｆijを導出し、順序が隣接しない識別符号が付された個体Ｋを選定個体とせず引力ポテンシャルｆijを０とすると良い。すると個体Ｋの密度の影響を強くしすぎることなく収束させることができる。
【００４１】
また、マイコン５が全個体Ｋに対し引力ポテンシャルｆijを対等に印加するためには、図１６に示すように、個体Ｋ１と個体Ｋ５との間にも引力ポテンシャルｆijを印加するようにすると良い。なお図１５及び図１６には個体Ｋの変数ｘｉの小さい順に識別符号１〜５を付した形態を示しているが、変数ｘｉの小さい順に識別符号１〜５を付して並べる必要はなく、識別符号１〜５を付す順序は変数ｘｉの大小に影響するものではない。
【００４２】
また図１７にＭ＝２次元の選定個体Ｋの例を示す。この図１７は図６のように探索空間ＳにおけるＭ＝２次元の格子点位置に個体Ｋを初期分布させたときの選定個体の例を示す。また図１８に変数Ｍ＝３次元の例を示す。この図１８は図７のようにＭ＝３次元の格子点位置に個体Ｋを初期分布させたときの選定個体の例を示す。
【００４３】
マイコン５は、格子点位置の個体Ｋと隣接する格子点位置の最大２×Ｍ個の個体Ｋを選定個体として引力ポテンシャルｆijを導出し、その他の個体Ｋを選定個体とせず引力ポテンシャルｆijを０とすることが望ましい。図１７に示すように、個体Ｋｄ１に隣接する格子点位置に存在する個体Ｋｄ２〜Ｋｄ５を選定個体として引力ポテンシャルｆijを設定し、その他の個体Ｋを選定個体としないように引力ポテンシャルｆijを０に設定する。すなわち、個体ＫがそれぞれＭ＝２次元の変数ｘｉを備えるときには、最大２×Ｍ＝４個の隣接する格子点位置の個体Ｋを選定個体として引力ポテンシャルｆijを導出する。
【００４４】
また、図１８に示すように、個体ＫがそれぞれＭ＝３次元の変数ｘｉを備えるときには、最大２×Ｍ＝６個の格子点位置の個体Ｋを選定個体として引力ポテンシャルｆijを導出する。
【００４５】
また図１９には図９に示すようにＭ＝２次元の格子点位置の上限値又は下限値に個体Ｋを初期分布させたときの選定個体Ｋの例を示す。マイコン５は、これらの個体Ｋのうち隣接する２個の個体Ｋを選定個体として引力ポテンシャルｆijを導出し、その他の個体Ｋを選定個体とせず引力ポテンシャルｆijを０とする。図１９に示すように、マイコン５が例えば初期分布として複数の個体Ｋを探索範囲Ｓの変数ｘｉの上限値又は下限値に設定した場合には、探索空間Ｓにおいて変数ｘｉが上限値又は下限値となる個体Ｋａｍ、Ｋａ、Ｋｂから順次収束させることができる。すると探索空間Ｓを網羅して探索できる。
【００４６】
＜評価関数Ｈoptを考慮しない場合における初期分布からの個体Ｋの移動イメージ＞
図２０Ａから図２０Ｄに個体Ｋの移動イメージを示している。図２０Ａに初期分布を示している。この初期分布は、図１９に示す初期分布と同様であるが、改めて説明すると、全個体Ｋは、変数ｘｉ，１及びｘｉ，２が共に探索空間Ｓの上限値又は下限値となる頂点に設定された個体Ｋａｍ、変数ｘｉ，２が探索空間Ｓの上限値又は下限値となる辺部に設定された個体Ｋａ、変数ｘｉ，１が探索空間Ｓの上限値又は下限値となる辺部に設定された個体Ｋｂ、からなっている。すなわち、全個体Ｋａ、Ｋｂ、Ｋａｍは、それぞれ２次元の変数ｘｉ、１、ｘｉ、２の何れかの変数ｘｉが上限値又は下限値となるように設定されている。
【００４７】
隣接する個体Ｋは、２次元の変数ｘｉ、１、ｘｉ、２が等間隔で初期設定されている。そして、この例では、隣接する個体Ｋａ、Ｋｂ、Ｋａｍを選定個体として引力ポテンシャルｆijを印加するようにしている。なお、説明を単純化するため評価関数Ｈoptは考慮しない例を示す。
【００４８】
この例の場合、矢印を付した隣接した選定個体Ｋａ、Ｋｂ、Ｋａｍの間に引力がかかるため、隣接する個体Ｋａ、Ｋｂ、Ｋａｍは当該引力を合成したベクトル方向に引き寄せられることになる。このため、まず図２０Ｂに示すように、探索空間Ｓの頂点に初期設定された個体Ｋａｍが、探索空間Ｓの内方に引き込まれるように移動する。さらに図２０Ｃに示すように、探索空間Ｓの辺部に初期設定された個体Ｋａ、Ｋｂが探索空間Ｓの内方に引き込まれるように移動する。
【００４９】
さらに図２０Ｄに示すように、全個体Ｋａ、Ｋｂ、Ｋａｍが徐々に探索空間Ｓの中央内側に引き込まれるように移動する。これにより全個体Ｋａ、Ｋｂ、Ｋａｍがそれらの２変数ｘｉ，１、ｘｉ，２が互いに同一となる一点に収束するようになる。この例では、評価関数Ｈoptを考慮していない例を挙げているため、最終的には探索空間Ｓの中央に収束することになるが、実際に評価関数Ｈoptを考慮すれば、変数ｘｉに応じた評価値Ｈopt（ｘｉ）が実効評価値Ｈeffに反映されるため、この実効評価値Ｈeffを最小化するように個体Ｋａ、Ｋｂ、Ｋａｍが移動する。すなわち個体Ｋａ、Ｋｂ、Ｋａｍのそれぞれの変数ｘｉが変化する。これにより、これらの全探索空間Ｓにおいて変数ｘｉの最適値を網羅的に探索できることがわかる。
【００５０】
（第４実施形態）
以下、第４実施形態を説明する。この第４実施形態では、引力ポテンシャルｆijの設定方法について説明する。引力ポテンシャルｆijは（１）式に示したように、ｉ番目の個体Ｋとｊ番目の個体Ｋの差分の関数として表すことができる。この場合、引力ポテンシャルｆijは、ｉ番目の個体Ｋのｐ番目の変数をｘｉ，ｐと表したときに、例えば下記の（２）式に基づいて導出することが望ましい。
【００５１】
【数２】
2018037003.tif 000004
この（２）式の引力ポテンシャルｆijは、複数の個体Ｋの間のユークリッド距離が大きいほど大きな引力値とするように設定され、複数の個体Ｋの間の距離が小さいほど小さな引力値とするように設定される。この場合、初期分布として広範囲に分布させた個体Ｋを素早く収束させることができ、例えば図２に示すように処理を実行したときには、状態更新回数ｔの所定上限回数τを少なくしても十分に収束させることができる。しかも、この式は微分可能な関数となるため、微分値を０とするように実効評価値の変数ｘｉを求めることで容易に極値化できる。
【００５２】
また、引力ポテンシャルｆijを例えば下記の（３）式に基づいて導出するようにしても良い。
【００５３】
【数３】
2018037003.tif 000005
この（３）式の引力ポテンシャルｆijは、複数の個体Ｋの間の距離に関係なく一定の引力値とするように設定していることを示している。この場合、浅い谷、すなわち極大値を順に超えて収束させることができるようになる。
【００５４】
（第５実施形態）
図２１〜図２６は第５実施形態の追加説明図を示す。本実施形態では、実効評価値Ｈeff（ｘｉ）を極小化するように個体Ｋの変数ｘｉを変化させるための具体例となる補助関数法について説明する。補助関数法は、（１）式の第１項の評価加算値、第２項の引力値を極小化するときに用いられる一方法であり、評価関数Ｈoptを当該評価関数Ｈoptに近似した２次関数に置換し、この置換した２次関数に基づいて極値化する方法を示している。
【００５５】
以下、補助関数法について詳細説明する。補助関数法の詳細イメージを図２１に示している。図２１に示すように、変数ｘの評価関数をｆmej（ｘ）としたときに、この評価関数ｆmej（ｘ）の変数ｘに現在の解候補ｘ＾＊（図２１ではｘａ、ｘｂ）を代入し、この評価値ｆmej（ｘ＾＊）を通過すると共に、その微分値が評価関数の偏微分値∂ｆmej（ｘ＾＊）／∂ｘと等しく、且つ、その解候補ｘ＾＊を含む探索空間Ｓ内の全ての変数ｘｉにおける評価値ｆmej（ｘｉ）よりも大きな値を得る条件を満たすリプシッツ定数Ｌを用いた２次関数ｆｆを導入する。この２次関数ｆｆを数式化すると、（４−１）式の右辺のように示すことができる。また、この２次関数ｆｆが極値となる条件を満たす解をｘｚとすると（４−２）式のように導出できる。
【００５６】
【数４】
2018037003.tif 000006
これらの（４−１）式、（４−２）式において、Ｌはリプシッツ定数を示し、ｘ＾＊はｘの現在の解候補を示している。なお（４−２）式の右辺を微分すると（４−３）式のように導出できる。
【００５７】
【数５】
2018037003.tif 000007
このとき、変数ｘに解候補ｘ＾＊を代入することで（４−３）式の第２項を０にでき、現在の解候補ｘ＾＊における微分値は（４−３）式の第１項と等しくなる。この（４−３）式の第１項は、解候補ｘ＾＊における評価関数ｆmejの偏微分値∂ｆmej（ｘ＾＊）／∂ｘに一致する。また、この２次関数ｆｆは、解候補ｘ＾＊を含む全ての変数ｘｉで評価関数ｆmejの評価値ｆmej(ｘｉ)よりも大きな値となっている。このような２次関数ｆｆを用いて評価関数ｆmejの極値を求めることが望ましい方法となる。
【００５８】
（４−２）式に示すように、解候補ｘｚを繰り返し導出する。図２１に示すように、現在の解候補をｘａとしたときに、まず２次関数ｆｆ１を探索し、２次関数ｆｆ１の極値を満たす解を次回の解候補ｘｂとする。その後、この次回の解候補ｘｂについて再度２次関数ｆｆ２の探索を行い、２次関数ｆｆ２の極値を満たす解を解候補ｘｃに更新する。したがって解候補はｘａ→ｘｂ→ｘｃとなるように変化する。これらの処理が、例えば所定回数以上繰り返されることで評価関数ｆmej（ｘ）の極小値と見做すことが可能な解（例えばｘｃ）を得ることができる。
【００５９】
さて（１）式に（２）式の引力ポテンシャルｆijを代入すると下記の（５）式のように示すことができる。この（５）式における引力ポテンシャルｆijの関数は、第４実施形態に示したように、距離を大きくしたときに引力値を大きくする（２）式の関数を適用している。
【００６０】
【数６】
2018037003.tif 000008
ここでは、説明を理解しやすくするため、引力ポテンシャルｆijを印加する個体Ｋとして、第２実施形態の図１５に示したように、識別番号の隣接する個体Ｋ１−Ｋ２、Ｋ２−Ｋ３、…、を選定個体としている。すなわち、ｉ番目とｉ＋１番目の個体Ｋを選定して引力ポテンシャルｆijを印加する数式を示している。ここでは、この例について説明するが、第２、第３実施形態で説明したその他の例も同様に組み合わせることが可能である。
【００６１】
この（５）式の右辺において、評価関数Ｈoptを表す第１項と、引力係数ｇ／２×引力ポテンシャルｆijを表す第２項とに分けて補助関数法を適用する。（５）式の右辺の第１項について、補助関数法を適用して置換すると（６）式の右辺のようになる。
【００６２】
【数７】
2018037003.tif 000009
この（６）式の右辺は、ｊ番目の個体Ｋにおけるｑ番目の変数ｘｊ，ｑを更新する場合に、（５）式の右辺の第１項について補助関数法を適用した数式を示している。また、（５）式の右辺の第２項を補助関数法を適用して置換すると（７）式の右辺のようになる。
【００６３】
【数８】
2018037003.tif 000010
この（７）式の右辺も同様に、ｊ番目の個体におけるｑ番目の変数ｘｊ，ｑを更新する場合において、（５）式の右辺の第２項について、補助関数法を適用した数式を示している。このような（６）式と（７）式を加算した加算値を極小化した条件を満たす変数ｘｉを最終的に解出力することになる。
【００６４】
リプシッツ定数Ｌは大きすぎると、（４−１）式の不等式を満たすことになるものの、２次係数が比較的大きくなることから、図２２に２次関数ｆｆのイメージを示すように、解の更新処理の幅が小さくなりすぎる。このため、評価関数Ｈoptの谷Ｈ２の極値に到達するまでの処理ステップが多くなり処理時間が長くなる。
【００６５】
逆に、リプシッツ定数Ｌが小さすぎると（４−２）式の不等式を満たさなくなり、図２３に２次関数ｆｆのイメージを示すように、解の更新処理の幅が大きくなりすぎる。すると、１ステップの処理だけで隣接する谷Ｈ１に移動してしまうことが確認されている。
【００６６】
このため、リプシッツ定数Ｌは、変数ｘｉの解を更新する度に計算し直すと共に、式（４−１）の不等式を満たす中で可能な限り小さい値を設定すると良いが、特に（５）式の右辺の第２項に補助関数法を適用するときには、（７）式に示すようにリプシッツ係数Ｌを４に固定することが望ましい。このリプシッツ係数Ｌ＝４は変数ｘｉの解を更新処理する度に導出し直す必要がないことが発明者らにより確認されている。このとき特に、第２項におけるｊ番目の個体におけるｑ番目の変数の更新後の解ｘj,qは（８）式のように導出できる。
【００６７】
【数９】
2018037003.tif 000011
この（８）式に示したｊ番目以外の個体Ｋについても、ｑ番目の変数ｘ≠ｊ，ｑの更新処理を同じように行うことができ、１からＮ番目の個体Ｋのｑ番目の変数ｘｊ，ｑは、（９−１）式のように行列式を用いて一括更新できる。ただし、変数行列ｘｑ、リプシッツ係数行列Ｌｑ、引力係数行列Ｇ、評価関数偏微分行列∇ｑＨoptは、それぞれ（９−２）式、（９−３）式、（９−４）式、（９−５）式に示すように表すことができる。
【００６８】
【数１０】
2018037003.tif 000012
【００６９】
【数１１】
2018037003.tif 000013
【００７０】
【数１２】
2018037003.tif 000014
このようにして更新処理を行うことができる。
【００７１】
また、評価関数Ｈoptに補助関数法を適用し、第２項の引力値に補助関数法を用いなくても良い。すなわち、ｊ番目の個体のｑ番目の変数ｘｊ，ｑを更新するときに評価関数Ｈoptだけに補助関数法を適用すると、（５）〜（７）式に対応した実効評価値Ｈeffは（９−６）式のように表すことができる。
【００７２】
【数１３】
2018037003.tif 000015
このとき（９−６）式を極値化するには、（９−７）式に示すように変数ｘｊ，ｑにより偏微分した微分値が０となる条件を満たすように更新すると良い。
【００７３】
【数１４】
2018037003.tif 000016
他の個体Ｋのｑ番目の変数ｘｊ，ｑを一般化して考慮すると、（９−８）式のように表すことができる。
【００７４】
【数１５】
2018037003.tif 000017
この式を変数ｘｑについて解くと、（９−９）式のように表すことができる。
【００７５】
【数１６】
2018037003.tif 000018
この（９−９）式を適用すると、「（Ｌ＋ｇＧ）＾（−１）」に含まれるＧは正則行列ではないため、引力係数ｇ／２を大きくした場合にＧの特異性によって逆行列の計算精度が大幅に低下する。このため、前述したように、評価関数Ｈoptの評価値と共に引力値についても補助関数法を適用することが望ましい。すると、マイコン５を用いたとしても、（９−１）式に基づいて計算処理することになり、（９−９）式における（Ｌ＋ｇＧ）＾−１の逆行列を算出しなくても良くなり、計算精度を高めることができる。
【００７６】
このような最適化処理のフローチャートを図２４に示している。図２４に示すように、マイコン５はまずＳ１において探索空間Ｓ内に複数の個体Ｋを設定する。このとき、例えば第２実施形態に示したように個体Ｋを設定して初期分布を構成すると良い。マイコン５は、引力係数ｇ／２を初期値＝０とすることで実効評価値Ｈeff＝（１）式の右辺の第１項（＝複数の個体Ｋの評価関数Ｈoptの評価値）となるように初期設定する。そして、マイコン５はＳ２ａにおいて補助関数法を示す（８）式を用いて個体Ｋの全変数ｘｉを更新する。
【００７７】
このＳ２ａの処理は、このタイミングで複数回行うようにしても良い。そして、マイコン５は、Ｓ４にて所定の終了条件を満たすまで、Ｓ５において複数の個体Ｋの間の引力係数ｇ／２を徐々に増加させることで引力値を徐々に強くする。すると、これらのＳ２ａ〜Ｓ５の処理を繰り返すことで広範囲に散らばった個体Ｋは１カ所に収束することになる。引力値を増加するタイミングは、Ｓ２ａにおいて補助関数法を用いた更新処理を１回だけ実行した後でも良いし、Ｓ２ａの処理について実効評価値Ｈeffの極値を得られることが想定される回数だけ繰り返し実行した後であっても良い。
【００７８】
また、終了時点における個体Ｋの数は必ずしも１カ所の所定領域に収束して極値化している必要はないものの、引力により個体Ｋを収束させることによる優位性を活用するために、処理後には初期分布における個体Ｋの分散範囲よりも狭い所定範囲内に収束していることが望ましい。
【００７９】
＜具体例＞
発明者は評価関数Ｈoptを具体的な数式とした実例に合わせて最適値を導出するシミュレーションを行っている。以下ではこの具体例を説明する。評価関数Ｈoptを下記の（１０−１）式と定義した。ただし、ｆ（ｘ）は（１０−２）式、ｇ（ｘ）は（１０−３）式とし、ωは（１０−４）式としている。
【００８０】
【数１７】
2018037003.tif 000019
この評価関数Ｈoptは、Ｍ＝１次元の変数ｘに応じた関数とされており、図２５に示すように、複数の極小値を有する関数である。このとき図２６に示したように、（１０−１）式、（１０−２）式、（１０−３）式、（１０−４）式の定数ｘｍ、ａ、Ｐ、Ａ、Ｂ、Ｃを設定している。このように定数ｘｍ、ａ、Ｐ、Ａ、Ｂ、Ｃを設定することで、評価関数Ｈoptは、特に変数ｘの探索範囲（探索空間Ｓ）を−５．０≦ｘ≦５．０としたときに、最適解が変数０．５となる関数を示す。
【００８１】
また図２６に示したように、状態更新回数ｔの所定上限回数τを１００とし、個体Ｋの数Ｎを１０とし、図２４のＳ２ａに示すように、補助関数法を適用した処理を実行した。また図２４の処理ステップＳ５において、引力係数ｇ／２を増加させているが、下記の（１０−５）式のように状態更新回数ｔの増加に応じて引力係数ｇ／２を増加するように設定した。
【００８２】
【数１８】
2018037003.tif 000020
（１０−５）式のｇmax／２は引力係数ｇ／２の最大値を示す。図２７には、引力係数ｇ／２の最大値ｇmax／２を横軸とし、収束成功したと見做すことが可能なシミュレーション回数を全シミュレーション回数で除して導出された成功確率を縦軸として示している。
【００８３】
ここでは、少なくとも一つの個体Ｋの変数ｘｉが、最適解ｘ＝０．５の谷Ｈｙに含まれていることを成功条件としてカウントしている。ここでいう谷Ｈｙとは、図２５に示すように評価関数Ｈoptの評価値が最適解ｘ＝０．５の評価値からその高低両側の極大値に至るまでの範囲となることを満たす領域を示している。したがって、収束後において、少なくとも一つの個体Ｋの変数ｘｉが谷Ｈｙに対応した領域内に含まれることを成功と見做している。
【００８４】
図２７に示した結果を考慮すると、成功確率はｇmax／２に依存することがわかる。図２７の範囲ｇａに示すように、引力係数ｇ／２の最大値ｇmax／２を小さくしすぎると、引力値が弱く個体Ｋが収束する可能性は低くなり成功確率は比較的低くなる。この方法は所謂並列勾配法に類似した方法となる。逆に、引力係数ｇ／２の最大値ｇmax／２を大きくしすぎると、図２７の範囲ｇｂに示すように、評価関数Ｈoptを無視して収束することになり成功確率が低下する。このため、引力係数ｇ／２の最大値ｇmax／２をそれらの範囲ｇａ、ｇｂとはならないある所定範囲ｇｃに設定することで成功確率を極力上げることができる。特に、引力係数ｇ／２の最大値ｇmax／２を範囲ｇｃの中でも特定の範囲ｇｄに設定することで９０％近い成功確率を達成できることを確認できた。
【００８５】
図２８は、全ての個体Ｋが最適解に含まれないように初期分布を構成し、当該個体Ｋの変数ｘｉが、ある一点に収束する過程で最適解を含む谷Ｈｙに対応した所定領域ｘｘに収束する様子について状態更新回数ｔを横軸として示している。前述したように、この図２８に示す所定領域ｘｘに収束後の個体の変数ｘが１つでも入力していれば成功と見做す。
【００８６】
個体Ｋが収束過程における広範囲を探索処理することで評価関数Ｈoptの極値をくまなく探索できるようになる。
しかも図２５に示しているように、評価関数Ｈoptが変数ｘ≒−０．５〜１．５の領域において極値を多数有する関数であったとしても、図２８に示すように最適解＝０．５を含む谷Ｈｙに対応した領域ｘｘ内に個体Ｋを収束させることができることを確認できた。
【００８７】
（第６実施形態）
図２９は第６実施形態の追加説明図を示している。第６実施形態は、収束後の処理を示す。例えば図２又は図２４に示す処理を実行し、状態更新回数ｔを所定上限回数τまで繰り返したときに実効評価値Ｈeffが極値化している場合であっても、図２９に示すように個体Ｋが最適値を含む谷Ｈｙ１の１カ所に収束せず、他の谷Ｈｙ２等に位置していることがあり、この結果、何れの個体Ｋの変数ｘｉを解出力するか定めることができない場合がある。
【００８８】
（１）式を考慮すれば明らかなように、実効評価値Ｈeffが極値とされていたとしても、複数の個体Ｋの間に引力を生じている状態で釣り合っていることになるため、ある個体Ｋの変数ｘｉを評価関数Ｈoptに代入してもその評価関数Ｈoptの評価値が必ずしも極値とはならないことが多い。このため、マイコン５は最終段階の処理として（１）式の第２項の引力係数ｇ／２を０とし、実効評価値Ｈeffとして第１項の評価関数Ｈoptの評価値そのものの極値を導出することが望ましい。
【００８９】
例えば図２９に示すように、複数の個体Ｋがそれぞれ複数の谷Ｈｙ１、Ｈｙ２に位置している場合には、例えば前述の補助関数法を用いて極値化することで、複数の個体Ｋがそれぞれ対応した複数の谷Ｈｙ１、Ｈｙ２の極値に移動することになる。
【００９０】
これらの複数の個体Ｋの中で、変数ｘｉを（１）式の第１項に代入した実効評価値Ｈeffが最小値を満たす個体Ｋの変数ｘｉを解として出力することが望ましい。これにより、変数ｘｉの最適値を導出できる。しかも、個体Ｋが１カ所に収束していない場合であっても、評価関数Ｈoptが極値となる変数ｘｉを確実に得ることができる。
【００９１】
本実施形態に係る処理を適用すれば、前述実施形態又はそれらの実施形態を組み合わせた方法をしたときに必ずしも１カ所の谷（例えばＨｙ１）に収束している必要がなくなり、少なくとも１つの個体Ｋが変数ｘｉの最適解を含む谷Ｈｙ１に収束していればよくなる。このため、この処理を用いていない方法に比較して、例えば所定上限回数τを少なく設定できるようになる。
【００９２】
（第７実施形態）
図３０から図３２は第７実施形態の追加説明図を示している。この第７実施形態では探索開始前に予め推定解が与えられる例を示す。
【００９３】
例えば、車両用の運転支援装置１０１は、交通状況やその変化、事故防止への対応のために近年活発に開発されており、特にドライバーへの運転負担を軽減するために開発されている。例えば運転支援装置１０１は、図３０に示すように、制御器１０２を備え、位置検出器１０３、速度センサ１０４、地図情報取得部１０５、等を接続して構成され、未来時刻における最適移動位置を通過する最適経路を最適化する最適化装置として構成される装置である。
【００９４】
制御器１０２は、例えばＣＰＵ１０６、ＲＯＭ、ＲＡＭ、ＥＥＰＲＯＭなどのメモリ１０７、及び、Ｉ／Ｏ１０８を備えたマイクロコンピュータ１０９を主として構成され、モデル予測制御処理に関するプログラムがメモリ１０７に記憶されている。運転支援装置１０１は、制御器１０２により実現される機能ブロックとして、図示しないが、図１Ｂと同様の設定部６、極値化部７、導出部８としての機能を備える。
【００９５】
位置検出器１０３は、例えばＧＰＳ（Global Positioning System）等を用いて現在位置の情報を検出する。速度センサ１０４は移動体Ｃの移動速度を検出する。地図情報取得部１０５は、所定の記憶装置（例えばＨＤＤ）に予め記憶される地図情報、又は、外部の地図サーバから地図情報を取得する。制御器１０２は、メモリ１０７に記憶されたモデル予測制御処理のプログラムを実行することにより、位置検出器１０３から取得される現在位置情報、速度センサ１０４から取得される移動体Ｃの移動速度情報、及び、地図情報取得部１０５により取得される地図情報に基づいてモデル予測制御を行う。なお、その他のセンサ、例えば車両周辺の障害物Ｏｂ１、Ｏｂ２を検知するための超音波センサ、車両周辺の障害物Ｏｂ１、Ｏｂ２との距離を測定するための測距装置、などにより取得される各種情報を用いてモデル予測制御を行っても良い。
【００９６】
このモデル予測制御技術は、未来予測を行う技術であり、未来を含む一定期間の最適制御を行い、これらの最適制御を所定の時間毎に更新する技術である。運転支援装置１０１は、モデル予測制御技術を用いることで未来を含む一定期間における移動体（例えば自動車）Ｃの最適な走行経路を導出したり、障害物Ｏｂ１、Ｏｂ２に衝突することなく所定の駐車スペースに導くように支援できる。
【００９７】
このような運転支援装置１０１の制御器１０２が、障害物Ｏｂ１、Ｏｂ２への衝突を避けながら経路探索処理を行うときには、図３１に鳥瞰図を示すように、現在時刻ｔ０から未来時刻ｔ１〜ｔ６までの一定期間ｔ０〜ｔ６における移動体Ｃの最適経路Ｒ０を導出することで時刻ｔ１における最適移動位置Ｌ１を決定する。
【００９８】
図３２に時刻ｔ１におけるモデル予測制御処理を鳥瞰図で示している。図３２に示すように、運転支援装置１０１の制御器１０２は、時刻ｔ１において新たに現在時刻ｔ１以降における未来時刻ｔ２〜ｔ７における最適経路Ｒ１を導出するが、時刻ｔ１における最適経路Ｒ１は、時刻ｔ０における最適経路Ｒ０と近い軌跡となることが考えられる。
【００９９】
このため、制御器１０２は、例えば時刻ｔ１〜ｔ６に対応した位置Ｌ１〜Ｌ６による最適経路Ｒ０を推定解とし、この推定解に基づいて第２実施形態に示したように、例えばこの最適経路Ｒ０を含む領域に近いほど個体Ｋを密に分布させると共に当該最適経路Ｒ０から遠ざかるほど密度を減少させるように個体Ｋを設定して初期分布を構成する。すると、少ない探索回数で最適解に到達する確率を高めることができるようになる。
【０１００】
本実施形態によれば、制御器１０２が、未来時刻ｔ２〜ｔ７における移動体Ｃの最適経路Ｒ１を導出するときには、過去の最適経路Ｒ０を推定解とし、初期分布として最適経路Ｒ０を含む領域に近いほど個体Ｋを密に分布させると共に最適経路Ｒ０から遠ざかるほど個体Ｋの密度を減少させる。これにより、少ない探索回数で最適解に到達する確率を高めることができる。
【０１０１】
（他の実施形態）
本発明は、上記した実施形態に限定されるものではなく、以下のように変形又は拡張することができる。
【０１０２】
前述実施形態では、個体Ｋの変数ｘｉを解出力する形態を説明しているが、変数ｘｉに対応した評価値、すなわち、解出力すべき変数ｘｉを評価関数Ｈoptに代入した評価値を解出力するようにしても良い。また、引力ポテンシャルｆijに基づく引力値を０にする前の変数ｘｉを導出し、この変数ｘｉをそのまま解出力しても良いし、第６実施形態で説明したように、引力値を０にした後の変数ｘｉの最適値を導出して解出力しても良い。また、この変数ｘｉの最適値を評価関数Ｈoptに代入した評価値を導出し解出力しても良い。このような各種値を導出する場合に適用しても良い。
【０１０３】
評価関数Ｈoptが極小値、最小値となる条件を満たす変数ｘｉを最適値として解出力する形態を示したが、極大値、最大値となる条件を満たす変数ｘｉを最適値として解出力する形態に適用しても良い。
【０１０４】
所定の終了条件として、状態更新回数ｔが所定上限回数τを上回るか否かを条件としているが、これに限定されるものではなく、例えば変数ｘｉを代入した評価関数Ｈoptの評価値が所定値以下となっているか、などの異なる条件を用いても良い。
【０１０５】
引力係数ｇ／２を初期値＝０から徐々に大きくする形態を示したが、初期値は０に限られない。
また、特許請求の範囲に記載した括弧内の符号は、本発明の一つの態様として前述する実施形態に記載の具体的手段との対応関係を示すものであって、本発明の技術的範囲を限定するものではない。前述実施形態の一部を、課題を解決できる限りにおいて省略した態様も実施形態と見做すことが可能である。また、特許請求の範囲に記載した文言によって特定される発明の本質を逸脱しない限度において、考え得るあらゆる態様も実施形態と見做すことが可能である。
【０１０６】
また本発明は、前述した実施形態に準拠して記述したが、本発明は当該実施形態や構造に限定されるものではないと理解される。本発明は、様々な変形例や均等範囲内の変形をも包含する。加えて、様々な組み合わせや形態、さらには、それらに一要素、それ以上、あるいはそれ以下、を含む他の組み合わせや形態をも、本開示の範畴や思想範囲に入るものである。
【符号の説明】
【０１０７】
図面中、１は最適化装置、１０１は運転支援装置（連続値最適化問題の大域的探索装置）、１０２は制御器、６は設定部、７は極値化部、８は導出部、Ｋは個体、Ｓは探索空間、ｘｉは変数、ｇ／２は引力係数、Ｈoptは評価関数、Ｈeffは実効評価値、ｘizは推定解、を示す。
【図１Ａ】
2018037003.tif 000025
【図１Ｂ】
2018037003.tif 000026
【図２】
2018037003.tif 000027
【図３Ａ】
2018037003.tif 000028
【図３Ｂ】
2018037003.tif 000029
【図３Ｃ】
2018037003.tif 000030
【図３Ｄ】
2018037003.tif 000031
【図４】
2018037003.tif 000032
【図５】
2018037003.tif 000033
【図６】
2018037003.tif 000034
【図７】
2018037003.tif 000035
【図８】
2018037003.tif 000036
【図９】
2018037003.tif 000037
【図１０】
2018037003.tif 000038
【図１１】
2018037003.tif 000039
【図１２】
2018037003.tif 000040
【図１３】
2018037003.tif 000041
【図１４】
2018037003.tif 000042
【図１５】
2018037003.tif 000043
【図１６】
2018037003.tif 000044
【図１７】
2018037003.tif 000045
【図１８】
2018037003.tif 000046
【図１９】
2018037003.tif 000047
【図２０Ａ】
2018037003.tif 000048
【図２０Ｂ】
2018037003.tif 000049
【図２０Ｃ】
2018037003.tif 000050
【図２０Ｄ】
2018037003.tif 000051
【図２１】
2018037003.tif 000052
【図２２】
2018037003.tif 000053
【図２３】
2018037003.tif 000054
【図２４】
2018037003.tif 000055
【図２５】
2018037003.tif 000056
【図２６】
2018037003.tif 000057
【図２７】
2018037003.tif 000058
【図２８】
2018037003.tif 000059
【図２９】
2018037003.tif 000060
【図３０】
2018037003.tif 000061
【図３１】
2018037003.tif 000062
【図３２】
2018037003.tif 000063