Knapsack adalah tas atau karung yang digunakan untuk memasukkan sesuatu. Tapi tidak semua barang bisa ditampung ke dalam karung tersebut. Karung tersebut hanya dapat menyimpan beberapa objek dengan total ukurannya (weight) lebih kecil atau sama dengan ukuran kapasitas karung.
Knapsack problem merupakan masalah di mana orang dihadapkan pada persoalan optimasi pada pemilihan benda yang dapat dimasukkan ke dalam sebuah wadah yang memiliki keterbatasan ruang atau daya tampung. Dengan adanya optimasi dalam pemilihan benda yang akan dimasukkan ke dalam wadah tersebut diharapkan dapat menghasilkan keuntungan yang maksimum.
Benda-benda yang akan dimasukkan ini masing-masing memiliki berat dan sebuah nilai yang digunakan untuk menentukan prioritasnya dalam pemilihan tersebut. Nilainya dapat berupa tingkat kepentingan, harga barang, nilai sejarah, atau yang lainnya. Wadah yang dimaksud di sini juga memiliki nilai konstanta yang merupakan nilai pembatas untuk benda-benda yang akan dimasukkan ke dalam wadah tersebut sehingga harus diambil sebuah cara memasukkan benda-benda tersebut ke dalam wadah sehingga menghasilkan hasil optimum tetapi tidak melebihi kemampuan wadah untuk menampungnya.
Jenis-Jenis Knapsack Problem
Terdapat beberapa variasi Knapsack problem:
- 0/1 Knapsack problem
Setiap barang hanya tersedia 1 unit, take it or leave it.
- Fractional Knapsack problem
Barang boleh dibawa sebagian saja (unit dalam pecahan). Versi problem ini menjadi masuk akal apabila barang yang tersedia dapat dibagi-bagi misalnya gula, tepung, dan sebagainya.
- Bounded Knapsack problem
Setiap barang tersedia sebanyak N unit (jumlahnya terbatas).
- Unbounded Knapsack problem
Setiap barang tersedia lebih dari 1 unit, jumlahnya tidak terbatas
Berbagai Macam Stategi dalam Mengatasi Permasalahan Knapsack
a. Knapsack Problem
Masalah Knapsack merupakan sebuah persoalan yang menarik. Dalam dunia nyata permasalahan Knapsack ini sering sekali digunakan terutama pada bidang (jasa) pengangkutan barang (seperti pengangkutan peti kemas dalam sebuah kapal). Dalam usaha tersebut, diinginkan suatu keuntungan yang maksimal untuk mengangkut barang yang ada dengan tidak melebihi batas kapasitas yang ada. Berdasarkan persoalan tersebut, diharapkan ada suatu solusi yang secara otomatis dalam mengatasi persoalan itu. Problem Knapsack adalah permasalahan optimasi kombinatorial, dimana kita harus mencari solusi terbaik dari banyak kemungkinan yang dihasilkan.
b. Penyelesaian Knapsack
1. Brute Force
Brute force adalah pendekatan straightforward untuk menyelesaikan masalah, umumnya sangat bergantung pada pernyataan masalah dan definisi dari konsep.
Jika terdapat n item untuk dipilih, maka akan ada 2 kemungkinan kombinasi dari item-item tersebut untuk ditempatkan di Knapsack. Sebuah item dapat terpilih atau tidak dalam kombinasi tersebut. Angka 0 dan 1 akan dibangkitkan sepanjang n. Jika I menunjukkan 0 maka item tersebut tidak terpilih dan jika 1 maka item tersebut dipilih.
2. Algoritma Greedy
Teknik pemrograman dengan menggunakan Greedy sering digunakan untuk permasalahan optimasi. Secara umum teknik ini menggunakan heuristic untuk mencari solusi suboptimum sehingga diharapkan solusi optimum.
Pada Greedy Algorithm ada beberapa strategi yang digunakan untuk memilih objek yang akan dimasukkan ke dalam knapsack:
a. Greedy by profit
Pada setiap langkah, knapsack diisi dengan objek yang mempunyai keuntungan terbesar. Strategi ini mencoba memaksimumkan keuntungan dengan memilih objek yang paling menguntungkan terlebih dahulu. Pertama kali yang dilakukan adalah mengurutkan secara menurun objek-objek berdasarkan profit-nya.
Kemudian baru diambil satu-persatu objek yang dapat ditampung oleh knapsack sampai knapsack penuh atau sudah tidak ada objek lagi yang bisa dimasukkan.
b. Greedy by weight
Pada setiap langkah, knapsack diisi dengan objek yang mempunyai berat paling ringan. Strategi ini mencoba memaksimumkan keuntungan dengan memasukkan sebanyak mungkin objek ke dalam knapsack. Pertama kali yang dilakukan adalah mengurutkan secara menaik objek-objek berdasarkan weight-nya. Kemudian baru diambil satu-persatu objek yang dapat ditampung oleh knapsack sampai knapsack penuh atau sudah tidak ada objek lagi yang bisa dimasukkan.
c. Greedy by density
Pada setiap langkah, knapsack diisi dengan objek yang mempunyai densitas terbesar. Strategi ini mencoba memaksimumkan keuntungan dengan memilih objek yang mempunyai keuntungan per unit berat terbesar. Pertama kali yang dilakukan adalah mencari nilai profit per unit (density) dari tiap-tiap objek. Kemudian objek-objek tersebut diurutkan berdasarkan densitynya. Kemudian baru diambil satu-persatu objek yang dapat ditampung oleh knapsack sampai knapsack penuh atau sudah tidak ada objek lagi yang bisa dimasukkan.
Setelah tiga strategi tersebut diterapkan dan diuji, maka didapat hasil terbaik dating dari aturan ketiga, yaitu memilih item bernilai tinggi dari rasio bobot terhadap berat.
Pemilihan objek berdasarkan salah satu dari ketiga strategi di atas tidak menjamin akan memberikan solusi optimal. Berbeda dengan strategi brute force yang selalu dapat memberikan hasil yang optimal. Tetapi greedy mengurangi jumlah langkah (kompleksitas) pencarian.
3. Algoritma Genetika
Algoritma genetika adalah algoritma komputasi yang diinspirasi oleh teori evolusi yang kemudian diadopsi menjadi algoritma komputasi untuk mencari solusi suatu permasalahan dengan cara yang alamiah. Algoritma ini dikembangkan oleh Goldberg yang terinspirasi dari teori evolusi Darwin yang menyatakan bahwa kelangsungan hidup suatu makhluk dipengaruhi oleh aturan “yang kuat adalah yang menang”. Darwin juga mengatakan bahwa kelangsungan hidup suatu makhluk dapat dipertahankan melalui proses reduksi, crossover, dan mutasi.
Sebuah solusi yang dibangkitkan dalan Algoritma Genetika disebut sebagai kromosom, sedangkan kumpulan kromosom-kromosom tersebut disebut sebagai populasi. Sebuah kromosom dibentuk dari komponen-komponen penyusun yang disebuat sebagai gen dan nilainya dapat berupa bilangan numerik, biner, simbol atau pun karakter tergantung dari permasalahan yang ingin diselesaikan. Kromosom-kromosom tersebut akan berevolusi secara berkelanjutan yang disebut dengan generasi. Dalam tiap generasi, kromosom-kromosom tersebut dievaluasi tingkat keberhasilan nilai solusinya terhadap masalah yang ingin diselesaikan (fungsi_objektif) menggunakan ukuran yang disebut fitness.
Untuk memilih kromosom yang tetap dipertahankan untuk generasi selanjutnya, dilakukanlah proses seleksi. Kromosom dengan nilai fitness tinggi akan memiliki peluang lebih besar untuk terpilih lagi pada generasi selanjutnya.
Offspring merupakan kromosom-kromosom baru yang dibentuk dengan cara melakukan perkawinan antar kromosom dalam satu generasi, atau sering disebut sebagai proses crossover. Jumlah kromosom yang mengalami crossover ditentukan oleh parameter Pcrossover. Mekanisme perubahan susunan unsur penyusun makhluk hidup akibat adanya faktor alam disebut dengan mutasi. Jadi, mutasi direpresentasikan sebagai suatu proses berubahnya satu atau leih nilai gen dalam kromosom dengan suatu nilai acak. Jumlah gen dalam populasi yang mengalami mutasi ditentukan oleh parameter Pmutasi. Setelah beberapa generasi akan dihasilkan kromosom-kromosom yang nilai gennya konvergen ke suatu nilai tertentu yang merupakan solusi terbaik yang dihasilkan oleh Algoritma Genetika terhadap permasalahan yang ingin diselesaikan.
Algoritma Genetika sangat cocok untuk menyelesaikan masalah optimasi dengan ruang lingkup yang besar, karena Algoritma Genetika selalu bergerak dengan mencari sejumlah solusi sekaligus, selama solusi tersebut masih bersifat feasible (tidak melanggar constraint). Dengan seting parameter yang tepat, diharapkan salah satu dari sekian banyak solusi yang dibangkitkan oleh Algoritma Genetika merupakan solusi optimum global.
Akan tetapi, Algoritma Genetika ini juga masih memiliki kelemahan yaitu ketidakpastian untuk menghasilkan solusi optimum global, karena sebagian besar dari algoritma ini berhubungan dengan bilangan random yang bersifat probabilistik. Peranan programer disini adalah memaksimalkan probabilitas dalam menghasilkan solusi optimum global dengan cara membuat suatu skema pengolahan input argumen (fungsi fitness) dan setting parameter yang tepat.Algoritma genetik merupakan algoritma komputer yang mencari suatu solusi-solusi baik dalam permasalah yang memiliki sejumlah besar kemungkinan pemecahan yang ada. Semua algoritma-algoritma genetik dimulai dengan kumpulan solusi ( yang diwakili oleh kromosom) yang biasa disebut populasi. Suatu populasi baru diciptakan dari solusi-solusi yang ada dalam suatu populasi tua diharapan dapat menjadi suatu populasi lebih baik. Solusi-solusi yang telah dipilih dalam membentuk solusi baru (anak/offspings) akan diseleksi menurut fitness mereka. Semakin solusi-solusinya tersebut cocok maka akan lebih banyak kesempatan mereka dalam produksi kembali. Proses ini diulangi sampai kondisi yang diinginkan didapat.
Kebanyakan agoritma genetik berdasarkan atas element-elemen berikut: “populasi dari kromosom, pemilihan berdasarkan fitness, penyilangan dalam mendapatkan offspings baru, dan mutasi acak dalam offsprings baru”.
Penerapan algoritma genetika dalam knapsack:
Berikut adalah pengolahan fitness dan setting parameter yang kami terapkan :
> Representasi Barang
Kami merepresentasikan barang dalam dua array, dimana array pertama berisi weight (berat) barang, dan array kedua berisi profit (keuntungan) barang.
Weight :
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
180
|
170
|
100
|
190
|
270
|
120
|
190
|
140
|
180
|
100
|
140
|
70
|
150
|
120
|
190
|
140
|
80
|
150
|
200
|
130
|
Profit :
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
200
|
150
|
90
|
220
|
250
|
80
|
170
|
120
|
190
|
70
|
160
|
110
|
120
|
160
|
220
|
140
|
120
|
110
|
160
|
18
|
> Constraint
Adapun constraint yang kami gunakan dalam aplikasi ini adalah weight. Jadi,total berat dari sekumpulan barang yang dipilih tidak boleh melebihi kapasitas Knapsack.
Encoding Kromosom
Untuk merepresentasikan kromosom, kami menggunakan array 1 dimensi yang berisi 1 atau 0.
Misal :
Kromosom : 1 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 0 0
Arti : Barang 1, 4, 8, 9, 10, 12, 14, 16, 18 diambil
Barang 2, 3, 5, 6, 7, 11, 13, 15, 17, 19, 20 tidak diambil
> Termination Conditions
Pencarian solusi berhenti jika terdapat > 60% kromosom yang mempunyai nilai fitnes maksimum ATAU jumlah evolusi lebih besar limit evolusi yang telah ditentukan (jika jumlah evolusi > 1000).
> Fitness Function
Pada evolusi di dunia nyata, individu bernilai fitness tinggi akan bertahan hidup. Sedangkan individu bernilai fitnesss rendah akan mati. Pada AG, suatu individu dievaluasi berdasarkan suatu fungsi tertentu sebagai ukuran niali fitness-nya. Pada aplikasi ini, fitness dihitung dengan menjumlahkan profit tiap barang yang masuk ke dalam knapsack. Jika berat total dalam satu kromosom lebih besar daripada kapasitas maksimum knapsack, maka nilai fitnessnya diassign 0.
Selain dihitung nilai fitnessnya, dihitung pula berat total dari tiap kromosom untuk kemudian dilakukan pengecekan, dimana apabila ada kromosom yang berat totalnya melebihi kapasitas dari knapsack, maka akan dilakukan pencarian gen dalam kromosom tersebut yang bernilai 1 untuk diganti dengan nilai 0. Hal ini dilakukan terus menerus sampai dipastikan bahwa semua kromosom tidak ada yang melanggar constraint.
Untuk mencegah adanya individu yang dominan dalam suatu populasi (dalam pemilihan parent untuk dicrossover), maka diperlukan suatu fungsi Linier Fitness Ranking. Fungsi ini akan menurunkan perbedaan nilai fitness antar individu, sehingga perbedaan antara nilai fitness terbaik dengan nilai fitness terendah dapat diperkecil. Dengan begitu setiap kromosom memiliki kemungkinan untuk terpilih menjadi parent secara lebih merata (lebih adil).
> Selection Function
Aplikasi ini menggunakan metode seleksi Roulette Wheel yang dikombinasikan dengan Elitism. Roulette Wheel merupakan suatu metode pemilihan kromosom untuk dijadikan parent, dimana komosom dengan fitness tinggi mempunyai peluang lebih besar untuk dijadikan parent. Sedangkan Elitism adalah suatu metode yang berguna untuk mempertahankan nilai best fitness suatu generasi agar tidak turun di generasi berikutnya. Dalam AG caranya adalah dengan mengcopykan individu terbaik (maxfitness) sebanyak yang dibutuhkan.
> Crossover
Crossover merupakan proses mengkombinasikan bit-bit dalam satu kromosom dengan kromosom lain yang terpilih sebagai parent. Jumlah kromosom yang mengalami crossover ditentukan oleh parameter Pcrossover. Dimana Pcrossover ini kami assign sebesar 80%, karena kami mengharapkan 80% dari populasi mengalami crossover agar populasi individu menjadi lebih variatif.
> Mutation
Mutation diperlukan untuk mengembalikan informasi bit yang hilang akibat crossover. Mutasi ini dilakukan pada tingkat gen, dan jumlah gen yang dimutasi kami batasi dalam suatu variabel Pmutasi sebesar 5%. Nilai ini kami rasa cukup karena semakin banyak gen yang dimutasi maka kualitas dari suatu individu bisa mengalami penurunan.
Setelah dilakukan mutasi, kembali dicek untuk tiap kromosomnya apakah melanggar constraint atau tidak. Jika ada kromosom yang total beratnya melebihi kapasitas Knapsack, maka secara random, gen yang bernilai 1 akan diganti dengan 0 sampai kromosom tersebut tidak melanggar constraint. Jadi dapat disimpulkan, aplikasi kami akan selalu menemukan solusi.
Sumber :sukron-moh.blogspot.co.id
