1.一种基于改进蚁群算法的最短路径规划方法,其特征在于,基于MATLAB软件,运用改进的蚁群算法求解具体的TSP问题实现方式如下:一、数据初始化,包括以下步骤:
a、建立随机直角坐标系,导入n个城市的坐标值;
b、计算任意两个城市之间的距离,得到距离矩阵D,从而得到启发信息初始矩阵Heu_F=1./D;
c、初始化种群参数,设距离启发参数β∈[0,5]非均匀,向5聚集;信息素启发参数α∈[0,3]对给定的β为均匀分布,信息素挥发因子vol=0.1,设定循环所用蚂蚁次数为N_ants,N_ants的选取由问题规模n而定,一般取m∈[0.3n,0.7n];最大迭代次数为N_iter;
d、计算信息素初始值,通过计算各个城市a和b之间的距离Dab,比较到两城市之间的最短距离Dmin,其中Dmin=min{Dab},则信息素初始值为Q0=1/(n*Dmin),从而信息素初始矩阵P=Q0*ones(n,n);
e、准备内存表,分别用Tau=zeros(n,n)、Route_best=zeros(n,1)、Length_best=zeros(N_iter,1)和Length_avg=zeros(N_iter,1)来表示信息素基质、最佳TSP轨迹、最佳TSP长度和平均TSP长度;二、主循环部分,包括以下步骤:步骤A、N_ants=30只蚂蚁初始位置的确定及禁忌表的更新,优化蚂蚁们的α,β的参数分布;包括以下内容:beta=5*rand(N_ants,1).^0.6;
alpha=3-rand(N_ants,1).*min(3,2+beta/3);
开始前,按公式RL=round(rand(M,1)*n+0,5),将m只蚂蚁随机地放在n个城市上,利用has_visited=Table(i,1:(j-1))记录已访问城市,避免重复访问;
步骤B、路径搜索,包括以下步骤:
f、循环次数Nc=Nc+1;
g、起始的m只蚂蚁分别按照轮盘赌的规则移动到下一个城市,之后更新禁忌表;
h、获得信息素矩阵tau,并给其加入一个本底值0.01;
i、生成TSP轨迹;
j、分别计算m只蚂蚁走出的m条路径的长度,比较并保存最短路径L的长度及其遍历顺序;
k、果本轮迭代的第一名表现劣于目前发现的最优TSP路径时,最优TSP路径将作为一只蚂蚁排第一,其它蚂蚁名次顺延;
l、给已知信息素tau赋予排名因子,全局更新信息素矩阵;
m、判断Nc与Ncmax之间的关系,如果Ncmax>Nc,则循环结束,否则,清空禁忌表并返回到步骤f,算法继续循环执行;
三、算法的输出,包括以下内容:
输出程序结束时当前最短距离与全局最优路线图;
输出全局最优解随迭代次数变化的示意图。