高级人工智能.pptx

高级人工智能第十三章
史忠植
中国科学院计算技术研究所
进化计算 Evolutionary Computation
2021/6/24
史忠植 高级人工智能
2
内 容
概述
进化系统 高级人工智能
13
进化系统理论的形式模型
其中，g 是基因型
p 是表型。
基因gi的可能值称为等位基因。
在门德尔(Mendel)遗传学中，假设每个基因有有限数的等位基因。
2021/6/24
史忠植 高级人工智能
14
进化系统理论的形式模型
这个变换函数给出了模型，说明表型的发展是通过基
因与环境的交互作用。
变换过程是高度非线性的。
2021/6/24
史忠植 高级人工智能
15
进化系统理论的形式模型
质量函数q给出了具体选择环境ESi下表型的质量，
其定义如下：
质量定义适应度，用于达尔文选择。至今已有三种具体范例的通用模型，即 
门德尔遗传学 
遗传生态学 
进化配子
2021/6/24
史忠植 高级人工智能
16
门德尔遗传学
在门德尔遗传学中，基因型被详细模型化，而表型和
环境几乎被忽略。在遗传生态学中恰好相反。
进化配子论是从社会生物学导出的模型。
首先让我们讨论门德尔遗传学的选择模型。为了简单起见，我们假设一个基因具有n 等位基因a1,…,an。 二倍基因型以元组(ai,aj)为特征。 我们定义 pi,j 为总群体中基因型(ai,aj) 的频度。假设基因型与表型相等。质量函数给每个表型赋值。
q(ai,aj) = qi,j
qi,j 可以被解释为出生率减去死亡率
2021/6/24
史忠植 高级人工智能
17
门德尔遗传学
假设 p’i,j是下一代表型(ai,aj) 的频度。然后达尔文
选择根据选择方程调整表型的分布:
是群体的平均适应度。
2021/6/24
史忠植 高级人工智能
18
门德尔遗传学
设 pi 是群体中等位基因的频率。如果
pi,j = pi pj
那么，我们得到在 GS中的一个选择方程为
2021/6/24
史忠植 高级人工智能
19
门德尔遗传学
这个离散的选择方程可以用连续方程近似:
如果 qi,j = qj,i, 那么
2021/6/24
史忠植 高级人工智能
20
门德尔遗传学
这个方程很容易被证明:
这个结果称作菲希尔(Fisher)基本定理。它说明平均适应度随适应度的差别呈正比例增加。实际上，全部可能的基因型仅有一部分实现。这就是遗传操纵子探索基因型空间的任务，其个体数目相当小。这些操纵子是群体遗传变异性的来源。最重要的操纵子是突变和重组。
2021/6/24
史忠植 高级人工智能
21
达尔文进化算法
根据定量遗传学，达尔文进化算法采用简单
的突变/选择动力学。
达尔文算法的一般形式可以描述如下：
是一代的双亲数目，
为子孙数目。
整数 称作“混杂”数。
如果两个双亲混合他们的基因，则
= 2。仅 是最好的个体才允许产生子孙。
逗号表示双亲们没有选择，加号表示双亲有选择。
2021/6/24
史忠植 高级人工智能
22
达尔文进化算法
建立原始种体。
通过突变建立子孙。
选择：
返回到步骤(1)。
…
2021/6/24
史忠植 高级人工智能
23
遗传算法思想来源于生物进化过程, 它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法(以字符串表示状态空间)。遗传算法用概率搜索过程在该状态空间中搜索，产生新的样本。
遗传算法
2021/6/24
史忠植 高级人工智能
24
遗传算法的特点
特点：
通用
鲁棒
次优解、满意解
遗传算法能解决的问题：
优化
NP完全
NP难
高度复杂的非线性问题
2021/6/24
史忠植 高级人工智能
25
遗传算法
遗传算法先将搜索结构编码为字符串形式, 每个字符串结构被称为个体。
然后对一组字符串结构(被称为一个群体)进行循环操作。每次循环被称作一代,包括一个保存字符串中较优结构的过程和一个有结构的、随机的字符串间的信息交换过程。
类似于自然进化，遗传算法通过作用于染色体上的基因寻找好的染色体来求解问题。
2021/6/24
史忠植 高级人工智能
26
遗传算法
与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。
在遗