(57)【要約】【課題】処理負担の低減および時間短縮を図ること。【解決手段】計算機が、島モデルの各島に対して互いに異なるパラメータ群を設定するパラメータ群設定部１３と、設定されたパラメータ群を用いて、島毎に解候補の探索を行う計算部１４と、所定のタイミングで、計算部１４により得られた各解候補の適合評価値を取得し、これらに基づいて各島の適合評価を行う島適合評価部１５とを備え、島間で解候補の移住が行われる場合に、パラメータ群設定部１３が、島適合評価部１５による適合評価の結果が最良であった島に対しては前回と同じパラメータ群を設定し、他の島に対しては新たなパラメータ群を設定する。【選択図】      図２
2009069865.tif 000002
【特許請求の範囲】
【請求項１】
計算機を備え、遺伝的アルゴリズムを用いて最適な解候補を探索する最適解探索装置であって、
前記計算機が、
島モデルの各島に対して互いに異なるパラメータ群を設定するパラメータ群設定部と、
設定された前記パラメータ群を用いて、前記島毎に解候補の探索を行う計算部と、
所定のタイミングで、前記計算部により得られた各解候補の適合評価値を取得し、これらに基づいて各前記島の適合評価を行う島適合評価部と
を備え、
前記島間で解候補の移住が行われる場合に、前記パラメータ群設定部は、前記島適合評価部による適合評価の結果が最良であった島に対しては前回と同じパラメータ群を設定し、他の前記島に対しては新たなパラメータ群を設定する最適解探索装置。
【請求項２】
前記島適合評価部による適合評価の結果が最良であった島に設定されていたパラメータ群を記憶する記憶部を備える請求項１に記載の最適解探索装置。
【請求項３】
前記所定のタイミングは、前記島間における解候補の移住が行われるときである請求項１または請求項２に記載の最適解探索装置。
【請求項４】
前記計算部は島毎に対応して設けられる複数の分散計算部を備え、
各前記分散計算部は、
各解候補の適合評価を行う固体評価部と、
前記適合評価に基づいて前記解候補の選択を行う固体選択部と、
前記固体選択部によって選択された前記解候補に遺伝的操作を行うことにより次世代の解候補を作成する遺伝的操作部と
を備える請求項１から請求項３のいずれかに記載の最適解探索装置。
【請求項５】
計算機により遺伝的アルゴリズムを用いて最適な解候補を探索する最適解探索方法であって、
島モデルの各島に対して互いに異なるパラメータ群を設定する工程と、
設定された前記パラメータ群を用いて、前記島毎に解候補の探索を行う工程と、
所定のタイミングで、各前記解候補の適合評価値を取得し、これらに基づいて各前記島の適合評価を行う工程と
を含み、
前記島間における解候補の移住が行われる場合に、前記適合評価の結果が最良であった島に対しては前回と同じパラメータ群を設定し、他の前記島に対しては新たなパラメータ群を設定する最適解探索方法。
【請求項６】
遺伝的アルゴリズムを用いて最適な解候補を探索するための処理をコンピュータに実行させるための最適解探索プログラムであって、
島モデルの各島に対して互いに異なるパラメータ群を設定する処理と、
設定された前記パラメータ群を用いて、前記島毎に解候補の探索を行う処理と、
所定のタイミングで、各前記解候補の適合評価値を取得し、これらに基づいて各前記島の適合評価を行う処理と
を含み、
前記島間における解候補の移住が行われる場合に、前記適合評価の結果が最良であった島に対しては前回と同じパラメータ群を設定させ、他の島に対しては新たなパラメータ群を設定させる最適解探索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、遺伝的アルゴリズム（Genetic Algorithm、以下「ＧＡ」という。）を用いて最適解を探索する最適解探索装置及び方法並びにプログラムに関するものである。
【背景技術】
【０００２】
ＧＡは、生物の進化を模倣した確率的な最適化アルゴリズムである。以下、ＧＡの概要について簡単に説明する。
まず、最適化問題の解候補を例えば、遺伝子の一次ストリングである染色体として表現し、様々な遺伝子をもつ解候補をランダムに選択して、初期世代の集団（母集団）を作成する。次に、各解候補の適合度（最適化問題での目的関数の値）を計算する。続いて、適合度に応じて複数の解候補を選択（複製選択）し、これらがもつ遺伝子の交叉（crossover；図６参照）や突然変異（mutation；図７参照）等の遺伝的操作を行うことにより、次世代の解候補の集団を作成する。このとき、解候補の選択では、環境（目的関数）への適合度が高い解候補ほど次の世代に高い確率で生き残るように選択される。そして、この世代交代を繰り返し行うことにより、適合度の低い遺伝子を持つ解候補は淘汰され、適合度の高い遺伝子を持つ解候補が生き残り、最終的に目的関数をより最適化する解を得ることができる。
【非特許文献１】伊庭斉志、「進化論的計算の方法」、東京大学出版会、１９９９年
【発明の開示】
【発明が解決しようとする課題】
【０００３】
ところで、上述したようなＧＡを実行する場合、選択された解候補のうち、どのような割合で交叉、突然変異等を発生させるかを決定するパラメータ群（例えば、交叉率、突然変異率等）を設定する必要がある。これらのパラメータは探索効率に影響を与えるため、これらパラメータの設定は非常に重要視されるが、最適となるパラメータは対象となる問題毎に異なることが知られている。
しかしながら、最適なパラメータを得るためには、上記ＧＡを運用する前段階において、膨大な予備実験を行うか、或いは、メタＧＡなどの適応的パラメータ調節の手法を用いる必要がある。このような処理は、大規模反復計算であるＧＡを更に大規模に反復することとなるため、大規模な計算機能力を必要とするとともに、膨大な時間を要していた。
【０００４】
本発明は、上記問題を解決するためになされたもので、処理負担の低減および時間短縮を図ることのできる最適解探索装置及び方法並びにプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
上記課題を解決するために、本発明は以下の手段を採用する。
本発明は、計算機を備え、遺伝的アルゴリズムを用いて最適な解候補を探索する最適解探索装置であって、前記計算機が、島モデルの各島に対して互いに異なるパラメータ群を設定するパラメータ群設定部と、設定された前記パラメータ群を用いて、前記島毎に解候補の探索を行う計算部と、所定のタイミングで、前記計算部により得られた各解候補の適合評価値を取得し、これらに基づいて各前記島の適合評価を行う島適合評価部とを備え、前記島間で解候補の移住が行われる場合に、前記パラメータ群設定部は、前記島適合評価部による適合評価の結果が最良であった島に対しては前回と同じパラメータ群を設定し、他の前記島に対しては新たなパラメータ群を設定する最適解探索装置を提供する。
【０００６】
本発明によれば、島モデルを適用した分散ＧＡにおいて、各島に互いに異なるパラメータ群を設定し、移住等の所定のタイミングにおいて、最も適合評価値の高い島に関しては現時点でのパラメータ群を保持し、他の島に対しては新たなパラメータ群を設定して、ＧＡを遂行し、最良解を探索する。このように、最良のパラメータ群を常に保持するので、性能の向上を図ることができ、更に、所定のタイミングごとに新たなパラメータを導入するので、予期しない更に優れた解候補の発見を期待することも可能となる。更に、解探索を行いながらパラメータ群の最適化を行うので、ＧＡに先駆けてパラメータ群の最適化処理等を行う必要がなくなり、処理負担の大幅な軽減を実現できるとともに、処理時間の短縮を図ることが可能となる。
【０００７】
上記最適解探索装置は、前記島適合評価部による適合評価の結果が最良であった島に設定されていたパラメータ群を記憶する記憶部を更に備えていてもよい。
【０００８】
これにより、所定のタイミング毎に最良のパラメータ群を保存することができる。
【０００９】
上記最適解探索装置において、前記所定のタイミングは、例えば、前記島間における解候補の移住が行われるときである。
【００１０】
島間における解候補の移住のタイミングで島の適合評価等を行うことにより、既存のアルゴリズムを大幅に変更することなく、処理を遂行することが可能となる。
【００１１】
上記最適解探索装置において、前記計算部は前記島毎に対応して設けられる複数の分散計算部を備え、各前記分散計算部は、各解候補の適合評価を行う固体評価部と、前記適合評価に基づいて前記解候補の選択を行う固体選択部と、前記固体選択部によって選択された前記解候補に遺伝的操作を行うことにより次世代の解候補を作成する遺伝的操作部とを備えていてもよい。
【００１２】
このような構成によれば、固体評価部により各解候補の適合評価が行われ、この適合評価に基づいて個体選択部により複数の解候補が選択、複製される。そして、遺伝的操作部により、当該島に設定されているパラメータ群に基づいて決定される交叉率、突然変異率、逆位率等に従って、複製された解候補に対して遺伝的操作が行われ、次世代における解候補の集団が生成される。そして、上記各部が順番に処理を遂行することにより解候補の世代交代が繰り返し行われ、最適な解候補の探索が進められる。
【００１３】
本発明は、計算機により遺伝的アルゴリズムを用いて最適な解候補を探索する最適解探索方法であって、島モデルの各島に対して互いに異なるパラメータ群を設定する工程と、設定された前記パラメータ群を用いて、前記島毎に解候補の探索を行う工程と、所定のタイミングで、各前記解候補の適合評価値を取得し、これらに基づいて各前記島の適合評価を行う工程とを含み、前記島間における解候補の移住が行われる場合に、前記適合評価の結果が最良であった島に対しては前回と同じパラメータ群を設定し、他の前記島に対しては新たなパラメータ群を設定する最適解探索方法を提供する。
【００１４】
本発明は、遺伝的アルゴリズムを用いて最適な解候補を探索するための処理をコンピュータに実行させるための最適解探索プログラムであって、島モデルの各島に対して互いに異なるパラメータ群を設定する処理と、設定された前記パラメータ群を用いて、前記島毎に解候補の探索を行う処理と、所定のタイミングで、各前記解候補の適合評価値を取得し、これらに基づいて各前記島の適合評価を行う処理とを含み、前記島間における解候補の移住が行われる場合に、前記適合評価の結果が最良であった島に対しては前回と同じパラメータ群を設定させ、他の島に対しては新たなパラメータ群を設定させる最適解探索プログラムを提供する。
【００１５】
また、本発明の最適解探索装置及び方法並びにプログラムは、様々な技術分野に適用可能なものである。一例としては、例えば、カーナビゲーションにおける最適経路の探索、飛行機やヘリコプター等の最適な航路の探索等が挙げられる。
【発明の効果】
【００１６】
本発明によれば、最適な解候補の探索処理において、処理負担の低減および時間短縮を図ることができるという効果を奏する。
【発明を実施するための最良の形態】
【００１７】
以下に、本発明に係る最適解探索装置及び方法並びにプログラムの一実施形態について、図面を参照して説明する。
図１は、本実施形態に係る最適解探索装置の概略構成を示したブロック図である。
図１に示すように、本実施形態に係る最適解探索装置１０は、コンピュータシステム（計算機システム）であり、ＣＰＵ（中央演算処理装置）１、ＲＡＭ（Random Access
Memory）などの主記憶装置２、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk
Drive）などの補助記憶装置３、キーボードやマウスなどの入力装置４、及びモニタやプリンタなどの出力装置５などを備えて構成されている。
補助記憶装置３には、各種プログラムが格納されており、ＣＰＵ１が補助記憶装置３からＲＡＭなどの主記憶装置２にプログラムを読み出し、実行することにより種々の処理を実現させる。
【００１８】
図２は、最適解探索装置１０が備える機能を展開して示した機能ブロック図である。図２に示されるように、最適解探索装置１０は、複数の解候補をランダムに生成して母集団を作成する初期固体生成部１１と、初期固体生成部１１により作成された母集団の解候補を分割して複数の島モデルを生成する島モデル生成部１２と、各島に対してパラメータ群を設定するパラメータ群設定部１３と、解候補の適合評価、選択・複製、及び遺伝的操作等のアルゴリズムを島毎に実行する計算部１４と、所定のタイミングで計算部１４により得られた各解候補の適合評価値を取得し、これらに基づいて各島の適合評価を行う島適合評価部１５と、島適合評価部１５による適合評価の結果が最良であった島に設定されているパラメータ群を最良パラメータ群として保存する記憶部１６と、最適解を決定し出力する最適解決定部１７とを備えている。
【００１９】
計算部１４は、図３に示すように、島毎に分散計算部１４１を備えている。各分散計算部１４１は、例えば、固体評価部１４１ａ、選択部１４１ｂ、遺伝的操作部１４１ｃを備えている。各分散計算部１４１は、対応する島における固体評価、固体選択、及び固体の遺伝的操作を繰り返し行うことで、適合度の高い解候補の探索を行う。
【００２０】
次に、上述した最適解探索装置１０が備える各部において実行される処理内容について図４を参照して説明する。なお、図２に示した各部により実現される後述の各種処理は、ＣＰＵ１が補助記憶装置３に記憶されている最適解探索プログラムを主記憶装置２に読み出して実行することにより実現されるものである。
【００２１】
まず、初期固体生成部１１は、複数の解候補をランダムに生成し、母集団を設定する（図４のステップＳＡ１）。次に、島モデル生成部１２は、母集団の解候補を分割し、複数の島を生成する（ステップＳＡ２）。本実施形態では、説明の便宜上、図５の上段に示すように、Ａ島、Ｂ島、Ｃ島からなる３つの島を生成した場合を考える。
【００２２】
次に、パラメータ群設定部１３は、Ａ島、Ｂ島、Ｃ島に対して互いに異なるパラメータ群を設定する（ステップＳＡ３）。パラメータ群は、例えば、交叉率、突然変異率、逆位率、移住率、移住間隔等のように、ＧＡを行う上でＧＡの性質を左右する重要とされる複数のパラメータから構成されている。また、これらの外、ルーレット戦略やトーナメント戦略といった淘汰（選択）戦略等もパラメータとして加えられても良い。ここで、「互いに異なる」とは、例えば、パラメータ群を構成する少なくとも１つのパラメータ（要素）に対して設定値が異なっていればよく、例えば、上述した交叉回数、突然変異率等の全てのパラメータについて異なる値が設定される必要はない。
【００２３】
本実施形態では、図５の上段に示されるように、Ａ島に対してパラメータ群ａを、Ｂ島に対してパラメータ群ｂを、Ｃ島に対してパラメータ群ｃを設定した場合を考える。このとき、パラメータ群設定部１３は、最適と推定される初期パラメータ群を保有している。パラメータ群設定部１３は、パラメータ群の初期設定時において、初期パラメータ群をいずれかの島に設定する。このように初期パラメータ群を保有しておくことで、一定の性能を保持することが可能となる。
【００２４】
このようにして各島にパラメータ群が設定されると、計算部１４の各分散計算部１４１は、対応する島について解候補の探索をそれぞれ開始する。具体的には、各島において、固体評価部１４１ａによる各解候補の適合度評価（ステップＳＡ４）、選択部１４１ｂによる適合度評価に基づく解候補の選択・複製（ステップＳＡ５）、遺伝的操作部１４１ｃによる複製した解候補を用いた交叉、突然変異等の遺伝的操作（ステップＳＡ６）が順番に繰り返し実行されることにより、解候補の世代交代が行われる。なお、このような解候補の探索手法については、公知の技術を採用することが可能であり、その手法については特に限定されない。
【００２５】
次に、上述した各分散計算部１４１による解候補の世代交代が所定回数行われることにより、予め設定されている所定の世代に到達すると（ステップＳＡ７において「ＹＥＳ」）、終了条件を満たすか否かを判定する（ステップＳＡ８）。ここで、終了条件は、例えば、世代交代が予め設定されている所定の世代に到達したか、或いは、いずれかの解候補の適合評価値が予め設定されている最終適合評価値に到達したか、或いは、処理開始からの経過時間が所定の時間に達したか等である。この結果、終了条件を満たしていない場合には（ステップＳＡ８において「ＮＯ」）、各分散計算部１４１は、この時点での解候補とその適合評価値とを島適合評価部１５に出力する。
【００２６】
島適合評価部１５は、計算部１４から与えられた各島における各解候補の適合評価値に基づいて、各島の適合評価を行う（ステップＳＡ９）。具体的には、所定の手順に従って各島の適合評価値を算出する。適合評価値については、任意の評価関数を用いることが可能であるが、例えば、各島の平均適合評価値、各島における最高の適合評価値とそこから一定世代前における最高の適合評価値との差分等を使用することが可能である。このようにして、島適合評価部１５は各島の適合評価値を算出すると、適合評価値の最も高かった島を最良島として特定するとともに、最良島に設定されているパラメータ群を記憶部１６に保存する（ステップＳＡ１０）。
【００２７】
続いて、島モデル生成部１２は、各島の解候補を移住させ、各島を構成する解候補を変更する（ステップＳＡ１１）。また、パラメータ群設定部１３は、最良島として特定した島以外の島、例えば、Ｂ島を最良島として特定した場合には、図５の後段に示されるようにＡ島とＣ島に対して新たなパラメータ群ｄ、ｅをそれぞれ設定する（ステップＳＡ１２）。このとき新規に設定されるパラメータ群は、最良島のパラメータ群ｂに微小の変化を加えたものとしてもよい。このように、最良パラメータ群に基づいて他のパラメータ群を設定することにより、更なる高品質の解候補を期待することが可能となる。
【００２８】
このようにして、移住並びにパラメータ群の維持・再設定が行われると、図４のステップＳＡ４に戻り、計算部１４による解候補の探索が上述と同様の手順に従って行われる。そして、ステップＳＡ４〜ＳＡ１２が繰り返し行われることにより、ステップＳＡ８において終了条件を満たすと判断された場合には（ステップＳＡ８において「ＹＥＳ」）、計算部１４から各島における解候補とその適合評価値が最適解決定部１７に出力される。
【００２９】
最適解決定部１７は、計算部１４から取得した解候補の中から最高の適合評価値を持つ解候補を最適解として定め、この最適解を出力情報として出力し（ステップＳＡ１３）、当該処理を終了する。
【００３０】
以上、説明してきたように、本実施形態に係る最適解探索装置及び方法並びにプログラムによれば、島モデルを適用した分散ＧＡにおいて、各島に互いに異なるパラメータ群を設定し、移住等の所定のタイミングにおいて、適合評価値の最も高い島に関しては現時点でのパラメータ群を保持し、他の島に対しては新たなパラメータ群を設定して、ＧＡを遂行し、最良解を探索する。このように、最良のパラメータ群を常に保持することで、性能の向上を図ることができ、更に、所定のタイミングごとに新たなパラメータを導入することにより、予期しない更に優れた解候補の発見を期待することも可能となる。更に、解探索を行いながらパラメータ群の最適化を行うので、ＧＡに先駆けてパラメータ群の最適化処理等を行う必要がなくなり、処理負担の大幅な軽減を実現できるとともに、処理時間の短縮を図ることが可能となる。また、最良島に設定されていたパラメータ群が記憶部１６に蓄積されるので、所定世代における最適なパラメータ群を得ることが可能となる。
【００３１】
なお、上記実施形態においては、最良島も含む各島間で解候補の移住を実施していたが、これに代えて、最良島以外の島間において解候補の移住を行うこととしてもよい。換言すると、最良島については解候補の移住を禁止することとしてもよい。これにより、最良島の解候補の品質が低減されることを回避することが可能となる。
【００３２】
〔適用例〕
次に、本発明の最適解探索装置及び方法並びにプログラムを、カーナビゲーションシステムの一部として備えられる最適経路を決定する最適経路決定装置に適用した場合の一実施形態について説明する。
【００３３】
この場合、最適解探索装置１０には、入力情報として、現在地、目的地等が与えられる。現在地は、例えば、車両に搭載されているＧＰＳ車載器等により取得される位置情報を用いることが可能であり、目的地は、例えば、運転手等によって入力される情報を用いることが可能である。
これらの入力情報が与えられると、最適解探索装置１０の初期固体生成部１２は、任意に解候補を生成し、母集団を作成する。この場合、解候補として、現在地から目的地までを繋ぐ様々な経路が生成される。続いて、島モデル生成部１２によってこれらの解候補は分割されて複数の島が生成され、パラメータ群設定部１３により各島に対してパラメータ群が設定される。そして、計算部１４により各島における解候補の探索が行われることにより、好ましくない経路は淘汰され、より最適な経路が残される。このとき、固体評価部１４１ａで用いられる評価関数は、例えば、到達時間、燃費、安全性に関する評価パラメータを用いて表される。
【００３４】
そして、解候補の移住のタイミングにおいて、島適合評価部１５により各島の適合評価が行われ、適合評価値が最良である最良島のパラメータ群が記憶部１６に保存される。また、島モデル生成部１２により各島間における解候補の移住が行われるとともに、パラメータ群設定部１３によって最良島以外の島に対して新たなパラメータ群が設定される。このようにして、移住、パラメータ群の再設定が完了すると、各島に対する解候補の探索が計算部１４によって再び実施される。そして、上述したような処理が繰り返し行われることにより、終了条件を満たすと判断されると、計算部１４は各島の解候補と適合評価値とを最適解決定部１７に出力する。最適解決定部１７は、最高の適合評価値を示した解候補を最適経路として出力する。
【００３５】
なお、上述した実施形態では、車両に搭載されているカーナビゲーションシステムにおける最適経路の探索に本発明の最適探索方法等を適用する例を代表として取り上げたが、本発明の最適探索装置及び方法並びにプログラムは、様々な分野において適用が可能であることはいうまでもない。この場合、各適用に応じて入力情報、評価関数等が与えられる。例えば、ヘリコプターの最適航路探索に適用する場合には、入力情報として、初期位置、初期針路、初期速力、目標位置、目標到達時針路、速力、風速、風向等が与えられ、最小飛行時間、最小消費燃費、エリアカバー等を評価パラメータとした評価関数が与えられる。
【００３６】
以上、本発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、本発明の要旨を逸脱しない範囲の設計変更等も含まれる。
【図面の簡単な説明】
【００３７】
【図１】本発明の一実施形態に係る最適解探索装置の概略構成を示したブロック図である。
【図２】本発明の一実施形態に係る最適解探索装置が備える機能を展開して示した機能ブロック図である。
【図３】図２に示した計算部の詳細構成例を示した図である。
【図４】本発明の一実施形態に係る最適解探索装置によって実行される処理の手順を示したフローチャートである。
【図５】島モデルについて説明するための図である。
【図６】交叉について説明するための図である。
【図７】突然変異について説明するための図である。
【符号の説明】
【００３８】
１  ＣＰＵ
２  主記憶装置
３  補助記憶装置
４  入力装置
５  出力装置
１０  最適解探索装置
１１  初期固体生成部
１２  島モデル生成部
１３  パラメータ群設定部
１４  計算部
１５  島適合評価部
１６  記憶部
１７  最適解決定部
１４１  分散計算部
１４１ａ  固体評価部
１４１ｂ  選択部
１４１ｃ  遺伝的操作部
【図１】
2009069865.tif 000003
【図２】
2009069865.tif 000004
【図３】
2009069865.tif 000005
【図４】
2009069865.tif 000006
【図５】
2009069865.tif 000007
【図６】
2009069865.tif 000008
【図７】
2009069865.tif 000009