ABSTRAK
Traveling Salesman Problem (TSP) 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 Algoritma Genetika (AG). AG adalah sebuah metode yang dapat menghasilkan solusi dan waktu yang optimal. Meskipun AG 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 AG. Sistem tersebut akan dijalankan pada Microsoft – Message Passing Interface (MPI) menggunakan Algoritma Genetika Paralel agar menghasilkan komplesitas waktu yang optimal.
Pada penelitian ini digunakan metode Algoritma Genetika Paralel dengan MPI yang akan diterapkan pada studi kasus TSP untuk 101 kota. Metode ini merupakan sebuah sistem untuk menangani masalah waktu pada GA saat jumlah kota di TSP bertambah dengan cara memparalelkan proses perhitungan fitness menggunakan fungsi Send dan Recv MPI yang akan dilakukan pada slave node. Untuk proses inisialisasi, crossover, mutasi dan elitisme dilakukan pada master node. Metode ini mampu bekerja optimal saat jumlah populasi bertambah, dimana nilai probabilitas crossover dan mutasi konstan pada setiap generasi.
Hasil observasi menunjukan bahwa performa Algoritma Genetika Paralel lebih baik daripada Algoritma Genetika Serial. Algoritma Genetika Paralel 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 Algoritma Genetika Serial 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.