## Penerapan Algoritma Genetika Untuk Optimasi Pembelian Sembako Sebagai Solusi Dari Knapsack Problem
Fachry Asy’ari Program Studi Teknik Informatika Jurusan Teknologi Informasi Politeknik Negeri Jember Jember, Indonesia
fcry1997@gmail.com
Al Faris Cahya Pratama Program Studi Teknik Informatika Jurusan Teknologi Informasi
Politeknik Negeri Jember Jember, Indonesia Trismayanti Dwi Puspitasari Program Studi Teknik Informatika Jurusan Teknologi Informasi
Politeknik Negeri Jember Jember, Indonesia trismayantidwipuspitasari@gmail.com
Avinda Renaldi Alamsyah Program Studi Teknik Informatika Jurusan Teknologi Informasi Politeknik Negeri Jember Jember, Indonesia
Dian Pusparini Program Studi Teknik Informatika
Jurusan Teknologi Informasi
Politeknik Negeri Jember
Jember, Indonesia Cahya Affrillah Prasetyo Program Studi Teknik Informatika Jurusan Teknologi Informasi Politeknik Negeri Jember Jember, Indonesia Najmi Nurus Shofi Program Studi Teknik Informatika Jurusan Teknologi Informasi
Politeknik Negeri Jember Jember, Indonesia
Abstract—  Knapsack  Problems  are  everyday  problems related  to  optimization  in  elections,  one  example  is  the Purchase  of  Grocery.  Groceries  purchase  is  a  process  of selecting  the  optimization  of  goods  according  to  the  needs  of the  buyer  so  that  the  goods  obtained  can  be  maximized  by taking into account the costs owned. For this optimization, this research  uses  Genetic  Algorithms.  Genetic  Algorithm  is considered  optimal in cases  related  to  the total  price  of goods, making  it  suitable  for  the  selection  of  nine-basic  necessities with  different  prices  and  brands.  The  algorithm  in  this research  is  carried  out  by  determining  the  initial  population containing  randomly  selected  individuals,  then  by  the  process of  selection  and  evolution,  a  new  population  is  found  that matches the desired results at the start, which is in accordance with the costs they have. In this study, the results of an increase in  fitness  from  generation  1  to  generation  2.  This  shows  that the  second  generation  produces  individuals  who  are  better than the first generation.
Keywords— Genetic Algorithm; Knapsack Problem;

## Optimization of goods
Abstrak— Knapsack Problem adalah permasalahan sehari- hari yang berhubungan dengan optimasi pada pemilihan ,salah satu  contohnya  adalah  Pembelian  Sembako.  Pembelian Sembako  merupakan  sebuah  proses  pemilihan  optimasi barang  sesuai  dengan  kebutuhan  pembeli  agar  barang  yang diperoleh  dapat maksimal  dengan  memperhatikan  biaya  yang dimiliki.  Untuk  optimasi  tersebut  maka  penelitian  ini menggunakan Algoritma Genetika. Algoritma Genetika dinilai optimal  dalam  kasus  yang  berkaitan  dengan  total  harga barang,  sehingga  cocok  untuk  pemilihan  sembako  yang berbeda harga dan merk. Algoritma di penelitian ini dilakukan dengan penentuan  populasi  awal yang  berisi  individu-individu yang dipilih secara acak ,yang kemudian dengan proses seleksi dan evolusi didapatkan populasi baru yang sesuai dengan hasil yang  diinginkan  di  awal  yaitu  sesuai  dengan  biaya  yang dimiliki.  Dalam penelitian  ini didapatkan  hasil  kenaikan  pada fitness  dari  generasi  1  ke  generasi  2.  Hal  ini  menunjukkan
bahwa  generasi  kedua  menghasilkan  individu-individu  yang lebih baik daripada generasi pertama.
Keywords—  Algoritma  Genetika;  Knapsack  Problem; Optimasi Barang

## PENDAHULUAN
Knapsack Problem merupakan permasalahan yang sering muncul dalam  kehidupan  sehari-hari,  sehingga persoalan  ini sangat  menarik  untuk  diteliti  karena  mudah  untuk diimplementasikan pada kehidupan nyata. Knapsack problem sendiri  adalah  sebuah  permasalahan  dimana  seseorang dihadapkan  pada  permasalahan  optimasi  pada  pemilihan benda  yang  dapat  dimasukkan  ke  dalam  wadah  yang memiliki  keterbatasan  ruang  atau  daya  tampung,  contohnya adalah pembelian sembako.
Secara  tidak  langsung,  pembelian  sembako  merupakan sebuah  contoh  proses  pemilihan  optimasi  barang  dalam kehidupan  sehari-hari.  Permasalahan  yang  biasanya  muncul adalah bagaimana pembeli dapat memaksimalkan pembelian dengan  biaya  yang  terbatas  dan  terpenuhinya  barang  yang memiliki prioritas tinggi. Untuk optimalisasi proses tersebut, maka  hal  hal  yang  perlu  diperhatikan  adalah  berat  tiap barang, harga dan juga uang yang dimiliki oleh konsumen. Penerapan  Algoritma  Genetika  untuk  memberikan  solusi pada Knapsack Problem sudah pernah dilakukan sebelumnya.  Beberapa  diantanya  yaitu  implementasi algoritma  genetika  pada  optimasi  pemilihan  buah  kemasan kotak yang menjelaskan tentang optimasi dari item item yang dapat  dipilih  untuk  dimasukkan  ke  dalam  Knapsack  tanpa melewati kapasitas yang ada [3]. Penelitian lain menjelaskan perbandingan antara algoritma genetika dan algoritma greedy di  dalam  penyelesaian  permasalahan  Knapsack  problem. Dari  penelitian  tersebut  didapatkan  sebuah  kesimpulan bahwa  baik  algoritma  genetika  dan  algoritma  greedy  sama- sama  dapat  menyelesaikan  Knapsack  problem.  Akan  tetapi algoritma genetika lebih optimal dalam kasus dengan jumlah
harga  barang.  Sedangkan  algoritma  greedy  unggul  dalam kompleksitas waktu pencarian solusi [1]
Knapsack  adalah  tas  atau  karung.  Karung  digunakan untuk  memuat  sesuatu.  Dan  tentunya  tidak  semua  objek dapat  ditampung  di  dalam  karung  tersebut.  Karung  tersebut hanya  dapat  menyimpan  beberapa  objek  dengan  total ukurannya  (weight)  lebih  kecil  atau  sama  dengan  ukuran kapasitas karung [2].
Algoritma  genetika  adalah  algoritma  pencarian  yang didasarkan  atas  mekanisme  dari  seleksi  alam  yang  lebih dikenal  dengan  proses  evolusi.  Dalam  proses  evolusi, individu  secara  terus  menerus  mengalami  perubahan  gen untuk  menyesuaikan  dengan  lingkungan  hidupnya.  Hanya individu-individu  yang  kuat  yang  mampu  bertahan.  Proses seleksi  alamiah  ini  melibatkan  perubahan  gen  yang  terjadi pada individu melalui proses perkembang-biakan. Algoritma genetika  mampu  menghasilkan  solusilebih  dari  satu,  hal  ini disebabkan  karena  selama  prosesnya,  algoritma  genetika menghasilkan  solusi  optimasi  kombinatorial  yang  mirip solusi  optimalnya.  Peningkatan  jumlah  populasi  akan memberikan  ruang  solusi  yang  semakin  banyak,  sehingga solusi optimal yang ditemukan juga semakin sempurna. oleh sebab  itu  dapat  dikatakan  bahwa  semakin  besar  jumlah populasi maka  akan memberikan nilai  fitness  yang  semakin tinggi [4].
Secara  umum,  dalam  algoritma  genetika  terdapat  5 (lima) proses, yaitu: pembentukan populasi awal, perhitungan  nilai  fitness,  seleksi,  regenerasi  (crossover  dan mutasi),  penciptaan  populasi  baru  hasil  regenerasi.  Proses rekombinasi  atau  yang  lebih  dikenal  dengan  nama  proses crossover  adalah  menyilangkan  dua  kromosom  sehingga membentuk kromosom baru yang harapannya lebih baik dari pada induknya. Tidak semua kromosom pada suatu populasi akan  mengalami  proses  rekombinasi.  Kemungkinan  suatu kromosom  mengalami  proses  rekombinasi  didasarkan  pada probabilitas crossover yang telah ditentukan terlebih dahulu. Probabilitas crossover menyatakan peluang suatu kromosom akan mengalami crossover. Ada beberapa teknik rekombinasi  yang  dapat  digunakan  untuk  menyelesaikan Traveling  Salesman  Problem,  antara  lain  adalah  partially mapped  crossover  (PMX),  order  crossover  dan  cycle crossover [6].
Fokus  utama  pada  penelitian  ini  adalah  implementasi algoritma  genetika  untuk  optimasi  pemilihan  sembako sebagai  salah  satu  kasus  dalam  Knapsack  problem.  Dengan penelitian  ini,  diharapkan  dapat  dikembangkannya  sebuah system  yang  memudahkan  konsumen  di  dalam  optimasi barang dari harga yang dimiliki.

## METODE PENELITIAN
Cara  kerja  program  secara  garis  besar  adalah mencari  total  harga  yang  tidak  melebihi  batas  uang maksimal.  Pencariannya  menggunakan  algoritma  genetika. Berikut adalah gambar blok diagram sistem.
Gambar 1. Alur kerja sistem 1. Representasi Kromosom Dalam  kasus Knapsack  problem ,  gen  dari  kromosom direpresentasikan  dalam  bentuk  angka.  Caranya  dengan memilih  nomor  dari  masing  -  masing  jenis  yang  kemudian dijadikan  gen  untuk  kromosom  secara  berurutan.  Dengan demikian  panjang  dari  kromosom  nanti  adalah  9  digit (sejumlah jenis barang).
Data  barang  yang  nantinya  akan  dicari  kombinasinya berdasarkan algoritma genetika adalah sebagai berikut :
TABEL I DAFTAR TELUR AYAM No Merek Berat Harga 1 Sajira Farm Telur Ayam Negeri [30 butir] 3 kg 73.750 2 Sajira Telur  3 kg 91.000
Ayam Kampung [30 butir] 3 Duta Buah Pusat Telur Ayam Negeri [17 butir] 1,5 kg 26.500 4 Duta Buah Telur Ayam Kampung Merah [10 butir] 1 kg 30.000 5 Sajira Farm Telur Ayam Negeri [10 butir]
1 kg 47.000
TABEL II DAFTAR SUSU KENTAL MANIS No Merek Berat Harga 1 Fisian Flag Susu Kental Manis Kaleng 0,370 kg 9.900 2 Frisian Flag Susu kental Manis  -  Gold Kaleng 0,370 kg 14.100 3 Frisian Flag Susu Kental Manis Pouch 0,560 kg 14.500 4 Cap Enaak Susu Kental Manis Kaleng 0,370 kg 9.200 5 Indomilk  Plain Susu Kental Manis Kaleng [3 pcs] 1,110 kg 36.000
TABEL III DAFTAR JAGUNG No Merek Berat Harga 1 Qooali  Jagung Manis 0,650 kg 9.500 2 Qooali  Jagung Manis Besar 1,500 kg 20.000 3 FreshBox Jagung Manis Kupas 1 kg 14.500 4 Alif Cooperation Jagung Manis 0,500 kg 7.000 5 Alif Cooperation Jagung Acar 0,250 kg 8.000 TABEL IV DAFTAR MIE No Merek Berat Harga 1 Indomie Mie Goreng  Special [40 pcs] 3,4 kg 99.500
2 Indomie Mie Kari  Ayam  [40 pcs] 2,88 kg 93.000 3 Indomie Mie Goreng Special 0,085 kg 2.850 4 Indomie Mie Goreng  Special [10 pcs] 0,85 kg 25.900 5 Indomie Rasa Soto [5 pcs] 0,375 kg 11.500 TABEL V DAFTAR BERAS No Merek Berat Harga 1 Topi Kaki 5 kg 64.000 2 Fortune 5 kg 60.000 3 Rojo Lele 5 kg 60.500 4 Sania 2,5 kg 35.000 5 Beras Coklat Keep Me First 2,5 kg 85.000 6 Sumo 10 kg 128.000 TABEL VI DAFTAR GULA No Merek Berat Harga 1 Gulaku Premium 1 kg 13.000 2 Fs Gula Pasir 1 kg 12.600 3 Rose Brand 1 kg 12.000 4 Matahari  Merah Premium 1  kg 11.500 5 Gulaku Tebu 0,5 kg 7.000 6 Tropicana Slim 0,25 kg 74.000 7 Manise 0,5 kg 6.900 TABEL VII DAFTAR MINYAK GORENG No Merek Berat Harga 1 Bimoli [1 pcs] 2 L 24.500 2 Rose  Brand  [1 pcs] 2 L 20.900 3 Tropica [1 pcs] 2 L 26.000 4 Tropica [6 pcs] 2 L 137.000 5 Fortune [1 pcs] 2 L 25.000 6 Sania [1 pcs] 2 L 21.900 7 Filma [1 pcs] 2 L 30.000 8 Filma [6 pcs] 2 L 126.000 TABEL VIII DAFTAR GARAM No Merek Berat Harga 1 Garena [1 pcs] 1  kg 15.000 2 Dolpin  [1 pcs] 1 kg 12.000 3 Real Salt Kosher [1 pcs] 0,454 kg 160.000 4 Redmond  Real Salt [1 pcs] 0,454 kg 190.000 5 Real  Salt  Fine  0,454 kg 154.000
[1pcs] TABEL IX DAFTAR DAGING AYAM No Bagian Berat Harga 1 Sayap 1 kg 32.000 2 Paha 1 kg 38.000 3 Ayam Karkas 0,8 kg 42.000 4 Kulit 1 kg 29.000 5 Ceker 1 kg 27.000 6 Dada 1 kg 42.500

## 2. Fungsi Fitness
Setiap  kromosom  dievaluasi  berdasarkan  fungsi tertentu  sebagai  nilai  fitness.  Dalam Knapsack problem, untuk  mencari  nilai  fitness  yakni  dengan  menemukan  total harga  dari  semua  barang  terpilih  kurang  dari  atau  sama dengan  batas  harga  yang  telah  ditentukan.  Sehingga  fungsi nilai fitness adalah
keterangan : h k = harga barang ke k hMax = uang maksimal

## 3. Seleksi
Untuk  melakukan  proses  seleksi  pada  masalah Knapsack problem,  digunakan  metode  seleksi  berdasarkan roulette whee l. Langkah - langkah penyelesaiannya adalah
a. Hitung  probabilitas  fitness  dari  masing  -  masing kromosom
keterangan : p i = probabilitas fitness ke i f i = fitness ke i ft = total fitness
b. Hitung  fitness  kumulatif  untuk  masing  -  masing kromosom dari probabilitas
keterangan : p i = probabilitas fitness ke i fk = fitness kumulatif
c. Melakukan  proses  pemutaran  roulette  wheel sebanyak  total  populasi.  Angka  yang  didapatkan kemudian dijadikan acuan untuk memilih kromosom baru.
4. Crossover Crossover
dilakukan dua kromosom untuk menghasilkan  kromosom  anak  , crossover dalam  kasus  ini menggunakan one  point  crossover . one  point  crossover adalah  metode crossover dalam  genetika  algoritma  dengan
cara  membagi  dua  ruas  bagian  kiri  dan  kanan,  kemudian dapat  memilih  bagian  kanan  atau  kiri  yang  akan  di- crossover .

## 5. Mutasi
Mutasi  adalah  salah  satu  proses  untuk  merubah  secara acak nilai dari suatu gen pada posisi yang dipilih. Perubahan nilai  pada  permasalahan  ini  yaitu  dengan  mengacak  nilai sesuai  batas  angka  dari  tipe  masing  -  masing  jenis.  Untuk menentukan gen yang akan dimutasi adalah sebagai berikut :
a. Menghitung  jumlah  gen  dari  kromosom  dikali populasi.
keterangan : tGen = total gen seluruh populasi jGen = total gen dalam 1 kromosom po = total kromosom dalam populasi
b. Menentukan  persentase  peluang  mutasi  yang kemudian  dikali  dengan  total  gen  yang  telah dihitung  sebelumnya.  Hasilnya  adalah  jumlah  gen yang akan dimutasi.
keterangan : mGen = jumlah gen yang dimutasi pm = peluang mutasi
HASIL DAN PEMBAHASAN Hasil  penerapan  dari  metode  yang  dijelaskan  sebelumnya pada sebuah permasalahan adalah sebagai berikut :
1. Menentukan Populasi Awal
Untuk  batas  uang  yang  ditentukan  dalam  permasalahan  ini adalah  Rp.  350,000,-.  Kemudian  untuk  populasi  awal  yang dibangkitkan sesuai dengan representasi kromosom adalah
TABEL X STRUKTUR KROMOSOM POPULASI AWAL
Be ras G u l a Min yak Gor eng
Dag ing Aya m Telur Ayam Susu Kental Manis Jag ung Mie Gara m K1 5 5 3 5 5 3 4 5 2 K2 3 1 1 6 1 3 2 1 2 K3 6 1 3 1 2 2 1 2 1 K4 1 3 2 1 1 1 3 3 3 K5 4 7 1 2 3 1 1 4 4

## 2. Fungsi Fitness
Nilai  hMax  didapat  dari  batas  uang  yang  ditentukan sebelumnya  sebesar  Rp  350,000,-.  Sehingga  didapatkan nilai  fitness  untuk  masing  -  masing  kromosom  sesuai dengan rumus yang telah ditentukan sebagai berikut :
TABEL XI NILAI FITNESS TIAP KROMOSOM POPULASI AWAL
No Kromosom Total Berat Total Harga Fitness 1 K1 kg 237.000 237.000 2 K2 kg 360.250 10.250 3 K3 kg 421.600 71.600 4 K4 kg 389.900 39.900 5 K5 kg 366.200 16.200
3. Seleksi
Nilai  hMax  didapat  dari  batas  uang  yang  ditentukan sebelumnya  sebesar  Rp  350,000,-.  Sehingga  didapatkan
nilai  fitness  untuk  masing  -  masing  kromosom  sesuai dengan rumus yang telah ditentukan sebagai berikut :
TABEL XII

## FITNESS KUMULATIF TIAP KROMOSOM POPULASI
AWAL
N o Kro moso m
Total Harga Fitness Probabilitas Fitness
Fitness Kumulatif 1 K1 237.000 237.000 0,632 0,632 2 K2 360.250 10.250 0,027 0,659 3 K3 421.600 71.600 0,191 0,850 4 K4 389.900 39.900 0,106 0,956 5 K5 366.200 16.200 0,043 1
Lalu  dilakukan  proses roulette  wheel sebanyak  5  kali,  dan dihasilkan bilangan sebagai berikut :
TABEL XIII HASIL DARI ROULETTE WHEEL UNTUK SELEKSI POPULASI
AWAL
No Bilangan Acak 1 0,235 2 0,317 3 0,789 4 0,697 5 0,812
Sehingga  didapatkan  kromosom  baru  dari  proses  seleksi kromosom awal yaitu :
TABEL XIV HASIL KROMOSOM TERPILIH DARI ROULETTE WHEEL No Kromoso m Fitness Probabilitas Fitness Asal 1 K1 237.000  0,632 K1 2 K2 237.000  0,632 K1 3 K3 71.600 0,191 K3 4 K4 71.600 0,191 K3 5 K5 71.600 0,191 K3
4. Crossover
Untuk  permasalahan  ini,  peluang crossover yang diharapkan  adalah  40%  dari  total  kromosom.  Sehingga kromosom  yang  mengalami crossover adalah  40%  *  5  =  2 kromosom.
TABEL XV HASIL DARI ROULETTE WHEEL UNTUK CROSSOVER No Bilangan Acak 1 0,671 2 0,172 3 0,222 4 0,593 5 0,315
Pilih  bilangan  -  bilangan  acak  yang  kurang  dari peluang crossover ,  maka  kromosom  yang  sesuai  dengan urutan  bilangan  terpilih  tadi  yang  akan  di- crossover . Sehingga bilangan yang akan di- crossover adalah TABEL XVI KROMOSOM YANG AKAN DI- CROSSOVER No Kromosom Fitness Probabilitas Fitness Asal 2 K2 237.000 0,632 K1 3 K3 71.600 0,191 K3
Karena  kita  menggunakan  one-point crossover , maka crossover untuk kromosom 2 dan 3 adalah :
TABEL XVII KROMOSOM YANG AKAN DI- CROSSOVER
Be ras G u l a Min yak
Gor eng Dag ing Aya m Telur Ayam Susu Kental Manis Jag ung Mie Gara m K2 3 1 1 6 1 3 2 1 2 K3 6 1 3 1 2 2 1 2 1
Maka  dihasilkan  anak  dari  hasil crossover di  atas  sebagai berikut :

## TABEL  XVIII
HASIL DARI PROSES CROSSOVER
Be ras G u l a Min yak Gor eng
Dag ing
Aya m Telur Ayam Susu Kental Manis Jag ung Mie Gara m
K2 3 1 1 1 2 2 1 2 1
K3 6 1 3 6 1 3 2 1 2

## 5. Mutasi
Sehingga  untuk  melakukan mutasi pada  permasalahan diatas adalah 9 * 5 = 45, lalu 20% * 45 = 9. Didapatkan nilai sebagai berikut :
TABEL XIX BILANGAN ACAK KROMOSOM 1 No Bilangan Acak No Bilangan Acak 1 0,3 6 0,4 2 0,41 7 0,19 3 0,55 8 0,56 4 0,001 9 0,72 5 0,3
TABEL XX
BILANGAN ACAK KROMOSOM 2 No Bilangan Acak No Bilangan Acak 1 0,49 6 0,13 2 0,56 7 0,24 3 0,61 8 0,16 4 0,72 9 0,14 5 0,29 TABEL XXI
BILANGAN ACAK KROMOSOM 3 No Bilangan Acak No Bilangan Acak 1 0,65 6 0,17 2 0,59 7 0,51 3 0,28 8 0,27 4 0,78 9 0,26 5 0,21
TABEL XXII BILANGAN ACAK KROMOSOM 4
No Bilangan Acak No Bilangan Acak 1 0,29 6 0,73 2 0,27 7 0,28 3 0,02 8 0,31 4 0,81
9 0,62 5 0,15 TABEL XXIII
BILANGAN ACAK KROMOSOM 5 No Bilangan Acak No Bilangan Acak 1 0,34 6 0,35 2 0,43 7 0,31 3 0,41 8 0,67 4 0,12 9 0,65
5 0,59
Sehingga  hasil  dari roulette  wheel untuk  masing  masing kromosom terpilih gen sebagai berikut :
TABEL XXIV GEN YANG TERPILIH Kromosom Gen ke Kromosom Gen ke 1 4 3 6 1 7 4 5 2 6
4 3
2 8 5 4
2 9
Dari  gen  yang  terpilih  pada  proses  sebelumnya kemudian  melakukan  acak  bilangan  sesuai  dengan  batas masing  -  masing  gen  sehingga  dapat  dihasilkan  populasi baru dengan kromosom sebagai berikut :
TABEL XXV

## HASIL MUTASI BERUPA POPULASI BARU
Be ras G u l a Min yak Gor eng Dag ing Aya m Telur Ayam Susu Kental Manis Jag ung Mie Gara m
K1 5 5 3 2 5 3 5 5 2 K2 3 1 1 1 2 3 1 2 2
K3 6 1 3 6 1 2 2 1 2 K4 6 1 2 1 3 2 1 3 1 K5 6 1 3 3 2 2 1 2 1

## 6. Mencari Solusi Optimal
Untuk  mencari  solusi  optimal  dari  populasi  baru yaitu dengan  cara  mencari  kembali  nilai  fitness  dari  masing  - masing  kromosom  pada  populasi  baru.  Sehingga  diketahui sebagai berikut :
TABEL XXVI NILAI FITNESS DARI SETIAP KROMOSOM POPULASI BARU No Kromosom Total Berat Total Harga Fitness 1 K1 kg 249.000 249.000 2 K2 kg 350.000 350.000 3 K3 kg 428.850 78.850 4 K4 kg 261.850 261.850 5 K5 kg 831.600 81.600 TABEL XXVII DAFTAR FITNESS SETIAP GENERASI Generasi ke Fitness Terbaik Fitness Terburuk Fitness Rata - rata 1 237.000 10.250 123.625 2 350.000 78.850 214.425
Dari  data  fitness  yang  telah  didapat,  kemudian  dijari nilai  fitness yang  sama  dengan hMax .  Sehingga  didapatkan kromosom K2 menjadi kombinasi yang sesuai dengan batas uang  yang  telah  ditentukan,  dengan  detail  barang  yang dibeli adalah :
1. Beras = Rojo lele
2. Gula = Gulaku Premium
3. Minyak Goreng = Bimoli [1 pcs]
4. Daging Ayam = Sayap
5. Telur  Ayam  =  Sajira  Telur  Ayam  Kampung  [30 butir]
6. Susu  Kental  Manis  =  Frisian  Flag  Susu  Kental Manis Pouch
7. Jagung = Qooali Jagung Manis Besar
8. Mie = Indomie Kari Ayam [40 pcs]
9. Garam = Dolpin [1 pcs]

## KESIMPULAN
Penentuan  statistik  tiap  generasi  didapatkan  dari  nilai maximum (fitness terbaik) tiap generasi dan nilai minimum (fitness  terburuk)  tiap  generasi.  Selain  dapat  digunakan untuk    optimasi  pembelian  sembako,    Algoritma  genetika memberikan  kemudahan  dalam  menentukan  kombinasi barang  terutama  pada  studi  kasus  Knapsack  problem  yaitu dengan  menggunakan  parameter  harga  dari  data  barang. Pada  penerapan  algoritma  genetika  terdapat  beberapa komponen  penting  yang  berperan  dalam  studi  kasus  ini meliputi kromosom, seleksi, crossover, dan mutasi. Dimana dari  beberapa  komponen  tersebut  dapat  melakukan  proses perhitungan  perolehan  hasil  kromosom  terbaik.  Dari  studi kasus yang diangkat dapat ditarik kesimpulan bahwa terjadi kenaikan  pada  nilai  fitness  dari  generasi  1  yaitu  dengan nominal  273.000  ke  generasi 2  dengan  nilai fitness  sebesar 350.000.  Selain  itu,  nilai  fitness  rata-rata  juga  mengalami kenaikan  dari  generasi  1  ke  2  yaitu  dari  nominal  123.625 naik ke 214.425.

## UCAPAN TERIMA KASIH
Terimakasih  kepada  Politeknik  Negeri  Jember  dan Dosen pengampu Mata Kuliah Sistem Cerdas.

## REFERENSI
[1] N.  Aima, Penerapan  Algoritma  Genetika  dan  Perbandingannya dengan  Algoritma  Greedy  dalam  Penyelesaian  Knapsack  Problem. Skripsi.  Universitas Islam Negeri Alauddin Makassar, 2017.
[2] D. Rachmawati & A.Candra, Implementasi Algoritma Greedy untuk Menyelesaikan
Masalah Knapsack Problem . 2013. Jurnal SAINTIKOM Vol. 12, No. 3.
[3] Setemen,  Komang.  Implementasi  Algoritma  Genetika  Pada Knapsack  Problem  Untuk  Optimasi  Pemilihan  Buah  Kemasan Kotak.  2010.  Seminar  Nasional  Aplikasi  Teknologi  Informasi  2010 (SNATI 2010) ISSN: 1907-5022, Yogyakarta.
[4] Fitri, Mega Orina. 2017. Optimasi Pengangkutan Peti Kemas Dalam Penyelesaian  Knapsack  Berdasarkan  Perbandingan  Algoritma Genetika Dan Algoritma Greedy. Jurnal INSTEK (Informatika Sains dan Teknologi), vol 2 no 2.
[5] K.Diah,  M.Fadhli  &  C.Sutanto,  “Penyelesaian Knapsack Problem Menggunakan  Algoritma  Genetika.  2010.  Seminar  Nasional Informatika (SEMNASIF), vol 1 no 4.
[6] S.Lukas,  T.Anwar  &  W.Yuliani  .  Penerapan  Algoritma  Genetika Untuk  Traveling  Salesman  Problem  Dengan  Menggunakan  Metode Order Crossover Dan  Insertion  Mutation.  2005.  Seminar  Nasional Aplikasi Teknologi Informasi (SNATI).
[7] L.Tambunan,  Implementasi  Algoritma  Genetika  dalam  Pembuatan Jadwal Kuliah,  2017. Jaringan Sistem Informasi Robotik (JSR), vol 1, no 1.
[8] IW.Supriana, Optimalisasi Penyelesaian Knapsack Problem Dengan Algoritma Genetika, 2016. Lontar Komputer (Jurnal Ilmiah Teknologi Informasi), vol 7 no 3.
[9] CWM Vermila, Analisis Karakteristik Konsumen
Yang Berbelanja Sembilan Bahan Pokok(Sembako) Di Pasar Tradisional Dan Pasar Moderen Di Kecamatan Marpoyan Damai Kota Pekanbaru. 2016. Jurnal Agribisnis, vol 18 no 2.
[10] (2019) The Pakarayam website [Online]. Tersedia:http//pakarayam.id/