遺伝的アルゴリズムによるルール変化型一次元セルオートマトンの進化
スポンサーリンク
概要
- 論文の詳細を見る
In this paper we propose a new method to obtain transition rules of one-dimensional two-state cellular automata (CAs) using genetic algorithms (GAs). CAs have the advantages of producing complex systems from the interaction of simple elements, and have attracted increased research interest. However, the difficulty of designing CAs transition rules to perform a particular task has severely limited their applications. The evolutionary design of CA rules has been studied by the EVCA group in detail. A GA was used to evolve CAs for two tasks: density classification and synchronization problems. That GA was shown to have discovered rules that gave rise to sophisticated emergent computational strategies. Sipper has studied a cellular programming algorithm for 2-state non-uniform CAs, in which each cell may contain a different rule. Meanwhile, Land and Belew proved that the perfect two-state rule for performing the density classification task does not exist. However, Fuks´ showed that a pair of human written rules performs the task perfectly when the size of neighborhood is one. In this paper, we consider a pair of rules and the number of rule iterations as a chromosome, whereas the EVCA group considers a rule as a chromosome. The present method is meant to reduce the complexity of a given problem by dividing the problem into smaller ones and assigning a distinct rule to each one. Experimental results for the two tasks prove that our method is more efficient than a conventional method. Some of the obtained rules agree with the human written rules shown by Fuks´. We also grouped 1000 rules with high fitness into 4 classes according to the Langtons λ parameter. The rules obtained by the proposed method belong to Class- I, II, III or IV, whereas most of the rules by the conventional method belong to Class-IV only. This result shows that the combination of simple rules can perform complex tasks.
- 2003-11-01
著者
-
狩野 均
筑波大学電子・情報工学系
-
狩野 均
筑波大学
-
鳥 云
筑波大学・システム情報工学研究科
-
狩野 均
筑波大学システム情報工学研究科コンピュータサイエンス専攻
-
烏 云
筑波大学システム情報工学研究科
関連論文
- 点字翻訳ボランティアのための対話型分かち書き支援システム
- 知識ベースに基づく点字翻訳のための日本語文節区切り手法
- 知識べースに基づく対話型点字翻訳システム
- ファジィクラスタリングに基づく道路交通量の予測方式に関する研究(セッション2)
- 遺伝的アルゴリズムによるルール変化型一次元セルオートマトンの進化
- 状態遷移規則が変化する一次元CAの密度分類問題への適応(セルオートマトン)
- CA法による広域道路交通シミュレータを用いた経路案内方式の評価(第2セッション)
- セルオートマトンとGAを用いた仮想都市の時系列的生成手法
- 制約充足問題研究支援システム
- 対話型進化計算によるポスター制作支援システムの開発
- 対話型進化計算によるポスター制作支援システムの開発
- 多目的遺伝的アルゴリズムを用いたカーナビゲーションのための予測経路探索(セッション2)
- 行動ルールが変化する人工社会の進化的設計手法
- 行動ルールが変化する人工社会の進化的設計手法
- ウイルス感染を用いた遺伝的アルゴリズムによる ニューラルネットワークの学習
- ウイルス感染を用いた遺伝的アルゴリズムによるニューラルネットワークの学習(進化的計算)
- 知識の集団を用いたGAによる不特定な立ち寄り地を含む経路探索
- 遺伝的アルゴリズムを用いたカーナビのための経路案内方式(ITS情報処理・一般)
- 遺伝的アルゴリズムを用いたカーナビのための経路案内方式
- セルオートマトンとGAを用いた仮想都市の時系列的生成手法
- 集団の再利用に基づくGAによるカーナビゲーションのための動的経路探索
- L-systemを用いた仮想都市のための道路網生成手法
- 高度道路交通システム(ITS)とAI(高度道路交通システム(ITS)とAI)
- 遺伝的アルゴリズムを用いた仮想都市のための建物配置方式 (知能情報メディア論文特集)
- セルの相互作用とGAを用いた仮想都市の生成
- 3S-8 セルの相互作用に基づく仮想都市の創発
- 5L-5 ウイルス感染を用いたGAによるカーナビのための動的経路探索
- 仮想都市生成システムのための建物配置手法の検討
- 知識ベースに基づく点字翻訳のための日本語文節区切り手法
- 制約に基づく対話型時間割編成システム
- 制約違反最少化戦略による対話型時間割編成システム
- 制約違反最少化戦略による対話型時間割編成システム
- 事前処理に k-means 法を利用したスパムフィルタの開発
- 事前処理に k-means 法を利用したスパムフィルタの開発
- 曲げ加工機能を有する板金図面生成システム
- 曲げ加工機能を有する対話型図面生成システム
- 制約違反最少化戦略に基づくハイブリッドGAによる制約充足問題の解法
- ウイルス感染を用いたハイブリッドGAによるリアルタイム経路探索
- 遺伝的アルゴリズムによる制約充足問題の解法
- 遺伝的アルゴリズムによる制約充足問題の解法
- 行動ルールが変化する人工社会の進化的設計手法(進化的計算I)
- 多目的遺伝的アルゴリズムによるカーナビゲーションのための経路探索(進化的計算)
- 仮想都市のためのL-systemによる道路網生成手法の検討
- セルオートマトンによる多値画像のノイズ低減手法 : 評価方法の検討
- セルオートマトンによる多値画像のノイズ低減手法(評価方法の検討)
- 拡張制約表現による時間割編成システム
- 三面図を対象とした知的CADシステム
- 制約充足問題の並列化効率に基づく分類
- 制約条件の構造に着目したCSPの分類方法
- 制約充足問題の併合解法における並列化の効率解析
- ニューラルネットワークの集団を用いた制約充足問題の解法
- 予測交通量に基づくアントコロニー最適化法による時間依存TSPの解法
- 予測交通量に基づくアントコロニー最適化法による時間依存TSPの解法
- 制約充足に基づく三面図理解システム
- 高速化の知識を取り入れた制約充足問題の一般解法
- ファジィc-means法による渋滞情報の補間方式(セッション3)
- 図面の直線形状による細線化歪みの除去
- 動的環境を対象とした遺伝的アルゴリズムによる実時間径路探索
- あいまいな三面図の概略理解手法
- 制約知識ベースに基づく三面図理解
- 制約充足に基づく三面図理解
- 省略のある板金三面図からの3次元モデルの復元
- 省略の含まれる三面図からの3次元モデルの復元
- 省略の含まれる三面図からの3次元モデルの復元
- 板金向き三面図入力システムの開発曲げ加工におけるコーナーの自動生成
- 知識ベースにもとづく三面図の矛盾解消
- 曲面を含む三面図の矛盾の検出と理解 : 画面理解および一般 : 画像処理・コンピュータビジョン
- 図面の生成・理解によるモデリングのためのCADシステム : 画面理解および一般 : 画像処理・コンピュータビジョン
- 曲面を含む三面図の矛盾の検出と理解
- 図面の生成・理解によるモデリングのためのCADシステム
- 曲げ加工機能を有する板金図面生成システム
- 適応型確率探索による制約充足問題の解法
- 補助線を用いない三面図からの曲面物体の復元