遗传算法

1 遗传算法概述

• 一种仿生全局优化算法
• 模仿生物的遗传进化原理，通过选择（Selection）、交叉（Crossover）与变异（Mutation）等操作机制，使种群中个体的适应度（FItness）不断提高
• 核心思想：物竞天择，适者生存。“天"：适应度函数（Fitness Function）

2 遗传算法的特点

四大优点：

• 良好的并行性（良好的并行性（操作对象是一组可行解；搜索轨迹有多条）
• 强大的通用性（只需要目标的取值信息，无需梯度等高价值信息）
• 良好的全局优化性和鲁棒性
• 良好的可操作性

两个缺点：

• 未成熟收敛问题
• 收敛速度较慢，算法实时性欠佳。

3 遗传算法生物学基础

4 标准遗传算法

4.1 遗传算法的基本流程

4.2 遗传算法的若干基本概念

• 个体(Individual) 称 S = { 0 , 1 } l S=\{0,1\}^l S={0,1}l为个体空间，个体空间的元素$a=a_0{a}_1...a_{l-1}\in S$称为个体，它是染色体带有特征的实体。分量$a_j$称为基因，正整数$l$称为个体的基因长度。（函数的一个解）
• 种群(Population)称个体空间$S$中$N$个个体组成的一个子集（个体允许重复）称为一个种群，记为：$A=(A_1,A_2,...,A_N)$，其中$A_j(j=1,2,..,N)$，N为种群规模。（函数多个解组成）
• 适应度（Fitness）：在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个五种对于生存环境的适应程度。对生存环境适应程度高的物种将获得更多繁殖机会，而对生存环境适应程度较低的物种，其繁殖的机会就相对较少，甚至逐渐灭绝。在遗传算法中，一般用适应度函数(Fitness function)来衡量某一个体的适应度高低（适应度用来评价给定解好不好，适应度函数就是要求最优的那个函数，用它计算适应度）
• 编码（Coding）：将一个待求解的问题的实际可行解从其解空间转换到遗传算法所能处理的搜索空间（即个体空间）的过程，就称为编码。（编码是为了交叉变异）
• 解码（Decoding）:解码就是将遗传算法所搜索到的最优个体的染色体转换称待求问题的实际最优解的过程，即编码的逆过程。
• 选择操作（Selection）:根据各个个体的适应度，按照一定规则，从第t代群体$P(t)$中选择出一些优良的个体遗传到下一代群体$P(t+1)$中。一般地，选择操作通过选择算子(Selection Operator)进行。
• 交叉操作（Crossover）：将群体$P(t)$内的各个个体随机搭配成对，对每一对个体，以某种概率（称为交叉概率）遵循某一种规则交换它们之间的部分染色体。
• 变异操作（Mutation）：对群体$P(t)$中的每一个个体，以某概率（称为变异概率）改变某一个或某一些基因上的基因值为其他等位基因。

4.3 遗传算法的应用步骤

（1）确定决策变量以及各种约束条件，即确定出个体的表现型X和问题的解空间。
（2）建立优化模型，确定出目标函数的类型及其数学描述形式或量化方法。
（3）确定表示可行解的染色体编码方法，即确定出个体的基因型$X^{\ast }$，及遗传算法的搜索空间。

编码是遗传算法解决问题的先决条件和关键步骤

• 不仅决定个体基因的排列形式（从而决定选择于繁殖等操作的作用方式），而且也决定了从搜索空间的基因型到解空间的表现型的解码方式（从而决定对GA所获得解的翻译与理解）；
• 决定GA搜索的困难度与复杂性
• 决定对问题的求解精度

常用的编码方式有：二进制编码、浮点数编码等。二进制编码比浮点数编码搜索能力强，但浮点数编码比二进制编码在变异操作上能够保持更好的种群多样性。

标准遗传算法多采用二进制编码方法，将决策变量用二进制字符串表示，二进制编码的长度由所求精度确定。然后将各决策变量的二进制编码串连在一起，构成一个染色体。

（4）确定解码方法，即确定出由个体基因型$X^{\ast }$，到个体表现型$X$的对应关系和转换方法。

（5）确定个体适应度的量化评价方法，就是确定出由目标函数值到个体适应度的转换规则。标准遗传算法的适应度函数常用以下三种：

• 直接以待求解的目标函数为适应度函数（常用）
  若目标函数为最大值函数，则$Fit(f(X))=f(X)$
  若目标函数为最小值函数，则$Fit(f(X))=-f(X)$
  优点：简单直观；
  缺点：其一，可能不满足非负的要求；其二，某些代求解的函数值分布相差很大，由此得到的平均适应度可能不利于体现种群的平均性能。

• 界限构造法：
  
  
  该方法是第一种方法的改进，但有时存在界限值预先估计困难或估计不精确等问题。

• 倒数法：
  

（6）确定各遗传具体操作方法

<1>选择算子和选择操作
个体选择概率的常用分配方法有以下两种：

• A按比例的适应度分配（Proportional Fitness Assignment）亦可称为选择的蒙特卡罗方法，是利用比例于各个个体适应度的概率决定其子孙的遗留可能性。若某个个体$i$，其适应度$f_i$，则其被选择的概率表示为：
  
  显然适应度大的（选择概率大）的个体，能被多次选中，它的遗传因子就会在种群中扩大。

• 基于排序的适应度分配：在基于排序的适应度分配中，种群按目标值进行排序。适应度仅仅取决于个体在种群中的序位，而不是实际的目标值。
  排序方法比比例方法表现出更好的鲁棒性，它能在一定程度上克服了比列适应度计算的尺度问题和过早收敛问题。

个体选择概率确定后，可以选用的选择算法有：轮盘赌选择法、随机遍历抽样法、局部选择法、截断选择法和锦标赛选择法等。标准遗传算法常用的轮盘赌选择法的原理如下图所示：

轮盘赌选择法

另外，还可采用以下几种提高遗传算法性能的方法：

• 稳态繁殖：在迭代过程中用部分优质新子个体来更新群体中部分夫个体，作为下一代种群。
• 没有重串的稳态繁殖：在稳态繁殖的基础上，形成下一代种群时，使其中的个体不重复。

<2>交叉率及交叉操作
交叉，也可以称为基因重组，是遗传算法获取新的优良个体的最重要手段，决定了遗传算法的全局搜索能力。
一般地，当随机产生的概率大于交叉率，遗传算法就会按一定规则选择两个个体，执行交叉操作。交叉率的选择决定了交叉的频率，较大的交叉率使各代充分交叉，但群体中的优良模型遭到破坏的可能性增大，以致产生较大的代沟，从而使搜索走向随机化；交叉率越低，产生的代沟越小，就会使得更多的个体直接复制到下一代，遗传搜索可能陷入停滞状态，一般建议取值范围0.4-0.9。
对于二进制编码，常用的交叉方法有：单点交叉、多点交叉和均匀交叉。一个单点交叉的例子如下图：

此外，还有部分匹配交叉、顺序交叉、洗牌交叉等

<3>变异率和变异操作
变异本身是一种局部随机搜索，使遗传算法具有局部随机搜索能力；同时使得遗传算法保持种群的多样性，以防止出现非成熟收敛。
一般地，随机产生的概率大于变异率就会触发变异操作。变异率一般可取0。001~0.1。变异率不能取得太大，如果大于0.5，遗传算法就退化为随机搜索，而遗传算法的一些重要的数学特性和搜索能力也不复存在了。
常用的变异操作方法有：实值变异法和二进制变异法等。

（7）确定遗传算法的有关运行参数，包括群体规模（Popsize）、迭代次数（一般取100-500）、选择算子、交叉率、变异率等。

（8）初始化群体

• 初始群体一般随机产生
• 初始值最好能在解空间中均匀采样（收敛速度比较快）
• 对于非二进制编码，还要考虑所生成的染色体是否在可行域内。

（9）计算群体个体编码后的适应值

（10）按照遗传策略，运用所选定的选择、交叉和变异算子作用于群体，生成下一代群体。
（11）判断群体性能是否满足某一指标或是否完成预定迭代次数，不满足则回到（9）

4.4 未成熟收敛问题

1 未成熟收敛现象：
未成熟收敛现象是遗传算法中的特有现象，且十分常见。它是指当遗传算法还没找到全局最优解或满意解时，群体中不能再产生性能超过父代的后代，群体中的各个个体非常相似。未成熟收敛的重要特征是群体中个体结构的多样性急剧减少。

原因：

• 理论上考虑的选择、交叉、变异操作都是绝对精确的，他们相互协调，能搜索到整个解空间，但实际不然。
• 存在随机误差（主要包括取样误差和选择误差）
• 所求解的问题是遗传算法的欺骗问题

防止：

---

遗传算法具体步骤小结：

5MATLAB遗传算法工具箱下载

6 MATLAB遗传算法工具箱用法：

补充：

FieldD=[len lb ub code scale lbin ubin]' 是译码矩阵，一般用于二进制串到实值的转换

其中len是包含在Chrom中每个字符串的长度，lb和ub是行向量，指明每个变量的下界和上界，code表明如何编码（code=1二进制，code=0格雷），scale指明刻度（scale=0算数，scale=1对数），lbin和ubin表示是否包含边界，0表示去掉，1表示包含

代沟参数GGAP：就是上一代(假设总数为100)通过轮盘法筛选后要舍弃部分适应度低的基因(假设为20),则下一代就剩下80个基因.代沟就是80/100=0.8,以此类推.