Prosiding Matematika ISSN:

Prosiding Matematika

ISSN: 2460-6464

Representasi Matriks untuk Proses Crossover Pada Algoritma Genetika untuk Optimasi Travelling Salesman Problem Matrix Representation for The Crossover on Genetic Algorithm for Optimization Travelling Salesman Problem 1

Ismi Fadhilah, 2Yurika Permanasari, 3Erwin Harahap

1,2,3

Prodi Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Islam Bandung, Jl. Tamansari No.1 Bandung 40116 email: [email protected], [email protected], [email protected]

Abstract. Travelling Salesman Problem (TSP) is one of combinatorial optimization problems in everyday life. TSP is about someone who had to visit all the cities exactly once and return to the initial city with minimal distances. TSP can be solved using Genetic Algorithms. In a Genetic Algorithm, a matrix representation represents chromosomes which indicates a journey. If in the course of the past n number of city will set up a matrix n x n. The matrix element Mij with row i and column j where entry M (i, j) will be equal to 1 if and only if the city i before the city j visited in one trip. In addition to the M (i, j) = 0. Crossover is a mechanism that is owned by the Genetic Algorithm to combine the two chromosomes to produce offspring inherited basic characteristics of the parent. Genetic Algorithms in addition to involve the population early in the optimization process will also generate new populations through the crossover process, so as to provide optimal number of variables is not just a single solution. From the results of the crossover process in the case of TSP passing through six cities, there are two the best offspring with the same finess value which is 0.014. Genetic Algorithms can be stopped on the second generation due to successive received the highest fitness value unchanged. Keywords: Travelling Salesman Program (TSP), Genetic Algorithm, Matrix Representation, Crossover Process

Abstrak. Travelling Salesman Problem (TSP) merupakan salah satu permasalahan optimasi kombinatorial yang biasa terjadi dalam kehidupan sehari-hari. Permasalahan TSP yaitu mengenai seseorang yang harus mengunjungi semua kota tepat satu kali dan kembali ke kota awal dengan jarak tempuh minimal. TSP dapat diselesaikan dengan menggunakan metode Algoritma Genetika. Dalam Algoritma Genetika, representasi matriks merupakan representasi kromosom yang menunjukan sebuah perjalanan. Jika dalam perjalanan tersebut melewati n kota maka akan dibentuk matriks n x n. Matriks elemen Mij dengan baris i dan kolom j dimana entry M(i,j) akan bernilai 1 jika dan hanya jika kota i dikunjungi sebelum kota j dalam satu perjalanan tersebut, selain itu M(i,j)=0. Crossover adalah mekanisme yang dimiliki algoritma genetika dengan menggabungkan dua kromosom sehingga menghasilkan anak kromosom yang mewarisi ciri-ciri dasar dari parent. Algoritma Genetika selain melibatkan populasi awal dalam proses optimasi juga membangkitkan populasi baru melalui proses crossover, sehingga dapat memberikan daftar variabel yang optimal bukan hanya solusi tunggal. Dari hasil proses crossover dalam contoh kasus TSP melewati 6 kota, terdapat 2 kromosom anak terbaik dengan nilai finess yang sama yaitu 0.014. Algoritma Genetika dapat berhenti pada generasi II karena berturut-turut mendapat nilai fitness tertinggi yang tidak berubah Kata kunci : Travelling Salesman Program (TSP), Algoritma Genetika, Representasi Matriks, Proses Crossover

158

Representasi Matriks untuk Proses Crossover pada Algoritma Genetika untuk ...| 159

A. Pendahuluan Travelling Salesman Problem (TSP) merupakan salah satu permasalahan optimasi kombinatorial yang biasa terjadi. Permasalahan TSP yaitu mengenai seseorang yang harus mengunjungi semua kota tepat satu kali dan kembali ke kota awal dengan jarak tempuh dan biaya minimal. Perjalanan dalam penjualan tersebut dapat dimodelkan dalam bentuk graf. Graf adalah himpunan yang terdiri dari verteks dan garis. Verteks merepresentasikan kota, garis merepresentasikan jalan yang menghubungkan dua kota, dan bobot merepresentasikan biaya, jarak tempuh, atau waktu perjalanan. TSP dapat diselesaikan dengan menggunakan metode Algoritma Genetika. Algoritama Genetika adalah algoritma pencarian optimasi yang didasarkan atas mekanisme evolusi biologis yaitu genetik dan seleksi alam. Variabel solusi dikodekan kedalam struktur gen, yang merupakan karakteristik dari solusi. Himpunan solusi pada algoritma genetika yang dihasilkan secara acak disebut populasi, sedangkan setiap individu dalam populasi disebut kromosom yang merupakan representasi dari solusi. Kromosom-kromosom berevolusi dalam suatu proses iterasi berkelanjutan yang disebut generasi. Pada setiap generasi, kromosom akan melalui proses evaluasi dengan menggunakan alat ukur yaitu fungsi fitness. Nilai fitness suatu kromosom akan menunjukkan kualitas kromosom dalam populasi tersebut. Generasi berikutnya dikenal dengan istilah anak (offspring) yang terbentuk dari gabungan dua kromosom generasi sekarang yang bertindak sebagai induk (parent) dengan menggunakan operator penyilangan (crossover). Cara merepresentasikan permasalahan dalam kromosom merupakan suatu hal yang penting dalam Algoritma Genetika. Ada beberapa model representasi kromosom yang dipergunakan untuk proses croosover Algoritma Genetika, salah satunya adalah representasi matriks. Berdasarkan latar belakang yang telah diuraikan, maka perumusan masalah dalam penelitian ini sebagai berikut: “Bagaimana proses dan hasil crossover dengan representasi matriks pada Algoritma Genetika untuk meyelesaikan TSP?”. Selanjutnya, tujuan dalam penelitian ini diuraikan dalam pokok-pokok sebagai berikut: 1. Untuk memahami representasi matriks Traveling Salesman Problem pada Algoritma Genetika. 2. Untuk mengetahui proses crossover dengan representasi matriks pada Algoritma Genetika.. 3. Untuk mengetahui hasil crossover yang menghasilkan kromosom anak terbaik pada suatu generasi. B. Landasan Teori Algoritma genetika pertama kali dikembangkan oleh John Holland dari Univeristas Michigan (1975). John Holland mengatakan bahwa setiap masalah yang berbentuk adaptasi (alami maupun buatan) dapat diformulasikan dalam terminologi genetika. Algoritma genetika adalah simulasi dari proses evolusi Darwin dan operasi genetika atas kromosom. Pada algoritma ini, teknik pencarian dilakukan sekaligus atas sejumlah solusi yang mungkin yang dikenal dengan istilah populasi. Individu yang terdapat dalam suatu populasi disebut dengan kromosom. Kromosom ini merupakan suatu solusi yang masih berbentuk simbol. Populasi awal dibangun secara acak, Selanjutnya, kromosom untuk generasi berikutnya diperoleh dengan melakukan operasi genetika (Crossover dan Mutasi). Matematika, Gelombang 2, Tahun Akademik 2015-2016

160 |

Ismi Fadhilah, et al.

Operasi genetika ini dilakukan dengan tujuan untuk dapat menghasilkan sejumlah kromosom baru (offspring) yang memberikan solusi lebih baik. Evaluasi terhadap masing-masing kromosom dilakukan dengan menghitung nilai fitness kromosom tersebut. Salah satu nilai fitness yang bisa dipakai adalah dengan menghitung nilai fungsi tujuan. Umumnya jika diasumsikan bahwa nilai fitness semakin besar, maka sistem yang dihasilkan semakin baik. Sangat mungkin pada generasi awal, kromosom yang dibangkitkan akan memiliki nilai fitness yang kecil. Proses seleksi dilakukan untuk memperoleh kromosom generasi berikutnya. Salah satu metode seleksi yang sering digunakan adalah Roulette Wheel. Pada umumnya, proses seleksi bertujuan agar populasi kromosom pada generasi berikutnya mempunyai nilai fitness yang lebih baik. Proses pembentukan generasi baru dengan operasi genetika dilakukan hingga terpenuhi kriteria pemberhentian. Ada beberapa kriteria pemberhentian yang sering digunakan diantaranya: 1. Berhenti pada generasi tertentu (maximum generation). 2. Berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness tertinggi tidak berubah. 3. Berhenti bila dalam beberapa generasi berikutnya tidak didapatkan perubahan nilai fitness yang lebih tinggi. Representasi Kromosom Pada implementasi Algoritma Genetika, suatu hal yang pertama kali harus dipertimbangkan adalah representasi kandidat solusi (kromosom) yang sesuai untuk persoalan yang akan diselesaikan. Proses ini dikenal dengan istilah encoding. Kita harus menyatakan karakteristik dari persoalan dalam bentuk sekumpulan string (bilangan atau alphabet). Representasi kromosom ini merupakan struktur data yang mempresentikan kandidat solusi. Representasi yang baik haruslah mampu mempresentasikan semua parameter dan solusi yang mungkin untuk persoalan yang akan diselesaikan. Penentuan metode representasi sangat berpengaruh pada komponen-komponen Algoritma Genetika misalnya evaluasi, crossover, mutasi dan seleksi. Karenanya, metode representasi mempunyai peran yang sangat penting terhadap efektifitas dan efisiensi dari Algoritma Genetika. Contoh kromosom yang menggunakan metode representasi permutasi dapat dilihat pada Gambar 1: 5

2

3

1

4

9

7

6

8

Gambar 1. Contoh Kromosom Representasi Permutasi Nilai Fitness Fitness adalah nilai yang dimiliki oleh masing-masing individu untuk menentukan tingkat kesesuaian individu tersebut dengan kriteria atau tujuan (obyektif) permasalahan yang ingin dicapai . Nilai fitness suatu kromosom menggambarkan kualitas kromosom dalam populasi tersebut Pada pembahasan ini nilai fitness dapat dihitung dengan rumus : eval(vi)= ⁄

Volume 2, No.2, Tahun 2016


Seleksi Proses seleksi adalah proses untuk menyaring calon generasi yang baru. Induk yang baik akan mampu untuk menghasilkan anak yang baik. Semakin tinggi nilai fitness dari suatu individu maka semakin besar kemungkinannya untuk terpilih. Kemampuan algoritma genetika untuk memproduksi kromosom yang lebih baik secara progresif tergantung pada penekanan selektif (selective pressure) yang diterapkan ke populasi. Penekanan selektif dapat diterapkan dalam dua cara. Cara pertama adalah membuat lebih banyak kromosom anak yang dipelihara dalam populasi dan memilih hanya kromosom-kromosom terbaik bagi generasi berikutnya. Walaupun orang tua dipilih secara acak, metode ini akan terus menghasilkan kromosom yang lebih baik. Cara lain menerapkan penekanan selektif adalah memilih orang tua yang lebih baik ketika membuat keturunan baru. Dengan metode ini, hanya kromosom sejumlah populasi yang akan disimpan untuk generasi selanjutnya. Metode untuk seleksi yang sering digunakan salah satunya adalah seleksi roda roulet (roulette wheel selection). Metode seleksi roulette wheel merupakan metode yang paling sederhana serta paling banyak digunakan, dan sering juga dikenal dengan nama stochastic sampling with replacement. Pada metode ini, orangtua dipilih berdasarkan nilai fitness, semakin baik nilai fitness maka semakin besar kemungkinannya untuk terpilih. Diandaikan semua kromosom diletakkan pada sebuah roda roulet, besarnya kemungkinan bagi setiap kromosom adalah tergantung dari nilai fitness. Dalam Algoritma Genetika Parameter genetika berguna dalam pengendalian operator-operator genetika yang digunakan. Pemilihan nilai-nilai parameter sangat berpengaruh terhadap kinerja Algoritma Genetika. Parameter yang sering digunakan adalah ukuran populasi, Probabilitas Crossover, Probabilitas Mutasi. C. Hasil Penelitian dan Pembahasan Diberikan sebuah kasus perjalanan yang harus melewati 6 kota dan kembali ke kota asal. Jika edge merepresentasikan satu kota terhubung ke kota lain dengan bobot edge menunjukkan jarak antar kota tersebut maka dibentuk graf sebagai berikut:

Ditetapkan p_C = 0.25, didapatkan kromosom yang terpilih untuk proses Matematika, Gelombang 2, Tahun Akademik 2015-2016

162 |


crossover yaitu v5’= 5 2 1 3 6 4 v10’= 4 5 1 3 6 2 v16’= 3 6 5 4 2 1 v24’= 4 1 5 2 3 6 v28’= 3 2 1 4 6 5 v34’= 6 3 1 4 2 5 v39’= 4 1 5 2 3 6 v48’= 1 3 4 5 6 2 v49’= 4 6 3 1 2 5 v54’= 5 2 6 3 4 1 Dari kromosom tersebut dapat dilakukan proses Crossover. Untuk crossover pertama dipilih Parent 1 = v5’ = 5 2 1 3 6 4 Parent 2 = v10’= 4 5 1 3 6 2 Kromosom yang terpilih diubah kedalam representasi Matriks, menjadi M1 dan M2. Parent 1 dibentuk menjadi M1. Parent 2 dibentuk menjadi M2. 1 2 3 4 5 6

1 0 1 0 0 1 0

2 0 0 0 0 1 0

3 1 1 0 0 1 0

4 1 1 1 0 1 1

5 0 0 0 0 0 0

6 1 1 1 0 1 0

Gambar 2. Matriks 1

1 2 3 4 5 6

1

2

3

4

5

6

0 0 0 1 1 0

1 0 1 1 1 1

1 0 0 1 1 0

0 0 0 0 0 0

0 0 0 1 0 0

1 0 1 1 1 0

Gambar 3. Matriks 2 Selanjutnya di bentuk Matriks ditunjukkan pada gambar 4. 1 2 1 0 0 2 0 0 3 0 0 4 0 0 5 1 1 6 0 0

3 dari irisan Matriks 1 dan Matriks 2 3 1 0 0 0 1 0

4 0 0 0 0 0 0

5 0 0 0 0 0 0

6 1 0 1 0 1 0

Gambar 4. Matriks 3 Selanjutnya memilih salah satu parent dari M1 dan M2 untuk menjadi Matriks Volume 2, No.2, Tahun 2016


4 lalu beberapa elemen 1 dari M4 dan elemen 1 baru di tambahkan pada Matriks M3, sehingga jumlah elemen 1 pada M3 sebanyak menunjukkan perjalanan akhir yang mungkin. Matriks M4 dipilih M1, ditunjukkan pada Gambar 5. 1 2 3 4 5 6 1 0 0 1 1 0 1 2 1 0 1 1 0 1 3 0 0 0 1 0 1 4 0 0 0 0 0 0 5 1 1 1 1 0 1 6 0 0 0 1 0 0 Gambar 5. Matriks 4 Kromosom anak pertama adalah 1 2 3 4 5 6

1 0 1 0 0 1 0

2 0 0 0 0 1 0

3 1 1 0 0 1 0

4 1 1 1 0 1 0

5 0 0 0 0 0 0

6 1 1 1 1 1 0

Gambar 6. Matriks kromosom anak pertama Matriks kromosom anak pertama menunjukkan perjalanan 5- 2 - 1 - 3 - 4 - 6. Untuk matriks 4 (M4) dipilih M2, ditunjukkan pada Gambar 7 1 2 3 4 5 6 1 0 1 1 0 0 1 2 0 0 0 0 0 0 3 0 1 0 0 0 1 4 1 1 1 0 1 1 5 1 1 1 0 0 1 6 0 1 0 0 0 0 Gambar 7. Matriks 4 Kromosom anak kedua adalah 1 2 3 4 5 6

1 0 0 0 1 1 0

2 1 0 1 1 1 0

3 1 0 1 1 1 0

4 0 0 0 0 0 0

5 0 0 0 1 0 0

6 1 1 1 1 1 0

Gambar 8. Matriks kromosom anak kedua Matriks kromosom anak kedua menujukkan perjalanan 4- 5 - 1 - 3 - 2 - 6. Matematika, Gelombang 2, Tahun Akademik 2015-2016

164 |


Dengan cara yang sama dapat dilakukan untuk mencari offspring dari parent yang berbeda. Sehingga diperoleh hasil crossover dari representasi matriks sebagai berikut: v1” = 5 - 2 - 1 - 3 - 4 - 6 v2” = 4 - 5 - 1 - 3 - 2 - 6 v3” = 3 - 6 - 4 - 5 - 2 - 1 v4” = 4 - 1 - 5 - 2 - 6 - 3 v5” = 3 - 6 - 1 - 4 - 2 - 5 v6” = 6 - 3 - 1 - 4 - 5 - 2 v7” = 4 - 1 - 5 - 3 - 2 - 6 v8” = 1 - 3 - 4 - 5 - 2 - 6 v9” = 4 - 6 - 3 - 2 - 1 - 5 v10”= 5 - 2 - 6 - 3 - 1 - 4 Setelah nilai fitness dihitung, ditunjukkan pada tabel 1 Tabel 1. Populasi Baru dan Nilai Fitness Populasi Baru Nilai Fitness v1” = 5 - 2 - 1 - 3 - 4 - 6

0.010

v2” = 4 - 5 - 1 - 3 - 2 - 6

0.011

v3” = 3 - 6 - 4 - 5 - 2 - 1

0.014

v4” = 4 - 1 - 5 - 2 - 6 - 3

0.011

v5” = 3 - 6 - 1 - 4 - 2 - 5

0.011

v6” = 6 - 3 - 1 - 4 - 5 - 2

0.013

v7” = 4 - 1 - 5 - 3 - 2 - 6

0.009

v8” = 1 - 3 - 4 - 5 - 2 - 6

0.012

v9” = 4 - 6 - 3 - 2 - 1 - 5

0.013

v10”= 5 - 2 - 6 - 3 - 1 - 4

0.013

Dari tabel 1 menunjukkan urutan jalur terbaik untuk metode crossover dengan menggunakan representasi matriks adalah 3- 6 - 4 - 5 - 2 - 1. Memiliki nilai Fitness 0.014 dengan panjang perjalanan 71.3 km. Dengan cara yang sama bisa dilakukan untuk generasi selanjutnya, Yang terpilih menjadi parent adalah v1’ dan v6’. v1’= 4 6 3 2 1 5 v6’= 4 5 1 3 2 6 Urutan jalur terbaik untuk metode crossover dengan menggunakan representasi matriks adalah 4- 6 - 3 - 1 - 2 - 5, Memiliki nilai Fitness 0.014 dengan panjang perjalanan 71.3 km.

Volume 2, No.2, Tahun 2016


D. Kesimpulan Dalam Algoritma Genetika, representasi matriks merupakan representasi kromosom yang menunjukan sebuah perjalanan. Jika dalam perjalanan tersebut melewati n kota maka akan dibentuk matriks n x n. Matriks elemen Mij dengan baris i dan kolom j dimana entry M(i,j) akan bernilai 1 jika dan hanya jika kota i dikunjungi sebelum kota j dalam satu perjalanan tersebut, selain itu M(i,j)=0 Proses crossover dengan representasi matriks yaitu mekanisme yang dimiliki algoritma genetika dengan menggabungkan dua kromosom yang direpresentasikan kedalam matriks dengan operator irisan sehingga menghasilkan anak kromosom yang mewarisi ciri-ciri dasar dari parent. Dari hasil proses crossover dalam contoh kasus TSP melewati 6 kota, terdapat 2 kromosom anak terbaik dengan nilai finess yang sama yaitu 0.014 dengan jarak perjalanan 71.3 km. Kedua jalur tersebut diperoleh setelah dua generasi. Algoritma Genetika dapat berhenti pada generasi II karena berturut-turut mendapat nilai fitness tertinggi yang tidak berubah. Daftar Pustaka Dajan, Anto.1996. Pengantar Metode Statistik Jilid II. Jakarta : PT Pustaka Indonesia LP3ES Indonesia. Lipschuts, S. Lipson, M. 2008. Schaums’s Outliner Matematika Diskrit, Edisi ketiga. Jakarta : Erlangga. Mischalewicz, Z. 1996. Genetic Algoritms + Data Structures = Evolution Programs, Third, Revised and Extended Edition. Berlin, Heidelberg, New York: SpringerVerlag. Munir, R. 2011. Matematika Diskrit. Bandung :Informatika. Syamsudin, Aries. 2004. Pengenalan Algoritma Genetik. (IlmuKomputer.com). Syarif, A. 2014. Algoritma Genetika Teori dan Aplikasi Edisi 2. Yogyakarta: Graha Ilmu.

Matematika, Gelombang 2, Tahun Akademik 2015-2016

Prosiding Matematika ISSN:

Recommend Documents