Algoritma Genetika (ag) Paralel Untuk Menyelesaikan Traveling Salesman Problem (tsp) Menggunakan Message Passing Interface (mpi)

Abstrak

Traveling Salesman Problem baik dikenal sebagai masalah penting optimasi kombinatorial. Tujuannya adalah untuk menemukan jalur terpendek dari sebuah kota awal ke kota tujuan yang setiap kota hanya boleh dilewati tepat satu kali kemudian kembali ke kota awal. Metode untuk memecahkan TSP salah satunya adalah Genetic Algorithm (GA). GA adalah sebuah metode yang dapat menghasilkan solusi dan waktu yang optimal. Meskipun GA adalah metode yang optimal dan pendekatan yang baik untuk TSP namun saat jumlah kota pada TSP meningkat waktu yang dibutuhkan akan semakin besar. Hal ini disebabkan karena perhitungan nilai fitness setiap generasinya akan semakin banyak setiap jumlah kota bertambah. Oleh karena itu akan dibuat sebuah sistem untuk menangani masalah tersebut dengan memparalelkan metode GA. Sistem tersebut akan dijalankan pada Microsoft – MPI menggunakan Parallel Genetic Algorithm agar menghasilkan komplesitas waktu yang optimal. Hasil observasi menunjukan bahwa performa Paralel AG lebih baik daripada Serial AG. Parallel AG pada TSP menghasilkan nilai jarak terpendek sebesar 4697,18 dan nilai fitness 0,000213 untuk penggunaan 100 generasi, ukuran populasi sebanyak 100, probabilitas crossover 0,9 dan probabilitas mutasi 0,1 dengan waktu yang dibutuhkan sebesar 1,67 detik. Sedangkan Serial AG pada TSP menghasilkan nilai jarak terpendek sebesar 4801,91 dan nilai fitness 0,000208 untuk penggunaan 100 generasi, ukuran populasi sebanyak 100, probabilitas crossover 0,9 dan probabilitas mutasi 0,1 dengan perhitungan waktu 5,04 detik.

Kata kunci : Traveling Salesman Problem, Genetic Algorithm, Microsoft Cluster