Top > Search of Japanese Patents > EVOLUTIONARY COMPUTATION SYSTEM AND EVOLUTIONARY COMPUTATION METHOD

EVOLUTIONARY COMPUTATION SYSTEM AND EVOLUTIONARY COMPUTATION METHOD

Patent code P110004981
Posted date Aug 18, 2011
Application number P2007-031592
Publication number P2008-197867A
Patent number P5011533
Date of filing Feb 13, 2007
Date of publication of application Aug 28, 2008
Date of registration Jun 15, 2012
Inventor
  • (In Japanese)長尾 智晴
  • (In Japanese)白川 真一
Applicant
  • (In Japanese)国立大学法人横浜国立大学
Title EVOLUTIONARY COMPUTATION SYSTEM AND EVOLUTIONARY COMPUTATION METHOD
Abstract PROBLEM TO BE SOLVED: To provide an evolutionary computation system for operating evolutionary computation by genetic programming equipped with a control system operator for controlling a processing flow separately from a function system operator for operating normal data processing as genetic information, and to optimize an algorithm including a plurality of control by describing a data flow separately from the processing flow.
SOLUTION: In a node related with function system operators f0 to f2, data processing such as addition is applied to data acquired from a first buffer ID 105 and a second buffer ID 106 in a buffer column, and the data are stored in the buffer of a third buffer ID 107. In a node related with control system operators f3 to f5, condition decision such as comparison is applied to data acquired from the first buffer ID 105 and the second buffer ID 106, and either a first connection destination node No103 or a second connection destination node No104 is selected as the next processing node.
Outline of related art and contending technology (In Japanese)

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

遺伝的プログラミングは、遺伝的アルゴリズムを発展させたものであって、個体を構造的に表現する。例えば、(A(B)(C(D)))のように記述するLispのS式などにより木構造を表現する。

しかし、遺伝的プログラミングは、複雑な制御を含むアルゴリズムを生成することには向いていない。上述のLispのS式を例とすると、Dノードは、Cノードの処理の後に、Cノードの出力データを入力して演算を行なう。祖父にあたるAノードや叔父にあたるBノードからデータを受け取ることはない。つまり、Dノードは、処理フロー上の親も、データフロー上の親も同一のノードであり、処理フローとデータフローが一体となっている。そして、それらフローを分離して扱うことはできない。

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

【非特許文献2】青木紳也、長尾智晴,「木構造状画像変換の自動構築法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)個体集団記憶部に含まれる個体毎に、当該個体のグラフ型個体構造情報に含まれるノード情報に含まれる演算子識別情報によって識別されるファンクション実行部が条件判定を行なう場合には、その判定結果に基づいてノード情報に含まれる複数の連結先ノード識別情報のうちいずれかにより次に処理するノードを選択する制御系演算と、当該個体のグラフ型個体構造情報に含まれるノード情報に含まれる演算子識別情報によって識別されるファンクション実行部がデータ加工を行なう場合には、ノード情報に含まれるバッファ識別情報によって特定される取得バッファから取得したデータを加工し、加工結果をノード情報に含まれるバッファ識別情報によって特定される格納バッファに書き込み、ノード情報に含まれる所定の連結先ノード識別情報により次に処理するノードを選択する関数系演算を、順次選択されるノード毎に実行し、当該個体のグラフ型個体構造情報に含まれるノード情報に含まれる演算子識別情報が完了を示す場合に、いずれかのバッファのデータを演算結果データとし、当該演算結果データと、学習用目標データを比較して、個体毎の適応度を計算する適応度計算工程
(2)適応度に基づいて、個体集団から個体を選択する個体選択工程
(3)選択した個体のグラフ型個体構造情報に対して、複数の個体間で一部の情報を交換する交叉処理、あるいは一部の情報を変化させる突然変異処理を行い、次世代の個体集団の要素となる各個体のグラフ型個体構造情報を求め、個体集団記憶部に記憶させる生殖工程。

【請求項3】
 
初期値として、定数、学習用入力データ、あるいは学習用入力データに対する所定の演算を施した関数値を記憶する複数のバッファを、バッファ識別情報に対応付けて備えるバッファ列と、
同一世代に係る個体集団の要素である各個体について、ノードで起動されるファンクション実行部を識別する演算子識別情報と、次に実行されるノードの候補を識別する複数の連結先ノード識別情報と、当該ファンクション実行部への入力データを得る取得バッファ及び当該ファンクション実行部からの出力データを書き込む格納バッファを識別するバッファ識別情報群を含むノード情報が連続するグラフ型個体構造情報を記憶する個体集団記憶部を有し、グラフ型個体構造を用いて進化計算を行なう進化計算システムとなるコンピュータに、以下の処理を実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体
(1)個体集団記憶部に含まれる個体毎に、当該個体のグラフ型個体構造情報に含まれるノード情報に含まれる演算子識別情報によって識別されるファンクション実行部が条件判定を行なう場合には、その判定結果に基づいてノード情報に含まれる複数の連結先ノード識別情報のうちいずれかにより次に処理するノードを選択する制御系演算と、当該個体のグラフ型個体構造情報に含まれるノード情報に含まれる演算子識別情報によって識別されるファンクション実行部がデータ加工を行なう場合には、ノード情報に含まれるバッファ識別情報によって特定される取得バッファから取得したデータを加工し、加工結果をノード情報に含まれるバッファ識別情報によって特定される格納バッファに書き込み、ノード情報に含まれる所定の連結先ノード識別情報により次に処理するノードを選択する関数系演算を、順次選択されるノード毎に実行し、当該個体のグラフ型個体構造情報に含まれるノード情報に含まれる演算子識別情報が完了を示す場合に、いずれかのバッファのデータを演算結果データとし、当該演算結果データと、学習用目標データを比較して、個体毎の適応度を計算する適応度計算処理
(2)適応度に基づいて、個体集団から個体を選択する個体選択処理
(3)選択した個体のグラフ型個体構造情報に対して、複数の個体間で一部の情報を交換する交叉処理、あるいは一部の情報を変化させる突然変異処理を行い、次世代の個体集団の要素となる各個体のグラフ型個体構造情報を求め、個体集団記憶部に記憶させる生殖処理。

【請求項4】
 
初期値として、定数、学習用入力データ、あるいは学習用入力データに対する所定の演算を施した関数値を記憶する複数のバッファを、バッファ識別情報に対応付けて備えるバッファ列と、
同一世代に係る個体集団の要素である各個体について、ノードで起動されるファンクション実行部を識別する演算子識別情報と、次に実行されるノードの候補を識別する複数の連結先ノード識別情報と、当該ファンクション実行部への入力データを得る取得バッファ及び当該ファンクション実行部からの出力データを書き込む格納バッファを識別するバッファ識別情報群を含むノード情報が連続するグラフ型個体構造情報を記憶する個体集団記憶部を有し、グラフ型個体構造を用いて進化計算を行なう進化計算システムとなるコンピュータに、以下の手順を実行させるためのプログラム
(1)個体集団記憶部に含まれる個体毎に、当該個体のグラフ型個体構造情報に含まれるノード情報に含まれる演算子識別情報によって識別されるファンクション実行部が条件判定を行なう場合には、その判定結果に基づいてノード情報に含まれる複数の連結先ノード識別情報のうちいずれかにより次に処理するノードを選択する制御系演算と、当該個体のグラフ型個体構造情報に含まれるノード情報に含まれる演算子識別情報によって識別されるファンクション実行部がデータ加工を行なう場合には、ノード情報に含まれるバッファ識別情報によって特定される取得バッファから取得したデータを加工し、加工結果をノード情報に含まれるバッファ識別情報によって特定される格納バッファに書き込み、ノード情報に含まれる所定の連結先ノード識別情報により次に処理するノードを選択する関数系演算を、順次選択されるノード毎に実行し、当該個体のグラフ型個体構造情報に含まれるノード情報に含まれる演算子識別情報が完了を示す場合に、いずれかのバッファのデータを演算結果データとし、当該演算結果データと、学習用目標データを比較して、個体毎の適応度を計算する適応度計算手順
(2)適応度に基づいて、個体集団から個体を選択する個体選択手順
(3)選択した個体のグラフ型個体構造情報に対して、複数の個体間で一部の情報を交換する交叉処理、あるいは一部の情報を変化させる突然変異処理を行い、次世代の個体集団の要素となる各個体のグラフ型個体構造情報を求め、個体集団記憶部に記憶させる生殖手順。
Industrial division
  • Computation controlling device
IPC(International Patent Classification)
Drawing

※Click image to enlarge.

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


PAGE TOP

close
close
close
close
close
close
close