遗传算法2

、适应度的计算方法、终止条件等。表示方案通常是把问题的搜索空间的每一个可能的点,编码为一个看做染色体的字符串, 字符通常采用二进制数0、1。适应度的计算方法一般根据实际问题而定。 null4.3 遗传算法应用举例 　　例4.1 利用遗传算法求解区间［0,31］上的二次函数y=x2的最大值。  　　分析 可以看出,只要能在区间［0,31］中找到函数值最大的点a,则函数y=x2的最大值也就可以求得。于是, 原问题转化为在区间［0, 31］中寻找能使y取最大值的点a的问题。显然, 对于这个问题, 任一点x∈［0, 31］都是可能解, 而函数值f(x)= x2也就是衡量x能否为最佳解的一种测度。那么,用遗传算法的眼光来看, 区间［0, 31］就是一个(解)空间,x就是其中的个体对象, 函数值f(x)恰好就可以作为x的适应度。这样, 只要能给出个体x的适当染色体编码, 该问题就可以用遗传算法来解决。 null　　解 　　(1) 定义适应度函数,编码染色体。由上面的分析,函数f(x)=x2就可作为空间U上的适应度函数。显然y=x2是一个单调增函数,其取最大值的点x=31是个整数。另一方面, 5位二进制数也刚好能表示区间［0, 31］中的全部整数。所以, 我们就仅取［0,31］中的整数来作为参加进化的个体,并且用5位二进制数作为个体x的基因型编码, 即染色体。 　　(2) 设定种群规模, 产生初始种群。我们将种群规模设定为4,取染色体s1=01101(13),s2=11000(24),s3=01000(8), s4=10011(19)组成初始种群S1。 null　　(3) 计算各代种群中的各染色体的适应度, 并进行遗传操作,直到适应度最高的染色体(该问题中显然为“11111”=31)出现为止。  　　计算S1中各染色体的适应度、选择概率、积累概率等并列于表4.1中。 null表 4.1 第一代种群S1中各染色体的情况 null选择-复制 　设从区间［0, 1］中产生4个随机数如下: r1=0.450126, r2=0.110347, r3=0.572496, r4=0.98503 按赌轮选择法，染色体s1, s2, s3, s4的被选中次数依次为：1, 2, 0, 1。于是，经复制得群体： s1’=11000（24）, s2’=01101（13）, s3’=11000（24）, s4’=10011（19） 　　可以看出，在第一轮选择中适应度最高的染色体s2被选中两次，因而被复制两次；而适应度最低的染色体s3一次也没有选中而遭淘汰。 null　交叉 设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1’与s2’配对，s2’与s4’配对。分别交换后两位基因，得新染色体： s1’’=11001（25）, s2’’=01100（12）, s3’’=11011（27）, s4’’=10000（16） 　变异 设变异率pm=0.001。这样，群体S1中共有5*4*-60.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。 　现在，我们得到了第二代种群S2： s1=11001（25）, s2=01100（12）, s3=11011（27）, s4=10000（16）null表 4.2 第二代种群S2中各染色体的情况 null　　假设这一轮选择-复制操作中，种群S2中的4个染色体都被选中（因为选择概率毕竟只是一种几率，所以4个染色体恰好都被选中的情况是存在的），我们得到群体： s1’=11001（25）, s2’=01100（12）, s3’=11011（27）, s4’=10000（16） 然后，做交叉运算，让s1’与s2’，s3’与s4’ 分别交换后三位基因，得 s1’’=11100（28）, s2’’=01001（9）, s3’’=11000（24）, s4’’=10011（19） 这一轮仍然不会发生变异。于是，得第三代种群S3： s1=11100（28）, s2=01001（9）, s3=11000（24）, s4=10011（19） null表4-3 第三代种群S4中各染色体的情况 null设这一轮的选择-复制结果为： s1’=11100（28）, s2’=11100（28）, s3’=11000（24）, s4’=10011（19） 然后，做交叉运算，让s1’与s4’，s2’与s3’ 分别交换后两位基因，得 s1’’=11111（31）, s2’’=11100（28）, s3’’=11000（24）, s4’’=10000（16） 这一轮仍然不会发生变异。于是，得第四代种群S4： s1=11111（31）, s2=11100（28）, s3=11000（24）, s4=10000（16） null　显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。 　　然后，将染色体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。 null　例4.2 用遗传算法求解TSP。 　分析 在前面的图搜索技术中，我们曾用状态图搜索中最佳图搜索算法A*算法求解过TSP。在那里算法是在问题的状态空间中从初始节点（起点城市）出发一步一步试探性地朝目标节点前进，以找到一条最短路径。然而，对于这个问题，其任一可能解———— 一个合法的城市序列，即n个城市的一个排列都可以事先构造出来。于是，我们就可以直接在解空间（所有合法的城市序列）中搜索最佳解。这正适合用遗传算法求解。null　　事实上，我们可以将一个合法的城市序列s=（c1, c2, …, cn, cn+1）(cn+1就是c1)作为一个个体。这个序列中相邻两城之间的距离之和的倒数就可作为相应个体s的适应度，从而适应度函数就是 null　　接下来的问题就是如何对个体s=（c1, c2, …, cn, cn+1）进行编码。然而，这却不是一个直截了当的事情。因为这里的任一个体（x1, x2, …, xn, xn+1）必须是一个合法的城市序列，所以如果编码不当，就会在实施交叉或变异操作时出现非法城市序列即无效解。例如，对于5个城市的TSP，我们用符号A、B、C、D、E代表相应的城市，用这5个符号的序列表示可能解即染色体。那么，对下面的两个染色体（合法序列表示的可能解） s1=（A, C, B, E, D, A），s2=（A, E, D,C, B, A） null实施常规的交叉或变异操作，如交换后三位，得 s1’=（A, C, B, C, B, A），s2’=（A, E, D, E, D, A） 或者将染色体s1第二位的C变为E，得 s1’’=（A, E, B, E, D, A） null4.4 遗传算法的特点与优势 　　由上所述, 我们看到,遗传算法模拟自然选择和有性繁殖、 遗传变异的自然原理, 实现了优化搜索和问题求解。与图搜索相比, 遗传算法的主要特点是:  　　——遗传算法一般是直接在解空间搜索, 而不像图搜索那样一般是在问题空间搜索, 最后才找到解(如果搜索成功的话)。 　　——遗传算法的搜索随机地始于搜索空间的一个点集, 而不像图搜索那样固定地始于搜索空间的初始节点或终止节点, 所以遗传算法是一种随机搜索算法。 null　　——遗传算法总是在寻找优解(最优解或次优解), 而不像图搜索那样并非总是要求优解, 而一般是设法尽快找到解(当然包括优解), 所以遗传算法又是一种优化搜索算法。  　　——遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集(种群)的搜索,而不像图搜索那样一般是从空间的一个点到另一个点地搜索。 因而它实际是一种并行搜索, 适合大规模并行计算, 而且这种种群到种群的搜索有能力跳出局部最优解。 　　——遗传算法的适应性强, 除需知适应度函数外, 几乎不需要其他的先验知识。  　　——遗传算法长于全局搜索, 它不受搜索空间的限制性假设的约束,不要求连续性, 能以很大的概率从离散的、多极值的、 含有噪声的高维问题中找到全局最优解。 null习 题 四 　　1. 遗传算法是一种什么样的算法? 它适合于解决哪一类问题? 　　2. 举例说明遗传算法中的三种遗传操作。 　　3. 试编写程序, 用遗传算法解决一个实际问题。