Kohonen Self-Organizing Maps dengan Pembobotan Ketetanggan Simetris pada Kurva Gaussian untuk Penyelesaian Travelling Salesman Problem

MUH SULKIFLY SAID, Dr. Indah Soesanti, S.T., M.T; Dr. Sri Suning Kusumawardani, S.T., M.T

2017 | Tesis | S2 Teknik Elektro

Neural network merupakan salah satu metode dalam Artificial Intelligence yang sangat berkembang pesat dalam beberapa dekade terakhir. Salah satu varian Neural Network adalah Kohonen Self-Organizing Maps (SOM) yang umumnya digunakan dalam proses data mining atau knowledge discovery, kelebihan SOM dalam pemetaan input berdimensi tinggi ke dimensi yang lebih rendah berpotensi untuk digunakan dalam menyelesaikan permasalahan penentuan rute seperti Travelling Salesman Problem (TSP). Dengan jumlah kota yang relatif sedikit TSP dapat diselesaikan dengan mudah menggunakan metode konvensional namun permasalahan muncul dengan bertambah banyaknya jumlah kota yang akan diselesaikan, metode ini tidak efektif lagi disebabkan meningkatnya kandidat solusi secara eksponensial Sehingga dibutuhkan suatu metode pendekatan untuk dapat menyelesaikan permasalahan tersebut dengan cepat namun juga dengan tingkat akurasi yang dapat diterima. Dalam menerapkan algoritme SOM dalam menyelesaikan permasalahan optimasi terlebih dahulu diformulasikan suatu topologi yang dapat membentuk suatu graf tertutup, dalam penelitian ini topologi yang dibangun merupakan suatu lingkaran ring yang terdiri atas neuron dengan posisi koordinat yang berubah secara dinamis, berdasarkan hasil percobaan kombinasi parameter learning rate, radius dan neuron per city dan jumlah iterasi didapatkan, hasil terbaik pada pembobotan Gaussian pada percobaan ke 2 dengan rerata akurasi sebesar 89,51% dengan rerata waktu tempuh untuk keseluruhan dataset 10,20 menit

Neural network is one of the vast growing methods in Artificial Intelligence in the past few decades. One of the variants of Neural Network is Kohonen Self-Organizing Maps (SOM) which is commonly used in data mining or knowledge discovery process. Advantages of SOM in mapping high-dimensional input into lower dimensions can potentially be used to solve route determination problems such as Travelling Salesman Problem (TSP). With relatively small number of cities, TSP can easily be solved with conventional method but problems arise with the increase on the number of cities to be solved, this method would no longer be effective because of the rise of candidate solutions exponentially. Hence there needs to be an approach which can solve those problems rapidly with an acceptable level of accuracy. The implementation of SOM algorithm in solving optimization problems include first and foremost formulation of a topology which can form a closed graph. In this research, the formulated topology is a Ring circle which comprises of neurons with coordinate positions that change dinamically, based on trial result using a combination of learning rate, radius and neuron amount of , this algorithm generates a fairly high accuracy using weighted neighbor Gaussian curve that is with an average of 89,51% and of travel time for whole dataset 10,20 minute.

Kata Kunci : Neural Network, Artificial Intelligence, Self-Organizing Map, Travelling Salesman Problem, Combinatorial Optimization, shortest path, Artifficial intelligence