蚁群算法解决TSP问题MATLAB程序

压缩包内含有蚁群算法解决TSP问题的MATLAB源程序，代码有详细注释，还有一个TXT文档，文档中包含全国近60个城市的地理坐标，前34个为直辖市，省会及港澳城市，下载解压后直接用MATLAB运行即可

%====================================
%蚁群算法求解TSP问题
%====================================
clc
clear all;
close all;
%初始化蚁群
fid=fopen（‘Cities.txt‘‘rt‘）;
C=fscanf（fid‘%g‘[234]）;%读取城市的坐标矩阵
fclose（fid）;
C=C‘;%城市坐标采用n*2的矩阵存储
Nc_max=1500;%最大迭代次数
alpha=1;%蚂蚁在运动过程中所积累信息（即信息素）在蚂蚁选择路径时的相对重要程度，alpha过大时，算法迭代到一定代数后将出现停滞现象
beta=5;%启发式因子在蚂蚁选择路径时的相对重要程度
rho=0.5;%0Q=100;%蚂蚁释放的信息素量，对本算法的性能影响不大

%变量初始化
n=size（C1）;%表示TSP问题的规模，亦即城市的数量
m=n;%蚁群中蚂蚁的数量，当m接近或等于城市个数n时，本算法可以在最少的迭代次数内找到最优解
D=ones（nn）;%表示城市完全地图的赋权邻接矩阵，记录城市之间的距离

for i=1:n
    for j=1:n
        if i            D（ij）=sqrt（（C（i1）-C（j1））^2+（C（i2）-C（j2））^2）;
        end
    D（ji）=D（ij）;
    end
end
eta=1./D;%启发式因子，这里设为城市之间距离的倒数
pheromone=ones（nn）;%信息素矩阵这里假设任何两个城市之间路径上的初始信息素都为1
tabu_list=zeros（mn）;%禁忌表，记录蚂蚁已经走过的城市，蚂蚁在本次循环中不能再经过这些城市。当本次循环结束后，禁忌表被用来计算蚂蚁当前所建立的解决方案，即经过的路径和路径的长度
Nc=0;%循环次数计数器
repeat_num=0;%迭代终止参数，当最短路径重复重复次数，当达此条件时停止迭代
routh_best=zeros（Nc_maxn）;%各次循环的最短路径
length_best=ones（Nc_max1）;%各次循环最短路径的长度
length_average=ones（Nc_max1）;%各次循环所有路径的平均长度
tic
while Nc    %将m只蚂蚁放在n个城市上
    rand_position=[];
    for i=1:ceil（m/n）
        rand_position=[rand_positionrandperm（n）];
    end
    tabu_list（:1）=（rand_position（1:m））‘;%将蚂蚁放在城市上之后的禁忌表，第i行表示第i只蚂蚁，第i行第一列元素表示第i只蚂蚁所在的初始城市
    %m只蚂蚁按概率函数选择下一座城市，在本次循环中完成各自的周游
    for j=2:n
        for i=1:m
            city_visited=tabu_list（i1:（j-1））;%已访问的城市
            city_remained=zeros（1（n-j+1））;%待访问的城市
            probability=city_remained;%待访问城市的访问概率
            cr=1;
            for k=1:n%for循环用于求待访问的城市。比如如果城市个数是5，而已访问的城市city_visited=[2 4]则经过此for循环后city_remanied=[1 3 5]
                if isempty（find（city_visited==k））
                    city_remained（cr）=k;
                    cr=cr+1;
                end
            end
            %状态转移规则****************************************
            q0=0.5;
            if rand>q0
                for k=1:length（city_remained）
                    probability（k）=（pheromone（city_visited（end）city_remained（k）））^alpha*（eta（city_visited（end）city_remained（k）））^beta;
                end
                path=find（probability==max（probability））;
                to_visit=city_remained（path（1））;
            else
                for k=1:length（city_remained）
                    probability（k）=（pheromone（city_visited（end）city_remained（k）））^alpha*（eta（city_visited（end）city_remained（k）））^beta;
                end
                probability=probability/sum（probability）;
                pcum=cumsum（probability）;
                select=find（pcum>=rand）;
                to_visit=city_remained（select（1））;
            end
            tabu_list（ij）=to_visit;
            %**************************************************************
        end
    end
    if Nc>0
        tabu_list（1:）=routh_best（Nc:）;%将上一代的最优路径（最优解）保留下来，保证上一代中的最适应个体的信息不会丢失
    end
    %记录本次循环的最佳路线
    tot

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        931  2012-12-11 16:29  Cities.txt

     文件       6481  2012-12-11 16:42  ACA_TSP.m

----------- ---------  ---------- -----  ----

                 7412                    2