虽然遗传算法存在诸如陷入局部最优解，收敛速度缓慢等问题，人们也进行了很多的修改，但是鉴于遗传算法本身就具有很高的性能，而且各种修正方案都存在一定的复杂性和非普适性，所以经典遗传算法在应用领域还是几乎绝对的主流。
二、遗传算法的原理
-
种群初始化：在可行域内随机产生若干个解，称其为初始种群。
-
对种群内的每个解进行适应度评估，评价每个个体对环境的适应程度强弱。
-
适者生存，不适者淘汰，运用随机数等方式，将不适合的个体淘汰，适合的保留。
-
通过交叉互换、变异等方式对中云进行扰动，实质上就是在可行域内进行搜索，搜索出最适合环境的解。
上述的环境是指目标函数，需要求解最优值的函数，每个个体就是每个可行解，适应度评估就是将可行解带入函数进行计算然后对比其大小，如果可行解代入函数的结果最优，那这个解就是最优解。优胜劣汰是对优秀解的保留，较差解的淘汰，交叉和变异就是对解进行扰动，以进一步提高解的优度。
三、遗传算法实现
遗传算法的机理相对复杂，而使用时可能需要编程实现，有没有什么比较方便的现成的工具能够快速使用遗传算法呢？答案！
没有！
的反义词！哈哈！
在Matlab中已经由封装好的工具箱命令，通过调用就能够十分方便的使用遗传算法啦！
先来说说简单命令：
函数ga：
[x, fval,reason]= ga(@fitnessfun, nvars, options)
x是最优解，fval是最优值，@fitnessness是目标函数，nvars是自变量个数，options是其他属性设置。系统默认求最小值，所以在求最大值时应在写函数文档时加负号。
options=gaoptimset(‘PropertyName1’, ‘PropertyValue1’, ‘PropertyName2’, ‘PropertyValue2’,‘PropertyName3’, ‘PropertyValue3’, …)
通过这个函数就能够实现对部分遗传算法的参数的设置。
四、遗传算法的详细原理
1、过程详解
在这里，用一个比较形象的方式讲解一下遗传算法的寻优机理。
例如我需要计算(-1,1)内的，函数y=x*x的最小值（基本上知道正确答案了吧= =，最优解为0，最小值也为0）。
种群初始化运用随机数给出一些初始解，例如0.5, 0.8, -0.2, -0.1。
将每个可行解带入函数中，发现-0.1得到的结果最小，我们默认其为当前最优解，其他的比较差，而0.8最差，我们选择将它淘汰，重新生成一个新的数，为0.4，为了查看其附近有没有更好的解，我们需要对其进行扰动，在遗传算法中，这种扰动识通过变异、交叉呼唤和自然选择进行的。
0.5通过变化变为0.1，0.4则变为0.5，-0.2变为0，-0.1变为-0.3，结果发现0的解是最好的。
经过若干次扰动和测试后，就能够得到最好的解0最好。
就是这样不停地搜索，4个数，就像是四条鱼随机的在水里游，每经过一个地方就进行测试，以找到最好的食物。这就是遗传算法的过程，通过几个个体的缓慢探索最终找到最优解。
2、编码
为了更好的进行后面的扰动，就需要对参数记性特定的编码，在Holland的经典研究中，运用的是二进制，虽然二进制编码具有“汉明悬崖”等的问题，但是二进制凭借其操作简单，计算方便等优势仍处主流。
设参数的范围是（L,U）,k为编码长度，其具体计算公式为：
c=L+x*δ
其中，（这个我还是用公式了额）
编码长度k和所需的精度s有关，通过下列形式求得：
例如，某个参数的范围是0-10，精度是到整数，则其编码维数为4位。8对应的编码是1000。
恢复为实际数的公式为：
其中bi为二进制编码里面的每一位数，例如0101，b1=1, b2=0, b3=1, b4=0。
当然，目前有诸如格雷编码，实数编码等方式，相比二进制编码更加先进，有兴趣的同学可以上网搜一下~
作为利用计算机进行计算的算法，要求将迭代初始，迭代过程，迭代终止条件都需要定义清楚，在此介绍迭代初始，在遗传算法中，成为种群初始化。
在此需要设置一个重要的参数，就是种群规模，在第0章汇总我们看到的种群规模就是4，这个参数的含义就类似一次任务派出搜索员的数量，搜索员数量越多，找的越快，但是需要付出的成本越多，为了平衡两者的关系，一般定为10-100之内，对相对简单的系统，用50以内的种群规模即可。
种群初始化一般使用直接随机的方法，这样能够快速，简便的生成众多初始可行解。
3、适应度评估
无论是在种群初始化化后，还是进行扰动之后，都需要进行适应度评估，适应度的评价标准，就是所求的函数，如果需要函数最大值，则带入求出的值越大，该个体适应度越高，在环境中，就就越不容易被淘汰。在第0章中，-0.1就是适应度比较高的解。
4、选择交叉变异
这三个步骤放在一起说，因为是遗传算法的特色过程，类似搜索员在可行域内搜索最优解的过程。
选择是指根据每个个体的适应度，优胜劣汰，假设淘汰率为0.5，则就讲其中适应度倒数50%的个体直接删除，然后用各种方式来补充，这个是比较机械的方式，方便理解。最常见的选择机制是轮盘赌法，根据适应度将每个个体放在转盘上，是应对越高，占据的面积就越大，然后根据种群规模n，旋转转盘n次，将指针所指的参数加到新种群里面，完成优胜劣汰，毕竟最优秀的个体不见得就能绝对保留，最差的解也不一定就活该淘汰，这是有一定概率出现的。
在进行选择后，就应该进行繁衍，繁衍是相对的，父母会产生和自己类似但是不见得绝对相同的方式产生后代，变异和交叉互换是会发生的。
交叉的含义，我直接举例：
A个体：100100
B个体：100011
假设第四位进行互换，就变成了
A‘个体：100000
B’个体：100111
产生新个体，以变异是以一定概率出现的，概率的设定十分有讲究，太高可能会另最优解有变化，丢失最优解，如果太低，则搜索效率很低，故一般设为0.7-0.9。
变异的含义我同样利用举例来说明：
A个体：100100
第四位产生变异。
A‘个体：100000
这就是变异，和交叉类似，其概率需要有比较精细的判断，一般设为0.01-0.1。
5、其他参数
上面提到了一些比较影响算法性能的参数，除了上面之外，其他的参数也需要谨慎判断。
计算精度：计算精确度越高，计算所需要的代价会越高，所以需要根据实际需求确定。
迭代次数：迭代的目的是搜索最优解，一般而言，找到一定精度的最优解，其实就不必再进行迭代了，所以一般会根据函数复杂性设定比较合理的迭代次数。
综上所述，需要重点分析的参数就是：种群规模，变异概率，交叉概率，计算精度，迭代次数。
五、遗传算法的实现
目前实现遗传算法的方式很多，多半是利用编程语言编辑实现，由于编程过程复杂，今天给大家介绍一个已经编好封装的命令，在Matlab中，只需要两句简单的命令就能够利用遗传算法进行计算了相关命令，在前面有所提到，今天我来举几个例子。
1、命令介绍
首先我们来复习一下遗传算法（上）里面提到的两句关键命令。
函数ga：
|
1 |
[x, fval,reason]= ga(@fitnessfun, nvars, options) |
x是最优解，fval是最优值，@fitnessness是目标函数，nvars是自变量个数，options是其他属性设置。系统默认求最小值，所以在求最大值时应在写函数文档时加负号。
为了设置options，需要用到下面这个函数：
|
1 2 3 |
options=gaoptimset('PropertyName1', 'PropertyValue1', 'PropertyName2', 'PropertyValue2', 'PropertyName3', 'PropertyValue3', ...) |
通过这个函数就能够实现对部分遗传算法的参数的设置。
下面是一些常见的属性、默认属性以及其含义。
运用上述两个关键命令就能够实现遗传算法的全过程，这是最简单快捷的方法啦！
下面来举两个例子，一个比较简单，另一个比较难。
下面来看看代码。首先是函数文件：
|
1 2 3 4 5 |
function y=ga_test(x) y=-200.*exp(-0.05.*x).*sin(x);if x<-3 || x>3 y=999; end end |
由于ga这个函数是求最小值，所以需要将函数取负号。为了限制范围在-3到3之间，运用这个条件语句进行约束。
|
1 2 3 4 |
options=gaoptimset('PlotFcns', @gaplotbestf); [x, fval, reason]=ga(@ga_test,1, options); x -fval |
参数设定上，我决定直接用默认的，另外为了给大家呈现寻优过程，所以运用了和这个参数@gaplotbestf，来看看寻优过程吧~
|
1 2 |
x = 1.5181 ans = 185.1235 |
结果是，最优解为1.5181，最优值是185.1235。可见结果是比较好的。
哼哼，看公式难，看图更难！
|
1 2 3 4 5 6 7 8 9 10 11 |
function y=ga_test2(x)a=power( sin( power(x(1).*x(1)+x(2).*x(2),0.5) ), 2) -0.5;b=power( 1+0.001*(x(1).*x(1)+x(2).*x(2)) ,2); y=-(0.5+a./b); if x(1)<-10 y=999;end if x(1)>10 y=999;end if x(2)<-10 y=999;end if x(2)>10 y=999;end end |
真的写了我一年啊orz
|
1 2 3 4 |
options=gaoptimset('PlotFcns', @gaplotbestf,'StallGenLimit', Inf, 'Generations',1000); [x, fval, reason]=ga(@ga_test2,2, options); x -fval |
为了提高精确度，并且减少后期因为搜索缓慢而导致的偶然停止，我将搜索停止条件设为无穷（就是除非到达1000代，否则搜索会一直进行），进化代数为1000。寻优过程如下：
可以看到这个寻优过程就比较坎坷= =
|
1 2 |
x = 0.4989 -0.4997 ans = 0.4211 |
结果还是相对满意的，哈哈~
4、补充
当然，在参考文献里面还有直接编出来的代码，另外网络上也有很多写好的程序，有兴趣的可以看看。
经典遗传算法有其本身的缺点，上面的结果其实可以通过改进变得更加精确。相关方法大家可以看看论文，然后自己编程实现。
还有一个预防针要打，遗传算法是牛刀，编程代价还是比较高的，对于线性优化等问题，用单纯形法，部分求最值的问题也可以用梯度下降法等解决，遗传算法在解决这种简单的问题，最好还是别放在第一位置，杀鸡焉用牛刀。
参考文献：卓金武. MATLAB在数学建模中的应用[M]. 北京:北京航空航天大学出版社, 2014. 38-59
数据科学与编程 » 遗传算法简介、基本原理及算法实现
