1、 第4章 基于遗传算法的随机优化搜索 4.1 基本概念 4.2 基本遗传算法 4.3 遗传算法应用举例 4.4 遗传算法的特点与优势 4.1 基本概念 1染色体及其编码染色体及其编码 遗传算法以生物细胞中的染色体(chromosome)代表问题中个体对象（即可能解）。一般用字符串表示，而基因也就是字符串中的一个个字符。例如，假设数字9是某问题中的个体对象，则我们就可以用它的二进制数串1001作为它的染色体编码。2.适应度与适应度函数适应度与适应度函数 适应度(fitness)就是借鉴生物个体对环境的适应程度，而对所求解问题中的对象（即染色体）设计的一种表征优劣的测度。适应度函数(fitness
2、 function)就是问题中的全体对象与其适应度之间的一个对应关系，即对象集合到适应度集合的一个映射。3.种群种群 种群（population）就是模拟生物种群而由若干个染色体组成的群体，它一般是整个论域空间的一个很小的子集。遗传算法就是通过在种群上实施所称的遗传操作，使其不断更新换代而实现对整个论域空间的搜索。4.遗传操作遗传操作 遗传算法中有三种关于染色体的运算：选择-复制*、交叉和变异，称为遗传操作或遗传算子（genetic operator）。选择-复制 选择概率P(xi)的计算公式为其中，f为适应度函数，f(xi)为xi的适应度。按概率选择的方法可用一种称为赌轮的原理来实现。算法中
3、赌轮选择法可用下面的子过程来模拟：在0,1区间内产生一个均匀分布的伪随机数r；若rq1，则染色体x1被选中；若qk-1rqk(2kN)，则染色体xk被选中。其中的qi称为染色体xi（i=1,2,n）的积累概率，其计算公式为交叉 交叉(crossover)亦称交换、交配或杂交，就是互换两个染色体某些位上的基因。例如，设染色体s1=01001011，s2=10010101，交换其后4位基因，即则得新串s1=01000101，s2=10011011。s1和s2可以看作是原染色体s1和s2的子代染色体。变异 变异(Mutation)亦称突变，就是改变染色体某个（些）位上的基因。例如，把染色体s=110
4、01101的第三位上的0变为1，则得到新染色体s=11101101。4.2 基本 遗传 算法4.3 遗传算法应用举例 例 4-1 利用遗传算法求区间0,31上的二次函数y=x2的最大值。解 (1)定义适应度函数，编码染色体。将函数f(x)=x2就可作为空间U上的适应度函数。(2)设定种群规模，产生初始种群。将种群规模设定为4，取染色体 s1=01101（13）,s2=11000（24）s3=01000（8）,s4=10011（19）组成初始种群S1。(3)计算各代种群中的各染色体的适应度，并进行遗传操作，直到适应度最高的染色体（该问题中显然为“11111”=31）出现为止。计算S1中各染色体的
5、适应度、选择概率、积累概率等并列表于表4-1中。选择-复制 设从区间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）交叉 设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。将s1与s2配对，s2与s4配对，分别交换后两位基因，得新染色体：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10
6、000（16）变异 设变异率pm=0.001。这样，群体S1中共有 54 0.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。现在，得到了第二代种群S2：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）计算S2中各染色体的适应度、选择概率、积累概率等并列表于表4-2中。假设这一轮选择-复制操作中，种群S2中的4个染色体都被选中，则得到群体：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）然后，做交叉运算，让s1与s2，s3与s4 分别配对并交换后三位基因，得
7、 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）计算S3中各染色体的适应度、选择概率、积累概率等并列表于表4-3中。设这一轮的选择-复制结果为：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=1000
8、0（16）这一轮仍然不会发生变异。于是，得第四代种群S4：s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为 961。例 4-2 用遗传算法求解TSP。解 将一个合法的城市序列s=(c1,c2,cn,cn+1)(cn+1就是c1)作为一个个体。这个序列中相邻两城之间的距离之和的倒数就可作为相
9、应个体s的适应度，从而适应度函数就是用符号A、B、C、D、E代表相应的城市，用这5个符号的序列表示可能解即染色体。然后设计合适的染色体和相应的遗传运算，使得这些遗传运算对染色体集合封闭。为此，人们针对TSP提出了许多编码方法和相应的特殊化了的交叉、变异操作，如顺序编码或整数编码、随机键编码、部分映射交叉、顺序交叉、循环交叉、位置交叉、反转变异、移位变异、互换变异等等。从而巧妙地用遗传算法解决了TSP。同时，也发展和完善了遗传算法，进一步扩展了它的应用。4.4 遗传算法的特点与优势 遗传算法一般是直接在解空间搜索，而不像图搜索那样一般是在问题空间搜索，最后才找到解（如果搜索成功的话）。遗传算法的
10、搜索随机地始于搜索空间的一个点集，而不像图搜索那样固定地始于搜索空间的初始节点或终止节点。所以，遗传算法是一种随机搜索算法。遗传算法总是在寻找优解（最优解或次优解），而不像图搜索那样并非总是要求优解，而一般是设法尽快找到解（当然包括优解）。所以，遗传算法又是一种优化搜索算法。遗传算法的搜索过程是从空间的一个点集（种群）到另一个点集（种群）的搜索，而不像图搜索那样一般是从空间的一个点到另一个点地搜索。因而它实际是一种并行搜索，适合大规模并行计算，而且这种种群到种群的搜索有能力跳出局部最优解。遗传算法的适应性强，除需知适应度函数外，几乎不需要其他的先验知识。遗传算法长于全局搜索，它不受搜索空间的限制性假设的约束，不要求连续性，能以很大的概率从离散的、多极值的、含有噪声的高维问题中找到全局最优解。
