(57)【要約】【課題】  設計パラメータに対する依存性を低下せしめ、高速／高精度に探索解を求める事が可能な最適解探索方法及び最適解探索装置を提供する。【解決手段】  遺伝的アルゴリズムを用いた最適解探索方法において、複数の個体により構成される個体集団を複数作成する工程と、作成された複数の個体集団に、其々異なる遺伝的パラメータを設定する工程と、指定された遺伝的パラメータに従って、各集団内の個体に遺伝的操作を行なう工程と、各個体集団の適応度を求める工程と、各個体集団間の適応度を比較する工程と、比較結果に従って、各個体集団の遺伝的パラメータを変更する工程を有する。【選択図】        図１
2005222286.tif 000002
【特許請求の範囲】
【請求項１】
遺伝的アルゴリズムを用いた最適解探索方法において、
複数の個体により構成される個体集団を複数作成する工程と、
作成された複数の個体集団に其々異なる遺伝的パラメータを設定する工程と、
指定された遺伝的パラメータに従って、各集団内の個体に遺伝的操作を行なう工程と、
各個体集団の適応度を求める工程と、
各個体集団間の適応度を比較する工程と、
比較結果に従って、各個体集団の遺伝的パラメータを変更する工程を有する事を特徴とする最適解探索方法。
【請求項２】
個体集団の適応度の大小に従って、個体集団の遺伝的パラメータを交換する事を特徴とする請求項１に記載の最適解探索方法。
【請求項３】
個体集団の適応度が，当該集団内の最大適応度を有する個体の適応度である事を特徴とする請求項１または２に記載の最適解探索方法。
【請求項４】
遺伝的パラメータが突然変異確率である事を特徴とする請求項１ないし３いずれかに記載の最適解探索方法。
【請求項５】
遺伝的パラメータが交差確率である事を特徴とする請求項１ないし３いずれかに記載の最適解探索方法。
【請求項６】
遺伝的パラメータが交差手法である事を特徴とする請求項１ないし３いずれかに記載の最適解探索方法。
【請求項７】
請求項１ないし６いずれかに記載の最適解探索方法における工程を処理する手段を有する事を特徴とする最適解探索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、遺伝的アルゴリズムを用いた最適解探索方法および最適解探索装置に関する。
【背景技術】
【０００２】
Ｊ．Ｈ．Ｈｏｌｌａｎｄによって提案された遺伝的アルゴリズム（Ｊ．Ｈ．Ｈｏｌｌａｎｄ  “Ａｄａｐｔａｔｉｏｎ  ｉｎ  Ｎａｔｕｒａｌ  ａｎｄ  Ａｒｔｉｆｉｃｉａｌ  Ｓｙｓｔｅｍｓ”，ＭＩＴ  Ｐｒｅｓｓ）は、生物の進化の過程を模擬する事で適応的に最適解を求める確率的探索手法であり、画像処理等様々な分野への応用が提案され、実用に供されている。図７はＳＧＡ（Ｓｉｍｐｌｅ  Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍ）と呼ばれる基本的な遺伝的アルゴリズムの原理を説明する図である。探索解を染色体として表現する複数の個体をランダムに生成し、初期集団とする（ステップＳ２０１）。当該集団内の個体に対して、所定の世代に渡り遺伝的操作（ステップＳ２０２〜Ｓ２０６）を繰り返す事で進化的に最適な解を探索する。遺伝的アルゴリズムにおいては、交差処理（ステップＳ２０５）／突然変異処理（ステップＳ２０６）等の遺伝的操作が重要な役割を果たしている。
【０００３】
遺伝的アルゴリズムは極めて簡単な処理で広い解空間を効率的に探索可能な手法であるが、実際の問題に適用する場合、突然変異率／交差率／交差手法／集団数など、いわゆる遺伝的パラメータの最適設計が困難であり、また、応用毎に最適なパラメータが異なる等の問題があった。例えば、突然変異率を小さく設定した場合、局所解に陥る可能性が高く、大きく設定した場合、最適解の近傍に存在するより高い最適解の探索性能等が低下する。最適な突然変異率は探索空間の特徴、即ち適用する問題の特性に大きく依存する。
【０００４】
探索回数の短縮を目的として、遺伝的パラメータを動的に変動させる場合について提案されている（例えば、特許文献１参照。）。
【特許文献１】特開平８−３１４８８３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記のような従来例では、パラメータ変動条件／方法が新たな設計パラメータとなる等の問題があった。
【０００６】
本発明は、上記問題に鑑みてなされたものであり、設計パラメータに対する依存性を低下せしめ、高速／高精度に探索解を求める事が可能な最適解探索方法及び最適解探索装置を提供する事を目的とするものである。
【課題を解決するための手段】
【０００７】
本発明では、上記問題点を解決するために、遺伝的アルゴリズムを用いた最適解探索方法において、
複数の個体により構成される個体集団を複数作成する工程と、
作成された複数の個体集団に、其々異なる遺伝的パラメータを設定する工程と、
指定された遺伝的パラメータに従って、各集団内の個体に遺伝的操作を行なう工程と、
各個体集団の適応度を求める工程と、
各個体集団間の適応度を比較する工程と、
比較結果に従って、各個体集団の遺伝的パラメータを変更する工程を有する事を特徴としている。
【発明の効果】
【０００８】
本発明により、設計パラメータに対する性能の依存性を低下せしめ、高速／高精度な最適解探索方法又は装置を容易に設計する事が可能になる。
【発明を実施するための最良の形態】
【０００９】
以下、添付図面を参照して本発明に関する実施例を説明する。
【００１０】
〔実施例〕
図１は本発明による遺伝的アルゴリズムの基本原理を説明する図である。複数の個体集団に対して遺伝的アルゴリズムを並列に動作させ（１０１、１０２）、各集団の適応度の比較結果（１０３）に基づいて、遺伝的パラメータの交換を行なう（１０４）。これにより、複数の個体集団を世代単位で競合させながら進化的探索を行なう。
【００１１】
図２は本発明に関する遺伝的アルゴリズムの処理フローを示す図である。初期集団１生成ステップ（Ｓ１０１）では探索解を染色体として有する所定の数の個体をランダムに生成する。染色体は求める探索解を２値文字列で表現する。例えば、任意の画像中から楕円を認識する問題に適用する場合（図４の（ａ））、楕円の中心座標値（ｘ，ｙ）及び半径（ｒｘ，ｒｙ）を染色体にマッピングする。各値が８ビットであるとすると、染色体は３２ビットの２値文字列で表現される事になる（図４の（ｂ））。
【００１２】
遺伝的パラメータ１設定ステップ（Ｓ１０１）では初期集団１に対する遺伝的パラメータを設定する。ここで、遺伝的パラメータとは、遺伝的操作に使用する突然変異確率、交差確率等の設計パラメータである。ステップＳ１０３〜Ｓ１０４では、同様に初期集団２を生成し、初期集団１で設定したパラメータと異なる遺伝的パラメータを設定する。
【００１３】
具体的には、初期集団１に対しては小さい突然変異確率を設定し、初期集団２には大きい突然変異確率を設定する。次に、個体集団１及び個体集団２の適応度を算出する（ステップＳ１０５及びステップＳ１０７）。前述の楕円認識問題の場合、集団内の各個体の適応度は、染色体が表現する位置及び大きさの楕円と画像データの相関値を適応度とする。
【００１４】
例えば、画像データが２値画像の場合、個体が表現する画像データと対象画像との論理積の総和を適応度とする。集団の適応度は例えば、多点解探索（複数の最適解を探索する場合）の場合、各染色体が表現する適応度の平均値を集団の適応度とし、１点解探索（１つの最適解を探索する場合）の場合、各集団が表現する適応度の最大値を集団の適応度とする。集団の適応度が探索終了条件を超えている場合、当該適応度を示す個体を探索解として処理を終了する（ステップＳ１０６及びステップＳ１０８）。
【００１５】
次に集団適応度の比較を行い（ステップＳ１０９）、比較結果に従って、集団に設定する遺伝的パラメータの入換えを行なう（ステップｓ１１２）。集団１の適応度が集団２の適応度を上回る場合かつ集団１に対して遺伝的パラメータ２が設定されている場合（ステップＳ１１０）、遺伝的パラメータを交換する。即ち、集団１に対して、遺伝的パラメータ１を設定し、集団２に対して遺伝的パラメータ２を設定する。一方、集団２の適応度が集団１の適応度を上回る場合かつ集団１に遺伝的パラメータ１が設定されている場合（ステップｓ１１１）、遺伝的パラメータを入れ替える。
【００１６】
以上の処理により、本実施例では、集団の適応度が高い場合、低い突然変異確率が設定され、集団の適応度低い場合、高い突然変異確率が設定される。続いて、ステップＳ１１１〜Ｓ１１４で各集団に対してそれぞれ遺伝的操作を行なう。
【００１７】
遺伝的操作は従来提案されている手法（Ｄ．Ｅ．Ｇｏｌｄｂｅｒｇ，  “Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍｓ  ｉｎ  Ｓｅａｒｃｈ，  Ｏｐｔｉｍｉｚａｔｉｏｎ  ａｎｄ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ”，Ａｄｄｉｓｏｎ−Ｗａｓｌｅｙ  Ｐｕｂｌｉｓｈｉｎｇ  Ｃｏｍｐａｎｙ，１９８９  等に記載）を利用して処理する。
【００１８】
図３は遺伝的操作ステップの処理内容を説明する図である。Ｓ３０１では、各染色体の適応度に基づいて淘汰選択処理を行なう。淘汰ステップでは、例えば、従来提案されているルーレット選択法／エリート選択法などを用いて適応度の高い染色体を保存増殖し、適応度の低い染色体を集団から削除（淘汰）する。
【００１９】
交差処理ステップ（Ｓ３０２）では、遺伝的パラメータで指定された交差確率に従って、ランダムに選んだ２つの染色体に対して交差処理をおこなう。交差処理ステップでは染色体の部分的な入換えを行なう。次に突然変異処理ステップ（Ｓ３０３）では、遺伝的パラメータで指定する突然変異確率に基づいて、染色体上の遺伝子座の値を確率的に変更する。例えば，染色体が２値データ−列で構成されている場合、ランダムに選んだ遺伝子座のビット値を指定する確率で反転する。
【００２０】
以上の処理を集団１及び２に対してそれぞれ実行する。１回の評価／遺伝的操作（ステップＳ１０５〜ステップＳ１１４）を１世代とし、探索条件を満足するかあるいは予め指定する最大世代数に達する（探索打ち切り回数）まで処理を繰り返す。
【００２１】
図５の（ａ）は実施例で説明した方式を関数の最小値探索に応用した場合のシミュレーション結果の一例を示すものである。全ての集団は単純１点交差、淘汰選択処理はエリート保存／ルーレット選択、バイナリ突然変異により遺伝的操作を行なった。個体数は其々４０個で評価を行ない、５００世代の試行を１０回行なった平均を示す。また、集団数は２とし、遺伝的パラメータとしてそれぞれ突然変異確率０．０５、０．００５を与え、集団の適応度に従って当該値を交換するようにした。５１は集団１の探索処理結果、５２は集団２の探索処理結果を示す。
【００２２】
また、横軸を世代数、縦軸を適応度とする。集団１集団２が其々競合しながら、最適解の探索を。各集団の適度度が交差する点（世代）で遺伝的パラメータの交換が行なわれている。図５の（ｂ）は比較のために上記２つの集団を独立に進化させた場合の探索結果を示している。５３は突然変異率０．０５の集団、５４は突然変異率０．００５の集団の探索結果を示す。（ａ）に比べて進化速度（探索速度）が遅く、また突然変異確率によって探索性能に著しい違いがある。
【００２３】
以上、本実施例では、突然変異確率が高い集団と突然変異確率が低い集団を同時に進化させ、適応度の高い集団は低い突然変異率で最適解近傍をより良い解を求めて探索し、適応度の低い集団は高い突然変異率で広い探索空間を探索する。更に、集団間の適応度に基づき突然変異率を交換する事で、競合する集団より高い探索解を発見した集団は、低い突然変異率にパラメータを変更する事で、新たに発見した高い探索解の近傍を中心に、より適応度の高い解を探索する動作に移行する。
【００２４】
一方、適応度の比較で敗れた集団は、高い突然変異率を設定する事で、確率的に探索範囲を広げ、新たな最適解を求めて探索を開始する。
【００２５】
このように、特性の異なる（遺伝的パラメータの異なる）個体集団が適応度に基づいてその特性を交換しながら探索を行う事で、遺伝的パラメータの依存性を低下せしめ、より精度の高い解を高速に得る事が可能になる。
【００２６】
〔他の実施例〕
上述の実施例では、遺伝的パラメータとして、突然変異率を交換する場合について説明したが、交差率、交差手法、淘汰手法など様々な設計パラメータに適応してよい。
【００２７】
また実施例では、２集団間でパラメータ交換を行なう場合について説明したが、さらに多くの集団に分割する方法でも良い。その場合も、集団適応度の比較結果に応じて、遺伝的パラメータを交換すればよい。
【００２８】
また実施例では、遺伝的パラメータを交換する場合について説明したが、集団間の適応度の大小に基づいてパラメータ値を変化させるような手法でも良い。
【００２９】
第６図は本発明による処理を、例えば、画像処理機器に応用する場合の構成例を示す図である。６０１は画像入力部でありＣＣＤカメラ等により撮像された画像データの取り込み、画像補正処理等をハードウエアにより処理するものである。
【００３０】
６０２は本発明の主要な処理を司るプロセッサであり、例えばマルチメディア信号処理用に特化されたメディアプロセッサやＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）等により各種の信号処理を行うものである。６０３はＲＡＭ（Ｒａｎｄａｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）であり、プロセッサ６０２の動作に必要な作業メモリ及び処理すべき画像データの各種バッファメモリとして使用される。ＲＡＭ６０３は、例えばＳＤＲＡＭ（Ｓｙｎｃｈｒｏｎｏｕｓ  ＤＲＡＭ）等の高速大容量のメモリにより実現されるものである。６０４はＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）であり、プロセッサ６０２の動作に必要な命令プログラムを格納するためのものである。６０５は通信インターフェースであり符号化された画像データを所定のプロトコルで通信回線上に送り出すためのインターフェースを司るものである。例えば，画像入力部６０１で入力された画像データから所定のオブジェクトを認識するような場合、プロセッサ６０２では画像認識処理内部に図２、図３で示す処理ステップを組込み所定の処理を行なう。
【００３１】
このように本発明はマイクロコントローラ等を使用した組込みシステムで実現可能であり、また、汎用のコンピュータ等で実現しても良い、更に専用の処理ハードウェアにより実現しても良い。
【図面の簡単な説明】
【００３２】
【図１】本発明の遺伝的アルゴリズム原理を説明する図
【図２】実施例の遺伝的アルゴリズム処理フローを説明する図
【図３】遺伝的操作の処理フローを説明する図
【図４】遺伝的アルゴリズムを画像認識に適用した場合の例を説明する図
【図５】本発明によるシミュレーション結果の例を示す図
【図６】本発明をシステムに応用する場合の構成例を説明する図
【図７】従来の遺伝的アルゴリズムの処理フローを説明する図
【符号の説明】
【００３３】
Ｓ１０１、Ｓ１０３  初期集団生成ステップ
Ｓ１０２、Ｓ１０４  遺伝的パラメータ設定ステップ
Ｓ１０５、Ｓ１０７  集団の適応度算出ステップ
Ｓ１０６、Ｓ１０８  探索終了条件判定ステップ
Ｓ１０９  集団の適応度比較ステップ
Ｓ１１０、Ｓ１１１  現在指定されている遺伝的パラメータの判定ステップ
Ｓ１１２  遺伝的パラメータ交換ステップ
Ｓ１１３、Ｓ１１４  遺伝的操作処理ステップ
【図１】
2005222286.tif 000003
【図２】
2005222286.tif 000004
【図３】
2005222286.tif 000005
【図４】
2005222286.tif 000006
【図５】
2005222286.tif 000007
【図６】
2005222286.tif 000008
【図７】
2005222286.tif 000009