此时的目标函数为侦察所有目标的路径长度或称代价函数。我们要求
minf(?1,?2,?,?102)??d??i?1101ii?1
而一次迭代由下列三步构成：
（3）新解的产生 ① 2变换法
任选序号 u,v（u?v）交换u与v之间的顺序，此时的新路径为：
?1??u?1?v?v?1??u?1?u?v?1??102
② 3变换法
任选序号u,v和w，将u和v之间的路径插到w之后，对应的新路径为（设u?v?w）
?1??u?1?v?1??w?u??v?w?1??102 （4）代价函数差
对于2变换法，路径差可表示为
?f?(d?u?1?v?d?u?v?1)?(d?u?1?u?d?v?v?1)
（5）接受准则
?f?0?1 P??exp(??f/T)?f?0? 如果?f?0，则接受新的路径。否则，以概率exp(??f/T) 接受新的路径，即若exp(??f/T)大于0到1之间的随机数则接受。
（6）降温
利用选定的降温系数?进行降温即：T??T，得到新的温度，这里我们取??0.9999。
（7）结束条件 用选定的终止温度e?10，判断退火过程是否结束。若T?e，算法结束，输出当前状态。
我们编写如下的matlab程序如下： clc,clear
load sj.txt %加载敌方100个目标的数据，数据按照表格中的位置保存在纯文本文件sj.txt中
x=sj(:,1:2:8);x=x(:); y=sj(:,2:2:8);y=y(:); sj=[x y]; d1=[70,40]; sj=[d1;sj;d1]; sj=sj*pi/180; %距离矩阵d d=zeros(102); for i=1:101
for j=i+1:102
temp=cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2)); d(i,j)=6370*acos(temp); end
-275-
?30end d=d+d';
S0=[];Sum=inf;
rand('state',sum(clock)); for j=1:1000
S=[1 1+randperm(100),102]; temp=0; for i=1:101
temp=temp+d(S(i),S(i+1)); end
if temp S0=S;Sum=temp; end end e=0.1^30;L=20000;at=0.999;T=1; %退火过程 for k=1:L %产生新解 c=2+floor(100*rand(1,2)); c=sort(c); c1=c(1);c2=c(2); %计算代价函数值 df=d(S0(c1-1),S0(c2))+d(S0(c1),S0(c2+1))-d(S0(c1-1),S0(c1))-d(S0(c2),S0(c2+1)); %接受准则 if df<0 S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:102)]; Sum=Sum+df; elseif exp(-df/T)>rand(1) S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:102)]; Sum=Sum+df; end T=T*at; if T break; end end % 输出巡航路径及路径长度 S0,Sum 计算结果为44小时左右。其中的一个巡航路径如下图所示： -276- 4035302520151050010203040506070 §3 蚁群算法 3.1 蚁群算法简介 蚁群是自然界中常见的一种生物，人们对蚂蚁的关注大都是因为“蚁群搬家，天要下雨”之类的民谚。然而随着近代仿生学的发展，这种似乎微不足道的小东西越来越多地受到学者们地关注。1991年意大利学者M. Dorigo等人首先提出了蚁群算法，人们开始了对蚁群的研究：相对弱小，功能并不强大的个体是如何完成复杂的工作的（如寻找到食物的最佳路径并返回等）。在此基础上一种很好的优化算法逐步发展起来。 蚁群算法的特点是模拟自然界中蚂蚁的群体行为。科学家发现，蚁群总是能够发现从蚁巢到食物源的最短路径。经研究发现，蚂蚁在行走过的路上留下一种挥发性的激素，蚂蚁就是通过这种激素进行信息交流。蚂蚁趋向于走激素积累较多的路径。找到最短路径的蚂蚁总是最早返回巢穴，从而在路上留下了较多的激素。由于最短路径上积累了较多的激素，选择这条路径的蚂蚁就会越来越多，到最后所有的蚂蚁都会趋向于选择这条最短路径。基于蚂蚁这种行为而提出的蚁群算法具有群体合作，正反馈选择，并行计算等三大特点，并且可以根据需要为人工蚁加入前瞻、回溯等自然蚁所没有的特点。 在使用蚁群算法求解现实问题时，先生成具有一定数量蚂蚁的蚁群，让每一只蚂蚁建立一个解或解的一部分，每只人工蚁从问题的初始状态出发，根据“激素”浓度来选择下一个要转移到的状态，直到建立起一个解，每只蚂蚁根据所找到的解的好坏程度在所经过的状态上释放与解的质量成正比例的“激素”。之后，每只蚂蚁又开始新的求解过程，直到寻找到满意解。为避免停滞现象，引入了激素更新机制。 3.2 解决TSP问题的蚁群算法描述 现以TSP问题的求解为例说明蚁群系统模型。首先引进如下记号：n为城市的个数；m为蚁群中蚂蚁的数量；dij为两城市i和j之间距离；bi(t)为t时刻位于城市i的蚂蚁的个数，m? ?b(t)；?ii?1nij(t)为t时刻边弧(i,j)的轨迹强度（即ij连线上残留的 i,j?1,2,?,n，i?j；信息量），且设?ij(0)?c（c为常数），?ij(t)为t时刻边弧(i,j)的能见度，反映由城市i转移到城市j的期望程度。 根据上述原理，蚂蚁k(k?1,2,?,m)在运动过程中根据各条路径上的信息量决定 转移方向。与真实蚁群系统不同，人工蚁群系统具有一定的记忆功能。随着时间的推移，以前留下的信息逐渐消逝，经n个时刻，蚂蚁完成一次循环，各路径上信息量要作调整。 -277- 由此得到下述的人工蚁群系统模型： 1）设人工蚁群在并行地搜索TSP的解，并通过一种信息素做媒介相互通信，在每个结点上且和该结点相连的边上以信息素量做搜索下一结点的试探依据，直到找到一个TSP问题的可行解。 2）在时刻t人工蚁k由位置i转移至位置j的转移概率为 ????ij(t)?ij(t)????(t)??(t) , j?S kpij(t)???iv （3） ivv?S?? j?S?0, 其中参数?为轨迹的相对重要性（??0）；?为能见度的相对重要性（??0）；S为可行点集，即蚂蚁k下一步允许选择的城市。?,?分别反映了蚂蚁在运动过程中所积 累的信息及启发式因子在蚂蚁选择路径中所起的不同作用。 3）当m个人工蚁按（3）式找到了可行解，则将各边的信息量用下式修改。即调整信息量的轨迹强度更新方程为 ?ij(t?1)???ij(t)???ij，??(0,1) （4） k ??ij????ijk?1mk其中??ij为第k只蚂蚁在本次循环中留在路径(i,j)上的信息量；??ij为本次循环中路 径(i,j)上的信息量的增量；参数?为轨迹的持久性；1??为轨迹衰减度，表示信息消逝程度。 对上述系统模型，采用人工蚁群方法求解的算法步骤可归结为： step 1：NC?0（NC为迭代步数或搜索次数）；各?ij和??ij的初始化；将m个蚂蚁置于n个顶点上。 step 2：将各蚂蚁的初始出发点置于当前解集中；对每个蚂蚁k（k?1,2,?,m） k按概率pij转移至下一顶点j；将顶点j置于当前解集。 step 3：计算各蚂蚁的目标函数值zk(k?1,?,m)，记录当前的最好解。 step 4：按更新方程修改轨迹强度。 step 5：NC?NC?1，若NC?预定的迭代次数且无退化行为（即找到的都是相同解），则转step 2。 若为了简化计算，增加处理较大规模的TSP问题的能力，则可将（4）式修改为： ?ij(t?1)???ij(t)?(1??)??ij，??(0,1) 其中 ?1?d,(i,j)?BEk??ij??ij ?0, 其它?此处BE为本次最优路线上的边集。 3.3 人工蚁群算法性能的讨论 人工蚁群算法是一种基于种群的进化算法。作为一个新兴的研究领域，虽它还远未像GA、SA等算法那样形成系统的分析方法和坚实的数学基础，但目前已有一些基 -278- 本结果。 在M. Dorigo 三种不同的模型中，循环路径(i,j)上信息量的增量??ij不同。 1）Ant-quantity system 模型中， ?Q?d,若第k只蚂蚁在时刻t和t?1之间经过ijk??ij??ij ?0, 其它?2）在Ant-density system 模型中， t和t?1之间经过ij?Q,若第k只蚂蚁在时刻 ????其它?0, kij3）在Ant-cycle system 模型中， ?Q过ij?,若第k只蚂蚁在本次循环中经k ??ij??Lk?0, 其它?其中Q是反映蚂蚁所留轨迹数量的常数，Lk表示第k只蚂蚁在本次循环中所走路径的 kk长度；且t?0时，?ij(0)?c，??ij、2）利用的是局部信息，模?0。算法中模型1） 型3）利用的是整体信息。 人工蚁群算法中，?,?,Q等参数对算法性能也有很大的影响。?值的大小表明留在每个结点上的信息量受重视的程度，?值越大，蚂蚁选择以前选过的点的可能性越大，但过大会使搜索过早陷于局部极小点；?的大小表明启发式信息受重视的程度；Q值会影响算法的收敛速度，Q过大会使算法收敛于局部极小值，过小又会影响算法的收敛速度，随问题规模的增大Q的值也需要随之变化；蚂蚁的数目越多，算法的全局搜索能力越强，但数目加大将使算法的收敛速度减慢。 -279-