人工智能导论课件人工智能导论——第三章2_5838059901章节幻灯片.pptVIP

离线比较法 该方法与在线比较法有些相似，但是用进化过程中每代最好解的指标函数值的平均值，来评价算法的进化过程。计算方法如下： 其中T是到目前为止的进化代数，f*(t)是第t代中，染色体的最好指标函数值。 适应函数 一般情况下，我们可以直接选取问题的指标函数作为适应函数。如求函数f(x)的最大值，就可以直接采用f(x)为适应函数。但在有些情况下，函数f(x)在最大值附近的变化可能会非常小，以至于他们的适应值非常接近，很难区分出那个染色体占优。在这种情况下，希望定义新的适应函数，要求该适应函数与问题的指标函数具有相同的变化趋势，但变化的速度更快。 非线性加速适应函数 其中f(x)是问题的指标函数，fmax是当前得到的最优指标函数值，M是一个充分大的数。 线性加速适应函数 上式中的第一个方程表示变换前后的平均值不变，第二个方程表示将当前的最优值放大为平均值的M倍。 二进制编码的交叉规则 双亲双子法 a1 a2 ... ai ai+1 ... an b1 b2 ... bi bi+1 ... bn a1 a2 ... ai bi+1 ... bn b1 b2 ... bi ai+1 ... an 交叉前 交叉后 交叉位置 变化交叉法 1 1 0 1 0 0 1 1 1 0 0 0 1 0 由于两个父染色体的前三位完全一致，因此当交叉位选择在前三位时，其子染色体将与两个父染色体完全一致。变化交叉法就是在随机产生交叉位时，排除掉这样的交叉位。 多交叉位法 1 1 0 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 1 0 1 1 整数编码的交叉规则 下面以旅行商问题为例，介绍几种整数编码的交叉规则。 常规交叉法 随机选取一个交叉位，子代1交叉位之前的基因选自父代1交叉位之间的基因，交叉位之后的基因，从父代2中按顺序选取那些没有出现过的基因。 交叉位 交叉位 ? 父代1：1 2 3 4 5 6 7 8 子代1：1 2 3 4 5 7 8 6 父代2：5 2 1 7 3 8 4 6 子代2：5 2 1 7 3 4 6 8 基于次序的交叉法 父代1: 1 2 3 4 5 6 7 8 9 10 父代2: 5 9 2 4 6 1 10 7 3 8 所选位置: * * * * 父代1中与所选位置相对应的数字为：2、3、5、8。从父代2中找出这些数字，并去除它们，其中b表示空位置： 父代2: b 9 b 4 6 1 10 7 b b 用2、3、5、8依次填入上述父代2的空位置中，得到子代1： 子代1: 2 9 3 4 6 1 10 7 5 8 基于部分映射的交叉法 对于两个选定的父代染色体父代1和父代2，随机产生两个位置，两个父代在这两个位置之间的基因产生对应对，然后用这种对应对分别去替换两个父代的基因，从而产生两个子代。 父代1：2 6 4 3 8 1 5 7 9 父代2：8 5 1 7 6 2 4 3 9 子代1：1 8 4 7 6 2 5 3 9 对应对：3:7 8:6 1:2 变异规则 二进制编码中的变异 整数编码中的变异 二进制编码中的变异 当问题以二进制编码形式表示时，随机的产生一个变异位，被选中的基因由“0”变为“1”，或者由“1”变为“0”。 变异前 变异后 1 1 0 1 1 0 1 1 1 0 1 0 0 1 变异位 整数编码中的变异 基于位置的变异 随机的产生两个变异位，然后将第二个变异位上的基因移动到第一变异位之前。 2 1 3 6 4 5 7 2 4 1 3 6 5 7 变异前 变异后 基于次序的变异 随机的产生两个变异位，然后交换这两个变异位上的基因。 2 1 3 6 4 5 7 2 4 3 6 1 5 7