多目标优化蚁群算法的matlab_混合参数蚁群算法的改进优化
蚁群算法是一个功能强大的优化算法，常用来求解旅行商 (TSP) 问题。本文分享一个我自己写的蚁群算法 Matlab 程序代码，详细交代其中的优化点。主要特色是对蚁群的启发参数采用混合参数，即每只蚂蚁的参数不一样，以更好地发挥出蚁群算法的优势。此外，我还对信息素的记录规则进行了一些优化，使之好于天然蚁群的行为。 1、旅行商 (TSP) 问题先交代一下什么是旅行商问题，即 Traveling Sa..
蚁群算法是一个功能强大的优化算法，常用来求解旅行商 (TSP) 问题。本文分享一个我自己写的蚁群算法 Matlab 程序代码，详细交代其中的优化点。主要特色是对蚁群的
1、旅行商 (TSP) 问题
先交代一下什么是旅行商问题，即 Traveling Salesman Problem (TSP). 给定地图上 N 个点的坐标，让一个走街窜巷的小商贩从其中任何一个点出发，周游全部的 N 个点，每个点只经过一次，最后回到出发点。如何安排这 N 个点的访问次序，使周游路径的总长度最小？
旅行商问题不同于最短路径，没有多项式时间的严格解法，属于 NP 难问题。主要原因是问题并非指定起点和终点的目的性旅行，而是要周游全部的 N 个点，且规定每个点只访问一次。旅行商问题类似于哈密顿环问题。后者是在一个非完全连通的无向图上判定周游路径是否存在，而前者则是在一个完全连通的无向图上寻找最短的周游路径。
2、蚁群算法简介
蚁群算法受自然界中的蚁群寻找最短路径的启发。每只蚂蚁遇到一个岔路口表现出随机行为，在群体留下的信息素和局域距离信息的贪心规则启发下选择道路。信息素的通俗理解就是蚂蚁们留下的“脚印”，用来帮助每只蚂蚁判断哪条路走的人多。而贪心规则就是尽量就近选择下一个点。比如一只蚂蚁站在点 i 上，下一个点 j 被访问的概率
如果 j 是已访问点 (visited)，则
Evan：蚁群算法 - 求解 TSP 问题
在传统的蚁群算法中，所有蚂蚁的
3、本文的改进和创新点
针对这些问题，本文对传统的蚁群算法的信息素记录规则和蚂蚁们的
引入排名因子除了能择优推广成功经验以外，还有一个好处：增大了更优 TSP 路径发现者的话语权。以 50 只蚂蚁为例。如果整个种群中有一大半的蚂蚁都卡在了某个次优的 TSP 路径上，而恰巧有 1 只蚂蚁发现了更短的路径，按照传统规则，它只有 1/50 的话语权。而按照排名因子规则，前 10 只蚂蚁权重线性递减，第一名大约有 1/5 的话语权。这使得先进的经验能更加顺利地推广，而落后的经验更不容易形成自锁和压制先进经验的产生。
在改进后的信息素记录规则下，我们又进一步优化了蚂蚁们的
beta = 5 * rand(N_ants, 1) .^ 0.6;
alpha = 3 - rand(N_ants, 1) .* min(3, 2 + beta / 3);设定 N_ants = 50，表示有 50 只蚂蚁。每轮迭代重新随机产生 50 只蚂蚁的参数，尽可能遍历有意义的参数空间。最后，我们还对
4、迭代收敛性测试
对第 1 节中 N_cities = 30 个点的图，用 N_ants = 50 只蚂蚁迭代 N_iter = 100 轮，所有蚂蚁走出的平均 TSP 路径长度 Length_avg 和已发现最短 TSP 路径长度 Length_best 如下图所示。最终求得 Length_best = 423.4278。迭代终止时，有 36 只蚂蚁找到了这条最短的 TSP 路径，而仍有 14 只蚂蚁在尝试寻找其它更短路径。
附：图 1、3 的测试数据
1 67.6574 86.3741 11 22.5754 39.3258 21 82.1454 44.2359
2 7.3892 19.7959 12 23.4455 57.5248 22 84.2245 30.3047
3 79.3013 30.5917 13 29.3575 32.6004 23 79.2524 10.4921
4 42.0558 56.5795 14 85.1126 5.8458 24 53.6559 35.8695
5 89.5986 53.8136 15 77.4075 47.7901 25 23.6507 83.3554
6 89.9445 40.212 16 89.3246 17.5049 26 51.8401 38.1844
7 57.702 80.4651 17 12.8378 81.6263 27 88.1619 71.7336
8 88.1541 43.0679 18 58.1159 20.3746 28 38.6824 13.4435
9 45.3028 94.5444 19 13.627 66.3624 29 74.1217 54.1191
10 16.8351 93.063 20 81.7615 61.2067 30 14.4592 84.35685、代码展示
% TSP solved by ant colony optimization (ACO)
% Part 1.1 Generate the map
N_cities = 30; N_ants = 50; N_iter = 100;
cities = 5 + rand(N_cities, 2) * 90;
plot(cities(:, 1), cities(:, 2), 'bo');
xticks([0: 10: 100]); yticks([0: 10: 100]);
xlabel('X'); ylabel('Y'); grid on;
axis equal; axis([0, 100, 0, 100]); getframe;
% Part 1.2 Calculate distances
D = zeros(N_cities, N_cities);
for i = 1 : N_cities
for j = 1 : N_cities
x = cities(i, 1) - cities(j, 1);
y = cities(i, 2) - cities(j, 2);
D(i, j) = sqrt(x * x + y * y);
end
end
% Part 1.3 Prepare memory tables
Tau = zeros(N_cities, N_cities); % pheromone matrix
Route_best = zeros(N_cities, 1); % Best TSP trajectory
Length_best = zeros(N_iter, 1); % Best TSP length
Length_avg = zeros(N_iter, 1); % Average TSP length
% Part 2 The main loop
for iter = 1 : N_iter
beta = 5 * rand(N_ants, 1) .^ 0.6;
alpha = 3 - rand(N_ants, 1) .* min(3, 2 + beta / 3);
% Part 2.1 Generate TSP trajectories
Table = zeros(N_ants, N_cities);
for i = 1 : N_ants
Table(i, 1) = unidrnd(N_cities);
cities_index = 1 : N_cities;
for j = 2 : N_cities
has_visited = Table(i, 1 : (j - 1));
allow_index = ~ismember(cities_index, has_visited);
allow_cities = cities_index(allow_index);
P = zeros(length(allow_cities), 1);
for k = 1 : length(allow_cities)
tau = Tau(has_visited(end), allow_cities(k)) + 0.01;
dist = D(has_visited(end), allow_cities(k));
P(k) = tau ^ alpha(i) / dist ^ beta(i);
end
P = P / sum(P); Pc = cumsum(P);
target_index = find(Pc >= rand);
target_city = allow_cities(target_index(1));
Table(i, j) = target_city;
end
end
% Part 2.2 Calculate TSP lengths
Length = zeros(N_ants, 1);
for i = 1 : N_ants
TSP = [Table(i, :), Table(i, 1)];
for j = 1 : N_cities
dist = D(TSP(j), TSP(j + 1));
Length(i) = Length(i) + dist;
end
end
Length_avg(iter) = mean(Length);
[min_Length, min_index] = min(Length);
if iter == 1 || min_Length < Length_best(iter - 1)
Length_best(iter) = min_Length;
Route_best = Table(min_index, :);
else
Length_best(iter) = Length_best(iter - 1);
Table = [Table; Route_best];
Length = [Length; Length_best(iter)];
end
% Part 2.3 Update Tau matrix (pheromones)
Delta_Tau = zeros(N_cities, N_cities);
[Len, index] = sort(Length);
vol = max(0.1, 0.5 * (1 - (iter - 1) / 15));
pcnt = max(0.2, vol); n_ants = floor(N_ants * pcnt);
for i = 1 : n_ants
TSP = [Table(index(i), :), Table(index(i), 1)];
tau = Len(1) / Len(i) * (1 - (i - 0.5) / n_ants);
for j = 1 : N_cities
x = TSP(j); y = TSP(j + 1);
Delta_Tau(x, y) = Delta_Tau(x, y) + tau;
end
end
Delta_Tau = (Delta_Tau + transpose(Delta_Tau)) / n_ants * 2;
Tau = Tau * (1 - vol) + Delta_Tau * vol;
% Part 2.4 Plot currently best TSP
TSP = [Route_best, Route_best(1)];
plot(cities(TSP, 1), cities(TSP, 2), 'bo-');
xticks([0: 10: 100]); yticks([0: 10: 100]);
xlabel('X'); ylabel('Y'); grid on;
axis equal; axis([0, 100, 0, 100]);
title(['Iteration = ',num2str(iter),', Length = ',num2str(Length_best(iter))]);
getframe;
end
% Part 3 Print standardized TSP and label the cities
TSP = Route_best; i = find(TSP == 1);
TSP = [TSP(i : end), TSP(1 : i - 1)];
if TSP(2) > TSP(end)
TSP = [TSP(1), TSP(end : -1 : 2)];
end
for i = 1 : N_cities
x = cities(i, 1); y = cities(i, 2);
text(x + 1, y + 1, num2str(i));
end
disp(['Min TSP Length = ', num2str(Length_best(end))]);
disp(['TSP trajectory: ', num2str(TSP)]);
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
6
0- 0
已为社区贡献5条内容
所有评论(0)