KOMPUTASI ALGORITME GENETIKA PARALEL PADA TRAVELING SALESMAN PROBLEM DENGAN COMPUTE UNIFIELD DEVICE ARCHITECTURE (CUDA)

SEAN COONERY SUMARTA, Noor Akhmad Setiawan, S.T., M.T., Ph.D.;Teguh Bharata Adji, S.T., M.T., M.Eng., Ph.D.

2015 | Tesis | S2 Teknik Elektro

Traveling Salesman Problem (TSP) merupakan permasalahan dalam bidang transportasi darat. Masalah dalam TSP yaitu mencari suatu lintasan terpendek yang dapat di tempuh dari titik awal (keberangkatan) menuju titik akhir (tujuan), dengan harapan biaya perjalanan yang dikeluarkan dan waktu tempuh perjalanan seminimum mungkin. Terdapat beberapa pendekatan yang dapat digunakan dalam mencari solusi optimum dalam menjawab masalah TSP, diantaranya Algoritme Genetika. Algoritme Genetika merupakan salah satu metode efektif untuk menyelesaikan TSP. Dalam prosesnya, Algoritme Genetika menghasilkan biaya evaluasi yang cukup besar. Biaya evaluasi yang dimaksudkan adalah proses komputasi yang lama. Ada beberapa teknik dalam menyelesaikan permasalahan dalam penyelesaian proses komputasi yang lama, salah satunya adalah komputasi paralel. Seiring dengan perkembangan dunia teknologi, komputasi paralel dapat dilakukan pada Graphic Processing Unit (GPU). NVIDIA dengan arsitektur CUDA (Compute Unified Device Architecture) telah memungkinkan pengembang memanfaatkan resource GPU dari NVIDIA untuk melakukan proses komputasi paralel. Tujuan penelitian ini adalah mengembangkan metode komputasi algoritme genetika paralel untuk mendapatkan waktu komputasi yang cepat dalam menyelesaikan masalah TSP. Metode komputasi algoritme genetika paralel yang dikembangkan adalah paralelisasi operator crossover dan mutasi. Operator crossover menggunakan metode heuristic crossover dan operator mutasi menggunakan metode inversion mutation. Hasil menunjukan waktu komputasi algoritme genetika paralel 6 sampai 9 kali lebih cepat dari waktu komputasi algoritme genetika serial dengan rata rata error akurasi sebesar 6 sampai 10 % dari berbagai data kasus TSP.

Traveling Salesman Problem (TSP) is a problem in the field of land transports. TSP problem is to find a shortest path that can be traveled from the starting point (departure) to the end of point (destination), which is expected to decrease the travel costs and travel time. There are some methods that can be used to find the shortest path for solving the TSP problem, such as genetic algorithm. Genetic algorithm is one of the effective methods, which can be used to solve TSP. Genetic algorithm requires a long computation time to find the shortest path on the TSP problem. There are some techniques to solve this problem, one of them is parallel computing. Recently , parallel computing can be performed on Graphic Processing Unit (GPU). NVIDIA with CUDA (Compute Unified Device Architecture) architecture has allowed developers to utilize the GPU for parallel computing. The objectives of this research is to develop a parallel genetic algorithm method to solve TSP problem with faster computation time. The parallel genetic algorithm method was developed in the stage of parallel crossover and mutation operators. The crossover operator uses heuristic crossover methods and the mutation operators uses inversion mutation method respectively. Results of this research shows that the parallel genetic algorithm computing time are 6 to 9 times faster than the serial genetic algorithm computing time, and the average error of accuracy is 6 to 10%.

Kata Kunci : Traveling Salesman Problem, Parallel Genetic Algorithm, Heuristic Crossover, Inversion Mutation, Graphic Processing Unit, Compute Unified Device Architecture.