三分钟学会遗传算法

遗传算法

此节介绍最著名的遗传算法(GA)。遗传算法属于进化算法，基本思想是取自“物竞天泽、适者生存”的进化法则。简单来说，遗传算法就是将问题编码成为染色体，然后经过不断选择、交叉、变异等操作来更新染色体的编码并进行迭代，每次迭代保留上一代好的染色体，丢弃差的染色体，最终达到满足目标的最终染色体。整个流程由下图构成（手写，见谅 -_-!!）

流程图

步骤由以下几步构成：

编码（coding）——首先初始化及编码。在此步，根据问题或者目标函数（objective function）构成解数据（solutions），在遗传算法中，该解数据就被称为染色体（chromosome）。值得一提的是，遗传算法为多解（population based）算法，所以会有多条染色体。初始化中会随机生成N条染色体，, 这里表示染色体包含了n条。其中 ，这里表示第i条染色体由d维数值构成。GA会以这个N个数据作为初始点开始进行进化。

评估适应度（evaluate fitness）——这一步用染色体来进行目标函数运算，染色体的好坏将被指明。

选择（selection）——从当前染色体中挑选出优良的个体，以一定概率使他们成为父代进行交叉或者变异操作，他们的优秀基因后代得到保留。物竞天择这里得以体现。

交叉（crossover）——父代的两个两个染色体，通过互换染色体构成新的染色体。例如下图，父亲母亲各提供两个基因给我。这样我既保留了父母的基于，同时又有自己的特性。

交叉

变异（mutation）——以一定概率使基因发生突变。该算子一般以较低概率发生。如下图所示：

变异

下面我们将一步一步为各位呈现如何用matlab编写一个简单的GA算法。

本问题为实数最小化minimization问题。我们需要在解空间内找到最小值或近似最小值，此处我们使用sphere函数作为目标函数（读者可以自行修改为其他的目标函数）。

sphere function

• 初始化：在这一步中，我们将在给定问题空间内生成随机解，代码如下：

% %% 初始化
% % 输入：chromes_size，dim维数,lb下界，ub上界
% % 输出：chromes新种群
function chromes=init_chromes(chromes_size,dim,lb,ub)
 % 上下界中随机生成染色体
 chromes = rand(chromes_size,dim)*(ub-lb)+lb;
end

• 选择：选择是从当前代中挑选优秀的染色体保留以繁殖下一代。我们这里采取的方法是俄罗斯轮盘选择方式。谁的解优，谁获得选中的概率越高。首先，我们需要先求出各染色体的fitness倒数。
• ,然后求出各染色体的比重，比重越大，被保留机会越大。。代码如下：

%% 选择
%俄罗斯轮盘赌
function [newchromes,newfitness] = selection(chromes,fitness)
 weights = 1./fitness; % fitness倒数
 totalfit=sum(weights); % 累加所有weights
 totalf = weights./totalfit; %求出各染色体比重
 index = [];
 for i = 1:size(chromes,1) % 循环选出较优染色体
 pick = rand;
 while pick == 0
 pick = rand;
 end
 for j = 1:size(chromes,1)
 pick = pick - totalf(j);
 if pick<0
 index = [index j];
 break
 end
 end
 end
 newchromes =chromes(index,:);
 newfitness = fitness(index);
end

• 交叉：此步会随机选取两个选择过后的染色体作为父代，从两个染色体中各截取一部分基因生成新的染色体，代码如下：

%% 交叉
function newchromes = crossover(chromes,pc)
 % 生成一个新的解
 newchromes = ones(size(chromes));
 for i = 1:size(chromes,1)
 % 随机选取两个染色体
 parents=randperm(10,2);
 %随机选取一个位置
 pos = round(rand*size(chromes,2));
 if(rand<pc)
 % 交叉生成新的解
 newchromes(i,:)=[chromes(parents(1),1:pos) chromes(parents(2),pos+1:size(chromes,2))];
 else
 newchromes(i,:)=chromes(i,:);
 end
 end
end

• 变异：以一各小概率生成随机变异一个gene，代码如下：

% 变异
function newchromes= muatation(chromes,pm,lb,ub)
 for i = 1:size(chromes,1)
 newchromes(i,:) = chromes(i,:);
 if (rand<pm)
 %随机选取一位
 pos = ceil(rand*size(chromes,2));
 %变异
 newchromes(i,pos)= rand*(ub-lb)+lb;
 end
 end
end

• 主函数，首先初始化各参数，然后进行迭代，当满足终止条件停止：

% 清除workspace，清屏
clear
clc 
% 染色体数量
chromes_size = 20;
% 问题维数
dim = 10;
% 交叉概率
pc =0.9;
% 变异概率
pm = 0.2;
% 问题上下边界
lb = -1;
ub = 1;
% 循环次数
maxiter = 1000;
% 目标方程
namefunc= 'objfun';
fd = str2func(namefunc);
​
% 初始化
chromes = init_chromes(chromes_size,dim,lb,ub);
% 求个染色体fitness
 for i = 1:chromes_size
 fitness(i)=feval(fd,chromes(i,:));
 end
% 求出最优解
 [bestfitness bestindex]=min(fitness);
 bestchrome = chromes(bestindex,:);
 % 主循环
for iter=1:maxiter
 % 选择
 [chromes,newfitness] = selection(chromes,fitness);
 % 交叉
 chromes= crossover(chromes,pc);
 % 变异
 chromes= muatation(chromes,pm,lb,ub);
 % 更新最优
 for i = 1:chromes_size
 fitness(i)=feval(fd,chromes(i,:));
 if fitness(i)<bestfitness
 bestfitness= fitness(i)
 bestchrome = chromes(i,:);
 end
 end
 trace(iter)=bestfitness;
 
end
​
% 绘制fitness曲线
plot(trace)
title('Fitness curve')
xlabel('Iterations')
ylabel('Fitness value')

运行之后生成一个fitness下降曲线，如下图：

适应度下降曲线

遗传算法大大提升了寻优问题的通用性,因为遗传算法属于stochastic algorithm,不再是Deterministic algorithm（如果各位对此感兴趣，请留言，我可进一步讲解）。

但是有些显著缺陷还是明显影响该算法效率，主要问题如下：

1. premature，过早收敛，极易陷入局部最优解
2. 初始点对算法结果影响巨大，初始点好的解效果好，反之亦然。

下一节，将介绍群智能算法的代表之作——粒子群寻优算法。

如有任何疑问请留言，欢迎评论交流，创作不易，请勿抄袭，请收藏，关注，转发~