很有用的遗传算法（附完整源代码）

八卦谈佚名 ▪ 2023-06-10 12:20:14

你好，我是阳寜。
让我们一起进步吧！

算法简介

遗传算法(Genetic Algorithm,GA):是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

遗传算法是一种启发式算法，那什么是启发式算法呢？简单来讲，启发式算法就是例如遗传算法、模拟退火以及各种种群算法如蚁群算法、鱼群算法、粒子群算法、人工神经网络等等模仿自然界或生命体行为模式的算法，一般也称为人工智能算法或全局优化算法。

启发式稍官方的定义是一个基于直观或经验构造的算法，在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度一般不能被预计。

生物遗传与算法间相关术语的关系

转录->编码
翻译->解码
个体交配->交叉
染色体变异->变异
自然选择->适应度函数选择

编码

编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。==编码方法影响到交叉算子、变异算子等遗传算子的运算方法，很大程度上决定了遗传进化的效率。==

迄今为止人们已经提出了许多种不同的编码方法。总的来说这邪恶编码方法可以分为三大类：二进制编码、浮点是编码、符号编码。

编码一直是遗传算法的首要难题，目前没有统一的方法可以解决。

二进制编码

就像人类的基因含有四种碱基一样。不过在这里我们只用了0和1两种碱基，然后将他们串成一条链形成染色体。一个位能表示出两种状态的信息量，因此足够长的二进制染色体便能表示出所有的特征。

二进制编码其实就是变为二进制代码的过程。
首先，要计算出编码长度k
设某一参数的取值范围为(L,U)，使用长度为k的二进制数编码表示该参数，则它共有种不同的编码。该参数编码时的对应关系为:

00000000 = 0 ->L
00000001 = 1 ->L +
00000010 = 2 ->L + 2
00000011 = 3 ->L + 3
......
111111111 = - 1 -> U = L + ( - 1)
即

则易知:

表示求解精度，k是计算链长度，即编码的长。

实数编码

本文的示例代码为解决TSP问题，采用实数编码方式。
实数编码指直接使用实数表示基因，容易理解且不需要解码过程，但容易过早收敛，从而陷入局部最优。

解码

解码的目的就是为了将不直观的二进制码还原成十进制。假设一个个体的二进制编码为:

，则对应的解码公式为：

例如：设有参数X，取值为[2,4]，现在用3位二进制数对X进行编码，可得

条染色体：

,对于任意的二进制数据串只要代入解码公式，就可以得到对应的解码，如

,则它对应的十进制数为：

,则对应的参数X的值为：

适应度函数

适应度函数用来评价一个个体（解）的好坏程度，它是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。
例如求解一个函数的最值，那么函数的法则就用来做适应度函数。

遗传算子

选择算子

选择算子：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。
选择操作的任务就是从父代群体中选取一些个体，遗传到下一代群体。
基本的遗传算法采用轮赌法进行，思想是各个个体被选中的概率与其适应度函数值大小成正比。

如设群体大小为N，的适应度为

，则个体的的选择概率为：

，这为其基本思想，在计算机程序中可以以如下的方法进行实现：

在[0,1]内产生一个均匀分布的随机数r
若

,则染色体被选中
若 < r

,则染色体被选中
其中的称为染色体

的累计概率，其计算公式为：

假若有染色体：

若要求解

的适应度，那么轮盘赌算法如下：

则染色体的概率为：

交叉算子

在遗传算法中，交叉有很多种实现方法，如：

1.单点交叉法
2.两点交叉法
3.PMX(洗牌)交叉法
4.均匀交叉法
5.离散交叉法
······

交叉运算，是指对两个相互配对的染色体依据交叉概率按某种方式相互交换其部分基因，从而形成两个新的个体。基本的遗传算法采用单点交叉。如下所示:
1101==0111110010== -> 11010101001010
10010101001010 -> 1001==0111110010==

而当采用其它编码方式时，如实数编码会产生一些问题，如下所示：
4287/1653
6138/5274
交叉后：
6138/1653
4287/5274
从交叉结果来看，字串中出现了重复的码，但在一些问题中，串中的码不允许出现重复现象，如TSP问题，那么可以采用如下方法：

单点交叉映射法
单点顺序交叉法

单点映射交叉法：对于交叉点前的码，检查其出现的遍历重复，依据交叉点后的位置映射关系，逐一进行交换。
使用前:
9 1 4 5 6 / 9 5 4 7
6 8 1 2 3 / 7 8 3 2
使用后：
8 1 2 3 6 9 5 4 7
6 9 1 4 5 7 8 3 2
单点顺序交叉法：设两父串为A,B.随机选取交叉点,定义交叉点后面为匹配区域,首先将A和B的匹配区域分别加到B和A的前面, 然后分别在匹配区域后依次删除与匹配区域相同的码得到最终的子串。
如：
9 1 4 5 6 / 7 8 3 2
6 8 1 2 3 / 9 5 4 7
变化得：
9 5 4 7 / 9 1 4 5 6 7 8 3 2
7 8 3 2 / 6 8 1 2 3 9 5 4 7
消除重复得：
9 5 4 7 1 6 8 3 2
7 8 3 2 6 1 9 5 4

变异算子

变异运算，是指改变个体编码串中的某些基因值，从而形成新的个体。
决定遗传算法的局部搜索能力，保持种群多样性。
交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。
基本遗传算法（SGA）中变异算子采用基本位变异算子。
基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则将其变为1；
反之，若原有基因值为1，则将其变为0 。
如：
10010101001010
变化得：
10011101001010

算法步骤

初始化种群
计算种群上每个个体的适应度
按由个体适应度所决定的某个规则选择将进入下一代的个体
按概率Pc进行交叉操作
按概率Pm进行变异操作
若没有满足某种停止条件，则转入第2步
输出种群中适应度最优的染色体作为问题的满意解或最优解。

实例代码

代码以函数及主代码的方式存在，其中，读取的文件是一个写了城市数据的.txt文件，==代码末尾给出数据==，代码如下：
主代码

clear all; close all; CityNum=48; inn=30; %初始种群大小 gnmax=10000; %最大代数 pc=0.8; %交叉概率 pm=0.5; %变异概率 [dislist,Clist]=tsp(CityNum); %dislist为距离方阵,Clist就是48行两列的原数据 %产生初始种群 s=zeros(inn,CityNum); %30行，48列 for i=1:inn s(i,:)=randperm(CityNum); %randperm(N) 返回一个长度为N，数值是1:N的随机打乱的数组 end [~,p]=objf(s,dislist); gn=1; %当前代数 ymean=zeros(gn,1); ymax=zeros(gn,1); xmax=zeros(inn,CityNum); scnew=zeros(inn,CityNum); smnew=zeros(inn,CityNum); tic %10000代迭代开始 while gn<gnmax+1 for j=1:2:inn seln=sel(p); %选择操作 scro=cro(s,seln,pc); %交叉操作 scnew(j,:)=scro(1,:); scnew(j+1,:)=scro(2,:); smnew(j,:)=mut(scnew(j,:),pm); %变异操作 smnew(j+1,:)=mut(scnew(j+1,:),pm); end s=smnew; %产生了新的种群 [f,p]=objf(s,dislist); %计算新种群的适应度 %记录当前代最好和平均的适应度 [fmax,nmax]=max(f); ymean(gn)=1000/mean(f); ymax(gn)=1000/fmax; %记录当前代的最佳个体 x=s(nmax,:); xmax(gn,:)=x; %drawTSP(Clist,x,ymax(gn),gn,0); gn=gn+1; end toc [min_ymax,index]=min(ymax); drawTSP(Clist,xmax(index,:),min_ymax,index,1); % figure(2); % plot(ymax,'r'); hold on; % plot(ymean,'b');grid; % title('搜索过程'); % legend('最优解','平均解'); fprintf('遗传算法得到的最短距离:%.2f\n',min_ymax); fprintf('遗传算法得到的最短路线'); disp(xmax(index,:));

求距离矩阵代码

%城市位置坐标 function [DLn,cityn]=tsp(n) DLn=zeros(n,n); city=importdata('att48.txt'); %利用整数编码对城市编码 for i=1:48 for j=1:48 %伪欧式距离，最优解为10628 dst1=(((city(i,1)-city(j,1))^2+(city(i,2)-city(j,2))^2)/10)^0.5; dst2=round(dst1); %round函数对每个元素进行四舍五入取整 if (dst2 < dst1) DLn(i,j) = dst2 + 1; DLn(j,i) = DLn(i,j); else DLn(i,j) = dst2; DLn(j,i)=DLn(i,j); end end end cityn=city; end

选择代码

function seln=sel(p) %轮盘赌选择 seln=zeros(2,1); %从种群中选择两个种群，最好不要两次选择同一个种群 for i=1:2 r=mod(randi([1,65535]),1000)/1000.0; %产生一个随机数 prand=p-r; j=1; while prand(j)<0 %当随机概率小于个体累计概率时则选中 j=j+1; end seln(i)=j; %选中个体的序号 if i==2&&j==seln(i-1) %%若相同就再选一次 r=rand; %产生一个随机数 prand=p-r; j=1; while prand(j)<0 j=j+1; end end end end

交叉代码

%根据变异（交叉）概率判断是否变异（交叉） %((rand()%100 + 0.0) / 100) %产生的随机数小于变异（交叉）概率则该个体进行变异（交叉） function pcc=pro(pc) test(1:100)=0; l=round(100*pc); test(1:l)=1; n=round(rand*99)+1; pcc=test(n); end

求累计概率代码

function [f,p]=objf(s,dislist)%传入初始化种群、距离方阵 inn=size(s,1); %读取种群大小,30 f=zeros(inn,1); %f为存放30个种群适应度的矩阵 for i=1:inn f(i)=CalDist(dislist,s(i,:)); %计算函数值，即适应度，就是此种群总城市距离 end f=1000./f'; %取距离倒数 ,f可以理解为某种概率，代表选择程度，越大越选择 %根据个体的适应度计算其被选择的概率 fsum=0; for i=1:inn fsum=fsum+f(i)^15;% 让适应度越好的个体被选择概率越高 end ps=zeros(inn,1); for i=1:inn ps(i)=f(i)^15/fsum; end %计算累积概率 p=zeros(inn,1); p(1)=ps(1); for i=2:inn p(i)=p(i-1)+ps(i); end p=p'; end

变异代码

%“变异”操作 function snnew=mut(snew,pm) bn=size(snew,2); snnew=snew; pmm=pro(pm); %根据变异概率决定是否进行变异操作，1则是，0则否 if pmm==1 c1=mod(randi([65535]),48); %在[1,bn-1]范围内随机产生一个变异位 c2=mod(randi([65535]),48); chb1=min(c1,c2); chb2=max(c1,c2); x=snew(chb1+1:chb2); snnew(chb1+1:chb2)=fliplr(x); end end

交叉操作代码

%“交叉”操作 function scro=cro(s,seln,pc) bn=size(s,2); pcc=pro(pc); %根据交叉概率决定是否进行交叉操作，1则是，0则否 scro(1,:)=s(seln(1),:); scro(2,:)=s(seln(2),:); if pcc==1 c1=mod(randi([65535]),48); %在[1,bn-1]范围内随机产生一个交叉位 c2=mod(randi([65535]),48); chb1=min(c1,c2); chb2=max(c1,c2); middle=scro(1,chb1+1:chb2); scro(1,chb1+1:chb2)=scro(2,chb1+1:chb2); scro(2,chb1+1:chb2)=middle; for i=1:chb1 while find(scro(1,chb1+1:chb2)==scro(1,i)) zhi=find(scro(1,chb1+1:chb2)==scro(1,i)); y=scro(2,chb1+zhi); scro(1,i)=y; end while find(scro(2,chb1+1:chb2)==scro(2,i)) zhi=find(scro(2,chb1+1:chb2)==scro(2,i)); y=scro(1,chb1+zhi); scro(2,i)=y; end end for i=chb2+1:bn while find(scro(1,1:chb2)==scro(1,i)) zhi=logical(scro(1,1:chb2)==scro(1,i)); y=scro(2,zhi); scro(1,i)=y; end while find(scro(2,1:chb2)==scro(2,i)) zhi=logical(scro(2,1:chb2)==scro(2,i)); y=scro(1,zhi); scro(2,i)=y; end end end end

适应度函数代码

%适应度函数 function F=CalDist(dislist,s) DistanV=0; n=size(s,2); %n为城市数目 for i=1:(n-1) DistanV=DistanV+dislist(s(i),s(i+1)); %把此种群总城市距离加起来 end DistanV=DistanV+dislist(s(n),s(1)); F=DistanV; end

画图代码

%画图 function drawTSP(Clist,BSF,bsf,p,f) CityNum=size(Clist,1); for i=1:CityNum-1 plot([Clist(BSF(i),1),Clist(BSF(i+1),1)],[Clist(BSF(i),2),Clist(BSF(i+1),2)],'ms-','LineWidth',1,'MarkerEdgeColor','k','MarkerFaceColor','g'); text(Clist(BSF(i),1),Clist(BSF(i),2),[' ',int2str(BSF(i))]); text(Clist(BSF(i+1),1),Clist(BSF(i+1),2),[' ',int2str(BSF(i+1))]); hold on; end plot([Clist(BSF(CityNum),1),Clist(BSF(1),1)],[Clist(BSF(CityNum),2),Clist(BSF(1),2)],'ms-','LineWidth',1,'MarkerEdgeColor','k','MarkerFaceColor','g'); title([num2str(CityNum),'城市TSP']); if f==0&&CityNum~=10 text(10,5500,['第 ',int2str(p),' 代',' 最短距离为 ',num2str(bsf)]); else text(10,5500,['最终搜索结果：最短距离 ',num2str(bsf),'，在第 ',num2str(p),' 代达到']); end hold off; pause(0.05); end

数据

6734 1453 2233 10 5530 1424 401 841 3082 1644 7608 4458 7573 3716 7265 1268 6898 1885 1112 2049 5468 2606 5989 2873 4706 2674 4612 2035 6347 2683 6107 669 7611 5184 7462 3590 7732 4723 5900 3561 4483 3369 6101 1110 5199 2182 1633 2809 4307 2322 675 1006 7555 4819 7541 3981 3177 756 7352 4506 7545 2801 3245 3305 6426 3173 4608 1198 23 2216 7248 3779 7762 4595 7392 2244 3484 2829 6271 2135 4985 140 1916 1569 7280 4899 7509 3239 10 2676 6807 2993 5185 3258 3023 1942

将此数据复制粘贴入.txt文件即可，如出现问题可私聊我哦~

本文为我原创本文禁止转载或摘编

编程算法启发式算法