(57)【要約】ローカルミニマムに陥ることを回避し、かつ、時系列的に変化するような問題についても対応できる適正解探索方法及び適正解探索装置を提供すること。複数の個体についての遺伝的情報の１つとして、生の状態と死の状態とについての情報が含まれている。つまり、当該情報が、個体データ格納領域Ｅ２の寿命格納領域Ｅ２４に格納されている。これにより、各個体は、比較的良好な適応値（適応度）を持つものであっても、良好でない適応値（適応度）を持つものであっても、いずれ死を迎えることで淘汰されるため、例えば比較的良好であるが適正解とは言えない適応値を持つ個体によって寡占状態となることがなく、設定された問題の適正解を探索する上でローカルミニマムに陥ることが回避され、また、個体の多様性が保たれて時系列的に変化するような問題にも対応可能となる。
2013051701.tif 000002
【特許請求の範囲】
【請求項１】
問題の解の候補の要素を遺伝子配列としてそれぞれ有する複数の個体について、淘汰、突然変異及び交叉を含む遺伝的操作を行う遺伝的アルゴリズムを用いた適正解探索方法であって、
初期の複数の個体を生成して処理の対象となる複数の対象個体とする初期個体生成工程と、
前記初期個体生成工程で生成された前記複数の対象個体についての遺伝的情報を情報記憶部に記憶する情報記憶工程と、
前記複数の対象個体の少なくとも一部について前記淘汰、突然変異及び交叉のうち少なくともいずれか１つの遺伝的操作をすることにより、既存の複数の対象個体から新たな複数の対象個体を生成する遺伝的操作工程と、
前記遺伝的操作工程で生成された前記新たな複数の対象個体についての遺伝的情報を前記情報記憶部に書き込む情報書込工程と、
前記初期の複数の個体及び前記新たな複数の対象個体がそれぞれ有する前記遺伝子配列に基づいて前記問題の解の候補に対応する適応値を計算する適応値計算工程と、
前記新たな複数の対象個体に対して前記遺伝的操作工程及び前記適応値計算工程を繰り返させる再操作工程と、
複数回繰り返される前記適応値計算工程において得られた複数の前記適応値のうち最も適応度の高いものの少なくとも１つの値を、前記問題の解の候補の１つとする解候補抽出工程と、
を有し、
前記情報記憶部は、前記複数の対象個体についての前記遺伝的情報の１つとして、各個体が前記遺伝的操作工程における遺伝的操作の対象及び前記適応値計算工程における前記適応値の計算の対象となっている生の状態と、前記遺伝的操作の対象及び前記適応値の計算の対象となっていない死の状態とのうちいずれの状態にあるかについての情報を含む、適正解探索方法。
【請求項２】
前記複数の対象個体は、所定値の寿命をそれぞれ有し、
前記複数の対象個体について前記遺伝的操作工程に対応して世代を更新するとともに前記寿命を減少させる世代更新工程をさらに有する、請求項１に記載の適正解探索方法。
【請求項３】
前記複数の対象個体の前記寿命は、各個体の有する前記適応値に応じてそれぞれ異なる、請求項２に記載の適正解探索方法。
【請求項４】
前記初期個体生成工程及び前記遺伝的操作工程において、前記複数の対象個体を所定数まで保有可能な繁殖用エリアが単数又は複数用意されている、請求項１に記載の適正解探索方法。
【請求項５】
前記繁殖用エリアは、複数の階層で構成され、かつ、当該複数の階層には相対的に上下の順位付けがあり、前記繁殖用エリアのうち上位の階層に属する個体が、下位の階層に属する個体を捕食によって前記死の状態に至らせる捕食工程を前記遺伝的操作工程の一態様とする、請求項４に記載の適正解探索方法。
【請求項６】
前記繁殖用エリアのうち異なる階層に属する個体同士は交叉せず、同じ階層に属する個体同士間でのみ交叉する、請求項５に記載の適正解探索方法。
【請求項７】
前記捕食工程において、前記上位の階層の一の個体が前記下位の階層の一の個体の捕食に成功した場合には、捕食された当該下位の階層の一の個体が前記死の状態となり、捕食に失敗した場合には、捕食に失敗した当該上位の階層の一の個体が前記死の状態となる、請求項５に記載の適正解探索方法。
【請求項８】
前記捕食工程において、捕食の成否は、各個体の有する前記適応値の適応度によって定まる、請求項７に記載の適正解探索方法。
【請求項９】
前記繁殖用エリアにおいて、一の階層に属する個体の数が所定の生存限界数以下に減少した場合に、当該一の階層に属する個体の数を所定の生存可能数まで増加させる絶滅回避工程をさらに備える、請求項５に記載の適正解探索方法。
【請求項１０】
前記適応値計算工程を繰り返すことで得られた全ての適応値を前記情報記憶部に記録する歴代適応値記録工程をさらに有し、
前記歴代適応値記録工程において記録された前記全ての適応値のうち、最も適応度の高いものを前記問題の解の候補とする、請求項１に記載の適正解探索方法。
【請求項１１】
前記繁殖用エリアを構成する前記複数の階層に属する個体の前記適応値の平均値を基準として、一の階層に属する個体と他の階層に属する個体との全入替をする階層交換工程をさらに有する、請求項１に記載の適正解探索方法。
【請求項１２】
前記問題の解の候補の決定後、新たな問題を設定するとともに、先の解の候補の決定時における前記複数の対象個体を、前記初期個体生成工程で生成された前記初期の複数の個体として用いる新規探索設定工程をさらに有する、請求項１に記載の適正解探索方法。
【請求項１３】
前記複数の対象個体は、雌雄の別をそれぞれ有しており、前記遺伝的操作工程は、雄性淘汰を含む、請求項１に記載の適正解探索方法。
【請求項１４】
問題の解の候補の要素を遺伝子配列としてそれぞれ有する複数の個体について、淘汰、突然変異及び交叉を含む遺伝的操作を行う遺伝的アルゴリズムを用いた適正解探索装置であって、
初期の複数の個体を生成して処理の対象となる複数の対象個体とする初期個体生成部と、
前記前記複数の対象個体についての遺伝的情報を記憶する情報記憶部と、
前記複数の対象個体の少なくとも一部について前記淘汰、突然変異及び交叉のうち少なくともいずれか１つの遺伝的操作をすることにより、既存の複数の対象個体から新たな複数の対象個体を生成する遺伝的操作部と、
前記遺伝的操作部で生成された前記新たな複数の対象個体についての遺伝的情報を前記情報記憶部に書き込む情報書込部と、
前記初期の複数の個体及び前記新たな複数の対象個体がそれぞれ有する前記遺伝子配列に基づいて前記問題の解の候補に対応する適応値を計算する適応値計算部と、
前記新たな複数の対象個体に対して前記遺伝的操作部及び前記適応値計算部での処理を繰り返させる再操作部と、
複数回処理を繰り返されることで前記適応値計算部において得られた複数の前記適応値のうち最も適応度の高いものの少なくとも１つの値を、前記問題の解の候補の１つとして格納する解候補格納部と、
を有し、
前記情報記憶部は、前記複数の個体についての前記遺伝的情報の１つとして、各個体が前記遺伝的操作部における遺伝的操作の対象及び前記適応値計算部における前記適応値の計算の対象となっている生の状態と、前記遺伝的操作の対象及び前記適応値の計算の対象となっていない死の状態とのうちいずれの状態にあるかについての情報を含む、適正解探索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば事案の効率的な処理を見出すための問題に対して解の候補の要素から適正と考えられる解を探索するための適正解探索方法及び適正解探索装置に関する。
【背景技術】
【０００２】
設定された問題について最適解を探索するための方法の１つとして、ニューラルネットワーク（以下，ＮＮとする。）を用いたものが一般的に知られている。ＮＮは、脳細胞をモデル化したものを複数配置し、最適解を解くものである。【０００３】
また、別の方法として、遺伝的アルゴリズム(以下，一般的ＧＡとする。）を用いたものが種々知られている（例えば非特許文献１、２等参照）。一般的ＧＡは、問題の対象を遺伝子の形で表現し、交配、突然変異を施して遺伝子を進化させるもので、進化的計算の一種である。この一般的ＧＡは、ダーウィン進化説をベースに構築されたアルゴリズムである。【０００４】
しかしながら、ＮＮでは、探索方法が、線形的な最急降下法であるため、探索開始位置への依存性が強く探索開始位置の近傍のミニマムポイントに収束するといういわゆるローカルミニマムに陥って最適解又はこれに近い値までたどり着かないことが多いという問題点がある。【０００５】
また、上記非特許文献１等に示す一般的ＧＡでは、特定の種のみに収束してしまい、必ずしも最適解ではないところまでしか進化させられない傾向があり、ＮＮと形は違うがローカルミニマムの問題を抱えている。つまり、進化の過程で遺伝子の種類が少なくなり、最適解以外の大きく離れた解に収束してしまうことがある。また、一般的ＧＡでは、一つの問題を探索し解を出すと、遺伝子すなわち個体の情報が偏ったもので寡占状態に陥り種の多様性を持っていないため、そのままの遺伝子集団を別の問題に適応させることができない。従って、別の問題に取り組む場合には、再度初期化をして問題を解かなければならない。このため、例えば最適解を求めようとする問題の形質が時系列的に変化するようなものである場合には迅速に対応できない。
【先行技術文献】
【特許文献】
【０００６】
【非特許文献１】情報処理学会論文誌：数理モデル化と応用  近傍培養型遺伝的アルゴリズムによる多目的最適化  ｐｐ．１８３−１９８、Ｎｏｖ．２００２
【非特許文献２】情報処理学会論文誌：数理モデル化と応用  多目的遺伝的アルゴリズムにおける近傍交叉の効果  ｐｐ．４０−４８、Ｆｅｂ．２００７
【発明の概要】
【０００７】
本発明は、ローカルミニマムに陥ることを回避し、かつ、時系列的に変化するような問題についても柔軟に対応できる適正解探索方法及び適正解探索装置を提供することを目的とする。
【０００８】
上記課題を解決するため、本発明に係る適正解探索方法は、問題の解の候補の要素を遺伝子配列としてそれぞれ有する複数の個体について、淘汰、突然変異及び交叉を含む遺伝的操作を行う遺伝的アルゴリズムを用いた適正解探索方法であって、（ａ）初期の複数の個体を生成して処理の対象となる複数の対象個体とする初期個体生成工程と、（ｂ）初期個体生成工程で生成された複数の対象個体についての遺伝的情報を情報記憶部に記憶する情報記憶工程と、（ｃ）複数の対象個体の少なくとも一部について淘汰、突然変異及び交叉のうち少なくともいずれか１つの遺伝的操作をすることにより、既存の複数の対象個体から新たな複数の対象個体を生成する遺伝的操作工程と、（ｄ）遺伝的操作工程で生成された新たな複数の対象個体についての遺伝的情報を情報記憶部に書き込む情報書込工程と、（ｅ）初期の複数の個体及び新たな複数の対象個体がそれぞれ有する遺伝子配列に基づいて問題の解の候補に対応する適応値を計算する適応値計算工程と、（ｆ）新たな複数の対象個体に対して遺伝的操作工程及び適応値計算工程を繰り返させる再操作工程と、（ｇ）複数回繰り返される適応値計算工程において得られた複数の適応値のうち最も適応度の高いものの少なくとも１つの値を、問題の解の候補の１つとする解候補抽出工程と、を有し、（ｈ）情報記憶部は、複数の対象個体についての遺伝的情報の１つとして、各個体が遺伝的操作工程における遺伝的操作の対象及び適応値計算工程における適応値の計算の対象となっている生の状態と、遺伝的操作の対象及び適応値の計算の対象となっていない死の状態とのうちいずれの状態にあるかについての情報を含む。
【０００９】
ここで、個体とは、問題の解の候補の要素を遺伝子配列で表現したものである。また、複数の個体についての遺伝的情報とは、各個体についての生又は死の状態についての情報のほか、各個体の有する遺伝子配列や、遺伝子配列から算出される適応値といった各個体に関する種々の情報を含むものである。また、遺伝子配列とは、生物界における遺伝子が有する染色体をモデル化したもの等を意味し、この配列順が、問題の解の候補の要素となる。問題の解は、複数の要素からなっていて、複数の個体の適応値の優劣で評価されるものである。また、遺伝的操作について、淘汰とは、複数の個体のうち環境などによりよく適合するものが生存を続けそうでないものが滅びるという生物界における自然淘汰をモデル化したもので、適応値等の遺伝的情報にもとづいて複数の個体のうち諸条件を満たすものを残し満たさないものを排除する操作である。突然変異とは、生物界における遺伝子の突然変異をモデル化したもので、個体の遺伝子配列の一部を変化させる操作である。交叉とは、生物が交配によって子孫を残すことをモデル化したもので、複数の個体の相互間で遺伝子配列の一部を入れ換える操作である。
【００１０】
上記適正解探索方法によれば、複数の個体についての遺伝的情報の１つとして、生の状態と死の状態とについての情報が含まれている。これにより、各個体は、比較的良好な適応値（適応度）を持つものであっても、良好でない適応値（適応度）を持つものであっても、いずれ死を迎えることで、結果的に淘汰される。これにより、例えば比較的良好ではあるが適正解とは言えない適応値を持つ個体によって寡占状態となることがなく、設定された問題の適正解を探索する上でローカルミニマムに陥ることが回避される。また、良好な適応値を持つものにもそうでないものにも生死があることで、個体のもつ情報の多様性を確保でき、１つの問題の解の探索の後、新たな問題を設定するために各パラメータ等を修正すれば、個体についての初期の設定を再度することなく当該新たな問題の解の探索を行うことができるので、時系列的に変化するような問題についても対応できる。
【００１１】
本発明の具体的な態様又は観点では、複数の対象個体が、所定値の寿命をそれぞれ有し、複数の対象個体について遺伝的操作工程に対応して世代を更新するとともに寿命を減少させる世代更新工程をさらに有する。この場合、全ての個体について寿命があり、その寿命は、１世代毎に１ずつ減る。寿命をまっとうすれば、適応値の優劣に関係なく死に、死んだものは、交叉や突然変異等はできないことになる。これにより、特定の偏った遺伝子を有する個体のみが残り続けることを回避し、個体のもつ情報の多様性を確保することができる。
【００１２】
本発明の別の態様では、複数の対象個体の寿命が、各個体の有する適応値に応じてそれぞれ異なる。この場合、例えば比較的良好な適応値を持つ個体の寿命を比較的長くして、有利な状態とすることができる。これにより、全ての個体に寿命があることによって全体としての個体の多様性を保ちつつも、比較的良好な遺伝子配列を有する個体を優先的に残すことができるので、比較的早期に問題の解の候補を探索できる。
【００１３】
本発明のさらに別の態様では、初期個体生成工程及び遺伝的操作工程において、複数の対象個体を所定数まで保有可能な繁殖用エリアが単数又は複数用意されている。この場合、繁殖用エリアにおいて、複数の個体を確保することができる。特に、繁殖用エリアを複数用意して複数の個体を異なる階層に分類して取り扱うことで、自然界における食物連鎖を応用した探索システムの構築が可能となる。
【００１４】
本発明のさらに別の態様では、繁殖用エリアが、複数の階層で構成され、かつ、当該複数の階層には相対的に上下の順位付けがあり、繁殖用エリアのうち上位の階層に属する個体が、下位の階層に属する個体を捕食によって死の状態に至らせる捕食工程を遺伝的操作工程の一態様とする。この場合、捕食工程によって、捕食と被食すなわち喰う側と喰われる側とが存在するという自然界の関係を応用した探索システムの構築が可能となる。
【００１５】
本発明のさらに別の態様では、繁殖用エリアのうち異なる階層に属する個体同士は交叉せず、同じ階層に属する個体同士間でのみ交叉する。この場合、限られた種の間でのみで交叉を行う自然界の状況を応用したものとすることができる。環境に適応して生命の存続を図ろうとする自然界の状況を応用することで、求めるべき適正解に早期に近づくことができる。
【００１６】
本発明のさらに別の態様では、捕食工程において、上位の階層の一の個体が下位の階層の一の個体の捕食に成功した場合には、捕食された当該下位の階層の一の個体が死の状態となり、捕食に失敗した場合には、捕食に失敗した当該上位の階層の一の個体が死の状態となる。この場合、捕食工程において、下位の階層の個体数は、捕食されることで減少し、上位の階層の個体数は、捕食できないことで減少することで、捕食の成否が生死を分けるという自然界の状況を応用したものになる。
【００１７】
本発明のさらに別の態様では、捕食工程において、捕食の成否は、各個体の有する適応値の適応度によって定まる。この場合、例えばより適応度が高いものが勝者となり、敗者は餌となるので、自然界の状況を応用したものになる。
【００１８】
本発明のさらに別の態様では、繁殖用エリアにおいて、一の階層に属する個体の数が所定の生存限界数以下に減少した場合に、当該一の階層に属する個体の数を所定の生存可能数まで増加させる絶滅回避工程をさらに備える。この場合、当該一の階層に属する個体の数及び多様性を維持でき、また、自然界の生物爆発をモデル化したものになる。
【００１９】
本発明のさらに別の態様では、適応値計算工程を繰り返すことで得られた全ての適応値を情報記憶部に記録する歴代適応値記録工程をさらに有し、歴代適応値記録工程において記録された全ての適応値のうち、最も適応度の高いものを問題の解の候補とする。この場合、多様性のある個体の中から最も適すると考えられる適応値を問題の解の候補として選択することができる。
【００２０】
本発明のさらに別の態様では、繁殖用エリアを構成する複数の階層に属する個体の適応値の平均値を基準として、一の階層に属する個体と他の階層に属する個体との全入替をする階層交換工程をさらに有する。この場合、喰う側と喰われる側との立場が逆転するという革命的な現象を組み込んだものになる。このような革命的な現象は、自然界にも見られるものであり、これを応用したものになる。
【００２１】
本発明のさらに別の態様では、問題の解の候補の決定後、新たな問題を設定するとともに、先の解の候補の決定時における複数の対象個体を、初期個体生成工程で生成された初期の複数の個体として用いる新規探索設定工程をさらに有する。この場合、１つの問題の解の候補の探索後、新たな問題の解の探索を行うという問題の形質が時系列的に変化するようなものにおいて、再度複数の個体についての初期の設定をすることなく新たな問題に取り組むことができる。
【００２２】
本発明のさらに別の態様では、複数の対象個体は、雌雄の別をそれぞれ有しており、遺伝的操作工程は、雄性淘汰を含む。ここで、雄性淘汰とは、自然界において例えば雌の嗜好に合う様に雄の遺伝子が方向付けされるといった現象をモデル化したものである。この場合、例えば対象個体のうち雄の個体同士で適応値を比較することで生存競争を行わせて、自然界における雄性淘汰をモデル化したものにできる。
【００２３】
上記課題を解決するため、本発明に係る適正解探索装置は、問題の解の候補の要素を遺伝子配列としてそれぞれ有する複数の個体について、淘汰、突然変異及び交叉を含む遺伝的操作を行う遺伝的アルゴリズムを用いた適正解探索装置であって、（ａ）初期の複数の個体を生成して処理の対象となる複数の対象個体とする初期個体生成部と、（ｂ）複数の対象個体についての遺伝的情報を記憶する情報記憶部と、（ｃ）複数の対象個体の少なくとも一部について淘汰、突然変異及び交叉のうち少なくともいずれか１つの遺伝的操作をすることにより、既存の複数の対象個体から新たな複数の対象個体を生成する遺伝的操作部と、（ｄ）遺伝的操作部で生成された新たな複数の対象個体についての遺伝的情報を情報記憶部に書き込む情報書込部と、（ｅ）初期の複数の個体及び新たな複数の対象個体がそれぞれ有する遺伝子配列に基づいて問題の解の候補に対応する適応値を計算する適応値計算部と、（ｆ）新たな複数の対象個体に対して遺伝的操作部及び適応値計算部での処理を繰り返させる再操作部と、（ｇ）複数回処理を繰り返されることで適応値計算部において得られた複数の適応値のうち最も適応度の高いものの少なくとも１つの値を、問題の解の候補の１つして格納する解候補格納部と、を有し、（ｈ）情報記憶部が、複数の個体についての遺伝的情報の１つとして、各個体が遺伝的操作部における遺伝的操作の対象及び適応値計算部における適応値の計算の対象となっている生の状態と、遺伝的操作の対象及び適応値の計算の対象となっていない死の状態とのうちいずれの状態にあるかについての情報を含む。
【００２４】
上記適正解探索装置によれば複数の個体についての遺伝的情報の１つとして、生の状態と死の状態とについての情報が含まれている。これにより、各個体は、比較的良好な適応値（適応度）を持つものであっても、良好でない適応値（適応度）を持つものであっても、いずれ死を迎えることで、結果的に淘汰される。これにより、例えば比較的良好ではあるが適正解とは言えない適応値を持つ個体によって寡占状態となることがなく、ローカルミニマムに陥ることが回避される。また、良好な適応値を持つものにもそうでないものにも生死があることで、個体のもつ情報の多様性が確保でき、１つの問題の解の探索の後、新たな問題の解の探索を行うという時系列的に変化するような問題についても対応できる。
【図面の簡単な説明】
【００２５】
【図１】図１Ａは、第１実施形態に係る適正解探索装置の構造を概念的に説明するブロック図であり、図１Ｂは、複数の個体の情報管理の様子を概念的に示す図であり、図１Ｃは、１つの個体に含まれる情報について概念的に示す図である。
【図２】記憶装置内のメモリマップについて概念的に示す図である。
【図３】図１の適正解探索装置を用いた適正解探索方法を概念的に説明するフローチャートである。
【図４】図３に示す適正解探索方法のうち、階層交換の工程について概念的に説明するフローチャートである。
【図５】図１の適正解探索装置を用いた適正解探索方法を概念的に説明するフローチャートである。
【図６】図１の適正解探索装置を用いた適正解探索方法を概念的に説明するフローチャートである。
【図７】図１の適正解探索装置を用いた適正解探索方法を概念的に説明するフローチャートである。
【図８】図１の適正解探索装置を用いた適正解探索方法を概念的に説明するフローチャートである。
【図９】図９Ａ〜９Ｄは、第１の方法による交叉について説明する図であり、図９Ｅは、第２の方法による交叉について説明する図である。
【図１０】実施形態に係る適正解探索方法を用いた一実施例の結果を示すグラフである。
【図１１】図１１Ａ及び１１Ｂは、比較例の一実施例の結果を示すグラフである。
【図１２】第２実施形態に係る適正解探索方法を概念的に説明するフローチャートである。
【発明を実施するための形態】
【００２６】
〔第１実施形態〕
以下、本発明の第１実施形態に係る適正解探索方法及び適正解探索装置について図面を参照しつつ説明する。
【００２７】
図１Ａに示すように、本実施形態に係る適正解探索装置１００は、一般的なコンピュータと同様に、ＣＰＵ１０、入力装置１１、表示装置１２、記憶装置１３及びバス５０を備えている。
【００２８】
ＣＰＵ１０は、バス５０を介して、入力装置１１、表示装置１２や記憶装置１３との間で相互にデータの授受が可能になっている。また、ＣＰＵ１０は、入力装置１１からのオペレーターの指示に基づいて、記憶装置１３から所定のプログラムやデータを読み出し、これらプログラム及びデータに基づく各種処理を実行する。
【００２９】
具体的に説明すると、ＣＰＵ１０は、適正解探索のためのプログラムにおいて、入力装置１１からの指示に基づいて、記憶装置１３等に入力された問題について、遺伝的アルゴリズムによって、設定された問題の解の候補を探索して出力することができる。
【００３０】
入力装置１１は、キーボード、プリンタ等から構成され、適正解探索装置１００を操作するオペレーターの意思を反映した指令信号をＣＰＵ１０に出力するとともに、ＣＰＵ１０からの指示に従ってこれによる処理結果を適当なフォーマットとした情報を例えばプリントアウトする。
【００３１】
表示装置１２は、ＣＰＵ１０から入力されるデータに基づいて駆動信号を生成する表示駆動回路と、表示駆動回路から入力される駆動信号に基づいて必要な表示を行う画像表示部等とにより構成され、ＣＰＵ１０からの指令信号に基づいて必要な表示を行う。
【００３２】
記憶装置１３は、適正解探索装置１００を動作させる各種プログラム等を複数記憶しているプログラム領域と、入力指示、入力データ、処理結果等を一時格納するデータ領域とを備える。記憶装置１３は、対象として設定される問題を適正解探索装置１００で探索できるように適合させるための各パラメータや、設定された問題の解を探索するために用意される遺伝子配列を有する複数の個体の遺伝的情報等の各種情報を格納するとともに、図１Ｂに示す複数の個体ＩＮの各種情報について交叉や突然変異等の遺伝的操作工程を行うプログラムに応じて適宜書換えられたものを格納していく情報記憶部として機能している。特に、本実施形態では、図１Ｃに示すように、個体ＩＮは、自己のＩＤのほか遺伝子配列の配列情報といった遺伝的情報ＧＩの１つとして、各個体が生の状態と死の状態とのうちいずれの状態にあるかについての情報をエリア２１ａに含んでいる。ここで、生の状態とは、遺伝的操作工程における遺伝的操作の対象や適応値の計算の対象となっていることを言い、死の状態とは、遺伝的操作工程における遺伝的操作の対象にも適応値の計算の対象にもなっていないことを言う。つまり、本実施形態では、各個体ＩＮは、生の状態のときのみ適正解探索の対象となっており、いずれ死の状態となることで対象から外れていくという構成を取ることで、従来の一般的ＧＡには見られない、個体の多様性を持たせつつ、適正解を比較的早期に導き出すことを可能としている。
【００３３】
ここで、適正解探索のためのプログラムによって探索を行う対象として設定される問題について説明する。本実施形態では、一例として、ＴＳＰ（巡回セールスマン問題）を取り上げるものとする。つまり、設定された問題として入力されるべきパラメータは、ＴＳＰにおける都市数と都市間距離であり、全ての都市間を巡るにあたっての最短経路を求めることが目的となる。本実施形態において、遺伝子配列をそれぞれ有する複数の個体において、全ての個体に共通する遺伝子配列の配列数が都市数に対応し、各個体の遺伝子配列の配列順が都市を巡回する順序に対応する。また、各配列順に巡回した場合の経路の長さを各個体の適応値とする。従って、以上の設定の場合、適応値が小さい個体ほど適応度の高いものということになる。また、ここでは、上記のようにＴＳＰに絞って説明をするが、一般的ＧＡにおいて対象となる問題はＴＳＰに限らず種々のものがあり、本実施形態の適正解探索装置１００を用いた適正解探索方法を用いることにより、種々の問題に対応可能である。
【００３４】
図２は、適正解探索装置１００のうち、記憶装置１３において格納される各種データやプログラムのメモリマップを示している。つまり、ＣＰＵ１０は、各種の動作を行うに際して必要となるデータや各種プログラムを記憶装置１３から適宜読み出して実行している。
【００３５】
まず、図２において、記憶装置１３は、各種データを格納するデータ領域Ｄ１と、各種プログラムを格納するプログラム領域Ｄ２とを有している。データ領域Ｄ１は、問題に設定された条件を含む初期の情報を格納する初期データ格納領域Ｅ１と、個体についての各種情報を格納する個体データ格納領域Ｅ２と、世代更新とともに増加する世代数をカウントするための世代数カウンタＥ３とを備える。また、プログラム領域Ｄ２は、初期情報を処理するためのプログラム群である初期設定制御部Ｐ１と、各個体の適応値を計算するためのプログラムである適応値（スコア）計算部Ｐ２と、遺伝的アルゴリズムにおける各種動作をするためのプログラム群である遺伝的操作制御部Ｐ３とを備える。ここで、本実施形態では、図１Ｂ及び図２に示すように、一例として、各個体ＩＮの属する繁殖エリアとして、最上位の階層である上位層ＴＲと、中間位の階層である中間層ＭＲと、最下位の階層である下位層ＢＲとの相対的に順位付けられた３つの階層が、個体データ格納領域Ｅ２において用意されているものとする。図１Ｂに示すように、各個体ＩＮでの突然変異、各階層内での個体ＩＮ同士の交叉、あるいは、上位側の階層の個体ＩＮによる下位側の個体ＩＮの捕食である捕食１、捕食２の操作がなされるごとに、個体データ格納領域Ｅ２の内容が書き換えられる。なお、ここでは、各階層ＴＲ，ＭＲ，ＢＲには、個体ＩＮを例えば５０個までそれぞれ保有できるものとする。繁殖エリアを複数用意することで、食物連鎖の関係を模してこれを応用している。また、本実施形態では、階層間で捕食と被食の関係が存することで共進化（Co-evolution）の促進を図っている。ここでは、このような仕組みを用いた解の探索方法をＣＤＳ（Co-evolution Diversity Solution）と呼ぶものとする。
【００３６】
データ領域Ｄ１のうち、まず、初期データ格納領域Ｅ１は、設定される問題（ここではＴＳＰ）についての入力パラメータである個体の遺伝子配列の配列数等の初期設定で定められる各変数や、繁殖エリアの個数、また、各繁殖エリアで所有可能な個体の数についてのデータが格納されるためのデータ領域である。
【００３７】
次に、個体データ格納領域Ｅ２は、上記のように、３つの階層ＴＲ，ＭＲ，ＢＲのいずれかに属するものとなった各個体が個々に有する固有の情報を格納する部分である。個体データ格納領域Ｅ２は、各個体の生死の状態についての情報を格納する生死情報格納領域Ｅ２１と、各個体の有する遺伝配列を格納する遺伝子配列格納領域Ｅ２２と、各個体の適応値（スコア）の情報を格納する適応値（スコア）情報格納領域Ｅ２３と、各個体の寿命についての情報を格納する寿命格納領域Ｅ２４と、各階層の最良適応値である最小適応値についての情報を格納する最良適応値格納領域Ｅ２ｘとを備える。つまり、個体データ格納領域Ｅ２の各領域Ｅ２１〜Ｅ２４，Ｅ２ｘは、図１Ｃに示す各個体ＩＮでの各情報２１ａ〜２４ａ，２ｘａを集積したものである。
【００３８】
最後に、世代数カウンタＥ３は、世代を更新する際に世代数をカウントする。全ての個体は、この世代更新とともに寿命が減少するものとなっている。つまり、寿命格納領域Ｅ２４に記憶されている寿命すなわち年齢が世代更新とともに変化し、寿命が尽きた個体は死の状態となる。ここでは、各個体の寿命が、各個体の有する適応値に応じてそれぞれ異なるものとする。より具体的には、例えば通常の個体の寿命が５年すなわち５回世代更新すると死の状態となるのに対して、比較的良好な適応値を持つすなわち規定の下限値以下の適応値を有する個体は、通常の個体の寿命の３倍の寿命を有するものとする。つまり、寿命が１５年であるものとする。逆に、良好でない適応値を持つすなわち規定の上限値以上の適応値を有する個体の寿命は、通常より短い２年であるものとする。なお、規定の下限値及び上限値については、例えばスコアの平均値で定めることができる。つまり、平均値より高いスコアのもの（適応値が悪いもの）は寿命が短く、平均値より低いスコア（適応値が良いもの）は寿命が長いと定められる。
【００３９】
プログラム領域Ｄ２のうち、まず、初期設定制御部Ｐ１は、初期データを受け付け、当該初期データを各データ領域に格納して初期設定を行うための各種プログラムを含む領域である。このため、初期設定制御部Ｐ１は、オペレーターの操作により入力装置１１を介して入力されるＴＳＰの都市数すなわち個体の遺伝子配列の配列数等の問題を適正解探索装置１００での処理に適合させる各パラメータ等の問題データを読み込むためのプログラムである問題読込部Ｐ１１と、遺伝子配列の情報を有する最初の複数の個体を生成するプログラムである初期遺伝子生成部Ｐ１２と、入力された繁殖エリアの数の情報に基づいて、繁殖エリアを生成するプログラムである繁殖用エリア生成部Ｐ１３と、初期遺伝子生成部Ｐ１２及び繁殖用エリア生成部Ｐ１３で生成された複数の個体と繁殖エリアとを対応付けるすなわち初期の個体がどの繁殖エリアに属すものとするかを定めるプログラムである繁殖用エリアへの個体移植部Ｐ１４とを有する。
【００４０】
次に、適応値計算部Ｐ２は、各個体の適応値を算出するためのプログラムを含む領域である。個体の適応値は、設定された問題の解の探索において直接的に関係するものであり、直接的に解の候補を見つけ出す場合に限らず、種々の指標として随時用いられる。従って、適応値計算部Ｐ２は、必要に応じて種々の工程において適宜読み出されるものとなっている。なお、既述のように、本実施形態では、複数の個体のうち最小のスコアを有するものが最も優秀な適応値を有するものなるが、例えば繁殖エリアごとすなわち各階層ＴＲ，ＭＲ，ＢＲごとに最も優秀な適応値を有するものが探索される。
【００４１】
最後に、遺伝的操作制御部Ｐ３は、各個体についての生死や遺伝子配列の変更、寿命すなわち年齢の変更といった各種操作を行うために必要となるプログラムを含む領域である。遺伝的操作制御部Ｐ３は、各繁殖用エリアでの個体数調整のための間引き処理を行うプログラムである間引き制御部Ｐ３１と、突然変異すなわち遺伝子配列の入れ替えを行うプログラムである突然変異制御部Ｐ３２と、交叉を制御するプログラムである交叉制御部Ｐ３３と、捕食行動を制御するプログラムである捕食行動制御部Ｐ３４と、各階層ＴＲ，ＭＲ，ＢＲのうち捕食される側にある下位側の階層ＭＲ，ＢＲにおいて個体の数が生存限界数以下に減少した場合に、生存可能数まで増加させる絶滅を回避させるためのプログラムである絶滅回避制御部Ｐ３５と、各個体の寿命を制御するプログラムである寿命制御部Ｐ３６と、世代更新をするプログラムである世代更新部Ｐ３７と、適応値（スコア）の平均値を計算するプログラムである適応値（スコア）平均値算出部Ｐ３８と、適応値（スコア）平均値算出部Ｐ３８で算出された結果に基づいて階層の交換を行うか否かの判断をする階層交換制御部Ｐ３９とを備える。なお、交叉制御部Ｐ３３による交叉については、繁殖用エリアである上記３つの階層ＴＲ，ＭＲ，ＢＲのうち異なる階層に属する個体同士は交叉せず、同じ階層に属する個体同士間でのみ交叉するものとしている。上記において、生存限界数の一例としては、各層の全個体数の半数に設定することが考えられる。また、生存可能数の一例としては、個体数を５０個に設定することが考えられる。例えばＴＳＰのシミュレータであれば、ＴＳＰの都市数すなわち個体の遺伝子配列の配列数の５８％以上の個数を生存可能数とすることが望ましい。
【００４２】
ここで、本実施形態では、既述のように、全ての個体に生死があり、かつ、寿命があるということの他にも、いくつかの点において、従来の一般的ＧＡにはない特徴がある。まず、第１に、捕食行動制御部Ｐ３４を有し、属する階層に応じて個体間での捕食行動がある点に特徴がある。これは、上記のように、喰う、喰われる関係によってＣＤＳに特有の共進化の促進を図ることで、より早期に適正解を得ようとするものである。また、第２に、絶滅回避制御部Ｐ３５があり、絶滅しかけた階層の個体が、突然爆発的に増加するという生物爆発の状態を模したものつまり応用・モデル化したものとしている点に特徴がある。これは、いわば見えざる神の手のごときものである。これにより、種の保存及び多様性を保証している。また、第３に、階層交換制御部Ｐ３９があり、各階層ＴＲ，ＭＲ，ＢＲの立場が逆転して、個体の全入替が生じるといういわば革命的現象（Class Change）が起こり得るものとしている。これは、例えば自然界においても、例えば本来肉食獣である熊が雑食性の生き物へ進化し、さらに、熊の一種であるパンダが笹だけを主食にする草食獣となるように、その環境変化に応じて変化を遂げることがあり、これを模したものである。
【００４３】
以下、図１Ａに示す適正解探索装置１００を用いた適正解探索方法の主要な動作について説明する。図３〜図８は、適正解の探索プログラムを抽象化して説明するフローチャートである。なお、以下の動作を行うシステムは、例えば高級言語等(C言語、C++言語、Java（登録商標）言語等)で実装することが可能である。
【００４４】
まず、ＣＰＵ１０は、プログラム領域Ｄ２の初期設定制御部Ｐ１から問題読込部Ｐ１１のプログラムを読み出して、入力装置１１等を介して問題データである各パラメータ等を取り込んでＴＳＰ等の問題を適正解探索装置１００で処理可能となるように適合化させるとともに当該問題データを記憶装置１３の初期データ格納領域Ｅ１に格納する（ステップＳ１）。
【００４５】
次に、ＣＰＵ１０は、初期設定制御部Ｐ１から初期個体生成部である初期遺伝子生成部Ｐ１２のプログラムを読み出して、乱数を用いて初期の複数の個体の遺伝子配列を作成し、初期の個体データを初期データ格納領域Ｅ１に格納する（ステップＳ２：初期個体生成工程）。
【００４６】
次に、ＣＰＵ１０は、適応値計算部Ｐ２及びを読み出して、初期の個体について、初期データ格納領域Ｅ１に格納されている各個体の遺伝子配列のデータに基づいて各個体のスコアすなわち適応値をそれぞれ演算し（ステップＳ３）、スコアに基づいて各個体のソートを行うとともに初期データ格納領域Ｅ１に各個体の各種情報を格納する（ステップＳ４：情報記憶工程）。次に、ＣＰＵ１０は、初期設定制御部Ｐ１から繁殖用エリア生成部Ｐ１３及び繁殖用エリアへの個体移植部Ｐ１４を読み出して、ソートされた個体を、個体データ格納領域Ｅ２上に分配された各繁殖用エリア、すなわち、最上位の階層である上位層ＴＲと、中間位の階層である中間層ＭＲと、最下位の階層である下位層ＢＲとの３階層に振り分けることで、各階層ＴＲ，ＭＲ，ＢＲに初期値を入れる（ステップＳ５）。具体的に例えば、生成された各個体は、配属された各階層ＴＲ，ＭＲ，ＢＲにおいて、生死については生の状態にあるとして生死情報格納領域Ｅ２１に格納され、遺伝子配列の配列順が遺伝子配列格納領域Ｅ２２に格納され、適応値が適応値（スコア）情報格納領域Ｅ２３に格納され、寿命が２年、５年又は１５年として寿命（年齢）格納領域Ｅ２４に格納される。以上の設定により、生成された初期の複数の個体が以後の処理の対象となる複数の対象個体として扱われるものとなる。また、ここでは、一例として、初期の対象個体のうちスコアの上位２０％を占める個体が、上位層ＴＲに属し、中位３０％を占める個体が、中間層ＭＲに属し、下位５０％を占める個体が、下位層ＢＲに属するものとする。例えば、初期に生成された個体の個体数を１００とすると、適応値の小さい順に上位２０個が上位層ＴＲに属し、次の３０個が中間層ＭＲに属し、残りの５０個が下位層ＢＲに属することになる。これらの個体はいずれも生の状態にあることになる。一方、各繁殖エリアは、５０個ずつ所有可能であるので、上位層ＴＲのエリアのうち埋まっていない３０個と中間層ＭＲのエリアのうち埋まっていない２０個とについては、死の状態と実質的に等しい状態にあるものとしてスタートすることになる。なお、図３〜図８に示すように、適正解探索装置１００の動作は、以後、ステップＳ７からステップＳ７１に示す遺伝的操作を含む各種の動作を規定の回数繰り返すものとなっている。これにより、初期の複数の対象個体から新たな複数の対象個体が生成され、生成された複数の対象個体からさらに新たな複数の対象個体が形成されていく。
【００４７】
ここで、ＣＰＵ１０は、本プログラムによる推移を示すための各種データの採取を行う（ステップＳ６，Ｓ７）。具体的には、各階層ＴＲ，ＭＲ，ＢＲについてスコアの平均すなわちアベレージを算出してデータを格納するとともに（ステップＳ６）、その分散も算出してデータを格納する（ステップＳ７）。なお、これらのデータは、解の探索の推移を検証する（例えば図１０参照）ために算出されるものであり、解の探索そのものには用いない。
【００４８】
次に、ＣＰＵ１０は、各階層ＴＲ，ＭＲ，ＢＲ間での階層の交換をすべきか否かを判断するための処理を行う（ステップＳ８〜Ｓ１０）。つまり、階層交換制御部Ｐ３９を用いた処理を行うか否かを判断する。具体的には、まず、ＣＰＵ１０は、各対象個体の適応値（スコア）平均値算出部Ｐ３８を読み出して、各階層ＴＲ，ＭＲ，ＢＲでのスコア（適応値）のアベレージ（平均値）を算出するとともに、当該アベレージの世代間での移動平均を採取する（ステップＳ８）。つまり、ステップＳ８においてスコアのアベレージの変遷を確認し、これを階層の交換をするという革命的なこと（Class Change）が生じるべき状況にあるか否かの判断基準の１つとする。ステップＳ８において世代間での移動平均の大小を確認すると、次に、ＣＰＵ１０は、世代数カウンタＥ３を読み出して、現在の世代数が、６０以上でかつ６０で割り切れるか否かを確認する（ステップＳ９）。つまり、ステップＳ９において、現在の世代数や移動平均の大小から革命的なことが生じるべきタイミングにあるか否かを判断する。ステップＳ９において、世代数が６０以上でかつ６０で割り切れると判断されると（ステップＳ９：Ｙｅｓ）、ＣＰＵ１０は、階層交換制御部Ｐ３９を読み出して階層交換のための処理を行う（ステップＳ１０：階層交換工程）。一方、ステップＳ９において、世代数が６０以上でかつ６０で割り切れるものではないと判断されると（ステップＳ９：Ｎｏ）、階層交換のための処理を行うことなく次段の処理（図５参照）に移行する。なお、ステップＳ９において、世代数が６０以上でかつ６０で割り切れる場合であっても、移動平均の値が所定の条件を満たさない場合には、ＣＰＵ１０は、階層交換のための処理を行わずに次段の処理に移行するものとしてもよい。
【００４９】
ＣＰＵ１０は、ステップＳ９において階層交換のための処理を行うと判断すると、図４に示すように、ステップＳ１０の階層交換工程として、６種類の場合についての判断及び処理の動作を行う。本実施形態の場合、３つの階層ＴＲ，ＭＲ，ＢＲが存在するため、これらの上下関係のパターンが６通り考え得るためである。まず、ステップＳ１０の最初のステップとして、現状の勢力関係が正しいか否かの判断をする。具体的には、下位層ＢＲのスコア平均値（アベレージ）が中間層ＭＲのスコア平均値（アベレージ）以上であるかを確認し、かつ、中間層ＭＲのスコア平均値（アベレージ）が上位層ＴＲのスコア平均値（アベレージ）以上であるかを確認する（ステップ１０１ａ）。ステップ１０１ａにおいて、各スコア平均値の大小関係が上記のとおりである場合には（ステップ１０１ａ：Ｙｅｓ）、ＣＰＵ１０は、各階層間での勢力関係は変化していないものと判断し、現状の上下関係を維持する（ステップＳ１０２ａ）。
【００５０】
次に、ＣＰＵ１０は、ステップ１０１ａに示す関係が満たされていないと判断すると（ステップ１０１ａ：Ｎｏ）、別の勢力関係となっているかの判断をする。具体的には、中間層ＭＲのスコア平均値が下位層ＢＲのスコア平均値以上であるかを確認し、かつ、下位層ＢＲのスコア平均値が上位層ＴＲのスコア平均値以上であるかを確認する（ステップ１０１ｂ）。ステップ１０１ｂにおいて、各スコア平均値の大小関係が上記のとおりである場合には（ステップ１０１ｂ：Ｙｅｓ）、ＣＰＵ１０は、中間層ＭＲと下位層ＢＲとでの勢力関係が逆転したものと判断し、中間層ＭＲと下位層ＢＲとの個体のデータの全入替を行う（ステップＳ１０２ｂ）。
【００５１】
なお、上記ステップＳ１０２ａの処理が行われた場合には、ステップ１０１ｂにおいて必ずＮｏと判断されるため、ステップＳ１０２ｂの処理がされることはない。
【００５２】
次に、ＣＰＵ１０は、ステップ１０１ｂに示す関係が満たされていないと判断すると（ステップ１０１ｂ：Ｎｏ）、別の勢力関係となっているかの判断をする。具体的には、下位層ＢＲのスコア平均値が上位層ＴＲのスコア平均値以上であるかを確認し、かつ、上位層ＴＲのスコア平均値が中間層ＭＲのスコア平均値以上であるかを確認する（ステップ１０１ｃ）。ステップ１０１ｃにおいて、各スコア平均値の大小関係が上記のとおりである場合には（ステップ１０１ｃ：Ｙｅｓ）、ＣＰＵ１０は、上位層ＴＲと中間層ＭＲとでの勢力関係が逆転したものと判断し、上位層ＴＲと中間層ＭＲとの個体のデータの全入替を行う（ステップＳ１０２ｃ）。
【００５３】
なお、上記ステップＳ１０２ａ，１０２ｂの処理が行われた場合には、ステップ１０１ｃにおいて必ずＮｏと判断されるため、ステップＳ１０２ｃの処理がされることはない。
【００５４】
次に、ＣＰＵ１０は、ステップ１０１ｃに示す関係が満たされていないと判断すると（ステップ１０１ｃ：Ｎｏ）、別の勢力関係となっているかの判断をする。具体的には、中間層ＭＲのスコア平均値が上位層ＴＲのスコア平均値以上であるかを確認し、かつ、上位層ＴＲのスコア平均値が下位層ＢＲのスコア平均値以上であるかを確認する（ステップ１０１ｄ）。ステップ１０１ｄにおいて、各スコア平均値の大小関係が上記のとおりである場合には（ステップ１０１ｄ：Ｙｅｓ）、ＣＰＵ１０は、各階層ＴＲ，ＭＲ，ＢＲについて、下位層ＢＲであったものが最上位の階層となり、上位層ＴＲであったものが中間位の階層となり、中間層ＭＲであったものが最下位の階層となるように勢力関係が逆転したものと判断し、各階層ＴＲ，ＭＲ，ＢＲの各個体のデータの全入替を行う（ステップＳ１０２ｃ）。つまり、下位層ＢＲの個体を上位層ＴＲの個体と全入替して下位層ＢＲであった個体が最上位の階層に属するものとし、上位層ＴＲの個体を中間層ＭＲの個体と全入替して上位層ＴＲであった個体が中間位の階層に属するものとし、中間層ＭＲの個体を下位層ＢＲの個体と全入替して中間層ＭＲであった個体が最下位の階層に属するものとする。
【００５５】
なお、上記ステップＳ１０２ａ〜１０２ｃの処理が行われた場合には、ステップ１０１ｄにおいて必ずＮｏと判断されるため、ステップＳ１０２ｄの処理がされることはない。
【００５６】
次に、ＣＰＵ１０は、ステップ１０１ｄに示す関係が満たされていないと判断すると（ステップ１０１ｄ：Ｎｏ）、別の勢力関係となっているかの判断をする。具体的には、上位層ＴＲのスコア平均値が下位層ＢＲのスコア平均値以上であるかを確認し、かつ、下位層ＢＲのスコア平均値が中間層ＭＲのスコア平均値以上であるかを確認する（ステップ１０１ｅ）。ステップ１０１ｅにおいて、各スコア平均値の大小関係が上記のとおりである場合には（ステップ１０１ｅ：Ｙｅｓ）、ＣＰＵ１０は、各階層ＴＲ，ＭＲ，ＢＲについて、下位層ＢＲであったものが中間位の階層となり、中間層ＭＲであったものが最上位の階層となり、上位層ＴＲであったものが最下位の階層となるように勢力関係が逆転したものと判断し、各階層ＴＲ，ＭＲ，ＢＲの各個体のデータの全入替を行う（ステップＳ１０２ｅ）。つまり、下位層ＢＲの個体を中間層ＭＲの個体と全入替して下位層ＢＲであった個体が中間位の階層に属するものとし、中間層ＭＲの個体を上位層ＴＲの個体と全入替して中間層ＭＲであった個体が最上位の階層に属するものとし、上位層ＴＲの個体を下位層ＢＲの個体と全入替して上位層ＴＲであった個体が最下位の階層に属するものとする。
【００５７】
なお、上記ステップＳ１０２ａ〜１０２ｄの処理が行われた場合には、ステップ１０１ｅにおいて必ずＮｏと判断されるため、ステップＳ１０２ｅの処理がされることはない。
【００５８】
次に、ＣＰＵ１０は、ステップ１０１ｅに示す関係が満たされていないと判断すると（ステップ１０１ｅ：Ｎｏ）、別の勢力関係となっているかの判断をする。具体的には、上位層ＴＲのスコア平均値が中間層ＭＲのスコア平均値以上であるかを確認し、かつ、中間層ＭＲのスコア平均値が下位層ＢＲのスコア平均値以上であるかを確認する（ステップ１０１ｆ）。ステップ１０１ｆにおいて、各スコア平均値の大小関係が上記のとおりである場合には（ステップ１０１ｆ：Ｙｅｓ）、ＣＰＵ１０は、上位層ＴＲと下位層ＢＲとでの勢力関係が逆転したものと判断し、上位層ＴＲと下位層ＢＲとの個体のデータの全入替を行う（ステップＳ１０２ｆ）。
【００５９】
なお、上記ステップＳ１０２ａ〜１０２ｅの処理が行われた場合には、ステップ１０１ｆにおいて必ずＮｏと判断されるため、ステップＳ１０２ｆの処理がされることはない。
【００６０】
以上のようにして、ＣＰＵ１０は、勢力関係の逆転についての全ての可能性を確かめると、ステップＳ１０の処理を終了して、次の処理として、図５に示すように、上位層ＴＲの生存率の計算処理を行う（ステップＳ２０）。なお、ステップＳ２０の演算結果は、データ領域Ｄ１中に格納され、後述するステップＳ２１ｃｃ（図６参照）において用いられる。
【００６１】
次に、ＣＰＵ１０は、遺伝的操作部として、下位層ＢＲについての各種の遺伝的操作を行う（ステップＳ２１ａ〜２７ａ：下位層ＢＲの遺伝的操作工程）。具体的には、まず、ＣＰＵ１０は、下位層ＢＲに属する各個体について、生存可能な個体数の上限に達しているかを判断し（ステップＳ２１ａ）、上限に達していると判断すると（ステップＳ２１ａ：Ｙｅｓ）、間引き制御部Ｐ３１を読み出して、上限数以下となるまで下位層ＢＲ内での間引きを行う（ステップＳ２２ａ）。このため、例えば、エリート選択により生存をかけた競争をさせる。具体的には、各個体のスコアを計算し、スコアの下位のもの（弱者）を条件が満たされていないものとして排除するすなわち消去する（殺す）ことで、個体数を下位層ＢＲで許容できる最大数である５０になるまで個体を削減する。言い換えると、スコアの最上位から５０位までのもの（強者）のみが存続する。以上のようにして個体数の確認又は調整がなされる（ステップＳ２１ａ：Ｎｏ又はステップＳ２２ａ）と、まず、下位層ＢＲに属する５０個の個体のうち、１つの対象個体についてそれが生存しているか否かについて生死情報格納領域Ｅ２１を照合して判断する（ステップＳ２３ａ）。なお、後述するように、下位層ＢＲに属する５０個全ての個体について以下の動作を行う。ステップＳ２３ａで、当該対象個体が生存していないすなわち死の状態にあると判断されると（ステップＳ２３ａ：Ｎｏ）、乱数を用いた交叉を行う処理に進める（ステップＳ２７ａ）。一方、ステップＳ２３ａにおいて、対象個体が生存しているすなわち生の状態にあると判断されると（ステップＳ２３ａ：Ｙｅｓ）、さらに、その対象個体の寿命が基本寿命（５年）の２倍未満であるか否かについて寿命格納領域Ｅ２４を照合して判断がなされ（ステップＳ２４ａ）、ステップＳ２４ａにおいて２倍未満であると判断されると（ステップＳ２４ａ：Ｙｅｓ）、その対象個体の遺伝子配列の突然変異を発生させる。すなわち、一定の確率でその個体の遺伝子配列の組み替えを行う（ステップＳ２５ａ）。なお、ステップＳ２４ａにおいて、その対象個体の寿命が基本寿命の２倍以上であると判断された場合には（ステップＳ２４ａ：Ｎｏ）、比較的良好な適応値を有する長寿な個体の遺伝子配列を維持すべく突然変異を発生させることなく次の処理に進む。ステップＳ２４ａ，Ｓ２５ａを経た後、ＣＰＵ１０は、情報書込部として、新たな遺伝的情報を有する対象個体の各種情報を情報記憶部である個体データ格納領域Ｅ２の各領域Ｅ２１，Ｅ２２等に書き込むとともに（情報書込工程）、適応値計算部Ｐ２を読み出して、適応値すなわちスコアを計算し、得られた値を個体データ格納領域Ｅ２の適応値情報格納領域Ｅ２３に書き込む（ステップＳ２６ａ：適応値計算工程）。さらに、ＣＰＵ１０は、乱数を用いた交叉を行う（ステップＳ２７ａ）。
【００６２】
ここで、ステップＳ２７ａにおける交叉は、２つの個体の遺伝子配列を適宜組み換えることでなされる。具体的に説明すると、まず、図９Ａ及び９Ｂに示すように、交叉させる対象を第１個体ＩＮ１及び第２個体ＩＮ２とし、さらに、第１個体ＩＮ１の遺伝子配列を配列要素ＧＮ１'〜ＧＮｘ'とし、第２個体ＩＮ２の遺伝子配列を配列要素ＧＮ１"〜ＧＮｘ"とする。ここで、第１個体ＩＮ１と第２個体ＩＮ２とを交叉させる第１の方法としては、乱数を用いて何番目までの配列要素で区切るかを定め、各個体の配列要素を組み換えるものが考えられる。例えば、図示のように、乱数により３番目までの配列要素で区切って組み換えるものと定まったとすると、この交叉によって図９Ｃに示す配列要素ＧＮ１'〜ＧＮ３'，ＧＮ４"〜ＧＮｘ"を有する新たな個体ＩＮ３や、個体ＩＮ３とは逆に、図９Ｄに示す配列要素ＧＮ１"〜ＧＮ３"，ＧＮ４'〜ＧＮｘ'を有する新たな個体ＩＮ４が発生することになる。以上のような第１の方法による交叉の場合、新たな個体ＩＮ３，ＩＮ４は、第１個体ＩＮ１及び第２個体ＩＮ２の双方の情報をある程度受け継いだものとなるため、この交叉の方法は、比較的遺伝的特徴を強く残したものと言える。
【００６３】
また、図９Ｅに示すように、上述した第１の方法とは別の第２の方法として、例えば第１個体ＩＮ１と第２個体ＩＮ２とで対応する各遺伝子配列を配列要素についてどちらの配列要素を選択するかを１つずつ乱数で定めることで新たな個体ＩＮ５を発生させることもできる。つまり、まず、第１個体ＩＮ１の１番目の配列要素である配列要素ＧＮ１'と第２個体ＩＮ２の１番目の配列要素である配列要素ＧＮ１"とについて、乱数を用いてどちらか一方の配列要素を選択し、選択された方を新たな個体ＩＮ５の１番目の配列要素とする。以下、２番目以降の配列要素についても同様に定めることで、新たな個体の遺伝子配列を確定させる。この第２の方法による交叉の場合、上述した第１の方法による交叉と異なり、新たな個体ＩＮ５は、略ランダムに近いものの、第１及び第２個体ＩＮ１，ＩＮ２からの影響を全く受けないものではなく、間接的・潜在的には情報を受け継いだものとなる。
【００６４】
また、上記の第１の方法と第２の方法とを組み合わせることもできる。例えば、上述した第１の方法と第２の方法とを１：１の割合で組み合わせた方法を、ステップＳ２７ａでの交叉として用いることができる。これにより、遺伝的特徴を高く残すものとそうでないものとの双方が新たな個体として発生することになるので、種の多様性を確保しやすくなる。
【００６５】
図５に戻って、ステップＳ２７ａの次に、ＣＰＵ１０は、下位層ＢＲの最小適応値である最良適応値の確認をする（ステップＳ２８ａ）。すなわち、上記ステップＳ２３ａ〜Ｓ２７ａを経た１つの対象個体の適応値と、最良適応値格納領域Ｅ２ｘに格納されている遺伝的情報を有する個体の適応値とを比較し、小さい値を新たな最小の適応値とする。ここで、最良適応値格納領域Ｅ２ｘは、現存する個体についての情報とは別に、これまでに各階層ＴＲ，ＭＲ，ＢＲに存在した個体のうち最小の適応値を有する個体についての情報を格納している。つまり、最良適応値格納領域Ｅ２ｘには、最終目的であるＴＳＰ等の問題の解の候補となる情報が納められている。従って、当該１つの対象個体が、最良適応値格納領域Ｅ２ｘに格納されているこれまでの適応値以下であれば、当該１つの対象個体が新たな適正解の候補であると判断してその遺伝的情報を最良適応値格納領域Ｅ２ｘに書き込む。当該１つの対象個体の適応値がこれまでの最小の適応値より大きい値であれば、これまでに格納されていた個体の遺伝的情報を維持する処理を行う。これにより、常に、下位層ＢＲに存在した歴代の個体のうち最も小さい適応値を有する個体の遺伝的情報を、最良適応値格納領域Ｅ２ｘに記録することができる（歴代適応値記録工程）。
【００６６】
次に、ＣＰＵ１０は、遺伝的操作部として、中間層ＭＲについての各種の遺伝的操作を行う（ステップＳ２１ｂ〜２７ｂ：中間層ＭＲの遺伝的操作工程）。具体的には、まず、ＣＰＵ１０は、中間層ＭＲに属する各個体について、生存可能な個体数の上限に達しているかを判断し（ステップＳ２１ｂ）、上限に達していると判断すると（ステップＳ２１ｂ：Ｙｅｓ）、捕食行動制御部Ｐ３４を読み出して、捕食動作を行う（ステップＳ２２ｂ：捕食工程）。すなわち、ここで、ＣＤＳに特有の事項である中間層ＭＲと下位層ＢＲとの個体について喰う、喰われる動作に伴う生死の状態の変更がなされる。具体的には、乱数により、中間層ＭＲに属する一の個体と下位層ＢＲに属する一の個体とが選択され、双方のスコアを読出して比較し、中間層ＭＲの一の個体のスコアが下位層ＢＲの一の個体のスコア以下である場合には、捕食に成功したものとして捕食された当該下位層ＢＲの一の個体が死の状態となり、中間層ＭＲの一の個体のスコアが下位層ＢＲの一の個体のスコアより大きい場合には、捕食に失敗したものとして中間層ＭＲの一の個体が死の状態となる。これにより、中間層ＭＲの個体数が調整される。なお、ＣＰＵ１０は、捕食工程における生死の状態の変更に伴い、生死情報格納領域Ｅ２１に格納されている情報を書換える。
【００６７】
個体数の確認又は調整がなされる（ステップＳ２１ｂ：Ｎｏ又はステップＳ２２ｂ）と、下位層ＢＲの場合と同様に（ステップＳ２３ａ〜２８ａ参照）、中間層ＢＲに属する１つの対象個体について生存の有無の判断（ステップＳ２３ｂ）、寿命の判断（ステップＳ２４ｂ）、突然変異の処理（ステップＳ２５ｂ）、適応値（スコア）計算（ステップＳ２６ｂ）の処理及び交叉の処理（ステップＳ２７ｂ）がなされ、最終的にＣＰＵ１０は、中間層ＭＲの最良適応値の確認をする（ステップＳ２８ｂ）。なお、この動作により遺伝的情報が変更されれば、これに伴い個体データ格納領域Ｅ２のデータが適宜書き換えられる。また、ステップＳ２７ｂの交叉の具体的な処理については、上述したステップＳ２７ａと同様とすることができる。
【００６８】
次に、ＣＰＵ１０は、遺伝的操作部として、上位層ＴＲについての各種の遺伝的操作を行う（ステップＳ２１ｃ〜２７ｃ：上位層ＴＲの遺伝的操作工程）。具体的には、まず、上位層ＴＲに属する各個体について、生存可能な個体数の上限に達しているかを判断し（ステップＳ２１ｃ）、上限に達していると判断されると（ステップＳ２１ｃ：Ｙｅｓ）、さらにステップＳ２０で得た計算結果を読み出して上位層ＴＲに属する個体の生存率が上限に達しているかを確認する（ステップＳ２１ｃｃ）。ステップＳ２１ｃｃにおいて、上限に達していると判断されると、生存率が上限以下となるまで上位層ＴＲ内での間引きを行う（ステップＳ２２ｃ）。具体的には、例えばステップＳ２２ａの場合と同様エリート選択によって間引かれる。個体の生存率が上限以下になると（ステップＳ２１ｃｃ：Ｎｏ又はステップＳ２２ｃ）、捕食動作を行う（ステップＳ２２ｃｃ）。すなわち、上位層ＴＲと中間層ＭＲとの個体について喰う、喰われる動作に伴う生死の状態の変更がなされる。具体的には、乱数により、上位層ＴＲに属する一の個体と中間層ＭＲに属する一の個体とが選択され、双方のスコアを読出して比較し、上位層ＴＲの一の個体のスコアが中間層ＭＲの一の個体のスコア以上である場合には、捕食に成功したものとして捕食された当該中間層ＭＲの一の個体が死の状態となり、上位層ＴＲの一の個体のスコアが中間層ＭＲの一の個体のスコア未満である場合には、捕食に失敗したものとして上位層ＴＲの一の個体が死の状態となる。これにより、上位層ＴＲの個体数が調整される。なお、ここでの個体の生存率の上限は、一例として５０個としている。
【００６９】
上位層ＴＲの個体数の確認又は調整がなされる（ステップＳ２１ｃ：Ｎｏ又はステップＳ２２ｃｃ）と、下位層ＢＲ等の場合と同様に（例えばステップＳ２３ａ〜２８ａ参照）、上位層ＴＲに属する１つの対象個体について生存の有無の判断（ステップＳ２３ｃ）、寿命の判断（ステップＳ２４ｃ）、突然変異の処理（ステップＳ２５ｃ）、適応値（スコア）計算（ステップＳ２６ｃ）の処理及び交叉の処理（ステップＳ２７ｃ）がなされ、最終的にＣＰＵ１０は、上位層ＴＲの最良適応値の確認をする（ステップＳ２８ｃ）。なお、ステップＳ２７ｃの交叉の具体的な処理については、上述したステップＳ２７ａと同様とすることができる。
【００７０】
ＣＰＵ１０は、各階層ＴＲ，ＭＢ，ＢＲに属する各個体の全てについて、以上の確認の動作をする。すなわち、上記の各個体についての確認動作の回数が繁殖可能な最大個体数すなわち各繁殖用エリアの個数として設定された５０回に達しているかを確認し（ステップＳ４０）、最大個体数に達したと判断されるまで、上記ステップＳ２１ａ〜ステップＳ２８ｃまでの動作を繰り返す。
【００７１】
ステップＳ４０において、最大個体数に達した判断されると（ステップＳ４０：Ｙｅｓ）、ＣＰＵ１０は、寿命制御部Ｐ３６を読み出して、上位層ＴＲ、中間層ＭＲ及び下位層ＢＲの全個体の寿命を１つずつ減らす（ステップＳ５０〜Ｓ５２）。つまり、寿命格納領域Ｅ２４に格納されている情報の書換えとともに寿命をまっとうして死の状態となったものがあれば、生死情報格納領域Ｅ２１の生死状態の書換えを行う。
【００７２】
次に、ＣＰＵ１０は、捕食工程において被食側にある中間層ＭＲ及び下位層ＢＲについて、絶滅回避制御部Ｐ３５を読み出して生物爆発に相当する現象を生じさせる処理を行うか否かの判断をするため、生死情報格納領域Ｅ２１を照合して中間層ＭＲ及び下位層ＢＲの生存個体数をそれぞれカウントする（ステップＳ６０，Ｓ６１）。
【００７３】
ステップＳ６０の結果、中間層ＭＲの生存個体数が最大数である５０に対して規定数である生存限界数以下に減少しているか否かを判断する（ステップＳ６２ａ）。なお、ここでの生存限界数は、各層の全個体数の半数とする。ＣＰＵ１０は、ステップＳ６２ａにおいて、生存限界数以下でないと（ステップＳ６２ａ：Ｎｏ）、生物爆発に相当する現象を生じさせる必要がないと判断し、下位層ＢＲの個体数についての処理に移行する。一方、ステップＳ６２ａにおいて、生存限界数以下であると（ステップＳ６２ａ：Ｙｅｓ）、絶滅回避制御部Ｐ３５を読み出して、中間層ＭＲの個体数を爆発的の増大させるための処理を行う（絶滅回避工程）。まず、中間層ＭＲに属する１つの対象個体についてそれが死んでいるか否かを判断する（ステップＳ６３ａ）。ここで、当該対象個体が死の状態にあるすなわち生存していないと判断されると（ステップＳ６３ａ：Ｙｅｓ）、乱数を用いて新たな遺伝子配列を有する１つの個体を生成し（ステップＳ６４ａ）、死んでいる個体と入れ替える。つまり、新しく生成された個体の遺伝子配列の情報のほか、例えば生成された個体のスコアを計算して（ステップＳ６５ａ）、得られた各情報を個体データ格納領域Ｅ２の適応値情報格納領域Ｅ２３等に書き込み、ステップＳ６３ａ〜Ｓ６５ａの動作が規定回数である繁殖用エリアの個数として設定された５０回に達したかを確認する（ステップＳ６６ａ）。すなわち、中間層ＭＲに属する全ての個体について生存の有無を確認したかを判断する。一方、ステップＳ６２ａにおいて、当該対象個体が死んでいないすなわち生存していると判断された場合には上記のような新たな生成をすることなくステップＳ６６ａの動作を行う。つまり、ここでは、絶滅を回避するために必要な生存可能数を生存個体数の最大である５０とし、５０回となるまで上記の動作を行うことで、生物爆発に相当する現象を生じさせている。
【００７４】
ステップＳ６６ａにおいて、中間層ＭＲに属する全ての個体について生存の有無を確認すると（ステップＳ６６ａ：Ｙｅｓ）、中間層ＭＲでの固体数の増大の動作を終了し、同様の動作を下位層ＢＲに属する個体に対して行う（ステップＳ６２ｂ〜６６ｂ）。すなわち、下位層ＢＲの生存個体数が規定数である生存限界数以下に減少しているか否かを判断し（ステップＳ６２ｂ）、対象個体の生死をそれぞれ確認して（ステップＳ６３ｂ）、死んでいる場合には乱数を用いて新たな遺伝子配列を有する１つの個体を生成し（ステップＳ６４ｂ）、その個体のデータを収集するともに死んでいる個体と入れ替える（ステップＳ６５ｂ）。さらに、以上の動作を規定回数行ったかを確認する（ステップＳ６６ｂ）。
【００７５】
次に、ＣＰＵ１０は、世代の更新の動作を行う（ステップＳ７０）。つまり、ＣＰＵ１０は、世代更新部Ｐ３７を読み出して、世代数カウンタＥ３の値を１つ加算して、本実施形態で構築されたシステム全体についての世代を１つ更新する動作を行う。なお、ステップＳ５０〜Ｓ５２の動作により、ステップＳ７０での世代の更新とともに各個体の寿命が１つずつ減るものとなっている。いわば、暦ともに全ての個体の１つずつが年齢をそれぞれ重ねることになっている。次に、ＣＰＵ１０は、世代数カウンタＥ３を読み出して、世代の更新回数が上限に達したか否かを判断する（ステップＳ７１）。更新回数が上限に達していなければ（ステップＳ７０：Ｎｏ）、ＣＰＵ１０は、再操作部として、ステップＳ６（図３参照）からステップＳ７０までの動作を繰り返す（再操作工程）。更新回数が上限に達していれば（ステップＳ７０：Ｙｅｓ）、上位層ＴＲ、中間層ＭＲ及び下位層ＢＲでの最良適応値を解候補格納部である最良適応値格納領域Ｅ２ｘからそれぞれ読み出し、出力する（ステップＳ８０〜ステップＳ８２）。ステップＳ８０〜ステップＳ８２で出力された各値は、対象となっていた問題の解の候補の要素となる。これらの最良適応値のうち、単数又は複数の値を探索された問題の解の候補である適正解として出力する（ステップＳ８３：解候補抽出工程）。
【００７６】
また、以上の場合では、ステップＳ２８ａ，Ｓ２８ｂ，Ｓ２８ｃにおいて、現存する個体についての適応値だけでなく、歴代の各階層ＴＲ，ＭＲ，ＢＲにおいて存在した個体の適応値のうち最も小さい値を有する個体の遺伝的情報を最良適応値格納領域Ｅ２ｘに格納している。従って、現存する個体の多様性は維持しつつも、これまでの探索の中から最も適応度の高い問題の解の候補を探し出すことができる（歴代適応値記録工程）。
【００７７】
図１０は、上記のようなプログラムを有する適正解探索装置１００を用いた探索によって得られた適正解を示す一例についてのグラフである。横軸は、更新回数すなわち世代数を示しており、縦軸は、スコアの値等を示している。なお、既述のように、本実施形態では、複数の個体のうち最小のスコアを有するものが最も優秀な適応値を有するものとしている。また、図１０のグラフは、例えばステップＳ６，Ｓ７で得られるデータを表示装置１２によって出力表示可能となる。
【００７８】
図１０において、折線Ｃ１，Ｃ２，Ｃ３は、上位層ＴＲ、中間層ＭＲ及び下位層ＢＲの各世代での最小の適応値（スコア）の推移をそれぞれ示している。この場合、下位層ＢＲについての折線Ｃ３が、世代数６４〜７９のところで、歴代のうち最も優秀な適応値である「３．０１９３３８」を示している。つまり、この場合、世代数６４〜７９において下位層ＢＲに属する最小の適応値を有する個体の遺伝子配列が、設定された問題の解の候補である適正解として出力されることになる。また、折線Ｃ１，Ｃ２，Ｃ３の推移から、各階層の最適なスコアの上下関係は、適度に入れ替わっており、個体の多様性を維持していることが分かる。
【００７９】
また、図１０において、折線Ｑ１，Ｑ２，Ｑ３は、各階層ＴＲ，ＭＲ，ＢＲにおけるスコアの平均値の推移をそれぞれ示している。折線Ｑ１，Ｑ２，Ｑ３の推移から、スコアの平均値が一定の値となることなく、適度に分散された状態を維持していることが分かる。これも、個体の多様性を維持していることを示すものである。
【００８０】
なお、図１１Ａ及び１１Ｂは、比較例として示す図であり、図１０に示したものと同じ問題について一般的ＧＡによって探索されたものの結果であり、図１１Ａは、スコアの平均値及び最小適応値を示しており、図１１Ｂは、最小適応値の分散を示している。比較例の場合、最も優秀な最小適応値やその平均、或いは分散についての折線は、いずれも、すぐに変動が小さくなり、ほとんど同じ値を示すものとなり、急速に多様性を失っていることが分かる。
【００８１】
以上のように本実施形態では、複数の個体についての遺伝的情報の１つとして、生の状態と死の状態とについての情報が含まれている。つまり、当該情報が、個体データ格納領域Ｅ２のうち寿命格納領域Ｅ２４に格納されている。これにより、各個体は、比較的良好な適応値（適応度）を持つものであっても、良好でない適応値（適応度）を持つものであっても、いずれ死を迎えることで淘汰されるため、例えば比較的良好であるが適正解とは言えない適応値を持つ個体によって寡占状態となることがなく、設定された問題の解の候補である適正解を探索する上でローカルミニマムに陥ることが回避される。
【００８２】
〔第２実施形態〕
以下、第２実施形態に係る適正解探索方法等について説明する。なお、本実施形態は、第１実施形態の適正解探索方法等の変形例であり、特に説明しない部分又は事項は、第１実施形態の場合と同様である。
【００８３】
図１２は、本実施形態の適正解探索方法を概念的に説明するフローチャートである。なお、動作を実行するための適正解探索装置については、図１Ａに示す適正解探索装置１００と同様であるので、図示及び説明を省略する。
【００８４】
本実施形態では、第１実施形態の変形例であり、１つの問題の解の探索の後、例えば新たな問題の設定のための各パラメータ等を修正して当該新たな問題の解の探索を行うという時系列的に変化するような問題について対応可能する場合の例である。具体的には、第１の問題についての最初の処理である問題データの読込みの処理（ステップＳ１）から最後の処理である問題の解の候補の出力の処理（ステップＳ８３）までの処理を第１実施形態の場合と同様に行う。これにより、最初に設定された問題の適正解の候補についての出力がなされる。次に、ＣＰＵ１０（図１Ａ参照）は、最初に設定された問題とは別の新たな問題が設定されたか否かを判断する（ステップＳ９０：新規探索設定工程）。つまり、オペレーターから入力装置１１を介して新規問題の設定のための各パラメータ等の問題データの入力動作がなされたかを確認する。新規問題の設定がなされていないと判断されれば（ステップＳ９０：Ｎｏ）、探索すべき問題が全て完了したと判断し、動作を終了する。一方、新規問題の設定がなされたと判断されると（ステップＳ９０：Ｙｅｓ）、ＣＰＵ１０は、ステップＳ８３の時点での各階層に属する各個体についての情報を初期の個体の情報として取り扱う処理を行う（ステップＳ９１）。つまり、ステップＳ９０及びステップＳ９１の処理は、ステップＳ１〜ステップＳ５の処理に相当する処理であり、これにより、ステップＳ８３の時点での各個体を、遺伝的操作等を行う対象個体として取り扱うことで、再度個体についての初期設定を行うことなく、新たに設定された問題の適正解の探索を行うことができる。例えば、ＴＳＰ（巡回セールスマン問題）において、最初（第１）の問題と次（第２）の問題とでは、都市の配置が異なり、巡回した時の都市間距離の関係が異なる場合、第１の問題の解の候補を探索した後、ステップＳ９０及びステップＳ９１において、第２の問題での都市間距離の計算方法すなわち適応値の算出方法さえ設定し直せば、新たに個体を設定することなく第１の問題での個体情報をそのまま適用して、すぐに第２の問題に取り掛かることができる。
【００８５】
以上のように、本実施形態では、問題の解の候補の決定後、新たな問題を設定するとともに、先の解の候補の決定時における複数の対象個体を、初期個体生成工程で生成された初期の複数の個体として用いる新規探索設定工程をさらに有することで、１つの問題の解の候補の探索後、新たな問題の解の探索を行うという問題の形質が時系列的に変化するようなものにおいて、再度初期の設定をすることなく新たな問題に取り組むことができる。
【００８６】
この発明は、上記の実施形態に限られるものではなく、その要旨を逸脱しない範囲において種々の態様で実施することが可能である。
【００８７】
まず、上記実施形態において、設定された数値はいずれも例示であり、例えば、複数の階層として上位層ＴＲ、中間層ＭＲ及び下位層ＢＲの３つの階層で構成されるものとしているが、３層に限らず、例えば５層以上の構造等とすることも可能である。また、逆に複数の階層ではなく１つすなわち単数の階層としてもよい。また、上位層ＴＲ、中間層ＭＲ及び下位層ＢＲにおいて、捕食と被食の関係を上位層ＴＲと中間層ＭＲの間についてと、中間層ＭＲと下位層ＢＲの間についてのみあるものとしているが、さらに、上位層ＴＲと下位層ＢＲの間についても捕食と被食の関係があることとする態様も可能である。また、各繁殖用エリアに所有される個体数を５０としているが、これについても適宜変更可能であり、例えば５０より多くしてもよい。また、個体の寿命も通常のもの（５年）と長寿のもの（１５年）と短命のもの（２年）との３種類があるとしているが、この種類の数や寿命の違いについても種々のパターンが考えられる。
【００８８】
また、上記において、複数の個体が、雌雄の別をそれぞれ有しており、遺伝的操作工程に雄性淘汰を含むものであるとしてもよい。この場合、例えば対象個体のうち雄の個体同士で適応値を比較することで生存競争を行わせて、自然界における雄性淘汰を模したものにできる。この場合、個体データ格納領域Ｅ２には、個体の雌雄の情報も格納されることになる。
【００８９】
また、上記のうち、ステップＳ２７ａ等の交叉については、上記第１及び第２の方法に限らない。例えば、第１の方法は、遺伝子配列として並べられた配列要素ＧＮ１'等に対して一箇所に区切りを設けて組み換えるものとする方法であるが、複数の区切りを設けて組み換えるものとする方法を採用し、これを他の方法と組み合わせることもできる。また、複数の方法を組み合わせる場合の割合も適宜定めることができる。
【００９０】
また、上記のうち、例えばステップＳ６１において下位層ＢＲの生存個体数をカウントする処理までを行った後に、一定の場合に、上位層ＴＲに生存している個体のうち、ベストに近い情報を有する個体をある程度の割合で強制的に間引く操作をさらに付加してもよい。具体的には、例えばステップＳ６１の処理が繰り返されて１０回目となるごとに、その時点で上位層ＴＲに属する個体のうちベストの適応値（スコア）を有する個体の情報と他の個体の情報とを比較して、遺伝的情報の内容の７割以上がベストの適応値（スコア）の個体と同じである個体を、無条件に消去する（殺す）操作を行うものとする。このような間引きの操作を加えることで、ローカルミニマムに陥る可能性を減らすことができる。
【００９１】
また、上記では、最上位の階層である上位層ＴＲにいるものが喰われること及び最下位の階層である下位層ＢＲが喰うことは生じないものとなっている。なお、階層の交換をするという革命的なこと（Class Change）が生じた場合には、層が入れ替わるので、やはり階層の交換の後、位層ＴＲにいるものは喰う一方であり下位層ＢＲにいるものは喰われる一方となる。しかし、これに加えて、さらに、最下位の階層のものが最上位の階層を喰うという概念を取り入れてもよい。言い換えると、上記では、喰う、喰われる関係が最上位から最下位までとする序列的であったが、最下位のものが最上位を喰うとする要素を加えて、ループ的なものとなっていてもよい。
【００９２】
また、既述のように、本実施形態の適正解探索装置１００を用いることで、ＴＳＰ（巡回セールスマン問題）に限らず、一般的ＧＡの場合と同様に、種々の問題に対応可能である。さらに、適正解探索装置１００では、時系列的に変化するような問題について、新たに初期設定し直すことなく解の探索が可能である点において、一般的ＧＡよりも迅速な探索が可能である。
【００９３】
また、用途に応じて適正解探索装置１００に含まれる手法の部分的に採用してシステムを構築することも可能である。
【００９４】
本実施形態の適正解探索装置１００を用いる応用例としては、例えばＩＣチップ等の配線において複数の端子を定められた組み合わせで配線する場合に最短の配線距離となる処理パターンを見出すという問題の適正解を探索することが考えられる。また、適正解探索装置１００を用いて、例えば宅配業務を行うにあたって配送先を巡る順序パターンのうちより好ましい順序パターンを選んだり、ある作業を分業するにあたってより効率的な分業の仕方を選んだりすることが迅速に行える。
【図１】
2013051701.tif 000003
【図２】
2013051701.tif 000004
【図３】
2013051701.tif 000005
【図４】
2013051701.tif 000006
【図５】
2013051701.tif 000007
【図６】
2013051701.tif 000008
【図７】
2013051701.tif 000009
【図８】
2013051701.tif 000010
【図９】
2013051701.tif 000011
【図１０】
2013051701.tif 000012
【図１１】
2013051701.tif 000013
【図１２】
2013051701.tif 000014
【手続補正書】
【提出日】平成25年4月25日(2013.4.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１１
【補正方法】変更
【補正の内容】
【請求項１１】
前記繁殖用エリアを構成する前記複数の階層に属する個体の前記適応値の平均値を基準として、一の階層に属する個体と他の階層に属する個体との全入替をする階層交換工程をさらに有する、請求項５に記載の適正解探索方法。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１４
【補正方法】変更
【補正の内容】
【請求項１４】
問題の解の候補の要素を遺伝子配列としてそれぞれ有する複数の個体について、淘汰、突然変異及び交叉を含む遺伝的操作を行う遺伝的アルゴリズムを用いた適正解探索装置であって、
初期の複数の個体を生成して処理の対象となる複数の対象個体とする初期個体生成部と、
前記複数の対象個体についての遺伝的情報を記憶する情報記憶部と、
前記複数の対象個体の少なくとも一部について前記淘汰、突然変異及び交叉のうち少なくともいずれか１つの遺伝的操作をすることにより、既存の複数の対象個体から新たな複数の対象個体を生成する遺伝的操作部と、
前記遺伝的操作部で生成された前記新たな複数の対象個体についての遺伝的情報を前記情報記憶部に書き込む情報書込部と、
前記初期の複数の個体及び前記新たな複数の対象個体がそれぞれ有する前記遺伝子配列に基づいて前記問題の解の候補に対応する適応値を計算する適応値計算部と、
前記新たな複数の対象個体に対して前記遺伝的操作部及び前記適応値計算部での処理を繰り返させる再操作部と、
複数回処理を繰り返されることで前記適応値計算部において得られた複数の前記適応値のうち最も適応度の高いものの少なくとも１つの値を、前記問題の解の候補の１つとして格納する解候補格納部と、
を有し、
前記情報記憶部は、前記複数の個体についての前記遺伝的情報の１つとして、各個体が前記遺伝的操作部における遺伝的操作の対象及び前記適応値計算部における前記適応値の計算の対象となっている生の状態と、前記遺伝的操作の対象及び前記適応値の計算の対象となっていない死の状態とのうちいずれの状態にあるかについての情報を含む、適正解探索装置。
【国際調査報告】
2013051701.tif 000015
2013051701.tif 000016
2013051701.tif 000017
2013051701.tif 000018