Analisis Panjang Populasi dan Banyak Generasi Algoritma Genetika pada Traveling Salesman Problem

Abstract

Abstrak. Traveling Salesman Problem (TSP) adalah masalah optimasi yang penting dalam bidang ilmu komputer dan matematika. Tujuan utama dari TSP adalah mencari rute terpendek yang melibatkan kunjungan ke sejumlah titik atau kota tertentu oleh seorang salesman. Algoritma Genetika (AG) telah menjadi salah satu pendekatan populer dalam menyelesaikan Traveling Salesman Problem karena kemampuannya untuk menghasilkan solusi yang mendekati optimum. Pada penelitian ini, dilakukan analisis mengenai panjang populasi dan banyak generasi pada Algoritma Genetika dalam menyelesaikan Traveling Salesman Problem. Tujuan penelitian ini adalah untuk menganalisis pengaruh kedua parameter tersebut terhadap kinerja Algoritma Genetika dalam mencapai solusi yang mendekati optimal. Digunakan studi kasus pendistribusian suatu produk UMKM (Usaha Mikro Kecil dan Menengah) di Bandung. Evaluasi dilakukan berdasarkan panjang rute terpendek yang ditemukan oleh Algoritma Genetika dalam jumlah iterasi tertentu. Hasil eksperimen menunjukkan bahwa dengan peningkatan panjang populasi pada Algoritma Genetika dapat meningkatkan kemampuan algoritma untuk menemukan solusi yang lebih baik. Dengan jumlah individu dalam populasi yang lebih besar, algoritma memiliki lebih banyak kesempatan untuk menjelajahi ruang solusi dan menemukan rute terpendek yang memenuhi kriteria Traveling Salesman Problem.

Abstract. The Traveling Salesman Problem (TSP) is an important optimization problem in the fields of computer science and mathematics. Its main objective is to find the shortest route that involves visiting a specific set of points or cities by a salesman. Genetic Algorithms (GA) have become a popular approach in solving the Traveling Salesman Problem due to their ability to generate solutions that approximate optimality. In this study, an analysis was conducted on the population size and number of generations in the Genetic Algorithm for solving the Traveling Salesman Problem. The aim of this research was to analyze the influence of these two parameters on the performance of the genetic algorithm in achieving near-optimal solutions. A case study was conducted on the distribution of a small and medium-sized enterprise (SME) product in Bandung. The evaluation was based on the shortest route length discovered by the the Genetic Algorithms within a specified number of iterations. The experimental results indicated that increasing the population size in the Genetic Algorithms can enhance the algorithm's ability to find better solutions. With a larger number of individuals in the population, the algorithm had more opportunities to explore the solution space and discover the shortest routes that met the the Traveling Salesman Problem criteria.