トップ :: G 物理学 :: G06 計算;計数




【発明の名称】 最適解探索方法及び最適解探索装置
【発明者】 【氏名】櫻井 茂明
【要約】 【課題】最適解をより少ない探索数で効率良く探索することで、最適解探索を高速に行うことである。

【解決手段】最適解探索問題において、探索後の解およびその評価結果を、評価結果に基づき事例として選択し（Ｓ００５〜Ｓ０１１）、この選択された事例の集合を用いて、最適解探索のための判断規則を帰納的に生成し（Ｓ０１３）、この判断規則を用いて探索を行う（Ｓ０１５，Ｓ０１６）ことにより、最適解探索の方向を制限する。
【特許請求の範囲】
【請求項１】 与えられた解集団に対して各々の解の良さを評価し、該評価の結果が得られた解集団に対して新たな解集団を生成するための最適解の探索を行い、必要とされる最適解が求められたと判断されるまで前記評価および前記探索を繰り返し行うことにより最適解を出力する最適解探索方法であって、少なくとも前記評価のなされた解および前記評価結果に基づく値を、該評価結果に従って、事例として選択し、該選択された事例の集合を用いて、前記最適解の探索の方向を制限するための判断規則を帰納的に生成することを特徴とする最適解探索方法。
【請求項２】 前記最適解探索方法は、さらに、前記選択された事例を事例保持手段に格納し、前記格納された事例の集合の中から、前記評価結果の値に基づいて、最も格納に適さない１または複数の事例を判定し、前記判定のなされた事例を前記事例集合から削除することによって前記事例集合の洗練化を行うことを特徴とする請求項１記載の最適解探索方法。
【請求項３】 遺伝的アルゴリズムを用いて最適解の探索を行う方法において、初期解を探索するステップと、探索された解について解の良さを示す適合度の算出を行うステップと、前記適合度の得られた解について、帰納学習を行うための事例として格納するか否かを該適合度に基づいて判定するステップと、少なくとも、格納すると判定された解について、事例として事例保持手段に選択的に格納するステップと、前記格納された事例の集合から帰納的に最適解探索に用いられる判断規則を生成するステップと、該判断規則を用いることにより最適解探索の方向を制限して新たな解を探索するステップと、を少なくとも含み、前記事例は、それぞれ解の属性値および該解の適合度に基づいて決定された分類クラスとを少なくとも有し、前記適合度が当該世代の解集団の全ての解について得られた場合に、前記分類クラスに示された値に基づいて判断規則を生成し、最適解探索を行う際に、該判断規則の示すパターンに基づいて、解の一部を探索から除くことにより解の探索の方向を制限することを特徴とする最適解探索方法。
【請求項４】 前記分類クラスは所定値以上の適合度を持つことを示す値である正または所定値以下の適合度を示す値である負のいずれかであり、前記正および／または負の値に基づいて、前記事例集合の洗練化および前記判断規則の生成を行うことを特徴とする請求項３記載の最適解探索方法。
【請求項５】 前記事例の格納の判定に用いられる上限のしきい値は、初期解集団のうち前記適合度の上位集団中から求められた所定値であり、下限のしきい値は、前記初期解集団のうち前記適合度の下位集団中から求められた所定値であることを特徴とする請求項２乃至４のいずれか記載の最適解探索方法。
【請求項６】 初期解を探索する初期解生成部、探索された解について解の良さの評価を行う探索結果評価部、および探索済みの解集団から新たな解を探索する解生成部とを有する探索部と、前記評価のなされた解について、帰納学習を行うための事例として格納するか否かを判定する事例抽出部、少なくとも格納すると判定された事例を選択的に格納する事例格納部、および前記格納された事例の集合から最適解探索に用いる判断規則を生成する探索知識生成部とを有する帰納学習部と、を少なくとも有し、前記帰納学習部は、少なくとも前記評価のなされた解および前記評価結果に基づく値を、該評価結果に従って、事例として選択し、該選択された事例の集合を用いて、最適解探索の方向を制限するための判断規則を帰納的に生成し、前記解生成部は、該判断規則を用いて探索を行うことにより最適解探索の方向を制限することを特徴とする最適解探索装置。
【請求項７】 前記事例格納部は、さらに、前記事例集合の中から、前記評価結果の値に基づいて、最も格納に適さない１または複数の事例を判定し、前記判定のなされた事例を前記事例集合から削除することによって前記事例集合の洗練化を行うことを特徴とする請求項６記載の最適解探索装置。
【請求項８】 遺伝的アルゴリズムを用いて最適解の探索を行う装置において、初期解を探索する初期解生成部、探索された解について解の良さを示す適合度の算出を行う探索結果評価部、および探索済みの解集団から新たな解を探索する解生成部とを有する探索部と、 前記適合度の得られた解について、帰納学習を行うための事例として格納するか否かを該適合度に基づいて判定する事例抽出部、少なくとも格納すると判定された解について事例として事例保持手段に選択的に格納する事例格納部、および前記格納された事例の集合から帰納的に判断規則を生成する探索知識生成部とを有する帰納学習部と、を少なくとも具備し、前記事例は、それぞれ解の属性値および該解の適合度に基づいて決定された分類クラスとを少なくとも有し、前記探索知識生成部は、前記適合度が当該世代の解集団の全ての解について得られた場合に、前記分類クラスに示された値に基づいて判断規則を生成し、前記解生成部は、該判断規則の示すパターンに基づいて、解の一部を探索から除くことにより解の探索の方向を制限することを特徴とする最適解探索装置。
【請求項９】 前記分類クラスは所定値以上の適合度を持つことを示す値である正または所定値以下の適合度を示す値である負のいずれかであり、前記正および／または負の値に基づいて、前記事例集合の洗練化および前記判断規則の生成を行うことを特徴とする請求項８記載の最適解探索装置。
【請求項１０】 前記事例の格納の判定に用いられる上限のしきい値は、初期解集団のうち前記適合度の上位集団中から求められた所定値であり、下限のしきい値は、前記初期解集団のうち前記適合度の下位集団中から求められた所定値であることを特徴とする請求項６乃至９のいずれか記載の最適解探索装置。
【発明の詳細な説明】【０００１】
【発明の属する技術分野】本発明は、最適解探索方法及び最適解探索装置に関し、特に、事例を用いた帰納学習により、最適解探索の方向を制限して、最適解をより少ない探索数で効率良く高速に探索するための技術に関する。
【０００２】
【従来の技術】一般に、製品の生産順序を決定するスケジューリング、制御モデルに内在する制御パラメータの調整、種々の形状を持った部品を２次元上の領域に配置する設計等、産業上の様々な分野において、最適化問題の技法が必要とされ、また事実、応用に供されている。
【０００３】ここで、最適化問題とは、所定の制約条件の下で、与えられた評価関数の値を可能な限り最大または最小にするような解を解集合の中から決定する問題と定義される。
【０００４】こうした最適化問題では一般に、解空間が大きくなると、探索に非常な長時間を要してしまうため、解探索を効率化すべく、種々の接近手法が試みられている。こうした中でも、最適解を効率よく探索するための一技法として、近年注目されているものに、遺伝的アルゴリズム（Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ、以下、「ＧＡ」という。）がある。ＧＡとは、自然界における生物進化（選択淘汰、交差、突然変異）の原理から着想を得て、染色体の進化の様子をモデル化したアルゴリズムである。ＧＡは、この染色体を、各問題に応じた解としてとらえて、染色体中の各遺伝子座に解の一部分を表現した値を割り振り、また各問題ごとの評価関数に基づく評価を経て遺伝子操作を加えていくことにより、様々な最適化問題に適用されるものである（「ジェネティックアルゴリズム」、安居院猛、長尾智晴、昭晃堂、１９９３年）。
【０００５】ＧＡによる一般的な処理手順を、図２４に示すフローチャートに基づき説明する。
【０００６】ある最適化問題を解く場合、まず、集団の大きさ、解の良さを判定するための評価関数、遺伝子操作を行う確率、探索数、各種しきい値等のＧＡの稼働に必要なパラメータを設定し、その問題に対する解の一般的な表現方法を、染色体における遺伝子表現として、その長さやコーディング方法などを決定する（Ｓ１００）。そして、まず、問題の解である染色体のパターンをランダムに複数生成し、初期染色体集団を作成する（Ｓ１０１）。
【０００７】以降は、染色体集団の収束条件が満たされるまで、以下の処理のル−プを行う（Ｓ１１２）。すなわち、染色体集団の各々の個体（染色体）に対して、染色体の善し悪しの基準である適合度の評価を評価関数を用いて行い（Ｓ１０４）、当該世代の全ての染色体の評価がなされたと判断された場合には（Ｓ１０２、Ｓ１０３）、最適解探索の終了条件に達しない限り、選択（Ｓ１１４）、交差（Ｓ１１５）、突然変異（Ｓ１１６）による遺伝子操作を行い、次世代の染色体集団を生成していくのである。
【０００８】ここで、選択とは、適合度の高さに応じて、次世代に残す染色体を確率的に選択し、残りの染色体を淘汰するプロセスである。また、交差とは、二つの個体間で染色体を組み替えることにより新しい個体を生成するプロセスであり、突然変異とは、染色体上のある遺伝子座の値を他の対立遺伝子に置き換えることにより、個体の近傍に新しい個体を生成するプロセスである。
【０００９】かかるＧＡは、前述の交差、突然変異といった遺伝子操作の概念を用いることによって、組み合わせによる冗長性を排除できるため、解空間の中から効率よく最適解を探索できる手法であり、すでに実績を有している。しかしながら、他方では、遺伝子操作中での突然変異の対象となる遺伝子座の決定や交差における遺伝子切断箇所の決定等においてランダム探索的な要素が残っているため、最適解の周辺には早く近づくことができるが、その近傍に一旦は近づいてから逆に遠のいてしまう場合がままある。すなわち、最適解の近傍における収束がよくないという欠点を有している。このため、最適解発見までに多くの探索数を要しており、特に探索する解空間が大きい場合には、多数の染色体の適合度を調べる必要があり、ＧＡのみによって現実的な時間内で最適解を発見することが困難となっていた。
【００１０】かかるＧＡの欠点を解消すべく、いわゆるハイブリッドＧＡと呼ばれる、ＧＡによる探索と局所探索等の他の手法とを組み合わせた手法が開発された。従来より知られる「最適化問題解決処理方法および装置」（特開平７−２１９９２０）も、かかる手法の流れを汲むものの一つであり、人工知能による方法などの決定論的な手法を用いるＡＩ処理部、ＧＡ処理部、及び、これら処理部の各々に対応する修正部とを有する計画エンジン部により構成されるものである。
【００１１】その処理内容を以下に説明する。まず、第一の過程として、ＡＩ処理部によって、探索のための基本ルールを用いて解空間中の最適解の探索を行い、解を構成する変数の集合のうちで、最適解である値が判明したものについて、その判明した値を解の一部として固定することによって解空間を限定する。その後、第二の過程として、第一の過程によって限定された解空間の範囲のみを対象として、ＧＡ処理部が、ＧＡを用いた探索を行うことにより、最適解探索の高速化を図っている。
【００１２】
【発明が解決しようとする課題】しかしながら、前述した探索方法および装置には、以下の問題点があった。すなわち、第一に、ＡＩ処理部における解空間の限定が適切かつ実効性を有するものとなるか否かは、ＡＩ探索に用いられる基本ルールを、いかに適切に準備できるかに依存する。ところが、肝要であるところの基本ルールの決定および蓄積は、あらかじめ人間系などの別の手段によってなされている必要を要していた。このため、この基本ルールの蓄積に要する時間およびその妥当性は大きく経験に依存することとなってしまっていた。また、第二に、計画エンジン部においては、解の修正を人間系で行う構成となっているため、探索数が多ければそれだけ長時間を要してしまっていた。
【００１３】このため、特に解空間が大きい場合においては、前述の基本ルールの準備や解の修正の部分がボトルネックとなって、トータルでの最適解探索の高速化という課題の解決を十分に図るものとはいい難く、さらに、ＡＩ処理部の用いる基本ルールや評価手法の内容いかんによっては、求められた解の精度を損なう場合も生じるという限界を有していた。
【００１４】以上のように、本発明は、従来技術における、最適解の近傍における収束が悪かったために、最適解発見までに多くの探索数を要し、特に探索空間が大きい場合には、実用的な時間内で最適解を発見できなかったという問題点を解決するためになされたものである。そして、その目的とするところは、事例を用いた帰納学習により、最適解探索の方向を制限して、最適解をより少ない探索数で効率良く探索することを可能とする最適解探索方法および装置を提供することにある。
【００１５】また、他の目的は、帰納学習に用いる事例集合を適宜洗練化することにより、さらに最適解探索の方向の制限についての精度の向上を図ることにある。
【００１６】加えて、他の目的は、解の評価結果を事例中に正または負として保持し、この値に基づいた探索を行うことにより、さらに簡易に最適解探索の実現を図ることにある。
【００１７】加えて、他の目的は、事例抽出の判断に用いるしきい値を内部的に生成することにより、さらに簡易に最適解探索の実現を図ることにある。
【００１８】
【課題を解決するための手段】要するに、本発明方法（請求項１）は、与えられた解集団に対して各々の解の良さを評価し、該評価の結果が得られた解集団に対して新たな解集団を生成するための最適解の探索を行い、必要とされる最適解が求められたと判断されるまで前記評価および前記探索を繰り返し行うことにより最適解を出力する最適解探索方法であって、少なくとも前記評価のなされた解および前記評価結果に基づく値を、該評価結果に従って、事例として選択し、該選択された事例の集合を用いて、前記最適解の探索の方向を制限するための判断規則を帰納的に生成することを特徴とするものである。かかる方法によれば、解の評価の結果に基づいて蓄積された事例集合から、最適解探索の方向を制限するための判断規則を、帰納学習によって自動生成することにより、この判断規則を用いて、評価値の高い解が存在すると期待される方向に対して解を探索することができる。つまり、より少ない探索数で、最適解を効率良く探索することが可能となる。
【００１９】また、請求項２の発明においては、前記最適解探索方法は、さらに、前記選択された事例を事例保持手段に格納し、前記格納された事例の集合の中から、前記評価結果の値に基づいて、最も格納に適さない１または複数の事例を判定し、前記判定のなされた事例を前記事例集合から削除することによって前記事例集合の洗練化を行うことにより、評価の結果である適合度の値を用いて事例集合を洗練化することができる。つまり、事例が数多く蓄積されるにつれて、より最適解探索の方向の制限についての精度の向上を図ることが可能となる。
【００２０】また、請求項３の発明は、遺伝的アルゴリズムを用いて最適解の探索を行う方法において、初期解を探索するステップと、探索された解について解の良さを示す適合度の算出を行うステップと、前記適合度の得られた解について、帰納学習を行うための事例として格納するか否かを該適合度に基づいて判定するステップと、少なくとも、格納すると判定された解について、事例として事例保持手段に選択的に格納するステップと、前記格納された事例の集合から帰納的に最適解探索に用いられる判断規則を生成するステップと、該判断規則を用いることにより最適解探索の方向を制限して新たな解を探索するステップと、を少なくとも含み、前記事例は、それぞれ解の属性値および該解の適合度に基づいて決定された分類クラスとを少なくとも有し、前記適合度が当該世代の解集団の全ての解について得られた場合に、前記分類クラスに示された値に基づいて判断規則を生成し、最適解探索を行う際に、該判断規則の示すパターンに基づいて、解の一部を探索から除くことにより解の探索の方向を制限することを特徴とするものである。かかる方法によれば、解の適合度から導かれる分類クラスに基づいて蓄積された事例集合から、ＧＡによる最適解探索の方向を制限するための判断規則を、帰納学習によって自動生成することにより、この判断規則を用いて適合度の高い解が存在すると期待される方向に対して解を探索することができる。つまり、より少ない探索数で、最適解を効率良く探索することが可能となる。
【００２１】また、請求項４の発明においては、前記分類クラスは所定値以上の適合度を持つことを示す値である正または所定値以下の適合度を示す値である負のいずれかであり、前記正および／または負の値に基づいて、前記事例集合の洗練化および前記判断規則の生成を行うことにより、解の評価結果を事例中に正または負として保持し、この二値に基づいた探索を行うことができる。つまり、さらに簡易に最適解探索を行うことが可能となる。
【００２２】また、請求項５の発明においては、前記事例の格納の判定に用いられる上限のしきい値は、初期解集団のうち前記適合度の上位集団中から求められた所定値であり、下限のしきい値は、前記初期解集団のうち前記適合度の下位集団中から求められた所定値とすることにより、事例抽出の判断に用いるしきい値を内部的に生成することが可能となる。つまり、さらに簡易に最適解探索を行うことが可能となる。尚、ここにいう所定値とは、処理速度やコンピュータ資源状況等により定まる、蓄積される事例数の適正値等に応じて求められる値である。
【００２３】更に、本発明装置（請求項６）は、初期解を探索する初期解生成部、探索された解について解の良さの評価を行う探索結果評価部、および探索済みの解集団から新たな解を探索する解生成部とを有する探索部と、前記評価のなされた解について、帰納学習を行うための事例として格納するか否かを判定する事例抽出部、少なくとも格納すると判定された事例を選択的に格納する事例格納部、および前記格納された事例の集合から最適解探索に用いる判断規則を生成する探索知識生成部とを有する帰納学習部と、を少なくとも有し、前記帰納学習部は、少なくとも前記評価のなされた解および前記評価結果に基づく値を、該評価結果に従って、事例として選択し、該選択された事例の集合を用いて、最適解探索の方向を制限するための判断規則を帰納的に生成し、前記解生成部は、該判断規則を用いて探索を行うことにより最適解探索の方向を制限することを特徴するものである。かかる装置によれば、解の評価の結果に基づいて蓄積された事例集合から、最適解探索の方向を制限するための判断規則を、帰納学習によって自動生成することにより、この判断規則を用いて、評価値の高い解が存在すると期待される方向に対して解を探索することができる。つまり、より少ない探索数で、最適解を効率良く探索することが可能となる。
【００２４】また、請求項７の発明においては、前記事例格納部は、さらに、前記事例集合の中から、前記評価結果の値に基づいて、最も格納に適さない１または複数の事例を判定し、前記判定のなされた事例を前記事例集合から削除することによって前記事例集合の洗練化を行うことにより、評価の結果である適合度の値を用いて事例集合を洗練化することができる。つまり、事例が数多く蓄積されるにつれて、より最適解探索の方向の制限についての精度の向上を図ることが可能となる。
【００２５】また、請求項８の発明は、遺伝的アルゴリズムを用いて最適解の探索を行う装置において、初期解を探索する初期解生成部、探索された解について解の良さを示す適合度の算出を行う探索結果評価部、および探索済みの解集団から新たな解を探索する解生成部とを有する探索部と、前記適合度の得られた解について、帰納学習を行うための事例として格納するか否かを該適合度に基づいて判定する事例抽出部、少なくとも格納すると判定された解について事例として事例保持手段に選択的に格納する事例格納部、および前記格納された事例の集合から帰納的に判断規則を生成する探索知識生成部とを有する帰納学習部と、を少なくとも具備し、前記事例は、それぞれ解の属性値および該解の適合度に基づいて決定された分類クラスとを少なくとも有し、前記探索知識生成部は、前記適合度が当該世代の解集団の全ての解について得られた場合に、前記分類クラスに示された値に基づいて判断規則を生成し、前記解生成部は、該判断規則の示すパターンに基づいて、解の一部を探索から除くことにより解の探索の方向を制限することを特徴とするものである。かかる方法によれば、解の適合度から導かれる分類クラスに基づいて蓄積された事例集合から、ＧＡによる最適解探索の方向を制限するための判断規則を、帰納学習によって自動生成することにより、この判断規則を用いて適合度の高い解が存在すると期待される方向に対して解を探索することができる。つまり、より少ない探索数で、最適解を効率良く探索することが可能となる。
【００２６】また、請求項９の発明においては、前記分類クラスは所定値以上の適合度を持つことを示す値である正または所定値以下の適合度を示す値である負のいずれかであり、前記正および／または負の値に基づいて、前記事例集合の洗練化および前記判断規則の生成を行うことにより、解の評価結果を事例中に正または負として保持し、この二値に基づいた探索を行うことができる。つまり、さらに簡易に最適解探索を行うことが可能となる。
【００２７】また、請求項１０の発明においては、前記事例の格納の判定に用いられる上限のしきい値は、初期解集団のうち前記適合度の上位集団中から求められた所定値であり、下限のしきい値は、前記初期解集団のうち前記適合度の下位集団中から求められた所定値とすることにより、事例抽出の判断に用いるしきい値を内部的に生成することが可能となる。つまり、さらに簡易に最適解探索を行うことが可能となる。
【００２８】尚、上述した最適解探索機能を実現するためのプログラムは、記録媒体に保存することが可能であり、かかる記録媒体をコンピュータシステムに読み込ませ、コンピュータを制御しながら前記プログラムを実行することにより、上述した最適解探索を実現することができる。ここで、記録媒体とは、メモリ装置、磁気ディスク装置、光ディスク装置等、プログラムを機械読取り可能な状態で記録することができる装置一般を含むものである。
【００２９】
【発明の実施の形態】以下、本発明の実施形態について、図面を参照しながら詳細に説明する。本実施形態は、ＧＡを用いて、制御システム内に存在する制御パラメータの調整問題についての最適解を得る目的のものである。
【００３０】図２に示すように、本実施形態に係る最適解探索装置は、探索部１００と、帰納学習部２００とを備えている。尚、図２において、実線は制御の遷移を、破線はデータの入出力（ＩＯ）を示すものである。
【００３１】探索部１００はさらに、探索を行うための初期染色体集団を形成する初期解生成部１１０と、生成された各染色体に対する評価を、評価関数を用いた適合度計算により行う探索結果評価部１３０と、各世代における探索を選択、交差、突然変異といった遺伝子操作を用いて行う解生成部１２０とを備えている。また、さらに探索結果の解を探索結果ファイル１１を用いて保持する構成としてもよい。尚、かかる探索結果は、必ずしもファイルの形式で保持する必要はなく、コンピュータ資源状況等に応じて、メモリ内に持つことも可能である。
【００３２】帰納学習部２００とは、本実施形態の新規機能を実現する構成部分であり、さらに、評価を行った染色体の中から判断規則を生成するための事例として格納するか否かを判断する事例抽出部２１０と、格納すると判断された事例を事例集合として保持、蓄積する事例格納部２２０と、蓄積された事例集合から最適解探索の方向を制限するための判断規則を生成する探索知識生成部２３０とを備えている。尚、事例集合を保持する手段としては、事例ベース１２を用いる構成としても、また、特に高速処理の要請の高い問題の場合にはメモリ内に保持する構成としてもよい。さらに、事例集合から生成した判断規則も、知識ベース１３に保持する構成とすれば、全事例を用いて判断規制を生成するかわりに、新たに追加、及び削除された事例だけを利用して、バッチ的に判断規制を部分修正することにより、探索の高速化を促進することや、判断規則の他の問題への適用が可能となる。また、制御データベース１０は、ＧＡ探索のための初期パラメータ等の各種制御用パラメータを格納しており、適宜各構成部分から参照されるが、これも高速処理の要請や汎用性などを勘案して適宜メモリ上に保持する構成とすることができる。
【００３３】本実施形態は、上記のように構成されており、以下、その処理の流れを図１に示すフローチャートに基づき説明する。
【００３４】ここでは、４つのパラメータ（ｐ１〜ｐ４）を最適化の対象とし、各パラメータは、各々３ビットを用いて表現されているものとする。すなわち、本問における一つの解を染色体として表現すると、１２ビットからなる遺伝子の並びとなる。ここで例えば、ｐ１＝０．０，ｐ２＝１．４，ｐ３＝１．２，ｐ４＝１．２という解は、図３に示すビット表現から、図４に示す染色体として表現されることとなる。
【００３５】最適解を探索するにあたっては、まず、初期処理として、最適解探索方法の本実施例の稼働に必要となる各種パラメータの設定を行う。具体的には、探索部によってＧＡ探索に用いられるｇ１〜ｇ４、および帰納学習部によって事例格納等に用いられるＴ１〜Ｔ４の値を設定する（Ｓ０００）。
【００３６】続いて、まず、遺伝子操作の対象とする染色体における各遺伝子座の値、ここでは０あるいは１の値を、乱数を用いて決定する。こうして作成した染色体をｇ１個生成することにより、初期染色体集団（第０世代の染色体集団）を作成する（Ｓ００１）。さらに、このステップにおいては、生成した染色体の数ｇ１を、第０世代の探索数として設定する。例えば、ｇ１の値が１０と設定された場合は、図６に示すようにｃ１〜ｃ１０までの１０個の染色体が生成され、探索数も１０と設定されることとなる。尚、ここでの各遺伝子座における初期値の設定は、必ずしも乱数を用いる必要はなく、問題のパターンや経験の程度に応じてＳ０００において初期値として与えてもよい。
【００３７】次に、染色体集団の中から、まだ評価を行っていない、すなわち評価関数によって適合度を計算していない染色体を一つづつ取り出す（Ｓ００２）。
【００３８】この場合、取り出す対象となる染色体が、染色体集団中に存在するか否かが判断され（Ｓ００３）、取り出した染色体が存在した場合、すなわち、まだ当該世代における評価（適合度の計算）を行っていない場合には、Ｓ００４の評価のステップに進む。一方、取り出した染色体が存在しなかった場合、すなわち、全染色体について評価済みである場合には、Ｓ０１２の収束判定のステップへ進む。例えば、図５の１０個の染色体のうち、ｃ１〜ｃ４までの染色体の適合度が計算されているとすると、染色体ｃ５が取り出され、Ｓ００４へと進む。一方、図５の全ての染色体の適合度の計算が行われているとすれば、Ｓ００２で取り出される染色体は存在せず、Ｓ０１２へと進むのである。
【００３９】ここで、前述のように、染色体ｃ５が取り出されたとすると、次に、ｃ５の染色体の評価、すなわち適合度の計算を、各問題に応じた評価関数を用いて行う（Ｓ００４）。いま、各染色体の適合度が所定の評価関数によって図６に示すように計算されたとすると、染色体ｃ５の適合度は１６と与えられることとなる。
【００４０】次に、Ｓ００４で計算された適合度の値に基づいて、評価のなされた染色体を、判断規則を生成するために用いる事例として格納するか否かが判断される（Ｓ００５）。すなわち、取り出されている染色体の適合度の値が上限のしきい値Ｔ１よりも大きい場合に、正事例として格納すると判定し、下限のしきい値Ｔ２よりも小さい場合に、負事例として格納すると判定する。また、どちらにも該当しない場合、すなわち、Ｔ２以上Ｔ１以下の染色体は、事例として格納しないと判定する。すなわち、格納される染色体（事例）と格納されない染色体（事例）には、図７に示す関係が存在する。例えば、Ｔ１，Ｔ２が、それぞれ１１，９と与えられているとすれば、染色体ｃ１，ｃ５，ｃ７，ｃ８，ｃ１０に対しては、正事例として格納すると判定する。また、染色体ｃ２，ｃ４，ｃ６，ｃ９に対しては、負事例として格納すると判定する。さらに、染色体ｃ３に対しては、格納を実施しないと判定する。尚、Ｓ０５０における事例の格納判定処理においては、外部から与えられるしきい値Ｔ１，Ｔ２を使った判定を行なっている。しかしながら、しきい値Ｔ１，Ｔ２を、例えば初期染色体集団の上位半分の適合度、初期染色体集団の下位半分の適合度とすることにより、外部から与えないようにすることもできる。
【００４１】このように、Ｓ００５において正事例と判断された染色体を、正事例として事例ベース１２に格納する（Ｓ００６）。
【００４２】正事例を格納した場合には、さらに、事例ベースに格納されている正事例の数が、正事例格納上限値Ｔ３よりも大きいかどうかの判定を行う（Ｓ００７）。このとき、Ｔ３以下であれば、正事例格納数の上限に達していないと判定し、Ｓ００２へ進む。一方、Ｔ３よりも大きければ、正事例格納数の上限に達したと判定して、Ｓ００８へ進む。例えばＴ３の値が２であるとする。このとき、事例格納部に格納されている事例が図８のように与えられているならば、正事例の数は１個しかないので、正事例格納の上限に達していないと判定し、Ｓ００２へ進む。一方、事例格納部に格納されている事例が図１２のように与えられているならば、正事例の数は３個となるので、正事例格納の上限に達していると判定し、Ｓ００８へ進む。
【００４３】Ｓ００７によって正事例の上限値を超えたと判断された場合には、事例格納部に格納されている正事例の中から最も適合度の低い染色体を探索し、当該染色体を事例格納部から削除する（Ｓ００８）。例えば、図１２のように事例が与えられていれば、図６により、３個の正事例の中で最も適合度の小さいものとして、（ｃ５，正）が選択されるので、ｃ５の事例が事例格納部から削除される。従って、Ｓ００８の処理の後に事例格納部に格納されている事例集合は図１３に示す内容となる。
【００４４】一方、Ｓ００５において負事例と判断された染色体は、負事例として事例ベース１２に格納される（Ｓ００９）。
【００４５】負事例を格納した場合には、さらに、事例ベース１２に格納されている負事例の数が、負事例格納上限値Ｔ４よりも大きいかどうかの判定を行う（Ｓ０１０）。このとき、Ｔ４以下であれば、負事例格納数の上限に達していないと判定し、Ｓ００２へ進む。一方、Ｔ４よりも大きければ、負事例格納数の上限に達したと判定して、Ｓ０１１へ進む。例えばＴ４の値が２であるとする。このとき、事例格納部に格納されている事例が図９のように与えられているならば、負事例の数は１個しかないので、負事例格納の上限に達していないと判定し、Ｓ００２へ進む。一方、事例格納部に格納されている事例が図１０のように与えられているならば、負事例の数は３個となるので、負事例格納の上限に達していると判定し、Ｓ０１１へ進む。
【００４６】Ｓ０１０によって負事例の上限値を超えたと判断された場合には、事例格納部に格納されている負事例の中から最も適合度の高い染色体を探索し、当該染色体を事例格納部から削除する（Ｓ０１１）。例えば、図１０のように事例が与えられていれば、図６により、３個の負事例の中で最も適合度の高いものとして、（ｃ２，負）が選択されるので、ｃ２の事例が事例格納部から削除される。従って、Ｓ０１１の処理の後に事例格納部に格納されている事例集合は図１１に示す内容となる。
【００４７】以上のＳ００５からＳ０１１の事例格納処理を、図５の初期世代（第０世代）に対して実施することにより、図１４に示す内容の事例が事例ベース１２に格納されることとなる。
【００４８】一方、先のＳ００３において、染色体集団中の全ての染色体についての適合度の計算がすでになされたと判断された場合には、まず、当該世代の染色体集団が十分収束しているか否か、すなわち、終了条件の判定を行う（Ｓ０１２）。具体的には、これまでの探索数がｇ２よりも大きいかどうかによって、探索数がｇ２以下の場合は、染色体集団が収束していないと判定して、Ｓ０１３へと進み、一方、この探索数がｇ２より大きい場合には、染色体集団が収束した、すなわち、与えられた問題に対する最適解を発見したとして、最適解探索処理を終了する。
【００４９】例えば、ｇ２の値が１００と設定されているとする。このとき、初期世代（第０世代）の適合度を計算した段階では、探索数は１０と与えられるので、染色体集団は収束していないと判定して、Ｓ０１３へと進む。一方、第１０世代目の適合度を計算した段階では、探索数は１１０と与えられるので、染色体集団は収束したと判定して、本最適解探索装置の処理を終了する。尚、ここにおける収束判定（解探索の終了判定）は、必ずしも探索数の上限を用いる方式である必要はなく、例えば、処理時間はある程度要しても解の精度を追及したいタイプの問題については、最良の解に対する適合度の値や、あるいは最良の解についての収束度によって判定を行うことも可能である。しかし、探索数を用いて、これを所定の時間内に探索が終了するように適宜設定することによって、例えば実用的時間内における最適解を得たい問題に対応することが容易となる。即ち、収束判定のための条件を問題に応じて適宜変更することによって、異なる要請の種々の最適化問題に対応することが可能となる。
【００５０】Ｓ０１２において、未だ染色体集団が収束していないと判断された場合には、まず、最適解探索の方向を制限するための判断規則を生成し、これを用いて以下の遺伝子操作を行って当該世代における最適解探索を実行する（Ｓ０１４〜Ｓ０１６）。
【００５１】すなわち、まず行われる判断規則生成の処理では、事例ベース１２に格納されている各事例に対して、染色体の各ビットを属性、正事例を分類クラス「正」、負事例を分類クラス「負」と解釈する。また、この解釈に従って、ＩＤＦアルゴリズム（参考文献「櫻井茂明，荒木大，帰納学習によるファジィ決定木の生成，電気学会論文誌，ｖｏｌ．１１３−Ｃ，ｎｏ．７，４８８頁−４９４頁（１９９３年）」）を事例集合に適用することにより、決定木形式の判断規則を生成する（Ｓ０１３）。この判断規則はすなわち探索方向を制御するための知識である。例えば、事例ベース中の図１４の各事例は、各々、図１５に示す属性値および分類クラスを持つ事例と解釈される。この事例集合に対して、ＩＤＦを適用することにより、図１６に示す木構造の知識が生成される。ここで、図１６の木構造（探索方向制御知識）は、この場合さらに、「Ａ２＝０かつＡ３＝０かつＡ５＝０ならば、負」、「Ａ２＝０かつＡ３＝０かつＡ５＝１ならば、正」、「Ａ２＝０かつＡ３＝１ならば、正」、「Ａ２＝１ならば、負」という４つの判断規則に対応しているものである。尚、各事例の有する分類クラスのとりうる値は、必ずしも正負に限定されるものではなく、例えば適合度のとりうる値の幅をより細分化した値を設定し、この重みづけ等を用いて判断規則に反映させることが可能である。また、この細分化された値は分類クラスとは別の情報として保有することも可能である。さらに、判断規則生成に用いる手法はＩＤＦに限定されるものではない。こうした探索方向制御知識の学習にＩＤＦを利用する代わりに、例えば、参考文献「大須賀節雄 監訳，人工知能大辞典，丸善，１７７頁−１７８頁（１９９１年）」に記載のＡＱ１１を利用することも考えられる。
【００５２】次に、まず遺伝子操作対象となる染色体の選択を行う。即ち、式（１）により計算される各染色体についての選択の確率に従って、染色体集団の中からｇ１個の染色体を取り出し、次世代（第１世代）の染色体集団の基になる染色体集団を生成する（Ｓ０１４）。ここで、式（１）において、ｆｉは、染色体ｉについての適合度を表すものとする。
【００５３】
【数１】

尚、この選択に用いられる計算式（１）は、最適化問題の種類に応じて準備される式である。また、本実施形態においては、選択を行う際に、特に事例の内容を考慮した処理は行っていない。しかしながら、事例の内容を反映した選択圧力を用いて選択を行うことも可能であり、かかる場合には、さらに探索の効率を向上させることとなる。
【００５４】次に、当該染色体集団に含まれる染色体の数を探索総数に加えることにより、探索総数を更新する。例えば、図５の染色体集団の場合、各染色体の確率は図１７のように計算される。この例の場合では、選択する染色体の数ｇ１が１０個と与えられているので、平均的には、確率０．１ごとに１個の染色体が選択される計算となる。ただし、実際の選択においては、かかる選択は乱数を利用して行なわれるので、０．１よりも小さな確率しかもたない染色体が選択されることもある。ここでは、図１８の染色体集団が選択されたとする。また、当該染色体集団の生成により、探索数が２０に更新される。
【００５５】図１８に示す、選択された染色体集団を対象として、次に、探索方向制御知識を利用した交差を行なう（Ｓ０１５）。すなわち、初めに、Ｓ１５０で選択した染色体集団の中から乱数を用いて取り出した二つの染色体に対して、まず切断箇所を決定し、切断箇所で切り離された染色体同志の交換を行なう。次に、探索方向制御知識を利用して、交差の処理を行うのである。すなわち、まず、取り出した元の二つの染色体の中に、分類クラスが「正」となるビットパターンと一致するビットパターンがあるかどうかを判定する。ここで、分類クラスが「正」となるビットパターンとは、ステップＳ０１３において生成した判断規則のうち、結論部分が「正」となる判断規則の条件部分に対応している。例えば、図１６の判断規則の場合、第２ビット０（Ａ２＝０）、第３ビット１（Ａ３＝１）及び第２ビット０（Ａ２＝０）、第３ビット０（Ａ３＝０）、第５ビット（Ａ５＝１）という二つの「正」となるビットパターンが存在する。もし、このビットパターンが存在しないならば、取り出した染色体に対する交差は終了と判断する。一方、このビットパターンが存在しているならば、当該ビットパターンがあった元の染色体の遺伝子を多数保存している染色体に当該ビットパターンが表れるように、切断したもう一方の染色体との間で遺伝子（ビット）の交換を行なう。この探索方向制御知識を利用した交差を、式（２）で計算される交差率がｇ３のしきい値以上になるまで行なう。
【００５６】
【数２】

例えば、図１８の中から、染色体ｃ７と染色体ｃ３とが取り出されたとし、図１９のような交差によって、染色体ｃ１１，ｃ１２が生成されたものとする。ここで、図１９に示すように、染色体ｃ７には、第２ビット０、第３ビット０、第５ビット１という「正」の分類クラスを持つビットパターンが含まれているので、適合度が高いと期待される事例と同じ当該ビットパターンが表れるように、染色体ｃ１１，ｃ１２の第２ビット及び第３ビットを交換する。この結果、図２０に示す染色体ｃ１３，ｃ１４が生成される。ここで、しきい値ｇ３の値を０．８とした場合には、４回の交差が行なわれることとなり、８個の染色体が作り直される。作り直された後の染色体集団を図２１に示す。
【００５７】かかる交差の処理ののち、図２１に示す、交差後の染色体集団を対象として、探索方向制御知識を利用した突然変異を行なう（Ｓ０１６）。すなわち、染色体集団の染色体の各ビットに対して、探索方向制御知識を利用したビットの反転を行なう。。具体的には、分類クラス「正」のビットパターンに対応するビットパターンに含まれるビットの場合には、当該ビットパターンに突然変異を行なわないと判断する。一方、それ以外のビットに対しては、ｇ４の確率で、ビットの反転を行なう。例えば、図２１の染色体集団に含まれる染色体ｃ１４の場合、「正」のビットパターンと一致する第２，第３，第５ビット以外のビットが突然変異の対象となる。染色体ｃ１４の場合、第７ビットにだけ突然変異が発生するとすれば、図２２に示すように染色体ｃ１４から染色体ｃ２１が生成される。ここで、突然変異率ｇ４が０．１と与えられているならば、染色体集団全体では１２０個のビットが存在し、このうち図２１に示すように、分類クラスが「正」となるビットパターンを構成するビットが１４個存在するので、これが突然変異の対象から除かれ、平均的には１０．６個のビットが反転される。このとき、図２１の染色体集団に含まれる染色体に対して、突然変異を実施した結果の例を図２３に示す。図２３においては、１０個のビットが反転されている。
【００５８】また、本実施形態においては、分類クラスが「正」となる判断規則のみをすべて直接利用した交差および突然変異を行なっている（Ｓ０１５、Ｓ０１６）。しかしながら、事例数が少ない探索当初においては、正しい判断規則が生成されているとは限らないので、分類クラスが「正」となる判断規則に、判断規則を構成する事例の数に応じて順位付けを行ない、探索が進むにつれて、ビットパターンを保存するのに利用する判断規則を増加させるといった方法も考えられる。
【００５９】さらに、分類クラスが「正」となる判断規則のみならず、これと併用して、または単独で、分類クラスが「負」となる判断規則をも利用した交差および突然変異を行なってもよい。すなわち、交差については、分類クラスが負となるビットパターンに対して、このビットパターンが出現しないように、さらに二つの染色体の遺伝子を交換してもよいし、突然変異については、分類クラスが負となるビットパターンに対しては、このビットパターンが壊れるように、このビットパターンの一部が必ず反転するようにしてもよい。この他、本実施形態に示した方法以外にも、本発明の要旨を逸脱しない範囲で種々変形して実施し得る。
【００６０】以上が１つの世代について行われる最適解探索の処理である。これらの処理を、次世代の染色体集団に対しても、染色体集団が収束したとの判断がなされるまで（Ｓ０１２）、再帰的に繰り返すことによって、最適解を探索するのである。
【００６１】このようにして、本実施形態によれば、以下の効果が得られる。すなわち、適合度に応じて選択した事例を遺伝子操作に利用することによって、より適合度の高いビットパターンを次世代の染色体に残し易くすることとなり、従来のＧＡに比べて、少ない探索数で最適解に到達することが可能となった。
【００６２】
【発明の効果】以上説明したように、本発明によれば、以下に記載されるような効果を奏する。即ち、生成された解の中から、適合度の値に応じて抽出した解および分類クラスを事例として蓄積し、かかる事例集合から最適解探索の方向性を制限するための判断規則を帰納学習によって自動生成するという機能を有するので、生成された判断規則を用いて、適合度の高い解（より良い解）が存在すると期待される方向に最適解探索の方向を限定することが可能となる。従って、探索におけるランダム性を軽減し、最適解の近傍における解の収束度を向上させて、より少ない探索数で最適解を得ることが可能となるという効果が得られる。このように探索を効率化することにより、最適化問題処理における解の評価時間と解の探索時間とをともに減少させることができる。このため、結果的に、より高速に最適解を得ることが可能となる。また、同様に、実用レベルの最適化問題、いわゆる準最適解を得る問題においても、現実的な時間内において最適解を発見することが可能となる。
【００６３】さらに、判断規則を生成するために用いられる事例の蓄積、即ち知識の獲得自体を、あらかじめ準備することなく、自動的に行う機能を有するので、判断規則獲得の負荷を軽減することができ、トータルの探索処理の高速化を図ることが可能となるという効果が得られる。
【００６４】また、判断規則生成の基礎となる事例集合を、適合度の幅を用いて洗練化する機能を有するので、世代数が増して蓄積される事例の数が増すにつれて、最適解探索の方向を、より良い解が存在すると期待される方向に、より限定することが可能となるという効果を有する。これにより、最適解の収束度をより向上させ、さらに効率良く最適解探索を行うことが可能となる。
【００６５】また、判断規則生成の基礎となる事例は、評価の結果を正負の分類クラスにより保持する機能を有するので、かかる分類クラスの値を用いて判断規則生成を行うことにより、大規模なＡＩ、事例ベース推論システム等を必要とすることなく、簡易に最適解探索を行うことが可能となるという効果が得られる。
【００６６】さらに、事例抽出の判断に用いるしきい値を内部的に生成するという機能を有するので、事例格納の判断のためにあらかじめ外部からしきい値を入力することが不要となるという効果が得られる。これにより、人的経験に依存することなく、さらに簡易に最適解探索を行うことが可能となる。
【００６７】このように、本発明を用いれば、最適化問題の適用される分野に応じて、生産コストや流通コストの削減、製品の精度の向上など、種々の産業分野における実用的効果を奏することができるのであり、産業上その効果の極めて大きい発明である。
【出願人】 【識別番号】０００００３０７８
【氏名又は名称】株式会社東芝
【出願日】 平成９年（１９９７）９月５日
【代理人】 【弁理士】
【氏名又は名称】三好 秀和 （外３名）
【公開番号】 特開平１１−８５７２０
【公開日】 平成１１年（１９９９）３月３０日
【出願番号】 特願平９−２４１５１９