Pencarian Rute Optimum Menggunakan Algoritma Genetika

Abstract

Genetic algorithm can be used to solve optimation problems, such as for finding optimal route, which may be influenced by many internal conditions. In this paper, genetic algorithm was implemented to search optimal route from the start point to the destination point. Genetic algorithm system was designed by using bit string - chromosome representation, thus the mutation used was bit mutation. The selection method used was roulette wheel, elitism and hybrid selection between roulette wheel and elitism. There were two kind of crossover points used - one and two cut point crossover. From the experiments, we could conclude that the genetic algorithm system design worked well and solved the optimation problems. Abstract in Bahasa Indonesia : 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. 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. Dari hasil pengujian, dapat disimpulkan bahwa secara keseluruhan, algoritma genetika yang telah didisain dapat berjalan dengan baik dan dapat menyelesaikan permasalahan. Kata kunci : algoritma genetika, kromoson, mutasi, seleksi, populasi, reproduksi.