基本遗传算法介绍

1. 导言

遗传算法是群智能优化计算中应用最为广泛、最为成功、最具代表性的智能优化方法。它是以达尔文的生物进化论和孟德尔的遗传变异理论为基础，模拟生物进化过程和机制，产生的一种群体导向随机搜索技术和方法。

2. 基本原理

2.1 基本思想

遗传算法的基本思想：首先根据待求解优化问题的目标函数构造一个适应度函数。然后，按照一定的规则生成经过基因编码的初始群体，对群体进行评价、遗传运算（交叉和变异）、选择等操作。经过多次进化，获得适应度最高的一个或几个最优个体作为问题的最优解。

2.2 组成元素

2.2.1 编码方法

编码是对问题的可行解的遗传表示，是影响算法执行效率的关键因素的之一。遗传算法中，一个解 $X\in P$ 称为个体或染色体（chromosome），染色体由被称为基因（gene）的离散单元组成，每个基因控制颜色体的一个或多个特性，通常采用固定长度的0-1二进制编码，每个解对应一个唯一的二进制编码串编码空间中的二进制位串称为基因型（genotype）。而实际所表示问题的解空间的对应点称为表现型（phenotype）。

常见编码方法：

二进制编码

实数编码

顺序编码

2.2.2 种群初始化方法

种群由个体构成，每个个体的染色体对应优化问题的一个初始解。

常见种群初始化方法：

随机方法

基于反向学习优化的种群产生法：首先随机生成一个种群 $P(N)$ ，然后按照反向学习方式生成一个新的种群 $OP(N)$ ，合并两种群得到新的种群 $S(N)$ 。

2.2.3 适应度函数的设计

适应度函数是评价种群中个体对环境适应能力的唯一确定性指标，体现出“适者生存，优胜劣汰”这一自然选择原则。

常见适应度函数设计方法( $f(x)$ 是目标函数)：

线性变换： $F(x) = a^kf(x)+b^k$

幂律变换： $F=f^a(x)$

指数变换： $F(x) = a\cdot e^{bf(x)}+c$

对数变换： $F(x) = a\cdot \ln f(x) +b$

2.2.4 选择策略

遗传算法在每次迭代过程中，在父代种群中采用某种选择策略选择出指定数目的哥特体提进行遗传操作。最常用的选择策略是正比选择（proportional selection）策略。

正比选择策略：种群中每个个体被选中进行遗传运算的概率与其适应度大小成正比。即
$P_i = \frac{F_i}{\sum_{i=1}^nF_i},\quad i=1,2,\cdots,n$

2.2.5 遗传操作

2.2.5.1 交叉算子

在交叉算子中，通常由两个被称为父代（parent）的染色体组合，形成新的染色体，称为子代（offspring）。父代是在种群中根据个体适应度进行选择，因此适应度较高的染色体的基因更有可能被遗传到下一代。通过在迭代过程中不断地应用交叉算子，使优良个体的基因得以在种群中频繁出现，最终使得整个种群收敛到一个最优解。

常见交叉算子：

单点交叉

双点交叉

单形杂交

球形杂交

2.2.5.2 变异算子

在染色体交叉之后产生的子代个体，其基因位可能以很小的概率发生转变，这个过程称为变异。变异是为了增强种群的多样性，将搜索跳出局部最优解。

常见变异算子：

按位变异

高斯变异

有向变异

2.2.6 停止准则

遗传算法的停止准则一般采用设定最大迭代次数或适应值函数评估次数，也可以是规定的搜索精度。

2.3 算法流程

已Holland的基本GA为例介绍算法等具体实现，具体的执行过程描述如下：

Step 1： 初始化。随机生成含有 $N$ 个个体的初始种群 $P=\{ X_1,\cdots,X_n \}$ ，每个个体经过编码对应着待求解优化问题的一个初始解。

Step 2： 计算适应值。个体 $X_i,i=1,2,\cdots,n$ ，由指定的适应度函数评价其适应环境的能力。不同的问题，适应度函数的构造方式也不同。对函数优化问题，通常取目标函数作为适应度函数。

Step 3： 选择。根据某种策略从当前种群中选择出 $M$ 个个体作为重新繁殖的下一代群体。选择的依据通常是个体的适应度的高低，适应度高的个体相比适应度低的个体为下一代贡献一个或多个后代的概率更大。选择过程提现了达尔文“适者生存”原则。

Step 4： 遗传操作。在选出的 $M$ 个个体中，以事件给定的杂交概率 $P_c$ 任意选择出两个个体进行交叉运算，产生两个新的个体，重复此过程直到所有要求杂交的个体杂交完毕。根据预先设定的变异概率 $P_m$ 在 $M$ 个个体中选择出若干个体，按一定的策略对选出的个体进行变异运算。

Step 5： 检验算法等停止条件。若满足，则停止算法的执行，将最优个体的染色体进行解码得到所需要的最优解，否则转到Step 2继续进行迭代过程。