(57)【要約】      （修正有）【課題】効率的に最適解を探索できるようにした連続最適化問題の大域的探索装置及びプログラムを提供する。【解決手段】設定部６は、１以上の次元を備えた探索空間の内部の評価関数に沿って複数の個体の変数を設定する。極値化部７は、複数の個体の変数による評価関数の評価値を加算した評価加算値及び設定部６により設定される少なくとも２つ以上の選定個体に引力を作用させる引力相互作用項であり選定個体の変数の差が大きいときには大きな値を取る引力相互作用項、に基づいて実効評価値を算出して当該実効評価値を極値化する。導出部８は、極値化部７により実効評価値が極値化するように複数の個体の変数を変化させ、所定の終了条件を満たしたときにおける少なくとも一つの個体Ｋに基づいて、個体の変数、その変数の最適値、変数に対応した評価値又は評価値の最適値を導出する。【選択図】図１Ｂ
2018156281.tif 000002
【特許請求の範囲】
【請求項１】
１以上の次元を備えた探索空間（Ｓ）の内部の評価関数（Ｈopt）に沿って複数の個体の変数を設定する設定部（６）と、
前記複数の個体の変数による評価関数の評価値を加算した評価加算値、及び、前記設定部により設定される複数の個体のうち少なくとも２つ以上の選定個体に引力を作用させる引力相互作用項（λｉ、ρｉ）であり前記選定個体の変数の差が大きいときにはその変化が大きくなるように更新され前記選定個体の変数の差が小さいときにはその変化が小さくなるように更新される引力相互作用項、に基づいて実効評価値（Ｈeff）を算出して当該実効評価値を極値化する極値化部（７）と、
前記極値化部により実効評価値が極値化するように前記複数の個体の変数を変化させ、所定の終了条件を満たしたときにおける前記複数の個体の少なくとも一つの個体に基づいて、前記個体の変数、その変数の最適値、変数に対応した評価値、又は、評価値の最適値を導出する導出部（８）と、
を備える連続最適化問題の大域的探索装置。
【請求項２】
前記実効評価値（Ｈeff）を（１）式とし、前記引力相互作用項を当該（１）式の右辺第２項及び第３項としたときに、下記（２）式を満たすように個体の間に引力を作用させる請求項１記載の連続最適化問題の大域的探索装置。
【数１】
2018156281.tif 000019
【数２】
2018156281.tif 000020
【請求項３】
前記（２）式のｆ（ｘ）として下記（３）式を適用する請求項２記載の連続最適化問題の大域的探索装置。
【数３】
2018156281.tif 000021
【請求項４】
前記極値化部が、前記実効評価値を極値化するときには、
前記評価加算値（Ｈopt）の解候補を求めた後、当該解候補を代入したときの微分値が当該評価関数の微分値と等しく、且つ、前記解候補を含む探索空間の内の全ての変数における評価値よりも大きな値を得る条件を満たす２次関数に置換し、当該２次関数の極値を次回の値の解候補として繰り返して更新する補助関数法を用い、
前記評価加算値及び前記引力相互作用項を加算した実効評価値を極値化する請求項１から３の何れか一項に記載の連続最適化問題の大域的探索装置。
【請求項５】
前記設定部は、初期分布として前記探索空間に前記複数の個体の変数をランダムに分布させるように設定する請求項１から４の何れか一項に記載の連続最適化問題の大域的探索装置。
【請求項６】
前記変数の探索を開始する前に予め変数の推定解（ｘiz）が与えられている場合には、
前記設定部は、初期分布として前記探索空間の内部に限定された限定探索範囲（Ｓａ）であって当該推定解を含む限定探索範囲に前記個体の変数を設定する請求項１から４の何れか一項に記載の連続最適化問題の大域的探索装置。
【請求項７】
前記変数の探索を開始する前に予め変数の推定解（ｘiz）が与えられている場合には、
前記設定部は、初期分布として前記推定解を含む空間に近い所定範囲（Ｓｂ）に個体を密に分布させると共にその他の個体を前記所定範囲の外にランダムに分布させるように設定する請求項１から４の何れか一項に記載の連続最適化問題の大域的探索装置。
【請求項８】
連続最適化問題の大域的探索装置（１）に、
１以上の次元を備えた探索空間（Ｓ）の内部の評価関数（Ｈopt）に沿って複数の個体の変数を設定する手順と、
前記複数の個体の変数による評価関数の評価値を加算した評価加算値、及び、前記設定される複数の個体のうち少なくとも２つ以上の選定個体に引力を作用させる引力相互作用項（λｉ、ρｉ）であり前記選定個体の変数の差が大きいときにはその変化が大きくなるように更新され前記選定個体の変数の差が小さいときにはその変化が小さくなるように更新される引力相互作用項、に基づいて実効評価値（Ｈeff）を算出して当該実効評価値を極値化する手順と、
前記極値化部により実効評価値が極値化するように前記複数の個体の変数を変化させ、所定の終了条件を満たしたときにおける前記複数の個体の少なくとも一つの個体に基づいて、前記個体の変数、その変数の最適値、変数に対応した評価値、又は、評価値の最適値を導出する手順と、
を実行させるプログラム。
【請求項９】
前記実効評価値（Ｈeff）を（１）式とし、前記引力相互作用項を当該（１）式の右辺の第２項及び第３項としたときに、下記（２）式を満たすように個体の間に引力を作用させる請求項８記載のプログラム。
【数１】
2018156281.tif 000022
【数２】
2018156281.tif 000023
【請求項１０】
前記（２）式のｆ（ｘ）として下記（３）式を適用する請求項９記載のプログラム。
【数３】
2018156281.tif 000024
【請求項１１】
前記実効評価値を極値化するときには、
前記評価加算値（Ｈopt）の解候補を求めた後、当該解候補を代入したときの微分値が当該評価関数の微分値と等しく、且つ、前記解候補を含む探索空間の内の全ての変数における評価値よりも大きな値を得る条件を満たす２次関数に置換し、当該２次関数の極値を次回の値の解候補として繰り返して更新する補助関数法を用い、
前記評価加算値及び前記引力相互作用項を加算した実効評価値を極値化する請求項８から１０の何れか一項に記載のプログラム。
【請求項１２】
前記設定部は、初期分布として前記探索空間に前記複数の個体の変数をランダムに設定する請求項８から１１の何れか一項に記載のプログラム。
【請求項１３】
前記変数の探索を開始する前に予め変数の推定解（ｘiz）が与えられている場合には、
前記設定部は、初期分布として前記探索空間の内部に限定された限定探索範囲（Ｓａ）であって当該推定解を含む限定探索範囲に前記個体の変数を設定する、
請求項８から１１の何れか一項に記載のプログラム。
【請求項１４】
前記変数の探索を開始する前に予め変数の推定解（ｘiz）が与えられている場合には、
前記設定部は、初期分布として前記推定解を含む空間に近い所定範囲（Ｓｂ）に個体を密に分布させると共にその他の個体を前記所定範囲の外にランダムに分布させるように設定する請求項８から１１の何れか一項に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、連続最適化問題の大域的探索装置及びプログラムに関する。
【背景技術】
【０００２】
例えば、多次元の探索空間において変数、すなわちパラメータの最適値を求める手法が提案されている（例えば、特許文献１参照）。特許文献１記載の技術によれば、探索空間内に最適値算出対象のパラメータを要素とする複数の個体を生成し、これらの個体の評価値を算出し、個体の中から評価値の悪い個体を選択している。そして、この選択された個体を評価値の良い個体に所定の割合（α）で近づけている。
【０００３】
また、評価値の悪い個体を最良の評価値の個体から一定のユークリッド距離内にある任意の領域に移動させている。そして、より良い評価値の個体を選択し最良の評価値の個体を随時更新し、複数の個体の評価値を収束させ、終了判定条件を満たしたと判定した時点で最良の評価値を有する個体に含まれるパラメータを、パラメータの最適値として出力している。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００７−２３３６７６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
特許文献１に記載の技術においては、選択された個体を評価値の良い個体に所定の割合αで近づけているが、この所定の割合αは、与えられる問題毎に異なるため、ユーザが問題別に適宜設定しなければならない。例えば、所定の割合αを大きく設定すると個体の収束が速くなるため高速探索できるものの、探索の分解能が低下し解の精度が悪化する。他方、所定の割合αを小さく設定すると解の精度は向上できるが、探索処理に必要以上に時間を要してしまう。効率的に複数の個体を収束させて最適解を探索する方法が望まれている。
【０００６】
本発明の目的は、効率的に最適解を探索できるようにした連続最適化問題の大域的探索装置及びプログラムを提供することにある。
【課題を解決するための手段】
【０００７】
請求項１に記載した発明によれば、設定部は、１以上の次元を備えた探索空間の内部の評価関数に沿って複数の個体の変数を設定する。また、極値化部は、複数の個体の変数による評価関数の評価値を加算した評価加算値、及び、設定部により設定される複数の個体のうち少なくとも２つ以上の選定個体に引力を作用させる引力相互作用項であり選定個体の変数の差が大きいときには大きな値を取る引力相互作用項、に基づいて実効評価値を算出して当該実効評価値を極値化する。そして導出部は、極値化部により実効評価値が極値化するように複数の個体の変数を変化させ、所定の終了条件を満たしたときにおける複数の個体の少なくとも一つの個体に基づいて、個体の変数、その変数の最適値、変数に対応した評価値、又は、評価値の最適値を導出する。このような処理を行うことで、効率的に最適解を探索できる。
【図面の簡単な説明】
【０００８】
【図１Ａ】第１実施形態における連続最適化問題の大域的探索装置の電気的構成図
【図１Ｂ】連続最適化問題の大域的探索装置を機能的に示すブロック図
【図２】処理の流れを概略的に示すフローチャート
【図３Ａ】個体の移動過程を示す説明図（その１）
【図３Ｂ】個体の移動過程を示す説明図（その２）
【図３Ｃ】個体の移動過程を示す説明図（その３）
【図３Ｄ】個体の移動過程を示す説明図（その４）
【図４】個体の移動過程を示す説明図（その５）
【図５】第２実施形態における個体の初期分布を示す図（その１）
【図６】個体の初期分布を示す図（その２）
【図７】個体の初期分布を示す図（その３）
【図８】個体の初期分布を示す図（その４）
【図９】個体の初期分布を示す図（その５）
【図１０】第３実施形態における補助関数法の原理を概略的に示す説明図
【図１１】処理の流れを概略的に示すフローチャート
【発明を実施するための形態】
【０００９】
以下、本発明の連続最適化問題の大域的探索装置及びプログラムの幾つかの実施形態について図面を参照して説明する。以下の実施形態中では、各実施形態間で同一機能または類似機能を備えた部分に同一符号を付して説明を行い、同一又は類似機能を備えた構成及びその作用、連携動作説明等を必要に応じて省略する。
【００１０】
（第１実施形態）
図１Ａから図３Ｄは第１実施形態の説明図を示している。最適化装置１は、ＣＰＵ２と、ＲＯＭ、ＲＡＭ等のメモリ３と、入出力インタフェース４とをバス接続して構成されたマイクロコンピュータ（以下マイコン）５、又は汎用コンピュータなどを用いて連続最適化問題の大域的探索装置として構成される。以下、マイコン５が最適化処理を実行することとして説明を行う。マイコン５は、メモリ３に記憶された最適化プログラムを実行し、各種手順を実行することで最適化処理を実行する。メモリ３は非遷移的実体的記録媒体として用いられる。
【００１１】
ここで最適化処理とは、１以上のＭ（≧１）次元を備えたユークリッド空間からなる探索空間Ｓを想定し、この探索空間Ｓに予め定められる評価関数Ｈoptの最小値又は最大値、すなわち最適値を求める処理、又は／及び、評価関数Ｈoptが最適値となる条件を満たす変数ｘｉを求める処理を示す。評価関数Ｈoptは、１以上のＭ個の変数（パラメータ）に基づく数式による関数を示すものであり、例えば任意の多項式、有理関数、無理関数、指数関数、対数関数やその加減乗除等による組み合わせなどを挙げることができる。
【００１２】
図１Ｂに示すように、最適化装置１は、マイコン５により実現される機能ブロックとして、設定部６、極値化部７、及び導出部８などの各種機能ブロックを備える。設定部６は、複数の個体Ｋの変数ｘｉを探索空間Ｓの内部の評価関数Ｈoptに沿って設定する。複数の個体ＫはそれぞれＭ次元の変数ｘｉを備える。
【００１３】
また極値化部７は、複数の個体Ｋの変数ｘｉによる評価関数Ｈoptの評価値を加算した評価加算値、及び、設定部６により設定される複数の個体Ｋのうち少なくとも２つ以上の選定個体Ｋ（例えばＫ１，Ｋ２）に引力を作用させる引力相互作用項、に基づいて評価関数Ｈoptの実効評価値Ｈeffを算出し当該実効評価値を極値化する。後述するが、この引力相互作用項は、選定個体Ｋの変数ｘｉの差が大きいときにはその変化が大きくなるように更新され選定個体Ｋの変数ｘｉの差が小さいときにはその変化が小さくなるように更新される。
【００１４】
そして導出部８は、極値化部７により実効評価値Ｈeffが極値化するように複数の個体Ｋの変数ｘｉを変化させ、所定の終了条件を満たしたときにおける複数の個体Ｋの少なくとも一つの個体に基づいて、個体Ｋの変数ｘｉの最適値を導出する。このとき、個体Ｋ１，Ｋ２の変数ｘｉに対応した実効評価値、又は、この評価値の最適値等の値を導出しても良い。すると、複数の個体Ｋが評価関数Ｈoptの最適値の一点に収束しやすくなる。本実施形態では、この原理を利用し、ある個体Ｋの変数ｘｉの最適値を導出して解出力する。
【００１５】
図２に最適化処理の詳細な流れをフローチャートで示し、図３Ａ〜図３Ｄは、初期の探索処理のイメージ図、図４に後期の探索処理のイメージ図を示している。これらの図３Ａ〜図３Ｄ及び図４では、探索空間Ｓを一次元のユークリッド空間とし、この評価関数Ｈoptが複数の極小値を備えた関数である場合、その中の最小値を探索するときの個体Ｋ１、Ｋ２の移動状態のイメージ図を示している。
【００１６】
まずマイコン５は、図２のＳ１において評価関数Ｈoptに沿って個体Ｋを設定する。図３には、Ｎ＝２個すなわち複数の個体Ｋ１、Ｋ２を設定した状態を示している。以下、断らない限り、複数の個体Ｋ１、Ｋ２のうちの一部又は全ての個体を個体Ｋと略して説明を行うと共に、特別な個体Ｋについては、符号Ｋの後に添え字を付して説明を行う。
【００１７】
次にマイコン５は、図２のＳ２において実効評価値Ｈeffを求め、この実効評価値を極小化するように個体Ｋの変数ｘｉを変化させて更新する。実効評価値Ｈeffは、前述したように複数の個体Ｋの変数ｘｉを評価関数Ｈoptに導入した評価値Ｈopt（ｘｉ）に基づく値であり、具体例として下記のように表すことができる。
【数１】
2018156281.tif 000003
【００１８】
この（１）式のうち、Ｈeff（｛ｘｉ｝）は実効評価値を示しており、Ｈopt（ｘｉ）は評価関数Ｈoptの各個体Ｋの評価値を示している。また、λｉは１次引力係数、ρｉ／２は２次引力係数を示している。ここでρｉは予め定められた正の定数である。
【００１９】
（１）式の右辺第１項は、複数の個体Ｋによる評価関数Ｈoptの評価値Ｈopt（ｘｉ）を加算した評価加算値、すなわち、評価関数Ｈoptに複数の個体Ｋの変数ｘｉを代入した評価値Ｈopt（ｘｉ）を加算した加算値を示しており、（１）式の右辺第２項及び第３項は、複数の個体Ｋの間の引力相互作用項を示している。この引力相互作用項は、複数の個体Ｋの間の変数ｘｉの差が大きいほど大きくなり、逆に複数の個体Ｋの間の変数ｘｉの差が小さいときには小さくなるように変化する項である。
【００２０】
以下では、全ての個体Ｋのうち隣接する識別符号を備える個体Ｋを選定し、当該選定個体Ｋを対象として引力相互作用項を設定する形態を示すが、１つの選定個体Ｋについて他の全ての個体Ｋを選定個体Ｋとし当該選定個体Ｋの間で作用するように設定しても良い。なお、全ての２つの個体Ｋの組み合わせに引力相互作用項を与えてしまうと、ある谷に集中して多数の個体Ｋを備えている場合には、この多数の個体Ｋの密度分布の影響が強くなることが想定される。このようなときには、特定の選定個体Ｋの間にだけ引力相互作用項の影響を与えることが望ましい。これにより、個体Ｋの密度の影響を強くしすぎることなく収束させることが可能となる。
【００２１】
また（１）式のλｉは１回の演算処理毎に更新される係数であり、例えば（２）式のように定義することが望ましい。~λｉは更新後の値であり、λｉは更新前の値を示す。
【数２】
2018156281.tif 000004
【００２２】
この（２）式において、ｆ（ｘ）は変数ｘに応じて変化する関数を示し単調増加関数である。
【数３】
2018156281.tif 000005
【００２３】
特に、この（３）式に示すように、ｆ（ｘ）はｘの奇数乗の値とすることが望ましい。マイコン５は、図２のＳ２において評価加算値と引力相互作用項とを加算した実効評価値Ｈeffを導出し、実効評価値Ｈeffを小さくする個体Ｋの変数ｘｉを探索する。
【００２４】
例えば、評価関数Ｈoptが、図３Ａに示すように複数の極小値を備える一次関数であるときに、個体Ｋ１、Ｋ２の間の変数ｘｉの差が大きいと、（１）式の右辺第２項及び第３項の影響により、低評価値となる個体Ｋ２の変数ｘｉを固定したまま、個体Ｋ１の変数ｘｉを大きく移動させて評価関数Ｈoptの中でも大域的に極小値を探索することになる。このとき、個体Ｋ１は極大値を超えるように順に移動し、谷を順に移動する。例えば、図３Ｂに示すように、個体Ｋ１は探索空間Ｓ内の変数ｘｉを例えば減少させる方向に移動する。
【００２５】
次に、マイコン５は、図２のＳ３において一次引力係数λｉを（２）式を用いて更新する。（３）式に示すように、ｆ（ｘ）を単調増加関数とすると、ｘi−ｘｉ＋１が正の値であればλｉは増加し、ｘｉ−ｘｉ＋１が大きくなればなるほどλの増加量は大きくなる。また、ｘi−ｘｉ＋１が負の値であればλは減少し、ｘi−ｘｉ＋１が小さくなればなるほどλｉの減少量は大きくなる。以上のように、λｉはｘi−ｘｉ＋１と同符号になる様に更新されるため、λｉ（ｘi−ｘｉ＋１）はｘｉ＋１−ｘｉ＝０の時に最小値を取ることになり、実効評価値Ｈeffの最小値では全ての個体Ｋが一致することになる。
【００２６】
次に、マイコン５は、図２のＳ４において終了条件を満たしたか否かを判定する。この終了条件は、例えば実効評価値Ｈeffが所定の閾値以下となったか否か、又は、繰り返し処理回数が所定の上限回数を超えたか否かを判定することを条件としている。実効評価値Ｈeffの閾値は、複数の個体Ｋが評価関数Ｈoptの極値の位置に概ね収束することが想定される値に予め設定することが望ましい。このため、複数の個体Ｋが概ね一点に収束していなければ、Ｓ２に戻して処理が繰り返されることになる。
【００２７】
前述したように、隣り合う個体Ｋの変数ｘｉとｘｉ＋１との差が小さくなればなるほど実効評価値Ｈeffも小さくなるため、これらのＳ２〜Ｓ４の処理が繰り返されれば、図３Ｂ、図３Ｃに示すように、個体Ｋ１、Ｋ２間の距離が縮小すると共に、個体Ｋ１、Ｋ２の各評価値Ｈopt（ｘｉ）、Ｈopt（ｘｉ＋１）も徐々に小さくなる。すると、図３Ｄに示すように、複数の個体Ｋ１、Ｋ２が同一の谷に位置するようになる。また（２）式の次回の一次引力係数~λと今回の一次引力係数λとの差が徐々に少なくなり、一次引力係数λは次第に一定値に収束する。
【００２８】
探索終盤の個体Ｋの移動状態を示す図４において、複数の個体Ｋ１、Ｋ２が同一の谷に位置するようになると、隣り合う個体Ｋの変数ｘｉとｘｉ＋１との差が小さくなるため、（１）式の右辺第２項及び第３項の引力相互作用項の影響が弱まり、個体Ｋ１、Ｋ２の位置が同一の谷の極小値に近づくように小刻みに更新される。そして、それぞれの個体Ｋ１、Ｋ２はこの同一の谷の極小値の一点に収束する。そして、マイコン５は、図２のＳ４において終了条件を満たしたときに、Ｓ５において例えば複数の個体Ｋ１、Ｋ２のうち何れか一つの個体Ｋの変数ｘｉの解を出力する。これにより個体Ｋの変数ｘｉを解出力できる。
【００２９】
以上、本実施形態によれば、（１）式に応じて評価関数Ｈoptの実効評価値Ｈeffが極値化するように複数の個体Ｋの変数ｘｉを変化させ、所定の終了条件を満たしたときの少なくとも一つの個体Ｋに基づいて個体Ｋの変数ｘｉを導出している。
【００３０】
個体Ｋの変数ｘｉとｘｉ＋１との間の距離が大きいときには引力相互作用項の影響が大きくなるため、例えば図３Ａ〜図３Ｄに示すように、低評価値となる個体Ｋ２を固定したまま高評価値となる個体Ｋ１を大きく移動させることができ、これにより大域的な探索処理を行うことができる。また逆に、個体Ｋの変数ｘｉとｘｉ＋１との間の距離が短いときには引力相互作用項の影響が小さくなるため、図４に示すように、同一の谷の極小値に近づくように個体Ｋ１、Ｋ２を小刻みに更新できるようになる。このため、複数の個体Ｋ１、Ｋ２を効率よく収束させることができる。またこのとき、評価関数Ｈoptの評価値が最も低くなる条件を満たす個体Ｋの変数ｘｉを解出力することが望ましい。
【００３１】
（第２実施形態）
図５から図９は第２実施形態の追加説明図を示している。第２実施形態では、個体Ｋの変数ｘｉの初期分布の設定方法を説明する。前述実施形態に示したように、各個体ＫはＭ次元の変数ｘｉを備えているが、このＭ次元の変数ｘｉの初期分布を如何なる形態とするかに応じて、評価関数Ｈoptの谷の通過数、すなわち極値の通過数、及び、収束方法も変化する。
【００３２】
評価関数Ｈoptの評価値が、どのような値で極値、最小値となるか予め把握することはできないため、マイコン５は、予め探索空間Ｓを満たすように個体Ｋを初期設定することが望ましい。個体Ｋの数を多くすれば精度が高くなるが、個体Ｋの数を多くすれば処理時間も大きくなる。
【００３３】
このため、限られた数の個体Ｋを用いて処理を行うことが望ましく、この限られた個体Ｋの変数ｘｉの初期分布が最適値の探索処理に重要な要素を占めることになる。このためには、例えば図５から図９に示すように、個体Ｋの変数ｘｉの初期分布を設定することが望ましい。図５から図９は、それぞれの個体ＫがＭ＝２次元の変数ｘｉを備えている場合の初期分布の例を示している。Ｍ＝２次元の探索空間Ｓを想定したときに、例えば図５に示すように、探索空間Ｓ内に複数の個体Ｋの変数ｘｉをランダムに設定すると良い。この場合、個体Ｋが一点に収束する過程において広範囲の極値を探索できるようになる。
【００３４】
この中でも図６の個体Ｋａ、Ｋｂに示すように、少なくとも１つ以上の個体Ｋａ、Ｋｂの変数ｘｉを探索空間Ｓの上限値又は下限値とすると良い。また、その他の個体Ｋの変数ｘｉを探索空間Ｓの内部にランダムに設定すると良い。このように設定することで、さらに広範囲の極値を探索できる。特に、探索空間Ｓの中で全ての変数ｘｉについて上限値又は下限値となるように個体Ｋａｍの変数ｘｉを設定することがさらに望ましい。
【００３５】
ある収束過程において広範囲の極値を探索できるようにするため、探索空間Ｓの全てを極力網羅するように個体Ｋを広範囲に分布させることが望ましいが、変数ｘｉの探索を開始する前に例えば探索空間Ｓの内部に推定解が与えられる場合もある。
【００３６】
例えば、ある変数ｘｉが時間的に連続して変化することを考慮する。例えばマイコン５がこのような変数ｘｉ（ｔ）の解をある所定の時間毎に導出するときに、次回のタイミングにおける変数ｘｉ（ｔ＋１）の解を得るために、今回の変数ｘｉ（ｔ）の解を推定解ｘizとして与えることで、次回のタイミングにおける変数ｘｉ（ｔ＋１）の解の導出処理を素早くしかも正確に行うことができる場合もある。
【００３７】
このような場合、図７に示すように、初期分布として探索空間Ｓ内に限定された限定探索範囲Ｓａを設け、この限定探索範囲Ｓａとして推定解ｘizを含むように初期分布を設定することが望ましい。特にこの場合、例えば推定解ｘizから所定範囲（例えばｘｉ，１−α１＜変数ｘｉ，１＜ｘｉ，１＋β１、ｘｉ，２−α２＜変数ｘｉ，２＜ｘｉ，２＋β２；但し、α１、α２、β１、β２＞０）を満たすように限定探索範囲Ｓａを絞ることが望ましい。これにより、さらに少ない評価回数で変数ｘｉの最適解への到達確率を高めることができる。
【００３８】
さらに図８に示すように、初期分布として推定解ｘizを含む空間に近いほど個体Ｋを密に分布させると共に推定解ｘizから遠ざかるほど個体Ｋの密度を減少させるように設定するようにしても良い。これにより、より少ない個体Ｋの数で変数ｘｉの最適解への到達確率を高めることができる。
【００３９】
さらに図９に示すように、初期分布として推定解ｘizを含む空間に近い所定範囲Ｓｂ内に個体Ｋを密に分布させると共にその他の個体Ｋを所定範囲Ｓｂの外にランダムに分布させ、その他の個体Ｋのうち、少なくとも１つの個体Ｋａ、Ｋｂ、Ｋａｍの変数ｘｉを探索空間Ｓの変数ｘｉの上限値又は下限値に設定するようにしても良い。これにより、変数ｘｉの推定解ｘizの付近を重点的に探索しながら広範囲を探索することができ、推定解ｘiz又はその周辺に解が存在していなかった場合においても、変数ｘｉの最適解への到達確率の低下を防ぐことができる。
【００４０】
（第３実施形態）
図１０及び図１１は第３実施形態の追加説明図を示す。本実施形態では、実効評価値Ｈeff（ｘｉ）を極小化するように個体Ｋの変数ｘｉを変化させるための具体例となる補助関数法について説明する。本実施形態において、補助関数法は（１）式の第１項の評価加算値を極小化するときに用いられる一方法であり、評価関数Ｈoptを当該評価関数Ｈoptに近似した２次関数ｆｆに置換し、この置換した２次関数ｆｆに基づいて極値化する方法を示している。
【００４１】
＜補助関数法について＞
以下、補助関数法について詳細説明する。補助関数法の詳細イメージを図１０に示している。図１０に示すように、変数ｘの評価関数をＨopt（ｘ）としたときに、この評価関数Ｈopt（ｘ）の変数ｘに現在の解候補ｘ＾＊を代入し、この評価値Ｈopt（ｘ＾＊）を通過すると共に、その微分値が評価関数の偏微分値∂Ｈopt（ｘ＾＊）／∂ｘと等しく、且つ、その解候補ｘ＾＊を含む探索空間Ｓ内の全ての変数ｘにおける評価値Ｈopt（ｘ）よりも大きな値を得る条件を満たすリプシッツ定数Ｌを用いた２次関数ｆｆを導入する。この２次関数ｆｆを数式化すると、（４−１）式の右辺のように示すことができる。また、この２次関数ｆｆが極値となる条件を満たす解をｘｚとすると（４−２）式のように導出できる。
【数４】
2018156281.tif 000006
【００４２】
これらの（４−１）式、（４−２）式において、Ｌはリプシッツ定数を示し、ｘ＾＊はｘの現在の解候補を示している。（４−１）式、（４−２）式を繰り返し適用し、２次関数ｆｆ１、ｆｆ２を繰り返し求め、所定回数以上、（４−２）式の解ｘｚを繰り返し更新することで、評価関数Ｈoptの極小値と見做すことが可能な解ｘ１、ｘ２を順次得ることができる。このようにすることで、２次関数ｆｆの変形処理をするだけで実効評価値Ｈeffを極小化できる。
【００４３】
リプシッツ定数Ｌは大きすぎると、（４−１）式の不等式を満たすことになるものの、２次係数が比較的大きくなることから、解の更新処理の幅が小さくなりすぎる。このため、評価関数Ｈoptの谷の極値に到達するまでの処理ステップが多くなり処理時間が長くなる。逆に、リプシッツ定数Ｌが小さすぎると解の更新処理の幅が大きくなりすぎる。すると、１ステップの処理だけで隣接する谷Ｈ１に移動してしまうことが確認されている。このため、リプシッツ定数Ｌは、変数ｘｉの解を更新する度に計算し直すと共に、式（４−１）の不等式を満たす中で可能な限り小さい値を設定すると良い。
【００４４】
＜数式展開説明＞
以下、補助関数法を用いた数式展開を説明する。ここでは、Ｍ個（次元）の変数を備える評価関数Ｈoptを適用し、Ｎ個の個体Ｋを用いて評価関数Ｈoptの最小値を探索する場合について説明する。
【００４５】
前述した（１）式をＭ個の変数ｘを備える形態に一般化すると、（５）式のように表すことができる。
【数５】
2018156281.tif 000007
【００４６】
【数６】
2018156281.tif 000008
【００４７】
ここで、Ｍ個の変数ｘを（６−１）式のように１×Ｍの行列式で表している。また一次引力係数λｉを（６−２）式のように１×Ｍの行列式で表しており、これにより、（５）式ではｉ番目の個体Ｋのｐ番目の変数ｘｉ，ｐに対しそれぞれ一次引力係数λｉ，ｐを乗じることで一次引力係数λｉ，ｐとしている。また（５）式において、ρｉは正のスカラー定数であり、このスカラー定数ρｉ／２を二次引力係数としている。
【００４８】
図１１はＭ個の変数ｘに一般化した場合の処理の流れをフローチャートで示している。図１１に示すように図２に示される処理をＭ個の変数ｘに適用可能なように一般化したものであるため、ステップ番号に添え字ａを付して説明する。
【００４９】
まずマイコン５は、Ｓ１において複数の個体Ｋを設定し、Ｓ２ａにおいて実効評価値Ｈeffが極小となるように変数｛ｘｐ｝を更新する。このＳ２ａにおいては、（５）式の実効評価関数Ｈeff（｛ｘｉ｝）のうち、右辺第１項の評価関数Ｈoptに補助関数法を適用して極小値を得る変数｛ｘｐ｝を求める。（５）式の右辺第１項の評価関数Ｈoptに補助関数法を適用して、変数ｘｉ，ｐの二次関数に置換すると（７）式の右辺のようになる。
【数７】
2018156281.tif 000009
【００５０】
ここで、ｘｉ＾＊は、ｉ番目の個体Ｋの更新前の値を示している。さらに、その他（５）式の右辺第２項及び第３項の引力相互作用項について、変数ｘｉ，ｐに関係する項だけ抜き出して記述すると、（８）式の右辺第２項〜第５項に示すように導出できる。
【数８】
2018156281.tif 000010
【００５１】
ここで、変数ｘｉ，ｐに関連する項だけ抜き出して記述している理由は、後述するように変数ｘｉ，ｐで偏微分処理したときに当該変数ｘｉ，ｐに関連する項以外は０になるためであり、その記述を簡略化するためである。この実効評価値Ｈeffを表す（８）式の右辺は、変数ｘｉ，ｐの二次多項式となる。このため、（９）式のように実効評価値Ｈeffを偏微分して零となる条件を満たす変数ｘｉ，ｐが、実効評価値Ｈeffが極小値となる条件を満たす変数となる。
【数９】
2018156281.tif 000011
【００５２】
このため、この（９）式を数式展開すると（１０）式のようになる。
【数１０】
2018156281.tif 000012
【００５３】
この（１０）式について、変数ｘｉ，ｐについて解くと（１１）式に示すようになる。（１０）式に示したｉ番目以外の個体Ｋについても、変数ｘ≠ｉ，ｐの更新処理を同じように行うことができ、１からＮ番目の個体Ｋのｐ番目の変数ｘｊ，ｐは、（１１）式のように行列式を用いて一括更新できる。
【数１１】
2018156281.tif 000013
【００５４】
ただし、ｐ番目の更新後の変数~ｘｐ、更新前の変数ｘｐ＾＊は（１２−１）式、（１２−２）式のように表している。
【数１２】
2018156281.tif 000014
【００５５】
また、リプシッツ定数行列Ｌｐ、二次引力係数行列ρ、引力係数行列Ｇ、評価関数偏微分行列∇ｐＨopt（ｘｉ＾＊）、一次引力係数行列λｐ＾＊、係数行列Ｗ、は、それぞれ、（１３−１）式、（１４−１）式、（１４−２）式、（１５−１）式、（１５−２）式、（１５−３）式に示すように表すことができる。
【数１３】
2018156281.tif 000015
【００５６】
【数１４】
2018156281.tif 000016
【００５７】
【数１５】
2018156281.tif 000017
【００５８】
このように実効評価関数Ｈeff（｛ｘｉ｝）の全体が二次関数となることから更新式を容易に導出でき更新後の変数~ｘｐを容易に導出できる。続いて、図１１のＳ３において変数｛λｉ｝を更新する。この変数｛λｉ｝は、引力に関して更新するものであり、下記の（１６）式に示すように更新処理する。
【数１６】
2018156281.tif 000018
【００５９】
（１１）式を適用すると、「（Ｌ＋ρＧ）＾（−１）」に含まれるＧは正則行列ではないため、二次引力係数ρを大きくした場合にＧの特異性によって逆行列の計算精度が大幅に低下する。二次引力係数ρを正のあるスカラー値で固定とし、一次引力係数λｉを調整することで二次引力係数ρを必要以上に大きくすることなく算出できるようになり、計算精度を高めることができる。
【００６０】
そして、マイコン５はＳ４において終了条件を満たしていなければＳ２ａ、Ｓ３ａに処理を戻して繰り返すが、Ｓ４において終了条件を満たしたことを条件として、個体Ｋの変数｛ｘｐ｝の解を出力する。この終了条件は、一定回数の更新処理が上限回数に達したことを条件としたり、一定程度以上の収束条件が得られることを条件としたり、実効評価関数Ｈeffが所定値以下となることを条件とする、ことが挙げられるが、その他、様々な例を挙げることも可能である。
【００６１】
本実施形態によれば、評価関数Ｈoptを当該評価関数Ｈoptに近似した２次関数に置換し、この置換した２次関数に基づいて極値化するようにしたので、複雑な計算処理を要することなく計算精度を高めることができる。
【００６２】
（他の実施形態）
本発明は、上記した実施形態に限定されるものではなく、以下のように変形又は拡張することができる。
【００６３】
前述実施形態では、個体Ｋの変数ｘｉを解出力する形態を説明しているが、変数ｘｉに対応した評価値、すなわち、解出力すべき変数ｘｉを評価関数Ｈoptに代入した評価値を解出力するようにしても良い。また、この変数ｘｉの最適値を評価関数Ｈoptに代入した評価値を導出して解出力しても良い。
【００６４】
評価関数Ｈoptが極小値、最小値となる条件を満たす変数ｘｉを最適値として解出力する形態を示したが、極大値、最大値となる条件を満たす変数ｘｉを最適値として解出力する形態に適用しても良い。
【００６５】
所定の終了条件として、状態更新回数ｔが所定上限回数τを上回るか否かを条件としているが、これに限定されるものではなく、例えば変数ｘｉを代入した評価関数Ｈoptの評価値が所定値以下となっているか、などの異なる条件を用いても良い。Ｍは１、２、３次元以上の場合にも一般化して適用できる。
【００６６】
また、特許請求の範囲に記載した括弧内の符号は、本発明の一つの態様として前述する実施形態に記載の具体的手段との対応関係を示すものであって、本発明の技術的範囲を限定するものではない。前述実施形態の一部を、課題を解決できる限りにおいて省略した態様も実施形態と見做すことが可能である。また、特許請求の範囲に記載した文言によって特定される発明の本質を逸脱しない限度において、考え得るあらゆる態様も実施形態と見做すことが可能である。
【００６７】
また本発明は、前述した実施形態に準拠して記述したが、本発明は当該実施形態や構造に限定されるものではないと理解される。本発明は、様々な変形例や均等範囲内の変形をも包含する。加えて、様々な組み合わせや形態、さらには、それらに一要素、それ以上、あるいはそれ以下、を含む他の組み合わせや形態をも、本開示の範畴や思想範囲に入るものである。
【符号の説明】
【００６８】
図面中、１は最適化装置（連続最適化問題の大域的探索装置）、６は設定部、７は極値化部、８は導出部、Ｋは個体、Ｓは探索空間、ｘｉは変数、λｉは一次引力係数（引力相互作用）、ρｉ／２は二次引力係数（引力相互作用）、Ｈoptは評価関数、Ｈeffは実効評価値、Ｓａは限定探索範囲、ｘizは推定解、を示す。
【図１Ａ】
2018156281.tif 000025
【図１Ｂ】
2018156281.tif 000026
【図２】
2018156281.tif 000027
【図３Ａ】
2018156281.tif 000028
【図３Ｂ】
2018156281.tif 000029
【図３Ｃ】
2018156281.tif 000030
【図３Ｄ】
2018156281.tif 000031
【図４】
2018156281.tif 000032
【図５】
2018156281.tif 000033
【図６】
2018156281.tif 000034
【図７】
2018156281.tif 000035
【図８】
2018156281.tif 000036
【図９】
2018156281.tif 000037
【図１０】
2018156281.tif 000038
【図１１】
2018156281.tif 000039