EVALUASI KINERJA GENETIC ALGORITHM (GA) DENGAN STRATEGI PENALTI STUDI KASUS MULTI-CHOICE MULTIDIMENSIONAL KNAPSACK PROBLEM (MMKP) (Skripsi)
OLEH Dian Anggraini
JURUSAN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS LAMPUNG 2016
ABSTRACT
EVALUATION OF GENETIC ALGORITHM (GA) PERFORMANCE USING PENALTY STRATEGY CASE STUDY MULTI-CHOICE MULTIDIMENSIONAL KNAPSACK PROBLEM (MMKP)
By Dian Anggraini
Optimization problem frequently encountered in daily activity. Knapsack problem (KP) is one of the examples. KP have varian, KP used in this research was MultiChoice Multi-Dimensional Knapsack Problem (mmKP). mmKP problem has constraints function that will divide feasible and not feasible solution. Handle constraints strategy is needed to resolve this problem. Strategy will be used is penalty strategy. This research used Genetic Algorithm (pGA) and pGA with addition Local Search (phGA) to resolve mmKP. The result of this research shows that phGA has better solution value than pGA, but pGA need less running time than phGA. Key word: Genetic Algorithm (GA), Knapsack Problem, Multi-Choice MultiDimensional Knapsack Problem, Local Search, Penalty Strategy
ABSTRAK
EVALUASI KINERJA GENETIC ALGORITHM (GA) DENGAN STRATEGI PENALTI STUDI KASUS MULTI-CHOICE MULTI-DIMENSIONAL KNAPSACK PROBLEM (MMKP)
Oleh Dian Anggrani
Persoalan optimasi sering ditemui dalam kehidupan sehari-hari. Salah satu contohnya adalah persoalan knapsack. Persoalan Knapsack memiliki beberapa jenis, pada penelitian ini akan digunakan Multi-Choice Multi-Dimensional Knapsack Problem (mmKP). Persoalan mmKP memiliki fungsi kendala yang akan membagi ruang solusi layak dan tidak layak. Untuk mengatasi ini dibutuhkan strategi penanganan kendala. Strategi yang akan digunakan adalah strategi penalti. Pada penelitian ini digunakan Genetic Algorithm (pGA) dan pGA dengan tambahan Local Search (phGA) untuk menyelesaikan mmKP. Hasil dari penelitian ini menunjukkan phGA memiliki hasil yang lebih baik dibandingkan pGA, namun pGA membutuhkan running time yang lebih sedikit dibandingkan phGA. Kata kunci: Genetic Algorithm (GA), Knapsack Problem, Multi-Choice MultiDimensional Knapsack Problem, Local Search, Penalty Strategy
EVALUASI KINERJA GENETIC ALGORITHM (GA) DENGAN STRATEGI PENALTI STUDI KASUS MULTI-CHOICE MULTIDIMENSIONAL KNAPSACK PROBLEM (MMKP)
OLEH Dian Anggraini Skripsi Sebagai Salah Satu Syarat untuk Memperoleh Gelar SARJANA KOMPUTER Pada Jurusan Ilmu Komputer Fakultas Matematika dan Ilmu Pengetahuan Alam
JURUSAN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS LAMPUNG 2016
RIWAYAT HIDUP
Penulis dilahirkan pada tanggal 9 Mei 1994 di Ogan Lima. Penulis merupakan anak ketiga dari tiga bersaudara dari Bapak
Helmi
Padil
dan
Ibu
Widaningsih.
Penulis
menyelesaikan pendidikan formal pertama kali di SDN 1 Abung Tengah pada tahun 2006. Pendidikan menengah pertama ditempuh di Sekolah Menengah Pertama (SMP) Negeri 1 Abung Barat pada tahun 2009 dan melanjutkan ke Sekolah Menengah Kejuruan (SMK) Negeri 1 Abung Selatan pada tahun 2009 -2012. Pada tahun 2012, penulis terdaftar sebagai mahasiswa Universitas Lampung, Fakultas Matematika dan Ilmu Pengetahuan Alam, Jurusan Ilmu Komputer. Pada bulan Januari dan Februari, penulis melaksanakan Kerja Praktik di Lembaga Penelitian Universitas Lampung (Lemlit Unila) Selama perkuliahan, penulis mengikuti organisasi, yaitu Himpunan Mahasiswa Ilmu Komputer (Himakom). Di Himakom, penulis menjadi anggota bidang Keilmuan pada kepengurusan periode 2012-2013.
Tidak semua yang penting bisa dihitung, dan tidak semua yang dapat dihitung diperhitungkan --- Albert Einstein
Boleh jadi kamu membenci sesuatu, padahal ia amat baik bagimu , dan boleh jadi (pula) kamu menyukai seuatu , padahal ia amat buruk bagimu ; Allah mengetahui , sedang kamu tidak mengetahui” (QS Al-Baqarah / 2:216)
Kupersembahkan karya sederhana ini untuk superhero dalam hidup ku papa dan mama Ayuk Vivin, Kanjeng, Ayuk Evi, Adam, bulek, dan mbah ku terimakasih sudah mengisi hidupku dengan tawa dan semangat yang tak pernah putus
SANWACANA
Segala puji dan syukur penulis panjatkan ke hadirat Allah SWT, yang Maha Pengasih lagi Maha Penyayang. Selama studi sampai dengan penulisan skripsi ini, penulis banyak menerima bantuan baik secara langsung maupun tidak langsung. Oleh karena itu, penulis menyampaikan rasa terimakasih yang sebesar-besarnya kepada: 1. Bapak Dr. Eng. Admi Syarif, selaku Pembimbing I atas segala saran, bimbingan, kepercayaan serta berbagi pengalamannya untuk kerja-keras dalam hidup ini dan juga motivasi untuk belajar dan terus belajar. 2. Bapak Aristoteles, S.Si, M.Si Selaku Pembimbing II atas segala waktu yang telah diberikan untuk diskusi, bimbingan serta pengarahannya selama ini. 3. Bapak Rico Andrian, S.Si, M.Kom., selaku pembahas yang telah memberikan kritik dan saran dalam skripsi ini, serta pengarahan dan bimbingan selama ini. 4. Bapak Dwi Sakethi, S.Si, M.Kom., selaku Pembimbing Akademik atas saran dan motivasi yang diberikan serta bimbingan selama perkuliahan. 5. Bapak Dr. Ir. Kurnia Muludi, selaku Ketua Jurusan Ilmu Komputer Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lampung. 6. Bapak Didik Kurniawan, S.Si., MT, selaku Sekretaris Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lampung. 7. Seluruh staff dan dosen jurusan ilmu komputer: Dwi Sakethi, M.Kom. Rangga Firdaus, S.Kom., M.Kom., Ossy Dwi Endah Wulansari, M.T., Febi Eka Febriansyah, ST., Anie Rose Irawati, ST, M.Cs., Didik Kurniawan, S.Si., MT, Rico Andrian, S.Si.,M.Kom, Tristiyanto, S.Kom., M.I.S., Aristoteles, S.Si., M.Si., Astria Hijriani, S.Kom., M.Kom, Favorisen Rossy King, S.Kom., M.Si., Dr. Ir. Kurnia Muludi, M.Sc. 8. Rani
Cahyani
pengerjaan skripsi
yang
selalu
sabar
menemani,
mendampingi
selama
9. Cindona, Erika, Erlina, Nurul, Nila, Taqiya, Erlina, Riska, Nafi, Qonitati, Eko, Anita dan Indah atas Dukungan, Motivasi, dan Doa yang telah diberikan. 10. Semua rekan-rekan Ilmu Komputer 2012 atas Pengalaman, Motivasi, Ilmu dan Dukungan yang telah diberikan 11. Bebe, Mas Abi, Mami, Teteh, Cungkring, dan Sugab terimakasih atas waktu yang telah diberikan selama ini. 12. dan beberapa orang tercinta yang belum disebutkan Demikian ucapan terimakasih penulis sampaikan kepada semua pihak, hanya Allah SWT yang dapat membalas dan memberi rahmat-Nya atas segala usaha dan bantuan yang telah diberikan kepada penulis.
Bandar Lampung, Desember 2016
Dian Anggraini
DAFTAR ISI
Halaman ABSTRAK ABSTRACT Daftar Isi…………..……………………………………………………………..
i
Daftar Gambar……………………………………………………………………
iv
Daftar Tabel………………………………………………………………………
vii
BAB I 1.1 Latar Belakang……………………………………………………………
1
1.2 Rumusan Masalah………………………………………………………..
5
1.3 Batasan Masalah………………………………………………………….
5
1.4 Tujuan…………………………………………………………………….
5
1.5 Manfaat…………………………………………………………………..
5
BAB II 2.1 Knapsack Problem………………………………………………………
6
2.1.1 0.1 Knapsack Problem…………………………………………….
7
2.1.2 Bounded Knapsack Problem………………………………………
8
2.1.3 Multiple-choice Knapsack Problem………………………………
9
2.1.4 Multi-dimensional Knapsack Problem……………………………
10
i
2.1.5 Multi Choice Multi-dimensional Knapsack Problem………..……
11
2.2 Algoritma Genetika………………………………………………….…..
14
2.2.1 Inisiasi Populasi……………………………………………………
16
2.2.2 Evaluasi Populasi………………………………………………….
19
2.2.3 Seleksi Populasi……………………………………………………
20
2.2.4 Proses Penyilangan………………………………………………..
21
2.2.5 Mutasi…………..………………………………………………….
27
2.2.6 Strategy Penalty...………………………………………………….
29
2.3 Local Search……..………………………………………………………
31
BAB III 3.1 Waktu dan Tempat Penelitian………...…………………………………
33
3.2 Lingkungan Pengembangan..……………………………………………
33
3.3 Tahapan Penelitian………………………………………………………
33
3.3.1 Studi Literatur dari Test Problem…………………………………
35
3.3.2 Penyusunan Algoritma………….…………………………………
36
3.3.3Pengembangan Program……………………………………………
43
3.3.4 Pengujian………………………..…………………………………
48
4.1 Hasil dan Pembahasan…..………………………………………………
50
BAB IV
BAB V ii
5.1 Kesimpulan……………..………………………………………………
60
5.2 Saran……..……………..………………………………………………
60
DAFTAR PUSTAKA LAMPIRAN
iii
DAFTAR GAMBAR
Halaman Gambar 1.1 Ilustrasi Persoalan Knapsack…………………………………. 2 Gambar 2.1 Knapsack Problem……………………………………………. 6 Gambar 2.2 Ilustrasi mmKP………………………….……………………. 13 Gambar 2.3 Kerangka Kerja Implementasi GA..…….……………………. 16 Gambar 2.4 Contoh Kromosom Metode Representasi Nilai……………… 17 Gambar 2.5 Contoh Kromosom Metode Representasi Biner……………... 17 Gambar 2.6 Contoh Kromosom Metode Representasi Permutasi………… 17 Gambar 2.7 Contoh Edge Encoding……………………….……………… 18 Gambar 2.8 Contoh Representasi Bilangan Prüfer………..………………. 18 Gambar 2.9 Contoh Representasi Matrik………………………………….. 19 Gambar 2.10 Contoh Selection Probability dan Fitness Value…………… 21 Gambar 2.11 Contoh Metode One Point Crossover……………..……….. 21 Gambar 2.12 Contoh Metode Two Point Crossover…………….……….. 22 Gambar 2.13 Ilustrasi PMX………………………..…………….……….. 22 Gambar 2.14 Ilustrasi PMX………………………..…………….……….. 22 Gambar 2.15 Ilustrasi PMX…………………..…………….…………….. 22 Gambar 2.16 Ilustrasi PMX………………..…………….……………….. 23 Gambar 2.17 Ilustrasi OX...………………..…………….……………….. 23 Gambar 2.18 Ilustrasi OX...………………..…………….……………….. 23 iv
Gambar 2.19 Ilustrasi OX...………………..…………….……………….. 23 Gambar 2.20 Ilustrasi OX...………………..…………….……………….. 23 Gambar 2.21 Ilustrasi OX...………………..…………….……………….. 24 Gambar 2.22 Ilustrasi PX...………………..…………….……………….. 24 Gambar 2.23 Ilustrasi PX...………………..…………….……………….. 24 Gambar 2.24 Ilustrasi PX...………………..…………….……………….. 24 Gambar 2.25 Ilustrasi PX...………………..…………….……………….. 24 Gambar 2.26 Ilustrasi OBX...………………..…………….…….……….. 25 Gambar 2.27 Ilustrasi CX...………………..…………….……….………. 25 Gambar 2.28 Ilustrasi CX...………………..…………….……….………. 25 Gambar 2.29 Ilustrasi CX...………………..…………….……….………. 26 Gambar 2.30 Ilustrasi WMX...………………..…………….…….………. 26 Gambar 2.31 Ilustrasi WMX...…………………..…………….….………. 26 Gambar 2.32 Ilustrasi WMX...…………………..…………….….………. 26 Gambar 2.33 Ilustrasi Metode Pembalikan…………..…………….…….. 27 Gambar 2.34 Ilustrasi Metode Penyisipan.…………..…………….…….. 27 Gambar 2.35 Ilustrasi Metode Pemindahan…………..…………….……. 28 Gambar 2.36 Ilustrasi Metode Penukaran.…………..…………….……... 28 Gambar 2.37 Ilustrasi Metode Penggantian…………..……………..……. 28 Gambar 2.38 Ilustrasi Local Search…………………..……………..……. 31 Gambar 3.1 Tahapan Penelitian……………………………………….….. 34 Gambar 3.2 Flowchart GA…………………………………………….….. 37 Gambar 3.3 Flowchart GA dengan Local Search………………………… 38
v
Gambar 3.4 Crossover….……………………………………………….... 39 Gambar 3.5 Mutasi…….…………………………………………………. 40 Gambar 3.6 Merge Sort….……………………………………………….. 41 Gambar 3.7 Local Search.………………………………………………… 42 Gambar 3.8 Ilustrasi Kromosom..………………………………………… 45 Gambar 3.9 Contoh Metode Two Pont Crossover……………………….. 45 Gambar 3.10 Ilustrasi Metode Penukaran………………………………... 46 Gambar 4.1 Waktu Rata-rata Komputasi……………………………….… 55 Gambar 4.2 Generasi I07….………………………………..…………..... 56 Gambar 4.3 Diagram Persentase Error……………………..…………..... 59
vi
DAFTAR TABEL
Halaman Tabel 2.1 Pemetaan Proses Alamiah keproses Komputasi………………… 15 Tabel 2.2 Contoh 10 Kromosom Terbaik………………………………….. 31 Tabel 3.1 Representasi Item……………………………………………..… 43 Tabel 3.2 Dataset mmKP……………………………….………………….. 48 Tabel 4.1 Ukuran Populasi dan Maksimal Generasi………………...…….. 51 Tabel 4.2 Persentase Error…………………………………………...…….. 52 Tabel 4.3 Kromosom I01………………………………………..….……… 53 Tabel 4.4 Metode phGA…………………………………….…….…….…. 54 Tabel 4.5 Perbandingan Metode………………………….……….……….. 58
vii
BAB I PENDAHULUAN
1.1
Latar Belakang
Optimasi didefinisikan sebagai proses menentukan nilai minimum dan maksimum bergantung pada fungsi tujuannya (Malinda, 2015). Permasalahan optimasi sering ditemui dalam kehidupan sehari-hari, contoh dari permasalahan optimasi: penentuan jadwal, mencari rute terpendek dalam distribusi barang dan penyusunan barang dalam wadah (Container). Optimasi dikelompokan menjadi empat, yaitu Optimasi tanpa pembatas (Unconstraint Optimization), Optimasi dengan pembatas (Constraint Optimization), Optimasi dengan beberapa fungsi tujuan
(Multi-Objective
Optimization)
dan
Optimasi
Kombinatorik
(Combinatorial Optimization) (Syarif, 2014).
Persoalan Knapsack (Knapsack problem / KP) adalah salah satu permasalahan optimasi kombinatorik, tujuan dari KP memaksimalkan keuntungan (Profit) dari objek yang dipilih tanpa melewati kapasitas yang ada (Setemen, 2010). Dapat diilustrasikan sebagai berikut: Sebuah Knapsack / karung akan diisi dengan memilih sebuah objek diantara banyak objek (item), disana terdapat n item yang berbeda, setiap item j memiliki weight (wj), dan memiliki cost (cj). Knapsack dapat menampung weight sebanyak W (Gen dan Cheng, 2000).
2
Gambar 1.1 Ilustrasi Persoalan Knapsack KP sering ditemui di kehidupan sehari-hari, contohnya adalah seorang pendaki gunung yang akan menaiki gunung. Tas yang akan dibawa tentu memiliki kapasitas sehingga barang yang akan di hanya barang yang memiliki kegunaan selama pendakiannya.
KP memiliki beberapa macam tipe diantara lain: 1. 0-1 Knapsack Problem (KP) 2. Bounded Knapsack Problem (bKP) 3. 0-1 Multiple Knapsack Problem (mKP) ( Martello dan Toth, 1990) 4. Multiple-choice knapsack problem (mcKP) (Gen dan Cheng, 2000) 5. Multidimensional Knapsack Problem (mdKP) (Varnamkhasti,2012) 6. Multi-choice Multi-dimensional Knapsack Problem (mmKP) (Rahman dan Ahmed, 2009)
Selama ini banyak penelitian yang menerapkan KP. Salah satunya penelitian yang dilakukan Setemen, pada penelitiannya dia menerapkan KP dalam permasalahan optimasi pemilihan buah kemasan kotak. Optimasi pemilihan buah kemasan kotak pada proses distribusi barang digunakan untuk menekan biaya pengiriman dan memaksimalkan keuntungan (Setemen, 2010).
3
Selain itu penelitian mengenai KP diterapkan pada permasalahan optimasi distribusi barang dua tahap. Distribusi barang dua tahap digunakan untuk mempermudah pendistribusian barang dari produsen kepada konsumen, dengan cara membangun sebuah distributor yang berdekatan dengan wilayah pemasaran pelanggan. Distribusi dua tahap diterapkan pada pabrik yang mendistribusikan pada distributor dan dilanjutkan pendistribusian barang pada agen sesuai dengan kapasitas persediaan pabrik (Sulistyorini dan Mahmudy, 2015)
Artificial Inteligent (AI) merupakan salah ilmu terapan yang tergolong baru. AI mulai dikenal pada tahun 1956 (Russel dan Norvig, 1995). John McCarthy merupakan orang yang pertama kali mendefinisikan tujuan dari AI. Menurutnya tujuan dari AI adalah “The goal of AI is to develop machines that behave as though they were intelligent” (Ertel, 2011)
Implementasi AI sering ditemui dalam kehidupan sehari-hari. Salah satunya pada bidang Teknologi Informasi (Information Technology / IT), contoh dari penerapan AI dibidang IT adalah penelitian yang dilakukan Hermawan dan Bendi yang mengimplementasikan algoritma A* pada aplikasi puzzle (Hermawan dan Bendi, 2013).
AI juga diterapkan pada sistem perparkiran. AI diterapkan untuk program pengaturan dan penjadwalan parkir berbasis cerdas. Penelitian ini membantu pengelola parkir dalam mengelola informasi, mendata, dan mengatur penempatan lokasi parkir (Purwadi dan Istiyanto, 2005).
4 Pada bidang medis AI diterapkan untuk menganalisa penyakit dalam. Aplikasi yang dikembangkan merupakan sistem pakar yang digunakan untuk mendiagnosa penyakit dalam dengan menggunakan metode Faktor Kepastian. Diagnosa dilakukan dengan cara menganalisa masukan gejala berupa pertanyaan tentang apa yang dirasakan oleh pasien (Broto, 2010).
AI memiliki cabang ilmu diantaranya adalah: 1. Sistem Pakar (Expert System) 2. Logika Fuzzy (Fuzy Logic) 3. Jaringan syaraf tiruan (Neural Network) 4. Algoritma Genetika (Genetic Algorithm / GA) (Kusumadewi, 2003)
GA merupakan salah satu cabang ilmu dari AI. GA pertama kali dirintis oleh John Holland dari universitas michigan pada tahun 1960-an. GA telah diterapkan pada beberapa permasalahan yang sering ditemui dalam kehidupan sehari-hari. Salah satunya pada penelitian yang dilakukan oleh Nugraha. GA diterapkan pada permasalahan optimasi pada kegiatan belajar mengajar (Nugraha, 2013).
GA memiliki solusi penangan kendala. Solusi penanganan kendala pada GA yaitu Strategi Penolakan (Rejecting Strategy), Strategi Perbaikan (Repair Strategy), Strategi
Modifikasi Operasi Genetik Operator (Modified Genetic Operator
Strategy), dan Strategi Penalti (Penalty Strategy) (Syarif, 2014).
Penelitian ini akan difokuskan pada evaluasi kinerja GA dengan Strategi Penalti pada studi kasus Multi-choice Multi-dimensional Knapsack Problem (mmKP).
5 1.2
Rumusan masalah
Rumusan masalah dari penelitian ini adalah mengimplementasikan GA dengan Strategi Penalti pada studi kasus mmKP.
1.3
Batasan Masalah
Batasan masalah dari evaluasi kinerja GA adalah: 1. Studi kasus yang digunakan adalah mmKP 2. Representasi kromosom yang digunakan adalah representasi permutasi 3. Penangan pembatas yang digunakan adalah strategi penalti 4. Bahasa pemrograman yang digunakan adalah matlab
1.4
Tujuan
Adapun tujuan dari penelitian ini adalah: 1. Mengimplementasikan GA pada permasalahan mmKP. 2. Mengevaluasi kinerja GA pada studi kasus mmKP.
1.5
Manfaat
Manfaat dari penelitian ini 1. Menambah pustaka terkait dengan evaluasi kinerja AG pada studi kasus mmKP. 2. Mengetahui informasi mengenai efektivitas kinerja GA pada KP. 3. Memberikan sumber informasi bagi penelitian selanjutnya. 4. Mengetahui kinerja GA dengan strategi penalti kromosom pada KP.
BAB II TINJAUAN PUSTAKA
2.1 Knapsack Problem
Persoalan Knapsack (Knapsack Problem / KP) adalah salah satu permasalahan optimasi kombinatorik. Dapat diilustrasikan sebagai berikut:
Sebuah karung
(Knapsack) akan diisi dengan memilih sebuah objek diantara banyak objek (item). Terdapat n objek yang berbeda, setiap objek j memiliki berat (weight / wj) dan memiliki biaya (cost / cj). Knapsack dapat menampung berat sebanyak w (Gen dan Chen, 2000). Permasalahannya adalah untuk menemukan kumpulan objek yang memiliki biaya paling sedikit.
Gambar 2.1 Knapsack Problem (Gen dan Cheng, 2000)
7 Knapsack memiliki beberapa macam tipe diantara lain: 1. 0-1 Knapsack Problem (KP) ( Martello dan Toth, 1990) 2. Bounded Knapsack Problem (bKP) ( Martello dan Toth, 1990) 3. Multiple-choice knapsack problem (mcKP) (Gen dan Cheng, 2000) 4. Multidimensional Knapsack Problem (mdKP) (Varnamkhasti,2012) 5. Multiple-choice Multidimensional Knapsack Problem (mmKP) (Rahman dan Ahmed, 2009)
2.1.1 0.1 Knapsack Problem
0/1 KP merupakan salah satu variasi dari KP, dimana objek yang dimasukkan ke Knapsack dapat menghasilkan keuntungan yang maksimum. Berat objek yang akan dimasukkan tidak boleh melebihi kapasitas. Knapsack jenis ini setiap objek hanya tersedia 1 unit.
Penelitian yang telah mengimplementasikan KP jenis ini: Penyelesaian Knapsack Problem Menggunakan Algoritma Genetika (KW, Mardhiah, dan Charly, 2010), Implementasi Genetic Algorithm Berbasis Strategi Penalti pada Knapsack Problem (Malinda, 2015), dan Evaluasi Kinerja Genetic Algorithm (GA) dengan Strategi Perbaikan Kromosom Studi Kasus: Knapsack Problem (Dwiastuti, 2015). Berikut persamaan dari KP diberikan satu set n objek dengan: pi : keuntungan dari objek ke-i wi : berat dari objek ke-i C : kapasitas karung
8
∶
=
(2.1)
≤ =0 =
(2.2) 1,
∈
= (1, … , )
(2.3)
1; jika item ke − terpilih 0; item ke − i tidak terpilih
(Malinda, 2015)
2.1.2 Bounded Knapsack Problem
Bounded KnapsackProblem (bKP) merupakan variasi dari KP. bKP adalah permasalahan pengambilan sebagian atau semua objek dari beberapa objek yang jumlahnya terbatas. Penelitian yang pernah dilakukan menggunakan bKP : Penerapan Algoritma Genetika Hybrid pada Permasalahan Bounded Knapsack ( Hadi, 2016), Penyelesaian Bounded Knapsack Problem Menggunakan Dynamic Programming (Studi Kasus: Cv. Mulia Abadi) (Kosasi, 2013), dan Algorithms with Guarantee Value for Bounded Knapsack Problems (Guler dan Fidan, 2010).
Berikut persamaannya:
pi : keuntungan dari objek i wi : berat dari objek i bi : batas atas yang tersedia dari objek jenis i C : kapasitas dari karung :
1 ; jika objek ke − 0; objek ke −
9 n
max
: z=
px
i i
(2.4)
i 1
n
:
s.t
wx C i i
(2.5)
i 1
0 xi bi dan integer, i N = (1,…,n)
(2.5)
(Malinda, 2015)
2.1.3 Multiple-choice Knapsack Problem
Multiple-choice Knapsack problem (mcKP) merupakan salah satu dari variasi KP. Diilustrasikan sebagai berikut : Terdapat sebuah tas dengan kapasitas terbatas. Objek yang akan dimasukkan terbagi menjadi beberapa kelompok. Di dalam setiap kelompok terdapat beberapa benda. Permasalahannya adalah memilih sebuah benda dari setiap kelompok dengan keuntungan yang paling besar tanpa melebihi kapasitas.
Banyak penelitian yang menggunakan mcKP. Berikut beberapa penelitian yang mcKP : An Algorithm for the Penalized Multiple Choice
menggunakan
Knapsack Problem (Hilliard, dkk, 2014), Efficient Algorithms with Performance Guarantees for the Stochastic Multiple-Choice Knapsack Problem (Thanh, Yingce, Tao, dan Nicholas, 2015), dan Developing A 0-1 Multi-Choice Knapsack Problem Using Fuzzy (Noujavan dan Ghazanfari, 2004). Persamaan dari mcKP sebagai berikut. i
: indeks kelompok
j
: indeks objek
10 pi
:
keuntungan dari objek i
wi
: berat dari objek i
c
: kapasitas karung
m
: jumlah kelompok
Pilih sejumlah xij = (1,...,n) dari masing-masing tipe objek sehingga: ∶
=
.
(2.7)
.
≤
,
∈
≤ 1, ∈
=
= {1, … ,
}
= {1, … , }
(2.8)
(2.9)
1 ; jika objek ke − terpilih di kelompok ke − 0; objek ke − tidak terpilih di kelompok ke −
(Gen dan Cheng, 2000)
2.1.4 Multidimensional Knapsack Problem
Multidimensional Knapsack Problem (mdKP) merupakan variasi dari Knapsack Problem. mdKP adalah salah satu permasalahan NP-Hard Combinatorial (nondeterministic polynomial). Tujuan dari mdKP adalah meningkatkan jumlah objek yang dipilih (Martello dan Tooth, 1990)
Penelitian telah lama dilakukan untuk permasalahan mdKP, berikut beberapa penelitian mengenai mdKP : Overview of the Algorithms for Solving the Multidimensional Knapsack Problems(Varnamkhasti, 2012), An Approximate Dynamic Programming Approach to Multidimensional Knapsack Problems (Bertsimas dan Ramazan, 2002), dan The Minmax Multidimensional Knapsack
11 Problem with Application to a Chance-Constrained Problem (Kress, Michal, dan Maria, 2007). Berikut persamaannya dari mdKP: j : nomor objek i : nomor kelompok wi : berat kelompok ke- i objek ke- j ci : kapasitas karung ke-i pj : keuntungan objek ke-j xi : objek variabel keputusan Pilih sejumlah xi=(1,...,n) dari masing-masing tipe objek sehingga: ∶
=
(2.10)
≤
, = {1, … ,
}
(2.11)
∈ {0,1}, = {1, … , }. =
1; jika item ke − terpilih di 0; item ke − tidak terpilih di
ke − ke −
(Varnamkhasti, 2012)
2.1.5 Multi-choice Multi-dimensional Knapsack Problem
Multiple-Choice Multi-Dimensional Knapsack Problem (mmKP) merupakan salah variasi KP. mmKP lebih komplek dibandingkan varian 0-1 KP, dikenal sebagai Non Polynomial Hard Problem (NP-Hard Problem). Algoritma ini kurang cocok untuk
aplikasi pembuat keputusan (Decision Making) secara real time karena
memiliki kompleksitas yang tinggi (Hifi, dkk, 2005).
12 Kita ilustrasikan mmKP sebagai berikut : terdapat n kelompok, kelompok i memiliki li objek. Setiap objek dalam kelompok memiliki keuntungan dan membutuhkan m sumber daya. Persoalannya mmKP harus memilih satu objek dari setiap kelompok dengan keuntungan besar, tetapi m sumber daya tidak melebihi batasan sumber daya (Akbar, dkk, 2004)
Penelitian yang telah dilakukan mengenai mmKP : A Reactive Local SearchBased. Pada penelitiannya permasalahan mmKP diselesaikan menggunakan dua algoritma : A Simple Reactive Local Search dan Local Search (LS) yang telah dimodifikasi. Algoritma pertama menggunakan LS dan kombinasi Degrading dengan Deblocking Strategy. Algoritma kedua menggunakan Memory List, ini digunakan untuk mengganti Deblocking Strategy. Hasil komputasi menunjukkan algoritma pertama menghasilkan solusi yang baik dengan waktu komputasi yang cepat. Algoritma kedua menghasilkan solusi yang sangat baik, mendapatkan solusi yang optimal pada beberapa permasalahan dengan waktu yang sesuai (Hifi, dkk, 2005).
A New Hybrid Algorithm for the Multiple-Choice Multi-Dimensional Knapsack Problem. Pada penelitiannya menggunakan algoritma hybrid : Branch and Bound Pareto-algebraic yang dinilai lebih baik dibandingkan algoritma Constructive Procedure (CP) dan A Complementary One (CCP). Algoritma ini akan lebih berguna dipakai dalam aplikasi real-time. Hal ini dikarenakan pada aplikasi realtime waktu running merupakan parameter yang penting (Zennaki, 2013).
13
v =10 r1=5, r2=7
v =12 r1=7, r2=7
v =14 r1=4, r2=7
v =11 r1=8, r2=2
v =7 r1=5, r2=3
v =9 r1=5, r2=5
v =13 r1=6, r2=4
v =7 r1=10, r2=8
Grup
Grup
Grup
Maksimal Sumber Daya Type r1: 17 Type r2: 15
Knapsack
Gambar 2.2 Ilustrasi mmKP (Akbar, dkk, 2004)
Berikut persamaan dari mmKP : n
max : v = i 1
n
s.t :
li
x v
(2.12)
≤ Rk
(2.13)
li
x r
ij ijk
i 1
ij ij
j 1
j 1
li
1 ≤ k ≤ m, xij ∈ {0,1},
x
ij
=1
j 1
Dengan i
: index kelompok
j
: index produk
k
: index sumber daya
n
: jumlah kelompok
li
: jumlah produk
vij : keuntungan produk j di kelompok i rijk : sumber daya yang dibutuhkan produk j dikelompok i Rk : batasan sumber daya (Akbar, dkk, 2004)
14 2.2 Algoritma Genetika
Algoritma genetika (Genetic Algorithm / GA) merupakan evolusi/ perkembangan dunia komputer dalam bidang kecerdasan buatan (Artificial Intelligence). Kemunculan algoritma genetika terinspirasi teori evolusi Darwin dan teori-teori dalam ilmu biologi, sehingga banyak istilah dan konsep biologi yang digunakan.
GA merupakan algoritma pencarian heuristik. Heuristik merupakan teknik yang digunakan untuk meningkatkan efisiensi dari proses pencarian. Metode Heuristik akan memilih jalur yang paling mungkin dalam penyelesaian permasalahan secara optimal (Rahmanti, 2016)
Algoritma genetika terdiri dari dua operasi yaitu operasi genetika dan operasi evolusi. Operasi genetika terdiri dari operator crossover dan operator mutasi. Pada operasi evolusi terdapat operator seleksi. Populasi generasi yang baru dibentuk dengan cara menyeleksi nilai ketahanan (fitness) dari kromosom induk (pa-rent) dan nilai fitness dari kromosom anak (offspring), serta menolak kromosomkromosom yang lainnya sehingga ukuran populasi konstan (Kartika, 2013).
Aspek penting dalam penggunaan GA: 1. Definisi fungsi ketahanan (fitness function) 2. Definisi dan implementasi representasi genetik 3. Definisi dan implementasi operasi genetik (Nugraha, 2008).
GA memiliki beberapa kelebihan dibandingkan algoritma lainnya. Menurut Gen dan Cheng(1997), kelebihan tersebut adalah:
15 1. Algoritma GA hanya melakukan sedikit perhitungan matematis yang berhubungan dengan masalah yang ingin diselesaikan 2. Operator-operator evolusi membuat algoritma GA sangat efektif pada pencarian global 3. Algoritma GA memiliki fleksibilitas yang tinggi untuk digabungkan dengan metode pencarian lainnya supaya lebih efektif.
GA memiliki beberapa istilah, berikut pemetaan proses alamiah ke dalam proses komputasi GA pada tabel 2.1
Tabel 2.1 Pemetaan Proses Alamiah Ke Proses Komputasi
Proses Alamiah
Proses Komputasi
Individu
Penyelesaian Masalah
Populasi
Himpunan Penyelesaian
Fitness/Kebugaran
Kualitas Penyelesaian
Kromosom
Kode/Representasi Penyelesaian
Gen
Bagian Dari Representasi Penyelesaian
Proses Alamiah
Proses Komputasi
Pertumbuhan
Pendekodean Representasi Penyelesaian
Penyilangan
Operator Genetika
Proses Alamiah
Proses Komputasi
Mutasi
Operator Genetika
Seleksi Alam
Menyeleksi Penyelesaian Masalah
Di dalam GA untuk menyelesaikan suatu permasalahan optimasi umumnya menggunakan kerangka kerja, yang ditunjukkan pada Gambar 2.3
16
Gambar 2.3 Kerangka Kerja Implementasi GA
Struktur dasar GA terdiri atas beberapa langkah, berikut langkah-langkahnya 1. Insisalisasi populasi. 2. Evaluasi populasi. 3. Seleksi populasi yang akan dikenai operator genetika. 4. Proses penyilangan pasangan tertentu. 5. Evaluasi populasi baru. Ulangi dari langkah 3 selama syarat berhenti belum terpenuhi.
2.2.1 Inisialisasi Populasi
Proses yang pertamakali dilakukan di dalam GA adalah inisialisasi populasi. Inisialisasi Populasi dilakukan untuk merepresentasikan kromosom. Proses ini dikenal dengan istilah encoding. Penentuan metode representasi sangat berpengaruh pada komponen-komponen GA, yang dalam hal ini akan mempengaruhi efektivitas dan efisiensi dari GA.
17 GA memiliki beberapa metode untuk merepresentasikan kromosom, berikut metode yang umum dipakai: 1. Representasi Nilai
Metode ini sering dipakai dalam permasalahan penyesuaian kata (Word Matching Problem), Contoh kromosom yang menggunakan metode representasi nilai pada Gambar 2.4
2390 4322 1254 6632 9812 Gambar 2.4 Contoh Kromosom Metode Representasi Nilai
2. Representasi Biner
Metode ini sering ini digunakan pada banyak persoalan salah satunya optimasi fungsi-fungsi matematika. Contoh kromosom yang menggunakan metode representasi biner pada Gambar 2.5
0 0 1 1 0 1 0 1 Gambar 2.5 Contoh Kromosom Metode Representasi Biner
3. Representasi Permutasi
Metode ini sering digunakan pada persoalan yang memiliki prioritas dalam penghitungan
nilai
ketahanan
(fitness).
Contoh
kromosom
menggunakan metode representasi permutasi pada Gambar 2.6 7 4 1 6 9 2 7 6 8 Gambar 2.6 Contoh Kromosom Metode Representasi Permutasi
yang
18 4. Representasi Pohon
Metode ini digunakan pada persoalan yang solusinya memiliki struktur pohon. Terdapat dua jenis representasi pada metode pohon yaitu: a. Edge Encoding Metode
ini
N
menggunakan
digit
bilangan
biner
yang
merepresentasikan jaringan dengan N arc. Apabila digit ke-i tersebut merupakan bagian dari solusi.
0
0
1
1
1
0
0
1
0
1
1
0
Gambar 2.7 Contoh Edge Encoding b. Vertex Encoding Salah satu metode representasi yang cukup dikenal adalah bilangan Prüfer. Bilangan Prüfer adalah suatu bilangan dengan N digit yang dapat merepresentasi suatu Tree dengan N-2 node. 5 3 8 1
3 4
2
13
7
Bilangan Prüfer : 4
P (T) = [4 2 2 7 3]
3 14
6
Gambar 2.8 Contoh Representasi Bilangan Prüfer
19 5. Representasi Matrik Metode ini digunakan pada persoalan dimana solusinya dalam bentuk matrik. Matrik dapat berupa satu dimensi, dua dimensi, dan tiga dimensi sesuai dengan persoalan yang dihadapi. 11
12
21
22
… m1
… m2
… … … …
1n 2n
… mn
Gambar 2.9 Contoh Representasi Matrik (Syarif, 2014)
2.2.2 Evaluasi Populasi Metode yang umumnya dipakai pada evaluasi populasi adalah menghitung nilai fungsi tujuan sebagai fitness value. Kromosom yang layak setelah proses crossover dan mutasi menghasilkan offspring yang tidak layak, oleh karena itu setiap generasi harus diuji kelayakannya (Syarif, 2014)
Untuk mengatasi kromosom yang tidak layak dapat menggunakan beberapa metode yaitu: 1. Rejecting Methods Metode ini akan menolak semua kromosom yang tidak layak selama proses evolusi. Cara ini merupakan cara termudah tetapi kurang efektif untuk menangani masalah.
2. Repairing Methods Metode ini akan mengambil kromosom yang tidak layak dan melakukan prosedur untuk memperbaiki kromosom.
20 3. Penalty Methods Metode ini adalah metode yang sering dipakai dalam permasalahan optimasi yang memiliki kendala. Metode ini akan menambahkan penalti pada solusi yang tidak layak (Gen dan Cheng, 2000)
4. Strategi Penyesuaian Operator Genetika Pada strategi ini operator-operator genetika yang diterapkan harus mampu menghasilkan kromosom yang memenuhi kendala (Zukhri, 2014)
5. Decoding Pada metode ini terdapat decoder yang berfungsi untuk membangun relasi antara daerah penyelesaian buatan yang lebih mudah diselesaikan.
6. Pengamanan Pada metode ini terdapat operator yang memastikan solusi yang dibangkitkan selama proses pencarian adalah penyelesaian yang layak (Purnomo, 2014)
Pada penelitian ini akan dilakukan menggunakan metode penalti
2.2.3 Seleksi Populasi Pada proses ini akan dipilih kromosom yang tetap bertahan dalam populasi. Kromosom yang terpilih mempunyai kemungkinan untuk dipasangkan dengan kromosom lain atau mengalami proses penyilangan.
Terdapat beberapa model seleksi yaitu seleksi sebanding dengan nilai fitness, Seleksi Peringkat, Seleksi Turnamen, dan Seleksi Elitism (Zukhri, 2014). Selain model seleksi diatas terdapat pula Roulette Wheel Selection disebut juga
21 Stochastic Sampling with Replacement. Setiap individu akan dibuat menjadi satu barisan, setiap individu memiliki nilai yang setara dengan nilai fitness. Model seleksi ini merupakan salah satu model yang paling sering digunakan. Number Of Individual Fitness Value Selection Probability
1 2.0 0.18
2 1.8 0.16
3 1.6 0.15
4 1.4 0.13
5 1.2 0.11
6 1.0 0.09
7 0.8 0.07
8 0.6 0.06
9 0.4 0.03
10 0.2 0.02
Gambar 2.10 Contoh Selection Probability dan Fitness Value(Volna, 2013)
2.2.4 Proses Penyilangan (Crossover)
Pada tahapan ini akan dilakukan proses penyilangan. Proses ini dilakukan untuk menghasilkan kromosom turunan(offspring) dengan menggabungkan elemen dari induk yang terpilih (Syarif, 2014) ada beberapa metode crossover yaitu:
1. One Point Crossover One point crossover akan memilih sebuah angka secara random (c). Maka angka yang nilainya < c akan dilakukan swap (perpindahan tempat) yang ditunjukkan pada Gambar 2.12 1 1 0 0 1 0 0 1
0 0 1 0 1 0 0 1
SWAP
0 0 1 0 1 1 0 0
1 1 0 0 1 1 0 0
Gambar 2.11 Contoh Metode One Point Crossover
2. Two point crossover Metode ini akan memilih dua angka secara random (c dan d), setelah dua angka didapatkan dilakukan swap diantara angka c dan d
11 0.0 0.0
c 1
1
0
0
1
0
0
1
1
1
0
0
1
0
0
1
0
0
1
1
1
0
0
SWAP
SWAP
0
22
d
c
d
1
1
0
0
0
0
1
0
Gambar 2.12 Contoh Metode Two Point Crossover (Luke, 2015) 3. Partial Mapped Crossover (PMX) Metode ini sering dipakai pada permasalahan representasi permutasi. Metode ini merupakan pengembangan dari crossover dua titik. Proses PMX dilakukan sebagai berikut : a. Pilih satu bagian dari kromosom secara acak
Parent 1
1
7
2
3
4
6
5
8
Parent 2
4
6
3
5
7
1
8
2
Gambar 2.13 Ilustrasi PMX b.
Tukar masing-masing substring
Parent 1
1
7
3
5
7
6
5
8
4
1
8
2
SWAP Parent 2
4
6
2
3
Gambar 2.14 Ilustrasi PMX c.
Tentukan pemetaan masing-masing gen pada substring 3 5 7
2 4
3 7
5
2 3 4 Gambar 2.15 Ilustrasi PMX
23 d. Perbaiki kromosom dengan menggunakan informasi dari tahap c. Offspring 1
1
4
3
5
7
6
2
8
Offspring 2
7
6
2
3
4
1
8
5
Gambar 2.16 Ilustrasi PMX (Syarif, 2014)
4. Order Crossover (OX) Metode ini mirip dengan PMX, perbedaanya pada prosedur perbaikan. Berikut contoh dari OX : a. Pilih satu bagian kromosom secara acak Parent 1
1 7 2 3 4 6 5 8 Gambar 2.17 Ilustrasi OX
b. Pindahkan substring terpilih, pada offspring sesuai pada posisinya 2 3 4
Offspring 1
Gambar 2.18 Ilustrasi OX c. Hapus node yang sudah terdapat pada offspring dari parent kedua Parent 1
6
5 7 1 8 Gambar 2.19 Ilustrasi OX
d. Pindahkan sisa node yang ada pada parent secara berurutan dari kiri ke kanan Offspring 1
6 5 2 3 4 7 1 8 Gambar 2.20 Ilustrasi OX
Dengan cara melakukan cara yang sama dimulai pada parent kedua dapat diperoleh offspring kedua sebagai berikut :
24 Offspring 2
1 2 3 5 7 4 6 8 Gambar 2.21 Ilustrasi OX (Syarif, 2014)
5. Position-based Crossover (PX) Metode ini merupakan pengembangan dari metode Uniform Crossover untuk kromosom dengan representasi permutasi. Pada metode ini node akan dipilih secara acak. Prosedur PX sebagai berikut : a. Pilih sekumpulan substring dari parent pertama secara random Parent 1 :
1 7 2 3 4 6 5 8 Gambar 2.22 Ilustrasi PX
b. Pindahkan substring terpilih pada offspring sesuai pada posisinya Offspring 1
2
5 8
Gambar 2.23 Ilustrasi PX c. Hapus node yang sudah terdapat offspring dari parent kedua Parent 2 :
4 6 3 5 7 1 8 2 Gambar 2.24 Ilustrasi PX
d. Pindahkan sisa node yang ada pada parent kedua secara berurutan dari kiri kekanan Parent 2 :
4 6 3 5 7 1 8 2
Offspring 1
4 6 2 3 7 1 5 8 Gambar 2.25 Ilustrasi PX
Proses yang sama dilakukan pada parent memperoleh offspring kedua (Syarif, 2014)
kedua untuk dapat
25 6. Order-based Crossover (ObX) Perbedaan metode ini dari metode PX hanya pada prosedur penempatan posisi node. Disini, posisi substring yang tidak terpilih diisi dengan substring pada posisi yang sama dari parent kedua. Berikut contoh dari Obx : Parent 1 :
1 7 2 3 4 6 5 8
Offspring
4 6 2 3 7 1 5 8
Parent 2 :
4 6 3 5 7 1 8 2 Gambar 2.26 Ilustrasi ObX (Syarif, 2014)
7. Cycle Crossover (CX) CX dilakukan dengan menempatkan beberapa unit node yang dipilih dari suatu parent dan sisanya diambil dari induk yang lain. Perbedaanya , pada metode ini pemilihan node
dilakukan dengan membentuk cycle pada
posisi yang sepadan dari masing-masing contoh. Berikut contoh dari metode CX : a. Pilih titik potong pada kromosom secara acak Parent 1 :
1 7 2 3 4 6 5 8
Parent 2 :
4 6 3 5 7 1 8 2 Gambar 2.27 Ilustrasi CX
b. Salin node yang ada pada cycle dari parent 1 sesuai dengan posisinya Offspring 1
1 7 2 3 4 6 5 8 Gambar 2.28 Ilustrasi CX
26 c. Salin node yang tidak terdapat cycle dari parent 2 sesuai dengan posisinya Parent 2
4 6 3 5 7 1 8 2
Offspring 1
1 7 3 5 4 6 8 2 Gambar 2.29 Ilustrasi CX (Syarif, 2014)
8. Weight Mapping Crossover (WMX) Proses WMX sebagai berikut : a. Pilih titik potong secara random 2 1 7 4 5 3 6
Parent 1
3 7 2 6 5 1 4
Parent 2
Gambar 2.30 Ilustrasi WMX b. Urutkan node secara ascending dan tentukan pemetaan dari masingmasing node
5
3
6
3
5
6
5
3
6
1
4
5
Gambar 2.31 Ilustrasi WMX c. Bentuk offspring dengan menggunakan informasi pemetaan dari masing-masing node Offspring 1
2 1 7 4 6 3 5
Offspring 2
3 7 2 6 4 1 5 Gambar 2.32 Ilustrasi WMX (Syarif, 2014)
27 2.2.5. Mutasi
Proses mutasi dilakukan dengan cara mengubah nilai gen pada posisi tertentu. Nilai gen dipilih secara acak, nilai gen yang mengalami mutasi akan berubah. Diilustrasikan nilai gen awal adalah nol ketika mengalami mutasi akan berubah menjadi satu, begitu pula sebaliknya.
Pada metode mutasi terdapat beberapa macam metode 1. Metode pembalikan (Inversion Mutasi) Metode ini dilakukan dengan mengambil substring secara acak yang terletak diantara dua titik pada kromosom, selanjutnya substring dilakukan invers. Ilustrasi terdapat pada Gambar 2.33 Parent
: Offspring
:
8
7
4
5
3
9
8
2
8
7
4
9
3
5
8
2
Gambar 2.33 Ilustrasi Metode Pembalikan 2. Metode Penyisipan (Insertion Mutation) Metode ini akan memilih satu gen yang akan disisipkan pada posisi yang dipilih secara acak. Ilustrasi pada Gambar 2.34 Parent
:
Offspring :
8
7
4
5
3
9
8
2
8
5
7
4
3
9
8
2
Gambar 2.34 Ilustrasi Metode Penyisipan
28 3. Metode Pemindahan (Displacement Mutation)
Metode ini akan mengambil dua gen yang akan disisipkan pada posisi yang dipilih secara acak. Ilustrasi metode ini pada Gambar 2.35. Parent :
8
7
4
5
3
9
8
2
Offspring :
8
5
4
8
2
5
3
9
Gambar 2.35 Ilustrasi Metode Pemindahan 4. Metode Penukaran(Swap Mutation)
Metode ini memilih dua buah gen secara acak, selanjutnya dua buah akan saling dipertukarkan. Metode ini diilustrasikan pada Gambar 2.36.
Parent :
8
7
4
5
3
9
8
2
Offspring :
8
2
4
5
3
9
8
7
Gambar 2.36 Ilustrasi Metode Penukaran
5. Metode Penggantian(Flip Mutation) Metode ini mengganti nilai gen yang dipilih, apabila gen bernilai satu akan diganti menjadi nol begitu pula sebaliknya. Ilustrasi metode ini pada Gambar 2.37. Parent :
1
0
1
1
0
0
0
1
Offspring :
1
0
0
0
1
0
0
1
Gambar 2.37 Ilustrasi Metode Penggantian (Syarif, 2014)
29 2.2.6. Strategy Penalty
Strategi penalti merupakan salah satu metode yang digunakan untuk penanganan kendala. Strategi penalti merupakan metode yang sering dipakai pada optimasi berkendala.
Fungsi penalti dapat menggunakan dua cara, yaitu: 1.
Metode Penambahan Penjumlahan antara fungsi tujuan dan fungsi penalti akan menghasilkan fungsi evaluasi, seperti berikut ini. evalx fx px (2.12) merupakan fungsi tujuan awal, jika kromosom tidak memenuhi fungsi pembatas maka nilai fungsi evaluasi ditambah dengan fungsi penalti px . Terlihat jelas bahwa nilai fungsi evaluasi akan bernilai sama dengan nilai fungsi tujuan jika nilai dari px bernilai 0. Artinya kromosom tersebut memenuhi fungsi pembatas.
2.
Perkalian Metode lain yang bisa digunakan adalah dengan mengalikan fungsi tujuan dengan fungsi penalti sebagai berikut. evalx fx* px (2.13) Berbeda dengan metode sebelumnya, pada metode perkalian jika kromosom memenuhi pembatas (feasible) maka px 1 . Nilai fungsi penalti untuk persoalan maksimasi haruslah 0 px 1 . Sebaliknya, untuk persoalan n
minimasi, nilai fungsi penalti haruslah
w
i
i 1
(Malinda, 2015)
30 Pada penelitian yang dilakukan Yeniay, mendiskusikan tentang kelebihan dan keuntungan strategi penalti, berikut beberapa stategi penalti yang digunakan 1.
Death penalty Metode ini akan menolak solusi yang tidak layak dari populasi. Pada metode ini tidak akan ditemukan solusi yang tidak layak. Kelemahan dari solusi ini adalah ketika memiliki kendala yang besar akan menghabiskan banyak waktu untuk menemukan solusi yang layak
2.
Static Penalties Pada metode ini parameter penalti tidak berdasarkan angka generasi terbaru. Kelemahan dari metode ini adalah jumlah parameter yang harus di set tergolong banyak.
3.
Dynamic Penalties Parameter
pada
metode
ini
berdasarkan
angka
generesai
terbaru.
Kelemahannya metode ini harus menetukan parameter, namun pada kasus ini sulit untuk menentukkan parameter.
4.
Annealin penalties Metode ini berdasarkan simulasi annealing. Kelemahan dari metode ini adalah metode ini sangat sensitif terhadap nilai parameter, tidak adanya cara yang spesifik dalam menentukkan parameter
5.
Adaptive penalties Parameter pada metode ini akan selalu akan diperbarui untuk setiap generasinya berdasarkan informasi yang dikumpulkan dari populasi
31
2.3. Local Search
Local search (LS) merupakan salah satu metode yang tertua dan paling mudah dalam metaheuristic method. Metode ini dimulai dengan memberikan solusi diawal (initial solution), pada setiap iterasi, selanjutnya solusi dibagian akhir akan diubah ( Talbi, 2009)
Metode LS yang diterapkan dalam penelitian ini dengan mengambil 10 kromosom terbaik (memiliki nilai optimum tertinggi) di generasi baru. Kromosom ini selanjutnya diambil satu titik yang akan dilakukan proses mutasi. Apabila kromosom hasil mutasi lebih baik maka kromosom ini akan diambil, begitupula sebaliknya. Tabel 2.2 Contoh 10 Kromosom terbaik No 1 2 3 4 5 6 7 8 9 10
Profit 162 150 159 162 167 154 163 167 159 159
4 2 5 4 5 5 4 4 5 4
Kromosom 5 2 5 3 2 4 5 2 5 2 4 4 5 1 5 2 2 4 5 2
3 2 4 3 2 1 2 4 4 5
Kita ambil satu kromosom diatas untuk dilakukan mutasi. 4 5 2 3 3
4 5 2 4 3 Gambar 2.38 Ilustrasi Local Search
3 5 3 3 4 2 5 3 3 1
32 Proses mutasi menganti bilangan 3 menjadi 4. Hasil pergantian gen tersebut menghasilkan keuntungan sebesar 173. Hal ini tentu lebih baik dari kromosom sebelumnya. Kromosom sebelumnya hanya memiliki keuntungan sebesar 162, maka kromosom yang dilakukan mutasi akan masuk keproses selanjutnya. Proses pada LS terdapat dua strategi yaitu: 1. The Degrading Strategy strategi ini diaplikasikan setelah solusi yang paling akhir ditingkatkan dengan cara swap antar item. 2. The Deblocking Strategy Strategi membuat arah pencarian berubah hal ini dilakukan agar hasil yang didapat lebih optimal (Sbihi, Michrafy, dan Hifi, 2005)
BAB III METODE PENELITIAN
3.1 Waktu Dan Tempat Penelitian
Penelitian dilaksanaan di lingkungan Program Studi Ilmu Komputer Fakultas Matematika Dan Ilmu Pengetahuan Alam Universitas Lampung. Waktu penelitian dilakukan di Semester Ganjil tahun ajaran 2015/2016
3.2 Lingkungan Pengembangan
Lingkungan pengembangan yang akan digunakan pada penelitian ini adalah sebagai berikut: a. Software
: Ubuntu 14.04 LTS, Matlab R2016a
b. Hardware : PC HP (Processor intel
®
Core
TM
i5-3470S CPU @2.90 GHZ x 4,
RAM 4 GB
3.3 Tahapan Penelitian Tahapan penelitian yang akan dilakukan terdapat beberapa langkah yaitu studi literatur dari test problem, penyusunan algoritma, pengembangan program, pengujian dan eksperimen, analisis dan pembahasan, dan terakhir pengambilan kesimpulan. Tahapan penelitian terdapat pada Gambar 3.1.
34
Gambar 3.1 Tahapan Penelitian
35 3.3.1. Studi Literatur dari Test Problem Penelitian mengenai knapsack telah sering dilakukan, berikut penelitian mengenai knapsack : 1.
Selama ini banyak penelitian yang menerapkan Knapsack Problem. Salah satunya penelitian yang dilakukan Setemen, Pada penelitiannya dia menerapkan knapsack problem dalam permasalahan optimasi pemilihan buah kemasan kotak. Optimasi pemilihan buah kemasan kotak pada proses distribusi barang digunakan untuk menekan biaya pengiriman dan memaksimalkan keuntungan (Setemen, 2010).
2.
Selain itu penelitian mengenai Knapsack diterapkan pada permasalahan optimasi distribusi barang dua tahap. Distribusi barang dua tahap digunakan untuk mempermudah pendistribusian barang dari produsen kepada konsumen, dengan cara membangun sebuah distributor yang berdekatan dengan wilayah pemasaran pelanggan. Distribusi dua tahap diterapkan pada pabrik yang mendistribusikan pada distributor dan dilanjutkan pendistribusian barang pada agen dengan kapasitas permintaan yang sesuai dengan kapasitas persediaan pabrik (Sulistyorini dan Mahmudy, 2015)
3.
Permasalahan Knapsack juga diterapkan pada pemilihan menu makan berdasarkan harga, pada penelitian ini diterapkan metode Dynamic Programming (Prabowo, dkk, 2013)
Pada penelitian ini knapsack problem yang akan digunakan adalah Multi-choice Multi-dimensional Knapsack Problem (mmKP), berikut beberapa penelitian yang menggunakan mmKP:
36 1.
Penelitian ini membahas mengenai permasalahan mmKP menggunakan algoritma A Reactive Local Search-Based (HIFI, dkk, 2005)
2.
Pada peneltian yang dilakukan oleh Rahman dan Syed permasalahan mmKP diselesaikan menggunakan Algoritma Genetika (GA) (Rahman dan Syed, 2009)
3.
Penelitian
ini
membahas
penyelesaian
mmKP
pada
Pram
Model
menggunakan algoritma Heuristic (Sadid, dkk, 2005)
Pada penelitian ini algoritma yang dipakai adalah GA, berikut contoh penelitian yang menggunakan GA: 1.
Penelitian yang dilakukan oleh Widodo dan Wayan merupakan penerapan GA pada sistem rekomendasi wisata kuliner (Widodo dan Wayan, 2010)
2. Penelitian ini menggabungkan Algoritma Semut dan GA untuk pencarian jalur terpendek (Mutakhiroh, dkk, 2007)
3. Pada penelitian ini GA digunakan untuk meningkatkan kinerja
Fuzzy
Clustering untuk pengenalan pola (Widyastuti dan Amir, 2007)
3.3.2. Penyusunan Algoritma Algoritma yang dipakai dalam penelitian ini akan ditunjukkan pada Flowchart sebagai berikut:
37
Gambar 3.2 Flowchart GA
38 Mulai
Limit, UkPop, JumGen, MaxGen, nItem, pC, pM, Profit
JumGen = Length (grup)
nItem = Length (item)
For i = 1 : MaxGen
Crossover
Mutasi
Evaluasi
Seleksi
nLocalSearch
i
Solusi Optimal
Selesai
Gambar 3.3 Flowchart GA Local Search
39 Mulai fCross = 0; fCross2 = 0; fIndex = 0; ParentX (1,:) = Populasi (1,:); For i = 1 ; UkPop cc = rand;
If cc < pC Tidak Ya fCross = fCross + 1; ParentX (fCross,:) = Populasi (i,:); fIndex = i;
fCross2 = fCross2+1; tempPop2(fCross2,:) = Populasi(i,:);
i
for j =1 : fCross
Tidak tPotong = rnd1; flag2 = rnd2;
If rnd2 < rnd1
ya
tPotong = rnd2; flag2 = rnd1;
tempA = parentX (i-1, ; ) ; tempA = parentX (i, : ) ; tempA (tPotong : (tPotong – 1 + flag2)) = parentX (i, (tPotong : (tPotong – 1 + flag2))); tempB (tPotong : (tPotong – 1 + flag2)) = parentX (i-1, (tPotong : (tPotong – 1 + flag2))); hasilX (i-1,: ) = temppA; hasilX(I, : ) =tempB; fCross2 = 0
j
selesai
Gambar 3.4 Crossover
40
Gambar 3.5 Mutasi
41
Mulai
for i = 1 : length(PopGab(:,1));
Populasi2(i,:) = [ProfitGab(i) PopGab(i,:)];
Populasi2 = mergesort2 (Populasi2); a= length(Populasi2(:,1)); b= length(Populasi2(1,:));
i
for i = 1: UkPop
Populasi(i,:) = Populasi2(a-UkPop+i,(2 : b)); popProfit(i) = Populasi2(a-UkPop+i,1);
i
Selesai
Gambar 3.6 Merge Sort
42
Gambar 3.7 Local Search Jika diketahui total required resource melebihi resource constraint maka nilai penalti akan dibangkitkan menggunakan persamaan-persamaan berikut.
43 n
a:
w
(3.1)
i
i 1 n
b:
wx
i i
(3.2)
diff : minc, a c
(3.3)
dist : |b c|
(3.4)
i 1
Prosedur strategi penalti : if b < c then begin penalti = 1 - dist/diff; if penalti <= 0 then penalti = 0.00001; fit_val(i)= fit_val(i) * penalti; end end end (Malinda, 2015)
3.3.3. Pengembangan Program 1. Representasi Item Tabel 3.1 Representasi Item
Grup
1
2
3
Item
Profit item
Required Resource1
Required Resource2
Required Resource3
Required Resource4
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
7.00 17.00 25.00 35.00 36.00 9.00 10.00 10.00 39.00 44.00 15.00 19.00 20.00 44.00 50.00
1 1 4 4 6 0 0 1 9 8 2 2 3 6 9
3 4 3 5 8 0 0 1 1 7 0 3 1 7 5
1 9 9 8 3 4 1 6 2 0 5 2 6 5 9
1 9 8 0 0 4 8 0 2 8 5 6 4 6 2
Required Resource5
6 3 2 6 7 2 7 6 4 2 5 2 7 9 2
44 Grup
4
5
Item
Profit item
Required Resource1
Required Resource2
Required Resource3
Required Resource4
1 2 3 4 5 1 2 3 4 5
50.00 25.00 32.00 37.00 37.00 24.00 30.00 32.00 43.00 44.00
0 2 5 6 7 4 4 5 5 9
1 2 5 3 9 0 8 2 5 2
3 7 6 6 7 7 9 7 9 2
8 0 1 9 2 0 0 2 5 2
Required Resource5
0 8 9 1 3 2 0 0 2 3
Item-item dapat direpresentasi menggunakan array 3 dimensi yang memiliki 3 kolom berisi number of item, number of grup dan required resource. Tabel 3.1. merupakan Tabel yang merepresentasikan data dari number of item, number of grup dan required resource. Data tersebut merupakan salah satu dari 13 Benchmark yang diujicobakan. (resource constraints = 25).
2. Representasi Kromosom
Kromosom adalah kumpulan dari gen-gen. Jumlah gen dalam kromosom sama dengan jumlah grup yang tersedia. Gen yang dipilih dari setiap grup hanya berjumlah 1. Kromosom kemudian dibangkitkan pada ruang solusi feasible (layak), Artinya kromosom awal merupakan kromosom yang layak. Berikut merupakan algoritma yang digunakan pada pembangkitan kromosom yang layak.
for i= 1 : UkPop; for j = 1 : JumGen; RK(j,:,1) = (kk((Populasi(i,j)),:,j)); end; batas = 0; for h = 1 : nItem; % cek layak sumK = (sum (RK(:,h+1,1))); if sumK > Limit batas = 1; break end; end;
45 if BatasL == 0; Profit = (sum (RK(:,1,1))); Status = 'Layak'; else [Populasi, Profit] = repair(nItem,JumGen,Populasi,RK,BatasL,Limit,kk,i); Status = 'Layak'; end; popProfit(i) = Profit; BatasL = 0; end;
Sebagai contoh, berikut merupakan kromosom yang telah dibangkitkan melalui proses pembangkitan kromosom diatas. Kelompok
1
2
3
4
5
Produk
4
5
2
3
4
Gambar 3.8 Ilustrasi Kromosom
3. Crossover Metode crossover dalam pengujian ini adalah Two Point Crossove. Metode ini akan mengambil dua titik secara random. Bilangan yang akan berada dalam dua titik selanjutnya akan ditukar dengan kromosom lain.
d
c 1
1
0
0
1
d
c 0
0
1
1
1
0
0
1
0
1
0
0
1
1
1
0
0
SWAP
SWAP
0
0
1
1
0
0
0
0
1
0
Gambar 3.9 Contoh Metode Two Point Crossover Berikut merupakan prosedur crossover yang digunakan if cc < pC fCross = fCross + 1; ParentX (fCross,:) = Populasi (i,:); fIndex = i; else fCross2 = fCross2+1;
46 tempPop2(fCross2,:) = Populasi(i,:); end; if mod(fCross , 2) == 1; if fIndex == UkPop fIndex2 = fix ((rand)*(length(tempPop2(:,1)))+1); ParentX(fCross+1,:) = tempPop2(fIndex2,:); else ParentX(fCross+1,:) = Populasi(fIndex+1,:); fCross = fCross + 1; end; end; fCross2 = zeros; for i = 1 : fCross; fCross2 = fCross2+1; if fCross2 == 2; rnd1 = int8((rand*JumGen)); rnd2 = int8((rand*JumGen)); if rnd1 == 0; rnd1 = 1; end; if rnd2 == 0; rnd2 = 1; end; if rnd2 < rnd1; tPotong = rnd2; flag2 = rnd1; else tPotong = rnd1; flag2 = rnd2; end; if (tPotong + flag2) >= JumGen; flag2 = JumGen - tPotong; end; end; end;
4. Mutasi Metode mutasi dalam pengujian ini adalah Swap Mutation. Metode ini akan memilih gen secara acak, selanjutnya gen akan dilakukan penukaran Parent :
Offspring :
8
7
4
5
3
9
8
2
8
2
4
5
3
9
8
7
Gambar 3.10 Ilustrasi Metode Penukaran Berikut merupakan prosedur mutasi yang digunakan. for i = 1 : UkPop; cc = (rand); if cc < pM
47 rnd1 = int8((rand*JumGen)); rnd2 = int8((rand*JumGen)) while rnd2 == rnd1 rnd2 = int8((rand*JumGen)); end; if rnd1 == 0; rnd1 = 1; end; if rnd2 == 0; rnd2 = 1; end; if (Populasi(i,rnd1)) == (Populasi(i,rnd2)) if ((rnd1)-1) <= 1 rnd2 = rnd1+1; else rnd2 = rnd1-1; end; end; end;
5. Evaluasi (Strategi Penalti)
Pada
proses evaluasi dilakukan pemilihan. Meskipun kromosom awal
dibangkitkan pada ruang solusi yang layak, namun setelah melewati proses mutasi dan crossover ada kemungkinan kromosom tersebut menjadi tidak layak. Oleh karena itu, setiap kromosom yang diketahui required resource melebihi resource constraint maka akan dikalikan dengan nilai penalti (berupa bilangan pecahan). Berikut merupakan algoritma yang digunakan untuk membangkitkan nilai penalti.
for i = 1: length(tempPop(:,1)); BatasL = cek_layak(RK,nItem,Limit); Profit = (sum (RK(:,1,1))); if BatasL == 0; penalti = 1; else penalti = 0.0001; end; Profit = fix(Profit * penalti); popProfit2(i) = Profit; BatasL = 0; end;
48 6. Local Search Algoritma yang dipakai pada LS adalah sebagai berikut for i = 1 : elit; for j = 1 : JumGen; rnd1 = fix (nItem*rand+1); while rnd1 == PopLocal(i,j); rnd1 = fix (nItem*rand+1); end; PopLocal(i,:) = Populasi(i,:); PopLocal (i,j) = rnd1; RK = generateRK (i,JumGen,kk,PopLocal); BatasL = cek_layak(RK,nItem,Limit); if BatasL == 0; Profit2 = (sum (RK(:,1,1))); if Profit2 >= Profit; Profit = Profit2 ; GenLocal = PopLocal(i,:); end; else Profit2 = 0; PopLocal(i,:) = 0; end; end; end;
3.3.4 Pengujian
Tahap pengujian menggunakan benchmark test problem. Setiap test problem memiliki beberapa tipe data dengan jumlah data yang berbeda-beda. Data yang digunakan berupa data value, resource constraint dan required resource yang berasal dari website http://cermsem.univ-paris1.fr/pub/CERMSEM/hifi/MMKP/ dari Universitas Perugia. Tabel 3.2 Dataset mmKP Dataset I01 I02 I03 I04 I05 I06 I07
Jumlah Objek
Jumlah RK 5 5 10 10 10 10 10
5 5 10 10 10 10 10
Mosers
Heuristik
151 291 1464 3375 3905.7 4115.2 23556
167 354 1533 3437 3899.1 4799.3 23912
Upper Bound 182.71 365.8 1626.59 3631.6 3905.9 4812.82 24607.95
Exact 173 364 1602 3597 3905.7 4799.3 23912
49 Dataset I08 I09 I10 I11 I12 I13
Jumlah Objek
Jumlah RK 10 10 10 10 10 10
10 10 10 10 10 10
Mosers
Heuristik
35373 47205 58648 70532 82377 94166
35979 47901 59811 71760 84141 96003
Upper Bound 36904.41 49193.87 61486.3 73797.74 86100.45 98448.64
Exact 35979 47901 59811 71760 84141 96003
BAB V KESIMPULAN
5.1. Kesimpulan
Dari hasil percobaan dan pembahasan yang telah dilakukan maka dapat ditarik kesimpulan sebagai berikut: 1. Metode Algoritma Genetika (Genetic Algorithm / GA) optimal pada data I01, namun pada data I02 s.d I13 kurang optimal dibandingkan metode lainnya. 2. Metode GA ketika ditambahkan metode Pencarian Lokal (Local Search / phGA) memiliki hasil yang lebih baik dibandingkan dengan hanya menggunakan metode GA. 3. Metode phGA pada data berukuran kecil lebih baik dibandingkan dengan metode Mosers, Heuristik, dan KLMA, namun pada data berukuran besar kurang optimal.
5.2. Saran
Untuk penelitian selanjutnya, GA dapat diimplementasikan pada berbagai tipe Knapsack Problem yang lain. Misalnya, bounded Knapsack Problem atau Multiple Knapsack Problem dengan penanganan kendala yang lainnya yaitu strategi penolakan kromosom (Rejecting Strategy). Serta membandingkan hasil penelitian tersebut dengan penelitian yang telah dilakukan. Penelitian selanjutnya juga disarankan untuk membandingkan ketiga penanangan kendala yaitu, strategi penalti, strategi perbaikan
61 kromosom dan strategi penolakan kromosom dengan studi kasus Knapsack problem pada data yang lebih besar.
DAFTAR PUSTAKA
Akbar,Md. M., Rahman, M. S., Kaykobad, M., Maning, E. G., dan Shoja, G. C., Solving the Multidimensional Multiple-choice Knapsack Problem by constructing convex hulls, Elsevier, 2004
Broto, A.S., Perancangan Dan Implementasi Sistem Pakar Untuk Analisa Penyakit Dalam, Jurusan Teknik Elektro, Fakultas Teknik, Universitas Diponegoro, 2010
Dake.2007.Knapsack problem diambil dari Knapsack_problem#/media/File:Knapsack.svg
http://en.wikipedia.org/wiki/
Dimitris, B., dan Ramazan, B., An Approximate Dynamic Programming Approach to Multidimensional Knapsack Problems, Management Science 2002 INFORMS, Vol. 48, No. 4, 2002
Dwiastuti, A., Evaluasi Kinerja Genetic Algorithm (GA) dengan Strategi Perbaikan Kromosom: Studi Kasus Knapsack Problem, Jurusan Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Lampung, 2015
Ertel, W. Introduction to Artificial Intelligence. London: Springer, 2011.
Gen, M. dan Cheng, R., Genetic Algorithms and Engineering Optimization, Canada, John Wiley & Sons, Inc., 2000.
Guler, A., dan Fidan, N., Algorithms With Guarantee Value for Bounded Knapsack Problems, International Conference 24th Mini EURO Conference “Continuous Optimization and Information-Based Technologies in the Financial Sector” , 2010
Hadi, I. S., Penerapan Algoritma Genetika Hybrid pada Permasalahan Bounded Knapsack, Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Jember, 2015
Hermawan, L dan Bendi, R.K, Penerapan Algoritma A* pada Aplikasi Puzzle, Seminar Nasional Teknologi Informasi dan Komunikasi, 2013
Hifi, M., Michrafy, M., dan Sbihi, A., Algorithms for the Multiple-Choice MultiDimensionalKnapsack Problem, LaRIA, Laboratoire de Recherche en Informatique d’Amie ns, 5 rue du Moulin Neuf, 80000 Amiens,France, 2005
Kartika, M. A., Pencocokan Kata Secara Acak dengan Metode Algoritma Genetika Menggunakan Program Pascal, Jurnal Matematika UNAND Vol. 2 No. 2, 2013
Kosasi, S., Penyelesaian Bounded Knapsack Problem Menggunakan Dynamic Programming (Studi Kasus: CV. Mulia Abadi), Jurnal Informatika Mulawarman, Vol 8, 2013
Kusumadewi, S. Artificial Intelligence (Teknik dan Aplikasinya). Yogyakarta: Graha Ilmu, 2003
Kw, K. D., Mardhiah, F., dan Charly,S., Penyelesaian Knapsack Problem Menggunakan Algoritma Genetika, Seminar Nasional Informatika, 2010
Luke, S., Essentials Of Metaheuristi, 2015
Malinda, R., Implementasi Genetic Algorithm Berbasis Strategi Penalti pada Knapsack Problem, Jurusan Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Lampung, 2015
Martello, S. dan Toth, P., Knapsack Problems Algorithms and Computer Implementations, England, John Wiley & Sons, 1990 Mutakhiroh,i., Fajar,S., Nur,H., dan Romi ,W., Pemanfaatan Metode Heuristik dalam Pencarian Jalur Terpendek dengan Algoritma Semut Dan Algoritma Genetika, Seminar Nasional Aplikasi Teknologi Informasi, 2007
Nugraha, I., Algoritma Genetik untuk Optimasi Penjadwalan Kegiatan Belajar Mengajar, Institut Teknologi Bandung, 2008
Prabowo, A. D, Ema. R, dan Untari, N. W., Implementasi Knapsack Problem Menggunakan Metode Dynamic Programming pada Pemilihan Menu Makan Berdasarkan Harga, Teknik Informatika, Fakultas Teknik Informatika, Universitas Telkom, 2013
Purnomo, H.D., Cara Mudah Belajar Metode Optimasi Metaheuristik Menggunakan Matlab. Yogyakarta: Gava Media, 2014.
Purwadi,J dan Istiyanto, J. E., Pemrograman Interaktif Sipp : Program Informasi Pengaturan dan Penjadwalan Parkir Berbasis Cerdas, Seminar Nasional Ilmu Komputer & Teknologi Informasi Universitas Kristen Satya Wacana, 2005
Rahman, K. M dan Syed,i. A., Performance Analysis of Genetic Algorithm for Solving the Multiple-Choice Multi-Dimensional Knapsack Problem, International Journal of Recent Trends in Engineering, Vol 2, 2009
Rahmanti, F. Z., Algoritma Pencarian Heuristic, Universitas Dian Nuswantoro, 2016
Sadid, M. D. H, Rabiul, I., dan Kamrul, H., A New Strategy for Solving MultipleChoice Multiple-Dimension Knapsack Problem in PRAM Model, Department of Computer Science & Engineering, Rajshahi University of Engineering & Technology, Bangladesh, 2005
Sbihi, A. D., Mustapha, M., dan Hifi, M., A Reactive Local Search-Based Algorithm for the Multiple-Choice Multi-Dimensional Knapsack Problem, Computational Optimization and Applications, 2005
Setemen, K., Implementasi Algoritma Genetika Pada Knapsack Problem Untuk Optimasi Pemilihan Buah Kemasan Kotak, Seminar Nasional Aplikasi Teknologi Informasi ,2010
Sulistiyorini , R dan Wayan, F. M., Penerapan Algoritma Genetika Untuk Permasalahan Optimasi Distribusi Barang Dua Tahap, Repository Jurnal Mahasiswa Ptiik Universitas Brawijaya, Vol. 5, No. 12, 2015
Syarif, A., Algoritma Genetika; Teori dan Aplikasi Edisi 2, Yogyakarta, Graha Ilmu, 2014
Talbi, E., Metaheuristics from Design to Implementation, New Jersey , John Wiley & Sons, Inc, 2009
Varnamkhasti, M. J., Overview Of The Algorithms For Solving The Multidimensional Knapsack Problems, Advanced Studies In Biology, Vol. 4, 2012
Volna, E., Introduction To Soft Computing, Czech Republic, 2013
Widodo,A. W., dan Wayan, F. M., Penerapan Algoritma Genetika pada Sistem Rekomendasi Wisata Kuliner, Jurnal Ilmiah KURSOR Vol. 5, No. 4, 2010
Widyastuti,W., dan Amir, H., Penggunaan Algoritma Genetika dalam Peningkatan Kinerja Fuzzy Clustering untuk Pengenalan Pola, Berkala MIPA, 17(2), 2007
Yeniay, Özgür., Penalty Function Methods For Constrained Optimization With Genetic Algorithms, Mathematical and Computational Applications, Vol. 10, 2005
Zennaki, M.,, A New Hybrid Algorithm for the Multiple-Choice Multi-Dimensional Knapsack Problem, Wseas Transactions on Information Science and Applications, 2013 Zukhri, Z., Algoritma Genetika : Metode Komputasi Evolusioner Menyelesaikan Masalah Optimasi, Yogyakarta, Andi Offset, 2014.
untuk
