您的当前位置是：第四章 计算智能>>学习内容>>知识点四

生活中的有些问题没有解析的求解方法，如TSP问题，需要一些智能的搜索方法寻找问题的满意解。遗传算法是模仿生物遗传学和自然选择机理，通过人工方式所构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的最重要的形式。遗传算法为那些难以找到传统数学模型的难题给出了一个解决方法。

一、遗传算法的基本机理

这里以霍兰德提出的简单遗传算法（SGA）作为讨论主要对象，加上适应的改进，来分析遗传算法的结构和机理。

1．编码与解码

将问题结构变换为位串形式表示的过程叫编码；而相反将位串形式表示变换为原问题结构的过程叫解码或译码。把位串形式编码表示叫染色体，有时也叫个体。

种群：种群是指用遗传算法求解问题时，初始给定的多个染色体（解）的集合。遗传算法的求解过程是从这个集合开始。

遗传算法的编码方法有二进制编码、浮点数编码方法、格雷码、符号编码方法、多参数编码方法等。

①二进制编码

假设某一参数的取值范围是[A，B]，A<B。用长度为l的二进制编码串来表示该参数，将[A，B]等分成2l-1个子部分，记每一个等分的长度为δ。参数编码的对应关系:

假设某一个体的编码是：X:x_lx_l-1x_l-2…x₂x₁，则上述二进制编码所对应的解码公式为：

    （4.17）

例4.8 假设变量x的定义域为[5，10]，要求的计算精度为10^-5，则需要将[5，10]至少分为600000个等长小区间，每个小区间用一个二进制串表示。于是，串长至少等于20，原因是：

524288=1019<600000<220=1048576

这样，对应于区间[5，10]内满足精度要求的每个值x，都可用一个20位编码的二进制串<b19,b18,…b0>来表示。

二进制编码的最大缺点之一是长度较大，对很多问题用其他编码方法可能更有利。

②格雷编码

格雷编码是对二进制编码进行变换后所得到的一种编码方法。这种编码方法要求两个连续整数的编码之间只能有一个码位不同，其余码位都是完全相同的。

如，十进制数7和8的二进制编码分别为0111和1000，而其格雷编码分别为0100和1100。

③浮点数编码方法

实数编码是将每个个体的染色体都用某一范围的一个实数（浮点数）来表示，其编码长度等于该问题变量的个数。

这种编码方法是将问题的解空间映射到实数空间上，然后在实数空间上进行遗传操作。由于实数编码使用的是变量的真实值，因此这种编码方法也叫做真值编码方法。

④符号编码

符号编码方法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。

例如，对于TSP问题，采用符号编码方法，按一条回路中城市的次序进行编码，一般情况是从城市w₁开始，依次经过城市w₂…，w_n，最后回到城市w₁，我们就有如下编码表示：

w₁,w₂,…,w_n

由于是回路，记w_n+1=w₁。它其实是1，…，n的一个循环排列。要注意w₁,w₂,…,w_n是互不相同的。

2．适应度函数

为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数（fitness function）。

对优化问题，适应度函数就是目标函数。TSP的目标是路径总长度为最短，路径总长度可作为TSP问题的适应度函数：

    （4.18）

3．遗传操作

简单遗传算法的遗传操作主要有有三种:选择（selection）、交叉（crossover）、变异（mutation）。改进的遗传算法大量扩充了遗传操作，以达到更高的效率。

①选择

选择操作也叫复制（reproduction）操作，根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。一般地说，选择将使适应度较大（优良）个体有较大的存在机会，而适应度较小（低劣）的个体继续存在的机会也较小。

常用的选择策略可分为比例选择、排序选择和竞技选择三种类型。比例选择方法的基本思想是：各个个体被选中的概率与其适应度大小成正比。常用的比例选择策略有轮盘赌选择。

在轮盘赌选择方法中，个体被选中的概率取决于该个体的相对适应度。而相对适应度的定义为：

    （4.19）

其中，P（x_i）是个体x_i的相对适应度，即个体x_i被选中的概率；f（x_i）是个体x_i的原始适应度；是种群的累加适应度。

轮盘赌选择算法的基本思想是：根据每个个体的选择概率P（x_i）将一个圆盘分成N个扇区，其中第i个扇区的中心角为：

    （4.20）

并再设立一个固定指针。当进行选择时，可以假想转动圆盘，若圆盘静止时指针指向第i个扇区，则选择个体i。

如图4.8所示，从统计角度看，个体的适应度值越大，其对应的扇区的面积越大，被选中的可能性也越大。这种方法有点类似于发放奖品使用的轮盘，并带有某种赌博的意思，因此亦被称为轮盘赌选择。

②交叉操作

交叉操作的简单方式是将被选择出的两个个体P1和P2作为父母个体，将两者的部分码值进行交换。

假设有八位长的两个个体，产生一个在1到8之间的随机数c，假如现在产生的是3，将P1和P2的低三位交换，交叉后的个体分别称为Q1和Q2。交叉过程如图4.9所示

③变异操作

变异操作的简单方式是改变数码串的某个位置上的数码。二进制编码表示的简单变异操作是将0与1互换：0变异为1，1变异为0。有如下二进制编码表示：

其码长为8，随机产生一个1到8之间的数k。假设k＝5，对从右往左的第5位进行变异操作，将原来的0变为1，得到如下新的个体。

TSP的一种变异操作：随机产生一个1至n之间的数k，对回路中的第k个城市的代码w_k作变异操作，又产生一个1至n之间的数w，替代w_k，并将w_k加到尾部，得到：

w₁w₂…w_k-1ww_k+1…w_nw_k

1  2