Aplikasi Algoritma Genetika untuk Menyelesaikan Masalah Travelling Salesman Problem (TSP)

Travelling Salesman Problem (TSP) is a cassical optimization problem which refers to the directed graph that search hamilton circuit with the shortest distance or minimum travel tour. TSP is categorized as a NP-Hard Problem that can be solved perfectly with polynomial time. TheTSP problem is generally solved using heuristic method. Heuristic method, simpler than other method, can solve complex problems with more varied results and shorter calculation time. We use Genetic Algorithm, a kind of heuristic method, to determine the shortest route through every city only once and return to original departure city. Genetic Algorithm is an analogy form of Darwin's Evolution Theory and Principles of Genetic in Biological Science. The algorithm is very effective to solve the complex optimization problems that is difficult to be solved with conventional method. The solution obtained by genetic algorithm depend on type of operator and parameter used in the algorithm. Genetic operator includes selection, crossover and mutation. The parameters involve population size, number of generations, crossover probability and mutation probability. Genetic Algorithm as heuristic algorithm can search the solution for TSP problem, but because it starts from a random solution then the result is not always the optimal solutio