Analisis dan Implementasi Algoritma Water Drops pada permasalahan Travelling Salesman Problem

Haffiz Anugragiri

Informasi Umum

Kode

113081126

Klasifikasi

518.172 - Algorithm-Research Methods

Jenis

Karya Ilmiah - Skripsi (S1) - Reference

Subjek

Salesman

Dilihat

312 kali

Informasi Lainnya

Abstraksi

Algoritma Intellgient WaterDrops (IWD) merupakan algoritma optimasi tipe swarm-based yang diinspirasi oleh fenomena sekumpulan tetesan air (water drops) yang bergabung dan membentuk aliran air yg cukup besar disebuah sungai. Aliran air ini lalu menyelusuri sungai dari tepian ke tepian hingga membentuk satu rute perjalanan Algoritma ini merupakan salah satu algoritma yang transpirasi dari alam yang memiliki performa mengesankan pada permasalahan optimasi kontinu, seperti masalah kombinatorial Travelling salesman problem (TSP).<br> Didalam algoritma IWD, terdapat beberapa elemen penting yang mempengaruhi jalannya aliran air, yaitu Velocity dan Soil. Kedua elemen ini saling bekerja sama dengan aliran air (water drops) sehingga dapat merubah lingkungan di sekitarnya, hingga water drops tersebut tiba di akhir tujuan. Dari mekanisme inilah diketahui sungai - sungai mencari path optimum tergantung kondisi dari lingkungan sekit arnya untuk menuju tujuan akhir atau lautan. Mekanisme inilah yang merupakan kelebihan dari algoritma IWD agar dapat menemukan path dengan lebih cepat dan optimum dibandingkan dengan algortima lain.<br> Pada tugas akhir ini, data yang digunakan adalah empat dataset yang masing – masing berisi 51,70,75 dan 100 kota. Dari hasil pengujian menunjukkan IWD dapat bekerja dengan baik pada TSP dan solusi yang didapatkan menunjukkan solusi sudah mendekati nilai optimum dengan akurasi diatas 96%.<br> Travelling Salesman Problem , Intelligent Water drops , NP-Complete, solusi optimum