%蚂蚁算法test  

%用产生的一个圆上的十个点来检验蚂蚁算法

 

clc

clear

 

%参数

alpha = 1 ;                               %信息素指数

beta = 5  ;                                %启发指数

rho = 0.5 ;                                %挥发系数 

n = 16 ;                                   %城市个数

k = 20 ;                                    %迭代次数

m = n - 1 ;                                %蚂蚁只数，这里取比城市数目少一的蚂蚁只数

Q = 100 ;

bestr = inf ;

%产生一个圆上的十个点

x = zeros(1,n) ;

y = x ;

for i = 1 : (n/2)                          

    x(i) = rand * 20 ;

    y(i) = sqrt(100 - (x(i) - 10) ^ 2) + 10;

end

for i = (n/2 + 1) : n

    x(i) = rand * 20 ;

    y(i) = - sqrt(100 - (x(i) - 10) ^ 2) + 10;

end

plot(x,y,‘.‘) ;

%计算距离

d = zeros(n,n) ;

for i = 1 : n 

    for j = 1 : n

        d(i,j) = sqrt( ( x(i) - x(j) ) ^ 2 + ( y(i) - y(j) ) ^ 2) ;

    end

end

temp = min(d) ;

dmin = temp(1) ;

tau = ones(n,n) ;

%tau = tau ./ (n * dmin) ;                   %初始化tau信息素矩阵

 

%开始迭代

for i = 1 : k   

    %初始化

    visited = zeros(m,n) ;                  %用visited 来储存所有蚂蚁走过的城市 m×n 其中未到达的城市为0

    visited(:,1) = (randperm(n,m))‘;        %将m只蚂蚁随机放在n座城市 即产生一列1到n的随机数进行第一列数据的更新

    for b = 2 : n                           %所有蚂蚁都走到第b个城市时

        current = visited(:,(b-1)) ;         %所有蚂蚁现在所在城市 m×1

        allow = zeros(m,(n - b + 1)) ; 

        

        for a = 1 : m

            j = 1 ;

            for s = 1 : n

                if length(find(visited(a,:) == s)) == 0

                   allow(a,j) = s ;

                   j = j + 1 ;

                end

            end

        end

        

        l = n-b+1 ;

        for a = 1 : m                       %分析第a只蚂蚁

            p = zeros(1,l) ;

            for j = 1 : l                   %根据下式来选择下一个城市

                p(j) = ( ( tau( current(a,1) , allow(a,j) ) ) ^ alpha ) * ( ( 1 / d( current(a,1) , allow(a,j) ) ) ^ beta ) ;

            end

            p = p ./ sum(p) ;               %采用轮盘赌的方式

            p = cumsum(p) ;

            pick = rand ;

            for c = 1 : l

                if pick < p(c)

                    visited(a,b) = allow(a,c) ;          %找到符合要求的城市 并 记入蚂蚁a的路径中

                    break ;

                end

            end

        end

    end

    %计算每只蚂蚁所走的路径总长

    L = zeros(1,m) ;

    for a = 1 : m

        t = d(visited(a,n),visited(a,1)) ;

        for b = 1 : (n - 1)

            t = t + d(visited(a,b),visited(a,(b + 1)));

        end

        L(a) = t ;

    end

    [newbestr,newbestant] = min(L) ;          %寻本次迭代最短路径及其相应蚂蚁

    if newbestr < bestr                       %到目前为止最优值的保存

        bestr = newbestr ;

        bestroad = visited(newbestant,:) ;

    end

    %离线更新信息素矩阵

    %挥发

    for a = 1 : m

        tau(visited(a,n),visited(a,1)) = tau(visited(a,n),visited(a,1)) * (1 - rho) ;

        for b = 1 : (n - 1)

            tau(visited(a,b),visited(a,(b + 1))) = tau(visited(a,b),visited(a,(b + 1))) * (1 - rho) ;

        end

    end

    %加强

    tau(visited(newbestant,n),visited(newbestant,1)) = tau(visited(newbestant,n),visited(newbestant,1)) + Q / L(newbestant) ;

    for b = 1 : (n - 1)

        tau(visited(newbestant,b),visited(newbestant,(b + 1))) = tau(visited(newbestant,b),visited(newbestant,(b + 1))) + Q / L(newbestant) ;

    end

end

bestr 

bestx = zeros(1,n) ;

besty = zeros(1,n) ;

for i = 1 : n

    bestx(i) = x(bestroad(i)) ;

    besty(i) = y(bestroad(i)) ;

end

bestx = [bestx,bestx(1)] ;

besty = [besty,besty(1)] ;

plot(bestx,besty,‘-‘) ;