(57)【要約】      （修正有）【課題】所定環境において最適解を求めるにあたり、染色体の初期値を新たに発生させる場合に、探索済み領域以外の領域に発生させ、効率的に最適解を求める。【解決手段】複数の情報体からなる情報体集団に対し、遺伝的アルゴリズムを用いて探索操作を行い、最適解を求める最適解探索装置において、適応度値の変化率と予め定められた変化率とを比較し、前記適応度値の変化率が、前記予め定められた変化率より小さいと判断した場合、新たな情報体を導入する。その際に、すでに導入されている情報体の分布情報を参照して、情報体密度がより少ない領域に対して新たに情報体を導入する。【選択図】図３
2007199943.tif 000002
【特許請求の範囲】
【請求項１】
複数の情報体からなる情報体集団を用いて、遺伝的アルゴリズムにより探索操作を行い、所定の環境への適応度を示す適応度値に基づいて、該環境における最適解もしくは最適解に近い準最適解を求める最適解探索装置において、
該探索操作が繰り返される過程において、各情報体に係る該適応度値の変化率と予め定められた変化率とを比較する適応度値変化率比較手段と、
該適応度値変化率比較手段において、前記適応度値の変化率が、前記予め定められた変化率より小さいと判断した場合、新たな情報体を導入する情報体導入手段と、
該情報体導入手段により導入する情報体を構成する値が取り得る範囲を複数の領域に分割して分割領域を生成する分割領域生成手段と、
それぞれの該分割領域における新たに導入される情報体の導入頻度より成る分布情報を記憶する導入情報体分布格納手段とからなる最適解探索装置であって、
該情報体導入手段は、該分布情報を参照して、情報体密度がより小さい領域に対して新たに情報体を導入することを特徴とする最適解探索装置。
【請求項２】
該導入情報体分布格納手段は、各情報体を所定の順に並べて階層構造とし、各情報体の該分布情報をツリー構造として格納することを特徴する請求項１に記載の最適解探索装置。
【請求項３】
該分割領域生成手段は、該情報体を構成する値が存在しない分割領域は生成しないことを特徴とする請求項１に記載の最適解探索装置。
【請求項４】
該導入情報体分布格納手段は、各分割領域における情報体の数を累積して、累積値を算出することを特徴とする請求項１に記載の最適解探索装置。
【請求項５】
複数の情報体からなる情報体集団に対し、遺伝的アルゴリズムを用いて探索操作を行い、所定の環境への適応度を示す適応度値に基づいて、該環境における最適解もしくは最適解に近い準最適解を求める最適解探索方法において、
該探索操作が繰り返される過程において、各情報体に係る該適応度値の変化率と予め定められた変化率とを比較する適応度値変化率比較手順と、
該適応度値変化率比較手順において、前記適応度値の変化率が、前記予め定められた変化率より小さいと判断した場合、新たな情報体を導入する情報体導入手順と、
該情報体導入手順により導入する情報体を構成する値が取り得る範囲を複数の領域に分割して分割領域を生成する分割領域生成手順と、
それぞれの該分割領域における新たに導入される情報体の導入頻度より成る分布情報を記憶する導入情報体分布格納手順とからなる最適解探索方法であって、
該情報体導入手順は、該分布情報を参照して、情報体密度がより小さい領域に対して新たに情報体を導入することを特徴とする最適解探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適解探索装置、最適解探索方法に関するものであり、特に一つの環境内において、複数個の情報を組み合わせて最適な解を得るに際して、遺伝的アルゴリズム（Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍｓ；ＧＡ）を適用して探索を行う最適解探索装置、最適解探索方法に関するものである。
【背景技術】
【０００２】
遺伝的アルゴリズムは、生物の進化のメカニズムをモデル化して最適解を求める手法である。そして設計支援、製造支援、スケジューリング等に応用され、産業界において、有効な最適化手法の一つとしての利用が期待されている。      
【０００３】
特に、遺伝的アルゴリズムは大規模で多峰性を有した最適化問題を解くのに有用な手法である。
【０００４】
遺伝的アルゴリズムが非常に有効な問題として、巡回セールスマン問題（Ｔｒａｖｅｌｉｎｇ  ｓａｌｅｓｍａｎ  ｐｒｏｂｌｅｍ；ＴＳＰ）があげられる。
【０００５】
ＴＳＰとは、ある１人のセールスマンが幾つかの都市を次々に一度ずつ訪問して、最後に出発点に戻らなければならないときに、最短の距離で回る巡回路を決定する問題である。
【０００６】
つまりＴＳＰは、すべての都市を一度だけ訪問するという制約条件のもとで、総距離を最小にするという組み合わせ最適化問題である。
【０００７】
遺伝的アルゴリズムでは、まず、個体群の中の個体の初期分布を決定する。ここでは、個体の染色体は最大化しようとしている関数の定義域を決めるコードであると仮定する。例えば、定義域を決めるコードは２進数である。もちろん、初期分布を決定するときに所定の情報があればそれを具備して初期分布を作成してもよいし、ランダムに決定してもよい。  
【０００８】
遺伝的アルゴリズムを適用するためには、コード化された個体に対する評価値が明確に与えられていることが必要である。ここで、評価値は関数の形で与えられていなくてもよい。
【０００９】
遺伝的アルゴリズムでは、環境に対して適応する度合い（以下、フィットネス値と呼ぶ。）の良い個体が生き残り、フィットネス値の悪い個体は淘汰され、個体群の中から消滅することになるという進化過程を取り入れている。これは再生（ｒｅｐｒｏｄｕｃｔｉｏｎ、リプロダクション）と呼ばれる。
【００１０】
しかし、リプロダクションだけでは初期分布の中にある個体の中でフィットネス値の高いものばかりが再生することになってしまうため、進化を進めることができない。
【００１１】
そのため、遺伝的アルゴリズムにおいては、交叉（ｃｒｏｓｓｏｖｅｒ、クロスオーバー）と呼ばれる染色体の一部組み換え操作を行う。
【００１２】
一般的にクロスオーバーさせる２つの個体は確率的に選択される。ここで、クロスオーバーのやり方は、全個体をクロスオーバーさせてもよいし、一部の個体のみをクロスオーバーさせる構成でもよい。さらに、子ができると同時に親を抹消するのか、あるいは他の操作をほどこした後に個体数の調整をするなど、適用する問題に対応して変える構成であってもよい。
【００１３】
交叉では、どのようにして任意の２つの個体を選択するのか、またどのようにして選択した２つの個体を交叉させるのか、クロスオーバーにより生成された新しい個体をいかにして個体群の中に組み込むのかという操作が重要である。これらの操作はそれぞれ、クロスオーバー確率、クロスオーバー点の数、世代ギャップ（入れ替える新個体の割合）に通常は関係するものである。
【００１４】
１点交叉とよばれている最も単純な交叉では、親１、親２の染色体上で任意に選ばれた交叉点において、染色体を切り、お互いの切れた染色体を交換して、子１、子２が得られる。
【００１５】
多点交叉は、親１、親２の染色体上において、交叉点を任意に複数個選び、交叉点の間で交互に２つの親の部分染色体を交換して、子１、子２を生成するものである。
【００１６】
しかし、リプロダクションとクロスオーバーを行っても子のバリエーションは限られてしまうため、クロスオーバーの操作を導入しても進化は十分に行われないことが多い。
【００１７】
そのためフィットネス値が十分に高くない個体に収束してしまうのを防ぐため、繰り返しの過程において、新しい遺伝子をもつ個体を補充する必要があり、これは自然界においては突然変異（ｍｕｔａｔｉｏｎ、ミューテーション）として生じる。
【００１８】
突然変異は、染色体上のある遺伝子座の値を他の対立遺伝子に置き換えることにより、クロスオーバーだけでは生成できない子孫を生成して、個体群の多様性を維持する働きをする。遺伝的アルゴリズムにおいては、染色体上の各遺伝子が比較的低い確率で突然変異の対象とされ、クロスオーバーだけでは生成できない子孫を生成して、個体群の多様性を維持する働きをする。例えば乱数により対象となった遺伝子において、対立遺伝子のいずれかの値を確率的選択する。
【００１９】
そして一般的に、遺伝的アルゴリズムの終了判定条件は、個体群の中の最大のフィットネス値が設定された閾値を超えたときや、個体群全体の平均のフィットネス値が設定された閾値を超えたとき、世代交代の回数があらかじめ設定した回数を超えたときなどがある。
【００２０】
上記に示すように遺伝的アルゴリズムは、リプロダクションにより望ましい解を重点的に探索すると同時に、クロスオーバーと突然変異によって解の探索範囲を広げているので、これらの両方の手続きが有効に作用すれば、その威力を十分に発揮することになる。
【００２１】
しかしながら、所定の問題の最適な解を探索する場合、情報体集団が局所的な最適点に陥ってしまい、世代の値の増加に対するフィットネス値の増加の割合が減少するという問題が起こる。
【００２２】
これは新たな導入情報体を意識的に外部から導入する方法により、情報体集団は、それに含まれる複数の情報体に関する多様性が増加して、局所的な最適点から抜け出す確率が高まる。
【００２３】
遺伝的アルゴリズムを用いた最適解の探索において、導入情報体をランダムに発生させて、新しい世代を構成する情報体集団を生成する場合においては、導入情報体が情報体集団のフィットネス値の向上に貢献する程度が低下することになるという問題もある。
【００２４】
上記の問題を解決する特許文献として以下のものが存在する。
【特許文献１】特許３５３４４７２号公報  情報体集団の所定の環境内における最適解を求める最適解探索装置において、探索処理操作が繰り返される過程において、各情報体のフィットネス値の変化率が低下したと判断した場合において、過去に出現した染色体を記憶し、世代ごとに変形度合いを示す距離を設け、染色体からの距離に応じた頻度で過去の世代から導入情報体を選択するものである。
【発明の開示】
【発明が解決しようとする課題】
【００２５】
しかしながら、上記に記載の最適解探索装置においては、フィットネス値の変化率が鈍化してきた場合に導入する新たな初期値の分布が偏る傾向がある。
【００２６】
そのため初期値発生の偏在によって、最適な解（良好な解）が未探索領域に存在する場合には、最適な解を発見することが非常に困難となってくる。
【００２７】
本発明は、上記のことに鑑みてなされたものであり、染色体の初期値を新たに発生させる場合において、探索済み領域以外の領域に発生させることを目的とする。
【課題を解決するための手段】
【００２８】
本発明に係る最適解探索装置は、複数の情報体からなる情報体集団を用いて、遺伝的アルゴリズムにより探索操作を行い、所定の環境への適応度を示す適応度値に基づいて、該環境における最適解もしくは最適解に近い準最適解を求める最適解探索装置において、該探索操作が繰り返される過程において、各情報体に係る該適応度値の変化率と予め定められた変化率とを比較する適応度値変化率比較手段と、該適応度値変化率比較手段において、前記適応度値の変化率が、前記予め定められた変化率より小さいと判断した場合、新たな情報体を導入する情報体導入手段と、該情報体導入手段により導入する情報体を構成する値が取り得る範囲を複数の領域に分割して分割領域を生成する分割領域生成手段と、それぞれの該分割領域における新たに導入される情報体の導入頻度より成る分布情報を記憶する導入情報体分布格納手段とからなる最適解探索装置であって、該情報体導入手段は、該分布情報を参照して、情報体密度がより小さい領域に対して新たに情報体を導入することを特徴とする。
【００２９】
また本発明に係る最適解探索装置は、該導入情報体分布格納手段が各情報体を所定の順に並べて階層構造とし、各情報体の該分布情報をツリー構造として格納することを特徴する。
【００３０】
また本発明に係る最適解探索装置は、該分割領域生成手段が該情報体を構成する値が存在しない分割領域は生成しないことを特徴とする。
【００３１】
また本発明に係る最適解探索装置は、該導入情報体分布格納手段が各分割領域における情報体の数を累積して、累積値を算出することを特徴とする。
【００３２】
さらに本発明に係る最適解探索方法は、複数の情報体からなる情報体集団に対し、遺伝的アルゴリズムを用いて探索操作を行い、所定の環境への適応度を示す適応度値に基づいて、該環境における最適解もしくは最適解に近い準最適解を求める最適解探索方法において、該探索操作が繰り返される過程において、各情報体に係る該適応度値の変化率と予め定められた変化率とを比較する適応度値変化率比較手順と、該適応度値変化率比較手順において、前記適応度値の変化率が、前記予め定められた変化率より小さいと判断した場合、新たな情報体を導入する情報体導入手順と、該情報体導入手順により導入する情報体を構成する値が取り得る範囲を複数の領域に分割して分割領域を生成する分割領域生成手順と、それぞれの該分割領域における新たに導入される情報体の導入頻度より成る分布情報を記憶する導入情報体分布格納手順とからなる最適解探索方法であって、該情報体導入手順は、該分布情報を参照して、情報体密度がより小さい領域に対して新たに情報体を導入することを特徴とする。
【発明の効果】
【００３３】
本発明により、遺伝的アルゴリズムにおける局所解から脱出するために発生させる初期値分布の偏在を防止することができ、局所解から脱出する可能性を向上させることができる。
【００３４】
また、初期値を発生させた領域を、発生させる染色体に基づくツリー構造にすることによって、探索領域を効率的に記憶することができ、より効率的に遺伝的アルゴリズムの処理を行うことができる。
【発明を実施するための最良の形態】
【００３５】
図１は、本実施例に係る染色体の一例である。
【００３６】
Ｌ１、Ｌ２、Ｌ３は染色体１における遺伝子座である。ここでは遺伝子座の数は３つである。遺伝子座とは、染色体上において各遺伝子が置かれている位置のことである。遺伝子座の数はこれに限られることはない。
【００３７】
遺伝子座Ｌ１、Ｌ２、Ｌ３には、それぞれ遺伝子が置かれ、染色体における遺伝子の組み合わせが決定される。そして所定の環境において、最適な遺伝子の組み合わせ、最適解を遺伝的アルゴリズムを用いて計算して求める。遺伝子座Ｌ１、Ｌ２、Ｌ３に置かれる遺伝子は、実数値である。また、他の染色体も遺伝子座の数は３つである。
【００３８】
図２は、遺伝子座Ｌ１、Ｌ２、Ｌ３の値の範囲を表す図である。
【００３９】
本実施例において、それぞれの遺伝子座Ｌ１、Ｌ２、Ｌ３の値の範囲は実数値をとることが可能である。遺伝子座Ｌ１、Ｌ２、Ｌ３の値の範囲は、遺伝子がとることのできる遺伝子候補であり、対立遺伝子と呼ばれる。
【００４０】
そして遺伝子座Ｌ１、Ｌ２、Ｌ３の対立遺伝子はそれぞれ３つの領域に分割されている。具体的には遺伝子座Ｌ１の対立遺伝子は、領域ｒ１＿１、ｒ１＿２、ｒ１＿３、遺伝子座Ｌ２の対立遺伝子は、領域ｒ２＿１、ｒ２＿２、ｒ２＿３、遺伝子座Ｌ３の対立遺伝子は、領域ｒ３＿１、ｒ３＿２、ｒ３＿３に分割されている。そしてそれぞれの領域は等間隔に分割された領域である。
【００４１】
Ｌ１、Ｌ２、Ｌ３の対立遺伝子は実数値に限定されることはなく、離散値であっても構わないし、環境によっては、一部分の対立遺伝子のみが離散値である構成であっても構わない。
【００４２】
また本実施例において、遺伝子座の値は３つの領域に分割されているが、これに限定されることはなく、他の数に分割しても構わないし、それぞれの遺伝子座の値の分割数が異なっていても構わない。
【００４３】
図３において、ＧＡ実行装置１００は、初期染色体発生装置１０１に対して、初期染色体（以下、初期値と呼ぶ。）を発生するよう指示する。
【００４４】
初期染色体発生装置１０１は、ＧＡ実行装置１００からの指示を受けて、所定の環境における個体群の中の初期値をランダムに発生し決定する。発生染色体分布格納装置１０２は、それぞれの遺伝子座の対立遺伝子が、領域ｒ１＿１、ｒ１＿２、ｒ１＿３、領域ｒ２＿１、ｒ２＿２、ｒ２＿３、領域ｒ３＿１、ｒ３＿２、ｒ３＿３のいずれかに属するかを判別し、初期値の頻度分布を格納する。ＧＡ実行装置１００は、頻度分布を参照して、リプロダクション、クロスオーバー、突然変異などの所定のＧＡ処理を実行していく。
【００４５】
本実施例においては、ＧＡ実行装置１００、初期染色体発生装置１０１、発生染色体分布格納装置１０２を物理的に分離して、それぞれにおいて、所定の処理を行うシステムとなっているが、これに限定されることはなく、ハードウェアとしては、一つの装置で構成されており、ＧＡ実行装置１００、初期染色体発生装置１０１、発生染色体分布格納装置１０２の行う処理のすべてをその一つの装置が行う構成でもよい。
【００４６】
また本実施例で行う遺伝的アルゴリズムの処理において、リプロダクションは、フィットネス値比例に基づくルーレット選択が行われるものとする。リプロダクション（自然淘汰の選択）は、ルーレット選択以外であってもよく、所定の個体群の中から定められた個数の個体をランダムに選択して、最もフィットネス値の高い個体を次世代に残し、この処理を次世代に残したい数の個体が選択されるまで繰り返すというトーナメント選択や、個体群の中で最もフィットネス値の高い個体は無条件でそのまま次世代に残すというエリート保存選択などであってもよい。
【００４７】
クロスオーバーにおいては、一点交叉が行われる。またクロスオーバーさせる２つの個体は確率的に選択される。ここで一点交叉とは、親１、親２の染色体上で任意に選ばれた交叉点において、染色体を切り、お互いの切れた染色体を交換して、子１、子２を生成するものである。クロスオーバーは、これ以外にも多点交叉や一様交叉などであっても構わない。クロスオーバーさせる個体は、個体群に含まれるすべての個体であってもよいし、個体群に含まれる一部の個体に対してでも構わない。さらに、子を生成すると同時に親を抹消するのか、あるいは他の操作をほどこした後に個体数の調整をするなど、適用する問題に対応して変えてもよい。
【００４８】
図３は、本実施例に係る情報処理システムの構成図である。
【００４９】
１００はＧＡ実行装置であり、１０１は初期染色体発生装置であり、１０２は発生染色体分布格納装置である。
【００５０】
ＧＡ実行装置１００は、ＣＰＵ、ＲＯＭ（Ｒｅａｄ−Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ−Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等を備えたコンピュータで構成され、遺伝的アルゴリズム処理制御、初期染色体発生装置１０１への指示制御、初期染色体の頻度分布の発生染色体分布格納装置１０２との送受信制御の各種制御を行う。
【００５１】
まず、ＧＡ実行装置１００は遺伝的アルゴリズムを実行する。その際に、ＧＡ実行装置１００は、初期値の発生を初期染色体発生装置１０１に依頼する。
【００５２】
ＧＡ実行装置１００から依頼を受けた初期染色体発生装置１０１は、初期値を発生して、ＧＡ実行装置１００に初期値を送る。
【００５３】
そして発生した初期値の頻度分布は、発生染色体分布格納装置１０２に格納される。
【００５４】
発生染色体分布格納装置１０２は、ＲＯＭ、ＲＡＭ等を総括的に表しており、着脱可能な記録媒体で構成してもよく、電源を解除しても記憶内容を消失しないメモリとして例えば、フラッシュメモリなどによって構成してもよい。
【００５５】
遺伝的アルゴリズムを行っていく過程において、クロスオーバー、突然変異などの操作によって出現した染色体も発生染色体分布装置１０２に格納する構成でもよい。その場合、ＧＡ実行装置１００は、遺伝的アルゴリズムの処理を行い、その処理過程において発生する染色体も発生染色体分布格納装置１０２に格納する。発生染色体分布格納装置１０２には、初期染色体発生装置１０１が発生した初期値と遺伝的アルゴリズムの処理過程において発生する染色体のそれぞれの領域における合計の数の頻度分布が格納されている。
【００５６】
また発生染色体分布格納装置１０２は、初期染色体発生装置１０１で発生した初期値の頻度分布とＧＡ実行装置１００によって生成される染色体の頻度分布とを分離して格納する構成であってもよい。そして、初期染色体発生装置１０１において、新たに初期染色体の発生をするときにＧＡ実行装置１００によって生成された染色体の頻度分布を参照して、ＧＡ実行装置１００において生成された染色体が少ない領域ほど高い確率で発生するように、初期値を発生させる構成であってもよい。
【００５７】
ここでそれぞれの領域において、情報体密度が小さい領域ほど高い確率で染色体を発生する構成であっても構わない。ここで情報体密度とは、単位領域当たりの情報体の数を示すものである。
【００５８】
遺伝的アルゴリズムにおいて得られる解のフィットネス値の変化率が鈍化してきた場合には、ＧＡ実行装置１００は、初期染色体発生装置１０１に初期値の発生を再び依頼する。
【００５９】
ＧＡ実行装置１００内に予め定められた変化率が記憶されており、フィットネス値の変化率は、ＧＡ実行装置１００内に記憶されている予め定められた変化率とＧＡ実行装置１００によって比較される。
【００６０】
そしてＧＡ実行処理装置１００が、フィットネス値の変化率が予め定められた変化率よりも小さいと判断した場合には、初期染色体発生装置１０１に初期値の発生を再び依頼する。
【００６１】
ＧＡ実行装置１００から依頼を受けた初期染色体発生装置１０１は、初期値を発生し、ＧＡ実行装置１００へ送る。
【００６２】
ＧＡ実行装置１００は、初期染色体格納装置１０２に格納されている頻度分布を参照し、過去に染色体発生が少ない領域ほど高い確率で発生するように、初期値を発生させる。また頻度分布を参照し、過去に染色体発生がより少ない領域に初期染色体を発生させる構成であってもよい。
【００６３】
発生染色体分布格納装置１０２は、初期染色体発生装置１０１及びＧＡ実行装置１００において発生した初期値を受け取り、初期染色体発生装置１０１が初期染色体を発生するタイミングで発生染色体分布格納装置１０２の頻度分布に関する情報を更新する。
【００６４】
ＧＡ実行装置１００は、発生した初期値を含んだ染色体を用いて、再び遺伝的アルゴリズム処理を行う。再びフィットネス値の変化率が鈍化し、解のフィットネス値が充分に高くない場合には、再び初期値の発生、導入し、遺伝的アルゴリズム処理を行う。
【００６５】
以上の操作を繰り返し行い、所定のフィットネス値を超える解が見つかった場合に遺伝的アルゴリズム処理を終了する等して、所定の終了条件にしたがって最適解を求めていく。
【００６６】
ここで発生染色体分布格納装置１０２が、初期染色体発生装置１０１及びＧＡ実行装置１００において発生した初期値を受け取るタイミングは、これに限定されることはなく、例えば初期染色体発生装置１０１及びＧＡ実行装置１００において初期値の発生が完了した後に、それぞれでの初期値を受け取り頻度分布を構成しても構わない。
【００６７】
また発生染色体分布格納装置１０２に格納されている頻度分布を参照し、初期染色体発生装置１０１は、参照した頻度分布における初期値が発生していない領域、若しくは比較的初期値が発生していない領域に対する初期値を発生させて、初期値と発生させる領域の情報を対応付けて、ＧＡ実行装置１００へ送るという構成であっても構わない。
【００６８】
本実施例における情報処理システムは、ＧＡ実行装置１００、初期染色体発生装置１０１、発生染色体分布格納装置１０２のハードウェアから構成されているが、これに限定されることはなく、例えば一つの情報処理装置がこれらの処理を機能的に有している構成であっても構わない。
【００６９】
図４は、遺伝子の選択回数の記録に関する概念図である。
【００７０】
染色体Ｌ１、Ｌ２、Ｌ３のそれぞれを３分割しており、それぞれの染色体の分割領域において［１］、［２］、［３］は、それぞれの領域を識別するための番号である。そして、Ｌ２、Ｌ３においては、［１］、［２］、［３］はそれぞれ複数個存在するが、これは図４に表すように、それぞれＬ１、Ｌ２の領域［１］、［２］、［３］内での番号［１］、［２］、［３］である。［１］、［２］、［３］は、もちろん通し番号であってもよく、例えばＬ２においては［１］〜［９］，Ｌ３においては［１］〜［２７］と番号を付してもよい。
【００７１】
また［１］、［２］、［３］とは別にｒ１＿１、ｒ１＿２、ｒ１＿３、ｒ２＿１・・・もそれぞれ染色体Ｌ１、Ｌ２、Ｌ３の領域を表すものであり、形式的に染色体の区別とＬ１、Ｌ２の分割領域内でさらにその中で分割された領域であること区別するための添え字を用いている。［１］、［２］、［３］やｒ１＿１、ｒ１＿２、ｒ１＿３の番号は遺伝的アルゴリズムを円滑に行うために付した識別番号として用いられるものであり、他の識別方法によって、それぞれの染色体の分割領域を識別しても構わない。
【００７２】
そしてｑ１、ｑ２、ｑ３は、染色体Ｌ１の分割領域ｒ１＿１、ｒ１＿２、ｒ１＿３に発生した対立遺伝子の数である。同様にして、ｑ１＿１、ｑ１＿２、ｑ１＿３、ｑ２＿１、ｑ２＿２、ｑ２＿３、ｑ３＿１、ｑ３＿２、ｑ３＿３はＬ２の分割領域において発生した対立遺伝子の数であり、ｑ１＿１＿１、ｑ１＿１＿２、ｑ１＿１＿３、ｑ１＿２＿１、ｑ１＿２＿２、ｑ１＿２＿３・・・ｑ３＿３＿３はＬ３の分割領域において発生した対立遺伝子の数である。遺伝的アルゴリズムの処理過程において、フィットネス値の伸び率が鈍化したと判断した場合における初期値の導入に際し、これらの対立遺伝子の数を示す値ｑによって、初期値が導入されていない領域、比較的導入されていない領域を適宜判断して、初期値の偏在を防止する。ここでｑは、添え字を省略したものであり、Ｌ１の分割領域における対立遺伝子の数ｑｉ、Ｌ２の分割領域における対立遺伝子の数ｑｉ＿ｊ、Ｌ３の分割領域における対立遺伝子の数ｑｉ＿ｊ＿ｋ（ｉ、ｊ、ｋ＝１〜３）を表すものである。
【００７３】
図５は、対立遺伝子が選択されない程度を表す概念図である。
【００７４】
図４に示す概念図に対応するものであり、染色体Ｌ１、Ｌ２、Ｌ３は図４と同様に３分割しており、それぞれの領域を識別する番号［１］、［２］、［３］とｒ１＿１、ｒ１＿２、ｒ１＿３、ｒ２＿１・・・ｒ３＿３とする。図４と同様に、Ｌ２、Ｌ３においては、［１］、［２］、［３］はそれぞれ複数個存在するが、これは図４に表すように、それぞれＬ１、Ｌ２の領域［１］、［２］、［３］内での番号［１］、［２］、［３］である。［１］、［２］、［３］は、もちろん通し番号であってもよく、例えばＬ２においては［１］〜［９］、Ｌ３においては［１］〜［２７］と番号を付してもよい。
【００７５】
そしてｐ１、ｐ２、ｐ３は、染色体Ｌ１の分割領域ｒ１＿１、ｒ１＿２、ｒ１＿３における対立遺伝子が発生していない程度を表すものである。本実施例では、染色体の分割した領域ｒ１＿１、ｒ１＿２、ｒ１＿３において、対立遺伝子を発生することが可能な限度の数をｗ１、ｗ２、ｗ３とし、ｐ１＝ｗ１−ｑ１、ｐ１＝ｗ１−ｑ１、ｐ１＝ｗ１−ｑ１と定義する。同様にしてｐ１＿１＝ｗ１＿１−ｑ１＿１、ｐ１＿２＝ｗ１＿２−ｑ１＿２、ｐ１＿３＝ｗ１＿３−ｑ１＿３、・・・、ｐ３＿３＝ｗ３＿３−ｑ３＿３、ｐ１＿１＿１＝ｗ１＿１＿１−ｑ１＿１＿１、ｐ１＿１＿２＝ｗ１＿１＿２−ｑ１＿１＿２、ｐ１＿１＿３＝ｗ１＿１＿３−ｑ１＿１＿３、・・・、ｐ３＿３＿３＝ｗ３＿３＿３−ｑ３＿３＿３とする。一般的に記載すると、ｐｉ＝ｗｉ−ｑｉ、ｐｉ＿ｊ＝ｗｉ＿ｊ−ｑｉ＿ｊ、ｐｉ＿ｊ＿ｋ＝ｗｉ＿ｊ＿ｋ−ｑｉ＿ｊ＿ｋ（ｉ、ｊ、ｋ＝1〜３）と記載することができる。ｗｉ、ｗｉ＿ｊ、ｗｉ＿ｊ＿ｋは、染色体において分割した領域ｒｉ，ｒｉ＿ｊ，ｒｉ＿ｊ＿ｋにおいて、対立遺伝子を発生することが可能な限度の数である。
【００７６】
遺伝的アルゴリズムの処理の過程において、フィットネス値の伸び率が鈍化したと判断した場合における初期値の導入に際し、ｐを参照することによって、ｐが大きいほど初期値が導入されていない程度が大きいことが認識することができるので、これによりｐが大きい領域に初期値を導入して初期値の偏在を防止することができる。これにより、準最適解に陥ってしまった場合においても初期値を導入してそこから脱出する確率を高めることができる。ここでｐは、添え字を省略したものであり、Ｌ１の分割領域において対立遺伝子が発生していない程度ｐ＿ｉ、Ｌ２の分割領域において対立遺伝子が発生していない程度ｑ＿ｉ＿ｊ、Ｌ３の分割領域において対立遺伝子が発生していない程度ｑ＿ｉ＿ｊ＿ｋ（ｉ、ｊ、ｋ＝１〜３）を表すものである。
【００７７】
また図６に示す本実施例では、Ｌ３の分割領域において、２７分割されておらず、例えばＬ１の領域がｒ１＿１であり、Ｌ２の領域がｒ２＿２である場合のｒ３＿２が存在しないが、これは初期値が導入されていないことを示すものである。情報処理装置上において、遺伝的アルゴリズムの処理を行う場合、染色体におけるすべての分割領域を予め用意しておくことは、大きなメモリが必要となり処理が効率的ではないため、初期値が導入されて初めてその分割領域を割り当てる処理とすることを意味するものである。したがって、図６において図示されていない分割領域には、初期値がまだ導入されていないことを意味するものである。
【００７８】
図６は、対立遺伝子が選択されていない程度を反映した概念図である。
【００７９】
初期値が初めて発生したときに、初期値を発生する範囲を作成する構成とする。
【００８０】
図６では、Ｌ１の分割領域［１］であって、Ｌ２の分割領域［２］である場合の、Ｌ３の分割領域［２］は、初期値が未発生のため分割領域として存在しない。同様にして、Ｌ１の分割領域［２］であって、Ｌ２の分割領域［１］である場合の、Ｌ３の分割領域［１］や、その他図６中にのＬ３で存在しない分割領域も、初期値が発生していないため、まだ存在しない状態を表している。
【００８１】
本実施例では、過去に初期値が選択されていない程度すなわち、前述ｐの値が高い程、次に初期値を発生する確率が高くなるとする。
【００８２】
また図６では、各遺伝子が、過去に初期値として選択されていない程度、即ち初期値として発生したい程度が大きいほど、横幅が大きく示されている。例えば、（Ｌ１、Ｌ２、Ｌ３）が（ｒ１＿２、ｒ２＿１、ｒ３＿３）である染色体を発生したい程度は、ｐ２＿１＿３の分割領域の横幅の大きさで示されており、他の分割領域との間の、相対的な横幅の大きさの関係で示されている。新たに染色体の初期値を発生する場合には、０以上１以下の乱数値（実数値）を発生する。図６の表の左端を０、右端を１に対応させ、乱数値に対応する位置の染色体パターンを見出して、初期値を発生する。
【００８３】
図７は、発生染色体分布格納装置１０２に格納されている遺伝子の選択回数データ格納構造を示す図である。
【００８４】
対立遺伝子を導入していき、同一の領域に導入される遺伝子の数を格納するデータ構造は、ツリー構造としてデータを格納する。便宜的に染色体Ｌ１、Ｌ２、Ｌ３の順でリーフが形成されているとする。以下、各染色体Ｌ１、Ｌ２、Ｌ３における対立遺伝子が発生する領域をノードと呼ぶ。そして各ノードは、図６において説明したように、そのノードに対応する対立遺伝子が発生した場合において、初めて作成する構成とする。遺伝的アルゴリズムの処理過程を通じて、新たな染色体が発生するごとに、必要に応じてツリー上に新ノードを発生することは処理を行う上でメモリ使用の効率化につながり処理が軽くなるという利点がある。もちろん、全染色体において各ノードを予め用意しておいてもよく、発生した対立遺伝子を、用意しておいたノードの格納していく構成であっても構わない。具体的には、新たな染色体が発生するごとに、ツリー上の既存ノードのｑ（ｑｉ、ｑｉ＿ｊ、ｑｉ＿ｊ＿ｋ）の値を増加させるか、ノードが存在しない場合には、新たなノードを発生し、対応するｑの値を新たに作成する。このようにして遺伝的アルゴリズムの処理を行い、ｑの値に応じて初期値の導入を行っていく。
【００８５】
また一般的に、染色体の長さが或る程度以上長くなると、発生し得る染色体パターン数に対して、発生する染色体のパターン数は、相対的に小さくなる傾向にあるため、ツリーは、全染色体パターンを表現した場合のツリーに比べて、比較的多数のノードを除去したツリーとなる。もちろん遺伝的アルゴリズムの処理を行う過程において、最適解がなかなか得られず、初期値導入の偏在を防止した結果として、ほぼ全染色体パターンのノードが存在するツリー構造となっても構わない。
【００８６】
本実施例の図７に記載のツリーは、各矢印の方向に向かって、発生した染色体がそのノードに対応するものであるか否かを判断していく構成とする。ツリーの各ノードに記載のｒ１＿１やｑ１は上記に記載したものと同じ意味を表すものである。例えば、Ｌ１においては領域ｒ１＿２であって、Ｌ２においては、領域ｒ２＿３であって、Ｌ３においては領域ｒ３＿１において対立遺伝子が発生した場合には、まずＬ１において、ｒ１＿２に対応するノードが存在するかを判断し、対応するノードが存在する場合には、そのノードをたどってＬ２のノードを参照し、領域ｒ２＿３に対応するノードが存在するか否かを判断する。そしてｒ２＿３に対応するノードが存在する場合には、同様にしてＬ３のノードを参照し、領域ｒ３＿１に対応するノードが存在するかを判断して、対応するノードが存在する場合には、ｑの値すなわちｑ２＿３＿１の値を更新する。上記各染色体におけるノードの存在の有無の判断においてノードが存在しないと判断した場合には、対応するノードを新たに作成して、初期染色体を発生し、そのノードに対応するｑの値も作成する。
【００８７】
図８は、染色体の分割数を一般化した場合の染色体の概念図である。
【００８８】
図４の場合と同様にして、染色体Ｌ１における分割領域を識別するために［１］、［２］、［３］・・・［ｉ］・・・［ｉｍａｘ］と番号を付す。Ｌ２、Ｌ３においても［１］、［２］、［３］・・・［ｊ］・・・［ｊｍａｘ］、［１］、［２］、［３］・・・［ｋ］・・・［ｋｍａｘ］と番号を付すが、図４の場合と同様にしてそれぞれＬ１、Ｌ２の領域［１］、［２］、［３］・・・［ｉｍａｘ］、［１］、［２］、［３］・・・［ｊｍａｘ］内での番号［１］、［２］、［３］・・・［ｊｍａｘ］、［１］、［２］、［３］・・・［ｋｍａｘ］である。これはもちろん上記と同様にして、それぞれの染色体において通し番号であっても構わない。ｑ（ｑｉ，ｑｉ＿ｊ，ｑｉ＿ｊ＿ｋ）は対応する分割領域における対立遺伝子の発生した数、ｐ（ｐｉ，ｐｉ＿ｊ，ｐｉ＿ｊ＿ｋ）は対応する分割領域における対立遺伝子が発生していない程度、ｗ（ｗｉ，ｗｉ＿ｊ，ｗｉ＿ｊ＿ｋ）は対応する分割領域における対立遺伝子を発生することが可能な限度の数である。ｗ＝ｐ＋ｑの関係にあるものと定義する。
【００８９】
それぞれの染色体Ｌ１、Ｌ２、Ｌ３において、Ｌ１はｉｍａｘの数だけ分割領域が存在し、Ｌ２はｊｍａｘの数だけ分割領域が存在し、Ｌ３はｋｍａｘの数だけ分割領域が存在する。ｉｍａｘ、ｊｍａｘ、ｋｍａｘは、同じであっても構わないし、同じでなくても構わない。
【００９０】
そしてｑ、ｐ、ｗの累積値を、Ｑ、Ｐ、Ｗと表し、Ｑ１〜ｉは、Ｌ１におけるｑ１からｑｉの和であって、Ｑ１〜ｉ＝Σｑｘ（ｘ＝１〜ｉ）である。同様にして、Ｐ１〜ｉはＬ１におけるｐ１からｐｉの和であって、Ｐ１〜ｉ＝Σｐｘ（ｘ＝１〜ｉ）であり、Ｗ１〜ｉはＬ１におけるｗ１からｗｉの和であって、Ｗ１〜ｉ＝Σｗｘ（ｘ＝１〜ｉ）である。染色体Ｌ２については、Ｑｉ＿（１〜ｊ）＝Σｑｉ＿ｘ（ｘ＝１〜ｊ），Ｐｉ＿（１〜ｊ）＝Σｐｉ＿ｘ（ｘ＝１〜ｊ），Ｗｉ＿（１〜ｊ）＝Σｗｉ＿ｘ（ｘ＝１〜ｊ）と記載することができ、Ｌ３についても、Ｑｉ＿ｊ＿（１〜ｋ）＝Σｑｉ＿ｊ＿ｘ（ｘ＝１〜ｋ），Ｐｉ＿ｊ＿（１〜ｋ）＝Σｐｉ＿ｊ＿ｘ（ｘ＝１〜ｋ），Ｗｉ＿ｊ＿（１〜ｋ）＝Σｗｉ＿ｊ＿ｘ（ｘ＝１〜ｋ）と記載することができる。
【００９１】
これらの累積値を考慮することによって、対立遺伝子が発生していない場所すなわちｐの値が大きい場所を効率よく識別することができ、対立遺伝子が発生していない分割領域もしくは対立遺伝子の発生頻度の低い分割領域に初期値となる対立遺伝子を導入し、遺伝的アルゴリズムを実行処理することができる。具体的には、発生させる初期値の対立遺伝子が決定した後、累積値Ｐ（Ｐ１〜ｉ、Ｐｉ＿（１〜ｊ）、Ｐｉ＿ｊ＿（１〜ｋ））に１以下の乱数値を掛け合わせ、対応する分割領域を見出すことにより遺伝的アルゴリズム処理をより効率的にすることができる。
【００９２】
ｗに関して、遺伝的アルゴリズムの処理を行っていく過程において最適解が得られる前に、分割領域において発生可能な限界値ｗになってしまった場合には必要に応じてｗの値を新たに更新し、続けて発生可能な分割領域としても構わない。また累積値の発生は、
また導入した初期値を発生染色体分布格納装置１０２に格納し終えた後に導入した分割領域のｑ、ｐ、ｗを更新してそれらの累積値Ｑ、Ｐ、Ｗも更新する。
【００９３】
図７に示したツリー状のデータ格納構造と同様に図８も便宜的に染色体Ｌ１、Ｌ２、Ｌ３の順でリーフが形成されている。
【００９４】
各ノードは、そのノードに対応する対立遺伝子が発生した場合において、初めて作成する構成となっている。
【００９５】
新たな染色体が発生するごとに、ツリー上の既存ノードのｑ（ｑｉ、ｑｉ＿ｊ、ｑｉ＿ｊ＿ｋ）の値を増加させるか、ノードが存在しない場合には、新たなノードを発生し、対応するｑの値を新たに作成する。
【００９６】
ツリーは、Ｌ１、Ｌ２、Ｌ３の順に、初期値を発生するノードを判断していく構成とする。
【００９７】
ここで、Ｌ１においては、分割領域［ｉ］からのみツリーが形成されており、Ｌ２においては、分割領域［ｊ］からのみツリーが形成されているが、これは表記を簡略化したものであって、他の分割領域からツリーが形成されていないことを示すものではない。もちろん、Ｌ１においては、分割領域［ｉ］からのみツリーが形成され、Ｌ２においては、分割領域［ｊ］からのみツリーが形成される場合もあり得る。
【００９８】
そして、それぞれの分割領域に対して、対立遺伝子の発生した数ｑ（ｑｉ，ｑｉ＿ｊ，ｑｉ＿ｊ＿ｋ）、対立遺伝子が発生していない程度ｐ（ｐｉ，ｐｉ＿ｊ，ｐｉ＿ｊ＿ｋ）、対立遺伝子を発生することが可能な限度の数ｗ（ｗｉ，ｗｉ＿ｊ，ｗｉ＿ｊ＿ｋ）を遺伝的アルゴリズム処理上で更新していく。
【００９９】
Ｌ１、Ｌ２、Ｌ３の順に、それぞれの染色体の対立遺伝子を効率よく求めるために、ツリーの形成時点で、各染色体Ｌ１、Ｌ２、Ｌ３の途中に、ｑ  （ｑｉ，ｑｉ＿ｊ，ｑｉ＿ｊ＿ｋ）の累計値Ｑを用意する構成にしておく。
【０１００】
その際、ノードが存在しない部分については、隣接する分割領域の関係から、そのノード数を求める。また、ｑ（ｑｉ，ｑｉ＿ｊ，ｑｉ＿ｊ＿ｋ）から、ｐ（ｐｉ、ｐｉ＿ｊ，ｐｉ＿ｊ＿ｋ）を求め、存在しないノードの横幅の大きさを計算する。
【０１０１】
図９は、図８に記載の染色体Ｌ１、Ｌ２、Ｌ３におけるｑ、ｐ、ｗの関係を模式的に表した概念図である。
【０１０２】
それぞれの段は上から順に染色体Ｌ１、Ｌ２、Ｌ３を表すものである。そして分割領域は、スロット９００、９０１などの高さで表され、ｗ＝ｑ＋ｐの関係を満たすことを視覚的に表している。そしてｐ（ｐｉ，ｐｉ＿ｊ，ｐｉ＿ｊ＿ｋ）の値が大きいほど、つまりスロットのｐの占める面積が大きい領域ほど、初期値を発生する確率が大きいことを示す。
【０１０３】
Ｌ２についてのスロットは、Ｌ１の分割領域が［ｉ］である場合を示し、Ｌ３についてのスロットは、Ｌ１の分割領域が［ｉ］、Ｌ２の分割領域が［ｊ］の場合を示す。スロット９００〜９０４は、Ｌ１の分割領域であり、対応する対立遺伝子が発生した発生した分割領域のみ存在する。そのため、スロット９０２と９０３の間のスロットにおいて、対立遺伝子が未だに発生していない場合には、対応するスロットは存在していないとする。同様にしてスロット９０３と９０４の間、スロット９０７と９０８の間、スロット９０８と９０９の間、スロット９１２と９１３の間、スロット９１３と９１４の間においても対応する対立遺伝子が存在しない場合には、対応するスロットも存在していないとする。
【０１０４】
図１０は、本実施例にかかる発生染色体分布格納装置１０２において行われる頻度分布を更新する処理のフローチャートである。
【０１０５】
まず、反映対象染色体に対応するリーフが、すでに図７に示すツリー構造に存在するか判断する（ステップＳ１００１）。反映対象染色体とは、新たに導入する染色体であって、初期染色体発生装置１０１によって、発生される染色体のことである。
【０１０６】
反映対象染色体に対応するリーフがすでにツリー構造に存在する場合には（ステップＳ１００１  ＹＥＳ）、ツリーのルートから対応するリーフに至る経路上で、必要な情報の更新を行う（ステップＳ１００２）。
【０１０７】
反映対象染色体に対応するリーフがツリー構造に存在しない場合には（ステップＳ１００１  ＮＯ）、ツリーに必要なリーフを新たに追加し、ルートからリーフに至る経路、及びその周辺経路上で、必要な情報の格納、更新を行う（ステップＳ１００３）。
【０１０８】
通常、フィットネス値の変化率が鈍化して初期値を再び導入する場合に、導入する対立遺伝子の数は複数である。そのため、初期分布を更新する際には、導入する対立遺伝子一つずつに関して、順次上記の判断を行い更新するものとする。
【０１０９】
もちろん、これは他の構成であってもよく、複数の対立遺伝子を導入した際に、複数の対立遺伝子の更新処理を平行して処理する構成であっても構わない。
【０１１０】
また、ステップＳ１００３において、反映対象染色体に対応するリーフがツリー構造に存在しない場合には、ツリーに必要なリーフを新たに追加するが、これは他の構成であってもよく、予め初期染色体が発生可能なすべてのリーフを用意しておく構成でもよい。
【０１１１】
図１１は、本実施例にかかる初期染色体発生するフローチャートである。
【０１１２】
まず、ＧＡ実行装置１００において乱数ｄを発生させる（ステップＳ１１０１）。ｄは０よりも大きい値であって、１以下の値である。
【０１１３】
発生した乱数ｄを用いてあらたにＰ´＝Ｐ・ｄを定義する（ステップＳ１１０１）。パラメータｚを定義しておき、ｚ＝１とする（ステップＳ１１０３）。ここでｚは、いずれの染色体かを表すものである。図１１に記載のフローチャートでは、染色体をレイヤＬｚと呼ぶ。ｚの値は自然数であり、値が大きくなるほど、ツリー構造において深くなる構成となっている。本実施例において、Ｐを用いて初期値を投入するか否かの範囲を選択しているが、これはＱを用いた構成であっても構わない。
【０１１４】
そして発生染色体分布格納装置１０２に格納されている頻度分布において、Ｐ´に相当する範囲がレイヤＬｚのノード不在領域か否かを判断する（ステップＳ１１０４）。頻度分布は図７に示すようなツリー構造によって発生染色体分布格納装置１０２に格納されている。
【０１１５】
Ｐ´に相当する範囲がレイヤＬｚのノード不在領域に存在しない場合には（Ｓ１１０４  ＮＯ）、レイヤＬｚでＰ´に相当する範囲に対応するノードを選択する（ステップＳ１１０５）。選択したノードがツリー構造における末端ノードか否かを判断する（ステップＳ１１０６）。末端のノードでない場合には（ステップＳ１１０６  ＮＯ）、ｚ＝ｚ＋１としてステップＳ１１０４に戻り、下のレイヤに移動して、Ｐ´に相当する範囲がノード不在領域に存在するか否かを判断する。末端のノードの場合には（ステップＳ１１０６  ＹＥＳ）、ノードに対応する範囲に初期染色体を発生する（ステップＳ１１０８）。
【０１１６】
発生染色体分布格納装置において、Ｐ´に相当する範囲がレイヤＬｚのノード不在領域に存在する場合には（ステップＳ１１０４  ＹＥＳ）、その範囲に初期値を発生して初期値発生処理を終了する（ステップＳ１１０９）。この際に初期染色体の発生染色体分布格納装置１０２の登録は行わない。
【０１１７】
本実施例における遺伝的アルゴリズムの適用対象問題は、非組み合わせ問題に限られることはなく、組み合わせ問題においても適用することは可能である。
【０１１８】
また遺伝的アルゴリズムは、適用する環境に応じて決定するあらゆるパラメータが存在する。例えば、個体群中の個体数、交叉確率、突然変異確率、世代ギャップ、世代交代回数などである。これらのパラメータは、解く問題に応じて適宜決定するものとする。
【０１１９】
次に、以上述べた本発明の最適解探索装置の実施形態の変形例、その他の技術的な拡張事項等を以下に列挙する。
【０１２０】
（１）  上記実施形態では、情報処理装置としてパーソナルコンピュータを例にとり、説明したが、これに限定されるものではなく、グリッドコンピュータも含むものである。
【０１２１】
（２）  上記実施形態では、遺伝子値は連続値を例にとり説明したがこれに限定されるものではなく、これは離散値であってもよい。
【０１２２】
（３）  上記実施形態では、Ｌ１、Ｌ２、Ｌ３の染色体の分割数を同一としたがこれに限定されることはなく、各染色体の分割数は異なっていても構わない。
【０１２３】
（４）  上記実施形態では、染色体の数は３つにしたがこれに限定されるものではなく、他の数であってもよい。
【０１２４】
次に、以上述べた最適解探索装置の実施形態から抽出される技術的思想を請求項の記載形式に準じて付記として列挙する。本発明に係る技術的思想は上位概念から下位概念まで、様々なレベルやバリエーションにより把握できるものであり、以下の付記に本発明が限定されるものではない。
【０１２５】
（付記１）  複数の情報体からなる情報体集団を用いて、遺伝的アルゴリズムにより探索操作を行い、所定の環境への適応度を示す適応度値に基づいて、該環境における最適解もしくは最適解に近い準最適解を求める最適解探索装置において、
該探索操作が繰り返される過程において、各情報体に係る該適応度値の変化率と予め定められた変化率とを比較する適応度値変化率比較手段と、
該適応度値変化率比較手段において、前記適応度値の変化率が、前記予め定められた変化率より小さいと判断した場合、新たな情報体を導入する情報体導入手段と、
該情報体導入手段により導入する情報体を構成する値が取り得る範囲を複数の領域に分割して分割領域を生成する分割領域生成手段と、
それぞれの該分割領域における新たに導入される情報体の導入頻度より成る分布情報を記憶する導入情報体分布格納手段とからなる最適解探索装置であって、
該情報体導入手段は、該分布情報を参照して、情報体密度がより小さい領域に対して新たに情報体を導入することを特徴とする最適解探索装置。
【０１２６】
（付記２）  複数の情報体からなる情報体集団を用いて、遺伝的アルゴリズムにより探索操作を行い、所定の環境への適応度を示す適応度値に基づいて、該環境における最適解もしくは最適解に近い準最適解を求める最適解探索装置において、
該探索操作が繰り返される過程において、各情報体に係る該適応度値の変化率と予め定められた変化率とを比較する適応度値変化率比較手段と、
該適応度値変化率比較手段において、前記適応度値の変化率が、前記予め定められた変化率より小さいと判断した場合、新たな情報体を導入する情報体導入手段と、
該情報体導入手段により導入する情報体を構成する値が取り得る範囲を複数の領域に分割して分割領域を生成する分割領域生成手段と、
それぞれの該分割領域における新たに導入される情報体の導入頻度と該探索操作によって生成された情報体の生成頻度より成る分布情報を記憶する導入情報体分布格納手段とからなる最適解探索装置であって、
該情報体導入手段は、該分布情報を参照して、情報体密度がより小さい領域に対して新たに情報体を導入することを特徴とする最適解探索装置。
【０１２７】
（付記３）  複数の情報体からなる情報体集団を用いて、遺伝的アルゴリズムにより探索操作を行い、所定の環境への適応度を示す適応度値に基づいて、該環境における最適解もしくは最適解に近い準最適解を求める最適解探索装置において、
該探索操作が繰り返される過程において、各情報体に係る該適応度値の変化率と予め定められた変化率とを比較する適応度値変化率比較手段と、
該適応度値変化率比較手段において、前記適応度値の変化率が、前記予め定められた変化率より小さいと判断した場合、新たな情報体を導入する情報体導入手段と、
該情報体導入手段により導入する情報体を構成する値が取り得る範囲を複数の領域に分割して分割領域を生成する分割領域生成手段と、
それぞれの該分割領域における該探索操作によって生成された情報体の生成頻度より成る分布情報を記憶する導入情報体分布格納手段とからなる最適解探索装置であって、
該情報体導入手段は、該分布情報を参照して、情報体密度がより小さい領域に対して新たに情報体を導入することを特徴とする最適解探索装置。
【０１２８】
（付記４）  付記１乃至３に記載の最適解探索装置において、
該情報体導入手段は、該分布情報に基づいて、情報体密度がより小さい領域程、より高い確率で新たに情報体を導入することを特徴とする最適解探索装置。
【０１２９】
（付記５）  該導入情報体分布格納手段は、各情報体を所定の順に並べて階層構造とし、各情報体の該分布情報をツリー構造として格納することを特徴する付記１に記載の最適解探索装置。
【０１３０】
（付記６）  該分割領域生成手段は、該情報体を構成する値が存在しない分割領域は生成しないことを特徴とする付記１に記載の最適解探索装置。
【０１３１】
（付記７）  該導入情報体分布格納手段は、各分割領域における情報体の数を累積して、累積値を算出することを特徴とする付記１に記載の最適解探索装置。
【０１３２】
（付記８）  該導入情報体分布格納手段は、１以下の乱数を発生させて、該乱数と該累積値と掛け合わせた分割領域判定値を算出し、該分割領域判定値に基づいて、分布情報を記憶することを特徴とする付記４に記載の最適解探索装置。
【０１３３】
（付記９）  該情報体導入手段は、予め定められた所定の導入情報体の数に達した分割領域には、情報体を導入しないことを特徴とする付記１に記載の最適解探索装置。
【０１３４】
（付記１０）  該情報体導入手段は、分割領域における導入情報体の数が、予め定められた所定の導入可能情報体数に達した場合には、さらに導入可能情報体数を増加させることを特徴とする付記１に記載の最適解探索装置。
【０１３５】
（付記１１）  複数の情報体からなる情報体集団に対し、遺伝的アルゴリズムを用いて探索操作を行い、所定の環境への適応度を示す適応度値に基づいて、該環境における最適解もしくは最適解に近い準最適解を求める最適解探索方法において、
該探索操作が繰り返される過程において、各情報体に係る該適応度値の変化率と予め定められた変化率とを比較する適応度値変化率比較手順と、
該適応度値変化率比較手順において、前記適応度値の変化率が、前記予め定められた変化率より小さいと判断した場合、新たな情報体を導入する情報体導入手順と、
該情報体導入手順により導入する情報体を構成する値が取り得る範囲を複数の領域に分割して分割領域を生成する分割領域生成手順と、
それぞれの該分割領域における新たに導入される情報体の導入頻度より成る分布情報を記憶する導入情報体分布格納手順とからなる最適解探索方法であって、
該情報体導入手順は、該分布情報を参照して、情報体密度がより小さい領域に対して新たに情報体を導入することを特徴とする最適解探索方法。
【０１３６】
（付記１２）
複数の情報体からなる情報体集団を用いて、遺伝的アルゴリズムにより探索操作を行い、所定の環境への適応度を示す適応度値に基づいて、該環境における最適解もしくは最適解に近い準最適解を求める最適解探索装置において、
該探索操作が繰り返される過程において、各情報体に係る該適応度値の変化率と予め定められた変化率とを比較する適応度値変化率比較手段と、
該適応度値変化率比較手段において、前記適応度値の変化率が、前記予め定められた変化率より小さいと判断した場合、新たな情報体を導入する情報体導入手段と、
該情報体導入手段により導入する情報体を構成する値が取り得る範囲を複数の領域に分割して分割領域を生成する分割領域生成手段と、
それぞれの該分割領域における新たに導入される情報体の数より成る分布情報を記憶する導入情報体分布格納手段とからなる最適解探索装置であって、
該情報体導入手段は、該分布情報を参照して、情報体数がより少ない領域に対して新たに情報体を導入することを特徴とする最適解探索装置。
【０１３７】
（付記１３）  複数の情報体からなる情報体集団を用いて、遺伝的アルゴリズムにより探索操作を行い、所定の環境への適応度を示す適応度値に基づいて、該環境における最適解もしくは最適解に近い準最適解を求める最適解探索装置において、
該探索操作が繰り返される過程において、各情報体に係る該適応度値の変化率と予め定められた変化率とを比較する適応度値変化率比較手段と、
該適応度値変化率比較手段において、前記適応度値の変化率が、前記予め定められた変化率より小さいと判断した場合、新たな情報体を導入する情報体導入手段と、
該情報体導入手段により導入する情報体を構成する値が取り得る範囲を複数の領域に分割して分割領域を生成する分割領域生成手段と、
それぞれの該分割領域における新たに導入される情報体の数と該探索操作によって生成された情報体の数より成る分布情報を記憶する導入情報体分布格納手段とからなる最適解探索装置であって、
該情報体導入手段は、該分布情報を参照して、情報体数がより少ない領域に対して新たに情報体を導入することを特徴とする最適解探索装置。
【０１３８】
（付記１４）  複数の情報体からなる情報体集団を用いて、遺伝的アルゴリズムにより探索操作を行い、所定の環境への適応度を示す適応度値に基づいて、該環境における最適解もしくは最適解に近い準最適解を求める最適解探索装置において、
該探索操作が繰り返される過程において、各情報体に係る該適応度値の変化率と予め定められた変化率とを比較する適応度値変化率比較手段と、
該適応度値変化率比較手段において、前記適応度値の変化率が、前記予め定められた変化率より小さいと判断した場合、新たな情報体を導入する情報体導入手段と、
該情報体導入手段により導入する情報体を構成する値が取り得る範囲を複数の領域に分割して分割領域を生成する分割領域生成手段と、
それぞれの該分割領域における該探索操作によって生成された情報体の数より成る分布情報を記憶する導入情報体分布格納手段とからなる最適解探索装置であって、
該情報体導入手段は、該分布情報を参照して、情報体数がより少ない領域に対して新たに情報体を導入することを特徴とする最適解探索装置。
【図面の簡単な説明】
【０１３９】
【図１】本実施例に係る染色体の図
【図２】対立遺伝子の範囲を表す図
【図３】本実施例に係る情報処理システムの構成図
【図４】遺伝子の選択回数の記録に関する概念図
【図５】対立遺伝子が選択されない程度を表す概念図
【図６】対立遺伝子が選択されていない程度を反映した概念図
【図７】遺伝子の選択回数データ格納構造を示す図
【図８】染色体の分割数を一般化した場合の染色体の概念図
【図９】ｑ、ｐ、ｗの関係を示す概念図
【図１０】頻度分布を更新する処理のフローチャート
【図１１】初期値発生に係るフローチャート
【符号の説明】
【０１４０】
１００…ＧＡ実行装置
１０１…初期染色体発生装置
１０２…発生染色体分布格納装置
【図１】
2007199943.tif 000003
【図２】
2007199943.tif 000004
【図３】
2007199943.tif 000005
【図４】
2007199943.tif 000006
【図５】
2007199943.tif 000007
【図６】
2007199943.tif 000008
【図７】
2007199943.tif 000009
【図８】
2007199943.tif 000010
【図９】
2007199943.tif 000011
【図１０】
2007199943.tif 000012
【図１１】
2007199943.tif 000013