(57)【要約】【課題】遺伝的最適化エージェントが、多数の異なる問題解決技術を共同作用させるような方法をもって統合する方法を提供するコンピュータシステムを提供する。【解決手段】コンピュータシステムは、問題に対する解を示す遺伝子型プールを保持する少なくとも１つの遺伝的最適化エージェントを具備する。そのエージェントは、プールから新たな遺伝子型を生成し、所定の適応度基準に応じて評価し、遺伝子型の新世代を形成すべくプール内の最も適合する遺伝子型を選択する。システムはまた、シミュレートされたアニーリング、強制論理及び神経系ネットワーク等の異なる技術を用いて更なる解を生成する多数の更なるエージェントを有する。これら更なる解はまた遺伝子型により示される。遺伝的最適化エージェントは、更なるエージェントから遺伝子型を輸入し、それらを増殖・選択のためその遺伝子型プールに付加する。【選択図】図１
2007018531.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータシステムにおいて、
（ａ）問題に対する複数の可能な解を示す遺伝子型であって所定の方法で符号化されたもののプールを格納する手段、遺伝子型の前記プールから新たな遺伝子型を生成する増殖手段、所定の適応度の基準に従って前記新たな遺伝子型の評価を行う評価手段、及び前記プール内において遺伝子型の新たな世代を形成するため前記遺伝子型のうち最も適合するものを選択する選択手段を具備する少なくとも１つの遺伝的最適化エージェント、及び
（ｂ）前記問題に対する更なる解を他の技術を用いて生成し、そして更なる遺伝子型によって前記更なる解を示す少なくとも１つの更なるエージェント、を具備し、
（ｃ）前記遺伝的最適化エージェントは、前記更なるエージェントから前記更なる遺伝子型を輸入し、そして増殖及び選択のためにそれらを前記プール内の前記遺伝子型の新たな世代に付加する手段を有することを特徴とするコンピュータシステム。
【請求項２】
請求項１に記載のコンピュータシステムにおいて、前記更なるエージェントは、
（ａ）シミュレートされたアニーリングエージェント、（simulated annealing agent）、
（ｂ）強制論理エージェント（constraint logic agent）、及び
（ｃ）神経系ネットワークエージェント（neural network agent）、のいずれか１つを具備することを特徴とするコンピュータシステム。
【請求項３】
請求項１又は２のいずれかに記載のコンピュータシステムにおいて、更にマニュアル最適化エージェントを具備し、前記マニュアル最適化エージェントが、
（ａ）前記遺伝的最適化エージェント又は前記更なるエージェントから遺伝子型を輸入する手段、
（ｂ）輸入された遺伝子型を、その遺伝子型によって示される解の可視表示に変換する手段、
（ｃ）変更された解を生成するため、使用者に前記可視表示を手際よく処理させ得る手段、及び
（ｄ）前記変更された解を遺伝子型に変換し、その変換された遺伝子型を遺伝的最適化エージェントによる輸入のため用いられ得るようにする手段、を具備することを特徴とするコンピュータシステム。
【請求項４】
請求項１乃至３に記載のコンピュータシステムにおいて、前記増殖手段は、
（ａ）新たな遺伝子型を生成するため、前記プール内に存在する遺伝子型に作用する複数のオペレータ、
（ｂ）前記オペレータの各々に重み付け値を割り当てる手段、
（ｃ）前記オペレータの重み付け値によって決定される可能性に比例した使用をするため前記オペレータを選択する手段、及び
（ｄ）より適合する遺伝子型を生成したオペレータの重み付け値を増加させること及びより適合しない遺伝子型を生成したオペレータの重み付け値を減少させることによって、前記重み付け値を調整する手段、を具備することを特徴とするコンピュータシステム。
【請求項５】
請求項４に記載のコンピュータシステムにおいて、前記オペレータは、新たな遺伝子型を生成するために、存在する遺伝子型に突然変異(mutations)を応用する突然変異オペレータを具備することを特徴とするコンピュー タシステム。
【請求項６】
請求項４又は５に記載のコンピュータシステムにおいて、前記オペレータは、新たな子孫（offspring）遺伝子型を生成するため、存在する２つの親遺伝子型を結合する交配（crossover）オペレータを具備することを特徴とするコンピュータシステム。
【請求項７】
請求項４乃至６のいずれかに記載のコンピュータシステムにおいて、前記オペレータは、前記更なるエージェントから遺伝子型を輸入する輸入（import）オペレータを有することを特徴とするコンピュータシステム。
【請求項８】
コンピュータシステムにおいて、
（ａ）問題に対する複数の可能な解を示す遺伝子型であって所定の方法で符号化されるもののプールを格納する手段、前記遺伝子型のプールから新たな遺伝子型を生成する増殖手段、所定の適応度の基準に従って前記新たな遺伝子型の評価を行う評価手段、及び前記プール内において遺伝子型の新たな世代を形成するため前記遺伝子型の最も適合するものを選択する選択手段を具備する少なくとも１つの遺伝的最適化エージェント、及び
（ｂ）前記問題に対する更なる解を他の技術を用いて生成し、そして更なる遺伝子型によって前記更なる解を他の技術を用いて生成し、そして更なる遺伝子型によって前記更なる解を示す複数の更なるエージェント、を具備し、
（ｃ）前記遺伝的最適化エージェントは、前記更なるエージェントから前記更なる遺伝子型を輸入して、増殖及び選択のためそれらを前記プール内の前記遺伝子型の新たな世代に付加する手段を具備することを特徴とするコンピュータシステム。
【請求項９】
請求項８に記載のコンピュータシステムにおいて、前記更なるエージェントは、
（ａ）シミュレートされたアニーリングエージェント、
（ｂ）強制論理エージェント、及び
（ｃ）神経系ネットワークエージェント、を具備することを特徴とするコンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、問題解決のためのコンピュータシステムに関し、特にこのようなシステムにおける遺伝的最適化技術(genetic optimization techniques)の新規な用法に関するものである。
【背景技術】
【０００２】
遺伝的最適化技術とは、複雑で非確定的な問題を、進化及び自然淘汰に基づく処理によって解決する技術である。問題に対するパラメータは、染色体及び遺伝子にならって作成されたデータ構造をもって符号化される。問題に対する個々の解は、それら染色体の特有のパターンを有する「遺伝子型(genotype)」によって示される。遺伝的最適化処理は、そのような遺伝子型のプール(pool)を利用し、それら遺伝子型を増殖させて新しい遺伝的結合を形成する。その後、遺伝的最適化処理は、個々の解の適応度（即ち、その特有の解がどの程度良好なのか）を評価し、そして更なる増殖のため最も適応する解を選択する。場合によっては、数千回又は無数回この処理を繰り返すことによって、非常に良好な解がしばしば明らかになる。
【０００３】
遺伝的最適化技術のより一層の詳細については、デビッド・Ｅ・ゴールドバーグ(David E. Goldberg)著による「検索、最適化及び機械学習における遺伝的ア ルゴリズム(Genetic Algorithms in Seach, Optimization and Machine Learning)」(Addison-Wesley, Reading Ma, 1989)がある。
【０００４】
しかし、特に複雑で非確定的な問題については、検索スペースが非常に大きくなるので、遺伝的最適化のみに依存するのではしばしば不十分となる。このような場合の遺伝的最適化は、偶然に最適の解となることが殆どなくて、急速に１つに収束することのない無数の遺伝子型を生成することがある。
【０００５】
このような場合の従来の解決策としては、問題特有の情報(problem-specific intelligence)を遺伝的最適化処理に付加することが挙げられる。これは現実の論点からの実際的な知識及び制約に基づく遺伝子型の符号化(genotype encodings)をクリエイトさせるものであり、また遺伝的最適化処理がその検索において早期に良好な解を誘導することを助けることにもなる。しかし、これには以下のような幾つかの欠点がある。
【０００６】
即ち、遺伝的最適化処理の速度が遅くなるので、はるかに少ない回数の繰返し処理しかできないため、与えられた時間内に達成し得る解の適応度の改善の程度が低くなる。
【０００７】
また、情報部分に組み込まれた仮定は、非常に効果的で刷新的かつ根本的な解から実際に遺伝的最適化処理を他の方向へ向けてしまうことが可能である。
【０００８】
更にまた、解答する機関(solver engine)それ自体が一般的なものでなくなり、変更せずに再使用することが不可能となる。
【０００９】
それに加えて、全ての問題が遺伝的最適化によって解決されるのに適している訳ではない。つまり、幾つかの問題については、シミュレートされたアニーリング(simulated annealing)、強制推論(constraint reasoning)又は神経系ネットワーク(neural networks)等の他の公知の技術の方がより適している。しかし、与えられた問題に対して、明らかに最高の技術である演繹性(a priori)を決定することは一般的には不可能である。また、特定の問題であってもデータに影響され易い(data-sensitive)ことがある。即ち、あるデータのパターンに関して遺伝的最適化処理が迅速に良好な解答を見つけることができても、異なるデータについては異なる技術が最高に適するという事態を生じ得る。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は、従来技術における上述の種々の問題を新規な方法で克服することを目的とする。
【課題を解決するための手段】
【００１１】
本発明によれば、コンピュータシステムであって、(a) 問題に対する複数の可能な解を示す遺伝子型であって所定の方法で符号化されたもののプールを格納する手段、前記遺伝子型プールから新たな遺伝子型を生成する増殖手段、所定の適応度基準に従って前記新たな遺伝子型の評価を行う評価手段、及び前記プール内において遺伝子型の新たな世代を形成するため前記遺伝子型のうち最も適合するものを選択する選択手段を具備する少なくとも１つの遺伝的最適化エージェント、及び(b) 前記問題に対する更なる解を他の技術を用いて生成し、そして更なる遺伝子型によって前記更なる解を示す少なくとも１つの更なるエージェント、を具備し、(c) 前記遺伝的最適化エージェントは、前記更なるエージェントから前記更なる遺伝子型を輸入し、そして増殖及び選択のためにそれらを前記プール内の前記遺伝子型の新たな世代に付加する手段を有することを特徴とするもの、が提供される。
【００１２】
このようなコンピュータシステムにおいて、遺伝的最適化エージェントは、多数の異なる問題解決技術を異なる技術間の共同作用を達成するような方法をもって統合することができる骨組みを提供する。
【発明の効果】
【００１３】
以上説明したように、本発明によれば、遺伝的最適化エージェントが多数の異なる問題解決技術をそれらの技術間の共同作用を達成するような方法をもって統合することができる方法を提供するようなコンピュータシステムを提供することが可能となる。
【実施例】
【００１４】
以下、本発明の１つの実施例について添付図面を参照しつつ説明する。
【００１５】
図１は、複数のエージェント(agents)１１乃至１６を具備するコンピュータシステム１０を示す。これらエージェントは別個独立のプロセッサに関する処理であってよく、そうでなければ１又はそれ以上のエージェントは同一のプロセッサに関する時分割処理として動作するものであってもよい。これらエージェントは、いずれか１つのエージェントに他のいずれかのエージェントに対するメッセージを送出させることができるメッセージ通過機構１７によって相互にコミュニケーションをとることが可能である。
【００１６】
コンピュータシステムは、遺伝的最適化技術によって問題を解決することができる少なくとも１つの遺伝的最適化エージェントを有する。この例においては２つの遺伝的最適化エージェント１１及び１２を有しているが、本発明の別の例においては１つの遺伝的最適化エージェントのみであってもよく、また２つ以上の遺伝的最適化エージェントであってもよい。この遺伝的最適化エージェントについては、以下に詳細に説明する。
【００１７】
本コンピュータシステムはまた、他の（非遺伝的な）技術によって問題を解決することができる１又は２以上の更なるエージェントを有する。この例においては、これら更なるエージェントとして、シミュレートされたアニーリング(simulated annealing)エージェント１３、強制（制約）論理プログラミング(constraint logic programming:ＣＬＰ)エージェント１４、及び神経系ネットワークエージェント１５を有する。シミュレートされたアニーリング、ＣＬＰ及び神経系ネットワークは当該技術分野においては公知の技術であり、これらの処理の詳細は本発明のいかなる部分も構成しない。従って、これらのエージェント１３乃至１５についてのこれ以上詳細な説明は必要ではない。この例において、本コンピュータシステムはまた、使用者に解をマニュアルにクリエイトさせ及び変更させることができるマニュアル最適化エージェント１６を有する。これについては、以下に詳細に説明する。
【００１８】
動作において、エージェント１１乃至１６の各々は、各々の特有の方法を用いて与えられた問題に対する可能な解をクリエイトすることを試みる。これら可能な解の各々は幾つかの所定の方法、例えばビット列として符号化される。符号化された解は「遺伝子型(genotype)」と呼ばれる。全てのエージェントは同一の所定の遺伝子型符号化スキームを用いるので、どのような遺伝子型であっても全てのエージェントによって理解され得る。例えば、輸送スケジュールの問題において、各遺伝子型は、多数のトラック運転手の各々によって実行されるべき集荷及び配送の特有のシーケンスを示す符号化された情報を含むようにしてもよい。
【００１９】
以下、遺伝的最適化エージェント１１又は１２について、図２を参照しつつ詳細に説明する。
【００２０】
遺伝的最適化エージェントは、懸案の問題に対する解の現在の世代(generation)を示す遺伝子型のプール２０を維持する。遺伝的最適化エージェントの動作が開始されたとき、処理２１は遺伝子型の最初の世代を、例えば無作為化によって、又は以前の動作から格納されている遺伝子型を用いることによって、クリエイトする。
【００２１】
遺伝的最適化エージェントは、プール２０内の遺伝子型の処理を行って１セットの新たな遺伝子型２３を生成する増殖処理２２を含む。それら新たな遺伝子型の各々は、遺伝子型がどのような問題特有の制約をも満足させるか否かチェックする妥当性検査処理２４を経る。例えば、輸送スケジュールの問題において、妥当性検査処理は、遺伝子型によって示される配送スケジュールが運転手の最大許容時間以上の運転を伴うことになるか否かをチェックするようにしてもよい。遺伝子型がこのような制約を満足させないときは、妥当性検査処理は、制約を満足させる値を検索することによって「遺伝子修復(gene-repair)」動作を行う。もしそのような値が見つけられないときは、その新たな遺伝子型は放棄される。
【００２２】
遺伝的最適化エージェントはまた、新たな遺伝子型を評価し各遺伝子型について適応値を生成する評価処理２５を含む。この適応値は、遺伝子型がどのような良好な解を示すかを示すものである。例えば、輸送スケジュールの問題において、この適応値は遺伝子型によって示される配送スケジュールの効率を示すようにしてもよい。
【００２３】
遺伝的最適化エージェントは更に、最も良い遺伝子型を（遺伝子型のプール２０及び新たな遺伝子型セット２３の両方から）選択し、選択された遺伝子型を遺伝子型プールにおく選択処理２６を含む。この場合、最も悪い遺伝子型は放棄される。
【００２４】
この増殖、妥当性検査、評価及び選択処理は循環的に行われ、遺伝子型の連続した世代を生成する。この循環は、以下のうちの１つのようなある程度の基準が満足させられるまで継続する。
【００２５】
即ち、定められた数の世代が生成されていること、
平均適応値におけるパーセンテージの改善が所定値以下に落ちること、及び
所定回数が経過していること、である。
【００２６】
また増殖処理２２は、突然変異(mutation)オペレータ２７、交配(crossover)オペレータ２８及び輸入(import)オペレ−タ２９を含む多数のオペレータを有する。各オペレータは、それに関する重み付け値を有する。この重み付け値は、そのオペレータを使用する可能性を決定するものである。また、これらの重み付け値は連続する世代について調整され、より適応する遺伝子型を生成するそれらオペレータの使用の可能性を向上させる。
【００２７】
突然変異オペレータ２７は、プール２０から複数の遺伝子型のうちの１つを入手して何らかの方法でそれを突然変異(mutate)させる。例えば、ビット方式で符号化された遺伝子型の場合、その突然変異は、そのビットのうちの無作為に選択された１つを反転させることによるものであってもよい。
【００２８】
図３は、遺伝子型３１に適用されるそのような突然変異オペレータを示す。ここでは、５番目のビットが反転のために選択される。
【００２９】
交配オペレータ２８は、プール２０から複数の遺伝子型のうちの２つを「親(parents)」として選択し、それらの遺伝子情報の一部を交換することによって、それら親から２つの新たな「子孫(offspring)」を生成する。ここで、親はそれらの適応値に基づく可能性に比例して無作為に選択されるので、その結果より高い適応値の遺伝子型はより多くの子孫を生成する傾向を持つようになる。一例として、図４は、２つの子孫遺伝子型４３及び４４を生成するため、２つの親遺伝子型４１及び４２に適用される１つの可能性ある交配オペレータを示す。この例においては、５番目のビットの後にクロスポイント４５が無作為に選択される。第１の子孫４３は、クロスポイント手前の第１の親４１のビット及びクロスポイント以降の第２の親４２のビットを入手することによってクリエイトされる。同様に、第２の子孫４４は、クロスポイント手前の第２の親４２のビット及びクロスポイント以降の第１の親４１のビットを入手することによってクリエイトされる。実際には、遺伝子型が符号化される方法に依存して、他の形式の交配オペレータが用いられるようにすることも認められる。
【００３０】
輸入オペレータ２９は、コンピュータシステム内の別の複数のエージェントの１つに対し、その別のエージェントがクリエイトし得る限りの最高の遺伝子型を送るよう要求するメッセージを送る。要求された遺伝子型が受信されたとき、その受信された遺伝子型は、突然変異オペレータ及び交配オペレータによって生成されたローカル生成の遺伝子型と全く同じ方法で妥当性検査がなされそして新たな遺伝子型２３のセットに付加される。このように輸入された遺伝子型は、遺伝的最適化エージェントによる更なる進化に利用できる。
【００３１】
マニュアル最適化エージェント１６は、使用者に現在の最高の遺伝子型を他の全てのエージェント１１乃至１５から選択させ、そして選択された遺伝子型によって示される解を何らかの容易に理解し得る形式でスクリーン上に表示させ得る。エージェント１６はまた、使用者に表示された解を、それを改善する試みにおいて手際よく処理させ得る。例えば、輸送スケジュールの問題において、エージェント１６は、ガント(Gantt)チャートの形式における遺伝子型によって示される配送スケジュールを表示するようにしてもよい。その後使用者は、チャート上の１又はそれ以上のバー(bar)を他の場所へ引くためマウス又は他のポインタデ バイスを用いて、このガントチャートを変更してもよい。使用者が動作を終えたとき、エージェント１６は変更された解を遺伝子型へ再変換し、再変換した遺伝子型を遺伝的最適化エージェントへの輸出に利用できるようにする。既に述べたように、遺伝的最適化エージェントは、その後この遺伝子型を輸入し、その妥当性検査を行い、それを修復し、そしてそれを新たな遺伝子型のセットに付加する。
【００３２】
これによって、使用者がその時点までの最高の解を獲得し、そして使用者の熟練及び経験を用いてガントチャートを変更し、それによる新たな遺伝子型を遺伝的最適化エージェントに提供することができるのをみることができる。遺伝子型が良好な新しい開始点を示す場合には、それは遺伝的最適化エージェントによって更に良好な解を生成するため用いられる。
【００３３】
要約すると、遺伝的最適化エージェントは、他のエージェントから適応するようにみえる遺伝子型を定常的に輸入し、そしてそれらをより一層適応するものまで進化させるよう試みる。一方、その他のエージェントは良好な解を独自の方法でクリエイトするよう試みることになる。もしその他のエージェントの１つが偶然に特有の素晴らしい解を非常に迅速に提供する場合は、それはこの解を更に精緻なものにするため遺伝的最適化エージェントに提供する。もしそうでない場合は、遺伝的最適化エージェントはそれ自身の解を生成するため正常な方法で動作することになる。
【００３４】
実際にこのことが意味するものは、遺伝的最適化処理が２つのことを行っているということである。即ち、第１に遺伝的最適化処理は独立した個々の解を引き出すというそれが持つ正常な仕事(job)をしているということであるが、第２に 入力データ特有のパターンを用いて特有の問題を解決するために最も適応する技術をまた事実上引き出しているということである。
【００３５】
商業的問題を解決することに関し本発明は特に重大な利点を有している。まず最初に、問題に取りかかるためにいわゆる「在庫(off-the-shelf)」の解答エー ジェント(solver agent)のみを用いることができるという点である。より問題に適応したアプローチが明らかにされるほど、新たなエージェントは現存するエージェントを変化させることなく簡単にアーキテクチャに付加されることができる。もし新たなエージェントが良好に動作すれば、良好な解がより迅速に見つけられることになる。一方、良好に動作しなければ、それらの結果は遺伝的最適化エージェントによって単純に無視される。これは、現在のコンピュータの応用開発のうちの最もハイリスクな領域の１つにおいて、効果的に開発上のリスク減少をもたらすことになる。
【００３６】
（幾つかの可能な変更例）
上述のコンピュータシステムについては、本発明の範囲を逸脱することなく多くの変更が可能である。例えば、幾つかの可能性ある変更例として、以下のようなものがあげられる。
【００３７】
システムは、エージェントによる輸出のために提供された遺伝子型の中央プールを有するようにしてもよい。この場合、遺伝的最適化エージェントが新たな遺伝子型を輸入することを要求するときはいつでも、他のエージェントからよりもこの中央プールから新たな遺伝子型を得ることになる。
【００３８】
システムはまた、分割された評価エージェントを有するようにしてもよい。ここで、各評価エージェントは、システム内において各遺伝的最適化エージェントに対し評価サービスを提供する。
【００３９】
また、適当な最高の遺伝子型に代えて、輸入オペレータは幾つかの最高の遺伝子型を別のエージェント（１以上の遺伝子型がその別のエージェントにおいて利用できると仮定する）の各々から輸入するようにしてもよい。
【００４０】
更に、タグ付け等の何らかの方法を、最近輸出された遺伝子型が同じエージェント内に再度輸入されることを回避するため用いるようにしてもよい。
【００４１】
更にまた、遺伝子型のソースのトラックを保持しておくためのメカニズムを設けてもよい。それによって、最適化のどのようなステージでも最高に動作した技術のヒストリーを保持することになる。
【図面の簡単な説明】
【００４２】
【図１】本発明を採用したコンピュータシステムのブロック図である。
【図２】システムの遺伝的最適化エージェント形成部を示した概略図である。
【図３】遺伝的最適化エージェントによって使用される変更動作を示す概略図である。
【図４】遺伝的最適化エージェントによって使用される交配動作を示す概略図である。
【符号の説明】
【００４３】
１１、１２  遺伝的最適化エージェント
１３  シミュレートされたアニーリングエージェント
１４  強制論理エージェント
１５  神経系ネットワークエージェント
１７  メッセージ通過メカニズム
【図１】
2007018531.tif 000003
【図２】
2007018531.tif 000004
【図３】
2007018531.tif 000005
【図４】
2007018531.tif 000006