PENERAPAN HYBRID DISCRETE CAT SWARM OPTIMIZATION (DCSO) DAN SIMULATED ANNEALING (SA) UNTUK MENGOPTIMALKAN TRAVELLING SALESMAN PROBLEM (TSP)
| Main Author: | GREGORIUS YOGA DARU NARENDRA, 081211232046 |
|---|---|
| Format: | Thesis NonPeerReviewed Book |
| Bahasa: | ind |
| Terbitan: |
, 2016
|
| Subjects: | |
| Online Access: |
http://repository.unair.ac.id/45345/1/ABSTRAK.pdf http://repository.unair.ac.id/45345/2/MPM.%20103-16%20Nar%20p.pdf http://repository.unair.ac.id/45345/ http://lib.unair.ac.id |
Daftar Isi:
- Travelling Salesman Problem (TSP) diteliti sejak abad ke-19, TSP merupakan salah satu masalah yang dikenal dalam penelitian operasional. Persoalan ini muncul di berbagai aplikasi seperti telekomunikasi, elektronik, logistik, transportasi, astronomi, industri, dan sebagainya. Permasalahan TSP (Traveling Salesman Problem) adalah permasalahan dimana seorang salesman harus mengunjungi semua kota dimana tiap kota hanya dikunjungi sekali, dan dia harus mulai dari dan kembali ke kota asal. Tujuannya adalah menentukan rute dengan jarak tempuh atau biaya total yang minimum. CSO (Cat Swarm Optimization) merupakan algoritma optimasi yang modelnya berupa perilaku alami kucing. Perilaku ini digambarkan dalam dua submodel yaitu seeking mode dan tracing mode. Discrete CSO adalah CSO yang menggunakan pengkodean bilangan bulat (integer). Simulated Annealing merupakan metode yang diusulkan di Kirkpatrick, dkk (1983) dan Cerny (1985) untuk menemukan minimum global suatu fungsi biaya yang mungkin memiliki solusi yang minimum lokal. Ia bekerja dengan meniru proses fisika dimana zat padat secara perlahan didinginkan sehingga ketika akhirnya struktur beku ini terjadi pada konfigurasi energi minimum. Karena solusi yang dihasilkan algoritma discrete CSO memungkinkan terjebak dalam kondisi optimum lokal, dan SA mampu menemukan minimum global suatu solusi yang minimum lokal, maka pada skripsi ini permasalahan TSP akan diselesaikan dengan menggabungkan (hybrid) kedua algoritma antara discrete CSO dan SA. Proses hybrid dilakukan dengan melakukan proses SA setelah iterasi DCSO dilakukan kecuali pada iterasi terakhir. Proses Hybrid Discrete Cat Swarm Optimization dan Simulated Annealing diawali dengan inisialisasi parameter, input data, selanjutnya seeking mode dan tracing mode. Hasil dari Discrete Cat Swarm Optimization yang terburuk akan diproses dengan algoritma Simulated Annealing. Data yang digunakan adalah data sedang berukuran 29 kota di Western Sahara dan data besar berukuran 100 kota TSPLIB Problem A oleh Krolak,dkk (2015) diselesaikan dengan bahasa pemrograman C++ menggunakan software Borland C++. Fungsi tujuan (jarak) minimum terbaik berdasarkan dari hybrid DCSO dan SA didapatkan untuk data 29 kota di Western Sahara sebesar 270699 satuan panjang, sedangkan untuk data 100 kota Problem-A diperoleh jarak minimum sebesar 153270 satuan panjang.