《带精英策略的蚂蚁系统》由会员分享，可在线阅读，更多相关《带精英策略的蚂蚁系统（5页珍藏版）》请在金锄头文库上搜索。
1、用蚁群算法解决TSP问题function R_best,L_best,L_ave,Shortest_Route,Shortest_Length=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)%-% 主要符号说明% C n个城市的坐标，n2的矩阵% NC_max 最大迭代次数% m 蚂蚁个数% Alpha 表征信息素重要程度的参数% Beta 表征启发式因子重要程度的参数% Rho 信息素蒸发系数% Q 信息素增加强度系数% R_best 各代最佳路线% L_best 各代最佳路线的长度%=%第一步：变量初始化C=41 94;37 84;54 67;25 62; 7 64
2、;2 99;68 58;71 44; 54 62; 83 69;64 60;18 54; 22 60;83 46;91 38;25 38; 24 42;58 69;71 71;74 78; 87 76;18 40;13 40;82 7; 62 32;58 35;45 21;41 26; 44 35;4 50; Alpha=1; Beta=5; Q=100; Rho=0.1;n=size(C,1);%n表示问题的规模（城市个数）D=zeros(n,n);%D表示完全图的赋权邻接矩阵for i=1:nfor j=1:nif i=jD(i,j)=(C(i,1)-C(j,1)2+(C(i,2)-C(j
3、,2)2)0.5;elseD(i,j)=eps; %i=j时不计算，应该为0，但后面的启发因子要取倒数，用eps（浮点相对精度）表示endD(j,i)=D(i,j); %对称矩阵endendm=90;Eta=1./D; %Eta为启发因子，这里设为距离的倒数Tau=ones(n,n); %Tau为信息素矩阵Tabu=zeros(m,n); %存储并记录路径的生成NC=1; NC_max =100;%迭代计数器，记录迭代次数%R_best=zeros(NC_max,n); %各代最佳路线%L_best=inf.*ones(NC_max,1); %各代最佳路线的长度%L_ave=zeros(NC_
4、max,1); %各代路线的平均长度while NC=rand); %若计算的概率大于原来的就选择这条路线to_visit=J(Select(1);Tabu(i,j)=to_visit;endendif NC=2Tabu(1,:)=R_best(NC-1,:);end%第四步：记录本次迭代最佳路线L=zeros(m,1); %开始距离为0，m*1的列向量for i=1:mR=Tabu(i,:);for j=1:(n-1)L(i)=L(i)+D(R(j),R(j+1); %原距离加上第j个城市到第j+1个城市的距离endL(i)=L(i)+D(R(1),R(n); %一轮下来后走过的距离endL
5、_best(NC)=min(L); %最佳距离取最小pos=find(L=L_best(NC);R_best(NC,:)=Tabu(pos(1),:); %此轮迭代后的最佳路线q=size(pos); x=q(1); %x精英蚂蚁数R=;R=R_best(NC,:);L_ave(NC)=mean(L); %此轮迭代后的平均距离NC=NC+1 %迭代继续%第五步：更新信息素Delta_Tau=zeros(n,n); %开始时信息素为n*n的0矩阵for i=1:mfor j=1:(n-1)Delta_Tau(Tabu(i,j),Tabu(i,j+1)=Delta_Tau(Tabu(i,j),Ta
6、bu(i,j+1)+Q/L(i); %此次循环在路径（i，j）上的信息素增量endDelta_Tau(Tabu(i,n),Tabu(i,1)=Delta_Tau(Tabu(i,n),Tabu(i,1)+Q/L(i);%此次循环在整个路径上的信息素增量endfor j=1:(n-1)Delta_Tau(Tabu(pos(1),j),Tabu(pos(1),j+1)=Delta_Tau(Tabu(pos(1),j),Tabu(pos(1),j+1)+Q/L(pos(1)+x*Q/L(pos(1);endDelta_Tau(Tabu(pos(1),n),Tabu(pos(1),1)=Delta_Ta
7、u(Tabu(pos(1),n),Tabu(pos(1),1)+Q/L(pos(1)+x*Q/L(pos(1);Tau=(1-Rho).*Tau+Delta_Tau; %考虑信息素挥发，更新后的信息素%第六步：禁忌表清零Tabu=zeros(m,n); %直到最大迭代次数end%第七步：输出结果Pos=find(L_best=min(L_best); %找到最佳路径（非0为真）Shortest_Route=R_best(Pos(1),:) %最大迭代次数后最佳路径Shortest_Length=L_best(Pos(1) %最大迭代次数后最短距离subplot(1,2,1) %绘制第一个子图形
8、DrawRoute(C,Shortest_Route) %画路线图的子函数subplot(1,2,2) %绘制第二个子图形plot(L_best)hold on %保持图形plot(L_ave,r)title(平均距离和最短距离) %标题运行结果Shortest_Route = Columns 1 through 20 24 25 26 29 28 27 16 17 22 23 30 12 13 4 5 6 1 2 3 9 Columns 21 through 30 18 19 20 21 10 11 7 8 14 15Shortest_Length = 425.6490基于蚁群优化算法的旋转
9、货架拣选路径规划 冯艳君，李梅娟,王罡近年来,许多学者已提出了多种主法来求解旋转货架拣选路径规划问题。有的文献采用启发式算法对这一问题进行求解,但是启发式算法针对性较强,缺乏通用性;有的文献中用改进的模拟退火算法进行了研究,其最终解是全局或近似最优解;还有的文献提出层序邻域概念及其快速局部搜索方法,设计了将其与遗传算法相结合的新型混合遗传算法,该算法虽然克服了单纯用遗传算法解决问题早期收敛、遗传漂移以及容易陷入局部最优解的缺点,但是它的全局最优解出现的概率却比较低。因此，专家学者们提出了改进的蚁群优化算法,用于解决货物拣选路径规划问题。该方法能够在全局内快速找到最优货物拣选路径,求解质量高,计
10、算时间短。遗传算法试验的主要内容及步骤如下:(1)给出了旋转货架拣选路径规划问题的数学模型;(2)对基本蚁群算法改进后进行设计和描述;(3)仿真实验,对结果进行对比分析并得出结论：“该方法适合求解中小规模货物拣选路径规划问题,提高了自动存储作业效率”。遗传算法在试验中出现的问题及改进方法：基本蚁群算法优点是具有很强的发现较好解的能力,不容易陷入局部最优。但当种群规较大时算法复杂度高,搜索时间长的问题就显得尤为突出。（1）造成这些问题的原因之一是随着解空间的增大,位于一点上的蚂蚁个体在选择转移路径时,不同路径上的转移概率相互接近的可能性也越大,而基本蚁群算法在每次进化时,只能固定地选择其中一条路
11、径,若在每一个点上都放置一只蚂蚁,必然使算法复杂度增加,搜索时间长。（2）针对问题本身的特点,由于每次作业时货架都从拣选点开始旋转,并且完成拣选作业后又回到拣选点,因此在这里,提出一种对基本蚁群算法进行改进的方法,每次循环开始时在起始点既拣选点上放置m只蚂蚁,作业开始后,m只蚂蚁随机地选择下一个拣选货位点。这样可以有效地减小算法的复杂度,缩短搜索时间。运用遗传算法解决旋转货架拣选路径规划结论：根据单拣选台分层水平旋转货架系统,建立货物拣选路径规划问题的数学模型,将该问题归结为旅行售货商问题,首次引入蚁群优化算法进行求解,基于单拣选台旋转货架拣选路径规划问题特点,对基本蚁群算法进行了改进。通过仿真实验对比,解决中小规模拣选路径规划问题能够快速找到全局最优解,并且求解质量高,计算时间比其它方法大大缩短,从而提高了自动存储作业效率。如何改进算法更好地求解大规模货物拣选路径规划问题有待作进一步的研究。
