2009-8-20 高级人工智能 史忠植 1
第十二章 人工生命史忠植中科院计算所
2009-8-20 高级人工智能 史忠植 2
内容
12.1 引言
12.2 研究人工生命的原因
12.3 人工生命的探索
12.4 人工生命的模型
12.5 人工生命的研究方法和战略
12.6 计算机生命
12.7 细胞自动机
12.8 形态形成理论
12.9 混沌理论
2009-8-20 高级人工智能 史忠植 3
12.1 引言人工生命定义 1
研究具有自然生命系统行为的人造系统。
2009-8-20 高级人工智能 史忠植 4
人工生命定义 2
人工生命是研究怎样通过抽取生物现象中的基本动力规则来理解生命，并且在物理媒体如计算机上重建这些现象，使它们成为一种新的实验方式和受操纵。
2009-8-20 高级人工智能 史忠植 5
人工生命定义 3
在人工生命中的所有存在或将会存在的事物中，我们至少可以说这一领域从总体来说，代表了一种尝试，就是加重了生物学中合成理论的分量。
2009-8-20 高级人工智能 史忠植 6
人工生命定义 4
人工生命模型有足够强大的功能来获取复杂系统中更多的认知。这种方式较之自然系统更容易被操纵、重复和精确控制实验
。
2009-8-20 高级人工智能 史忠植 7
人工生命人工生命是指用计算机和精密机械等生成或构造表现自然生命系统行为特点的仿真系统或模型系统。自然生命系统的行为特点表现为自组织、自修复、自复制的基本性质，以及形成这些性质的混沌动力学、环境适应和进化。
在现实世界中，普遍地存在着各类复杂系统，一般认为，非线性、不稳定性、
不确定性是造成复杂性的根源。复杂事物只能照它复杂的面貌来理解。
2009-8-20 高级人工智能 史忠植 8
相关会议
7th International Conference on Artificial Life （ The
Seventh International Conference on the Simulation and
Synthesis of Living Systems ） Reed College,Portland,
Oregon,USA,1-6 August 2000
"Looking Backward,Looking Forward"
6th International Conference on Artificial Life
4th International Conference on Artificial Life
3rd International Conference on Artificial Life
2nd International Conference on Artificial Life
1st International Conference on Artificial Life,1987
2009-8-20 高级人工智能 史忠植 9
相关刊物
Artificial Life (MIT Press)
Adaptive Behavior (MIT Press)
Artificial Life and Robotics (Springer Verlag)
Advances in Complex Systems (formerly Journal of Complex
Systems) (Editions Hermes)
Biological Cybernetics (Springer Verlag)
Complexity (Wiley)
Cybernetics & Systems Analysis (Plenum)
Evolution (Society for the Study of Evolution)
Evolution of Communication (John Benjamins Publishing Co.)
Evolutionary Computation (MIT Press)
2009-8-20 高级人工智能 史忠植 10
相关刊物
IEEE Transactions on Evolutionary Computation (IEEE)
IEEE Transcations on Fuzzy Systems (IEEE)
IEEE Transactions on Neural Networks (IEEE)
IEEE Transactions on Systems,Man,and Cybernetics B,
Cybernetics (IEEE)
Journal of Complexity (Academic Press)
Journal of Social and Evolutionary Systems (JAI)
Journal of Theoretical Biology (Academic)
Kybernetes (MCB)
Open Systems & Information Dynamics (Kluwer)
2009-8-20 高级人工智能 史忠植 11
AI vs,AL
1,Complex human
functions
2,Top-down
3,Global Control
4,Complex Rules
5,Preprogrammed
behavior
6,Knowledge-
Representation
1,Basic natural
behavior
2,Bottom-up
3,Local Control
4,Simple Rules
5,Emergent behavior
6,Avoid Knowledge-
Representation &
Planning
2009-8-20 高级人工智能 史忠植 12
12.2 研究人工生命的原因
人工生命的研究可使我们更好地理解突发特征，个体在低级组织中的集合，通过我们的相互作用，常可产生特征。
人工生命将会成为研究生物的一个特别有用的工具。
对于发展新技术及增强我们控制自然的能力，人工生命系统是很有潜力的。
人工生命的另一显著应用是遗传工程。
2009-8-20 高级人工智能 史忠植 13
12.3 人工生命的探索
20世纪初，逻辑在算术机械运算中的运用，导致过程的抽象形式化。
40年代末,50年代初，冯,诺伊曼提出了机器自增长的可能性理论。以计算机为工具，迎来了信息科学的发展。
70年代以来，科拉德 (Conrad)和他的同事研究人工仿生系统中的自适应、进化和群体动力学，提出了不断完善的“人工世界”模型。
80年代，人工神经网络又兴起，出现了许多神经网络模型和学习算法。与此同时，人工生命的研究也逐渐兴起。 1987年召开了第一届国际人工生命会议。
2009-8-20 高级人工智能 史忠植 14
12.4 人工生命的模型
1,计算机病毒
2,计算机的进程
3,生物统计学和个体胎生学
4,机器人
5,自催化 (autocatalytic)网络
6,细胞自动机
7,人工核苷酸
2009-8-20 高级人工智能 史忠植 15
12.5 人工生命的研究方法和战略按照人工生命的组织机构，人工生命的内容大致可以分成两类：
1) 构成生物体的内部系统，包括脑、神经系统、内分泌系统、免疫系统、遗传系统、
酶系统、代谢系统等。
2) 在生物体及其群体中表现的外部系统。生物群体中环境适应系统和遗传进化系统等。
2009-8-20 高级人工智能 史忠植 16
1) 模型法。
根据内部和外部系统所表现的生命行为，
建造信息模型。
2) 工作原理法。
生命行为所显示的自律分散和非线性的行为，它的工作原理是混沌和分形，据此研究它的机理。
人工生命研究的方法
2009-8-20 高级人工智能 史忠植 17
1) 采用以计算机等信息处理机器为中心的硬件生成生命行为。
一种是采用已有的信息处理机器和执行装置，实现具有人工生命行为的系统。
另一种是用生物器件构造生命系统。这些都通称为生物计算机，
是一种向人工生命接近的方法。
2) 用计算机仿真，研究开发显示生命体特征行为的模型软件。简单地说，
神经网络系统和遗传算法等，都是采用信息数学模型，模拟人工生命的生成。
3) 基于工作原理，利用计算机仿真生成生命体。生命现象的基础是随物理熵的增大而杂乱无章。生成这种现象的原理是混沌的分形、耗散结构、协同反应等，采用这些产生生命现象。
4) 通过计算机仿真，分析生命特有的行为生成，建立新的理论。利用上面 3个策略，得到生命行为共同的一般性质，通过概括，建立生命的基本理论。这种策略形成自组织、超并行处理等理论。
人工生命研究的策略
2009-8-20 高级人工智能 史忠植 18
生命系统中的一些最重要的特性是：
生命体的复杂性和组织；
构成它们的分子的化学结构唯一性；
单个生命体的唯一性及变异；
拥有遗传程序，最终形成遗传表现型；
通过自然选择形成；
行为的明显不确定性。
12.6 计算机生命
2009-8-20 高级人工智能 史忠植 19
细胞自动机 (CA)是另一种对结构递归应用简单规则组的例子 。 在细胞自动机中,被改变的结构是整个有限自动机格阵 。 在这种情况下,局部规则组是传递函数,在格阵中的每个自动机是同构的 。 所考虑修改的局部上下文是当时邻近的自动机的状态 。
自动机的传递函数构造一种简单的,离散的空间 /
时间范围的局部物理成分 。 要修改的范围里采用局部物理成分对其结构的,细胞,重复修改 。 这样,尽管物理结构本身每次并不发展,但是状态在变化 。
12.7 细胞自动机
2009-8-20 高级人工智能 史忠植 20
细胞自动机元胞自动机 —产生和发展,四个阶段,
1940s 诞生,Von Neumann 自我复制机,
1960-70s起步,JH.Conway 生命游戏,
1980s 理论研究,S.Wolfram CA分类,
1980-90s 应用,HPP-FHP格子气自动机,
C.Langton N.Packard 人工生命
2009-8-20 高级人工智能 史忠植 21
记 V为细胞状态集,V中有一元素
v0为静止状态，定义 f是
V*V*…*V → V的函数,且满足
f(v0,v0,…,v0)=v0,
则 (V,v0,f)称为是 m个邻居的细胞自动机,f 称为该细胞自动机的变换函数。
二维空间中的细胞自动机
2009-8-20 高级人工智能 史忠植 22
信号传播的过程
2 2 2 2 2 2
1 1 0 s 1 1
2 2 2 2 2 2
2 2 2 2 2 2
1 1 1 0 s 1
2 2 2 2 2 2
2009-8-20 高级人工智能 史忠植 23
信号复制
2 2 2 2 2 2
1 0 s 1 1 1
2 2 1 2 2 2
* 2 1 2 * *
* 2 1 2 * *
2 2 2 2 2 2
1 1 0 s 1 1
2 2 s 2 2 2
* 2 1 2 * *
* 2 1 2 * *
2 2 2 2 2 2
1 1 1 0 s 1
2 2 0 2 2 2
* 2 s 2 * *
* 2 1 2 * *
时刻 T 时刻 T+1 时刻 T+2
2009-8-20 高级人工智能 史忠植 24
数据路径扩张
2 2 2 2 2 2 2 2
1 1 0 6 1 1 1 1
2 2 2 2 6 2 2 2
* * * 2 0 2 * *
* * * 2 1 2 * *
* * * 2 1 2 * *
2 2 2 2 2 2 2 2
1 1 1 0 7 1 1 1
2 2 2 2 0 2 2 2
* * * 2 1 2 * *
* * * 2 1 2 * *
* * * 2 1 2 * *
2009-8-20 高级人工智能 史忠植 25
f(0,1,2,7,6)=1 f(7,0,0,0,2)=3 f(2,0,0,2,3)=7 f(1,0,2,3,2)=6
f(0,1,2,3,2)=1 f(3,0,2,2,1)=0 f(7,0,2,1,2)=0 f(1,0,7,2,2)=3
f(4,0,2,0,2)=2 f(2,0,0,2,4)=0 f(2,0,2,6,2)=4 f(2,0,0,1,4)=2
f(4,0,2,6,2)=2 f(2,0,4,6,2)=4 f(1,2,4,2,6)=4 f(4,1,2,2,2)=0
f(2,0,0,4,2)=0 f(2,0,2,4,2)=0 f(2,0,1,2,4)=2 f(6,0,2,4,2)=4
f(7,0,0,2,1)=0 f(0,1,2,7,2)=4
变换规则表
2009-8-20 高级人工智能 史忠植 26
首先我们有一细胞空间，它组成了 N维欧几里德空间，
以及定义于该细胞空间的邻居关系。对于每个细胞空间，由于邻居关系，必有有限个细胞作为它的邻居。一个细胞自动机系统 (简称“细胞系统” )是这样定义的：该系统对每个细胞给定有限个状态和一个区分状态 (叫“空状态” )，及一条规则。该规则给出每个细胞在时刻 T+1时的状态，且该规则是在时间 t时该细胞自身的状态及它的邻居的状态的函数。我们把一个细胞的所有可能状态连同管理该细胞的状态变换的规则一起称为一个变换函数。所以一个细胞自动机系统是由一个细胞空间和定义于该空间上的变换函数所组成。细胞自动机状态由有限个细胞连同赋于每个细胞的状态所指定，可理解为其它的细胞都处于空的状态。
细胞自动机的概念可由以下方式建立
2009-8-20 高级人工智能 史忠植 27
典型的形态形成理论是 1968年 Lindenmayer提出的 L-系统。 L-系统由一组符号串的重写规则组成，它与乔姆斯基 (Chomsky)形式语法有密切关系。
在下面,X→ Y”表示结构中当出现 X时用字符串 Y
代替。因为字符 X可以出现在规则的右边和左边，
这组规则可以被递归地应用来重写新的结构。
12.8 形态形成理论
2009-8-20 高级人工智能 史忠植 28
形态形成理论规则采用上下文无关,即在特定部分改变时不考虑上下文中的关系 。 例如一组规则：
(1) A? CB
(2) B? A
(3) C? DA
(4) D? C
2009-8-20 高级人工智能 史忠植 29
当把这组规则用于初始种子结构,A”,就可以得到下面的序列：
次数 结构 应用规则
0 A 初始种子
1 C B 规则 1,CB 代替 A
2 D A A 规则 3,DA代替 C; 规则 2,A代替 B
3 C C B C B 规则 4,C代替 D; 规则 1用两次,CB代替 A
4 … 继续进行例子 1
2009-8-20 高级人工智能 史忠植 30
规则,(1) A → C[B]D
(2) B → A
(3) C → C
(4) D → C(E)A
(5) E → D
当把这组规则用于初始种子结构,A”,就可以得到下面的序列：
次数 结构 应用规则
0 A 开始种子
1 C[B]D 规则 1,
2 C[A]C(E)A 规则 3,2,4.
3 C[C[B]D]C(D)C[B]D 规则 3,1,3,5,1.
4 C[C[A]C(E)A]C(C(E)A)C(E)A 规则 3,3,2,4,3,4,3,2,3.
例子 2
2009-8-20 高级人工智能 史忠植 31
规则,(1) [{C} → C 在字符串左端的,C”保持,C”
(2) C{C} → C,C”和它左端的,C”保持,C”
(3) *{C} → *,C”和它左端的,*”变成,*”
(4) {*}C → C,*”和右端的,C”变成,C”
(5) {*}] → * 在字符串右端的,*”保持,*”
在这些规则下，初始结构,*CCCCCCC”将产生向右传播：
次数 结构
0 *CCCCCCC
1 C*CCCCCC
2 CC*CCCCC
3 CCC*CCCC
4 CCCC*CCC
5 CCCCC*CC
6 CCCCCC*C
7 CCCCCCC*
例子 3
2009-8-20 高级人工智能 史忠植 32
从系统角度来看生命的行为，首先在物理上可以定义为非线性、
非平衡的开放系统。所以，这种系统特殊行为是自然振荡，即有限周期和混沌。这些生命特有的行为是本体主义和高级信息处理所关注的，
人工生命中，它的生成原理是主要的。有限周期可以分为稳定的和不稳定的。把自然振荡称为稳定的有限周期。这种稳定的有限周期邻近的位相面轨道渐近闭轨道。有限振荡和混沌是结构稳定的两个方面。
它们的差别仅仅在于有限周期的初始条件的差对于以后运动影响很大。
在混沌中，初始条件的差随着时间很快扩大，近似再现是困难的。这种性质称为轨道不稳定性，这和基于有限周期的轨道稳定性的有序化形成明显对照。自然界中动力学分为有序和混沌。有序的规则行为是周期解。其它混沌系统是复杂的，长期不能预测的行为。两者从时间发展上基本上是动力学系统。所以，生命体是混沌和有序的复合。
12.9 混沌理论
2009-8-20 高级人工智能 史忠植 33
混沌理论生命行为所提取的特征现象的发生原理的有序和混沌的计算能力怎样呢 。 首先,有序系统具有在它的周期上的复杂性,高度的复杂计算是不可能的 。 混沌系统必须有严格的规定,从理论上计算它的轨道的不稳定性行为是困难的,因此,仅考虑在混沌的边界所看到的生命行为 。 这样,信息的存储,传送,变换之类的基本操作可以通过有序和混沌的混合系统实现：
(1) 信息存储是从有序系统所看到的稳定周期动力学获得 。
(2) 信息的传送和变换可以从混沌系统不稳定动力学实现 。
第十二章 人工生命史忠植中科院计算所
2009-8-20 高级人工智能 史忠植 2
内容
12.1 引言
12.2 研究人工生命的原因
12.3 人工生命的探索
12.4 人工生命的模型
12.5 人工生命的研究方法和战略
12.6 计算机生命
12.7 细胞自动机
12.8 形态形成理论
12.9 混沌理论
2009-8-20 高级人工智能 史忠植 3
12.1 引言人工生命定义 1
研究具有自然生命系统行为的人造系统。
2009-8-20 高级人工智能 史忠植 4
人工生命定义 2
人工生命是研究怎样通过抽取生物现象中的基本动力规则来理解生命，并且在物理媒体如计算机上重建这些现象，使它们成为一种新的实验方式和受操纵。
2009-8-20 高级人工智能 史忠植 5
人工生命定义 3
在人工生命中的所有存在或将会存在的事物中，我们至少可以说这一领域从总体来说，代表了一种尝试，就是加重了生物学中合成理论的分量。
2009-8-20 高级人工智能 史忠植 6
人工生命定义 4
人工生命模型有足够强大的功能来获取复杂系统中更多的认知。这种方式较之自然系统更容易被操纵、重复和精确控制实验
。
2009-8-20 高级人工智能 史忠植 7
人工生命人工生命是指用计算机和精密机械等生成或构造表现自然生命系统行为特点的仿真系统或模型系统。自然生命系统的行为特点表现为自组织、自修复、自复制的基本性质，以及形成这些性质的混沌动力学、环境适应和进化。
在现实世界中，普遍地存在着各类复杂系统，一般认为，非线性、不稳定性、
不确定性是造成复杂性的根源。复杂事物只能照它复杂的面貌来理解。
2009-8-20 高级人工智能 史忠植 8
相关会议
7th International Conference on Artificial Life （ The
Seventh International Conference on the Simulation and
Synthesis of Living Systems ） Reed College,Portland,
Oregon,USA,1-6 August 2000
"Looking Backward,Looking Forward"
6th International Conference on Artificial Life
4th International Conference on Artificial Life
3rd International Conference on Artificial Life
2nd International Conference on Artificial Life
1st International Conference on Artificial Life,1987
2009-8-20 高级人工智能 史忠植 9
相关刊物
Artificial Life (MIT Press)
Adaptive Behavior (MIT Press)
Artificial Life and Robotics (Springer Verlag)
Advances in Complex Systems (formerly Journal of Complex
Systems) (Editions Hermes)
Biological Cybernetics (Springer Verlag)
Complexity (Wiley)
Cybernetics & Systems Analysis (Plenum)
Evolution (Society for the Study of Evolution)
Evolution of Communication (John Benjamins Publishing Co.)
Evolutionary Computation (MIT Press)
2009-8-20 高级人工智能 史忠植 10
相关刊物
IEEE Transactions on Evolutionary Computation (IEEE)
IEEE Transcations on Fuzzy Systems (IEEE)
IEEE Transactions on Neural Networks (IEEE)
IEEE Transactions on Systems,Man,and Cybernetics B,
Cybernetics (IEEE)
Journal of Complexity (Academic Press)
Journal of Social and Evolutionary Systems (JAI)
Journal of Theoretical Biology (Academic)
Kybernetes (MCB)
Open Systems & Information Dynamics (Kluwer)
2009-8-20 高级人工智能 史忠植 11
AI vs,AL
1,Complex human
functions
2,Top-down
3,Global Control
4,Complex Rules
5,Preprogrammed
behavior
6,Knowledge-
Representation
1,Basic natural
behavior
2,Bottom-up
3,Local Control
4,Simple Rules
5,Emergent behavior
6,Avoid Knowledge-
Representation &
Planning
2009-8-20 高级人工智能 史忠植 12
12.2 研究人工生命的原因
人工生命的研究可使我们更好地理解突发特征，个体在低级组织中的集合，通过我们的相互作用，常可产生特征。
人工生命将会成为研究生物的一个特别有用的工具。
对于发展新技术及增强我们控制自然的能力，人工生命系统是很有潜力的。
人工生命的另一显著应用是遗传工程。
2009-8-20 高级人工智能 史忠植 13
12.3 人工生命的探索
20世纪初，逻辑在算术机械运算中的运用，导致过程的抽象形式化。
40年代末,50年代初，冯,诺伊曼提出了机器自增长的可能性理论。以计算机为工具，迎来了信息科学的发展。
70年代以来，科拉德 (Conrad)和他的同事研究人工仿生系统中的自适应、进化和群体动力学，提出了不断完善的“人工世界”模型。
80年代，人工神经网络又兴起，出现了许多神经网络模型和学习算法。与此同时，人工生命的研究也逐渐兴起。 1987年召开了第一届国际人工生命会议。
2009-8-20 高级人工智能 史忠植 14
12.4 人工生命的模型
1,计算机病毒
2,计算机的进程
3,生物统计学和个体胎生学
4,机器人
5,自催化 (autocatalytic)网络
6,细胞自动机
7,人工核苷酸
2009-8-20 高级人工智能 史忠植 15
12.5 人工生命的研究方法和战略按照人工生命的组织机构，人工生命的内容大致可以分成两类：
1) 构成生物体的内部系统，包括脑、神经系统、内分泌系统、免疫系统、遗传系统、
酶系统、代谢系统等。
2) 在生物体及其群体中表现的外部系统。生物群体中环境适应系统和遗传进化系统等。
2009-8-20 高级人工智能 史忠植 16
1) 模型法。
根据内部和外部系统所表现的生命行为，
建造信息模型。
2) 工作原理法。
生命行为所显示的自律分散和非线性的行为，它的工作原理是混沌和分形，据此研究它的机理。
人工生命研究的方法
2009-8-20 高级人工智能 史忠植 17
1) 采用以计算机等信息处理机器为中心的硬件生成生命行为。
一种是采用已有的信息处理机器和执行装置，实现具有人工生命行为的系统。
另一种是用生物器件构造生命系统。这些都通称为生物计算机，
是一种向人工生命接近的方法。
2) 用计算机仿真，研究开发显示生命体特征行为的模型软件。简单地说，
神经网络系统和遗传算法等，都是采用信息数学模型，模拟人工生命的生成。
3) 基于工作原理，利用计算机仿真生成生命体。生命现象的基础是随物理熵的增大而杂乱无章。生成这种现象的原理是混沌的分形、耗散结构、协同反应等，采用这些产生生命现象。
4) 通过计算机仿真，分析生命特有的行为生成，建立新的理论。利用上面 3个策略，得到生命行为共同的一般性质，通过概括，建立生命的基本理论。这种策略形成自组织、超并行处理等理论。
人工生命研究的策略
2009-8-20 高级人工智能 史忠植 18
生命系统中的一些最重要的特性是：
生命体的复杂性和组织；
构成它们的分子的化学结构唯一性；
单个生命体的唯一性及变异；
拥有遗传程序，最终形成遗传表现型；
通过自然选择形成；
行为的明显不确定性。
12.6 计算机生命
2009-8-20 高级人工智能 史忠植 19
细胞自动机 (CA)是另一种对结构递归应用简单规则组的例子 。 在细胞自动机中,被改变的结构是整个有限自动机格阵 。 在这种情况下,局部规则组是传递函数,在格阵中的每个自动机是同构的 。 所考虑修改的局部上下文是当时邻近的自动机的状态 。
自动机的传递函数构造一种简单的,离散的空间 /
时间范围的局部物理成分 。 要修改的范围里采用局部物理成分对其结构的,细胞,重复修改 。 这样,尽管物理结构本身每次并不发展,但是状态在变化 。
12.7 细胞自动机
2009-8-20 高级人工智能 史忠植 20
细胞自动机元胞自动机 —产生和发展,四个阶段,
1940s 诞生,Von Neumann 自我复制机,
1960-70s起步,JH.Conway 生命游戏,
1980s 理论研究,S.Wolfram CA分类,
1980-90s 应用,HPP-FHP格子气自动机,
C.Langton N.Packard 人工生命
2009-8-20 高级人工智能 史忠植 21
记 V为细胞状态集,V中有一元素
v0为静止状态，定义 f是
V*V*…*V → V的函数,且满足
f(v0,v0,…,v0)=v0,
则 (V,v0,f)称为是 m个邻居的细胞自动机,f 称为该细胞自动机的变换函数。
二维空间中的细胞自动机
2009-8-20 高级人工智能 史忠植 22
信号传播的过程
2 2 2 2 2 2
1 1 0 s 1 1
2 2 2 2 2 2
2 2 2 2 2 2
1 1 1 0 s 1
2 2 2 2 2 2
2009-8-20 高级人工智能 史忠植 23
信号复制
2 2 2 2 2 2
1 0 s 1 1 1
2 2 1 2 2 2
* 2 1 2 * *
* 2 1 2 * *
2 2 2 2 2 2
1 1 0 s 1 1
2 2 s 2 2 2
* 2 1 2 * *
* 2 1 2 * *
2 2 2 2 2 2
1 1 1 0 s 1
2 2 0 2 2 2
* 2 s 2 * *
* 2 1 2 * *
时刻 T 时刻 T+1 时刻 T+2
2009-8-20 高级人工智能 史忠植 24
数据路径扩张
2 2 2 2 2 2 2 2
1 1 0 6 1 1 1 1
2 2 2 2 6 2 2 2
* * * 2 0 2 * *
* * * 2 1 2 * *
* * * 2 1 2 * *
2 2 2 2 2 2 2 2
1 1 1 0 7 1 1 1
2 2 2 2 0 2 2 2
* * * 2 1 2 * *
* * * 2 1 2 * *
* * * 2 1 2 * *
2009-8-20 高级人工智能 史忠植 25
f(0,1,2,7,6)=1 f(7,0,0,0,2)=3 f(2,0,0,2,3)=7 f(1,0,2,3,2)=6
f(0,1,2,3,2)=1 f(3,0,2,2,1)=0 f(7,0,2,1,2)=0 f(1,0,7,2,2)=3
f(4,0,2,0,2)=2 f(2,0,0,2,4)=0 f(2,0,2,6,2)=4 f(2,0,0,1,4)=2
f(4,0,2,6,2)=2 f(2,0,4,6,2)=4 f(1,2,4,2,6)=4 f(4,1,2,2,2)=0
f(2,0,0,4,2)=0 f(2,0,2,4,2)=0 f(2,0,1,2,4)=2 f(6,0,2,4,2)=4
f(7,0,0,2,1)=0 f(0,1,2,7,2)=4
变换规则表
2009-8-20 高级人工智能 史忠植 26
首先我们有一细胞空间，它组成了 N维欧几里德空间，
以及定义于该细胞空间的邻居关系。对于每个细胞空间，由于邻居关系，必有有限个细胞作为它的邻居。一个细胞自动机系统 (简称“细胞系统” )是这样定义的：该系统对每个细胞给定有限个状态和一个区分状态 (叫“空状态” )，及一条规则。该规则给出每个细胞在时刻 T+1时的状态，且该规则是在时间 t时该细胞自身的状态及它的邻居的状态的函数。我们把一个细胞的所有可能状态连同管理该细胞的状态变换的规则一起称为一个变换函数。所以一个细胞自动机系统是由一个细胞空间和定义于该空间上的变换函数所组成。细胞自动机状态由有限个细胞连同赋于每个细胞的状态所指定，可理解为其它的细胞都处于空的状态。
细胞自动机的概念可由以下方式建立
2009-8-20 高级人工智能 史忠植 27
典型的形态形成理论是 1968年 Lindenmayer提出的 L-系统。 L-系统由一组符号串的重写规则组成，它与乔姆斯基 (Chomsky)形式语法有密切关系。
在下面,X→ Y”表示结构中当出现 X时用字符串 Y
代替。因为字符 X可以出现在规则的右边和左边，
这组规则可以被递归地应用来重写新的结构。
12.8 形态形成理论
2009-8-20 高级人工智能 史忠植 28
形态形成理论规则采用上下文无关,即在特定部分改变时不考虑上下文中的关系 。 例如一组规则：
(1) A? CB
(2) B? A
(3) C? DA
(4) D? C
2009-8-20 高级人工智能 史忠植 29
当把这组规则用于初始种子结构,A”,就可以得到下面的序列：
次数 结构 应用规则
0 A 初始种子
1 C B 规则 1,CB 代替 A
2 D A A 规则 3,DA代替 C; 规则 2,A代替 B
3 C C B C B 规则 4,C代替 D; 规则 1用两次,CB代替 A
4 … 继续进行例子 1
2009-8-20 高级人工智能 史忠植 30
规则,(1) A → C[B]D
(2) B → A
(3) C → C
(4) D → C(E)A
(5) E → D
当把这组规则用于初始种子结构,A”,就可以得到下面的序列：
次数 结构 应用规则
0 A 开始种子
1 C[B]D 规则 1,
2 C[A]C(E)A 规则 3,2,4.
3 C[C[B]D]C(D)C[B]D 规则 3,1,3,5,1.
4 C[C[A]C(E)A]C(C(E)A)C(E)A 规则 3,3,2,4,3,4,3,2,3.
例子 2
2009-8-20 高级人工智能 史忠植 31
规则,(1) [{C} → C 在字符串左端的,C”保持,C”
(2) C{C} → C,C”和它左端的,C”保持,C”
(3) *{C} → *,C”和它左端的,*”变成,*”
(4) {*}C → C,*”和右端的,C”变成,C”
(5) {*}] → * 在字符串右端的,*”保持,*”
在这些规则下，初始结构,*CCCCCCC”将产生向右传播：
次数 结构
0 *CCCCCCC
1 C*CCCCCC
2 CC*CCCCC
3 CCC*CCCC
4 CCCC*CCC
5 CCCCC*CC
6 CCCCCC*C
7 CCCCCCC*
例子 3
2009-8-20 高级人工智能 史忠植 32
从系统角度来看生命的行为，首先在物理上可以定义为非线性、
非平衡的开放系统。所以，这种系统特殊行为是自然振荡，即有限周期和混沌。这些生命特有的行为是本体主义和高级信息处理所关注的，
人工生命中，它的生成原理是主要的。有限周期可以分为稳定的和不稳定的。把自然振荡称为稳定的有限周期。这种稳定的有限周期邻近的位相面轨道渐近闭轨道。有限振荡和混沌是结构稳定的两个方面。
它们的差别仅仅在于有限周期的初始条件的差对于以后运动影响很大。
在混沌中，初始条件的差随着时间很快扩大，近似再现是困难的。这种性质称为轨道不稳定性，这和基于有限周期的轨道稳定性的有序化形成明显对照。自然界中动力学分为有序和混沌。有序的规则行为是周期解。其它混沌系统是复杂的，长期不能预测的行为。两者从时间发展上基本上是动力学系统。所以，生命体是混沌和有序的复合。
12.9 混沌理论
2009-8-20 高级人工智能 史忠植 33
混沌理论生命行为所提取的特征现象的发生原理的有序和混沌的计算能力怎样呢 。 首先,有序系统具有在它的周期上的复杂性,高度的复杂计算是不可能的 。 混沌系统必须有严格的规定,从理论上计算它的轨道的不稳定性行为是困难的,因此,仅考虑在混沌的边界所看到的生命行为 。 这样,信息的存储,传送,变换之类的基本操作可以通过有序和混沌的混合系统实现：
(1) 信息存储是从有序系统所看到的稳定周期动力学获得 。
(2) 信息的传送和变换可以从混沌系统不稳定动力学实现 。
