基于元胞自动机的植物生态仿真系统研究

为了建立植物生态系统微观与宏观之问的关联,并在多个层次上描述生态系统复杂性,文中建立了一个基于元胞自动机理论的植物生态仿真系统,以研究单植株与整体生态现象之间的关系.该方法避免了传统分析方法中直接求取单株属性与宏观统计量之间解析关系所遇到的困难,而且相较于其它模拟方法,元胞自动机理论提供了更为完善的理论框架,并且元胞空间与植物分布空间有着直接映射关系.为了说明该系统的有效性,选择了生态学中的一个实例濒危植物明党参(Changium smyrnioides)的种群生长进行了动态模拟,并选取同科的峨参(Anthriscus sylvestris)作为对照种进行了比较分析.实验分析表明,仿真系统能够较好的重现出物种个体规律和整体生态现象之间的关系,获得物种在不同生存策略上的显著差异,而且这些结果与实际生态学结论相吻合. 观统计量之间解析关系所遇到的困难,而且相较于其它模拟方法,元胞自动机理论提供了更为完善的理论框架,并且元胞空间与植物分布空问有着直接映射关系.为了说明该系统的有效性,选择了生态学中的一个实例濒危植物明党参(Changium smyrnioides)的种群生长进行了动态模拟,并选取同科的峨参(Anth iscus sylvestris)作为对照种进行了比较分析.实验分析表明,仿真系统能够较好的重现出物种个体规律和整体生态现象之间的关系,获得物种在不同生存策略上的显著差异,而且这些结果与实际生态学结论相吻合. 观统计量之间解析关系所遇到的困难,而且相较于其它模拟方法,元胞自动机理论提供了更为完善的     

人工生命及其基本原理

该文总结了人工生命的产生和发展状况,介绍了人工生命的研究对象和实现技术,讨论了人工生命和人工智能的关系。通过若干典型人工生命研究实例,分析了人工生命技术的基本原理,并用计算机程序模拟自然生态系统对人工生命的理论方法和实现技术进行了探讨。程序模拟方法在基因的遗传与优选方面有着相当的实际意义,用类似方法对各种自然生物的生命状态、生活习性进行模拟,可在较短的时间内模拟自然生命需要几千乃至上万年的进化历程。     

人工生命评述

对近年来发展的人工生命科学进行了评述。描述了人工生命的概念、主要内容、研究方法及现实意义。     

元胞自动机在"数字油田"中的应用

“数字油田”要设计一个涵盖油田全部业务活动的综合信息系统指导性框架,当作今后油田信息化建设的指南。它作为一个复杂的开放系统,适于使用元胞自动机模型来进行研究。介绍了元胞自动机的产生与原理,作为复杂性研究的新途径,探讨了元胞自动机在“数字油田”中的应用并做了复杂性分析。     

Complexity of reachability problems for finite discrete dynamical systems

Sequential Dynamical Systems (SDSs) are a special type of finite discrete dynamical systems that can be used to model simulation systems. We focus on the computational complexity of testing several phase space properties of SDSs. Our main result is a sharp delineation between classes of SDSs whose behavior is easy to predict and those whose behavior is hard to predict. Specifically, we show the following.

1.

Several state reachability problems for SDSs are PSPACE-complete, even when restricted to SDSs whose underlying graphs are of bounded bandwidth (and hence of bounded pathwidth and treewidth), and the function associated with each node is symmetric. Moreover, this result holds even when the underlying graph is d-regular for some constant d and all the nodes compute the same symmetric Boolean function. An immediate corollary of this result is a PSPACE-hard lower bound on the complexity of reachability problems for regular generalized 1D-Cellular Automata and undirected systolic networks with Boolean totalistic local transition functions.

2.

In contrast, the above reachability problems are solvable in polynomial time for SDSs when the Boolean function associated with each node is symmetric and monotone.

The PSPACE-completeness results follow as corollaries of simulation results which show for several classes of SDSs, how one class of SDSs can be efficiently simulated by another (more restricted) class of SDSs. We also prove several structural properties concerning the phase space of an SDS. SDSs are closely related to Cellular Automata (CA), concurrent transition systems, discrete Hopfield networks and systolic networks. This observation in conjunction with our lower bounds for SDSs, yields new PSPACE-hard lower bounds on the complexity of state reachability problems for these models, extending some of the earlier results in [K. Culik II, J. Karhumäki, On totalistic systolic networks, Inform. Process. Lett. 26 (5) (1988) 231-236; P. Floréen, E. Goles, G. Weisbuch, Transient length in sequential iterations of threshold functions, Discrete Appl. Math. 6 (1983) 95-98; P. Floréen, P. Orponen, Complexity issues in discrete Hopfield networks, Research Report No. A-1994-4, Department of Computer Science, University of Helsinki, 1994. Also appears in: I. Parberry (Ed.), Comp. and Learning Complexity of Neural Networks: Advanced Topics, 1999; D. Harel, O. Kupferman, M.Y. Vardi, On the complexity of verifying concurrent transition systems, Inform. and Comput. 173 (2002) 143-161; S.K. Shukla, H.B. Hunt III, D.J. Rosenkrantz, R.E. Stearns, On the complexity of relational problems for finite state processes, in: International Colloquium on Automata Programming and Languages, ICALP, 1996, pp. 466-477; A. Rabinovich, Complexity of equivalence problems for concurrent systems of finite agents, Inform. and Comput. 127 (2) (1997) 164-185].     

基于元胞自动机的人工金融市场及其仿真研究

该文通过对金融市场复杂性的分析,并基于元胞自动机和争当少数者模型提出了一个开放的金融预测模型。模型中的投资者相当于争当少数者模型里的agent,每个投资者都必须从初始时各自定义的策略集合中选择最成功的作为每一步的预测策略。同样,投资者也相仿于元胞自动机中的元胞,而选定的预测策略就作为元胞的局部规则,每个元胞都根据局部信息和局部规则做出估价。模型的最终预测值就是由数千个这样的投资者决定的。此模型是开放性的,因为可以通过扩充或重构其预测策略库来获得更精确的预测结果。数值实验显示,虽然策略库比较简单,但其预测的平均相对误差仅为1．73％。     

Constructible functions in cellular automata and their applications to hierarchy results

We investigate time-constructible functions in one-dimensional cellular automata (CA). It is shown that (i) if a function t(n) is computable by an O(t(n)−n)-time Turing machine, then t(n) is time constructible by CA and (ii) if two functions are time constructible by CA, then the sum, product, and exponential functions of them are time constructible by CA. As an application, it is shown that if t₁(n) and t₂(n) are time constructible functions such that lim_n→∞ t₁(n)/t₂(n) = 0 and t₁(n)n, then there is a language which can be recognized by a CA in t₂(n) time but not by any CA in t₁(n) time.     

复杂适应系统理论与计算机作战模拟

该文介绍了CAS理论的基本思想,对以往的作战模拟手段存在的缺欠和应用CAS理论于作战模拟的优势进行了分析,并对应用CAS理论的计算机平台进行了讨论。以此为基础,建立仿真模型。针对这一模型,说明CAS理论在军事仿真中的其他应用。     

改进的基于元胞自动机扩展模型的图的最短路径算法

在基于元胞自动机单源点到单节点图的最短路算法的基础之上,通过改进控制演化的终止条件和记录演化过程中的路径信息,提出了单源点到多节点的元胞自动机扩展模型求解图的最短路算法模型，将该算法应用于城市道路交通网的实证研究之中,可以得到路段上任意两端点之间的最短路径及路权。