TSP商旅问题（从某个城市出发经过经过n个城市一次且仅一次，最后回到出发城市）

xiaomangguo

MATLAB程序实现
1.种群初始化
初始化函数InitPop代码：
function Chrom = InitPop(NIND,N)
%%初始化种群
%输入：
%NIND:种群大小
%N：个体染色体长度（这里是水库的个数）
%输出：
%初始种群
Chrom = zeros(NIND,N);
for i = 1:NIND
    Chrom(i,:) = randperm(N);
end
2.适应度函数
适应度函数Fitness代码：
function FitnV = Fitness(len)
%%适应度函数
%输入：
%len     个体的长度
%输出：
%FitnV   个体的适应度
FitnV = 1./len;

3.选择操作
选择函数Select的代码：
function SelCh = Select(Chrom,FitnV,GGAP)
%%选择操作
%输入：
%Chrom  种群
%FitnV  适应度值
%GGAP   选择概率
%输出：
%SelCh  被选择个体
NIND = size(Chrom,1);
NSel = max(floor(NIND * GGAP+ .5),2);
ChrIx = Sus(FitnV,NSel);
SelCh = Chrom(ChrIx,:);
其中函数Sus的代码为：
function NewChrIx = Sus(FitnV,Nsel)
%输入：
%FitnV  个体的适应度值
%Nsel   被选择个体的数目
%输出：
%NewChrIx 被选择个体的索引号
[NIND,ans] = size(FitnV);
cumfit = cumsum(FitnV);
trials = cumfit(Nind) / Nsel * (rand + (0:Nsel-1)');
Mf = cumfit(:,ones(1,Nsel));
Mt = trials(:,ones(1,Nind))';
[NewChrIx, ans] = find(Mt < Mf & [zeros(1,Nsel);Mf(1:Nind-1, :)] < = Mt);
[ans,shuf] = sort(rand(Nsel,1));
NewChrIx = NewChrIx(shuf);

4.交叉操作
交叉操作函数Recombin的代码
function SelCh = Recombin(SelCh,Pc)
%%交叉操作
%输入：
%SleCh  被选择的个体
%Pc     交叉概率
%输出：
%SelCh  交叉后的个体
Nsel = size(SelCh,1);
for i = 1:2:NSel - mod(NSel,2)
    if Pc >= rand    %交叉概率Pc
        [SelCh(i,:),SelCh(i+1,:)] = intercross(SelCh(i,:),SelCh(i+1,:)):
    end
end
其中 intercross的代码为：
function [a,b] = intercros(a,b)
%输入：
%a和b为两个待交叉的个体
%输出：
%a和b为两个交叉后得到的两个个体
L = length(a);
r1 = randsrc(1,1,[1:L]);
r2 = randsrc(1,1,[1:L]);
if r1~= r2
    a0 = a;b0 = b;
    s = min([r1,r2]);
    e = max([r1,r2]);
    for i = s:e
        a1 = a;b1 = b;
        a(i) = b0(i);
        b(i) = a0(i);
        x = find(a == a(i));
        y = find(b == b(i));
        i1 = x(x~=i);
        i2 = y(y~=i);
        if ~isempty(i1)
            a(i1) =a1(i);
        end
        if ~isempty(i2)
            a(i2) =b1(i);
        end
    end
end

5.变异操作
变异函数Mutate的代码：
function SelCh = Mutate(SelCh,Pm)
%%变异操作
%输入：
%SleCh  被选择的个体
%Pm     变异概率
%输出：
%SelCh  变异后的个体
[NSel,L] = size(SelCh);
for i = 1:nsEL
    if Pm >= rand    %变异概率Pm
        R = randperm(L);
        SelCh(i,R(1:2)) = SelCh(i,R(2: -1;1));
    end
end

6.进行逆转操作
逆转函数Reverse的代码
function SelCh = Reverse(SelCh,D)
%%进行逆转函数
%输入：
%SleCh  被选择的个体
%D      各城市间的距离
%输出：
%SelCh  进行逆转后的个体
[row,col] = size(SelCh);
Objv = PathLength(D,SelCh);  %计算路线长度
SelCh1 = SelCh;
for i = 1:row
    r1 = randsrc(1,1,[1;col]);
    r2 = randsrc(1,1,[1;col]);
    mininverse = min([r1 r2]);
    maxinverse = max([r1,r2]);
    SelCh1(1,mininverse:maxinverse) =SelCh1(i,maxinverse: -1:mininverse):
end
ObjV1 = PathLength(D,SelCh1);   %计算路线长度
index = ObjV1 < ObjV;
SelCh(index,:) = SelCh1(index,:);
7.画路线轨迹图
画图函数DrawPath的代码：
function DrawPath(Chrom,X)
%%画路线图函数
%输入：
%Chrom  待画路线
%X      各城市的坐标位置
R = [Chrom(1,:) Chrom(1,1)];    %一个随机解（个体）
figure;
hold on
plot(X(:,1),X(:,2),'o','color',[0.5,0.5,0.5])
plot(X(Chrom(1,1),1),X(Chrom(1,1),2),'rv','MarkerSize',20)
for i = 1:size(X,1)
    text(X(i,1) + 0.05,X(i,2)+0.05,num2str(i),'color',[1,0,0]);
end
A = X(R,:);
row = size(A,1);
for i = 2:row
    [arrowx,arrowy] = dsxy2figxy(gca,A(i-1:i,1),A(i-1:i,2));  %坐标转换
    annotation('textarrow',arrowx,arrowy,'HeadWidth',8,'color',[0,0,1]);
end
hold off
xlabel(' 横坐标 ')
ylabel(' 纵坐标 ')
title(' 轨迹图 ')
box on
其中坐标转换函数dsxy2figxy的代码为：
function varargout = dsxy2figxy(varargin)
if length(varargin{1}) == 1 && ishandle(varargin{1}) ...
                             && strcmp(get(varargin{1},'type'),'axes')   
     hAx = varargin{1};
     varargin = varargin(2:end);
else
     hAx = gca;
end;
if length(varargin) == 1
     pos = varargin{1};
else
     [x,y] = deal(varargin{:});
end
axun = get(hAx,'Units');
set(hAx,'Units','normalized');
axpos = get(hAx,'Position');
axlim = axis(hAx);
axwidth = diff(axlim(1:2));
axheight = diff(axlim(3:4));
if exist('x','var')
     varargout{1} = (x - axlim(1)) * axpos(3) / axwidth + axpos(1);
     varargout{2} = (y - axlim(3)) * axpos(4) / axheight + axpos(2);
else
     pos(1) = (pos(1) - axlim(1)) / axwidth * axpos(3) + axpos(1);
     pos(2) = (pos(2) - axlim(3)) / axheight * axpos(4) + axpos(2);
     pos(3) = pos(3) * axpos(3) / axwidth;
     pos(4) = pos(4) * axpos(4 )/ axheight;
     varargout{1} = pos;
end
set(hAx,'Units',axun)

遗传算法主函数
主函数代码如下：
clear
clc
close all
X=[16.47,96.10
   16.47,94.44
   20.09,92.54
   22.39,93.37
   25.23,97.24
   22.00,96.05
   20.47,97.02
   17.20,96.29
   16.30,97.38
   14.05,98.12
   16.53,97.38
   21.52,95.59
   19.41,97.13
   20.09,92.55];
NIND=100;
MAXGEN=200;
Pc=0.9;
Pm=0.05;
GGAP=0.9;
D=Distanse(X);
N=size(D,1);
%%初始化种群
Chrom=InitPop(NIND,N);
%%在二维图上画出所以坐标点
%figure
%piot(X( :,1),X( :,2),'o');
%%画出随机解的路线图
DrawPath(Chrom(1, :),X)
pause(0.0001)
%%输出随机解的路线和总距离
disp('初始种群中的一个随机值：')
OutputPath(Chrom(1,:));
Rlength = PathLength(D,Chrom(1,:))
disp(['总距离:',num2str(Rlength)]);
disp('____________________')
%%优化
gen = 0;
figure;
hold on;box on
xlim([0,MAXGEN])
title('优化过程')
xlabel('代数')
ylabel('最优值')
ObjV = PathLength(D,Chrom);
preObjV  = min(ObjV );
while gen<MAXGEN
    %%计算适应度
    Objv = PathLength(D,Chrom);
    %fprintf('%d   %1.10f\n',gen,min(Objv))
    line([gen -1,gen],[preObjV ]);pause(0.0001)
    preObjV  = min(ObjV );
    FitnV = Fitness(ObjV )
    %%选择
    SelCh = Select(Chrom,FitnV,GGAP);
    %%交叉操作
    SelCh = Recombin(SelCh,Pc);
    %%变异
    SelCh = Mutate(SelCh,Pm);
    %%逆转操作
    SelCh = Reverse(SelCh,D);
    %%重插入子代的新种群
    Chrom = Reins(Chrom,SelCh,ObjV );
    %%更新迭代次数
    gen = gen+1;
end
%%画出最优解的路线图
Objv = PathLength(D,Chrom);
[minObjV ,minInd] = min(ObjV );
DrawPath(Chrom(minInd(1),:),X)
%%输出最优解的路线和总距离
disp('最优解:')
p = OutputPath(Chrom(minInd(1),:));
disp(['总距离':',num2str(ObjV (minInd(1)))]);
    disp('-------------------’）


其中
1.计算距离函数Distanse,其代码如下：
function D = Distanse(a)
%%计算两两城市间的距离
%输入 a 各城市的位置坐标
%输出 D 两两城市间的距离

row =size(a,1);
D = zeros(row,row);
for i = 1:row
    for j = i+1:row
        D(i,j) = ((a(i,1)-a(j,1))^2+(a(i,2)-a(j,2))^2)^0.5;
        D(j,i) = D(i,j);
    end
end

2.输出路线函数OutputPath（R）代码
function p = OutputPath(R)
%%输出路线函数
%输入  R  路线
R=[R,R(1)];
N = length(R);
p = num2str(R(1));
for i = 2:N
    p = [p,'->',num2str(R(1))];;
end
disp(p)

3.计算个体路线长度函数PathLength代码
function len = PathLength(D,Chrom)
%%计算个体的路线长度
%输入：
%D    两两城市之间的距离
%Chrom  个体的轨迹
[row,col] = size(D);
NIND = size(Chrom,1);
len = zeros(NIND,1);
for i=1:NIND
    p = [Chrom(i,:) Chrom(i,1)];
    i1 = p(1:end-1);
    i2 = p(2:end);
    len(i,1) = sum(D((i1-1)*col + i2));
end

5.重新插入子代得到新种群的函数Reins
function Chrom = Reins(Chrom,SelCh,ObjV)
%%重插入子代的新种群
%输入：
%Chrom   父代的种群
%SelCh   子代种群
Objv     父代适应度
%输出：
%Chrom   组合父代与子代厚得到的新种群
NIND = size(Chrom,1);
NSel = size(SelCh,1);
[TobjV,index] = sort(ObjV);
Chrom = [Chrom(index(1:NIND-NSel),:);SelCh];