TOP > 国内特許検索 > 進化計算システム及び進化計算方法

進化計算システム及び進化計算方法 コモンズ

国内特許コード P110004953
掲載日 2011年8月18日
出願番号 特願2005-274309
公開番号 特開2007-087055
登録番号 特許第4862150号
出願日 平成17年9月21日(2005.9.21)
公開日 平成19年4月5日(2007.4.5)
登録日 平成23年11月18日(2011.11.18)
発明者
  • 長尾 智晴
  • 藤嶋 航
出願人
  • 学校法人横浜国立大学
発明の名称 進化計算システム及び進化計算方法 コモンズ
発明の概要

【課題】 遺伝的プログラミングにより進化計算を行なう進化計算システムに係り、交叉処理や突然変異処理などの生殖の自由度を高め、更に個体構造と数値の同時最適化を行なうことを課題とする。
【解決手段】 遺伝子に対する連結数を定義する遺伝子テーブルを設け、遺伝子間の連結関係を記述する表現型個体構造情報を生成する際に、連結数を満たすように連結先のノードとなる遺伝子を特定し、矛盾無く表現型を構成する。また、遺伝子で特定されるファンクションに用いるパラメータを遺伝子情報に付加し、遺伝子とパラメータを同時に操作する。更に、遺伝子情報にノード種別を付加し、終端と非終端を操作し、部分木構造をダイナミックに変化させる。マトリクス型の個体構造を採用し、生殖処理でブロックの交叉や突然変異の操作を行なう。
【選択図】 図47

従来技術、競合技術の概要


進化計算法とは、生物の進化から着想した最適化(探索)アルゴリズムである。進化論的な発想に基づいてデータを操作し、解空間を探索する多点探索法の一種とも言える。その代表的な手法として、遺伝的アルゴリズムと遺伝的プログラミングがある。



遺伝的アルゴリズムは、一般的に個体を0あるいは1を示すビットの一次元の列(染色体)として定義する。そして、生殖として、一点交叉、多点交叉、一様交叉などにより、2つの個体間で染色体の部位を交換する交叉処理、あるいは染色体の一部をランダムに変化させる突然変異処理を行う。



遺伝的プログラミングは、遺伝的アルゴリズムを発展させたものであって、個体をグラフ構造や木構造のように構造的に表現する。例えば、(A(B)(C(D)))のように記述するLispのS式などにより木構造を表現する。このように、一次元の文字列として記述するので、交叉処理によって新たな式を生成することができる。しかし、実際には構造として成り立たない致死遺伝子が含まれる恐れがある。突然変異処理についても無作為に文字列を書き換えることはできないという問題点がある。つまり、遺伝的プログラミングでは、生殖における任意性が低く、個体の多様性が確保できていない面がある。この点を改善すれば、構造的に表現された個体に係る探索効率を向上させることができる。



また、従来の進化計算法には、構造と数値の同時最適化ができないという問題点がある。遺伝的アルゴリズムは、染色体としてビットから構成される記号列を用いるため、数値の最適化には適しているが、構造の最適化には向いていない。一方、遺伝的プログラミングは、構造的表現により複雑な問題を解決できるようにした反面、ノードに対するパラメータの設定など、数値の最適化は図られていない。

【非特許文献1】佐藤浩、小野功、小林重信,「遺伝的アルゴリズムにおける世代交代モデルの提案と評価」,人工知能学会誌,人工知能学会誌1997年,vol.12,No.5,p.734-744

【非特許文献2】伊庭斉志、佐藤泰介,「システム同定アプローチに基づく遺伝的プログラミング」,人工知能学会誌,人工知能学会,1995年,vol.10,No.4,p.100-110

【非特許文献3】青木紳也、長尾智晴,「木構造状画像変換の自動構築法ACTIT」,映像情報メディア学会誌,映像情報メディア学会,1999年,vol.53,No.6,p.888-894

産業上の利用分野


本発明は、遺伝的プログラミングにより進化計算を行なう進化計算システムに係り、遺伝的プログラミングにおける生殖の自由度を高め、更に個体構造と数値の同時最適化を行なう技術に関する。

特許請求の範囲 【請求項1】
ファンクションを識別する遺伝子を含む遺伝子情報が連続する遺伝子型個体構造情報を用いて進化計算を行なう進化計算システムであって、以下の要素を有することを特徴とする進化計算システム
(1)同一世代に係る個体集団の要素である各個体の遺伝子型個体構造情報を記憶する個体集団記憶部
(2)遺伝子に対応付けて、当該遺伝子により特定されるファンクション入力されるデータの数を連結数として定義する遺伝子テーブル
(3)遺伝子型個体構造情報に含まれる遺伝子を順次読込み、当該遺伝子の連結数を遺伝子テーブルから取得し、連結数を満たすように連結先のノードとなる遺伝子を特定し、遺伝子間の連結関係を記述する表現型個体構造情報を生成し、学習用入力データを入力して、表現型個体構造情報によって特定される遺伝子の連結関係に従って、各遺伝子により特定されるファンクションによる演算を順次実行して個体演算出力データを求め、個体演算出力データを学習用目標データと比較して、個体毎の適応度を計算する適応度計算部
(4)適応度に基づいて、個体集団から個体を選択する個体選択部
(5)選択した個体の遺伝子型個体構造情報に対して、複数の個体間で一部の情報を交換する交叉処理、あるいは一部の情報を変化させる突然変異処理を行い、次世代の個体集団の要素となる各個体の遺伝子型個体構造情報を求め、個体集団記憶部に記憶させる生殖部。

【請求項2】
遺伝子型個体構造情報の遺伝子情報は、更に当該遺伝子に付加されたパラメータを含み、
適応度計算部は、遺伝子により特定されるファンクションによる演算を実行する際に、当該遺伝子に付加されているパラメータを用いて演算を実行することを特徴とする請求項1記載の進化計算システム。

【請求項3】
遺伝子型個体構造情報の遺伝子情報は、更に当該遺伝子が連結関係を構成するノードとなる際に終端ノードとなるか非終端ノードとなるかの別を示すノード種別を含み、
適応度計算部は、遺伝子間の連結関係を記述する表現型個体構造情報を生成する際に、遺伝子のノード種別が終端ノードの別を示す場合には、当該遺伝子の連結数を0とすることを特徴とする請求項1記載の進化計算システム。

【請求項4】
遺伝子型個体構造情報の遺伝子情報は、少なくとも遺伝子と、当該遺伝子に付加されたパラメータと、当該遺伝子が連結関係を構成するノードとなる際に終端ノードとなるか非終端ノードとなるかの別を示すノード種別の項目を含むレコードであり、遺伝子型個体構造情報は、レコードの行と項目の列からなるマトリクスを構成するマトリクス型個体構造情報であって、
生殖部は、マトリクスの一部として複数のレコードに跨るブロックを交換する交叉処理、あるいはマトリクスの一部として複数のレコードに跨るブロックを変化させる突然変異処理を行うことを特徴とする請求項1記載の進化計算システム。

【請求項5】
遺伝子型個体構造情報の遺伝子情報は、少なくとも遺伝子を示すビット構成と、当該遺伝子に付加されたパラメータを示すビット構成と、当該遺伝子が連結関係を構成するノードとなる際に終端ノードとなるか非終端ノードとなるかの別を示すノード種別を示すビット構成を含むレコードであり、遺伝子型個体構造情報は、レコードの行とビットの列からなるマトリクスを構成するマトリクス型個体構造情報であって、
生殖部は、マトリクスの一部として複数のレコードに跨るブロックを交換する交叉処理、あるいはマトリクスの一部として複数のレコードに跨るブロックを変化させる突然変異処理を行うことを特徴とする請求項1記載の進化計算システム。

【請求項6】
同一世代に係る個体集団の要素である各個体について、ファンクションを識別する遺伝子を含む遺伝子情報が連続する遺伝子型個体構造情報を記憶する個体集団記憶部と、遺伝子に対応付けて、当該遺伝子により特定されるファンクション入力されるデータの数を連結数として定義する遺伝子テーブルを有し、遺伝子型個体構造情報を用いて進化計算を行な進化計算システムによる進化計算方法であって、以下の要素を有することを特徴とする進化計算方法
(1)遺伝子型個体構造情報に含まれる遺伝子を順次読込み、当該遺伝子の連結数を遺伝子テーブルから取得し、連結数を満たすように連結先のノードとなる遺伝子を特定し、遺伝子間の連結関係を記述する表現型個体構造情報を生成し、学習用入力データを入力して、表現型個体構造情報によって特定される遺伝子の連結関係に従って、各遺伝子により特定されるファンクションによる演算を順次実行して個体演算出力データを求め、個体演算出力データを学習用目標データと比較して、個体毎の適応度を計算する適応度計算工程
(2)適応度に基づいて、個体集団から個体を選択する個体選択工程
(3)選択した個体の遺伝子型個体構造情報に対して、複数の個体間で一部の情報を交換する交叉処理、あるいは一部の情報を変化させる突然変異処理を行い、次世代の個体集団の要素となる各個体の遺伝子型個体構造情報を求め、個体集団記憶部に記憶させる生殖工程。

【請求項7】
同一世代に係る個体集団の要素である各個体について、ファンクションを識別する遺伝子を含む遺伝子情報が連続する遺伝子型個体構造情報を記憶する個体集団記憶部と、遺伝子に対応付けて、当該遺伝子により特定されるファンクション入力されるデータの数を連結数として定義する遺伝子テーブルを有し、遺伝子型個体構造情報を用いて進化計算を行な進化計算システムとなるコンピュータに、以下の処理を実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体
(1)遺伝子型個体構造情報に含まれる遺伝子を順次読込み、当該遺伝子の連結数を遺伝子テーブルから取得し、連結数を満たすように連結先のノードとなる遺伝子を特定し、遺伝子間の連結関係を記述する表現型個体構造情報を生成し、学習用入力データを入力して、表現型個体構造情報によって特定される遺伝子の連結関係に従って、各遺伝子により特定されるファンクションによる演算を順次実行して個体演算出力データを求め、個体演算出力データを学習用目標データと比較して、個体毎の適応度を計算する適応度計算処理
(2)適応度に基づいて、個体集団から個体を選択する個体選択処理
(3)選択した個体の遺伝子型個体構造情報に対して、複数の個体間で一部の情報を交換する交叉処理、あるいは一部の情報を変化させる突然変異処理を行い、次世代の個体集団の要素となる各個体の遺伝子型個体構造情報を求め、個体集団記憶部に記憶させる生殖処理。

【請求項8】
同一世代に係る個体集団の要素である各個体について、ファンクションを識別する遺伝子を含む遺伝子情報が連続する遺伝子型個体構造情報を記憶する個体集団記憶部と、遺伝子に対応付けて、当該遺伝子により特定されるファンクション入力されるデータの数を連結数として定義する遺伝子テーブルを有し、遺伝子型個体構造情報を用いて進化計算を行な進化計算システムとなるコンピュータに、以下の手順を実行させるためのプログラム
(1)遺伝子型個体構造情報に含まれる遺伝子を順次読込み、当該遺伝子の連結数を遺伝子テーブルから取得し、連結数を満たすように連結先のノードとなる遺伝子を特定し、遺伝子間の連結関係を記述する表現型個体構造情報を生成し、学習用入力データを入力して、表現型個体構造情報によって特定される遺伝子の連結関係に従って、各遺伝子により特定されるファンクションによる演算を順次実行して個体演算出力データを求め、個体演算出力データを学習用目標データと比較して、個体毎の適応度を計算する適応度計算手順
(2)適応度に基づいて、個体集団から個体を選択する個体選択手順
(3)選択した個体の遺伝子型個体構造情報に対して、複数の個体間で一部の情報を交換する交叉処理、あるいは一部の情報を変化させる突然変異処理を行い、次世代の個体集団の要素となる各個体の遺伝子型個体構造情報を求め、個体集団記憶部に記憶させる生殖手順。
産業区分
  • 演算制御装置
国際特許分類(IPC)
画像

※ 画像をクリックすると拡大します。

JP2005274309thum.jpg
出願権利状態 権利存続中
※ 掲載特許について詳しくお知りになりたい方はHPの「お問い合わせ」ページにてお問い合わせください。


PAGE TOP

close
close
close
close
close
close
close