蚁群算法解决ATT48问题(matlab)

[复制链接]

字体大小: 正常放大

fantimond

1 主题	3 听众	5 积分

升级 0%

该用户从未签到

电梯直达

1^#

发表于 2009-5-25 16:01 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

function [bestr, phe, rlength] = ACO(city, varargin)       %(city, Niteration, use prebuilt pheromone, batch mode)
tic
%load att48.txt city;

global NC distan phe a b

NC = size(city, 1);          % 城市个数
distan = zeros(NC);          % store the distance between citys
bestr = logical(zeros(1, NC));       % 用来记录最优路径

if nargin >= 2
M = varargin{1};
else
M = 1;    % 最大循环次数
end

if nargin >= 3
phe = varargin{2};
rlength = inf;
else
phe = ones(NC, NC); % 初始时刻各边上的信息量为1
rlength = inf;       % 用来记录当前找到的最优路径长度
end
evap = 0.2;       % 挥发系数 0.2 ?
a = 1;       % a = 1 ?
b = 2;
Q = 33000;          % length is 33062
Qt = 1000;
ants = 20;       % 蚂蚁数量

for i = 1: NC    % 计算各城市间的距离
for j = 1: NC
      distan(i, j) = sqrt((city(i, 2) - city(j, 2)) ^2 + (city(i, 3) - city(j, 3)) ^2);
end
end

for ite = 1 : M
for k = 1 : ants    %考查第K只蚂蚁
      nphe = zeros(NC, NC);       % 第K只蚂蚁移动前各边上的信息增量为零
      [routek, lengthk] = travel();
      if lengthk < rlength          % 找到一条更好的路径
         rlength = lengthk;
         bestr = routek;
      end
      for i = 1 : NC - 1    % 第K只蚂蚁在路径上释放的信息量
         nphe(routek(i), routek(i + 1)) = nphe(routek(i), routek(i + 1)) + (exp(Qt / (lengthk - Q))) * 0.4 / ants;       %%%
      end
      nphe(routek(NC), 1) = nphe(routek(NC), 1) + (exp(Qt / (lengthk - Q))) * 0.4 / ants;          %%%
end
for i = 1 : NC - 1
      for j = i + 1 : NC
         if nphe(i, j) == 0
            nphe(i, j) = nphe(j, i);
         end
      end
end
phe = (1 - evap) .* phe + nphe;
end

rlength
if nargin < 4
toc
end

%%% travel
function [tabuk, val] = travel() % 某只蚂蚁找到的某条路径

global NC distan phe a b cp

p = fix(NC * rand) + 1;
val = 0;       % 初始路径长度设为 0
isin = logical(zeros(1, NC));       % mark visited city
tabuk = int8(zeros(1, NC));       % used to store the route

tabuk(1) = p; % 该蚂蚁都从第 p 个城市出发的
isin(p) = true;
n = 1;

for i = 1 : NC - 1
cp = zeros(1, NC);    % 转移概率
np = tabuk(n);       % 蚂蚁当前所在的城市号
p_sum = 0;       % to calc pheromone sum
for j = 1 : NC
      if isin(j) ~= true
         ada=1 / distan(np, j);
         cp(j) = phe(np, j) ^ a * ada ^ b;
         p_sum = p_sum + cp(j);
      end
end
cp = cp ./ p_sum;

NextCity = pchoice();
n = n + 1;
isin(NextCity) = true;
tabuk(n) = NextCity;
val = val + distan(np, NextCity);
end
val = val + distan(tabuk(1), tabuk(NC));

%%% pchoice
function NextCity = pchoice()       % choose the next city

global NC cp

tempR = rand(1, NC);
R2 = rand + 0.5;
tempR = (tempR + R2) .* cp;
[t2, NextCity] = max(tempR);

注：各种参数，包括信息量的增加等应该怎么弄，有规则吗？我这个程序只能达到3.54, 而最优的都3.3呢。

zan