四、MATLAB程序实现
按照枚举法，我国31个直辖市、省会和自治区的巡回路径应该有约
1.326?10种，利用蚁群算法寻找一条最佳或者较佳的路径。利用MATLAB中提
32供的函数，可以方便地在MATLAB环境下实现。 4.1 清空环境变量
程序运行之前，清除工作空间Workspace中的变量及Command Window中的命令。具体程序如下： %% 清空环境变量 clear all clc
4.2 导入数据
31个城市的位置坐标保存在citys_data.mat文件中，变量citys为31行2列的数据，第1列表示各个城市的横坐标，第2列表示各个城市的纵坐标。具体城市如下： %% 导入数据
load citys_data.mat
4.3 计算城市间相互距离
利用城市的横、纵坐标，可以方便地计算出城市间的相互距离。具体程序如下：
%% 计算城市间相互距离 n = size(citys,1); D = zeros(n,n); for i = 1:n for j = 1:n if i ~= j
D(i,j) = sqrt(sum((citys(i,:) - citys(j,:)).^2)); else
D(i,j) = 1e-4; end end
end
4.4 初始化参数
在计算之前，需要对参数进行初始化。同时，为了加快程序的执行速度，对于程序中涉及的一些过程变量，需要预分配其存储容量。具体程序如下： %% 初始化参数
m = 50; % 蚂蚁数量
alpha = 1; % 信息素重要程度因子 beta = 5; % 启发函数重要程度因子 rho = 0.1; % 信息素挥发因子 Q = 1; % 常系数 Eta = 1./D; % 启发函数 Tau = ones(n,n); % 信息素矩阵 Table = zeros(m,n); % 路径记录表
16
iter = 1; % 迭代次数初值 iter_max = 200; % 最大迭代次数 Route_best = zeros(iter_max,n); % 各代最佳路径 Length_best = zeros(iter_max,1); % 各代最佳路径的长度 Length_ave = zeros(iter_max,1); % 各代路径的平均长度
4.5 迭代寻找最佳路径
迭代寻找最佳路径为整个算法的核心，首先逐个蚂蚁逐个城市访问，直至遍历所有的城市，以构建问题的解空间，然后计算各个蚂蚁经过路径的长度，记录下当前迭代次数中的最佳路径，并实时对各个城市间连续路径上的信息素浓度进行更新，最终经过多次迭代，寻找到最佳路径。具体程序如下： %% 迭代寻找最佳路径
while iter <= iter_max
% 随机产生各个蚂蚁的起点城市 start = zeros(m,1); for i = 1:m
temp = randperm(n); start(i) = temp(1); end
Table(:,1) = start; % 构建解空间
citys_index = 1:n; % 逐个蚂蚁路径选择 for i = 1:m
% 逐个城市路径选择 for j = 2:n
tabu = Table(i,1:(j - 1)); % 已访问的城市集合(禁忌表) allow_index = ~ismember(citys_index,tabu);
allow = citys_index(allow_index); % 待访问的城市集合 P = allow;
% 计算城市间转移概率
for k = 1:length(allow)
P(k) = Tau(tabu(end),allow(k))^alpha * Eta(tabu(end),allow(k))^beta; end
P = P/sum(P);
% 轮盘赌法选择下一个访问城市 Pc = cumsum(P);
target_index = find(Pc >= rand); target = allow(target_index(1)); Table(i,j) = target; end end
% 计算各个蚂蚁的路径距离 Length = zeros(m,1);
17
for i = 1:m
Route = Table(i,:); for j = 1:(n - 1)
Length(i) = Length(i) + D(Route(j),Route(j + 1)); end
Length(i) = Length(i) + D(Route(n),Route(1)); end
% 计算最短路径距离及平均距离 if iter == 1
[min_Length,min_index] = min(Length); Length_best(iter) = min_Length; Length_ave(iter) = mean(Length); Route_best(iter,:) = Table(min_index,:); else
[min_Length,min_index] = min(Length);
Length_best(iter) = min(Length_best(iter - 1),min_Length); Length_ave(iter) = mean(Length); if Length_best(iter) == min_Length
Route_best(iter,:) = Table(min_index,:); else
Route_best(iter,:) = Route_best((iter-1),:); end end
% 更新信息素
Delta_Tau = zeros(n,n); % 逐个蚂蚁计算 for i = 1:m
% 逐个城市计算
for j = 1:(n - 1)
Delta_Tau(Table(i,j),Table(i,j+1)) = Delta_Tau(Table(i,j),Table(i,j+1)) + Q/Length(i); end
Delta_Tau(Table(i,n),Table(i,1)) = Delta_Tau(Table(i,n),Table(i,1)) + Q/Length(i); end
Tau = (1-rho) * Tau + Delta_Tau; % 迭代次数加1，清空路径记录表 iter = iter + 1; Table = zeros(m,n); end
4.6 结果显示
为了更为直观地对结果进行观察和分析，将寻找到的最佳路径及其长度显示在Command Window中。具体程序如下： %% 结果显示
18
[Shortest_Length,index] = min(Length_best); Shortest_Route = Route_best(index,:); disp(['最短距离:' num2str(Shortest_Length)]);
disp(['最短路径:' num2str([Shortest_Route Shortest_Route(1)])]);
由于各个蚂蚁的起始城市是随机设定的，因此每次运行的结果都会不同。某次运行的结果如下： 最短距离:15828.7082
最短路径:15 14 12 13 11 23 16 4 2 5 6 7 8 9 10 3 18 17 19 24 4.7 绘图
为了更为直观地对结果进行观察和分析，以图形的形式将结果显示出来。具体程序如下： %% 绘图 figure(1)
plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],... [citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-'); grid on
for i = 1:size(citys,1)
text(citys(i,1),citys(i,2),[' ' num2str(i)]); end
text(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),' 起点');
text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),' 终点');
xlabel('城市位置横坐标') ylabel('城市位置纵坐标')
title(['蚁群算法优化路径(最短距离:' num2str(Shortest_Length) ')']) figure(2)
plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:') legend('最短距离','平均距离') xlabel('迭代次数') ylabel('距离')
title('各代最短距离与平均距离对比')
与运行结果对应的路径如图4-1所示。从图中可以清晰地看到，自起点出发，每个城市访问一次，遍历所有城市后，返回起点。寻找到的最短路15828.7082km。
各代的最短距离与平均距离如图4-2所示，从图中不难发现，随着迭代次数的增加，最短距离与平均距离均呈现不断下降的趋势。当迭代次数大于121时，最短距离已不再变化，表示已经寻找到最佳路径。
19
图4-1 蚁群算法优化路径
图4-2 各代的最短距离与平均距离对比
20
参考文献:
[1]Dorigo M,Maniezzo V,Colorni A.The ant system:optimization by a colonyof cooperating agents[J].IEEE Transaction on Systems,1996,26(1):1-26
[2]Gutjahr W J.A graph-based ant system and its convergence[J].FutureGeneration Computer Systems,2000,16(8):873-888
[3]Bonabeau E,Dorigo M,Theraulaz G.Inspiration for optimization fromsocial insect behavior[J].Nature,2000,406(6):39-42
[4]马良，朱刚，宁爱兵．蚁群优化算法[M]．北京：科学出版社，2008
[5]周康，强小利，同小军等.求解TSP算法[J].计算机工程与应用,2007,43(29):43-47 [6]Holland J H.Genetic algorithms and the optimal allocation of trials[J].SIAM Journal of Computing,1973,2(2)：89-104
[7]胡纯德,祝延军,高随祥.一种求解旅行商问题的单亲遗传算法[J].计算机工程与应用,2004,40(35)：37-40
[8]刘烨,倪志伟,刘慧婷.求解旅行商问题的一个改进的遗传算法[J].计算机工程与应用,2007,40(6)：65-68
[9]莫海芳,康立山.求解TSP问题的混合遗传算法[J].计算机工程与应用,2007,43(18)：40-41
[10]Glover F.Future Paths for Interger Programming and Links to ArtificalIntelligence[J].Computers and Operations Research,1986,13(5):533-549 [11]方永慧,刘光远,贺一等.一种基于插入法的禁忌搜索算法[J].西南师范大学学报(自然科学版),2002,27(3):341-345
[12]杨宁，田蔚风，金志华.一种求解旅行商问题的交叉禁忌搜索[J].系统仿真学报，2006，18(4)：897-900
21