遗传算法求解TSP（旅行商）问题

clear all;clc %% 输入参数 N=15; %城市的个数 M=100; %种群的个数 C=100; %系统迭代次数 C_old=C; m=2; %适应值归一化淘汰加速指数 Pc=0.4; %交叉概率 Pmutation=0.2; %变异概率 %% 生成城市的坐标 pos=randn(N,2); %随机生成N行2列的坐标矩阵 %% 生成城市之间的距离矩阵 D=zeros(N,N); %生成城市间距离全零矩阵 for i=1:N for j=i+1:N dis=(pos(i,1)-pos(j,1)).^2+(pos(i,2)-pos(j,2)).^2; D(i,j)=dis^(0.5); D(j,i)=D(i,j); end end %上述D矩阵为实对称矩阵，主对角线为0元素，为第i个城市与第i个城市之间的距离，为0; %D矩阵只要看对角线之上的元素就可以； %D(i,j)中元素的实际含义是第i个城市与第j个城市的距离；由此，也可更好的解释其为实对称矩阵的原因 %% 生成初始群体 popm=zeros(M,N); %popm为M行N列的矩阵； %M是种群的个数； %N是种群基因编码的个数，popm矩阵元素为N个城市之间的编号； for i=1:M popm(i,:) =randperm(N); end %randperm(N)函数随机生成一个1行N列的行矩阵，行矩阵的元素为从1到N的数字； %举例如下： %>>>randperm(N); %>>>13 15 4 3 14 12 9 11 10 7 8 6 2 1 5 %% 随机选择一个种群绘制其行走路径 R=popm(1,:); %本部分内容对最优路径没有帮助，仅是作为一个随意的解释 %R为popm矩阵的第一个种群，本部分内容中随机生成一个行走路径 figure(1); subplot(1,3,1); scatter(pos(:,1),pos(:,2),'b*'); %绘制离散点坐标 xlabel('横轴');ylabel('纵轴');title('随机产生的种群图');grid on; subplot(1,3,2); plot_route(pos,R); %绘制第一个种群的城市行走路径 xlabel('横轴');ylabel('纵轴');title('随机生成种群中城市路径情况');grid on; %% 初始化种群及其适应函数 fitness=zeros(M,1); %生成一个M行1列的全零列矩阵，列矩阵元素为种群适应度； len=zeros(M,1); %生成一个M行1列的全零列矩阵，列矩阵元素为所行城市的路径总长度； for i=1:M len(i,1)=myLength(D,popm(i,:));%求解行走路径总长度 end maxlen=max(len);%maxlen是当前种群最长的行走距离 minlen=min(len);%minlen是当前种群最短的行走距离 fitness=fit(len,m,maxlen,minlen); rr=find(len==minlen);%通过find()函数取得len矩阵中所有数值等于最小举例的索引数值 R=popm(rr(1,1),:);%选择第rr个种群矩阵 for i=1:N fprintf('%d ',R(i)); %打印出第rr个种群城市行走路径顺序 end fprintf('\n'); fitness=fitness/sum(fitness);%轮盘赌选择法确定是否被选中 distance_min=zeros(C+1,1);%该矩阵为刷新种群最小距离储存矩阵 while C>=0 fprintf('迭代第%d次\n',C); %% 选择操作 nn=0; for i=1:size(popm,1) %size(popm,1)种群行数，既有多少个种群数 len_1(i,1)=myLength(D,popm(i,:)); %求取该种群个体城市行走路径总长度 jc=rand*0.3; %rand生成0-1的随机数 for j=1:size(popm,1) if fitness(j,1)>=jc %如果适应度大于选择概率，则选择相应的种群进行后续操作 nn=nn+1; popm_sel(nn,:)=popm(j,:); %保留种群中相应的种群个体基因编码 break; end end end %% 每次选择都保存最优的种群 popm_sel=popm_sel(1:nn,:); [len_m len_index]=min(len_1); %得到距离矩阵中距离最短的行走路径长度和相应的基因个体编号，是第几个基因个体 popm_sel=[popm_sel;popm(len_index,:)]; %将最短距离的种群个体基因编码补充至保留的种群后面 %上一个程序含义解释的还不是很到位 %% 交叉操作 nnper=randperm(nn); %选择部分选择了nn个基因编码个体进行后续操作，这里也是生成基因编码顺序个体 A=popm_sel(nnper(1),:); %选中nnper(1)所对应的基因编码个体 B=popm_sel(nnper(2),:); %选中nnper(2)所对应的基因编码个体 for i=1:nn*Pc %交叉概率(Pc)的数值是0.4，通过nn*Pc可以得到一共交叉多少次 [A,B]=cross(A,B); %A、B个体中部分基因编码进行交换 popm_sel(nnper(1),:)=A; %将交换后的种群个体基因编码送回原矩阵 popm_sel(nnper(2),:)=B; %将交换后的种群个体基因编码送回原矩阵 end %% 变异操作 for i=1:nn %对nn个种群个体基因编码进行变异操作 pick=rand; %随机指定种群内某一个基因编码个体的变异概率，以备后续决定是否进行变异操作 while pick==0 pick=rand; end if pick>=Pmutation popm_sel(i,:)=Mutation(popm_sel(i,:)); %如果小于变异概率则进行变异操作 %popm_sel矩阵中每一个基因编码个体都要进行变异 end end %% 求适应度函数 NN=size(popm_sel,1); %求取popm_sel矩阵的行数，以备进行种群适应度的求取 len=zeros(NN,1); for i=1:NN len(i,1)=myLength(D,popm_sel(i,:)); %求取popm_sel矩阵中对应城市行走路径的总长度 end maxlen=max(len); %maxlen是当前种群最长的行走距离 minlen=min(len); %minlen是当前种群最短的行走距离 distance_min(C+1,1)=minlen; %求取最短距离 fitness=fit(len,m,maxlen,minlen); %求取对应的适应度数值 rr=find(len==minlen); %求取最短距离的数值索引 fprintf('minlen=%d\n',minlen); %打印最短距离 R=popm_sel(rr(1,1),:); %保留最短距离对应的种群个体基因编码 for i=1:N fprintf('%d ',R(i)); %打印当前种群个体基因编码 end fprintf('\n'); popm=[]; %清空种群个体矩阵 popm=popm_sel; %将当前选择的矩阵赋值给popm矩阵 C=C-1; pause(0.03); end subplot(1,3,3); plot_route(pos,R); xlabel('横轴');ylabel('纵轴');title('优化后种群中城市路径情况');grid on;