蚁群算法解决路径优化问题 |
您所在的位置：网站首页 › 蚁群算法cvrp问题横纵坐标 › 蚁群算法解决路径优化问题 |
蚁群算法解决路径优化问题
|
蚁群算法是一种用来在图中寻找优化路径（最小花费函数）的几率型算法。 一．基本原理： 1 蚂蚁在行走过程中会释放一种称为“信息素”的物质，用来标识自己的行走路径。 2 在寻找食物的过程中，根据信息素的浓度选择行走的方向，并最终到达食物所在的地方。 3 信息素会随着时间的推移而逐渐挥发。 二．算法的特点： 1 自组织，依据信息素，使蚂蚁从无序到有序 2 并行的算法，每只蚂蚁都是独立的，具有较强的全局搜索能力。 3 正反馈，最短路径依赖于信息素的堆积 最经典的是旅行商问题的最优路径 三．算法步骤： 1 初始化参数 蚂蚁数量m，信息素因子α，启发函数因子β，信息素挥发因子p，信息素常数 构建Q，最大迭代次数t等等。 2构建解空间： 将各个蚂蚁随机的放置在不同的出发点，对于每个蚂蚁K（k=1,2,3，...m）,计算其下一个待访问的城市，直到所有蚂蚁访问完所有的城市。 3 更新信息素：计算各个蚂蚁经过的路径长度L，记录当前迭代次数中的最优解（最短路径），同时，对各个城市连接路径上的信息素浓度进行更新。 4 判断是否终止：若迭代次数小于最大迭代次数加一，清空蚂蚁经过路径的记录表，返回步骤2，否则终止计算，输出最优解。 解决旅行商问题： 四．参数的设计： 1 蚂蚁数量：过大，会导致每条路径上信息素趋于平均，正反馈作用减弱，从而导致收敛速度减慢。过小，会导致过早的收敛 2 信息素常量Q：就是每只蚂蚁能分泌的信息素总量。过大会使搜索范围减小容易过早，使种群陷入局部最优。过小，每条路径信息素差不多，会使种群陷入局部最优。 3 最大迭代次数t ：过多，运算时间过长。过小，可选择路径较少，使种群陷入局部最优解。 蚂蚁数量一般为目标数的1.5倍较为稳妥，信息素常量根据经验一般取值在[10,1000]。 最大迭代次数一般取[100,500]，通常会根据实际问题试用设置参数，直到找到最优的参数。 4 信息素因子α：反映了蚂蚁运动过程中路径积累信息素的量在蚁群搜索的相对重要程度，取值范围通常在[1,4]之间。 5 启发函数因子β：启发式信息在指导蚁群搜索中的相对重要程度，蚁群寻优过程的先验性，确定性因素作用的强度取值范围在[0,5]之间。之前蚂蚁对现在蚂蚁的影响程度。 6 信息挥发素因子p：反映了信息素的消失水平，相反的1-p反映了信息素的保持水平。取值范围通常在[0.2,0.5]之间。 五．构建解空间： 1构建路径: 每只蚂蚁随机的选择一个城市作为其出发城市，并维护一个路径记忆向量，用于存放该蚂蚁一次经过的城市，蚂蚁在构建路径的每一步中，用轮盘赌法选择下一个要到达的城市。 2轮盘赌法的概率公式：
a i,j分别为起点和终点，分子第一项为时间t时由i到j的信息素浓度，分子第二项为i到j路径距离的倒数，allowedk为尚未访问过的节点集合。 b 对轮盘概率的影响因素主要是，信息素浓度和启发函数（就是距离）。启发函数 η_ij(t)=1⁄d_ij用于表示蚂蚁从i到j的能见度。两地距离越短，信息素浓度越大的路径被选择的概率应该越大。从公式可以看出信息素因子ɑ为信息素浓度的指数，启发函数因子β为启发函数的指数。分别决定了信息素浓度以及转移期望对蚂蚁k从i到j的可能性的贡献程度。
123456表示城市，圆圈1到2中间的6表示城市间的距离，现在设每条路径上的信息素浓度均为1,信息素因子为2，启发函数因子为3，则蚂蚁k的起点城市为2到下一个城市j的概率分别为：
3 轮盘赌法：个体被选中的概率与其适应度大小成正比，让计算机产生一个[0，~，1]的数。
若计算机产生了一个随机数： 0.02，则蚂蚁会选择到城市1 （0~0.04） 0.05，则蚂蚁会选择到城市3 （0.04~0.08） 0.5，则蚂蚁会选择到城市5 （0.08~1） 更新信息素：
表示新增信息素含量=m只蚂蚁在城市i到j路径上留下的信息素总和 根据不同的规则，我们可以将蚁群算法分为三种模型，蚁周模型（ant-Cycle），蚁量模型（ant-Quantity）和蚁密模型（ant-Density）。 蚁周模型规则是：完成一次路径循环后，蚂蚁才释放信息素， 则新增信息素可计算为：
Q是信息素常量，即每只蚂蚁能产生的信息素，Lk表示蚂蚁k从i到j 判断是否终止：是否达到迭代次数 一次迭代就是指m只蚂蚁都走完所有的城市，即存在m个搜索路径。将所有路径进行比较，选择长度最短的路径，做出这一次迭代的可视化结果，更新信息素。并将当前的最短路径与过往的最短路径长度进行对比，同时迭代次数加1.然后判断当前迭代次数是否等于设置的迭代次数。如果等于则停止迭代，否则进行下一次迭代。 实例：TSP问题（旅行商） 一个旅行商人，他要遍历n个城市，但是每个城市只能遍历一次，最终还要回到最初所在的城市，要求制定一个遍历方案，使经过的总路程最短。 城市序号 1 2 3 4 5 6 7 x坐标 18.47 16.47 20.09 14.39 25.23 22.00 23.47 y坐标 95.10 94.64 94.54 93.37 97.24 93.05 92.02 城市序号 8 9 10 11 12 13 14 x坐标 16.2 17.30 13.05 15.53 24.52 16.41 15.09 y坐标 96.29 97.38 98.12 97.38 95.59 97.13 92.55 编程实例： 包括一个主函数和一个求城市间距离距离的函数 %% I. 清空环境 clc clear all %% II. 符号说明 % C -- n个城市的坐标 % NC_max -- 最大迭代次数 % m -- 蚁群中蚂蚁的数量，一般设置为城市的1.5倍 % D(i, j) -- 两城市i和之间的距离 % Eta(i, j) = 1 ./ D(i, j) -- 启发函数 % alpha -- 表征信息素重要程度的参数 % beta -- 表征启发函数重要程度的参数 % rho -- 信息素挥发因子 % Q -- 信息素常量，表示蚂蚁k可以产生的信息素 % rBest -- 各代最佳的路线 % lBest -- 各代最佳路线的长度 % lAverage --各代的平均长度 %% III. 导入城市位置数据 citys = [18.4700 95.1000 16.4700 94.6400 20.0900 94.5400 14.3900 93.3700 25.2300 97.2400 22.0000 93.0500 23.4700 92.0200 16.2000 96.2900 17.3000 97.3800 13.0500 98.1200 15.5300 97.3800 24.5200 95.5900 16.4100 97.1300 15.0900 92.5500]; %% IV. 计算距离矩阵 D = Distance(citys); % 计算距离矩阵 n = size(D, 1); % 城市的个数 %% V. 初始化参数 NC_max = 200; % 最大迭代次数，取100~500之间 m = 22; % 蚂蚁的个数，一般设为城市数量的1.5倍 alpha = 1; % α 选择[1, 4]比较合适 beta = 4; % β 选择[3 4 5]比较合适 rho = 0.2; % ρ 选择[0.1, 0.2, 0.5]比较合适 Q = 20; NC = 1; % 迭代次数，一开始为1 Eta = 1 ./ D; % η = 1 / D(i, j) ,这里是矩阵,每个城市距离的倒数 Tau = ones(n, n); % Tau(i, j)表示边(i, j)的信息素量，一开始都为1 Table = zeros(m, n); % 路径记录表 rBest = zeros(NC_max, n); % 记录各代的最佳路线 lBest = inf .* ones(NC_max, 1); % 记录各代的最佳路线的总长度 lAverage = zeros(NC_max, 1); % 记录各代路线的平均长度 %% VI. 迭代寻找最佳路径 while NC > S=[0 2 4 6 8 10 12 14 16 18 20]; %>> a=[1 2 3 4 5 6]; %>> k=ismember(a,S) %k =0 1 0 1 0 1 %1表示相同元素的位置 Allow = citys_index(allow_index); % Allow表：存放待访问的城市 P = Allow; % 计算从城市j到剩下未访问的城市的转移概率 for k = 1: size(Allow, 2) % 计算allow的列数，即待访问的城市数量 P(k) = Tau(tabu(end), Allow(k))^alpha * Eta(tabu(end), Allow(k))^beta; end P = P / sum(P); % 归一化 % 轮盘赌法选择下一个访问城市（为了增加随机性） Pc = cumsum(P);%cumsum函数默认是列求和，cumsum（p，1）。cumsum(p,2)按行求和。这里怎么是按行累加的？ target_index = find(Pc >= rand); target = Allow(target_index(1)); Table(i, j) = target; end end % 第3步：计算各个蚂蚁的路径距离 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 % 第4步：计算最短路径距离及平均距离 if NC == 1 [min_Length, min_index] = min(length); lBest(NC) = min_Length; lAverage(NC) = mean(length); rBest(NC, :) = Table(min_index, :); else [min_Length, min_index] = min(length); lBest(NC) = min(lBest(NC - 1), min_Length); lAverage(NC) = mean(length); if lBest(NC) == min_Length rBest(NC, :) = Table(min_index, :); else rBest(NC, :) = rBest((NC - 1), :); end end % 第5步：更新信息素 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; % 第6步：迭代次数加1，并且清空路径记录表 NC = NC + 1; Table = zeros(m, n); end %% VII. 结果显示 [shortest_Length, shortest_index] = min(lBest); shortest_Route = rBest(shortest_index, :); disp(['最短距离:' num2str(shortest_Length)]); disp(['最短路径:' num2str([shortest_Route shortest_Route(1)])]); %% VIII. 绘图 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: NC_max, lBest, 'b', 1: NC_max, lAverage, 'r:') legend('最短距离', '平均距离') xlabel('迭代次数') ylabel('距离') title('各代最短距离与平均距离对比') function D = Distance(citys) %% 计算两两城市之间的距离 % 输入:各城市的位置坐标(citys) % 输出:两两城市之间的距离(D) n = size(citys, 1);%用来计算citys矩阵的行数和列数。size(citys, 1)表示计算矩阵citys的行数，size(citys, 2)表示计算矩阵citys的列数 D = zeros(n, n); for i = 1: n for j = i + 1: n D(i, j) = sqrt((citys(i, 1) - citys(j, 1))^2 + (citys(i, 2) - citys(j, 2))^2); D(j, i) = D(i, j); end D(i, i) = 1e-4; %对角线的值为0，但由于后面的启发因子要取倒数，因此用一个很小数代替0 end运行结果：
图：
|
【本文地址】
今日新闻 |
推荐新闻 |