Calc_Temp: A pragmatic algorithm to classify 2D-NTCA // Calc_Temp:一个实用性的2D-NTCA 分类器

I recently integrated my understanding of spatial fluctuation to produce a automatic classifier for 2D non-totalistic cellular automata. It’s now available as a git repository. I am seeking to implement it on a web server in the near future.

github repo

An example of output is shown here

On the discovery of density fluctuation in Cellular Automata//写在发现元胞自动机密度涨落之际

这个想法是在2017年3月7日凌晨,在伦敦的一台HP_Z600上初步实现的。整个发现的过程还是挺戏剧性的。

背景:

在这之前的一个月里我在MATLAB上断断续续从转移矩阵(transfer matrix)开始编起,发现没啥卵结果,然后在一篇文献上重新看到了Derrida Plot,也就是离散版本的Lyapunov Exponent,然后心中暗骂“Derrida这死脑筋干嘛要取平均值啊?”,并且在这样的心情中编写了derrida_general.m架构出了一个面向对象的流程结构,并且用协方差作为一个伪距离函数替代了平均值,获得了更多的信息。 这个时候的算法还是给了我一点小惊喜的,这直接导致我花了一个星期浏览它生成的Profile图片,大概收集了500条左右的有趣CA规则。但是浏览久了发现不对劲啊,这到底是我在筛选CA还是我的程序在筛选CA啊擦。(当然这个问题从我开始写算法时就一直有,也就是说算法的敏感度不错,真阳性基本都能检测到,但是假阳性也一堆一堆的,只有靠人工筛除)。

思维跳跃如我,结合信息学最近上课学的多序列对齐(Multiple Sequence Alignment)猜想,能不能把CA的规则看成一条遗传信息,并且比较小的变异对其动力学性质的影响? 一方面也希望能把MSA的想法应用进来,给出一个隐马尔可夫Profile,将会是一个非常漂亮的结果。随机变异过程倒是比较容易写,一两天就写完了,难在控制Alignment的深度,因为有些CA规则对变异一点都不敏感,18个比特你变掉三个它都无所谓,导致生成了巨大的团状Alignment,这个必须用算法进行控制。另一方面对这个树状图进行操作也需要一些新的编程技巧,以达到比较好的并行计算优化。 同时还花了三天帮室友修他的外星人,在EFI引导上栽了个大跟头,不过好在最后总算修好了Windows/Linux双系统。修系统无聊时就在琢磨把树状图显示出来,因为节点和连边一多起来Matlab的可视化就变得很慢,最后用vis.js做出了“毛毛毛球”

然后我兴致冲冲地就去做随机测试了,结果……没卵用……仅仅发现了一些小的结论,比如B3/S23的18个比特里面有4个比特的变异是不太影响它的动力学的,其中两个的影响大一点(B7,S7的变异),另外两个的变异几乎不产生影响(B8,S8),我称之为a2b2型。有趣/糟糕的是,a2b2型简直满地都是,但是和B3/S23的动力学性质没有半毛钱关系,我只好太息而弃。

但是这里的另一个观察是,有一些强稳定的动力学可以经受7-8个比特的变异,给出~128左右的团簇。 我据此写了一个专门探测这些强稳规则的团簇边界,再找出混沌团簇的边界,以期在这两个团簇的交界处找到复杂的动力学性质,但是目前来看效果并不是特别好。

故事:

周一(03/06)早上正在改进团簇边界的算法,最后发现效果并不好,下午四点赶去上了一节动力系统的课程,结果老师貌似心情也不好一直在讲浅显/糟糕的废话,介绍了极限环理论,但是估计没有一个人听懂。他是学物理出身的,结果讲的时候一直在提系统论的概念,比如负反馈啊,延迟反馈啊,非线性啊,结果在座的这群生物狗估计一句都没听进去。。。然后老师提了个总结性问题:动力系统的极限环振荡解和谐振动的区别是?在座一片死机。 正解是:极限环震荡解的性质不依赖系统的初始状态,但是谐振子解的性质是虽初始状态而改变的,往深了讲是因为谐振子作为线性系统是保守的(Conservative),而极限环往往是耗散(Dissipative)系统的渐进解,这本来是鲁棒性的一个极好体现,结果他对着生物狗强调了半天内部的数学结构。。。但是吧,非线性和生物之间到底有啥关系,的确也很难说请,老师对Hill Function的介绍还是很到位的,虽然他没能解释Hill的非线性和系统的鲁棒性到底有啥关系。

上完了课肚子饿,不想回家,图书馆(Sci-Lib)浓浓的新生气息,编程没结果,死线就在周三,缺乏睡眠,你大概可以想像我到了一个多糟的境地。 为了防止把更多的时间浪费在方向不明的Coding上,我强迫自己在外面走走,恰巧ULU Student Hub 三楼在排练爵士乐,我就爬上去听了听,站在窗口看楼下过往的行人,放松放松:信号的本质是什么呢?伦敦的夜景我很少这样观察,远处WellcomeTrust的大楼闪烁着现代性,近处King’s Church沉默在黑暗里。第一次,我站在这个高度俯瞰天天走过的Malet Street。 不断地搜索记忆,我想找出一丝线索: DerridaPlot之所以有用,FamilyTree之所以能被建构,背后靠的都是相关性函数,更进一步,FamilyTree比较的是同样的初始条件在两条相似的规则下的结果,并合并大量样本取一个协方差,但这个过程中所有的比特位都没有区别了。联想之前实践的平均场近似,只把0/1密度提取出来作为参数,而不关心具体的排列方式,这样处理CA显然是不妥当的,而且根据我之前的实验,如果把CA不断重新随机混合,得到的结果是非常符合平均场给出的结果的,但是一旦我去掉随机混合这个过程,平均场给出的近似和CA本身的动力学就没有半毛钱关系,这说明CA的空间不均匀性是非常核心的东西。同样的,如果对二维Ising不断进行混合/重排,其能量显然也不是不变的。取极端例子,本来是随机白噪音,假设重排成了一堆0和一堆1,显然能量有很大改变,所以Ising模型也是对空间不均匀性很敏感的。

接下来就想怎么把CA的空间不均匀性抽象出来,于是想到了对同一个比特取一个延时摄影,并且取其平均为密度。本来这个操作的目的是移除闪光(Strobing)和高频闪烁的,但是很凑巧的是在真正Implement的过程中这个操作居然真的记录了空间不均性,也就是涨落。或者说,得到这个密度参数以后,只要观察这个密度在时间和空间上的统计行为,就能反映CA的动力学性质,而不取密度参直接用0/1(应该)是得不到这样的结果的,或者说会出一些别的问题。 当然这个算法也不完美,取0/1平均是有一定问题的,因为不同顺序相同密度的0/1序列蕴含的信息不一定相等,但是取0/1密度再做协方差的确是最简单最快的Implementation(相比共信息而言)。

先写道这里,写完作业再来补。