J~ICON, Vol. 1 No. 1, Maret 2013, pp. 33~44
33
PERBANDINGAN UNJUK KERJA METODE DECODER DENGAN METODE PENALTY DALAM MENYELESAIKAN KNAPSACK PROBLEM 0/1 MENGGUNAKAN ALGORITMA GENETIKA
Arini Aha Pekuwali 1, Adriana Fanggidae 2, Yulianto T. Polly 3 1,2,3
Jurusan Ilmu Komputer, Fakultas Sains dan Teknik, Universitas Nusa Cendana
ABSTRAK Knapsack problem 0/1 adalah optimasi kombinatorial yang bertujuan memilih objek-objek mana yang harus dimasukan ke dalam knapsack sedemikian hingga menghasilkan profit maksimum. Knapsack problem 0/1 dapat diselesaikan menggunakan algoritma genetika dengan pendekatan representasi biner yang dapat menghasilkan infeasible solution. Masalah infeasible solution dapat diselesaikan dengan dua metode, yaitu metode decoder dan metode penalty, pada penelitian ini dilakukan perbandingan untuk kedua metode tersebut. Siklus algoritma genetika yang digunakan dalam penelitian ini adalah siklus yang dicetuskan oleh Zbigniew Michalewis. Parameter perbandingan yang digunakan adalah rata-rata jumlah feasible solution dan standar deviasi dari nilai fitness kromosom terbaik, dengan menggunakan 8 data set yang diujikan terhadap kedua metode dengan variasi jumlah objek mulai dari 10 sampai 80 objek. Objek-objek yang diujikan dalam penelitian ini diasumsikan merupakan benda mati yang tidak mengalami penurunan kualitas, dimensi dari objek yang diujikan pada masalah knapsack 0/1 ini tidak diperhitungkan. Setiap data set diujikan sebanyak 5 kali, perbandingan yang didapatkan yaitu metode decoder berhasil mengeliminasi infeasible solution dari 5 kali pengujian untuk setiap data set, rata-rata metode decoder memberikan 5 feasible solution, sedangkan metode penalty belum berhasil mengeliminasi infeasible solution, dari 5 kali pengujian untuk setiap data set, rata-rata metode penalty memberikan 4 infeasible solution. Metode decoder juga unggul dalam tingkat kekonsistenan dalam memberikan solusi yang sama, dari 5 kali pengujian untuk setiap data set, metode decoder memiliki rata-rata standar deviasi sebesar 12,7875, sedangkan metode penalty memiliki rata-rata standar deviasi sebesar 100,85, sehingga metode decoder merupakan metode yang dianjurkan untuk digunakan dalam menyelesaikan knapsack problem 0/1. Kata Kunci : Masalah Knapsack 0/1, Algoritma Genetika, Representasi Biner, Infeasible Solution, Unjuk Kerja Metode Decoder dan Metode Penalty
ABSTRACT Knapsack problems 0/1 is a combinatorial optimization aimed at selecting objects which should be put into the knapsack in such a way that produces maximum profit. Knapsack problems 0/1 can be solved using a genetic algorithm with the binary representation approach that can generate infeasible solution. Problem infeasible solution can be solved by two methods, namely decoder and penalty methods, in this study were compared to both methods. Cycle of the genetic algorithm used in this research is a cycle triggered by Zbigniew Michalewis. The parameters of comparison used is the average number of feasible solutions and the standard deviation of the best chromosome fitness value, using 8 data sets were tested against both methods by varying the amount of objects ranging from 10 to 80. Objects were tested in this study is assumed to be an inanimate object that does not degrade the quality, the dimensions of the object being tested on knapsack problems 0/1 is not taken into account. Each data set was tested 5 times, the ratio obtained the decoder method successfully eliminates infeasible solution of the test 5 times for each data set, the average decoder method provides five feasible solution, while the penalty method has not been successful to eliminate
ISSN 2337-7631
34
ISSN 2337-7631
infeasible solutions, from 5 times the test for each data set, the average penalty method give 4 infeasible solution. Decoder method also excels in the level of consistency in providing the same solution, from 5 times of testing for each data set, the decoder method has an average standard deviation of 12.7875, while the penalty method has an average standard deviation of 100.85, so decoder method is the preferred method to use in solving knapsack problems 0/1. Keywords: knapsack problem 0/1, genetic algorithm, binary representation approach, infeasible solution, performance of decoder method and penalty method
I.
PENDAHULUAN
Knapsack problem adalah optimasi kombinatorial dimana memaksimalkan keuntungan dari objek–objek yang akan ditampung oleh knapsack tanpa melewati kapasitas knapsack. Knapsack problem 0/1 merupakan salah satu masalah knapsack yang dapat ditemui dalam kehidupan sehari-hari, misalnya sebuah knapsack akan diisi dengan beberapa objek yang dipilih diantara berbagai objek, dimana setiap objek memiliki berat dan profit. Tujuannya adalah memilih objek-objek mana yang harus dimasukan ke dalam knapsack sedemikian hingga menghasilkan profit maksimum. Dalam [1] knapsack problem 0/1 merupakan NP-Hard (Non Polynomial Hard), oleh karena itu knapsack problem 0/1 dapat diselesaikan menggunakan algoritma genetika dengan pendekatan representasi biner. Penyelesaian menggunakan representasi ini dapat menghasilkan infeasible solution (solusi yang total berat objek yang terpilih melebihi kapasitas knapsack). Masalah infeasible solution dapat diselesaikan dengan dua metode, yaitu metode decoder dan metode penalty [1]. Pada metode penalty, Gordon dan Whitley memberikan sebuah pinalti sederhana untuk setiap infeasible solution dan feasible solution yang di bawah kapasitas knapsack. Metode decoder lebih ke solusi umum dari setiap kromosom menggunakan greedy approximation heuristic. Pada penelitian ini peneliti tertarik untuk membandingkan unjuk kerja metode decoder dengan metode penalty, untuk mencapai tujuan tersebut peneliti akan menguji kedua metode menggunakan 8 data set berdasarkan parameter perbandingan mean (rata-rata) jumlah feasible solution dan standar deviasi dari fitness kromosom terbaik.
II. 2.1
MATERI DAN METODE
Knapsack Problem 0/1
Knapsack problem 0/1 merupakan salah satu masalah knapsack yang dapat ditemui dalam kehidupan sehari-hari, misalnya sebuah knapsack akan diisi dengan beberapa objek yang dipilih diantara berbagai objek, dimana setiap objek memiliki berat dan profit. Tujuannya adalah memilih objek-objek mana yang harus dimasukan ke dalam knapsack sedemikian hingga menghasilkan profit maksimum. Masalah knapsack dapat diformulasikan secara matematis seperti di bawah ini : max f (x) =
(1)
dengan batasan : g (x) =
~ICON, Vol. 1 No. 1, Maret 2013 : 33~44
≤W
(2)
J~ICON
ISSN 2337-7631
35
dimana : j
: indeks dari objek, j = 1, 2, 3, ….., n
n
: jumlah objek
pj
: nilai profit atau keuntungan dari setiap objek
wj
: berat dari setiap objek
W
: kapasitas knapsack
xj
:
Knapsack problem 0/1 dapat diselesaikan menggunakan algoritma genetika dengan pendekatan representasi biner. Barisan biner adalah representasi asli dari solusi knapsack problem 0/1, dimana 1 berarti terpilih dan 0 tidak terpilih dalam 1 dari n item knapsack. Contoh sebuah solusi untuk masalah 10 item dapat diperlihatkan seperti barisan di bawah ini : x = [x1 x2 … x10] [0 1 0 1 0 0 0 0 1 0] Ilustrasi di atas menyatakan bahwa item 2, 4 dan 9 terpilih untuk mengisi knapsack. Penyelesaian menggunakan representasi ini dapat menghasilkan infeasible solution. Dengan kata lain, pemilihan item dalam pengisian knapsack melebihi kapasitas dari knapsack. 2.2 Metode Penalty Metode penalty yang ditemukan oleh Gordon dan Whitley [1] akan memberikan sebuah pinalti sederhana untuk setiap infeasible solution. Untuk mencari nilai fitness : (3) dimana f(x) adalah fitness kromosom dan p(x) adalah pinalti untuk kromosom tersebut. Fungsi pinalti untuk masalah maksimasi dikonstruksikan seperti pada Gambar 1. p(x) 1
W - delta
W
feasible solution
W + delta infeasible solution
Gambar 1 Metode penalty disadur dari Gen dan Cheng (1996)
Nilai p(x) pada Gambar 2.1, yaitu sebagai berikut : (4)
Perbandingan Unjuk Kerja Metode Decoder Dengan Metode Penalty Dalam … (Arini Aha Pekuwali)
36
ISSN 2337-7631
dimana
(delta) adalah (5)
Dari Gambar 1 dapat dilihat bahwa fungsi pinalti dapat dinyatakan tidak hanya untuk infeasible solution, tapi juga untuk feasible solution yang di bawah kapasitas knapsack. 2.3
Metode Decoder
Metode decoder ditemukan oleh Gordon dan Whitley [1]. Metode ini lebih ke solusi umum dari setiap kromosom menggunakan greedy approximation. Prosedur decoding : a. b.
2.4
Langkah 1 Urutkan item-item (x) secara ascending order sebanyak jumlah item (j), lalu mengurutkan secara descending order terhadap rasio profit dibagi berat. Langkah 2 Pilih item menggunakan first fit heuristic sampai knapsack tidak dapat menampung lagi untuk item selanjutnya. Algoritma Genetika
Dalam [2] menyatakan bahwa algoritma genetika adalah teknik pencarian heuristik yang didasarkan pada gagasan evolusi seleksi alam dan genetik. Algoritma ini memanfaatkan proses seleksi alamiah yang dikenal dengan proses evolusi. Dalam proses evolusi, individu secara terus-menerus mengalami perubahan gen untuk menyesuaikan dengan lingkungan hidupnya. Hanya individuindividu yang kuat yang mampu bertahan.
Evaluasi Fitness
Populasi Awal
Reproduksi : Cross-Over dan Mutasi Seleksi Individu
Populasi Baru
Elitisme
Gambar 2 Siklus algoritma genetika oleh Zbigniew Michalewicz
Siklus Algoritma Genetika yang digunakan dalam penelitian ini, yaitu siklus yang dicetuskan oleh Zbigniew Michalewicz. Siklus dimulai dengan membuat populasi secara acak. Kemudian menghitung nilai fitness dari setiap individu. Proses berikutnya adalah proses cross-over menggunakan metode one-cut-point dan mutasi kode biner dengan mengganti nilai bit 0 menjadi bit 1, sebaliknya bit 1 diubah menjadi 0 terhadap gen yang memiliki nilai random kurang dari probabilitas mutasi. Setelah itu akan terjadi seleksi yang di dalamnya disertai dengan proses elitisme, yaitu menggandakan kromosom yang memiliki fitness tertinggi ke generasi baru. Selanjutnya populasi baru ini mengalami siklus yang sama dengan populasi sebelumnya. Proses ini berlangsung terus hingga maksimal generasi. Siklus algoritma genetika dapat digambarkan pada Gambar 2. 2.4.1
Teknik Encoding/Decoding
Menurut [2] Encoding (pengkodean) berguna untuk mengodekan atau menyandikan nilai gengen pembentuk kromosom. Decoding (pengkodean) berguna untuk mendekode gen-gen pembentuk individu agar nilainya tidak melebihi range yang telah ditentukan dan sekaligus menjadi nilai variabel
~ICON, Vol. 1 No. 1, Maret 2013 : 33~44
J~ICON
ISSN 2337-7631
37
yang akan dicari sebagai solusi permasalahan (Sutojo, 2010). Pada penyelesaian knapsack problem 0/1 menggunakan penyandian biner yang dimana nilai gen berupa biner 0 atau 1. Biner 0 menyatakan objek tersebut tidak terpilih, sedangkan biner 1 menyatakan objek tersebut terpilih. 2.4.2 Membangkitkan Populasi Proses pencarian solusi yang optimal dengan algoritma genetika tidak dimulai dari suatu nilai awal melainkan dari sekumpulan nilai awal yang disebut populasi. Populasi awal sebagai daerah awal pencarian solusi optimal dilakukan secara acak [3]. Pada knapsack problem 0/1, misalnya ada sekumpulan objek yang terdiri dari 5 buah objek, untuk inisialisasi awal populasi didapat hasil acakan sebagai berikut : 1
1
0
0
1
Gambar 3 Contoh Kromosom
Kromosom di atas menggambarkan bahwa objek 1, objek 2, dan objek 5 terpilih, sedangkan objek 3 dan objek 4 tidak terpilih. 2.4.3 Cross-over (Pindah Silang) One Cut Point Sebuah individu yang mengarah pada solusi optimal bisa diperoleh melalui proses pindah silang, dengan catatan bahwa pindah silang hanya bisa dilakukan jika sebuah bilangan acak r dalam interval [0 1] yang dibangkitkan nilainya lebih kecil dari probabilitas pc tertentu, dengan kata lain r < pc [2]. Cross-over dilakukan atas 2 kromosom untuk menghasilkan kromosom anak (offspring). Kromosom anak yang terbentuk akan mewarisi sebagian sifat kromosom induknya [4]. Teknik crossover yang dipakai adalah cross-over one cut point.
Gambar 4 Ilustrasi Cross-over one cut point
2.4.4 Mutasi Mutasi dilakukan untuk semua gen yang terdapat pada kromosom, jika bilangan acak yang dibangkitkan lebih kecil dari probabilitas mutasi pm yang ditentukan. Untuk kode biner, mutasi dilakukan dengan cara membalik nilai bit 0 menjadi bit 1, sebaliknya bit 1 diubah menjadi bit 0 [2]. 2.4.5 Elitisme Dalam [2], elitisme adalah prosedur untuk menggandakan individu yang mempunyai nilai fitness tertinggi sebanyak satu (bila individu dalam suatu populasi adalah ganjil) atau dua (bila jumlah individu dalam suatu populasi adalah genap). Hal ini dilakukan agar individu ini tidak mengalami kerusakan (nilai fitness menurun) selama proses pindah silang maupun mutasi. 2.4.6 Seleksi Proses pemilihan dua individu sebagai orang tua biasanya dilakukan secara proporsional berdasarkan nilai fitness. Metode roulette-wheel merupakan metode seleksi yang digunakan dalam penelitian ini. Sesuai dengan namanya, metode ini menirukan permainan roulette-wheel dimana masing-masing individu menempati potongan lingkaran pada roda roulette secara proporsional sesuai dengan nilai fitness [5].
Perbandingan Unjuk Kerja Metode Decoder Dengan Metode Penalty Dalam … (Arini Aha Pekuwali)
38
ISSN 2337-7631
2.4.7 Metode Statistika Menurut McClave dan Sincich dalam [6] ilmu statistika berhubungan dengan metode yang digunakan dalam pengumpulan, penyajian, analisis serta penyimpulan data. Data mentah dapat diolah dengan menggunakan metode statistika untuk menghasilkan informasi yang lebih jelas. Dengan menggunakan komputer, proses analisis dengan menggunakan metode statistika dapat dilakukan dengan lebih cepat dan teliti. Dalam penelitian ini digunakan metode statistika, yaitu menghitung ratarata (mean) jumlah feasible solution dan standar deviasi fitness terbaik. Metode statistika yang dipakai [7] : a. Rata-rata (mean) jumlah feasible solution (6)
x dimana : x : nilai rata-rata feasiblei : jumlah feasible solution untuk setiap data set n : jumlah data set b. Standar deviasi fitness terbaik
(7) dimana : s2 : variansi s : standar deviasi fiti : nilai fitness terbaik n : jumlah pengujian 2.4.8
Bagan Alir Program untuk Perulangan For-Do
[8] mengatakan bahwa struktur perulangan dengan intruksi FOR-DO akan mengulang eksekusi baris program selama syarat atau kondisi perulangan dipenuhi. Pada perulangan menggunakan intruksi FOR-DO, pengujian dilakukan sebelum perulangan dari satu blok intruksi dilaksanakan sehingga selama kondisi dipenuhi maka perulangan akan dilaksanakan, sedangkan jika kondisi sejak awal sudah tidak terpenuhi maka perulangan tidak akan dilakukan. Kondisi yang digunakan pada instruksi perulangan ini tidak dalam bentuk intruksi logika tapi dalam bentuk angka.
Gambar 5 Bagan Alir Perulangan FOR-DO
~ICON, Vol. 1 No. 1, Maret 2013 : 33~44
J~ICON
ISSN 2337-7631
39
2.5 Contoh Kasus Penggunaan Metode Decoder Dalam [9], hasil perhitungan rasio profit/berat adalah array T:
Setelah diurutkan secara descending order menjadi:
Misalnya kromosom
maka objek yang terpilih adalah:
1
2
3
4
5
6
7
8
9
10
X =
0
1
0
1
0
0
0
1
0
0
Tindex =
8
1
10
7
4
9
2
6
3
5
Bobot =
2
9
6
5
9
9
5
2
7
2
1
2
3
4
5
6
7
8
9
10
Bobot Total = 2 + 9 + 5 = 16 Kg
1
2
3
4
5
6
7
8
9
10
X =
0
1
0
1
0
0
0
1
0
0
Tindex =
8
1
10
7
4
9
2
6
3
5
Profit =
13
10
4
14
5
10
16
17
9
11
1
2
3
4
5
6
7
8
9
10
Profit Total = 13 + 10 + 16 = 39
X =
1
0
0
0
0
1
1
0
0
0
1
2
3
4
5
6
7
8
9
10
Artinya: Objek yang terpilih masuk knapsack adalah Objek 1, Objek 6 dan Objek 7
Jadi, fitness dari kromosom kromosom real adalah
adalah sama dengan profit yaitu 39 dengan .
Perbandingan Unjuk Kerja Metode Decoder Dengan Metode Penalty Dalam … (Arini Aha Pekuwali)
40
2.6
ISSN 2337-7631
Contoh Kasus Penggunaan Metode Penalty
Tersedia knapsack yang memiliki kapasitas 10 Kg dan 5 barang yang masing-masing memiliki berat dan profit. Barang 1 memiliki berat 8 Kg dan profit 7, Barang 2 memiliki berat 9 Kg dan profit 6, Barang 3 memiliki berat 3 Kg dan profit 8, Barang 4 memiliki berat 5 Kg dan profit 5, dan Barang 5 memiliki berat 2 Kg dan profit 6. Untuk kromosom v1 [0 0 1 1 0] : fitness (v1) = f (x) p(x) f (x) = ((0 x 7) + (0 x 6) + (1 x 8) + (1 x 5) + (0 x 6)) = 13 p (x) = = = = = = 0,8 fitness (v1) = 13 x 0,8 = 10,4 2.7
Cara Kerja Sistem Perbandingan Unjuk Kerja Metode Decoder dengan Metode Penalty
Dalam implementasi sistem perbandingan metode decoder dengan metode penalty, penerapan proses algoritma genetika untuk kedua metode dibuat dalam 1 prosedur saja, sehingga dilakukan pembedaan variabel untuk masing-masing metode. Hal ini dilakukan untuk menghemat waktu pengujian untuk kedua metode, sebab apabila proses algoritma genetika dilakukan pada prosedur yang berbeda maka proses pengujian akan memakan waktu 2 kali lebih lama dari penggunaan 1 prosedur. Berikut ini adalah flowchart cara kerja sistem dalam membandingkan unjuk kerja metode decoder dengan metode penalty untuk menyelesaikan knapsack problem 0/1 menggunakan algoritma genetika :
~ICON, Vol. 1 No. 1, Maret 2013 : 33~44
J~ICON
ISSN 2337-7631
41
Mulai Jumlah Kromosom, Maksimal Generasi, Berat Barang, Profit Barang, Jumlah Barang, Jumlah Data Set
Untuk i mulai dari 1 sampai Jumlah Data Set lakukan
Untuk j mulai dari 1 sampai 5 lakukan
Inisialisasi Kromosom Decoder = Kromosom Penalty
Mencari Tindex Rasio Profit/Berat
Generasi = Generasi + 1 CrossOver
Mutasi
Evaluasi Tidak
Elitisme
Seleksi
(Generasi = Maksimal Generasi) Or ((Selesai Decoder = true) dan (Selesai Penalty = true))
Ya
Kromosom Decoder terbaik [i,j], Kromosom Penalty terbaik [i,j], Generasi Decoder terbaik [i,j], Generasi Penalty terbaik [i,j], Fitness Decoder terbaik [i,j], Fitness Penalty terbaik [i,j], Total berat Decoder terbaik [i,j], Total Berat Penalty terbaik [i,j]
j selanjutnya
i selanjutnya
Selesai
Gambar 6. Flowchart Cara Kerja Sistem Perbandingan Unjuk Kerja Metode Decoder dengan Metode Penalty
Proses awal yang dilakukan dalam implementasi sistem perbandingan metode decoder dengan metode penalty adalah membuat 2 populasi awal yang berisi kromosom yang sama untuk penyelesaian menggunakan metode penalty dan metode decoder. Kromosom yang dibangkitkan berjumlah n buah sesuai dengan masukan dari pengguna. Setelah membangkitkan kromosom awal untuk metode penalty dan metode decoder, proses selanjutnya adalah melakukan crossover untuk setiap kromosom yang memiliki nilai acak kurang dari probabilitas crossover (pc) yang telah dimasukkan oleh pengguna.
Perbandingan Unjuk Kerja Metode Decoder Dengan Metode Penalty Dalam … (Arini Aha Pekuwali)
42
ISSN 2337-7631
Proses selanjutnya adalah proses mutasi untuk setiap gen yang memiliki nilai random kurang dari probabilitas mutasi (pm) yang telah dimasukkan oleh pengguna. Setelah mendapatkan kromosom baru hasil mutasi, maka dilakukanlah evaluasi fitness terhadap setiap kromosom. Pada bagian evaluasi inilah metode penalty dan metode decoder akan dipakai. Kromosom yang dibangkitkan untuk penyelesaian menggunakan metode penalty akan mengalami evaluasi fitness menggunakan metode penalty dan kromosom yang dibangkitkan untuk penyelesaian menggunakan metode decoder akan mengalami evaluasi fitness menggunakan metode decoder. Kromosom yang memiliki fitness terbaik akan langsung dimasukkan pada populasi baru melalui proses elitisme. Selanjutnya dilakukan proses seleksi terhadap setiap kromosom menggunakan metode roullete wheel, sehingga didapatkan kromosom-kromosom terbaik yang akan menempati populasi baru. Setelah mendapatkan populasi baru, maka akan dilakukan pengecekan kondisi berhenti yaitu kesamaan kromosom terbaik sebanyak 80% atau maksimal generasi. Apabila kondisi berhenti belum terpenuhi, maka proses crossover, mutasi, seleksi akan diulang. Apabila kondisi berhenti terpenuhi, maka kromosom terbaik, nilai fitness terbaik, generasi terbaik atau generasi dimana kondisi berhenti terpenuhi dan total berat dari kromosom solusi yang didapat, akan disimpan ke dalam array. Nilai yang didapatkan dari setiap pengujian akan dibandingkan menggunakan standar deviasi. Nilai standar deviasi yang mendekati 0 menunjukan kekonsistenan dari sebuah metode dalam memberikan solusi terbaik. III.
HASIL DAN PEMBAHASAN
Hasil perbandingan 8 data set disajikan dalam Tabel 1 yang terlihat bahwa metode decoder berhasil mengeliminasi infeasible solution, terbukti dari 5 kali pengujian untuk setiap data set, metode decoder tidak pernah memberikan solusi yang termasuk infeasible solution. Dari 5 feasible solution yang dihasilkan oleh metode decoder, rata-rata 2,625 ≈ 3 diantaranya merupakan optimal solution. Dari Tabel 5.25 juga terlihat bahwa metode penalty belum berhasil mengeliminasi infeasible solution, dari rata-rata pengujian terlihat bahwa dari 5 kali pengujian untuk setiap data set, metode penalty berpeluang memberikan 4 solusi yang termasuk infeasible solution. Metode penalty rata-rata hanya dapat memberikan 0,75 ≈ 1 optimal solution untuk 5 kali pengujian pada setiap data set. Tabel 1. Perbandingan Metode Decoder dengan Metode Penalty untuk 5 kali pengujian
Metode decoder juga unggul dalam tingkat kekonsistenan memberikan solusi yang sama. Dari 5 kali pengujian untuk setiap data set, metode decoder memiliki rata-rata standar deviasi sebesar 12,7875, sedangkan metode penalty memiliki rata-rata standar deviasi sebesar 100,85. Dari hasil penelitian ini, metode decoder merupakan metode yang dianjurkan untuk dipakai dalam menyelesaikan knapsack problem 0/1. Ditinjau dari mean generasi atau rata-rata generasi dapat dilihat bahwa metode penalty lebih cepat menemukan solusi dengan rata-rata generasi sebesar 142,3 ≈ 142
~ICON, Vol. 1 No. 1, Maret 2013 : 33~44
J~ICON
ISSN 2337-7631
43
generasi, dibandingkan dengan metode decoder yang memiliki rata-rata generasi sebesar 463,05 ≈ 463 generasi. Namun kecepatan menemukan solusi oleh metode penalty tidak diikuti dengan ketepatan dalam menemukan solusi yang berupa feasible solution, sehingga metode decoder tetap dipilih sebagai metode terbaik. IV. 4.1
KESIMPULAN DAN SARAN
KESIMPULAN
Berdasarkan hasil perbandingan unjuk kerja metode decoder dengan metode penalty dan pembahasan pada bab sebelumnya, maka dapat ditarik kesimpulan sebagai berikut : a. Pada penelitian ini metode decoder berhasil mengeliminasi infeasible solution, dari 5 kali pengujian untuk setiap data set, rata-rata metode decoder memberikan 5 feasible solution, sedangkan metode penalty belum berhasil mengeliminasi infeasible solution, dari 5 kali pengujian untuk setiap data set, rata-rata metode penalty memberikan 4 infeasible solution. b. Metode decoder merupakan metode yang dianjurkan untuk digunakan dalam menyelesaikan knapsack problem 0/1. 4.2
SARAN
Sistem perbandingan unjuk kerja metode decoder dengan metode penalty pada penelitian ini masih menggunakan operator-operator algoritma genetika standar. Operator algoritma genetika standar yang dimaksud seperti crossover menggunakan metode one-cut-point, mutasi menggunakan flip one bit, dan seleksi menggunakan metode roullete wheel, sehingga untuk pengembangan sistem ke depan untuk membandingkan metode decoder dengan metode penalty diharapkan dapat menggunakan metode-metode lain untuk operator algoritma genetika. Contohnya untuk seleksi menggunakan tournament selection, crossover menggunakan metode two-cut-point atau metode crossover lainnya, agar hasil analisa perbandingan dapat membantu pembaca lainnya dalam menentukan metode yang tepat untuk digunakan pada kasus yang relevan. Ada beberapa keterbatasan dalam penelitian ini seperti objek yang diujikan diasumsikan sebagai benda mati yang tidak mengalami penurunan kualitas dan dimensi dari objek yang diujikan pada masalah knapsack 0/1 tidak diperhitungkan. Hal ini disebabkan masalah knapsack 0/1 hanya memiliki satu batasan, yaitu total berat objek yang terpilih tidak melebihi kapasitas knapsack, oleh karena itu untuk penelitian selanjutnya diharapkan untuk menggunakan permasalahan knapsack yang batasannya lebih dari satu atau yang lebih dikenal dengan Multiconstraint Knapsack Problem. DAFTAR PUSTAKA .Gen, Mitsuo dan Runwei Cheng, 1996, Genetic Algorithms and Engineering Design, John Wiley & Sons, Inc, New York. [1]
Sutojo, Edy Mulyanto dan Vincent Suhartono, 2010, Kecerdasan Buatan. Penerbit Andi, Yogyakarta.
[2]
Berlianty, Intan dan Miftahol Arifin, 2010, Teknik-Teknik Optimasi Heuristik, Graha Ilmu, Yogyakarta.
[3]
Kusumadewi, Sri dan Hari Purnomo, 2005, Penyelesaian Masalah Optimasi dengan TeknikTeknik Heuristik, Graha Ilmu, Yogyakarta.
[4]
Suyanto, 2011, Artificial Intelligence, Informatika, Bandung.
[5]
Fanggidae, Adriana, 2008, Pengenalan Wajah dengan Self Organizing Maps (SOM) dan Principal Components Analysis (PCA). Tesis Universitas Gadjah Mada Yogyakarta.
Perbandingan Unjuk Kerja Metode Decoder Dengan Metode Penalty Dalam … (Arini Aha Pekuwali)
44
ISSN 2337-7631
[6]
Furqon, 2008, Statistika Terapan untuk Penelitian, Alfabeta, Bandung.
[8]
Sutedjo, Budi dan Michael AN, 2004, Algoritma dan Teknik Pemrograman, Penerbit Andi, Yogyakarta.
[9]
Sir, Yosua, 2012, Materi Mengajar Mata Kuliah Algoritma Genetika : Contoh Kasus Penyelesaian Masalah Knapsack 0-1dengan Algoritma Genetika, Ilmu Komputer Undana, Kupang.
~ICON, Vol. 1 No. 1, Maret 2013 : 33~44
