Computer File
Penerapan algoritma viral systems untuk traveling salesman problem
Traveling Salesman Problem (TSP) merupakan salah satu contoh
pengambilan keputusan dimana dianalogikan dengan seorang salesman yang
harus melewati semua kota sebanyak satu kali dan kembali ke kota awal di mana
perjalanannya dimulai dengan jarak minimum. Semakin banyak kota yang harus
dilewati maka akan serna kin banyak pula kemungkinan solusi yang ada sehingga
menyebabkan TSP sulit diselesaikan secara manual. Beberapa metode optimasi
seperti Branch and Bound dan Dynamic Programming hanya sesuai diterapkan
untuk kasus ukuran kecil. Hal inilah yang menyebabkan munculnya pendekatan
dengan metode-metode heuristik, seperti Genetic Algorithm, Tabu Search, dll.
Viral Systems (VS) merupakan salah satu metode heuristik yang dapat
digunakan untuk menyelesaikan permasalahan kombinatorial dari skala sedang
hingga besar. VS terinspirasi oleh performansi kerja virus dalam menginfeksi sel.
Penelitian dilakukan untuk membuat model algoritma VS yang sesuai dengan
TSP, membandingkan performansi VS dengan Branch and Bound dan Genetic
Algorithm, dan mengetahui parameter-parameter apa saja yang berpengaruh
terhadap kasus yang diuji.
Dalam algoritma VS, virus akan menyerang sel yang memiliki genome
yang merupakan kode matematis dari solusi yang akan dicari. Genome terdiri
dari beberapa gen yang berisi angka dimana angka tersebut merupakan kota
yang akan dilalui. Jika ada n buah kota yang harus dilewati maka akan terbentuk
n + 1 gen dimana gen pertama dan gen terakhir memiliki angka yang sarna.
Sebagai contoh genome dengan urutan gen 1-2-3-4-5-1 memiliki arti bahwa
seorang salesman harus mengunjungi setiap kota dimulai dari kota pertama,
kedua, ketiga, keempat, kelima, dan diakhiri dengan kembali ke kota pertama.
Dari hasil penelitian didapatkan kesimpulan bahwa algoritma VS dapat
diterapkan pada TSP dengan kasus 5 dan 10 kota, namun tidak sesuai untuk
kasus 48 kota. Untuk kasus 5 kota, VS menghasilkan solusi optimal yaitu 668
miles sarna dengan metode Branch and Bound. Untuk kasus 10 kota dengan
kombinasi 1, VS menghasilkan solusi dengan jarak 161 dan untuk kombinasi 2,
VS menghasilkan solusi dengan jarak 157. VS menghasilkan solusi yang sama
baiknya dengan metode Branch and Bound dan Genetic Algorithm. Parameter-parameter
penelitian VS yang berpengaruh terhadap kasus 48 kota adalah LIT°,
Pr, Pi, kombinasi LIT° dan Pr, kombinasi Pr dan Pi, serta kombinasi LNR°, Pr, dan
Pi.
Barcode | Tipe Koleksi | Nomor Panggil | Lokasi | Status | |
---|---|---|---|---|---|
skp20352 | DIG - FTI | Skripsi | TI VAL p/10 | Perpustakaan | Tersedia namun tidak untuk dipinjamkan - Missing |
Tidak tersedia versi lain