PERBANDINGAN KINERJA OPERATOR PARTIALLY MAPPED CROSSOVER, CYCLE CROSSOVER, DAN ORDER CROSSOVER DALAM ALGORITMA GENETIKA PADA PENCARIAN RUTE TERPENDEK PERJALANAN WISATA

Abstract

ABSTRACT
Traveling Salesman Problem (TSP) or known as the Shortest Cross Search, is an optimization
problem that has many important applications in finding the best results in order to find a solution
of values that are close to optimal. One of the TSP cases is determining the distance to tourism
locations in Bali Province. In general, tourists prefer to travel independently because they can freely
determine their own travel destinations rather than using travel agents that require tourists to follow
the travel packages provided. Therefore, this study discusses the Comparison of Operators'
Performance Partially Mapped Crossover, Cycle Crossover, and Order Crossover in Genetic
Algorithms for Searching the Shortest Route of Travel Travel. The purpose of this research is to find
the best crossover technique so that it can optimize the process of distance traveled to tourism
locations in Bali Province. The route formation will be carried out by applying a genetic mutation
algorithm that is used is the inversion mutation in the optimum global search. The system built is
expected to optimize the process of tourist travel distance to every tourism location in Bali Province.
In conducting this research, the authors used the Operator Partially Mapped Crossover, Cycle
Crossover, and Order Crossover method and used Inversion Mutation. Based on the research
conducted, it can be concluded that in this study, the optimal value is obtained by applying the Cycle
Crossover type crossover. With the results in the form of the shortest distance of 153.9 km and the
computation time of 1.521929264 seconds for 8 cities. As well as the shortest distance of 229.1 km
with a computing time of 1.915934801 seconds for 12 cities. This shows the average results are
better when compared to 2 other types of crossovers, namely Partially Mapped Crossover and Order
Crossover.
Keywords : Traveling Salesman Problem, Genetic Algorithm, Operator Partially Mapped
Crossover, Cycle Crossover, Order Crossover, Inversion Mutation.
ABSTRAK
Travelling Salesman Problem (TSP) atau disebut dengan Pencarian Lintas Terpendek, merupakan
permasalahan optimasi yang mempunyai banyak terapan penting dalam pencarian hasil yang terbaik
dengan tujuan untuk mendapatkan solusi nilai-nilai yang mendekati optimal. Salah satu kasus TSP
adalah menentukan jarak tempuh lokasi pariwisata di Provinsi Bali. Secara umum, wisatawan lebih
suka bepergian secara mandiri karena mereka dapat dengan bebas menentukan tujuan wisata mereka
sendiri daripada menggunakan agen perjalanan yang mengharuskan wisatawan untuk mengikuti
paket perjalanan yang telah disediakan. Maka dari itu Penelitian ini membahas mengenai
Perbandingan Kinerja Operator Partially Mapped Crossover, Cycle Crossover, dan Order
Crossover dalam Algoritma Genetika pada Pencarian Rute Terpendek Perjalanan Wisata. Tujuan
dari penelitian ini adalah untuk menemukan teknik crossover yang paling baik sehingga dapat
mengoptimalkan proses jarak tempuh lokasi pariwisata di Provinsi Bali. Pembentukan rute akan
dilakukan dengan menerapkan algoritma genetika mutasi yang digunakan adalah Mutasi Inversion
320 Jurnal Teknologi Informasi dan Komputer, Volume 6, Nomor 3, Oktober 2020
pada pencarian global optimum. Sistem yang dibangun diharapkan dapat mengoptimalkan proses jarak tempuh travel wisatawan ke setiap lokasi pariwisata di Provinsi Bali. Dalam melakukan penelitian ini, penulis menggunakan metode Operator Partially Mapped Crossover, Cycle Crossover, dan Order Crossover serta menggunakan Mutasi Inversion. Berdasarkan penelitian yang dilakukan dapat disimpulkan bahwa pada penelitian ini, nilai optimal diperoleh dengan menerapkan Crossover jenis Cycle Crossover. Dengan hasil berupa jarak terpendek 153.9 km dan waktu komputasi selama 1.521929264 detik untuk 8 kota. Serta jarak terpendek sebesar 229.1 km dengan waktu komputasi selama 1.915934801 detik untuk 12 kota. Hal ini menunjukan rata-rata Hasil yang lebih baik jika dibadingkan 2 buah jenis crossover yang lain yaitu Partially Mapped Crossover dan Order Crossover. Kata kunci— Travelling Salesman Problem, Algoritma Genetika, Operator Partially Mapped Crossover, Cycle Crossover, Order Crossover, Mutasi Inversion