遗传算法入门
============4.2更新============== 1. 对代码注释进行了增删 2. 对代码#crossover#部分进行了优化 3. 对图片进行了优化 ================================ 目前应用较多的优化算法有遗传算法、粒子群算法、蚁群算法、模拟退火算法等。现对遗传算法（genetic algorithm）作略微介绍，并附MATLAB算例。 “物竞天择，优胜劣汰”是大自然的进化准则，同时也是遗传算法的核心思想。遗传算法的步骤为： 1.生成一定规模的初始种群（NP：种群规模）。在遗传算法中可采用二进制编码或实数编码。编码也称“染色体/基因”。对于二进制编码来说，其长度（L：编码长度）体现了计算精度。 2.按照一定规则（如“轮盘赌”）对初始种群进行选择（select）。其依据是个体的适应度（对应待求极值的函数），以此来模拟大自然的“选择”。 3.按照一定概率（Pc）对个体进行交叉（cross）。 4.按照一定概率（Pm）产生个体基因变异（mutation）。 5.下一代产生。 6.重复步骤2-5，直至达到规定的迭代数（G：迭代数）。此时算法得到最优解（代表最适宜环境生存的个体）。 ++++MATLAB算例++++ 求函数y=-x^2+10在区间［-5,5］的极值。很明显其极值为（0,10）（选取函数比较简单）。 MATLAB运算结果如图1所示。
MATLAB中各参数为：NP=500，L=20，Pc=0.8，Pm=0.1，xu=5，xl=-5，G=1000。图中由上到下依次为（a）函数图像；（b）适应度进化曲线（图中显示的收敛性并不好，可通过参数的调整和代码的优化解决）；（c）历代最优个体。 ===源码crossover部分（version 1）=== % crossover for i = 1:2:NP-1 if rand < Pc cross_point = round(rand*L); % location of crossover nf(i,:) = ［nf(i,1:cross_point),nf(i+1,cross_point+1:end)］; % exchange after cross POINT nf(i+1,:) = ［nf(i+1,1:cross_point),nf(i,cross_point+1:end)］; end end 适应度曲线的收敛性问题在一定程度上受代码（version1）#crossover#部分算法影响。version1中个体之间的交叉是固定的，即前后两两之间交叉；另外交叉范围存在过大或者过小的问题（取决于交叉的位置cross_point），因而交叉的随机性较大。在version2中针对#crossover#部分进行了优化。 ===源码crossover部分（version 2）=== % version 2 best individual and best fitness/trace ［best_fitvalue(k), best_index(k)］ = max(fitvalue); No_cross = round(L*Pc); % number of crossover Po_cross = randi(L,NP/2,No_cross); % Position of crossover for i = 1:NP/2 Rand1 = rand; if Rand1 < Pc for j = 1:No_cross nf(2*i-1,Po_cross(i,j)) = f(best_index(k),Po_cross(i,j)); % crossover with best individual involved nf(2*i,Po_cross(i,j)) = nf(2*i-1,Po_cross(i,j)); end end end 优化结果如图2所示。图2中显示的收敛性更好，最优个体比较集中。
注意，这里的示例选取的函数比较简单。当寻找函数y=x+10sin(5x)+7cos(4x)（多极值函数）在区间［0,10］的最大值时，遗传算法很容易陷入局部最大值。这也是作者所写的遗传算法缺点所在，因此有待进一步改进。 PS：文中错误和疏漏在所难免，以后将对其进行更新维护。
