用蚁群算法求解TSP问题的matlab程序

自己在做基于蚂蚁算法的移动机器人路径规划,先写了一个用蚂蚁算法求解TSP问题的MATLAB程序,给大家分享下.(可以用TSP问题标准测试数据来测试)

%蚁群算法求解TSP问题的matlab程序
clear all
close all
clc

%初始化蚁群
m=31;%蚁群中蚂蚁的数量，当m接近或等于城市个数n时，本算法可以在最少的迭代次数内找到最优解
C=[1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;3238 1229;4196 1004;
   4312 790;4386 570;3007 1970;2562 1756;2788 1491;2381 1676;1332 695;3715 1678;
   3918 2179;4061 2370;3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2367;
   3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;2370 2975];%城市的坐标矩阵
Nc_max=200;%最大循环次数，即算法迭代的次数，亦即蚂蚁出动的拨数（每拨蚂蚁的数量当然都是m）
alpha=1;%蚂蚁在运动过程中所积累信息（即信息素）在蚂蚁选择路径时的相对重要程度，alpha过大时，算法迭代到一定代数后将出现停滞现象
beta=5;%启发式因子在蚂蚁选择路径时的相对重要程度
rho=0.5;%0Q=100;%蚂蚁释放的信息素量，对本算法的性能影响不大

%变量初始化
n=size（C1）;%表示TSP问题的规模，亦即城市的数量
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;%循环次数计数器
routh_best=zeros（Nc_maxn）;%各次循环的最短路径
length_best=ones（Nc_max1）;%各次循环最短路径的长度
length_average=ones（Nc_max1）;%各次循环所有路径的平均长度

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 length（find（city_visited==k））==0
                    city_remained（cr）=k;
                    cr=cr+1;
                end
            end
            %for循环计算待访问城市的访问概率分布，此概率和两个参数有关，一是蚂蚁当前所在城市（即city_visited（end））和待访问城市（即city_remained（k））路径上的信息素，一是这两者之间的启发因子即距离的倒数            
            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））;
            tabu_list（ij）=to_visit;
        end
    end
    if Nc>0
        tabu_list（1:）=routh_best（Nc:）;%将上一代的最优路径（最优解）保留下来，保证上一代中的最适应个体的信息不会丢失
    end
    %记录本次循环的最佳路线
    total_length=zeros（m1）;%m只蚂蚁在本次循环中分别所走过的路径长度
    for i=1:m
        r=tabu_list（i:）;%取出第i只蚂蚁在本次循环中所走的路径
        for j=1:（n-1）
            total_length（i）=total_length（i）+D（r（j）r（j+1））;%第i只蚂蚁本次循环中从起点城市到终点城市所走过的路径长度
        end

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

     文件       5947  2008-05-14 08:44  ant_colony.m

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

                 5947                    1