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

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

国内特許コード P110004981
掲載日 2011年8月18日
出願番号 特願2007-031592
公開番号 特開2008-197867
登録番号 特許第5011533号
出願日 平成19年2月13日(2007.2.13)
公開日 平成20年8月28日(2008.8.28)
登録日 平成24年6月15日(2012.6.15)
発明者
  • 長尾 智晴
  • 白川 真一
出願人
  • 国立大学法人横浜国立大学
発明の名称 進化計算システム及び進化計算方法 コモンズ
発明の概要

【課題】本発明は、遺伝的プログラミングにより進化計算を行なう進化計算システムに係り、遺伝子情報として通常のデータ加工を行なう関数系演算子と区別して、処理フローの制御を行なう制御系演算子を設け、更に処理フローと区別してデータフローを記述することにより複雑な制御を含むアルゴリズムを最適化する。
【解決手段】f0~f2の関数系演算子に係るノードでは、バッファ列のうち第一バッファID105と第二バッファID106の両バッファから得たデータに対して加算等のデータ加工を施し、第三バッファID107のバッファへ格納する。f3~f5の制御系演算子に係るノードでは、第一バッファID105と第二バッファID106から得たデータを比較等の条件判定を行ない、次処理ノードとして第一連結先ノードNo103あるいは第二連結先ノードNo104を選択する。
【選択図】図1

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


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



遺伝的プログラミングは、遺伝的アルゴリズムを発展させたものであって、個体を構造的に表現する。例えば、(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

産業上の利用分野


本発明は、遺伝的プログラミングにより進化計算を行なう進化計算システムに係り、複雑な制御を含むアルゴリズムを最適化する技術に関する。

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

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

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

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

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

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


PAGE TOP

close
close
close
close
close
close
close