首页分享遗传算法+改良圈算法

遗传算法+改良圈算法

来源：花匠小妙招时间：2024-12-03 20:09

关于改良圈算法的操作，不再赘述
https://blog.csdn.net/Fighting_Peter/article/details/104278498

泻药，没看懂太多，代码抄的书本，MATLAB的矩阵表示让我有点儿无法想象，所以很多下标或者行向量列向量没法写。

我看懂的一部分，用注释标出来了。

tic %计时开始 clc,clear; sj0=load('sj.txt'); x=sj0(:,[1:2:8]);x=x(:);%将x变成列向量 y=sj0(:,[2:2:8]);y=y(:);%将y变成列向量 sj=[x y];%变成一百行两列的矩阵 d1=[70 40];%出发地点 sj=[d1;sj;d1];%起点，中间过程，终点 sj=sj*pi/180;%角度化成弧度 d=zeros(102);%距离矩阵初始化 for i=1:101 for j=i+1:102 d(i,j)=6370*acos(cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2)));%计算任意两点之间的距离 end end d=d+d';%矩阵等于矩阵加上转置，构造一个对称矩阵 w=50;g=100;%w为种群的个数，g为进化的代数 rand('state',sum(clock));%初始化随机数发生器 %也是一种贪心的策略,仍然是近似最优来排除明显不合理的解 for k =1:w %试图通过改良圈算法来选取初始种群 c=randperm(100);%产生一个100的全排列 c1=[1 c+1 102];%初始解 for t=1:102 %该层循环是修改圈 flag=0;%修改圈退出标记 for m=1:100 for n=m+2:101 if d(c1(m),c1(n))+d(c1(m+1),c1(n+1))<d(c1(m),c1(m+1))+d(c1(n),c1(n+1))%改良圈成立则进行修改路径 c1(m+1:n)=c1(n:-1:m+1); flag=1;%修改圈 end end end if flag==0 %无修改则退出，节省算力 J(k,c1)=1:102;%记录下较好的解并且推出当前循环 break; end end end J(:,1)=0;J=J/102;%把整数序列转换成01区间上的实数，即转换成染色体编码 for k=1:g %进行遗传算法的操作 A=J;%交配产生子代A的初始染色体 for i=1:2:w ch1(1)=rand;%混沌序列的初始值，rand产生的是01之间的数字 for j =2:50 ch1(j)=4*ch1(j-1)*(1-ch1(j-1));%产生混沌序列 end ch1=2+floor(100*ch1);%产生交叉操作的地址 %进行一次交叉互换，矩阵到现在都搞不懂 temp=A(i,ch1);%中间变量的保存值 A(i,ch1)=A(i+1,ch1);%交叉操作 A(i+1,ch1)=temp; %%矩阵的表示方法至今没弄很懂 end by=[]; while ~length(by) by=find(rand(1,w)<0.1);%产生变异操作的地址 end num1=length(by); B=J(by,:); %产生变异操作的初始染色体 ch2=rand; %混沌序列的初始值 for t=2:2*num1 ch2(t)=4*ch2(t-1)*(1-ch2(t-1));%产生混沌序列，logistics混沌序列公式 end for j=1:num1 bw=sort(2+floor(100*rand(1,2)));%产生变异操作的两个地址 B(j,bw)=ch2([j,j+1]);%bw处的两个基因发生了变异 end G=[J;A;B];%父代和子代种群合起来在一起 [SG,ind1]=sort(G,2);%把染色体翻译成1 ……102的序列 num2=size(G,1);long=zeros(1,num2);%路径长度的初始值 for j=1:num2 for i=1:101 long(j)=long(j)+d(ind1(j,i),ind1(j,i+1));%计算每条路径的长度 end end [slong,ind2]=sort(long);%对路径长度进行从小到大排序 J=G(ind2(1:w),:); %精选前w个较短的路径对应的染色体 end path=ind1(ind2(1),:),flong=slong(1); %解的路径及路径长度 toc %计时结束 xx=sj(path,1);yy=sj(path,2); plot(xx,yy,'-o'); %画出路径 fprintf("%f",flong/1000);%输出路径的长度

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384

总体的思路是，遗传算法模仿DNA的交叉互换方式进行遗传淘汰选择，并且通过变异来跳出局部最优的困境，最终选择最短路。
此题目与上一篇的模拟退火是一个题目，最终得到的结果发现，此题目用遗传算法得到的答案更优，并且波动更小，这是因为遗传算法模拟生物进化时，每次交叉互换采用了单点交叉，即只改变一小部分基因序列，使得结果不至于大起大落甚至最后不能趋于稳定，改进后具有良好的收敛性。
在操作过程中，可以通过改变变异概率使得程序不至于早熟（即很早就达到一个平衡点。
这样看来，神经网络的算法并不具有所谓模板。而如何最优利用算力，是建模过程中应该好好考虑的问题。
PS：学到了一个词叫做，“寻优抖振问题”。
并没有查到具体词条，看意思来说，大概：
抖振现象是指，机翼或者机尾受到外力而随机性振动，类比过来，可能说的就是最优解寻找过程中最终无法达到平衡点，反而上下波动的现象吧。我的理解就是，即使你得到了一个解，但是由于其不收敛的趋势，此问题仍然处于无答案的状态。