(57)【特許請求の範囲】
【請求項１】
遺伝子アルゴリズムを利用して最適解を求めるべく複数の戦略アルゴリズムを備えた推論装置において、
ユーザが与える目的関数を入力する目的入力手段と、
前記目的関数の複雑さを推論する複雑さ推論手段と、
前記遺伝子アルゴリズムにおけるＧＡパラメータを前記目的関数の複雑さに応じて自動的に設定するＧＡパラメータ設定手段と、
を有することを特徴とする推論装置。
【請求項２】
前記目的関数および前記ＧＡパラメータにしたがって推論プロセスを実行して解を求める推論プロセス実行手段と、
前記推論プロセスの実行に際し、個体の評価値の変動または前記解のばらつきに応じて前記ＧＡパラメータを動的に変更するＧＡパラメータ変更手段と、
をさらに具備することを特徴とする請求項１に記載の推論装置。
【請求項３】
前記目的入力手段は、前記目的関数をファジィルールで定義することを特徴とする請求項１または２に記載の推論装置。
【請求項４】
遺伝子アルゴリズムを利用して最適解を求めるべく複数の戦略アルゴリズムを備えた推論装置を用いた推論方法において、
前記推論装置の目的入力手段からユーザに目的関数を入力させる目的入力ステップと、
前記推論装置の推論手段によって、前記目的関数の複雑さを推論する複雑さ推論ステップと、
前記推論装置のＧＡパラメータ設定手段によって、前記遺伝子アルゴリズムにおけるＧＡパラメータを前記目的関数の複雑さに応じて自動的に設定するＧＡパラメータ設定ステップと、
を有することを特徴とする推論方法。
【請求項５】
前記推論装置の推論プロセス実項手段によって、前記目的関数および前記ＧＡパラメータにしたがって推論プロセスを実行して解を求める推論プロセス実行ステップと、
前記推論プロセスの実行に際し、前記推論装置のＧＡパラメータ変更手段によって、個体の評価値の変動または前記解のばらつきに応じて前記ＧＡパラメータを動的に変更するＧＡパラメータ変更ステップと、
を有することを特徴とする請求項４に記載の推論方法。
【請求項６】
前記目的入力ステップは、前記目的関数をファジィルールで定義させることを特徴とする請求項４または５に記載の推論方法。
【請求項７】
コンピュータに、遺伝子アルゴリズムを利用して最適解を求めるべく複数の戦略アルゴリズムが組み込まれた推論方法を推論装置によって実行させるためのプログラムを記録した記録媒体において、
前記推論装置の目的入力手段からユーザに目的関数を入力させる目的入力ステップと、
前記推論装置の推論手段によって、前記目的関数の複雑さを推論する複雑さ推論ステップと、
前記推論装置のＧＡパラメータ設定手段によって、前記遺伝子アルゴリズムにおけるＧＡパラメータを前記目的関数の複雑さに応じて自動的に設定するＧＡパラメータ設定ステップと、
を前記推論装置に実行させるためのプログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、遺伝子アルゴリズム（ＧＡ：Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍ）を利用して最適解を求めるべく複数の戦略アルゴリズムを備えた推論装置、推論方法および該推論方法を実行させるためのプログラムを記録した記録媒体に係り、特に、ユーザが入力した目的から、適用する問題の複雑さを推論して、遺伝子アルゴリズムを適用する問題の複雑さにより遺伝子の型、個体の数、世代数等の遺伝子アルゴリズムにおけるパラメータを自動的に設定でき、個体の評価値の変動或いは解のばらつきにより動的に遺伝子アルゴリズムにおけるパラメータを変動させ得る推論装置、推論方法および記録媒体に関する。
【０００２】
【従来の技術】
従来の最適化手法として、１９７０年代初期に  Ｊｏｈｎ  Ｈｏｌｌａｎｄ  によって提案された自然淘汰の原理に基づくアルゴリズムである遺伝子アルゴリズム（ＧＡ：Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍ）がある。この遺伝子アルゴリズムは、探索空間の中の一点だけでなく、多くの点を同時に考慮するため局所解に陥りにくいという特徴を持っており、広い範囲の探索、最適化問題、機械学習などに応用されている。また、従来から遺伝子アルゴリズムを応用した種々の提案がなされているが、遺伝子アルゴリズム自体のパラメータを設定するものについては未だ提案されていない。
【０００３】
【発明が解決しようとする課題】
このような従来の遺伝子アルゴリズムを利用して最適解を求める推論装置にあっては、ユーザが、遺伝子アルゴリズムを特徴づけるパラメータを事前に設定する必要がある。ここで、該パラメータには、例えば、遺伝子の表現型、染色体の長さ、選択戦略（ルーレット戦略等の戦略種別，順位等）、選択時のスケーリング手法（線形スケーリング，シグマ切断等）、交差戦略（一点交差，二点交差，一様交差）、交差率、突然変異率、終了判定、目的関数等々がある。このようなパラメータは、適用する問題の性質により変更されなければならないが、実際にユーザは、どのように変更すればよいか分からず試行錯誤を繰り返すこととなり、適用問題に応じて適正なパラメータを設定するのが難しいという問題があった。
【０００４】
本発明は、このような従来の問題点に着目してなされたもので、その目的とするところは、ユーザが入力した目的（入力値の取りうる範囲、個体の評価関数、個体の評価ルール）から、適用する問題（入出力空間）の複雑さを推論して、遺伝子アルゴリズムを適用する問題の複雑さにより、（ユーザが指定しなければならない遺伝子の表現型、染色体の長さ、目的関数以外の）遺伝子の型、個体の数、世代数等の遺伝子アルゴリズムにおけるパラメータを自動的に設定し得る推論装置、推論方法および記録媒体を提供することにある。
【０００５】
また、本発明の他の目的は、個体の評価値の変動或いは解（推論結果）のばらつきにより、動的に遺伝子アルゴリズムにおけるパラメータを変動させ得る推論装置、推論方法および記録媒体を提供することにある。
【０００６】
【課題を解決するための手段】
上記課題を解決するために、本出願の第１の発明は、遺伝子アルゴリズムを利用して最適解を求めるべく複数の戦略アルゴリズムを備えた推論装置において、ユーザが与える目的関数を入力する目的入力手段と、前記目的関数の複雑さを推論する複雑さ推論手段と、前記遺伝子アルゴリズムにおけるＧＡパラメータを前記目的関数の複雑さに応じて自動的に設定するＧＡパラメータ設定手段とを具備することを特徴とする推論装置にある。
【０００７】
本出願の第２の発明は、前記第１の発明による推論装置において、前記目的関数および前記ＧＡパラメータにしたがって推論プロセスを実行して解を求める推論プロセス実行手段と、前記推論プロセスの実行に際し、個体の評価値の変動または前記解のばらつきに応じて前記ＧＡパラメータを動的に変更するＧＡパラメータ変更手段とを具備することを特徴とするものである。
【０００８】
本出願の第３の発明は、前記第１の発明または第２の発明による推論装置において、前記目的入力手段は、前記目的関数をファジィルールで定義することを特徴とするものである。
【０００９】
本出願の好ましい実施の形態においては、前記第３の発明による推論装置において、前記ＧＡパラメータ変更手段は、世代交代が進むにつれ交差率の変動をファジィ推論により求めるものであってもよい。
【００１０】
本出願の好ましい実施の形態においては、前記第３の発明による推論装置において、前記ＧＡパラメータ変更手段は、世代交代が進むにつれ突然変異率の変動をファジィ推論により求めるものであってもよい。
【００１１】
本出願の好ましい実施の形態においては、前記第３の発明による推論装置において、前記ＧＡパラメータ変更手段は、世代交代が進むにつれスケーリングのパラメータ変動をファジィ推論により求めるものであってもよい。
【００１２】
本出願の好ましい実施の形態においては、前記第３の発明による推論装置において、前記ＧＡパラメータ変更手段は、世代交代が進むにつれスケーリング戦略をファジィ推論により求めるものであってもよい。
【００１３】
本出願の第４の発明は、遺伝子アルゴリズムを利用して最適解を求めるべく複数の戦略アルゴリズムを備えた推論装置を用いた推論方法において、前記推論装置の目的入力手段からユーザに目的関数を入力させる目的入力ステップと、前記推論装置の推論手段によって、前記目的関数の複雑さを推論する複雑さ推論ステップと、前記推論装置のＧＡパラメータ設定手段によって、前記遺伝子アルゴリズムにおけるＧＡパラメータを前記目的関数の複雑さに応じて自動的に設定するＧＡパラメータ設定ステップと、を具備することを特徴とする推論方法にある。
【００１４】
本出願の第５の発明は、前記第４の発明による推論方法において、前記推論装置の推論プロセス実項手段によって、前記目的関数および前記ＧＡパラメータにしたがって推論プロセスを実行して解を求める推論プロセス実行ステップと、前記推論プロセスの実行に際し、前記推論装置のＧＡパラメータ変更手段によって、個体の評価値の変動または前記解のばらつきに応じて前記ＧＡパラメータを動的に変更するＧＡパラメータ変更ステップと、を具備することを特徴とするものである。
【００１５】
本出願の第６の発明は、前記第４または第５の発明による推論方法において、前記目的入力ステップは、前記目的関数をファジィルールで定義させることを特徴とするものである。
【００１６】
本出願の好ましい実施の形態においては、前記第６の発明による推論方法において、前記ＧＡパラメータ変更ステップは、世代交代が進むにつれ交差率の変動をファジィ推論により求めるものであってもよい。
【００１７】
本出願の好ましい実施の形態においては、前記第６の発明による推論方法において、前記ＧＡパラメータ変更ステップは、世代交代が進むにつれ突然変異率の変動をファジィ推論により求めるものであってもよい。
【００１８】
本出願の好ましい実施の形態においては、前記第６の発明による推論方法において、前記ＧＡパラメータ変更ステップは、世代交代が進むにつれスケーリングのパラメータ変動をファジィ推論により求めるものであってもよい。
【００１９】
本出願の好ましい実施の形態においては、前記第６の発明による推論方法において、前記ＧＡパラメータ変更ステップは、世代交代が進むにつれスケーリング戦略をファジィ推論により求めるものであってもよい。
【００２０】
本出願の第７の発明は、コンピュータに、遺伝子アルゴリズムを利用して最適解を求めるべく複数の戦略アルゴリズムが組み込まれた推論方法を推論装置によって実行させるためのプログラムを記録した記録媒体において、前記推論装置の目的入力手段からユーザに目的関数を入力させる目的入力ステップと、前記推論装置の推論手段によって、前記目的関数の複雑さを推論する複雑さ推論ステップと、前記推論装置のＧＡパラメータ設定手段によって、前記遺伝子アルゴリズムにおけるＧＡパラメータを前記目的関数の複雑さに応じて自動的に設定するＧＡパラメータ設定ステップと、を前記推論装置に実行させるためのプログラムを記録した記録媒体にある。
【００２１】
本出願の好ましい実施の形態においては、前記第７の発明による記録媒体は、コンピュータに、前記目的関数および前記ＧＡパラメータにしたがって推論プロセスを実行して解を求める推論プロセス実行ステップと、前記推論プロセスの実行に際し、個体の評価値の変動または前記解のばらつきに応じて前記ＧＡパラメータを動的に変更するＧＡパラメータ変更ステップとを実行させるためのプログラムを記録したものであってもよい。
【００２２】
本出願の好ましい実施の形態においては、前記第７の発明による記録媒体において、前記目的入力ステップは、前記目的関数をファジィルールで定義するものであってもよい。
【００２３】
ここで、前記ＧＡパラメータ変更ステップは、世代交代が進むにつれ交差率の変動をファジィ推論により求めるものであってもよい。
【００２４】
ここで、前記ＧＡパラメータ変更ステップは、世代交代が進むにつれ突然変異率の変動をファジィ推論により求めるものであってもよい。
【００２５】
ここで、前記ＧＡパラメータ変更ステップは、世代交代が進むにつれスケーリングのパラメータ変動をファジィ推論により求めるものであってもよい。
【００２６】
ここで、前記ＧＡパラメータ変更ステップは、世代交代が進むにつれスケーリング戦略をファジィ推論により求めるものであってもよい。
【００２７】
そして、この第１の発明、第４の発明または第７の発明によれば、目的入力手段（目的入力ステップ）によりユーザが与える目的関数を入力すると、複雑さ推論手段（複雑さ推論ステップ）では目的関数の複雑さを推論し、ＧＡパラメータ設定手段（ＧＡパラメータ設定ステップ）では、遺伝子アルゴリズムにおけるＧＡパラメータを目的関数の複雑さに応じて自動的に設定するようにしている。
【００２８】
このように、ユーザが入力した目的関数（入力値の取りうる範囲、個体の評価関数、個体の評価ルール等）から、適用する問題（入出力空間）の複雑さを推論して、遺伝子アルゴリズムを適用する問題の複雑さにより、（ユーザが指定しなければならない遺伝子の表現型、染色体の長さ、目的関数以外の）遺伝子の型、個体の数、世代数等の遺伝子アルゴリズムにおけるＧＡパラメータを自動的に設定できるので、ユーザが遺伝子アルゴリズムにおけるＧＡパラメータを設定する場合に、従来のように試行錯誤を繰り返す必要がなく、容易に設定できる。また、遺伝子アルゴリズムを複数（各種戦略）を組み込んだ構造にしているので、問題ごとにアルゴリズムを組み替える必要がなく、汎用の推論装置および推論方法を実現できる。
【００２９】
また、第２の発明または第５の発明によれば、推論プロセス実行手段（推論プロセス実行ステップ）により、目的関数およびＧＡパラメータにしたがって推論プロセスを実行して解を求め、ＧＡパラメータ変更手段（ＧＡパラメータ変更ステップ）では、推論プロセスの実行に際し、個体の評価値の変動または解のばらつきに応じてＧＡパラメータを動的に変更するようにしている。これにより、個体の評価値の変動或いは解（推論結果）のばらつきにより、遺伝子アルゴリズムにおけるＧＡパラメータを動的に変動させることができ、また、評価値に従って動的にＧＡパラメータを変更できるので、最適な解が早く求まる。
【００３０】
特に、目的入力手段は、目的関数を数式で定義し、または、目的入力手段は、目的関数をＣ言語などのプログラミング言語で定義し、また特に、第３の発明または第６の発明によれば、目的入力手段は、目的関数をファジィルールで定義するのが望ましい。これらにより、遺伝子アルゴリズムにおけるＧＡパラメータの詳細な意味が分からなくても容易に利用でき、よりユーザフレンドリなユーザインタフェースを実現することができる。
【００３１】
【発明の実施の形態】
以下、本発明の推論装置、推論方法および記録媒体の実施の形態について、図面を参照して詳細に説明する。
【００３２】
図１は本発明の一実施形態に係る推論装置の構成図である。本実施形態の推論装置は、遺伝子アルゴリズムを利用して最適解を求めるべく複数の戦略アルゴリズムを備えたものである。
【００３３】
図１において、本実施形態の推論装置は、ユーザが与える目的関数を入力する目的入力部１０１と、入力された目的関数から問題の複雑さを推論する複雑さ推論部１０２と、遺伝子アルゴリズムにおける遺伝子の型、染色体の長さ、個体の数、各種戦略などのＧＡパラメータを問題の複雑さに応じて自動的に初期設定するＧＡパラメータ設定部１０３と、目的関数およびＧＡパラメータにしたがって推論プロセスを実行して解を求める推論プロセス実行部１０４と、個体の評価値の変動および解を監視するＧＡ監視部１０５と、評価値の変化の監視結果により、個体の評価値の変動または解のばらつきに応じてＧＡパラメータを動的に変更するＧＡパラメータ変更部１０６と、推論結果出力部１０７とを備えて構成されている。
【００３４】
本実施形態の推論装置は、遺伝子アルゴリズムを複数（各種戦略）を組み込んだ構造にしているので、問題ごとにアルゴリズムを組み替える必要がなく、汎用の推論装置および推論方法を実現できるものであるが、以下の説明では、当該推論装置がナップサック問題を扱うものとして説明する。
【００３５】
ここで、「ナップサック問題」とは、ナップサックの重量制限のもとで、それぞれ異なる重量と価値の品物をナップサックに詰め込むときに、総価値が最大になるような品物の組合わせを選択するものである。
【００３６】
この問題を定式化すると、次のようになる。すなわち、品物の個数をｎ、ｊ番目の品物をｊ、重量をａｊ、価値をｃｊ、最大重量をｂとするとき、目的関数ｆｉは次式（数１）で表される。
【００３７】
【数１】
ｆｉ＝Σａｊ・ｃｊ  ；Σａｊ・ｃｊ≦ｂのとき
ｆｉ＝０          ；Σａｊ・ｃｊ＞ｂのとき                    （数１）
但し、Σはｊ＝１〜ｎの積和を意味する。
【００３８】
品物の個数が２０である場合は、ｎ＝２０となる。上記の問題を遺伝子で表現すると図３に示すようになる。各遺伝子の内容は、「荷物を入れる」ことを意味する“１”と、「荷物を入れない」ことを意味する“０”であり、染色体は“０”と“１”のビット列となっている。
【００３９】
ここで、遺伝子アルゴリズムで使用される語について説明をしておく。「遺伝子（ｇｅｎｅ）」は個体の性質を規定する基本的構成要素であり、「染色体（ｃｈｒｏｍｏｓｏｍｅ）」は遺伝子の集合体である。また「個体（ｉｎｄｉｖｉｄｕａｌ）」は染色体によって特徴づけられた自律的な個であり、「集団（ｐｏｐｕｌａｔｉｏｎ）」は個体の集まりである。また「遺伝子型（ｇｅｎｏｔｙｐｅ）」は特徴量と特徴量のマッピングの表現方法であり、一般的に、図３に示したように“０”と“１”のビット列を用いる方法が良いとされている。また「遺伝子座（ｌｏｃｕｓ）」は染色体上の遺伝子の位置を意味する。さらに「表現型（ｐｈｅｎｏｔｙｐｅ）」は染色体によって規定される形質の外部的表現であり、遺伝子型は形質の染色体による内部表現である。表現型から遺伝子型への写像を「コード化（ｃｏｄｉｎｇ）」と呼び、遺伝子型から表現型への写像を「デコード化（ｄｅｃｏｄｉｎｇ）」という。尚、多くの探索問題において、表現型＝遺伝子型とすれば十分であることが経験的に知られている。
【００４０】
次に、本実施形態の推論装置を構成する各構成要素の機能および動作について詳細に説明する。まず、目的入力部１０１では、遺伝子アルゴリズムを適用する問題の目的関数をユーザが入力するが、その入力方法には、目的関数を数式で定義する第１の入力方法、目的関数をＣ言語などのプログラミング言語で定義する第２の入力方法、目的関数をファジィルールで定義するする第３の入力方法がある。このように、問題に応じた入力方法を選択して目的関数を入力できるので、よりユーザフレンドリなユーザインタフェースを実現することができる。
【００４１】
上記ナップザック問題の場合、目的関数を数式で定義する第１の入力方法では、上記（１）式の目的関数が入力されることとなる。また、プログラミング言語で定義する第２の入力方法では、例えば、図２の目的入力画面２０１における目的関数の画面領域２０４に示すように、Ｃ言語における関数として入力されることとなる。また、目的関数の表記は、プロダクションルール（第３の入力方法）で記述しても良い。
【００４２】
また、目的入力部１０１では、図２の目的入力画面２０１に示したように、目的関数の他に、「解の質」および「遺伝子の表現型」についても入力される。
【００４３】
まず、解の質の入力では、図２における解の質の画面領域２０２に示すように、求める解の質について表示されたものの中からラジオボタンなどにより選択する。図２の例では、「幅広く探索」，「普通に探索」，「とにかく解が見つかればよい」の中から、「普通に探索」が選択されている。
【００４４】
また、遺伝子の表現型の入力では、図２における遺伝子の表現型の画面領域２０３に示すように、「遺伝子が取りうる値」および「遺伝子間の関連」の数値を入力する。図２の例では、「遺伝子が取りうる値」として“８”が指定されているので、遺伝子は１〜８の値を取ることになる。また、遺伝子間の関連は隣合う遺伝子同士に関係があるかどうかを示すものである。図２の例では、「遺伝子間の関連」として“１”が指定されているので関連は無いことになる。尚、もし「遺伝子間の関連」の値が“３”であれば、隣合う３つの遺伝子で１つの意味を持つことになる。
【００４５】
次に、複雑さ推論部１０２では、入力された目的関数から問題の複雑さ（局所解の多さ）を推論する。ナップザック問題の場合、例えば図２のようなＣ言語による目的関数が入力されるが、該関数を構文解析することにより、ループの回数、並びに、和、差、積、商および三角関数等の演算子の数を求める。尚、ループの回数は染色体の長さを表すこととなる。
【００４６】
目的関数の複雑さは、これらループの回数や演算子の使用回数により決まる。すなわち、積や商の演算子が多く使われていると問題は複雑になる。具体的には、目的関数の複雑さは以下のようなルール（数２）で決定する。
【００４７】
【数２】
ｉｆ（染色体の長さ＝大）ｔｈｅｎ（複雑）
ｉｆ（積の数＝小）ｔｈｅｎ（簡単）
ｉｆ（商の数＝小）ｔｈｅｎ（簡単）
ｉｆ（積の数＝中）ｔｈｅｎ（普通）
ｉｆ（商の数＝中）ｔｈｅｎ（普通）
ｉｆ（積の数＝大）ｔｈｅｎ（複雑）
ｉｆ（商の数＝大）ｔｈｅｎ（複雑）
ｉｆ（和の数＝大）ｔｈｅｎ（やや複雑）
ｉｆ（差の数＝大）ｔｈｅｎ（やや複雑）
ｉｆ（三角関数の数＝大）ｔｈｅｎ（とても複雑）
ｉｆ（べきの数＝大）ｔｈｅｎ（とても複雑）              （数２）
【００４８】
また、目的関数がプロダクションルール（第３の入力方法）で記述されている場合には、ルール数およびメンバシップ関数（ＭＦ）の分割数により目的関数の複雑度を想定する。図４（ａ）および（ｂ）には、メンバシップ関数（ＭＦ）の例を示す。
【００４９】
ナップサック問題の場合、目的関数の複雑さは、積の数が“１”で小であるので複雑さは「簡単」で、一方、遺伝子数が２０で染色体の長さは大であるので複雑さは「複雑」となるが、両者の加重平均をとることにより、問題全体としては「普通」と判断されることとなる。
【００５０】
次に、ＧＡパラメータ設定部１０３では、遺伝子アルゴリズムにおける遺伝子の型、染色体の長さ、個体の数、各種戦略などのＧＡパラメータを、遺伝子の表現型、目的関数の複雑さと求める解の質により決定する。各パラメータの選択ルールを以下に示す。
【００５１】
［１］選択時のスケーリング手法  遺伝子アルゴリズムの処理の初期状態では、スケーリング無しを選択する。尚、スケーリングは、最初の個体の評価後にＧＡパラメータ変更部１０６により選択される。
【００５２】
［２］交差戦略  交差戦略は、染色体の長さおよび遺伝子間の関連に基づいて選択される。ここで、「交差」とは、２つの個体間で任意の位置で切れた遺伝子同士がつなぎ合わされる現象である。これにより、優秀な遺伝子同士が組み合わされ精度が向上していく（当然ながら悪くなる場合もある）。交差戦略には、一点交差、二点交差、一様交差などがある。交差戦略の選択ルールを以下の式（数３）に示す。
【００５３】
【数３】
ｉｆ（染色体の長さ＝短い）ｔｈｅｎ（一点交差）
ｉｆ（染色体の長さ＝中）ａｎｄ（遺伝子間の関連＞中）ｔｈｅｎ（一点交差）
ｉｆ（染色体の長さ＝中）ａｎｄ（遺伝子間の関連＝小）ｔｈｅｎ（二点交差）
ｉｆ（染色体の長さ＝大）ａｎｄ（遺伝子間の関連＝大）ｔｈｅｎ（一点交差）
ｉｆ（染色体の長さ＝大）ａｎｄ（遺伝子間の関連＝中）ｔｈｅｎ（二点交差）
ｉｆ（染色体の長さ＝大）ａｎｄ（遺伝子間の関連＝小）ｔｈｅｎ（一様交差）（数３）
【００５４】
［３］交差率  交差率は、解の質と目的関数の複雑さによって決める。ここで、「交差率」は、交差の起こる割合を決定するパラメータである。０〜１の値を取る。交差率の選択ルールを以下の式（数４）に示す。
【００５５】
【数４】
ｉｆ（解の質＝幅広く探索）ｔｈｅｎ（交差率＝大）
ｉｆ（解の質＝普通に探索）ｔｈｅｎ（交差率＝中）
ｉｆ（解の質＝とにかく解が見つかればよい）ｔｈｅｎ（交差率＝小）
ｉｆ（目的関数の複雑さ＝複雑）ｔｈｅｎ（交差率＝小）
ｉｆ（目的関数の複雑さ＝やや複雑）ｔｈｅｎ（交差率＝中）
ｉｆ（目的関数の複雑さ＝とても複雑）ｔｈｅｎ（交差率＝大）  （数４）
【００５６】
［４］突然変異率  突然変異率は、解の質と目的関数の複雑さによって決める。ここで、「突然変異」とは、ある時突然に遺伝子が変化してしまう現象であり、この突然変異によりローカルミニマムに陥りそうになることを防ぐ。どこがどのように変わるかはランダムに決定される。「突然変異率」は、遺伝子の突然変異の割合を決定するパラメータであり、０〜１の値を取る。突然変異率の値は通常０．１〜０．５％程度が良いとされている。突然変異率の選択ルールを以下の式（数５）に示す。
【００５７】
【数５】
ｉｆ（解の質＝幅広く探索）ｔｈｅｎ（突然変異率＝大）
ｉｆ（解の質＝普通に探索）ｔｈｅｎ（突然変異率＝中）
ｉｆ（解の質＝とにかく解が見つかればよい）ｔｈｅｎ（突然変異率＝小）
ｉｆ（目的関数の複雑さ＝複雑）ｔｈｅｎ（突然変異率＝小）
ｉｆ（目的関数の複雑さ＝やや複雑）ｔｈｅｎ（突然変異率＝中）
ｉｆ（目的関数の複雑さ＝とても複雑）ｔｈｅｎ（突然変異率＝大）  （数５）
【００５８】
［５］終了判定  終了判定は、解の質と目的関数の複雑さによって決める。終了判定の選択ルールを以下の式（数６）に示す。
【００５９】
【数６】
ｉｆ（解の質＝幅広く探索）ｔｈｅｎ（終了判定＝長く）
ｉｆ（解の質＝普通に探索）ｔｈｅｎ（終了判定＝普通）
ｉｆ（解の質＝とにかく解が見つかればよい）ｔｈｅｎ（終了判定＝短く）
ｉｆ（目的関数の複雑さ＝複雑）ｔｈｅｎ（終了判定＝短く）
ｉｆ（目的関数の複雑さ＝やや複雑）ｔｈｅｎ（終了判定＝普通）
ｉｆ（目的関数の複雑さ＝とても複雑）ｔｈｅｎ（終了判定＝長く）  （数６）
【００６０】
尚、遺伝的アルゴリズムの終了判定は、集団評価ステップにおいて行われ、具体的には、以下の条件を満たした場合にアルゴリズムを終了させるものである。すなわち、第１は「世代交代数」について、与えられた世代交代の回数に達した場合に終了する。探索空間や個体数により変化するが、より広範囲な領域を探索する場合などは世代交代数を大きくする。また第２は「最大適合度」について、最大適合度が設定したしきい値を越えた場合に終了する。適合度の最大値が明確にわかっている場合や０〜１に正規化している場合に利用できる。１つでも良い解が得られた場合に設定する条件である。また第３は「平均適合度」について、平均適合度が設定したしきい値を越えた場合に終了する。適合度の最大値が明確にわかっている場合や０〜１に正規化している場合に利用できる。複数の解を求めたい場合に設定する条件である。さらに第４は「適合度増加率」について、適合度の増加率が一定時間以上連続した場合に終了する。最大適合度がわからない場合で、ある程度質の良い解を求めたい場合に設定する条件である。
【００６１】
次に、推論プロセス実行部１０４では、ユーザによって定義され入力された目的関数とＧＡパラメータ設定部１０３によって決定されたＧＡパラメータにしたがって遺伝子アルゴリズム（推論プロセス）を実行して解を求める。
【００６２】
ここで、遺伝子アルゴリズムに関する処理は、一般的に以下のような手順で実行される。まず、手順１では、初期集団を発生させる。ランダムに発生させる場合と制約に基づいて発生させる場合とがある。ランダムに発生させる場合は、探索空間全体を探索するときにはなるべく全体に分散するように初期集団を発生させる。探索開始時において、探索空間がブラックボックスであり、どのような個体が有効か全くわからない場合に応用する。一般的には、探索初期において探索空間がブラックボックスであることが多い。また、制約に基づいて発生させる場合は、探索空間に対して何らかのルール、ノウハウが存在するとき、評価値が高いと思われる部分を中心に遺伝子を生成する。
【００６３】
次に、手順２では、各個体の適応度を計算する。すなわち、各個体がどれだけ環境に適合しているかを求める。具体的には、適合度計算、スケーリングおよび淘汰が行われる。まず、適合度計算では、各個体に対して適合度の計算を行う。各個体の評価は問題によって異なり、評価関数の与え方が問題となる。評価関数をどのように与えるかが工夫のしどころとなる。評価関数を与えることが困難な場合は、ルールを利用することもできる。次に、スケーリングでは、淘汰を効率よく進めるためスケーリングを採用する。「スケーリング」とは、本来の適合度に対して適合度の大きさ或いは適合度の標準偏差により傾斜を付ける操作である。この操作により初期段階にはなるべく均等に淘汰され、収束段階では適合度の低い個体をより優先的に淘汰させることができる。最後に、淘汰では、環境に適合しない個体（適合度が低い個体）が間引かれる。すなわち、より環境に適合している子孫を残すようにする。
【００６４】
次に、手順３では、集団評価が行われる。つまり、遺伝的アルゴリズムの終了判定であり、これについては上述した通りである。
【００６５】
次に、手順４では、遺伝子の交差が行われる。つまり、２つの個体を取り出し、それぞれの遺伝子を交差させる。遺伝子を交差させるかどうかは交差率によって決定する。交差率が高いほど交差する可能性が高くなり速く進化が進むが、よりよい解に収束するとは限らない。
【００６６】
最後に、手順５では、遺伝子の突然変異が行われる。つまり、個体の一部の遺伝子を変化させる。変化させるかどうかは突然変異率によって決定する。突然変が多いと、様々な状態に変化し探索空間を広く探索できるが、よりよい解に収束するとは限らない。尚、手順５を経た集団は、手順２に進んで、再び各個体の適応度が計算されることとなる。
【００６７】
次に、ＧＡ監視部１０５では、推論プロセス実行部１０４で計算された各個体の適合度（適合度の分散および最大適合度）の変異を監視する。
【００６８】
また、ＧＡパラメータ変更部１０６では、ＧＡ監視部１０５で監視された各個体の適合度（適合度の分散、最大適合度）の変異により、遺伝子アルゴリズムのＧＡパラメータを変更する。ここで変更されるＧＡパラメータは、スケーリング手法、スケーリング手法のパラメータ、交差率、並びに、突然変異率である。
【００６９】
まず、スケーリング手法およびスケーリング手法のパラメータについて説明する。スケーリング手法には、適合度の変換に線形式を利用する線形スケーリング、適合度の変換にべき関数を利用するべき乗スケーリング、および、適合度の変換に標準偏差を利用するシグマ切断等があるが、各個体の適合度に基づいてこれら手法の中から選ばれる。具体的には次の選択ルールにより選択される。
【００７０】
【数７】
ｉｆ（個体群の中の多くの個体が高い適合度を持ち、残りのわずかな個体が非常
に小さな値の適合度を持つ場合が多い）ｔｈｅｎ（シグマ切断を選択する）
【００７１】
また、交差率は、世代交代数および各個体適合度の分散、並びに、最大適合度の変化率に基づいて変更される。交差率の変更ルールを以下の式（数８）に示す。
【００７２】
【数８】
ｉｆ（世代交代数＝大）ｔｈｅｎ（交差率＝小）
ｉｆ（最大適合度の変化率＝小）ｔｈｅｎ（交差率＝小）
ｉｆ（最大適合度の変化率＝中）ｔｈｅｎ（交差率＝中）
ｉｆ（最大適合度の変化率＝大）ｔｈｅｎ（交差率＝大）
ｉｆ（各個体適合度の分散＝小）ｔｈｅｎ（交差率＝小）
ｉｆ（各個体適合度の分散＝中）ｔｈｅｎ（交差率＝中）
ｉｆ（各個体適合度の分散＝大）ｔｈｅｎ（交差率＝大）        （数８）
【００７３】
次に、突然変異率は、各個体適合度の分散、および、最大適合度の変化率に基づいて変更される。突然変異率の変更ルールを以下の式（数９）に示す。
【００７４】
【数９】
ｉｆ（最大適合度の変化率＝小）ｔｈｅｎ（突然変異率＝小）
ｉｆ（最大適合度の変化率＝中）ｔｈｅｎ（突然変異率＝中）
ｉｆ（最大適合度の変化率＝大）ｔｈｅｎ（突然変異率＝大）
ｉｆ（各個体適合度の分散＝小）ｔｈｅｎ（突然変異率＝小）
ｉｆ（各個体適合度の分散＝中）ｔｈｅｎ（突然変異率＝中）
ｉｆ（各個体適合度の分散＝大）ｔｈｅｎ（突然変異率＝大）    （数９）
【００７５】
最後に、推論結果出力部１０７では、遺伝子アルゴリズムで最終的に求められた解（得られた遺伝子とその適合度）を出力する。出力先はディスプレイ等の表示機器やメモリ、ハードディスクなどの記憶媒体である。
【００７６】
以上のように、本実施形態によれば、目的入力部１０１（目的入力ステップ）によりユーザが与える目的関数を入力すると、複雑さ推論部１０２（複雑さ推論ステップ）では目的関数の複雑さを推論し、ＧＡパラメータ設定部１０３（ＧＡパラメータ設定ステップ）では、遺伝子アルゴリズムにおけるＧＡパラメータを目的関数の複雑さに応じて自動的に設定するようにし、ユーザが入力した目的関数（入力値の取りうる範囲、個体の評価関数、個体の評価ルール等）から、適用する問題（入出力空間）の複雑さを推論して、遺伝子アルゴリズムを適用する問題の複雑さにより、（ユーザが指定しなければならない遺伝子の表現型、染色体の長さ、目的関数以外の）遺伝子の型、個体の数、世代数等の遺伝子アルゴリズムにおけるＧＡパラメータを自動的に設定できるので、ユーザが遺伝子アルゴリズムにおけるＧＡパラメータを設定する場合に、従来のように試行錯誤を繰り返す必要がなく、容易に設定できる。また、遺伝子アルゴリズムを複数（各種戦略）を組み込んだ構造にしているので、問題ごとにアルゴリズムを組み替える必要がなく、汎用の推論装置および推論方法を実現できる。
【００７７】
また、本実施形態によれば、推論プロセス実行部１０４（推論プロセス実行ステップ）により、目的関数およびＧＡパラメータにしたがって推論プロセスを実行して解を求め、ＧＡパラメータ変更部１０６（ＧＡパラメータ変更ステップ）では、推論プロセスの実行に際し、個体の評価値の変動または解のばらつきに応じてＧＡパラメータを動的に変更するので、個体の評価値の変動或いは解（推論結果）のばらつきにより、遺伝子アルゴリズムにおけるＧＡパラメータを動的に変動させることができ、また、評価値に従って動的にＧＡパラメータを変更できるので、最適な解が早く求めることができる。
【００７８】
【発明の効果】
以上の説明から明らかなように、本発明によれば、目的入力手段（目的入力ステップ）によりユーザが与える目的関数を入力すると、複雑さ推論手段（複雑さ推論ステップ）では目的関数の複雑さを推論し、ＧＡパラメータ設定手段（ＧＡパラメータ設定ステップ）では、遺伝子アルゴリズムにおけるＧＡパラメータを目的関数の複雑さに応じて自動的に設定することとし、ユーザが入力した目的関数から、適用する問題の複雑さを推論して、遺伝子アルゴリズムを適用する問題の複雑さにより、遺伝子の型、個体の数、世代数等の遺伝子アルゴリズムにおけるＧＡパラメータを自動的に設定できるので、ユーザが遺伝子アルゴリズムにおけるＧＡパラメータを設定する場合に、試行錯誤を繰り返すことなく容易に設定でき、また、遺伝子アルゴリズムを複数（各種戦略）を組み込んだ構造にしているので、問題ごとにアルゴリズムを組み替える必要がなく、汎用の推論装置および推論方法を実現し得る推論装置、推論方法および記録媒体を提供することができる。
【００７９】
また、本発明によれば、推論プロセス実行手段（推論プロセス実行ステップ）により、目的関数およびＧＡパラメータにしたがって推論プロセスを実行して解を求め、ＧＡパラメータ変更手段（ＧＡパラメータ変更ステップ）では、推論プロセスの実行に際し、個体の評価値の変動または解のばらつきに応じてＧＡパラメータを動的に変更することとしたので、個体の評価値の変動或いは解（推論結果）のばらつきにより、遺伝子アルゴリズムにおけるＧＡパラメータを動的に変動させることができ、また、評価値に従って動的にＧＡパラメータを変更できるので、最適な解をより早く求め得る推論装置および推論方法を提供することができる。
【００８０】
また、本発明によれば、目的入力手段は、目的関数を数式、Ｃ言語などのプログラミング言語、或いはファジィルールで定義することとしたので、遺伝子アルゴリズムにおけるＧＡパラメータの詳細な意味が分からなくても容易に利用でき、よりユーザフレンドリなユーザインタフェースを実現した推論装置および推論方法を提供することができる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係る推論装置の構成図である。
【図２】目的入力画面を例示する説明図である。
【図３】ナップサック問題を遺伝子で表現した場合の説明図である。
【図４】図４（ａ）および（ｂ）はメンバシップ関数（ＭＦ）を例示する説明図である。
【符号の説明】
１０１    目的入力部
１０２    複雑さ推論部
１０３    ＧＡパラメータ設定部
１０４    推論プロセス実行部
１０５    ＧＡ監視部
１０６    ＧＡパラメータ変更部
１０７    推論結果出力部
２０１    目的入力画面
２０２    解の質の画面領域
２０３    遺伝子の表現型の画面領域
２０４    目的関数の画面領域
【図１】
0003599156.tif 000002
【図２】
0003599156.tif 000003
【図３】
0003599156.tif 000004
【図４】
0003599156.tif 000005