(57)【要約】【課題】  本発明は、一つの環境条件内で、複数個の情報の組合せから最適な解を得る遺伝的アルゴリズムの探索処理を利用し、処理速度を向上し、短時間で容易に最適解を求めることができる最適解探索装置を提供する。【解決手段】  複数個の情報体(J1〜Jn）で形成された情報体集団S1から環境の要求する条件に最適な解を持つ情報体を求める最適解探索１は、入力された情報体集団S1の各情報体(J1〜Jn）に対して探索処理を施す探索処理手段３、情報体(J1〜Jn）の夫々が示す解の適応度値ｆを演算する適応度値演算手段４、各情報体(J1〜Jn）の適応度値の変化率Δｆ／ΔＧを演算する変化率演算手段９、適応度値の変化率Δｆ／ΔＧが鈍化した場合に、環境（探索空間）に於ける既存情報体からの変形の度合いを有する導入情報体群を、現在探索処理操作が行われている情報体集団から選択する導入情報体選択手段１４を含む。【選択図】      図１
2005209222.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも一つの情報を保持する情報体が複数個集合して形成された情報体集団を所定の環境内に配置させ、当該環境における評価において最適な解若しくはそれに近い解を有する情報体を求める最適解探索装置に於いて、
当該情報体集団を所定の環境内に導入する入力手段と、
入力された当該情報体集団に対して第１の探索処理操作に基づいて探索処理を行わせる探索処理手段と、
当該第１の探索処理に基づき、探索処理せしめた該情報体集団の該情報体のそれぞれが示す解が、設定されている環境に於ける最適な解と、どの程度適合しているかを示す、或いは最適解は分からなくても適応度を示す、適応度値（フィットネス値）を演算する適応度値演算手段と、
当該各情報体の適応度値と予め定められた当該環境で要求される適応度値とを比較して、最終的解が得られたか否かを判断する判定手段と、
当該判定手段が、未だ最終的解が得られていないと判断した場合には、該探索処理手段に対して当該第１の探索処理操作を繰り返す様に指示すると共に、最終的解が得られたと判断した場合、或いは、予め定めた許容（処理）繰返し回数に到達した場合、又は予め定めた許容処理時間が経過した場合、には該探索処理手段に対して当該第１の探索処理操作を終了する様に指示する探索処理操作制御手段と、
当該第１の探索処理操作が繰り返される過程に於いて、当該各情報体の適応度値の変化率を演算する変化率演算手段と、
該適応度値の変化率を予め定められた変化率と比較する適応度値変化率比較手段と、
当該適応度値変化率比較手段が、当該探索処理を施されて得られた情報体集団である世代ｉ（基準世代）に於ける各情報体の適応度値の変化率が、予め定められた当該変化率より低下したと判断した場合で、該探索処理操作制御手段が、該世代ｉ（基準世代）に対して、該第１の探索処理操作の再開を指示した場合に於いて、当該世代ｉ（基準世代）を構成する情報体集団から、少なくとも一つの導入情報体を適宜選択して、当該第１の探索処理操作に基づいた世代ｉ＋１を形成する為の探索処理が再開されている探索空間に導入する導入情報体選択手段と、
を有する事を特徴とする最適解探索装置。
【請求項２】
前記導入情報体選択手段に接続されており、当該世代ｉ（基準世代）から当該導入情報体を選択するに際して、当該選択される各導入情報体が、世代ｉ（基準世代）中の探索空間中に於いて、互いに異なる変形度合いを有する様に選択される為の選択基準を設定する選択基準設定手段を含んでいる事を特徴とする請求項１に記載の最適解探索装置。
【請求項３】
前記選択基準設定手段に於ける前記導入情報体の選択基準としては、選択された導入情報体が、世代ｉ（基準世代）中の探索空間中で、互いに距離が異なるものとなる様に、設定されている事を特徴とする請求項２に記載の最適解探索装置。
【請求項４】
当該導入情報体は、該世代ｉ（基準世代）に加えて、該世代ｉ以前の世代である世代ｉ−１、世代ｉ−２・・・等からも選択されるものである事を特徴とする請求項１乃至３の何れかに記載の最適解探索装置。
【請求項５】
当該導入情報体が有する変形の度合いは、変形処理操作に於ける処理操作パラメータに依存するものである事を特徴とする請求項１に記載の最適解探索装置。
【請求項６】
当該選択された１つ若しくは複数の導入情報体は、選択される当該世代ｉ（基準世代）、世代ｉ−１、世代ｉ−２・・・等の少なくとも何れか一つに於ける探索空間中に於いて、互いに異なる変形の度合いを有しており且つ、それぞれの変形の度合い毎に異なる頻度を持つ様に選択される事を特徴とする請求項１乃至５の何れかに記載の最適解探索装置。
【請求項７】
当該選択された複数の導入情報体は、当該選択後の当該変形度合いが、所定の範囲内となる様に選択されている事を特徴とする請求項２に記載の最適解探索装置。
【請求項８】
前記導入情報体選択手段は、当該世代ｉ（基準世代）を構成する情報体集団から、該導入情報体を選択する場合に於いて、少なくとも一つの導入情報体が該世代ｉ（基準世代）を構成する情報体集団に於ける探索空間に於いて、適宜の距離を持つ様に選択するに際し、当該選択した導入情報体の少なくとも一部に対して変形処理を行うものである事を特徴とする請求項１乃至４の何れかに記載の最適解探索装置。
【請求項９】
前記導入情報体選択手段は、当該世代ｉ（基準世代）を構成する情報体集団から、複数個の該導入情報体を選択するに際し、前記変形処理を実行した結果、該世代ｉ（基準世代）を構成する情報体集団に於ける探索空間に於いて、互いに異なる距離要素を有することになる複数の導入情報体を選択する様に構成されている事を特徴とする請求項８に記載の最適解探索装置。
【請求項１０】
前記導入情報体選択手段は、該選択変形処理の結果生じる互いに異なる複数種の距離要素を持つ該導入情報体に於いて、該複数種の距離要素毎に当該導入情報体の数を互いに異ならせる様に選択するものである事を特徴とする請求項９に記載の最適解探索装置。
【請求項１１】
前記導入情報体選択手段に接続して、導入情報体変形処理手段が設けられており、該導入情報体変形処理手段は、該導入情報体選択手段により選択された少なくとも一つの導入情報体に所定の変形処理を施す様に構成されている事を特徴とする請求項１乃至１０の何れかに記載の最適解探索装置。
【請求項１２】
前記探索処理手段には、当該世代ｉ（基準世代）、世代ｉ−１、世代ｉ−２・・・等を構成する各情報体集団の情報を記憶する記憶手段が設けられている事を特徴とする請求項４に記載の最適解探索装置。
【請求項１３】
前記導入情報体選択手段は、適宜の情報体を当該世代ｉ（基準世代）を構成する情報体集団から選択し、前記導入情報体変形処理手段により、該情報体の一部に変形処理を実行して当該導入情報体を形成するに際し、当該世代ｉ（基準世代）を構成する情報体集団を構成する複数個の情報体の内で、世代ｉ＋１を構成する情報体集団に引き継がれない情報体の中から情報体を選択し、当該変形処理を施すものである事を特徴とする請求項１１に記載の最適解探索装置。
【請求項１４】
前記導入情報体選択手段は、適宜の情報体を当該世代ｉ（基準世代）を構成する情報体集団から選択し、前記導入情報体変形処理手段により、該情報体の一部に変形処理を実行して当該導入情報体を形成するに際し、当該世代ｉ（基準世代）を構成する情報体集団を構成する複数個の情報体の内で、世代ｉ＋１を構成する情報体集団に引き継がれる情報体の中から情報体を選択し、当該変形処理を施すものである事を特徴とする請求項１１に記載の最適解探索装置。
【請求項１５】
前記変形処理は、当該世代ｉ（基準世代）を構成する情報体集団に於ける探索空間に於いて、選択された該情報体が、互いに異なる距離要素を有する様にするものである事を特徴とする請求項１３又は１４に記載の最適解探索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適解探索装置に関するものであり、更に詳しくは、一つの環境内に於いて、複数個の情報を組み合わせて最適な解を得るに際して、遺伝的アルゴリズム（ＧＡ）を適用して探索を行う最適解探索装置に関するものである。
【背景技術】
【０００２】
遺伝的アルゴリズムは、産業界に於いては、設計支援、製造支援、或いはスケジューリング等、多数の変数要素が組み合わされた状態で、所定の環境条件に適合する最適な解を求めると言う様な複雑な問題の解決に際して、有効な最適化手法の一つとしての利用が期待されている。
【０００３】
係る問題解決方法は、各種の問題解決に利用出来るが、主要な問題分野の一つとして、所謂数理計画問題があり、中でも代表的な問題として、トラベリングセールスパーソン問題がある。
この問題は、例えば、Ｎ箇所の地点を重複、欠落を許さずに最短距離でセールスパーソンが回れる巡回路を解として求めるものであって、全ての組み合わせを探索して、その目的に合った最適解を求めるものである。
【０００４】
係る問題に於ける最適解を求める場合、巡回すべき地域の数が増加すると共に、その為の演算処理時間が急激に増加する事になり、従来の遺伝的アルゴリズム（ＧＡ）による演算処理方法では、最適解を求める事が事実上不可能である事が認識されている。
その為、係る問題を解決する一つの方法として、上記した遺伝的アルゴリズム（ＧＡ）のより改良された方法による解決手法の導入が検討されて来ている。
【０００５】
即ち、上記した遺伝的アルゴリズムは、自然界に存在する染色体（遺伝子の配列）の変化態様を上記の様な数理計画問題の解を求める方法に応用しようとするものであり、該染色体は、自然界においては、或る染色体（又は染色体の組）を持つ複数の個体からなる集団が存在する時、主に生殖（リプロダクション）、交叉（クロスオーバー）及び突然変異（ミューテーション）と言う３種類の遺伝子操作を繰り返しながら、世代交代を繰り返し、その時代の環境に適合する最適な個体が生成され、当該環境に適合する最適な染色体を持った生物が生き残って行くと言うプロセスを繰り返している。
【０００６】
遺伝的アルゴリズム（ＧＡ）に於ける生殖は、前世代の個体の内、幾つかの環境に、より適合するものをより頻度高く選択する様な傾向を持つランダムな選択を行って現世代の個体を決定する操作であり、その結果の個体に対しては、次いで交叉処理を行い、少なくとも２個の個体に於けるそれぞれの染色体を部分的に相互に入れ替える事により新しい染色体を持った個体を子孫として生成するものであり、更にその後に突然変異を行い、子孫となる一部の個体に於ける染色体の一部を対立遺伝子に交換或いは変異せしめ、これらの染色体を持つ複数個の個体群で、新世代が形成する様にする。
【０００７】
そして、係る染色体の変形処理操作を、所定の環境に適合する最適な、又は最適でなくても十分適切な染色体を持つ個体が生成されるまで繰り返すものである。
係る遺伝的アルゴリズムを上記したトラベリングセールスパーソン問題に於ける最適解を求める演算方法に適用する場合には、例えば、一人のセールスパーソンが１００の都市を巡回する場合を前提とすると、例えば、図５に示す様に、それぞれの都市に番号を付与して、第１番目に回る都市１５、第２番目に回る都市１２、・・・・第１００番目に回る都市９６と言う一つの解を形成した情報体Ｊを作る事が出来、この１００個の情報体Ｊのそれぞれが特定の情報を含んだ染色体に見立てる事が出来る。
【０００８】
係る情報体Ｊとしては、それぞれの都市を巡回する順番をそれぞれ異ならせたものを形成する事が出来、従って、上記した情報体Ｊと同じ構造（フォーマット）を持つ互いに異なる（又は一部互いに等しいものもある）解を表現する複数個の情報体Ｊ１〜Ｊｍを生成する事が出来る。
係る複数個の情報体Ｊ１〜Ｊｍのそれぞれを染色体と見立てて、該トラベリングセールスパーソン問題と言う環境下に、最短時間で巡回すると言う最適解を求める為に上記した遺伝子操作を行わせる事が可能である。
【０００９】
然しながら、係る数理計画問題に対して、上記遺伝的アルゴリズムを適用して最適な解を探索する場合、上記した世代交代を繰り返して、ジェネレーションの値が大きくなると、ジェネレーションの値の増加に対する、解の評価値としての適応度値（フィットネス値）の増加の割合が減少する事が起こる。
つまり、フィットネス値の伸び率が鈍化すると言う問題が発生する。
【００１０】
係る問題が発生する理由を検討してみると、上記した遺伝的アルゴリズムによって所定の問題を解決する場合、多くの場合に於いて、フィットネス値の大きい個体、つまり情報体を得ることは、個別のフィットネス値の小さい情報体を得る事よりも一般的には難しい。
即ち、基本的には、確率的に進行される遺伝的アルゴリズム処理に於いて、フィットネス値の大きい個体、つまり情報体を得る確率は、そうでない場合に対して小さい。
【００１１】
また、該フィットネス値の大きい個体、つまり情報体の方が、正解とされる染色体の特定の情報の配列に近い情報の配列を多く含んでいる場合が多い。
その為、該遺伝的アルゴリズムに於いては、一般的には、常に当該情報体の集合である情報体集団の中で、フィットネス値の大きな個体、即ち情報体を維持しながら処理を行う事が多く、その結果、正解（最適解）の染色体に含まれる特定の情報の配列に近い情報の配列を持つ情報体が順次増加して、漸進的に正解（最適解）に近づく事になる。
【００１２】
ところが、係る処理方法に於いては、世代の増加と共に当該情報体集団のフィットネス値が未だ正解（最適解）または許容解から遠いにも係わらず、当該フィットネス値の伸びが鈍化する様な原因があり、その原因の一つとしては、当該情報体集団が局所的な最適点に陥っていると言う現象が発生している事が考えられる。
係る現象を回避する為の一つの方法として、該情報体集団が当該局所的な最適点から抜け出す為の方策として、当該情報体集団に新たな個体、即ち新たな導入情報体を意識的に外部から導入する方法がある。
【００１３】
係る方法により、当該情報体集団は、それに含まれる複数の情報体に関する多様性が増加して、当該情報体集団内の各情報体が、所定の探索空間内で広域に分布する事が可能となり、その結果、その後の遺伝的アルゴリズム処理操作によって、当該局所的な最適点から抜け出す確率が高まると考えられる。
然しながら、遺伝的アルゴリズムを用いた最適解探索方法に於ける上記の方法の内、従来のものに於いては、新たな個体、つまり導入情報体をランダムに発生させて、新しい世代を構成する情報体集団を生成しているが、特に、前世代に於ける優秀な情報体を引き継ぐ操作が行われている場合には、上記集団でのフィットネス値は、単調に増加することから、世代が進んで当該情報体集団のフィットネス値が新たな個体（情報体）のフィットネス値との乖離が生じてくる。
【００１４】
従って、このような乖離が発生する段階となると、新たな個体（情報体）は、当該情報体集団に於ける探索空間内で当該情報体集団から離れ過ぎてしまう事になり、その時点で当該情報体集団が目指す正解（最適解）の探索への貢献度が低いものとなる。
これは、上記の新たな個体（情報体）に於いては、該情報体集団に比べて、正解（最適解）の染色体に含まれる、特定の情報の配列に近い情報の配列を多く持つ情報体の数が少なくなるので、その結果その後の遺伝的アルゴリズム処理操作に於いて当該情報体集団にフィットネス値の大きな向上をもたらす確率が低くなる（向上効果の悪化）ためと考えられる。
【００１５】
その為、遺伝的アルゴリズム操作によって、新たな個体（情報体）が導入されても、当該導入情報体が当該情報体集団のフィットネス値の漸進的な向上に貢献する程度が低下する事になる。
その為、当該遺伝的アルゴリズム処理操作全体の処理速度は低速となり、一定世代数で到達する水準も低下する事になる。
【発明の開示】
【発明が解決しようとする課題】
【００１６】
本発明の課題は、上記した従来技術の欠点を改良し、一つの環境条件内に於いて、複数個の情報を組み合わせて最適な解を得るに際して、遺伝的アルゴリズムを適用して探索を行う最適解探索装置において、当該遺伝的アルゴリズム処理操作が進行して当該情報体集団のフィットネス値が大きくなると当該新たに発生した情報体（個体）のフィットネス値との差が大きくなり、当該新たに発生した情報体の当該情報体集団のフィットネス値改善への貢献度が低下するのを防止し、遺伝的アルゴリズム処理速度を向上させて、最適な解を容易に且つ短時間に求める事が出来る最適解探索装置を提供することである。
【課題を解決するための手段】
【００１７】
本発明は上記した目的を達成するため、基本的には以下に記載されたような技術構成を採用するものである。即ち、少なくとも一つの情報を保持する情報体が複数個集合して形成された情報体集団を所定の環境内に配置させ、当該環境における評価において最適な解若しくはそれに近い解を有する情報体を求める装置に於いて、当該情報体集団を所定の環境内に導入する入力手段、入力された当該情報体集団に対して第１の探索処理操作に基づいて探索処理を行わせる探索処理手段、当該第１の探索処理に基づき、探索処理せしめた該情報体集団の該情報体のそれぞれが示す解が、設定されている環境に於ける最適な解と、どの程度適合しているかを示す、或いは最適解は分からなくても適応度を示す、適応度値（フィットネス値）を演算する適応度値演算手段、当該各情報体の適応度値と予め定められた当該環境で要求される適応度値とを比較して、最終的解が得られたか否かを判断する判定手段、当該判定手段が、未だ最終的解が得られていないと判断した場合には、該探索処理手段に対して当該第１の探索処理操作を繰り返す様に指示すると共に、最終的解が得られたと判断した場合、或いは予め定めた許容（処理）繰返し回数に到達した場合、又は、予め定めた許容処理時間が経過した場合には、該探索処理手段に対して当該第１の探索処理操作を終了する様に指示する探索処理操作制御手段とから構成された最適解探索装置であって、当該最適解探索装置は更に、当該第１の探索処理操作が繰り返される過程に於いて、当該各情報体の適応度値の変化率を演算する変化率演算手段、該適応度値の変化率を予め定められた変化率と比較する適応度値変化率比較手段、当該適応度値変化率比較手段が、当該探索処理を施されて得られた情報体集団である世代ｉ（基準世代）に於ける各情報体の適応度値の変化率が、予め定められた当該変化率より低下したと判断した場合で、該探索処理操作制御手段が、該世代ｉ（基準世代）に対して、該第１の探索処理操作の再開を指示した場合に於いて、当該世代ｉ（基準世代）を構成する情報体集団から、少なくとも一つの導入情報体を適宜選択して、当該第１の探索処理操作に基づいた世代ｉ＋１を形成する為の探索処理が再開されている探索空間に導入して第２の探索処理を実行させる為の導入情報体選択手段、とから構成されている最適解探索装置である。
【発明の効果】
【００１８】
本発明に係る最適解探索装置は、上記した様な技術構成を採用しているので、一つの環境条件内に於いて、複数個の情報を組み合わせて最適な解を得るに際して、遺伝的アルゴリズムを適用して探索を行う最適解探索装置において、当該遺伝的アルゴリズム処理操作が進行して当該情報体集団のフィットネス値が大きくなると当該新たに発生した情報体（個体）のフィットネス値との差が大きくなり、当該新たに発生した情報体の当該情報体集団のフィットネス値改善への貢献度が低下するのを防止し、遺伝的アルゴリズム処理速度を向上させながら、最適な解を容易に且つ短時間に正確に求める事が出来る最適解探索装置を提供する事が可能となる。
【発明を実施するための最良の形態】
【００１９】
本発明に係る実施例を説明するにあたり、本発明に於いて使用される用語の内、「世代」及び「探索処理」等に関してその意味を以下の様に定義しておくことにする。
（１）「世代」：或る情報体集団に探索処理を施して、一つの解に到達した世代であって、その解のフィットネス値の変化率が予め定められた基準の変化率以下になったので、新たに本発明に基づいて探索処理を施す必要が生じた世代を世代ｉ（基準世代）と言う。
【００２０】
従って、基準世代ｉに対して新たに探索処理が開始されてから、新たな解に到達する迄の期間を次の世代、即ち世代ｉ＋１と称する。逆に基準世代ｉ以前の世代を世代ｉ−１、世代ｉ−２、・・・の様に称する。
（２）「探索処理」：或る世代ｉ（基準世代）を構成する情報体集団から世代ｉ＋１を構成する情報体集団を形成させる際の探索操作に於いて、かかる情報体集団に対してＧＡオペレーションを行う事を意味する。
【００２１】
かかるＧＡオペレーションとしては、従来から知られているＧＡオペレーション（以下第１の探索処理操作と言う）と、本発明に於いて使用される新規なＧＡオペレーション（以下第２の探索処理操作と言う）とがあり、前者、即ち従来から知られているＧＡオペレーション、即ち第１の探索処理操作としては、１）交又（クロスオーバー）、２）生殖（リプロダクション）、３）突然変異（ミューテーション）及び４）世代ｉ（基準世代）から優秀情報体の引継ぎ等の処理があり、係る各処理の少なくとも一つを実行するか、若しくはこれ等の各処理を適宜に組み合わせて実行されるものである。
【００２２】
また、後者、本発明に於いて使用される新規なＧＡオペレーション、即ち第２の探索処理操作としては、導入情報体の導入であって、世代ｉ（基準世代）の中から、別途に選択された情報体を、導入情報体として、現在探索処理が実行されている情報体集団（世代ｉ＋１を作りつつある情報体集団）に導入した上で、前記した第１の探索処理操作を実行するものであり、単に選択された情報体を導入する場合と、選択された情報体に変形処理を行った上で導入する場合とがある。
【００２３】
また、上記の導入情報体の選択基準としては、選択された導入情報体が、世代ｉ（基準世代）中の探索空間中で、互いに距離が異なるものとなる様に、選択するものである。
尚、本発明に於ける、新規なＧＡオペレーションとしては、導入情報体を、世代ｉ（基準世代）の中からのみ選択する場合と、世代ｉ（基準世代）及びそれ以前の世代ｉ−１、或いは、世代ｉ−２、・・・等の情報体集団の中から選択する様にしても良い。
（３）「探索空間」：上記探索処理が実行される空間。
（４）「最適化処理」：探索空間の中で、最適化条件を求めて探索操作を実行する事を言う。
【実施例】
【００２４】
以下に、本発明に係る最適解探索装置の一具体例の構成について、図面を参照しながら詳細に説明する。
即ち、図１は、本発明に係る最適解探索装置１の一具体例の構成例を示すブロックダイアグラムであって、図中、少なくとも一つの情報を保持する情報体Ｊが複数個（Ｊ１〜Ｊｎ）集合して情報体集団Ｓ１を所定の環境内に配置させ、当該環境における評価に際して最適な解、若しくはそれに近い解を有する情報体を求める装置１に於いて、ある世代の情報体集団から次の世代の情報体集団を形成させる為に、当該ある情報体集団Ｓ１を所定の環境内に導入する入力手段２、入力された当該情報体集団Ｓ１のそれぞれの情報体Ｊ１〜Ｊｎに対して第１の探索処理操作に基づいて探索処理を行わせる第１の探索処理部３−１を含む探索処理手段３、当該第１の探索処理に基づき、探索処理せしめた該情報体集団Ｓ１の該情報体Ｊ１〜Ｊｎのそれぞれが示す解が、設定されている環境に於ける最適な解と、どの程度適合しているかを示す、或いは最適解は分からなくても適応度を示す、適応度値ｆ（フィットネス値）を演算する適応度値演算手段４、当該各情報体Ｊ１〜Ｊｎの適応度値ｆと予め定められた当該環境で要求される適応度値ｆ０とを比較して、最終的解が得られたか否かを判断する判定手段７、当該判定手段７が、未だ最終的解が得られていないと判断した場合には、該探索処理手段３の第１の探索処理部３−１に対して、当該第１の探索処理操作を繰り返す様に指示すと共に、最終的解が得られたと判断した場合、或いは予め定めた許容（処理）繰返し回数に到達した場合、又は予め定めた許容処理時間が経過した場合には、該探索処理手段３に対して当該第１の探索処理操作を終了する様に指示する探索処理操作制御手段１２とから構成された最適解探索装置１であって、当該最適解探索装置１は更に、当該第１の探索処理操作が繰り返される過程に於いて、当該各情報体Ｊ１〜Ｊｎの適応度値ｆの変化率Δｆを演算する変化率演算手段９、該適応度値ｆの変化率Δｆを予め定められた変化率Δｆ０と比較する適応度値変化率比較手段１１、当該適応度値変化率比較手段１１が、当該探索処理を施されて得られた情報体集団Ｓ１である世代ｉ（基準世代）における各情報体の適応度値の変化率Δｆが、予め定められた当該変化率より低下したと判断した場合で、該探索処理操作制御手段１２が、該世代ｉ（基準世代）に対して、該第１の探索処理操作の再開を指示した場合に於いて、当該世代ｉ（基準世代）を構成する情報体集団Ｓ１から、少なくとも一つの導入情報体Ｊ’１〜Ｊ’ｎを適宜選択して、当該第１の探索処理操作に基づいた世代ｉ＋１を形成する為の探索処理が再開されている探索空間に導入して、第２の探索処理を該探索処理手段３に設けた第２の探索処理部３−２を介して実行させる導入情報体選択手段１４、とから構成されている最適解探索装置である。
【００２５】
即ち、本発明に係る最適解探索装置１に於いては、更に、当該情報体集団が配置される環境の条件を設定し、且つ当該環境条件に対する最適な解を設定する環境条件設定手段５及び当該最適な解と等しい値か或いは当該最適な解の値に限りなく接近した値ｆ０を設定しうる最適適応度値設定手段６、更には、該判定手段７により最後に得られた当該情報体集団の中の最も優秀な情報体（個体）のフィットネス値ｆが、該最適適応度値と等しくなった場合に、当該環境条件を満足する最適な解が得られたと判断し、その結果を世代ｉ＋１の情報体集団Ｓ２として出力する出力手段８が設けられている事が望ましい。
【００２６】
上記した本発明に於ける最適解探索装置１に於いては、最適適応度値設定手段６が設定する最適適応度値としては、例えば、当該最適な解の値の９０〜１００％の値である事が望ましい。
本発明に於ける該最適解探索装置１に於いて、通常では、該探索手段３に於いては、例えば、或る情報体集団Ｓ０（世代ｉ−１）に対し、該第１の探索処理部３−１に基づいて、前記した様に、当該環境におかれた複数個の情報体Ｊ１〜Ｊｎのそれぞれに対して、第１の探索処理操作である、増殖処理、交又処理並びに突然変異処理、更には優秀な個体（情報体）の引継ぎ等と言う遺伝的操作処理を順次に実行し、１世代の処理を行わせる。
【００２７】
その結果得られた当該情報体集団Ｓ１（世代ｉ）に於ける、各情報体Ｊ１〜Ｊｎのそれぞれに付いて、適応度値ｆ１〜ｆｎを求め、その結果から、例えば当該情報体集団Ｓ１に於ける、各情報体Ｊ１〜Ｊｎの内最高の適応度値ｆｍａｘを有する最優秀の情報体の適応度値ｆｍａｘと前記した最適適応度値ｆ０とを該判定手段７で比較し、当該情報体の適応度値ｆｍａｘが、該最適適応度値ｆ０と等しいか、或いは、それよりも大きな値を示す場合には、当該第１の探索処理により、当該環境に於ける最適な解が得られたと判断して、該出力手段８からその結果である情報集団Ｓ２（世代ｉ＋１の）を出力する。
【００２８】
然しながら、該判定手段７に於いて、当該情報体の適応度値ｆｍａｘでは、未だ当該環境に於ける十分な最適な解が得られていないと判断した場合には、当該探索処理操作制御手段１２が該探索処理手段３に対して、前記した探索処理操作を再度実行する様に指令を出し、当該探索処理手段３は、上記した第１の探索処理操作を繰り返して実行すると同時に、上記した第２の探索処理操作を実行して、世代ｉ＋１の情報体集団を生成する。
【００２９】
係る第１の探索処理操作に於いては、世代ｉの情報体集団を構成する複数個の情報体の内、該フィットネス値ｆの高い、優秀な解を持つ少なくとも一つの情報体が優先的に世代ｉ＋１の情報体集団に引き継がれる様にする事も出来る。
以後、かかる操作が複数回繰り返され、最終的には、目標となる最終的解が得られる事になる。
【００３０】
係る方法に於いては、上記した様に、図７に示す様に、探索空間に於けるフィットネス値ｆは、染色体の情報のパターンに対して、多くの場合、起伏のある空間的変化を示す。この様な空間の探索においては、図８に示す様に、世代数に対応した上記フィットネス値ｆの値は、世代数の増加に伴い次第に飽和してくるので、目標の最終的解に到達しえない場合が発生する。
【００３１】
その為、前記した様に、従来に於いては、係る問題を解決する為に、当該情報体集団にランダムに発生した導入情報体Ｊ’を外部から導入する方法が考えられており、図１中適宜の最終的解Ｊ”が、当該探索処理手段３に導入されている。
上記で説明した様に、ランダムに発生した導入情報体Ｊ”が、当該情報体集団Ｓ１に導入されると、図９に示す様に、新しく導入情報体Ｊ”が導入された時点で、該情報体集団Ｓ１の構成が変化するので、探索空間に於けるフィットネス値ｆは、既成の局所解から抜け出す事が出来、最適値に向けた新たな探索が開始される。
【００３２】
然しながら、係るランダムに発生した導入情報体Ｊ”を導入する方法を採用しても、上記した様な理由から、探索空間に於けるフィットネス値ｆの固定化及び該フィットネス値ｆの変化率Δｆ／ΔＧ値の鈍化が起こるので（ΔＧは、世代数の変化）、最終的解を得る事が出来ないか、或いは、最終的解を得るに至る演算操作に時間が係ると言う問題が有るので、本発明に於いては、当該導入情報体Ｊ”の導入方法に特殊な方法を採用し、上記した様な問題が発生しない様にしたものである。
【００３３】
本発明に於いて、上記したフィットネス値ｆの変化率Δｆ／ΔＧ値は、図１０に例示する様に、該フィットネス値演算手段４から出力される当該情報体集団Ｓ１を形成する各情報体Ｊ１〜Ｊｎのフィットネス値ｆの時間的変化Δｆを、世代数Ｇの時間的増加ΔＧで除算して求めるものであり、該変化率演算手段９に於いて、演算処理して求めるものである。
一方、当該フィットネス値ｆの変化率Δｆ／ΔＧ値が、飽和したか、或いは、所定の変化率Δｆ／ΔＧ値に対して鈍化してきたか否かは、フィットネス値ｆの変化率しきい値設定手段１０を設けて、該フィットネス値ｆの変化率しきい値設定手段１０に所定のしきい値ρを予め設定しておき、適宜の比較手段１１に於いて、当該現在のフィットネス値ｆの変化率Δｆ／ΔＧ値が該設定されたフィットネス値ｆの変化率しきい値ρを下回った場合には、当該フィットネス値ｆの変化率Δｆ／ΔＧ値が鈍化した、或いは、飽和したと判断し、その結果、前記定義に示す様な、世代ｉ（基準世代）に到達したものと判断する。
【００３４】
そして、本発明に於いては、係る判断結果を該探索処理操作制御手段１２に出力すると、該探索処理操作制御手段１２から、世代ｉ＋１を形成する為の新たな探索処理を該探索処理手段３に制御信号が出力され、最初に前記した第１の探索処理部３−１を駆動させて前記した第１の探索処理操作を開始すると同時に、前記した導入情報体選択手段１４と第２の探索処理操作を行う第２の探索処理部３−２にも所定の信号が出力され、上記世代ｉの情報体集団Ｓ１を構成する複数個の情報体Ｊ１〜Ｊｎの中から、予め設定された基準に適合する少なくとも一つの導入情報体Ｊ’ｍ、或いは複数個の導入情報体Ｊ’１〜Ｊ’ｎが選択され、上記した第１の探索処理操作が行われている探索空間内に導入され、第２の探索処理操作が開始される様に成っている。
【００３５】
つまり、本発明に於いては、上記した様に、該フィットネス値ｆの変化率Δｆ／ΔＧ値が鈍化した場合に、現在新たに探索処理が実行されている情報体集団Ｓ１（世代ｉ）に、該情報体集団Ｓ１（世代ｉ）を構成する複数個のＪ１〜Ｊｎの中から、予め定められた特定の選択基準に基づいて、適宜の一つ若しくは複数個の導入情報体Ｊ’を選択して導入する様にしたものである。
【００３６】
また、本発明に於いては、上記した新たに導入される導入情報体Ｊ’の数は、一つに限る事はなく、複数個が同時に導入されても良い。
更に、本発明に於いて、選択される当該１つ若しくは複数個の導入情報体Ｊ’は、当該情報体集団Ｓ１を構成する全ての情報体Ｊ１からＪｎの内、世代ｉ＋１の情報体集団Ｓ２に引き継がれる情報体を除いた情報体から選択されるものである事が望ましい。
【００３７】
また、他の方法としては、該導入情報体Ｊ’は、当該世代ｉを構成する情報体集団Ｓ１の全ての情報体Ｊ１〜Ｊｎの内、世代ｉ＋１の情報体集団Ｓ２に引き継がれる情報体から選択されたものでも良く、更には、当該世代ｉを構成する情報体集団Ｓ１を構成する全ての情報体Ｊ１〜Ｊｎの内、世代ｉ＋１の情報体集団Ｓ２に引き継がれる情報体と、世代ｉ＋１の情報体集団Ｓ２に引き継がれない情報体とのそれぞれから、適当な数の導入情報体Ｊ’１〜Ｊ’ｎを選択する事も可能である。
【００３８】
一方、本発明に於いては、当該導入情報体Ｊ’を、世代ｉ＋１の情報体集団を形成する為に、探索処理操作が実行されている探索空間に導入するに際しては、前記した様に、遺伝的アルゴリズムを用いた第２の探索処理操作に於いて、探索空間に於けるフィットネス値ｆが一定の値にはまり込まないで、然もフィットネス値変化率Δｆ／ΔＧ値が飽和しない様な状況を実現し得るような選択基準を採用するものであって、その一例としては、選択された当該導入情報体Ｊ’は、当該情報体集団Ｓ１に於ける一部の情報体Ｊを変形して生成されるものである。
【００３９】
係る処理操作を実現する為に、該最適解探索装置１は、更に、当該導入情報体選択手段１４に接続され、且つ、当該世代ｉ（基準世代）から当該導入情報体Ｊ’を選択するに際して、当該選択される各導入情報体Ｊ’が、世代ｉ（基準世代）中の探索空間中に於いて、互いに異なる変形度合いを有する様に選択される為の選択基準を設定する選択基準設定手段１３を含んでいる事が望ましい。
【００４０】
更に、本発明に於いては、該選択基準設定手段１３に於ける該導入情報体Ｊ’の選択基準としては、選択された導入情報体Ｊ’が、世代ｉ（基準世代）中の探索空間中で、互いに距離が異なるものとなる様に、設定されている事が望ましい。
当該導入情報体Ｊ’は、該世代ｉ（基準世代）に加えて、該世代ｉ以前の世代である世代ｉ−１、世代ｉ−２、・・・等からも選択されるもので有っても良い。
【００４１】
係る場合には、世代ｉ−１、世代ｉ−２、・・・等を、その時点でそれぞれ構成していた複数個の情報体Ｊ１〜Ｊｎを記憶しておく手段が設けられている事が必要であり、例えば、図１に示す様に、探索処理手段３と接続した情報体集団記憶手段１６を設ける事が望ましい。
つまり、本発明に於いて、該各情報体Ｊのフィットネス値ｆの変化率Δｆ／ΔＧが鈍化してきた場合に、選択される導入情報体Ｊ’の選択基準は、上記した導入情報体選択基準設定手段１３に予め設定されているものであり、当該導入情報体選択基準設定手段１３に、予め定められた複数の導入情報体選択基準の内から、該探索処理操作制御手段１２により適当な基準が選択される事になる。
【００４２】
そして、本発明に於ける基本的な該選択基準としては、上記した様に、当該探索処理を受けている情報体集団Ｓ１を構成する情報体Ｊを変形して生成する導入情報体Ｊ’を選択して導入し得るものであっても良く、該変形とは、上記したように遺伝的アルゴリズムに於ける突然変異の様な、該遺伝子の壊しかたを示すものである。
【００４３】
ここで、本発明に於ける情報体Ｊ’が有する変形の度合いは、変形処理操作に於ける処理操作パラメータに依存するものである。
また、本発明に於ける当該選択された複数の導入情報体Ｊ’１〜Ｊ’ｎは、導入直前の情報体集団Ｓ１を構成する各情報体Ｊを変形する度合いが、互いに変化する様にそれぞれ選択されるものであるか、所定の変形度合い毎に、異なる頻度がえられる様に選択されるものであっても良い。
【００４４】
即ち、本発明に於いては、当該選択された１つ若しくは複数の導入情報体Ｊ’１〜Ｊ’ｎは、選択される、当該世代ｉ（基準世代）、世代ｉ−１、世代ｉ−２、・・・等の少なくとも何れか一つに於ける探索空間中に於いて、互いに異なる変形の度合いを有しており且つ、それぞれの変形の度合い毎に異なる頻度を持つ様に選択されるものである。
【００４５】
また、本発明に於いては、当該選択された複数の導入情報体Ｊ’１〜Ｊ’ｎは、当該選択後の当該変形度合いが、所定の範囲内となる様に選択されている事が望ましい。
更に、本発明に於いては、上記した該変形の度合いは、該探索空間中に於ける距離要素を含むものであっても良い。
【００４６】
即ち、本発明に於いて、当該導入情報体選択手段１３は、当該世代ｉ（基準世代）を構成する情報体集団Ｓ１から、該導入情報体Ｊ’を選択する場合に於いて、少なくとも一つの導入情報体Ｊ’が該世代ｉ（基準世代）を構成する情報体集団Ｓ１に於ける探索空間に於いて、適宜の距離を持つ様に選択するに際し、当該選択した導入情報体Ｊ’の少なくとも一部に対して変形処理を行うものである。
【００４７】
本発明に於いて、係る距離的要素とは、従来のユークリッド空間に於ける距離の概念を当然含むと同時に、例えば、複数個の変数要素（座標要素）が存在する場合に、幾つかの変数要素の値が決定されると残りの変数要素の値が制約又は決定される様な関係に有る様な空間における距離関係を示す場合も含まれる。
より具体的には、図１１に示す情報体パターンと適応度値ｆで表される探索空間に於いて、或る点（例えば、情報体集団の個体）から各々距離Ｌ１、Ｌ２、Ｌ３離れた位置に存在する様な導入情報体Ｊ’１、Ｊ’２、Ｊ’３を選択する事が出来る。
【００４８】
つまり、新たに導入する導入情報体Ｊ’を情報体集団に於ける情報体で上記探索空間中で適当な距離を持ったもので構成する事になる。
その為、本発明に於いては、該導入情報体選択手段１３は、当該世代ｉ（基準世代）を構成する情報体集団Ｓ１から、複数個の導入情報体Ｊ’１〜Ｊ’ｎを選択するに際し、該変形処理を実行した結果、該世代ｉ（基準世代）を構成する情報体集団に於ける探索空間に於いて、互いに異なる距離要素を有することになる複数の導入情報体を選択する様に構成されているものである。
【００４９】
更に、本発明に於いては、該導入情報体選択手段１３は、該選択変形処理の結果生じる互いに異なる複数種の距離要素を持つ該導入情報体に於いて、該複数種の距離要素毎に当該導入情報体の数を互いに異ならせる様に選択するもので有っても良い。
また、他の具体例としては、探索空間内に存在する情報体集団Ｓ１を構成する情報体Ｊを変形した情報体を導入するものであり、図１１にも示される様に、或る情報体集団の或る点（個体）から適当な距離Ｌ１、Ｌ２、Ｌ３（Ｌ１、Ｌ２、Ｌ３は、互いに同一の長さで有ってもよく、又互いに異なるものであっても良い）だけそれぞれ離れた位置に存在する様な導入情報体Ｊ’１、Ｊ’２、Ｊ’３を導入するものである。
【００５０】
更に、本発明に於ける別の具体例としては、図１２に示す様に、それぞれの距離に応じて導入される導入情報体Ｊ’の頻度に変化を設けようとするものである。
更に、本発明に於ける上記具体例に於いては、該導入情報体に於ける変形の度合いに付いて変形の程度を、ある適宜に設定された範囲内に収める様にする事も可能である。
【００５１】
更に、本発明に於いては、上記の選択基準に従って選択された一つ若しくは複数個の導入情報体Ｊ’１〜Ｊ’ｎをそのままの形で該探索空間内に導入するものであってもよいが、当該選択された導入情報体Ｊ’１〜Ｊ’ｎの少なくとも一部の導入情報体に対して、所定の部分的変形処理操作を行う事が望ましい。
本発明に於ける当該導入情報体Ｊ’に施される変形処理は、図２（Ａ）に示す様に、当該導入情報体Ｊ’の一部の情報の配置位置を別の配置位置に移動させ、その間の他の情報をシフトさせるシフト方法、或いは、図２（Ｂ）に示す様に、当該導入情報体Ｊ’の一部の情報の配置位置を、他の情報の配置位置とそっくり入れ換えるスワップ方法、或いは、当該導入情報体Ｊ’の一部の複数の情報の配置位置を完全に反転させるインバージョン方法等のやり方がある。
【００５２】
また、本発明に於いては、該導入情報体選択手段１３に接続して、導入情報体変形処理手段１５が設けられており、該導入情報体変形処理手段１５は、該導入情報体選択手段１３により選択された少なくとも一つの導入情報体に所定の変形処理を施す様に構成されているものである。
即ち、係る変形処理操作は、図１に於ける導入情報体選択手段１４と該探索処理手段３との間に設けられ、該探索処理操作制御手段１２により制御される変形処理手段１５で所定の選択された方法を用いて実行されるものである。
【００５３】
当該変形処理操作は、該導入情報体選択手段１４により選択された全ての導入情報体に適用しても良く、又、必要な個数の該導入情報体にのみ適用するもので有ってもよい。
次に、本発明に於ける更に別の具体例に付いて説明するならば、前記した様に、本発明に於ける遺伝的アルゴリズムに於いては、一つの情報体集団のある世代ｉに対して探索処理操作を施し世代ｉ＋１の情報体集団を生成するに際し、基本的には、世代ｉの情報体Ｊに増殖処理、交叉処理、突然変異処理等の変形処理を施して得た或いは変形処理しない０個若しくは１個、若しくは数個の導入情報体Ｊ’を、新たに探索処理が開始された世代ｉ＋１の情報体集団に導入するが、同時に世代ｉに於ける０個若しくは１個、若しくは数個の最も優秀な情報体を、若しくは、更に優秀ではない一般の情報体も含めて世代ｉ＋１の情報体集団に引き継がせると同時に、その他の情報体に付いては、全く新しい情報体群を全くランダムに発生させて世代ｉ＋１の情報体集団に導入するか、上記した選択基準に従って所定の情報体を選択して導入するか、或いは上記の両者の方法を組み合わせて導入することにより、次世代の情報体集団を生成することになるが、前記した問題点を回避する為の、情報体の多様性化をより一層はかる為に、本具体例では、特に少なくとも一つの当該導入情報体を、当該探索処理操作が実行される直前の情報体集団にある情報体の内、新たな探索処理手段が施される新規の情報体集団に引き継がれることの無い、少なくとも一つの情報体から選択する様にするものである。
【００５４】
つまり、本具体例に於いては、世代ｉに於ける当該情報体群の内で、世代ｉ＋１の情報体集団に引き継がれない、所謂消え行く運命に有る情報体群を選択し、当該選択された消え行く運命に有る情報体に上記の変形処理を施して、世代ｉ＋１の情報体集団に導入する様にするものである。
係る具体例に於いては、現世代の情報体集団に於ける消え行く運命に有る情報体群の全てに当該変形処理を施して世代ｉ＋１を形成する情報体集団を生成する探索空間に導入しても良く、その一部に対して当該変形処理を施して次世代情報体集団を生成する探索空間に導入しても良く、更には、世代ｉ＋１の情報体集団に引き継がれる情報体に対しても係る変形処理操作を併用する事も可能である。
【００５５】
また、本具体例に於いても、選択される世代ｉの情報体集団に於ける消え行く運命に有る情報体群の全て対して、前記した様に、該導入情報体選択基準設定手段１３により設定される導入情報体選択基準が適用される事も可能であり、従って、係る場合には、選択される世代ｉの情報体集団に於ける消え行く運命に有る情報体群も、所定の探索空間に於ける所定の距離を有すること、又当該距離が、複数種の異なる距離を含んでいる事、更には、当該複数の互いに異なる探索空間に於ける距離のそれぞれに対して、選択される情報体の数が異なる様に構成される事も可能である。
【００５６】
即ち、上記本発明に於ける具体例を実現する為、該導入情報体選択手段１３は、適宜の情報体を、当該世代ｉ（基準世代）を構成する情報体集団から選択し、該導入情報体変形処理手段１５により、該情報体の一部に変形処理を実行して当該導入情報体を形成するに際し、当該世代ｉ（基準世代）を構成する情報体集団を構成する複数個の情報体の内で、世代ｉ＋１を構成する情報体集団に引き継がれない情報体の中から情報体を選択し、当該変形処理を施す様に構成されているものである。
【００５７】
更に、本発明に於ける該導入情報体選択手段１３は、適宜の情報体を、当該世代ｉ（基準世代）を構成する情報体集団から選択し、該導入情報体変形処理手段１５により、該情報体の一部に変形処理を実行して当該導入情報体を形成するに際し、当該世代ｉ（基準世代）を構成する情報体集団を構成する複数個の情報体の内で、世代ｉ＋１を構成する情報体集団に引き継がれる情報体の中から情報体を選択し、当該変形処理を施すものである事が望ましい。
【００５８】
また、上記した該変形処理は、当該世代ｉ（基準世代）を構成する情報体集団に於ける探索空間に於いて、選択された該情報体が、互いに異なる距離要素を有する様にするものであっても良い。
次に、本発明に係る最適解探索装置１により所定の環境条件下に於いて最適な解を求める為の具体例を図３及び図４を参照しながら説明する。
【００５９】
即ち、図３（Ａ）は、本発明に於ける最適解探索装置１を用いて最適な解を求める方法に於いて、予め定められた所定の環境内に導入され処理された後の世代ｉを形成する情報体集団Ｓ１が、Ｎ個の情報体Ｊ１〜Ｊｎから構成されている事を示している。
また、図３（Ｂ）は、図３（Ａ）に於ける情報体集団Ｓ１と、同一の数の情報体Ｊ’１〜Ｊ’ｎを持つ世代ｉ＋１を形成する情報体集団Ｓ２であって、当該環境内に現在導入されている情報体集団の構成を示すものである。
【００６０】
本具体例に於いては、図３（Ｂ）に示す様に、世代ｉ＋１を形成する為の探索処理を行う環境に現在導入されている情報体集団Ｓ２に於いては、当該情報体Ｊ’１〜Ｊ’１の１個の情報体は、図３（Ａ）に示す世代ｉを形成している、即ち、所定の探索処理を施された後の情報体集団Ｓ１に於ける対応する、１個の情報体Ｊ１〜Ｊ１をそのまま引き継ぐものであり、又図３（Ｂ）に示す様に、当該世代ｉ＋１を形成する為の探索処理を行う環境に現在導入されている情報体集団Ｓ２に於いて、当該情報体Ｊ’１＋１〜Ｊ’ｍの（ｍ−１）個の情報体は、図３（Ａ）に示す世代ｉを形成している情報体集団Ｓ１中の全ての情報体を基に遺伝的アルゴリズムの増殖処理、交叉処理、突然変異処理によって生成されるものであり、更に又図３（Ｂ）に示す様に、当該情報体集団Ｓ２に於いて、当該情報体Ｊ’ｍ＋１〜Ｊ’ｎの（ｎ−ｍ）個の情報体は、図３（Ａ）に示す当該情報体集団Ｓ１の全ての情報体から、上記した本発明に於ける選択基準に従って、適宜に選択された、情報体集団Ｓ１の情報体に、前記した所定の変形処理操作を行った後、該環境に導入されたものである。
【００６１】
そして、本具体例に於いては、当該導入情報体Ｊ’を選択する導入情報体選択基準として、該変形の度合いを複数段に変更し、且つ各変形の度合に於いて選択される情報体の数を所定の関数に従って変化させる様にした基準を採用している。
具体的には、当該選択される複数個の導入情報体Ｊ’ｍ＋ｌ〜Ｊ’ｎの、世代ｉを形成している探索空間に於ける距離を複数段階に変化させ、その距離毎に選択される当該導入情報体の数ｙは、所定の距離に応じた関数Ｆ（ｘ）とするものである。
【００６２】
即ち、ｙ＝Ｆ（ｘ）と表される。
此処で、ｘは、変形の度合い即ち、環境（探索空間）に於ける当該導入情報体の或る点からの個別の距離を示すものであって、図１３に示す様に、例えばｘ＝ｘｏ〜ｘmaxで与えられるものである。
また、本発明に於ける当該選択される当該導入情報体の数ｙを出力する関数としては、上記以外に、例えば、Ｆ（ｘ）＝ｅｘｐ（Ａｘ＋Ｂ）、Ｆ（ｘ）＝Ａｙ、或いはＦ（ｘ）＝ｌｏｇ（Ａｘ＋Ｂ）等の関数を使用する事も可能である。
【００６３】
つまり、本具体例に於いては、当該環境（探索空間）に於ける当該導入情報体の或る点からの個別の距離ｘの関数Ｆ（ｘ）で表される分布に従って、該導入情報体が選択される様に設定したものである。
図４のフローチャートに従って、本具体例に於ける導入情報体選択手順を説明すると、先ずスタート後、ステップ（１）に於いて、該環境（探索空間）に於ける当該導入情報体の個別の距離ｘの初期値が設定され、此処では、ｘ＝ｘｏが入力される。
【００６４】
次いで、ステップ（２）に進んで、当該環境（探索空間）に於ける当該導入情報体の個別の距離ｘが、上限値、即ちｘmaxに到達したか否かが判断され、ＹＥＳであれば、係る選択処理操作が終了しＥＮＤとなる。
一方、ステップ（２）においてＮＯである場合には、ステップ（３）に進んで、ｘ＝ｘｏに於ける当該導入情報体の選択個数ｙの初期値が設定される。
【００６５】
この場合、該初期値ｙの値は、正の整数（例えば１）である事が望ましい。
つまり、係るステップに於いては、先ず一個目の導入情報体が選択されたと仮定するものである。
次に、ステップ（４）に進み、当該選択された導入情報体の数ｙが、前記した環境（探索空間）に於ける当該導入情報体の個別の距離ｘ＝ｘｏに於ける当該導入情報体の選択個数ｙ＝Ｆ（ｘｏ）に到達したか否かが判断され、ＹＥＳであれば、ステップ（８）に進んで、当該導入情報体の個別の距離ｘ＝ｘｏ時点での選択処理を終了して、当該導入情報体の個別の距離ｘの値を更新してｘ＝ｘ＋１としてステップ（２）に戻る。
【００６６】
そして、ステップ（２）に於いて再度、当該環境（探索空間）に於ける当該導入情報体の個別の距離ｘ＋１が、上限値、即ちｘmaxに到達したか否かが判断され、ＹＥＳであれば、係る選択処理操作が終了しＥＮＤとなり、ＮＯである場合には、上記のステップ（３）及びステップ（４）の各工程が繰り返される。
次いで、該ステップ（４）に於いて、ＮＯである場合には、ステップ（５）に進んで、当該情報体集団Ｓ１に於ける（ｎ）個の情報体Ｊ１〜Ｊｎからランダムに一つの情報体、例えば、情報体Ｊｉを導入情報体Ｊ’ｉとして選択し、かかる選択された導入情報体Ｊ’ｉに対して、ステップ（６）に於いて、図２に示す様な変形処理操作を、例えば、ｒ回繰り返した後、当該情報体Ｊｉを環境（探索空間）内に導入して情報体Ｊ’ｉとする。
【００６７】
その後、ステップ（７）に進んで、選択される導入情報体の数ｙの値を更新してｙ＋δｉとなし、ステップ（４）に戻って上記した各工程が繰り返されることになる。
尚、上記フローチャートに於ける当該情報体集団Ｓ１から適宜の導入情報体を選択するに際しては、図３（Ａ）に示された（ｎ）個の情報体Ｊ１〜Ｊｎからランダムに一つの情報体を選択するのに特定されるものではなく、例えば、当該情報体集団Ｓ１を構成する（ｎ−１）個の情報体Ｊ１＋１〜Ｊｎの中から選択する様にしても良く、更には、ステップ（６）に於いて、選択された導入情報体Ｊ’ｉに図２に示す様な変形処理操作を、ｒ回繰り返したが、係る繰り返し操作を１回或いは１〜ｒの間の任意の回数だけ繰り返す様にしても良い。
【００６８】
尚、本発明に於いては、上記した基本的な技術構成を、一つの情報体集団内で、処理実行するのみではなく、複数種の情報体集団を同時平行的に処理実行する事も可能である。
係る同時平行処理する場合には、それぞれの情報体集団が、その情報体集団内で独自に上記した遺伝的アルゴリズム（ＧＡ）処理を行うもので有ってもよく、また、特に、一つの情報体集団が、上記した本発明に於ける第２の探索処理を行う場合に、他の異なる情報体集団に於ける適宜の世代から所定の情報体Ｊを導入情報体Ｊ’として採用する事も可能である。
【００６９】
係る場合には、各情報体集団間で、世代数、世代水準が、互いに異なっている場合があり得るので、選択される他の情報体集団に於ける世代水準に注意を払う事が必要となる。
【００７０】
以上のように、本発明は、一つの環境内に於いて、複数個の情報を組み合わせて最適な解を得るに際して、遺伝的アルゴリズムを適用して探索を行う最適解探索装置において、当該遺伝的アルゴリズム処理操作が進行して当該情報体集団のフィットネス値が大きくなると当該新たに発生した情報体（個体）のフィットネス値との差が大きくなり、当該新たに発生した情報体の当該情報体集団のフィットネス値改善への貢献度が低下するのを防止し、遺伝的アルゴリズム処理速度を向上させながら、最適な解を容易に且つ短時間に求める事が出来る最適解探索装置を提供する事が出来る。
【図面の簡単な説明】
【００７１】
【図１】本発明に係る最適解探索装置の一具体例の構成を示すブロックダイアグラムである。
【図２】本発明に於いて使用される、選択された導入情報体に施される変形処理操作の一例を示す図である。
【図３】本発明に於ける最適解探索装置に適用される世代ｉを形成する情報体集団Ｓ１の情報体の構成例と世代ｉ＋１を形成する情報体集団Ｓ２の情報体の構成例を説明する図である。
【図４】図３に示す情報体集団モデルを用いて、本発明に係る情報体集団を生成する操作の一例に於ける手順を説明するフローチャートである。
【図５】従来に於ける最適解探索方法に於いて使用されている巡回セールスパーソン問題を扱う場合の情報体の一例を示す図である。
【図６】従来に於ける最適解探索方法に於いて使用されている情報体集団を構成する情報体群の例を示す図である。
【図７】従来に於ける最適解探索方法に於いて、環境（探索空間）内に於ける情報体のパターンと適応度値（フィットネス値）ｆとの関係の一例を示す図である。
【図８】従来に於ける最適解探索方法に於いて、世代数（の増加）と情報体の適応度値（フィットネス値）ｆとの関係の一例を示す図である。
【図９】従来に於ける最適解探索方法に於いて、所定の情報体集団に導入情報体を導入した場合に、環境（探索空間）内に於ける情報体のパターンの適応度値（フィットネス値）ｆの分布の様子を示す図である。
【図１０】従来に於ける最適解探索方法に於いて、情報体の適応度値（フィットネス値）ｆの変動率が、世代数の変化に応じて変化する様子を示すグラフである。
【図１１】本発明に於ける最適解探索装置を使用するに際して、導入される導入情報体の変形の度合い或いは環境（探索空間）内での距離を説明する図である。
【図１２】本発明に於ける最適解探索装置を使用するに際して、導入される導入情報体の変形の度合いに特定の分布を付与した場合の例を説明する図である。
【図１３】本発明に於ける最適解探索装置を使用するに際して、導入される導入情報体の変形の度合いに特定の範囲を設け且つその範囲内で特定の分布を付与した場合の例を説明する図である。
【符号の説明】
【００７２】
１    最適解探索装置
２    入力手段
３    探索処理手段
４    適応度値（フィットネス値）演算手段
５    環境条件設定手段
６    最適適応度値設定手段
７    適応度値（フィットネス値）判定手段
８    出力手段
９    適応度値変化率演算手段
１０    適応度値変化率しきい値設定手段
１１    適応度値変化率比較手段
１２    探索処理操作制御手段
１３    導入情報体選択基準設定手段
１４    導入情報体選択手段
１５    変形処理操作手段
１６    前世代情報体集団記憶手段
【図１】
2005209222.tif 000003
【図２】
2005209222.tif 000004
【図３】
2005209222.tif 000005
【図４】
2005209222.tif 000006
【図５】
2005209222.tif 000007
【図６】
2005209222.tif 000008
【図７】
2005209222.tif 000009
【図８】
2005209222.tif 000010
【図９】
2005209222.tif 000011
【図１０】
2005209222.tif 000012
【図１１】
2005209222.tif 000013
【図１２】
2005209222.tif 000014
【図１３】
2005209222.tif 000015
【手続補正書】
【提出日】平成17年3月17日(2005.3.17)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の情報体が集合して形成された情報体集団を所定環境に配置させ、基準世代ｉを構成する情報体集団から世代ｉ＋１を構成する情報体集団を形成する探索操作を繰り返し行う遺伝的アルゴリズムを用い、該環境への適応度を示す適応度値に基づいて、該環境における最適解若しくはそれに近い解を有する情報体を求めることが可能な最適解探索装置において、
前記探索操作が繰り返される過程において、前記各情報体に係る前記適応度値の変化率と予め定められた変化率とを比較する適応度値変化率比較手段と、
前記適応度値変化率比較手段において、前記情報体集団の基準世代である世代ｉにおける前記各情報体に係る前記適応度値の変化率が、前記予め定められた変化率より小さいと判断した場合、前記世代ｉを構成する情報体集団から情報体を選択して変形処理し、前記所定環境の探索空間に導入情報体として世代ｉ＋１の情報対集団に導入する導入情報体選択手段と、
を含むことを特徴とする最適解探索装置。
【請求項２】
前記導入情報体選択手段は、前記世代ｉから複数の前記情報体を選択して変形処理するとき、複数の前記情報体の前記探索空間の所定の点からの距離が互いに異なるように、該情報体を変形処理することを特徴とする請求項１に記載の最適解探索装置。
【請求項３】
前記導入情報体選択手段は、前記世代ｉから複数の前記情報体を選択するとき、前記世代ｉの前記探索空間中において、複数の前記情報体の前記探索空間の所定の点からの距離が互いに異なるように、該情報体を選択する選択基準を設定する選択基準設定手段を含むことを特徴とする請求項１又は２に記載の最適解探索装置。
【請求項４】
前記導入情報体選択手段は、前記世代ｉから複数の前記情報体を選択して変形処理するとき、前記探索空間の所定の点からの距離が異なる情報体の数が異なるように、前記情報体を変形処理することを特徴とする請求項１に記載の最適解探索装置。
【請求項５】
前記導入情報体選択手段は、前記世代ｉから複数の前記情報体を選択するとき、前記探索空間の所定の点からの距離が異なる情報体の数が異なるように、前記情報体を選択することを特徴とする請求項１又は４に記載の最適解探索装置。
【請求項６】
前記距離は、変形処理における処理操作パラメータに依存することを特徴とする請求項１乃至５のいずれかに記載の最適解探索装置。
【請求項７】
前記導入情報体選択手段が選択した情報体は、前記距離が所定の範囲内となるように選択されることを特徴とする請求項１乃至６のいずれかに記載の最適解探索装置。
【請求項８】
前記導入情報体選択手段が選択する複数の情報体のうち少なくとも一つの情報体は、該世代ｉ以前に行われた前記探索操作による世代である世代ｉ−１、世代ｉ−２・・・等から選択されることを特徴とする請求項１乃至７のいずれかに記載の最適解探索装置。
【請求項９】
導入情報体変形処理手段が、前記導入情報体選択手段に接続され、該導入情報体変形処理手段は、該導入情報体選択手段により選択された少なくとも一つの前記情報体に変形処理することを特徴とする請求項１乃至８のいずれかに記載の最適解探索装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
本発明は、上記した目的を達成するため、基本的には、以下に記載されたような技術構成を採用するものである。即ち、複数の情報体が集合して形成された情報体集団を所定環境に配置させ、基準世代ｉを構成する情報体集団から世代ｉ＋１を構成する情報体集団を形成する探索操作を繰り返し行う遺伝的アルゴリズムを用い、該環境への適応度を示す適応度値に基づいて、該環境における最適解若しくはそれに近い解を有する情報体を求めることが可能な最適解探索装置において、前記探索操作が繰り返される過程において、前記各情報体に係る前記適応度値の変化率と予め定められた変化率とを比較する適応度値変化率比較手段と、該適応度値変化率比較手段において、前記情報体集団の基準世代である世代ｉにおける前記各情報体に係る前記適応度値の変化率が、前記予め定められた変化率より小さいと判断した場合、前記世代ｉを構成する情報体集団から情報体を選択して変形処理し、前記所定環境の探索空間に導入情報体として世代ｉ＋１の情報対集団に導入する導入情報体選択手段と、を含めた。