図面 (/)

技術 連続値最適化問題の大域的探索装置及びプログラム

出願人 株式会社デンソー国立大学法人京都大学
発明者 岡田俊太郎寺部雅能大関真之
出願日 2016年9月2日 (4年10ヶ月経過) 出願番号 2016-171776
公開日 2018年3月8日 (3年4ヶ月経過) 公開番号 2018-037003
状態 特許登録済
技術分野 学習型計算機 フィードバック制御一般
主要キーワード 引力ポテンシャル 移動イメージ 終了判定条件 分散範囲 変数行列 未来時刻 有理関数 成功条件
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2018年3月8日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題

複数の極値を備えた評価関数最小値又は最大値を探索するときに、変数最適値への到達確率を高めながら極力少ない回数で最適値へ到達できるようにした最適化装置及び最適化プログラムを提供する。

解決手段

複数の個体Kの変数xiを探索空間S内の評価関数Hoptに沿って設定する(S1)。また、設定された複数の個体Kのうち少なくとも2つ以上の選定個体Kに引力を作用させる引力ポテンシャルfijを導出し、複数の個体Kによる評価関数Hoptの評価値加算した評価加算値、及び、導出された選定個体K間の引力ポテンシャルfijを加算しこの加算値に選定個体Kの間に作用させる引力係数g/2を乗算した引力値、を加算した実効評価値Heffを極値化する。さらに、引力係数g/2を初期値から徐々に大きくしながら実効評価値Heffが極値化するように複数の個体Kの変数xiを変化させる(S2,S5)。

概要

背景

例えば、多次元探索空間において変数、すなわちパラメータ最適値を求める手法が提案されている(例えば、特許文献1参照)。特許文献1記載の技術によれば、探索空間内に最適値算出対象のパラメータを要素とする複数の個体を生成し、これらの個体の評価値を算出し、個体の中から評価値の悪い個体を選択している。そして、この選択された個体を評価値の良い個体に所定の割合で近づけている。また、評価値の悪い個体を最良の評価値の個体から一定のユークリッド距離内にある任意の領域に移動させている。そして、より良い評価値の個体を選択し最良の評価値の個体を随時更新し、複数の個体の評価値を収束させ、終了判定条件を満たしたと判定した時点で最良の評価値を有する個体に含まれるパラメータをパラメータの最適値として出力している。

概要

複数の極値を備えた評価関数最小値又は最大値を探索するときに、変数の最適値への到達確率を高めながら極力少ない回数で最適値へ到達できるようにした最適化装置及び最適化プログラムを提供する。複数の個体Kの変数xiを探索空間S内の評価関数Hoptに沿って設定する(S1)。また、設定された複数の個体Kのうち少なくとも2つ以上の選定個体Kに引力を作用させる引力ポテンシャルfijを導出し、複数の個体Kによる評価関数Hoptの評価値を加算した評価加算値、及び、導出された選定個体K間の引力ポテンシャルfijを加算しこの加算値に選定個体Kの間に作用させる引力係数g/2を乗算した引力値、を加算した実効評価値Heffを極値化する。さらに、引力係数g/2を初期値から徐々に大きくしながら実効評価値Heffが極値化するように複数の個体Kの変数xiを変化させる(S2,S5)。

目的

本発明の目的は、複数の極値を備えた評価関数の最小値又は最大値を探索するときに、変数の最適値への到達確率を高めながら極力少ない回数で最適値へ到達できるようにした連続値最適化問題大域的探索装置及びプログラムを提供する

効果

実績

技術文献被引用数
1件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

1以上の次元を備えた探索空間(S)に複数の極値を備える評価関数(Hopt)に個体(K)を設定することに基づいて個体の変数(xi)または変数の最適値導出する連続値最適化問題大域的探索装置(1、101)であって、複数の個体の変数を前記探索空間の中の評価関数に沿って設定する設定部(6)と、前記設定部により設定される複数の個体のうち少なくとも2つ以上の選定個体に引力を作用させる引力ポテンシャルを導出し、前記複数の個体の変数による評価関数の評価値加算した評価加算値、及び、導出された前記選定個体の間の引力ポテンシャルを加算しこの加算値に前記選定個体の間に作用させる引力係数(g/2)とを乗算した引力値、を加算した実効評価値(Heff)を極値化する極値化部(7)と、前記引力係数を初期値から徐々に大きくしながら前記極値化部により実効評価値が極値化するように前記複数の個体の変数を変化させ、所定の終了条件を満たしたときにおける前記複数の個体の少なくとも一つの個体に基づいて、前記個体の変数、その変数の最適値、変数に対応した評価値、又は、評価値の最適値による各種値を導出する導出部(8)と、を備える大域的探索装置。

請求項2

請求項1記載の大域的探索装置において、前記変数の探索を開始する前に予め変数の推定解(xiz)が与えられている場合には、前記設定部は、初期分布として前記探索空間の内部に限定された限定探索範囲(Sa)であって当該推定解を含む限定探索範囲に前記個体の変数を設定する大域的探索装置。

請求項3

請求項1または2記載の大域的探索装置において、前記設定部は、初期分布として前記探索空間に前記複数の個体の変数をランダムに設定する大域的探索装置。

請求項4

請求項1または2記載の大域的探索装置において、前記設定部は、初期分布として少なくとも1つ以上の個体の少なくとも一つ以上の変数を前記探索空間の上限値又は下限値とし、その他の個体の変数をランダムに設定する大域的探索装置。

請求項5

請求項1または2記載の大域的探索装置において、前記設定部は、初期分布として前記探索空間を分割した格子点位置になるように前記個体の変数を設定する大域的探索装置。

請求項6

請求項5記載の大域的探索装置において、前記個体の変数が谷の生成に寄与する寄与度の高い前記個体の変数の分割数を寄与度の低い個体の変数よりも大きく設定する大域的探索装置。

請求項7

請求項5または6記載の大域的探索装置において、前記設定部は、前記初期分布として少なくとも1つ以上の変数が上限値又は下限値となる個体を選定して設定する大域的探索装置。

請求項8

請求項3から7の何れか一項に記載の大域的探索装置において、前記設定部は、前記探索空間を複数の部分空間(Sc、Sd)に分け、当該各部分空間にそれぞれ個体を設定し、前記導出部は、前記極値化部により求められた実効評価値が所定終了条件を満たしたときにおける前記複数の個体の少なくとも一つの個体に基づいて前記各種値を導出する大域的探索装置。

請求項9

請求項1記載の大域的探索装置において、前記変数の探索を開始する前に予め変数の推定解(xiz)が与えられている場合には、前記設定部は、初期分布として前記推定解を含む空間に近いほど個体を密に分布させると共に前記推定解から遠ざかるほど個体の密度を減少させるように設定する大域的探索装置。

請求項10

請求項1記載の大域的探索装置において、前記変数の探索を開始する前に予め変数の推定解(xiz)が与えられている場合には、前記設定部は、初期分布として前記推定解を含む空間に近い所定範囲(Sb)に個体を密に分布させると共にその他の個体を前記所定範囲の外にランダムに分布させ、その他の個体の少なくとも1つの個体の少なくとも一つ以上の変数を前記探索範囲の上限値又は下限値に設定する大域的探索装置。

請求項11

請求項1から10の何れか一項に記載の大域的探索装置において、前記極値化部は、前記複数の個体に対し識別符号順序付けて付し、順序が隣接する識別符号が付された個体を前記選定個体として引力値を導出し、順序が隣接しない識別符号が付された個体を前記選定個体とせず引力値を0とする大域的探索装置。

請求項12

請求項5から7の何れか一項に記載の大域的探索装置において、前記極値化部は、変数の数をM(但しMは1以上の自然数)としたときに、前記格子点位置の個体と隣接する格子点位置の最大2×M個の個体を前記選定個体として引力値を導出し、その他の個体を選定個体とすることなく前記引力値を0とする大域的探索装置。

請求項13

請求項11または12記載の大域的探索装置において、前記極値化部が前記複数の個体の間の引力ポテンシャルを導出し引力値を導出するときには、前記複数の個体の間の距離が大きいほど大きな引力値とし距離が小さいほど小さな引力値とする大域的探索装置。

請求項14

請求項13記載の大域的探索装置において、前記極値化部が前記複数の個体の間の引力ポテンシャルを導出し引力値を導出するときに、の(2)式により導出する大域的探索装置。

請求項15

請求項11または12記載の大域的探索装置において、前記極値化部が前記複数の個体の間の引力ポテンシャルを導出し引力値を導出するときには、前記複数の個体の間の距離に依存しない一定の引力値とする大域的探索装置。

請求項16

請求項15記載の大域的探索装置において、前記極値化部が前記複数の個体の間の引力ポテンシャルを導出し引力値を導出するときに、の(3)式により導出する大域的探索装置。

請求項17

請求項1から16の何れか一項に記載の大域的探索装置において、前記導出部は、少なくとも一つの個体の評価値に基づいて各種値を導出するときに、前記引力値を0として前記複数の個体の評価加算値による実効評価値を極値化して前記複数の個体の変数の実効評価値の最小値を導出し、当該実効評価値が最小値を満たす変数を最適値として導出する大域的探索装置。

請求項18

請求項1から17の何れか一項に記載の大域的探索装置において、前記極値化部が、前記実効評価値を極値化するときには、前記評価加算値及び前記引力値のそれぞれについて、当該値の解候補を求めた後、当該解候補を代入したときの微分値が当該評価関数の微分値と等しく、且つ、前記解候補を含む探索空間の内の全ての変数における評価値よりも大きな値を得る条件を満たす2次関数置換し、当該2次関数の極値を次回の値の解候補として繰り返して更新する補助関数法を用い、前記評価加算値と前記引力値とを加算した実効評価値を極値化する大域的探索装置。

請求項19

請求項14記載の大域的探索装置において、前記極値化部が、前記実効評価値を極値化するときには、前記評価加算値及び前記引力値のそれぞれについて、当該値の解候補を求めた後、当該解候補を代入したときの微分値が当該評価関数の微分値と等しく、且つ、前記解候補を含む探索空間の内の全ての変数における評価値よりも大きな値を得る条件を満たすリプシッツ定数を用いた2次関数に置換し、当該2次関数の極値を次回の値の解候補として繰り返して更新する補助関数法を用い、前記評価加算値と前記引力値とを加算した実効評価値を極値化するものであり、前記極値化部が、前記引力値について前記補助関数法を用いるときには前記2次関数のリプシッツ定数を4に固定して設定する大域的探索装置。

請求項20

請求項1記載の大域的探索装置(101)であって、前記導出部が、前記個体の変数又はその最適値として、未来時刻における最適経路(R1)を導出するときに、前記設定部は、過去の最適経路(R0)を推定解とし、前記初期分布として前記推定解を含む領域に近いほど個体を密に分布させると共に前記推定解から遠ざかるほど個体の密度を減少させるように設定する大域的探索装置。

請求項21

1以上の次元を備えた探索空間(S)に複数の極値を備える評価関数(Hopt)に個体(K)を設定することに基づいて個体の変数(xi)または変数の最適値を導出するプログラムであって、大域的探索装置(1,101)に、複数の個体の変数を前記探索空間の中の評価関数に沿って設定する手順と、設定された複数の個体のうち少なくとも2つ以上の選定個体に引力を作用させる引力ポテンシャルを導出し、前記複数の個体の変数による評価関数の評価値を加算した評価加算値、及び、導出された前記選定個体の間の引力ポテンシャルを全て加算しこの加算値に前記選定個体の間に作用させる引力係数(g/2)とを乗算した引力値、を加算した実効評価値(Heff)を極値化する手順と、前記引力係数を初期値から徐々に大きくしながら前記極値化部により実効評価値が極値化するように前記複数の個体の変数を変化させ、所定の終了条件を満たしたときにおける前記複数の個体の少なくとも一つの個体の評価値に基づいて、前記個体の変数、その変数の最適値、変数に対応した評価値、又は、評価値の最適値による各種値を導出する手順と、を実行させるプログラム。

請求項22

請求項21記載のプログラムにおいて、前記変数の探索を開始する前に予め変数の推定解(xiz)が与えられている場合には、前記最適化装置が前記複数の個体の変数を設定する手順では、初期分布として前記探索空間に限定された限定探索範囲(Sa)であって当該推定解を含む限定探索範囲に前記個体の変数を設定するプログラム。

請求項23

請求項21または22記載のプログラムにおいて、前記最適化装置が前記複数の個体の変数を設定する手順では、初期分布として前記探索空間に前記複数の個体の変数をランダムに設定するプログラム。

請求項24

請求項21または22記載のプログラムにおいて、前記最適化装置が前記複数の個体の変数を設定する手順では、初期分布として少なくとも1つ以上の個体の少なくとも一つ以上の変数を前記探索空間の上限値又は下限値とし、その他の個体の変数をランダムに設定するプログラム。

請求項25

請求項21または22記載のプログラムにおいて、前記最適化装置が前記複数の個体の変数を設定する手順では、初期分布として前記探索空間において全ての個体の変数を分割した格子点位置になるように前記個体の変数を設定するプログラム。

請求項26

請求項25記載のプログラムにおいて、前記最適化装置が前記複数の個体の変数を設定する手順では、前記個体の変数が谷の生成に寄与する寄与度の高い前記個体の変数の分割数を寄与度の低い個体の変数よりも大きく設定するプログラム。

請求項27

請求項25または26記載のプログラムにおいて、前記最適化装置が前記複数の個体の変数を設定する手順では、前記初期分布として少なくとも1つ以上の変数が上限値又は下限値となる個体を選定して設定するプログラム。

請求項28

請求項23から27の何れか一項に記載のプログラムにおいて、前記探索空間を複数の部分空間(Sc、Sd)に分け、当該各部分空間にそれぞれ個体を設定し、前記極値化部により実効評価値を求め当該実効評価値が所定終了条件を満たしたときにおける前記複数の個体の少なくとも一つの個体の評価値に基づいて前記個体の変数又はその変数の最適値を導出するプログラム。

請求項29

請求項21記載のプログラムにおいて、前記変数の探索を開始する前に予め変数の推定解(xiz)が与えられている場合には、前記最適化装置が前記複数の個体の変数を設定する手順では、初期分布として前記推定解を含む空間に近いほど個体を密に分布させると共に前記推定解から遠ざかるほど個体の密度を減少させるように設定するプログラム。

請求項30

請求項21記載のプログラムにおいて、前記変数の探索を開始する前に予め変数の推定解(xiz)が与えられている場合には、前記最適化装置が前記複数の個体の変数を設定する手順では、初期分布として前記推定解を含む空間に近い所定範囲内に個体を密に分布させると共にその他の個体を前記所定範囲の外にランダムに分布させ、その他の個体の少なくとも1つの個体の少なくとも一つ以上の変数を前記探索範囲の上限値又は下限値に設定するプログラム。

請求項31

請求項21から30の何れか一項に記載のプログラムにおいて、前記実効評価値を極値化する手順では、前記複数の個体に対し識別符号を順序付けて付し、順序が隣接する識別符号が付された個体を前記選定個体として引力値を導出し、順序が隣接しない識別符号が付された個体を前記選定個体とせず引力値を0とするプログラム。

請求項32

請求項25から27の何れか一項に記載のプログラムにおいて、前記実効評価値を極値化する手順では、変数の数をM(但しMは1以上の自然数)としたときに、前記格子点位置の個体と隣接する格子点位置の最大2×M個の個体を前記選定個体として引力値を導出し、その他の個体を選定個体とすることなく前記引力値を0とするプログラム。

請求項33

請求項31または32記載のプログラムにおいて、前記実効評価値を極値化する手順では、前記複数の個体の間の引力ポテンシャルを導出し引力値を導出するときには、前記複数の個体の間の距離が大きいほど大きな引力値とし距離が小さいほど小さな引力値とするプログラム。

請求項34

請求項33記載のプログラムにおいて、前記実効評価値を極値化する手順では、前記複数の個体の間の引力ポテンシャルを導出し引力値を導出するときに、の(2)式により導出するプログラム。

請求項35

請求項31または32記載のプログラムにおいて、前記実効評価値を極値化する手順において、前記複数の個体の間の引力ポテンシャルを導出するときには、前記複数の個体の間の距離に依存しない一定の引力値とする最適化プログラム

請求項36

請求項35記載のプログラムにおいて、前記実効評価値を極値化する手順では、前記複数の個体の間の引力ポテンシャルを導出し引力値を導出するときに、の(3)式により導出するプログラム。

請求項37

請求項21から36の何れか一項に記載のプログラムにおいて、前記各種値を導出する手順では、少なくとも一つの個体の評価値に基づいて個体の変数を導出するときに、前記引力値を0として前記複数の個体の評価加算値による実効評価値を極値化して前記複数の個体の変数の実効評価値の最小値を導出し、当該実効評価値が最小値を満たす変数を最適値として導出するプログラム。

請求項38

請求項21から37の何れか一項に記載のプログラムにおいて、前記実効評価値を極値化する手順では、前記評価加算値及び前記引力値のそれぞれについて、当該値の解候補を求めた後、当該解候補を代入したときの微分値が当該評価関数の微分値と等しく、且つ、前記解候補を含む探索空間の内の全ての変数における評価値よりも大きな値を得る条件を満たす2次関数に置換し、当該2次関数の極値を次回の値の解候補として繰り返して更新する補助関数法を用い、前記評価加算値と前記引力値とを加算した実効評価値を極値化するプログラム。

請求項39

請求項34記載のプログラムにおいて、前記実効評価値を極値化する手順では、前記評価加算値及び前記引力値のそれぞれについて、当該値の解候補を求めた後、当該解候補を代入したときの微分値が当該評価関数の微分値と等しく、且つ、前記解候補を含む探索空間の内の全ての変数における評価値よりも大きな値を得る条件を満たすリプシッツ定数を用いた2次関数に置換し、当該2次関数の極値を次回の値の解候補として繰り返して更新する補助関数法を用い、前記評価加算値と前記引力値とを加算した実効評価値を極値化するものであり、前記引力値について前記補助関数法を用いるときには前記2次関数のリプシッツ定数を4に固定して設定するプログラム。

請求項40

請求項21記載のプログラムにおいて、前記個体の変数又はその最適値を導出する手順では、未来時刻における最適経路(R1)を導出するものであって、前記複数の個体の変数を設定する手順では、過去の最適経路(R0)を推定解とし、前記初期分布として前記推定解を含む領域に近いほど個体を密に分布させると共に前記推定解から遠ざかるほど個体の密度を減少させるように設定する最適化プログラム。

技術分野

0001

本発明は、連続値最適化問題大域的探索装置及びプログラムに関する。

背景技術

0002

例えば、多次元探索空間において変数、すなわちパラメータ最適値を求める手法が提案されている(例えば、特許文献1参照)。特許文献1記載の技術によれば、探索空間内に最適値算出対象のパラメータを要素とする複数の個体を生成し、これらの個体の評価値を算出し、個体の中から評価値の悪い個体を選択している。そして、この選択された個体を評価値の良い個体に所定の割合で近づけている。また、評価値の悪い個体を最良の評価値の個体から一定のユークリッド距離内にある任意の領域に移動させている。そして、より良い評価値の個体を選択し最良の評価値の個体を随時更新し、複数の個体の評価値を収束させ、終了判定条件を満たしたと判定した時点で最良の評価値を有する個体に含まれるパラメータをパラメータの最適値として出力している。

先行技術

0003

特開2007−233676号公報

発明が解決しようとする課題

0004

特許文献1等に記載の技術を用いて、例えば、複数の極値(例えば極小値)を備えた評価関数最小値又は最大値となる変数の最適値を探索するとき、当該変数の最適値への到達確率を高めるためには、複数の個体が最適な1カ所に収束する過程において可能な限り多くの極値(例えば、極小値)を探索することが望ましい。

0005

しかしながら、特許文献1記載の技術を適用したとしても、複数の個体を互いに近づける収束過程において、個体の移動経路はその評価関数の形状とは無関係に決定されてしまう。このため、個体が収束過程において極値を通過するとは限らず、どの個体に収束させることが望ましいか正確に判断できなかったり最適値を通過してしまうことがある。個体の移動処理を極力細かくすることにより最適値への到達確率は高まるものの、個体の移動の回数が増加してしまい好ましくない。

0006

本発明の目的は、複数の極値を備えた評価関数の最小値又は最大値を探索するときに、変数の最適値への到達確率を高めながら極力少ない回数で最適値へ到達できるようにした連続値最適化問題の大域的探索装置及びプログラムを提供することにある。

課題を解決するための手段

0007

請求項1に記載した発明によれば、1以上の次元を備えた探索空間に複数の極値を備える評価関数に個体を設定することに基づいて個体の変数又は変数の最適値を導出する最適化装置を対象としている。

0008

設定部は、複数の個体の変数を探索空間の中の評価関数に沿って設定する。また、極値化部は、設定部により設定される複数の個体のうち少なくとも2つ以上の選定個体に引力を作用させる引力ポテンシャルを導出し、複数の個体による評価関数の評価値を加算した評価加算値、及び、導出された選定個体の間の引力ポテンシャルを加算しこの加算値に選定個体の間に作用させる引力係数とを乗算した引力値、を加算した実効評価値を極値化する。そして導出部は、引力係数を初期値から徐々に大きくしながら極値化部により実効評価値が極値化するように複数の個体の変数を変化させ、所定の終了条件を満たしたときにおける複数の個体の少なくとも一つの個体の評価値に基づいて、個体の変数、その変数の最適値、変数に対応した評価値、又は、評価値の最適値を導出する。このような処理を行うことで、複数の極値を備えた評価関数の最小値又は最大値を探索するときに、変数の最適値への到達確率を高めながら極力少ない回数で最適値へ到達できる。

図面の簡単な説明

0009

第1実施形態を示す連続値最適化問題の大域的探索装置の電気的構成
連続値最適化問題の大域的探索装置を機能的に示すブロック図
処理の流れを概略的に示すフローチャート
個体が探索空間内の最適解に収束するときの移動状態を示すイメージ図(その1)
個体が探索空間内の最適解に収束するときの移動状態を示すイメージ図(その2)
個体が探索空間内の最適解に収束するときの移動状態を示すイメージ図(その3)
個体が探索空間内の最適解に収束するときの移動状態を示すイメージ図(その4)
第2実施形態の説明図であり個体の初期分布を示す図(その1)
個体の初期分布を示す図(その2)
個体の初期分布を示す図(その3)
個体の初期分布を示す図(その4)
個体の初期分布を示す図(その5)
個体の初期分布を示す図(その6)
個体の初期分布を示す図(その7)
個体の初期分布を示す図(その8)
個体の初期分布を示す図(その9)
個体の初期分布を示す図(その10)
第3実施形態の説明図であり個体の存在分布の例を示す図
引力ポテンシャルを与える選定個体の例を示す説明図(その1)
引力ポテンシャルを与える選定個体の例を示す説明図(その2)
引力ポテンシャルを与える選定個体の例を示す説明図(その3)
引力ポテンシャルを与える選定個体の例を示す説明図(その4)
引力ポテンシャルを与える選定個体の例を示す説明図(その5)
個体の移動過程を示す説明図(その1)
個体の移動過程を示す説明図(その2)
個体の移動過程を示す説明図(その3)
個体の移動過程を示す説明図(その4)
第5実施形態の説明図であり補助関数法原理を概略的に示す説明図
リプシッツ定数の説明図(その1)
リプシッツ定数の説明図(その2)
処理の流れを概略的に示すフローチャート
シミュレーションに用いた評価関数を示す図
シミュレーションに用いた定数を示す図
シミュレーション結果
ある所定領域に収束する過程を示す図
第6実施形態の説明図であり個体が収束した後の状態を示す説明図
第7実施形態を示す電気的構成図
ある時刻における移動体最適経路を示す鳥瞰図(その1)
ある時刻における移動体の最適経路を示す鳥瞰図(その2)

実施例

0010

以下、本発明の連続値最適化問題の大域的探索装置及びプログラムの幾つかの実施形態について図面を参照して説明する。以下の実施形態中では、各実施形態間で同一機能または類似機能を備えた部分に同一符号を付して説明を行い、同一又は類似機能を備えた構成及びその作用、連携動作説明等を必要に応じて省略する。

0011

(第1実施形態)
図1A図3Dは第1実施形態の説明図を示している。最適化装置1は、CPU2と、ROM、RAM等のメモリ3と、入出力インタフェース4とをバス接続して構成されたマイクロコンピュータ(以下マイコン)5、又は汎用コンピュータなどを用いて連続値最適化問題の大域的探索装置として構成される。以下、マイコン5が最適化処理を実行することとして説明を行う。マイコン5が、メモリ3に記憶された最適化プログラムを実行し、各種手順を実行することで最適化処理を実行する。メモリ3は非遷移的実体記録媒体として用いられる。

0012

ここで最適化処理とは、1以上のM(≧1)次元を備えたユークリッド空間からなる探索空間Sを想定し、この探索空間Sに予め定められる評価関数Hoptの最小値又は最大値、すなわち最適値を求める処理、又は/及び、評価関数Hoptが最適値となる変数xiを求める処理を示す。以下では、評価関数Hoptの最小値を最適値として求めるための形態を示すが、最大値を最適値として求める処理に適用しても良い。評価関数Hoptは、1以上のM個の変数(パラメータ)に基づく数式による関数を示すものであり、例えば任意の多項式有理関数、無理関数、指数関数対数関数やその加減乗除等による組み合わせなどを挙げることができる。

0013

図1Bに示すように、最適化装置1は、マイコン5により実現される機能ブロックとして、設定部6、極値化部7、及び導出部8などの各種機能ブロックを備えるものである。設定部6は、複数の個体Kの変数xiを探索空間Sの内部の評価関数Hoptに沿って設定する。複数の個体KはそれぞれM次元の変数xiを備える。

0014

また極値化部7は、設定部6により設定された複数の個体Kのうち少なくとも2つ以上の選定個体Kに引力を作用させる引力ポテンシャルfijを導出し、複数の個体Kの変数xiによる評価関数Hoptの評価値Hopt(xi)を加算した評価加算値ΣHopt(xi)、及び、導出された選定個体Kの間の引力ポテンシャルfijを加算しこの加算値に選定個体Kの間に作用させる引力係数g/2とを乗算した引力値、を加算した実効評価値Heffを極値化、本実施形態では極小化する。

0015

そして導出部8は、引力係数g/2を初期値(例えば0)から徐々に大きくしながら極値化部7により実効評価値Heffが極値化するように複数の個体Kの変数xiを変化させ、所定の終了条件を満たしたときにおける複数の個体Kの少なくとも一つの個体Kの評価値に基づいて、個体Kの変数xiを導出する。すると、複数の個体Kが評価関数Hoptの最小値の一点に収束しやすくなる。本実施形態では、この原理を利用し、ある個体Kの変数xiを導出して解出力する。

0016

図2に最適化処理の詳細な流れをフローチャートで示し、図3A図3D探索処理のイメージ図を示している。これらの図3A図3Dでは、探索空間Sを一次元のユークリッド空間とし、この評価関数Hoptが複数の極小値を備えた関数である場合にその中の最小値を探索する際の個体Kの移動状態のイメージ図を示している。

0017

まずマイコン5は、図2のS1において評価関数Hoptに沿って個体Kを設定する。図3Aには、N=3個(N>2)すなわち複数の個体K1〜K3を設定した状態を示している。以下、断らない限り、複数の個体K1〜K3のうちの一部又は全ての個体を個体Kと略して説明を行うと共に、特別な個体Kについては符号Kの後に添え字を付して説明を行う。

0018

次に、マイコン5は、図2のS2において実効評価値Heffを求め、この実効評価値Heffを極小化するように個体Kの変数xiを変化させて更新する。実効評価値Heffは、前述したように複数の個体Kの変数xiを評価関数Hoptに導入した評価値Hopt(xi)に基づく値であり、具体例としては下記のように表すことができる。

0019

この(1)式のうち、Heffは実効評価値を示しており、Hopt(xi)は評価関数Hoptの各個体Kの評価値を示している。また、g/2は引力係数、ΣΣfij(xi−xj)は引力ポテンシャルの加算値を示している。

0020

(1)式の第1項は、複数の個体Kによる評価関数Hoptの評価値Hopt(xi)を加算した評価加算値、すなわち、評価関数Hoptに複数の個体Kの変数xiを代入した評価値Hopt(xi)を加算した加算値を示しており、(1)式の第2項は、複数の個体K間の引力ポテンシャルfijを加算し、この加算値に複数の個体Kの間に作用させる引力係数g/2を乗算した引力値、を示している。この引力ポテンシャルfijは、1つの個体Kが、他の全ての個体Kとの間で作用するように設定しても良いが、後述実施形態に示すように、全ての個体Kのうち一部を選定し当該選定個体Kを対象として引力ポテンシャルfijを設定しても良い。また、この引力ポテンシャルfijの関数は、後述実施形態に示すように、複数の個体K間の所謂ユークリッド距離が遠いほど引力値が大きくなる関数を適用しても良いし、ユークリッド距離に拘わらず引力値が一定値となるように設定しても良い。またこれに限られるものではなく、ユークリッド距離が遠いほど引力値が小さくなる関数を適用しても良い。マイコン5は、図2のS2においてこの評価加算値と引力値とを加算した実効評価値Heffを導出し、実効評価値Heffを小さくする個体Kの変数xiを探索する。この探索方法としては、後述実施形態に示す補助関数法を用いることが望ましいが、極値を探索可能な方法であればどのような方法を用いて探索しても良い。

0021

例えば、評価関数Hoptが図3Aに示すように複数の極小値を備える関数であるときには、(1)式の第2項の引力係数g/2を増加させると、個体Kを一点に収束させる引力が強くなり、個体Kは低い山から順に昇り、すなわち極大値を超えるように順に移動し、谷、すなわち極小値、を順に移動する。このため、例えば図3Bに示すように、個体K1は探索空間S内の変数xiを例えば増加する方向に移動すると共に、個体K3は探索空間S内の変数xiを例えば減少する方向に移動する。

0022

次に、マイコン5は、図2のS3において状態更新回数tをインクリメントすることでt=t+1とし、この状態更新回数tが所定上限回数τを超えたか否か、すなわち図2のS4においてt=τ+1であるか否かを判定する。本実施形態では、この図2のS4における所定上限回数τを超えたか否かの判定処理を所定の終了条件としている。マイコン5は、状態更新回数tが所定上限回数τ以下であり、この終了条件を満たしていないときには、S5において引力係数g/2を例えば所定数だけ増加し、S2に戻り処理を繰り返す。マイコン5は、このように引力係数g/2を徐々に大きくしながらS2〜S3の処理を繰り返すことで、図3Cに示すように、各個体Kは評価関数Hoptの極大値の大きな山を徐々に超えるようになる。これらの処理が繰り返されることにより、図3Dに示すように、複数の個体K1〜K3が評価関数Hoptの一点に収束するようになる。そして、マイコン5は、図2のS5において終了条件を満たしたときに例えば個体K1〜K3のうちの何れか一つの個体Kの変数xiの解を出力する。これにより個体Kの変数xiを解出力できる。

0023

本実施形態によれば、引力係数g/2を初期値から徐々に大きくしながら実効評価値Heffが極値化するように複数の個体Kの変数xiを変化させ、状態更新回数tが所定上限回数τを超えたときにおける複数の個体Kのうち少なくとも一つの個体Kに基づいて個体Kの変数xiを導出している。またこのとき、評価関数Hoptの評価値が最も低くなる条件を満たす個体Kの変数xiを解出力すると良い。これにより、変数xiの最適値への到達確率を高めながら極力少ない回数で最適値へ到達できるようになる。

0024

(第2実施形態)
図4から図13は第2実施形態の追加説明図を示している。第2実施形態では、個体Kの変数xiの初期分布の設定方法を説明する。前述実施形態に示したように、各個体KはM次元の変数xiを備えているが、このM次元の変数xiの初期分布を如何なる形態とするかに応じて、評価関数Hoptの谷の通過数、すなわち極値の通過数、及び、収束方法も変化する。

0025

評価関数Hoptの評価値がどのような値で極値、最小値となるか予め把握することはできないため、マイコン5は、予め探索空間Sを満たすように個体Kを初期設定することが望ましい。個体Kの数を多くすれば精度が高くなるが、個体Kの数を多くすれば処理時間も大きくなる。このため、限られた数の個体Kを用いて処理を行うことが望ましく、この限られた個体Kの変数xiの初期分布が最適値の探索処理に重要な要素を占めることになる。このためには、例えば図4から図13に示すように、個体Kの変数xiの初期分布を設定することが望ましい。

0026

図4から図6図8から図13は、複数のそれぞれの個体KがM=2次元の変数xiを備えている場合の初期分布の例を示し、図7は複数のそれぞれの個体KがM=3次元の変数xiを備えている場合の初期分布の例を示している。

0027

M=2次元の探索空間Sを想定したときに、例えば図4に示すように、探索空間S内に複数の個体Kの変数xiをランダムに設定すると良い。この場合、個体Kが一点に収束する過程において広範囲の極値を探索することができるようになる。この中でも図5の個体Ka、Kbに示すように、少なくとも1つ以上の個体Ka、Kbの変数xiを探索空間Sの上限値又は下限値とすると良い。また、その他の個体Kの変数xiをランダムに設定すると良い。このように設定することで、さらに広範囲の極値を探索できる。特に、探索空間Sの中で全ての変数xiについて上限値又は下限値となるように個体Kamの変数xiを設定することがさらに望ましい。

0028

また、例えば図6に示すように、初期分布として探索空間Sを分割した格子点位置になるように個体Kの変数xiを設定しても良い。この場合、図6にM=2次元の例を示すように、隣接する個体Kの間を等分割して設定しても良いが、変数xi毎、すなわちxi,1、xi,2毎に異なる分割数となるように設定しても良い。ここで「隣接」とはユークリッド距離が最も近い個体Kを意味する。また、例えば、複数の個体KがそれぞれM=3次元の変数xiを備えているときには、図7に示すように、個体Kが格子点位置に位置するように変数xiを設定することで初期分布を構成すると良い。このように格子点位置に個体Kを初期分布させることで探索空間Sの内部における極値を網羅して探索できる。

0029

さらに図8に示すように、個体Kの変数xiが谷の生成に寄与する寄与度の高い個体Kの変数xi,2の分割数を寄与度の低い個体Kの変数xi,1よりも大きく設定するようにしても良い。寄与度は、予め実験やシミュレーション等に応じて設定したり、実際の問題に対する定性的な考察から設定する。図8の例では、変数xi,2の分割数を5とし、変数xi,1の分割数を2としている。すると、初期分布として設定する個体Kの数を削減しながら探索空間Sの内部における極値を網羅して探索できる。個体Kの数を削減できるため処理時間を削減できる。

0030

また図9に示すように、例えば図6から図8のように設定されている場合、この中から少なくとも1つ以上の変数xiが探索空間Sで上限値又は下限値となる個体Kだけを選定して設定しても良い。すると、個体Kの数を削減しながら広範囲において極値の探索を行うことができる。

0031

また図10に示すように、初期分布として探索空間Sを複数の部分空間Sc、Sdに分けて各部分空間Sc、Sdにそれぞれ個体Kを設定しても良い。このとき、各部分空間Sc、Sd毎に実効評価値Heffを求め当該実効評価値Heffが所定終了条件を満たしたときにおける複数の個体Kの少なくとも一つの個体Kに基づいて個体Kの変数xiを導出するようにしても良い。これにより、より少ない個体Kの数で探索空間Sを網羅的に探索できる。この場合、部分空間Sc、Sd毎に異なる評価関数Hoptの最小値(最適値)を得る個体Kg1,Kg2の変数xiを求めることができるが、最終的に部分空間Sc、Sd毎に得られた個体Kg1,Kg2の変数xiの評価関数Hoptの評価値を比較し、この評価値の最小値を得る個体Kg1,Kg2の変数xiを選定して解として導出すると良い。

0032

これまで説明したように、収束過程において広範囲の極値を探索できるようにするため、探索空間Sの全てを極力網羅するように個体Kを広範囲に分布させることが望ましいが、例えば探索空間Sの内部に推定解が与えられる場合もある。

0033

例えば、ある変数xiが時間的に連続して変化することを考慮する。例えばマイコン5がこのような変数xi(t)の解をある所定の時間毎に導出するときに、次回のタイミングにおける変数xi(t+1)の解を得るために今回の変数xi(t)の解を推定解xizとして与えることで、次回のタイミングにおける変数xi(t+1)の解の導出処理を素早くしかも正確に行うことができる場合もある。

0034

このような場合、図11に示すように、初期分布として探索空間S内に限定された限定探索範囲Saを設け、この限定探索範囲Saとして推定解xizを含むように初期分布を設定することが望ましい。特にこの場合、例えば推定解xizから所定範囲(例えばxi,1−α1<変数xi,1<xi,1+β1、xi,2−α2<変数xi,2<xi,2+β2;但し、α1、α2、β1、β2>0)を満たすように限定探索範囲Saを絞ることが望ましい。これにより、さらに少ない評価回数で変数xiの最適解への到達確率を高めることができる。

0035

さらに図12に示すように、初期分布として推定解xizを含む空間に近いほど個体Kを密に分布させると共に推定解から遠ざかるほど個体Kの密度を減少させるように設定するようにしても良い。これにより、より少ない個体Kの数で変数xiの最適解への到達確率を高めることができる。

0036

さらに図13に示すように、初期分布として推定解xizを含む空間に近い所定範囲Sb内に個体Kを密に分布させると共にその他の個体Kを所定範囲Sbの外にランダムに分布させ、その他の個体Kのうち、少なくとも1つの個体Ka、Kb、Kamの変数xiを探索範囲Sの変数xiの上限値又は下限値に設定するようにしても良い。これにより、変数xiの推定解xizの付近重点的に探索しながら広範囲を探索することができ、推定解xiz又はその周辺に解が存在していなかった場合においても、変数xiの最適解への到達確率の低下を防ぐことができる。

0037

(第3実施形態)
図14から図20Dは第3実施形態の追加説明図を示す。第3実施形態は、選定個体の選定方法について説明する。引力ポテンシャルfijは(1)式に示したように、i番目の個体Kとj番目の個体Kの差の関数として表すことができる。この場合、引力ポテンシャルfijは、全ての2つの個体Kの組み合わせ数分の差分を求めて加算値を求めるようにすると良い。しかし図14に示すように、多数の個体Kが一の谷H1の中で密に分布すると共に、他の個体Kcが他の谷H2の中で疎に分布しているときには、密度が密に分布している谷H1の中の多数の個体Kの影響を受けやすくなる。

0038

すると、図14の矢印Yに示すように、本来評価値が最小値となり変数xiが最適値となる個体Kcが、他の多数の個体Kの影響を受けて谷H2を抜け出してしまうことがある。また例えば第2実施形態に初期分布を示したように、個体Kの密度がそのある所定の領域、空間毎にばらつくこともある。

0039

このような場合を考慮し、全ての2つの個体Kの組み合わせに引力ポテンシャルfijを与えてしまうと、個体Kの密度分布の影響が強くなることが想定されるような条件(例えば、評価関数Hoptの条件、又は/及び、個体Kの密度の初期分布の条件)を用いるときには、引力ポテンシャルfijを与える個体Kを選定し、特定の選定個体Kの間にだけ引ポテンシャルfijを与えることが望ましい。

0040

この場合、図15に変数M=1次元の例を示すように、マイコン5が特に複数の個体Kに対し識別符号(例えば1〜5)を順序付けて付し、順序が隣接する識別符号が付された個体Kを選定個体K1−K2、K2−K3、K3−K4、K4−K5として引力ポテンシャルfijを導出し、順序が隣接しない識別符号が付された個体Kを選定個体とせず引力ポテンシャルfijを0とすると良い。すると個体Kの密度の影響を強くしすぎることなく収束させることができる。

0041

また、マイコン5が全個体Kに対し引力ポテンシャルfijを対等に印加するためには、図16に示すように、個体K1と個体K5との間にも引力ポテンシャルfijを印加するようにすると良い。なお図15及び図16には個体Kの変数xiの小さい順に識別符号1〜5を付した形態を示しているが、変数xiの小さい順に識別符号1〜5を付して並べる必要はなく、識別符号1〜5を付す順序は変数xiの大小に影響するものではない。

0042

また図17にM=2次元の選定個体Kの例を示す。この図17図6のように探索空間SにおけるM=2次元の格子点位置に個体Kを初期分布させたときの選定個体の例を示す。また図18に変数M=3次元の例を示す。この図18図7のようにM=3次元の格子点位置に個体Kを初期分布させたときの選定個体の例を示す。

0043

マイコン5は、格子点位置の個体Kと隣接する格子点位置の最大2×M個の個体Kを選定個体として引力ポテンシャルfijを導出し、その他の個体Kを選定個体とせず引力ポテンシャルfijを0とすることが望ましい。図17に示すように、個体Kd1に隣接する格子点位置に存在する個体Kd2〜Kd5を選定個体として引力ポテンシャルfijを設定し、その他の個体Kを選定個体としないように引力ポテンシャルfijを0に設定する。すなわち、個体KがそれぞれM=2次元の変数xiを備えるときには、最大2×M=4個の隣接する格子点位置の個体Kを選定個体として引力ポテンシャルfijを導出する。

0044

また、図18に示すように、個体KがそれぞれM=3次元の変数xiを備えるときには、最大2×M=6個の格子点位置の個体Kを選定個体として引力ポテンシャルfijを導出する。

0045

また図19には図9に示すようにM=2次元の格子点位置の上限値又は下限値に個体Kを初期分布させたときの選定個体Kの例を示す。マイコン5は、これらの個体Kのうち隣接する2個の個体Kを選定個体として引力ポテンシャルfijを導出し、その他の個体Kを選定個体とせず引力ポテンシャルfijを0とする。図19に示すように、マイコン5が例えば初期分布として複数の個体Kを探索範囲Sの変数xiの上限値又は下限値に設定した場合には、探索空間Sにおいて変数xiが上限値又は下限値となる個体Kam、Ka、Kbから順次収束させることができる。すると探索空間Sを網羅して探索できる。

0046

<評価関数Hoptを考慮しない場合における初期分布からの個体Kの移動イメージ
図20Aから図20Dに個体Kの移動イメージを示している。図20Aに初期分布を示している。この初期分布は、図19に示す初期分布と同様であるが、改めて説明すると、全個体Kは、変数xi,1及びxi,2が共に探索空間Sの上限値又は下限値となる頂点に設定された個体Kam、変数xi,2が探索空間Sの上限値又は下限値となる辺部に設定された個体Ka、変数xi,1が探索空間Sの上限値又は下限値となる辺部に設定された個体Kb、からなっている。すなわち、全個体Ka、Kb、Kamは、それぞれ2次元の変数xi、1、xi、2の何れかの変数xiが上限値又は下限値となるように設定されている。

0047

隣接する個体Kは、2次元の変数xi、1、xi、2が等間隔で初期設定されている。そして、この例では、隣接する個体Ka、Kb、Kamを選定個体として引力ポテンシャルfijを印加するようにしている。なお、説明を単純化するため評価関数Hoptは考慮しない例を示す。

0048

この例の場合、矢印を付した隣接した選定個体Ka、Kb、Kamの間に引力がかかるため、隣接する個体Ka、Kb、Kamは当該引力を合成したベクトル方向に引き寄せられることになる。このため、まず図20Bに示すように、探索空間Sの頂点に初期設定された個体Kamが、探索空間Sの内方に引き込まれるように移動する。さらに図20Cに示すように、探索空間Sの辺部に初期設定された個体Ka、Kbが探索空間Sの内方に引き込まれるように移動する。

0049

さらに図20Dに示すように、全個体Ka、Kb、Kamが徐々に探索空間Sの中央内側に引き込まれるように移動する。これにより全個体Ka、Kb、Kamがそれらの2変数xi,1、xi,2が互いに同一となる一点に収束するようになる。この例では、評価関数Hoptを考慮していない例を挙げているため、最終的には探索空間Sの中央に収束することになるが、実際に評価関数Hoptを考慮すれば、変数xiに応じた評価値Hopt(xi)が実効評価値Heffに反映されるため、この実効評価値Heffを最小化するように個体Ka、Kb、Kamが移動する。すなわち個体Ka、Kb、Kamのそれぞれの変数xiが変化する。これにより、これらの全探索空間Sにおいて変数xiの最適値を網羅的に探索できることがわかる。

0050

(第4実施形態)
以下、第4実施形態を説明する。この第4実施形態では、引力ポテンシャルfijの設定方法について説明する。引力ポテンシャルfijは(1)式に示したように、i番目の個体Kとj番目の個体Kの差分の関数として表すことができる。この場合、引力ポテンシャルfijは、i番目の個体Kのp番目の変数をxi,pと表したときに、例えば下記の(2)式に基づいて導出することが望ましい。

0051

この(2)式の引力ポテンシャルfijは、複数の個体Kの間のユークリッド距離が大きいほど大きな引力値とするように設定され、複数の個体Kの間の距離が小さいほど小さな引力値とするように設定される。この場合、初期分布として広範囲に分布させた個体Kを素早く収束させることができ、例えば図2に示すように処理を実行したときには、状態更新回数tの所定上限回数τを少なくしても十分に収束させることができる。しかも、この式は微分可能な関数となるため、微分値を0とするように実効評価値の変数xiを求めることで容易に極値化できる。

0052

また、引力ポテンシャルfijを例えば下記の(3)式に基づいて導出するようにしても良い。

0053

この(3)式の引力ポテンシャルfijは、複数の個体Kの間の距離に関係なく一定の引力値とするように設定していることを示している。この場合、浅い谷、すなわち極大値を順に超えて収束させることができるようになる。

0054

(第5実施形態)
図21図26は第5実施形態の追加説明図を示す。本実施形態では、実効評価値Heff(xi)を極小化するように個体Kの変数xiを変化させるための具体例となる補助関数法について説明する。補助関数法は、(1)式の第1項の評価加算値、第2項の引力値を極小化するときに用いられる一方法であり、評価関数Hoptを当該評価関数Hoptに近似した2次関数置換し、この置換した2次関数に基づいて極値化する方法を示している。

0055

以下、補助関数法について詳細説明する。補助関数法の詳細イメージを図21に示している。図21に示すように、変数xの評価関数をfmej(x)としたときに、この評価関数fmej(x)の変数xに現在の解候補x^*(図21ではxa、xb)を代入し、この評価値fmej(x^*)を通過すると共に、その微分値が評価関数の偏微分値∂fmej(x^*)/∂xと等しく、且つ、その解候補x^*を含む探索空間S内の全ての変数xiにおける評価値fmej(xi)よりも大きな値を得る条件を満たすリプシッツ定数Lを用いた2次関数ffを導入する。この2次関数ffを数式化すると、(4−1)式の右辺のように示すことができる。また、この2次関数ffが極値となる条件を満たす解をxzとすると(4−2)式のように導出できる。

0056

これらの(4−1)式、(4−2)式において、Lはリプシッツ定数を示し、x^*はxの現在の解候補を示している。なお(4−2)式の右辺を微分すると(4−3)式のように導出できる。

0057

このとき、変数xに解候補x^*を代入することで(4−3)式の第2項を0にでき、現在の解候補x^*における微分値は(4−3)式の第1項と等しくなる。この(4−3)式の第1項は、解候補x^*における評価関数fmejの偏微分値∂fmej(x^*)/∂xに一致する。また、この2次関数ffは、解候補x^*を含む全ての変数xiで評価関数fmejの評価値fmej(xi)よりも大きな値となっている。このような2次関数ffを用いて評価関数fmejの極値を求めることが望ましい方法となる。

0058

(4−2)式に示すように、解候補xzを繰り返し導出する。図21に示すように、現在の解候補をxaとしたときに、まず2次関数ff1を探索し、2次関数ff1の極値を満たす解を次回の解候補xbとする。その後、この次回の解候補xbについて再度2次関数ff2の探索を行い、2次関数ff2の極値を満たす解を解候補xcに更新する。したがって解候補はxa→xb→xcとなるように変化する。これらの処理が、例えば所定回数以上繰り返されることで評価関数fmej(x)の極小値と見做すことが可能な解(例えばxc)を得ることができる。

0059

さて(1)式に(2)式の引力ポテンシャルfijを代入すると下記の(5)式のように示すことができる。この(5)式における引力ポテンシャルfijの関数は、第4実施形態に示したように、距離を大きくしたときに引力値を大きくする(2)式の関数を適用している。

0060

ここでは、説明を理解しやすくするため、引力ポテンシャルfijを印加する個体Kとして、第2実施形態の図15に示したように、識別番号の隣接する個体K1−K2、K2−K3、…、を選定個体としている。すなわち、i番目とi+1番目の個体Kを選定して引力ポテンシャルfijを印加する数式を示している。ここでは、この例について説明するが、第2、第3実施形態で説明したその他の例も同様に組み合わせることが可能である。

0061

この(5)式の右辺において、評価関数Hoptを表す第1項と、引力係数g/2×引力ポテンシャルfijを表す第2項とに分けて補助関数法を適用する。(5)式の右辺の第1項について、補助関数法を適用して置換すると(6)式の右辺のようになる。

0062

この(6)式の右辺は、j番目の個体Kにおけるq番目の変数xj,qを更新する場合に、(5)式の右辺の第1項について補助関数法を適用した数式を示している。また、(5)式の右辺の第2項を補助関数法を適用して置換すると(7)式の右辺のようになる。

0063

この(7)式の右辺も同様に、j番目の個体におけるq番目の変数xj,qを更新する場合において、(5)式の右辺の第2項について、補助関数法を適用した数式を示している。このような(6)式と(7)式を加算した加算値を極小化した条件を満たす変数xiを最終的に解出力することになる。

0064

リプシッツ定数Lは大きすぎると、(4−1)式の不等式を満たすことになるものの、2次係数が比較的大きくなることから、図22に2次関数ffのイメージを示すように、解の更新処理の幅が小さくなりすぎる。このため、評価関数Hoptの谷H2の極値に到達するまでの処理ステップが多くなり処理時間が長くなる。

0065

逆に、リプシッツ定数Lが小さすぎると(4−2)式の不等式を満たさなくなり、図23に2次関数ffのイメージを示すように、解の更新処理の幅が大きくなりすぎる。すると、1ステップの処理だけで隣接する谷H1に移動してしまうことが確認されている。

0066

このため、リプシッツ定数Lは、変数xiの解を更新する度に計算し直すと共に、式(4−1)の不等式を満たす中で可能な限り小さい値を設定すると良いが、特に(5)式の右辺の第2項に補助関数法を適用するときには、(7)式に示すようにリプシッツ係数Lを4に固定することが望ましい。このリプシッツ係数L=4は変数xiの解を更新処理する度に導出し直す必要がないことが発明者らにより確認されている。このとき特に、第2項におけるj番目の個体におけるq番目の変数の更新後の解xj,qは(8)式のように導出できる。

0067

この(8)式に示したj番目以外の個体Kについても、q番目の変数x≠j,qの更新処理を同じように行うことができ、1からN番目の個体Kのq番目の変数xj,qは、(9−1)式のように行列式を用いて一括更新できる。ただし、変数行列xq、リプシッツ係数行列Lq、引力係数行列G、評価関数偏微分行列∇qHoptは、それぞれ(9−2)式、(9−3)式、(9−4)式、(9−5)式に示すように表すことができる。

0068

0069

0070

このようにして更新処理を行うことができる。

0071

また、評価関数Hoptに補助関数法を適用し、第2項の引力値に補助関数法を用いなくても良い。すなわち、j番目の個体のq番目の変数xj,qを更新するときに評価関数Hoptだけに補助関数法を適用すると、(5)〜(7)式に対応した実効評価値Heffは(9−6)式のように表すことができる。

0072

このとき(9−6)式を極値化するには、(9−7)式に示すように変数xj,qにより偏微分した微分値が0となる条件を満たすように更新すると良い。

0073

他の個体Kのq番目の変数xj,qを一般化して考慮すると、(9−8)式のように表すことができる。

0074

この式を変数xqについて解くと、(9−9)式のように表すことができる。

0075

この(9−9)式を適用すると、「(L+gG)^(−1)」に含まれるGは正則行列ではないため、引力係数g/2を大きくした場合にGの特異性によって逆行列計算精度が大幅に低下する。このため、前述したように、評価関数Hoptの評価値と共に引力値についても補助関数法を適用することが望ましい。すると、マイコン5を用いたとしても、(9−1)式に基づいて計算処理することになり、(9−9)式における(L+gG)^−1の逆行列を算出しなくても良くなり、計算精度を高めることができる。

0076

このような最適化処理のフローチャートを図24に示している。図24に示すように、マイコン5はまずS1において探索空間S内に複数の個体Kを設定する。このとき、例えば第2実施形態に示したように個体Kを設定して初期分布を構成すると良い。マイコン5は、引力係数g/2を初期値=0とすることで実効評価値Heff=(1)式の右辺の第1項(=複数の個体Kの評価関数Hoptの評価値)となるように初期設定する。そして、マイコン5はS2aにおいて補助関数法を示す(8)式を用いて個体Kの全変数xiを更新する。

0077

このS2aの処理は、このタイミングで複数回行うようにしても良い。そして、マイコン5は、S4にて所定の終了条件を満たすまで、S5において複数の個体Kの間の引力係数g/2を徐々に増加させることで引力値を徐々に強くする。すると、これらのS2a〜S5の処理を繰り返すことで広範囲に散らばった個体Kは1カ所に収束することになる。引力値を増加するタイミングは、S2aにおいて補助関数法を用いた更新処理を1回だけ実行した後でも良いし、S2aの処理について実効評価値Heffの極値を得られることが想定される回数だけ繰り返し実行した後であっても良い。

0078

また、終了時点における個体Kの数は必ずしも1カ所の所定領域に収束して極値化している必要はないものの、引力により個体Kを収束させることによる優位性活用するために、処理後には初期分布における個体Kの分散範囲よりも狭い所定範囲内に収束していることが望ましい。

0079

<具体例>
発明者は評価関数Hoptを具体的な数式とした実例に合わせて最適値を導出するシミュレーションを行っている。以下ではこの具体例を説明する。評価関数Hoptを下記の(10−1)式と定義した。ただし、f(x)は(10−2)式、g(x)は(10−3)式とし、ωは(10−4)式としている。

0080

この評価関数Hoptは、M=1次元の変数xに応じた関数とされており、図25に示すように、複数の極小値を有する関数である。このとき図26に示したように、(10−1)式、(10−2)式、(10−3)式、(10−4)式の定数xm、a、P、A、B、Cを設定している。このように定数xm、a、P、A、B、Cを設定することで、評価関数Hoptは、特に変数xの探索範囲(探索空間S)を−5.0≦x≦5.0としたときに、最適解が変数0.5となる関数を示す。

0081

また図26に示したように、状態更新回数tの所定上限回数τを100とし、個体Kの数Nを10とし、図24のS2aに示すように、補助関数法を適用した処理を実行した。また図24の処理ステップS5において、引力係数g/2を増加させているが、下記の(10−5)式のように状態更新回数tの増加に応じて引力係数g/2を増加するように設定した。

0082

(10−5)式のgmax/2は引力係数g/2の最大値を示す。図27には、引力係数g/2の最大値gmax/2を横軸とし、収束成功したと見做すことが可能なシミュレーション回数を全シミュレーション回数で除して導出された成功確率縦軸として示している。

0083

ここでは、少なくとも一つの個体Kの変数xiが、最適解x=0.5の谷Hyに含まれていることを成功条件としてカウントしている。ここでいう谷Hyとは、図25に示すように評価関数Hoptの評価値が最適解x=0.5の評価値からその高低両側の極大値に至るまでの範囲となることを満たす領域を示している。したがって、収束後において、少なくとも一つの個体Kの変数xiが谷Hyに対応した領域内に含まれることを成功と見做している。

0084

図27に示した結果を考慮すると、成功確率はgmax/2に依存することがわかる。図27の範囲gaに示すように、引力係数g/2の最大値gmax/2を小さくしすぎると、引力値が弱く個体Kが収束する可能性は低くなり成功確率は比較的低くなる。この方法は所謂並列勾配法に類似した方法となる。逆に、引力係数g/2の最大値gmax/2を大きくしすぎると、図27の範囲gbに示すように、評価関数Hoptを無視して収束することになり成功確率が低下する。このため、引力係数g/2の最大値gmax/2をそれらの範囲ga、gbとはならないある所定範囲gcに設定することで成功確率を極力上げることができる。特に、引力係数g/2の最大値gmax/2を範囲gcの中でも特定の範囲gdに設定することで90%近い成功確率を達成できることを確認できた。

0085

図28は、全ての個体Kが最適解に含まれないように初期分布を構成し、当該個体Kの変数xiが、ある一点に収束する過程で最適解を含む谷Hyに対応した所定領域xxに収束する様子について状態更新回数tを横軸として示している。前述したように、この図28に示す所定領域xxに収束後の個体の変数xが1つでも入力していれば成功と見做す。

0086

個体Kが収束過程における広範囲を探索処理することで評価関数Hoptの極値をくまなく探索できるようになる。
しかも図25に示しているように、評価関数Hoptが変数x≒−0.5〜1.5の領域において極値を多数有する関数であったとしても、図28に示すように最適解=0.5を含む谷Hyに対応した領域xx内に個体Kを収束させることができることを確認できた。

0087

(第6実施形態)
図29は第6実施形態の追加説明図を示している。第6実施形態は、収束後の処理を示す。例えば図2又は図24に示す処理を実行し、状態更新回数tを所定上限回数τまで繰り返したときに実効評価値Heffが極値化している場合であっても、図29に示すように個体Kが最適値を含む谷Hy1の1カ所に収束せず、他の谷Hy2等に位置していることがあり、この結果、何れの個体Kの変数xiを解出力するか定めることができない場合がある。

0088

(1)式を考慮すれば明らかなように、実効評価値Heffが極値とされていたとしても、複数の個体Kの間に引力を生じている状態で釣り合っていることになるため、ある個体Kの変数xiを評価関数Hoptに代入してもその評価関数Hoptの評価値が必ずしも極値とはならないことが多い。このため、マイコン5は最終段階の処理として(1)式の第2項の引力係数g/2を0とし、実効評価値Heffとして第1項の評価関数Hoptの評価値そのものの極値を導出することが望ましい。

0089

例えば図29に示すように、複数の個体Kがそれぞれ複数の谷Hy1、Hy2に位置している場合には、例えば前述の補助関数法を用いて極値化することで、複数の個体Kがそれぞれ対応した複数の谷Hy1、Hy2の極値に移動することになる。

0090

これらの複数の個体Kの中で、変数xiを(1)式の第1項に代入した実効評価値Heffが最小値を満たす個体Kの変数xiを解として出力することが望ましい。これにより、変数xiの最適値を導出できる。しかも、個体Kが1カ所に収束していない場合であっても、評価関数Hoptが極値となる変数xiを確実に得ることができる。

0091

本実施形態に係る処理を適用すれば、前述実施形態又はそれらの実施形態を組み合わせた方法をしたときに必ずしも1カ所の谷(例えばHy1)に収束している必要がなくなり、少なくとも1つの個体Kが変数xiの最適解を含む谷Hy1に収束していればよくなる。このため、この処理を用いていない方法に比較して、例えば所定上限回数τを少なく設定できるようになる。

0092

(第7実施形態)
図30から図32は第7実施形態の追加説明図を示している。この第7実施形態では探索開始前に予め推定解が与えられる例を示す。

0093

例えば、車両用運転支援装置101は、交通状況やその変化、事故防止への対応のために近年活発に開発されており、特にドライバーへの運転負担を軽減するために開発されている。例えば運転支援装置101は、図30に示すように、制御器102を備え、位置検出器103、速度センサ104、地図情報取得部105、等を接続して構成され、未来時刻における最適移動位置を通過する最適経路を最適化する最適化装置として構成される装置である。

0094

制御器102は、例えばCPU106、ROM、RAM、EEPROMなどのメモリ107、及び、I/O108を備えたマイクロコンピュータ109を主として構成され、モデル予測制御処理に関するプログラムがメモリ107に記憶されている。運転支援装置101は、制御器102により実現される機能ブロックとして、図示しないが、図1Bと同様の設定部6、極値化部7、導出部8としての機能を備える。

0095

位置検出器103は、例えばGPS(Global Positioning System)等を用いて現在位置の情報を検出する。速度センサ104は移動体Cの移動速度を検出する。地図情報取得部105は、所定の記憶装置(例えばHDD)に予め記憶される地図情報、又は、外部の地図サーバから地図情報を取得する。制御器102は、メモリ107に記憶されたモデル予測制御処理のプログラムを実行することにより、位置検出器103から取得される現在位置情報、速度センサ104から取得される移動体Cの移動速度情報、及び、地図情報取得部105により取得される地図情報に基づいてモデル予測制御を行う。なお、その他のセンサ、例えば車両周辺障害物Ob1、Ob2を検知するための超音波センサ、車両周辺の障害物Ob1、Ob2との距離を測定するための測距装置、などにより取得される各種情報を用いてモデル予測制御を行っても良い。

0096

このモデル予測制御技術は、未来予測を行う技術であり、未来を含む一定期間の最適制御を行い、これらの最適制御を所定の時間毎に更新する技術である。運転支援装置101は、モデル予測制御技術を用いることで未来を含む一定期間における移動体(例えば自動車)Cの最適な走行経路を導出したり、障害物Ob1、Ob2に衝突することなく所定の駐車スペースに導くように支援できる。

0097

このような運転支援装置101の制御器102が、障害物Ob1、Ob2への衝突を避けながら経路探索処理を行うときには、図31に鳥瞰図を示すように、現在時刻t0から未来時刻t1〜t6までの一定期間t0〜t6における移動体Cの最適経路R0を導出することで時刻t1における最適移動位置L1を決定する。

0098

図32に時刻t1におけるモデル予測制御処理を鳥瞰図で示している。図32に示すように、運転支援装置101の制御器102は、時刻t1において新たに現在時刻t1以降における未来時刻t2〜t7における最適経路R1を導出するが、時刻t1における最適経路R1は、時刻t0における最適経路R0と近い軌跡となることが考えられる。

0099

このため、制御器102は、例えば時刻t1〜t6に対応した位置L1〜L6による最適経路R0を推定解とし、この推定解に基づいて第2実施形態に示したように、例えばこの最適経路R0を含む領域に近いほど個体Kを密に分布させると共に当該最適経路R0から遠ざかるほど密度を減少させるように個体Kを設定して初期分布を構成する。すると、少ない探索回数で最適解に到達する確率を高めることができるようになる。

0100

本実施形態によれば、制御器102が、未来時刻t2〜t7における移動体Cの最適経路R1を導出するときには、過去の最適経路R0を推定解とし、初期分布として最適経路R0を含む領域に近いほど個体Kを密に分布させると共に最適経路R0から遠ざかるほど個体Kの密度を減少させる。これにより、少ない探索回数で最適解に到達する確率を高めることができる。

0101

(他の実施形態)
本発明は、上記した実施形態に限定されるものではなく、以下のように変形又は拡張することができる。

0102

前述実施形態では、個体Kの変数xiを解出力する形態を説明しているが、変数xiに対応した評価値、すなわち、解出力すべき変数xiを評価関数Hoptに代入した評価値を解出力するようにしても良い。また、引力ポテンシャルfijに基づく引力値を0にする前の変数xiを導出し、この変数xiをそのまま解出力しても良いし、第6実施形態で説明したように、引力値を0にした後の変数xiの最適値を導出して解出力しても良い。また、この変数xiの最適値を評価関数Hoptに代入した評価値を導出し解出力しても良い。このような各種値を導出する場合に適用しても良い。

0103

評価関数Hoptが極小値、最小値となる条件を満たす変数xiを最適値として解出力する形態を示したが、極大値、最大値となる条件を満たす変数xiを最適値として解出力する形態に適用しても良い。

0104

所定の終了条件として、状態更新回数tが所定上限回数τを上回るか否かを条件としているが、これに限定されるものではなく、例えば変数xiを代入した評価関数Hoptの評価値が所定値以下となっているか、などの異なる条件を用いても良い。

0105

引力係数g/2を初期値=0から徐々に大きくする形態を示したが、初期値は0に限られない。
また、特許請求の範囲に記載した括弧内の符号は、本発明の一つの態様として前述する実施形態に記載の具体的手段との対応関係を示すものであって、本発明の技術的範囲を限定するものではない。前述実施形態の一部を、課題を解決できる限りにおいて省略した態様も実施形態と見做すことが可能である。また、特許請求の範囲に記載した文言によって特定される発明の本質を逸脱しない限度において、考え得るあらゆる態様も実施形態と見做すことが可能である。

0106

また本発明は、前述した実施形態に準拠して記述したが、本発明は当該実施形態や構造に限定されるものではないと理解される。本発明は、様々な変形例や均等範囲内の変形をも包含する。加えて、様々な組み合わせや形態、さらには、それらに一要素、それ以上、あるいはそれ以下、を含む他の組み合わせや形態をも、本開示の範畴や思想範囲に入るものである。

0107

図面中、1は最適化装置、101は運転支援装置(連続値最適化問題の大域的探索装置)、102は制御器、6は設定部、7は極値化部、8は導出部、Kは個体、Sは探索空間、xiは変数、g/2は引力係数、Hoptは評価関数、Heffは実効評価値、xizは推定解、を示す。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ