INTEGRAL, Vol. 10 No. 2, Juli 2005
ALTERNATIF MODEL PEMAMPATAN MATRIKS JARANG DENGAN MENGGUNAKAN ALGORITMA GENETIK Nico Saputro dan Ruth Beatrix Yordan Jurusan Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Katolik Parahyangan, Bandung 40141 - INDONESIA Email :
[email protected]
Intisari Makalah ini menyodorkan alternatif lain pemampatan matriks jarang dengan memakai algoritma genetik. Pada penelitian yang telah dilakukan oleh Aritonang [1], elemen nol pada kolom pertama dianggap sebagai elemen dummy dan turut disimpan pada hasil pemampatan. Pada makalah ini elemen dummy tersebut tidak digunakan sehingga diperoleh hasil pemampatan yang lebih kecil Kata kunci : Matriks Jarang, algoritma genetik, elemen dummy
Abstract This paper discusses an alternative of sparse matrix compression using genetic algorithm. In the last research, we assumed the zero elements at the first column as a dummy element and included in the compressed result.In this paper, we do not use the dummy element to make the compressed result smaller. Key words : sparse matrix, dummy element, genetic algorithm
Diterima : 17 Juni 2005 Disetujui untuk dipublikasikan : 25 Juli 2005
1. Pendahuluan
dekompresi. Adanya elemen dummy membuat pemampatan menjadi kurang optimal karena elemen nol yang seharusnya tidak perlu disimpan, terpaksa disimpan agar proses dekompresi dapat dilakukan. Makalah ini memberikan alternatif pemampatan matriks jarang dengan algoritma genetik tanpa menggunakan elemen dummy dan proses dekompresi tetap dapat dilakukan.
Pada penelitan sebelumnya [1] telah dapat dibuktikan bahwa matriks jarang dapat dimampatkan dengan menggunakan algoritma genetik. Pada penelitian tersebut, elemen nol pada kolom pertama dianggap sebagai bukan bernilai nol dan disebut sebagai elemen dummy. Elemen dummy tersebut selanjutnya disimpan pada hasil pemampatan. Tujuan penggunaan elemen dummy tersebut adalah untuk mempermudah proses
99
100 INTEGRAL, Vol. 10 No. 2, Juli 2005
2. Pemampatan Matriks Jarang Pemampatan matriks jarang adalah proses mengubah representasi dari matriks (array 2 dimensi) menjadi array 1 dimensi dengan menyimpan hanya elemen-elemen tidak nol. Misalkan diketahui suatu matriks jarang seperti pada Gambar 1. ⎡0 ⎢0 ⎢ ⎢8 ⎢ ⎢9 ⎢83 ⎢ ⎢7 ⎢0 ⎢ ⎢0 ⎢11 ⎢ ⎢⎣ 0
(a)
(b)
0 10 0 0 ⎤ 5 0 0 0 5 7 0 0 0 ⎥⎥ 9 0 0 0 0 0 0 0 0⎥ ⎥ 0 9 0 7 0 0 0 0 0⎥ 2 0 0 0 0 0 0 0 0⎥ ⎥ 0 0 21 0 24 0 0 0 0 ⎥ 0 0 0 17 0 0 0 0 0 ⎥ ⎥ 0 0 0 12 0 0 0 0 0 ⎥ 0 0 0 0 0 0 0 0 0⎥ ⎥ 0 0 0 0 0 0 0 8 0 ⎥⎦ 5 0
0
0
0
Gambar 2 : (a) kondisi awal array (b) kondisi setelah penempatan baris 4.
Saat dilakukan dekompresi, suatu elemen di array hasil dianggap sebagai elemen pertama dari suatu baris di matriks jarang ketika angka yang berada di kolom array posisi yang bersesuaian merupakan angka pertama yang ditemukan. Jadi saat dilakukan dekompresi, angka 9 di kolom pertama array hasil merupakan elemen pertama dari matriks jarang di baris ke-4 karena pada kolom yang bersesuaian (kolom 1) di array posisi berisi angka 4 (lihat Gambar 2). Muncul masalah ketika di suatu baris elemen pertamanya nol. Misalkan baris 2 dari matriks jarang di Gambar 1 disimpan seperti terlihat pada Gambar 3a.
Gambar 1 : Contoh matriks jarang 10 x 10
Gambar 1 memperlihatkan matriks jarang 10 x 10 dengan 19 buah elemen tidak nol. Untuk memampatkan matriks jarang tersebut ke dalam array 1 dimensi cukup disimpan 19 buah elemen tidak nol tersebut ke dalam array 1 dimensi sehingga diperoleh panjang array 1 dimensi adalah 19. Akan tetapi hasil kompresi tersebut tidak dapat digunakan untuk memperoleh kembali matriks jarang (tidak dapat di-dekompresi). Agar hasil kompresi dapat di-dekompresi, penelitian sebelumnya memakai 2 buah array 1 dimensi yang disebut array hasil dan array posisi. Array hasil dipakai untuk menyimpan elemen-elemen baris dari matriks jarang. Array posisi dipakai untuk mencatat nomor baris matriks jarang asal dari elemen tidak nol yang disimpan di array hasil [1]. Gambar 2 menunjukkan contoh dari isi array hasil dan array posisi ketika baris ke-4 dari matriks jarang di Gambar 1 yang pertama ditempatkan di array hasil.
(a)
(b) Gambar 3 : (a) elemen pertama nol (b) elemen pertama nol sebagai dummy
Saat dilakukan dekompresi, angka 5 di kolom kedua array hasil akan dianggap sebagai elemen pertama dari matriks jarang di baris 2. Oleh karena itu, elemen nol di kolom pertama dianggap sebagai elemen dummy. Gambar 3b. Memperlihatkan isi array hasil dan array posisi ketika dipakai elemen dummy.
100
INTEGRAL, Vol. 10 No. 2, Juli 2005
Gambar 4 memperlihatkan isi array hasil dan array posisi saat menyimpan baris ke2 dari matriks jarang di Gambar 1. Tanda | digunakan untuk memisahkan antara nomor baris dan nomor kolom. Isi array posisi kolom pertama adalah 2|2, yang berarti baris ke 2 kolom ke 2. Gambar 5 menunjukkan perbandingan isi array hasil dan array posisi untuk pemampatan dengan elemen dummy dan tanpa elemen dummy. Matriks jarang yang akan dimampatkan seperti pada Gambar 1 dan urutan baris yang ditempatkan di array hasil secara berturutan adalah baris ke 5, 2, 3, 1, 4, 7, 9, 8, 6, dan terakhir baris ke-10. Pada kasus ini, panjang array hasil pemampatan dengan menggunakan elemen dummy adalah 26, sedangkan panjang array hasil pemampatan tanpa elemen dummy adalah 21.
Alternatif model pemampatan yang dibahas pada makalah ini tetap memakai 2 buah array 1 dimensi yaitu array hasil dan array posisi. Array hasil tetap dipakai untuk menyimpan elemen-elemen baris tidak nol dari matriks jarang, sedangkan array posisi selain menyimpan nomor baris juga nomor kolom. Nomor kolom akan disimpan di array posisi ketika baris tersebut elemen pertamanya nol dan nomor kolom tersebut menunjukkan posisi pertama elemen tidak nol di baris tersebut.
Gambar 4 : Pemampatan tanpa elemen dummy
10
4
3
0
0
0
6
7
0
0 21
0 12
0
0
0
0
0
0
0
0
0
0
0 24 6
0
0
0 17
0
0
0
0
7
0
0
0
0
0
0
0 0 8 10
7 6
0
0
0
0
0 10
0
0
0
0
0
0
0
0
0
0 7
9 10 4 1
2
0
5
0
0
0
5
7
0
2
0
0
0
0
0
0
0
0
83 5
2 5
0 2
5 2
8 3
9 3
5 1
5 2
7 2
9 4
0
(a)
101
0
0 0
0
5
0 0
0
0
0
6 0
0
9
0
0 0
0
0
9
0
0 24
0
0
1
0
8
7
8
0
9 11
9
5 83
array hasil array posisi
0
7 17 11 4 7 9
0
0 12 21 8 6
6 10
0
102 INTEGRAL, Vol. 10 No. 2, Juli 2005
10
0
0
8
7
3
array hasil array posisi
0
0
0
0
0
0
0
0
0
0
6
0
6
7
0
0 21
0 24
0 12
0
0
0
0
0
0
0
0
0
0
0
0
0
9 11
0
0
0 17
0
0
0
0
0
4
9
9
0
7
0
0
0
0
1
0
5
0
0
0
0
0 10
0
8
9
0
0
0
0
0
0
0
0
2
0
5
0
0
0
5
7
0
0
5 83
2
0
0
0
0
0
0
0
0
2 5 5 2|2
8 3
9 5 3 1|2
5 2
7 2
9 17 4 7|5
83 5
0
0
9 10 4 1
7 11 12 4 9 8|5
7 6 6 10|9
21 6
0
0
0
0
0
0
0
24 6
(b) Gambar 5 : Perbandingan pemampatan dengan elemen dummy dan tanpa elemen dummy (a) dengan elemen dummy (b) tanpa Elemen dummy
3. Pemodelan ke Dalam Algoritma Genetik
Lokus Allele
Gambar 5b menunjukkan salah satu contoh penempatan baris-baris matriks jarang ke dalam array hasil. Urutan penempatan yang berbeda dapat menghasilkan panjang array hasil yang berbeda pula. Algoritma genetik dipergunakan untuk mencari urutan penempatan yang terbaik sehingga dihasilkan panjang array hasil yang seminimal mungkin.
1 5
2 2
3 3
4 1
5 4
6 7
7 9
8 8
9 6
10 10
Gambar 6 : Contoh representasi kromosom dari Gambar 5.
3.2 Fungsi Fitness Untuk mengukur fungsi objektif dari tiap kromosom dalam populasi digunakan fungsi fitness. Fungsi fitness dihitung dengan rumus :
banyaknya elemen tidak nol panjang array 1 dimensi
3.1 Representasi Kromosom Representasi ke bentuk kromosom untuk pemampatan tanpa elemen dummy tidak ada bedanya dengan pemampatan dengan elemen dummy. Posisi gen dalam kromosom atau disebut juga locus mewakili urutan penempatan baris. Locus paling kiri mewakili urutan penempatan baris yang pertama dan locus paling kanan mewakili urutan penempatan baris yang terakhir. Nilai gen atau disebut juga allele merepresentasikan nomor baris. Sebagai contoh, urutan penempatan pada Gambar 5, dapat dinyatakan dalam bentuk kromosom seperti pada Gambar 6.
(1)
Nilai fitness terletak antara 0 dan 1, kromosom yang semakin baik, memiliki nilai fitness yang semakin besar. Kromosom terbaik memiliki nilai fitness = 1 [1] atau dengan kata lain panjang array hasil sama dengan banyaknya elemen tidak nol. 3.3 Operator Genetik Sebagian besar operator genetik yang dipakai sama seperti penelitian sebelumnya, yang berbeda hanya metode reproduksi dan crossover yang dipergunakan.
102
INTEGRAL, Vol. 10 No. 2, Juli 2005
posisi tersebut dihapus. Sebuah posisi gen baru dipilih lagi secara acak kemudian gen yang dihapus tersebut disisipkan di posisi tersebut. Gambar 8 memperlihatkan proses mutasi dimana gen di posisi ke-5 dihapus kemudian disisipkan diposisi ke-7.
Metode reproduksi yang digunakan adalah gabungan metode elitism dan rank selection. Elitism dipakai untuk menjaga agar kromosom terbaik dari suatu generasi akan tetap bertahan di generasi selanjutnya. Rank Selection dipakai untuk memilih kromosom yang akan diproses lebih lanjut oleh operator pindah silang dan mutasi. Metode pindah silang yang digunakan adalah Precedence Preservative Crossover (PPX). Pada PPX, kromosom baru disusun secara acak dari allele kromosom-kromosom induk. Angka acak 1 atau 2 dipakai untuk memilih induk kromosom. Jika didapat angka 1 maka diturunkan allele paling kiri dari induk kromosom pertama, jika didapat angka 2 maka diturunkan allele paling kiri dari induk kromosom kedua. Selanjutnya allele yang terpilih tadi dihapus dari kedua induk kromosom. Proses dilakukan sampai gen-gen di kedua induk habis [2]. Sebagai contoh, Gambar 7a memperlihatkan 2 induk kromosom yang akan di crossover dan misalkan telah diperoleh 10 buah angka secara acak {1,2,2,1,2,2,1,2,1,2}. Hasil pindah silang memakai metode PPX dapat dilihat pada Gambar 7b. Induk A Induk B
9 8
8 7
4 1
5 2
6 3
7 10
1 9
3 5
2 4
10 6
1
2
5
3
6
10
Anak C
Hasil Anak C
9
8
7
4
8
7
4
1
9
8
7
2
5 4
2
5
3
6
10
3
6
10
7 5
1
Gambar 8 : Contoh Mutasi
3.4 Parameter Genetik Parameter Genetik berguna dalam pengendalian operator-operator genetik. Parameter yang digunakan adalah ukuran populasi, jumlah generasi, probabilitas Crossover (Pc), dan probabilitas Mutasi (Pm). Tidak ada aturan pasti tentang berapa nilai setiap parameter ini [3].
4. Hasil Eksperimen Ada 2 eksperimen yang dilakukan. Eksperimen pertama untuk melihat apakah pemampatan matriks jarang tanpa elemen dummy dapat menghasilkan panjang array hasil sama dengan banyaknya elemen tidak nol. Jadi dapat diperoleh kromosom dengan nilai fitness = 1. Eksperimen kedua untuk membandingkan hasil pemampatan keseluruhan (ukuran array hasil dan ukuran array posisi) hasil pemampatan memakai algoritma genetik tanpa elemen dummy dan dengan elemen dummy.
(a) Anak C
9
Posisi Gen
(b) Gambar 7 : (a) kromosom induk A & induk B, dan (b) kromosom hasil mutasi
4.1 Eksperimen I Pada eksperimen ini digunakan matriks jarang berukuran 1000 x 1000, dengan banyaknya elemen tidak nol yang bervariasi antara 0.05% s/d 0.75% dari ukuran matriks jarang. Elemen-elemen tidak nol tersebut disebarkan secara acak pada matriks jarang. Untuk banyaknya elemen tidak nol tertentu, dilakukan percobaan sebanyak 20 kali kemudian dihitung berapa kali percobaan yang
Terlihat pada kromosom anak, gen pertama diturunkan dari induk A, gen kedua dan ketiga diturunkan dari induk B, gen keempat dari induk A, dst. Metode mutasi yang digunakan adalah remove and insert [1]. Pada metode ini pemindahan dan penyisipan gen dilakukan secara acak. Sebuah posisi gen dipilih secara acak kemudian gen di
103
104 INTEGRAL, Vol. 10 No. 2, Juli 2005
100, Probabilitas crossover (Pc) = 0.8, Probabilitas mutasi (Pm) = 0.01. Selain itu, ditetapkan juga bahwa banyaknya elitism = 1. Tabel 1 merangkum hasil eksperimen I.
dapat menghasilkan nilai fitness 1 dan rata-rata generasi untuk mendapatkan nilai fitness 1 tersebut. Parameter genetik yang dipakai pada eksperimen ditetapkan sebagai berikut : ukuran populasi 10, jumlah generasi =
Banyak elemen tidak nol
500 750 1000 1500 2500 3000 5000 7500
diperoleh kromosom bernilai fitness = 1 Jumlah Banyaknya generasi Min Maks Rata- percobaan Rata
1 2 37 47 78 67 87 na
19 45 55 68 78 67 87 na
4.53 17.71 45.67 57.5 78 67 87 na
15 6 3 2 1 1 1 0
nilai fitness (dari 20 percobaan) Min
Maks
RataRata
0.747
1.000
0.976
0.555
1.000
0.934
0.606
1.000
0.836
0.627
1.000
0.789
0.659
1.000
0.805
0.507
1.000
0.808
0.545
1.000
0.819
0.498
0.945
0.748
Tabel 1 : Hasil eksperimen I
dengan nilai fitness=1. Gambar 9 grafik rata-rata fitness untuk beragam variasi banyaknya elemen tidak nol juga menunjukkan hal tersebut. Semakin banyak elemen tidak nol, semakin kecil rata-rata nilai fitness terbaik yang diperoleh. Dengan kata lain, semakin banyak elemen tidak nol, semakin panjang array hasilnya.
Rata-rata fitness
1
0.8
0.6
0.4 500
750
1000
1500
2500
3000
5000
7500
Banyaknya elemen tidak nol
Gambar 9 : Grafik rata-rata fitness (dari 20 percobaan).
4.2 Hasil Eksperimen II Kegunaan pemampatan tabel jarang adalah untuk memperkecil ukuran file tempat menyimpan matriks jarang. Pada eksperimen ini dibandingkan hasil pemampatan dari algoritma genetik dengan elemen dummy dan tanpa elemen dummy. Pada kedua metode pemampatan (dummy dan tanpa dummy) ini, file hasil pemampatan tersebut menyimpan informasi berupa ukuran matriks jarang, array hasil, dan array posisi.
Terlihat pada tabel 1, pada jumlah elemen tidak nol = 500, dari 20 kali percobaan, 15 kali percobaan berhasil memperoleh nilai fitness 1 (75% keberhasilan). Akan tetapi seiring dengan semakin banyaknya elemen tidak nol, tingkat keberhasilan mendapatkan kromosom bernilai fitness = 1 semakin kecil. Bahkan pada saat banyaknya elemen tidak nol = 7500 (0.75% dari ukuran matriks jarang), tidak berhasil ditemukan kromosom
104
INTEGRAL, Vol. 10 No. 2, Juli 2005
percobaan dilakukan sebanyak 10 kali. Tabel 2 memperlihatkan perbandingan ukuran file penyimpanan matriks jarang tanpa pemampatan, pemampatan dengan elemen dummy dan tanpa menggunakan elemen dummy.
Parameter genetik yang digunakan pada eksperimen II ditetapkan sebagai berikut : ukuran populasi = 100, jumlah generasi = 100, probabilitas crossover = 0.8, dan probabilitas mutasi = 0.01. Sedangkan jumlah elitism yang dipakai adalah 5. Untuk setiap ukuran matriks jarang dan banyaknya elemen tidak nol tertentu, Ukuran Matriks Jarang
10 x 10
500 x 500
1000 x 1000
Ukuran File hasil kompresi
Banyak Elemen tidak nol
Ukuran file asli
1
333 byte
89 byte
19
251 byte
2500
Dengan dummy
Max
Avg
89 byte
89 byte
24 byte
24 byte
24 byte
10
10
10.0
1
1
1.0
158 byte
158 byte
158 byte
125 byte
131 byte
125.6 byte
25
25
25.0
19
20
19.1
491 Kb
29.1 Kb
29.6 Kb
29.3 Kb
28.5 Kb
28.8 Kb
28.71 Kb
5172
5294
5227.5
4203
4285
4241.8
10000
499 Kb
165.8 166 Kb 155.98 146 Kb 146.5 146.18 Kb Kb Kb Kb
29924
29999 29945.1
28444
29947
28281.8
10000
1.91 Mb 127 Kb 128 Kb 127.1 103 Kb 103 Kb 103 Kb Kb
24378
24576 24466.0
18984
18998
18990.9
62113
62311 62201.0
58572
58586
58578.9
367 Kb 368 Kb 367.1 303 Kb 303 Kb 303 Kb Kb
Min
Max
tanpa dummy
Min
1.974 Mb
Max
Dengan dummy
Avg
20000
Min
Panjang Array Hasil
Tanpa dummy
Avg
Min
Max
Avg
Tabel 2 : Perbandingan ukuran file hasil pemampatan
kecil dibandingkan menggunakan elemen dummy.
Dari tabel 2 dapat dilihat bahwa pemampatan matriks jarang tanpa elemen dummy dapat menghasilkan pemampatan yang lebih baik daripada menggunakan elemen dummy. Hal ini dapat dilihat baik dari ukuran file hasil kompresi maupun panjang array hasil.
dengan
6. Daftar Pustaka [1] Aritonang, J., Saputro, N., “Mengukur Kinerja Algoritma Genetik Pada Pemampatan Matriks Jarang”, Integral, Vol. 10, No. 1, 46-52, 2005. [2] Saputro, N., Yento, “Pemakaian Algoritma Genetik untuk Penjadwalan Job Shop Dinamis Non Deterministik”, Jurnal Teknik Industri, Vol 6, No. 1, 61-70, 2004 [3] Koza, J., “Genetic Algorithm”, http://cs.felk.cvut.cz/~xobitko/ga, Oktober 2004.
5. Kesimpulan Hasil eksperimen menunjukkan bahwa alternatif model pemampatan matriks jarang dengan algoritma genetik tanpa elemen dummy dapat menghasilkan panjang array hasil pemampatan sama dengan banyaknya elemen tidak nol. Ukuran file hasil pemampatan dengan metode tanpa elemen dummy juga lebih
105
