现代智能优化算法：遗传算法（1）综述

由于遗传算法框架简单，便于实现，而其全部精髓都在于”问题形式化 \rightarrow编码设计\rightarrow算子调整（俗称调参）\rightarrow结果展示“整条工作流程的工程实现上，而无代码不知乎，因此本文将以简短之口舌快速回顾一下遗传算法的基本知识。

遗传算法

遗传算法充分利用了“物竞天择，适者生存”的原理，是一种基于自然群体遗传进化机制的自适应全局优化概率搜索算法。算法的思想是，对于某一类优化问题，也许我们无法给出最优解的性质，但是我们可以找到一种适值函数来对解进行评估，迭代优化适应度函数，适应度函数的优化与解的优化单方向对应。

对于一个已经形式化的最优化问题，适应度函数可以是目标函数本身，也可以是标定的目标函数，见“选择压力”章节。

遗传算法的基本原理

根据问题的目标函数构造一个适值函数，对于一个由多个解（每个解对应一个染色体）构成的种群进行评估、遗传运算、选择，多代繁殖，获得适应值最好的个体作为问题的最优解，这是遗传算法的基本思想和算法流程。遗传算法的基本流程概括如下：

适值函数：目标函数f(x)，产生适值函数F(x)的过程称为标定，即转化为如下的优化问题：

F(x) = -\min f(x) 或者 F(x) = \max f(x)

构成要素实数编码 整数编码：

整数编码适合离散优化问题基于遗传算法的随机优化搜索，常用的一类编码有顺序编码遗传算子变异（Mutation）

变异方法：单点突变，随机选择编码中某个位点，改变该位点的值 选择策略：从种群中选择适应值高的个体以生成交配池的过程

正比选择策略，即每个个体被选中遗传运算的概率为该个体的适应值和种群中个体适应值总和的比例，种群规模为NP，得到选择概率P_i 后，按照旋轮法（Roulette Wheel，轮盘赌）实现选择操作：

PP_0 = 0\\ PP_i = \sum_{j = 1}^iPP_j

共转轮NP次，每次转轮时，随机产生\xi_k\in U(0,1)，当PP_{i-1}\le\xi_k

时，选择个体i.

其他额外的一些选择操作，具体问题具体分析：

选择操作的作用提高了群体适应度，降低了群体多样性

算法流程

一图胜千言。

解空间与编码空间转换

遗传算法的前处理将初始解进行编码，算法本质是在编码空间进行遗传运算（调用遗传算子），而进行解码并在解空间调用适应度函数为编码池的编码进行评估，运行选择策略，最终开启下一轮循环，直到达成停止准则。

遗传算法收敛性理论解释：模版理论

定义：

模版理论：

引入了模版理论后，遗传算法的群体进化过程可以看作通过选择、交叉、变异等遗传算子的运算来不断寻找好的模版的过程。

引理1：

在正比选择（轮盘赌选择）下，模版S在t+1代的期望个体数为 E(S,t+1) = f(S,t)N(S,t)，其中f(S,t)是t代模版中所有个体的适应值的均值与种群中所有个体的适应值均值的比。

引理2：（单点交叉）

第t代以概率P_c做交叉，对长度为l(S) 的模版中的个体，则在第t+1代中该个体仍然为S中个体的概率的下界为：

P(S,t+1) \ge1-\frac{P_c\,l(S)}{n-1}(1-P(S,t)) ，其中P(S,t)为第t代个体为模版S的概率

引理3:（变异）

若t代以概率P_m做变异，对于一个阶数为K(S)的模版S重点额个体，则在t+1代仍为S的概率的下界为：

P(S,t+1)\ge1-P_m\cdot K(S)

主定理（模版定理）：

第t代以概率P_c和P_m发生交叉和变异的时候，长度为l(S)，阶数为K(S)，适应值均值为f(S,t)的模版S在第t+1代的期望的个体数的下界为：

E(S,t) = [1-\frac{P_c\,l(s)}{n-1}(1-P(S,t))-K(S)P_m]f(S,t)N(S,t)

如果：

f(S,t)\ge[1-\frac{P_c\,l(S)}{n-1}(1-P(S,t))-K(S)P_m]^{-1}

则E(S,t)随着代数t增加而增加。

改进与变形编码方法遗传运算中的问题顺序编码的合法性修复变异修复策略

2. 实数编码合法性修复

适值函数的标定

通过标定使得目标函数映射为适值函数

定义：选择压力

选择压力指种群中好、坏个体被选中的概率差，如果差较大则选择压力大，通过调节选择压力的大小可以实现遗传算法中局部搜索和广域搜索的调节

局部搜索、广域搜索与选择压力的关系

局部搜索是针对一个较小的区域进行搜索，致力于找到更好、更精确的解，而广域搜索是进行大面积的搜索，希望找到较好的解存在的区域，显然，局部搜索和广域搜索是遗传算法的一对矛盾

适值函数的标定方法

最大化标定：F = \frac{f-f_{min}+r}{f_{max}-f_{min}+r}

最小化标定：F = \frac{f_{max}-f+r}{f_{max}-f_{min}+r}

其中r\in(0,1)

选择策略

概率归一化：当NP有限的时候，\sum_{j=1}^{NP}q(1-q)^{j-1}，令p_j = \bar{q}(1-q)^{j-1}，其中\bar{q} = \frac{q}{1-(1-q)^{NP}}

停止准则高级基因操作

在染色体中随机指定两个基因的位置为倒位点，以倒位概率P_i顺序翻转两个倒位点之间的基因

下一篇讲一讲如何构造一个优化问题的维度适应遗传算法框架，要上python辣。

Reference：

智能优化方法，汪定伟等，高等教育出版社，2007.

（编辑：清远站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!