实战1：基于遗传算法解决旅行商问题的MATLAB编程（1）程序篇

目录

   0.先上程序

   1.绪论

   2.研究方法

   3.使用遗传算法编写TSP问题

   4.结果分析

0.先上程序

==1=主函数

GeneticAlgorithm_TSP.m 

==2=子函数：

CityDistance.m （计算不同城市之间的距离)

GroupFit.m       （得出最短城市路径，最短城市路径样本，适应度函数）

selection.m         (选择)

crossover.m      （交叉）

Mutation.m      （变异）

SwapRepeat.m （重复交换）

SwapGene.m    （交换基因）

DrawPath.m       (路径描绘)

1.主程序   GeneticAlgorithm_TSP.m

clear;close;clc;
%% Function：Describle the distance between cities
%% Author  ：sophiaechoz@163.com
%% Date    ：20210119

%% Define cities coordination
city20=[29 54;71 76;74 78;81 71;25 38;58 35;4 50;
13 40;18 40;24 98;71 44;64 60;69 58;83 69;58 69;54 63;51 67;37 84;
41 94;3 85];
%% Define constant name
N=20;                            %城市数
city_coordinate=city20;          %城市位置，前面已经给点城市的数量，则可以确定城市的坐标。（8,15,20,30）
s=100;                           %样本数（种群）
c=30;                            %替换个数
pc=0.8;                          %交叉概率crossover
pm=0.1;                          %变异概率mutation
times=3000;                      %最大迭代次数
time=0;                          %实际迭代次数

%%初始化变量，设定总群，总适应度以及最短距离以及最小距离。
pop=zeros(s,N+1);                %初始种群+适应度,之所以加N+1，因为最后还要回到原点。
pop_fit_aver=[];%总适应度
min_dis=[];                      %最短距离
pop_min=[];%最短距离的基因

%初始化，其中s为种群数
for i=1:s   
    pop(i,1:N)=randperm(N);    %%randperm函数产生1-N内任意排列的N维数组。
end
clf
plot(city_coordinate(:,1),city_coordinate(:,2),'bo');%画平均适应度折线图  //一个列向量作为自变量，另一个列向亮作为应变量。
%%变量处理：城市间
for i=1:N
    test_t=num2str(i);                            %%将变量类型转换为浮点型数
    text(city_coordinate(i,1),city_coordinate(i,2),test_t);%标号      行不变，列改变
end
grid on;
title('城市坐标分布图');
xlabel('x');
ylabel('y');

city_distance=CityDistance(city_coordinate,N);%城市间距离

%适应度函数编写
[individual_fit,sum,min1,min_index]=GroupFit(city_distance,N,pop,s);   %%通过城市距离；城市数。pop（城市的随机分布）。s是城市分布的例子个数
sumP=sum;
pop_fit_aver=[pop_fit_aver;sum];        %%构造总群适应度函数
min_dis=[min_dis;min1];                 %%构造最小距离  min_dis=min1
pop(:,N+1)=individual_fit;              %%列矩阵的个体适应度函数
pop_min=[pop_min;pop(min_index,:)];

%% 选择父代
pop=selection(pop,N,s,c);
for i=1:times
    time=time+1;
    E_new_new=[];   %子代
    for j=1:s/2    
        a=rand(1);
        b=rand(1);
        
%%  交叉crossover
            if a>pc          
                ;
            else
                crosspoint=rand(1,2);
                crosspoint=floor(crosspoint*N)+1;
                [pop(j,:),pop(j+s/2,:)]=Crossover(pop(j,:),pop(j+s/2,:),crosspoint,N);       
            end
            
%% 变异mutation
            if b>pm         
                ;
            else
                pop(j,:)=Mutation(pop(j,:),N);
                pop(j+s/2,:)=Mutation(pop(j+s/2,:),N);
            end
            E_new_new=[E_new_new;pop(j,:);pop(j+s/2,:)];
  
    end
    [individual_fit,sum,min1,min_index]=GroupFit(city_distance,N,E_new_new,s);
    sumS=sum;
    pop_fit_aver=[pop_fit_aver;sum];
    min_dis=[min_dis;min1];
    E_new_new(:,N+1)=individual_fit;
    pop_min=[pop_min;E_new_new(min_index,:)];
    if(abs(sumS-sumP)<0.001)%退出条件
        break;
    end
    pop=selection(E_new_new,N,s,c);
end
[a,min_index]=min(min_dis);
a
time1=1:time+1;
figure%画平均适应度折线图
plot(time1,min_dis,'k.');
grid on;
title('每代最小值散点图');
xlabel('迭代的次数');
ylabel('最短的距离');
figure%画平均适应度折线图
plot(time1,pop_fit_aver);
grid on;
title('总适应度折线图');
xlabel('迭代次数');
ylabel('每代总适应度');
figure%画最优路径
DrawPath(city_coordinate,pop_min,min_index,N)
grid on;
title('最优路径图');
xlabel('x');
ylabel('y');

2.子程序

CityDistance.m

function [city_distance] = CityDistance(city_coordinate,N)%城市距离矩阵
    city_distance=zeros(N,N); %%通过zeros构造
    for i=1:N
        for j=1:N
            city_distance(i,j)=((city_coordinate(i,1)-city_coordinate(j,1))^2+...
                (city_coordinate(i,2)-city_coordinate(j,2))^2)^0.5;     %%matlab是以矩阵的思维编写的，则每个距离都会存入city_diatance
        end
    end
end

GroupFit.m

function [individual_fit,num,min_distance,index] = GroupFit(city_distance,N,pop,s)%种群适应度
    individual_distance=zeros(s,1);     %%目的是求得最短路劲的值，给定INDIVIDUAL为sx1的矩阵
    for j=1:s
        sum_distance=0;
        for i=1:N-1
            sum_distance=sum_distance+city_distance(pop(j,i),pop(j,i+1));
        end
        sum_distance=sum_distance+city_distance(pop(j,N),pop(j,1));        %%最后回到起点
        individual_distance(j,1)=sum_distance;                             %%individual_distance是一个列矩阵
    end
    [min_distance,index]=min(individual_distance);    %%找到最短的距离
    individual_fit=1./individual_distance;           %%分子越小，分母越大
    num=0;
    for i=1:s
      num=num+individual_fit(i,1);
    end
end

selection.m  选择

function [pop_ok]=selection(pop,N,s,c)%选择父代
    pop=sortrows(pop,N+1);
    for i=1:c
        pop(i,:)=pop(s+1-i,:);
    end
    randIndex=randperm(size(pop,1));
    pop=pop(randIndex,:);
    pop_ok=pop;
end

Crossover.m 交叉

function [a,b]=Crossover(pop1,pop2,crosspoint,N)%交叉
    A=pop1;
    if(crosspoint(:,1)

function [a]=Mutation(pop0,N)%变异
    crosspoint=rand(1,2);
    crosspoint=floor(crosspoint*N)+1;
    if(crosspoint(:,1)

function [a,b]=SwapRepeat(tbl,pop1,pop2,c1,c2,N)%基因去重
    i=100/N;
    for k=1:(c1-1)
        if tbl(pop1(k),3)>i
            kk=find(pop1(c1:c2)==pop1(k))+c1-1;
            kkk=pop1(k);
            pop1(k)=pop2(kk);
            pop2(kk)=kkk;
        end
    end
    for k=c2+1:N
        if tbl(pop1(k),3)>i
            kk=find(pop1(c1:c2)==pop1(k))+c1-1;
            kkk=pop1(k);
            pop1(k)=pop2(kk);
            pop2(kk)=kkk;
        end
    end
    a=pop1;
    b=pop2;
end

function [a]=SwapGene(sub,c1,c2)%交换
    kk=ceil((c2-c1)/2);
    kkk=(c2-c1)+2;
    for k=1:kk
        kkkk=sub(k);
        sub(k)=sub(kkk-k);
        sub(kkk-k)=kkkk;
    end
    a=sub;
end

function DrawPath(city_coordinate,E_new_new,min_index,N)%画路径图
    k=E_new_new(min_index,1:N)
    %plot(kkk(:,1),kkk(:,2),'b');%画平均适应度折线图
    plot(city_coordinate(:,1),city_coordinate(:,2),'bo');
    hold on;
    for i=1:N-1
        plot([city_coordinate(k(i),1),city_coordinate(k(i+1),1)],[city_coordinate(k(i),2),city_coordinate(k(i+1),2)],'r','LineWidth',2);
        test_t=num2str(i);
        text(city_coordinate(k(i),1),city_coordinate(k(i),2),test_t);
        hold on;
    end
    test_t=[num2str(N)];
    text(city_coordinate(k(N),1),city_coordinate(k(N),2),test_t);
end