(57)【特許請求の範囲】
【請求項１】
複数の個体について複数の世代形成を行って最適解を求める遺伝的アルゴリズム処理装置おいて、
並列的に世代の更新を行うと共に各世代の更新にあっては並列的に世代数の統一のための同期制御を行わないで並列処理を行って、各世代毎の個体形成をそれぞれが行う複数のプロセッサと、この複数のプロセッサ相互のデータ群通信を行う接続装置と、を備え、
各プロセッサは、世代処理手段と通信処理手段とを具えて、
通信処理手段は、自己の世代処理手段で自己の最新世代が形成されたかを監視し最新世代の形成があればこの最新世代個体データ群を上記接続装置を介して他プロセッサの通信処理手段へと送信し、他プロセッサの最新世代の形成によりその通信処理手段から上記接続装置を介して送られてくる最新世代固体データ群を受信するものとし、
世代処理手段は、自己の最新世代を形成すると共にその形成にあっては、第１世代では初期化に基づき第１世代個体データ群を形成し、第２世代以降にあっては、自己の通信処理手段で受信した他プロセッサの最新世代個体データ群と自己のそれまでに得た世代個体データ群とを用いて最新世代個体データ群を形成し、最新世代数が予め定めた最長世代数に達していれば世代処理を終了するものとした、
ことを特徴とする遺伝的アルゴリズム処理装置。
【請求項２】
Ｎ個の個体についてＧ個の世代形成を行って最適解を求める遺伝的アルゴリズム処理装置において、
並列的に世代の更新を行うと共に各世代の更新にあっては並列的に世代数の統一のための同期制御を行わないで並列処理を行うＰ個のプロセッサと、Ｐ個のプロセッサ相互のデータ群通信を行う接続装置とを備えて、Ｎ個の個体について上記Ｐ個のプロセッサにＮ／Ｐずつの個体の並列処理を割り当てると共に、
各プロセッサは、世代処理手段と通信処理手段とを具えて、
通信処理手段は、自己の世代処理手段で自己の最新世代が形成されたかを監視し最新世代の形成があればこの最新世代個体データ群を上記接続装置を介して他プロセッサの通信処理手段へと送信し、他プロセッサの最新世代の形成によりその通信処理手段から上記接続装置を介して送られてくる最新世代固体データ群を受信するものとし、
世代処理手段は、自己の最新世代を形成すると共にその形成にあっては、第１世代では初期化に基づき第１世代個体データ群を形成し、第２世代以降にあっては、自己の通信処理手段で受信した他プロセッサの最新世代個体データ群と自己のそれまでに得た世代個体データ群とを用いて最新世代個体データ群を形成し、最新世代数が予め定めた最長世代数に達していれば世代処理を終了するものとした、
ことを特徴とする遺伝的アルゴリズム処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、各種分野における様々な計画立案、設計、制御における組み合せ最適化問題を解く装置に関し、特に、組み合せ数が膨大な問題を並列計算機を用いて高速に処理する装置に関する。
【０００２】
【従来の技術】
組み合せ最適化問題を、現実的に許容しえる時間内に見つけ出すための手法として、例えば、生物の進化を模擬し、大域的に準最適化を求める、遺伝的アルゴリズムがある。これは、特開平８−１９４６７６号「並列遺伝的アルゴリズム実行装置」や特開平８−３１４８８２号「電源導入順序決定方法」に記載されている。
【０００３】
図４は、遺伝的アルゴリズムと称されるものの基本的な処理フローである。まずステップＳ４１の初期化では、最適化問題の解の候補を数列等に変換して生物の染色体情報として指定された数Ｎだけ作成する。染色体情報の個数は一つでも複数でも良く、この数Ｎは個体数と呼ばれる。ステップＳ４２では、指定された繰り返し数Ｇが満たされたかを判定する。この数Ｇは世代数と呼ばれる。ステップＳ４３では、指定された個体数Ｎが満たされたかを判定する。ステップＳ４４の個体作成では、既存の染色体情報から新しい染色体情報を作成する。ここでの新たな染色体情報の作成方法として、複数の染色体情報を組み合せる交叉や、１つの染色体情報中の要素をランダムに変化させる突然変異、等がある。
【０００４】
このような計算処理は、逐次処理で実行できるが、並列計算機を用いて並列処理することができる。
例えば、特開平８−１９４６７６号には以下の例の記載がある。Ｐ台のプロセッサを持つ並列プロセッサシステム（計算機システム）を用いて、Ｎ個体の計算を行う場合、各プロセッサはＮ個体の染色体情報のコピーを持ち、各世代毎の個体作成処理は各プロセッサはＮ／Ｐ個だけ担当し、新たに作成された全ての染色体情報を各プロセッサ間で通信によって更新する方法が従来例として記載されている。かかる従来例は、各プロセッサ間での通信に時間を有するという問題があり、特開平８−１９４６７６号の実施例では、交叉対象の染色体情報のみ各プロセッサ間で通信することにより、通信時間を削減する方法が提案されている。
また、日々の技術進歩により、ＬＡＮやバス等のデータ通信機器の性能も向上しており、同じデータ容量でも、この通信時間は削減されつつある。
【０００５】
【発明が解決しようとする課題】
並列計算機を用いた遺伝的アルゴリズムの並列処理において、従来技術により通信時間は短縮されつつあるが、実際の処理では、各個体作成の処理である、交叉、突然変異等に有する処理量が不均等であったり、マルチタスクシステムでは、当該処理以外の処理が平行処理されており、特定のプロセッサやバス、またはハードディスク等の電子計算機資源の利用負荷が高くなっており、各プロセッサの個体作成処理の時間が不均一である。
【０００６】
これを以下詳細に説明する。
図６は、図４による、２個体、３世代、の遺伝的アルゴリズムのタイムチャートを示している。先ず、初期化を行い、１世代目の個体（１）の作成、１世代目の個体（２）の作成、２世代目の個体（１）の作成、２世代目の個体（２）の作成、３世代目の個体（１）の作成、３世代目の個体（２）の作成、の順に処理が行われる。
【０００７】
図５は遺伝的アルゴリズムの並列処理の各プロセッサ毎のフローである。
まずステップＳ５１の初期化では、Ｓ４１と同様に染色体情報を個体数Ｎだけ作成する。ステップＳ５２では、Ｓ４２と同様に指定された繰り返し数Ｇが満たされたかを判定する。ステップＳ５３では、指定された繰り返し数である個体数Ｎ／Ｐが満たされたかを判定する。ここでＰはプロセッサ数である。ステップＳ５４では、Ｓ４４と同様に、既存の染色体情報から新しい染色体情報を作成する。ステップＳ５５では、新たに作成された全ての染色体情報を各プロセッサ間で通信によって更新する。
【０００８】
図７は、図５による、２個体、３世代、の遺伝的アルゴリズムの各個体作成処理時間が均一の、プロセッサ数が２つの場合のタイムチャートを示している。プロセッサ１では、初期化を行い、１世代目の個体（１）の作成、染色体情報の通信、２世代目の個体（１）の作成、染色体情報の通信、３世代目の個体（１）の作成、染色体情報の通信、の順に処理が行われる。プロセッサ２では、初期化を行い、１世代目の個体（２）の作成、染色体情報の通信、２世代目の個体（２）の作成、染色体情報の通信、３世代目の個体（２）の作成、染色体情報の通信、の順に処理が行われる。各プロセッサ間の通信は同期がとられて、同一世代間の情報通信を行っている。
【０００９】
図８は図５による、２個体、３世代、の遺伝的アルゴリズムの各個体作成処理時間が不均一である実際のタイムチャートを示している。プロセッサ１、プロセッサ２での処理内容は図７と同じであるが、染色体情報の通信は各プロセッサで同期させているため、網掛けで示された待ち時間ｔ１、ｔ２、ｔ３が生じてしまう。
そのため各プロセッサは利用効率が悪くなり、その結果、遺伝的アルゴリズムの処理の効率が悪くなってしまうという問題が生じる。つまり、並列化しても、あまり高速化されないという問題が生じる。
【００１０】
従来の技術における遺伝的アルゴリズムは、初期化後に、各プロセッサ上で個体作成を行い、全プロセッサ上での個体作成の終了後、次世代の交叉のために各プロセッサ間で個体情報を交換し、そして次世代の処理に移行する方式がとられている。
これを、自然界の生物の進化に当てはめると、幾つかの系統（血統）を持つ生物の系にて、全ての系統において、ある時点からの世代数が等しくなった時点で、交叉により新たな個体を生み出し、次世代に移っていく、と言うことである。
【００１１】
しかし通常、自然界の生物の進化においては、幾つかの系統間で交叉によって新たな個体を生み出す場合、各々の系統である時点からの世代数は統一される必要はなく、単に新たな個体生み出す時点において存在する交叉可能な個体から新たな個体が生み出される。これは、進化世代数を統一するためにそれぞれの系統間で互いに待つことを必要としない、つまり世代相互の同期を必要としない、と言い換えることができる。
本発明の目的は、世代間の同期をとることなく最適化問題を解くことを可能にする遺伝的アルゴリズム処理装置を提供するものである。
【００１２】
【課題を解決するための手段】
本発明は、複数の個体について複数の世代形成を行って最適解を求める遺伝的アルゴリズム処理装置おいて、
並列的に世代の更新を行うと共に各世代の更新にあっては並列的に世代数の統一のための同期制御を行わないで並列処理を行って、各世代毎の個体形成をそれぞれが行う複数のプロセッサと、この複数のプロセッサ相互のデータ群通信を行う接続装置と、を備え、
各プロセッサは、世代処理手段と通信処理手段とを具えて、
通信処理手段は、自己の世代処理手段で自己の最新世代が形成されたかを監視し最新世代の形成があればこの最新世代個体データ群を上記接続装置を介して他プロセッサの通信処理手段へと送信し、他プロセッサの最新世代の形成によりその通信処理手段から上記接続装置を介して送られてくる最新世代固体データ群を受信するものとし、
世代処理手段は、自己の最新世代を形成すると共にその形成にあっては、第１世代では初期化に基づき第１世代個体データ群を形成し、第２世代以降にあっては、自己の通信処理手段で受信した他プロセッサの最新世代個体データ群と自己のそれまでに得た世代個体データ群とを用いて最新世代個体データ群を形成し、最新世代数が予め定めた最長世代数に達していれば世代処理を終了するものとした、
ことを特徴とする遺伝的アルゴリズム処理装置を開示する。
【００１３】
更に本発明は、Ｎ個の個体についてＧ個の世代形成を行って最適解を求める遺伝的アルゴリズム処理装置において、
並列的に世代の更新を行うと共に各世代の更新にあっては並列的に世代数の統一のための同期制御を行わないで並列処理を行うＰ個のプロセッサと、Ｐ個のプロセッサ相互のデータ群通信を行う接続装置とを備えて、Ｎ個の個体について上記Ｐ個のプロセッサにＮ／Ｐずつの個体の並列処理を割り当てると共に、
各プロセッサは、世代処理手段と通信処理手段とを具えて、
通信処理手段は、自己の世代処理手段で自己の最新世代が形成されたかを監視し最新世代の形成があればこの最新世代個体データ群を上記接続装置を介して他プロセッサの通信処理手段へと送信し、他プロセッサの最新世代の形成によりその通信処理手段から上記接続装置を介して送られてくる最新世代固体データ群を受信するものとし、
世代処理手段は、自己の最新世代を形成すると共にその形成にあっては、第１世代では初期化に基づき第１世代個体データ群を形成し、第２世代以降にあっては、自己の通信処理手段で受信した他プロセッサの最新世代個体データ群と自己のそれまでに得た世代個体データ群とを用いて最新世代個体データ群を形成し、最新世代数が予め定めた最長世代数に達していれば世代処理を終了するものとした、
ことを特徴とする遺伝的アルゴリズム処理装置を開示する。
【００１６】
【発明の実施の形態】
先ず、本発明の基本的な考え方を述べる。
本発明では、各プロセッサ上で新たな個体作成を行う場合、その時点で既に、他プロセッサから通信によって送られてきている他プロセッサにおける最新世代の個体情報を親として個体作成を行い、プロセッサ間での世代数の統一のための同期を行わない（他プロセッサがその時点でどの世代を処理し終えているかは問題にしていない）。つまり、並列処理時における処理性能低下の重要な一項目である同期が無いため、並列処理性能を高く維持することができ、高速に処理することができる。
【００１７】
本発明では、進化世代数の統一を行わないため、処理の早いプロセッサでは、他プロセッサのＧ世代目の個体情報を取得する前に、（Ｇ−１）世代よりも前の世代の個体を使用して、Ｇ世代目の個体作成を行う。
これでも解の質が悪くならないことを説明する。
例えば、あるプロセッサにてＧ世代の個体を作成するときに、他のプロセッサでは（Ｇ−２）世代までしか処理が完了しておらず、それ以降の個体情報が通信によって当該プロセッサに通知されていなかったとする。この場合、当該プロセッサの（Ｇ−１）世代目の個体と他の（Ｇ−２）世代目の個体から新しく個体を作成することになるが、Ｇを十分に大きくすることで（Ｇ−１）／（Ｇ−２）の値は無視することができる。
【００１８】
そして、本発明では、各プロセッサでの単位時間当たりの処理世代数は、同期のための待ちが無いため従来の技術の処理世代数より、大きく取ることができるため、同一世代数を処理する場合はより高速に処理が可能である。
これは、例えば個体作成時間が正規分布Ｎ（ｍ，σ2）＝Ｎ（３０，５2単位秒）に従うとすると、個体作成時間が４０秒より大きい確率Ｑ（Ｘ＜４０）＝Ｑ（Ｘ＜ｍ＋２σ）＝０．１６であり、仮にプロセッサ数を１０とすると、個体作成時間が４０秒より大きいプロセッサが１つ、確率的に存在する。この場合、従来の技術では、４０秒で１世代が処理されることになる。一方、本発明では、この個体作成時間が４０秒より大きいプロセッサ以外の残りのプロセッサは平均３０秒未満で１世代処理することになる。そして４０秒間では、残りの１０秒間でも次世代の処理を行うため、合計で、
（作成時間が４０秒より大きいプロセッサが作る個数）＋（残りのプロセッサが作る個数）＝（４０秒間で１個）＋｛（３０秒間で９個）＋（残りの１０秒間で作れる個数）｝＝１＋９＋３＝１３
の個体を作成することができる。つまり本発明は各プロセッサの個体作成時間の標準偏差σが大きいほど有効に働くことが示せる。
【００１９】
また、特に解空間に対して、適応度が非連続的で離散的である場合は、適応度が良い個体を親としても必ずしもよい個体が作成されるわけではなく、いかに多くの個体を作成し評価するかが重要である。つまり世代数は重要ではなく、個体作成時に（Ｇ−１）世代目を親にするか、（Ｇ−１）世代より前の世代を親にするか、の処理の差がより少なくなる。
【００２０】
以下、図１を用いて本発明の実施の形態に係る遺伝的アルゴリズム並列処理装置を説明する。
図１は本発明に係る遺伝的アルゴリズム並列処理装置の機能構成を示している。
本実施例の遺伝的アルゴリズム並列処理装置は、図１に示すように、複数のプロセッサ（プロセッサ１〜プロセッサＰ）を持ち、各プロセッサはプロセッサ間接続装置（通信ラインを含む）１０によって互いに接続され、各プロセッサは、ＧＡ処理手段１０と、通信処理手段１１と、指定された個体数Ｎの遺伝的アルゴリズムの染色体情報を記憶する個体情報記憶手段１２と、から構成される。
ＧＡ処理手段１０は、他プロセッサとの通信手段を持たずに、初期化手段１０１と個体作成手段１０２とを制御するＧＡ制御手段１００と、遺伝的アルゴリズムの染色体情報の初期化を行う初期化手段１０１と、遺伝的アルゴリズムの個体選択、交叉、突然変異といった処理を行い新たな個体を作成する個体作成手段１０２と、から構成される。
通信処理手段１１は、個体情報記憶手段アクセス手段１１１と通信手段１１２とを制御する通信制御手段１１０と、個体情報記憶手段の記憶内容の読み取り書き込みをおこなう個体情報記憶手段アクセス手段１１１と、当該プロセッサ以外のプロセッサとの染色体情報の通信を行う通信手段１１２と、から構成されている。
【００２１】
ここで、ＧＡ処理手段１０は電子計算機上のプロセスとして、通信処理手段１１は電子計算機上のプロセスとして、個体情報記憶手段１２は電子計算機上の共有メモリエリアとして、実現することができ、さらに電子計算機上のプリエンプティブなオペレーティングシステムを用いることによりＧＡ処理手段１０と通信処理手段１１は並行処理することができる。
さらに、ＧＡ処理手段１０と、通信処理手段１１と、を電子計算機上の一つのプロセスのスレッドとして、個体情報記憶手段１２を電子計算機上のローカルメモリエリアとして、実現することもでき、この場合もＧＡ処理手段１０と通信処理手段１１とは平行処理することができる。
また、図１の破線は制御を、矢印付き実線は情報の流れを示している。
【００２２】
以下に本発明の動作例について図２と図３を使用して詳細に説明する。
説明のためプロセッサ数Ｐ＝２、個体数Ｎ＝２、世代数Ｇ＝３とするが、実際はプロセッサ数、個体数、世代数は任意の自然数であってもかまわない。
本装置の処理が開始されると、プロセッサ１では図２（a）のＧＡ処理手段１０のフローと、図２（ｂ）の通信処理手段１１のフローと、による２つの処理が平行処理される。図３には処理シーケンスを示す。
【００２３】
ＧＡ処理手段１０では、（Ｓ２１）初期化手段１０１にて、個体情報記憶手段１２に個体数Ｎ＝２の染色体情報が作成される。これは図３の▲１▼に対応する。（Ｓ２２）世代数Ｇ＝３が満たされたかのチェックが行われる。現在は１世代目なので、Ｎｏである。（Ｓ２３）個体数Ｎ／Ｐ＝２／２＝１が満たされたかのチェックが行われる。現在は１個体目なのでＮｏである。（Ｓ２４）個体作成手段１０２にて、個体情報記憶手段１２の指定の染色体情報に対して、交叉、突然変異等の処理を行って、１世代目の個体（１）が作成される。これは図３の▲２▼に対応する。さらに（Ｓ２３）（Ｓ２２）（Ｓ２３）と進み、（Ｓ２４）２世代目の個体（１）が作成される。これは図３の▲３▼に対応する。同様に（Ｓ２３）（Ｓ２２）（Ｓ２３）と進み、（Ｓ２４）３世代目の個体（１）が作成される。これは図３の▲４▼に対応する。
【００２４】
通信処理手段１１では、（Ｓ２５）ＧＡ処理手段が終了したかのチェックが行われる。最初はＮｏである。（Ｓ２６）個体情報記憶手段アクセス手段１１１にて、個体情報記憶手段１２の内容が読み出され１世代目の個体（１）が作成されたかがチェックされる。ＧＡ処理手段１０により▲２▼が処理されれば、Ｙｅｓであり（Ｓ２７）に進み、通信手段１１２により、個体情報記憶手段アクセス手段１１１を通じて個体情報記憶手段１２から１世代目の個体（１）の染色体情報を読み出しこれがプロセッサ２に送信され、さらに１世代目の個体（２）の染色体情報をプロセッサ２から受信しこれが個体情報記憶手段アクセス手段１１１を通じて個体情報記憶手段１２に書き込まれる。これは図３の▲５▼に対応する。ＧＡ処理手段１０により▲２▼が処理されていなければ、Ｎｏとなり（Ｓ２５）に戻る。この処理を繰り返して、ＧＡ処理手段１０により▲３▼が処理されれば、▲６▼が処理され、ＧＡ処理手段１０により▲４▼が処理されれば、▲７▼が処理される。
【００２５】
またこの動作例では、▲５▼〜▲７▼の通信のタイミングを新たな個体作成後としているが、この他に以下の例がある。
（１）、予め定めた一定時間隔で行う例がある。
（２）、世代形成をするプロセッサの中で、最長形成時間のプロセッサにを基準とし、その世代形成終了後に通信を行う例がある。
（３）、各世代処理終了後に通信要求を出すものとし、通信は全プロセッサ終了時に通信を行う例がある。
【００２６】
このように、本発明では、１世代目は、従来技術と同様に、初期化手段によって作成された染色体情報を用いるが、２世代目は、従来技術では１世代目に作成された染色体情報を用いるのに対し、本発明では当該プロセッサで作成されたＮ／Ｐ個の１世代目に作成された染色体情報と初期化手段によって作成されたＮ−（Ｎ／Ｐ）個の染色体情報を用いる。更に、ｇ世代目（ｇ＞２）は、従来技術では（ｇ−１）世代目に作成された染色体情報を用いるのに対し、本発明では当該プロセッサで作成されたＮ／Ｐ個の（ｇ−１）世代目に作成された染色体情報と他プロセッサで作成されたＮ−（Ｎ／Ｐ）個の（ｇ−２）世代目に作成された染色体情報を用いる。つまり本発明は従来技術と比べてＮ−（Ｎ／Ｐ）個の染色体情報が１世代古いものを用いて個体作成を行うが、世代数Ｇを大きくとることにより、（ｇ−１）と（ｇ−２）の比は少なくなるため、解の質が極端に落ちることは無い。逆に、本発明では各プロセッサの待ちが無いため、従来技術と比較してより多くの世代が処理できるため、解の質が向上する。
【００２７】
ＧＡ処理手段は、更新する世代数Ｇの管理を行っている。これにより例えば、最長世代数Ｇを与えておき、世代数Ｇになった時点の解を最適解とするやり方をとることができる。最長世代数Ｇは処理量と処理時間と解の様子とを考慮して事前に設定しておくやり方もあれば、オペレータが処理量と処理時間と解の様子とを監視しながら途中入力設定するやり方もある。
【００２８】
【発明の効果】
本発明によれば、従来技術における遺伝的アルゴリズムの並列処理における通信処理時の待ち時間を、有効に遺伝的アルゴリズムの処理に利用でき、言い換えれば各プロセッサの処理能力を十分に利用でき、従来技術の遺伝的アルゴリズムの並列処理と比べて、単位時間当たりの個体作成数が多くなる。つまり本発明により、最適化問題をより高速に、より高品質に解くことができできる。
【図面の簡単な説明】
【図１】本発明に係る遺伝的アルゴリズム並列処理装置の機能構成を示す図である。
【図２】本発明に係わる遺伝的アルゴリズムの並列処理フローを示す図である。
【図３】本発明に係る遺伝的アルゴリズムの並列処理タイミングチャートを示す図である。
【図４】遺伝的アルゴリズムの処理フローを示す図である。
【図５】従来技術の遺伝的アルゴリズムの並列処理フローを示す図である。
【図６】遺伝的アルゴリズムの処理タイミングチャートを示す図である。
【図７】各個体作成処理時間が均一な場合の、従来技術の遺伝的アルゴリズムの並列処理タイミングチャートを示す図である。
【図８】各個体作成処理時間が不均一な場合の、従来技術の遺伝的アルゴリズムの並列処理タイミングチャートを示す図である。
【符号の説明】
１０  ＧＡ処理手段
１００  ＧＡ制御手段
１０１  初期化手段
１０２  個体作成手段
１１  通信処理手段
１１０  通信制御手段
１１１  個体情報記憶手段アクセス手段
１１２  通信手段
１２  個体情報記憶手段
【図１】
0003710983.tif 000002
【図２】
0003710983.tif 000003
【図３】
0003710983.tif 000004
【図４】
0003710983.tif 000005
【図５】
0003710983.tif 000006
【図６】
0003710983.tif 000007
【図７】
0003710983.tif 000008
【図８】
0003710983.tif 000009