照合パラメータ最適化装置、最適化方法および最適化制御プログラム
【課題】自ら環境に適するように学習することができ、これによって経験を積んだ人に頼ることなく各種の照合用のパラメータを最適化することのできる照合パラメータ最適化装置、最適化方法および最適化制御プログラムを得ること。
【解決手段】初期パラメータ群を生成したら、指紋データを読み込んでパラメータを照合装置に適用する（ステップＳ２２３）。照合結果を取得したら評価関数を用いて適応度を算出し（ステップＳ２２５）、遺伝的アルゴリズムによりパラメータを変更して（ステップＳ２２７〜Ｓ２２９）、これを最大世代数だけ繰り返してパラメータ群を進化させて最適化する。これらを１段階として数段階処理を繰り返すことでパラメータを進化させてもよい。
【解決手段】初期パラメータ群を生成したら、指紋データを読み込んでパラメータを照合装置に適用する（ステップＳ２２３）。照合結果を取得したら評価関数を用いて適応度を算出し（ステップＳ２２５）、遺伝的アルゴリズムによりパラメータを変更して（ステップＳ２２７〜Ｓ２２９）、これを最大世代数だけ繰り返してパラメータ群を進化させて最適化する。これらを１段階として数段階処理を繰り返すことでパラメータを進化させてもよい。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、指紋照合パラメータ最適化装置のようにデータ照合用のパラメータを調節して最適な状態を作り出す装置に有効な照合パラメータ最適化装置、最適化方法および最適化制御プログラムに係わり、特に経験を積んだ有識者が手動でパラメータの設定を行うような装置の自動化に好適な照合パラメータ最適化装置、最適化方法および最適化制御プログラムに関する。
【背景技術】
【０００２】
たとえば指紋の照合を行うための指紋照合システムでは、多くの調節すべきパラメータが存在する。従来は、これらのパラメータを経験を積んだ特定の人が調節することで指紋照合システムのパフォーマンスを発揮してきた。
【０００３】
このような指紋照合システムでは、誰でもパラメータを調節できるようなシステム構成になっていない。このため、経験を積んだ人でなければパラメータを調節することができない。また、新たにパラメータが増えた場合、経験を積まなければ最適な値が分からないため、調節に時間と手間が掛かるという問題がある。
【０００４】
そこで、本発明の第１の関連技術として、電子回路パッケージの調整について遺伝的アルゴリズム（ＧＡ）とニューラルネットワークを適用することが提案されている（たとえば特許文献１参照）。この第１の関連技術で制御部は、機構部を制御して電子回路パッケージの調整用トリマの位置を指定した初期設定条件の状態に調整した後、測定部から電子回路パッケージに規定の入力信号を供給し、出力値を測定してその初期設定条件に対する出力値Ｘｓとして記憶する。そして、前記したすべての遺伝子をランダムに初期化したステップで設定したα個の遺伝子の１個を選択し、その遺伝子にコーディングされた回転量情報に基づいて各調整用トリマの回転を行った後、電子回路パッケージからの出力値を再び測定し記憶する。以上の前記した初期設定条件の状態に調整するステップから前記した電子回路パッケージからの出力値を再び測定し記憶するステップまでの処理を設定したα個のすべての遺伝子に対して実行した後、前記した記憶した出力値を調整目標の基準出力値Ｘｏと比較して適応度を算出するようにしている。
【０００５】
また、本発明の第２の関連技術として、指紋の照合に際して、指紋の特徴点をアルゴリズムで抽出して指紋の照合を行うことが提案されている（たとえば特許文献２参照）。この第２の関連技術では、指紋が入力されると、指紋画像から指紋の特徴点が抽出されて指紋情報が生成される。この指紋情報は、予め登録されている登録指紋情報ファイル中の指紋情報と照合される。そして、照合に成功した場合にはその指紋情報に対応する個人名が送られる。
【特許文献１】特開平０８−０１６２０７号公報（第００２３段落〜第００２５段落、図２）
【特許文献２】特開２００７−０５８６４９号公報（第００５３段落、図４）
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところで、学習アルゴリズムには、ニューラルネットワークや遺伝的アルゴリズムなどがある。ニューラルネットワークは教師付き学習といって、模範となる教師の存在を必要とする。本発明の第１の関連技術では、ニューラルネットワークを遺伝的アルゴリズムと併用している。このため、自ら環境に適するように学習するには不適当である。
【０００７】
次に本発明の第２の関連技術では、指紋の特徴点自体をアルゴリズムで抽出するようにしている。指紋の特徴点を抽出した後は、予め登録されている登録指紋情報ファイル中の指紋情報との照合が行われる。指紋情報が登録指紋情報ファイルに登録されているものであるとの照合結果を得た場合、すなわち、照合に成功した場合には、照合に成功した指紋情報に対応する個人名が送られる。
【０００８】
この照合を行う過程について、第２の関連技術で、パラメータの調整を行う配慮は行われていない。すなわち、第２の関連技術では、遺伝的アルゴリズムを指紋の特徴点の抽出に用いるだけであって、それ以上の工夫は行っていない。
【０００９】
そこで本発明の目的は、自ら環境に適するように学習することができ、これによって経験を積んだ人に頼ることなく各種の照合用のパラメータを最適化することのできる照合パラメータ最適化装置、最適化方法および最適化制御プログラムを提供することにある。
【００１０】
本発明の他の目的は、各種の照合用のパラメータについて、効率的に最適解を求めることのできる照合パラメータ最適化装置、最適化方法および最適化制御プログラムを提供することにある。
【課題を解決するための手段】
【００１１】
本発明では、（イ）各種データを照合するためのパラメータを生成する初期パラメータ生成手段と、（ロ）前記した各種データの照合を行う照合装置に前記したパラメータを適応することで照合結果を取得する照合結果取得手段と、（ハ）この照合結果取得手段により取得した照合結果を基に予め定められた評価関数を使用して適応度を算出する適応度算出手段と、（ニ）この適応度算出手段による適応度の算出が行われた後、この算出された適応度を基にして遺伝的アルゴリズムにより前記したパラメータを変更するパラメータ変更手段と、（ホ）このパラメータ変更手段で変更したパラメータについて前記した遺伝的アルゴリズムを最大世代数だけ世代交代を繰り返すことで最適化する最適化手段とを照合パラメータ最適化装置に具備させる。
【００１２】
また、本発明では、（イ）各種データを照合するためのパラメータを生成する初期パラメータ生成ステップと、（ロ）前記した各種データの照合を行う照合装置に前記したパラメータを適応することで照合結果を取得する照合結果取得ステップと、（ハ）この照合結果取得ステップにより取得した照合結果を基に予め定められた評価関数を使用して適応度を算出する適応度算出ステップと、（ニ）この適応度算出ステップによる適応度の算出が行われた後、この算出された適応度を基にして遺伝的アルゴリズムにより前記したパラメータを変更するパラメータ変更ステップと、（ホ）このパラメータ変更ステップで変更したパラメータについて前記した遺伝的アルゴリズムを最大世代数だけ世代交代を繰り返すことで最適化する最適化ステップと、（へ）この最適化ステップで最適化した最終個体群のパラメータを保存するパラメータ保存ステップと、（ト）このパラメータ保存ステップで保存したパラメータを前記した初期パラメータ生成ステップで生成したパラメータの代わりとして前記した各種データの照合を行うことで、前記した照合結果取得ステップと、前記した適応度算出ステップと、前記したパラメータ変更ステップおよび前記した最適化ステップを用いて前記したパラメータ保存ステップで保存する前記したパラメータを複数段階繰り返して更新し、前記したパラメータ保存ステップで保存する前記したパラメータを段階的に進化させる進化用繰り返しステップとを照合パラメータ最適化方法に具備させる。
【００１３】
更に、本発明では、各種データを照合する照合装置のコンピュータに、照合パラメータ最適化制御プログラムとして、（イ）前記した各種データを照合する際に使用するパラメータを生成する初期パラメータ生成処理と、（ロ）この初期パラメータ生成処理で生成したパラメータを適応することで照合結果を取得する照合結果取得処理と、（ハ）この照合結果取得処理により取得した照合結果を基に予め定められた評価関数を使用して適応度を算出する適応度算出処理と、（ニ）この適応度算出処理による適応度の算出が行われた後、この算出された適応度を基にして遺伝的アルゴリズムにより前記したパラメータを変更するパラメータ変更処理と、（ホ）このパラメータ変更処理で変更したパラメータについて前記した遺伝的アルゴリズムを最大世代数だけ世代交代を繰り返すことで最適化する最適化処理と、（へ）この最適化処理で最適化した最終個体群のパラメータを保存するパラメータ保存処理と、（ト）このパラメータ保存処理で保存したパラメータを前記した初期パラメータ生成処理で生成したパラメータの代わりとして前記した各種データの照合を行うことで、前記した照合結果取得処理と、前記した適応度算出処理と、前記したパラメータ変更処理および前記した最適化処理を用いて前記したパラメータ保存処理で保存する前記したパラメータを複数段階繰り返して更新し、前記したパラメータ保存処理で保存する前記したパラメータを段階的に進化させる進化用繰り返しステップ処理とを実行させることを特徴としている。
【発明の効果】
【００１４】
以上説明したように本発明によれば、指紋の照合等の各種データの照合に使用する各種のパラメータを遺伝的アルゴリズムの使用により最適化するので、人の経験に依存せずに照合装置に設定するパラメータを調節することができる。これにより、照合性能が介在する人によってばらつかないという利点がある。また、新たにパラメータが増えた場合にも、パラメータの調節に時間と手間が掛かることがない。
【００１５】
更に、本発明で多段階進化を行わせるようにすれば、パラメータについて初期収束を回避し、かつ探索領域を絞り込みながら効率的に最適解を求めることができる。
【発明を実施するための最良の形態】
【００１６】
次に本発明を一実施の形態と共に説明する。
【００１７】
図１は、本実施の形態における指紋照合パラメータ最適化装置の構成を表わしたものである。この指紋照合パラメータ最適化装置１００は、指紋データを外部から読み込む指紋ファイル読み込み装置１０１と、読み込んだ指紋データを照合に適したデータ形式に変換するトランザクションコントローラ１０２と、大量の指紋データを蓄積している指紋データベース１０３と、トランザクションコントローラ１０２によって変換された指紋データを指紋データベース１０３に登録されている指紋データと照合する指紋照合装置１０４と、学習アルゴリズムにより指紋照合装置１０４へ適用するパラメータを生成して、そのパラメータを最適化する学習アルゴリズム適用部１０５とによって構成されている。
【００１８】
ここで学習アルゴリズム適用部１０５は、指紋照合装置１０４で最適化するための初期パラメータ群を生成して、指紋ファイル読み込み装置１０１に対して指紋データの読み込みを指示するようになっている。指紋ファイル読み込み装置１０１は、この指示に従って、指紋データを読み込み、これをトランザクションコントローラ１０２へ送信する。トランザクションコントローラ１０２は、指紋データを照合に適したデータ形式に変換して、指紋照合装置１０４へ送信する。学習アルゴリズム適用部１０５は、生成したパラメータを指紋照合装置１０４での適用のために出力することになる。
【００１９】
指紋照合装置１０４は、トランザクションコントローラ１０２から受信した指紋データを、指紋データベース１０３の指紋データと照合し、照合結果を学習アルゴリズム適用部１０５へ送信する。学習アルゴリズム適用部１０５は、指紋照合装置１０４から受信した照合結果を基にして、予め決められた評価関数により適応度を算出する。その後、遺伝的操作である選択、交叉および突然変異を実施して、次の照合で指紋照合装置１０４へ適用するパラメータを生成する。
【００２０】
学習アルゴリズム適用部１０５は、世代交代回数が最大世代数未満の場合に、再び指紋ファイル読み込み装置１０１へ指紋データの読み込みを指示する。最大世代数分の世代交代が行われるまで、同様の処理が繰り返される。最大世代数分の世代交代が終了すると、学習アルゴリズム適用部１０５は、最終個体群のパラメータおよび適応度をファイルに保存するようにしている。
【００２１】
なお、本実施の形態の指紋照合パラメータ最適化装置１００は、図示しないがＣＰＵ（Central Processing Unit）と、このＣＰＵが実行する制御プログラムを格納したメモリを備えている。そして、ＣＰＵが制御プログラムを実行することによって指紋照合パラメータ最適化装置１００の全体的な制御を行う。また、ＣＰＵは指紋照合パラメータ最適化装置１００の少なくとも一部のデバイスをソフトウェア的に実現するようになっている。
【００２２】
ところで本実施の形態では、学習アルゴリズムとして遺伝的アルゴリズムを採用している。そこで遺伝的アルゴリズムについて概説する。遺伝子は生物の設計図である。この設計図は生物の長い歴史の中で自然によって徐々に編集されてきたものである。遺伝子という情報の流れに着目するならば、進化とは遺伝子の組み合わせの可能性の中で、その組み合わせを最適化するプロセスに他ならない。このことを現実問題の最適化手法として利用したのが遺伝的アルゴリズムである。遺伝的アルゴリズムは、記号で表現した遺伝子に対して選択、交叉および突然変異の操作を繰り返すことによって、問題に対する適応度が高い遺伝子の組み合わせを探索していく。
【００２３】
まず、遺伝における情報について説明する。ある生物個体は、染色体に記された遺伝情報に基づいて形作られる。染色体は、遺伝子が複数並んだ「遺伝子配列」として構成されており、個体を誕生させるときにそれが「解読」される。解読されて生成された個体のことを「表現型」と呼び、その元となる遺伝子のパターンを「遺伝子型」と呼ぶ。
【００２４】
遺伝的アルゴリズムで、個体は染色体を１つだけ持っていると想定する。遺伝子数ｎの個体は、次のような配列によって遺伝情報が記録されている。
Ａ1，Ａ2，Ａ3，……，Ａi，…，Ａn
【００２５】
ここで、「Ａ」はそれぞれ遺伝子を指していている。具体的には「１」や「０」あるいは実数値等の値を用いて遺伝子を表わしている。各遺伝子の位置を「遺伝子座」という。ある位置の遺伝子は、ある特有の性質を指定するようになっている。たとえば「Ａ2」が脚の長さに関する遺伝子であり、「０」が脚の長さが長いことを表わす値となっており、「１」が脚の長さが短いことを表わす値となっているとする。このとき、「０」と「１」が脚の長さについての対立遺伝子である。
【００２６】
以上説明した染色体から個々の遺伝情報を解読して表現することによって「個体」が誕生することになる。個体の集合のことを「個体群」という。各個体は、問題に対する適応度や他の個体との競争によって優劣が付けられる。その評価値を「適応度」という。
【００２７】
次に、遺伝的アルゴリズムの手順について説明する。
【００２８】
図２は、一般的な遺伝的アルゴリズムについての処理手順を示したものである。最適化問題を解きたい場合には、最適化したい問題を遺伝子で表現して、終了条件を設定しておく必要がある。
【００２９】
（１）初期集団の生成（ステップＳ２０１）：ランダムに染色体を生成して、初期個体を作る。
（２）評価（ステップＳ２０２）：それぞれの個体について、評価関数に従って適応度を計算する。
（３）選択（ステップＳ２０３）：適応度を基にして、親となる個体を選択する。
（４）交叉（ステップＳ２０４）：２人の親の染色体を交叉させ、新しい個体の染色体を構成する。
（５）突然変異（ステップＳ２０５）：新しい染色体の一部を突然変異率に従ってミスコピーする。
（６）再生（ステップＳ２０６）：個体群のすべてまたは一部を新しい個体で置き換える。
（７）繰り返し（終了判定）（ステップＳ２０７）：終了条件を満たすまで、ステップＳ２０２〜ステップ２０６を繰り返す。
以上のようなメカニズムで、適応度の高くなるような染色体を探索することになる。
【００３０】
次に、「選択」について更に詳しく説明する。
【００３１】
自然界の場合と同じように、遺伝的アルゴリズムでも適応度の高い個体ほど子供をより多く残すことができる。普通、１世代に生きている個体数は一定にしておく。この結果として、適応度が高いものは増殖するが、低いものは淘汰されていく。このように、適応度の大きさに従って親となる個体を決定する操作を「選択」という。選択のアルゴリズムには幾つか種類があるが、最も簡単で一般的なものに「ルーレット選択」がある。
【００３２】
「ルーレット選択」とは、適応度に比例した割合で個体を選択する方法である。それぞれの個体の適応度の大きさに比例した扇形に区切られたルーレットで、矢が刺さった場所を選択するのと同様に考えられたことから、この名前が付いた。
【００３３】
次に、「交叉」について更に詳しく説明する。
【００３４】
遺伝的アルゴリズムにおける交叉は、２つの染色体の一部を交換する操作のことである。これは自然界の２つの単一染色体における遺伝子の組み換えを模倣したものである。
【００３５】
交叉オペレータには、その置換方法の違いにより「一点交叉」、「多点交叉」、「一様交叉」の種類がある。ここで、オペレータとは、処理を行うプロセスをいう。
【００３６】
図３は一点交叉を説明するためのものである。親としての染色体Ａおよび染色体Ｂから子供としての染色体ａおよび染色体ｂができるものとする。一点交叉は、染色体Ａおよび染色体Ｂ上に１箇所だけ分離点１２１を決めて交叉を行うものである。
【００３７】
図４は、多点交叉の代表的なものとしての二点交叉を説明するためのものである。多点交叉は、複数の分離点で交叉するものである。親としての染色体Ａおよび染色体Ｂから子供としての染色体ａおよび染色体ｂができるものとする。一般には多点交叉のうちの二点交叉がよく使用される。二点交叉では、染色体Ａおよび染色体Ｂ上に２箇所の分離点１２２、１２３を決めて交叉を行うものである。三点以上の多点交叉では、分離点がそれに応じて増加することになる。
【００３８】
図５は、一様交叉を説明するためのものである。一様交叉は、任意数の交叉点によって交叉させる方法である。一様交叉ではこれを「０」および「１」からなるビット列のマスク（mask）を用いて実現する。具体的には、まず、マスク（mask）にランダムに「０」および「１」の文字列を発生させる。親としての染色体Ａおよび染色体Ｂから子供としての染色体ａおよび染色体ｂができるものとする。染色体ａの遺伝子は、対応するマスク（mask）が「０」のときは親としての染色体Ａから受け継ぐ。また、マスク（mask）が「１」のときは親としての染色体Ｂから受け継ぐ。逆に染色体ｂの遺伝子は対応するマスクが「０」のときは親としての染色体Ｂから受け継ぐ。また、マスク（mask）が「１」のときは親としての染色体Ａから受け継ぐ。
【００３９】
以上説明した「一点交叉」、「多点交叉」、「一様交叉」どの方法でも分離点の場所はランダムに決められる。交叉オペレータの探索能力は、次の（１）式に示す大小関係で効率がよい。
【００４０】
一点交叉 ＜ 多点交叉 ＜ 一様交叉 ……（１）
【００４１】
次に、「突然変異」について更に説明する。重要な遺伝的オペレータの１つである「突然変異」は、あるランダムに選ばれた遺伝子座の遺伝子を対立遺伝子に変えることである。
【００４２】
図６は、「突然変異」を説明するためのものである。「０」および「１」の組み合わせからなる親としての染色体Ａにおける※（米印）で示した箇所の遺伝子に突然変異が起きたとする。この場合、子としての染色体ａの※で示した箇所の遺伝子の「０」あるいは「１」が反転する。
【００４３】
最後に、「遺伝操作パラメータの経験則」について更に説明する。「集団数」については、５０〜１５０位が通常用いられる。あまり数が多いと計算量が多くなり時間が掛かってしまう。「交叉率」については大きい方がよい。一般に０．６〜０．９５の範囲が良い。「突然変異率」については、「遺伝子長」の逆数をとれば良い。これは世代ごとに各遺伝子につき平均１つの遺伝子座で変異が起こることを意味する。この値が小さいと初期収束を引き起こす可能性がある
【００４４】
図７は、本実施の形態の指紋照合パラメータ最適化装置が指紋照合用の最終個体群についてのパラメータを保存するまでの処理の流れを示したものである。図１と共に説明する。
【００４５】
最初に、学習アルゴリズム適用部１０５で、初期パラメータ群が生成される（ステップＳ２２１）。初期パラメータ群の生成に際して、指紋照合装置１０４は最適化するパラメータを抽出する。そして、これらを１つのビット列で表わした染色体をランダムに生成する。
【００４６】
図８は、最適化する３つのパラメータＡ、Ｂ、Ｃについてこれらの採り得る値の範囲と、構成ビット長としての遺伝子長の関係を表わしたものである。この例で、パラメータＡでは採り得る値の範囲が「０」から「３」であり、遺伝子長は２ビットとなっている。パラメータＢでは採り得る値の範囲が「０」から「７」であり、遺伝子長は３ビットとなっている。パラメータＣでは採り得る値の範囲が「０」から「１５」であり、遺伝子長は４ビットとなっている。
【００４７】
図９は、図８に示したパラメータＡ、Ｂ、Ｃを最適化する際に染色体をランダムに生成した様子を示したものである。この図に示すように染色体を遺伝子長に応じて区切って解読することで、染色体からパラメータＡ、Ｂ、Ｃに変換することができる。染色体は予め決められた個体数分生成する。ここでは６個体分が生成されている。
【００４８】
図１に示した学習アルゴリズム適用部１０５は、指紋ファイル読み込み装置１０１に対して指紋データの読み込みを指示する（図７ステップＳ２２２）。この指示によって、指紋ファイル読み込み装置１０１は、指紋データを読み込み、トランザクションコントローラ１０２へ送信する。トランザクションコントローラ１０２は、受信した指紋データを照合に適したデータ形式に変換し、指紋照合装置１０４へ送信する。
【００４９】
次に、学習アルゴリズム適用部１０５は、生成したパラメータを指紋照合装置１０４に適用する（ステップＳ２２３）。そして、照合結果を取得し（ステップＳ２２４）、予め決められた評価関数により適応度を算出する（ステップＳ２２５）。次に、以上の処理を世代を構成する個体数分だけ行ったかどうかを判断して（ステップＳ２２６）、そうでなければ（Ｎ）、ステップＳ２２２からステップＳ２２５までの一連の処理を世代を構成する個体数分だけ繰り返す。
【００５０】
このようにして全個体の適応度が算出されたら（ステップＳ２２６：Ｙ）、遺伝的操作である選択、交叉、突然変異が順に実施される（ステップＳ２２７〜ステップＳ２２９）。そして、世代交代数が、予め決められた最大世代数より多いか判断し（ステップＳ２３０）、世代交代数が最大世代数未満の場合は指紋データの読み込みを指示して（ステップＳ２２２）、それ以降の処理を繰り返し（ステップＳ２２３〜ステップＳ２２９）、パラメータ群を進化させる。このようにして最大世代数分の世代交代が終了後（ステップＳ２３０：Ｙ）、最終個体群のパラメータと適応度をファイルに保存して（ステップＳ２３１）、一連の処理を終了させる（エンド）。
【００５１】
以上説明したように本実施の形態によれば、図１に示した指紋照合装置１０４が必要とする複数のパラメータを人の経験に依存することなく自動的に最適化することができる。これは、学習の過程で学習アルゴリズムが指紋照合装置１０４の必要とする複数のパラメータを最適化できるからである。この結果、誰でも最適なパラメータを取得することが可能となり、更にパラメータ調節に掛かる手間と時間を軽減することが可能になる。
【００５２】
＜発明の変形例＞
【００５３】
図１０は、本発明の変形例の指紋照合パラメータ最適化装置が指紋照合用の最終個体群についてのパラメータを保存するまでの処理の流れを示したものである。この変形例の指紋照合パラメータ最適化装置では、第１段階進化ステップ（ステップＳ３０１）を経て、第１の最終個体群のパラメータを保存している（ステップＳ３０２）。ここで、第１段階進化ステップ（ステップＳ３０１）は、図７に示したステップＳ２２１〜ステップＳ２３０の処理と同じである。したがって、第１段階進化ステップ（ステップＳ３０１）では、図７に示したステップＳ２２１に対応する処理では初期パラメータ群がランダムに生成されて、それ以後、図７で説明したステップＳ２２２以降の処理が行われる。この結果、ステップＳ２３０で世代交代数が、予め決められた最大世代数より多いと判断された場合に（Ｙ）、ステップＳ３０２の処理に進むことになる。
【００５４】
第２段階進化ステップ（ステップＳ３０３）は、第１段階進化ステップ（ステップＳ３０１）と同様に図７に示したステップＳ２２１〜ステップＳ２３０の処理で構成されている。第２段階進化ステップ（ステップＳ３０３）では、ステップＳ３０２で得られた第１の最終個体群のパラメータを、第２段階進化ステップ（ステップＳ３０３）における初期パラメータ群として使用し（図７ステップＳ２２１参照）、第２段階の進化を開始する。この結果、ステップＳ３０３における、図７のステップＳ２３０に対応する処理で、世代交代数が予め決められた最大世代数より多いと判断された場合に（Ｙ）、ステップＳ３０４の処理として、第２の最終個体群のパラメータが保存されることになる。
【００５５】
このように、この変形例では第１段階進化ステップ（ステップＳ３０１）では初期パラメータ群をランダムに生成するが、第２段階進化ステップ（ステップＳ３０３）では第１段階進化で得られた第１の最終個体群のパラメータ（ステップＳ３０２）を初期パラメータ群として採用する。
【００５６】
ステップＳ３０１およびステップＳ３０２からなる第１段階進化の過程では、比較的緩やかな照合条件でパラメータを進化させる。これに対して、ステップＳ３０３およびステップＳ３０４からなる第２段階進化の過程では、ステップＳ３０２でで得られた最終個体群のパラメータと適応度を考慮してパラメータの探索領域を絞り込み、ステップＳ３０１で行われた進化よりも厳しい照合条件で更にパラメータを進化させることになる。
【００５７】
このように、変形例では進化の過程を、ステップＳ３０１、ステップＳ３０３の２段階に分けている。これを３段階以上に分けるようにしてもよい。一般に進化の過程を２段階以上の多段階に分ける利点は、次のように説明することができる。
【００５８】
まず、第１番目の利点は、探索領域を絞り込むことができることである。たとえば、あるパラメータの取り得る値の範囲が１〜１００であったとする。第１段階進化ステップ（ステップＳ３０１）の結果、適応度の高い個体のパラメータを調べたところ、パラメータの値が５０、７０、８０のときに圧倒的に適応度が高かったとする。このとき、指紋照合装置１０４へ適用すべき値として何が最適か不明瞭である。そこで、更に最適値を絞り込むために、あるパラメータの探索領域を５０〜８０として第２段階進化ステップ（ステップＳ３０３）を実施するのである。このような多段階進化を繰り返すことで、探索領域を絞り込まない場合に比べて効率的にパラメータを進化させることが可能になる。
【００５９】
進化の過程を多段階に分ける第２番目の利点は、たまたま適応度が高かった個体が強調されることにより、進化の比較的早い世代で局所的な値に収束する初期収束を回避することができることである。第１段階進化ステップ（ステップＳ３０１）では比較的緩やかな条件で進化させて、第２段階進化ステップ（ステップＳ３０３）以降の段階で徐々に条件を厳しくすることで、初期収束を回避することが可能になる。
【００６０】
以上説明したように、変形例のように多段階進化を適用することで、初期収束を回避し、かつ探索領域を絞り込みながら効率的にパラメータを進化させることができるようになる。
【００６１】
なお、本発明の実施の形態では、指紋データを扱う指紋照合パラメータ最適化装置について説明を行ったが、指紋データ以外を扱うその他の照合装置用の照合パラメータ最適化装置に本発明を適用できることは当然である。
【図面の簡単な説明】
【００６２】
【図１】本実施の形態における指紋照合パラメータ最適化装置の構成を表わしたブロック図である。
【図２】一般的な遺伝的アルゴリズムについての処理手順を示した流れ図である。
【図３】一点交叉の説明図である。
【図４】多点交叉の代表的なものとしての二点交叉の説明図である。
【図５】一様交叉の説明図である。
【図６】突然変異の説明図である。
【図７】本実施の形態で指紋照合用の最終個体群についてのパラメータを保存するまでの処理を示した流れ図である。
【図８】本実施の形態で最適化する３つのパラメータＡ、Ｂ、Ｃの採り得る値の範囲と遺伝子長の関係を表わした説明図である。
【図９】図８に示したパラメータＡ、Ｂ、Ｃを最適化する際に染色体をランダムに生成した様子を示した説明図である。
【図１０】本発明の変形例の指紋照合パラメータ最適化装置が指紋照合用の最終個体群についてのパラメータを保存するまでの流れ図である。
【符号の説明】
【００６３】
１００ 指紋照合パラメータ最適化装置
１０１ 指紋ファイル読み込み装置
１０２ トランザクションコントローラ
１０３ 指紋データベース
１０４ 指紋照合装置
１０５ 学習アルゴリズム適用部
１２１〜１２３ 分離点
Ｓ２０１ 初期集団の生成
Ｓ２０２ 評価
Ｓ２０３ 選択
Ｓ２０４ 交叉
Ｓ２０５ 突然変異
Ｓ２０６ 再生
Ｓ２０７ 繰り返し（終了判定）
Ｓ３０１ 第１段階進化ステップ
Ｓ３０３ 第２段階進化ステップ
【技術分野】
【０００１】
本発明は、指紋照合パラメータ最適化装置のようにデータ照合用のパラメータを調節して最適な状態を作り出す装置に有効な照合パラメータ最適化装置、最適化方法および最適化制御プログラムに係わり、特に経験を積んだ有識者が手動でパラメータの設定を行うような装置の自動化に好適な照合パラメータ最適化装置、最適化方法および最適化制御プログラムに関する。
【背景技術】
【０００２】
たとえば指紋の照合を行うための指紋照合システムでは、多くの調節すべきパラメータが存在する。従来は、これらのパラメータを経験を積んだ特定の人が調節することで指紋照合システムのパフォーマンスを発揮してきた。
【０００３】
このような指紋照合システムでは、誰でもパラメータを調節できるようなシステム構成になっていない。このため、経験を積んだ人でなければパラメータを調節することができない。また、新たにパラメータが増えた場合、経験を積まなければ最適な値が分からないため、調節に時間と手間が掛かるという問題がある。
【０００４】
そこで、本発明の第１の関連技術として、電子回路パッケージの調整について遺伝的アルゴリズム（ＧＡ）とニューラルネットワークを適用することが提案されている（たとえば特許文献１参照）。この第１の関連技術で制御部は、機構部を制御して電子回路パッケージの調整用トリマの位置を指定した初期設定条件の状態に調整した後、測定部から電子回路パッケージに規定の入力信号を供給し、出力値を測定してその初期設定条件に対する出力値Ｘｓとして記憶する。そして、前記したすべての遺伝子をランダムに初期化したステップで設定したα個の遺伝子の１個を選択し、その遺伝子にコーディングされた回転量情報に基づいて各調整用トリマの回転を行った後、電子回路パッケージからの出力値を再び測定し記憶する。以上の前記した初期設定条件の状態に調整するステップから前記した電子回路パッケージからの出力値を再び測定し記憶するステップまでの処理を設定したα個のすべての遺伝子に対して実行した後、前記した記憶した出力値を調整目標の基準出力値Ｘｏと比較して適応度を算出するようにしている。
【０００５】
また、本発明の第２の関連技術として、指紋の照合に際して、指紋の特徴点をアルゴリズムで抽出して指紋の照合を行うことが提案されている（たとえば特許文献２参照）。この第２の関連技術では、指紋が入力されると、指紋画像から指紋の特徴点が抽出されて指紋情報が生成される。この指紋情報は、予め登録されている登録指紋情報ファイル中の指紋情報と照合される。そして、照合に成功した場合にはその指紋情報に対応する個人名が送られる。
【特許文献１】特開平０８−０１６２０７号公報（第００２３段落〜第００２５段落、図２）
【特許文献２】特開２００７−０５８６４９号公報（第００５３段落、図４）
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところで、学習アルゴリズムには、ニューラルネットワークや遺伝的アルゴリズムなどがある。ニューラルネットワークは教師付き学習といって、模範となる教師の存在を必要とする。本発明の第１の関連技術では、ニューラルネットワークを遺伝的アルゴリズムと併用している。このため、自ら環境に適するように学習するには不適当である。
【０００７】
次に本発明の第２の関連技術では、指紋の特徴点自体をアルゴリズムで抽出するようにしている。指紋の特徴点を抽出した後は、予め登録されている登録指紋情報ファイル中の指紋情報との照合が行われる。指紋情報が登録指紋情報ファイルに登録されているものであるとの照合結果を得た場合、すなわち、照合に成功した場合には、照合に成功した指紋情報に対応する個人名が送られる。
【０００８】
この照合を行う過程について、第２の関連技術で、パラメータの調整を行う配慮は行われていない。すなわち、第２の関連技術では、遺伝的アルゴリズムを指紋の特徴点の抽出に用いるだけであって、それ以上の工夫は行っていない。
【０００９】
そこで本発明の目的は、自ら環境に適するように学習することができ、これによって経験を積んだ人に頼ることなく各種の照合用のパラメータを最適化することのできる照合パラメータ最適化装置、最適化方法および最適化制御プログラムを提供することにある。
【００１０】
本発明の他の目的は、各種の照合用のパラメータについて、効率的に最適解を求めることのできる照合パラメータ最適化装置、最適化方法および最適化制御プログラムを提供することにある。
【課題を解決するための手段】
【００１１】
本発明では、（イ）各種データを照合するためのパラメータを生成する初期パラメータ生成手段と、（ロ）前記した各種データの照合を行う照合装置に前記したパラメータを適応することで照合結果を取得する照合結果取得手段と、（ハ）この照合結果取得手段により取得した照合結果を基に予め定められた評価関数を使用して適応度を算出する適応度算出手段と、（ニ）この適応度算出手段による適応度の算出が行われた後、この算出された適応度を基にして遺伝的アルゴリズムにより前記したパラメータを変更するパラメータ変更手段と、（ホ）このパラメータ変更手段で変更したパラメータについて前記した遺伝的アルゴリズムを最大世代数だけ世代交代を繰り返すことで最適化する最適化手段とを照合パラメータ最適化装置に具備させる。
【００１２】
また、本発明では、（イ）各種データを照合するためのパラメータを生成する初期パラメータ生成ステップと、（ロ）前記した各種データの照合を行う照合装置に前記したパラメータを適応することで照合結果を取得する照合結果取得ステップと、（ハ）この照合結果取得ステップにより取得した照合結果を基に予め定められた評価関数を使用して適応度を算出する適応度算出ステップと、（ニ）この適応度算出ステップによる適応度の算出が行われた後、この算出された適応度を基にして遺伝的アルゴリズムにより前記したパラメータを変更するパラメータ変更ステップと、（ホ）このパラメータ変更ステップで変更したパラメータについて前記した遺伝的アルゴリズムを最大世代数だけ世代交代を繰り返すことで最適化する最適化ステップと、（へ）この最適化ステップで最適化した最終個体群のパラメータを保存するパラメータ保存ステップと、（ト）このパラメータ保存ステップで保存したパラメータを前記した初期パラメータ生成ステップで生成したパラメータの代わりとして前記した各種データの照合を行うことで、前記した照合結果取得ステップと、前記した適応度算出ステップと、前記したパラメータ変更ステップおよび前記した最適化ステップを用いて前記したパラメータ保存ステップで保存する前記したパラメータを複数段階繰り返して更新し、前記したパラメータ保存ステップで保存する前記したパラメータを段階的に進化させる進化用繰り返しステップとを照合パラメータ最適化方法に具備させる。
【００１３】
更に、本発明では、各種データを照合する照合装置のコンピュータに、照合パラメータ最適化制御プログラムとして、（イ）前記した各種データを照合する際に使用するパラメータを生成する初期パラメータ生成処理と、（ロ）この初期パラメータ生成処理で生成したパラメータを適応することで照合結果を取得する照合結果取得処理と、（ハ）この照合結果取得処理により取得した照合結果を基に予め定められた評価関数を使用して適応度を算出する適応度算出処理と、（ニ）この適応度算出処理による適応度の算出が行われた後、この算出された適応度を基にして遺伝的アルゴリズムにより前記したパラメータを変更するパラメータ変更処理と、（ホ）このパラメータ変更処理で変更したパラメータについて前記した遺伝的アルゴリズムを最大世代数だけ世代交代を繰り返すことで最適化する最適化処理と、（へ）この最適化処理で最適化した最終個体群のパラメータを保存するパラメータ保存処理と、（ト）このパラメータ保存処理で保存したパラメータを前記した初期パラメータ生成処理で生成したパラメータの代わりとして前記した各種データの照合を行うことで、前記した照合結果取得処理と、前記した適応度算出処理と、前記したパラメータ変更処理および前記した最適化処理を用いて前記したパラメータ保存処理で保存する前記したパラメータを複数段階繰り返して更新し、前記したパラメータ保存処理で保存する前記したパラメータを段階的に進化させる進化用繰り返しステップ処理とを実行させることを特徴としている。
【発明の効果】
【００１４】
以上説明したように本発明によれば、指紋の照合等の各種データの照合に使用する各種のパラメータを遺伝的アルゴリズムの使用により最適化するので、人の経験に依存せずに照合装置に設定するパラメータを調節することができる。これにより、照合性能が介在する人によってばらつかないという利点がある。また、新たにパラメータが増えた場合にも、パラメータの調節に時間と手間が掛かることがない。
【００１５】
更に、本発明で多段階進化を行わせるようにすれば、パラメータについて初期収束を回避し、かつ探索領域を絞り込みながら効率的に最適解を求めることができる。
【発明を実施するための最良の形態】
【００１６】
次に本発明を一実施の形態と共に説明する。
【００１７】
図１は、本実施の形態における指紋照合パラメータ最適化装置の構成を表わしたものである。この指紋照合パラメータ最適化装置１００は、指紋データを外部から読み込む指紋ファイル読み込み装置１０１と、読み込んだ指紋データを照合に適したデータ形式に変換するトランザクションコントローラ１０２と、大量の指紋データを蓄積している指紋データベース１０３と、トランザクションコントローラ１０２によって変換された指紋データを指紋データベース１０３に登録されている指紋データと照合する指紋照合装置１０４と、学習アルゴリズムにより指紋照合装置１０４へ適用するパラメータを生成して、そのパラメータを最適化する学習アルゴリズム適用部１０５とによって構成されている。
【００１８】
ここで学習アルゴリズム適用部１０５は、指紋照合装置１０４で最適化するための初期パラメータ群を生成して、指紋ファイル読み込み装置１０１に対して指紋データの読み込みを指示するようになっている。指紋ファイル読み込み装置１０１は、この指示に従って、指紋データを読み込み、これをトランザクションコントローラ１０２へ送信する。トランザクションコントローラ１０２は、指紋データを照合に適したデータ形式に変換して、指紋照合装置１０４へ送信する。学習アルゴリズム適用部１０５は、生成したパラメータを指紋照合装置１０４での適用のために出力することになる。
【００１９】
指紋照合装置１０４は、トランザクションコントローラ１０２から受信した指紋データを、指紋データベース１０３の指紋データと照合し、照合結果を学習アルゴリズム適用部１０５へ送信する。学習アルゴリズム適用部１０５は、指紋照合装置１０４から受信した照合結果を基にして、予め決められた評価関数により適応度を算出する。その後、遺伝的操作である選択、交叉および突然変異を実施して、次の照合で指紋照合装置１０４へ適用するパラメータを生成する。
【００２０】
学習アルゴリズム適用部１０５は、世代交代回数が最大世代数未満の場合に、再び指紋ファイル読み込み装置１０１へ指紋データの読み込みを指示する。最大世代数分の世代交代が行われるまで、同様の処理が繰り返される。最大世代数分の世代交代が終了すると、学習アルゴリズム適用部１０５は、最終個体群のパラメータおよび適応度をファイルに保存するようにしている。
【００２１】
なお、本実施の形態の指紋照合パラメータ最適化装置１００は、図示しないがＣＰＵ（Central Processing Unit）と、このＣＰＵが実行する制御プログラムを格納したメモリを備えている。そして、ＣＰＵが制御プログラムを実行することによって指紋照合パラメータ最適化装置１００の全体的な制御を行う。また、ＣＰＵは指紋照合パラメータ最適化装置１００の少なくとも一部のデバイスをソフトウェア的に実現するようになっている。
【００２２】
ところで本実施の形態では、学習アルゴリズムとして遺伝的アルゴリズムを採用している。そこで遺伝的アルゴリズムについて概説する。遺伝子は生物の設計図である。この設計図は生物の長い歴史の中で自然によって徐々に編集されてきたものである。遺伝子という情報の流れに着目するならば、進化とは遺伝子の組み合わせの可能性の中で、その組み合わせを最適化するプロセスに他ならない。このことを現実問題の最適化手法として利用したのが遺伝的アルゴリズムである。遺伝的アルゴリズムは、記号で表現した遺伝子に対して選択、交叉および突然変異の操作を繰り返すことによって、問題に対する適応度が高い遺伝子の組み合わせを探索していく。
【００２３】
まず、遺伝における情報について説明する。ある生物個体は、染色体に記された遺伝情報に基づいて形作られる。染色体は、遺伝子が複数並んだ「遺伝子配列」として構成されており、個体を誕生させるときにそれが「解読」される。解読されて生成された個体のことを「表現型」と呼び、その元となる遺伝子のパターンを「遺伝子型」と呼ぶ。
【００２４】
遺伝的アルゴリズムで、個体は染色体を１つだけ持っていると想定する。遺伝子数ｎの個体は、次のような配列によって遺伝情報が記録されている。
Ａ1，Ａ2，Ａ3，……，Ａi，…，Ａn
【００２５】
ここで、「Ａ」はそれぞれ遺伝子を指していている。具体的には「１」や「０」あるいは実数値等の値を用いて遺伝子を表わしている。各遺伝子の位置を「遺伝子座」という。ある位置の遺伝子は、ある特有の性質を指定するようになっている。たとえば「Ａ2」が脚の長さに関する遺伝子であり、「０」が脚の長さが長いことを表わす値となっており、「１」が脚の長さが短いことを表わす値となっているとする。このとき、「０」と「１」が脚の長さについての対立遺伝子である。
【００２６】
以上説明した染色体から個々の遺伝情報を解読して表現することによって「個体」が誕生することになる。個体の集合のことを「個体群」という。各個体は、問題に対する適応度や他の個体との競争によって優劣が付けられる。その評価値を「適応度」という。
【００２７】
次に、遺伝的アルゴリズムの手順について説明する。
【００２８】
図２は、一般的な遺伝的アルゴリズムについての処理手順を示したものである。最適化問題を解きたい場合には、最適化したい問題を遺伝子で表現して、終了条件を設定しておく必要がある。
【００２９】
（１）初期集団の生成（ステップＳ２０１）：ランダムに染色体を生成して、初期個体を作る。
（２）評価（ステップＳ２０２）：それぞれの個体について、評価関数に従って適応度を計算する。
（３）選択（ステップＳ２０３）：適応度を基にして、親となる個体を選択する。
（４）交叉（ステップＳ２０４）：２人の親の染色体を交叉させ、新しい個体の染色体を構成する。
（５）突然変異（ステップＳ２０５）：新しい染色体の一部を突然変異率に従ってミスコピーする。
（６）再生（ステップＳ２０６）：個体群のすべてまたは一部を新しい個体で置き換える。
（７）繰り返し（終了判定）（ステップＳ２０７）：終了条件を満たすまで、ステップＳ２０２〜ステップ２０６を繰り返す。
以上のようなメカニズムで、適応度の高くなるような染色体を探索することになる。
【００３０】
次に、「選択」について更に詳しく説明する。
【００３１】
自然界の場合と同じように、遺伝的アルゴリズムでも適応度の高い個体ほど子供をより多く残すことができる。普通、１世代に生きている個体数は一定にしておく。この結果として、適応度が高いものは増殖するが、低いものは淘汰されていく。このように、適応度の大きさに従って親となる個体を決定する操作を「選択」という。選択のアルゴリズムには幾つか種類があるが、最も簡単で一般的なものに「ルーレット選択」がある。
【００３２】
「ルーレット選択」とは、適応度に比例した割合で個体を選択する方法である。それぞれの個体の適応度の大きさに比例した扇形に区切られたルーレットで、矢が刺さった場所を選択するのと同様に考えられたことから、この名前が付いた。
【００３３】
次に、「交叉」について更に詳しく説明する。
【００３４】
遺伝的アルゴリズムにおける交叉は、２つの染色体の一部を交換する操作のことである。これは自然界の２つの単一染色体における遺伝子の組み換えを模倣したものである。
【００３５】
交叉オペレータには、その置換方法の違いにより「一点交叉」、「多点交叉」、「一様交叉」の種類がある。ここで、オペレータとは、処理を行うプロセスをいう。
【００３６】
図３は一点交叉を説明するためのものである。親としての染色体Ａおよび染色体Ｂから子供としての染色体ａおよび染色体ｂができるものとする。一点交叉は、染色体Ａおよび染色体Ｂ上に１箇所だけ分離点１２１を決めて交叉を行うものである。
【００３７】
図４は、多点交叉の代表的なものとしての二点交叉を説明するためのものである。多点交叉は、複数の分離点で交叉するものである。親としての染色体Ａおよび染色体Ｂから子供としての染色体ａおよび染色体ｂができるものとする。一般には多点交叉のうちの二点交叉がよく使用される。二点交叉では、染色体Ａおよび染色体Ｂ上に２箇所の分離点１２２、１２３を決めて交叉を行うものである。三点以上の多点交叉では、分離点がそれに応じて増加することになる。
【００３８】
図５は、一様交叉を説明するためのものである。一様交叉は、任意数の交叉点によって交叉させる方法である。一様交叉ではこれを「０」および「１」からなるビット列のマスク（mask）を用いて実現する。具体的には、まず、マスク（mask）にランダムに「０」および「１」の文字列を発生させる。親としての染色体Ａおよび染色体Ｂから子供としての染色体ａおよび染色体ｂができるものとする。染色体ａの遺伝子は、対応するマスク（mask）が「０」のときは親としての染色体Ａから受け継ぐ。また、マスク（mask）が「１」のときは親としての染色体Ｂから受け継ぐ。逆に染色体ｂの遺伝子は対応するマスクが「０」のときは親としての染色体Ｂから受け継ぐ。また、マスク（mask）が「１」のときは親としての染色体Ａから受け継ぐ。
【００３９】
以上説明した「一点交叉」、「多点交叉」、「一様交叉」どの方法でも分離点の場所はランダムに決められる。交叉オペレータの探索能力は、次の（１）式に示す大小関係で効率がよい。
【００４０】
一点交叉 ＜ 多点交叉 ＜ 一様交叉 ……（１）
【００４１】
次に、「突然変異」について更に説明する。重要な遺伝的オペレータの１つである「突然変異」は、あるランダムに選ばれた遺伝子座の遺伝子を対立遺伝子に変えることである。
【００４２】
図６は、「突然変異」を説明するためのものである。「０」および「１」の組み合わせからなる親としての染色体Ａにおける※（米印）で示した箇所の遺伝子に突然変異が起きたとする。この場合、子としての染色体ａの※で示した箇所の遺伝子の「０」あるいは「１」が反転する。
【００４３】
最後に、「遺伝操作パラメータの経験則」について更に説明する。「集団数」については、５０〜１５０位が通常用いられる。あまり数が多いと計算量が多くなり時間が掛かってしまう。「交叉率」については大きい方がよい。一般に０．６〜０．９５の範囲が良い。「突然変異率」については、「遺伝子長」の逆数をとれば良い。これは世代ごとに各遺伝子につき平均１つの遺伝子座で変異が起こることを意味する。この値が小さいと初期収束を引き起こす可能性がある
【００４４】
図７は、本実施の形態の指紋照合パラメータ最適化装置が指紋照合用の最終個体群についてのパラメータを保存するまでの処理の流れを示したものである。図１と共に説明する。
【００４５】
最初に、学習アルゴリズム適用部１０５で、初期パラメータ群が生成される（ステップＳ２２１）。初期パラメータ群の生成に際して、指紋照合装置１０４は最適化するパラメータを抽出する。そして、これらを１つのビット列で表わした染色体をランダムに生成する。
【００４６】
図８は、最適化する３つのパラメータＡ、Ｂ、Ｃについてこれらの採り得る値の範囲と、構成ビット長としての遺伝子長の関係を表わしたものである。この例で、パラメータＡでは採り得る値の範囲が「０」から「３」であり、遺伝子長は２ビットとなっている。パラメータＢでは採り得る値の範囲が「０」から「７」であり、遺伝子長は３ビットとなっている。パラメータＣでは採り得る値の範囲が「０」から「１５」であり、遺伝子長は４ビットとなっている。
【００４７】
図９は、図８に示したパラメータＡ、Ｂ、Ｃを最適化する際に染色体をランダムに生成した様子を示したものである。この図に示すように染色体を遺伝子長に応じて区切って解読することで、染色体からパラメータＡ、Ｂ、Ｃに変換することができる。染色体は予め決められた個体数分生成する。ここでは６個体分が生成されている。
【００４８】
図１に示した学習アルゴリズム適用部１０５は、指紋ファイル読み込み装置１０１に対して指紋データの読み込みを指示する（図７ステップＳ２２２）。この指示によって、指紋ファイル読み込み装置１０１は、指紋データを読み込み、トランザクションコントローラ１０２へ送信する。トランザクションコントローラ１０２は、受信した指紋データを照合に適したデータ形式に変換し、指紋照合装置１０４へ送信する。
【００４９】
次に、学習アルゴリズム適用部１０５は、生成したパラメータを指紋照合装置１０４に適用する（ステップＳ２２３）。そして、照合結果を取得し（ステップＳ２２４）、予め決められた評価関数により適応度を算出する（ステップＳ２２５）。次に、以上の処理を世代を構成する個体数分だけ行ったかどうかを判断して（ステップＳ２２６）、そうでなければ（Ｎ）、ステップＳ２２２からステップＳ２２５までの一連の処理を世代を構成する個体数分だけ繰り返す。
【００５０】
このようにして全個体の適応度が算出されたら（ステップＳ２２６：Ｙ）、遺伝的操作である選択、交叉、突然変異が順に実施される（ステップＳ２２７〜ステップＳ２２９）。そして、世代交代数が、予め決められた最大世代数より多いか判断し（ステップＳ２３０）、世代交代数が最大世代数未満の場合は指紋データの読み込みを指示して（ステップＳ２２２）、それ以降の処理を繰り返し（ステップＳ２２３〜ステップＳ２２９）、パラメータ群を進化させる。このようにして最大世代数分の世代交代が終了後（ステップＳ２３０：Ｙ）、最終個体群のパラメータと適応度をファイルに保存して（ステップＳ２３１）、一連の処理を終了させる（エンド）。
【００５１】
以上説明したように本実施の形態によれば、図１に示した指紋照合装置１０４が必要とする複数のパラメータを人の経験に依存することなく自動的に最適化することができる。これは、学習の過程で学習アルゴリズムが指紋照合装置１０４の必要とする複数のパラメータを最適化できるからである。この結果、誰でも最適なパラメータを取得することが可能となり、更にパラメータ調節に掛かる手間と時間を軽減することが可能になる。
【００５２】
＜発明の変形例＞
【００５３】
図１０は、本発明の変形例の指紋照合パラメータ最適化装置が指紋照合用の最終個体群についてのパラメータを保存するまでの処理の流れを示したものである。この変形例の指紋照合パラメータ最適化装置では、第１段階進化ステップ（ステップＳ３０１）を経て、第１の最終個体群のパラメータを保存している（ステップＳ３０２）。ここで、第１段階進化ステップ（ステップＳ３０１）は、図７に示したステップＳ２２１〜ステップＳ２３０の処理と同じである。したがって、第１段階進化ステップ（ステップＳ３０１）では、図７に示したステップＳ２２１に対応する処理では初期パラメータ群がランダムに生成されて、それ以後、図７で説明したステップＳ２２２以降の処理が行われる。この結果、ステップＳ２３０で世代交代数が、予め決められた最大世代数より多いと判断された場合に（Ｙ）、ステップＳ３０２の処理に進むことになる。
【００５４】
第２段階進化ステップ（ステップＳ３０３）は、第１段階進化ステップ（ステップＳ３０１）と同様に図７に示したステップＳ２２１〜ステップＳ２３０の処理で構成されている。第２段階進化ステップ（ステップＳ３０３）では、ステップＳ３０２で得られた第１の最終個体群のパラメータを、第２段階進化ステップ（ステップＳ３０３）における初期パラメータ群として使用し（図７ステップＳ２２１参照）、第２段階の進化を開始する。この結果、ステップＳ３０３における、図７のステップＳ２３０に対応する処理で、世代交代数が予め決められた最大世代数より多いと判断された場合に（Ｙ）、ステップＳ３０４の処理として、第２の最終個体群のパラメータが保存されることになる。
【００５５】
このように、この変形例では第１段階進化ステップ（ステップＳ３０１）では初期パラメータ群をランダムに生成するが、第２段階進化ステップ（ステップＳ３０３）では第１段階進化で得られた第１の最終個体群のパラメータ（ステップＳ３０２）を初期パラメータ群として採用する。
【００５６】
ステップＳ３０１およびステップＳ３０２からなる第１段階進化の過程では、比較的緩やかな照合条件でパラメータを進化させる。これに対して、ステップＳ３０３およびステップＳ３０４からなる第２段階進化の過程では、ステップＳ３０２でで得られた最終個体群のパラメータと適応度を考慮してパラメータの探索領域を絞り込み、ステップＳ３０１で行われた進化よりも厳しい照合条件で更にパラメータを進化させることになる。
【００５７】
このように、変形例では進化の過程を、ステップＳ３０１、ステップＳ３０３の２段階に分けている。これを３段階以上に分けるようにしてもよい。一般に進化の過程を２段階以上の多段階に分ける利点は、次のように説明することができる。
【００５８】
まず、第１番目の利点は、探索領域を絞り込むことができることである。たとえば、あるパラメータの取り得る値の範囲が１〜１００であったとする。第１段階進化ステップ（ステップＳ３０１）の結果、適応度の高い個体のパラメータを調べたところ、パラメータの値が５０、７０、８０のときに圧倒的に適応度が高かったとする。このとき、指紋照合装置１０４へ適用すべき値として何が最適か不明瞭である。そこで、更に最適値を絞り込むために、あるパラメータの探索領域を５０〜８０として第２段階進化ステップ（ステップＳ３０３）を実施するのである。このような多段階進化を繰り返すことで、探索領域を絞り込まない場合に比べて効率的にパラメータを進化させることが可能になる。
【００５９】
進化の過程を多段階に分ける第２番目の利点は、たまたま適応度が高かった個体が強調されることにより、進化の比較的早い世代で局所的な値に収束する初期収束を回避することができることである。第１段階進化ステップ（ステップＳ３０１）では比較的緩やかな条件で進化させて、第２段階進化ステップ（ステップＳ３０３）以降の段階で徐々に条件を厳しくすることで、初期収束を回避することが可能になる。
【００６０】
以上説明したように、変形例のように多段階進化を適用することで、初期収束を回避し、かつ探索領域を絞り込みながら効率的にパラメータを進化させることができるようになる。
【００６１】
なお、本発明の実施の形態では、指紋データを扱う指紋照合パラメータ最適化装置について説明を行ったが、指紋データ以外を扱うその他の照合装置用の照合パラメータ最適化装置に本発明を適用できることは当然である。
【図面の簡単な説明】
【００６２】
【図１】本実施の形態における指紋照合パラメータ最適化装置の構成を表わしたブロック図である。
【図２】一般的な遺伝的アルゴリズムについての処理手順を示した流れ図である。
【図３】一点交叉の説明図である。
【図４】多点交叉の代表的なものとしての二点交叉の説明図である。
【図５】一様交叉の説明図である。
【図６】突然変異の説明図である。
【図７】本実施の形態で指紋照合用の最終個体群についてのパラメータを保存するまでの処理を示した流れ図である。
【図８】本実施の形態で最適化する３つのパラメータＡ、Ｂ、Ｃの採り得る値の範囲と遺伝子長の関係を表わした説明図である。
【図９】図８に示したパラメータＡ、Ｂ、Ｃを最適化する際に染色体をランダムに生成した様子を示した説明図である。
【図１０】本発明の変形例の指紋照合パラメータ最適化装置が指紋照合用の最終個体群についてのパラメータを保存するまでの流れ図である。
【符号の説明】
【００６３】
１００ 指紋照合パラメータ最適化装置
１０１ 指紋ファイル読み込み装置
１０２ トランザクションコントローラ
１０３ 指紋データベース
１０４ 指紋照合装置
１０５ 学習アルゴリズム適用部
１２１〜１２３ 分離点
Ｓ２０１ 初期集団の生成
Ｓ２０２ 評価
Ｓ２０３ 選択
Ｓ２０４ 交叉
Ｓ２０５ 突然変異
Ｓ２０６ 再生
Ｓ２０７ 繰り返し（終了判定）
Ｓ３０１ 第１段階進化ステップ
Ｓ３０３ 第２段階進化ステップ
【特許請求の範囲】
【請求項１】
各種データを照合するためのパラメータを生成する初期パラメータ生成手段と、
前記各種データの照合を行う照合装置に前記パラメータを適応することで照合結果を取得する照合結果取得手段と、
この照合結果取得手段により取得した照合結果を基に予め定められた評価関数を使用して適応度を算出する適応度算出手段と、
この適応度算出手段による適応度の算出が行われた後、この算出された適応度を基にして遺伝的アルゴリズムにより前記パラメータを変更するパラメータ変更手段と、
このパラメータ変更手段で変更したパラメータについて前記遺伝的アルゴリズムを最大世代数だけ世代交代を繰り返すことで最適化する最適化手段
とを具備することを特徴とする照合パラメータ最適化装置。
【請求項２】
前記最適化手段で最適化した最終個体群のパラメータを保存するパラメータ保存手段を具備することを特徴とする請求項１記載の照合パラメータ最適化装置。
【請求項３】
前記各種データは指紋データであり、前記遺伝的アルゴリズムは、遺伝的操作である選択、交差および突然変異のいずれかを少なくとも含んで構成されることを特徴とする請求項１記載の照合パラメータ最適化装置。
【請求項４】
前記パラメータ保存手段に保存したパラメータを前記初期パラメータ生成手段の生成したパラメータの代わりとして前記各種データの照合を行うことで、前記照合結果取得手段と、前記適応度算出手段と、前記パラメータ変更手段および前記最適化手段を用いて前記パラメータ保存手段に保存する前記パラメータを複数段階繰り返して更新し、前記パラメータ保存手段に保存する前記パラメータを段階的に進化させる進化用繰り返し手段を具備することを特徴とする請求項２記載の照合パラメータ最適化装置。
【請求項５】
前記進化用繰り返し手段の多段階の進化における初期段階の進化は、比較的緩やかな照合条件でパラメータを進化させるものであり、それ以後の段階の進化でパラメータの探索領域が絞り込まれた形でパラメータが進化することを特徴とする請求項４記載の照合パラメータ最適化装置。
【請求項６】
各種データを照合するためのパラメータを生成する初期パラメータ生成ステップと、
前記各種データの照合を行う照合装置に前記パラメータを適応することで照合結果を取得する照合結果取得ステップと、
この照合結果取得ステップにより取得した照合結果を基に予め定められた評価関数を使用して適応度を算出する適応度算出ステップと、
この適応度算出ステップによる適応度の算出が行われた後、この算出された適応度を基にして遺伝的アルゴリズムにより前記パラメータを変更するパラメータ変更ステップと、
このパラメータ変更ステップで変更したパラメータについて前記遺伝的アルゴリズムを最大世代数だけ世代交代を繰り返すことで最適化する最適化ステップと、
この最適化ステップで最適化した最終個体群のパラメータを保存するパラメータ保存ステップと、
このパラメータ保存ステップで保存したパラメータを前記初期パラメータ生成ステップで生成したパラメータの代わりとして前記各種データの照合を行うことで、前記照合結果取得ステップと、前記適応度算出ステップと、前記パラメータ変更ステップおよび前記最適化ステップを用いて前記パラメータ保存ステップで保存する前記パラメータを複数段階繰り返して更新し、前記パラメータ保存ステップで保存する前記パラメータを段階的に進化させる進化用繰り返しステップ
とを具備することを特徴とする照合パラメータ最適化方法。
【請求項７】
各種データを照合する照合装置のコンピュータに、
前記各種データを照合する際に使用するパラメータを生成する初期パラメータ生成処理と、
この初期パラメータ生成処理で生成したパラメータを適応することで照合結果を取得する照合結果取得処理と、
この照合結果取得処理により取得した照合結果を基に予め定められた評価関数を使用して適応度を算出する適応度算出処理と、
この適応度算出処理による適応度の算出が行われた後、この算出された適応度を基にして遺伝的アルゴリズムにより前記パラメータを変更するパラメータ変更処理と、
このパラメータ変更処理で変更したパラメータについて前記遺伝的アルゴリズムを最大世代数だけ世代交代を繰り返すことで最適化する最適化処理と、
この最適化処理で最適化した最終個体群のパラメータを保存するパラメータ保存処理と、
このパラメータ保存処理で保存したパラメータを前記初期パラメータ生成処理で生成したパラメータの代わりとして前記各種データの照合を行うことで、前記照合結果取得処理と、前記適応度算出処理と、前記パラメータ変更処理および前記最適化処理を用いて前記パラメータ保存処理で保存する前記パラメータを複数段階繰り返して更新し、前記パラメータ保存処理で保存する前記パラメータを段階的に進化させる進化用繰り返しステップ処理
とを実行させることを特徴とする照合パラメータ最適化制御プログラム。
【請求項１】
各種データを照合するためのパラメータを生成する初期パラメータ生成手段と、
前記各種データの照合を行う照合装置に前記パラメータを適応することで照合結果を取得する照合結果取得手段と、
この照合結果取得手段により取得した照合結果を基に予め定められた評価関数を使用して適応度を算出する適応度算出手段と、
この適応度算出手段による適応度の算出が行われた後、この算出された適応度を基にして遺伝的アルゴリズムにより前記パラメータを変更するパラメータ変更手段と、
このパラメータ変更手段で変更したパラメータについて前記遺伝的アルゴリズムを最大世代数だけ世代交代を繰り返すことで最適化する最適化手段
とを具備することを特徴とする照合パラメータ最適化装置。
【請求項２】
前記最適化手段で最適化した最終個体群のパラメータを保存するパラメータ保存手段を具備することを特徴とする請求項１記載の照合パラメータ最適化装置。
【請求項３】
前記各種データは指紋データであり、前記遺伝的アルゴリズムは、遺伝的操作である選択、交差および突然変異のいずれかを少なくとも含んで構成されることを特徴とする請求項１記載の照合パラメータ最適化装置。
【請求項４】
前記パラメータ保存手段に保存したパラメータを前記初期パラメータ生成手段の生成したパラメータの代わりとして前記各種データの照合を行うことで、前記照合結果取得手段と、前記適応度算出手段と、前記パラメータ変更手段および前記最適化手段を用いて前記パラメータ保存手段に保存する前記パラメータを複数段階繰り返して更新し、前記パラメータ保存手段に保存する前記パラメータを段階的に進化させる進化用繰り返し手段を具備することを特徴とする請求項２記載の照合パラメータ最適化装置。
【請求項５】
前記進化用繰り返し手段の多段階の進化における初期段階の進化は、比較的緩やかな照合条件でパラメータを進化させるものであり、それ以後の段階の進化でパラメータの探索領域が絞り込まれた形でパラメータが進化することを特徴とする請求項４記載の照合パラメータ最適化装置。
【請求項６】
各種データを照合するためのパラメータを生成する初期パラメータ生成ステップと、
前記各種データの照合を行う照合装置に前記パラメータを適応することで照合結果を取得する照合結果取得ステップと、
この照合結果取得ステップにより取得した照合結果を基に予め定められた評価関数を使用して適応度を算出する適応度算出ステップと、
この適応度算出ステップによる適応度の算出が行われた後、この算出された適応度を基にして遺伝的アルゴリズムにより前記パラメータを変更するパラメータ変更ステップと、
このパラメータ変更ステップで変更したパラメータについて前記遺伝的アルゴリズムを最大世代数だけ世代交代を繰り返すことで最適化する最適化ステップと、
この最適化ステップで最適化した最終個体群のパラメータを保存するパラメータ保存ステップと、
このパラメータ保存ステップで保存したパラメータを前記初期パラメータ生成ステップで生成したパラメータの代わりとして前記各種データの照合を行うことで、前記照合結果取得ステップと、前記適応度算出ステップと、前記パラメータ変更ステップおよび前記最適化ステップを用いて前記パラメータ保存ステップで保存する前記パラメータを複数段階繰り返して更新し、前記パラメータ保存ステップで保存する前記パラメータを段階的に進化させる進化用繰り返しステップ
とを具備することを特徴とする照合パラメータ最適化方法。
【請求項７】
各種データを照合する照合装置のコンピュータに、
前記各種データを照合する際に使用するパラメータを生成する初期パラメータ生成処理と、
この初期パラメータ生成処理で生成したパラメータを適応することで照合結果を取得する照合結果取得処理と、
この照合結果取得処理により取得した照合結果を基に予め定められた評価関数を使用して適応度を算出する適応度算出処理と、
この適応度算出処理による適応度の算出が行われた後、この算出された適応度を基にして遺伝的アルゴリズムにより前記パラメータを変更するパラメータ変更処理と、
このパラメータ変更処理で変更したパラメータについて前記遺伝的アルゴリズムを最大世代数だけ世代交代を繰り返すことで最適化する最適化処理と、
この最適化処理で最適化した最終個体群のパラメータを保存するパラメータ保存処理と、
このパラメータ保存処理で保存したパラメータを前記初期パラメータ生成処理で生成したパラメータの代わりとして前記各種データの照合を行うことで、前記照合結果取得処理と、前記適応度算出処理と、前記パラメータ変更処理および前記最適化処理を用いて前記パラメータ保存処理で保存する前記パラメータを複数段階繰り返して更新し、前記パラメータ保存処理で保存する前記パラメータを段階的に進化させる進化用繰り返しステップ処理
とを実行させることを特徴とする照合パラメータ最適化制御プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２００９−１７５９２５（Ｐ２００９−１７５９２５Ａ）
【公開日】平成２１年８月６日（２００９．８．６）
【国際特許分類】
【出願番号】特願２００８−１２４２２（Ｐ２００８−１２４２２）
【出願日】平成２０年１月２３日（２００８．１．２３）
【出願人】（０００２１３３０１）中部日本電気ソフトウェア株式会社 (56)
【Ｆターム（参考）】
【公開日】平成２１年８月６日（２００９．８．６）
【国際特許分類】
【出願日】平成２０年１月２３日（２００８．１．２３）
【出願人】（０００２１３３０１）中部日本電気ソフトウェア株式会社 (56)
【Ｆターム（参考）】
[ Back to top ]