ABSTRAKSI: Travelling Salesman Problem adalah suatu permasalahan kombinatorial yang melibatkan beberapa titik yang disebut dengan node yang saling terhubung dan memiliki jarak berbeda antara satu node ke node lain. Kasus ini sering dijadikan sebagai sebuah benchmark terhadap performansi dari suatu algoritma. Tujuan dari penyelesaian kasus Travelling Salesman Problem adalah mencari jarak terpendek yang dibutuhkan untuk mengunjungi semua node tanpa harus mengunjungi sebuah node lebih dari satu kali.
Geometric Differential Evolution merupakan algoritma pencarian solusi optimal yang bekerja berdasarkan pergerakan dari kandidat-kandidat solusi yang direpresentasikan dalam bentuk vektor. Geometric Differential Evolution menggunakan pendekatan yang sedikit berbeda dengan Differential Evolution. Pada Differential Evolution , digunakan differential mutation dan discrete recombination untuk menggerakan vektor kandidat solusi, sedangkan, pada Geometric Differential Evolution, digunakan convex combination dan extension ray.
Pada tugas akhir ini, akan dianalisis performansi dari Geometric Differential Evolution dalam penyelesaian kasus Travelling Salesman Problem berdasarkan jarak terpendek yang diperoleh. Untuk mengetahui performansi maksimum dari Geometric Differential Evolution, akan dianalisis juga mengenai pengaturan parameter yang paling optimal untuk Geometric Differential Evolution.
Kata Kunci : Geometric Differential Evolution, convex combination, extension ray, Travelling Salesman Problem.ABSTRACT: Travelling Salesman Problem is a combinatorial problem that involves several points, called by nodes, that are connected each other and have different distances between one node to another. Travelling Salesman Problme usually used as a benchmark for the performance of an algorithm. The goal of Travelling Salesman Problem optimization is to find the shortest disance to visit all of the nodes without visiting one nodes more than once.
Geometric Differential Evolution is an algorithm that works on the movements of some vector that represent the solution candidates. Geometric Differential Evolution uses a slightly different approach to a conventional Differential Evolution. In Differential Evolution, the vectors moved by differential mutation and discrete recombination, whereas, in Geometric Differential Evolution, the vectors movement is controlled by mutation and recombination that uses convex combination and extension ray.
In this research, the performance of Geometric Differential Evolution in solving Travelling Salesman Problem will be analysed by the minimum route that produced by system. To analyse the maximum performance of Geometric Differential Evolution, the best parameter settings will be analysed too.
Keyword: geometric differential evolution, convex combination, extension ray, travelling salesman problem