Top > Search of International Patents > CONTINUOUS VALUE OPTIMIZATION PROBLEM GLOBAL SEARCH DEVICE AND PROGRAM

CONTINUOUS VALUE OPTIMIZATION PROBLEM GLOBAL SEARCH DEVICE AND PROGRAM

Foreign code F180009619
File No. 5459
Posted date Nov 20, 2018
Country WIPO
International application number 2017JP023050
International publication number WO 2018042840
Date of international filing Jun 22, 2017
Date of international publication Mar 8, 2018
Priority data
  • P2016-171776 (Sep 2, 2016) JP
Title CONTINUOUS VALUE OPTIMIZATION PROBLEM GLOBAL SEARCH DEVICE AND PROGRAM
Abstract In the present invention, a setting unit (6) sets a plurality of individual piece variables in accordance with an evaluation function in a search space. An extreme value conversion unit (7) derives a gravitational force potential that causes a gravitational force to act on at least two individual pieces selected from among the plurality of individual pieces set by the setting unit, and converts to an extreme value an effective evaluation value (Heff) obtained by adding: an evaluation addition value obtained by adding evaluation values of an evaluation function based on the plurality of individual piece variables; and a gravitational force value obtained by adding up the derived gravitational force potential between the selected individual pieces, and multiplying the addition value by a gravitational force coefficient (g/2) acting between the selected individual pieces. A derivation unit (8) changes the plurality of individual piece variables such that the effective evaluation value is converted to an extreme value by the extreme value conversion unit, while increasing the gravitational force coefficient gradually from an initial value, and derives various values using the individual piece variable, the optimized value of the variable, the evaluation value corresponding to the variable, or the optimized value of the evaluation value, on the basis of at least one of the plurality of individual pieces when a prescribed end condition is satisfied.
Outline of related art and contending technology BACKGROUND ART
For example, in a multi-variable search space, i.e. a method to determine the optimum value of the parameter has been proposed (for example, see Patent Document 1). According to the technique described in Patent Document 1, parameters for the optimum value calculation within the search space and generate a plurality of individual elements, and calculates the evaluation value of these individuals, individuals of poor evaluation value from a selected individual. Then, the individual evaluation value of the selected individual may be provided near at a predetermined ratio. In addition, the evaluation value of the best individual from the individual evaluation values of the poor Euclidean distance within the constant is moved to an arbitrary region. Then, a better evaluation value of the best individual of the selected individual evaluation value is updated at any time, the evaluation value converges a plurality of individual, end determination condition is satisfied on determining the individual having the best evaluation value as an optimum value of the parameters included in the output.
Scope of claims (In Japanese)請求の範囲 [請求項1]
 1以上の次元を備えた探索空間(S)に複数の極値を備える評価関数(Hopt)に個体(K)を設定することに基づいて個体の変数(x i)または変数の最適値を導出する連続値最適化問題の大域的探索装置(1、101)であって、
 複数の個体の変数を前記探索空間の中の評価関数に沿って設定する設定部(6)と、
 前記設定部により設定される複数の個体のうち少なくとも2つ以上の選定個体に引力を作用させる引力ポテンシャルを導出し、前記複数の個体の変数による評価関数の評価値を加算した評価加算値、及び、導出された前記選定個体の間の引力ポテンシャルを加算しこの加算値に前記選定個体の間に作用させる引力係数(g/2)とを乗算した引力値、を加算した実効評価値(Heff)を極値化する極値化部(7)と、
 前記引力係数を初期値から徐々に大きくしながら前記極値化部により実効評価値が極値化するように前記複数の個体の変数を変化させ、所定の終了条件を満たしたときにおける前記複数の個体の少なくとも一つの個体に基づいて、前記個体の変数、その変数の最適値、変数に対応した評価値、又は、評価値の最適値による各種値を導出する導出部(8)と、
 を備える大域的探索装置。

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

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

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

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

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

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

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

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

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

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

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

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

[請求項14]
 前記極値化部が前記複数の個体の間の引力ポテンシャルを導出し引力値を導出するときに、
[数2]

 の(2)式により導出する請求項13記載の大域的探索装置。

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

[請求項16]
 前記極値化部が前記複数の個体の間の引力ポテンシャルを導出し引力値を導出するときに、
[数3]

 の(3)式により導出する請求項15記載の大域的探索装置。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[請求項34]
 前記実効評価値を極値化する手順では、前記複数の個体の間の引力ポテンシャルを導出し引力値を導出するときに、
[数2]

 の(2)式により導出する請求項33記載のプログラム。

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

[請求項36]
 前記実効評価値を極値化する手順では、前記複数の個体の間の引力ポテンシャルを導出し引力値を導出するときに、
[数3]

 の(3)式により導出する請求項35記載のプログラム。

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

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

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

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

  • Applicant
  • ※All designated countries except for US in the data before July 2012
  • DENSO CORPORATION
  • National university corporation Kyoto University
  • Inventor
  • OKADA, Shuntaro
  • TERABE, Masayoshi
  • OHZEKI, Masayuki
IPC(International Patent Classification)
Specified countries National States: AE AG AL AM AO AT AU AZ BA BB BG BH BN BR BW BY BZ CA CH CL CN CO CR CU CZ DE DJ DK DM DO DZ EC EE EG ES FI GB GD GE GH GM GT HN HR HU ID IL IN IR IS JO KE KG KH KN KP KR KW KZ LA LC LK LR LS LU LY MA MD ME MG MK MN MW MX MY MZ NA NG NI NO NZ OM PA PE PG PH PL PT QA RO RS RU RW SA SC SD SE SG SK SL SM ST SV SY TH TJ TM TN TR TT TZ UA UG US UZ VC VN ZA ZM ZW
ARIPO: BW GH GM KE LR LS MW MZ NA RW SD SL SZ TZ UG ZM ZW
EAPO: AM AZ BY KG KZ RU TJ TM
EPO: AL AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HR HU IE IS IT LT LU LV MC MK MT NL NO PL PT RO RS SE SI SK SM TR
OAPI: BF BJ CF CG CI CM GA GN GQ GW KM ML MR NE SN ST TD TG
Please contact us by e-mail or facsimile if you have any interests on this patent. Thanks.

PAGE TOP

close
close
close
close
close
close