第五章计算智能.ppt

人工智能 第五章 计算智能（2） 进化计算 人工生命 NOTE 教学内容：遗传算法的基本机理和求解步骤；进化策略的算法模型、进化策略和遗传算法的区别；进化编程的机理与表示和算法步骤；人工生命的起源、发展、定义和研究意义，及其研究内容和方法。 教学重点：遗传算法的基本机理和求解步骤；进化策略的算法模型；进化编程表示和算法步骤；人工生命的定义、研究内容和方法。 教学难点：遗传算法的交叉和变异机制；进化编程的表示。 教学要求：通过对本章的学习，使学生了解三种进化算法和人工生命是如何工作的，并初步了解这些算法研究的进展和应用情况，以及它们的研究意义，掌握主要算法的求解步骤。 进化计算包括 遗传算法 进化策略 进化编程 人类为不满足于模仿生物进化行为，希望建立具有自然生命特征的人造生命和人造生命系统 人工生命是人工智能和计算智能的一个新的研究热点 5.1 遗传算法 遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程的一种数学仿真，是进化计算中最重要的形式之一 遗传算法为那些难以找到传统数学模型的难题指出了一个可行的解决方法 进化计算和遗传算法借鉴了生物科学中的某些知识，体现了人工智能这一交叉学科的特点。 霍兰德(Holland)提出的遗传算法通常称为简单遗传算法（SGA）。现以此作为讨论主要对象，加上适应的改进，来分析遗传算法的结构和机理。在讨论中会结合销售员旅行问题（TSP）来说明。 编码与解码 将问题结构变换为位串形式编码表示的过程叫编码；而相反将位串形式编码表示变换为原问题结构的过程叫解码或译码。把位串形式编码表示叫染色体，有时也叫个体。 适应度函数 为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数（fitness function）。TSP的目标是路径总长度为最短，自然地，路径总长度就可作为TSP问题的适应度函数。 适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距。适应度函数的取值大小与求解问题对象的意义有很大的关系。 遗传操作 遗传操作 选择操作也叫复制（reproduction）操作，根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。 交叉操作的简单方式是将被选择出的两个个体P1和P2作为父母个体，将两者的部分码值进行交换。 变异操作的简单方式是改变数码串的某个位置上的数码。二进制编码表示的简单变异操作是将0与1互换：0变异为1，1变异为0。 TSP问题 编码 适应度函数 适应度函数如何有效反映每一个染色体与问题的最优解染色体之间的差距？ 遗传算法的求解步骤 1、遗传算法的特点 　　遗传算法是一种基于空间搜索的算法，它通过自然选择、遗传、变异等操作以及达尔文适者生存的理论，模拟自然进化过程来寻找所求问题的解答。遗传算法具有以下特点： 　　(1) 遗传算法是对参数集合的编码而非针对参数本身进行进化； 　　(2) 遗传算法是从问题解的编码组开始而非从单个解开始搜索； 　　(3) 遗传算法利用目标函数的适应度这一信息而非利用导数或其它辅助信息来指导搜索； 　　(4) 遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。 一般遗传算法的主要步骤如下： (1) 随机产生一个由确定长度的特征字符串组成的初始群体。 (2) 对该字符串群体迭代的执行下面的步(a)和(b)，直到满足停止标准： (a) 计算群体中每个个体字符串的适应值； (b) 应用复制、交叉和变异等遗传算子产生下一代群体。 (3) 把在后代中出现的最好的个体字符串指定为遗传算法的执行结果，这个结果可以表示问题的一个解。 GA算法框图 算法伪代码 Procedure: Genetic Algorithms Begin t 0; Initialize P(t); Evaluate P(t); While(not termination condition) do Begin Recombine P(t) to yield C(t); Evaluate C(t); Select P(t+1) from P(t) and C(t); End end 遗传算法问题求解举例：（P134） 遗传算法归纳为五个基本组成部分 方案表示 群体初始化 适应度函数 遗传操作 算法参数 5.2 进化策略 进化策略是一类模仿自然进化原理以求解参数优化问题的算法。 它是由雷切伯格（Rechenberg）、施韦费尔（Schwefel）和彼得·比纳特（Peter Bienert）于1964年提出的，并在德国共同建立的。 5.2.1 进化策略的算法模型 最简单形式的进化策略可描述如下： (1) 寻求与函数的极值相关联的实数n维矢量x (2) 随机选