iacskroc100bingxingxiaochuangkoubianyi.m

这是在最初的蚁群算法的变异算子的基础上改进的变异算子

%具有遗传特征的蚁群系统
clear;
gens=10000;                                         %搜索代数
tracepop1=zeros(gens,2);                        %记录平均搜索到的最优路径长度随进化代数变化的规律（统计值）第一列存储进化代数，第二列存储路径长度
iterations=20;                                  %iterations实验次数
ppp=zeros(iterations,101);
for ffff=1:iterations
time1=clock;
c=[1 1357 1905
2 2650 802
3 1774 107
4 1307 964
5 3806 746
6 2687 1353
7 43 1957
8 3092 1668
9 185 1542
10 834 629
11 40 462
12 1183 1391
13 2048 1628
14 1097 643
15 1838 1732
16 234 1118
17 3314 1881
18 737 1285
19 779 777
20 2312 1949
21 2576 189
22 3078 1541
23 2781 478
24 705 1812
25 3409 1917
26 323 1714
27 1660 1556
28 3729 1188
29 693 1383
30 2361 640
31 2433 1538
32 554 1825
33 913 317
34 3586 1909
35 2636 727
36 1000 457
37 482 1337
38 3704 1082
39 3635 1174
40 1362 1526
41 2049 417
42 2552 1909
43 3939 640
44 219 898
45 812 351
46 901 1552
47 2513 1572
48 242 584
49 826 1226
50 3278 799
51 86 1065
52 14 454
53 1327 1893
54 2773 1286
55 2469 1838
56 3835 963
57 1031 428
58 3853 1712
59 1868 197
60 1544 863
61 457 1607
62 3174 1064
63 192 1004
64 2318 1925
65 2232 1374
66 396 828
67 2365 1649
68 2499 658
69 1410 307
70 2990 214
71 3646 1018
72 3394 1028
73 1779 90
74 1058 372
75 2933 1459
76 3099 173
77 2178 978
78 138 1610
79 2082 1753
80 2302 1127
81 805 272
82 22 1617
83 3213 1085
84 99 536
85 1533 1780
86 3564 676
87 29 6
88 3808 1375
89 2221 291
90 3499 1885
91 3124 408
92 781 671
93 1027 1041
94 3249 378
95 3297 491
96 213 220
97 721 186
98 3736 1542
99 868 731
100 960 303];                               %城市坐标信息
m=size(c,1);                             %城市个数
dist=zeros(m,m);                            
distance=zeros(m,m);%城市间距离信息的倒数矩阵,distance存储城市间的距离信息
for i=1:m
    for j=1:m
        if i==j
            dist(i,j)=0;
            distance(i,j)=0;
           else
           dist(i,j)=1/(round(((c(i,3)-c(j,3))^2+(c(i,2)-c(j,2))^2)));
           distance(i,j)=(round(sqrt((c(i,3)-c(j,3))^2+(c(i,2)-c(j,2))^2)));
        end
   end
end
initial=1/23564;                   %根据具体问题更改
for i=1:m
    for j=1:m
        if i==j
            pheromone0(i,j)=0;
        else
            pheromone0(i,j)=initial*(1/m);  %pheromone0信息素初始值存储矩阵
        end
    end
end
pheromone=pheromone0;                         %信息素存储矩阵，实时更新
choiceinfor=zeros(m,m);                       %choiceinfor信息素和启发式信息存储矩阵，实时更新
for i=1:m
    for j=1:m
        if i==j
            choiceinfor(i,j)=0;
        else
            choiceinfor(i,j)=pheromone0(i,j)*((dist(i,j)));
        end
    end
end
antnum=10;                                        %蚂蚁总数是个定值，具体确定原因，见参考文献
%信息素分配完毕
aaa=1;                                            %信息素敏感参数
bbb=2;                                            %可见度敏感参数
q0=0.98;                                  
q1=0.1;                                           %挥发参数1 
q2=0.1;                                           %挥发参数2
tracepop=zeros(gens,m+1);  %记录当前最优路径
for gen=1:gens
    pop=zeros(antnum,m+1);
    for i=1:antnum
        tabu(i,1:m)=1:m;       %存储蚂蚁下一步可选城市
    end
    for i=1:m
        for j=1:antnum
            if i==1
                bzw=ceil(m*rand(1));
                pop(j,i)=tabu(j,bzw);
                tt=tabu(j,1);
                tabu(j,1)=tabu(j,bzw);
                tabu(j,bzw)=tt;    %tabu含义其第j行的后m-i+1个元素存储的是第j个蚂蚁在第i步可选的城市集合
            end
            if i>1
            %tabu1的第一行下一步可能城市
            tabu1=zeros(2,m-i+1);
            tabu1(1,1:m-i+1)=tabu(j,i:m);
           %tabu1的第二行表示选择信息
            tabu1(2,1:m-i+1)=choiceinfor(pop(j,i-1),tabu1(1,1:m-i+1));
           %按概率选择下一个城市
            randomfig=rand(1);
            randomfig1=rand(1);
if randomfig<q0
    [x1,y1]=max(tabu1(2,:));  %
    bzw=y1;
    pop(j,i)=tabu1(1,bzw);
    tt=tabu(j,i);
    tabu(j,i)=tabu(j,i+y1-1);
    tabu(j,i+y1-1)=tt; 
else
    ddd=zeros(1,m-i+1);
    ddd(1,1:m-i+1)=distance(pop(j,i-1),tabu1(1,1:m-i+1));
    [x1,y1]=sort(ddd);
    i8=min(15,m-i+1);
    tabu2=zeros(2,i8);
    tabu2(1,1:i8)=tabu1(1,y1(1:i8));
    tabu2(2,1:i8)=dist(pop(j,i-1),tabu1(1,y1(1:i8)));
    summation=sum(tabu2(2,:));
    probability(1,1:i8)=tabu2(2,1:i8)/summation;               %概率
    cumulateprobability=cumsum(probability);
    randomfig=rand(1);
    for j1=1:i8
        if randomfig<cumulateprobability(1,j1)
                bzw=j1;
                pop(j,i)=tabu2(1,bzw);
                tt=tabu(j,i);
                tabu(j,i)=tabu(j,i+y1(j1)-1);
                tabu(j,i+y1(j1)-1)=tt; 
                break;
         end
    end
end
%局部信息素更新
pheromone(pop(j,i-1),pop(j,i))=(1-q2)*pheromone(pop(j,i-1),pop(j,i))+q2*pheromone0(pop(j,i-1),pop(j,i));
pheromone(pop(j,i),pop(j,i-1))=pheromone(pop(j,i-1),pop(j,i));
choiceinfor(pop(j,i-1),pop(j,i))=pheromone(pop(j,i-1),pop(j,i))*(dist(pop(j,i-1),pop(j,i)));
choiceinfor(pop(j,i),pop(j,i-1))=choiceinfor(pop(j,i-1),pop(j,i));
%局部信息素更新完毕
end
end
end
%路径长度计算
for i1=1:antnum                                                
    for j1=1:m-1
        pop(i1,m+1)=pop(i1,m+1)+distance(pop(i1,j1),pop(i1,j1+1));
    end
       pop(i1,m+1)=pop(i1,m+1)+distance(pop(i1,m),pop(i1,1));
end
%路径长度计算完毕
[x,y]=min(pop(:,m+1));
tracepop(gen,1:m+1)=pop(y,1:m+1);
if gen>1
   if tracepop(gen-1,m+1)<tracepop(gen,m+1)
       tracepop(gen,1:m+1)=tracepop(gen-1,1:m+1);
   end
end
tracepop1(gen,1)=gen;
tracepop1(gen,2)=tracepop1(gen,2)+tracepop(gen,m+1)/iterations;
ave(gen,1)=gen;
ave(gen,2)=mean(pop(:,m+1)); 
%信息素更新
%全局信息素更新
for j=1:m-1
       pheromone(tracepop(gen,j),tracepop(gen,j+1))=(1-q1)*pheromone(tracepop(gen,j),tracepop(gen,j+1))+q1/tracepop(gen,m+1);
       pheromone(tracepop(gen,j+1),tracepop(gen,j))=pheromone(tracepop(gen,j),tracepop(gen,j+1));
       choiceinfor(tracepop(gen,j),tracepop(gen,j+1))=pheromone(tracepop(gen,j),tracepop(gen,j+1))*(dist(tracepop(gen,j),tracepop(gen,j+1)));
       choiceinfor(tracepop(gen,j+1),tracepop(gen,j))=choiceinfor(tracepop(gen,j),tracepop(gen,j+1));
end
pheromone(tracepop(gen,m),tracepop(gen,1))=(1-q1)*pheromone(tracepop(gen,m),tracepop(gen,1))+q1/tracepop(gen,m+1);
pheromone(tracepop(gen,1),tracepop(gen,m))=pheromone(tracepop(gen,m),tracepop(gen,1));
choiceinfor(tracepop(gen,m),tracepop(gen,1))=pheromone(tracepop(gen,m),tracepop(gen,1))*(dist(tracepop(gen,m),tracepop(gen,1)));
choiceinfor(tracepop(gen,1),tracepop(gen,m))=choiceinfor(tracepop(gen,m),tracepop(gen,1));
%全局信息素更新完毕
end
tracepop(gens,m+1)
timend=etime(clock,time1)
ppp(ffff,1:m+1)=tracepop(gens,1:m+1);
end
mean(ppp(1:ffff,m+1))
max(ppp(1:ffff,m+1))
min(ppp(1:ffff,m+1))