## ANALISIS  METODE CYCLE CROSSOVER (CX) DAN METODE PARTIAL- MAPPED CROSSOVER (PMX) PADA PENYELESAIAN KASUS TRAVELING
SALESMAN PROBLEM (TSP)
Theresia Kolo 1 , Adriana Fanggidae 2 , Yelly N. Nabuasa 3
Jurusan Ilmu Komputer, Fakultas Sains dan Teknik, Universitas Nusa Cendana Email: theresiakolo123@gmail.com 1 , adrianailkom@gmail.com 2 , yelly.yosiana.n@gmail.com 3

## ABSTRAK
Travelling  Salesman Problem (TSP) merupakan bentuk permasalahan optimasi  pencarian rute  terpendek  dengan  menempuh  setiap  kota  tepat  satu  kali.  Permasalahan  pencarian  rute terpendek suatu lokasi dapat diselesaikan menggunakan berbagai  algoritma optimasi lainnya. Pada penelitian ini digunakan algoritma genetika dengan menggunakan dua metode crossover  yaitu cycle crossover dan partial mapped crossover . Parameter  yang digunakan ialah probabilitas crossover dan probabilitas  mutasi,    jumlah  kota,  generasi  maksimum,  jumlah  populasi  serta    threshold.  Pada penelitian ini menggunakan dua  model pengujian yaitu pertama dalam mendapatkan generasi dan fitness  terbaik  digunakan  kriteria  berhenti  keseragaman  populasi  80%,  dan  kedua  untuk mendapatkan  waktu  pengujian  terbaik  digunakan  kriteria  berhenti  maksimum  generasi  100  dan 500.  Hasil  pengujian  pertama  didapatkan  metode  PMX  lebih  baik  dari  CX,  ini  ditunjukkan  nilai rata-rata  dari  8  kali  pengujian  untuk  generasi  terbaik  PMX  sebesar    104,0469    dan  CX  sebesar 125,7938, dan untuk fitness terbaik PMX sebesar 344,6031 dan CX sebesar 350,4563. Hasil pengujian kedua  didapatkan  waktu  pengujian  terbaik  metode    PMX  sebesar  1,1035  detik  dan  metode  CX sebesar  2,2374  detik,  sehingga  dapat  disimpulkan  Solusi  yang  diberikan  metode  PMX  lebih  baik dibandingkan metode CX.
Kata kunci : Traveling salesman problem, algoritma  genetika, algoritma Djikstra, cycle crossover, partial mapped crossover, seleksi  roulette wheel

## ABSTRACT
Travelling  Salesman  Problem  (TSP)  is  a  form  of  a  problem in  optimizing  the  search  for  the shortest route by passing through every city in exactly one time. The problem of searching the shortest route of a location can be solved by using many other optimizing algorithms. In this research, genetics algorithm  was  used  by  using  two  crossover  methods  namely  cycle  crossover  and  partial-mapped crossover. The parameters used were crossover probability and mutation probability, the sum of the city, maximum generation, the sum of the population and also threshold. In this research two testing models were used. In the first one, in order to get the generation and the best fitness it used the 80% consistency stopping criteria, and in the second one, in order to get the best testing time, it  used the 100 and 500 maximum generation stopping criteria. The result of the first test showed that PMX method is better than the CX one. This was shown through the 8 times of testing which the result was the best PMX generation was 104,0469 and the CX was 350,4563. The second test resulted that the best testing time of the PMX time was 1,1035 second and the CX method was 2,2374 second, thus, it can be concluded that the solution brought by the PMX method is considered better than the CX.
Keywords  :  traveling  salesman  problem,  Djikstra  algorithm,  genetic  algorithm,  cycle  crossover, partial mapped crossover, roullete wheel selection

## I. PENDAHULUAN
Travelling Salesman Problem (TSP) merupakan bentuk permasalahan optimasi pencarian rute  terpendek  dengan  mencari  solusi  paling  optimal  dalam  menempuh  jarak  lokasi  tertentu dimana seorang salesman melakukan perjalanan dengan rute perjalanan yang ditempuh tepat satu kali pada setiap titik lokasi dan kembali ke lokasi semula.
Algoritma  genetika  merupakan  salah  satu  algoritma  yang  pendekatannya  menyerupai sistem genetika manusia, dimana semua rute perjalanan dari titik awal perjalanan  ke titik tujuan atau akhir diimplementasikan ke dalam bentuk kromosom dan kumpulan dari semua kromosom yang ada merupakan suatu populasi. Salah satu aspek yang mempunyai peranan penting dalam
proses  algoritma  genetika  yaitu  penentuan  kromosom  berupa  jalur  atau  rute  perjalanan  yang melibatkan proses proses crossover atau proses pertukaran gen dalam kromosom sehingga dapat menghasilkan keturunan baru dari pasangan kromosom tersebut.Algoritma Genetika merupakan salah  satu  metode  yang  dapat  digunakan  untuk  menyelesaikan traveling  salesman  problem . Walaupun  telah  banyak  penelitian  yang  menggunakan  algoritma  genetika  dalam  penerapannya untuk traveling salesman problem , namun belum pernah diketahui pada probabilitas crossover, mutasi  atau  jumlah  populasi  keberapakah  yang  menunjukkan  mana crossover yang  lebih  baik antara cycle crossover (CX) dan partial mapped crossover (PMX). Oleh karena itu, peneliti akan membandingkan  kedua  metode  CX  dan  PMX  untuk  mengetahui  metode  manakah  yang memberikan solusi lebih optimal.

## II. MATERI DAN METODE
2.1 Teori Graf
Graf adalah kumpulan simpul/kota yang dihubungkan satu sama lain melalui sisi/busur. Suatu graf G terdiri dari dua himpunan yakni himpunan V dan himpunan E.
2.2 Traveling Salesman Problem (TSP)
Salah  satu  bentuk  masalah  optimasi  yang  memiliki  lintasan  dan  sirkuit  Hamilton  adalah Traveling Salesman Problem (TSP). Traveling salesman problem merupakan suatu permasalahan dimana seorang salesman harus melewati sejumlah kota tiap satu kali dan kembali ke kota awal. Yang perlu dicari adalah rute terpendek bagi salesman tersebut. 2.3 Algoritma Genetika
Algoritma genetik pertama kali dikembangkan oleh John Holland dari Universitas Michingan pada tahun 1975. John Holland mengatakan bahwa setiap masalah yang berbentuk adaptasi (alami maupun buatan) dapat diformulasikan dalam betuk terminalogi genetika. Dalam menyusun suatu algoritma  genetika  menjadi  program,  maka  diperlukan  beberapa  tahapan  proses,  yaitu  proses encoding ,  proses selection , crossover,  mutation, dan  pengulangan  proses  sebelumnya  hingga menemukan solusi terbaik. Flowchart proses algoritma genetika dapat dilihat pada Gambar 2.1.
Mulai Encoding Seleksi Crossover Mutasi Solusi Terbaik selesai Tidak Ya Gambar 2.1  Flowchart Proses Algoritma Genetika
1. Teknik Encoding
Ada  bermacam-macam  teknik encoding yang  dapat  dilakukan  dalam  algoritma  genetika. Beberapa teknik encoding itu antara lain adalah binary encoding , permutation encoding , value encoding serta tree encoding .
2. Proses Seleksi
Selection  merupakan  suatu  proses  untuk  mendapatkan  kromosom-  kromosom berkualitas pada generasi berikutnya. Metode seleksi roulette wheel merupakan metode seleksi yang menggunakan prinsip kerja roda roulette.

## 3. Crossover
Ada  beberapa  macam  teknik crossover yang  dapat  digunakan  pada  penyelesaian traveling salesman problem , diantaranya Cycle Crossover (CX) dan Partial Mapped Crossover (PMX). Prosedur CX  :
1) Tentukan pola cycle dari dua parent , yang dimulai dari posisi awal gen kromosom parent 1
2) Bentuk anak 1 dengan :
a. Tandai allele-allele pada parent 1 yang termasuk dalam pola cycle (hasil dari langkah 1)
b. Ambil secara berurutan alle-allele yang tidak ditandai pada parent 2 (yang tidak termasuk pada pola cycle ) untuk diisi pada gen yang masih kosong pada parent 1
3) Bentuk anak 2 dengan
a. Tandai allele-allele pada parent 2 yang termasuk dalam pola cycle (hasil dari langkah 1)
b. Ambil secara berurutan allele-allele yang tidak ditandai pada parent 2 (yang tidak termasuk dalam pola cycle hasil dari langkah 1) untuk diisi pada gen yan masih kosong pada parent 2.
Prosedur PMX  :
a. Tentukan 2 bilangan secara acak, dimana kedua bilangan ini akan dijadikan posisi awal dan akhir gen dari suatu kromosom yang akan mengalami crossover . Tandai allele-allele yang akan di crossover
b. Tukarkan allele yang ditandai antara parent 1 dan parent 2
c. Tentukan hubungan mapping antar allele-allele yang ditandai jika ada allele yang sama antara allele yang ditandai dan allele yang tidak ditandai untuk setiap parent maka ganti allele yang tidak ditandai dengan allele hasil mapping .
4. Mutasi
Pada  kasus  TSP  ini  skema  mutasi  yang  digunakan  adalah swapping  mutation .  Jumlah kromosom  yang  mengalami  mutasi  dalam  satu  populasi  ditentukan  oleh  parameter probabilitas mutasi (p m ) .

## 2.4 Metode Penelitian
Pengujian  akan  dilakukan  sebanyak  8  kali  untuk  masing-masing  jumlah  kota  yang diinputkan.  Travelling  Salesman  Problem  menggunakan  graf  lengkap  dan  berbobot  untuk penyelesaiannya.  Gambar  2.2  adalah  matriks  ketetanggaan  dari  20  kota  yang  dijadikan sampel dalam penelitian.

## Gambar 2.2 Matriks Ketentanggaan[1]

## 2.3 Rancangan Algoritma Genetika TSP
Pada Algoritma Genetika TSP terdapat beberapa tahap, yaitu sebagai berikut : Langkah 1. Proses Inisialisasi atau Encoding. Pada Gambar 2.3 adalah salah satu inisialisi kromosom untuk jumlah kota = 10
Gambar 2.3 Contoh kromosom untuk jumlah kota = 10[1]
Langkah 2. Selection . Pada penelitian ini digunakan metode roulette wheel selection . Merujuk  pada  Gambar  2.2,  dalam roulette  wheel  selection ,  langkah  pertama  yang  dilakukan adalah (1) Hitung nilai fitness s ; (2) Hitung total fitness s untuk populasi; (3) Hitung probabilitas seleksi p k untuk setiap kromosom v k ; (4) Hitung probabilitas komulatif q k untuk setiap kromosom v k , selanjutnya diputar roda roulette sebanyak jumlah pop_size . Kromosom yang  ambil adalah kromosom yang memenuhi syarat q k-1 ≤  r k ≤ q k , apabila persamaan di atas terpenuhi maka akan dipilih kromosom ke- k ( v k ) sebagai induk.
Langkah  3.  Crossover dan  Mutasi.  Berdasarkan  uraian  diatas,  probabilitas crossover yang digunakan dalam pengujian ini adalah 0,1, 0,3; 0,5; dan 0,7. Sedangkan probabilitas mutasi yang digunakan adalah 0,01 dan 0,03.

## III. HASIL DAN PEMBAHASAN

## 3.1 Hasil Pengujian
Parameter  algoritma  genetika  yang  digunakan  dalam  pengujian  ini,  yaitu  :  (1) jumlah_generasi=1000; (2)  jumlah_populasi  =  100;  (3) probabilitas mutasi=0,01  dan  0,03;(4) probabilitas crossover = 0,10, 0,30, 0,50 dan  0,70; (5) threshold= 0,80; (6) banyaknya_kota=5, 10, 15 dan 20 kota. Hasil pengujian didapat generasi dan fitness terbaik  dari jumlah kota sebanyak 5,  10,  15,  dan  20  kota  untuk  metode cycle  crossover dan partial  mapped  crossover dengan menggunakan probabilitas mutasi 0,1 dan 0,3 juga probabilitas crossover nya 0,1, 0,3, 0,5 dan 0,7 dapat dilihat pada Gambar 3.1 dan Gambar 3.2 di bawah sebagai berikut.
Gambar 3.1 Grafik Perbandingan generasi dan fitness terbaik dari metode Cycle crossover dan partial mapped crossover untuk : (a) jumlah kota= 5, (b) jumlah kota= 10,  (c) jumlah kota=15 dan  (d) jumlah kota=20
Hasil  pengujian  gambar  3.1  bahwa  metode crossover PMX    lebih  baik  dalam menyelesaikan kasus TSP dibandingkan dengan metode  CX. Hal ini dapat dilihat  Gambar 3.1, menunjukkan rata-rata generasi dan fitness terbaik untuk pengujian kota 5,10,15 dan 20, metode PMX  memiliki  rata-rata  generasi  dan  fitness  terbaik  lebih    kecil  dari    metode  CX.  sehingga metode PMX merupakan metode yang  memberikan solusi yang optimal dibandingkan dengan metode CX.
Ditinjau dari rata-rata generasi  dan fitness terbaik pada Gambar 3.1 untuk  jumlah kota yang berbeda,  metode  PMX selalu unggul dalam tingkat kekonsistenan memberikan solusi yang sama. Dari hasil penelitian ini, metode PMX merupakan metode yang dianjurkan untuk dipakai dalam  menyelesaikan  kasus  TSP  dengan  melihat  kecepatan  dan  ketepatan  dalam  menemukan solusi pencarian rute yang terbaik.
Gambar 3.2 Grafik Perbandingan waktu terbaik dari metode Cycle crossover  dan partial mapped crossover untuk : (a) generasi = 100, (b) generasi = 500 Gambar 3.2 terlihat bahwa perbandingan antara kedua metode crossover yang digunakan yakni cycle crossover dan partial mapped crossover untuk metode cycle crossover jumlah rata- rata waktu terbaik proses pencarian  rute yang optimal lebih tinggi dari metode partial mapped crossover. Pada Gambar 3.2 juga terlihat bahwa  jumlah waktu yang didapat pada generasi 100 lebih kecil dari generasi 500 sehingga dapat dikatakan bahwa  jumlah generasi yang besar  dapat mempengaruhi jumlah waktu akan semakin lama  untuk mendapatkan solusi yang  lebih optimal.

## IV. KESIMPULAN DAN SARAN

## 5.1  Kesimpulan
Pada  penelitian  ini    metode partial  mapped  crossover memberikan  solusi  yang  terbaik dalam kasus pencarian rute terpendek dengan rata-rata nilai dalam 8 kali pengujian diperoleh nilai rata-rata generasi terbaik  sebesar 104,0469 , fitness terbaik sebesar 3446031 dan waktu pengujian tercepat untuk generasi 100 sebesar 1,1035 second dan untuk generasi 500 sebesar 1,5846 second. Solusi yang diberikan metode PMX lebih baik dibandingkan algoritma Djikstra.
5.2  Saran
Sistem  perbandingan  metode cycle  crossover dan partial  mapped  crossover pada penelitian  ini  masih  merupakan    operator  algoritma  yang  standar.  Oleh  sebab  itu  untuk pengembangan sistem ke depan diharapkan dapat menggunakan metode – metode lain yang telah mengalami pengembangan dari metode – metode terdahulu.

## UCAPAN TERIMA KASIH
Penulis mengucapkan terima kasih kepada Bapak  Arfan Y. Mauko,S.T.,MCs selaku penguji.

## DAFTAR PUSTAKA
[1]  Kolo,  Theresia.  2018,  Perbandingan  Kinerja  Metode Cycle  Crossover (CX)  dan Partial Mapped  Crossover (PMX)    dalam  Algoritma  Genetika  pada  penyelesaian Traveling Salesman Problem (TSP). Skripsi Ilmu Komputer. Kupang: Universitas Nusa Cendana.
[2] Arzain, Jayanti., 2009. Implementasi Algoritma Genetika untuk Traveling Salesman Problem .Skripsi Universitas Sumatera Utara Medan.
[3] Basuki,Achmad., 2006. Algoritma Genetika, Politeknik Elektronika Negeri Surabaya.
[4] Fanggidae, Adriana. 2015. Algoritma Genetika dan penerapannya . Kupang:   Universitas Nusa Cendana.Kupang.
[5]   Munir, Rinaldi. 2005. Matematika Diskrit. Bandung : Informatika.Bandung.