NIM : D1041141039
NAMA : Lia Suci Fitriawati
Kasus : Implementasi AI dalam Kasus TSP (Traveling Salesman Problem)
Permasalahan :
Seorang salesman ingin mengunjungi sejumlah kota yang ada di Kalimantan Barat. Semua kota yang ada harus dikunjungi oleh salesman tersebut tanpa satupun kota yang terlewatkan.. Salesman mengunjungi seluruh kota yang ada dan kembali ke kota awal keberangkatan dengan aturan bahwa tidak boleh ada kota yang dikunjungi lebih dari satu kali.
Solusi :
Solusi dari permasalahan tersebut menggunakan algoritma Generate and Test (GT) yaitu pencarian rute terpendek dari semua jalur antar kota tersebut dengan aturan setiap kota hanya boleh dilewat satu kali. Generate and Test adalah sebuah metode dari beberapa konsep pencarian heuristik. Metode ini melakukan mekanisme kerja dengan cara membangkitkan atau generate kemungkinan solusi, kemudian melakukan pengujian atau test. Selama belum ditemukan solusi atau masih ada kemungkinan solusi maka akan terus dilakukan pencarian solusi. Jika ditemukan solusi maka berhasil, jika tidak maka gagal.
Algoritma dari metode Generate and Test ini adalah:
- Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal).
- Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.
- Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah yang pertama.
Pada kasus ini dapat dibuat sebuah konsep robot bersensor sonar dan warna yang dapat menyelesaikan TSP dengan metode Generate and Test. Robot dengan anatomi manusia ini memilki kemampuan self-recognizing atau dapat mengenali lingkungan dengan sendirinya. Dari kemampuan ini selanjutnya robot dapat diprogram sedemikian rupa hingga dapat menyelesaikan permasalahan TSP. Dari segi efektifitas, penggunaan metode Generate and Test dalam kasus ini dapat dikatakan cukup baik dimana secara teknis walaupun membutuhkan banyak iterasi bagi robot dalam membaca jarak dan lintasan namun masih dalam batasan sehingga tidak menyebabkan waktu yang lama untuk robot bekerja.
Referensi :
Ridho Rahmadi, Juni 2010, “Implementasi Metode Generate and Test dalam Menyelesaikan Travelling Salesman Problem Menggunakan Robot Bersensor Sonar dan Warna”, http://journal.uii.ac.id/index.php/Snati/article/download/1936/1711 , 13 November 2017.
Tidak ada komentar:
Posting Komentar