怎么给喜欢的人做网站,嘉兴海盐县城乡建设局网站,一个完整网站制作的实例,东莞凤岗企业网站建设推广蚁群算法简介
蚁群算法#xff08;Ant Clony Optimization#xff0c; ACO#xff09;是一种群智能算法#xff0c;它是由一群无智能或有轻微智能的个体#xff08;Agent#xff09;通过相互协作而表现出智能行为#xff0c;从而为求解复杂问题提供了一个新的方法。 蚁…蚁群算法简介
蚁群算法Ant Clony Optimization ACO是一种群智能算法它是由一群无智能或有轻微智能的个体Agent通过相互协作而表现出智能行为从而为求解复杂问题提供了一个新的方法。 蚁群算法是一种模拟进化算法初步的研究表明该算法具有许多优良的性质。
蚁群算法最早用来求解TSP问题并且表现出了很大的优越性因为它分布式特性鲁棒性强并且容易与其它算法结合但是同时也存在这收敛速度慢容易陷入局部最优local optimal等缺点。
蚂蚁寻找食物
蚂蚁在行走过程中会释放一种称为“信息素”的物质用来标识自己的行走路径。在寻找食物的过程中根据信息素的浓度选择行走的方向并最终到达食物所在的地方。
而信息素会随着时间的推移而逐渐挥发所以在一开始的时候由于地面上没有信息素因此蚂蚁们的行走路径是随机的。蚂蚁们在行走的过程中会不断释放信息素标识自己的行走路径。随着时间的推移有若干只蚂蚁找到了食物此时便存在若干条从洞穴到食物的路径。由于蚂蚁的行为轨迹是随机分布的因此在单位时间内短路径上的蚂蚁数量比长路径上的蚂蚁数量要多从而蚂蚁留下的信息素浓度也就越高。这为后面的蚂蚁们提供了强有力的方向指引越来越多的蚂蚁聚集到最短的路径上去。 优化问题与蚂蚁寻找食物的关系
蚁群算法自然界的蚂蚁可行解蚂蚁行走的路径最优解待寻找的最短路径解空间所有可能的路径信息素矩阵某条途径上的信息素浓度轮盘赌选择路径根据信息素浓度来选择路径
蚁群算法基本操作
初始化参数
蚁群算法所需要的参数
蚁群规模蚂蚁数量 m m m信息素重要程度因子 α \alpha α启发函数重要程度因子 β \beta β信息素挥发因子 ρ \rho ρ信息素释放总量 Q Q Q最大迭代次数 i t e r m a x iter_{max} itermax
另外设节点i与节点j之间的距离权为 d i j ( i , j 1 , 2 , . . . , n ) d_{ij} \ (i,j1,2,...,n) dij (i,j1,2,...,n) t t t时刻节点i与节点j连接路径上的信息素浓度为 τ i j ( t ) \tau_{ij}(t) τij(t)在初始时刻各路径上信息素浓度相同即 τ i j ( 0 ) τ 0 \tau_{ij}(0) \tau_0 τij(0)τ0。
构建解空间
随机将蚂蚁置于所有出发点蚂蚁按规则访问所有节点计算每个蚂蚁经过的路径和长度求出最优路径
访问规则蚂蚁 k ( k 1 , 2 , . . . , m ) k \ (k 1,2,...,m) k (k1,2,...,m)根据各个节点连接路径上的信息素浓度和路径距离权决定其下一个要访问的节点。t时刻蚂蚁k从节点i访问节点j的概率蚂蚁已经在节点i为 P i j k [ τ i j ( t ) ] α ∗ [ η i j ( t ) ] β ∑ s ∈ a l l o w k [ τ i j ( t ) ] α ∗ [ η i j ( t ) ] β s ∈ a l l o w k P^k_{ij} \frac{[\tau_{ij}(t)]^\alpha*[\eta_{ij}(t)]^\beta}{\sum_{s \in allow_k}[\tau_{ij}(t)]^\alpha*[\eta_{ij}(t)]^\beta} \qquad s \in allow_k Pijk∑s∈allowk[τij(t)]α∗[ηij(t)]β[τij(t)]α∗[ηij(t)]βs∈allowk 其中 η i j \eta_{ij} ηij为启发函数 η i j 1 d i j \eta_{ij} \frac{1}{d_{ij}} ηijdij1表示蚂蚁从节点i转移到节点j的期望程度 a l l o w k allow_k allowk表示蚂蚁k剩余待访问的节点集合。
更新信息素
蚂蚁访问完所有城市之后进行信息素的更新。信息素的更新包括挥发和蚂蚁的产生由以下公式决定 τ i j ( t 1 ) ( 1 − ρ ) τ i j ( t ) Δ τ i j \tau_{ij}(t1) (1-\rho)\tau_{ij}(t)\Delta\tau_{ij} τij(t1)(1−ρ)τij(t)Δτij
前一部分是信息素的挥发后一部分表示每只蚂蚁在这一段路上新差生的信息素。 Δ τ i j ∑ k 1 n Δ τ i j k \Delta\tau_{ij} \sum_{k1}^n \Delta\tau_{ij}^k Δτijk1∑nΔτijk 即对每只蚂蚁在该段路上释放信息素浓度之和。而对于蚂蚁k在i到j之间所释放的信息素 Δ τ i j k \Delta\tau_{ij}^k Δτijk的计算有三种不同的模型
蚁周模型释放总量一定利用路径整体信息计算 L k L_k Lk为第k只蚂蚁经过路径的总长 Δ τ i j k Q L k \Delta\tau_{ij}^k \frac{Q}{L_k} ΔτijkLkQ蚁量模型释放总量一定利用路径局部信息计算 Δ τ i j k Q d i j \Delta\tau_{ij}^k \frac{Q}{d_{ij}} ΔτijkdijQ蚁密模型每段路释放量一定 Δ τ i j k Q \Delta\tau_{ij}^k Q ΔτijkQ
判断终止与迭代
递增迭代次数计数器如果达到了最大代数则输出否则清空路径记录表继续迭代。
代码实现
代码使用蚁群算法计算中国TSP问题的最优解。
% 使用蚁群算法解决旅行商TSP问题的优化
% 中国31个省会城市的坐标数据保存在文件city_data.mat中%导入数据
load city_data.mat%计算城市之间的相互距离矩阵
n size(city_data,1); %城市数目为n
D zeros(n,n); %距离矩阵为D
for i 1:nfor j 1:nif i ~ jD(i,j) sqrt((city_data(i,1)-city_data(j,1))^2(city_data(i,2)-city_data(j,2))^2);elseD(i,j) 1e-4; %为了不使启发函数变成infendend
end%初始化蚁群算法各个参数
eta 1./D; %启发函数
m 31; %蚂蚁个数31
alpha 1; %信息素重要程度因子
beta 5; %启发函数重要程度因子
rho 0.5; %信息素挥发因子
Q 1; %信息素释放总量
iter_max 400; %最大迭代次数
iter 0; %代数初值
Table zeros(m,n); %每只蚂蚁的路径记录表
tau ones(n,n); %各节点间路径上的信息素含量记录表tau0 1)%开始迭代
while 1%结束迭代的条件iter iter 1;if iter iter_maxbreakend%清空路径记录表Table zeros(m,n);%构建解空间city 1:n;%随机将蚂蚁置于所有出发点start floor(n*rand(m,1))1;Table(:,1) start;%逐个蚂蚁进行路径选择for i 1:m%对于每个蚂蚁逐个节点进行访问for j 2:n%初始化以访问的节点禁忌表tabu Table(i,1:(j-1));allow city(~ismember(city,tabu));%计算节点间转移概率P zeros(size(allow));for k 1:length(allow)P(k) tau(tabu(end),allow(k))^alpha * eta(tabu(end),allow(k))^beta;endP P/sum(P);%轮盘赌法选择下一个访问的城市P_sum cumsum(P);target allow(find(P_sum rand,1));Table(i,j) target;endend%计算每个蚂蚁经过的路径Length zeros(m,1);for i 1:mRoute Table(i,:);for j 1:(n-1)Length(i) Length(i) D(Route(j),Route(j1));endLength(i) Length(i) D(Route(n),Route(1));end%更新信息素Delta_tau zeros(n,n);for i 1:mfor j 1:(n-1)Delta_tau(Table(i,j),Table(i,j1)) Delta_tau(Table(i,j),Table(i,j1)) Q/Length(i);endDelta_tau(Table(i,n),Table(i,1)) Delta_tau(Table(i,n),Table(i,1)) Q/Length(i);endtau (1-rho)*tau Delta_tau;endmin(Length)代码输出结果为 而中国TSP问题的最新研究结果为15377km因此该算法寻求到的是一个局部最优解。
