深圳网页设计制作网站,环球资源网是卖什么的,网站seo优化技术入门,蚌埠市建设局网站一、蚁群算法 蚁群算法由意大利学者Dorigo M等根据自然界蚂蚁觅食行为提岀。蚂蚁觅食行为表示大量蚂蚁组成的群体构成一个信息正反馈机制#xff0c;在同一时间内路径越短蚂蚁分泌的信息就越多#xff0c;蚂蚁选择该路径的概率就更大。 蚁群算法的思想来源于自然界蚂蚁觅食在同一时间内路径越短蚂蚁分泌的信息就越多蚂蚁选择该路径的概率就更大。 蚁群算法的思想来源于自然界蚂蚁觅食蚂蚁在寻找食物源时会在路径上留下蚂蚁独有的路径标识——信息素蚂蚁会感知其他蚂蚁在各条路径上留下的信息素并根据各条路径上的信息素浓度来选择之后要走的路路径上留有的信息浓度越高则蚂蚁更倾向于选择该路径。在蚂蚁选择某条路径后也会在改路径上留下信息素吸引更多蚂蚁选择该路径随着时间的推移信息素浓度不断增大蚂蚁选择路径的概率也随之增高由此形成了正反馈机制。由于蚁群算法的正反馈性因此蚁群算法也属于增强型学习算法的其中一种。
初始时刻不妨将P kij (t)设为t时刻蚂蚁k从结点i转移到结点j的概率。“蚂蚁TSP”策略收到两方面的左右首先是访问某结点的概率这个概率的大小依赖于其他蚂蚁释放的信息素浓度。所以定义 式中nkij(t)为启发函数表示蚂蚁从结点i转移到结点j的概率allowk为蚂蚁k下一步可转移结点的集合随着时间的推移allowk储存的元素数量会减小最终会变为空集合。a 为信息素重要程度因子。 与实际情况类似的一点是随着时间的推移残留在路径上的信息素会逐渐挥发蚂蚁在经过路径时残留的信息素量也会逐渐等同于信息素挥发量最终使信息素残留量趋于稳定。令α表示信息素挥发程度那么所有蚂蚁遍历完所有结点之后各路径上的信息素残留量的数学表达式如下 式中ckij为第k只蚂蚁在连接结点i 与结点k的路径上释放信息素而增加的信息素浓度。Δckij为所有蚂蚁在结点i 与结点k 连接路径上释放信息素而增加的信息素浓度通常情况下 式中Q为路径信息素常量I为第k 只蚂蚁所经过路径的总长度。 二、蚁群算法改进自适应
改进自适应蚁群算法
1每次循环结束后求出最优解将其保留。
2自适应的改变 值。
1. 信息素挥发系数的存在会让没有搜索到的信息素的量减小到接近于0降低了算法的全局搜索能力。
2. 当过大且解的信息量过大时曾经搜索过的解被重新搜索的可能性会变大。
3. 减小提高算法的全局搜索能力但这会让算法的收敛速度降低
实现方法
1. 的初始值为
2. 当算法求得的最优解在N次循环内没有改进时减小为 三、实现步骤 四、代码结果
改进前 改进后 五、改进后运行的数据
1. 迭代最后城市之间的信息素部分 2. 最佳路径记录部分 3. 城市初始化顺序 4. 最终城市顺序最优结果 5. 最终蚁群算法初始参数
sumnum0; %记录选择概率全为0的次数
m100; %蚂蚁个数
Alpha1; %信息素重要程度参数
Beta5; %启发式因子重要程度参数
Rho1; %信息素蒸发系数
Rho_min0.2; %最小信息素蒸发系数
num_G0; %迭代多少次最优值不变得次数
num_G_max15; %最大迭代多少次最优值不变得次数
G_max200; %最大迭代次数
Q100; %信息素增加强度系数
六、代码改进前
clear all; %清除所有变量
close all; %清图
clc; %清屏%% 初始化
%蚂蚁个数50
%信息素重要程度参数1
%启发式因子重要程度参数5
%信息素蒸发系数0.1
%最大迭代次数200
%信息素增加强度系数100
m100; %蚂蚁个数
Alpha1; %信息素重要程度参数
Beta5; %启发式因子重要程度参数
Rho0.15; %信息素蒸发系数
G_max300; %最大迭代次数
Q100; %信息素增加强度系数 % C [1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;
% 3238 1229;4196 1044;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 2376;
% 3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;
% 2370 2975]; %31 个省会城市坐标C[6734 1453;2233 10;5530 1424;401 841;3082 1644;7608 4458;
7573 3716;7265 1268;6898 1885;1112 2049;5468 2606;5989 2873;
4706 2674;4612 2035;6347 2683;6107 669;7611 5184;7462 3590;
7732 4723;5900 3561;4483 3369;6101 1110;5199 2182;1633 2809
4307 2322;675 1006;7555 4819;7541 3981;3177 756;7352 4506;
7545 2801;3245 3305;6426 3173;4608 1198;23 2216;7248 3779;
7762 4595;7392 2244;3484 2829;6271 2135;4985 140;1916 1569;
7280 4899;7509 3239;10 2676;6807 2993;5185 3258;3023 1942]; %% 第一步变量初始化nsize(C,1); %n 表示问题的规模城市个数
Dzeros(n,n); %D 表示两个城市距离间隔矩阵
for i1:nfor j1:nif i~jD(i,j)((C(i,1)-C(j,1))^2(C(i,2)-C(j,2))^2)^0.5; %计算两两城市之间的距离elseD(i,j)eps;endD(j,i)D(i,j);end
end
Eta1./D; %Eta 为启发因子这里设为距离的倒数
Tauones(n,n); %Tau 为信息素矩阵
Tabuzeros(m,n); %存储并记录路径的生成
NC1; %迭代计数器
R_bestzeros(G_max,n); %各代最佳路线
L_bestinf.*ones(G_max,1); %各代最佳路线的长度
figure(1); %优化解
%% 判断是否满足终止条件若满足则结束搜索过程输出优化值若不满足则继续进行迭代优化。
while NCG_max
%% 第二步将 m 只蚂蚁放到 n 个城市上Randpos[];for i1:(ceil(m/n))Randpos[Randpos,randperm(n)];endTabu(:,1)(Randpos(1,1:m));
%% 第三步m 只蚂蚁按概率函数选择下一座城市完成各自的周游
%将 m 个蚂蚁置于n个城市上计算待选城市的概率分布m 只蚂蚁按概率函数选择下一座城市完成各自的周游。for j2:nfor i1:mvisitedTabu(i,1:(j-1)); %己访问的城市Jzeros(1,(n-j1)); %待访问的城市PJ; %待访问城市的选择概率分布Jc1;for k1:nif length(find(visitedk))0J(Jc)k;JcJc1;endend
%计算待选城市的概率分布for k1:length(J)P(k)(Tau(visited(end),J(k))^Alpha)...*(Eta(visited(end),J(k))^Beta);endPP/(sum(P));
%按概率原则选取下一个城市Pcumcumsum(P); % 如 P[1 2 3 4]则cumsum(P)[1 3 6 10],要累加轮盘赌法依次看是否在转得的区域内Selectfind(Pcumrand);%轮盘赌法随机选择to_visitJ(Select(1)); %待选择的城市Tabu(i,j)to_visit; %访问的城市endendif NC2Tabu(1,:)R_best(NC-1,:); %最佳路线end
%% 第四步记录本次迭代最佳路线Lzeros(m,1);for i1:mRTabu(i,:); %第i只蚂蚁走过的城市for j1:(n-1)L(i)L(i)D(R(j),R(j1)); %计算i只蚂蚁走过的路径endL(i)L(i)D(R(1),R(n)); %加上初始位置的路径endL_best(NC)min(L); %获取路径最少的一只posfind(LL_best(NC));%在50只蚂蚁中寻找走最少的一只R_best(NC,:)Tabu(pos(1),:);%记录最佳路径%% 第五步更新信息素%蚁环算法更新信息素增量%离线更新——蚁群Delta_Tauzeros(n,n);for i1:mfor j1:(n-1)Delta_Tau(Tabu(i,j),Tabu(i,j1))...Delta_Tau(Tabu(i,j),Tabu(i,j1))Q/L(i);%信息素增量的更新endDelta_Tau(Tabu(i,n),Tabu(i,1))...Delta_Tau(Tabu(i,n),Tabu(i,1))Q/L(i);%加上起使信息素增量的更新endTau(1-Rho).*TauDelta_Tau; %更新公式
%% 第六步: 禁忌表清零Tabuzeros(m,n);
%历代最优路线for i1:n-1plot([ C(R_best(NC,i),1), C(R_best(NC,i1),1)],...[C(R_best(NC,i),2), C(R_best(NC,i1),2)],bo-);%绘制路径hold on;endplot([C(R_best(NC,n),1), C(R_best(NC,1),1)],...[C(R_best(NC,n),2), C(R_best(NC,1),2)],ro-); %绘制更新过程title([优化最短距离:,num2str(L_best(NC))]); %输出结果hold off;pause(0.005);NCNC1; %迭代1
end
%% 第七步输出结果
Posfind(L_bestmin(L_best));
Shortest_RouteR_best(Pos(1),:); %最佳路线
Shortest_LengthL_best(Pos(1)); %最佳路线长度
figure(2),
plot(L_best)
xlabel(迭代次数)
ylabel(目标函数值)
title(适应度进化曲线)七、代码改进后
clear all; %清除所有变量
close all; %清图
clc; %清屏
%% 初始化sumnum0; %记录选择概率全为0的次数
m100; %蚂蚁个数
Alpha1; %信息素重要程度参数
Beta5; %启发式因子重要程度参数 Rho1; %信息素蒸发系数
Rho_min0.2; %最小信息素蒸发系数
num_G0; %迭代多少次最优值不变得次数
num_G_max3; %最大迭代多少次最优值不变得次数G_max200; %最大迭代次数
Q100; %信息素增加强度系数 %48 个省会城市坐标
C[6734 1453;2233 10;5530 1424;401 841;3082 1644;7608 4458;
7573 3716;7265 1268;6898 1885;1112 2049;5468 2606;5989 2873;
4706 2674;4612 2035;6347 2683;6107 669;7611 5184;7462 3590;
7732 4723;5900 3561;4483 3369;6101 1110;5199 2182;1633 2809
4307 2322;675 1006;7555 4819;7541 3981;3177 756;7352 4506;
7545 2801;3245 3305;6426 3173;4608 1198;23 2216;7248 3779;
7762 4595;7392 2244;3484 2829;6271 2135;4985 140;1916 1569;
7280 4899;7509 3239;10 2676;6807 2993;5185 3258;3023 1942]; %% 第一步变量初始化
aaaaeps;
nsize(C,1); %n 表示问题的规模城市个数
Dzeros(n,n); %D 表示两个城市距离间隔矩阵
for i1:nfor j1:nif i~jD(i,j)((C(i,1)-C(j,1))^2(C(i,2)-C(j,2))^2)^0.5; %计算两两城市之间的距离elseD(i,j)eps;%eps表示从 1.0 到下一个最大双精度数的距离endD(j,i)D(i,j);end
end
Eta1./D; %Eta 为启发因子这里设为距离的倒数
Tauones(n,n); %Tau 为信息素矩阵
Tabuzeros(m,n); %存储并记录路径的生成
NC1; %迭代计数器
R_bestzeros(G_max,n); %各代最佳路线
L_bestinf.*ones(G_max,1); %各代最佳路线的长度
figure(1); %优化解
%% 判断是否满足终止条件若满足则结束搜索过程输出优化值若不满足则继续进行迭代优化。
while NCG_max
%% 第二步将 m 只蚂蚁放到 n 个城市上Randpos[];for i1:(ceil(m/n))%蚂蚁个数除以城市个数向上取整Randpos[Randpos,randperm(n)];%生成ceil(m/n)个1*n的矩阵并合并endTabu(:,1)(Randpos(1,1:m)); %将Randpos的第一行前m个放到Tabu的第1列
%% 第三步m 只蚂蚁按概率函数选择下一座城市完成各自的周游
%将 m 个蚂蚁置于n个城市上计算待选城市的概率分布m 只蚂蚁按概率函数选择下一座城市完成各自的周游。for j2:n%第j个城市for i1:m%第i个蚂蚁visitedTabu(i,1:(j-1)); %己访问的城市Jzeros(1,(n-j1)); %待访问的城市PJ; %待访问城市的选择概率分布Jc1;for k1:nif length(find(visitedk))0%判断第k个城市有没有被访问J(Jc)k;JcJc1;endend
%计算待选城市的概率分布for k1:length(J)P(k)(Tau(visited(end),J(k))^Alpha)...*(Eta(visited(end),J(k))^Beta);end%% 修改%开始if sum(P)0to_visitJ(ceil(length(J)*rand)); %% 如果所选择的全部城市信息素为0将随机选择sumnumsumnum1;else%结束 PP/(sum(P));
%按概率原则选取下一个城市Pcumcumsum(P); % 如 P[1 2 3 4]则cumsum(P)[1 3 6 10],要累加轮盘赌法依次看是否在转得的区域内Selectfind(Pcumrand);%轮盘赌法随机选择to_visitJ(Select(1)); %待选择的城市endTabu(i,j)to_visit; %访问的城市endendif NC2Tabu(1,:)R_best(NC-1,:); %最佳路线end
%% 第四步记录本次迭代最佳路线Lzeros(m,1);%m*1的距离矩阵for i1:mRTabu(i,:); %第i只蚂蚁走过的城市for j1:(n-1)L(i)L(i)D(R(j),R(j1)); %计算i只蚂蚁走过的路径endL(i)L(i)D(R(1),R(n)); %加上初始位置的路径endL_best(NC)min(L); %获取路径最少的一只posfind(LL_best(NC));%在m只蚂蚁中寻找走最少的一只R_best(NC,:)Tabu(pos(1),:);%记录最佳路径
%% 改进算法%开始
if NC1
if L_best(NC)L_best(NC-1)num_Gnum_G1;if num_G num_G_maxif RhoRho_minRho0.95*Rho;if RhoRho_minRhoRho_min;endnum_G0;endend
end
end
Rho_list(NC)Rho;
%结束%% 第五步更新信息素%蚁环算法更新信息素增量%离线更新——蚁群Delta_Tauzeros(n,n);for i1:mfor j1:(n-1)Delta_Tau(Tabu(i,j),Tabu(i,j1))...Delta_Tau(Tabu(i,j),Tabu(i,j1))Q/L(i);%信息素增量的更新endDelta_Tau(Tabu(i,n),Tabu(i,1))...Delta_Tau(Tabu(i,n),Tabu(i,1))Q/L(i);%加上起使信息素增量的更新endTau(1-Rho).*TauDelta_Tau; %更新公式
%% 第六步: 禁忌表清零Tabuzeros(m,n);
%历代最优路线for i1:n-1plot([ C(R_best(NC,i),1), C(R_best(NC,i1),1)],...[C(R_best(NC,i),2), C(R_best(NC,i1),2)],bo-);%绘制路径hold on;endplot([C(R_best(NC,n),1), C(R_best(NC,1),1)],...[C(R_best(NC,n),2), C(R_best(NC,1),2)],ro-); %绘制更新过程title([优化最短距离:,num2str(L_best(NC))]); %输出结果hold off;pause(0.005);NCNC1; %迭代1
end
%% 第七步输出结果
Posfind(L_bestmin(L_best));
Shortest_RouteR_best(Pos(1),:); %最佳路线
Shortest_LengthL_best(Pos(1)); %最佳路线长度
figure(2),
plot(L_best)
xlabel(迭代次数)
ylabel(目标函数值)
title(适应度进化曲线)
figure(3),
plot(Rho_list)
xlabel(迭代次数)
ylabel(挥发系数)
title(挥发系数自适应曲线)
