OPTIMASI METODE RABNET PADA PENYELESAIAN TRAVELLING SALESMAN PROBLEM Radhifan Prastiama1, Yudhi Purwananto2, Rully Soelaiman3 Teknik Informatika, Fakultas Teknologi Informasi, ITS email :
[email protected],
[email protected],
[email protected]
salesman pada suatu kota harus mengunjungi seluruh bagian dari kota tersebut sebanyak satu kali dan kembali ke tempat asal dengan meminimalkan biaya perjalanan. Banyak metode yang dapat digunakan untuk permasalahan TSP seperti Articial Neural Network (ANN) yang sudah dipelajari secara luas untuk memecahkan masalah tersebut dan memperlihatkan hasil yang baik. Pada makalah ini akan digunakan metode RABNETTSP [3]. Dimana RABNET-TSP adalah Real-Valued Antibody Network untuk menemukan solusi dari TSP [4].
ABSTRAKSI Permasalahan Traveling Salesman Problem (TSP) adalah salah satu permasalahan klasik NPcomplete. Permasalahan NP-complete ini pada umumnya memiliki penyelesaian yang membutuhkan waktu yang sangat lama. Dalam beberapa tahun terakhir, para ahli telah membuat solusi penyelesaiannya dengan menggunakan metode heuristik yang memiliki waktu penyelesaian yang lebih cepat. Namun metode heuristik yang ditemukan ini tidak menjamin akan mendapatkan solusi yang optimal. Real-Valued Antibody Network (RABNET) merupakan metode self-organizing neural network yang terinspirasi dari metode immune system. Metode ini awalnya diciptakan untuk menyelesaikan permasalahan pada data clustering, namun karena keunggulannya maka dimodifikasi untuk dapat menyelesaikan permasalahan TSP yang disebut RABNET-TSP. Metode ini dalam menganggap permasalahan sebagai kelompok antigen, sehingga untuk menyelesaikannya dibentuk kelompok antibody yang dapat menangani semua antigen. Antibodyantibody tersebut akan bersaing satu sama lain dan beradaptasi terhadap antigen agar setiap antigen dapat ditangani dengan tepat oleh antobody. Metode RABNET-TSP memiliki empat buah parameter utama. Keempat parameter tersebut memiliki pengaruhnya masing-masing terhadap jalannya proses RABNET-TSP. Pada uji coba dalam tugas akhir ini didapatkan nilai parameter yang dapat mengoptimalkan kinerja dari RABNET-TSP.
2
Real-valued antibody network to the travelling salesman problem (RABNET-TSP) adalah sebuah algoritma yang didapatkan dari hasil modifikasi algoritma RABNET untuk menyelesaikan salah satu permasalahan optimisasi combinatorial, yaitu TSP. Pada RABNET-TSP, pemodelan arsitekturnya hampir sama dengan model arsitektur dari algoritma RABNET [2]. Namun pada RABNET-TSP jumlah fase utama yang digunakan lebih banyak [3].
2.1 Network Initialization Pada jaringan RABNET-TSP hanya diinisialisasikan oleh satu antibody. Pada fase ini dilakukan inisialisasi pertama dengan membuat satu network cell (antibody) yang letaknya berada di centroid distribusi kota (antigen), agar antibody hasil network growing dapat tersebar secara merata. Sehingga seluruh kota (antigen) dapat ditangani oleh antibody yang berbeda. Menentukan letak dari antibody pertama yaitu dengan cara merata-rata koordinat dari sumbu x dan sumbu y.
Kata kunci: TSP, RABNET, Antibody, Antigen
1
REAL-VALUED ANTIBODY NETWORK TO THE TRAVELLING SALESMAN PROBLEM (RABNET-TSP)
PENDAHULUAN
Permasalahan tentang optimasi merupakan suatu hal yang sudah umum dan banyak ditemukan dalam suatu hal yang nyata seperti pemilihan rute perjalanan dan masalah penjadwalan. Optimasi adalah untuk memaksimalkan atau mengoptimalkan sesuatu hal yang bertujuan untuk mengelola sesuatu yang dikerjakan agar dapat mencapai suatu kepuasan yang maksimal. Suatu hal yang mungkin paling sering dijumpai pada permasalahan optimasi adalah masalah mengenai Travelling Salesman Problem (TSP) [1]. Dimana
2.2 Presentation Of Antigens Dalam fase ini urutan kota dirandom untuk tiap-tiap iterasi. Proses ini dilakukan agar selama proses adaptasi, antibody tidak tergantung pada urutan kota yang ada.
1
σ(t) = σ(0) exp(-t/)
2.3 Competition Pada fase ini tiap antibody bersaing untuk mendapatkan antigen. Persaingan ini didasarkan pada jarak antara antigen dan antibody. Antibody yang memenangkan sebuah antigen dalam persaingan adalah antibody yang memiliki jarak terdekat dengan antigen tersebut. Informasi dari hasil persaingan ini akan digunakan pada fase-fase berikutnya, yaitu fase growing dan fase pruning. Langkah awal yang dilakukan setelah proses inisialisasi adalah mencari antibody pemenang untuk antigen. Sesuatu yang menentukan bahwa antibody telah mendapatkan suatu antigen adalah dengan menghitung jaraknya. Jarak yang dihitung adalah jarak Euclidean. Dalam metode RABNET-TSP, proses ini berada pada tahap ini. Rumus untuk mendapatkan hasil persaingan antibody ditunjukkan oleh Rumus 1.
J = arg minj ║Agi – Abj║ ∀j
Setelah semua nilai yang diperlukan untuk menghitung nilai hjJ telah selesai dihitung, selanjutnya dilakukan perhitungan nilai hjJ dengan menggunakan Rumus 4.
hjJ = exp(-djJ2/2σ2)
(4)
2.5 Adaptation Fase ini merupakan fase untuk menggerakkan posisi antibody berdasarkan letak antigen yang berpengaruh dan fungsi kernel hjJ. Fase ini merupakan fase pembelajaran bagi antibody. Setiap antibody akan mempelajari cara menangani antigen dengan merubah posisinya menjadi lebih dekat dengan antigen atau dengan kata lain bergerak menuju antigen. Namun sebelum menghitung nilai pergerakan antibody, terlebih dahulu menghitung nilai update alfa. Nilai alfa merupakan salah satu parameter pembentuk pergerakan antibody. Rumus perhitungan nilai alfa yang baru ditunjukkan pada Rumus 5.
(1)
2.4 Cooperation Fase ini merupakan fase untuk menentukan nilai general kernel hjJ. Kernel ini digunakan sebagai factor pengali dalam fase Adaptation. Nilai kernel ini berbedabeda untuk tiap antibody dan nilai ini kalau dilakukan plotting akan membentuk kurva lonceng. Sebelum membentuk nilai hjJ, terlebih dahulu perlu dihitung nilai variable pendukungnya. Salah satunya adalah nilai djJ yang merupakan nilai derajat ketetanggaan antibody dimana nilai tersebut merupakan nilai jarak topologikal atau urutan antibody. Setelah selesai mendapatkan antibody pemenang untuk masing-masing antigen, selanjutnya perlu menghitung nilai kernel deerajat ketetanggaan. Nilai ini merupakan nilai yang berasal dari nilai ketetanggaan antar antibody. Nilai ini nantinya akan digunakan sebagai salah satu parameter untuk menghitung pergerakan antibody. Pada langkah awal dihitung nilai djJ. Nilai djJ merupakan nilai jarak indeks antar antibody yang direpresentasikan dengan bilangan bulat. Rumus untuk menghitung djJ ditunjukkan pada Rumus 2.
djJ = min [ | j – J |, N - | j –J | ]
(3)
α(t) = α(0) exp(-t/)
(5)
Setelah mendapatkan nilai alfa yang baru kemudian dapat dihitung pergerakan antibody. Rumus untuk mengetahui posisi antibody yang baru terhadap antigen ditunjukkan pada Rumus 6.
Abi (t+1) = Abi(t) + α(t) hjJ(t) [Ag(t) – Abi(t)]
(6)
2.6 Network Growing Fase ini merupakan fase untuk mengkloning antibody menggunakan tiga syarat yaitu: Memilih antibody yang memiliki affinitas paling besar. Memilih antigen yang dikenali oleh antibody terpilih dengan jarak yang paling jauh. Menghitung jarak antara antibody terpilih dengan antigen terpilih kemudian dibandingkan dengan threshold ε. Jika nilai tersebut lebih besar dari nilai threshold, maka antibody tersebut dikloning.
(2)
. Nilai j merepresentasikan indeks antibody yang akan dihitung jarak indeks ketetanggannya, sedangkan nilai J merepresentasikan indeks antibody terpilih atau antibody acuan. Setelah nilai djJ didapatkan, selanjutnya nilai djJ tersebut digunkan untuk menghitung nilai hjJ, namun sebelum dilakukan perhitungan nilai hjJ, terlebih dahulu dilakukan update nilai sigma. Nilai ini merupakan salah satu parameter penyusun hjJ. Untuk mencari nilai sigma ditunjukkan oleh Rumus 3.
Hasil kloningan antibody tersebut memiliki nilai koordinat yang sama dengan nilai koordinat antibody yang dikloning dan letak urutan topologinya bersebelahan dengan antibody yang dikloning.
2.7 Stabilization Of The Winners Fase ini merupakan fase untuk mencari nilai kestabilan antibody pemenang dengan membandingkan posisi iterasi sebelumnya dan posisi iterasi saat ini. Fase
2
ini digunakan untuk mencari tahu apakah susunan pemenang hasil dari fase competition ini masih sama atau sudah berubah. Jika masih sama, maka proses cooperation tidak usah dihitung pada iterasi yang sedang berlangsung.
Mulai Tidak
Neighborhood = 1?
Inisialisasi nilai iterasi, tau1, tau2, gamma, v, dan neighborhood
2.8 Convergence Criterion Fase ini digunakan untuk memberhentikan iterasi jika semua antibody telah menangani satu antigen. Untuk mengetahui apakah kondisi tersebut sudah dipenuhi atau belum, maka setiap antibody setidaknya memiliki jarak sebesar λ dengan satu antigen. Kriteria konvergen ini untuk memastikan apakah proses penyelesaian dengan algoritma RABNET-TSP ini sudah mecapai kestabilan. Jika sudah stabil maka proses dianggap sudah selesai dan akan dihentikan. Pada fase ini semua jarak antigen dan antibody pemenangnya dibandingkan dengan nilai threshold. Jika semua jarak tersebut lebih kecil dibandingkan dengan nilai threshold maka antibody tersebut sudah benar-benar menangani antigen tersebut dan dianggap sudah konvergen. Pertimbangan lainnya adalah setiap antibody hanya boleh menangani satu antigen, tidak boleh lebih.
Ya
Cooperation
Network Initializaton Adaptation
1
Update nilai iterasi, alfa, dan sigma Convergence Criterion
Presentation of Antigen
2 Competition
2.9 Network Prunning
Gambar 1 Diagram alir sistem RABNET-TSP
Dalam fase ini antibody yang tidak menangani antigen manapun akan dihapus karena solusi yang dibutuhkan hanya antibody yang berada pada antigen sehingga jumlah antibody yang dibutuhkan sama dengan jumlah antigen.
3
2
Konvergen?
Ya
Tidak
Winners Stabilize
IMPLEMENTASI
Pada subbab ini akan dijelaskan mengenai prosesproses utama dalam metode RABNET-TSP. Secara garis besar tahapan utama yang digunakan dalam RABNETTSP ditunjukkan pada Gambar 1 dan 2. Pada langkah awal setelah proses penginisialisasian, dilakukan proses untuk membentuk antibody pertama. Seiring bertambahnya proses iterasi, antibody ini akan membelah diri. Dalam proses tiap iterasi, antibodyantibody yang sudah terbentuk akan melakukan persaingan untuk dapat menangani antigen. Pada akhirnya antibody-antibody ini akan saling berbagi tugas dalam penanganan antigen. Setelah masing-masing antibody mendapatkan antigen untuk ditangani, selanjutnya antibody-antibody tersebut akan beradaptasi dengan merubah posisinya menuju posisi antigen yang ditangani. Pada metode RABNET-TSP, langkah awal yang dilakukan setelah proses inisialisasi adalah mencari antibody pemenang untuk antigen. Proses ini berada pada tahap competition. Rumus yang digunakan untuk mendapatkan antibody pemenang dari sebuah antigen ditunjukkan pada Rumus 1.
Stabil?
Ya
Neighborhood = 0
Tidak
1
Network Growing
Pruning
Selesai
Gambar 2 Diagram alir sistem RABNET-TSP lanjutan
Setelah selesai mendapatkan antibody pemenang untuk masing-masing antigen, selanjutnya perlu menghitung nilai kernel deerajat ketetanggaan. Nilai ini
3
1. 2. 3. 4. 5.
merupakan nilai yang berasal dari nilai ketetanggaan antar antibody. Nilai ini nantinya akan digunakan sebagai salah satu parameter untuk menghitung pergerakan antibody. Proses ini berada pada tahap cooperation. Pada langkah awal dihitung nilai djJ. Nilai djJ merupakan nilai jarak indeks antar antibody yang direpresentasikan dengan bilangan bulat. Rumus untuk menghitung djJ ditunjukkan pada Rumus 2. Langkah selanjutnya adalah melakukan perhitungan pergerakan antibody. Fase ini masuk ke dalam fase adaptation. Fase ini merupakan fase pembelajaran bagi antibody. Setiap antibody akan mempelajari cara menangani antigen dengan merubah posisinya menjadi lebih dekat dengan antigen atau dengan kata lain bergerak menuju antigen. Namun sebelum menghitung nilai pergerakan antibody, terlebih dahulu menghitung nilai update alfa. Nilai alfa merupakan salah satu parameter pembentuk pergerakan antibody. Rumus perhitungan nilai alfa yang baru ditunjukkan pada Rumus 5. Setelah mendapatkan nilai alfa yang baru kemudian dapat dihitung pergerakan antibody. Rumus untuk mengetahui posisi antibody yang baru terhadap antigen ditunjukkan pada Rumus 6. Langkah selanjutnya dalam algoritma RABNETTSP ini adalah melakukan pembelahan diri untuk antibody. Hal ini berguna agar antibody yang menangani lebih dari satu antigen dapat memberikan salah satu antigennya kepada antibody yang baru agar tugas dari antibody tetap fokus hanya pada satu buah antigen saja. Fase ini termasuk ke dalam fase network growing. Langkah selanjutnya adalah menghitung kriteria konvergen. Kriteria konvergen ini untuk memastikan apakah proses penyelesaian dengan algoritma RABNETTSP ini sudah mecapai kestabilan. Jika sudah stabil maka proses dianggap sudah selesai dan akan dihentikan. Pada fase ini semua jarak antigen dan antibody pemenangnya dibandingkan dengan nilai threshold. Langkah berikutnya adalah mencari nilai kestabilan antibody pemenang dengan membandingkan posisi iterasi sebelumnya dan posisi iterasi saat ini. Fase terakhir adalah melakukan prunning,dimana dalam fase ini antibody yang tidak menangani antigen manapun akan dihapus karena solusi yang dibutuhkan hanya antibody yang berada pada antigen sehingga jumlah antibody yang dibutuhkan sama dengan jumlah antigen.
4
Berlin52 St70 Ncit64 KroA100 Eil51
4.1 Uji Coba Mengganti Parameter Alfa Pada uji coba ini, parameter alfa akan diuji pengaruhnya dengan mengguanakan berbagai macam nilai. Untuk parameter selain alfa, yaitu sigma, etha, lambda digunakan nilai yang terdapat pada paper, yaitu: Sigma = 16 Etha = 0,2 Lambda = 0,01 Hasil uji coba mengganti parameter alfa dapat dilihat pada tabel 1, tabel 2, tabel 3, tabel 4 dan tabel 5. Tabel 1 Hasil uji coba parameter alfa pada permasalahan berlin52 Alfa 0.1 0.2 0.3 0.4 0.5 0.6 0.7
Cost 8336.907255 8311.593406 8294.429052 8266.982513 8076.264472 8112.926806 8050.948811
Iterasi 997.6 922.8 922 882.6 853.0 784.2 786.6
Running Time 181.272718 170.191376 171.960504 165.412108 161.972800 146.128530 143.805188
Tabel 2 Hasil uji coba parameter alfa pada permasalahan st70 Alfa 0,1 0,2 0,3 0,4 0,5 0,6 0,7
Cost 726.557063 712.277962 697.071217 688.233674 690.037761 684.446299 689.971954
Iterasi 970.8 960.2 899.8 877.6 863 832 828.2
Running Time 275.625218 261.774813 246.343151 237.422754 245.142751 234.404145 232.299530
Tabel 3 Hasil uji coba parameter alfa pada permasalahan kroA100
UJI COBA DAN EVALUASI
Alfa 0.1 0.2 0.3 0.4 0.5 0.6 0.7
Pada bagian ini dijelaskan mengenai skenario uji coba yang telah dilakukan. Terdapat empat skenario yang diujicobakan pada aplikasi. Keempat skenario itu merupakan pengujian untuk keempat parameter yang dibutuhkan, yaitu alfa, sigma, etha, dan lambda. Dalam pengujian aplikasi ini data yang digunakan berasal dari TSPLIB yang mempunyai beberapa permasalahan. Dalam tugas akhir ini diambil 5 permasalahan dari TSPLIB. Permasalahan –permasalahan tersebut antara lain :
4
Cost 21511.740583 21641.098026 21590.021171 21546.975672 21585.541529 21636.228840 21573.146683
Iterasi 1135.8 1069.6 1037.4 998.8 981 980.8 980.8
Running Time 599.960203 367.635721 352.934880 355.894463 350.579574 351.321235 354.142931
Tabel 4 Hasil uji coba parameter alfa pada permasalahan eil51 Alfa 0.1 0.2 0.3 0.4 0.5 0.6 0.7
Cost 450.621280 448.391321 444.480941 446.314083 444.452782 446.029166 444.025571
Iterasi 931.8 878.2 869.8 825.4 804 791.6 767
Tabel 7 Hasil uji coba parameter sigma pada permasalahan st70
Running Time 159.714868 141.460282 140.269688 137.537940 133.710721 133.850527 127.235124
Sigma 16 17 18 19 20 21
Cost 6400 6400 6433.137085 6499.411255 6515.979797 6499.411255 6482.842712
Iterasi 929 843.4 838.2 825.8 823.2 813.2 819
Sigma 16 17 18 19 20 21
Running Time 183.578173 163.086036 170.997309 168.483766 174.522800 173.497954 174.370227
Sigma 16 17 18 19 20 21
4.2 Uji Coba Mengganti Parameter Sigma Uji coba parameter sigma ini digunakan untuk menguji pengaruh sigma terhadap cost, iterasi, dan running time. Pengujian ini dilakukan dengan member nilai-nilai bervariasi pada parameter sigma dengan rentang nilai 16 sampai 21. Sedangkan parameter selain sigma diisi dengan nilai-nilai tetap, yaitu: Alfa = 0,1 Etha = 0,2 Lambda = 0,01
Sigma 16 17 18 19 20 21
Tabel 6 Hasil uji coba parameter sigma pada permasalahan berlin52 Iterasi 997.6 992.8 975.6 968.8 984.8 969.6
Cost 21511.740583 21513.627726 21565.693649 21529.923981 21529.923981 21553.516210
Iterasi 1135.8 1141.8 1122.8 1133 1140.8 1111.2
Running Time 599.960203 410.718679 416.156452 412.138354 477.338225 428.461768
Cost 450.621280 450.269475 451.282244 449.645136 450.190973 450.033970
Iterasi 931.8 926 916.6 935.4 886.8 909
Running Time 159.714868 154.419116 151.253160 148.498639 146.217230 146.346107
Tabel 10 Hasil uji coba parameter sigma pada permasalahan ncit64
Hasil uji coba mengganti parameter sigma dapat dilihat pada tabel 6, tabel 7, tabel 8, tabel 9 dan tabel 10.
Cost 8336.907255 8323.468942 8331.396289 8323.468942 8323.468942 8323.468942
Running Time 275.625218 285.938895 267.727767 279.749857 273.422359 262.801460
Tabel 9 Hasil uji coba parameter sigma pada permasalahan eil51
Berdasarkan hasil uji coba, parameter alfa memperlihatkan hasil yaitu mempengaruhi hasil cost. Namun penentuan parameter alfa harus dilakukan uji coba terlebih dahulu, karena belum tentu dengan nilai alfa besar akan menghasilkan cost yang kecil.
Sigma 16 17 18 19 20 21
Iterasi 970.8 1013 979.4 972.2 975.2 969
Tabel 8 Hasil uji coba parameter sigma pada permasalahan kroA100
Tabel 5 Hasil uji coba parameter alfa pada permasalahan ncit64 Alfa 0.1 0.2 0.3 0.4 0.5 0.6 0.7
Cost 726.557063 717.899865 724.217661 724.918329 726.757477 724.918329
Cost 6400 6400 6400 6400 6400 6400
Iterasi 929 904.4 893.8 883.2 873 876
Running Time 183.578173 181.217174 174.883717 172.641028 176.081770 170.887671
Dari hasil uji coba menunjukkan bahwa uji coba mengganti parameter sigma menunjukkan hasil yang relatif konstan sehingga pengaruhnya kurang begitu terlihat.
Running Time 181.272718 190.239031 187.363270 186.511018 187.853825 184.373602
4.3 Uji Coba Mengganti Parameter Etha Pada uji coba parameter etha, akan dilakukan pengujian dengan menggunakan nilai etha yang bervariasi dengan rentang nilai 0,2 sampai 0,8. Sedangkan untuk nilai pada parameter lainnya digunakan nilai yang terdapat pada paper, yaitu: Alfa = 0,1
5
Tabel 15 Hasil uji coba parameter etha pada permasalahan ncit64
Sigma = 16 Lambda = 0,01 Etha
Hasil uji coba mengganti parameter etha dapat dilihat pada tabel 11, tabel 12, tabel 13, tabel 14dan tabel 15.
0.2 0.3 0.4 0.5 0.6 0.7 0.8
Tabel 11 Hasil uji coba parameter etha pada permasalahan berlin52 Etha 0.2 0.3 0.4 0.5 0.6 0.7 0.8
Cost 8336.907255 8323.468942 8315.541594 8331.396289 8315.541595 8331.396289 8331.396289
Iterasi 997.6 1042.2 1013 997.4 1017.2 1032.6 994.2
Running Time 181.272718 192.434702 176.769402 177.140317 180.773112 181.855952 168.969702
Cost 726.557063 730.498475 723.013402 725.118744 723.148038 723.345375 723.48001
Iterasi 970.8 993.2 999.8 1006.6 987.4 1011.4 1013.6
Cost 21511.740583 21534.636782 21558.234970 21558.234969 21527.178103 21556.862031 21559.607908
Iterasi 1135.8 1141.8 1137 1141.4 1139.8 1135.4 1136.8
Pada uji coba ini, parameter lambda akan diuji pengaruhnya terhadap proses RABNET-TSP. Pengujian dilakukan dengan memberikan nilai yang bervariasi pada parameter lambda dengan rentang nilai 0,01 sampai 0,07. Parameter selain lambda diberikan nilai sesuai dengan paper, yaitu: Alfa = 0,1 Sigma = 16 Etha = 0,2
Running Time 275.625218 251.514818 249.490810 250.681658 249.975631 268.199743 261.811954
Hasil uji coba mengganti parameter lambda dapat dilihat pada tabel 16, tabel 17, tabel 18, tabel 19 dan tabel 20. Tabel 16 Hasil uji coba parameter lambda pada permasalahan berlin52
Running Time 599.960203 531.672092 525.175128 583.276315 487.218817 479.667006 474.757923
Lambda 0.01 0.02 0.03 0.04 0.05 0.06 0.07
Tabel 14 Hasil uji coba parameter etha pada permasalahan eil51 Etha 0.2 0.3 0.4 0.5 0.6 0.7 0.8
Cost 450.621280 449.971127 450.222249 450.269475 450.269475 451.439247 450.269475
Iterasi 931.8 950 967.8 978.8 951.4 988.6 963
Running Time 183.578173 170.870141 170.295636 163.834252 149.869570 155.918119 158.892367
4.4 Uji Coba Mengganti Parameter Lambda
Tabel 13 Hasil uji coba parameter etha pada permasalahan kroA100 Etha 0.2 0.3 0.4 0.5 0.6 0.7 0.8
Iterasi 929 937.4 915.2 931.8 943 980.6 999.4
Dari hasil uji coba menunjukkan bahwa uji coba mengganti parameter etha menunjukkan hasil yang relatif konstan sehingga pengaruhnya kurang begitu terlihat.
Tabel 12 Hasil uji coba parameter etha pada permasalahan st70 Etha 0,2 0,3 0,4 0,5 0,6 0,7 0,8
Cost 6400 6400 6400 6400 6400 6400 6400
Cost 8336.907255 8328.979908 8339.323637 8331.396289 8347.250984 8352.761949 8315.541595
Iterasi 997.6 996.6 957 952.4 975.2 923.4 881.8
Running Time 181.272718 173.762270 167.093535 168.699365 169.552516 159.060596 152.461218
Tabel 17 Hasil uji coba parameter lambda pada permasalahan st70
Running Time 159.714868 150.693643 145.688049 139.524035 141.199441 141.361769 136.398771
Lambda 0,01 0,02 0,03 0,04 0,05 0,06 0,07
6
Cost 726.557063 725.052965 719.604377 721.374669 723.079181 723.171402 719.670156
Iterasi 970.8 962.2 967.8 949.2 941 928.2 937
Running Time 275.625218 265.473203 260.387513 274.658039 258.12926 284.409664 256.562451
Tabel 18 Hasil uji coba parameter lambda pada permasalahan kroA100 Lambda 0.01 0.02 0.03 0.04 0.05 0.06 0.07
Cost 21511.740583 21558.234969 21521.092363 21556.862031 21550.776291 21534.636782 21556.862031
Iterasi 1135.8 1117.2 1103.4 1089.2 1079.6 1077.4 1063.4
Running Time 599.960203 488.782322 485.799679 481.217881 489.217102 467.079240 466.995841 Gambar 4 St70
Tabel 19 Hasil uji coba parameter lambda pada permasalahan eil51 Lambda 0.01 0.02 0.03 0.04 0.05 0.06 0.07
Cost 450.621280 449.971127 450.269475 450.269475 450.190973 450.112472 450.269475
Iterasi 931.8 934.6 922.6 892.2 882.4 850.6 858
Running Time 159.714868 153.760235 149.043179 146.858935 138.560214 133.703168 128.858797
Tabel 20 Hasil uji coba parameter lambda pada permasalahan ncit64 Lambda 0.01 0.02 0.03 0.04 0.05 0.06 0.07
Cost 6400 6400 6400 6400 6400 6400 6400
Iterasi 929 896 880.8 857 845.6 836.6 812.6
Gambar 5 KroA100
Running Time 183.578173 162.881887 157.651003 150.981709 151.049326 147.684804 144.060051
Parameter lambda merupakan parameter untuk stopping criterion sehingga memperbesar nilainya akan memperkecil jumlah iterasi dan running time namun nilai cost yang didapat belum tentu lebih baik. Untuk contoh hasil screenshot dapat dilihat pada Gambar 3, Gambar 4, Gambar 5, Gambar 6, dan Gambar 7.
Gambar 6 Eil51
Gambar 7 Ncit64 Gambar 3 Berlin52
7
5
KESIMPULAN
Berdasarkan algoritma yang telah dibuat beserta uji coba yang telah dilakukan, maka dapat ditarik kesimpulan sebagai berikut. 1. Implementasi metode RABNET-TSP dalam memecahkan permasalahan TSP telah berhasil dilakukan seperti yang ditunjukkan pada bab uji coba. 2. Solusi optimal RABNET-TSP dalam memecahkan permasalahan TSP dapat dilakukan dengan mengubah nilai parameter alfa, sigma, etha, dan lambda seperti yang ditunjukkan pada bab uji coba. 3. Dari hasil uji coba menunjukkan bahwa perubahan parameter alfa dan lambda dapat menghasilkan solusi optimal yang paling mencolok, sedangkan perubahan pada parameter sigma dan etha kurang begitu terlihat.
REFERENSI [1] Rahman, Nur Kholes. Penerapan Algoritma Genetika Void Vertex Dengan Model Traveling Salesman Problem Yang Tergeneralisasi Dalam Distribusi Rantai Pasok. Surabaya : s.n., 2008. [2] RABNET: A Real-Valued Antibody Network for Data Clustering. Knidel, Helder, de Castro, Leandro N. and Zuben, Fernando J. Von. Washington DC. : s.n., 2005, pp. 371-372. [3] A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem. Masutti, Thiago A.S. and de Castro, Leandro N. Sao Paulo : Science Direct, 2009, Information Sciences, pp. 1454– 1468. [4] A Neuro-Immune Network for Solving the Traveling Salesman Problem. Pasti, Rodrigo and de Castro, Leandro Nunes. Vancouver : s.n., 2006, International Joint Conference on Neural Networks, pp. 3760-3766.
.
8
