查看: 1008|回復: 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

最佳答案
2#
發表于 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

最佳答案
3#
 樓主| 發表于 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)這個函數咋編呀

論壇優秀回答者

權威

3902 麥片

財富積分



3

主題

4120

帖子

868

最佳答案
  • 關注者: 184
4#
發表于 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

最佳答案
5#
 樓主| 發表于 2019-8-6 15:52:12 | 只看該作者

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

入門

68 麥片

財富積分


50500


0

主題

52

帖子

4

最佳答案
6#
發表于 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

最佳答案
7#
 樓主| 發表于 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

最佳答案
8#
發表于 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 下一條

快速回復 返回頂部 返回列表
哪一款德州扑克还能玩