遗传算法
概 述
遗传算法（Genetic Algorithm，GA）最早是由美国的 John holland于20世纪70年代提出，该算法是根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。该算法通过数学的方式，利用计算机仿真运算，将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时，相对一些常规的优化算法，通常能够较快地获得较好的优化结果。遗传算法已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。
01
大致了解
遗传算法属于启发式算法的一种，大家理解启发式算法的时候可以将其与枚举法类比。举个简单的例子，我们在求解某一函数f（x）的最大值时，通常的方法是通过求导，找到极值点。但是大家一定还知道另外一种最笨的办法，就是枚举法。假设x的可行域在［0，1］之间，x最大值的精确度是0．01，那就可以把［0，1］之间所有的可行解（0．01， 0．02， 0．03，．．． 0．98， 0．99， 1．00）都拿出来代入f（x），计算比较它们的大小，找到最大值对应的x＇即为最优解，f（x＇）为最大值。但是这种方法的求解效率太低了，为了解决这一问题，各路大神就根据各种学科的不同原理，比如生物界的遗传、鱼群、蚁群、冶金学的退火等，将这些理论应用在求解中，以提高求解效率。同样是不断地尝试找到最优解，利用这些原理可以让尝试的过程没那么盲目，而是按照一定的规律去寻找最优解，可以有效地提高求解效率，让我们更快地寻找到f（x）的最优解。
总之，为了更容易理解遗传算法，大家首先可以有一个大致的思维：遗传算法是枚举法的升级版本。
02
简单算例
问题：求解函数 f（x） ＝ x ＋ 10＊sin（5＊x） ＋ 7＊cos（4＊x） 在区间［0，9］的最大值。
p．s． f（x） 函数大致图像如上图
流程：遗传算法（Genetic Algorithm）遵循『适者生存』、『优胜劣汰』的原则，是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。遗传算法模拟一个人工种群的进化过程，通过选择（Selection）、交叉（Crossover）以及变异（Mutation）等机制，在每次迭代中都保留一组候选个体，重复此过程，种群经过若干代进化后，理想情况下其适应度达到＊＊＊近似最优＊＊＊的状态。
p．s． 遗传算法流程图如上图
组成：
✧ 编码 －＞ 创造染色体
✧ 个体 －＞ 种群
✧ 适应度函数
✧ 遗传算子
• 选择
• 交叉
• 变异
✧ 运行参数
• 是否选择精英操作
• 种群大小
• 染色体长度
• 最大迭代次数
• 交叉概率
• 变异概率
编码与解码：
实现遗传算法的第一步就是明确对求解问题的编码和解码方式。
对于函数优化问题，一般有两种编码方式，各具优缺点。
实数编码：直接用实数表示基因，容易理解且不需要解码过程，但容易过早收敛，从而陷入局部最优；
二进制编码：稳定性高，种群多样性大，但需要的存储空间大，需要解码且难以理解。
对于求解函数最大值问题，我一般选择二进制编码：
以目标函数 f（x） ＝ x ＋ 10sin（5x） ＋ 7cos（4x）， x∈［0，9］ 为例。
假如设定求解的精度为小数点后4位，可以将x的解空间划分为 （9－0）×（1e＋4）＝90000个等分。
2＾16＜90000＜2＾17，需要17位二进制数来表示这些解。换句话说，一个解的编码就是一个17位的二进制串。
一开始，这些二进制串是随机生成的。
一个这样的二进制串代表一条染色体串，这里染色体串的长度为17。
对于任何一条这样的染色体chromosome，如何将它复原（解码）到［0，9］这个区间中的数值呢？
对于本问题，我们可以采用以下公式来解码：
x ＝ 0 ＋ decimal（chromosome）×（9－0）／（2＾17－1）decimal（ ）： 将二进制数转化为十进制数
一般化解码公式：
f（x）， x∈［lower＿bound， upper＿bound］x ＝ lower＿bound ＋ decimal（chromosome）×（upper＿bound－lower＿bound）／（2＾chromosome＿size－1）f（x）， x∈［lower＿bound， upper＿bound］x ＝ lower＿bound ＋ decimal（chromosome）×（upper＿bound－lower＿bound）／（2＾chromosome＿size－1）lower＿bound： 函数定义域的下限
upper＿bound： 函数定义域的上限
chromosome＿size： 染色体的长度
通过上述公式，我们就可以成功地将二进制染色体串解码成［0，9］区间中的十进制实数解。
个体与种群：
『染色体』表达了某种特征，这种特征的载体，称为『个体』。
对于本次实验所要解决的一元函数最大值求解问题，个体可以用上一节构造的染色体表示，一个个体里有一条染色体。
许多这样的个体组成了一个种群，其含义是一个一维点集（x轴上［0，9］的线段）。
适应度函数：
遗传算法中，一个个体（解）的好坏用适应度函数值来评价，在本问题中，f（x）就是适应度函数。
适应度函数值越大，解的质量越高。
适应度函数是遗传算法进化的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。
遗传算子：
我们希望有这样一个种群，它所包含的个体所对应的函数值都很接近于f（x）在［0，9］上的最大值，但是这个种群一开始可能不那么优秀，因为个体的染色体串是随机生成的。
如何让种群变得优秀呢？
不断地进化
每一次进化都尽可能保留种群中的优秀个体，淘汰掉不理想的个体，并且在优秀个体之间进行染色体交叉，有些个体还可能出现变异。
种群的每一次进化，都会产生一个最优个体。种群所有世代的最优个体，可能就是函数f（x）最大值对应的定义域中的点。
如果种群无休止地进化，那总能找到最好的解。但实际上，我们的时间有限，通常在得到一个看上去不错的解时，便终止了进化。
对于给定的种群，如何赋予它进化的能力呢？
首先是选择（selection）
✧ 选择操作是从前代种群中选择＊＊＊多对＊＊＊较优个体，一对较优个体称之为一对父母，让父母们将它们的基因传递到下一代，直到下一代个体数量达到种群数量上限
✧ 在选择操作前，将种群中个体按照适应度从小到大进行排列
✧ 采用轮盘赌选择方法（当然还有很多别的选择方法，比如竞标赛法），各个个体被选中的概率与其适应度函数值大小成正比
✧ 轮盘赌选择方法具有随机性，在选择的过程中可能会丢掉较好的个体，所以可以使用精英机制，将前代最优个体直接选择
其次是交叉（crossover）
✧ 两个待交叉的不同的染色体（父母）根据交叉概率（cross＿rate）按某种方式交换其部分基因
✧ 采用单点交叉法，也可以使用其他交叉方法
最后是变异（mutation）
✧ 染色体按照变异概率（mutate＿rate）进行染色体的变异
✧ 采用单点变异法，也可以使用其他变异方法
一般来说，交叉概率（cross＿rate）比较大，变异概率（mutate＿rate）极低。像求解函数最大值这类问题，我设置的交叉概率（cross＿rate）是0．6，变异概率（mutate＿rate）是0．01。
因为遗传算法相信2条优秀的父母染色体交叉更有可能产生优秀的后代，而变异的话产生优秀后代的可能性极低，不过也有存在可能一下就变异出非常优秀的后代。这也是符合自然界生物进化的特征的。
03
算例代码
上述算例是我学习遗传算法时的算例，比较容易理解，如果还有不懂得可以后台联系我们，这里附上算例的代码（matlab版本）：
链接：https：／／pan．baidu．com／s／1rvhtA4kaxQuJTmndiVS71Q提取码：bfrr
