Analisis Pemilihan Partially Mapped Crossover Algoritma Genetika pada Penyelesaian Travelling Salesman Problem

Abstract

Traveling Salesman Problem (TSP) is an optimization problem that can be applied to a variety of activities. Fundamental from problems of TSP is how the salesman can arrange travel routes so that the distance which he passes an optimum route is the best minimum distance. The methods used include: Ant colony, simulated annealing, taboo search, genetic algorithms and others. The research was formulated by the influence of the crossover point determination of the probability of crossover, especially in finding the optimal route to the TSP. The purpose of this study was to find a good crossover probability value in achieving an optimal route. Method crossover which applied in this research is partially mapped crossover (PMX). Selection is used roulette wheel selection. From the testing conducted by using 20%, 40%, 60%, 80% and 99% can be found that a good crossover probability is 99%, with the determination of mutation is worth 0.05%. The number of generations is 10000 generations. The optimal route for data att48.tsp is 43910 and data bays29.tsp is 10463.

Travelling Salesman Problem (TSP) merupakan sebuah permasalahan optimasi yang dapat diterapkan pada berbagai kegiatan. Pokok dari permasalahan TSP adalah bagaimana salesman tersebut dapat mengatur rute perjalanannya sehingga jarak yang ditempuhnya merupakan rute yang optimum yaitu jarak minimum terbaik. Metode-metode yang sudah digunakan antara lain : Ant colony, simulated annealing, tabu search, algoritma genetika dan lain-lain. Penelitian ini dirumuskan dengan pengaruh penentuan crossover point khususnya probabilitas crossover dalam mencari rute optimal pada TSP. Tujuan dari penelitian ini adalah untuk mencari nilai probabilitas crossover yang baik dalam mencapai rute optimal. Metode crossover yang digunakan dalam penelitian ini adalah partially mapped crossover (PMX). Seleksi yang digunakan adalah seleksi Roulette wheel. Dari pengujian yang dilakukan dengan menggunakan 20%, 40%, 60%, 80% dan 99% dapat ditemukan bahwa probabilitas crossover yang baik adalah 99%, dengan penetapan mutasi bernilai 0.05%. Banyaknya generasi adalah 10000 generasi. Rute optimal yang diperoleh dari data att48.tsp adalah 43910 dan data bays29.tsp adalah 10463.