IMPLEMENTASI ALGORITMA GENETIKA UNTUK PENCARIAN RUTE PALING OPTIMUM

Abstract

Algoritma genetika dapat digunakan untuk menyelesaikan masalah optimasi yang kompleks seperti mencari rute paling optimum dengan memperhatikan kondisi jalan misalnya kepadatan lalulintas, jalan satu arah dan lain-lain. Dalam makalah ini akan dijelaskan tentang penerapan algoritma genetika untuk mencari rute yang paling optimum dari titik asal ke titik tujuan. Kriteria optimum disini adalah waktu dan jarak tempuh yang paling minimal dari titik asal ke titik tujuan dengan memperhatikan berbagai kondisi jalan seperti kepadatan lalulintas, jalan satu arah atau dua arah, juga syarat harus melalui titik tertentu. Sistem algoritma genetika yang telah didisain menggunakan representasi kromosom dalam bentuk bit string. Karena itu jenis mutasi yang digunakan adalah mutasi bit. Sistem ini juga menggunakan beberapa metode seleksi yaitu roulette wheel, elitism dan gabungan antara metode roulette wheel dan elitism. Ada dua jenis crossover yang digunakan yaitu one cut point crossover dan two cut point crossover. Beberapa pengujian telah dilakukan untuk menguji sistem ini. Pengujian dilakukan dengan variasi jumlah kromosom dalam satu populasi, variasi nilai crossover rate, variasi nilai mutation rate, variasi metode seleeksi dan variasi metode crossover. Dari hasil pengujian, dapat disimpulkan bahwa secara keseluruhan, algoritma genetika yang telah didisain dapat berjalan dengan baik dan dapat menyelesaikan permasalahan.