遗传算法（Genetic Algorithm, GA）

注：此文是学习了多个博客和视频，整理总结。如有侵犯，请私聊。

一、遗传算法是什么？

1.就是在一个有可能存在解集的种群开始寻找。（假设我有X这个集，X集中包含不重复的X1,X2,X3....，我的最优解有可能在里面，这个X就是我的种群）

2.种群是由多个个体组成的。（个体就是里面的X1,X2,X3.....）

3.一个个体是由多个基因组成的。（而我每一个Xi,都是由多个x1，x2,x3...组成的。这些x1,x2,...就是基因。）

二、遗传算法模仿的思路？

优胜弱汰~~~~

三、模仿出来的思路？

<一>编码

1.意思：GA在进行搜索之前将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合构造成了不同的点。简单理解：把我们要寻优的问题，用数学表达出来，映射在优化问题上。把实属值根据编码规则转化为对应的字串。

2.编码方式：二进制编码：有比浮点编码有更好的搜索能力。

                   浮点编码：比二进制编码在变异上可以有更多的种群多样性。

                    格雷编码、符号编码、复数编码、DNA编码。

3.举例说明：（二进制编码）变量x在[-2,3]，要求精度10^-5.

                    换句话来说，是要在-2到3这个区间分500000个值。

                    log2（500000）=18.93

                    所以我们要用19位二进制把x表示。

<二>初始群体的生成

1.意思：随机产生的几个初始串结构数据，每个串结构数据称为一个个体，N个个体构成一个群体。而GA以这N个串结构数据作为初始点开始进化。

2.N的重要性：如果N太小，会很慢才能遍历整个解空间。

                      如果N太大，会出现两个个体很相似，导致计算量大。偶合性很高的迭代回归问题。

<三>适应度评估

1.适应度都表明个体或解的优劣性。不同的问题，适应性的函数的定义方式不同。

2.常用三种常用的适应度评价

    直接以待求解的目标函数为适应度函数。（是为了计算个体的适配值，适配值非负，且越大越好）

        例：若目标函数为最大值问题，则Fit(f(x))=f(x)

               若目标函数为最小值问题，则Fit(f(x))=-f(x)

        优点：简单直观

        缺点：1.可能满足不到非负的要求。

                   2.有些函数值分析相差很大，由此得到的平均适应度可能不利于体现种群的平均性能。

    界限构造法（不想打了）

        例：

    倒数法（还是不想打了）

         例：

<四>选择

1.选择的目的是为了从前群体中选出优良的个体，使他们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。

2.如何选择

选择算子

F:按比例的分配：利用比例与各个个体适应度的概率决定其子孙的遗留可能性。若某个个体i，其适应度为fi，则被选中的概率

                                                                                Pi=fi/sum(all fi)

                        概率大的，能多次被选中，它的遗传因子也会扩大。

S:基于排序：种群按目标值进行排序。适应度取决于排位。（更有鲁棒性）

选择操作

轮盘赌选择性、随机遍历抽样法、局部选择法、截断选择法、锦标赛选择性。

<五>交叉

1.交叉操作是遗传算法中最重要的遗传操作。通过交叉操作可以得到新一代个体，新个体组合了其父辈个体的特性。交叉体现了信息交换的思想。

2.重点：交叉率的选择决定了交叉的概率。

            较大，可以各代充分交叉，但群体中的优良模式遭到破坏。

            较小，会使很多个体直接复制到下一代，遗传搜索会停滞。

            一般选择0.4-0.9

3.方法：对于二进制编码：单点交叉、多点交叉、均匀交叉。

<六>变异

1.变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，GA中变异发生的概率很低，通畅取值很小。

2.变异是随机抽取的，使算法具有局部的随机搜索能力；同时使得遗传算法保持多样性。防止非成熟收敛。

3.一般取值：0.001-0.1。如果大于0.5就变为随机搜索了。

<七>两大问题

    欺骗问题：H与H'，*位置一样，且最大值为F(x*)，H为一包含X*的m阶模式，F(H)>F(H')，则f为m阶欺骗。

                            例如：F(11)为最大值。若：F(*1)<F(*0),F(*1)<F(0*),F(1*)<F(*0),F(*1)<F(0*),任何一条成立

                                       则为欺骗。

        个人理解：就是妨碍高适应度模式生成的都是欺骗，就是把导向引歪了。

    未成熟收敛：还没找到全局最优，但又找不到比父代更好的。

<八>优缺点：

    优点：1.良好的并行性（操作对象是一组可行解；搜索轨道有多条）

                    2.强大的通用性（只需利用目标的取值信息，无需梯度等高价值信息）

                    3.良好的全局优化性和鲁棒性

                    4.  良好的可操作性

    缺点：1.未成熟收敛问题

                    2.收敛速度较慢，算法实时性欠佳

<九>两个流程图：

遗传算法优化BP神经网络初始权值与阈值

代码：https://github.com/chocolatechu/Genetic-Algorithm--GA