距离判断矩阵.docx

由于蚁群算法的特殊性，在求解问题时往往需要消耗较多的时间，若不对具体问题进行细致的算法优化，会导致算法效率低下，运行时间极长，甚至会跌入死循环导致求解失败。为此，本文提出以下算法优化策略，降低运行时间提升算法效率。距离判断矩阵distance算法会首先计算各点间的间距,distance(i,j)即表示从i点到j点的距离。而由于数据集中点数繁多，若在每个位置对每点进行遍历则会导致算法复杂性大幅增加。引入j_distance矩阵。根据题目给出的kesi(0.001)与theta(数据集一30,数据集二20),若从i点到j点的距离大于theta/kesi则令LdiStanCe(i,j)为0,即表示无论前置误差情况如何，从i点都无法到达j点，在后续遍历中仅需检索j_distance非0的点作为允许点的预选。相关matIb代码如下：fori=1:nnforj=i:nndistance(i,j)=sqrt(point(i,l)-point(j,1)2+(point(i,2)-point(j,2)2+(point(i,3)-point(j,3)2);j_distance(i,j)=distance(i,j);ifdistance(i,j)>(theta/kesi)jdistance(i,j)=0;enddistance(j,i)=distance(i,j);j_distance(j,i)=j_distance(i,j);endendj_distance(:,1)=0;信息素损失策略在TSP问题中由于求解目的即为遍历所有点，不存在无效路径的情况。故不存在除迭代外针对信息素减小的操作。而针对本体问题，每只蚂蚁都存在走入“死胡同”的问题，即在当前点时，由于此时具有一定的水平/垂直误差，而当前点可到达的下一个点均不能满足对消除误差的要求，此时该蚂蚁所走路径即为无效路径。算法中，若不对无效路径进行处理，则会导致每只蚂蚁都有概率步入无效路径消耗解算时间，故引入信息素损失策略，若判断得到当前蚂蚁以“无路可走”，则对当前蚂蚁最后一步路径上的信息素进行减小，从而达到减小后续蚂蚁重蹈覆辙的概率。相关代码如下：ifstep>1Q(path_table(ant,step-1),path_table(ant,step)=O,99*Q(path_table(ant,step-1),path_table(ant,step);end迭代优化策略在每次迭代得到多条路径时，原生的蚁群算法将通过每条路径的长度为每条路径分配不同的信息素，路径短则信息素多，借此达到每次迭代朝向更短路径的目的，本文由于在算法中直接计算了每条路径的长度，为了加快算法的收敛速度，每次迭代将只对前IO条最短路径进行信息素增加操作，增大下次迭代时蚂蚁选择最短路径的概率，极大加快算法收敛速度。相关代码如下：path_long_temp,path_index=sort(path_long);temp2=find(pathtabIe(pathindex(i),:)=0);forj=1:temp2(l)-2Q(path_table(path_index(i),j),path_table(path_index(i),j+l)=Q(Path_table(Path_index，j),path_table(path_index(i),j+l)+Q_ant/path_long(i);end