1 算法介绍

1.1 TSP介绍

“旅行商问题”(Traveling Salesman Problem,TSP)可简单描述为：一位销售商从n个城市中的某一城市出发，不重复地走完其余n-1个城市并回到原出发点，在所有可能路径中求出路径长度最短的一条。

旅行商的路线可以看作是对n城市所设计的一个环形，或者是对一列n个城市的排列。由于对n个城市所有可能的遍历数目可达(n-1)!个，因此解决这个问题需要O(n!)的计算时间。而由美国密执根大学的Holland教授发展起来的遗传算法，是一种求解问题的高效并行全局搜索方法，能够解决复杂的全局优化问题，解决TSP问题也成为遗传算法界的一个目标。

1.2 遗传算法求解tsp模型

巡回旅行商问题(TSP)是一个组合优化方面的问题，已经成为测试组合优化新算法的标准问题。应用遗传算法解决 TSP 问题，首先对访问城市序列进行排列组合的方法编码，这保证了每个城市经过且只经过一次。接着生成初始种群，并计算适应度函数，即计算遍历所有城市的距离。然后用最优保存法确定选择算子，以保证优秀个体直接复制到下一代。采用有序交叉和倒置变异法确定交叉算子和变异算子。

算法流程

旅行商问题的遗传算法实现

1.初始群体设定

一般都是随机生成一个规模为 N 的初始群体。在这里，我们定义一个s行t列的pop矩阵来表示群体，t 为城市个数 + 1，即 N + 1，s 为样本中个体数目。在本文探讨了 30 个城市的 TSP 问题，此时 t 取值 31，该矩阵中每一行的前 30 个元素表示经过的城市编号，最后一个元素表示适应度函数的取值，即每个个体所求的距离。

2.适应度函数的设计是根据个体适应值对其优劣判定的评价函数。在该问题中用距离的总和作为适应度函数，来衡量求解结果是否最优。

3.选择指以一定的概率从群体中选择优胜个体的操作，它是建立在群体中个体适应度评估基础上的。为了加快局部搜索的速度，在算法中采用最优保存策略的方法，即将群体中适应度最大的个体直接替换适应度最小的个体。它们不进行交叉和变异运算，而是直接复制到下一代，以免交叉和变异运算破坏种群中的优秀解答。

4.交叉算子是产生新个体的主要手段。它是指将个体进行两两配对，以交叉概率 Pc 将配对的父代个体的部分结构加以替换重组生成新个体的操作。本文中采用有序交叉法来实现。有序交叉法的步骤描述如下:

5.变异操作是以较小的概率 Pm 对群体中个体编码串上的某位或者某些位作变动，从而生成新的个体。本文中采用倒置变异法:假设当前个体 X为(1 3 7 4 8 0 5 9 6 2)，如果当前随机概率值小于 Pm，则随机选择来自同一个体的两个点mutatepoint(1) 和 mutatepoint(2)，然后倒置两点的中间部分，产生新的个体。例如，假设随机选择个体 X 的两个点“7”和“9”，则倒置该两个点的中间部分，即将“4805”变为“5084”，产生新的个体 X 为(1 3 7 5 0 8 4 9 6 2)。

6.终止条件为循环一定的代数。

2 部分代码

nn=40; % number of cities
asz=10; % area size   asx x asz
​
​
ps=3000; % population size
ng=5000; % number of generation
​
pm=0.01; % probability of mutation of exchange 2 random cities in the path (per gene, per genration)
pm2=0.02; % probability of mutation of exchange 2 peices of path (per gene, per genration)
pmf=0.08; % probability of mutation  of flip random pece of path
​
r=asz*rand(2,nn); % randomly distribute cities
% r(1,:) -x coordinaties of cities
% r(2,:) -y coordinaties of cities
​
% % uncomment to make circle:
% % circle
% al1=linspace(0,2*pi,nn+1);
% al=al1(1:end-1);
% r(1,:)=0.5*asz+0.45*asz*cos(al);
% r(2,:)=0.5*asz+0.45*asz*sin(al);
​
dsm=zeros(nn,nn); % matrix of distancies
for n1=1:nn-1
    r1=r(:,n1);
    for n2=n1+1:nn
        r2=r(:,n2);
        dr=r1-r2;
        dr2=dr'*dr;
        drl=sqrt(dr2);
        dsm(n1,n2)=drl;
        dsm(n2,n1)=drl;
    end
end
​
% start from random closed pathes:
G=zeros(ps,nn); % genes, G(i,:) - gene of i-path, G(i,:) is row-vector with cities number in the path
for psc=1:ps
    G(psc,:)=randperm(nn);
end
​
figure('units','normalized','position',[0.05 0.2 0.9 0.6]);
​
subplot(1,2,1);
​
% to plot best path:
hpb=plot(NaN,NaN,'r-');
ht=title(' ');
​
hold on;
​
% plot nodes numbers
for n=1:nn
    text(r(1,n),r(2,n),num2str(n),'color',[0.7 0.7 0.7]);
end
​
plot(r(1,:),r(2,:),'k.'); % plot cities as black dots
​
​
​
axis equal;
xlim([-0.1*asz 1.1*asz]);
ylim([-0.1*asz 1.1*asz]);
​
subplot(1,2,2);
hi=imagesc(G);
title('color is city number');
colorbar;
xlabel('index in sequence of cities');
ylabel('path number');
​
pthd=zeros(ps,1); %path lengths
p=zeros(ps,1); % probabilities
for gc=1:ng % generations loop
    % find paths length:
    for psc=1:ps
        Gt=G(psc,:);
        pt=0; % path length summation
        for nc=1:nn-1
            pt=pt+dsm(Gt(nc),Gt(nc+1));
        end
        % last and first:
        pt=pt+dsm(Gt(nn),Gt(1));
        pthd(psc)=pt;
    end
    ipthd=1./pthd; % inverse path lengths, we want to maximize inverse path length
    p=ipthd/sum(ipthd); % probabilities
    
    [mbp bp]=max(p); 
    Gb=G(bp,:); % best path 
    
    % update best path on figure:
    if mod(gc,5)==0
        set(hpb,'Xdata',[r(1,Gb) r(1,Gb(1))],'YData',[r(2,Gb) r(2,Gb(1))]);
        set(ht,'string',['generation: ' num2str(gc)  '  best path length: ' num2str(pthd(bp))]);
        set(hi,'CData',G);
        drawnow;
    end
    
    
    % crossover:
    ii=roulette_wheel_indexes(ps,p); % genes with cities numers in ii will be put to crossover
    % length(ii)=ps, then more probability p(i) of i-gene then more
    % frequently it repeated in ii list
    Gc=G(ii,:); % genes to crossover
    Gch=zeros(ps,nn); % childrens
    for prc=1:(ps/2) % pairs counting
        i1=1+2*(prc-1);
        i2=2+2*(prc-1);
        g1=Gc(i1,:); %one gene
        g2=Gc(i2,:); %another gene
        cp=ceil((nn-1)*rand); % crossover point, random number form range [1; nn-1]

        
      
        % two childrens:
        g1ch=insert_begining(g1,g2,cp);
        g2ch=insert_begining(g2,g1,cp);
        Gch(i1,:)=g1ch;
        Gch(i2,:)=g2ch;
    end
    G=Gch; % now children
    
    
    % mutation of exchange 2 random cities:
    for psc=1:ps
        if rand<pm
            rnp=ceil(nn*rand); % random number of sicies to permuation
            rpnn=randperm(nn);
            ctp=rpnn(1:rnp); %chose rnp random cities to permutation
            Gt=G(psc,ctp); % get this cites from the list
            Gt=Gt(randperm(rnp)); % permutate cities
            G(psc,ctp)=Gt; % % return citeis back
         end
    end
    
    % mutation of exchange 2 peices of path:
    for psc=1:ps
        if rand<pm2
            cp=1+ceil((nn-3)*rand); % range [2 nn-2]
            G(psc,:)=[G(psc,cp+1:nn) G(psc,1:cp)];
        end
    end
    
    % mutation  of flip randm pece of path:
    for psc=1:ps
        if rand<pmf
            n1=ceil(nn*rand);
            n2=ceil(nn*rand);
            G(pscs,n1:n2)=fliplr(G(psc,n1:n2));
        end
    end
    
    
​
    
    G(1,:)=Gb; % elitism
    
    
        
end
​

3 仿真结果

4 参考文献

[1]谢胜利, 唐敏, 董金祥. 求解TSP问题的一种改进的遗传算法[J]. 计算机工程与应用, 2002, 38(008):58-60.

[2]文艺, and 潘大志. "用于求解TSP问题的改进遗传算法." 计算机科学 43.0z1(2016):90-92.