BAB 4 IMPLEMENTASI DAN EVALUASI
4.1
Implementasi
4.1.1
Spesifikasi Perangkat Keras Spesifikasi perangkat keras minimum yang diperlukan untuk dapat menjalankan
aplikasi adalah sebagai berikut. a.
Processor Pentium IV
b.
Mouse dan Keyboard
c.
RAM 512 MB
d.
Graphic Card/VGA Card dengan memory minimum 64 MB dengan resolusi minimum 1024x768
e.
Monitor SVGA
4.1.2
Spesifikasi Perangkat Lunak Spesifikasi perangkat lunak yang dibutuhkan untuk dapat menjalankan aplikasi
adalah sebagai berikut. a.
Operating System Windows XP ke atas
b.
Java SE 6 Runtime
c.
Aplikasi penyelesaian TSP yang dibuat
49 4.1.3 Cara Penggunaan Aplikasi Pada saat aplikasi penyelesaian TSP dijalankan, aplikasi akan langsung masuk ke layar utama.
Gambar 4.1 Tampilan layar menu utama Konfigurasi untuk algoritma genetik dan tabu search terdapat pada layar menu utama, nilai-nilai parameter yang terdapat pada layar ini merupakan nilai default yang dapat diganti oleh user. Tombol Open File digunakan untuk membuka file yang mengandung masalah TSP yang ingin diselesaikan, sedangkan tombol TSP Maker akan mengaktifkan fungsi pembuatan masalah TSP. Tombol Run akan menjalankan kedua algoritma (algoritma genetik dan tabu search) sekaligus, untuk melakukan perbandingan antar keduanya. Tombol About menampilkan informasi tentang pembuat program dan tombol Exit akan menghentikan program.
50 4.1.3.1 Tombol Open File Setelah user mengklik tombol Open File pada layar utama, maka akan ditampilkan dialog berikut untuk membuka file yang mengandung permasalahan TSP.
Gambar 4.2 Tampilan dialog Open File Setelah file TSP dibuka maka permasalahan TSP dapat segera dijalankan dengan cara mengklik tombol Run.
4.1.3.2 Tombol TSP Maker Jika user ingin membuat permasalahan TSP, hal ini dapat dilakukan dengan cara mengklik tombol TSP Maker dari layar utama untuk menampilkan layar TSP Maker.
51
Gambar 4.3 Tampilan layar TSP Maker Pada layar ini user dapat dengan bebas membuat permasalahan TSP, dengan menentukan path untuk masalah TSP sesuai keinginannya dengan cara meng-klik layar TSP Maker. User dapat pula membuat kota-kota secara acak yaitu dengan menekan tombol Randomize, dimana setelah tombol ini diklik akan muncul sebuah dialog untuk menanyakan berapa jumlah kota yang ingin dimasukkan.
52
Gambar 4.4 Tampilan dialog untuk menanyakan jumlah kota yang dimasukkan Setelah user memasukkan jumlah kota, maka kota-kota akan dibuat secara acak seperti yang terlihat pada Gambar 4.5 berikut ini.
Gambar 4.5 Hasil dari pengacakan kota
53 Jika tombol Save File diklik, maka akan ditampilkan dialog untuk menyimpan permasalahan TSP yang dibuat ke dalam file TSP.
Gambar 4.6 Tampilan dialog penyimpanan file Setelah file disimpan, sebuah dialog akan ditampilkan untuk memberitahukan user bahwa file tersebut telah disimpan.
Gambar 4.7 Tampilan dialog sebagai informasi bahwa file telah disimpan
54 Jika user mengklik tombol Open File maka akan ditampilkan dialog buka file untuk membuka file TSP yang telah disimpan (seperti pada Gambar 4.2). Sedangkan tombol Erase digunakan untuk menghapuskan semua kota-kota yang telah dibuat di layar TSP Maker.
Gambar 4.8 Tampilan layar TSP Maker setelah semua kota dihapus
55 4.1.3.3 Tombol Run Apabila user menekan tombol Run pada layar utama, maka program akan menjalankan kedua algoritma TSP pada permasalahan TSP yang telah dibuat, yang ditampilkan di layar TSP Result seperti pada Gambar 4.9 berikut.
Gambar 4.9 Tampilan layar TSP Result Setelah program berhasil menyelesaikan permasalahan TSP tersebut, hasilnya akan ditampilkan pada layar beserta dengan jumlah jaraknya pada textbox yang tersedia.
56
Gambar 4.10 Hasil akhir setelah menyelesaikan TSP
4.1.3.4 Tombol About Jika tombol About diklik oleh user, maka dialog mengenai keterangan pembuat program akan ditampilkan ke layar.
Gambar 4.11 Dialog About
57 4.1.3.5 Mode non-interaktif (tanpa GUI) Mode ini digunakan untuk mengukur kinerja program. Karena jika menggunakan mode interaktif, dua algoritma akan dikerjakan pada waktu yang bersamaan. Hal ini disebabkan oleh penggunaan multi-thread pada program, yang dilakukan agar tampilan grafis program responsif dan nyaman untuk digunakan oleh user. Sintaks untuk penggunaan mode non-interaktif adalah sebagai berikut: Java –jar “TSP Solver”.jar –help untuk menampilkan petunjuk sintaks yang benar. Java –jar “TSP Solver”.jar –nogui ga filekonfigurasi filetsp untuk menjalankan algoritma genetik. Java –jar “TSP Solver”.jar –nogui ts filekonfigurasi filetsp untuk menjalankan algoritma tabu search. File konfigurasi merupakan file teks. Format file konfigurasi untuk algoritma genetik adalah sebagai berikut: •
persilangan (range [0.00 .. 1.00])
•
mutasi (range [0.00 .. 1.00])
•
elitisme (range [0.00 .. 1.00])
•
populasi (range >= 2)
•
generasi (range >=10) Sedangkan format file konfigurasi untuk algoritma tabu search adalah sebagai
berikut: •
panjang_memori (range >=1)
•
jumlah_solusi_baru (range >=5)
•
jumlah_pembaharuan_solusi (range >=10)
•
probabilitas_pemilihan_solusi (range [0.00 .. 1.00])
58 Untuk file TSP, format yang digunakan adalah sebagai berikut: 136 175 178 105 221 45 263 100 ... xn yn Dimana angka-angka tersebut merupakan nilai-nilai koordinat x dan y.
4.2
Analisis Dan Evaluasi Dengan menggunakan aplikasi TSP Solver ini kemudian dilakukan evaluasi
performa dari kedua algoritma TSP yang dibahas, yaitu algoritma genetik dan tabu search. Pengevaluasian dilakukan dengan menggunakan mode non-interaktif dan dilakukan sebanyak 10 kali untuk setiap parameter. Lalu kemudian dari hasil tersebut akan dihitung rata-ratanya, standar deviasi, nilai minimum dan nilai maksimum. Tabel 4.1 berikut merupakan parameter yang digunakan pada kedua algoritma dalam proses pengujian. Tabel 4.1
Tabel parameter algoritma pada pengujian
Parameter Tabu Search Panjang Memori Jumlah Solusi Baru Jumlah Pembaharuan Solusi Probabilitas Pemilihan Solusi
Nilai 10 15 50 0.85
Parameter Algoritma Genetik Persilangan Mutasi Elitisme Populasi Generasi
Nilai 0.85 0.02 0.1 50 500
59 Hasil parameter jarak dan waktu untuk menyelesaikan masalah TSP yang berbentuk lingkaran dapat dilihat pada Tabel 4.2 berikut. Tabel 4.2 Jumlah Kota 10 20 50 100 150
Tabel hasil penyelesaian dengan menggunakan algoritma genetik
Ratarata 1002.5010 1472.3279 5212.2694 13237.3093 22178.1522
Jarak Standar Min Deviasi 0.0000 1002.5010 79.88 1428.1993 311.7513 4755.4202 452.1028 12704.6625 1128.9202 20656.4847
Max 1002.5010 1634.4827 5682.3978 14246.2922 24227.3026
Waktu (detik) Standar Min Rata-rata Deviasi 0.4266 0.0456 0.39 0.5875 0.0182 0.563 1.264 0.0365 1.203 2.6671 0.0293 2.625 4.4532 0.0879 4.375
Max 0.547 0.61 1.344 2.718 4.594
Dapat dilihat pada Tabel 4.2 diatas bahwa algoritma genetik dapat menyelesaikan TSP dengan hasil yang cukup memuaskan. Sedangkan hasil dari tabu search dapat dilihat pada Tabel 4.3 berikut. Tabel 4.3 Jumlah Kota 10 20 50 100 150
Ratarata 1002.5010 1428.1993 3369.6129 7225.4913 11993.6681
Tabel hasil penyelesaian dengan algoritma Tabu Search Jarak Standar Min Max Deviasi 0.0000 1002.5010 1002.5010 0.0000 1428.1993 1428.1993 190.6077 2972.3161 3650.2454 393.0821 6777.0961 7700.6870 501.7873 11448.9353 12619.8536
Waktu (detik) Standar Min Max Rata-rata Deviasi 0.3284 0.0165 0.297 0.358 2.1906 0.3058 1.921 2.703 27.7295 0.4340 27.234 28.468 215.2126 11.0269 206.859 233.672 695.7598 28.2194 657.375 722.524
Dapat dilihat dari Tabel 4.3 di atas bahwa pada konfigurasi standar algoritma Tabu Search memberikan hasil yang lebih baik, walaupun memiliki kinerja yang sangat lambat. Jika jumlah solusi baru dan jumlah pembaharuan solusi pada tabu search dinaikkan, maka akan didapatkan hasil yang lebih baik lagi, namun kinerjanya juga akan menjadi jauh lebih lambat.
60 Tabel 4.4
Tabel parameter Tabu Search pada pengujian Nilai
Parameter Tabu Search 50 Kota (I)
50 Kota (II)
Panjang Memori
15
40
Jumlah Solusi Baru
20
20
Jumlah Pembaharuan Solusi
100
100
Probabilitas Pemilihan Solusi
0.85
0.85
Tabel 4.5 Tabel hasil penyelesaian dengan algoritma Tabu Search Jumlah Kota 50 (I) 50 (II)
Jarak Waktu (detik) Rata- Standar RataStandar Min Min Max rata Deviasi rata Deviasi 2309.0490 597.3461 1505.7556 2918.4207 80.3315 1.9972 78.11 2732.3853 405.7995 2124.2826 3217.7465 83.927 1.0131 82.68
Max 83.114 85.17
Tabel 4.5 menunjukkan hasil dari penggunaan Tabu Search dengan file konfigurasi yang telah dioptimisasi. Dapat dilihat bahwa hasil yang diperoleh jauh lebih baik dibandingkan dengan konfigurasi standar, namun memakan waktu yang jauh lebih lama (dari 27 detik menjadi 80 detik). Panjang memori juga mempengaruhi hasil dari tabu search, jika memori terlalu besar (seperti pada tabel 4.4 (II)) hasil yang didapatkan akan menjadi lebih buruk. Hal ini disebabkan karena tabu search lebih susah mendapatkan solusi baru yang lebih baik, namun solusi tersebut tidak valid karena masih tabu. Walaupun di tabu search ada aspiration criterion, tapi hal itu berlaku hanya untuk solusi baru yang lebih baik daripada solusi terbaik. Jika solusi baru x lebih baik dari solusi awal tetapi tidak lebih baik daripada solusi terbaik dan solusi baru tersebut adalah tabu, maka solusi x tidak akan terpilih. Dan jika solusi baru y dibuat dari solusi x dan solusi y lebih baik daripada solusi terbaik, solusi y tidak akan pernah terpilih, karena solusi x telah ditolak karena solusi x adalah tabu.
61 Jika jumlah populasi dan generasi dinaikkan, maka algoritma genetik akan mendapatkan hasil yang lebih baik. Namun efek samping dari ini adalah kinerja algoritma yang akan semakin lambat. Tabel 4.6
Tabel parameter algoritma genetik
Parameter Algoritma Genetik Persilangan Mutasi Elitisme Populasi Generasi
Nilai 0.85 0.05 0.2 80 1250
Tabel 4.7 Tabel hasil penyelesaian dengan algoritma genetik Jumlah Kota 10 20 50 100 150
Ratarata 1002.5010 1428.1993 2848.8559 6732.5900 12950.0006
Jarak Standar Min Deviasi 0.0000 1002.5010 0.0000 1428.1993 549.1940 2022.5237 453.2899 5982.2119 575.2342 11942.3275
Max 1002.5010 1428.1993 3554.2933 7353.0214 13776.1633
Waktu (detik) Standar Min Max Rata-rata Deviasi 2.0060 0.0869 1.9220 2.1520 3.0616 0.1657 2.8920 3.2970 6.2456 0.1377 5.9890 6.4350 13.6000 0.1810 13.2970 13.8750 23.5875 0.2527 23.3030 24.1000
Tabel 4.8 Tabel parameter algoritma genetik Parameter Algoritma Genetik Persilangan Mutasi Elitisme Populasi Generasi
Nilai 0.85 0.02 0.2 100 2000
Tabel 4.9 Tabel hasil penyelesaian dengan algoritma genetik Jumlah Kota 50 100 150
Ratarata 2007.9894 5449.1783 10606.2237
Jarak Standar Min Max Rata-rata Deviasi 509.3398 1539.8290 2835.7351 12.8064 390.1659 4603.3011 5858.0162 31.6021 379.2171 10203.9431 11362.2801 45.1716
Waktu (detik) Standar Min Max Deviasi 0.2138 12.3680 13.1740 0.4069 31.0580 32.4000 0.4607 44.5780 45.7120
Berikut ini penyelesaian dari kedua algoritma dengan menggunakan kota yang dibuat secara melingkar, dengan parameter seperti pada Tabel 4.6 dan Tabel 4.8.
62
Gambar 4.12 Gambar penyelesaian untuk 10 kota
Gambar 4.13 Gambar penyelesaian untuk 20 kota.
63
Gambar 4.14 Gambar penyelesaian untuk 50 kota (konfigurasi tabel 4.4(I) dan 4.6).
Gambar 4.15 Gambar penyelesaian untuk 150 kota (konfigurasi tabel 4.8).
64 Dari hasil diatas dapat dilihat untuk jumlah kota yang besar (150 kota) baik algoritma genetik maupun tabu search tidak memberikan hasil yang 100 persen optimal. Namun algoritma genetik memberikan hasil yang lebih baik jika dibandingkan dengan hasil yang diberikan oleh tabu search dan waktu yang diperlukan jauh lebih cepat. Jika jumlah populasi, generasi dan elitisme pada algoritma genetik dinaikkan, maka hasil yang didapatkan akan jauh lebih baik tetapi proses penyelesaiannya sendiri akan menjadi sangat lama. Dari hasil-hasil pengujian dapat dilakukan analisis sebagai berikut. 1. Jumlah solusi baru dan jumlah pembaharuan solusi sangat mempengaruhi kinerja tabu search. Jumlah solusi baru dan pembaharuan solusi yang besar selain menghasilkan hasil yang lebih baik, juga memakan waktu lebih lama untuk menyelesaikan permasalahan. 2. Jumlah anggota populasi dan generasi di dalam algoritma genetik juga memiliki pengaruh serupa terhadap hasil dan waktu penyelesaian. 3. Persentase elitisme pada algoritma genetik sangat mempengaruhi kualitas hasil. Semakin tinggi persentase elitisme, maka hasilnya akan semakin baik. Tetapi nilai persentase elitisme yang terlalu tinggi juga akan memperburuk hasil. 4. Kinerja Tabu Search sangat buruk untuk jumlah kota yang besar. Hal ini disebabkan oleh cara kerja Tabu Search itu sendiri, dimana Tabu Search menggunakan algoritma 2-opt untuk mencari nilai lokal optimum. Jika jumlah kota besar, maka Tabu Search akan memakan waktu sangat lama untuk mencari nilai yang optimum dari kota-kota tersebut (notasi Big-Oh untuk 2-opt adalah O(n2)). 5. Sedangkan algoritma genetik bekerja dengan jauh lebih cepat karena algoritma genetik tidak memakai algoritma 2-opt untuk mencari nilai optimum. Jumlah iterasi
65 pada algoritma genetik ditentukan oleh jumlah populasi dan jumlah generasi. Jika konfigurasi algoritma genetik dioptimalkan, maka hasil yang dicapai akan sangat baik. 6. Dari hasil analisis diatas dan pengamatan terhadap hasil yang diperoleh dapat disimpulkan bahwa jika ruang lingkup permasalahan termasuk kecil (10-20 kota), tabu search memiliki kecepatan kerja yang lebih baik. Namun jika ruang lingkup permasalahan lebih besar (50-150 kota), algoritma genetik bekerja lebih cepat dibandingkan tabu search (walaupun hasil yang didapatkan tidak begitu optimal).
