(57)【要約】【課題】局所最適解の近くに真の最適解の存在する実数値ベクトル最適化問題に対して、真の最適解の発見率を向上させる。【解決手段】最適化装置１００の最適化部１１０は、遺伝的アルゴリズムに基づき、所定の実数値ベクトル領域のうちの探索禁止領域を除外した領域内で目的関数を最小化または最大化する実数値ベクトルの探索を繰り返し、探索ごとの近似最適解を求める。探索禁止領域設定部１３０は、最適化部１１０による探索のそれぞれが終了するごとに、終了した１以上の探索のそれぞれについて、当該探索に基づいて、探索禁止領域を探索の繰り返し回数に応じて小さくなるように設定する。【選択図】      図１
2012068776.tif 000002
【特許請求の範囲】
【請求項１】
遺伝的アルゴリズムにおける探索禁止領域を記憶する探索禁止領域記憶手段と、
遺伝的アルゴリズムに基づき、所定の実数値ベクトル領域のうちの前記探索禁止領域記憶手段に記憶された前記探索禁止領域を除外した領域内で目的関数を最小化または最大化する実数値ベクトルの探索を繰り返し、前記探索ごとの近似最適解を求める最適化手段と、
前記最適化手段による前記探索のそれぞれが終了するごとに、終了した１以上の前記探索のそれぞれについて、当該探索に基づいて、前記探索禁止領域を前記探索の繰り返し回数に応じて小さくなるように設定し、前記探索禁止領域記憶手段に保存する探索禁止領域設定手段と、
を含む最適化装置。
【請求項２】
前記探索禁止領域設定手段は、終了した１以上の前記探索のそれぞれについて、当該探索における近似最適解、または、当該探索の各世代で得られる解候補集団を基に、当該探索が他の領域よりも密に行われた領域を推定し、当該推定された領域を前記探索禁止領域として設定する
請求項１に記載の最適化装置。
【請求項３】
前記探索禁止領域設定手段は、前記探索が他の領域よりも密に行われたと推定される領域として、当該探索における近似最適解を中心とする所定形状の領域を抽出し、前記探索の繰り返し回数に応じて前記所定形状を縮小する
請求項２に記載の最適化装置。
【請求項４】
前記探索禁止領域設定手段は、前記探索が他の領域よりも密に行われと推定される領域として、当該探索の各世代で得られる解候補集団のうちの分散共分散行列が所定条件を満たす解候補集団の平均を中心とし、当該分散共分散行列により表される所定形状の領域を抽出し、
前記所定条件は、前記探索の繰り返し回数に応じて当該所定条件を満たす分散共分散行列が表わす前記所定形状が縮小されるように設定される
請求項２に記載の最適化装置。
【請求項５】
遺伝的アルゴリズムにおける探索禁止領域を記憶し、
遺伝的アルゴリズムに基づき、所定の実数値ベクトル領域のうちの前記探索禁止領域を除外した領域内で目的関数を最小化または最大化する実数値ベクトルの探索を繰り返し、前記探索ごとの近似最適解を求め、
前記探索のそれぞれが終了するごとに、終了した１以上の前記探索のそれぞれについて、当該探索に基づいて、前記探索禁止領域を前記探索の繰り返し回数に応じて小さくなるように設定する
最適化方法。
【請求項６】
前記探索禁止領域を設定する場合、終了した１以上の前記探索のそれぞれについて、当該探索における近似最適解、または、当該探索の各世代で得られる解候補集団を基に、当該探索が他の領域よりも密に行われた領域を推定し、当該推定された領域を前記探索禁止領域として設定する
請求項５に記載の最適化方法。
【請求項７】
コンピュータに、
遺伝的アルゴリズムにおける探索禁止領域を記憶し、
遺伝的アルゴリズムに基づき、所定の実数値ベクトル領域のうちの前記探索禁止領域を除外した領域内で目的関数を最小化または最大化する実数値ベクトルの探索を繰り返し、前記探索ごとの近似最適解を求め、
前記探索のそれぞれが終了するごとに、終了した１以上の前記探索のそれぞれについて、当該探索に基づいて、前記探索禁止領域を前記探索の繰り返し回数に応じて小さくなるように設定する
処理を実行させる最適化プログラム。
【請求項８】
前記探索禁止領域を設定する場合、終了した１以上の前記探索のそれぞれについて、当該探索における近似最適解、または、当該探索の各世代で得られる解候補集団を基に、当該探索が他の領域よりも密に行われた領域を推定し、当該推定された領域を前記探索禁止領域として設定する
請求項７に記載の最適化プログラム。
【請求項９】
前記探索禁止領域を設定する場合、前記探索が他の領域よりも密に行われたと推定される領域として、当該探索における近似最適解を中心とする所定形状の領域を抽出し、前記探索の繰り返し回数に応じて前記所定形状を縮小する
請求項８に記載の最適化プログラム。
【請求項１０】
前記探索禁止領域を設定する場合、前記探索が他の領域よりも密に行われと推定される領域として、当該探索の各世代で得られる解候補集団のうちの分散共分散行列が所定条件を満たす解候補集団の平均を中心とし、当該分散共分散行列により表される所定形状の領域を抽出し、
前記所定条件は、前記探索の繰り返し回数に応じて当該所定条件を満たす分散共分散行列が表わす前記所定形状が縮小されるように設定される
請求項８に記載の最適化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は最適化装置、最適化方法、及び最適化プログラムに関し、特に、局所最適解をもつ目的関数を最適化する最適化システム、最適化方法、及び最適化プログラムに関する。
【背景技術】
【０００２】
実数値ベクトル最適化問題とは、入力が実数値ベクトルｘで出力が実数値スカラーであるようなある目的関数ｆ（ｘ）が与えられたとき、この目的関数を最小化または最大化する実数値ベクトルを求める問題である。
【０００３】
実数値ベクトル最適化問題は、例えば特許文献１や特許文献２のように、産業上しばしば現れる重要な問題クラスである。
【０００４】
一般に、最適化問題には厳密解法が存在しないことが知られている。このため、最適化問題の解法としては、遺伝的アルゴリズム（Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍ、以下ＧＡとする）のようなメタヒューリスティクスを用いた解法が用いられることが多い。
【０００５】
ＧＡは、生物の進化のしくみを最適化問題に置き換えたもので、例えば非特許文献１に一例が紹介されている。ＧＡでは複数の解候補を用い、解候補集団をより目的関数値の小さい（または、大きい）領域へ移動、収束させて行くという特徴をもつ。
【０００６】
一方で、目的関数内に非最適解である局所最適解が存在しており、且つ最適解周辺の目的関数値が悪いとき（最適解周辺で、目的関数の値が、最適解から急激に変化するとき）、ＧＡでは解候補集団を非最適な局所最適解へと収束させてしまう、という問題が知られている。
【０００７】
これを解決するため、非特許文献２では探索を繰り返し行うという方法が開示されている。この方法では、探索が終了するごとに、十分探索したとみなせる領域を探索禁止領域として新しく保存し、次回以降の探索では保存されている探索禁止領域全てを探索対象から除外することで、解候補集団の局所最適解への収束を防止し、探索を真の最適解へと促している。
【０００８】
その他、関連技術として特許文献３や特許文献４などがある。特許文献３では、解候補をより密度の小さい領域に発生させる最適解探索装置が開示されている。特許文献４では、局所解を利用した並列ＧＡによる大域的探索装置が開示されている。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開平１１−２４２６９０号公報
【特許文献２】特開２０１０−０４５０６３号公報
【特許文献３】特開２００７−１９９９４３号公報
【特許文献４】特開平１０−１３４０１９号公報
【非特許文献】
【００１０】
【非特許文献１】北野宏明編、「遺伝的アルゴリズム４」、産業図書、２０００年８月３０日、ｐ．２２３−２４０
【非特許文献２】木下峻一、佐久間淳、小林重信、小野功、「ＵＶ構造を考慮した実数値ＧＡの新たな枠組みの提案とその性能評価」、人工知能学会全国大会論文集、２００８年
【発明の概要】
【発明が解決しようとする課題】
【００１１】
ところが非特許文献２の方法では、局所最適解の近くに真の最適解が存在する場合に、その真の最適解の発見率が低下する。これは、ある探索における局所最適解をその探索の最適解として求めたときに、その局所最適解の近くに存在する真の最適解を、誤って探索禁止領域に含めてしまうことがあるためである。最適解が探索禁止領域に含まれてしまうと、何度繰り返し探索を行ったとしても、最適解を発見することができない。
【００１２】
本発明の目的は、上述の課題を解決し、局所最適解の近くに真の最適解の存在する実数値ベクトル最適化問題に対して、真の最適解の発見率を向上させる最適化装置、最適化方法、及び最適化プログラムを提供することである。
【課題を解決するための手段】
【００１３】
本発明の最適化装置は、遺伝的アルゴリズムにおける探索禁止領域を記憶する探索禁止領域記憶手段と、遺伝的アルゴリズムに基づき、所定の実数値ベクトル領域のうちの前記探索禁止領域記憶手段に記憶された前記探索禁止領域を除外した領域内で目的関数を最小化または最大化する実数値ベクトルの探索を繰り返し、前記探索ごとの近似最適解を求める最適化手段と、前記最適化手段による前記探索のそれぞれが終了するごとに、終了した１以上の前記探索のそれぞれについて、当該探索に基づいて、前記探索禁止領域を前記探索の繰り返し回数に応じて小さくなるように設定し、前記探索禁止領域記憶手段に保存する探索禁止領域設定手段と、を含む。
【００１４】
本発明の最適化方法は、遺伝的アルゴリズムにおける探索禁止領域を記憶し、遺伝的アルゴリズムに基づき、所定の実数値ベクトル領域のうちの前記探索禁止領域を除外した領域内で目的関数を最小化または最大化する実数値ベクトルの探索を繰り返し、前記探索ごとの近似最適解を求め、前記探索のそれぞれが終了するごとに、終了した１以上の前記探索のそれぞれについて、当該探索に基づいて、前記探索禁止領域を前記探索の繰り返し回数に応じて小さくなるように設定する。
【００１５】
本発明の最適化プログラムは、コンピュータに、遺伝的アルゴリズムにおける探索禁止領域を記憶し、遺伝的アルゴリズムに基づき、所定の実数値ベクトル領域のうちの前記探索禁止領域を除外した領域内で目的関数を最小化または最大化する実数値ベクトルの探索を繰り返し、前記探索ごとの近似最適解を求め、前記探索のそれぞれが終了するごとに、終了した１以上の前記探索のそれぞれについて、当該探索に基づいて、前記探索禁止領域を前記探索の繰り返し回数に応じて小さくなるように設定する処理を実行させる。
【発明の効果】
【００１６】
本発明の効果は、局所最適解の近くに真の最適解の存在する実数値ベクトル最適化問題に対して、より確実に真の最適解を発見できることである。
【図面の簡単な説明】
【００１７】
【図１】本発明の第一の実施の形態の特徴的な構成を示すブロック図である。
【図２】本発明の第一の実施の形態における最適化装置１００の構成を示すブロック図である。
【図３】本発明の第一の実施の形態における最適化装置１００の動作を示すフローチャートである。
【図４】本発明の第一の実施の形態における最適解記憶部１２０に記憶されるデータの例を示す図である。
【図５】本発明の第一の実施の形態における探索禁止領域記憶部１４０に記憶されるデータの例を示す図である。
【図６】本発明の第一の実施の形態における探索禁止領域記憶部１４０に記憶されるデータの他の例を示す図である。
【図７】本発明の第一の実施の形態における、２次元の実数値ベクトルに対する探索禁止領域の設定の例を示す図である。
【図８】本発明の第二の実施の形態における最適化装置１００の構成を示すブロック図である。
【図９】本発明の第二の実施の形態における最適化装置１００の動作を示すフローチャートである。
【図１０】本発明の第二の実施の形態における探索履歴記憶部１５０に記憶されるデータの例を示す図である。
【図１１】本発明の第二の実施の形態における、２次元の実数値ベクトルに対する探索禁止領域の設定の例を示す図である。
【発明を実施するための形態】
【００１８】
（第一の実施の形態）
次に、本発明の第一の実施の形態について図面を参照して詳細に説明する。
【００１９】
はじめに、本発明の第一の実施の形態における最適化装置１００の構成について説明する。図２は、本発明の第一の実施の形態における最適化装置１００の構成を示すブロック図である。
【００２０】
図２を参照すると、本発明の第一の実施の形態における最適化装置１００は、最適化部１１０と、最適解記憶部１２０と、探索禁止領域設定部１３０と、探索禁止領域記憶部１４０と、を含む。
【００２１】
最適化部１１０は、制約対処つき実数値ＧＡを用いて、目的関数に対する実数値ベクトルの近似最適解を求める。ここで、制約対処とは、所定領域から探索禁止領域を除外した領域において、解候補を求めることを示す。また、実数値ベクトルには、次元数が１の場合（実数値）も含むものとする。
【００２２】
最適化部１１０は、探索禁止領域を除外した領域について探索を繰り返し、探索ごとの近似最適解を基に、目的関数に対する所定領域における近似最適解を求める。
【００２３】
最適化部１１０は、以下のようにして各探索を行う。
【００２４】
最適化部１１０は、まず制約を充足する解候補（所定領域から探索禁止領域を除外した領域における解候補）をランダムに一定数作成し、初期解候補集団とする。
【００２５】
次に、最適化部１１０は、解候補集団から複数の親を抽出し、任意の交叉および突然変異手法によって、新たな解候補を複数生成し、子とする。ここで、交叉および突然変異手法は任意で、例えば単峰性正規分布交叉や一様突然変異などが用いられる。
【００２６】
次に、最適化部１１０は、生成された子解候補について、各々の目標関数値の計算を行う。
【００２７】
次に、最適化部１１０は、任意の淘汰選択手法によって親および子から解候補集団に残す解候補を選択し、解候補集団に追加する。ここで、選択手法としては、エリート選択やルーレット選択などが用いられる。
【００２８】
制約対処としては、子解候補生成のときに制約を充足しない解候補（探索禁止領域に含まれる解候補）が生成されないように操作する手法、または淘汰選択において制約を充足しない解候補（探索禁止領域に含まれる解候補）から優先的に淘汰する手法が用いられる。
【００２９】
最適化部１１０は、上述の親選択から淘汰選択までの処理を１世代とし、この１世代の処理を所定の終了条件を満たすまで複数世代について行う。そして、最適化部１１０は、最終世代における解候補集団のうち最も目的関数値のよい解候補を、その探索における近似最適解とする。
【００３０】
そして、最適化部１１０は、上述の各探索における近似最適解のうち、最も目的関数値の良い解（目的関数値の値が最小（または最大）となる解）を、近似最適解として出力する。
【００３１】
最適解記憶部１２０は、最適化部１１０によって得られた、各探索における近似最適解のうち、最も目的関数値の良い解とその目的関数値とを記憶する。図４は、本発明の第一の実施の形態における最適解記憶部１２０に記憶されるデータの例を示す図である。最適解記憶部１２０は、例えば、図４のように、最も目的関数値の良い実数値ベクトルｘの解ｘｂｅｓｔと、ｘ＝ｘｂｅｓｔのときの目的関数ｆ（ｘ）の値ｆ（ｘｂｅｓｔ）と、を記憶する。
【００３２】
探索禁止領域設定部１３０は、探索禁止領域を設定し、探索禁止領域記憶部１４０に保存する。本発明の第一の実施の形態では、探索禁止領域設定部１３０は、各探索で得られる近似最適解を中心とした所定のモデルで表現された領域を、他の領域よりも密に探索が行われた領域と推定し、当該領域を当該探索に基づいた探索禁止領域として設定する。
【００３３】
具体的には、探索禁止領域設定部１３０は、最適化部１１０による探索が終了するごとに、既に終了している探索のそれぞれについて、当該探索の近似最適解を中心とする所定のモデルで表現された領域を探索禁止領域として設定する。
【００３４】
それぞれの探索についての上記所定のモデルの大きさは、探索の繰り返し回数に応じて小さくなるように設定される。
【００３５】
ここで、探索禁止領域を表すモデルとして、超球（または、円、球）、超楕円体（または楕円）、矩形など任意のものを用いることができる。
【００３６】
探索禁止領域記憶部１４０は、探索禁止領域設定部１３０によって設定された探索禁止領域を記憶する。図５及び図６は、本発明の第一の実施の形態における探索禁止領域記憶部１４０に記憶されるデータの例を示す図である。探索禁止領域の表現モデルに超球を用いた場合、探索禁止領域記憶部１４０は、例えば、図５のように、ｉ回目（ｉ＝１，２，…）の探索を基に設定した探索禁止領域ｉに対して、探索禁止領域の中心ｃｉ、と半径ｒｉとを記憶する。また、探索禁止領域の表現モデルに楕円を用いる場合は、探索禁止領域記憶部１４０は、例えば、図６のように、ｉ回目の探索を基に設定した探索禁止領域ｉに対して、探索禁止領域の中心ｃｉと楕円の形状を表す係数行列Ａｉとを記憶する。
【００３７】
ここで、最適化部１１０と、探索禁止領域設定部１３０とは、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）とプログラムを記憶した記憶媒体を含み、プログラムに基づく制御によって動作するコンピュータであってもよい。最適解記憶部１２０と、探索禁止領域記憶部１４０とは、それぞれ個別の記憶媒体でも、１つの記憶媒体によって構成されてもよい。
【００３８】
次に、本発明の第一の実施の形態における最適化装置１００の動作について説明する。図３は、本発明の第一の実施の形態における最適化装置１００の動作を示すフローチャートである。
【００３９】
ここでは例として、探索禁止領域の表現モデルに超球（または、円、球）を用いた場合について説明する。
【００４０】
まず初期化として、探索禁止領域設定部１３０は、最適解記憶部１２０と探索禁止領域記憶部１４０とを空にし、探索の繰り返し回数を示すｋに０を設定する（ステップＳ１０１）。
【００４１】
次に、最適化部１１０は、ｋに１を加算し、制約対処つきＧＡによる１回の探索を行いｆ（ｘ）の近似最適解を求める（ステップＳ１０２）。ここで、最適化部１１０は、探索禁止領域記憶部１４０に記憶されている全ての探索禁止領域の中心ｃｉと半径ｒｉと（ｉ＜ｋ）を読み出し、所定の探索領域から次の数１の超球で表される全ての探索禁止領域除いた探索領域について、探索を行う。
【００４２】
【数１】
2012068776.tif 000003
【００４３】
最適化部１１０は、探索により得られた近似最適解の評価値（近似最適解についての目的関数ｆ（ｘ）の値）を、最適解記憶部１２０に保存されている最良解の評価値ｆ（ｘｂｅｓｔ）と比較する（ステップＳ１０３）。探索により得られた近似最適解が、より優れた解であった場合（探索により得られた近似最適解についての目的関数値の値が、より小さい（または大きい）場合）（ステップＳ１０３／Ｙｅｓ）、最適化部１１０は、探索により得られた近似最適解とその評価値とをそれぞれｘｂｅｓｔ、ｆ（ｘｂｅｓｔ）として最適解記憶部１２０に上書き保存する（ステップＳ１０４）。
【００４４】
次に、最適化部１１０は、ｆ（ｘｂｅｓｔ）が、管理者等により予め与えられた所定の目標評価値よりも優れている、あるいは管理者等により予め与えられた所定の計算時間が経過した、等の終了条件の判定を行い（ステップＳ１０５）、終了条件を満たしていれば（ステップＳ１０５／Ｙｅｓ）、処理を終了する。
【００４５】
ステップＳ１０５において終了条件を満たしていない場合（ステップＳ１０５／Ｎｏ）、探索禁止領域設定部１３０は、探索禁止領域記憶部１４０に保存されている各探索禁止領域ｉ（ｉ＜ｋ）の半径ｒｉを各々読み込み、管理者等により予め与えられた１より小さい任意の正の定数（所定の比率）を乗じることによって更新し、探索禁止領域記憶部１４０に上書き保存する（ステップＳ１０６）。これにより、探索禁止領域記憶部１４０に保存されているそれぞれの探索禁止領域は、一定の比率で縮小される。
【００４６】
さらに、探索禁止領域設定部１３０は、探索禁止領域ｋの中心ｃｋ、及び、半径ｒｋに、ステップＳ１０２で得られた近似最適解、及び、予め与えられた所定値をそれぞれ設定し、探索禁止領域記憶部１４０に保存する（ステップＳ１０７）。
【００４７】
その後、探索禁止領域設定部１３０は、終了条件を満たすまでステップＳ１０２からステップＳ１０７を繰り返す。
【００４８】
図７は、本発明の第一の実施の形態における、２次元の実数値ベクトルに対する探索禁止領域の設定の例を示す図である。
【００４９】
例えば、真の最適解が、図７のＸであるものとする。また、真の最適解Ｘは、局所最適解ｘ１の近傍に存在するものとする。
【００５０】
最適化部１１０は、図７の（ａ）に示すように、１回目の探索により局所最適解ｘ１を最適解として出力する。探索禁止領域設定部１３０は、中心をｃ１＝ｘ１とし、半径ｒ１を所定の値Ｒとした円を探索禁止領域１に設定する。
【００５１】
ここで、真の最適解Ｘが、探索禁止領域１の中に含まれるものとする。
【００５２】
次に、最適化部１１０は、図７の（ｂ）に示すように、２回目の探索により局所最適解ｘ２を最適解として出力する。探索禁止領域設定部１３０は、探索禁止領域１の半径ｒ１に所定の比率０．５を乗じて、ｒ１＝０．５Ｒとする。また、探索禁止領域設定部１３０は、中心ｃ２＝ｘ２、半径ｒ２＝Ｒとした円を探索禁止領域２に設定する。
【００５３】
さらに、最適化部１１０は、図７の（ｃ）に示すように、３回目の探索によりより局所解ｘ３を最適解として出力する。探索禁止領域設定部１３０は、探索禁止領域１及び２の半径ｒ１、ｒ２に所定の比率０．５を乗じて、ｒ１＝０．２５Ｒ、ｒ２＝０．５Ｒとする。また、探索禁止領域設定部１３０は、中心ｃ３＝ｘ３、半径ｒ３＝Ｒとした円を探索禁止領域３に設定する。
【００５４】
ここで、探索禁止領域１が縮小されたことにより、真の最適解Ｘが、探索禁止領域１の外に出たものとする。
【００５５】
以降の探索では、最適化部１１０は、真の最適解Ｘが再び他の局所最適解を基に設定さされた探索禁止領域に含まれない限り、真の最適解Ｘを含む領域についても探索を行うため、真の最適解Ｘを発見する可能性が高まる。
【００５６】
以上により、本発明の第一の実施の形態の動作が完了する。
【００５７】
なお、本発明の第一の実施の形態の形態では、探索禁止領域設定部１３０が、探索が終了するごとに探索禁止領域を示す表現モデル（超球）の大きさ（半径）に所定の比率を乗じることにより、探索禁止領域を縮小しているが、表現モデルの大きさに探索の繰り返し回数に応じて減少するような所定の固定値を設定する等、探索の繰り返し回数に応じて表現モデルを縮小できるものであれば、他の方法を用いてもよい。
【００５８】
次に、本発明の第一の実施の形態の特徴的な構成を説明する。図１は、本発明の第一の実施の形態の特徴的な構成を示すブロック図である。
【００５９】
図１を参照すると、最適化装置１００は、探索禁止領域記憶部１４０と、最適化部１１０と、探索禁止領域設定部１３０と、を含む。
【００６０】
ここで、探索禁止領域記憶部１４０は、遺伝的アルゴリズムにおける探索禁止領域を記憶する。
【００６１】
最適化部１１０は、遺伝的アルゴリズムに基づき、所定の実数値ベクトル領域のうちの探索禁止領域記憶部１４０に記憶された探索禁止領域を除外した領域内で目的関数を最小化または最大化する実数値ベクトルの探索を繰り返し、探索ごとの近似最適解を求める。
【００６２】
探索禁止領域設定部１３０は、最適化部１１０による探索のそれぞれが終了するごとに、終了した１以上の探索のそれぞれについて、当該探索に基づいて、探索禁止領域を探索の繰り返し回数に応じて小さくなるように設定し、探索禁止領域記憶部１４０に保存する。
【００６３】
本発明の第一の実施の形態によれば、局所最適解の近くに真の最適解の存在する実数値ベクトル最適化問題に対して、より確実に真の最適解を発見できる。その理由は、探索禁止領域設定部１３０が、最適化部１１０による探索が終了するごとに、終了した探索のそれぞれについて、当該探索に基づいて、探索禁止領域を探索の繰り返し回数に応じて小さくなるように設定するためである。
【００６４】
これにより、真の最適解が誤って探索禁止領域に含まれたとしても、真の最適解は、探索の繰り返しを経て再度探索の対象となるため、真の最適解が最適解として出力される可能性が高くなる。
【００６５】
（第二の実施の形態）
次に、本発明の第二の実施の形態について図面を参照して詳細に説明する。
【００６６】
本発明の第二の実施の形態においては、探索禁止領域設定部１３０が、各探索の各世代で得られる解候補集団のうち、その分散が所定値以下となる解候補集団の分布をもとに探索禁止領域を設定する点で、本発明の第一の実施の形態と異なる。なお、本発明の第二の実施の形態において、本発明の第一の実施の形態と同一の符号を付した構成要素については、特に説明のない限り、第一の実施の形態と同様であるものとする。
【００６７】
次に、本発明の第二の実施の形態における最適化装置１００の構成について説明する。図８は、本発明の第二の実施の形態における最適化装置１００の構成を示すブロック図である。
【００６８】
図８を参照すると、本発明の第二の実施の形態における最適化装置１００は、本発明の第一の実施の形態における最適化装置１００の構成に加えて、探索履歴記憶部１５０を含む。
【００６９】
探索履歴記憶部１５０は、最適化部１１０によって行われた各探索における、各世代で得られた解候補集団の平均および分散共分散行列を記憶する。図１０は、本発明の第二の実施の形態における探索履歴記憶部１５０に記憶されるデータの例を示す図である。探索履歴記憶部１５０は、例えば、図１０のように、ｉ回目の探索のｊ世代（ｊ＝１，２，…，Ｎｉ）における解候補集団の平均μｉ，ｊ及び分散共分散行列Σｉ，ｊを記憶する。ここで、Ｎｉは、ｉ回目の探索における世代数である。
【００７０】
探索禁止領域設定部１３０は、探索禁止領域を設定し、探索禁止領域記憶部１４０に保存する。本発明の第二の実施の形態では、探索禁止領域設定部１３０は、各探索の各世代で得られる解候補集団のうち、分散共分散行列が所定条件を満たす解候補集団の分布をもとに、他の領域よりも密に探索が行われた領域を推定し、当該領域を当該探索に基づいた探索禁止領域として設定する。
【００７１】
具体的には、探索禁止領域設定部１３０は、最適化部１１０による探索が終了するごとに、既に終了している探索のそれぞれについて、当該探索の各世代のうち、解候補集団の分散共分散行列が上記所定条件を満たす世代を抽出する。そして、探索禁止領域設定部１３０は、抽出された世代の解候補集団の平均値を中心とし、その世代の分散共分散行列で形状が指定される所定のモデルで表現された領域を探索禁止領域として設定する。
【００７２】
分散共分散行列に関する上記所定条件は、探索の繰り返し回数に応じて上記所定条件を満たす分散共分散行列が表わす所定のモデルが縮小されるように設定される。
【００７３】
ここで、探索禁止領域を表すモデルとしては、平均と分散共分散行列で表される解候補集団の分布を表現できるモデルであれば、例えば、超楕円体（または楕円）、矩形等の任意のモデルを利用することができる。
【００７４】
次に、本発明の第二の実施の形態における最適化装置１００の動作について説明する。図９は、本発明の第二の実施の形態における最適化装置１００の動作を示すフローチャートである。
【００７５】
ここでは例として、探索禁止領域の表現モデルに超楕円体を用いた場合について説明する。また、探索禁止領域記憶部１４０は、図６のように、ｉ回目の探索を基に設定した探索禁止領域ｉに対して、探索禁止領域の中心ｃｉと超楕円体の形状を表す係数行列Ａｉとを記憶するものとする。
【００７６】
まず初期化として、探索禁止領域設定部１３０は、最適解記憶部１２０と探索禁止領域記憶部１４０とを空にし、探索回数を示すｋに０を設定する（ステップＳ２０１）。
【００７７】
次に、最適化部１１０は、ｋに１を加算し、制約対処つきＧＡによる１回の探索を行いｆ（ｘ）の近似最適解を求める（ステップＳ２０２）。ここで、最適化部１１０は、探索禁止領域記憶部１４０に保存されている全ての探索禁止領域の中心ｃｉと係数行列Ａｉと（ｉ＜ｋ）を読み出し、所定の探索領域から次の数２の超楕円体で表される全ての探索禁止領域除いた探索領域について、探索を行う。
【００７８】
【数２】
2012068776.tif 000004
【００７９】
このとき、最適化部１１０は、探索における各世代ｊにおける解候補集団の平均および分散共分散行列をμｋ，ｊ、Σｋ，ｊとして探索履歴記憶部１５０に保存する。
【００８０】
最適化部１１０は、探索により得られた近似最適解の評価値を、最適解記憶部１２０に保存されている最良解の評価値ｆ（ｘｂｅｓｔ）と比較する（ステップＳ２０３）。探索により得られた近似最適解が、より優れた解であった場合（探索により得られた近似最適解についての目的関数値の値が、より小さい（または大きい）場合）（ステップＳ２０３／Ｙｅｓ）、最適化部１１０は、探索により得られた近似最適解とその評価値とをそれぞれｘｂｅｓｔ、ｆ（ｘｂｅｓｔ）として最適解記憶部１２０に上書き保存する（ステップＳ２０４）。
【００８１】
次に最適化部１１０は、ｆ（ｘｂｅｓｔ）が、管理者等により予め与えられた所定の目標評価値よりも優れている、あるいは管理者等により予め与えられた所定の計算時間が経過した、等の終了条件の判定を行い（ステップＳ２０５）、終了条件を満たしていれば（ステップＳ２０５／Ｙｅｓ）、処理を終了する。
【００８２】
ステップＳ２０５において終了条件を満たしていない場合（ステップＳ２０５／Ｎｏ）、探索禁止領域設定部１３０は、分散行列探索履歴記憶部１５０に記憶されている、既に終了している各探索の各世代で得られた解候補集団の分散共分散行列を基に、探索禁止領域を設定する（ステップＳ２０６）
ここで、探索禁止領域設定部１３０は、既に終了している各探索（ｉ≦ｋ）について、探索履歴記憶部１５０に保存されている解候補集団の平均μｉ，ｊ及び分散共分散行列Σｉ，ｊ（ｉ≦ｋ、ｊ＝１，２，…，Ｎｉ）を読み込み、分散共分散行列Σｉ，ｊが次の数３の条件（所定条件）を満たす最小の世代ｊを抽出し、ｊ０（ｉ，ｋ）とする。
【００８３】
【数３】
2012068776.tif 000005
【００８４】
ここで、Σ０は所定の探索領域内に、一様に解候補集団を分布させたときの分散共分散行列である。また、｜Σ０｜の代わりに、管理者等により予め設定された他の定数を用いてもよい。
【００８５】
そして、探索禁止領域設定部１３０は、各探索禁止領域ｉ（ｉ≦ｋ）における中心ｃｉ、及び、係数行列Ａｉに、上記の数３を満たす世代ｊ０（ｉ，ｋ）における解候補集団の平均μｉ，ｊ０（ｉ，ｋ）、及び、分散共分散行列Σｉ，ｊ０（ｉ，ｋ）をそれぞれ設定し、探索禁止領域記憶部１４０に保存する。
【００８６】
その後、探索禁止領域設定部１３０は、終了条件を満たすまでステップＳ２０２からステップＳ２０６を繰り返す。
【００８７】
図１１は、本発明の第二の実施の形態における、２次元の実数値ベクトルに対する探索禁止領域の設定の例を示す図である。
【００８８】
例えば、真の最適解が、図１１のＸであるものとする。また、真の最適解Ｘは、局所最適解ｘ１の近傍に存在するものとする。
【００８９】
最適化部１１０は、図１１の（ａ）に示すように、１回目の探索により局所最適解ｘ１を最適解として出力する。探索禁止領域設定部１３０は、探索禁止領域１の楕円の中心ｃ１、及び、係数行列Ａ１に、１回目の探索における、数３を満たす（｜Σｉ，ｊ｜１／２＜１／２×｜Σ０｜１／２となる）最小の世代ｊ０（１，１）の解候補集団の平均値μ１，ｊ０（１，１）（図１１中のμ１ａ）、及び、分散共分散行列Σ１，ｊ０（１，１）を設定する。
【００９０】
ここで、真の最適解Ｘが、探索禁止領域１の中に含まれるものとする。
【００９１】
次に、最適化部１１０は、図１１の（ｂ）に示すように、２回目の探索により局所最適解ｘ２を最適解として出力する。探索禁止領域設定部１３０は、探索禁止領域１の楕円の中心ｃ１、及び、係数行列Ａ１に、１回目の探索における、数３を満たす（｜Σｉ，ｊ｜１／２＜１／３×｜Σ０｜１／２となる）最小の世代ｊ０（１，２）の解候補集団の平均値μ１，ｊ０（１，２）（図１１中のμ１ｂ）、及び、分散共分散行列Σ１，ｊ０（１，２）を設定する。同様に、探索禁止領域設定部１３０は、探索禁止領域２の楕円の中心ｃ２、及び、係数行列Ａ２に、２回目の探索における、数３を満たす最小の世代ｊ０（２，２）の解候補集団の平均値μ２，ｊ０（２，２）（図１１中のμ２ａ）、及び、分散共分散行列Σ１，ｊ０（２，２）を設定する。
【００９２】
さらに、最適化部１１０は、図１１の（ｃ）に示すように、３回目の探索により局所最適解ｘ３を最適解として出力する。探索禁止領域設定部１３０は、探索禁止領域１の楕円の中心ｃ１、及び、係数行列Ａ１に、１回目の探索における、数３を満たす（｜Σｉ，ｊ｜１／２＜１／４×｜Σ０｜１／２となる）最小の世代ｊ０（１，３）の解候補集団の平均値μ１，ｊ０（１，３）（図１１中のμ１ｃ）、及び、分散共分散行列Σ１，ｊ０（１，３）を設定する。同様に、探索禁止領域設定部１３０は、探索禁止領域２の楕円の中心ｃ２、及び、係数行列Ａ２に、２回目の探索における、数３を満たす最小の世代ｊ０（２，３）の解候補集団の平均値μ２，ｊ０（２，３）（図１１中のμ２ｂ）、及び、分散共分散行列Σ２，ｊ０（２，３）を設定し、探索禁止領域３の楕円の中心ｃ３、及び、係数行列Ａ３に、３回目の探索における、数３を満たす最小の世代ｊ０（３，３）の解候補集団の平均値μ３，ｊ０（３，３）（図１１中のμ３ａ）、及び、分散共分散行列Σ３，ｊ０（３，３）を設定する。
【００９３】
ここで、探索禁止領域１が縮小されたことにより、真の最適解Ｘが、探索禁止領域１の外に出たものとする。
【００９４】
以降の探索では、最適化部１１０は、真の最適解Ｘが再び他の局所最適解を基に設定さされた探索禁止領域に含まれない限り、真の最適解Ｘを含む領域についても探索を行うため、真の最適解Ｘを発見する可能性が高まる。
【００９５】
以上により、本発明の第二の実施の形態の動作が完了する。
【００９６】
なお、本発明の第二の実施の形態の形態では、探索禁止領域設定部１３０が、探索が終了するごとに、分散が数３の条件を満たす解候補集団の分布を基に探索禁止領域を設定することにより、探索の繰り返し回数に応じて探索禁止領域を縮小している。しかしながら、探索禁止領域設定部１３０は、探索の繰り返し回数に応じて探索禁止領域を求めるための解候補集団の分散を小さくできるものであれば、数３以外の他の条件を用いてもよい。例えば、探索禁止領域設定部１３０は、数３以外の他の方法により、解候補集団の分散を算出し、それを数３のように探索の繰り返し回数に応じて減少する閾値と比較するようにしてもよい。
【００９７】
本発明の第二の実施の形態によれば、第一の実施の形態と同様に、局所最適解の近くに真の最適解の存在する実数値ベクトル最適化問題に対して、より確実に真の最適解を発見できる。その理由は、探索禁止領域設定部１３０が、最適化部１１０による探索が終了するごとに、終了した探索のそれぞれについて、当該探索の各世代で得られる解候補集団のうちの分散共分散行列が所定条件を満たす解候補集団の平均を中心とし、当該分散共分散行列により表される所定形状の領域を抽出し、上記所定条件が、探索の繰り返し回数に応じて当該所定条件を満たす分散共分散行列が表わす所定形状が縮小されるように設定されるためである。
【００９８】
各探索に基づく探索禁止領域は、探索を繰り返すたびに、より密に解候補集団が配置された領域となるため、結果として、各探索に基づく探索禁止領域は、探索の繰り返しごとに縮小される。
【００９９】
これにより、真の最適解が誤って探索禁止領域に含まれたとしても、真の最適解は、探索の繰り返しを経て再度探索の対象となるため、真の最適解が最適解として出力される可能性が高くなる。
【０１００】
以上、これまで述べてきた各実施の形態は、本発明の好適な実施形態であり、上記実施の形態のみに本発明の範囲を限定するものではなく、本発明の要旨を逸脱しない範囲において種々の変更を施した形態での実施が可能である。
【０１０１】
例えば、本発明の実施の形態では、探索禁止領域設定部１３０が、探索禁止領域設定部１３０が最適化部１１０による探索が終了するごとに、終了した１以上の探索のそれぞれについて、当該探索に基づいて次の探索に用いる探索禁止領域を算出している（ステップＳ１０６、Ｓ１０７、Ｓ２０６）。これに対して、探索禁止領域設定部１３０は、探索が終了するごとに、当該探索に基づいて、その後に行われる１以上の探索で利用される探索禁止領域を上記ステップと同様の方法により予め算出し、図示しない記憶部に保存しておいてもよい。この場合、探索禁止領域設定部１３０は、最適化部１１０による探索が終了するごとに、当該記憶部に記憶されている探索禁止領域のうち、次の探索に用いる探索禁止領域を読み出して、探索禁止領域記憶部１４０に保存する。
【０１０２】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
（付記１）
遺伝的アルゴリズムにおける探索禁止領域を記憶する探索禁止領域記憶手段と、
遺伝的アルゴリズムに基づき、所定の実数値ベクトル領域のうちの前記探索禁止領域記憶手段に記憶された前記探索禁止領域を除外した領域内で目的関数を最小化または最大化する実数値ベクトルの探索を繰り返し、前記探索ごとの近似最適解を求める最適化手段と、
前記最適化手段による前記探索のそれぞれが終了するごとに、終了した１以上の前記探索のそれぞれについて、当該探索に基づいて、前記探索禁止領域を前記探索の繰り返し回数に応じて小さくなるように設定し、前記探索禁止領域記憶手段に保存する探索禁止領域設定手段と、
を含む最適化装置。
（付記２）
前記探索禁止領域設定手段は、終了した１以上の前記探索のそれぞれについて、当該探索における近似最適解、または、当該探索の各世代で得られる解候補集団を基に、当該探索が他の領域よりも密に行われた領域を推定し、当該推定された領域を前記探索禁止領域として設定する
（付記１）に記載の最適化装置。
（付記３）
前記探索禁止領域設定手段は、前記探索が他の領域よりも密に行われたと推定される領域として、当該探索における近似最適解を中心とする所定形状の領域を抽出し、前記探索の繰り返し回数に応じて前記所定形状を縮小する
（付記２）に記載の最適化装置。
（付記４）
前記探索禁止領域設定手段は、前記探索が他の領域よりも密に行われと推定される領域として、当該探索の各世代で得られる解候補集団のうちの分散共分散行列が所定条件を満たす解候補集団の平均を中心とし、当該分散共分散行列により表される所定形状の領域を抽出し、
前記所定条件は、前記探索の繰り返し回数に応じて当該所定条件を満たす分散共分散行列が表わす前記所定形状が縮小されるように設定される
（付記２）に記載の最適化装置。
（付記５）
遺伝的アルゴリズムにおける探索禁止領域を記憶し、
遺伝的アルゴリズムに基づき、所定の実数値ベクトル領域のうちの前記探索禁止領域を除外した領域内で目的関数を最小化または最大化する実数値ベクトルの探索を繰り返し、前記探索ごとの近似最適解を求め、
前記探索のそれぞれが終了するごとに、終了した１以上の前記探索のそれぞれについて、当該探索に基づいて、前記探索禁止領域を前記探索の繰り返し回数に応じて小さくなるように設定する
最適化方法。
（付記６）
前記探索禁止領域を設定する場合、終了した１以上の前記探索のそれぞれについて、当該探索における近似最適解、または、当該探索の各世代で得られる解候補集団を基に、当該探索が他の領域よりも密に行われた領域を推定し、当該推定された領域を前記探索禁止領域として設定する
（付記５）に記載の最適化方法。
（付記７）
前記探索禁止領域を設定する場合、前記探索が他の領域よりも密に行われたと推定される領域として、当該探索における近似最適解を中心とする所定形状の領域を抽出し、前記探索の繰り返し回数に応じて前記所定形状を縮小する
（付記６）に記載の最適化方法。
（付記８）
前記探索禁止領域を設定する場合、前記探索が他の領域よりも密に行われと推定される領域として、当該探索の各世代で得られる解候補集団のうちの分散共分散行列が所定条件を満たす解候補集団の平均を中心とし、当該分散共分散行列により表される所定形状の領域を抽出し、
前記所定条件は、前記探索の繰り返し回数に応じて当該所定条件を満たす分散共分散行列が表わす前記所定形状が縮小されるように設定される
（付記６）に記載の最適化方法。
（付記９）
コンピュータに、
遺伝的アルゴリズムにおける探索禁止領域を記憶し、
遺伝的アルゴリズムに基づき、所定の実数値ベクトル領域のうちの前記探索禁止領域を除外した領域内で目的関数を最小化または最大化する実数値ベクトルの探索を繰り返し、前記探索ごとの近似最適解を求め、
前記探索のそれぞれが終了するごとに、終了した１以上の前記探索のそれぞれについて、当該探索に基づいて、前記探索禁止領域を前記探索の繰り返し回数に応じて小さくなるように設定する
処理を実行させる最適化プログラム。
（付記１０）
前記探索禁止領域を設定する場合、終了した１以上の前記探索のそれぞれについて、当該探索における近似最適解、または、当該探索の各世代で得られる解候補集団を基に、当該探索が他の領域よりも密に行われた領域を推定し、当該推定された領域を前記探索禁止領域として設定する
（付記９）に記載の最適化プログラム。
（付記１１）
前記探索禁止領域を設定する場合、前記探索が他の領域よりも密に行われたと推定される領域として、当該探索における近似最適解を中心とする所定形状の領域を抽出し、前記探索の繰り返し回数に応じて前記所定形状を縮小する
（付記１０）に記載の最適化プログラム。
（付記１２）
前記探索禁止領域を設定する場合、前記探索が他の領域よりも密に行われと推定される領域として、当該探索の各世代で得られる解候補集団のうちの分散共分散行列が所定条件を満たす解候補集団の平均を中心とし、当該分散共分散行列により表される所定形状の領域を抽出し、
前記所定条件は、前記探索の繰り返し回数に応じて当該所定条件を満たす分散共分散行列が表わす前記所定形状が縮小されるように設定される
（付記１０）に記載の最適化プログラム。
【産業上の利用可能性】
【０１０３】
本発明は、目標関数が定義可能な実数値パラメータに対する最適化問題全般に適用することができる。例えば、本発明は、所望の特性をもつトランジスタのパラメータ設計といった用途に適用できる。また、本発明は、収差の少ない光学系の設計といった用途にも適用できる。
【符号の説明】
【０１０４】
１００  最適化装置
１１０  最適化部
１２０  最適解記憶部
１３０  探索禁止領域設定部
１４０  探索禁止領域記憶部
１５０  探索履歴記憶部
【図１】
2012068776.tif 000006
【図２】
2012068776.tif 000007
【図３】
2012068776.tif 000008
【図４】
2012068776.tif 000009
【図５】
2012068776.tif 000010
【図６】
2012068776.tif 000011
【図７】
2012068776.tif 000012
【図８】
2012068776.tif 000013
【図９】
2012068776.tif 000014
【図１０】
2012068776.tif 000015
【図１１】
2012068776.tif 000016