进化计算-复习题及部分参考答案.doc

进化计算 复习总结
一、 选择填空
1. 生命的共同特性是_D_____；__C____保证正熵世界中任何生命能延续；有限区域不断膨胀的种群中__B____和_A_____是不可避免的。
A. 选择
B. 竞争
C. 变异
D. 繁殖
D,C,B和A教材p4
2. __D____使复杂生命系统更为复杂。
A. 非线性
B. 多变量
C. 环境多变
D. 进化
D
3. 生物独立进化中某些明显相同的功能对应的__A____结构却是_D_____的，如从软体、节肢到脊椎动物的视觉凝视机制。
A. 底层基因
B. 表现型
C. 多变
D. 各种各样
A、D
4. Lamarck认为环境引起有神经系统动物变异的过程是___D___。
A. 机能à需要à习性à环境à形态构造
B. 需要à习性à环境à形态构造à机能
C. 习性à需要à环境à机能à形态构造
D. 环境à需要à习性à机能à形态构造
D教材p2
5. Medel定律表明：有深层次的__遗传因子____控制着遗传过程。
[遗传因子/基因] 教材p3
6. Weismann用连续切割鼠尾的实验明确否定了__D____的观点。
A. 演变和进化是缓慢而连续的
B. 演变和进化是连续有突变
C. 用进废退
D. 获得性遗传
D教材p3
7. Morgen果蝇实验研究了遗传性状的变化与_B_____之间的关系。
A. 基因
B. 染色体
C. 细胞
D. 核糖核酸
B教材p3
8. 生物体外在表现特征是__D____构成的体现。生物进化本质体现在_A_____的改进上。
A. 基因
B. 细胞
C. 核糖核酸
D. 染色体
D教材p3
9. ____C__的特异性决定生物多样性，____B__的稳定性保证物种稳定性，____D__的改变决定生物体的变异。
A. 基因的杂交和变异
B. 基因结构
C. 基因组合
D. 遗传信息
C,B,D教材p3
10. 现代进化论中进化机制本质上是鲁棒的___C___和___B___过程
A. 选择
B. 优化
C. 搜索
D. 繁殖
C,B教材p3
11. 现代进化论认为：只用_种群_____上和__物种____内的少量统计过程[四个]就可以充分解释大多数生命历史。
种群,物种，教材p3
12. 进化是__繁殖____、_变异_____、_竞争_____和__选择____四个相互作用的随机过程一代代作用在种群上的结果。
繁殖,变异,竞争,选择，教材p4
13. 达尔文进化论的选择机制直接作用于个体和物种的__B____，并不直接作用在___A___。
A. 基因型
B. 表现型
C. 群体的基因频率
D. 性选择
B,A，教材p4
14. 进化的受益者是__C____：
A. 个体基因
B. 个体基因组
C. 繁殖中的种群
C
15. 从系统论观点，生物适应过程是与周围环境相互___AB___的过程。
A. 制约
B. 影响
C. 互补
D. 互利
A,B
16. 标准遗传算法顺序操作的四个步骤是__ABCD____：
A. 确定编码方案
问题解空间的二进制表达，与精度、范围有关
B. 初始化种群
找到生成初始化群体的方法，定义域的随机值
C. 定义适值函数
问题准则，要满足的目标函数、判定准则等
D. 确定[]各参数值
求解评价需要的，种群规模、交叉概率、变异概率的值
A,B,C,D
17. 计算智能模拟生物特征，其中神经网络侧重于___C___、进化计算侧重于__D____的模拟。
A. 遗传
B. 生物神经系统
C. 人脑
D. 一般生物进化
C，D
18. 复杂信息处理系统研究有三个层次，理论层回答___B___、算法层回答___C___、实现层回答____D__。
A. 目的
B. 做什么
C. 如何做
D. 基于什么条件做
B，C，D教材p4
19. 各种方法适应的领域不同，___B___适合综合评判，____C__适合目标优化，__D___适合预测。
A. 模糊数学
B. 神经网络
C. 进化计算
D. 目标规划
二、 判断分析
1. 复杂性是“给定各部分及其相互作用规律却无法推演变异总体性质的情形”。
对，Simon观点
2. 生物系统，无论是在细胞级、器官级、个体级、种群级、物种级还是生态系统级，均存在大量复杂性。
对
3. Lamarck建立了完整的生物进化体系，其获得性遗传法则也得到了现代科学的支持。
错，比较完整，获得性遗传法则没获得支持
4. Lamarck认为：环境变化迫使生物发生适应性进化
教材p1
5. 达尔文进化论认为：自然选择是变异的最重要途径。
教材p2
6. 新达尔文主义认为：解释大多数生命历史的过程只需用种群上、物种内的少量统计过程，即繁殖、变异、竞争、选择。
教材p3
7. 优化就是从问题的可行的方案中找到更好或最好的，有三类搜索方法：枚举[动态规划]、解析[梯度]、随机[变向]。
教材p5
8. 遗传算法的搜索方法属于导向随机法的进化搜索子集。
详见课堂笔记及电子版主要参考书。
9. 模拟退火法平衡利用积累信息和未知空间的矛盾：“优取差概带”。
详见课堂笔记及电子版主要参考书。
10. 遗传算法利用“模式[而不是极值]”划分搜索子空间、种群并行。
详见课堂笔记及电子版主要参考书。
三、 名词解释
1. 个体
生物种群中的单个生物，进化计算的解空间中的一个解[一组编码]
组成总体的每一个考察对象称为个体
详见课堂笔记及电子版主要参考书。
2. 进化
生物体生命延续中适应环境变化的、由低级到高级、由简单到复杂的性状改变过程。教材p1
一个优化过程。这个过程通过选择，以统计的方式消除不佳的表现型，实现优化。
由繁殖、变异、竞争、选择四个相互作用的随机过程一代代作用在生物种群上的现象。教材p3
3. 种群
同种生物若干个体的集合体
特定时间内分布到同一区域的许多同种生物个体自然组成的生物系统，具有共同的基因库。教材p21
4. 智能体
具有自身目的性与主动性、有“活力”和适应性的个体。教材p27
一个物理的或抽象的实体，它能作用于自身或环境，并能对环境作出反应。教材p34
5. 协同进化
教材p17/20
物种间性状反应的相互协同作用，体现在特定性、相互性及同时性上。
一个物种的性状作为对另一个物种性状的反应而进化，而后一种物种的性状作为又是作为对前一种物种的性状。教材p20
生物与生物、生物与环境之间在进化过程中的某种依存关系。教材p21
6. 遗传
个体基因型的代际繁殖或复制。遗传是指经由基因的传递，使后代获得亲代的特征。
详见课堂笔记及电子版主要参考书。
7. 适值
即适应程度的度量结果，也叫选择压、适应函数等，是选择中的优势的度量。
生物在特定环境下生存和繁殖的能力
个体的适值是其基因成分的整体粘合函数；种群的适值也是其各个体的行为的整体粘合集的函数。参考1p19
8. 选择
生物对环境适留否灭的现象，通过对微小的有利变异的积累而促进生物进化。教材p4
新达尔文主义认为，选择是一种严格的后天过程，通过统计上剔除不合适的个体，而获得当前的成功。
9. 趋同
生物性状的相似化。
由于生活习性或环境相似，导致亲缘关系较远的生物获得形态相似或功能相同的特征的演化现象。
详见课堂笔记及电子版主要参考书。
10. 表现型
个体基因表现出来的行为模式。教材p4
具有特定基因型的个体，在一定环境条件下，所表现出来的性状特征的总和。
11. 交叉
染色体性状段的互换。来自两个不同个体的配子结合，或为该过程的结束生成重组体。
详见课堂笔记及电子版主要参考书。
12. 变异
变异是指同种生物世代之间或同代不同个体之间的差异，进化主要关注遗传中细胞核分子水平的基因突变、染色体突变或基因重组三种突变。教材p4
13. 竞争
生存竞争是指生物与环境所发生的种内、间及与环境三个关系。教材p4
14. 组织
面向单一功能特征的生物细胞的聚集体
组织（org）是类别(Class)取值相同的样本集合，不同组织的交集为空。
详见课堂笔记及电子版主要参考书。
15. 性状
即性能与状态，是生物组织结构及其功能的表现。
指生物体所有特征的总和。
详见课堂笔记及电子版主要参考书。
16. 建筑[积木]块
教材p10具有高适应值、长度短、低阶的模式。
详见课堂笔记及电子版主要参考书。
17. 二进制编码
以二进制描述事物得到的描述结果。
用0/1组成的字符串来表达所研究的问题，这个过程称作二进制编码。
详见课堂笔记及电子版主要参考书。
四、 算法分析
1. 排课问题需要处理教学任务中的三个对象[课程、教师、学生班]和动态调整三个参数[时间、地点即教室或空间、约束即假或会议等]，试用遗传算法给出系统解决方案的形式化算法设计。
答题框架：按照统一描述的进化计算算法步骤，简要描述针对课程任务安排问题的优化算法中对应细化内容或变化之处。参见基本遗传算法流程图。
详见课堂笔记及电子版主要参考书。

2. 针对围棋死活判定给出有限状态机设计，并设计其进化计算方法。
答题框架：按照有限状态机设计的可视化描述方法，简要描述死活判断及多步长的进化活动内容或变化。
状态机是展示状态与状态转换的图。通常一个状态机依附于一个类，并且描述一个类的实例。状态机包含了一个类的对象在其生命周期间所有状态的序列以及对象对接收到的事件所产生的反应。
状态机由状态、转换、事件、活动和动作5部分组成。
点位的能否落子就在于判断其是否增长“活气”。
围棋死活判定具体步骤：
1. 判断你落下去的这颗棋子的旁边有没有对方的棋子；
2. 若有，判断这个子还有没有外气；
3. 若没有，再判断有没有与这个子相连的己方棋子；
用递归的方法重复2,3两个步骤，如果有一次不符，则对方的棋就没死。
若没死，而刚才落下去的子却无外气，则违反规则（即：刚才落下去的子不入子、或称为不入气）
状态图是系统分析的一种常用工具，它通过建立类对象的生存周期模型来描述对象随时间变化的动态行为。
状态机图，由表示状态的节点和表示状态之间转换的带箭头的直接组成。若干个状态由一条或多条转换箭头连接，状态的转换由事件触发。模型元素的行为可以由状态图中的一条通路表示，沿着此通路状态机随之执行了一系列动作。一个简单的状态图如下：

参考上图，画出死活两种状态间的迁移条件。
详见课堂笔记及电子版主要参考书。
3. 说明蚂蚁食物的最佳路径选择算法。
答题框架：按照统一描述的进化计算算法步骤，简要描述针对特定问题的细化内容或变化之处。
详见课堂笔记及电子版主要参考书。
4. 分析并给出调课系统的有限状态Markov链模型。
答题框架：按照有限状态Markov链特点，简要描述针对调课的状态迁移及优化迭代算法中对应细化内容或变化之处。
详见课堂笔记及电子版主要参考书。
五、 简答论述
1. 进化计算的主要应用有哪些？/进化计算的应用类型有哪些？
教材p16
2. 进化计算的统一描述是什么？/遗传算法的问题即改进点是什么？
给定初始解[编码]；评价此组解性能[适值函数]；判断种群变换的迭代与否[是，进化计算——选择、交叉或重组及变异算子的计算，直至最优；否，结束]。教材p5
/个体重组强调交叉算子，变异采用随机变异技术。教材p5
3. 旅行商问题TSP有三种类型的应用求解算法，选择其一进行描述
组合优化【近邻、序、路径、边等表示】、作业调度【空闲、扰乱、交叉算子，作业、时间表】、问题，
详见课堂笔记及电子版主要参考书。
4. 选择一种高级进化计算方法举例说明其改进或拓展之处是什么？
进化规划：不使用个体重组操作[交叉算子]，选择侧重于群体中个体间竞争——选择压或；直接以问题的可行解为个体的表现形式，无需个体编码及扰动影响；以实数空间的优化问题为主要对象。教材p 8
进化策略：p8主要特点
遗传编程：分层结构表示解空间；叶节点是问题的原始变量；可演化任何复杂系统。
思维进化算法将交叉与变异算子改进为趋同与异化
详见课堂笔记及电子版主要参考书。
5. 学习进化计算对领域仿真的支持作用有哪些？
业务逻辑的仿真计算，决策支持算法研究……
详见课堂笔记及电子版主要参考书。
六、 推理证明
1. 根据定义证明模式定理/内在并行性定理
教材p9
参见课堂笔记及电子版主要参考书。
2. 基于Banach压缩映射定理/Markov链分析进化算法的收敛性
教材p10-12
参见课堂笔记及电子版主要参考书。
假定在给定购时间步t，一个特定的模式s在群体P(t)个包含有m个代表串，记为m=m(s,t)。在进行复制时，每个串根据它的适应值大小获得不同的复制概率。对于串i，它的复制概率为

则在群体P(t+1)中，模式s的代表串的数量的期望值为

其中，表示模式s在t时刻的所有代表串的适应值的均值，称为模式s的适应值。
若记中所有个体的适应值的平均值为

则
假定模式s在交叉后不被破坏的概率为，则

若假定交叉慨率为，则模式s不被破坏的概率为

设变异算子以慨率随机地改变个体的一位上的值。
只考虑变异算子对模式的影响时，模式s不被破坏的概率为

当时，
故考虑复制、交叉、变异时

假设模式的适应值为，其中c为一个常数．则方程可写为

当时，方程按指数型增长。
上式表明，为那些适应值较高，长度较短．阶次较低的模式分配的搜索次数按照指数率增长；而为那些适应值较低，长度较长，阶次较高的模式分配的搜索次数按照指数率衰减。
定理得证。

内在并行性定理证明
证明
“存活率”大于意味着
(3．7)
因为变异概率很小，而交叉概率较大，所以 (3．7)式可以化为

因为为整数．所以

对于任意个体p，它所包含的长度不大于的模式数目约为。因为对于任意个体P，它所有的长度为的连续于串数目为，在这些长度为的子串中，对其每一位保持不变或修改为“*”，就构成了长度小于的模式，因此，在每个子串中共有种长度小于的模式，所以，每个个体中共有约个长度小于的模式。
那么，在n个个体中所包含的长度小于的模式数目小于等于。然而，在一个规模较大的群体中，不同个体间肯定会存在完全相同的低阶模式，那么，为了得到一个较为精确的估计．我们可以选择个个体，使得所有阶不低于的模式不至于重复。同时，由于模式数对于阶次是二项分布，阶次高于和阶次低于的模式数目相等。那么，种群中的模式数目的下界为：

所以、种群中的模式数目为。 证毕
压缩映照定理证明
定理： 设X是完备的度量空间，T是X上的压缩映照，那么T有且只有一个不动点(就是说，方程，有且只有——个解)．
证明 设是X中任意一点。令，，…，,
…。我们证明点列是x中柯西点列。
由定义得
(2)
由三点不等式，当n＞m时

因，所以，于是得到

所以当时，，即是X中柯西点
列，由X完备性，存在，使，又由三点不等式和条件(1)，
我们有

上面不等式右端当时趋向于0，所以，即
下证唯一性。如果又有，使，则由条件（1），

因，所以必须，即，证毕．