APLIKASI ALGORITMA GENETIKA UNTUK MENYELESAIKAN MASALAH TRAVELING SALESMAN PROBLEM (TSP)

SAKINATUL CHASANAH - NIM. 06610021, (2011) APLIKASI ALGORITMA GENETIKA UNTUK MENYELESAIKAN MASALAH TRAVELING SALESMAN PROBLEM (TSP). Skripsi thesis, UIN Sunan Kalijaga Yogyakarta.

Abstract

ABSTRAK Travelling Saleman Problem (TSP) merupakan persoalan optimasi klasik yang mengacu pada graf berarah yang bertujuan mencari sirkuit Hamilton dengan jarak terpendek atau tour perjalanan minimum. TSP termasuk dalam NP-Hard yaitu masalah yang dapat diselesaikan secara sempurna dengan waktu polinomial. Umumnya diselesaikan menggunakan metode Heuristik yang dapat menyelesaikan masalah dengan lebih sederhana untuk menyelesaikan masalah yang kompleks dengan hasil yang lebih variatif dan waktu perhitungannya lebih singkat. Di sini digunakan Algoritma Genetika yang merupakan salah satu metode Heuristik untuk menentukan perjalanan terpendek yang melalui kota lainnya hanya sekali dan kembali ke kota asal keberangkatan. Algoritma Genetika adalah suatu bentuk analogi dari Teori Evolusi Darwin dan Prinsip Genetika dalam Ilmu Biologi. Algoritma ini sangat tepat digunakan untuk penyelesaian masalah optimasi yang kompleks dan sukar diselesaikan dengan metode konvensional. Dalam skripsi ini ada dua contoh kasus (5 kota dan 8 kota) yang akan diselesaikan dengan Algoritma Genetika. Solusi yang diperoleh Algoritma Genetika tergantung pada penentuan operator dan parameter yang digunakan dalam Algoritma Genetika untuk menyelesaikan masalah. Operator genetika meliputi seleksi, crossover dan mutasi. Parameter meliputi ukuran populasi, jumlah generasi, probabilitas crossover dan probabilitas mutasi. Algoritma Genetika sebagai Algoritma Heuristik dapat melakukan suatu pencarian solusi untuk masalah TSP, tetapi karena dimulai dari solusi acak maka solusi yang dihasilkan tidak selalu merupakan solusi optimal. div

Share this knowledge with your friends :

Actions (login required)

View Item