蚁群算法的由来
蚁群算法(ant colony optimization)最早是由Marco Dorigo等人在1991年提出，他们在研究新型算法的过程中，发现蚁群在寻找食物时，通过分泌一种称为信息素的生物激素交流觅食信息从而能快速的找到目标，据此提出了基于信息正反馈原理的蚁群算法。
蚁群算法的基本思想来源于自然界蚂蚁觅食的最短路径原理，根据昆虫科学家的观察，发现自然界的蚂蚁虽然视觉不发达，但它们可以在没有任何提示的情况下找到从食物源到巢穴的最短路径，并在周围环境发生变化后，自适应地搜索新的最佳路径。
蚂蚁在寻找食物源的时候，能在其走过的路径上释放一种叫信息素的激素，使一定范围内的其他蚂蚁能够察觉到。当一些路径上通过的蚂蚁越来越多时，信息素也就越来越多，蚂蚁们选择这条路径的概率也就越高，结果导致这条路径上的信息素又增多，蚂蚁走这条路的概率又增加，生生不息。这种选择过程被称为蚂蚁的自催化行为。对于单个蚂蚁来说，它并没有要寻找最短路径，只是根据概率选择；对于整个蚁群系统来说，它们却达到了寻找到最优路径的客观上的效果。这就是群体智能。
蚁群算法能做什么
蚁群算法根据模拟蚂蚁寻找食物的最短路径行为来设计的仿生算法，因此一般而言，蚁群算法用来解决最短路径问题，并真的在旅行商问题（TSP，一个寻找最短路径的问题）上取得了比较好的成效。目前，也已渐渐应用到其他领域中去，在图着色问题、车辆调度问题、集成电路设计、通讯网络、数据聚类分析等方面都有所应用。
函数优化问题MATLAB实现：
机器人路径规划：
更多ACO算法：http://www.omegaxyz.com/tag/aco/
TSP问题
旅行商问题，即TSP问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
本文要实现的代码
①问题建模
31个省市自治区的首都画在笛卡尔坐标系上，用坐标表示，两个城市间的距离用二维距离公式表示。
②初始化参数
m是种群数量，n是节点的多少（这里指城市数量的多少）
③构建解空间
将每个个体随机放到不同的点上，进行迭代更新
④更新信息素
计算本轮中最短路径，更新信息素。
⑤判断是否终止
ACO的优点
①采用正反馈机制，不容易陷入局部最优。
②利用信息素达到个体间的交互，有利于进行信息共享。
③可以并行编程，多个个体并行计算，有效地减少时间
MATLAB代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 |
%% 清空环境变量 clear all clc %% 导入数据 load citys_data.mat %% 计算城市间相互距离 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 %% 初始化参数 m = 50; % 蚂蚁数量 alpha = 1; % 信息素重要程度因子 beta = 5; % 启发函数重要程度因子 rho = 0.1; % 信息素挥发因子 Q = 1; % 常系数 Eta = 1./D; % 启发函数 Tau = ones(n,n); % 信息素矩阵 Table = zeros(m,n); % 路径记录表 iter = 1; % 迭代次数初值 iter_max = 500; % 最大迭代次数 Route_best = zeros(iter_max,n); % 各代最佳路径 Length_best = zeros(iter_max,1); % 各代最佳路径的长度 Length_ave = zeros(iter_max,1); % 各代路径的平均长度 %% 迭代寻找最佳路径 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); 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 %% 结果显示 [Shortest_Length,index] = min(Length_best); Shortest_Route = Route_best(index,:); disp(['最短距离:' num2str(Shortest_Length)]); disp(['最短路径:' num2str([Shortest_Route Shortest_Route(1)])]); %% 绘图 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('各代最短距离与平均距离对比') |
效果：
您好，轮盘赌选择下一城市的时候target = allow(target_index(1));一直会出现
索引超出数组元素的数目(0)。
这样的错误
若是改成target = allow(target_index(:,1));又会出现
位置 2 处的索引超出数组边界。
这样的错误
请问怎样才能完成target和target_index的匹配呢？
下载显示 该文件可能已被移至别处或遭到删除 是我没限权？
这篇文章的哪儿有下载？
citys_data.mat就是这个文件，或者距离矩阵怎么生成
手动输入点的坐标
是各代最短距离还是矢代最短距离啊
请问终点又回到起点是在哪里呢？
你好，请问一下如何把坐标改为距离矩阵
你可以根据坐标生成距离矩阵。
博主，只有距离矩阵，没有坐标的时候该怎么改
你这个m文件下不了呢，或者你能发个图片给我看看里面是什么嘛？citys_data.mat
挂VPN下载哦
求citys_data.mat 文件
我也想知道，你有了吗
你好，数据集可以从https://github.com/xyjigsaw/Dataset
下载
我们老师给的是这个，直接删掉load那一句，然后粘贴这个，citys=[
1304 2312;
3639 1315;
4177 2244;
3712 1399;
3488 1535;
3326 1556;
3238 1229;
4196 1004;
4312 790;
4386 570;
3007 1970;
2562 1756;
2788 1491;
2381 1676;
1332 695;
3715 1678;
3918 2179;
4061 2370;
3780 2212;
3676 2578;
4029 2838;
4263 2931;
3429 1908;
3507 2367;
3394 2643;
3439 3201;
2935 3240;
3140 3550;
2545 2357;
2778 2826;
2370 2975
]; %31个省会坐标数据
citys未定义
自己导入可以吧