《人工智能》教案 （四）.pptVIP

人 工 智 能 第5章 计算智能(2)Computational Intelligence 进化计算 人工生命 进化计算包括： 遗传算法(genetic algorithms，GA) 进化策略(evolutionary strategies) 进化编程(evolutionary programming) 遗传编程(genetic programming) 人类不满足于模仿生物进化行为，希望能够建立具有自然生命特征的人造生命和人造生命系统。 人工生命是人工智能和计算智能的一个新的研究热点。 5.1 遗传算法 遗传算法是模仿生物遗传学和自然选择机理，通过人工方式所构造的一类优化有哪些信誉好的足球投注网站算法，是对生物进化过程进行的一种数学仿真，是进化计算的最重要的形式。 遗传算法为那些难以找到传统数学模型的难题指出了一个解决方法。 进化计算和遗传算法借鉴了生物科学中的某些知识，这也体现了人工智能这一交叉学科的特点。 5.1.1 遗传算法的基本机理 霍兰德的遗传算法通常称为简单遗传算法（SGA）。现以此作为讨论主要对象，加上适应的改进，来分析遗传算法的结构和机理。 编码与解码 适应度函数 遗传操作 1.编码与解码 将问题结构变换为位串形式编码表示的过程叫编码；而相反将位串形式编码表示变换为原问题结构的过程叫解码或译码。把位串形式编码表示叫染色体，有时也叫个体。 遗传算法的编码方法有二进制编码、浮点数编码方法、格雷码、符号编码方法、多参数编码方法等。 二进制编码 最常用的编码方法 假设某一参数的取值范围是[A，B]，AB。用长度为l的二进制编码串来表示该参数，将[A，B]等分成2l-1个子部分，记每一个等分的长度为δ。参数编码的对应关系: 二进制编码的最大缺点之一是长度较大，对很多问题用其他主编码方法可能更有利 符号编码方法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。 例如，对于TSP问题，采用符号编码方法，按一条回路中城市的次序进行编码，一般情况是从城市w1开始，依次经过城市w2 ，……， wn，最后回到城市w1，我们就有如下编码表示： 由于是回路，记wn+1= w1。它其实是1，……，n的一个循环排列。要注意w1， w2，……， wn是互不相同的。 2.适应度函数 体现染色体的适应能力，对问题中的每一个染色体都能进行度量的函数，叫适应度函数（fitness function） 对优化问题，适应度函数就是目标函数。TSP的目标是路径总长度为最短，路径总长度可作为TSP问题的适应度函数： 3.遗传操作 简单遗传算法的遗传操作主要有有三种:选择(selection)、交叉(crossover)、变异(mutation)。改进的遗传算法大量扩充了遗传操作，以达到更高的效率。 选择操作也叫复制（reproduction）操作，根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。 一般地说，选择将使适应度较大（优良）个体有较大的存在机会，而适应度较小（低劣）的个体继续存在的机会也较小。 交叉操作 交叉操作的简单方式是将被选择出的两个个体P1和P2作为父母个体，将两者的部分码值进行交换 假设有八位长的二个体，产生一个在1到8之间的随机数c，假如现在产生的是3，将P1和P2的低三位交换 变异操作 返回 变异操作的简单方式是改变数码串的某个位置上的数码 二进制编码表示的简单变异操作是将0与1互换：0变异为1，1变异为0 TSP的变异操作：随机产生一个1至n之间的数k，对回路中的第k个城市的代码wk作变异操作，又产生一个1至n之间的数w，替代wk ，并将wk加到尾部，得到： 5.1.2 遗传算法的求解步骤 1. 遗传算法的特点 (1) 遗传算法是对参数集合的编码而非针对参数本身进行进化； (2)?遗传算法是从问题解的编码组开始而非从单个解开始有哪些信誉好的足球投注网站； (3)?遗传算法利用目标函数的适应度这一信息而非利用导数或其它辅助信息来指导有哪些信誉好的足球投注网站； (4)?遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。 2. 遗传算法的框图(图5.2) (1) 初始化种群; (2) 计算种群上每个个体的适应度值; (3) 按由个体适应度值所决定的某个规则选 择将进入下一代的个体; (4) 按概率Pc进行交叉操作; (5) 按概率Pm进行变异操作; (6) 若没有满足某种停止条件，则转第(2)步， 否则进入下一步。 (7) 输出种群中适应度值最优的染色体作为问题的满意解或最优解。 遗传算法的一般结构表示 Procedure: Genetic Algorithms begin t ← 0; initialize P(t);evaluat