遗传算法

借鉴生物进化论，遗传算法将要解决的问题模拟成一个生物进化的过程，通过复制、交叉、突变等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解，增加适应度函数值高的解。这样进化N代后就很有可能会进化出适应度函数值很高的个体。
举个例子，使用遗传算法解决“0-1背包问题”的思路：0-1背包的解可以编码为一串0-1字符串（0：不取，1：取）；首先，随机产生M个0-1字符串，然后评价这些0-1字符串作为0-1背包问题的解的优劣；然后，随机选择一些字符串通过交叉、突变等操作产生下一代的M个字符串，而且较优的解被选中的概率要比较高。这样经过G代的进化后就可能会产生出0-1背包问题的一个“近似最优解”。

二进制编码与浮点数编码的区别，主要在于解码的快捷。如果一个个体有多维信息（眼耳口鼻等），每一个都要有对应一个染色体上不同的位置。（也即是若是二进制编码，一个长的二进制不同位置代表不同的特征，不易区分。二用浮点数编码，如上，是分开的，很容易解码与运算）

一、基本思想

遗传算法是模拟达尔文的进化论思想，”生存竞争，适者生存”正好简要的阐述了这一算法的基本特质。用适应函数去考核每个基因的生存能力，用选择交叉变异去实现进化，搜索出种群的近似最优解，其主要步骤如下：
1.初始化种群 2.适应选择 3.交叉变异

二、算法描述

为了更好的描述，这里我以一个01背包问题为例子来简单的阐述遗传算法。
给定一个背包C=100，N=5个物品，其重量和价值分别如下，求这个背包能装的最大价值是多少
1 77 92
2 22 22
3 29 87
4 50 46
5 99 90

2.1编码

针对上面这个问题，首先我们要考虑编码，也就是把它转换成我们的基因型的形式，这里，我们用一个长度为5的二进制字符串表示相应物品的取舍。其基因型（染色体）就是10100,那么表现型就是选择了1号物品和3号物品。有编码自然就有解码，就是把基因型转换成表现型，编码个人认为是遗传算法中至关重要的一步，怎么根据问题去选择编码方式，直接影响了后面所提到的适应函数的简与复杂。
把问题映射到基因型上我们已经解决了，现在就是怎么去考核一个基因型对当前环境的适应度，换句话说就是更有可能存活遗传下去，那么这里我们必须得设计一个适应函数f，因为是求背包的最大值，又因为不能超过背包所能承受的总重量，所以用h(x)表示第二个不超过总重量的条件，f(y)表示背包的价值，所以得到适应函数f(h(x))。

2.2 选择

然后就是怎么去选择的问题，我们用p(x)=f(y)/totall(f(y))来表示某个基因型占总体的概率，现在我们就采用轮盘赌的方法，什么是轮盘赌呢，这里简要提及一下，我们把各个概率放在一个轮盘里，然后转动这个轮盘，最后轮盘停止，指针停在哪里就代表选择哪个概率的事件。
比如在01背包中，我们根据适应函数算出各个基因型的适应度，也算出了每个基因型所占的比例，然后我们根据轮盘赌的方法从中选择出n条基因型出来，然后n条基因型随机两两配对交叉产生两个子代。

2.3 交叉

交叉和生物学中染色体交叉是一样的概念，就是互换某一段基因，这里我们采用的是单点交叉。

2.4 变异

变异是指，在某一个比较小的概率下，某个基因在遗传时，某个基因座上的基因由0边成1，或者由1变成0。
新产生的基因型，如果原来的种群中没有的话，就加进这个种群，然后再按上面所述去迭代，直到找到我们比较满意的基因型为止，现在我们什么都准备好了，就让它们去交配把，去创建一个种族吧。

总结

实际上基本的遗传算法是有很多不足的，如容易选入局部收敛，全局搜索能力不够强，但是基本的遗传算法是有很多可以改进的地方，如交叉算子的设计、变异算子的设计、选择策略等等，有关遗传算法个人觉得作为一种智能启发式搜索算法它甚至比别的普通算法（如动态规划）理解起来还容易，而且它特别容易与别的算法相结合，设计新的混合算法，另外在基本遗传算法的基础上还衍生出了很多别的算法，如免疫遗传算法，这些都是一些比较高级的算法。

三、论文应用

华中农大特等奖淡水养殖池塘水华发生及池水自净化研究 .pdf
遗传算法是基于达尔文的进化论和孟德尔的遗传学说的理论基础发展得到的，是一种依据生物进化思想寻找全局最优解的概率优化算法，可以利用简单的编码技术和算法机制，模拟复杂的优化过程。
常用的标准遗传算法（SGA）基于二进制编码，但存在着一些问题如：易收敛于局部最优值、计算量大、解的精确度不高等。而基于实数编码的加速遗传算法 （RAGA）将标准遗传算法的二进制编码变为实数编码的形式，采用加速循环的方式求解使得求解的速度更为快捷，改善了标准遗传算法的部分问题，故而本文考虑使用基于实数编码的加速遗传算法求解所建立的投影寻踪模型。
RAGA 的求解步骤如下：