基本信息
- 項目名稱:
- 基于組合規(guī)則熵的元胞自動機行為研究
- 小類:
- 機械與控制
- 大類:
- 自然科學類學術論文
- 簡介:
- 本項目在分析Langton參數(shù)的基礎上提出了用組合規(guī)則熵來描述元胞規(guī)則的方法,并通過數(shù)學推理和計算機實驗的方法證明了其在進一步刻畫元胞自動機規(guī)則及其動力學行為時的有效性.
- 詳細介紹:
- 元胞自動機是von Neumann提出的一種時間、空間、狀態(tài)都離散的動力學模型.目前,它已成為非線性科學領域的一種重要研究方法,是人工生命科學研究的重要方向,其動力學行為研究也成為復雜性理論和計算普遍性研究的重要內(nèi)容.元胞自動機的應用已引起國內(nèi)外學者的高度關注,但其理論發(fā)展相對緩慢.Conway證明了元胞自動機具有通用圖靈機的計算能力,并在適當條件下可以模擬任何計算機.Wolfram在計算機實驗基礎上仿照動力系統(tǒng)理論的分類將元胞自動機演化行為定性的分為四類,由此奠定了元胞自動機動力學行為研究的理論基礎.迄今為止,引人注目的研究是Langton通過對元胞自動機規(guī)則和其動力學行為關系研究提出的Langton參數(shù)及“混沌的邊緣”. 元胞自動機研究面臨兩類問題.一是給定元胞自動機規(guī)則,分析和研究其性質(zhì);二是搜索具有指定演化類型的元胞自動機規(guī)則.但元胞自動機行為的不可判定性為這兩類問題的解決帶來了不小的困難.Langton參數(shù)通過將元胞規(guī)則空間參數(shù)化來研究元胞自動機的動力學行為,是統(tǒng)計意義下對元胞自動機規(guī)則整體性質(zhì)的刻畫.因此,即使在初始構(gòu)型一定的情況下,它對元胞自動機演化行為的描述也比較困難.圖1給出了Langton參數(shù)等于0.5,相同初始構(gòu)型下不同的元胞自動機演化行為示例.為進一步對元胞自動機規(guī)則及其動力學行為進行細致的刻畫,本文在分析Langton參數(shù)的基礎上提出了用組合規(guī)則熵來描述元胞規(guī)則的方法,并通過數(shù)學推理和計算機實驗的方法證明了其在進一步刻畫元胞自動機規(guī)則及其動力學行為時的有效性.
作品專業(yè)信息
撰寫目的和基本思路
- 元胞自動機已成為非線性科學領域的一種重要研究方法。引人注目的研究是Langton通過對元胞自動機規(guī)則和其動力學行為關系研究提出的Langton參數(shù)及“混沌的邊緣”. 本項目在分析Langton參數(shù)的基礎上提出了用組合規(guī)則熵來描述元胞規(guī)則的方法,并通過數(shù)學推理和計算機實驗的方法證明了其在進一步刻畫元胞自動機規(guī)則及其動力學行為時的有效性
科學性、先進性及獨特之處
- 元胞自動機是von Neumann提出的一種時間、空間、狀態(tài)都離散的動力學模型.本項目從信息學、數(shù)學和計算機實驗相結(jié)合的方法出發(fā),針對半徑為3的一維二值元胞自動機給出了不同Langton參數(shù)下各類型元胞自動機的分布情況并提出了用組合規(guī)則熵刻畫元胞自動機規(guī)則的方法.
應用價值和現(xiàn)實意義
- 雖然經(jīng)典數(shù)學在加法元胞自動機和初等元胞自動機的研究方面取得了一系列理論成果,但當元胞半徑變大時研究難度變大.本項目針對半徑為3的一維二值元胞自動機給出了不同Langton參數(shù)下各類型元胞自動機的分布情況并提出了用組合規(guī)則熵刻畫元胞自動機規(guī)則的方法.組合規(guī)則熵有利于在Langton參數(shù)的基礎上實現(xiàn)對元胞自動機性質(zhì)及動力學行為更為細致的刻畫,并可以提高對指定動力學演化類型的元胞自動機的搜索效率.
學術論文摘要
- 為在Langton參數(shù)的基礎上對一維二值元胞自動機的性質(zhì)及其動力學行為進行更細致的分析,提出了用組合規(guī)則熵刻畫元胞自動機規(guī)則的方法并證明了一維二值元胞自動機組合規(guī)則熵的最大值和最小值定理.實驗還進一步表明組合規(guī)則熵能夠在Langton參數(shù)的基礎上對元胞自動機的規(guī)則進行更細致的刻畫,有利于對元胞自動機動力學行為的分析和提高對指定類型元胞自動機的搜索效率.
獲獎情況
- 無
鑒定結(jié)果
- 無
參考文獻
- [1] von Neumann J.The general and logical theory of automata.New York:Wiley,1951,1-26 [2] Melanie M.Computation in cellular automata: a selected review [EB/OL]. .1-41 [3] Guisado J, Jimenez F, Fernandez F.Cellular Automata and Cluster Computing: an Application to the Simulation of Laser Dynamics.Advances in Complex System,2007,10(1):167-190 [4] Christian D,Mario G,Marco T.Performance and Roubustness of Cellular Automata Computation on Irregular Networks.Advances in Complex System,2007,10(1):85-110 [5] 周成虎,孫戰(zhàn)利,謝一春.地理元胞自動機研究.北京:科學出版社,2001,29-31 [6] Wolfram S.Computation theory of cellular automata.Communi-cations in Mathematical Physics,1984,96(1):15-57 [7] Langton C.Computation at the edge of chaos:Phase transitions and emergent computation.Physica D,1990,42(1):12-27 [8] Bastien Chopard,Michel Droz著,祝玉學,趙學龍,譯.Cellular Automata Modeling of Physical Systems.北京:清華大學出版社,2003,16-18
同類課題研究水平概述
- 元胞自動機是von Neumann提出的一種時間、空間、狀態(tài)都離散的動力學模型.目前,它已成為非線性科學領域的一種重要研究方法,應用已引起國內(nèi)外學者的高度關注,但其理論發(fā)展相對緩慢.國內(nèi)研究也剛剛起步。 采用什么手段來研究是至關重要的.本項目在Langton參數(shù)的基礎上對元胞自動機的規(guī)則進行更細致的刻畫,有利于對元胞自動機動力學行為的分析和提高對指定類型元胞自動機的搜索效率.