Algoritma Genetika Menentukan Jalur Jalan dengan Lintasan Terpendek

(Shortest Path)
Melladia
Teknik Informatika, fakultas Teknik, Universitas Nahdlatul Ulama Sumatera Barat
Melladia1311@[Link]

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.
Keywords: genetic algorithm, shortest path, TSP

Abstrak
Rute terpendek (shortest path) adalah permasalahan untuk mencari rute minimum dari titik (node) awal ke titik (node) tujuan.
Salah satu kecerdasan buatan yang dapat digunakan untuk menyelesaikan masalah pencarian rute terpendek adalah Algoritma
Genetika. Untuk mendapatkan solusi yang tepat untuk permasalahan optimasi dengan satu variabel atau multi variabel.
Permasalahan travelling salesman problem (TSP) merupakan salah satu persoalan optimasi kombinatorial. TSP merupakan
persoalan yang sulit bila dipandang dari sudut komputasinya. Beberapa metode telah digunakan untuk memecahkan
persoalan dan merupakan solusi dalam menentukan perjalanan terpendek yang melalui kota lainnya hanya sekali dan kembali
ke kota asal keberangkatan. teknik pencarian dilakukan sekaligus atas sejumlah solusi yang dikenal dengan istilah populasi.
Individu yang terdapat dalam satu populasi disebut dengan istilah kromosom. Algoritma genetika ini terdiri dari beberapa
prosedur utama yaitu prosedur seleksi, crossover, mutasi dan elitisme. Berdasarkan hasil penelitian, jalur terpendek adalah 1-
2-3-6-5-4-7-8-9-10 dimana jalur tersebut adalah Sunur, Kurai Taji, Lapai, Jati, Pasar Pariaman, Gelombang, Rawang, Pauh,
Sei Pasak, dan Koto Marapak dengan panjang jalur 55,8342.

Kata kunci: algoritma genetika, shortest path, TSP

1. Pendahuluan semuanya dan setiap tempat yang hanya sekali

dikunjungi[2].
Travelling Salesman Problem (TSP) dikenal sebagai
salah satu masalah optimasi yang menarik perhatian Shortest Path merupakan metode pencarian lintasan
para peneliti sejak beberapa dekade terdahulu. terpendek pada sebuah graf untuk pencarian lintasan
Travelling Salesman Problem (TSP) termasuk ke dalam terpendek dari sebuah graf bersambung dan berarah,
persoalan yang sangat terkenal dalam teori graf. dapat digunakan perhitungan cara manual atau dengan
Nama persoalan ini diilhami oleh masalah seorang melalui komputer Shortest Path yang diperoleh akan
pedagang yang berkeliling mengunjungi sejumlah meminimumkan fungsi linear khusus dari Path seperti
kota[1]. Masalah dalam menentukan rantaian jarak, waktu dan biaya dihadapi selama melakukan
terpendek diantara pasangan node (titik) tertentu dalam perjalanan. Perumusan persoalan ini akan menjadi salah
suatu graph telah banyak menarik perhatian. satu kegunaan dari lintasan dengan jarak (waktu)
Permasalahan pencarian rute optimum dalam suatu diminimumkan terhadap biaya yang dianggarkan[3].
perjalanan yang mencari jarak terpendek untuk
Permasalahan yang dihadapi adalah bagaimana cara
mencapai tempat tujuan yang akan dikunjungi
mengunjungi vertek pada graph dari vertek awal ke

112
 Melladia
Prosiding Seminar Nasional Sistem Informasi dan Teknologi (SISFOTEK) ke 4 Tahun 2020

vertek akhir dengan bobot minimum, dimana dalam hal menentukan shortest path problem dalam kasus ini
ini bobot yang digunakan adalah jarak dan kota-kota yang diangkat adalah memberi solusi optimasi dalam
yang dikunjungi diasumsikan sebagai graph yang maslah TSP di wilayah Kota Pariaman,
saling terhubung (connected graph) antar suatu kota
dengan kota lainnya. Suatu graph G disebut terhubung 2. Metode Penelitian
jika untuk setiap vertek dari graph terdapat jalur yang
menghubungkan kedua vertek tersebut, atau dengan Metode penelitian merupakan sebuah langkah atau cara
kata lain graph terhubung jika setiap vertek yaitu Vi yang digunakan dalam melakukan penelitian yang
dan Vj dalam suatu graph terdapat sedikitnya sebuah dapat dipertanggung jawabkan hasilnya
edge. Edge pada graph berarah disebut arc[4]. Pada pelaksanaan penelitian ini pengambilan data
dilakukan selama 2 hari dan data di dapatkan dari Dinas
Beberapa metode algoritma yang telah dikembangkan
untuk menyelesaikan persoalan jalur terpendek Perhubungan Kota Pariaman dan Dinas Pekerjaan
diantaranya Algoritma Djikstra, Algoritma Floyd- Umum Kota Pariaman.
Warshall dan Algoritma Bellman-Ford. Algoritma ini Dalam hal ini metode penelitian yang digunakan adalah
dapat diselesaikan dengan cepat jika kota-kota yang metode deskriptif. Penelitian dengan metode deskriptif
akan dikunjunginya sedikit. Seiring dengan itu muncul dapat diartikan sebagai proses pemecahan masalah
permasalahan bagaimana menentukan jalur terpendek yang diselidiki dengan melukiskan keadaan subyek dan
jika terdapat banyak jalur alternatif ke kota tujuan obyek penelitian pada saat sekarang berdasarkan fakta-
dengan mempertimbangkan efisiensi dan waktu fakta yang tampak dan bagaimana adanya. Pelaksanaan
sehingga diperlukan ketepatan dalam menentukan jalur metode penelitian deskriptif tidak terbatas sampai pada
terpendek antar suatu kota. Semakin banyak alternatif pengumpulan dan penyusunan data, tetapi meliputi
jalur ke kota tujuan, semakin rumit cara untuk analisis dan interpretasi tentang data tersebut[9-10].
menghitung jalur terpendek. Untuk itu diperlukan
metode/cara yang handal untuk dapat menentukan jalur 3. Hasil dan Pembahasan
terpendek dari kota asal ke kota tujuan sehingga
diperoleh solusi yang terbaik. Langkah-langkah dalam penyelesaian TSP dengan
algoritma genetika adalah sebagai berikut :
Kecerdasan Buatan (Artificial intelligence) merupakan
salah ilmu pengetahuan yang digunakan agar dapat Skema pengkodean
menyelesaikan masalah manusia dengan cara TSP dapat dirumuskan sebagai berikut : terdapat
memahami, memprediksi dan memanipulasi. sekumpulan N node dengan posisi-posisi koordinatnya
Kecerdasan dibuat agar sistem yang menggunakan {Xi, Yi}, i = 1,2,….,N perhatikan gambar 1 dibawah
algoritma tertentu sehingga sistem seolah-olah dapat ini. Terdapat 6 node yang harus dikunjungi.
berpikir menyamai manusia[5]. Maka penggunaan
metode AI (Artificial Intelligent) atau kecerdasan
buatan dalam perhitungan jalur terpendek merupakan
salah satu solusi untuk dapat menyelesaikan masalah
dengan jalur yang banyak dan rumit.
Pada tahun 70-an muncul sebuah algoritma baru yang
dikenal dengan Algoritma Genetika (Genetic
Algoritm,GA) yang merupakan salah satu cabang dari
AI. Algoritma Genetika ini diperkenalkan oleh John
Holland dari University of Michigan yang kemudian
dipopulerkan oleh salah satu muridnya yaitu David
Goldberg, sehingga Algoritma Genetika mulai
digunakan secara luas ke berbagai bidang, termasuk
Gambar 1. Peta dua dimensi untuk TSP.
untuk memecahkan permasalah-permasalahan optimasi.
Untuk menentukan jalur jalan dengan lintasan Suatu solusi dipresentasikan ke dalam suatu kromosom
terpendek (shortest path) ini digunakan algoritma yang berisi nomor urut dari semua kota yang ada.
genetika. Algoritma genetika merupakan salah satu Masing-masing nomor urut kota hanya boleh muncul
algoritma yang digunakan untuk menyelesaikan satu kali didalam kromosom sehingga satu kromosom
masalah optimasi. Algoritma genetika meniru cara mempresentasikan satu rute perjalanan (satu solusi)
kerja proses genetika pada makhluk hidup, dimana yang valid. Dimana suatu kromosom
terdapat proses seleksi, rossover dan mutasi untuk mempresentasikan suatu permutasi dari nomor urut
mendapatkan kromosom terbaik pada suatu generasi[6- kota 1,2,3…., N.
8].
Dengan demikian untuk gambar 1, suatu contoh
Tujuan penelitian ini untuk menerapkan suatu konsep kromosom adalah seperti pada gambar 2 dibawah ini :
algoritma genetika untuk penyelesaian dalam

113
 Melladia
Prosiding Seminar Nasional Sistem Informasi dan Teknologi (SISFOTEK) ke 4 Tahun 2020

algoritma genetika. Misalkna terdapat 10 kota yang

akan dikunjungi yaitu kota 1 (sunur), kota 2 (kurai taji),
kota 3 (lapai), kota 4 (gelombang), kota 5 (pasar
pariaman), kota 6 (jati), kota 7 (rawang), kota 8 (pauh),
kota 9 ([Link]), dan kota 10 (koto marapak). Letak
Gambar 4.2 Representasi kromosom untuk TSP masing-masing kota dinyatakan dalam koordinat.
Perjalanan dimulai dari kota pertama dan akhirnya juga
Pada gambar 2 kromosom K1 dan K2 akan berakhir dikota pertama. Akan ditentukan jalur
mempresentasikan rute perjalanan yang sama. Hal ini terpendek atau total bobot minimum yang akan
bisa dipahami karena, secara siklus, K1 dan K2 ditempuh untuk mengunjungi 10 kota tersebut. Kota
memang memberikan rute perjalanan yang sama. tersebut dipresentasikan dalam graf G berikut ini :
Pindah Silang
Pindah silang dapat diimplementasikan dengan skema
order crossover. Pada skema ini satu bagian kromosom
dipertukarkan dengan tetap menjaga urutan kota yang
bukan bagian dari kromosom tersebut. Ilustrasi skema
order crossover dapat dilihat pada gambar dibawah ini :

Gambar 4 Graph dengan G vertex

Penyelesaian :
Langkah 1 : inisialisasi
Koordinat masing-masing kota dapat dilihat pada graf
G pada gambar 4. Dengan menggunakan persamaan
crossover diperoleh jarak antar kota sebagaimana
Gambar 3 Pindah silang menggunakan skema order crossover
dipresentasikan dalam matrik bobot sisi graf G
Mula-mula 2 buah titik potong, TP1 dan TP2 berukuran 10x10.
dibangkitkan secara random untuk memotong 2 buah
kromosom orang tua, K1 dan K2 (gambar 4.3a) Langkah 2 :
kemudian 2 kromosom anak, A1 dan A2 mendapatkan Bentuk populasi awal dengan cara membangkitkan
gen-gen dari bagian kromosom K1 dan K2 secara kromosom secara acak sebanyak ukuran populasi.
menyilang kromosom A1 mendapatkan {6,1,5} dan A2
mendapatkan {1,4,3} (gambar 4.3b). Posisi-posisi gen Hitung panjang jalur masing-masing kromosom dengan
yang masih kosong pada kromosom A1 diisi dengan cara :
gen-gen dari K1, secara berurutan dari gen 1 sampai Untuk ukuran populasi :
gen 6 yang belum ada pada A1. Hal yang sama juga
dilakukan untuk kromosom A2 (gambar 4.3c). Kromosom [1] = 3-6-8-7-5-4-1-2-9-10
Panjang jalur [1] = jarak(3-6) + jarak(6-8) + jarak (8-7)
Mutasi + jarak(7-5) + jarak(5-4) + jarak
Operator mutasi biasanya diimplementasikan dengan (4-1) + jarak(1-2) + jarak(2-9)
menukarkan gen termutasi dengan gen lain yang dipilih + jarak(9-10) + jarak(10-3) = 3,605
secara random. Misalnya, kromosom {2,3,4,1,5} dapat + 9,434 + 6,325 + 5,000 + 3,000
termutasi menjadi kromosom {4,3,2,1,5}. Dalam hal ini + 13,454 + 6,708 + 15,133 + 4,472
gen 1 dan gen 3 saling ditukarkan. Skema mutasi ini + 17,464 = 84,595
dikenal sebagai swapping mutation.
Hitung nilai fitness masing-masing kromosom dengan
3.1 Pengolahan Data menggunakan persamaan sebagai berikut :
Berikut adalah contoh penyelesaian permasalahan Nilai Nilaifitness[i] = 1 / Panjangjalur[i] (1)
Travelling Salesman Problem dengan menggunakan Nilaifitness[1] = 1 / 84,595 = 0,0118

114
 Melladia
Prosiding Seminar Nasional Sistem Informasi dan Teknologi (SISFOTEK) ke 4 Tahun 2020

Dan seterusnya sampai populasi ke-30.

Langkah 3 :
Menghitung total fitness
TotalFitness = (2)
= fitness(1) + fitness(2) + fitness(3) + …
+fitness(30)
= 0,0118 + 0,0103 + 0,0095 + ….
+ 0,0076
= 0,3551 Lakukan proses crossover dengan cara yang sama
untuk kromosom 11 dengan 14, 17 dengan 18, 21
Hitung fitness relatif dengan 23, dan kromosom 26 dengan 27.
Fitness relatif dihitung dengan menggunakan
persamaan Proses Mutasi
P[i] = Bangkitkan bilangan acak r yang bernilai antara 0 dan 1
(3) sebanyak ukuran populasi (30).
Untuk fitness (1) Untuk i=1,2,…,30 maka, jika R[i] < 0,100 maka
P[1] = 0,0118/0,3551= 0,0332 kromososm ke-i terkena mutasi. karena tidak ada R[i] <
Dan seterusnya sampai populasi ke-30. 0,100 maka tidak ada kromosom yang terkena mutasi.
Hitung fitness kumulatif
Fitness kumulatif dihitung dengan menggunakan Proses Elitisme
persamaan berikut : Untuk i=1,2,…,30 maka, jika R[i] < 0,100 maka
(4) lakukan penggantian pada kromosom ke-i. bahwa
Untuk fitness (1) dan (2) bilangan acak yang nilainya kurang dari 0,100 adalah
Q[1] = 0,0332 bilangan acak pada populasi ke-4 maka lakukan
Q[2] = 0,0332 + 0,0290 = 0,0622 penggantian pada kromosom ke-4.
Seleksi Roda Roulette-Wheel Tabel 1 Populasi akhir ke-i
Bangkitkan nilai acak r yang bernilai antara 0 dan 1
sebanyak ukuran populasi (30) Pop Kromosom Panjang Fitness Pop Kromosom Panjang Fitness
ulas Jalur ula Jalur
Jika R[k] < C[k] maka kromosom ke-k sebagai induk, i si
selain itu pilih kromosom ke-k sebagai induk dengan 1 3-6-8-7-5-4- 84,595 0,0118 16 5-6-9-10-8- 80,935 0,0124
1-2-9-10 7-3-2-1-4
syarat C[k-1] < R[k] < C[k]. Putar roulette-wheel
2 9-7-4-6-5-3- 96,832 0,0103 17 5-4-3-1-2-6- 79,678 0,0126
sebanyak jumlah populasi yaitu 30 kali. Untuk i= 1-2-10-8 7-9-10-8
1,2,…,30, jika R[i] ≤ Q[1] maka pilih kromosom (1) 3 4-7-8-6-3-5- 105,491 0,0095 18 8-7-5-4-6-3- 74,514 0,0134
pada urutan ke-1. Untuk j= 2,3,…,29, jika Q[j] < R[i] ≤ 1-9-10-2 2-1-9-10
Q[j+1] maka pilih kromosom ke [j+1] pada urutan ke-i. 4 10-8-7-6-5- 72,63 0,0138 19 4-5-7-6-8- 80,767 0,0124
4-3-1-2-9 10-9-3-2-1
Untuk populasi ke-1 : 5 10-6-4-5-7- 98,995 0,0101 20 3-2-1-4-5-6- 84,975 0,0118
Q[9] < R[i] ≤ Q[10] yaitu 0,2995 < 0,3120 ≤ 0,3344 3-8-2-1-9 7-9-10-8
maka pilih kromosom pada populasi ke-10 pada urutan 6 7-8-6-5-4-3- 80,929 0,0124 21 10-6-7-5-4- 93,596 0,0107
ke-1. Begitu seterusnya sampai populasi ke-30. 1-2-9-10 3-2-1-9-8
7 6-7-5-4-3-1- 74,415 0,0134 22 6-9-10-8-7- 77,223 0,0129
Untuk i= 1,2,…, 30 2-9-10-8 5-4-3-2-1
Jika R[i] < Pc atau R[i] < 0,500 maka pilih kromosom 8 2-10-8-5-4- 95,866 0,0104 23 2-8-10-9-7- 84,866 0,0118
7-6-9-3-1 6-4-5-3-1
ke-i sebagai induk.
9 1-7-8-10-6- 108,058 0,0093 24 7-6-4-5-3-1- 72,874 0,0137
Populasi yang bilangan yang kurang dari Pc adalah 9-4-5-3-2 2-9-10-8
populasi ke : 2, 8, 11, 14, 17, 18, 21, 23, 26, 27, dan 28. 10 3-2-9-10-8- 80,782 0,0124 25 10-8-7-6-5- 72,63 0,0138
Hal ini berarti bahwa kromosom yang berhak untuk 7-5-4-6-1 4-3-1-2-9
melakukan crossover adalah kromosom pada populasi 11 9-10-8-7-4- 85,396 0,0117 26 4-10-8-9-7- 102,053 0,0098
seperti yang telah disebutkan diatas. 6-3-1-2-5 5-6-3-1-2
12 7-8-5-4-6-2- 84,091 0,0119 27 9-7-5-4-3-1- 80,457 0,0124
Untuk k=1,2,…,11, karena mod(11,2) ≠ 0, sehingga 1-3-9-10 2-6-8-10
k=k-1 = 11-1 = 10. Jadi buang salah satu kromosom, 13 6-10-9-3-2- 86,188 0,0116 28 2-3-1-4-7-5- 104,362 0,0096
misalkan kromosom ke 28 dibuang. 1-4-5-7-8 6-9-8-10
14 2-1-3-4-5-7- 74,415 0,0134 29 9-5-2-8-7-3- 118,12 0,0085
Lakukan crossover antara kromosom 2 dengan 8, 11 6-8-10-9 6-4-1-10
dengan 14, 17 dengan 18, 21 dengan 23, dan kromosom 15 7-5-4-6-3-1- 69,811 0,0143 30 8-2-10-5-6- 131,598 0,0076
26 dengan 27. 2-9-10-8 1-7-4-3-9

Crossover antara kromososm 2 dengan 8 :

115
 Melladia
Prosiding Seminar Nasional Sistem Informasi dan Teknologi (SISFOTEK) ke 4 Tahun 2020

Jadi hasil populasi akhir pada generasi ke-i pada tabel 1 42 1 2 3 6 5 4 7 8 9 10 0.0179 0.0105 0.0163
terlihat bahwa : 43 1 2 3 6 5 4 7 8 9 10 0.0179 0.0105 0.0168
44 1 2 3 6 5 4 7 8 9 10 0.0179 0.0105 0.0160
Fitness terbaik berada pada populasi ke-4 dengan nilai 45 1 2 3 6 5 4 7 8 9 10 0.0179 0.0105 0.0170
fitness 0,0138. 46 1 2 3 6 5 4 7 8 9 10 0.0179 0.0106 0.0175
47 1 2 3 6 5 4 7 8 9 10 0.0179 0.0179 0.0179
Fitness terburuk berada pada populasi ke-30 dengan
48 1 2 3 6 5 4 7 8 9 10 0.0179 0.0179 0.0179
nilai fitness 0,0076. 49 1 2 3 6 5 4 7 8 9 10 0.0179 0.0179 0.0179
Populasi akhir pada generasi ke-1 ini akan dijadikan 50 1 2 3 6 5 4 7 8 9 10 0.0179 0.0179 0.0179
sebagai populasi awal untuk generasi ke-2 dan lakukan Fitness rata-rata generasi ke-i diperoleh dengan :
langkah 1 sampai 3 untuk populasi ke-2 sampai Fitness rata-rata (47)
generasi maksimum (generasi ke-50). = FitnessTerbaik(47) + fitnessTerburuk(47)
Langkah 4 : Selesai 2
= 0,0179 + 0,0179
Setelah dilakukan pengujian dengan Matlab 7.9 2
diperoleh rekap hasil masing-masing generasi seperti = 0,0358
terlihat pada table 2 berikut : 2
Dari tabel 2 terlihat bahwa nilai fitness paling
Tabel 2 Rekap Hasil Setelah Diuji Dengan Matlab 7.9
F. maksimum adalah 0,0176 dengan kromosom 1-2-3-6-5-
F. Rata - 4-7-8-9-10. Ini berarti bahwa jalur terpendek setelah
No Pola jalur TSP Terburu
Terbaik rata
k dilakukan pencarian oleh algoritma genetika untuk 50
1 10 9 5 1 2 6 4 3 7 8 0.0127 0.0076 0.0092 generasi adalah 1-2-3-6-5-4-7-8-9-10 dengan panjang
2 10 9 5 1 2 6 4 3 7 8 0.0127 0.0078 0.0097 jalur 55,8342.
3 10 9 5 1 2 6 4 3 7 8 0.0127 0.0076 0.0100
4 1 2 6 3 7 5 4 8 9 10 0.0155 0.0076 0.0106 Hasil pemrosesan Algoritma Genetika menggunakan
5 1 2 6 3 7 5 4 8 9 10 0.0155 0.0083 0.0109 Matlab sebagai berikut:
6 1 2 6 3 7 5 4 8 9 10 0.0155 0.0083 0.0112
7 1 2 6 3 7 5 4 8 9 10 0.0155 0.0085 0.0117
8 1 2 6 3 7 5 4 8 9 10 0.0155 0.0085 0.0118
9 1 2 6 3 7 5 4 8 9 10 0.0155 0.0085 0.0121
10 1 2 6 3 7 5 4 8 10 9 0.0157 0.0085 0.0125
11 1 2 6 3 7 5 4 8 10 9 0.0157 0.0088 0.0131
12 1 2 3 7 6 5 4 8 9 10 0.0159 0.0087 0.0138
13 1 2 3 7 6 5 4 8 9 10 0.0159 0.0085 0.0137
14 1 2 3 7 6 5 4 8 9 10 0.0159 0.0086 0.0136
15 1 2 3 7 6 5 4 8 9 10 0.0159 0.0095 0.0138
16 1 2 3 6 7 5 4 8 9 10 0.0172 0.0096 0.0138
17 1 2 3 6 7 5 4 8 9 10 0.0172 0.0092 0.0135
18 1 2 3 6 7 5 4 8 9 10 0.0172 0.0097 0.0145
19 1 2 3 6 7 5 4 8 9 10 0.0172 0.0097 0.0150
20 1 2 3 6 7 5 4 8 9 10 0.0172 0.0096 0.0142 Gambar 5 Grafik Hasil Pemrosesan Algoritma Genetika
21 1 2 3 6 7 5 4 8 9 10 0.0172 0.0096 0.0151
22 1 2 3 6 7 5 4 8 9 10 0.0172 0.0105 0.0146 Pada gambar 5terdapat dua buah grafik, dimana pada
23 1 2 3 6 7 5 4 8 9 10 0.0172 0.0099 0.0153 figure 2 memperlihatkan fitness terbaik, fitness terburuk
24 1 2 3 6 7 5 4 8 9 10 0.0172 0.0097 0.0147 ,dan fitness rata-rata. Rute optimum yang harus dilalui
25 1 2 3 6 5 4 7 8 9 10 0.0179 0.0086 0.0149 salesman adalah 1-2-3-6-5-4-7-8-9-10 dimana jalur
26 1 2 3 6 5 4 7 8 9 10 0.0179 0.0092 0.0156 tersebut adalah Sunur, Kurai Taji, Lapai, Jati, Pasar
27 1 2 3 6 5 4 7 8 9 10 0.0179 0.0089 0.0154 Pariaman, Gelombang, Rawang, Pauh, Sei Pasak, dan
28 1 2 3 6 5 4 7 8 9 10 0.0179 0.0104 0.0163 Koto Marapak dengan panjang jalur 55,8342 seperti
29 1 2 3 6 5 4 7 8 9 10 0.0179 0.0105 0.0165 yang terlihat pada figure 3 pada gambar 5.
30 1 2 3 6 5 4 7 8 9 10 0.0179 0.0111 0.0170
31 1 2 3 6 5 4 7 8 9 10 0.0179 0.0123 0.0168
4. Kesimpulan
32 1 2 3 6 5 4 7 8 9 10 0.0179 0.0105 0.0163
33 1 2 3 6 5 4 7 8 9 10 0.0179 0.0106 0.0161 Kesimpulan yang di ambil dari hasil penelitian terhadap
34 1 2 3 6 5 4 7 8 9 10 0.0179 0.0117 0.0164 persoalan Travelling Salesman Problem (TSP) dapat
35 1 2 3 6 5 4 7 8 9 10 0.0179 0.0105 0.0162 diselesaikan dengan menggunakan algoritma genetika.
36 1 2 3 6 5 4 7 8 9 10 0.0179 0.0105 0.0162 Walaupun solusi TSP yang dihasilkan oleh algoritma
37 1 2 3 6 5 4 7 8 9 10 0.0179 0.0123 0.0170
genetika belum tentu merupakan solusi paling optimal
38 1 2 3 6 5 4 7 8 9 10 0.0179 0.0105 0.0167
(misalnya apabila yang dilalui sangat banyak), namun
39 1 2 3 6 5 4 7 8 9 10 0.0179 0.0105 0.0168
40 1 2 3 6 5 4 7 8 9 10 0.0179 0.0099 0.0161
algoritma genetika akan menghasilkan solusi yang
41 1 2 3 6 5 4 7 8 9 10 0.0179 0.0105 0.0169

116
 Melladia
Prosiding Seminar Nasional Sistem Informasi dan Teknologi (SISFOTEK) ke 4 Tahun 2020

lebih optimal pada setiap generasinya. Hal tersebut Pada PT. Es Malindo Boyolali. UNNES Journal of Mathematics,
8(1), 21-29.
terlihat dari nilai fitness tiap generasi.
[2] Utomo, R. G., Maylawati, D. S., Alam, C. N., (2018).
Kelebihan algoritma genetika sangat terlihat dari Implementasi Algoritma Cheapest Insertion Heuristic (CIH)
dalam Penyelesaian Travelling Salesman Problem (TSP). JOIN
adaptivitasnya dalam menyelesaikan masalah. Begitu (Jurnal Online Informatika), 3 (1), 61-67.
kita bisa mengkodekan masalah ke dalam kromosom [3] Simanjuntak, O.S., Seminar Nasional Informatika 2012
dan bisa membangun fungsi fitness, maka kita dapat (semnasIF 2012). In : UPN “Veteran”, Pengembangan Shortest
membangun algoritma genetika untuk masalah tersebut. Path Algorithm (SPA) Dalam Rangka Pencarian Lintasan
Terpendek Pada Graf Bersambung Berarah Terurai,
Beberapa komponen algoritma genetika, misalnya Yogyakarta, 30 Juni 2012. UPN “Veteran”: Yogyakarta.
Inisialisasi Populasi, Linear Fitness Ranking, Roulette- [4] Salaki, D. T., (2011). Penentuan Lintasan Terpendek Dari
Wheel, Pindah Silang dan Mutasi bisa digunakan untuk FMIPA ke Rektorat dan Fakultas di UNSRAT manado
beberapa masalah berbeda termasuk masalah TSP. Menggunakan Algoritma Djikstra. Jurnal Ilmiah Sains. 11(1),
73-78
Berdasarkan hasil penelitian, jalur terpendek adalah 1- [5] Melladia, M., & Mardani, I. R., (2018). Implementasi Algoritma
Backpropagation Prediksi Kegagalan Siswa Pada Mata Pelajaran
2-3-6-5-4-7-8-9-10 dimana jalur tersebut adalah Sunur, Matematika. Jurnal RESTI (Rekayasa Sistem Dan Teknologi
Kurai Taji, Lapai, Jati, Pasar Pariaman, Gelombang, Informasi), 2(3), 753 - 759.
Rawang, Pauh, Sei Pasak, dan Koto Marapak dengan [Link]
panjang jalur 55,8342. [6] Suyanto. (2005). Algoritma Genetika dalam MATLAB.
Yogyakarta : Andi.
[7] Saputro, Nico., (2003). Pengenalan Huruf dengan Memakai
Diharapkan nantinya dapat dikembangkan sebuah Algoritma Genetik. Integral, Vol 8 No.2, Oktober 2003.
pencarian TSP dengan algoritma genetika dan [8] Syamsudin, Aries., (2004). Pengenalan Algoritma Genetik.
([Link])
pengujian menggunakan aplikasi lain yang dapat [9] Utami, P. Y., Suhery, C., Ilhamsyah., (2014). Aplikasi Pencarian
ditampilkan dalam bentuk peta sebenarnya dari suatu Rute Terpendek Menggunakan Algoritma Genetika. Jurnal
daerah yang diteliti dengan cakupan jarak dan wilayah Coding Sistem Komputer Universitas Tangjungpura, 02(1), 19-
yang lebih besar dan luas. 25.
[10] Febriyana, R., Mahmudy, W. F., (2016). Penjadwalan Kapal
Penyeberangan Menggunakan Aloritma Genetika. Jurnal
Daftar Rujukan Teknologi Informasi dan Ilmu Komputer (JTIIK), 3(1), 43-50.

[1] Amozhita, K. K., Suyitno, S., Mashuri., (2019). Menyelesaikan

Travelling Salesman Problem Dengan Metode Dua Sisi Optimal

117