此节介绍最著名的遗传算法(GA)。遗传算法属于进化算法,基本思想是取自“物竞天泽、适者生存”的进化法则。简单来说,遗传算法就是将问题编码成为染色体,然后经过不断选择、交叉、变异等操作来更新染色体的编码并进行迭代,每次迭代保留上一代好的染色体,丢弃差的染色体,最终达到满足目标的最终染色体。整个流程由下图构成(手写,见谅 -_-!!)
步骤由以下几步构成:
编码(coding)——首先初始化及编码。在此步,根据问题或者目标函数(objective function)构成解数据(solutions),在遗传算法中,该解数据就被称为染色体(chromosome)。值得一提的是,遗传算法为多解(population based)算法,所以会有多条染色体。初始化中会随机生成N条染色体,, 这里表示染色体包含了n条。其中 ,这里表示第i条染色体由d维数值构成。GA会以这个N个数据作为初始点开始进行进化。
评估适应度(evaluate fitness)——这一步用染色体来进行目标函数运算,染色体的好坏将被指明。
选择(selection)——从当前染色体中挑选出优良的个体,以一定概率使他们成为父代进行交叉或者变异操作,他们的优秀基因后代得到保留。物竞天择这里得以体现。
交叉(crossover)——父代的两个两个染色体,通过互换染色体构成新的染色体。例如下图,父亲母亲各提供两个基因给我。这样我既保留了父母的基于,同时又有自己的特性。
变异(mutation)——以一定概率使基因发生突变。该算子一般以较低概率发生。如下图所示:
下面我们将一步一步为各位呈现如何用matlab编写一个简单的GA算法。
本问题为实数最小化minimization问题。我们需要在解空间内找到最小值或近似最小值,此处我们使用sphere函数作为目标函数(读者可以自行修改为其他的目标函数)。
- 初始化:在这一步中,我们将在给定问题空间内生成随机解,代码如下:
% %% 初始化% % 输入: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
变异:以一各小概率生成随机变异一个gene,代码如下:
% 变异function newchromes= muatation(chromes,pm,lb,ub) for i = 1:size(chromes,1) newchromes(i,:) = chromes(i,:); if (rand
主函数,首先初始化各参数,然后进行迭代,当满足终止条件停止:
% 清除workspace,清屏clearclc % 染色体数量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)
运行之后生成一个fitness下降曲线,如下图:
遗传算法大大提升了寻优问题的通用性,因为遗传算法属于stochastic algorithm,不再是Deterministic algorithm(如果各位对此感兴趣,请留言,我可进一步讲解)。
但是有些显著缺陷还是明显影响该算法效率,主要问题如下:
premature,过早收敛,极易陷入局部最优解初始点对算法结果影响巨大,初始点好的解效果好,反之亦然。
下一节,将介绍群智能算法的代表之作——粒子群寻优算法。
如有任何疑问请留言,欢迎评论交流,创作不易,请勿抄袭,请收藏,关注,转发~
今天的文章遗传算法matlab_三分钟学会遗传算法分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/32749.html