Algoritma Genetika Menentukan Jalur Jalan dengan Lintasan Terpendek (Shortest Path)

Abstract

The shortest route (shortest path) is a problem to find the minimum route from the initial point (node) to the destination point (node). One of the artificial intelligence that can be used to solve the problem of finding the shortest route is the Genetic Algorithm. To get the right solution for optimization problems with one variable or multiple variables. The problem of traveling salesman problem (TSP) is one of the combinatorial optimization problems. TSP is a difficult problem when viewed from the point of computation. Several methods have been used to solve the problem and are a solution in determining the shortest trip through another city only once and returning to the city of origin of departure. Search techniques are carried out at the same time on a number of solutions known as populations. Individuals in a population are called chromosomes. This genetic algorithm consists of several main procedures, namely the selection procedure, crossover, mutation and elitism. Based on research results, the shortest path is 1-2-3-6-5-4-7-8-9-10 where the path is Sunur, Kurai Taji, Lapai, Jati, Pasar Pariaman, Gelombang, Rawang, Pauh, Sei Pasak, dan Koto Marapak with a path length of 55.8342.