Implementasi Algoritme Genetika Dalam Optimasi Knapsack Problem Penentuan Objek Wisata Wilayah Malang Raya

Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer Vol. 2, No. 2, Februari 2018, hlm. 888-896

e-ISSN: 2548-964X http://j-ptiik.ub.ac.id

Implementasi Algoritme Genetika Dalam Optimasi Knapsack Problem Penentuan Objek Wisata Wilayah Malang Raya Abdul Fatih1, Budi Darma Setiawan2, Candra Dewi3 Program Studi Teknik Informatika, Fakultas Ilmu Komputer, Universitas Brawijaya Email: [email protected], [email protected], [email protected] Abstrak Pariwisata menjadi komoditas yang tidak terpisahkan lagi bagi kehidupan manusia. Beberapa wilayah di Indonesia menjadikan pariwisata sebagai khas daerahnya, salah satunya adalah wilayah Malang Raya. Bentuk perhatian pada sektor pariwisata salah satunya dengan digiatkan pembangunan objek wisata baru. Semakin banyak objek wisata semakin memanjakan wisatawan sekaligus memberi masalah baru. Wisatawan cenderung tidak memiliki waktu yang cukup untuk menghabiskan semua objek wisata yang ada. Wisatawan mengalami permasalahan knapsack problem dimana harus menentukan susunan objek wisata yang dikunjungi dengan keterbatasan waktu yang dimiliki. Optimasi knapsack problem ini dapat diselesaikan dengan algoritme genetika. Algoritme genetika akan melakukan pembentukan chromosome sebagai representasi solusi. Struktur algoritme genetika terdiri dari inisialisasi, reproduksi, evaluasi, dan seleksi. Proses algoritme genetika dilakukan sebanyak 50 generasi dengan jumlah populasi 100 sedangkan nilai pc sebesar 0,7 dan nilai pm sebesar 0,8. Hasil pengolahan algoritme genetika terhadap studi kasus yang diujikan menghasilkan solusi berupa susunan objek wisata yang cenderung berdekatan dan mengelompok pada daerah tertentu. Kata kunci: objek wisata Wilayah Malang Raya, knapsack problem, algoritme genetika. Abstract Tourism has become commodity that can’t be separated from human’s life. There are some areas in Indonesia make tourism into the specific characteristics of their region which one is Malang Raya. The form of attention in the tourism sector is activated the building of new tourism objects. There was more tourism object than before will be more coddling for the tourists and also give a new problem. The tourist have knapsack problem which the tourist must decided all of tourism objects list that visited with the limited time. The optimization of knapsack problem can be resolved by using genetic algorithm. The genetic algorithm will make a formation of chromosome as representation of solution. The structures of genetic algorithm consist of initialization, reproduction, evaluation, and selection. The process of genetic algorithm did in the 50 generations with 100 populations whereas the pc value is 0, 7 and the value of pm is 0, 8. Result of processing genetic algorithm towards case study that has been tested gave the solution resemble to nearby tourism areas list and grouping in the certain areas. Keywords: tourism objects Malang Raya, knapsack problem, genetic algorithm. selanjutnya Kotamadya Malang, dan terakhir Kotamadya Batu. Ketiga Daerah Tingkat II ini biasanya dikenal dengan Wilayah Malang Raya. Seiring semakin dikenalnya Wilayah Malang Raya sebagai kota pariwisata, turut memengaruhi grafik pendapatan daerah penghasil apel ini. Kesadaran tentang pentingnya sektor pariwisata membuat perhatian di sektor ini terus digiatkan. Perhatian dapat berbentuk pembangunan yang memerhatikan faktor potensi dan prioritas tiap daerah, serta memerlukan pengembangan

1. PENDAHULUAN Pariwisata telah menjadi komoditas yang tidak terpisahkan lagi dalam kehidupan manusia. Pentingnya komoditas ini telah membuat beberapa daerah di Indonesia menjadikan pariwisata sebagai khas daerahnya. Wilayah Malang adalah salah satu daerah di Indonesia yang dikenal secara luas melalui daya tarik pariwisatanya. Wilayah Malang terdiri dari tiga daerah wilayah administrasi tingkat II (Dati II). Petama adalah wilayah Kabupaten Malang, Fakultas Ilmu Komputer Universitas Brawijaya

888

Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer

Teknologi Informasi dan Telekomunikasi (Hartoko, 2009). Salah satu bentuk perhatian pada sektor pariwisata adalah dengan terus digiatkannya pembangunan objek wisata baru. Objek wisata yang terus bermunculan semakin memanjakan wisatawan sekaligus memberi masalah baru. Wisatawan cenderung tidak memiliki waktu cukup untuk menghabiskan semua objek wisata yang ada. Wisatawan harus memilih objek wisata dengan sebaik-baiknya agar waktu yang dimiliki dapat dipergunakan dengan maksimal. Permasalahan yang didapati oleh para wisatawan ini dapat dikategorikan ke dalam knapsack problem. Knapsack problem biasa diibaratkan kondisi suatu wadah yang memiliki daya tampung tertentu sedang dihadapkan pada banyaknya pilihan barang yang akan dimasukkan kedalamnya, maka diperlukan untuk memilah barang mana saja yang dapat dimasukkan sesuai dengan kapasitas wadah supaya mendapatkan keuntungan yang sebesarbesarnya atau keuntungan maksimal (Diah, et al., 2010). Wisatawan harus memilih objek wisata yang ingin dikunjungi dalam keterbatasan waktu yang dimiliki. Semakin banyak objek wisata yang dapat dikunjungi akan semakin baik. Kesalahan menentukan objek wisata dan salah membuat urutan mana yang harus dikunjungi dapat membuat banyak waktu terbuang sia-sia atau habis dalam perjalanan. Knapsack problem pada penelitian ini termasuk tipe 0/1 Knapsack problem, dimana setiap barang hanya terdapat satu unit, yakni barang itu dibawa atau ditinggalkan (Diah, et al., 2010). Artinya, suatu objek wisata berlaku aturan dikunjungi atau tidak dikunjungi. Knapsack problem disini juga bersifat permutasi, yakni memperhatikan urutan objek wisata yang dikunjungi. Banyaknya objek wisata yang tersedia akan menyulitkan penentuan kombinasi optimal jika dilakukan secara konvensional (Kosasi, 2013). Permasalahan yang komplek akan sangat sulit dan menghabiskan sumber daya apabila diselesaikan dengan metode exact. Salah satu metode yang sering digunakan adalah metode heuristik. Metode heuristik merupakan metode yang didasari oleh intuisi baik pengamatan maupun percobaan untuk mencari solusi terbaik dari solusi yang telah dicapai sebelumnya (Widodo & Mahmudy, 2010). Anggota keluarga metode hueristik yang sesuai dengan permasalahan ini adalah Fakultas Ilmu Komputer, Universitas Brawijaya

889

algoritme genetika. Knapsack problem membutuhkan pemilihan solusi untuk dipecahkan. Hal tersebut sesuai dengan kemampuan algoritme genetika untuk mencari solusi optimum (Jayanti, 2015). Algoritme genetika pada penelitian sebelumnya pernah digunakan untuk menyelesaikan masalah knapsack problem dalam bidang penentuan menu makanan. Dalam penelitian tersebut, menunjukkan bahwasanya algoritme genetika cocok digunakan untuk menyelesaikan permasalahan knaspsack problem (Ayuning, 2013). Algoritme Genetika merupakan algoritme yang paling popular dari keluarga algoritme evolusi, algoritme ini banyak digunakan untuk menyelesaikan masalah-masalah kompleks (Mahmudy, 2013). Metode ini menerapkan pencarian solusi menggunakan pendekatan evolusi biologis makhluk hidup untuk memecahkan suatu masalah (Widodo & Mahmudy, 2010). Algoritme Genetika terus mengalami perkembangan, semakin hari algoritme genetika dikembangkan untuk menuntaskan perhitungan matematika kompleksitas tinggi. Algoritme ini juga banyak digunakan untuk pengembangan di bidang fisika, biologi, ekonomi, sosiologi, dan lain-lainnya yang berhubungan dengan optimasi (Widodo & Mahmudy, 2010). Pada penelitian sebelumnya pernah dilakukan penelitian optimasi kunjungan objek wisata dengan menggunakan algoritme genetika. Dalam penelitian tersebut, individu pada algoritme genetika direpresentasikan secara permutasi. Setiap gen berisi urutan bilangan bulat dengan keterangan urutan posisi menunjukkan tempat dan bilangan menampilkan nomor urutan (Setiawan & Pinandito, 2016). Pada penelitian ini akan menggunakan bentuk representasi chromosome yang berbeda dari penelitian sebelumnya. Hal tersebut untuk mengetahui hasil optimasi algoritme genetika dengan bentuk representasi chromosome yang berbeda. Berlandaskan uraian yang telah disampaikan, maka dibuatlah implementasi algoritme genetika untuk mengoptimasi permasalahan yang dialami oleh wisatawan di Wilayah Malang Raya agar dapat memanfaatkan ketersediaan waktu sebaikbaiknya dari waktu yang ada. Dengan adanya aplikasi ini diharapkan dapat membantu wisatawan memanajemen objek wisata yang akan dikunjungi dan mengangkat pariwisata


890

Wilayah Malang Raya.

2, 3, …, n (Kashima, et al., 2009).

2. OBJEK WISATA

4. ALGORITME GENETIKA

Objek wisata Wilayah Malang Raya adalah tempat pariwisata yang tersebar di seluruh Wilayah Malang Raya yakni Kabupaten Malang, Kotamadya Malang, dan Kotamadya Batu. Destinasi wisata di Wilayah Malang Raya berada pada jumlah yang cukup banyak. Dalam penelitian ini digunakan beberapa objek wisata yang mewakili dari setiap destinasi wisata yang ada. Setiap objek wisata yang termasuk ke dalam daftar objek penelitian, akan dicatat koordinatnya melalui data yang disediakan oleh google maps. Setiap letak koordinat akan dihitung jarak antar objek wisata, setiap jarak akan dikonversi menjadi lama waktu tempuh, lama waktu tempuh tersebut juga didapat dari data yang disediakan oleh google maps navigasi.

Algoritme ini populer untuk digunakan menghadapai masalah optimasi yang model matematikanya kompleks atau susah dibangun (Mahmudy, 2013). Perancangan algoritme genetika meliputi bagaimana mekanisme inisialisasi, proses reproduksi, evaluasi, tahap seleksi, dan batas iterasi. Algoritme genetika menurunkan generasi hinnga mencapai generasi ke-n. Nilai n ditentukan terlebih dahulu sebagai batas iterasi. Penentuan nilai n sebagai batas iterasi sering kali didasari pada penelitian-penelitian sebelumnya. Perancanga Algoritme genetika dapat dilihat pada Gambar 1. Mulai

3. KNAPSACK PROBLEM Knapsack problem dapat dimisalkan suatu kantong dengan kapasitas tertentu, sedangkan dihadapkan pada begitu banyak pilihan barang yang dapat dimasukkan kedalamnya, maka diperlukan untuk memilih barang mana saja yang dapat dimasukkan sesuai dengan kapasitas kantong supaya mendapatkan keuntungan yang sebesar-besarnya atau keuntungan maksimal (Diah, et al., 2010). Knapsack problem memiliki bermacammacam bentuk sesuai dengan tipikal dari permasalahan yang dialami. Salah satu bentuknya seperti tersedia barang yang setiap item-nya hanya berjumlah tunggal. Kondisi permasalahan dengan kriteria tersebut dinamakan 0/1 knapsack problem (Diah, et al., 2010). Bentuk lain dari knapsack problem adalah fractional knapsack problem. Bentuk knapsack problem ini memungkin suatu pilihan barang dibagi ke dalam satuan yang lebih kecil (Granmo & Oommen, 2010). Multiple dimensional knapsack problem (MDKP) adalah bentuk knapsack problem dengan kriteria memiliki beberapa bentuk constraint, seperti berat, harga, volume, dan seterusnya. Kantong yang direpresentasikan dengn variabel W dan barang dengan variabel n, maka hubungan keduanya dapat ditulis seperti berikut: W1, W2, W3, …, Wn dan n barang masing-masing memiliki cost (cj), j = 1, Fakultas Ilmu Komputer, Universitas Brawijaya

Inisialisasi

Reproduksi

Evaluasi

Seleksi

Salah

Batas Iterasi (n)

Benar

Hasil

Selesai

Gambar 1. Algoritme Genetika

4.1. Inisialisasi Inisialisasi membentuk chromosome yang berupa susunan variabel keputusan. Sejumlah chromosome diletakkan di penampungan yang disebut populasi. Panjang string chromosome dinamakan dengan istilah stringLen. Ukuran populasi disebut popSize (Mahmudy, 2013). Inisialisasi membangkitkan chromosome sebanyak popSize. Suatu iterasi menggunakan individu dari iterasi sebelumnya untuk dijadikan chromosome of parent. Alur program tersebut digambarkan dalam bagan flowchart


891

sesuai pada Gambar 2.

Mulai

Reproduksi

Mulai

Inisialisasi

Input pc Input popSize Input parent

Input popSize Input Daftar objek wisata

Salah

Membangkitkan chrimosome pertama

offspring = pc x popSize

Menerima chromosom dari hasil iterasi sebelumnya

Benar

i=0 sampai i=offspring Memilih chromosom terbaik

Mencari parent pertama (n) i=1 sampai i=popSize

i=1 sampai i=popSize

Mencari parent kedua (m) Membangkitkan chromosome

Membangkitkan chromosome

Simpan hasil chromosome (sebagai parent)

Simpan hasil chromosome

i

i

Mencari titik potong

Mengisi offspring dengan n (index 0 – titik potong)

Mengisi offspring dengan m (index sisa dari n Selesai

Memasukkan hasil offspring ke array

Gambar 2. Inisialisasi

i

Contoh inisialisasi dengan kasus popSIze 5 serta panjang stringLend chromosome-nya 20 ditunjukkan pada Gambar 3.

Menyimpan hasil offspring

Selesai

P1 P2 P3 P4 P5

a h a a n

t k t d i

g c s q l

p b j g h

s d g s d

i o i j m

b f c r c

k n d h b

q s r n j

c l q o e

h t p l s

d q o m f

j r h f t

m j f t q

o p b c a

e i k p k

l g e e o

r m m k r

n a l b g

f e n i p


Keterangan: - P1, P2, dan seterusnya adalah individu. - Huruf abjad merepresentasikan objek wisata. - Urutan abjad adalah urutan yang dikunjungi. 4.2. Reproduksi Reproduksi dilakukan untuk menghasilkan keturunan (offspring). Offspring didapat dari parent yang diproses oleh dua operator genetika, yakni tukar silang (crossover) dan mutasi (mutation) (Diah, et al., 2010). Metode crossover yang digunakan adalah one-cut-point. Metode ini menggunakan dua parent dan menentukan titik potong (cut point). Fungsi cut point sebagai pembatas antara sisi stringLen sebelah kiri dan kanan. Sisi stringLen antara kiri dan kanan ini kemudian disilangkan sehingga menghasilkan susunan chromosome baru (Mahmudy, 2013). Dalam melakukan crossover perlu ditentukan tingkat crossovernya (pc). Flowchart crossover ditampilkan pada Gambar 4.

Fakultas Ilmu Komputer, Universitas Brawijaya


Contoh parent dalam crossover yanki ditunjukkan pada Gambar 5. P3 a P2 h

t k

s c

j b

g d

i o

c f

d n

r s

q l

p t

o q

h r

f j

b p

k i

e g

m m

l a

n e

Gambar 5. Parent Crossover

Titik potong (cut point) didefinisikan bernilai 11. Proses crossover dijalan menghasilkan offspring C1 dan C2 sebagaimana pada Gambar 6. C1 C2

a o

t h

s f

j b

g k

i e

c m

d l

r n

q c

p d

h s

k t

b q

o r

f j

n p

l i

m g

e a

Gambar 6. Offspring Crossover

Metode mutasi yang digunakan adalah reciprocal exchange mutation. Mutasi ini dimulai dengan menentukan satu parent secara acak dari populasi yang ada. Langkah berikutnya adalah memilih dua posisi (exchange point / XP) secara random kemudian menukarkan nilai gen pada posisi pertama menjadi nilai gen posisi kedua, begitu juga nilai gen posisi kedua menjadi nilai gen posisi pertama (Mahmudy, 2013). Dalam melakukan mutasi perlu ditentukan tingkat mutasinya (pm). Flowchart mutasi disajikan pada Gambar 7.


Ket: - f = fitness - n = banyak objek wisata yang dikunjungi - y = lama waktu di objek wisata - x = lama tempuh ke objek wisata Flowchart yang menggambar evaluasi dapat dilihat pada Gambar 10.

Mulai

Reproduksi

892

Input pm Input popSize Input parent

offspring = pm x popSize

Mulai

Evaluasi

i=1 sampai i=offspring Input durasi Input individu Input lama di objek Input stringlend Input daftar objek wisata

Mencari parent

Salah

Koneksi ke database

Mencari titik tukar pertama (x) Benar Mengambil matrik jarak dari database

Mencari titik tukar kedua (y) Mengambil list objek dari database

Menukar gen pada index x degan index y

in=0 sampai in=sebanyak individu

X = 0, y = 0, waktu = 0, waktu lolos = 0, dan gen = 0

Memasukkan hasil offspring ke array

i=0 sampai i=stringLend

i

Mencari titik ordo matrik

Mengambil nilai x tabel matrik sesuai ordo

Menyimpan hasil offspring Menyimpan deret nilai x

Selesai i

Gambar 7. Mutasi C

Parent dan titik exchange point diperlihatkan pada Gambar 8. Nilai titik XP adalah 2 dan 15. P5 n i l h d m c b j e s f t q a k o r g p

Gambar 8. Parent Mutasi dan Titik XP

Hasil dari Gambar 9.

mutasi

ditunjukkan

pada

C9 n a l h d m c b j e s f t q i k o r g p Gambar 9. Offspring Mutasi

C

A

A

B


Mencarai lama objek wisata berdasarkan list yang ada (y)

Menyimpan deret nilai (y)

i

4.3. Evaluasi Evaluasi dilakukan untuk menghitung kebugaran setiap chromosome, baik chromosome parent maupun offspring. Chromosome dalam tahap ini biasa disebut dengan individu. Proses evaluasi adalah menentukan nilai fitness dari setiap individu. Batas gen terpilih diformulasikan sebagai berikut: ∑𝑡𝑛 ≤ 𝑡𝑚𝑎𝑥

(1)

Persamaan yang digunakan untuk menghitung nilai fitness dirumuskan sebagai berikut: 𝑓=

𝑛 𝑥 ∑𝑦 ∑𝑥

(2)



Gen indeks ke-i <= dengan waktu

B

Salah

Benar

Catat gen dan waktu lolos

i

Menghitung rumus fitness

in

Selesai

Gambar 10. Evaluasi


Berdasarkan batas gen yang terpilih maka penghitungan nilai fitness sebagai mana sesuai dengan apa yang dicontohkan dalam Tabel 1. Tabel 1. Perhitungan Fitness In P1 P2 P3 P4 P5 C1 C2 C3 C4 C5 C6 C7 C8 C9

Bentuk Chromosome t g p 72 45 110 120 84 60 h k c b 55 45 91 90 129 45 a t s j 72 45 110 120 91 90 a d q g 72 45 90 120 18 90 18 60 n i l h 63 120 21 120 158 90 a t s j 72 45 110 120 91 90 o h f b 83 120 122 45 h k a d 55 45 91 90 134 45 c b d o 83 45 114 45 38 120 h k c a 55 45 91 90 129 45 14 45 b d o f 78 45 38 120 44 120 a t g p 72 45 110 120 84 60 i b k q 45 120 35 45 173 90 n a l h 63 120 112 45 139 90 a

Fitness … 2,537593985 … 1,963636364 … 2,802197802 … 6,363636364 … 4,090909091 … 2,802197802 … 1,609756098 … 1,928571429 … 2,680851064 … 3,114186851 …

5,34375

… 2,537593985 … 3,023715415 … 2,436305732

4.4. Seleksi Seleksi pada intinya memilih individu mana yang dipertahankan di dalam populasi, baik individu dari parent atau offspring. Semakin besar nilai fitness semakin besar kemungkinan individu tersebut hidup. Metode seleksi menggunakan elitism selection, yakni mencari nilai fitness tertinggi yang akan diloloskan ke generasi selanjutnya. Pada tahap ini diberlakukan elitism sebesar 20% untuk memberi penyegaran individu pada generasi selanjutnya. Mulai

Seleksi

Input fitness

Mengurutkan fitnes dari yang terbesar ke yang terkecil

Mengambil individu ranking terbaik

Selesai

Gambar 11. Evaluasi

Sebagai contoh pada Tabel 2 menunjukkan Fakultas Ilmu Komputer, Universitas Brawijaya

893

perankingan fitness dalam implementasi mutasi. Tabel 2. Hasil Seleksi in P4 C6 P5 C5 C8 P3 C1 C4 P1 C7 C9 P2 C3 C2

a b n h i a a c a a n h h o

d d i k b t t b t t a k k h

q o l c k s s d g g l c a f

g f h a q j j o p p h b d b

s n d t c g g f s s d d q k

j s m g h i i n i j m o g e

r l c p d c c s b i c f s m

h t b s j d d l k c b n j l

susunan chromosome n o l m q r j p j e s f i b q d m o e l r q p o r q p h t q r j q c h d d r q o j e s f s l t q r n o l n c d s

f i t j r h k p j h t r m t

t g q m n f b i m f q j f q

c m a o f b o g o b i p t r

p a k e a k f m e k k i c j

e e o l t e n a l e o g p p

k k r r s m l e r m r m e i

b c g n g l m h n l g a b g

i h p f p n e k f n p e i a

fitness 6,363636364 5,34375 4,090909091 3,114186851 3,023715415 2,802197802 2,802197802 2,680851064 2,537593985 2,537593985 2,436305732 1,963636364 1,928571429 1,609756098

5. ANGKA INDEKS Angka indeks merupakan analisa data statistik untuk mengukur bagaimana perubahan fluktuatif data dari berbagai mancam komoditi dalam kurun waktu tertentu. Angka indeks biasanya didefinisikan dalam bentuk nilai persentase (%) dari dua periode waktu yang berbeda Secara sistematis angka indeks dituliskan sebagai berikut: 𝐼𝑛 =

𝑃𝑛 𝑃0

𝑥 100%

(3)

Ket: - In = indeks nilai - P0 = periode dasar - Pn = periode berjalan 6. KEBUTUHAN DATA Terdapat tiga data yang dibutuhkan dalam penelitian ini. Daftar Data yang dibutuhkan dan pengkodeannya dapat dilihat pada Tabel 3. Tabel 3. Data dan Pengkodean No. 1 2 3

Nama Kebutuhan Objek wisata Waktu tempuh ke objek wisata Lama waktu di objek wisata

Keterangan Pengkodean dalam satuan

n

dalam menit

x

dalam menit

y

Data objek wisata (n) diperoleh dari pengamatan langsung di Wilayah Malang Raya. Pada penelitian ini disediakan 20 tempat wisata yang akan dikodekan dan lama waktunya sebagaimana dalam Tabel 4.


Tabel 4. Kode Objek Wisata dan Waktu No Objek Wisata

7. HASIL DAN PEMBAHASAN

Pengkodean waktu (menit)

1

Air Terjun Coban Pelangi

a

45

2

Air Terjun Cuban Rondo

b

45

3

Air Terjun Sumber Pitu

c

45

4

Jawa Timur Park 1

d

120

5

Jawa Timur Park 2 (Secret Zoo ) & e Eco Green Park

120

6

Kaliwatu Rafting

f

180

7

Kusuma Agrowisata

g

60

8

Masjid Tiban Malang

h

45

9

Museum Angkut

i

120

10 Musuem Brawijaya

j

60

11 Pantai Balekambang

k

90

12 Pantai Banyu Anjok

l

90

13 Pantai Sendang Biru

m

90

14 Paralayang & Rumah Pohon

n

120

15 Pemandian Air Panas Cangar

o

120

16 Predator Fun Park Batu

p

120

17 Selecta

q

90

18 Sengkaling

r

90

19 Songgoriti

s

90

20 Kebun Teh Wonosari

t

120

894

Pada bab ini akan membahas kemampuan algoritme genetika mencari solusi optimal dalam optimasi knapsack problem penentuan objek wisata Wilayah Malang Raya. 7.1. Jumlah Populasi Jumlah populasi diuji dengan menggunakan jumlah generasi sebanyak 50, nilai pc 0,5 dan nilai pm sebesar 0,5. Jumlah populasi yang diuji yakni 10, 50, 100, 150, 200, 250, 300, 350, dan 400. Hasil yang dicatat dari pengujian jumlah populasi adalah nilai fitness dan waktu eksekusinya. Hasil pengujian jumlah populasi terhadap fitness disajikan pada Gambar 12 dan imbas waktu eksekusinya disajikan pada Gambar 13.

Gambar 12. Populasi Terhadap Fitness

Data waktu tempuh ke objek wisata (x) didapat dari data google maps. Tabel waktu tempuh ke objek wisata tersebut dapat dilihat pada Tabel 5. Tabel 5. Matrik Jarak a

b

d

e

f

g

h

i

j

p

q

r

90

94

89

97

47

94

60

134 139 127 112 125 87

99

77

101 110 72

114 38

40

35

35

101 35

69

173 193 181 26

51

43

50

31

111 78

83

86

79

87

41

83

53

129 132 121 102 117 80

91

69

91

103 83

83

0

5

10

6

74

3

35

141 163 151 24

44

16

18

17

15

81

43

86

5

0

11

8

73

4

35

140 161 149 25

45

14

19

16

16

81

44

10

0 122

0

c

14

114

0

d

90

38

e

94

40

k

l

m

n

o 69

s

t

T0

c

122 14

a b

f

89

35

79

11

0

12

75

9

39

141 163 151 24

37

21

11

20

15

75

47

g

97

35

87

6

8

12

0

75

4

39

143 163 151 22

45

18

18

20

13

84

48

h

47

101 41

74

73

75

75

0

84

51

91

102 122 79

96

69

92

113 55

i

94

35

83

3

4

9

4

84

0

35

138 158 146 21

41

17

15

16

12

81

45

j

60

69

53

35

35

39

39

51

35

0

110 132 120 54

72

30

46

19

44

68

7

k

134 173 129 141 140 141 143 91

138 110

0

96

85

144 42

170 190 151 163 138 163 182 124

l

139 193 132 163 161 163 163 96

158 132 144

0

m

127 181 121 151 149 151 151 85

146 120 42

106

n

112 26

102 24

25

24

22

102 21

54

170 200 184

53

34

27

32

16

98

o

125 69

117 44

45

37

45

122 41

72

190 219 203 53

0

53

28

50

48

114 83

p

87

51

80

16

14

21

18

79

17

30

151 176 160 34

53

0

28

12

25

78

37

q

99

43

91

18

19

11

18

96

15

46

163 193 178 27

28

28

0

27

21

91

57

r

77

50

69

17

16

20

20

69

16

19

138 165 150 32

50

12

27

0

25

71

26

s

101 31

91

15

16

15

13

92

12

44

163 191 176 16

48

25

21

25

0

91

57

t

110 111 103 81

81

75

84

113 81

68

182 208 194 98

114 78

91

71

91

0

53

T0

72

44

47

48

55

7

124 155 148 63

83

57

26

57

53

0

78

83

43

45

106 200 219 176 193 165 191 208 155 0

Gambar 13. Populasi Terhadap Waktu

Berdasarkan nilai fitness dan efisiensi waktu, populasi 100 memberikan alternatif solusi, sedangkan populasi 200 merupakan nilai terbaik. 7.2. Jumlah Generasi

184 203 160 178 150 176 194 148 0

37


63

Jumlah generasi diuji menggunakan parameter pc 0,5 dan pm 0,5. Nilai dari jumlah generasi yang diuji adalah 5, 25, 50, 75, dan 100. Performa jumlah generasi terhadap fitness menggunakan jumlah populasi 100 dan 200


menghasilkan data sebagaimana pada Ganbar 13.

895

kombinasi pc 0,7 dan pm 0,8 serta kombinasi pc 0,7 dan pm 0,9 Pengaruh kombinasi pc dan pm waktu eksekusi diperlihatkan pada Gambar 17.

Gambar 14. Generasi Terhadap Waktu

Performa jumlah generasi terhadap waktu eksekusi ditunjukkan pada Gambar 13.

Gambar 17. pc-pm Terhadap Waktu

Hasil pengujian pc dan pm memberikan hasil bahwa kombinasi pc dan pm terbaik adalah ketika nilai pc 0,7 dan nilai pm 0,8. 7.4. Data Uji

Gambar 15. Generasi Terhadap Waktu

Hasil pengujian jumlah generasi menunjukkan bahwa jumlah generasi sebanyak 50 dan populasi sebesar 100 sebagai solusi terbaik yang dilihat dari segi efisiensi.

Data yang berbeda dengan data latih, namun data uji tetap menggunakan semua objek wisata di data base aplikasi dan waktu maksimal yang dimliki wisatawan sebesar 600 menit. Lama waktu yang dihabiskan di objek wisata diganti dengan skema sedemikian rupa seperti yang ditunjukkan pada Gambar 18.

7.3. Nilai pc dan Nilai pm Pengujian pc dan pm menggunakan kombinasi bilangan sebagaimana berikut: 0,1, 0,2, 0,3, 0,4, 0,5, 0,5, 0,6, 0,7, 0,8, dan 0,9. Hasil pengujian nilai pc dan pm diperlihatkan pada Gambar 16. Gambar 18. Input Aplikasi

Dari data uji, didapat sebuah hasil keluaran aplikasi sebagai mana pada Gambar 19.

Gambar 16. pc-pm Terhadap Waktu

Gambar 16 menunjukkan bahwa terdapat nilai fitness tertinggi yakni 52,04081633 pada dua kombinasi nilai pc dan pm, yakni pada Fakultas Ilmu Komputer, Universitas Brawijaya

Gambar 19. Output Aplikasi

Susunan objek wisata terbaik menunjukkan objek wisata yang terpilih berada di sekitaran


Batu serta objek wisata yang satu rute dengan Batu ditinjau dari titik keberangkatan. Pola yang keluar menunjukkan bahwa objek wisata yang terpilih akan mengelompok pada suata lokasi yang berdekatan. Kondisi persebaran yang tidak merata atau terkelompok-kelompok membuat hasil optimasi aplikasi akan berkumpul pada salah satu gerombolan objek wisata tertentu dan memiliki kecenderungan menutup peluang objek wisata di luar wilayah menjadi fokus optimasi tersebut. 8. KESIMPULAN Algoritme genetika rata-rata mampu memberikan solusi terbaik saat nilai pc 0,7 dan pm 0,8. Jumlah populasi 100 dan jumlah generasi 50. Sedangkan susunan objek wisata yang dihasilkan memiliki kecenderungan untuk mengelompok saling berdekatan pada suatu wilayah tertentu. 9. DAFTAR PUSTAKA Ayuning, R., 2013. Implementasi Algoritma Genetika untuk Optimasi 0/1 Multidimensional Knapsack Problem dalam Penentuan Menu Makanan Sehat. Volume 1. Diah, K., Fadhli, M. & Sutanto, C., 2010. Penyelesaian Knapsack Problem Menggunakan Algoritma Genetika. Granmo, O.-C. & Oommen, B. J., 2010. Optimal sampling for estimation with constrained resources using a learning automaton-based solution for the nonlinear fractional knapsack problem. Hartoko, A., 2009. Faktor-Faktor Yang Mempengaruhi Pendapatan Daerah Dari Sektor Pariwisata Di Kota Madya Malang. Jayanti, I. N., 2015. Implementasi Algoritma Genetika Dalam Pelatihan Backpropagation Untuk Peramalan Beban Listrik Jangka Pendek. Kashima, T., Matsumoto, S. & Ishii, H., 2009. Evaluation of Menu Planning Capability Based on Multi-dimensional 0/1 Knapsack Problem of Nutritional Management System. Kosasi, S., 2013. Penyelesaian Bounded Knapsack Problem Menggunakan Dynamic Programing (Studi Kasus: Fakultas Ilmu Komputer, Universitas Brawijaya

896

CV. Mulia Abadi). Volume 8. Mahmudy, W. F., 2013. Algoritma Evolusi. Malang: PTIIK (Program Teknologi Informasi dan Ilmu Komputer) Universitas Brawijaya. Setiawan, B. D. & Pinandito, A., 2016. Optimasi Kunjungan Objek Wisata Dengan Menggunakan Algoritma Genetika.

Implementasi Algoritme Genetika Dalam Optimasi Knapsack Problem Penentuan Objek Wisata Wilayah Malang Raya

Recommend Documents