优化算法之遗传算法

前几天，在听了学长关于遗传优化算法应用在考虑TMD作用的地震分析之后，感觉到优化算法一系列的优化算法的强大之处。回来也趁热打铁查了一下资料，大致理解一下遗传算法的机理。下面就记录分享一下吧。

一、遗传算法简介

顾名思义，遗传算法是模拟生物在自然环境下的遗传和进化过程的一种自适应的全局优化搜索算法，通过借助遗传学的原理，经过自然选择、遗传、变异等作用机制进而筛选出具有适应性更高的个体（适者生存）。遗传算法从20世纪七八十年代的诞生到现在主要集中的适用范围为：NP问题（指存在多项式算法能够解决的非决定性问题）、非线性、多峰函数优化和多目标优化问题等等。同时在机器学习、模式识别和神经网络及社会科学中的应用也显得非常出色。

二、遗传算法的算法理论

2.1遗传算法基本概念与术语：

遗传算法的概念简单来说，就是利用种群搜索技术将种群作为一组问题解，通过对当前种群施加类似生物遗传环境因素的选择、交叉、变异等一系列的遗传操作来产生新一代的种群，并逐步使种群优化到包含近似最优解的状态。

术语：

遗传算法基本术语 遗传学术语遗传算法术语

种群

可行解集

个体

可行解

染色体

可行解的编码

基因

可行解编码的分量

基因形式

遗传编码

适应度

评价的函数值（适应度函数）

选择

选择操作

交叉

编码的交叉操作

变异

可行解编码的变异

注意：这里的个体与染色体的关系，我个人进行一下解释。我可以把个体当做是染色体的组合。换句话说呢，就是染色体决定了个体，染色体上基因的操作（选择、交叉、变异）直接作用于个体的形态。所以呢，我们必须是基于对染色体、基因进行遗传学的操作，但是我们想象一下，在可行解中，我们对其进行一系列的遗传学操作，怎样才能直接影响到可行解呢？我们怎样才能进行对可行解实体进行分解？这里我们就引进了编码成位串。“编码”一词对于非科班的学生来说，显得有些抽象。我就简单做个解释吧：在我们大学计算机基础课上，我们知道数字的表示有二进制、八进制、十进制（日常所用）、十六进制等。比如十进制的10，我们可以用二进制位串表示为1010（0*2^0+1*2^1+0*2^2+1*2^3）。这样1010位串就是对10进行编码,反过来多十进制的10转化为1010的二进制也称作解码（相对于编码来说）。这样把十进制的10编码成1010的二进制位串就可以实现对1010的遗传操作了。具体的进制转化可以看我以前的博客“二进制、十进制、八进制、十六进制转化详解”。

三、遗传操作：

遗传操作：就包括优选适应性强的个体的“选择”；个体间交换基因产生新个体的“交叉”；个体间的基因突变而产生新个体的“变异”。其中遗传算法是运用遗传算子来进行遗传操作的。即：选择算子、变异算子、交叉算子。

1.选择算子：根据个体的适应度，按照一定的规则，从第n代群体中选择出一些具有优良性状的个体遗传到下一代（n+1）群体中。在这一选择过程中，个体适应度越大，则被选择到下一代的机会越大。某个体i的适应度fi，种群大小NP，则i被选择的概率公式为：

2.交叉算子：将群体P(n)中选中的各个个体随机搭配，对于每一个个体，以某一特定概率（交叉概率Pc（0.25-1.0取值））交换他们之间的部分染色体（编码位串的部分位置）。交叉算法是的，遗传算法的搜索能力得到更好的延伸。

2.1交叉操作的具体步骤可以表述为：1.在交配池中随机取出要交配的一对个体；2，根据编码位串长度L，对要交配的一对个体，随机选取[1,L-1]中的一个或者多个整数k作为交叉位置处，相互交换各自的部分基因，由此形成新的个体。

3.变异操作：对群体的每个个体，以某一个概率（变异概率Pm（0.01-0.1取值））将某一个或者某些基因座上的基因值改变为其他的等位基因值，根据个体的编码方式不同，可以将变异分为实值变异和二进制变异。

3.1变异的操作步骤为：首先基于遗传算法的随机优化搜索，对种群中的所有个体按事先的设定的变异概率判断是否进行变异操作；然后 对判断需要变异的个体进行随机选择变异位进行变异。

四、遗传算法特点：

4.1、遗传算法以决策变量的编码作为运算对象，这种对决策变量的编码处理，使得在优化计算中可以借鉴生物学的染色体和基因概念，模拟自然界的生物遗传和进化机制，方便的应用决策变量的编码成的位串进行遗传算子。

4.2、遗传算法直接是以目标函数值作为搜索收敛条件。它仅仅使用目标函数值变换来的适应度函数值，就可以确定进一步的搜索方向和范围。而不是使用目标函数的求导来进行。简化了算法

4.3、遗传操作是基于概率因子来操作的。

4.4、遗传算法是自组织、自适应个自学习的。

五、遗传算法的流程图：

六、Matlab遗传算法的仿真实例：

实例：利用标准遗传算法求函数

的最大值，其中定义域为[0,10]。（摘自智能优化算法及Matlab实例）

运用matalb画图功能我们可以得到原函数的代码和图形如下：

1.原图形画图命令：

x = linspace(0,10);
y = x + 10*sin(5*x) + 7*cos(4*x);
plot(x,y)

2.图像结果

根据流程图步骤仿真步骤如下：

1.初始化种群，种群数目NP=50，染色体编码长度为L = 20，最大进化代数G = 100，交叉概率为Pc=0.8,变异概率为Pm=0.1。

2.产生初始种群，将二进制编码转化为十进制，计算个体的适应度，并进行归一化，之后进行遗传操作，产生新的种群。并把优势种群遗传到下一代。

3.判断是否满足终止条件。满足则输出，不满足则继续迭代优化。

具体代码这里篇幅有限就不列出来了，需要的可以联系本人自取！

（编辑：92站长网）

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