Algoritma Genetika dengan Pendekatan Model Pulau pada Permasalahan Travelling Salesman

Abstract

Algoritma genetika telah banyak digunakan untuk menyelesaikan permasalahan-permasalahan susah (hard problem) atau permasalahan NP-Complete karena sifatnya yang heuristik dan mampu menghasilkan solusi yang optimal dalam waktu yang relatif cepat. Performansi dari algoritma genetika dalam menyelesaikan permasalahan tersebut dilihat dari seberapa cepat algoritma genetika mencapai solusi yang optimal atau seberapa luas penjelajahan algoritma genetika dalam ruang solusi yang luas (tingkat diversitas yang tinggi).

Algoritma genetika dengan pendekatan model pulau merupakan pendekatan paralel dimana beberapa instan algoritma genetika dijalankan secara bersamaan untuk menjelajahi ruang solusi mencari solusi optimal. Dengan menggunakan model pulau, algoritma genetika bisa dikembangkan lebih lanjut dalam hal peningkatan diversitas individu dalam populasi. Diversitas yang tinggi bisa meningkatkan peluang algoritma genetika untuk mendapatkan solusi yang paling optimal atau global optimum.

Di dalam penelitian ini digunakan studi kasus permasalahan travelling salesman untuk membandingkan algoritma genetika dengan konfigurasi jumlah pulau dan metode pertukaran informasi antar pulau yang berbeda. Kontribusi dari penelitian ini adalah untuk menghasilkan korelasi antara jumlah pulau yang digunakan dengan performansi algoritma genetika.