(57)【要約】【課題】コンピュータによる最適解探索において、局所解への陥りを抑制し、信頼性の高い解を索出することが可能な技術を提供する。【解決手段】与えられた評価関数に対する最適解をコンピュータによる繰り返し計算により求める最適解探索方法であって、解の候補である複数の個体それぞれの初期値と、繰り返し計算の終了条件と、を少なくとも設定する初期設定ステップと、各個体の値を評価関数に代入し各個体の評価値を計算する処理を、前記終了条件が満たされるまで、各個体の値を更新しながら、繰り返す探索ステップと、前記探索ステップにおいて最良の評価値を与えた個体の値を、前記評価関数の最適解として出力する出力ステップと、を含む。前記探索ステップでは、前記複数の個体それぞれの値を更新する際に、前記複数の個体のうちの一部の個体については、その個体の現在の値および評価値のいずれとも独立した乱数項を含む更新式が適用される。【選択図】図１
2014178717.tif 000002
【特許請求の範囲】
【請求項１】
与えられた評価関数に対する最適解をコンピュータによる繰り返し計算により求める最適解探索方法であって、
コンピュータが、解の候補である複数の個体それぞれの初期値と、繰り返し計算の終了条件と、を少なくとも設定する初期設定ステップと、
コンピュータが、各個体の値を評価関数に代入し各個体の評価値を計算する処理を、前記終了条件が満たされるまで、各個体の値を更新しながら、繰り返す探索ステップと、
コンピュータが、前記探索ステップにおいて最良の評価値を与えた個体の値を、前記評価関数の最適解として出力する出力ステップと、を含み、
前記探索ステップでは、
前記複数の個体それぞれの値を更新する際に、前記複数の個体のうちの一部の個体については、その個体の現在の値および評価値のいずれとも独立した乱数項を含む更新式が適用される
ことを特徴とする最適解探索方法。
【請求項２】
前記乱数項は、一様乱数とゲインとの積を含んでいる
ことを特徴とする請求項１に記載の最適解探索方法。
【請求項３】
前記探索ステップは、繰り返し計算のたびに前記ゲインを減少させるステップを含む
ことを特徴とする請求項２に記載の最適解探索方法。
【請求項４】
前記探索ステップは、前記複数の個体すべての評価値が所定の範囲に収まった場合に、前記ゲインを増加させるステップを含む
ことを特徴とする請求項３に記載の最適解探索方法。
【請求項５】
前記所定の範囲は、その時点での最良の評価値から所定の範囲である
ことを特徴とする請求項４に記載の最適解探索方法。
【請求項６】
前記探索ステップにおいて前記乱数項を含む更新式が適用される個体は、常に同じ個体である
ことを特徴とする請求項１〜５のいずれかに記載の最適解探索方法。
【請求項７】
前記探索ステップでは、粒子群最適化方法によって最適解の探索が行われ、
前記更新式は、個体の速度を更新するための更新式である
ことを特徴とする請求項１〜６のいずれかに記載の最適解探索方法。
【請求項８】
前記一部の個体以外の個体の速度を更新するための更新式が、下記式（１）、
前記一部の個体の速度を更新するための更新式が、下記式（２）、
下記式（１）又は（２）によって更新された速度を用いて、個体の位置を更新するための更新式が、下記式（３）、
で表されることを特徴とする請求項７に記載の最適解探索方法。
【数１】
2014178717.tif 000015
【請求項９】
前記探索ステップでは、遺伝的アルゴリズムによって最適解の探索が行われ、
前記更新式は、個体の値を更新するための更新式である
ことを特徴とする請求項１〜６のいずれかに記載の最適解探索方法。
【請求項１０】
前記一部の個体以外の個体の値を更新するための更新式が、下記式（２１）、
前記一部の個体の値を更新するための更新式が、下記式（２２）、
で表されることを特徴とする請求項９に記載の最適解探索方法。
【数２】
2014178717.tif 000016
【請求項１１】
前記乱数項の取り得る値の範囲を指定可能である
ことを特徴とする請求項１〜１０のいずれかに記載の最適解探索方法。
【請求項１２】
請求項１〜１１のいずれかに記載の最適解探索方法の各ステップをコンピュータに実行させることを特徴とするプログラム。
【請求項１３】
請求項１２に記載のプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項１４】
与えられた評価関数に対する最適解をコンピュータによる繰り返し計算により求める最適解探索装置であって、
解の候補である複数の個体それぞれの初期値と、繰り返し計算の終了条件と、を少なくとも設定する初期設定手段と、
各個体の値を評価関数に代入し各個体の評価値を計算する処理を、前記終了条件が満たされるまで、各個体の値を更新しながら、繰り返し実行する探索手段と、
前記探索手段による繰り返し計算において最良の評価値を与えた個体の値を、前記評価関数の最適解として出力する出力手段と、を有し、
前記探索手段は、
前記複数の個体それぞれの値を更新する際に、前記複数の個体のうちの一部の個体については、その個体の現在の値および評価値のいずれとも独立した乱数項を含む更新式を適用する
ことを特徴とする最適解探索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータによる最適解探索において、局所解に陥る欠点を改善するための技術に関する。
【背景技術】
【０００２】
複雑な関数を最小化あるいは最大化するパラメータ（最適解）を、コンピュータによる繰り返し計算によって求める方法は「最適解探索」と呼ばれる。コンピュータによる最適解探索のアルゴリズムとしては、粒子群最適化（Particle Swarm Optimization:ＰＳＯ）、遺伝的アルゴリズム（Genetic Algorithm：ＧＡ）などが知られている（非特許文献１
、非特許文献２参照）。
【０００３】
ＰＳＯとは、昆虫や鳥などの大群の挙動を模倣した探索方法であり、群れ全体で発見した解と個体それぞれが発見した解に基づき探索を行うというものである。一方、ＧＡとは、生物の遺伝過程を模倣した探索方法であり、解の候補と評価値をもつ個体を複数用意し、交叉（良い評価値をもつ個体同士を組み合わせて新たな個体を生成する操作）、突然変異（個体がもつ変数の一部を変化させる操作）などの操作を繰り返すことで最適解を探索するという方法である。
【０００４】
この種の最適解探索においては、局所解への陥りを回避することが共通の技術課題となる。例えば非特許文献１では、ＰＳＯの改良型として、個体の速度更新式の慣性項を動的に変化させる方法が提案されている。具体的には、計算初期では慣性項の係数を大きくし個体の挙動にバラツキを持たせることで、局所解への陥りを抑制する一方で、計算後期では慣性項の係数を小さくしていくことで収束性を向上させ、暫定解の周辺を集中的に探索するという方法である。しかしながら、この方法では、計算後期において暫定解の周辺に全ての個体が集中してしまうため、大域解（真の最適解）の探索ができなくなるおそれがある。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】P.C. Fourie and A.A. Groenwold, "The particle swarm optimization algorithm in size and shape optimization", Struct Multidisc Optim Vol.23, pp.259-267, 2002.
【非特許文献２】C.B. Lucasius and G. Kateman (1993). 「Understanding and using genetic algorithms - Part 1. Concepts, properties and context.」 Chemometrics and Intelligent Laboratory Systems 19:1-33.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明は上記実情に鑑みてなされたものであって、その目的とするところは、コンピュータによる最適解探索において、局所解への陥りを抑制し、信頼性の高い解を索出することが可能な技術を提供することにある。
【課題を解決するための手段】
【０００７】
上記目的を達成するために本発明は、以下の構成を採用する。すなわち、本発明の一態様に係る最適解探索方法は、与えられた評価関数に対する最適解をコンピュータによる繰り返し計算により求める最適解探索方法であって、コンピュータが、解の候補である複数の個体それぞれの初期値と、繰り返し計算の終了条件と、を少なくとも設定する初期設定
ステップと、コンピュータが、各個体の値を評価関数に代入し各個体の評価値を計算する処理を、前記終了条件が満たされるまで、各個体の値を更新しながら、繰り返す探索ステップと、コンピュータが、前記探索ステップにおいて最良の評価値を与えた個体の値を、前記評価関数の最適解として出力する出力ステップと、を含み、前記探索ステップでは、前記複数の個体それぞれの値を更新する際に、前記複数の個体のうちの一部の個体については、その個体の現在の値および評価値のいずれとも独立した乱数項を含む更新式が適用されることを特徴とする最適解探索方法である。
【０００８】
最適解探索においては、各個体の値や評価値、その時点における最良の解（暫定解と呼ぶ）などに基づいて各個体の値を更新する操作を繰り返し行い、より良い評価値を与える解を探索することが基本となる。しかし従来の方法では、全ての個体の挙動が暫定解に拘束される結果、その周辺領域しか探索されず、局所解に陥る場合がある。
【０００９】
これに対し、本発明では、更新式に乱数項を導入したことによって、一部の個体の値に対して適度なバラツキを付与することができる。しかも、乱数項は個体の値や評価値とは独立した項になっているため、付与されるバラツキの大きさや方向は、各個体の値や暫定解とは無関係に決まるものとなる。したがって、本発明によれば、少なくとも一部の個体が暫定解からの拘束を離れ、暫定解の周辺以外の領域もランダムに探索するような挙動をとるため、局所解への陥りを可及的に回避し、且つ、より良い解をより少ない計算回数で発見できるようになるものと期待できる。
【００１０】
また、本発明では、乱数項を含む更新式が適用される個体（特定個体と呼ぶ）を「一部の個体」に限定したことによって、収束性の低下を抑制することができる。特定個体の割合（もしくは数）については、評価関数や個体の次元数などに応じて適宜決定すればよい。ところで、特定個体は更新の都度任意に選んでもよいが、好ましくは、常に同じ個体であるとよい。乱数項を含む更新式が適用される個体とそれ以外の更新式が適用される個体とを予め固定しておくことにより、更新式および乱数項の設計が容易になるとともに、処理（プログラム）が単純化されるという利点があるからである。特定個体の選択方法（選択規則）としては、どのようなものを用いてもよい。例えば、全ての個体の中からランダムに特定個体を選ぶ方法、個体の位置に基づいて選ぶ方法、個体の評価値に基づいて選ぶ方法などがある。個体の位置に基づいて選ぶ方法としては、例えば、暫定解からの距離が遠い個体を優先的に特定個体としてもよいし、暫定解から所定の距離範囲にある個体を優先的に特定個体としてもよいし、暫定解からの距離が偏らないように群全体の位置分布に基づき様々な位置から特定個体を選び出してもよい。また、評価値に基づいて選ぶ方法としては、例えば、評価値の悪い個体を優先的に特定個体としてもよいし、逆に評価値の良い個体の中から特定個体を選んでもよいし、特定個体の評価値が偏らないように群全体の評価値分布に基づき様々な評価値の個体を特定個体として選んでもよい。
【００１１】
ここで、前記乱数項は、一様乱数とゲインとの積を含んでいることが好ましい。ゲインの値を調整するだけで、個体の多様性や集中性を簡単に制御できるようになるからである。
【００１２】
例えば、前記探索ステップにおいて、繰り返し計算のたびにゲインを減少させていけば、探索が進むにしたがって特定個体の動きが安定するため、集中性を向上させることができる。さらに、前記探索ステップにおいて、前記複数の個体すべての評価値が所定の範囲に収まった場合に、前記ゲインを増加させるようにしてもよい。これにより、探索途中で各個体の挙動が鈍くなってしまった場合などに、特定個体の動きを再び活発にすることができるので、局所解への陥りを防ぐことが可能となる。例えば、その時点での最良の評価値（暫定解に対する評価値）から所定の範囲にすべての個体の評価値が収まった場合などに、ゲインの増加（特定個体の活発化）を行うとよい。
【００１３】
前記探索ステップでは、粒子群最適化（ＰＳＯ）、遺伝的アルゴリズム（ＧＡ）など、任意の最適解探索方法を用いることができる。
【００１４】
例えば、ＰＳＯによって最適解の探索が行われる場合には、前記更新式は、個体の速度を更新するための更新式であるとよい。より詳しくは、前記一部の個体以外の個体の速度を更新するための更新式を下記式（１）、前記一部の個体の速度を更新するための更新式を下記式（２）とすることが好ましい。個体の値（位置）を更新するための更新式は、下記式（１）又は（２）によって更新された速度を用いて、下記式（３）のように設計する。
【数１】
2014178717.tif 000003
【００１５】
また、ＧＡによって最適解の探索が行われる場合には、前記更新式は、個体の値を更新するための更新式であるとよい。より詳しくは、前記一部の個体以外の個体の値を更新するための更新式を下記式（２１）、前記一部の個体の値を更新するための更新式を下記式（２２）のように設計することが好ましい。
【数２】
2014178717.tif 000004
【００１６】
本発明は、上記ステップの少なくとも一部を含む最適解探索方法として捉えてもよいし、かかる方法の各ステップをコンピュータに実行させるためのプログラムやそのプログラムを記憶したコンピュータ読み取り可能な記憶媒体として捉えることもできる。また、本発明は、上記の機能手段の少なくとも一部を有する最適解探索装置やシステムとして捉えることもできる。なお、上記手段および処理の各々は可能な限り互いに組み合わせて本発明を構成することができる。
【００１７】
例えば、本発明の一態様に係る最適解探索装置は、与えられた評価関数に対する最適解をコンピュータによる繰り返し計算により求める最適解探索装置であって、解の候補である複数の個体それぞれの初期値と、繰り返し計算の終了条件と、を少なくとも設定する初期設定手段と、各個体の値を評価関数に代入し各個体の評価値を計算する処理を、前記終了条件が満たされるまで、各個体の値を更新しながら、繰り返し実行する探索手段と、前記探索手段による繰り返し計算において最良の評価値を与えた個体の値を、前記評価関数の最適解として出力する出力手段と、を有し、前記探索手段は、前記複数の個体それぞれの値を更新する際に、前記複数の個体のうちの一部の個体については、その個体の現在の値および評価値のいずれとも独立した乱数項を含む更新式を適用することを特徴とする最適解探索装置である。
【発明の効果】
【００１８】
本発明によれば、コンピュータによる最適解探索において、局所解への陥りを抑制し、信頼性の高い解を索出することが可能となる。
【図面の簡単な説明】
【００１９】
【図１】（ａ）は従来の最適解探索方法の処理例を模式的に示す図であり、（ｂ）は本発明の最適解探索方法の処理例を模式的に示す図である。
【図２】第１実施形態の最適解探索装置の機能構成を模式的に示すブロック図である。
【図３】第１実施形態の最適解探索処理のフローチャートである。
【図４】（ａ）は第１実施形態の処理結果を示す図であり、（ｂ）は乱数項の無い比較例の処理結果を示す図である。
【図５】第２実施形態の最適解探索処理のフローチャートである。
【発明を実施するための形態】
【００２０】
本発明は、与えられた評価関数（目的関数とも呼ぶ）に対する最適解をコンピュータによる繰り返し計算により求める最適解探索に関し、より詳しくは、最適解探索における局所解への陥りを抑制する方法に関するものである。本発明は、既存の最適解探索方法の改良（性能向上）を可能にするものであり、例えば、粒子群最適化（ＰＳＯ）、遺伝的アルゴリズム（ＧＡ）をはじめとするあらゆる最適解探索方法に対して適用することができる。なお、本発明が適用される最適解探索方法の応用範囲は多岐にわたり、例えば、学術、研究、産業などの分野において、数値計算、問題解析、予測分析、各種シミュレーションなどに広く利用可能であることは言うまでもない。
【００２１】
以下では、まず本発明に係る最適解探索の基本概念について説明を行い、その後で、本発明を粒子群最適化（ＰＳＯ）に適用した例（第１実施形態）と、遺伝的アルゴリズム（ＧＡ）に適用した例（第２実施形態）をそれぞれ説明する。
【００２２】
＜最適解探索の基本概念＞
図１を参照して、従来の最適解探索の問題点と、本発明に係る最適解探索の基本概念について説明する。図１は、評価関数ｆ（ｘ）を最小にする解ｘを求める探索問題の処理例
を模式的に示すものであり、（ａ）は従来の最適解探索方法の例、（ｂ）は本発明に係る最適解探索方法の例をそれぞれ示している。
【００２３】
ここで、関数ｆ（ｘ）には、極小値をとる位置ｘが３箇所存在する。このうち左の２つは局所解（近傍領域のみをみたときに関数ｆ（ｘ）を最小化するｘの値）であり、一番右のものが大域解（関数ｆ（ｘ）を最小化するｘの値）である。すなわち、同図の探索問題では、一番右の大域解の位置を発見することが理想となる。
【００２４】
（ａ）の左図に示すように、まず、解の候補である複数の個体が、任意の初期位置に配置される。そして、ｆ（ｘ）の値を評価しながら各個体の位置ｘを更新するという操作を繰り返すことによって、評価値ｆ（ｘ）をより小さくする位置ｘを探索する。個体の位置を更新するアルゴリズムには様々なものが存在するが、基本的な考え方は、その時点における最良の解（暫定解）に向かって各個体を移動させていき、探索範囲を絞り込んでいくという方法が一般的である。（ａ）の中央図では、暫定解である黒丸で示した個体の位置に向かって、それぞれの個体が移動している様子が示されている。しかしながら、このような従来方法の場合、全ての個体の挙動が暫定解に拘束されることとなるため、（ａ）の右図に示すように、局所解の周辺に個体が集中してしまい、大域解を発見できない（あるいは、大域解に至るまでに膨大な繰り返し計算が必要になる）場合がある。
【００２５】
このような問題を解決するため、本発明に係る最適解探索では、（ｂ）に示すように、個体の位置を更新する際に、一部の個体に対し乱数によるバラツキを付与することとする。これにより、一部の個体（×印で示した個体）が、暫定解の拘束を離れて、暫定解とは無関係な方向に移動することが可能となる。したがって、暫定解の周辺だけでなく、暫定解の周辺以外の領域も含めた、広範囲な探索が可能となり、従来方法のような局所解への陥りを可及的に回避することができる。
【００２６】
以下、本発明に係る最適解探索の特徴部分である個体の更新アルゴリズムについて、具体的な実施形態を挙げて詳しく説明する。
【００２７】
＜第１実施形態＞
第１実施形態では、本発明を粒子群最適化（ＰＳＯ）による最適解探索に適用する例について説明する。
【００２８】
ＰＳＯとは、昆虫や鳥などの大群の挙動を模倣した探索方法であり、一つの個体が良い解を発見すると、それを他の個体に通知し、他の個体がその解の位置に向かって探索を行うというものである。ＰＳＯでは、各個体が、位置ｘと速度ｖの２つのパラメータをもつ。
【００２９】
オリジナルのＰＳＯにおける位置ｘと速度ｖの更新式は以下のとおりである。すなわち、個体の慣性ｗｖ、個体の位置ｘと個体の最良位置ｐｂｅｓｔの差分、及び、個体の位置ｘと群全体の最良位置ｇｂｅｓｔの差分に基づいて、速度ｖが更新され、元の位置ｘに速度ｖを加算することで位置ｘが更新される。なお、個体のパラメータが多次元の場合、下記式のｘ，ｖ，ｐｂｅｓｔ，ｇｂｅｓｔ，Ｒ１，Ｒ２はベクトルとなる。
【数３】
2014178717.tif 000005
【００３０】
本実施形態では、上記の更新式に対し、以下のような改良ないし拡張を施す。すなわち、１〜ｍ−１番目の個体については、オリジナルのＰＳＯと同様の更新式（１）を用いて速度ｖを計算するのに対し、ｍ〜ｎ番目の個体については、乱数項Ψを含む更新式（２）を用いて速度ｖを計算する。なお、位置ｘの更新式（３）はオリジナルのＰＳＯと同じものを用いる。
【数４】
2014178717.tif 000006
【００３１】
乱数項Ψを含む更新式（２）が適用される個体（特定個体と呼ぶ）の割合（もしくは数）は任意に設定することができる。ただし、特定個体の割合が増えると収束性の低下を招
く可能性があるため、評価関数ｆ（ｘ）や個体のパラメータの次元数などに応じて適宜設定するとよい。
【００３２】
なお、慣性係数ｗｋはオリジナルのＰＳＯと同様に定数としてもよいが、本実施形態では下記式のように探索の進行に伴って慣性係数ｗｋを徐々に小さくしていく。また、速度ｖについても、ｖ≦ｖｍａｘのように上限を設けるとともに、探索の進行に伴って最大速度ｖｍａｘの値を徐々に小さくするとよい。このように慣性係数ｗｋと最大速度ｖｍａｘの調整を行うことによって、探索初期では個体に多様性を持たせ大域的探索能力を向上することができる一方で、探索が進行するにしたがって集中性を高め局所的探索能力を向上することができるという利点がある。
【数５】
2014178717.tif 000007
【００３３】
（乱数項の設計）
乱数項Ψとしては、個体の位置ｘ、速度ｖ、評価値ｆ（ｘ）、個体や群全体の最良位置ｐｂｅｓｔ、ｇｂｅｓｔと独立しており、且つ、ランダムな値をとるものであれば、どのような変数を用いることもできる。ただし、乱数項Ψは更新式（２）の安定性に影響を与え得るため、以下に述べる条件に従って乱数項Ψを設計することが好ましい。
【００３４】
ここでは、上述した更新式（２）の安定性尺度に基づき、乱数項Ψの設計を行う。一般にＰＳＯの安定性解析には、乱数項ｃＲを一定とみなし、速度ｖと位置ｘを一次元としたモデルがよく用いられる。そうすると、更新式（２）のモデルは、下記のようになる。
【数６】
2014178717.tif 000008
【００３５】
一般に、最適化問題が多峰性ならば、その最適解の探索には、多様化と集中化、すなわち大域的探索能力と局所的探索能力の両方を備えた手法が望ましい。ここでは、大域的探索を行う場合には多様性を持ち、局所的探索を行う場合には集中性を持つように、乱数項Ψをシステム（４）の安定性の解析に基づいて設計する。
【００３６】
まず、リアプノフ第二の方法を用いてシステム（４）の安定性の解析を行う。
スカラ関数Ｖ（ｚ）を下記式のようにおく。
【数７】
2014178717.tif 000009
【００３７】
λ１（ｋ），λ２（ｋ）は（４）のシステム行列の固有値であり、Ｔは対角変換行列である。
【００３８】
この関数はｚの全域で存在し、ＴＴＤＴＤＴが正定であることから、下記が成り立つ。
【数８】
2014178717.tif 000010
また、Ｖ（０）＝０である。さらに、下記式が成り立つ。
【数９】
2014178717.tif 000011
ここで、ｚ（ｋ）ＴＴ（ｋ）ＴＤ(ｋ)ＴＴ(ｋ)とｚ（ｋ＋１）ＴＴ（ｋ＋１）ＴＤ(ｋ＋
１)ＴＴ(ｋ＋１)は正定であることから、ΔＶ(ｚ)が負定となる条件はＤ（ｋ＋１）ＴＤ
（ｋ＋１）−Ｉが負定となることである。すなわち固有値λ１（ｋ），λ２（ｋ）の絶対値が１より小さいときにΔＶ（ｚ）が負定となる。
【００３９】
以上のことから、固有値λ１（ｋ），λ２（ｋ）の絶対値が１より小さければ安定である。固有値が１より小さい条件は、以下のとおりである。
【数１０】
2014178717.tif 000012
【００４０】
次に、式（２）の安定性尺度に基づき、乱数項の設計を行う。
前述のように、探索初期では、個体の多様性を高め大域的探索能力を上げることが望まれる。そのため、乱数項Ψを、探索初期で大きい振幅の乱数となるように設計することで、多様性を高めることができる。加えて、慣性係数ｗｋの初期値は１以上に設定することで、さらに多様性を高めることができる。
【００４１】
探索中期においては、慣性係数ｗｋが徐々に小さくなり、式（９）を満たすようになることで、システムが安定になる。一般に入力項を０としたときにシステムが安定であるならば、そのシステムの状態は有界な入力に対して有界となることが知られている。そのため、システム（４）のｐｋに関する入力項とΨに関する入力項は有界な値であるとよい。
【００４２】
探索後期では、ｋ＞＞１に対してシステム（４）の入力を０とすることで収束させる。
【００４３】
ところで、システム（４）が収束したとしても、その収束先が大域解ではなく局所解である可能性がある。そのため、群全体が所定の範囲内に収束したときは、乱数項Ψの振幅を増加させることで、特定個体の動きを再び活発にすることが望ましい。
【００４４】
以上を踏まえ、本実施形態では、乱数項Ψを一様乱数Ｒ３と乱数ゲインｗｆとの積で定義し、且つ、乱数ゲインｗｆを下記のように制御する。すなわち、繰り返し計算のたびに乱数ゲインｗｆを徐々に減少させていくが、もし全ての個体の評価値ｆ（ｘ）が暫定解ｇｂｅｓｔに対する評価値ｆ（ｇｂｅｓｔ）から所定の範囲ε内に収まった場合には、例外的に、乱数ゲインｗｆを一定量Δｗだけ増加させるのである。所定の範囲εはどのような値に設定してもよいが、好ましくは、関数ｆ（ｘ）において複数の局所解が存在しないと予想される範囲（値域）をεに設定するとよい。このような範囲εは、例えば、探索初期における群全体の評価値の分布（分散、平均、最大値、最小値など）に基づいて決定することができる。
【数１１】
2014178717.tif 000013
【００４５】
（装置構成）
次に、上述した最適解探索を実現するための装置構成および処理フローの具体例について説明する。
【００４６】
図２は、本実施形態の最適解探索装置の機能構成を模式的に示すブロック図である。最適解探索装置は、演算部１、入力部２、及び出力部３から構成され、さらに演算部１は、初期条件設定部１０、探索処理部１１、及び乱数制御部１２から構成されている。同装置は、例えば、中央演算処理装置（ＣＰＵ）、主記憶装置（ＲＡＭ）、補助記憶装置（ＨＤＤ、ＳＳＤなど）、入力装置（キーボード、マウスなど）、表示装置などのハードウエア資源を備える汎用のコンピュータによって構成することができる。図２に示す各機能は、ＣＰＵが補助記憶装置に格納されたプログラムをＲＡＭにロードし、当該プログラムを実行することにより実現されるものである。
【００４７】
図３のフローチャートに沿って、最適解探索装置の各機能の詳細並びに最適解探索処理の流れを説明する。
【００４８】
Ｓ１０では、初期条件設定部１０が、表示装置などの出力部３に対し、初期条件設定画面を出力することにより、ユーザーに初期条件の入力を促す。ユーザーがキーボードなどの入力部２を介して初期条件を入力すると、初期条件設定部１０がそれらの初期条件を記憶装置に格納する。ここで入力される初期条件としては、評価関数、解の候補である複数の個体それぞれの初期値（初期位置及び初期速度）、終了条件などがある。終了条件としては、繰り返し演算の回数を指定することもできるし、解が収束したことを判定するための収束条件を指定することもできる。収束条件としては、例えば、所定回数の繰り返し計算を実行しても解が更新されないことを条件としたり、目標の評価値に対して許容誤差を指定し、その誤差範囲内に収まる解が発見されることを条件としたりすることができる。また必要に応じて、特定個体の数又は割合、特定個体の選択方法（選択規則）、乱数項Ψの取り得る値の範囲（つまり、乱数ゲインｗｆの初期値、範囲など）、更新式（１）、（２）における各種係数の値、慣性係数や最大速度の調整係数α，β、乱数ゲインの調整係数Ｋ，Δｗなどを設定することも可能である。このように特定個体の選び方や特定個体に
付与する乱数（バラツキ）などの設定値をユーザーが設定できるようにすることで、最適解探索装置の特性（大域的探索能力と局所的探索能力のバランス、収束性、安定性など）を目的や用途に応じてユーザー自身が自由に調整できるようになる。
【００４９】
初期条件の設定が完了すると、探索処理部１１が、終了条件を満足するまでＳ１１〜Ｓ１９の繰り返し計算を実行し、最適解を探索する。Ｓ１１では、探索処理部１１が、各個体の位置ｘを評価関数ｆ（ｘ）に代入し、各個体の評価値を求める。Ｓ１２では、探索処理部１１は、Ｓ１１で求めた各個体の評価値を、それまでに得られたｆ（ｐｂｅｓｔ）、ｆ（ｇｂｅｓｔ）の値と比較し、より良い解が発見された場合にはｐｂｅｓｔ、ｇｂｅｓｔを更新する。Ｓ１３及びＳ１４では、探索処理部１１が、式（１）、（２）の速度更新式を用いて、各個体の速度ｖを計算する。このとき、特定個体の速度に対しては、式（２）の乱数項Ψによりバラツキが付与される。そして、Ｓ１５において、探索処理部１１は、式（３）の位置更新式を用いて、各個体の位置ｘを計算する。
【００５０】
その後、Ｓ１６において、乱数制御部１２は、全ての個体の評価値がｆ（ｇｂｅｓｔ）＋εの範囲内に収まっているかどうかを判定し、収まっていなければ、式（１１）により乱数ゲインｗｆを減少し（Ｓ１７）、収まっている場合は、式（１２）により乱数ゲインｗｆを増加する（Ｓ１８）。
【００５１】
次に、Ｓ１９において、探索処理部１１が、Ｓ１０で設定された終了条件を満足しているか否かを判断し、終了条件に満たなければＳ１１へ戻り、終了条件を満足していればＳ２０に進む。そしてＳ２０において、探索処理部１１は、ｇｂｅｓｔの値を評価関数ｆ（ｘ）の最適解として出力部３などに出力し、最適解探索処理を終了する。
【００５２】
（比較実験）
本発明の効果を検証するため、本発明者は、最適解探索のベンチマークテストによく利用されるＧｒｉｅｗａｎｋ関数を用いて、第１実施形態の最適解探索処理における評価値の推移と、式（２）の乱数項Ψを無くした場合の評価値の推移とを比較した。その結果を、図４に示す。（ａ）が第１実施形態の処理結果を示し、（ｂ）が乱数項Ψの無い比較例の処理結果を示している。第１実施形態の処理のほうが、少ない繰り返し計算数でより良い解に到達できていることがわかる。
【００５３】
さらに、本発明者らは、比較例の処理で得られた評価値の平均を第１実施形態の処理で得られた評価値の平均で割った値を「性能改善比」と定義し、３次元の個体を用いた場合と、１０次元の個体を用いた場合それぞれの評価を行った。その結果、３次元の個体の場合には性能改善比が約２．０、１０次元の個体の場合には性能改善比が約２．４となり、いずれの場合も性能が向上していることが検証できた。
【００５４】
（本実施形態の利点）
以上述べた本実施形態の構成によれば、速度の更新式（２）に乱数項Ψを導入したことによって、一部の個体の値に対して適度なバラツキを付与することができる。しかも、乱数項Ψは個体の値ｘ，ｖや評価値ｆ（ｘ）とは独立した項になっているため、付与されるバラツキの大きさや方向は、各個体の値ｘ，ｖや暫定解ｇｂｅｓｔ，ｐｂｅｓｔとは無関係に決まるものとなる。したがって、本実施形態によれば、少なくとも一部の個体が暫定解からの拘束を離れ、暫定解の周辺以外の領域もランダムに探索するような挙動をとるため、局所解への陥りを可及的に回避し、且つ、より良い解をより少ない計算回数で発見できるようになる。
【００５５】
また、本実施形態では、乱数項Ψを含む更新式（２）が適用される個体を一部の個体に限定したことによって、収束性の低下を抑制することができる。また、乱数項Ψを含む更
新式（２）が適用される個体とそれ以外の更新式（１）が適用される個体とを予め固定したことにより、更新式（１）、（２）および乱数項Ψの設計が容易になるとともに、処理（プログラム）が単純化されるという利点がある。
【００５６】
さらに、本実施形態では、一様乱数Ｒ３と乱数ゲインｗｆの積からなる乱数項Ψを用いたので、乱数ゲインｗｆの値を調整するだけで、乱数の振幅の大小を調整でき、個体の多様性や集中性を簡単に制御することができる。また、Ｓ１７（式（１１））に示すように、繰り返し計算のたびに乱数ゲインｗｆを減少させていくので、探索が進むにしたがって特定個体の動きが安定し、集中性を向上させることができる。一方、Ｓ１８（式（１２））に示すように、全ての個体の評価値が所定の範囲に収まってしまった場合は、乱数ゲインｗｆを増加させる。これにより、探索途中で各個体の挙動が鈍くなってしまった場合などに、特定個体の動きを再び活発にすることができるので、局所解への陥りを防ぐことが可能となる。
【００５７】
＜第２実施形態＞
第２実施形態では、本発明を遺伝的アルゴリズム（ＧＡ）による最適解探索に適用する例について説明する。
【００５８】
ＧＡとは、生物の遺伝過程を模倣した探索方法であり、個体の値を遺伝子に見立て、交叉（良い評価値をもつ個体の遺伝子同士を組み合わせて次の世代の個体を生成する操作）、突然変異（個体の遺伝子の一部を変化させる操作）などの操作を繰り返しながら、より良い評価値を与える個体を探索する方法である。本実施形態では、ＧＡによって個体を生成した後、一部の個体に対し乱数によるバラツキを与えることによって、局所解への陥りを抑制している。ＧＡ自体の処理は従来公知のものをそのまま利用できるため、ここではＧＡの詳しい説明は省略し、本実施形態の特徴的な処理部分についてのみ説明を行う。なお、本実施形態の最適解探索処理を実行するための装置構成は、図２で示したものと同じであるため、以下、図２の符号も参照して説明を行うものとする。
【００５９】
では、図５のフローチャートに沿って、第２実施形態に係る最適解探索処理の流れを説明する。
【００６０】
Ｓ３０では、まず初期条件設定部１０が、表示装置などの出力部３に対し、初期条件設定画面を出力することにより、ユーザーに初期条件の入力を促す。ユーザーがキーボードなどの入力部２を介して初期条件を入力すると、初期条件設定部１０がそれらの初期条件を記憶装置に格納する。ここで入力される初期条件としては、評価関数、解の候補である複数の個体それぞれの初期値、終了条件などがある。終了条件としては、繰り返し演算の回数を指定することもできるし、解が収束したことを判定するための収束条件を指定することもできる。また必要に応じて、特定個体の数又は割合、特定個体の選択方法、乱数項Ψの取り得る値の範囲、乱数ゲインの調整係数Ｋ，Δｗなどを設定することも可能である。
【００６１】
初期条件の設定が完了すると、探索処理部１１が、終了条件を満足するまでＳ３１〜Ｓ３８の繰り返し計算を実行し、最適解を探索する。Ｓ３１では、探索処理部１１が、各個体の値ｘを評価関数ｆ（ｘ）に代入し、各個体の評価値を求める。Ｓ３２では、Ｓ３１で求めた各個体の評価値に基づいて選択した複数の個体に対し、交叉、突然変異などの操作を行い、次世代の個体を生成する。
【００６２】
その後、Ｓ３３において、探索処理部１１が、一部の個体の値に対し、乱数によるバラツキを付与する。Ｓ３３で用いられる更新式は下記のとおりである。すなわち、１〜ｍ−１番目の個体については、Ｓ３２で生成された値ｘ´がそのまま用いられ、ｍ〜ｎ番目の
個体については、更新式（２２）により、値ｘ´に乱数項Ψが加算される。
【数１２】
2014178717.tif 000014
【００６３】
ここで、乱数項Ψとしては、第１実施形態の式（１０）と同じく、一様乱数Ｒ３と乱数ゲインｗｆの積で定義されたものを用いることができる。ただし、第１実施形態の場合と異なり、第２実施形態ではＧＡのシステムの安定性は担保されているため、乱数ゲインｗｆの値に特に制約はない。
【００６４】
Ｓ３４では、探索処理部１１は、Ｓ３１で求めた各個体の評価値を、それまでに得られたｆ（ｇｂｅｓｔ）の値と比較し、より良い解が発見された場合にはｇｂｅｓｔを更新する。
【００６５】
その後、Ｓ３５において、乱数制御部１２は、全ての個体の評価値がｆ（ｇｂｅｓｔ）＋εの範囲内に収まっているかどうかを判定し、収まっていなければ、式（１１）により乱数ゲインｗｆを減少し（Ｓ３６）、収まっている場合は、式（１２）により乱数ゲインｗｆを増加する（Ｓ３７）。
【００６６】
次に、Ｓ３８において、探索処理部１１が、Ｓ３０で設定された終了条件を満足しているか否かを判断し、終了条件に満たなければＳ３１へ戻り、終了条件を満足していればＳ３９に進む。そしてＳ３９において、探索処理部１１は、ｇｂｅｓｔの値を評価関数ｆ（ｘ）の最適解として出力部３などに出力し、最適解探索処理を終了する。
【００６７】
（比較実験）
本発明の効果を検証するため、Ｇｒｉｅｗａｎｋ関数を用いて、第２実施形態の最適解探索処理の結果と、比較例として式（２２）の乱数項Ψを無くした場合の処理結果とを比較した。３次元の個体を用いた場合と、１０次元の個体を用いた場合それぞれの評価を行ったところ、３次元の個体の場合も１０次元の個体の場合も性能改善比が約２．０となり、いずれの場合も性能が向上していることが検証できた。
【００６８】
以上述べたように、本実施形態の構成によっても、第１実施形態と同様の作用効果が得られ、局所解への陥りを可及的に回避し、且つ、より良い解をより少ない計算回数で発見できるようになる。
【符号の説明】
【００６９】
１  演算部
２  入力部
３  出力部
１０  初期条件設定部
１１  探索処理部
１２  乱数制御部
【図１】
2014178717.tif 000017
【図２】
2014178717.tif 000018
【図３】
2014178717.tif 000019
【図４】
2014178717.tif 000020
【図５】
2014178717.tif 000021