Particle Swarm Optimization for Travelling Salesman Problem

Postingan saya di bawah ini merupakan tugas mata kuliah pilihan Metaheuristik yang sedang saya ambil semester 6 ini. i do really attracted to optimization. challenge my brain to think ;;). as well as my laboratory tag line: OPTIMIZE YOUR LIFE! haha :p

Permasalahan:1.          Dalam permasalahan Travelling Salesman Problem, tentukan rute terpendek untuk dapat

melewati 51 kota dan kembali ke kota asal dengan menggunakan algoritma Particle Swarm Optimization. Diketahui data koordinat lokasi 51 kota sebagai berikut:

xy = [37 52; 49 49; 52 64; 20 26; 40 30; 21 47; 17 63; 31 62; 52 33; 51 21; 42 41; 31 32; 5 25; 12 42; 36 16; 52 41; 27 23; 17 33; 13 13; 57 58; 62 42; 42 57; 16 57; 8 52; 7 38; 27 68; 30 48; 43 67; 58 48; 58 27; 37 69; 38 46; 46 10; 61 33; 62 63; 63 69; 32 22; 45 35; 59 15; 5 6; 10 17; 21 10; 5 64; 30 15; 39 10; 32 39; 25 32; 25 55; 48 28; 56 37; 30 40]

2.          Diketahui matriks jarak:dx =           0   132   217   164    58

   132     0   290   201    79   217   290     0   113   303   164   201   113     0   196    58    79   303   196   0;

Bandingkan performansi penyelesaian permasalahan TSP 5 kota dengan menggunakan LINGO serta MATLAB. Apa perbedaannya?

Penyelesaian:1.          ALGORITMA PSO UNTUK TSP 51 KOTA

function[rute_optimum,jarak_minimum,t]=psofortsp(xy,ba,bb,np,itmax)%xy = koordinat kota%ba,bb,np = batas atas(1), batas bawah(0), jumlah partikel%itmax = iterasi maksimum%rute_optimum = rute tsp terbaik (optimal)%jarak_minimum = jarak dari rute tps yang terbaik%t = waktu komputasi

%step 1:t=cputime;%menghitung matriks jarakL=length(xy);for i=1:L;    for j=1:L;        dx(i,j)=sqrt((xy(i,1)-xy(j,1)).^2+(xy(i,2)-xy(j,2)).^2);    endend%inisialisasi secara random partikel xi dan kecepatan vi dalam%ruang pencarian problem p-dimensi[r,c]=size(dx);nk=c;x=rand(np,nk)*(ba-bb)+bb;v=rand(np,nk);%mengurutkan nilai random secara ascending untuk mendapatkan rute[min1 perm]=sort(x,2);perm_tsp=[perm perm(:,1)];%step 2: evaluasi nilai fungsi tujuan jarak total tiap rute

jarak=zeros(np,1);for i=1:np    x1=perm_tsp(i,:);    jarak (i)=jartsp(x1,dx); %memanggil fungsi perhitungan jarak rute tspendf=jarak;%step 3: memperbarui nilai Pbest dan Gbest partikel awalPbest=x; %posisi terbaik individu (best local)fbest=f; %fungsi tujuan terbaik[minf,idk]=min(fbest);Gbest=x(idk,:); %posisi terbaik swarm (best global)minftot=[];minfk=[];

%step 4: memperbarui posisi dan kecepatan partikelit=1; %setting iterasirhomax=0.9;rhomin=0.4; %rentang nilai inersia yang digunakanwhile it<itmax    r1=rand;r2=rand;    rho=rhomax-((rhomax-rhomin)/itmax)*it; %bobot inersia    for j=1:np        v(j,:)=rho.*v(j,:)+r1.*(Pbest(j,:)-x(j,:))+r2.*(Gbest-x(j,:));        x(j,:)=x(j,:)+v(j,:);    end    %penyesuaian agar x tidak melanggar interval (bb,ba)    for i=1:np        for j=1:nk-1            if x(i,j)>ba                x(i,j)=ba;            end            if x(i,j)<bb                x(i,j)=bb;            end        end    end    %mengurutkan nilai random untuk mendapatkan rute dari yang terkecil ke    %terbesar    [min1 perm]=sort(x,2);    perm_tsp=[perm perm(:,1)]; %permutasi rute tsp       %evaluasi nilai fungsi tujuan permutasi tsp    jarak=zeros(np,1);    for i=1:np        x1=perm_tsp(i,:);        jarak(i)=jartsp(x1,dx); %memanggil fungsi penghitungan jarak rute tsp    end    f=jarak;       %memperbarui fbest, Pbest, Gbest    changerow=f<fbest;    fbest=fbest.*(1-changerow)+f.*changerow;    Pbest(find(changerow),:)=x(find(changerow),:);    [minf,idk]=min(fbest);

    Gbest=Pbest(idk,:);    minftot=[minftot;minf];    it=it+1; %penambahan jumlah iterasiend%step 5: output solutionlastbest=Pbest; %nilai random partikel terbaik pada iterasi terakhir[min1 perm]=sort(lastbest,2);perm_tsp=[perm perm(:,1)]; %rute tsp kembali ke kota awal %evaluasi nilai fungsi tujuan pada iterasi tahap akhirjarak=zeros(np,1);for i=1:np    x1=perm_tsp(i,:);    jarak(i)=jartsp(x1,dx); %memanggil fungsi perhitungan jarak rute tspendf=jarak; %fungsi tujuan[jarak_minimum,idk]=min(f);rute_optimum=perm_tsp(idk,:);t=cputime-t;function jarak=jartsp(x1,dx)[r,c]=size(x1);k=c-1; %jumlah kota dalam rute tsps=0; %jarak awal di kota pertamafor j=1:k    s=s+dx(x1(j),x1(j+1)); %pengakumulasian jarak rute tspendjarak=s;   

:: HASIL RUNNING MATLAB (PSO UNTUK TSP 51 KOTA)>> xy=[37 52; 49 49; 52 64; 20 26; 40 30; 21 47; 17 63; 31 62; 52 33; 51 21; 42 41; 31 32; 5 25; 12 42; 36 16; 52 41; 27 23; 17 33; 13 13; 57 58; 62 42; 42 57; 16 57; 8 52; 7 38; 27 68; 30 48; 43 67; 58 48; 58 27; 37 69; 38 46; 46 10; 61 33; 62 63; 63 69; 32 22; 45 35; 59 15; 5 6; 10 17; 21 10; 5 64; 30 15; 39 10; 32 39; 25 32; 25 55; 48 28; 56 37; 30 40]xy =    37    52    49    49    52    64    20    26    40    30    21    47    17    63    31    62    52    33    51    21    42    41    31    32     5    25    12    42    36    16    52    41    27    23    17    33    13    13

    57    58    62    42    42    57    16    57     8    52     7    38    27    68    30    48    43    67    58    48    58    27    37    69    38    46    46    10    61    33    62    63    63    69    32    22    45    35    59    15     5     6    10    17    21    10     5    64    30    15    39    10    32    39    25    32    25    55    48    28    56    37    30    40

>> [rute_optimum,jarak_minimum,t]=psofortsp(xy,1,0,1000,500)rute_optimum =  Columns 1 through 25    14    43     7    31    28     1    51    11    38    49    30    50    16    21    29    20     2     3     4     5     6     8     9    10    12  Columns 26 through 50    13    15    17    18    19    22    23    24    25    26    27    32    33    34    35    36    37    39    40    41    42    44    45    46    47  Columns 51 through 52    48    14jarak_minimum =  1.0216e+003t =    6.8594

>> [rute_optimum,jarak_minimum,t]=psofortsp(xy,1,0,1000,1000)rute_optimum =  Columns 1 through 25    32     1    27    48    43    18     5    11    16    38    10    45    33    39    30    21    29    20     2     3     4     6     7     8     9

  Columns 26 through 50    12    13    14    15    17    19    22    23    24    25    26    28    31    34    35    36    37    40    41    42    44    46    47    49    50  Columns 51 through 52    51    32jarak_minimum =  992.0706t =   16.3281

>> [rute_optimum,jarak_minimum,t]=psofortsp(xy,1,0,1000,1500)rute_optimum =  Columns 1 through 25    43     4    42    15    33    39    10     9    16    20     3    31    26    32     1     2     5     6     7     8    11    12    13    14    17  Columns 26 through 50    18    19    21    22    23    24    25    27    28    29    30    34    35    36    37    38    40    41    44    45    46    47    48    49    50  Columns 51 through 52    51    43jarak_minimum =  1.0473e+003t =   23.3594

:: ANALISIS DAN INTERPRETASI PERTANYAAN #1            Dilakukan tiga kali running dengan jumlah pembangkitan sampel rute dan iterasi yang berbeda-beda dan didapatkan bahwa jarak total minimum 51 kota dari tiga kali running tersebut adalah  992.0706 (lama waktu komputasi 16.3281detik) dengan rute sebagai berikut:32   -  1  -  27  -  48  -  43  -  18  -   5  -  11  -  16  -  38  -  10  -  45  -  33  -  39  -  30  -  21 -   29 -  20  -   2  -   3  -   4  -   6  -   7   -  8  -   9  -   12  -  13  -  14  -  15  -  17  -  19  -  22  -  23 -   24  -  25  -  26  -  28  -  31  -  34  -  35  -  36  -  37  -  40  -  41  -  42  -  44  -  46  -  47  -  49  -  50  - 51  -  32Masih ada kemungkinan untuk didapatkan total jarak yang lebih optimum (lebih kecil) karena hasil rute terbaik tergantung dari bilangan random yang dihasilkan. Walaupun belum tentu optimal, namun dengan jangka waktu yang relatif cepat bisa didapatkan hasil yang mendekati optimal.

2.          Permasalahan TSP 5 Kota::: CODING DENGAN MENGGUNAKAN LINGOMODEL: ! Traveling Salesman Problem for the cities of Atlanta, Chicago, Cincinnati, Houston, LA, Montreal; SETS:  CITY / 1.. 5/: U; ! U( I) = sequence no. of city;  LINK( CITY, CITY):       DIST,  ! The distance matrix;          X;  ! X( I, J) = 1 if we use link I, J; ENDSETS DATA:   !Distance matrix, it need not be symmetric;  DIST =   0   132   217   164    58   132     0   290   201    79   217   290     0   113   303   164   201   113     0   196

    58    79   303   196   0; ENDDATA

 !The model:Ref. Desrochers & Laporte, OR Letters,  Feb. 91;  N = @SIZE( CITY);  MIN = @SUM( LINK: DIST * X);  @FOR( CITY( K):  !  It must be entered;   @SUM( CITY( I)| I #NE# K: X( I, K)) = 1;  !  It must be departed;   @SUM( CITY( J)| J #NE# K: X( K, J)) = 1;  ! Weak form of the subtour breaking constraints;  ! These are not very powerful for large problems;   @FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:       U( J) >= U( K) + X ( K, J) -       ( N - 2) * ( 1 - X( K, J)) +       ( N - 3) * X( J, K)   );  );  ! Make the X's 0/1;  @FOR( LINK: @BIN( X));  ! For the first and last stop we know...;  @FOR( CITY( K)| K #GT# 1:   U( K) <= N - 1 - ( N - 2) * X( 1, K);   U( K) >= 1  + ( N - 2) * X( K, 1)  );END

:: HASIL LINGOGlobal optimal solution found.  Objective value:                              668.0000  Objective bound:                              668.0000  Infeasibilities:                             0.4440892E-15  Extended solver steps:                           0  Total solver iterations:                        18Rute Optimum: 1-5-2-4-3-1

:: CODING DENGAN MENGGUNAKAN MATLABfunction[rute_optimum,jarak_minimum,t]=psofortsp5kota(dx,ba,bb,np,itmax)%xy = koordinat kota%ba,bb,np = batas atas(1), batas bawah(0), jumlah partikel%itmax = iterasi maksimum%rute_optimum = rute tsp terbaik (optimal)%jarak_minimum = jarak dari rute tps yang terbaik%t = waktu komputasi

%step 1:t=cputime;%inisialisasi secara random partikel xi dan kecepatan vi dalam%ruang pencarian problem p-dimensi[r,c]=size(dx);nk=c;x=rand(np,nk)*(ba-bb)+bb;

v=rand(np,nk);%mengurutkan nilai random secara ascending untuk mendapatkan rute[min1 perm]=sort(x,2);perm_tsp=[perm perm(:,1)];%step 2: evaluasi nilai fungsi tujuan jarak total tiap rutejarak=zeros(np,1);for i=1:np    x1=perm_tsp(i,:);    jarak (i)=jartsp(x1,dx); %memanggil fungsi perhitungan jarak rute tspendf=jarak;%step 3: memperbarui nilai Pbest dan Gbest partikel awalPbest=x; %posisi terbaik individu (best local)fbest=f; %fungsi tujuan terbaik[minf,idk]=min(fbest);Gbest=x(idk,:); %posisi terbaik swarm (best global)minftot=[];minfk=[];

%step 4: memperbarui posisi dan kecepatan partikelit=1; %setting iterasirhomax=0.9;rhomin=0.4; %rentang nilai inersia yang digunakanwhile it<itmax    r1=rand;r2=rand;    rho=rhomax-((rhomax-rhomin)/itmax)*it; %bobot inersia    for j=1:np        v(j,:)=rho.*v(j,:)+r1.*(Pbest(j,:)-x(j,:))+r2.*(Gbest-x(j,:));        x(j,:)=x(j,:)+v(j,:);    end    %penyesuaian agar x tidak melanggar interval (bb,ba)    for i=1:np        for j=1:nk-1            if x(i,j)>ba                x(i,j)=ba;            end            if x(i,j)<bb                x(i,j)=bb;            end        end    end    %mengurutkan nilai random untuk mendapatkan rute dari yang terkecil ke    %terbesar    [min1 perm]=sort(x,2);    perm_tsp=[perm perm(:,1)]; %permutasi rute tsp       %evaluasi nilai fungsi tujuan permutasi tsp    jarak=zeros(np,1);    for i=1:np        x1=perm_tsp(i,:);        jarak(i)=jartsp(x1,dx); %memanggil fungsi penghitungan jarak rute tsp    end    f=jarak;   

    %memperbarui fbest, Pbest, Gbest    changerow=f<fbest;    fbest=fbest.*(1-changerow)+f.*changerow;    Pbest(find(changerow),:)=x(find(changerow),:);    [minf,idk]=min(fbest);    Gbest=Pbest(idk,:);    minftot=[minftot;minf];    it=it+1; %penambahan jumlah iterasiend%step 5: output solutionlastbest=Pbest; %nilai random partikel terbaik pada iterasi terakhir[min1 perm]=sort(lastbest,2);perm_tsp=[perm perm(:,1)]; %rute tsp kembali ke kota awal

%evaluasi nilai fungsi tujuan pada iterasi tahap akhirjarak=zeros(np,1);for i=1:np    x1=perm_tsp(i,:);    jarak(i)=jartsp(x1,dx); %memanggil fungsi perhitungan jarak rute tspendf=jarak; %fungsi tujuan[jarak_minimum,idk]=min(f);rute_optimum=perm_tsp(idk,:);t=cputime-t;function jarak=jartsp(x1,dx)[r,c]=size(x1);k=c-1; %jumlah kota dalam rute tsps=0; %jarak awal di kota pertamafor j=1:k    s=s+dx(x1(j),x1(j+1)); %pengakumulasian jarak rute tspendjarak=s;

:: HASIL RUNNING MATLAB (PSO UNTUK TSP 5 KOTA)>> [rute_optimum,jarak_minimum,t]=psofortsp5kota(dx,1,0,10,20)rute_optimum =     4     2     5     1     3     4jarak_minimum =   668t =     0

>> [rute_optimum,jarak_minimum,t]=psofortsp5kota(dx,1,0,5,10)rute_optimum =     1     5     2     4     3     1jarak_minimum =   668t =     0

>> [rute_optimum,jarak_minimum,t]=psofortsp5kota(dx,1,0,10,18)rute_optimum =     5     1     3     4     2     5jarak_minimum =

   668t =     0

:: ANALISIS DAN INTERPRETASI PERTANYAAN #2            Dalam menyelesaikan permasalahan TSP 5 kota di atas, digunakan 2 metode. Metode yang pertama menggunakan software LINGO. Output yang dihasilkan oleh software LINGO dapat dipastikan sudah optimum karena softwareLINGO menggunakan metode branch and bound untuk menyelesaikan permasalahan. Dari hasil running didapatkan bahwa jarak optimal 5 kota tersebut adalah 668, dicapai dalam 18 iterasi, dengan waktu komputasi selama 0 detik. Rute optimum yang dihasilkan adalah 1-5-2-4-3-1.Sedangkan ketika menyelesaikan permasalahan ini dengan menggunakan algoritma PSO di MATLAB didapatkan bahwa jarak optimum dengan 3 kali running adalah 668, dicapai dalam 10 iterasi, dengan waktu komputasi selama 0 detik. Rute optimum yang dihasilkan adalah 1-5-2-4-3-1.Bisa dilihat bahwa dalam permasalahan kecil (TSP 5 kota), hasil dari metode eksak (dengan menggunakan LINGO) sama dengan hasil yang dihasilkan dari metaheuristik dengan menggunakan algoritma PSO. Jika permasalahan diperbesar dengan menambah jumlah kota, bisa jadi hasil output dengan menggunakan PSO tidak optimal, hanya mendekati optimal saja karena hasil tergantung dari bilangan random yang dihasilkan. Namun penggunaan metode metaheuristik ini akan sangat menguntungkan jika problemnya sangat besar karena metode eksak akan membutuhkan waktu komputasi yang sangat lama untuk menyelesaikannya, berbeda dengan metaheuristik yang cepat waktu komputasinya