Top > Quick Search > Search patent in Japan > EVOLUTION CALCULATION SYSTEM AND EVOLUTION CALCULATION METHOD

EVOLUTION CALCULATION SYSTEM AND EVOLUTION CALCULATION METHOD commons

Patent code P110004953
Posted date Aug 18, 2011
Application number P2005-274309
Publication number P2007-087055A
Patent number P4862150
Date of filing Sep 21, 2005
Date of publication of application Apr 5, 2007
Date of registration Nov 18, 2011
Inventor
  • (In Japanese)長尾 智晴
  • (In Japanese)藤嶋 航
Applicant
  • (In Japanese)学校法人横浜国立大学
Title EVOLUTION CALCULATION SYSTEM AND EVOLUTION CALCULATION METHOD commons
Abstract

PROBLEM TO BE SOLVED: To increase the degree of freedom of reproduction such as crossing processing or mutation processing, and to simultaneously optimize an individual structure and numeric value in an evolution calculation system for operating evolution calculation by genetic programming.

SOLUTION: This evolution calculation system is provided with a genetic table for defining the number of connection of gene, and when expression type individual structure information describing a connection relation between genes is generated, gene as the node of connection destination is specified so that the number of connection can be satisfied, and an expression type is consistently configured. Also, a parameter to be used for a function to be specified by gene is added to gene information, and the gene and the parameter are simultaneously operated. Furthermore, node classification is added to gene information, and termination and non-termination are operated, and a partial tree structure is dynamically changed. A matrix type individual structure is adopted, and the operation of the crossing or mutation of a block is carried out by reproduction processing.

Outline of related art and contending technology (In Japanese)


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



遺伝的アルゴリズムは、一般的に個体を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

Field of industrial application (In Japanese)


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

Scope of claims (In Japanese)
【請求項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)選択した個体の遺伝子型個体構造情報に対して、複数の個体間で一部の情報を交換する交叉処理、あるいは一部の情報を変化させる突然変異処理を行い、次世代の個体集団の要素となる各個体の遺伝子型個体構造情報を求め、個体集団記憶部に記憶させる生殖手順。
Industrial division
  • Computation controlling device
IPC(International Patent Classification)
Drawing

※Click image to enlarge.

JP2005274309thum.jpg
State of application right Right is in force
(In Japanese)掲載特許について詳しくお知りになりたい方はHPの「お問い合わせ」ページにてお問い合わせください。


PAGE TOP

close
close
close
close
close
close
close