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

进化计算 复习总结一、 选择填空1. 生命的共同特性是_D_；_C_保证正熵世界中任何生命能延续；有限区域不断膨胀的种群中_B_和_A_是不可避免的。A. 选择B. 竞争C. 变异D. 繁殖D,C,B和A教材p42. _D_使复杂生命系统更为复杂。A. 非线性B. 多变量C. 环境多变D. 进化D3. 生物独立进化中某些明显相同的功能对应的_A_结构却是_D_的，如从软体、节肢到脊椎动物的视觉凝视机制。A. 底层基因B. 表现型C. 多变D. 各种各样A、D4. Lamarck认为环境引起有神经系统动物变异的过程是_D_。A. 机能需要习性环境形态构造B. 需要习性环境形态构造机能C. 习性需要环境机能形态构造D. 环境需要习性机能形态构造D教材p25. Medel定律表明：有深层次的_遗传因子_控制着遗传过程。遗传因子/基因 教材p36. Weismann用连续切割鼠尾的实验明确否定了_D_的观点。A. 演变和进化是缓慢而连续的B. 演变和进化是连续有突变C. 用进废退D. 获得性遗传D教材p37. Morgen果蝇实验研究了遗传性状的变化与_B_之间的关系。A. 基因B. 染色体C. 细胞D. 核糖核酸B教材p38. 生物体外在表现特征是_D_构成的体现。生物进化本质体现在_A_的改进上。A. 基因B. 细胞C. 核糖核酸D. 染色体D教材p39. _C_的特异性决定生物多样性，_B_的稳定性保证物种稳定性，_D_的改变决定生物体的变异。A. 基因的杂交和变异B. 基因结构C. 基因组合D. 遗传信息C,B,D教材p310. 现代进化论中进化机制本质上是鲁棒的_C_和_B_过程A. 选择B. 优化C. 搜索D. 繁殖C,B教材p311. 现代进化论认为：只用_种群_上和_物种_内的少量统计过程四个就可以充分解释大多数生命历史。种群,物种，教材p312. 进化是_繁殖_、_变异_、_竞争_和_选择_四个相互作用的随机过程一代代作用在种群上的结果。繁殖,变异,竞争,选择，教材p413. 达尔文进化论的选择机制直接作用于个体和物种的_B_，并不直接作用在_A_。A. 基因型B. 表现型C. 群体的基因频率D. 性选择B,A，教材p414. 进化的受益者是_C_：A. 个体基因B. 个体基因组C. 繁殖中的种群C15. 从系统论观点，生物适应过程是与周围环境相互_AB_的过程。A. 制约B. 影响C. 互补D. 互利A,B16. 标准遗传算法顺序操作的四个步骤是_ABCD_：A. 确定编码方案问题解空间的二进制表达，与精度、范围有关B. 初始化种群找到生成初始化群体的方法，定义域的随机值C. 定义适值函数问题准则，要满足的目标函数、判定准则等D. 确定各参数值求解评价需要的，种群规模、交叉概率、变异概率的值A,B,C,D17. 计算智能模拟生物特征，其中神经网络侧重于_C_、进化计算侧重于_D_的模拟。A. 遗传B. 生物神经系统C. 人脑D. 一般生物进化C，D18. 复杂信息处理系统研究有三个层次，理论层回答_B_、算法层回答_C_、实现层回答_D_。A. 目的B. 做什么C. 如何做D. 基于什么条件做B，C，D教材p419. 各种方法适应的领域不同，_B_适合综合评判，_C_适合目标优化，_D_适合预测。A. 模糊数学B. 神经网络C. 进化计算D. 目标规划二、 判断分析1. 复杂性是“给定各部分及其相互作用规律却无法推演变异总体性质的情形”。对，Simon观点2. 生物系统，无论是在细胞级、器官级、个体级、种群级、物种级还是生态系统级，均存在大量复杂性。对3. Lamarck建立了完整的生物进化体系，其获得性遗传法则也得到了现代科学的支持。错，比较完整，获得性遗传法则没获得支持4. Lamarck认为：环境变化迫使生物发生适应性进化教材p15. 达尔文进化论认为：自然选择是变异的最重要途径。教材p26. 新达尔文主义认为：解释大多数生命历史的过程只需用种群上、物种内的少量统计过程，即繁殖、变异、竞争、选择。教材p37. 优化就是从问题的可行的方案中找到更好或最好的，有三类搜索方法：枚举动态规划、解析梯度、随机变向。教材p58. 遗传算法的搜索方法属于导向随机法的进化搜索子集。详见课堂笔记及电子版主要参考书。9. 模拟退火法平衡利用积累信息和未知空间的矛盾：“优取差概带”。详见课堂笔记及电子版主要参考书。10. 遗传算法利用“模式而不是极值”划分搜索子空间、种群并行。详见课堂笔记及电子版主要参考书。三、 名词解释1. 个体生物种群中的单个生物，进化计算的解空间中的一个解一组编码 组成总体的每一个考察对象称为个体详见课堂笔记及电子版主要参考书。2. 进化生物体生命延续中适应环境变化的、由低级到高级、由简单到复杂的性状改变过程。教材p1一个优化过程。这个过程通过选择，以统计的方式消除不佳的表现型，实现优化。由繁殖、变异、竞争、选择四个相互作用的随机过程一代代作用在生物种群上的现象。教材p33. 种群同种生物若干个体的集合体特定时间内分布到同一区域的许多同种生物个体自然组成的生物系统，具有共同的基因库。教材p214. 智能体具有自身目的性与主动性、有“活力”和适应性的个体。教材p27一个物理的或抽象的实体，它能作用于自身或环境，并能对环境作出反应。教材p345. 协同进化教材p17/20物种间性状反应的相互协同作用，体现在特定性、相互性及同时性上。一个物种的性状作为对另一个物种性状的反应而进化，而后一种物种的性状作为又是作为对前一种物种的性状。教材p20生物与生物、生物与环境之间在进化过程中的某种依存关系。教材p21 6. 遗传个体基因型的代际繁殖或复制。遗传是指经由基因的传递，使后代获得亲代的特征。详见课堂笔记及电子版主要参考书。7. 适值即适应程度的度量结果，也叫选择压、适应函数等，是选择中的优势的度量。生物在特定环境下生存和繁殖的能力个体的适值是其基因成分的整体粘合函数；种群的适值也是其各个体的行为的整体粘合集的函数。参考1p198. 选择生物对环境适留否灭的现象，通过对微小的有利变异的积累而促进生物进化。教材p4新达尔文主义认为，选择是一种严格的后天过程，通过统计上剔除不合适的个体，而获得当前的成功。9. 趋同生物性状的相似化。由于生活习性或环境相似，导致亲缘关系较远的生物获得形态相似或功能相同的特征的演化现象。详见课堂笔记及电子版主要参考书。10. 表现型个体基因表现出来的行为模式。教材p4 具有特定基因型的个体，在一定环境条件下，所表现出来的性状特征的总和。11. 交叉染色体性状段的互换。来自两个不同个体的配子结合，或为该过程的结束生成重组体。详见课堂笔记及电子版主要参考书。12. 变异变异是指同种生物世代之间或同代不同个体之间的差异，进化主要关注遗传中细胞核分子水平的基因突变、染色体突变或基因重组三种突变。教材p413. 竞争生存竞争是指生物与环境所发生的种内、间及与环境三个关系。教材p414. 组织面向单一功能特征的生物细胞的聚集体组织（org）是类别(Class)取值相同的样本集合，不同组织的交集为空。详见课堂笔记及电子版主要参考书。15. 性状即性能与状态，是生物组织结构及其功能的表现。指生物体所有特征的总和。详见课堂笔记及电子版主要参考书。16. 建筑积木块教材p10具有高适应值、长度短、低阶的模式。详见课堂笔记及电子版主要参考书。17. 二进制编码以二进制描述事物得到的描述结果。用0/1组成的字符串来表达所研究的问题，这个过程称作二进制编码。详见课堂笔记及电子版主要参考书。四、 算法分析1. 排课问题需要处理教学任务中的三个对象课程、教师、学生班和动态调整三个参数时间、地点即教室或空间、约束即假或会议等，试用遗传算法给出系统解决方案的形式化算法设计。答题框架：按照统一描述的进化计算算法步骤，简要描述针对课程任务安排问题的优化算法中对应细化内容或变化之处。参见基本遗传算法流程图。详见课堂笔记及电子版主要参考书。2. 针对围棋死活判定给出有限状态机设计，并设计其进化计算方法。答题框架：按照有限状态机设计的可视化描述方法，简要描述死活判断及多步长的进化活动内容或变化。状态机是展示状态与状态转换的图。通常一个状态机依附于一个类，并且描述一个类的实例。状态机包含了一个类的对象在其生命周期间所有状态的序列以及对象对接收到的事件所产生的反应。状态机由状态、转换、事件、活动和动作5部分组成。点位的能否落子就在于判断其是否增长“活气”。围棋死活判定具体步骤：1. 判断你落下去的这颗棋子的旁边有没有对方的棋子；2. 若有，判断这个子还有没有外气；3. 若没有，再判断有没有与这个子相连的己方棋子；用递归的方法重复2,3两个步骤，如果有一次不符，则对方的棋就没死。若没死，而刚才落下去的子却无外气，则违反规则（即：刚才落下去的子不入子、或称为不入气）状态图是系统分析的一种常用工具，它通过建立类对象的生存周期模型来描述对象随时间变化的动态行为。状态机图，由表示状态的节点和表示状态之间转换的带箭头的直接组成。若干个状态由一条或多条转换箭头连接，状态的转换由事件触发。模型元素的行为可以由状态图中的一条通路表示，沿着此通路状态机随之执行了一系列动作。一个简单的状态图如下：参考上图，画出死活两种状态间的迁移条件。详见课堂笔记及电子版主要参考书。3. 说明蚂蚁食物的最佳路径选择算法。答题框架：按照统一描述的进化计算算法步骤，简要描述针对特定问题的细化内容或变化之处。详见课堂笔记及电子版主要参考书。4. 分析并给出调课系统的有限状态Markov链模型。答题框架：按照有限状态Markov链特点，简要描述针对调课的状态迁移及优化迭代算法中对应细化内容或变化之处。详见课堂笔记及电子版主要参考书。五、 简答论述1. 进化计算的主要应用有哪些？/进化计算的应用类型有哪些？教材p162. 进化计算的统一描述是什么？/遗传算法的问题即改进点是什么？给定初始解编码；评价此组解性能适值函数；判断种群变换的迭代与否是，进化计算选择、交叉或重组及变异算子的计算，直至最优；否，结束。教材p5/个体重组强调交叉算子，变异采用随机变异技术。教材p53. 旅行商问题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为一个常数则方程可写为当时，方程按指数型增长。上式表明，为那些适应值较高，长度较短阶次较低的模式分配的搜索次数按照指数率增长；而为那些适应值较低，长度较长，阶次较高的模式分配的搜索次数按照指数率衰减。定理得证。内在并行性定理证明证明“存活率”大于意味着 (37)因为变异概率很小，而交叉概率较大，所以 (37)式可以化为 因为为整数所以 对于任意个体p，它所包含的长度不大于的模式数目约为。因为对于任意个体P，它所有的长度为的连续于串数目为，在这些长度为的子串中，对其每一位保持不变或修改为“*”，就构成了长度小于的模式，因此，在每个子串中共有种长度小于的模式，所以，每个个体中共有约个长度小于的模式。 那么，在n个个体中所包含的长度小于的模式数目小于等于。然而，在一个规模较大的群体中，不同个体间肯定会存在完全相同的低阶模式，那么，为了得到一个较为精确的估计我们可以选择个个体，使得所有阶不低于的模式不至于