ALGORITMA ANT COLONY OPTIMIZATION (ACO) UNTUK MENYELESAIKAN TRAVELING SALESMAN PROBLEM (TSP)

BAB I
PENDAHULUAN

1.1    Latar Belakang
Traveling Salesman Problem (TSP) dikenal sebagai salah satu masalah optimasi yang banyak menarik perhatian para peneliti sejak beberapa dekade terdahulu. Pada mulanya, TSP dinyatakan sebagai permasalahan dalam mencari jarak minimal sebuah tour tertutup terhadap sejumlah n kota dimana kota-kota yang ada hanya dikunjungi sekali dengan kota awal juga merupakan kota akhir (tujuan). Meskipun TSP sepertinya mudah dinyatakan, akan tetapi sangat sulit untuk diselesaikan terutama untuk persoalan dengan jumlah kota yang banyak. Sampai saat ini belum ada suatu metode eksak yang dapat menjamin keberbhasilan nilai optimal untuk sebarang masalah dalam Polynomial computation time. TSP dikarakteristikan kedalam kelas NP-hard (Nondeterministik Polynomial – hard). Berdasarkan hal tersebut, banyak peneliti lebih memusatkan kepada pengembangan metode-metode pendekatan (heuristic) seperti simulated annealing, algoritma semut (Ant Algorithm), Algoritma Genetika, Tabu search, dan lain sebagainya.
Pada perkembangannya, ternyata TSP merupakan persoalan yang banyak diaplikasikan pada berbagai persoalan dunia nyata. Hingga saat ini, TSP diaplikasikan pada persoalan perencanaan pembangunan, perencanaan produksi, rute pengambilan surat dari kotak pos, rute pengisian uang pada mesin ATM, rute patroli polisi, rute pesawat terbang dsb.
Ant Colony Optimization (ACO) diadopsi dari perilaku koloni semut yang dikenal sebagai system semut (Dorigo, M., dan Gambardella, L., 1996). Secara alamiah koloni semut mampu menemukan rute terpendek dalam perjalanan dari sarang ke tempat-tempat sumber makanan. Koloni semut dapat menemukan rute terpendek antara sarang dan sumber makanan berdasarkan jejak kaki pada lintasan yang telah dilalui. Semakin banyak semut yang melalui suatu lintasan, maka akan semakin jelas bekas jejak kakinya. Hal ini akan menyebabkan lintasan yang dilalui semut dalam jumlah sedikit, semakin lama akan semakin berkurang kepadatan semut yang melewatinya, atau bahkan akan tidak dilewati sama sekali. Sebaliknya, lintasan yang dilalui semut dalam jumlah banyak, semakin lama akan semakin bertambah kepadatan semut yang melewatinya, atau bahkan semua semut akan melalui lintasan tersebut.
Pada ACO setiap semut ditempatkan di semua titik graph (dalam hal ini titik – titik yang dikunjungi) yang kemudian akan bergerak mengunjungi seluruh titik. Setiap semut akan membuat jalur masing – masing sampai kembali ketempat semula dimana mereka ditempatkan pertama kali. Jika sudah mencapai keadaan ini, maka semut telah menyelesaikan sebuah siklus (tour). Solusi akhir adalah jalur terpendek dari seluruh jalur yang dihasilkan oleh pencarian semut tersebut.
Mengingat prinsip algoritma yang didasarkan pada perilaku koloni semut dalam menemukan jarak perjalanan paling pendek tersebut, ACO sangat tepat digunakan untuk diterapkan dalam penyelesaian masalah optimasi, salah satunya adalah untuk menentukan jalur terpendek pada permasalahan TSP.
Berdasarkan uraian diatas, saya berkeinginan untuk membangun sebuah applikasi dalam pemasaran agar usaha tersebut akan lebih dikenal diluar daerahnya. Oleh karena itu, saya  mengajukan judul Skripsi yakni:“ALGORITMA ANT COLONY OPTIMIZATION (ACO) UNTUK MENYELESAIKAN TRAVELING SALESMAN PROBLEM (TSP)”


1.2. Rumusan masalah
Travelling Salesman Problem termasuk ke dalam masalah NPhard (Nondeterministik Polynomial – hard), sehingga sangat sulit untuk mencari solusi dari masalah ini dengan pendekatan eksak. Untuk menyelesaikan TSP digunakan pendekatan secara heuristic. Salah satu metode heuristic yang dikenal adalah Algoritma Ant Colony Optimization. Permasalahan dari penulisan Tugas Akhir ini adalah mengetahui bagaimana performa dari algoritma – algoritma ACO (Ant system, Elitist Ant System, Rank Based Ant System, Max-Min Ant System, dan Ant Colony System) untuk menyelesaikan TSP simetrik dan mengetahui manakah yang terbaik diantara algoritma tersebut.

1.3. Hipotesa
Algoritma ACO telah banyak diaplikasikan dalam berbagai bidang yang mencakup beberapa persoalan, yaitu :
1 Traveling Salesman Problem (TSP), yaitu mencari rute terpendek dalam sebuah graph menggunakan rute Hamilton.
2. Quadratic Assignment Problem (QAP), yaitu menugaskan sejumlah n resources untuk ditempatkan pada sejumlah m lokasi dengan meminimalisasi biaya penugasan (assignment).
3. Job-shop Scheduling Problem (JSP) juga salah satu contoh aplikasi Ant Colony Optimization, yaitu untuk mencari lintasan sejumlah n pekerjaan menggunakan sejumlah m mesin demikian sehingga seluruh pekerjaan diselesaikan dalam waktu yang seminimal mungkin.

1.4 Batasan Masalah
    Dalam tugas akhir ini masalah hanya akan dibatasi sebagai berikut :
1. Algoritma ACO yang dibandingkan adalah Ant System, Elitist Ant
     System, Rank-Based Ant System, Max-Min Ant System, dan Ant Colony System.
2. Permasalahan yang dibandingkan dalam semua algoritma adalah masalah Travelling Salesman Problem (TSP) Simetrik Euclidean dimana jarak antar 2 kota dan sebaliknya dianggap sama.

1.5 Tujuan Penelitian   
    Adapun Tujuan dari penelitian ini adalah
1. Menerapkan konsep dan cara kerja algoritma Ant Colony Optimization (ACO) untuk menyelesaikan masalah Travelling Salesman Problem (TSP).
2. Mengetahui perbandingan Algoritma Ant system, Elitist Ant System, Rank Based Ant System, Max-Min Ant System, dan Ant Colony System,dalam menyelesaikan TSP Simetrik.

Posted by: Induaksamang

Tips dan Triks rahasia, Updated at: 22:58