行動経路探索装置及び方法並びにプログラム
【課題】リアルタイムで最適解を得ることができるとともに、教師データの影響を受けない最適解導出を実現する。
【解決手段】計算機が、複数の解候補を生成する解候補生成部１１と、各解候補の適合評価を行う評価部１２と、適合評価に基づいて解候補の選択を行う選択部１３と、選択部１３によって選択された解候補に遺伝的操作を行うことにより次世代の解候補を作成する遺伝的操作部１４とを備え、解候補を構成する少なくとも１つの非終端記号には、動きを決定付けるパラメータが割り当てられている行動経路探索装置１０を提供する。
【解決手段】計算機が、複数の解候補を生成する解候補生成部１１と、各解候補の適合評価を行う評価部１２と、適合評価に基づいて解候補の選択を行う選択部１３と、選択部１３によって選択された解候補に遺伝的操作を行うことにより次世代の解候補を作成する遺伝的操作部１４とを備え、解候補を構成する少なくとも１つの非終端記号には、動きを決定付けるパラメータが割り当てられている行動経路探索装置１０を提供する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、遺伝的アルゴリズム（Genetic Algorithm、以下「ＧＡ」という。）を用いて行動経路を探索する行動経路探索装置及び方法並びにプログラムに関するものである。
【背景技術】
【０００２】
ＧＡは、生物の進化を模倣した確率的な最適化アルゴリズムである。以下、ＧＡの概要について簡単に説明する。
まず、最適化問題の解候補を例えば、遺伝子の一次ストリングである染色体として表現し、様々な遺伝子をもつ解候補をランダムに選択して、初期世代の集団（母集団）を作成する。次に、各解候補の適合度（最適化問題での目的関数の値）を計算する。続いて、適合度に応じて複数の解候補を選択（複製選択）し、これらがもつ遺伝子の交叉（crossover；図５参照）、突然変異（mutation；図６参照）、逆位等の遺伝的操作を行うことにより、次世代の解候補の集団を作成する。このとき、解候補の選択では、環境（目的関数）への適合度が高い解候補ほど次の世代に高い確率で生き残るように選択される。そして、この世代交代を繰り返し行うことにより、適合度の低い遺伝子を持つ解候補は淘汰され、適合度の高い遺伝子を持つ解候補が生き残り、最終的に目的関数をより最適化する解を得ることができる。
【非特許文献１】伊庭斉志、「進化論的計算の方法」、東京大学出版会、１９９９年
【発明の開示】
【発明が解決しようとする課題】
【０００３】
ところで、上述したようなＧＡを実際の最適化問題に運用する場合、運用の前段階として、様々な入力を教師データとして与え、それらの問題に適切な出力をすることのできるアルゴリズムを生成させる必要がある。換言すると、アルゴリズム自体を最適化対象として最適化を行うことにより、最適アルゴリズムを得る。このとき、解候補を構成する非終端記号には、条件分岐や演算子が割り当てられる。このようにして得られた最適アルゴリズムは、その後の最適化問題の運用時に用いられる。
【０００４】
上述のようにアルゴリズムを最適化対象として最適化を行った場合、教師データとして与えられる入力データに限りがあるため、運用時において教師データとかけ離れた入力データが入力された場合には、最適な解を得ることができないという問題があった。
また、実際の運用の前段階として、最適化アルゴリズムを生成するための計算処理を行う必要があるため、実際の運用までに時間を要するという問題があった。
【０００５】
本発明は、上記問題を解決するためになされたもので、リアルタイムで最適解を得ることができるとともに、教師データの影響を受けない最適解導出を実現することが可能な行動経路探索装置及び方法並びにプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記課題を解決するために、本発明は以下の手段を採用する。
本発明は、計算機を備え、遺伝的アルゴリズムを用いて最適な行動経路を探索する行動経路探索装置であって、前記計算機が、複数の解候補を生成する解候補生成部と、各前記解候補の適合評価を行う評価部と、前記適合評価に基づいて前記解候補の選択を行う選択部と、前記選択部によって選択された前記解候補に遺伝的操作を行うことにより次世代の解候補を作成する遺伝的操作部とを備え、前記解候補を構成する少なくとも１つの非終端記号には、動きを決定付けるパラメータが割り当てられている行動経路探索装置を提供する。
【０００７】
本発明によれば、評価部により各解候補の適合評価が行われ、この適合評価に基づいて選択部により複数の解候補が選択、複製される。そして、選択、複製された解候補に対して、遺伝的操作部により交叉率、突然変異率、逆位率等の遺伝的操作が行われ、次世代における解候補の集団が生成される。そして、上記各部が順番に処理を遂行することにより解候補の世代交代が繰り返し行われ、最適な行動経路の探索が進められる。この場合において、解候補を構成する少なくとも１つの非終端記号には、動きを決定付けるパラメータが割り当てられているので、解候補として行動経路を直接的に導くことができ、最終的に得られた解候補をそのまま出力データとして出力することが可能となる。このように、解候補の構成を工夫することで、従来のように、運用時に先駆けて行われていた最適アルゴリズムの計算処理を省略することができ、リアルタイムで行動経路を求めることが可能となる。更に、教師データなどが不要となるため、如何なる入力データに対しても適切な行動経路を求めることが可能となる。
【０００８】
上記行動経路探索装置において、前記動きを決定付けるパラメータは、例えば、変針または変速である。
また、上記行動経路探索装置において、前記解候補を構成する少なくとも１つの非終端記号には、初期位置を設定するためのプログラムが割り当てられていてもよい。
【０００９】
本発明は、計算機により遺伝的アルゴリズムを用いて最適な行動経路を探索する行動経路探索方法であって、複数の解候補を生成する工程と、各前記解候補の適合評価を行う工程と、前記適合評価に基づいて前記解候補の選択を行う工程と、選択された前記解候補に遺伝的操作を行うことにより次世代の解候補を作成する工程とを含み、前記解候補を構成する少なくとも１つの非終端記号には、動きを決定付けるパラメータが割り当てられている行動経路探索方法を提供する。
【００１０】
本発明は、遺伝的アルゴリズムを用いて最適な行動経路を探索するための処理をコンピュータに実行させるための行動経路探索プログラムであって、複数の解候補を生成する処理と、各前記解候補の適合評価を行う処理と、前記適合評価に基づいて前記解候補の選択を行う処理と、選択された前記解候補に遺伝的操作を行うことにより次世代の解候補を作成する処理とを含み、前記解候補を構成する少なくとも１つの非終端記号には、動きを決定付けるパラメータが割り当てられている行動経路探索プログラムを提供する。
【００１１】
また、本発明の行動経路探索装置及び方法並びにプログラムは、様々な技術分野に適用可能なものである。一例としては、例えば、カーナビゲーションにおける最適経路の探索、航空機、ヘリコプター、船舶、潜水艦等の最適な航路の探索等が挙げられる。
【発明の効果】
【００１２】
本発明によれば、リアルタイムで最適解を得ることができるとともに、教師データの影響を受けない最適解導出を実現することができるという効果を奏する。
【発明を実施するための最良の形態】
【００１３】
以下に、本発明に係る行動経路探索装置及び方法並びにプログラムの一実施形態について、図面を参照して説明する。
図１は、本実施形態に係る行動経路探索装置の概略構成を示したブロック図である。
図１に示すように、本実施形態に係る行動経路探索装置１０は、コンピュータシステム（計算機システム）であり、ＣＰＵ（中央演算処理装置）１、ＲＡＭ（Random Access
Memory）などの主記憶装置２、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk
Drive）などの補助記憶装置３、キーボードやマウスなどの入力装置４、及びモニタやプリンタなどの出力装置５などを備えて構成されている。
補助記憶装置３には、各種プログラムが格納されており、ＣＰＵ１が補助記憶装置３からＲＡＭなどの主記憶装置２にプログラムを読み出し、実行することにより種々の処理を実現させる。
【００１４】
図２は、行動経路探索装置１０が備える機能を展開して示した機能ブロック図である。図２に示されるように、行動経路探索装置１０は、複数の解候補をランダムに生成して母集団を作成する解候補生成部１１と、解候補の適合評価を行う評価部１２と、評価部１２による適合評価に基づいて解候補の選択を行う選択部１３と、選択部１３によって選択された解候補に複製、交叉、突然変異、逆位等の遺伝的操作等のアルゴリズムを実行する遺伝操作部１４と、最適解を決定し出力する最適解決定部１５とを備えている。
行動経路探索装置１０は、解候補の評価、選択、及び遺伝的操作を繰り返し行うことで、適合度の高い解候補の探索を行う。
【００１５】
次に、上述した行動経路探索装置１０が備える各部において実行される処理内容について図３を参照して説明する。なお、図２に示した各部により実現される後述の各種処理は、ＣＰＵ１が補助記憶装置３に記憶されている行動経路探索プログラムを主記憶装置２に読み出して実行することにより実現されるものである。
また、本実施形態では、航空機の最適航路を探索する場合を例示して説明する。
【００１６】
まず、入力データとして、初期位置、目標位置、経由すべき中継点、速力、風速、風向等が与えられると、解候補生成部１１は、これらの入力データに基づいて複数の解候補をランダムに生成する（図３のステップＳＡ１）。ここで、解候補生成部１１によって生成される解候補の一例を図４に示す。図４に示されるように、解候補は、非終端記号と終端記号とで表される複数のノードによって構成されており、非終端記号の少なくとも１つには動きを決定付けるパラメータが割り当てられる。動きを決定付けるパラメータは、行動経路を探索する対象物、すなわち、本実施形態においては、航空機がどのような行動をとるかを決定付ける情報となる。例えば、図５に示されるように、変速、変針等が挙げられる。
【００１７】
非終端記号には、少なくとも１つの子ノードが接続される。これらの子ノードには、当該非終端記号に割り当てられた動きを決定付けるパラメータに応じた数値が任意に割り当てられる。例えば、変速が割り当てられた非終端記号２０ａには、どのような変速を行うかを示す子ノード２１ａ、２１ｂ、例えば、＋１ｋｔ／ｓｅｃ、５分間等の数値が割り当てられた子ノードが接続される。これは、毎秒１ノットで５分間変速することを示している。また、変速が割り当てられた他の非終端記号２０ｂには、例えば、０ｋｔ／ｓｅｃ、１０分間等の数値が割り当てられた子ノード２２ａ、２２ｂが接続される。これは、速度を変えずに移動することを示している。
また、変針が割り当てられた非終端記号２０ｃには、どのような変針を行うかを示す子ノード２３ａ、２３ｂ、例えば、−１ｄｅｇ／ｓｅｃ、７分間等の数値が割り当てられた子ノードが接続される。これは、毎秒−１度で７分間針路を変化させることを示している。
【００１８】
そして、上述したような構成を持つ複数の解候補が生成されると、これらの解候補は評価部１２（図２参照）に与えられる。評価部１２は、各解候補の適合度評価を行う（図３のステップＳＡ２）。例えば、評価部１２は、飛行時間、消費燃費等を評価パラメータとした評価関数を用いて各解候補の適合度評価を行う。
選択部１３は、評価部１２によって得られた適合度評価に基づいて解候補の選択・複製を行う（ステップＳＡ３）。遺伝的操作部１４は、選択部１３により選択・複製された解候補に対して交叉、突然変異、逆位等の遺伝的操作を行う（ステップＳＡ４）。そして、上記適合度評価、解候補の選択・複製、並びに遺伝的操作が順番に繰り返し実行されることにより、解候補の世代交代が行われ、好ましくない行動経路は淘汰され、より最適な経路が残される。なお、このような解候補の探索手法については、公知の技術を採用することが可能であり、その手法については特に限定されない。
【００１９】
次に、上述した解候補の世代交代が所定回数行われることにより、終了条件を満たした場合には（ステップＳＡ５において「ＹＥＳ」）、評価部１２から解候補とその適合評価値が最適解決定部１５に出力される。ここで、終了条件とは、例えば、世代交代が予め設定されている所定の世代に到達したか、または、いずれかの解候補の適合評価値が予め設定されている最終適合評価値に到達したか、または、処理開始からの経過時間が所定の時間に達したか等である。
【００２０】
最適解決定部１５は、評価部１２から取得した解候補の中から最高の適合評価値を持つ解候補を最適解として定め、この最適解を出力データとして出力し（ステップＳＡ６）、当該処理を終了する。
【００２１】
以上、説明してきたように、本実施形態に係る行動経路探索装置及び方法並びにプログラムによれば、解候補を構成する少なくとも１つの非終端記号には、動きを決定付けるパラメータが割り当てられているので、解候補として行動経路を直接的に導くことができ、最終的に得られた解候補をそのまま出力データとして出力することが可能となる。
このように、解候補の構成を工夫することで、従来のように、運用時に先駆けて行われていた最適アルゴリズムの計算処理を省略することができ、リアルタイムで行動経路を求めることが可能となる。更に、教師データなどが不要となるため、如何なる入力データに対しても適切な行動経路を求めることが可能となる。
【００２２】
なお、上述した実施形態では、航空機の最適航路を探索する場合について例示して説明したが、本発明の行動経路探索装置及び方法並びにプログラムは、様々な分野において適用が可能であることはいうまでもない。この場合、各適用に応じて入力情報、評価関数等が与えられる。例えば、カーナビゲーションシステム等の車両の最適経路を探索する場合には、入力データとして、現在地、目的地等が与えられ、また、到達時間、消費燃費等を評価パラメータとした評価関数が与えられる。また、車両の場合には、航空機や船舶等と異なり、道がないところを走行できないという制約があるため、動きを決定付けるパラメータとしては、交差点では、右折、左折、直進する等、車両独特のパラメータを用いることとなる。このように、動きを決定付けるパラメータは、対象物に応じて決められる。
また、図４に例示した解候補の構成において、初期位置を設定するためのプログラムが割り当てられた非終端記号を更に付加してもよい。このように初期位置を設定するためのプログラムを付加することで、初期位置が不明である場合でも適用することが可能となる。
【００２３】
以上、本発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、本発明の要旨を逸脱しない範囲の設計変更等も含まれる。
【図面の簡単な説明】
【００２４】
【図１】本発明の一実施形態に係る行動経路探索装置の概略構成を示したブロック図である。
【図２】本発明の一実施形態に係る行動経路探索装置が備える機能を展開して示した機能ブロック図である。
【図３】本発明の一実施形態に係る行動経路探索装置によって実行される処理の手順を示したフローチャートである。
【図４】解候補の一構成例を示した図である。
【図５】交叉について説明するための図である。
【図６】突然変異について説明するための図である。
【符号の説明】
【００２５】
１ ＣＰＵ
２ 主記憶装置
３ 補助記憶装置
４ 入力装置
５ 出力装置
１０ 行動経路探索装置
１１ 解候補生成部
１２ 評価部
１３ 選択部
１４ 遺伝的操作部
１５ 最適解決定部
【技術分野】
【０００１】
本発明は、遺伝的アルゴリズム（Genetic Algorithm、以下「ＧＡ」という。）を用いて行動経路を探索する行動経路探索装置及び方法並びにプログラムに関するものである。
【背景技術】
【０００２】
ＧＡは、生物の進化を模倣した確率的な最適化アルゴリズムである。以下、ＧＡの概要について簡単に説明する。
まず、最適化問題の解候補を例えば、遺伝子の一次ストリングである染色体として表現し、様々な遺伝子をもつ解候補をランダムに選択して、初期世代の集団（母集団）を作成する。次に、各解候補の適合度（最適化問題での目的関数の値）を計算する。続いて、適合度に応じて複数の解候補を選択（複製選択）し、これらがもつ遺伝子の交叉（crossover；図５参照）、突然変異（mutation；図６参照）、逆位等の遺伝的操作を行うことにより、次世代の解候補の集団を作成する。このとき、解候補の選択では、環境（目的関数）への適合度が高い解候補ほど次の世代に高い確率で生き残るように選択される。そして、この世代交代を繰り返し行うことにより、適合度の低い遺伝子を持つ解候補は淘汰され、適合度の高い遺伝子を持つ解候補が生き残り、最終的に目的関数をより最適化する解を得ることができる。
【非特許文献１】伊庭斉志、「進化論的計算の方法」、東京大学出版会、１９９９年
【発明の開示】
【発明が解決しようとする課題】
【０００３】
ところで、上述したようなＧＡを実際の最適化問題に運用する場合、運用の前段階として、様々な入力を教師データとして与え、それらの問題に適切な出力をすることのできるアルゴリズムを生成させる必要がある。換言すると、アルゴリズム自体を最適化対象として最適化を行うことにより、最適アルゴリズムを得る。このとき、解候補を構成する非終端記号には、条件分岐や演算子が割り当てられる。このようにして得られた最適アルゴリズムは、その後の最適化問題の運用時に用いられる。
【０００４】
上述のようにアルゴリズムを最適化対象として最適化を行った場合、教師データとして与えられる入力データに限りがあるため、運用時において教師データとかけ離れた入力データが入力された場合には、最適な解を得ることができないという問題があった。
また、実際の運用の前段階として、最適化アルゴリズムを生成するための計算処理を行う必要があるため、実際の運用までに時間を要するという問題があった。
【０００５】
本発明は、上記問題を解決するためになされたもので、リアルタイムで最適解を得ることができるとともに、教師データの影響を受けない最適解導出を実現することが可能な行動経路探索装置及び方法並びにプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記課題を解決するために、本発明は以下の手段を採用する。
本発明は、計算機を備え、遺伝的アルゴリズムを用いて最適な行動経路を探索する行動経路探索装置であって、前記計算機が、複数の解候補を生成する解候補生成部と、各前記解候補の適合評価を行う評価部と、前記適合評価に基づいて前記解候補の選択を行う選択部と、前記選択部によって選択された前記解候補に遺伝的操作を行うことにより次世代の解候補を作成する遺伝的操作部とを備え、前記解候補を構成する少なくとも１つの非終端記号には、動きを決定付けるパラメータが割り当てられている行動経路探索装置を提供する。
【０００７】
本発明によれば、評価部により各解候補の適合評価が行われ、この適合評価に基づいて選択部により複数の解候補が選択、複製される。そして、選択、複製された解候補に対して、遺伝的操作部により交叉率、突然変異率、逆位率等の遺伝的操作が行われ、次世代における解候補の集団が生成される。そして、上記各部が順番に処理を遂行することにより解候補の世代交代が繰り返し行われ、最適な行動経路の探索が進められる。この場合において、解候補を構成する少なくとも１つの非終端記号には、動きを決定付けるパラメータが割り当てられているので、解候補として行動経路を直接的に導くことができ、最終的に得られた解候補をそのまま出力データとして出力することが可能となる。このように、解候補の構成を工夫することで、従来のように、運用時に先駆けて行われていた最適アルゴリズムの計算処理を省略することができ、リアルタイムで行動経路を求めることが可能となる。更に、教師データなどが不要となるため、如何なる入力データに対しても適切な行動経路を求めることが可能となる。
【０００８】
上記行動経路探索装置において、前記動きを決定付けるパラメータは、例えば、変針または変速である。
また、上記行動経路探索装置において、前記解候補を構成する少なくとも１つの非終端記号には、初期位置を設定するためのプログラムが割り当てられていてもよい。
【０００９】
本発明は、計算機により遺伝的アルゴリズムを用いて最適な行動経路を探索する行動経路探索方法であって、複数の解候補を生成する工程と、各前記解候補の適合評価を行う工程と、前記適合評価に基づいて前記解候補の選択を行う工程と、選択された前記解候補に遺伝的操作を行うことにより次世代の解候補を作成する工程とを含み、前記解候補を構成する少なくとも１つの非終端記号には、動きを決定付けるパラメータが割り当てられている行動経路探索方法を提供する。
【００１０】
本発明は、遺伝的アルゴリズムを用いて最適な行動経路を探索するための処理をコンピュータに実行させるための行動経路探索プログラムであって、複数の解候補を生成する処理と、各前記解候補の適合評価を行う処理と、前記適合評価に基づいて前記解候補の選択を行う処理と、選択された前記解候補に遺伝的操作を行うことにより次世代の解候補を作成する処理とを含み、前記解候補を構成する少なくとも１つの非終端記号には、動きを決定付けるパラメータが割り当てられている行動経路探索プログラムを提供する。
【００１１】
また、本発明の行動経路探索装置及び方法並びにプログラムは、様々な技術分野に適用可能なものである。一例としては、例えば、カーナビゲーションにおける最適経路の探索、航空機、ヘリコプター、船舶、潜水艦等の最適な航路の探索等が挙げられる。
【発明の効果】
【００１２】
本発明によれば、リアルタイムで最適解を得ることができるとともに、教師データの影響を受けない最適解導出を実現することができるという効果を奏する。
【発明を実施するための最良の形態】
【００１３】
以下に、本発明に係る行動経路探索装置及び方法並びにプログラムの一実施形態について、図面を参照して説明する。
図１は、本実施形態に係る行動経路探索装置の概略構成を示したブロック図である。
図１に示すように、本実施形態に係る行動経路探索装置１０は、コンピュータシステム（計算機システム）であり、ＣＰＵ（中央演算処理装置）１、ＲＡＭ（Random Access
Memory）などの主記憶装置２、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk
Drive）などの補助記憶装置３、キーボードやマウスなどの入力装置４、及びモニタやプリンタなどの出力装置５などを備えて構成されている。
補助記憶装置３には、各種プログラムが格納されており、ＣＰＵ１が補助記憶装置３からＲＡＭなどの主記憶装置２にプログラムを読み出し、実行することにより種々の処理を実現させる。
【００１４】
図２は、行動経路探索装置１０が備える機能を展開して示した機能ブロック図である。図２に示されるように、行動経路探索装置１０は、複数の解候補をランダムに生成して母集団を作成する解候補生成部１１と、解候補の適合評価を行う評価部１２と、評価部１２による適合評価に基づいて解候補の選択を行う選択部１３と、選択部１３によって選択された解候補に複製、交叉、突然変異、逆位等の遺伝的操作等のアルゴリズムを実行する遺伝操作部１４と、最適解を決定し出力する最適解決定部１５とを備えている。
行動経路探索装置１０は、解候補の評価、選択、及び遺伝的操作を繰り返し行うことで、適合度の高い解候補の探索を行う。
【００１５】
次に、上述した行動経路探索装置１０が備える各部において実行される処理内容について図３を参照して説明する。なお、図２に示した各部により実現される後述の各種処理は、ＣＰＵ１が補助記憶装置３に記憶されている行動経路探索プログラムを主記憶装置２に読み出して実行することにより実現されるものである。
また、本実施形態では、航空機の最適航路を探索する場合を例示して説明する。
【００１６】
まず、入力データとして、初期位置、目標位置、経由すべき中継点、速力、風速、風向等が与えられると、解候補生成部１１は、これらの入力データに基づいて複数の解候補をランダムに生成する（図３のステップＳＡ１）。ここで、解候補生成部１１によって生成される解候補の一例を図４に示す。図４に示されるように、解候補は、非終端記号と終端記号とで表される複数のノードによって構成されており、非終端記号の少なくとも１つには動きを決定付けるパラメータが割り当てられる。動きを決定付けるパラメータは、行動経路を探索する対象物、すなわち、本実施形態においては、航空機がどのような行動をとるかを決定付ける情報となる。例えば、図５に示されるように、変速、変針等が挙げられる。
【００１７】
非終端記号には、少なくとも１つの子ノードが接続される。これらの子ノードには、当該非終端記号に割り当てられた動きを決定付けるパラメータに応じた数値が任意に割り当てられる。例えば、変速が割り当てられた非終端記号２０ａには、どのような変速を行うかを示す子ノード２１ａ、２１ｂ、例えば、＋１ｋｔ／ｓｅｃ、５分間等の数値が割り当てられた子ノードが接続される。これは、毎秒１ノットで５分間変速することを示している。また、変速が割り当てられた他の非終端記号２０ｂには、例えば、０ｋｔ／ｓｅｃ、１０分間等の数値が割り当てられた子ノード２２ａ、２２ｂが接続される。これは、速度を変えずに移動することを示している。
また、変針が割り当てられた非終端記号２０ｃには、どのような変針を行うかを示す子ノード２３ａ、２３ｂ、例えば、−１ｄｅｇ／ｓｅｃ、７分間等の数値が割り当てられた子ノードが接続される。これは、毎秒−１度で７分間針路を変化させることを示している。
【００１８】
そして、上述したような構成を持つ複数の解候補が生成されると、これらの解候補は評価部１２（図２参照）に与えられる。評価部１２は、各解候補の適合度評価を行う（図３のステップＳＡ２）。例えば、評価部１２は、飛行時間、消費燃費等を評価パラメータとした評価関数を用いて各解候補の適合度評価を行う。
選択部１３は、評価部１２によって得られた適合度評価に基づいて解候補の選択・複製を行う（ステップＳＡ３）。遺伝的操作部１４は、選択部１３により選択・複製された解候補に対して交叉、突然変異、逆位等の遺伝的操作を行う（ステップＳＡ４）。そして、上記適合度評価、解候補の選択・複製、並びに遺伝的操作が順番に繰り返し実行されることにより、解候補の世代交代が行われ、好ましくない行動経路は淘汰され、より最適な経路が残される。なお、このような解候補の探索手法については、公知の技術を採用することが可能であり、その手法については特に限定されない。
【００１９】
次に、上述した解候補の世代交代が所定回数行われることにより、終了条件を満たした場合には（ステップＳＡ５において「ＹＥＳ」）、評価部１２から解候補とその適合評価値が最適解決定部１５に出力される。ここで、終了条件とは、例えば、世代交代が予め設定されている所定の世代に到達したか、または、いずれかの解候補の適合評価値が予め設定されている最終適合評価値に到達したか、または、処理開始からの経過時間が所定の時間に達したか等である。
【００２０】
最適解決定部１５は、評価部１２から取得した解候補の中から最高の適合評価値を持つ解候補を最適解として定め、この最適解を出力データとして出力し（ステップＳＡ６）、当該処理を終了する。
【００２１】
以上、説明してきたように、本実施形態に係る行動経路探索装置及び方法並びにプログラムによれば、解候補を構成する少なくとも１つの非終端記号には、動きを決定付けるパラメータが割り当てられているので、解候補として行動経路を直接的に導くことができ、最終的に得られた解候補をそのまま出力データとして出力することが可能となる。
このように、解候補の構成を工夫することで、従来のように、運用時に先駆けて行われていた最適アルゴリズムの計算処理を省略することができ、リアルタイムで行動経路を求めることが可能となる。更に、教師データなどが不要となるため、如何なる入力データに対しても適切な行動経路を求めることが可能となる。
【００２２】
なお、上述した実施形態では、航空機の最適航路を探索する場合について例示して説明したが、本発明の行動経路探索装置及び方法並びにプログラムは、様々な分野において適用が可能であることはいうまでもない。この場合、各適用に応じて入力情報、評価関数等が与えられる。例えば、カーナビゲーションシステム等の車両の最適経路を探索する場合には、入力データとして、現在地、目的地等が与えられ、また、到達時間、消費燃費等を評価パラメータとした評価関数が与えられる。また、車両の場合には、航空機や船舶等と異なり、道がないところを走行できないという制約があるため、動きを決定付けるパラメータとしては、交差点では、右折、左折、直進する等、車両独特のパラメータを用いることとなる。このように、動きを決定付けるパラメータは、対象物に応じて決められる。
また、図４に例示した解候補の構成において、初期位置を設定するためのプログラムが割り当てられた非終端記号を更に付加してもよい。このように初期位置を設定するためのプログラムを付加することで、初期位置が不明である場合でも適用することが可能となる。
【００２３】
以上、本発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、本発明の要旨を逸脱しない範囲の設計変更等も含まれる。
【図面の簡単な説明】
【００２４】
【図１】本発明の一実施形態に係る行動経路探索装置の概略構成を示したブロック図である。
【図２】本発明の一実施形態に係る行動経路探索装置が備える機能を展開して示した機能ブロック図である。
【図３】本発明の一実施形態に係る行動経路探索装置によって実行される処理の手順を示したフローチャートである。
【図４】解候補の一構成例を示した図である。
【図５】交叉について説明するための図である。
【図６】突然変異について説明するための図である。
【符号の説明】
【００２５】
１ ＣＰＵ
２ 主記憶装置
３ 補助記憶装置
４ 入力装置
５ 出力装置
１０ 行動経路探索装置
１１ 解候補生成部
１２ 評価部
１３ 選択部
１４ 遺伝的操作部
１５ 最適解決定部
【特許請求の範囲】
【請求項１】
計算機を備え、遺伝的アルゴリズムを用いて最適な行動経路を探索する行動経路探索装置であって、
前記計算機が、
複数の解候補を生成する解候補生成部と、
各前記解候補の適合評価を行う評価部と、
前記適合評価に基づいて前記解候補の選択を行う選択部と、
前記選択部によって選択された前記解候補に遺伝的操作を行うことにより次世代の解候補を作成する遺伝的操作部と
を備え、
前記解候補を構成する少なくとも１つの非終端記号には、動きを決定付けるパラメータが割り当てられている行動経路探索装置。
【請求項２】
前記動きを決定付けるパラメータが、変針または変速である請求項１に記載の行動経路探索装置。
【請求項３】
前記解候補を構成する少なくとも１つの非終端記号には、初期位置を設定するためのプログラムが割り当てられている請求項１または請求項２に記載の行動経路探索装置。
【請求項４】
計算機により遺伝的アルゴリズムを用いて最適な行動経路を探索する行動経路探索方法であって、
複数の解候補を生成する工程と、
各前記解候補の適合評価を行う工程と、
前記適合評価に基づいて前記解候補の選択を行う工程と、
選択された前記解候補に遺伝的操作を行うことにより次世代の解候補を作成する工程と
を含み、
前記解候補を構成する少なくとも１つの非終端記号には、動きを決定付けるパラメータが割り当てられている行動経路探索方法。
【請求項５】
遺伝的アルゴリズムを用いて最適な行動経路を探索するための処理をコンピュータに実行させるための行動経路探索プログラムであって、
複数の解候補を生成する処理と、
各前記解候補の適合評価を行う処理と、
前記適合評価に基づいて前記解候補の選択を行う処理と、
選択された前記解候補に遺伝的操作を行うことにより次世代の解候補を作成する処理と
を含み、
前記解候補を構成する少なくとも１つの非終端記号には、動きを決定付けるパラメータが割り当てられている行動経路探索プログラム。
【請求項１】
計算機を備え、遺伝的アルゴリズムを用いて最適な行動経路を探索する行動経路探索装置であって、
前記計算機が、
複数の解候補を生成する解候補生成部と、
各前記解候補の適合評価を行う評価部と、
前記適合評価に基づいて前記解候補の選択を行う選択部と、
前記選択部によって選択された前記解候補に遺伝的操作を行うことにより次世代の解候補を作成する遺伝的操作部と
を備え、
前記解候補を構成する少なくとも１つの非終端記号には、動きを決定付けるパラメータが割り当てられている行動経路探索装置。
【請求項２】
前記動きを決定付けるパラメータが、変針または変速である請求項１に記載の行動経路探索装置。
【請求項３】
前記解候補を構成する少なくとも１つの非終端記号には、初期位置を設定するためのプログラムが割り当てられている請求項１または請求項２に記載の行動経路探索装置。
【請求項４】
計算機により遺伝的アルゴリズムを用いて最適な行動経路を探索する行動経路探索方法であって、
複数の解候補を生成する工程と、
各前記解候補の適合評価を行う工程と、
前記適合評価に基づいて前記解候補の選択を行う工程と、
選択された前記解候補に遺伝的操作を行うことにより次世代の解候補を作成する工程と
を含み、
前記解候補を構成する少なくとも１つの非終端記号には、動きを決定付けるパラメータが割り当てられている行動経路探索方法。
【請求項５】
遺伝的アルゴリズムを用いて最適な行動経路を探索するための処理をコンピュータに実行させるための行動経路探索プログラムであって、
複数の解候補を生成する処理と、
各前記解候補の適合評価を行う処理と、
前記適合評価に基づいて前記解候補の選択を行う処理と、
選択された前記解候補に遺伝的操作を行うことにより次世代の解候補を作成する処理と
を含み、
前記解候補を構成する少なくとも１つの非終端記号には、動きを決定付けるパラメータが割り当てられている行動経路探索プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２００９−６９８６７（Ｐ２００９−６９８６７Ａ）
【公開日】平成２１年４月２日（２００９．４．２）
【国際特許分類】
【出願番号】特願２００７−２３４１３７（Ｐ２００７−２３４１３７）
【出願日】平成１９年９月１０日（２００７．９．１０）
【出願人】（０００００６２０８）三菱重工業株式会社 (10,378)
【公開日】平成２１年４月２日（２００９．４．２）
【国際特許分類】
【出願日】平成１９年９月１０日（２００７．９．１０）
【出願人】（０００００６２０８）三菱重工業株式会社 (10,378)
[ Back to top ]