情報処理装置、情報処理方法及びプログラム
【課題】 大規模かつ複雑な道路網であっても、遺伝的アルゴリズム（GA）を適用して現実解を得ることが可能な情報処理装置等を提案する。
【解決手段】 情報処理装置１において、個体内の遺伝子情報は、道路網における複数の交通経路における交通信号に対応する。情報処理装置１において、個体内では、複数の交通経路が多次元配列されている。情報処理装置１の遺伝子操作部７の遺伝子操作は、多次元配列を利用して、複数の遺伝子に対して行う。さらに、情報処理装置１の修正部９は、制約条件記憶部１９に記憶されたルールに従って、GAにおける遺伝子操作後の各個体の遺伝子情報を修正することにより、各個体が致死解になることを防ぐ。
【解決手段】 情報処理装置１において、個体内の遺伝子情報は、道路網における複数の交通経路における交通信号に対応する。情報処理装置１において、個体内では、複数の交通経路が多次元配列されている。情報処理装置１の遺伝子操作部７の遺伝子操作は、多次元配列を利用して、複数の遺伝子に対して行う。さらに、情報処理装置１の修正部９は、制約条件記憶部１９に記憶されたルールに従って、GAにおける遺伝子操作後の各個体の遺伝子情報を修正することにより、各個体が致死解になることを防ぐ。
【発明の詳細な説明】
【技術分野】
【０００１】
本願発明は、情報処理装置、情報処理方法及びプログラムに関し、特に、遺伝的アルゴリズムによって情報処理を行う情報処理装置等に関する。
【背景技術】
【０００２】
交通渋滞の慢性化は、環境や経済に対して深刻な影響を与える。交通信号は、最適化することによって、交通渋滞の緩和が期待される。交通信号の最適化は、困難な組合せ問題である。そのため、組合せ最適化アルゴリズムの１つである遺伝的アルゴリズム（GA）の適用が提案されている（非特許文献１〜２参照）。非特許文献１及び２では、GAを用いて、一条路（図８参照）のみの制御を行うことが記載されている。一条路とは、図８にあるように、流入口から流出口まで一本の道路でつながっており、その間に存在する交差点で交差する道路及びその交通条件は各々局所的に定義付けされたものである。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】高橋聖、外３名著，“遺伝的アルゴリズムによる交通流量の変動に適応した最適信号機オフセットの探索”，電学論Ｄ，Vol．123，No．3，pp．204-210，2003．
【非特許文献２】新川力、外３名著,“信号制御の最適化におけるメタ戦略の比較と制御パラメータの連続自動調整への適用”，山口大学工学部研究報告，vol.57，no.1，pp.21-24，2006.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、GAにおいて、個体内の遺伝子情報は、基本的に独立したものとしている。そのため、非特許文献１及び２にあるように、基本的に、交通信号の重複がない、一条路にしか適応できなかった。よって、大規模かつ複雑な道路網での制御には至っていない。
【０００５】
したがって、本願発明は、大規模かつ複雑な道路網であっても、GAを適用して現実解を得ることが可能な情報処理装置等を提案することを目的とする。
【課題を解決するための手段】
【０００６】
本願発明の第１の観点は、遺伝的アルゴリズムによって交通信号の複数の制御パラメータを求める情報処理装置であって、個体内の複数の遺伝子情報は、それぞれ、交通信号の複数の制御パラメータを含み、前記個体内の少なくとも２つの遺伝子情報に対して、前記複数の制御パラメータの一部又は全部を同一にするという条件を含む制約条件を記憶する制約条件記憶手段と、複数の前記個体に対して遺伝子操作を行う遺伝子操作手段と、前記制約条件に従って、遺伝子操作後の前記各個体内の前記少なくとも２つの遺伝子情報について、前記複数の制御パラメータの一部又は全部を同じ値にする修正手段と、修正後の前記各個体を評価する評価手段を備えるものである。
【０００７】
本願発明の第２の観点は、第１の観点において、前記各遺伝子情報は、複数の一条路の交通経路における交通信号の一つに対応するものであり、前記複数のパラメータは、前記交通信号の第１種制御パラメータ及び第２種制御パラメータを含み、前記制約条件は、異なる交通経路における同じ交通信号に対応する複数の遺伝子情報に対して、前記第１種制御パラメータを同じ値とし、前記第２種制御パラメータを、同じ向きに対応する交通信号は同じ値とし、異なる向きに対応する交通信号は総和を一定の値以下とするという条件を含み、前記修正手段は、前記制約条件に従って、異なる交通経路における同じ交通信号に対応する複数の遺伝子情報に対して、前記第１種制御パラメータを同じ値にし、前記第２種制御パラメータを同じ値にし又は総和を一定の値以下とするものである。
【０００８】
本願発明の第３の観点は、第２の観点において、前記各個体は、前記各交通経路に応じた多次元配列であり、前記遺伝子操作手段は各次元に対して遺伝子操作を行うものである。
【０００９】
本願発明の第４の観点は、第１から第３のいずれかの観点において、前記各遺伝子情報は、複数の一条路の交通経路における交通信号の一つに対応するものであり、前記複数のパラメータは、前記交通信号の複数の制御パラメータを含み、前記制約条件は、同じ交通経路上の交通信号に対応する遺伝子情報に対して、前記複数の制御パラメータの一部又は全部を同じ値とするという条件を含むものである。
【００１０】
本願発明の第５の観点は、情報処理装置において、遺伝的アルゴリズムによって交通信号の複数の制御パラメータを求める情報処理方法であって、複数の個体のそれぞれに含まれる複数の遺伝子情報は、それぞれ、交通信号の複数の制御パラメータを含み、遺伝子操作手段が、前記複数の個体に対して遺伝子操作を行う遺伝子操作ステップと、修正手段が、少なくとも２つの遺伝子情報に対して、前記複数の制御パラメータの一部又は全部を同一にするという条件を含む制約条件に従って、前記少なくとも２つの遺伝子情報について、前記複数の制御パラメータの一部又は全部を同じ値に修正する修正ステップと、評価手段が、修正後の前記各個体を評価する評価ステップを含むものである。
【００１１】
本願発明の第６の観点は、コンピュータにおいて、第５の観点の情報処理方法を実現するためのプログラムである。
【００１２】
なお、本願発明を、遺伝的アルゴリズムによって情報処理を行う情報処理装置であって、個体内の複数の遺伝子情報の制約条件を記憶する制約条件記憶手段と、複数の前記個体に対して遺伝子操作を行う遺伝子操作手段と、前記制約条件に従って、遺伝子操作後の前記各個体内の遺伝子情報の一部を修正する修正手段と、修正後の前記各個体を評価する評価手段を備えるものとして捉えてもよい。
【００１３】
また、本願発明を、第６の観点のプログラムを（定常的に）記録したコンピュータ読み取り可能な記録媒体としてとらえてもよい。
【発明の効果】
【００１４】
本願発明によれば、発明者らがGAを独自に深化させたマルチエレメントGAを用いて、複雑な交通網での交通信号の最適化を実現することが可能になる。すなわち、従来のGAでは、個体内の遺伝子情報は、基本的に独立していた。そのため、従来のGAは、交通信号の重複がない、一条路にしか適応できなかった。それに対し、マルチエレメントGAでは、遺伝子情報のルール付けを行うことにより、遺伝子間での不具合を解消して、致死解の発生をなくし、確実に現実解を導出することができる。そのため、広範囲かつ複雑な道路網への対応を図ることが可能になる。
【００１５】
さらに、本願発明は、交通信号の各種パラメータを最適化することによって、交通渋滞の緩和を実現することが可能になる。交通信号の制御パラメータとしては、例えば、サイクル時間、スプリット時間及びオフセットがある。サイクル時間は、「青，黄，赤」と一周の変化に関する時間である。スプリット時間は、信号の各現示に割り当てた通行許可時間である。オフセットは、隣接する信号との現示の切り替わるタイミングのズレである。本願発明によれば、すべての制御パラメータを最適化することにより、効率的に交通管理を行うことが可能になる。そして、例えば、情報の配信等によるものであれば、利益を得るのは、配信を受ける者のみになる。それに対し、本願発明は、既存の交通基盤である交通信号を利用していることから、全ての運転者に利益を生むことができる。さらに、大規模な範囲で、渋滞を緩和することが可能になる。
【００１６】
さらに、本願発明の第５の観点によれば、各次元を独立にして遺伝子操作を行うことにより、各交通経路を独立に、複数の遺伝子に対してGAの適用を行いつつ、個体内では致死解になることを避けることにより、より効率的に、パラメータの最適化を行うことができる。
【図面の簡単な説明】
【００１７】
【図１】本願発明の実施の形態の一例である情報処理装置の概略ブロック図である。
【図２】図１の情報処理装置１の動作の一例を示すフロー図である。
【図３】処理の対象となる道路網の一例を示す図である。
【図４】図３の道路網に対して遺伝子表現を行った個体の例を示す図である。
【図５】シミュレーションの対象となる交通網を示す図である。
【図６】（ａ）単純ルーレット選択と（ｂ）提案ルーレット選択について、世代数による評価値の推移を示す図である。
【図７】異なる目的関数を用いた場合のシミュレーション結果を示す図である。
【図８】交通信号の最適化において、従来のGAが適用されていた一条路の一例を示す図である。
【発明を実施するための形態】
【００１８】
以下では、図面を参照して、本願発明の実施例について説明する。なお、本願発明は、この実施例に限定されるものではない。
【実施例】
【００１９】
図１は、本願発明の実施の形態の一例である情報処理装置の概略ブロック図である。図２は、図１の情報処理装置１の動作の一例を示すフロー図である。図１及び図２を参照して、情報処理装置１の構成及び動作の一例について説明する。
【００２０】
情報処理装置１は、遺伝的アルゴリズム（GA）によって情報処理を行うものである。GAは、生物の進化過程から着想を得た確率的探索手法である。GAは、選択、交叉及び突然変異の３つの比較的単純な遺伝子操作から構成されているアルゴリズムであり、あらゆる最適化、探索問題に適用可能である。GAでは、遺伝子を持つ仮想的な個体の集団を計算機内に設定して、あらかじめ定めた環境に適応している個体が子孫を残す確率が高くなるよう世代交代のシミュレーションを実行し、遺伝子及び個体集団を「進化」させる。このように、GAは、適応度（環境に適合する度合）の高い個体を生成するように動作する。
【００２１】
一般的なGAの大きな特徴として、適応範囲の多様性が挙げられる。つまり、GAを適用することで解決できる問題の幅が広く、さらに、その問題に対する知識をあまり必要としない。このような利点から、GAは、多くの最適化問題に使用されてきた。しかし、その反面、ランダム性が強いことにより、制約条件の多い複雑な最適化問題においては、実現不可能な個体、すなわち、その問題が与える環境に適応できない個体が生成される可能性が考えられる。このような個体を致死解と呼ぶ。この致死解が同一世代数中の個体の多くを占めると、交叉対象の個体が少なくなる。
【００２２】
マルチエレメントGAは、発明者らが、GAでの致死解を出すという問題を解消し、複雑な最適化問題においても確実に世代交代を行い、現実解を導出するように、独自に開発したものである。このマルチエレメントGAは、次のような特徴を持つ。
【００２３】
まず、個体表現の多次元配列化である。従来のGAでは、１つの要素に対してのみ遺伝子操作を行うのが基本である。しかし、個体表現を多次元配列化することで、より複雑な問題に対してGAが適応可能になるという利点が生まれる。
【００２４】
次に、個体内の遺伝子情報へのルールの付与である。従来のGAでは、個体内の遺伝子情報は、基本的に独立している。「個体内で同一遺伝子の出現を禁止する」程度のルール付けをしているものは多く存在するが、「ある遺伝子がxならば、別の遺伝子はyでなければならない。」という、明確なルール付けをしているGAは存在しない。遺伝子情報のルール付けを行うことにより、遺伝子間での不具合を解消し、致死解の発生をなくし、確実に現実解を導出することができるという利点が生まれる。
【００２５】
このような特徴を持つマルチエレメントGAを用いることで、従来は一条路にしか適応できなかったGAを、広範囲かつ複雑な道路網へ適用することが可能になる。
【００２６】
具体的には、本実施例では、交通信号の制御パラメータ（サイクル時間、スプリット時間及びオフセット）（本願請求項の「制御パラメータ」の一例）を、広範囲かつ複雑な道路網において最適化する。本実施例では、すべての制御パラメータを最適化することにより、より効率的に交通管理を行う。このように、複数の制御パラメータを対象にしたり、制御対象道路網を拡大したりして、複数の要素が関係する複雑な最適化問題を解く場合、従来のGAを単純に拡張したときは、以下のような状況が発生する。すなわち、２本の道路が交差する交差点内において、交通信号のペア（ある方向と別の方向の交通信号）はそれぞれ逆の現示を示す。また、従来のGAでは、交叉や突然変異等の個体の遺伝子操作において、遺伝子間の連携が取れず、致死解が発生する。
【００２７】
そこで、これらの対策として、以下のルールを適用する。最適化を行う道路網において、ユーザ自身で流入口と流出口が１組の一条路を複数個決め、その数で個体を細分化する（多次元的表現）（ルール１）。２つ以上の道路が交差する交差点において、サイクル時間を同一にし（ルール２−１）、スプリット割合（％）の合計を１００にする（ルール２−２）（ルール２−１及び２−２を併せてルール２という。ルール２が、本願請求項の「制約条件」の一例である。）。これらのルール付けによって、交通信号制御に対応するマルチエレメントGAを構築する。ルール１より、複雑な最適化問題においても、より容易に現実解を求めることができる。さらに、それぞれの交通信号にルール２を適用することにより、個体が致死解となることを防ぐ。これらのルールは、制約条件記憶部１９に記憶されている。
【００２８】
図１の情報処理装置１は、初期化部３と、評価部５（本願請求項の「評価手段」の一例）と、遺伝子操作部７（本願請求項の「遺伝子操作手段」の一例）と、修正部９（本願請求項の「修正手段」の一例）と、制御部１１と、連結部１３と、シミュレーション部１５と、個体集合記憶部１７と、制約条件記憶部１９（本願請求項の「制約条件記憶手段」の一例）を備える。遺伝子操作部７は、選択部２１と、交叉・突然変異部２３を備える。
【００２９】
個体集合記憶部１７は、GAの処理対象となる個体の集合を記憶する。制約条件記憶部１９は、個体内の複数の遺伝子情報に関する制約条件を記憶する。図３及び図４を参照して、個体及び制約条件の具体例について説明する。
【００３０】
図３は、処理の対象となる道路網を示す。図４は、遺伝子表現を行った個体の例を示す。図３の道路網において、ルール１を適応し、ユーザ定義の一条路（図３の幹線）をｎ本決める。図４（ａ）に示すように、それぞれの一条路によって個体を細分化する。ここで、信号No.４と４’のように、’が付いて表現されている遺伝子が、それぞれの交差点における交通信号のペアを示す。
【００３１】
図１の初期化部３は、図４（ａ）のそれぞれの交通信号にルール２を適応して、初期の個体集合を生成し、個体集合記憶部１７に記憶する（図２のステップＳＴ１）。例えば、図４（ｂ）にあるように、信号４’、５’及び１２’について、それぞれ、信号４、５及び１２のオフセット及びサイクル時間を一致させる。そして、信号４’、５’及び１２’のスプリット割合を、１００から信号４、５及び１２のスプリット割合を引いた値とする（オフセット及びサイクル時間の制御パラメータが、本願請求項の「第１種制御パラメータ」の一例であり、スプリット割合が、本願請求項の「第２種制御パラメータ」の一例である。）。これにより、個体が致死解となることを防ぐことができる。なお、図３の信号５のように、交差点において、処理の対象となっていない方向に道路が存在するときは、信号５と５’のペアは、スプリット割合を１００未満にするようにしてもよい。
【００３２】
図１の評価部５は、個体集合記憶部１７に記憶された各個体を評価する（図２のステップＳＴ２）。評価部５とシミュレーション部１５は、連結部１３（ＡＰＩ部）で接続されている。シミュレーション部１５は、交通流シミュレータにより、交通流を実現する。評価部５は、シミュレーション部１５に対して、各個体について、交通流を実現させ、目的関数を用いて、各個体を評価する。その一例について、具体的に説明する。
【００３３】
シミュレーション部１５は、例えば、高機能交通シミュレータAimsun6により実現されている。シミュレーション部１５は、Aimsun6内で作成した交通網に対して、GAで生成された個体情報を割り当てることにより、実際の交通網に則したシミュレーションを行う。評価部５は、シミュレーション結果を取り込み、適応度を計算する。評価部５は、適応度を計算するために、まず、式(1)で示す単純な目的関数である車両通過割合（Fitness）を採用しているが、他の目的関数を採用してもよい。ここで、Ｖre（車両残留量）は、道路網に残留した車両数である。Ｖout（車両流出量）は、道路網を脱出した車両数である。Ｖwaitout（待機車両数）は、流入待ち車両数である。これらは、シミュレーション終了時の値とする。式(1)は、道路網を脱出した車両台数を比率にしたものである。このような単純な目的関数を使用することにより、視覚的に結果が分かりやすくなるという利点がある。この値が高いものほどよい解である。このようにして、個体ごとに適応度を導出する。
【００３４】
【数１】
【００３５】
図１の制御部１１は、規定の世代数を処理したか否かを判断する（図２のステップＳＴ３）。GAは明確な終了の基準を持たないアルゴリズムである。そのため、ユーザが、評価値の収束状況を見極めて、終了世代を決定する必要がある。ここでは、予備実験から、例えば、１世代を100個体とし，100世代を終了判定とする。
【００３６】
図１の遺伝子操作部７は、個体集合記憶部１７に記憶された複数の個体に対して遺伝子操作を行う。具体的には、図１の選択部２１は、評価部５の評価に基づいて、個体集合記憶部１７に記憶された複数の個体の一部を選択する（図２のステップＳＴ４）。図１の交叉・突然変異部２３は、選択された個体内の遺伝子情報を交換して交叉を行い、及び／又は、選択された個体内の遺伝子情報を変更して突然変異させる（図２のステップＳＴ５）。
【００３７】
選択部２１による処理について、具体的に説明する。選択とは、次世代に引き継ぐ個体や、交叉、突然変異等の遺伝子操作を行う個体を選び出すプロセスである。本実施例では、適応度として、まず、式(1)という単純な目的関数を用いる。単純化によって、適応度にあまり差が出ないという欠点が生じる。そこで、本実施例では、以下の選択を行う。まず、個体を適応度の小さい順に１，２，・・・，ｋ，・・・，Ｎのようにランク付けする。次に、各個体につけられたランクｋをｋ’＝ｋ2となるようにべき乗スケーリングを行う。スケーリングされたｋ’の割合によって、ルーレット盤の大きさを決定し、ルーレット選択を行う。このように、ランク付けとスケーリングによって、密集した適応度においても選択される個体に明確な差が出るようにする。さらに、ルーレット選択の特性を活かすことによって、全ての個体に次世代への生存の可能性を残す。
【００３８】
交叉・突然変異部２３による処理について、具体的に説明する。選択部２１により選ばれた個体に対して、交叉及び／又は突然変異といった遺伝子操作を行い、次世代の個体を作成する。本実施例では、交叉法には、最も簡単な方法である１点交叉法を用いる。突然変異法には、突然変異率によって選ばれた遺伝子をランダムに変異させる方法を用いる。また，その際の交叉率や突然変異率は、一般的な値を使用する。
【００３９】
図１の修正部９は、遺伝子操作後の各個体に対して、制約条件記憶部１９に記憶されたルール２を適応することにより、個体内の遺伝子情報の一部を修正する（図２のステップＳＴ６）。具体的には、初期化部３の動作として、図４（ｂ）により説明したものと同様である。そして、図２のステップＳＴ２の処理に戻る。
【００４０】
なお、図４は、交通信号のペアは、交差点の異なる方向が生ずる例である。しかし、異なる一条路において、同じ方向の交通信号が現れてもよい。この場合、制御パラメータの全部を同じ値というルール２を設定し、修正部９により修正するようにしてもよい。また、ルール２として、例えば、同じ交通経路上の交通信号のサイクル時間を一定にするようにしてもよい。
【００４１】
続いて、本実施例において、マルチエレメントGAが現実解で収束し、期待どおりの動作をしているかを、理論的最適解とシミュレーション結果を比較して確認する。ここでは、図５にあるように、結果を予測できるようなシンプルな交通網を作成する。すなわち、道路構造として、道路Ａ及びＢと道路α及びβとが直交し、道路長は、車両流入口から交差点の流入口、交差点間、交差点流出口から車両流出口までの長さは全て同じ（200m）とする。各道路において、記号「’」を付すことにより、反対方向を示すものとする。車両数は、道路α及びＡが900台/h、道路βが300台/h、道路Ｂが100台/h、道路α’、β’、Ａ’及びＢ’については０台/hとする。表１は、シミュレーション条件を示す。
【００４２】
【表１】
【００４３】
図６は、（ａ）単純ルーレット選択と（ｂ）提案ルーレット選択について、世代数による評価値の推移を示す図である。（ａ）では、平均値及び最小値は上昇しているものの、最大値が減少している。それに対し、（ｂ）では、最小値は変動しているものの、平均値及び最大値は、ほぼ増加している。そのため、（ｂ）提案ルーレット選択により、各世代の現実解を確実に次世代に継承し、世代間の進化を促しているといえる。これは、各個体をランク付けしてスケーリングして、似たような適応度が密集している場合においても、適応度の差を明確にすることで、適応度上位の個体が選ばれる確率が上昇したためだと考えられる。また、各世代の分散より、最終世代に向かって適応度が収束しており、本実施例は期待どおりの動作をしているといえる。
【００４４】
表２は、各流入口からの車両の流入量、車両の加速度、制限速度、速度許容値（速度許容値とは、実世界で制限速度が定められている道路において制限速度を超えて走行する車両を考慮して、制限速度から定数倍の速度で走行するような車両を交通網内で発生させるようなパラメータである。）、減加速度や、交通工学研究会が提供する計算式などから算出した理論値を示す。表３は、シミュレーションにより得られた制御パラメータの現実解を示す。表２と表３を比較すると、理論的最適解と本実施例の現実解がある程度近く、本実施例の有効性を示している。
【００４５】
【表２】
【００４６】
【表３】
【００４７】
複雑かつ広域な道路網による交通信号制御を実現するには、適切な目的関数を選択することが必要である。式(1)の目的関数は、初期収束にならずに収束しており（図６参照）、本実施例は、正しい挙動を示していることが分かる。しかし、式(1)の目的関数は、シミュレーション終了時点における車両台数のみしか考慮していない。そのため、どのような交通パラメータであっても、比較的良い結果を出力してしまうという欠点が存在する。
【００４８】
そこで、以下では、この問題を解決するために、適応度に幅が出て、さらに、シミュレーション中も考慮できるような速度や時間を単位に持つ物理量などを考慮した目的関数を用いた例について説明する。具体的には、式(2)により表されるものである。ここで、ＶSは、シミュレーション評価であり、ＶEは、感情評価である。目的関数Ｖから導出された適応度は、通常とは異なり、低い値の方が、環境に適応する度合いが高い優れた評価であるとする。
【００４９】
シミュレーション評価での目的関数ＶSでは、Delay Timeを採用している。Delay Timeとは、車両が理想的な状況下で走行し交通網を通過した場合にかかる走行時間と実際の走行にかかった時間との差の時間である。その理由は、オフセットにより交差点前で停止せずともブレーキを踏んだことによる遅延時間を考慮できること、車両通過割合と異なりシミュレーション中により得られるデータであること、シミュレーション結果において、各制御パラメータの変化に大きな差を出していること、などである。Delay Timeの変化する値の範囲は、車両長や流入量などにより大きく変化する。そのため、範囲を定数で調整できるようにする。また、シミュレーション結果より、オフセットにおいて最大値と最小値の比率は1.3倍程度であった。そのため、より適応度に幅を持たせるため、式(3)にあるように、指数関数を用いる。ここで、ｔDelayは、Delay Time(s)であり、Ｃは定数である。Ｃは、Ｃ=50とすることにより、Delay Timeの比率が最低でも２倍以上になるように設定する。
【００５０】
また、サイクルが大きな値をとれば、交差点需要率も高くなり、Delay Timeは低く、一定値に安定する。よって、交通条件だけを考慮して現実解を見つけるのであれば、サイクルを大きくすればよいということになる。そのため、Delay Timeが低い一定の値になると、類似する個体が多く存在してしまい、唯一の解を与えなくなってしまう。したがって、無制限にサイクルが大きくならないように、悪い評価を出す必要がある。この場合には、赤現示による待ち時間も長くなり、青現示待ちをしている運転者に精神的な負担が生じる。そこで、感情評価での目的関数ＶEとして、サイクルが長くなると悪い評価を与えるような、感情を含めた項を導入している。運転者の感情としては、赤現示による停車時間が短い場合における停車時間の増加はそれほど精神的に負担を伴わない。しかし、停車時間が長い（サイクルが大きい）場合には、停車時間が短い場合と同じ停車時間の増加幅であっても、運転者の精神的負担は増大する。そのため、感情評価ＶEは、式(4)にあるように、サイクルが長くなるほどに大きな値となるような指数関数を用いる。ここで、Ｃa及びＣbは、定数であり、感情評価を調整する。サイクルは、40秒を最小として変化しており、感情評価において最小が１となるようにするためにＣa=40とする。また、サイクルは70秒や140秒を採用する交通信号が多いので、ここで２倍程度の差が出るように、Ｃb=100とする。
【００５１】
【数２】
【００５２】
図７は、目的関数として式(2)を用いたシミュレーション結果を示す。図７は、各世代での適応度の最小、最大及び平均を示す。図７より、正しく収束していることが確認でき、正しい挙動を示している。また、目的関数として式(2)を用いた場合、最適サイクルを一意に導出することができた。さらに、理論的最適解を示す制御パラメータにおいて、式(2)の目的関数により適応度を計算すると、適応度は4.572223となった。一方、式(2)を用いたシミュレーションにより得られた現実解での適応度は、4.572225であった。これより、式(2)で示した提案目的関数は、有用であるといえる。
【符号の説明】
【００５３】
１ 情報処理装置、３ 初期化部、５ 評価部、７ 遺伝子操作部、９ 修正部、１１ 制御部、１３ 連結部、１５ シミュレーション部、１７ 個体集合記憶部、１９ 制約条件記憶部、２１ 選択部、２３ 交叉・突然変異部
【技術分野】
【０００１】
本願発明は、情報処理装置、情報処理方法及びプログラムに関し、特に、遺伝的アルゴリズムによって情報処理を行う情報処理装置等に関する。
【背景技術】
【０００２】
交通渋滞の慢性化は、環境や経済に対して深刻な影響を与える。交通信号は、最適化することによって、交通渋滞の緩和が期待される。交通信号の最適化は、困難な組合せ問題である。そのため、組合せ最適化アルゴリズムの１つである遺伝的アルゴリズム（GA）の適用が提案されている（非特許文献１〜２参照）。非特許文献１及び２では、GAを用いて、一条路（図８参照）のみの制御を行うことが記載されている。一条路とは、図８にあるように、流入口から流出口まで一本の道路でつながっており、その間に存在する交差点で交差する道路及びその交通条件は各々局所的に定義付けされたものである。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】高橋聖、外３名著，“遺伝的アルゴリズムによる交通流量の変動に適応した最適信号機オフセットの探索”，電学論Ｄ，Vol．123，No．3，pp．204-210，2003．
【非特許文献２】新川力、外３名著,“信号制御の最適化におけるメタ戦略の比較と制御パラメータの連続自動調整への適用”，山口大学工学部研究報告，vol.57，no.1，pp.21-24，2006.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、GAにおいて、個体内の遺伝子情報は、基本的に独立したものとしている。そのため、非特許文献１及び２にあるように、基本的に、交通信号の重複がない、一条路にしか適応できなかった。よって、大規模かつ複雑な道路網での制御には至っていない。
【０００５】
したがって、本願発明は、大規模かつ複雑な道路網であっても、GAを適用して現実解を得ることが可能な情報処理装置等を提案することを目的とする。
【課題を解決するための手段】
【０００６】
本願発明の第１の観点は、遺伝的アルゴリズムによって交通信号の複数の制御パラメータを求める情報処理装置であって、個体内の複数の遺伝子情報は、それぞれ、交通信号の複数の制御パラメータを含み、前記個体内の少なくとも２つの遺伝子情報に対して、前記複数の制御パラメータの一部又は全部を同一にするという条件を含む制約条件を記憶する制約条件記憶手段と、複数の前記個体に対して遺伝子操作を行う遺伝子操作手段と、前記制約条件に従って、遺伝子操作後の前記各個体内の前記少なくとも２つの遺伝子情報について、前記複数の制御パラメータの一部又は全部を同じ値にする修正手段と、修正後の前記各個体を評価する評価手段を備えるものである。
【０００７】
本願発明の第２の観点は、第１の観点において、前記各遺伝子情報は、複数の一条路の交通経路における交通信号の一つに対応するものであり、前記複数のパラメータは、前記交通信号の第１種制御パラメータ及び第２種制御パラメータを含み、前記制約条件は、異なる交通経路における同じ交通信号に対応する複数の遺伝子情報に対して、前記第１種制御パラメータを同じ値とし、前記第２種制御パラメータを、同じ向きに対応する交通信号は同じ値とし、異なる向きに対応する交通信号は総和を一定の値以下とするという条件を含み、前記修正手段は、前記制約条件に従って、異なる交通経路における同じ交通信号に対応する複数の遺伝子情報に対して、前記第１種制御パラメータを同じ値にし、前記第２種制御パラメータを同じ値にし又は総和を一定の値以下とするものである。
【０００８】
本願発明の第３の観点は、第２の観点において、前記各個体は、前記各交通経路に応じた多次元配列であり、前記遺伝子操作手段は各次元に対して遺伝子操作を行うものである。
【０００９】
本願発明の第４の観点は、第１から第３のいずれかの観点において、前記各遺伝子情報は、複数の一条路の交通経路における交通信号の一つに対応するものであり、前記複数のパラメータは、前記交通信号の複数の制御パラメータを含み、前記制約条件は、同じ交通経路上の交通信号に対応する遺伝子情報に対して、前記複数の制御パラメータの一部又は全部を同じ値とするという条件を含むものである。
【００１０】
本願発明の第５の観点は、情報処理装置において、遺伝的アルゴリズムによって交通信号の複数の制御パラメータを求める情報処理方法であって、複数の個体のそれぞれに含まれる複数の遺伝子情報は、それぞれ、交通信号の複数の制御パラメータを含み、遺伝子操作手段が、前記複数の個体に対して遺伝子操作を行う遺伝子操作ステップと、修正手段が、少なくとも２つの遺伝子情報に対して、前記複数の制御パラメータの一部又は全部を同一にするという条件を含む制約条件に従って、前記少なくとも２つの遺伝子情報について、前記複数の制御パラメータの一部又は全部を同じ値に修正する修正ステップと、評価手段が、修正後の前記各個体を評価する評価ステップを含むものである。
【００１１】
本願発明の第６の観点は、コンピュータにおいて、第５の観点の情報処理方法を実現するためのプログラムである。
【００１２】
なお、本願発明を、遺伝的アルゴリズムによって情報処理を行う情報処理装置であって、個体内の複数の遺伝子情報の制約条件を記憶する制約条件記憶手段と、複数の前記個体に対して遺伝子操作を行う遺伝子操作手段と、前記制約条件に従って、遺伝子操作後の前記各個体内の遺伝子情報の一部を修正する修正手段と、修正後の前記各個体を評価する評価手段を備えるものとして捉えてもよい。
【００１３】
また、本願発明を、第６の観点のプログラムを（定常的に）記録したコンピュータ読み取り可能な記録媒体としてとらえてもよい。
【発明の効果】
【００１４】
本願発明によれば、発明者らがGAを独自に深化させたマルチエレメントGAを用いて、複雑な交通網での交通信号の最適化を実現することが可能になる。すなわち、従来のGAでは、個体内の遺伝子情報は、基本的に独立していた。そのため、従来のGAは、交通信号の重複がない、一条路にしか適応できなかった。それに対し、マルチエレメントGAでは、遺伝子情報のルール付けを行うことにより、遺伝子間での不具合を解消して、致死解の発生をなくし、確実に現実解を導出することができる。そのため、広範囲かつ複雑な道路網への対応を図ることが可能になる。
【００１５】
さらに、本願発明は、交通信号の各種パラメータを最適化することによって、交通渋滞の緩和を実現することが可能になる。交通信号の制御パラメータとしては、例えば、サイクル時間、スプリット時間及びオフセットがある。サイクル時間は、「青，黄，赤」と一周の変化に関する時間である。スプリット時間は、信号の各現示に割り当てた通行許可時間である。オフセットは、隣接する信号との現示の切り替わるタイミングのズレである。本願発明によれば、すべての制御パラメータを最適化することにより、効率的に交通管理を行うことが可能になる。そして、例えば、情報の配信等によるものであれば、利益を得るのは、配信を受ける者のみになる。それに対し、本願発明は、既存の交通基盤である交通信号を利用していることから、全ての運転者に利益を生むことができる。さらに、大規模な範囲で、渋滞を緩和することが可能になる。
【００１６】
さらに、本願発明の第５の観点によれば、各次元を独立にして遺伝子操作を行うことにより、各交通経路を独立に、複数の遺伝子に対してGAの適用を行いつつ、個体内では致死解になることを避けることにより、より効率的に、パラメータの最適化を行うことができる。
【図面の簡単な説明】
【００１７】
【図１】本願発明の実施の形態の一例である情報処理装置の概略ブロック図である。
【図２】図１の情報処理装置１の動作の一例を示すフロー図である。
【図３】処理の対象となる道路網の一例を示す図である。
【図４】図３の道路網に対して遺伝子表現を行った個体の例を示す図である。
【図５】シミュレーションの対象となる交通網を示す図である。
【図６】（ａ）単純ルーレット選択と（ｂ）提案ルーレット選択について、世代数による評価値の推移を示す図である。
【図７】異なる目的関数を用いた場合のシミュレーション結果を示す図である。
【図８】交通信号の最適化において、従来のGAが適用されていた一条路の一例を示す図である。
【発明を実施するための形態】
【００１８】
以下では、図面を参照して、本願発明の実施例について説明する。なお、本願発明は、この実施例に限定されるものではない。
【実施例】
【００１９】
図１は、本願発明の実施の形態の一例である情報処理装置の概略ブロック図である。図２は、図１の情報処理装置１の動作の一例を示すフロー図である。図１及び図２を参照して、情報処理装置１の構成及び動作の一例について説明する。
【００２０】
情報処理装置１は、遺伝的アルゴリズム（GA）によって情報処理を行うものである。GAは、生物の進化過程から着想を得た確率的探索手法である。GAは、選択、交叉及び突然変異の３つの比較的単純な遺伝子操作から構成されているアルゴリズムであり、あらゆる最適化、探索問題に適用可能である。GAでは、遺伝子を持つ仮想的な個体の集団を計算機内に設定して、あらかじめ定めた環境に適応している個体が子孫を残す確率が高くなるよう世代交代のシミュレーションを実行し、遺伝子及び個体集団を「進化」させる。このように、GAは、適応度（環境に適合する度合）の高い個体を生成するように動作する。
【００２１】
一般的なGAの大きな特徴として、適応範囲の多様性が挙げられる。つまり、GAを適用することで解決できる問題の幅が広く、さらに、その問題に対する知識をあまり必要としない。このような利点から、GAは、多くの最適化問題に使用されてきた。しかし、その反面、ランダム性が強いことにより、制約条件の多い複雑な最適化問題においては、実現不可能な個体、すなわち、その問題が与える環境に適応できない個体が生成される可能性が考えられる。このような個体を致死解と呼ぶ。この致死解が同一世代数中の個体の多くを占めると、交叉対象の個体が少なくなる。
【００２２】
マルチエレメントGAは、発明者らが、GAでの致死解を出すという問題を解消し、複雑な最適化問題においても確実に世代交代を行い、現実解を導出するように、独自に開発したものである。このマルチエレメントGAは、次のような特徴を持つ。
【００２３】
まず、個体表現の多次元配列化である。従来のGAでは、１つの要素に対してのみ遺伝子操作を行うのが基本である。しかし、個体表現を多次元配列化することで、より複雑な問題に対してGAが適応可能になるという利点が生まれる。
【００２４】
次に、個体内の遺伝子情報へのルールの付与である。従来のGAでは、個体内の遺伝子情報は、基本的に独立している。「個体内で同一遺伝子の出現を禁止する」程度のルール付けをしているものは多く存在するが、「ある遺伝子がxならば、別の遺伝子はyでなければならない。」という、明確なルール付けをしているGAは存在しない。遺伝子情報のルール付けを行うことにより、遺伝子間での不具合を解消し、致死解の発生をなくし、確実に現実解を導出することができるという利点が生まれる。
【００２５】
このような特徴を持つマルチエレメントGAを用いることで、従来は一条路にしか適応できなかったGAを、広範囲かつ複雑な道路網へ適用することが可能になる。
【００２６】
具体的には、本実施例では、交通信号の制御パラメータ（サイクル時間、スプリット時間及びオフセット）（本願請求項の「制御パラメータ」の一例）を、広範囲かつ複雑な道路網において最適化する。本実施例では、すべての制御パラメータを最適化することにより、より効率的に交通管理を行う。このように、複数の制御パラメータを対象にしたり、制御対象道路網を拡大したりして、複数の要素が関係する複雑な最適化問題を解く場合、従来のGAを単純に拡張したときは、以下のような状況が発生する。すなわち、２本の道路が交差する交差点内において、交通信号のペア（ある方向と別の方向の交通信号）はそれぞれ逆の現示を示す。また、従来のGAでは、交叉や突然変異等の個体の遺伝子操作において、遺伝子間の連携が取れず、致死解が発生する。
【００２７】
そこで、これらの対策として、以下のルールを適用する。最適化を行う道路網において、ユーザ自身で流入口と流出口が１組の一条路を複数個決め、その数で個体を細分化する（多次元的表現）（ルール１）。２つ以上の道路が交差する交差点において、サイクル時間を同一にし（ルール２−１）、スプリット割合（％）の合計を１００にする（ルール２−２）（ルール２−１及び２−２を併せてルール２という。ルール２が、本願請求項の「制約条件」の一例である。）。これらのルール付けによって、交通信号制御に対応するマルチエレメントGAを構築する。ルール１より、複雑な最適化問題においても、より容易に現実解を求めることができる。さらに、それぞれの交通信号にルール２を適用することにより、個体が致死解となることを防ぐ。これらのルールは、制約条件記憶部１９に記憶されている。
【００２８】
図１の情報処理装置１は、初期化部３と、評価部５（本願請求項の「評価手段」の一例）と、遺伝子操作部７（本願請求項の「遺伝子操作手段」の一例）と、修正部９（本願請求項の「修正手段」の一例）と、制御部１１と、連結部１３と、シミュレーション部１５と、個体集合記憶部１７と、制約条件記憶部１９（本願請求項の「制約条件記憶手段」の一例）を備える。遺伝子操作部７は、選択部２１と、交叉・突然変異部２３を備える。
【００２９】
個体集合記憶部１７は、GAの処理対象となる個体の集合を記憶する。制約条件記憶部１９は、個体内の複数の遺伝子情報に関する制約条件を記憶する。図３及び図４を参照して、個体及び制約条件の具体例について説明する。
【００３０】
図３は、処理の対象となる道路網を示す。図４は、遺伝子表現を行った個体の例を示す。図３の道路網において、ルール１を適応し、ユーザ定義の一条路（図３の幹線）をｎ本決める。図４（ａ）に示すように、それぞれの一条路によって個体を細分化する。ここで、信号No.４と４’のように、’が付いて表現されている遺伝子が、それぞれの交差点における交通信号のペアを示す。
【００３１】
図１の初期化部３は、図４（ａ）のそれぞれの交通信号にルール２を適応して、初期の個体集合を生成し、個体集合記憶部１７に記憶する（図２のステップＳＴ１）。例えば、図４（ｂ）にあるように、信号４’、５’及び１２’について、それぞれ、信号４、５及び１２のオフセット及びサイクル時間を一致させる。そして、信号４’、５’及び１２’のスプリット割合を、１００から信号４、５及び１２のスプリット割合を引いた値とする（オフセット及びサイクル時間の制御パラメータが、本願請求項の「第１種制御パラメータ」の一例であり、スプリット割合が、本願請求項の「第２種制御パラメータ」の一例である。）。これにより、個体が致死解となることを防ぐことができる。なお、図３の信号５のように、交差点において、処理の対象となっていない方向に道路が存在するときは、信号５と５’のペアは、スプリット割合を１００未満にするようにしてもよい。
【００３２】
図１の評価部５は、個体集合記憶部１７に記憶された各個体を評価する（図２のステップＳＴ２）。評価部５とシミュレーション部１５は、連結部１３（ＡＰＩ部）で接続されている。シミュレーション部１５は、交通流シミュレータにより、交通流を実現する。評価部５は、シミュレーション部１５に対して、各個体について、交通流を実現させ、目的関数を用いて、各個体を評価する。その一例について、具体的に説明する。
【００３３】
シミュレーション部１５は、例えば、高機能交通シミュレータAimsun6により実現されている。シミュレーション部１５は、Aimsun6内で作成した交通網に対して、GAで生成された個体情報を割り当てることにより、実際の交通網に則したシミュレーションを行う。評価部５は、シミュレーション結果を取り込み、適応度を計算する。評価部５は、適応度を計算するために、まず、式(1)で示す単純な目的関数である車両通過割合（Fitness）を採用しているが、他の目的関数を採用してもよい。ここで、Ｖre（車両残留量）は、道路網に残留した車両数である。Ｖout（車両流出量）は、道路網を脱出した車両数である。Ｖwaitout（待機車両数）は、流入待ち車両数である。これらは、シミュレーション終了時の値とする。式(1)は、道路網を脱出した車両台数を比率にしたものである。このような単純な目的関数を使用することにより、視覚的に結果が分かりやすくなるという利点がある。この値が高いものほどよい解である。このようにして、個体ごとに適応度を導出する。
【００３４】
【数１】
【００３５】
図１の制御部１１は、規定の世代数を処理したか否かを判断する（図２のステップＳＴ３）。GAは明確な終了の基準を持たないアルゴリズムである。そのため、ユーザが、評価値の収束状況を見極めて、終了世代を決定する必要がある。ここでは、予備実験から、例えば、１世代を100個体とし，100世代を終了判定とする。
【００３６】
図１の遺伝子操作部７は、個体集合記憶部１７に記憶された複数の個体に対して遺伝子操作を行う。具体的には、図１の選択部２１は、評価部５の評価に基づいて、個体集合記憶部１７に記憶された複数の個体の一部を選択する（図２のステップＳＴ４）。図１の交叉・突然変異部２３は、選択された個体内の遺伝子情報を交換して交叉を行い、及び／又は、選択された個体内の遺伝子情報を変更して突然変異させる（図２のステップＳＴ５）。
【００３７】
選択部２１による処理について、具体的に説明する。選択とは、次世代に引き継ぐ個体や、交叉、突然変異等の遺伝子操作を行う個体を選び出すプロセスである。本実施例では、適応度として、まず、式(1)という単純な目的関数を用いる。単純化によって、適応度にあまり差が出ないという欠点が生じる。そこで、本実施例では、以下の選択を行う。まず、個体を適応度の小さい順に１，２，・・・，ｋ，・・・，Ｎのようにランク付けする。次に、各個体につけられたランクｋをｋ’＝ｋ2となるようにべき乗スケーリングを行う。スケーリングされたｋ’の割合によって、ルーレット盤の大きさを決定し、ルーレット選択を行う。このように、ランク付けとスケーリングによって、密集した適応度においても選択される個体に明確な差が出るようにする。さらに、ルーレット選択の特性を活かすことによって、全ての個体に次世代への生存の可能性を残す。
【００３８】
交叉・突然変異部２３による処理について、具体的に説明する。選択部２１により選ばれた個体に対して、交叉及び／又は突然変異といった遺伝子操作を行い、次世代の個体を作成する。本実施例では、交叉法には、最も簡単な方法である１点交叉法を用いる。突然変異法には、突然変異率によって選ばれた遺伝子をランダムに変異させる方法を用いる。また，その際の交叉率や突然変異率は、一般的な値を使用する。
【００３９】
図１の修正部９は、遺伝子操作後の各個体に対して、制約条件記憶部１９に記憶されたルール２を適応することにより、個体内の遺伝子情報の一部を修正する（図２のステップＳＴ６）。具体的には、初期化部３の動作として、図４（ｂ）により説明したものと同様である。そして、図２のステップＳＴ２の処理に戻る。
【００４０】
なお、図４は、交通信号のペアは、交差点の異なる方向が生ずる例である。しかし、異なる一条路において、同じ方向の交通信号が現れてもよい。この場合、制御パラメータの全部を同じ値というルール２を設定し、修正部９により修正するようにしてもよい。また、ルール２として、例えば、同じ交通経路上の交通信号のサイクル時間を一定にするようにしてもよい。
【００４１】
続いて、本実施例において、マルチエレメントGAが現実解で収束し、期待どおりの動作をしているかを、理論的最適解とシミュレーション結果を比較して確認する。ここでは、図５にあるように、結果を予測できるようなシンプルな交通網を作成する。すなわち、道路構造として、道路Ａ及びＢと道路α及びβとが直交し、道路長は、車両流入口から交差点の流入口、交差点間、交差点流出口から車両流出口までの長さは全て同じ（200m）とする。各道路において、記号「’」を付すことにより、反対方向を示すものとする。車両数は、道路α及びＡが900台/h、道路βが300台/h、道路Ｂが100台/h、道路α’、β’、Ａ’及びＢ’については０台/hとする。表１は、シミュレーション条件を示す。
【００４２】
【表１】
【００４３】
図６は、（ａ）単純ルーレット選択と（ｂ）提案ルーレット選択について、世代数による評価値の推移を示す図である。（ａ）では、平均値及び最小値は上昇しているものの、最大値が減少している。それに対し、（ｂ）では、最小値は変動しているものの、平均値及び最大値は、ほぼ増加している。そのため、（ｂ）提案ルーレット選択により、各世代の現実解を確実に次世代に継承し、世代間の進化を促しているといえる。これは、各個体をランク付けしてスケーリングして、似たような適応度が密集している場合においても、適応度の差を明確にすることで、適応度上位の個体が選ばれる確率が上昇したためだと考えられる。また、各世代の分散より、最終世代に向かって適応度が収束しており、本実施例は期待どおりの動作をしているといえる。
【００４４】
表２は、各流入口からの車両の流入量、車両の加速度、制限速度、速度許容値（速度許容値とは、実世界で制限速度が定められている道路において制限速度を超えて走行する車両を考慮して、制限速度から定数倍の速度で走行するような車両を交通網内で発生させるようなパラメータである。）、減加速度や、交通工学研究会が提供する計算式などから算出した理論値を示す。表３は、シミュレーションにより得られた制御パラメータの現実解を示す。表２と表３を比較すると、理論的最適解と本実施例の現実解がある程度近く、本実施例の有効性を示している。
【００４５】
【表２】
【００４６】
【表３】
【００４７】
複雑かつ広域な道路網による交通信号制御を実現するには、適切な目的関数を選択することが必要である。式(1)の目的関数は、初期収束にならずに収束しており（図６参照）、本実施例は、正しい挙動を示していることが分かる。しかし、式(1)の目的関数は、シミュレーション終了時点における車両台数のみしか考慮していない。そのため、どのような交通パラメータであっても、比較的良い結果を出力してしまうという欠点が存在する。
【００４８】
そこで、以下では、この問題を解決するために、適応度に幅が出て、さらに、シミュレーション中も考慮できるような速度や時間を単位に持つ物理量などを考慮した目的関数を用いた例について説明する。具体的には、式(2)により表されるものである。ここで、ＶSは、シミュレーション評価であり、ＶEは、感情評価である。目的関数Ｖから導出された適応度は、通常とは異なり、低い値の方が、環境に適応する度合いが高い優れた評価であるとする。
【００４９】
シミュレーション評価での目的関数ＶSでは、Delay Timeを採用している。Delay Timeとは、車両が理想的な状況下で走行し交通網を通過した場合にかかる走行時間と実際の走行にかかった時間との差の時間である。その理由は、オフセットにより交差点前で停止せずともブレーキを踏んだことによる遅延時間を考慮できること、車両通過割合と異なりシミュレーション中により得られるデータであること、シミュレーション結果において、各制御パラメータの変化に大きな差を出していること、などである。Delay Timeの変化する値の範囲は、車両長や流入量などにより大きく変化する。そのため、範囲を定数で調整できるようにする。また、シミュレーション結果より、オフセットにおいて最大値と最小値の比率は1.3倍程度であった。そのため、より適応度に幅を持たせるため、式(3)にあるように、指数関数を用いる。ここで、ｔDelayは、Delay Time(s)であり、Ｃは定数である。Ｃは、Ｃ=50とすることにより、Delay Timeの比率が最低でも２倍以上になるように設定する。
【００５０】
また、サイクルが大きな値をとれば、交差点需要率も高くなり、Delay Timeは低く、一定値に安定する。よって、交通条件だけを考慮して現実解を見つけるのであれば、サイクルを大きくすればよいということになる。そのため、Delay Timeが低い一定の値になると、類似する個体が多く存在してしまい、唯一の解を与えなくなってしまう。したがって、無制限にサイクルが大きくならないように、悪い評価を出す必要がある。この場合には、赤現示による待ち時間も長くなり、青現示待ちをしている運転者に精神的な負担が生じる。そこで、感情評価での目的関数ＶEとして、サイクルが長くなると悪い評価を与えるような、感情を含めた項を導入している。運転者の感情としては、赤現示による停車時間が短い場合における停車時間の増加はそれほど精神的に負担を伴わない。しかし、停車時間が長い（サイクルが大きい）場合には、停車時間が短い場合と同じ停車時間の増加幅であっても、運転者の精神的負担は増大する。そのため、感情評価ＶEは、式(4)にあるように、サイクルが長くなるほどに大きな値となるような指数関数を用いる。ここで、Ｃa及びＣbは、定数であり、感情評価を調整する。サイクルは、40秒を最小として変化しており、感情評価において最小が１となるようにするためにＣa=40とする。また、サイクルは70秒や140秒を採用する交通信号が多いので、ここで２倍程度の差が出るように、Ｃb=100とする。
【００５１】
【数２】
【００５２】
図７は、目的関数として式(2)を用いたシミュレーション結果を示す。図７は、各世代での適応度の最小、最大及び平均を示す。図７より、正しく収束していることが確認でき、正しい挙動を示している。また、目的関数として式(2)を用いた場合、最適サイクルを一意に導出することができた。さらに、理論的最適解を示す制御パラメータにおいて、式(2)の目的関数により適応度を計算すると、適応度は4.572223となった。一方、式(2)を用いたシミュレーションにより得られた現実解での適応度は、4.572225であった。これより、式(2)で示した提案目的関数は、有用であるといえる。
【符号の説明】
【００５３】
１ 情報処理装置、３ 初期化部、５ 評価部、７ 遺伝子操作部、９ 修正部、１１ 制御部、１３ 連結部、１５ シミュレーション部、１７ 個体集合記憶部、１９ 制約条件記憶部、２１ 選択部、２３ 交叉・突然変異部
【特許請求の範囲】
【請求項１】
遺伝的アルゴリズムによって交通信号の複数の制御パラメータを求める情報処理装置であって、
個体内の複数の遺伝子情報は、それぞれ、交通信号の複数の制御パラメータを含み、
前記個体内の少なくとも２つの遺伝子情報に対して、前記複数の制御パラメータの一部又は全部を同一にするという条件を含む制約条件を記憶する制約条件記憶手段と、
複数の前記個体に対して遺伝子操作を行う遺伝子操作手段と、
前記制約条件に従って、遺伝子操作後の前記各個体内の前記少なくとも２つの遺伝子情報について、前記複数の制御パラメータの一部又は全部を同じ値にする修正手段と、
修正後の前記各個体を評価する評価手段を備える情報処理装置。
【請求項２】
前記各遺伝子情報は、複数の一条路の交通経路における交通信号の一つに対応するものであり、
前記複数のパラメータは、前記交通信号の第１種制御パラメータ及び第２種制御パラメータを含み、
前記制約条件は、異なる交通経路における同じ交通信号に対応する複数の遺伝子情報に対して、
前記第１種制御パラメータを同じ値とし、
前記第２種制御パラメータを、同じ向きに対応する交通信号は同じ値とし、異なる向きに対応する交通信号は総和を一定の値以下とするという条件を含み、
前記修正手段は、前記制約条件に従って、異なる交通経路における同じ交通信号に対応する複数の遺伝子情報に対して、前記第１種制御パラメータを同じ値にし、前記第２種制御パラメータを同じ値にし又は総和を一定の値以下とする、請求項１記載の情報処理装置。
【請求項３】
前記各個体は、前記各交通経路に応じた多次元配列であり、
前記遺伝子操作手段は各次元に対して遺伝子操作を行う、請求項２記載の情報処理装置。
【請求項４】
前記各遺伝子情報は、複数の一条路の交通経路における交通信号の一つに対応するものであり、
前記複数のパラメータは、前記交通信号の複数の制御パラメータを含み、
前記制約条件は、同じ交通経路上の交通信号に対応する遺伝子情報に対して、前記複数の制御パラメータの一部又は全部を同じ値とするという条件を含む、請求項１から３のいずれかに記載の情報処理装置。
【請求項５】
情報処理装置において、遺伝的アルゴリズムによって交通信号の複数の制御パラメータを求める情報処理方法であって、
複数の個体のそれぞれに含まれる複数の遺伝子情報は、それぞれ、交通信号の複数の制御パラメータを含み、
遺伝子操作手段が、前記複数の個体に対して遺伝子操作を行う遺伝子操作ステップと、
修正手段が、少なくとも２つの遺伝子情報に対して、前記複数の制御パラメータの一部又は全部を同一にするという条件を含む制約条件に従って、前記少なくとも２つの遺伝子情報について、前記複数の制御パラメータの一部又は全部を同じ値に修正する修正ステップと、
評価手段が、修正後の前記各個体を評価する評価ステップを含む情報処理方法。
【請求項６】
コンピュータにおいて、請求項５記載の情報処理方法を実現するためのプログラム。
【請求項１】
遺伝的アルゴリズムによって交通信号の複数の制御パラメータを求める情報処理装置であって、
個体内の複数の遺伝子情報は、それぞれ、交通信号の複数の制御パラメータを含み、
前記個体内の少なくとも２つの遺伝子情報に対して、前記複数の制御パラメータの一部又は全部を同一にするという条件を含む制約条件を記憶する制約条件記憶手段と、
複数の前記個体に対して遺伝子操作を行う遺伝子操作手段と、
前記制約条件に従って、遺伝子操作後の前記各個体内の前記少なくとも２つの遺伝子情報について、前記複数の制御パラメータの一部又は全部を同じ値にする修正手段と、
修正後の前記各個体を評価する評価手段を備える情報処理装置。
【請求項２】
前記各遺伝子情報は、複数の一条路の交通経路における交通信号の一つに対応するものであり、
前記複数のパラメータは、前記交通信号の第１種制御パラメータ及び第２種制御パラメータを含み、
前記制約条件は、異なる交通経路における同じ交通信号に対応する複数の遺伝子情報に対して、
前記第１種制御パラメータを同じ値とし、
前記第２種制御パラメータを、同じ向きに対応する交通信号は同じ値とし、異なる向きに対応する交通信号は総和を一定の値以下とするという条件を含み、
前記修正手段は、前記制約条件に従って、異なる交通経路における同じ交通信号に対応する複数の遺伝子情報に対して、前記第１種制御パラメータを同じ値にし、前記第２種制御パラメータを同じ値にし又は総和を一定の値以下とする、請求項１記載の情報処理装置。
【請求項３】
前記各個体は、前記各交通経路に応じた多次元配列であり、
前記遺伝子操作手段は各次元に対して遺伝子操作を行う、請求項２記載の情報処理装置。
【請求項４】
前記各遺伝子情報は、複数の一条路の交通経路における交通信号の一つに対応するものであり、
前記複数のパラメータは、前記交通信号の複数の制御パラメータを含み、
前記制約条件は、同じ交通経路上の交通信号に対応する遺伝子情報に対して、前記複数の制御パラメータの一部又は全部を同じ値とするという条件を含む、請求項１から３のいずれかに記載の情報処理装置。
【請求項５】
情報処理装置において、遺伝的アルゴリズムによって交通信号の複数の制御パラメータを求める情報処理方法であって、
複数の個体のそれぞれに含まれる複数の遺伝子情報は、それぞれ、交通信号の複数の制御パラメータを含み、
遺伝子操作手段が、前記複数の個体に対して遺伝子操作を行う遺伝子操作ステップと、
修正手段が、少なくとも２つの遺伝子情報に対して、前記複数の制御パラメータの一部又は全部を同一にするという条件を含む制約条件に従って、前記少なくとも２つの遺伝子情報について、前記複数の制御パラメータの一部又は全部を同じ値に修正する修正ステップと、
評価手段が、修正後の前記各個体を評価する評価ステップを含む情報処理方法。
【請求項６】
コンピュータにおいて、請求項５記載の情報処理方法を実現するためのプログラム。
【図１】
【図２】
【図４】
【図５】
【図８】
【図３】
【図６】
【図７】
【図２】
【図４】
【図５】
【図８】
【図３】
【図６】
【図７】
【公開番号】特開２０１３−１６０７５（Ｐ２０１３−１６０７５Ａ）
【公開日】平成２５年１月２４日（２０１３．１．２４）
【国際特許分類】
【出願番号】特願２０１１−１４９４６０（Ｐ２０１１−１４９４６０）
【出願日】平成２３年７月５日（２０１１．７．５）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 発行所 社団法人情報処理学会 九州支部 刊行物名 火の国情報シンポジウム２０１１ 論文集 該当頁 Ｃ−２−１ 第１〜６ページ 発行日 平成２３年３月８日、発行所 社団法人 電子情報通信学会 刊行物名 電子情報通信学会 ２０１１年総合大会講演論文集 該当頁 Ａ−１７−１０ 発行日 平成２３年２月２８日
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２２年度、総務省、戦略的情報通信研究開発推進制度（ＳＣＯＰＥ）「中都市圏におけるマルチエレメントＧＡを用いた交通制御の研究開発」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（５０４１５９２３５）国立大学法人 熊本大学 (314)
【出願人】（５０５１６４６４５）株式会社 ネットワーク応用技術研究所 (9)
【Ｆターム（参考）】
【公開日】平成２５年１月２４日（２０１３．１．２４）
【国際特許分類】
【出願日】平成２３年７月５日（２０１１．７．５）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 発行所 社団法人情報処理学会 九州支部 刊行物名 火の国情報シンポジウム２０１１ 論文集 該当頁 Ｃ−２−１ 第１〜６ページ 発行日 平成２３年３月８日、発行所 社団法人 電子情報通信学会 刊行物名 電子情報通信学会 ２０１１年総合大会講演論文集 該当頁 Ａ−１７−１０ 発行日 平成２３年２月２８日
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２２年度、総務省、戦略的情報通信研究開発推進制度（ＳＣＯＰＥ）「中都市圏におけるマルチエレメントＧＡを用いた交通制御の研究開発」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（５０４１５９２３５）国立大学法人 熊本大学 (314)
【出願人】（５０５１６４６４５）株式会社 ネットワーク応用技術研究所 (9)
【Ｆターム（参考）】
[ Back to top ]