人工智能原理4new.ppt

* 3 遗传算法 7)算法终止条件 遗传算法是一种迭代算法，对生成的后代群体的n个个体继续进行选择、杂交和变异操作，直至不能再繁殖出更优良的个体。比较一般的终止条件可以是： 若fi=ε，则算法终止。 * 3 遗传算法 总结：为了建立任何一个对象系统的时序预测模型，只要能先用一个参数待定的非线性函数来大致描述该对象系统的变化规律，无论这个非线性模型有多么复杂，都可以用一组实际值作为学习实例，采用遗传算法来训练模型，求出模型的待定参数，从而建立起这个模型。 * * * * * * * * * * * * 3 遗传算法 染色体有两种表示模式，即基因型表示模式和表现型表示模式。 ①基因型是指与生物个体表现出来的性状密切相 关的基因组成。 ②表现型是指生物个体所表现出来的性状。 同一种基因型的生物个体在不同的环境条件下表现出来的性状会有差异，因此，表现型是基因型与环境条件相互作用的结果。 * 3 遗传算法 四、遗传算法的概念与计算方法 遗传算法中，与染色体相对应的是数据或数组。在标准的遗传算法中，染色体可用一维的 串结构数据来表示，串的各个位置对应染色体的基因座，各位置上所取的值对应等位基因。遗传算法对染色体进行处理，或者称为对基因型个体(Individual)进行处理。一定数量的个体组成 群体(Population)，群体中的个体数称为群体 大小(Population Size)或群体规模。各个个体对环境的适应程度称为适应度(Fitness)。 * 3 遗传算法 执行遗传算法时有两个必需的数据转换操作。 ①编码操作：把染色体数据从表现型表示转换成基因型表示。 ②译码操作：它是同编码操作相反的数据转换操作，译码操作把染色体数据从基因型表示转换成表现型表示。 * 3 遗传算法 遗传算法的基本流程如下图所示。他以群体中的所有个体为对象。选择(Selection)、杂交(Crossbreed)、变异(mutation)是三个主要的遗传算子。 对当前群体的所有个体的适应度计算 编码和初始群体生成 选 择 杂 交 变 异 * 3 遗传算法 应用遗传算法求解问题，需要根据求解的具体问题进行下述5个方面的工作： 1) 参数编码的格式及参数编码。 2) 初始群体的设定 3) 适应度函数的设计 4) 遗传操作的设计 5) 控制参数设计，主要是指群体规模和遗传操作中所需要使用的有关控制参数的设定和设计 * 3 遗传算法 五、例子 应用遗传算法求f(x) = x2的最大值的解， x∈[0, 31]。 * 3 遗传算法 (1) 编码 此问题给出的数据0~31是表现型表示模式，需要通过编码把它们转换成遗传空间的基因型表示。基因型表示模式通常是串结构形式，十进制数可以很方便地转换成二进制数串，因此，我们把0~31编码为5位长的二进制无符号整数表示形式。例如，x=8的基因型表示为01000，x=13的基因型表示为01101。 * 3 遗传算法 (2) 初始群体的生成 遗传算法是对一个群体中的所有个体为对象进行遗传操作的，为了简化该例子的说明，假定群体规模n=4，即群体由4个个体组成。初始群体的每个个体都是从遗传空间中随机选择的，假设随机选择的4个个体分别是x1=13=01101, x2=24=11100, x3=8=01000, x4=19=10011。初始群体也称为进化的初始代或第一代(first generation)群体。 * 3 遗传算法 (3) 适应度函数设计和适应度计算 遗传算法在有哪些信誉好的足球投注网站求解过程中一般不需要其他外部信息，仅用设计的适应度函数来评估个体的优劣，作为对个体进行遗传操作的依据。某个个体xi的适应度函数值fi称为这个个体xi的适应度，按适应度的大小来评估个体的优劣，适应度越大的个体越优良，优胜劣汰，遗传进化的结果将得到f(x)值最大的解x。 f(x) = x2 * 3 遗传算法 (4) 选择操作 选择操作是从当前群体中选出优良的个体，使它们有机会作为父代来繁殖下一代。判断个体优良的依据就是个体的适应度，个体的适应度越高，该个体被选择的机会就越多。 选择操作的实现方法很多，最简单的方法就是直接按适应度fi选择个体，也可以把选择操作算子设计成适应度fi的某种函数s(fi)，由该函数值来选择个体。 * 3 遗传算法 * * 3 遗传算法 杂交操作可分为下述两个步骤来实现： 1、随机配对：对配对池中的任意两个个体随机进行配对。 2、杂交繁殖：对任何一对配对个体随机指定一个交叉位置k，1=k=m，两个个体从基因座1至基因座k上的基因值对应彼此交换，从而产生