查看: 892|回复: 7|关注: 0

[已解决] MATLAB TSP问题

[复制链接]

新手

8 麦片

财富积分


050


2

主题

10

帖子

0

最佳答案
我属于matlab小白,最近在尝试做一个matlab  TSP问题

下面的矩阵展示了不同城市之间的距离,城市到自身的距离为0,现要求从Hong Kong出发,找一条最短的旅游顺序,使得游览所有城市后回到Hong Kong。
% distance from a city to others
Amsterdam    = [0    2.2  18.1 4.8  9.2  8.4  5.2  0.4  9.3  11.3 10.2 0.4  10.4]; %1
Athens       = [2.2  0    17.5 2.8  7.9  6.6  3.3  1.8  8.5  9.8  8.7  2.4  9.6];  %2
Auckland     = [18.1 17.5 0    14.7 9.6  10.9 14.2 18.2 9.1  7.6  8.7  18.3 8.0];  %3
Bahrain      = [4.8  2.8  14.7 0    5.4  3.8  0.5  4.4  6.4  7.0  6.0  5.1  7.4];  %4
Bangkok      = [9.2  7.9  9.6  5.4  0    2.4  4.9  9.0  1.7  2.3  1.2  9.5  2.2];  %5
Colombo      = [8.4  6.6  10.9 3.8  2.4  0    3.3  8.1  4.1  3.3  2.5  8.7  4.6];  %6
Dubai        = [5.2  3.3  14.2 0.5  4.9  3.3  0    4.8  6.0  6.6  5.5  5.5  6.9];  %7
Frankflurt   = [0.4  1.8  18.2 4.4  9.0  8.1  4.8  0    9.2  11.1 10.0 0.6  10.3]; %8
HK           = [9.3  8.5  9.1  6.4  1.7  4.1  6.0  9.2  0    3.3  2.5  9.6  1.1];  %9
Jakarta      = [11.3 9.8  7.6  7.0  2.3  3.3  6.6  11.1 3.3  0    1.2  11.7 2.8];  %10
KualaLumpur  = [10.2 8.7  8.7  6.0  1.2  2.5  5.5  10.0 2.5  1.2  0    10.5 2.5];  %11
London       = [0.4  2.4  18.3 5.1  9.5  8.7  5.5  0.6  9.6  11.7 10.5 0    10.7]; %12
Manila       = [10.4 9.6  8.0  7.4  2.2  4.6  6.9  10.3 1.1  2.8  2.5  10.7 0];    %13

我对其城市进行了1-13的编号,用randperm随机生成矩阵后,我想写一个函数,对其计算总的路程,但是我不太会写。。。
求大神帮帮我


入门

68 麦片

财富积分


50500


0

主题

52

帖子

4

最佳答案
发表于 2019-8-6 11:40:51 | 显示全部楼层
%这是我写的蚁群算法解决tsp问题可以参考一下
clear all
clc
Alpha = 1;
Beta = 5;
C=[
    565.0   575.0;
    25.0    185.0;
    345.0   750.0;
    945.0   685.0;
    845.0   655.0;
    880.0   660.0;
    25.0    230.0;
    525.0   1000.0;
    580.0   1175.0;
    650.0   1130.0;
    1605.0  620.0;
    1220.0  580.0;
    1465.0  200.0;
    1530.0  5.0;
    845.0   680.0;
    725.0   370.0;
    145.0   665.0;
    415.0   635.0;
    510.0   875.0;
    560.0   365.0;
    300.0   465.0;
    520.0   585.0;
    480.0   415.0;
    835.0   625.0;
    975.0   580.0;
    1215.0  245.0;
    1320.0  315.0;
    1250.0  400.0;
    60.0   180.0;
    410.0   250.0;
    420.0   555.0;
    575.0   665.0;
    1150.0  1160.0;
    700.0   580.0;
    685.0   595.0;
    685.0   610.0;
    770.0   610.0;
    795.0   645.0;
    720.0   635.0;
    760.0   650.0;
    475.0   960.0;
    95.0   260.0;
    875.0   920.0;
    700.0   500.0;
    555.0   815.0;
    830.0   485.0;
    1170.0    65.0;
    830.0   610.0;
    605.0   625.0;
    595.0   360.0;
    1340.0   725.0;
    1740.0   245.0;
    ];
city_len = length(C);
Tau = ones(city_len,city_len);%信息素矩阵
D = zeros(city_len,city_len,'double');
antnum = 50;
Q = 100;%信息素的增强强度
tic
for i = 1:city_len
    D(i,i) = eps('double');
    D(i,i+1:city_len) = sqrt((C(i,1)-C(i+1:city_len,1)).^2+(C(i,2) - C(i+1:city_len,2)).^2);
    D(i+1:city_len,i) = D(i,i+1:city_len);
end
Eta = 1./D;
Maxiter = 180;
iter = 1;
antpop(antnum,city_len) = 0;
waitcity = meshgrid(1:city_len,1:antnum);
Rho = 0.1;%信息素的蒸发系数


while iter <= Maxiter
   antpop = zeros(antnum,city_len);%假定每只蚂蚁放的城市各不相同
    %第一步随机将m只蚂蚁放到n个城市
    antpop(:,1) = (propos(antnum))';
    waitcity = meshgrid(1:city_len,1:antnum);
    for i = 2:city_len
        visited = antpop(:,i-1);
        waitcity_probability = zeros(antnum,city_len-i+1);
        logical_matrix = (bsxfun(@eq,waitcity,visited(:)));
        waitcity = waitcity';
        waitcity = (reshape(waitcity(~logical_matrix'),city_len-i+1,antnum))';
        for j = 1:city_len-i+1
            varnum = (visited(:)-1).*city_len+waitcity(1:antnum,j);%元素的位置
            waitcity_probability(:,j) = (Tau(varnum).^Alpha).*(Eta(varnum).^Beta);
        end
        waitcity_probability = bsxfun(@rdivide,waitcity_probability,sum(waitcity_probability,2));
        waitcity_probability = cumsum(waitcity_probability,2);
        ant_randnum  = rand(1,antnum);
        all_pos = bsxfun(@ge,waitcity_probability,ant_randnum(:));
        all_pos = sum(cumsum(all_pos,2) == 0,2)+1;%找到逻辑矩阵中第一个不为零的元素的位置
        antpop(:,i) = waitcity((all_pos-1).*antnum+(1:antnum)');%矩阵中的元素是按列进行索引的
    end
    %  %更新信息素增量还有记录本次迭代完成之后的最佳路线
    infor_matrix = zeros(city_len,city_len);
   
    all_distance = zeros(1,antnum,'double');
    for i = 1:antnum
        for j = 1:city_len-1
            all_distance(i) = all_distance(i)+sqrt((C(antpop(i,j),1)-C(antpop(i,j+1),1))^2 + (C(antpop(i,j),2)-C(antpop(i,j+1),2))^2);
        end
        for j = 1:city_len-1
            infor_matrix(antpop(i,j),antpop(i,j+1)) = infor_matrix(antpop(i,j),antpop(i,j+1)) +  Q/all_distance(i);
            infor_matrix(antpop(i,1),antpop(i,antnum)) = infor_matrix(antpop(i,1),antpop(i,antnum)) + Q/all_distance(i);
        end
    end
    Tau = (1-Rho).*Tau + infor_matrix;
    [lia,loc] = min(all_distance);%迭代之后的最佳路线及其路线名
    %求所有路线的平均值
    mean_distance = mean(all_distance);
    iter = iter + 1;
end
lia;
antpop(loc,:);



   
     
      
      


   
   



新手

8 麦片

财富积分


050


2

主题

10

帖子

0

最佳答案
 楼主| 发表于 2019-8-6 13:38:17 | 显示全部楼层
breezy_gkpm4 发表于 2019-8-6 11:40
%这是我写的蚁群算法解决tsp问题可以参考一下
clear all
clc

非常感谢!但是我想知道,我已经有城市之间的距离矩阵了,怎么求总路程呢。
例如[1 2 8 5 4]  距离应该按照 D(1,2)+D(2,8)+D(8,5)+D(5,4)+D(4,1)这个函数咋编呀

论坛优秀回答者

权威

3882 麦片

财富积分



3

主题

4109

帖子

864

最佳答案
  • 关注者: 183
发表于 2019-8-6 15:18:23 | 显示全部楼层 |此回复为最佳答案
本帖最后由 maple1314168 于 2019-8-6 15:23 编辑
王久久 发表于 2019-8-6 13:38
非常感谢!但是我想知道,我已经有城市之间的距离矩阵了,怎么求总路程呢。
例如[1 2 8 5 4]  距离应该按 ...
  1. n=10;%十个城市。
  2. A=rand(n,2);dis=squareform(pdist(A));%构造距离
  3. ind1=randperm(n);ind1=[ind1 ind1(1)];%随机一闭合路径。
  4. ind2=sub2ind([n n],ind1(1:n),ind1(2:n+1));
  5. len=sum(dis(ind2));
复制代码

新手

8 麦片

财富积分


050


2

主题

10

帖子

0

最佳答案
 楼主| 发表于 2019-8-6 15:52:12 | 显示全部楼层

非常感谢
ind2=sub2ind([n n],ind1(1:n),ind1(2:n+1))  这一行是什么意思呀

入门

68 麦片

财富积分


50500


0

主题

52

帖子

4

最佳答案
发表于 2019-8-6 16:33:26 | 显示全部楼层
王久久 发表于 2019-8-6 15:52
非常感谢
ind2=sub2ind([n n],ind1(1:n),ind1(2:n+1))  这一行是什么意思呀

如果想索引矩阵的 1行13列元素,本来是a(1,13) 可以改为a(sub2ind([1 15],1,13)) 假设矩阵只有1行 15列
里面的值是13也就是查找矩阵的第13个元素;
我写的这个算法很优化,你可以好好看看

新手

8 麦片

财富积分


050


2

主题

10

帖子

0

最佳答案
 楼主| 发表于 2019-8-6 21:32:08 | 显示全部楼层
breezy_gkpm4 发表于 2019-8-6 16:33
如果想索引矩阵的 1行13列元素,本来是a(1,13) 可以改为a(sub2ind([1 15],1,13)) 假设矩阵只有1行 15列 ...

我都不太好意思问你了  但是我自己还是搞不太明白
popu = 50;%初始种群大小   
CityNum = 13;%城市数量
dis = [0 2.2 18.1 4.8 9.2 8.4 5.2 0.4 9.3 11.3 10.2 0.4 10.4;
    2.2 0 17.5 2.8 7.9 6.6 3.3 1.8 8.5 9.8 8.7 2.4 9.6;
    18.1 17.5 0 14.7 9.6 10.9 14.2 18.2 9.1 7.6 8.7 18.3 8.0;
    4.8 2.8 14.7 0 5.4 3.8 0.5 4.4 6.4 7.0 6.0  5.1  7.4;
    9.2  7.9  9.6  5.4  0    2.4  4.9  9.0  1.7  2.3  1.2  9.5  2.2;
    8.4  6.6  10.9 3.8  2.4  0    3.3  8.1  4.1  3.3  2.5  8.7  4.6;
    5.2  3.3  14.2 0.5  4.9  3.3  0    4.8  6.0  6.6  5.5  5.5  6.9;
    0.4  1.8  18.2 4.4  9.0  8.1  4.8  0    9.2  11.1 10.0 0.6  10.3;
    9.3  8.5  9.1  6.4  1.7  4.1  6.0  9.2  0    3.3  2.5  9.6  1.1;
    11.3 9.8  7.6  7.0  2.3  3.3  6.6  11.1 3.3  0    1.2  11.7 2.8;
    10.2 8.7  8.7  6.0  1.2  2.5  5.5  10.0 2.5  1.2  0    10.5 2.5;
    0.4  2.4  18.3 5.1  9.5  8.7  5.5  0.6  9.6  11.7 10.5 0    10.7;
    10.4 9.6  8.0  7.4  2.2  4.6  6.9  10.3 1.1  2.8  2.5  10.7 0];%距离矩阵
popm=zeros(popu,CityNum);
for i=1:popu
popm(i,:)=randperm(CityNum)%生成初始群体
end
ind2=sub2ind([CityNum CityNum],popm(1:CityNum),popm(2:CityNum+1));
len=sum(dis(ind2))

%%我想对生成的50×13的初始群体的矩阵,每一列都进行距离的运算  但是我这么输入好像是错误的,最后len只输出一个结果 咋弄呀

入门

68 麦片

财富积分


50500


0

主题

52

帖子

4

最佳答案
发表于 2019-8-6 22:29:03 | 显示全部楼层
本帖最后由 breezy_gkpm4 于 2019-8-7 15:41 编辑
王久久 发表于 2019-8-6 21:32
我都不太好意思问你了  但是我自己还是搞不太明白
popu = 50;%初始种群大小   
CityNum = 13;%城市数量
popu = 50;%初始种群大小   
CityNum = 13;%城市数量
dis = [0 2.2 18.1 4.8 9.2 8.4 5.2 0.4 9.3 11.3 10.2 0.4 10.4;
     2.2 0 17.5 2.8 7.9 6.6 3.3 1.8 8.5 9.8 8.7 2.4 9.6;
     18.1 17.5 0 14.7 9.6 10.9 14.2 18.2 9.1 7.6 8.7 18.3 8.0;
     4.8 2.8 14.7 0 5.4 3.8 0.5 4.4 6.4 7.0 6.0  5.1  7.4;
     9.2  7.9  9.6  5.4  0    2.4  4.9  9.0  1.7  2.3  1.2  9.5  2.2;
     8.4  6.6  10.9 3.8  2.4  0    3.3  8.1  4.1  3.3  2.5  8.7  4.6;
     5.2  3.3  14.2 0.5  4.9  3.3  0    4.8  6.0  6.6  5.5  5.5  6.9;
     0.4  1.8  18.2 4.4  9.0  8.1  4.8  0    9.2  11.1 10.0 0.6  10.3;
     9.3  8.5  9.1  6.4  1.7  4.1  6.0  9.2  0    3.3  2.5  9.6  1.1;
     11.3 9.8  7.6  7.0  2.3  3.3  6.6  11.1 3.3  0    1.2  11.7 2.8;
     10.2 8.7  8.7  6.0  1.2  2.5  5.5  10.0 2.5  1.2  0    10.5 2.5;
     0.4  2.4  18.3 5.1  9.5  8.7  5.5  0.6  9.6  11.7 10.5 0    10.7;
     10.4 9.6  8.0  7.4  2.2  4.6  6.9  10.3 1.1  2.8  2.5  10.7 0];%距离矩阵
popm=zeros(popu,CityNum);
for i=1:popu
popm(i,:)= randperm(CityNum);%生成初始群体
end
city_index = (popm(:,1:CityNum-1)-1).*13 + popm(:,2:CityNum);
city_index1 = sub2ind([CityNum,popu],popm(:,2:CityNum),popm(:,1:CityNum-1));
city_distance = sum(dis(city_index),2)%或者用city_index1也行
     


您需要登录后才可以回帖 登录 | 注册

本版积分规则

关闭

站长推荐上一条 /3 下一条

快速回复 返回顶部 返回列表