ABSTRAKSI: Saat ini sudah tersedia teknologi yang memungkinkan programmer untuk menggunakan sumber daya GPU untuk melakukan pengolahan data pada aplikasi non-grafis secara parallel. Hal ini dapat dimanfaatkan untuk menangani kalkulasi data yang besar seperti yang terdapat pada permasalahan Traveling Salesman Problem (TSP). Algoritma Genetika sangat tepat digunakan untuk penyelesaian masalah optimasi yang kompleks dan sukar diselesaikan dengan menggunakan metode konvensional seperti TSP. Namun agar solusi yang diperoleh merupakan solusi yang mendekati solusi terbaik, kita harus bisa menentukan desain dan konfigurasi yang sesuai pada Algoritma Genetika yang digunakan.
Tugas akhir ini membahas mengenai penerapan Algoritma Genetika parallel pada GPU dalam menyelesaikan TSP. Dari hasil pengujian, dapat dianalisa bahwa penerapan model Master-Slave GA secara umum memiliki peningkatan performa yang lebih baik dibandingkan dengan pemodelan Multiple-Deme GA, baik dari segi waktu pencarian maupun hasil pencarian.
Kata Kunci : Algoritma Genetika, Parallel, TSP, CUDA, GPU.ABSTRACT: Nowadays, there is a technology that allows programmers to use GPU resources to perform data processing on non-graphics applications in parallel. This technology can be used to handle such a huge data calculation like Traveling Salesman Problem (TSP). Genetic Algorithm is really suitable to handle complex optimation problems like TSP which is really hard to be solved only with conventional methods. However to obtain solution which approximates the best solution, we have to determine proper design and configuration of the Genetic Algorithm used.
This final project discusses about the application of parallel Genetic Algorithm on the GPU to solve the TSP. From the test results, it can be analyzed that the implementation of Master-Slave GA generaly has a better performance improvement compared with Multiple-Deme GA, both in terms of search time and search results.
Keyword: Genetic Algorithm, Parallel, TSP, CUDA, GPU.