遗传算法（四）——遗传算法的基本实现技术

﹏ヽ暗。殇╰゛Y 2022-12-25 14:59 967阅读 0赞

**目录**

3.遗传算法的基本实现技术

3.1编码方法

3.1.1二进制编码方法

3.1.2格雷码编码方法

3.1.3浮点数编码方法

3.1.4 符号编码方法

3.2适应度函数

3.2.1目标函数与适应度函数

3.2.2适应度尺度变换

3.3选择算子

3.3.1比例选择

3.3.2最优保存策略

3.3.3确定式采样选择

3.3.4无回放随机选择

3.3.5无回放余数随机选择

3.3.6排序选择

3.3.7随机联赛选择

3.4交叉算子

3.4.1单点交叉

3.4.2双点交叉与多点交叉

3.5变异算子

3.5.1基本位变异

3.5.2均匀变异

3.6遗传算法的运行参数

3.7约束条件的处理方法

3.7.1搜索空间限定法

3.7.2可行解变换法

参考资料

--------------------

# 3.遗传算法的基本实现技术 #

## 3.1编码方法 ##

> 在遗传算法的运行过程中，它不对所求解问题的实际决策变量直接进行操作，而是对表示可行解的个体编码施加选择、交叉、变异等遗传运算，通过这种遗传操作来达到优化的目的，这是遗传算法的特点之一。遗传算法通过这种对个体编码的操作，不断搜出适应度较高的个体，并在群体中逐渐增加其数量，最终寻求出问题的最优解或近似最优解。在遗传算法中如何描述问题的可行解，即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就称为**编码**。
> 
> 编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。编码方法除了决定了个体的染色体排列形式之外，它还决定了个体从搜索空间的基因型变换到解空间的表现型时的解码方法，编码方法也影响到交叉算子、变异算子等遗传算子的运算方法。由此可见，编码方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化运算的效率。一个好的编码方法，有可能会使得交叉运算、变异运算等遗传操作可以简单地实现和执行。而一个差的编码方法，却有可能会使得交叉运算、变异运算等遗传操作难以实现，也有可能会产生很多在可行解集合内无对应可行解的个体，这些个体经解码处理后所表示的解称为无效解。虽然有时产生一些无效并不完全都是有害的，但大部分情况下它却是影响遗传算法运行效率的主要因素之一。
> 
> 针对一个具体应用问题，如何设计一种完美的编码方案一直是遗传算法的应用难点之一，也是遗传算法的一个重要研究方向。可以说目前还没有一套既严密又完整的指导理论及评价准则能够帮助我们设计编码方案。

由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的编码方法。总的来说，这些编码方法可以分为三大类 ：二进制编码方法、浮点数编码方法、符号编码方法。下面我们从具体实现的角度出发，介绍其中的几种主要编码方法。

### 3.1.1二进制编码方法 ###

> 二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集是由二进制符号0和1所组成的二值符号集\{0,1\}，它所构成的个体基因型是一个二进制编码符号串。
> 
> 二进制编码符号串的长度与问题所要求的求解精度有关。假设某一参数的取值范围是\[Umin，Umax\]，我们用长度为l的二进制编码符号串来表示该参数，则它总共能够产生![2^l][2_l]种不同的编码。
> 
> 若使参数编码时的对应关系如下：
> 
> ![20201202154109409.png][]
> 
> 则二进制编码的编码精度为：
> 
> ![20201202154229766.png][]

> 假设某一个体的编码是：  
> ![20201202154317310.png][]  
> 则对应的解码公式为：  
> ![20201202154340135.png][]
> 
> 例如，对于x∈\[0,1023\]，若用10位长的二进制编码来表示该参数的话，则下述符号串：X:0 0 1 0 1 0 1 1 1 1就可表示一个个体，它所对应的参数值是x=175。此时的编码精度为=1。

> 二进制编码方法有下述些优点：  
> (1)编码、解码操作简单易行；  
> (2)交叉、变异等遗传操作便于实现等。

### 3.1.2格雷码编码方法 ###

二进制编码不便于反映所求问题的结构特征，对于一些连续函数的优化问题等，也由于遗传运算的随机特性而使得其局部搜索能力较差。为改变这个特性，人们提出使用格雷码（Gray code）来对个体进行编码。

格雷码是这样的一种编码方法，其连续的两个整数所对应的编码值之间仅仅只有一个码位是不相同的，其余码位都完全相同。例如十进制数0~15之间的二进制码和相对应的格雷码分别如下表所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70][]

> 假设有一个二进制编码为![20201202155655822.png][]，其对应的格雷码为![20201202155726452.png][]。
> 
> 由二进制编码到格雷码的转换公式为：
> 
> ![20201202155802785.png][]也就是说，格雷码的此位=对应二进制的此位⊕对应二进制的高一位
> 
> 由格雷码到二进制码的转换公式为：
> 
> ![20201202155842853.png][]也就是说，二进制码的此位=二进制高一位⊕对应格雷码的此位
> 
> 上面两种转换公式中，⊕表示异或运算符。

> 格雷码有这样一个特点：任意两个整数的差是这两个整数所对应的格雷码之间的海明距离( Hamming distance)。这个特点是遗传算法中使用格雷码来进行个体编码的主要原因。
> 
> 遗传算法的局部搜索能力不强，引起这个问题的主要原因是，新一代群体的产生主要是依靠上一代群体之间的随机交叉重组来完成的，所以即使已经搜索到最优解附近，而想要达到这个最优解，却要费一番功夫，甚至需要花费较大的代价。对于用二进制编码方法表示的个体，变异操作有时虽然只是一个基因座的差异(个体基因型X的微小差异)，而对应的参数值却相差较大(个体表现型X相差较大)。但是，若使用格雷码来对个体进行编码，则编码串之间的一位差异，对应的参数值也只是微小的差别。这样就相当于增强了遗传算法的局部搜索能力，便于对连续函数进行局部空间搜索。
> 
> 例如，对于区间\[0,1023\]中两个邻近的整数x1=175和2=176，若使用长度为10位的二进制编码，它们可分别表示为  
> X1：0 0 1 0 1 0 1 1 1 1  
> X2：0 0 1 0 1 1 0 0 0 0  
> 而使用同样长度的格雷码，它们可分别表示为  
> X1：0 0 1 1 1 1 1 0 0 0  
> X2：0 0 1 1 1 0 1 0 0 0
> 
> 显见，使用格雷码时，两个编码串之间只有一位编码值不同；而使用二进制编码时，两个编码串之间却相差很大。格雷码编码方法是二进制编码的一种变形，其编码精度与相同长度的 二进制编码的精度相同。

> 格雷码编码方法的主要优点是：  
> （1）便于提高遗传算法的局部搜索能力；  
> （2）交叉、变异等遗传操作便于实现等。

### 3.1.3浮点数编码方法 ###

对于一些多维、高精度要求的连续函数优化问题，使用二进制编码来表示个体时将会有一些不利之处。

> 首先是二进制编码存在着连续函数离散化时的映射误差。个体编码串的长度较短时，可能达不到精度要求；而个体编码串的长度较长时，虽然能提高编码精度，但却会使遗传算法的搜索空间急剧扩大。例如，若使用二进制编码方法来处理一个含有100个决策变量的优化问题，其中每个决策变量的取值范围是\[-250,250\]，要求精度取小数点后5位小数，为达到这个精度要求，每个变量必须用26位长的二进制编码符号串来表示，这是因为  
> ![20201202163814785.png][]  
> 这样每个个体必须用100×26位长的二进制编码符号串表示。亦即此时遗传算法的搜索空间大约是![2^\{2600\}][2_2600]。在如此之大的搜索空间寻优肯定会使得遗传算法的运行性能相当差，甚至可能无法进行下去。

> 其次是二进制编码不便于反映所求问题的特定知识，这样也就不便于开发针对问题专门知识的遗传运算算子，人们在一些经典优化算法的研究中所总结出的一些宝贵经验也就无法在这里加以利用，也不便于处理非平凡约束条件。

> 为改进二进制编码方法的这些缺点，人们提出了个体的浮点数编码方法。所谓浮点数编码方法，是指个体的每个基因值用某一范围内的一个浮点数来表示，个体的编码长度等于其决策变量的个数。因为这种编码方法使用的是决策变量的真实值，所以浮点数编码方法也叫做真值编码方法。
> 
> 例如，若某一个优化问题含有5个变量xi（i=1,2,…5），每个变量都有其对应的上下限![\[U^\{i\}\_\{min\},U^\{i\}\_\{max\}\]][U_i_min_U_i_max]，则  
> ![20201202164850734.png][]就表示一个体的基因型，其对应的表现型是：![x=\[5.80,6.90,3.50,3.80,5.00\]^T][x_5.80_6.90_3.50_3.80_5.00_T]。
> 
> 在浮点数编码方法中，必须保证基因值在给定的区间限制范围内，遗传算法中所使用的交叉、变异等遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限制范围内。再者，当用多个字节来表示一个基因值时，交叉运算必须在两个基因的分界字节处进行，而不能在某个基因的中间字节分隔处进行。

> 浮点数编码方法有下面几个优点：  
> (1)适合于在遗传算法中表示范围较大的数；  
> (2)适合于精度要求较高的遗传算法；  
> (3)便于较大空间的遗传搜索；  
> (4)改善了遗传算法的计算复杂性，提高了运算效率；  
> (5)便于遗传算法与经典优化方法的混合使用；  
> (6)便于设计针对问题的专门知识的知识型遗传算子；  
> (7)便于处理复杂的决策变量约束条件。

### 3.1.4 符号编码方法 ###

> 符号编码方法是指个体染色体编码串中的基因值取自一个无数值含义，而只有代码含义的符号集。这个符号集可以是一个字母表，如\{A，B，C，D，...\}；也可以是一个数字序号表，如\{1，2，3，4，...\}；还可以是一个代码表，如\{A1，A2，A3，A4，...\}等等。  
> 例如，对于旅行商问题，假设有n个城市分别记为C1、C2、...Cn，将各个城市的代号按其被访问的顺序连接在一起，就可构成一个表示旅行路线的个体。如X：\[C1，C2，...，Cn\]就表示顺序访问城市C1，C2，...，Cn。若将各个城市按其代号的下标进行编号，则这个个体也可表示为X：\[1，2，...，n\]。

> 符号编码的主要优点是：  
> （1）便于在遗传算法中利用所求解问题的专门知识；  
> （2）便于遗传算法与相关近似算法之间的混合使用。  
> 但对于使用符号编码方法的遗传算法，一般需要认真设计交叉、变异等遗传运算的操作方法，以满足问题的各种约束要求，这样才能提高算法的搜索性能。

## 3.2适应度函数 ##

在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对于其生存环境的适应程度。对生存环境适应程度较高的物种将有更多的繁殖机会；而对生存环境适应程度较低的物种，其繁殖机会就相对较少，甚至会逐渐灭绝。与此相类似，遗传算法中也使用适应度这个概念来度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率就较大；而适应度较低的个体遗传到下一代的概率就相对小一些。度量个体适应度的函数称为适应度函数( Fitness Function)。

### 3.2.1目标函数与适应度函数 ###

遗传算法的一个特点是它仅使用所求问题的目标函数值就可得到下一步的有关搜索信息。而对目标函数值的使用是通过评价个体的适应度来体现的。

> 评价个体适应度的一般过程是：  
> (1)对个体编码串进行解码处理后，可得到个体的表现型；  
> (2)由个体的表现型可计算出对应个体的目标函数值；  
> (3)根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。

最优化问题可分为两大类，一类为求目标函数的全局最大值，另一类为求目标函数的全局最小值。对于这两类优化问题， 下面介绍，由解空间中某一点的目标函数值f(X)到搜索空间中对应个体的适应度函数值F(X)的转换方法：  
●对于求最大值的问题，作下述转换：  
![20201202185412746.png][]式中，Cmin为一个适当地相对较小的数.  
●对于求最小值的问题，作下述转换：  
![20201202185555752.png][]式中，Cmax为一个适当地相对较大的数

遗传算法中，群体的进化过程就是以群体中各个个体的适应度为依据，通过一个反复迭代过程，不断地寻求出适应度较大的个体，最终就可得到问题的最优解或近似最优解。

### 3.2.2适应度尺度变换 ###

在遗传算法中，各个个体被遗传到下一代群体中的概率是由该个体的适应度来确定的。应用实践表明，仅使用式(3-6)或式(3-7)来计算个体适应度时，有些遗传算法会收敛得很快，也有些遗传算法会收敛得很慢。由此可见，如何确定适应度对遗传算法的性能有较大的影响。

> 例如，在遗传算法运行的初期阶段，群体中可能会有少数几个个体的适应度相对其他个体来说非常高。若按照常用的比例选择算子来确定个体的遗传数量时，则这几个相对较好的个体将在下一代群体中占有很高的比例，在极端情况下或当群体规模较小时，新的群体甚至完全由这样的少数几个个体所组成。这时产生新个体作用较大的交叉算子就起不了什么作用，因为相同的两个个体不论在何处进行交叉操作都永远不会产生出新的个体，如下所示：  
> ![20201202185925866.png][]  
> 这样就会使群体的多样性降低，容易导致遗传算法发生**早熟现象**(或称早期收敛)，使遗传算法所求到的解停留在某一局部最优点上。为了克服这种现象，我们希望在遗传算法运行的初期阶段，算法能够对一些适应度较高的个体进行控制，降低其适应度与其他个体适应度之间的差异程度，从而限制其复制数量，以维护群体的多样性。

> 又例如，在遗传算法运行的后期阶段，群体中所有个体的平均适应度可能会接近于群体中最佳个体的适应度。也就是说，大部分个体的适应度和最佳个体的适应度差异不大，它们之间无竞争力，都会有以相接近的概率被遗传到下一代的可能性，从而使得进化过程无竞争性可言，只是一种随机的选择过程。这将导致无法对某些重点区域进行重点搜索，从而影响遗传算法的运行效率。为了克服这种现象，我们希望在遗传算法运行的后期阶段算法能够对个体的适应度进行适当的放大，扩大最佳个体适应度与其他个体适应度之间的差异程度，以提高个体之间的竞争性。

由此看来，不能仅仅依靠式(3-6)或式(3-7)就完全确定出个体的适应度，有时在遗传算法运行的不同阶段，还需要对个体的适应度进行适当的扩大或缩小。这种对个体适应度所做的扩大或缩小变换就称为**适应度尺度变换**( Fitness Scaling)。

目前常用的个体适应度尺度变换方法主要有三种：线性尺度变换、乘幂尺度变换和指数尺度变换。

> (1)线性尺度变换。线性尺度变换的公式如下：
> 
> ![20201202190543773.png][]
> 
> 式中 F—原适应度；  
> F'—尺度变换后的新适应度；  
> a和b—系数。
> 
> 线性比例尺度变换的正常情况如下图。
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70 1][]
> 
> 由该图可见，系数a、b直接影响到这个尺度变换的大小，所以对其选取有一定的要求，一般希望它们满足下面两个条件：
> 
> 条件一：尺度变换后全部个体的新适应度的平均值F'avg要等于其原适应度平均值Favg。即：
> 
> ![2020120219092070.png][]  
> 这条要求是为了保证群体中适应度接近于平均适应度的个体能够有期待的数量被遗传到下一代群体中。
> 
> 条件二：尺度变换后群体中新的最大适应度F’max要等于其原平均适应度Favg的指定倍数。即：  
> ![20201202191137847.png][]  
> 式中，C为最佳个体的期望复制数量，对于群体规模大小为50~100个个体的情况，一般取C=1.2~2。这条要求是为了保证群体中最好的个体能够期望复制C倍到新一代群体中。
> 
> 使用线性尺度变换时，如上图，群体中少数几个优良个体的适应度按比例缩小，同时几个较差个体的适应度也按比例扩大。但在搜索过程的后期阶段，随着个体适应度从总体上的不断改进，群体中个体的最大适应度和全部个体的平均适应度较接近，而少数几个较差的个体的适应度却远远低于最大适应度，这时若想维持F'max和Favg的指定倍数关系，将有可能会使较差个体的适应度变换为负值，如下图。
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70 2][]
> 
> 这将会给后面的处理过程带来不便，必须避免这种情况的发生。解决这个问题的方法是：把原最小适应度Fmin映射为F'min=0，并且保持原平均适应度Favg与新的平均适应度F'avg相等。

> (2)乘幂尺度变换。乘幂尺度变换的公式为：
> 
> ![2020120219205551.png][]
> 
> 即新的适应度是原有适应度的某个指定乘幂。幂指数k与所求解的问题有关，并且在算法的执行过程中需要不断对其进行修正才能使尺度变换满足一定的伸缩要求。

> (3)指数尺度变换。指数尺度变换的公式为：
> 
> ![20201202192212108.png][]
> 
> 即新的适应度是原有适应度的某个指数。式中系数β决定了选择的强制性，β越小，原有适应度较高的个体的新适应度就越与其他个体的新适应度相差较大，亦即越增加了选择该个体的强制性。

## 3.3选择算子 ##

在生物的遗传和自然进化过程中，对生存环境适应程度较高的物种将有更多的机会遗传到下一代；而对生存环境适应程度较低的物种遗传到下一代的机会就相对较少。模仿这个过程，遗传算法使用选择算子(或称复制算子， Reproduction Operator)来对群体中的个体进行优胜劣汰操作：适应度较高的个体被遗传到 下一代群体中的概率较大；适应度较低的个体被遗传到下一代群体中的概率较小。遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算。

选择操作建立在对个体的适应度进行评价的基础之上。选择操作的主要目的就是为了避免基因缺失、提高全局收敛性和计算效率。

最常用的选择算子是基本遗传算法中的比例选择算子。但对于各种不同的问题，比例选择算子并不是最合适的一种选择算子，所以人们提出了其他的一些选择算子。下面介绍几种常用的选择算子的操作方法。

### 3.3.1比例选择 ###

> 基本思想：各个个体被选中的概率与其适应度大小成正比。  
> 设群体大小为M，个体i的适应度为Fi，则个体i被选中的概率pis为：
> 
> ![20201202193150795.png][]
> 
> 由上式可见，适应度越高的个体被选中的概率也越大；反之，适应度越低的个体被选中的概率也越小。
> 
> 缺点：随机操作原因，误差比较大，有时连适应度较高的个体都选不上。

### 3.3.2最优保存策略 ###

> 基本思想：当前群体中适应度最高的个体不参与交叉变异运算。以免交叉变异操作破坏当前群体中的适应的最好的个体。而是用它来替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体。
> 
> 具体过程：
> 
> （1）找出当前群体中适应度最高的个体和适应度最低的个体；
> 
> （2）若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适应度还要高，则以当前群体中的最佳个体作为新的迄今为止的最好个体。
> 
> （3）用迄今为止的最好的个体替换掉当前群体中的最差的个体。
> 
> 缺点：容易使得某个局部最优个体不易被淘汰掉反而快速扩散，从而使得算法的全局搜索能力不强。

### 3.3.3确定式采样选择 ###

> 基本思想：按照一种确定的方式进行选择操作。
> 
> 具体过程：
> 
> （1）计算各个个体在下一代群体中的期望生存数目Ni：
> 
> ![20201202194514180.png][]
> 
> （2）用Ni的整数部分![\\left \\lfloor N\_\{i\} \\right \\rfloor][left _lfloor N_i_ _right _rfloor]确定各个对应个体在下一代群体中的生存数目,其中![\\left \\lfloor x \\right \\rfloor][left _lfloor x _right _rfloor]表示取不大于x的最大的整数。
> 
> 由该步共可得出下一代群体中的![20201202195328321.png][]个个体。
> 
> （3）按照的小数部分对个体进行降序排序，顺序取前M-![20201202195328321.png][]个个体加入下一代群体。至此下一代中的M个个体全部确定出来了。
> 
> 优点：能够保证适应度较大的一些个体一定能够被保留到下一代群体中。

### 3.3.4无回放随机选择 ###

### 3.3.5无回放余数随机选择 ###

### 3.3.6排序选择 ###

### 3.3.7随机联赛选择 ###

> 随机联赛选择( Stochastic Tournament Model）也是一种基于个体适应度之间大小关系的选择方法。其基本思想是每次选取几个个体之中适应度最高的一个个体遗传到下一代群体中。在联赛选择操作中，只有个体适应度之间的大小比较运算，而无个体适应度之间的算术运算，所以它对个体适应度是取正值还是取负值无特别要求。
> 
> 联赛选择中，每次进行适应度大小比较的个体数目称为联赛规模。一般情况下，联赛规模N的取值为2。
> 
> 具体过程：  
> ()从群体中随机选取N个个体进行适应度大小的比较，将其中适应度最高的个体遗传到下一代群体中；  
> (2)将上述过程重复M次，就可得到下一代群体中的M个个体。

## 3.4交叉算子 ##

在生物的自然进化过程中，两个同源染色体通过交配而重组形成新的染色体，从而产生出新的个体或物种。交配重组是生物遗传和进化过程中的一个主要环节。模仿这个环节，在遗传算法中也使用交叉算子来产生新的个体。

遗传算法中的所谓交叉运算，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起着关键作用，是产生新个体的主要方法。

遗传算法中，在交叉运算之前还必须先对群体中的个体进行配对。目前常用的配对策略是随机配对，即将群体中的M个个体以随机的方式组成![$\\lfloor M/2 \\rfloor$][lfloor M_2 _rfloor]对配对个体组，交叉操作是在这些配对个体组中的两个个体之间进行的。

交叉算子的设计和实现与所研究的问题密切相关，一般要求它既不要太多地破坏个体编码串中表示优良性状的优良模式，又要能够有效地产生出一些较好的新个体模式。另外交叉算子的设计要和个体编码设计统一考虑。

> 交叉算子的设计包括以下两方面的内容：  
> (1)如何确定交叉点的位置?  
> (2)如何进行部分基因交换?
> 
> 最常用的交叉算子是单点交叉算子。但单点交叉操作有一定的适用范围，故人们发展了其他一些交叉算子。下面介绍几种适合于二进制编码个体或浮点数编码个体的交叉算子。

### 3.4.1单点交叉 ###

单点交叉(One- point Crossover)又称为简单交叉，它是指在个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。单点交叉的具体运算过程已作过介绍，此处不再赘述。

单点交叉的重要特点是：若邻接基因座之间的关系能提供较好的个体性状和较高的个体适应度的话，则这种单点交操作破坏这种个体性状和降低个体适应度的可能性最小。

### 3.4.2双点交叉与多点交叉 ###

双点交叉( Two-point Crossover)是指在个体编码串中随机设置了二个交叉点，然后再进行部分基因交换。

双点交叉的具体操作过程是：  
(1)在相互配对的两个个体编码串中随机设置两个交叉点；  
()交换两个个体在所设定的两个交叉点之间的部分染色体。

> 如下所示，为双点交叉操作示例：
> 
> ![20201203165206588.png][]

将单点交叉和双点交叉的概念加以推广，可得到多点交叉（multi-point crossover）的概念。即多点交又是指在个体编码串中随机设置了多个交叉点，然后进行基因交换。多点交叉,又称为广义交叉，其操作过程与单点交叉和双点交叉相类似。

> 如下所示，为有三个交叉点时的交叉操作示例：
> 
> ![20201203165048808.png][]
> 
> 如下所示，为有四个交叉点时的交叉操作示例：
> 
> ![20201203165257696.png][]

需要说明的是，一般不太使用多点交叉算子，因为它有可能破坏一些好的模式。事实上，随着交叉点数的增多，个体的结构被破坏的可能性也逐渐增大，这样就很难有效地保存较好的模式，从而影响遗传算法的性能。

## 3.5变异算子 ##

在生物的遗传和自然进化过程中，其细胞分裂复制环节有可能会因为某些偶然因素的影响而产生一些复制差错，这样就会导致生物的某些基因发生某种变异，从而产生出新的染色体，表现出新的生物性状。虽然发生这种变异的可能性比较小，但它也是产生新物种的一个不可忽视的原因。模仿生物遗传和进化过程中的这个变异环节，在遗传算法中也引入了变异算子来产生出新的个体。

遗传算法中的所谓变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。例如，对于二进制编码的个体，其编码字符集为\{0,1\}，变异操作就是将个体在变异点上的基因值取反，即用0替换1，或用1替换0；对于浮点数编码的个体，若某一变异点处的基因值的取值范围为\[Umin,Umax\]，变异操作就是用该范围内的一个随机数去替换原基因值；对于符号编码的个体，若其编码字符集为\{A，B，C…\}，变异操作就是用这个字符集中的一个随机指定的且与原基因值不相同的符号去替换变异点上的原有符号。

从遗传运算过程中产生新个体的能力方面来说，交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力；而变异运算只是产生新个体的辅助方法，但它也是必不可少的一个运算步骤，因为它决定了遗传算法的局部搜索能力。交叉算子与变异算子的相互配合，共同完成对搜索空间的全局搜索和局部搜索，从而使得遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。

> 在遗传算法中使用变异算子主要有以下两个目的：
> 
> (1)改善遗传算法的局部搜索能力。遗传算法使用交叉算子已经从全局的角度出发找到了一些较好的个体编码结构，它们已接近或有助于接近问题的最优解。但仅使用交叉算子无法对搜索空间的细节进行局部搜索。这时若再使用变异算子来调整个体编码串中的部分基因值，就可以从局部的角度出发使个体更加近最优解，从而提高了遗传算法的局部搜索能力。
> 
> (2)维持群体的多样性，防止出现早熟现象。变异算子用新的基因值替换原有基因值，从而可以改变个体编码串的结构，维持群体的多样性，这样就有利于防止出现早熟现象。

变异算子的设计包括如下两方面的内容：  
●如何确定变异点的位置?  
●如何进行基因值替换?

最简单的变异算子是基本位变异算子。为适应各种不同应用问题的求解需要，人们也开发出了其他一些变异算子。下面介绍其中较常用的几种变异操作方法，它们适合于二进制编码的个体和浮点数编码的个体。

### 3.5.1基本位变异 ###

基本位变异(Simple Mutation)操作是指对个体编码串中以变异概率Pm随机指定的某一位或某几位基因座上的基因值作变异运算，其具体操作过程已作过介绍，此处不再赘述。

基本位变异操作改变的只是个体编码串中的个别几个基因座上的基因值，并且变异发生的概率也比较小，所以其发挥的作用比较慢，作用的效果也不明显。

### 3.5.2均匀变异 ###

均匀变异( Uniform Mutation)操作是指分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。

具体操作过程是：  
(1)依次指定个体编码串中的每个基因座为变异点；  
(2)对每一个变异点，以变异概率Pm从对应基因的取值范围内取一随机数来替代原有基因值。

特点：

均匀变异操作特别适合应用于遗传算法的初期运行阶段，它使得搜索点可以在整个搜索空间内自由移动，从而可以增加群体的多样性。

## 3.6遗传算法的运行参数 ##

遗传算法中需要选择的运行参数主要有个体编码串长度l、群体大小M、交叉概Pc、变异概率Pm、终止代数T、代沟G等。这些参数对遗传算法的运行性能影响较大，需认真选取。

(1)**编码串长度l**。使用二进编码来表示个体时，编码串长度l的选取与问题所要求的求解精度有关；使用浮点数编码来表示个体时，编码串长度l与决策变量的个数n相等；使用符号编码来表示个体时，编码串长度l由问题的编码方式来确定；另外，也可使用变长度的编码来表示个体。

(2)**群体大小M**。群体大小M表示群体中所含个体的数量。当M取值较小时，可提高遗传算法的运算速度，但却降低了群体的多样性，有可能会引起遗传算法的早熟现象；而当M取值较大时，又会使得遗传算法的运行效率降低。一般建议的取值范围是20~100。

(3)**交叉概率Pc**。交叉操作是遗传算法中产生新个体的主要方法，所以交叉概率一般应取较大值。但若值过大的话，它又会破坏群体中的优良模式，对进化运算反而产生不利影响；若取值过小的话，产生新个体的速度又较慢。一般建议的取值范围是0.4~0.99。

(4)**变异概率Pm**。若变异概率p取值较大话，虽然能够产生出较多的新个体，但也有可能坏掉很多较好的模式，使得遗传算法的性能近似于随机搜索算法的性能；若变异概率取值太小的话，则变异操作产生新个体的能力和抑制早熟现象的能力就会较差。一般建议的取值范围是0.0001~0.1。

(5)**终止代数T**。终止代数T是表示遗传算法运行结束条件的一个参数，它表示遗传算法运行到指定的进化代数之后就停止运行，并将当前群中的最佳个体作为所求问题的最优输出。一般建议的取值范围是100~1000。

至于遗传算法的终止条件，还可以利用某种判定性则，当判定出群体已经进化成熟且不再有进化趋势时就可终止算法的运行过程。常用的判定准则有下面两种：  
●连续几代个体平均适应度的差异小于某一个极小的阈值；  
●群体中所有个体适应度的方差小于某一个极小的阈值。

(6)**代沟G**。代沟G是表示各代群体之间个体重叠度的一个参数，它表示每一代群体中被替换掉的个体在全部个体中所占的百分率，即每一代群体中有(M\*G)个个体被替换掉。例如，G=1.0表示群体中的全部个体都是新产生的，这也是最常见的一种情况；G=0.7则表示70%的个体是新产生的，而随机保留了上一代群体中30%的个体。

## 3.7约束条件的处理方法 ##

实际应用中的优化问题一般都含有一定的约束条件，它们的描述形式各种各样。在遗传算法的应用中，必须对这些约束条件进行处理，而目前还未找到一种能够处理各种约束条件的一般化方法。所以对约束条件进行处理时，只能是针对具体应用问题及约束条件的特征，再考虑遗传算法中遗传算子的运行能力，选用不同的处理方法。

下面介绍，处理约束条件的常用方法。

### 3.7.1搜索空间限定法 ###

基本思想：对遗传算法的搜索空间的大小加以限制，使得搜索空间中表示一个个体的点与解空间中表示一个可行解的点有一一对应的关系。此时的搜索空间与解空间的对应关系如下图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70 3][]  
对一些比较简单的约束条件(如a≤x≤b之类)，在个体染色体的编码方法上着手，就能够达到这种搜索空间与解空间之间的对应的要求。用这种处理方法能够在遗传算法中设置最小的搜索空间，所以它能够提高遗传算法的搜索效率。但需要注意的是除了在编码方法上想办法之外，也必须保证经过交叉、变异等遗传算子作用之后所产生出的新个体在解空间中也要有确定的对应解，而不会产生无效解。

这种处理约束条件的方法可由下面两种方法之一来实现：

**方法一**：用编码方法来保证总是能够产生出在解空间中有对应可行解的染色体。

这个实现方法要求我们设计出一种比较好的个体编码方案。例如，在处理a≤x≤b这样的约束条件时，若使用二进制编码串来表示个体，我们将区间\[a,b\]划分为(![2^l-1][2_l-1])个等分(其中l为个体编码串长度)，![\\delta][delta]为每个等分的长度，并且使编码时的对应关系如下：  
![202012031817447.png][]  
则介于00000000...00000000和11111111...11111111之间的任何编码都会满足上述这个约束条件。

**方法二**：用程序来保证直到产生出在解空间中有对应可行解的染色体之前，一直进行交叉运算和变异运算。  
虽然这个实现方法对编码方法的要求不高，但它有可能需要反复地进行交叉运算和变异运算才能产生出一个满足约束条件的可行解，这样就有可能会降低遗传算法的运行效率。

### 3.7.2可行解变换法 ###

基本思想是：在由个体基因型到个体表现型的变换中，增加使其满足约束条件的处理过程。即寻找出一种个体基因型和个体表现型之间的多对一的变换关系，如下图所示，使进化过程中所产生的个体总能够通过这个变换而转化成解空间中满足约束条件的一个可行解。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70 4][]

这种处理方法虽然对个体的编码方法、交叉运算、变异运算等没有附加的要求，但它却是以扩大搜索空间为代价的，所以一般会使得遗传算法的运行效率有所下降。

例如，在处理![x^2+y^2\\leq 1][x_2_y_2_leq 1]并且x∈\[-1,1\]，y∈\[-1,1\]这个约束条件时，可以把单位圆之外的点都通过该点到圆心的连线而变换到圆周之内。如下图所示，即为单位圆的外点向内点的变换处理过程。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70 5][]

# 参考资料 #

《遗传算法原理及应用》周明、孙树栋编著

[2_l]: https://private.codecogs.com/gif.latex?2%5El
[20201202154109409.png]: https://img-blog.csdnimg.cn/20201202154109409.png
[20201202154229766.png]: https://img-blog.csdnimg.cn/20201202154229766.png
[20201202154317310.png]: https://img-blog.csdnimg.cn/20201202154317310.png
[20201202154340135.png]: https://img-blog.csdnimg.cn/20201202154340135.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201202155614211.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA==,size_16,color_FFFFFF,t_70
[20201202155655822.png]: https://img-blog.csdnimg.cn/20201202155655822.png
[20201202155726452.png]: https://img-blog.csdnimg.cn/20201202155726452.png
[20201202155802785.png]: https://img-blog.csdnimg.cn/20201202155802785.png
[20201202155842853.png]: https://img-blog.csdnimg.cn/20201202155842853.png
[20201202163814785.png]: https://img-blog.csdnimg.cn/20201202163814785.png
[2_2600]: https://private.codecogs.com/gif.latex?2%5E%7B2600%7D
[U_i_min_U_i_max]: https://private.codecogs.com/gif.latex?%5BU%5E%7Bi%7D_%7Bmin%7D%2CU%5E%7Bi%7D_%7Bmax%7D%5D
[20201202164850734.png]: https://img-blog.csdnimg.cn/20201202164850734.png
[x_5.80_6.90_3.50_3.80_5.00_T]: https://private.codecogs.com/gif.latex?x%3D%5B5.80%2C6.90%2C3.50%2C3.80%2C5.00%5D%5ET
[20201202185412746.png]: https://img-blog.csdnimg.cn/20201202185412746.png
[20201202185555752.png]: https://img-blog.csdnimg.cn/20201202185555752.png
[20201202185925866.png]: https://img-blog.csdnimg.cn/20201202185925866.png
[20201202190543773.png]: https://img-blog.csdnimg.cn/20201202190543773.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201202191307774.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA==,size_16,color_FFFFFF,t_70
[2020120219092070.png]: https://img-blog.csdnimg.cn/2020120219092070.png
[20201202191137847.png]: https://img-blog.csdnimg.cn/20201202191137847.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201202191603462.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA==,size_16,color_FFFFFF,t_70
[2020120219205551.png]: https://img-blog.csdnimg.cn/2020120219205551.png
[20201202192212108.png]: https://img-blog.csdnimg.cn/20201202192212108.png
[20201202193150795.png]: https://img-blog.csdnimg.cn/20201202193150795.png
[20201202194514180.png]: https://img-blog.csdnimg.cn/20201202194514180.png
[left _lfloor N_i_ _right _rfloor]: https://private.codecogs.com/gif.latex?%5Cleft%20%5Clfloor%20N_%7Bi%7D%20%5Cright%20%5Crfloor
[left _lfloor x _right _rfloor]: https://private.codecogs.com/gif.latex?%5Cleft%20%5Clfloor%20x%20%5Cright%20%5Crfloor
[20201202195328321.png]: https://img-blog.csdnimg.cn/20201202195328321.png
[lfloor M_2 _rfloor]: https://private.codecogs.com/gif.latex?%24%5Clfloor%20M/2%20%5Crfloor%24
[20201203165206588.png]: https://img-blog.csdnimg.cn/20201203165206588.png
[20201203165048808.png]: https://img-blog.csdnimg.cn/20201203165048808.png
[20201203165257696.png]: https://img-blog.csdnimg.cn/20201203165257696.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201203181329277.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA==,size_16,color_FFFFFF,t_70
[2_l-1]: https://private.codecogs.com/gif.latex?2%5El-1
[delta]: https://private.codecogs.com/gif.latex?%5Cdelta
[202012031817447.png]: https://img-blog.csdnimg.cn/202012031817447.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201203182126349.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA==,size_16,color_FFFFFF,t_70
[x_2_y_2_leq 1]: https://private.codecogs.com/gif.latex?x%5E2&plus;y%5E2%5Cleq%201
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201203182435282.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xZXzYyNA==,size_16,color_FFFFFF,t_70