现代优化算法三部曲 | 遗传算法

前言

这一篇文章简单地介绍了遗传算法。嗯，毛病没改（见上文的前言）。Besides，本文最大的不足在于根本没有好好介绍编码与遗传算子，算是“不求甚解”，不过入门也应该够了。

遗传算法

可以先看zhuanlan.zhihu.com/p/35986593建立一个大致的印象。

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

1.术语串讲

遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（基因型）是某种基因组合，它决定了个体的形状的外部表现（表现型），如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射（编码）工作（由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码）。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体（遗传算法中每一条染色体，对应着遗传算法的一个解决方案，一般我们用适应性函数来衡量这个解决方案的优劣），并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（基因型到表现型的映射），可以作为问题近似最优解。

2.生物遗传概念在遗传算法中的对应关系

适者生存：算法停止时，优目标值的解有大的可能被留住

个体：解

染色体：解的编码

基因：解中每一分量的特征

适应性：适应度函数值

种群：根据适应度函数值选取的一组解

交配：通过交配原则产生一组新解的过程

变异：编码的某一分量发生变化的过程

3.过程a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。

b)个体评价：计算群体P(t)中各个个体的适应度。

c)选择运算：将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。

d)交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。

e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。

f)终止条件判断：若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。

它必须做以下操作：初始群体的产生、求每一个体的适应度、根据适者生存的原则选择优良个体、被选出的优良个体两两配对，通过随机交叉其染色 体的基因并随机变异某些染色体的基因后生成下一代群体，按此方法使群体逐代进化， 直到满足进化终止条件。

其实现方法如下：

（1） 根据具体问题确定可行解域，确定一种编码方法，能用数值串或字符串表示可行解域的每一解。

（2） 对每一解应有一个度量好坏的依据，它用一函数表示，叫做适应度函数，适应度函数应为非负函数。

（3） 确定进化参数群体规模M 、交叉概率Pc、变异概率Pm、进化终止条件。 为便于计算，一般来说，每一代群体的个体数目都取相等。群体规模越大、越容 易找到优解，但由于受到计算机的运算能力的限制，群体规模越大，计算所需要的时间也相应的增加。进化终止条件指的是当进化到什么时候结束，它可以设定到某一代进化结束，也可能根据找出近似优是否满足精度要求来确定。

4.流程图

5.遗传算法组成· 编码 -> 创造染色体

几种常用的编码技术有二进制编码，浮点数编码，字符编码等。

· 个体 -> 种群

遗传算法中初始群体中的个体是随机产生的。一般来讲，初始群体的设定可采取如下的策略:

a)根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。

b)先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数达到了预先确定的规模

· 适应度函数

适应度函数的设计主要满足以下条件：

a）单值、连续、非负、最大化

b) 合理、一致性

c）计算量小

d）通用性强。

在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。适应度函数设计直接影响到遗传算法的性能。

评价个体适应度的一般过程为：

1. 对个体编码串进行解码处理后，可得到个体的表现型。

2. 由个体的表现型可计算出对应个体的目标函数值。

3. 根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。· 遗传操作——遗传算子

· 选择

从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。

选择的目的是把优化的个体(或解)直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。

选择操作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子有：适应度比例方法、随机遍历抽样法、局部选择法。

· 交叉

在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。

交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。目前常用的交叉算子有（大分类）：实值重组、二进制交叉。

· 变异

变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。依据个体编码表示方法的不同，目前常用的变异算子有：实值变异、二进制变异。

一般来说，变异算子操作的基本步骤如下：

a)对群中所有个体以事先设定的变异概率判断是否进行变异

b)对进行变异的个体随机选择变异位进行变异。

遗传算法引入变异的目的有两个:一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时基于遗传算法的随机优化搜索，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然，此种情况下的变异概率应取较小值，否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。此时收敛概率应取较大值。

· 运行参数

· 是否选择精英操作

· 种群大小

· 染色体长度

· 最大迭代次数

· 交叉概率

· 变异概率

最后看blog.csdn.net/lhy826877974/article/details/82420734巩固一下知识。

（编辑：上海站长网）

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