1 简介

旅行商问题是一个经典的NP(non-deterministic polynomial)困难问题,在日常生活中比较常见,例如物流,旅游,抄表等等.由于旅行商问题的时间复杂度增长很快,精确算法很难在可接受的时间内找到最优答案.因此解决旅行商问题通常使用启发式算法,遗传算法就是其中之一. 遗传算法是一种仿生算法.遗传算法将所需解决的问题抽象为种群,对种群的个体进行适应度评估,按照人工方向进行定向选择,淘汰适应度低个体,保留适应度高的个体进行基因重组和变异,经过多次迭代,得到问题的一个近似最优解.遗传算法自诞生以来得到了广泛的应用.但是,遗传算法存在对初始种群依赖性强,易早熟,收敛速度难以控制等方面的缺陷,需要对遗传算法进行改进. 为了克服遗传算法的缺陷,提出遗传蚁群算法.遗传蚁群算法结合使用遗传算法和蚁群算法.

2 部分代码

% function y20_2clc % 清屏clear; % 删除workplace变量close all; % 关掉显示图形窗口tic% 保留每次迭代的最优解% 以max(t^a*d^(-b))为依据找最优路劲，与保留的最优路劲比较x=[2,4,7,13,18,18,22,24,25,25,37,41,41,44,45,54,54,58,58,62,64,68,71,71,74,82,83,83,87,91];y=[99,50,64,40,40,54,60,42,38,62,84,26,94,35,21,62,67,35,69,32,60,58,44,71,78,7,46,69,76,38];n=30;% n表示城市数c=100;%最初的q=10^(+6);NC=50;r=0.5;% r表示轨迹持久性a=1;% a表示轨迹相对重要性b=4;% b表示能见度相对重要性m=30;% m表示蚂蚁数目for i=1:n    for j=1:n        dij(i,j)=sqrt((x(i)-x(j))^2+(y(i)-y(j))^2);%距离    endendfor i=1:n    dij(i,i)=0.01;endmin10=10^5;t=ones(n)*c;for i=1:100    road(i,:)=randperm(n);    ltspc(i)=ca_tsp(n,road(i,:),dij);endltspsort=sort(ltspc);l30=ltspsort(m);%选择m个初始解,m只蚂蚁i1=0;for i=1:100    if ltspc(i)<=1300        for k=1:n-1            t(road(i,k),road(i,k+1))=t(road(i,k),road(i,k+1))+10;            t(road(i,k+1),road(i,k))=t(road(i,k),road(i,k+1));        end        t(road(i,1),road(i,n))=t(road(i,1),road(i,n))+10;        t(road(i,n),road(i,1))=t(road(i,1),road(i,n));            i1=i1+1;        pcbest(i1,:)=road(i,:);%初始pcbest路径长度        plbest(i1)=ltspc(i);%初始plbest，路径    endend[glbest,j]=min(plbest);%初始glbest路径长度gcbest=pcbest(j,:);%初始gcbest路径for nc=1:NC    tabu=ones(m,n);%禁忌表    tabu(:,1)=0;    path=ones(m,n);    for k=1:m        for step=1:n-1            ta=t.^a;            tb=dij.^(-b);            td=ta.*tb;            pd=tabu(k,:).*td(path(k,step),:);            pk=pd/sum(pd);%概率            rk=rand;            spk=0;            j=1;            while j<=n                if rk<spk+pk(j)                    break;                else                    spk=spk+pk(j);                    j=j+1;                end %%ta=t.^a;tb=dij.^(-b);td=ta.*tb;k=3;ts(1)=1;td(:,1)=0;[my,i]=max(td(1,:));ts(2)=i;td(:,i)=0;while k<=n    [my,i]=max(td(i,:));    ts(k)=i;    td(:,i)=0;    k=k+1;endts;ltsp0=ca_tsp(n,ts,dij);if glbest<ltsp0    ts=gcbest;    ltsp0=glbest;endk=1;while k<=n    x1(k)=x(ts(k));    y1(k)=y(ts(k));    k=k+1;endx1(n+1)=x1(1);y1(n+1)=y1(1);%绘制图形figure(1),plot(x,y,'o--');grid onfigure(2),line(x1,y1,'color','r','linewidth',2);hold onplot(x,y,'o--');grid on[x1',y1']ltsp0tocend% ca_tsp.m% 计算路径长度function ltsp=ca_tsp(n,c,dij)i=1;ltsp=dij(c(n),c(1));while i<n    ltsp=ltsp+dij(c(i),c(i+1));    i=i+1;endend

3 仿真结果

4 参考文献

[1]熊道勇, 肖人岳. 遗传算法和蚂蚁算法混合求解旅行商问题[J]. 科学技术与工程, 2009(19):3.

[2]刘新亮. 基于遗传蚁群算法的旅行商问题的研究[D]. 山东科技大学, 2017.

博主简介：擅长智能优化算法、神经网络预测、信号处理、元胞自动机、图像处理、路径规划、无人机等多种领域的Matlab仿真，相关matlab代码问题可私信交流。

部分理论引用网络文献，若有侵权联系博主删除。