KATA PENGANTAR
Puji syukur kepada Tuhan Yang Maha Kuasa atas Kasih dan karuniaNya sehingga makalah ini dapat terselesaikan. Makalah ini merupakan tugas Penulis dalam mengikuti matakuliah KECERDASAN BUATAN. Penulis menyadari bahwa semuanya ini merupakan rangkaian kemurahan dan kehendakNya dalam hidup penulis. Dia adalah Sumber Pengetahuan abadi, motivasi dan tujuan hidup bagi kami secara khusus kelompok III bahkan untuk segala hal dalam hidup kami, sampai selama-lamanya.
Pada kesempatan ini penulis mengucapkan terima kasih kepada Bapak Parasian Silitonga, S.Kom, M.cs sebagai dosen pengasuh matakuliah kecerdasan buatan yang telah membimbing dan mengarahkan kami.
Penulis juga menyadari bahwa makalah ini jauh dari kesempurnaan, untuk itu penulis mengharapkan kritik dan saran dari pembaca yang bersifat membangun. Akhir kata penulis mengucapkan terima kasih dan semoga makalah ini dapat bermanfaat bagi pembaca.
Penulis
DAFTAR ISI
KATA PENGANTAR.......................................................................................................... i
DAFTAR ISI........................................................................................................................... ii
BAB I : PENDAHULUAN
1.1 LATAR BELAKANG..................................................................................................... 1
1.2 PERUMUSAN MASALAH............................................................................................. 1
1.3 BATASAN MASALAH................................................................................................... 1
1.4 TUJUAN.......................................................................................................................... 1
BAB II : PEMBAHASAN
2.1 KNAPSACK 0/1............................................................................................................. 2
2.2 MASALAH KNAPSACK............................................................................................... 3
2.3 PENYELESAIAN MASALAH..................................................................................... 3
2.4 STUDI KASUS
2.4.1 KNAPSACK 0/1 (BIN PACKING)....................................................................... 5
2.4.2 PENYELESAIAN................................................................................................. 5
2.5 PROGRAM
2.5.1 LISTING PROGRAM.......................................................................................... 8
2.5.2 OUTPUT............................................................................................................... 9
BAB III : PENUTUP
KESIMPULAN................................................................................................................... 10
DAFTAR PUSTAKA
BAB I
PENDAHULUAN
1.1 LATAR BELAKANG
Dari berbagai masalah yang sering muncul dalam kehidupan kita, optimasi selalu menarik untuk diperbincangkan. Dalam pemrograman, optimasi pun memiliki tempatnya tersendiri. Baik itu menjadi masalah yang harus dipecahkan, maupun keharusan dalam membuat program yang optimal. Knapsack adalah salah satu masalah yang sering muncul dalam kasus optimasi dan kombinatorial. Knapsack sendiri terdiri dari beberapa varian, yaitu 0-1Knapsack, Knapsack Terbatas, dan Knapsack Tak Terbatas. Ada berbagai macam algoritma yang dapat digunakan untuk memecahkan masing- masing varian, dan yang akan kita bahas pada tulisan ini adalah Algoritma greedy yang digunakan untuk menjawab permasalahan 0-1 Knapsack.
1.2 PERUMUSAN MASALAH
Berdasarkan latar belakang masalah, maka yang menjadi permasalahan adalah bagaimana mengaplikasikan Heuristic search agar dapat digunakan untuk mengatasi masalah knapsack. Permasalahan knapsack atau rucksack adalah permasalahan optimasi kombinatorial, ilustrasinya adalah : “Diberikan sekumpulan barang, masing-masing dengan berat dan nilai, kita harus dapat menentukan jumlah dari masing-masing barang untuk dimasukan dalam sebuah wadah sehingga total beratnya kurang dari sama dengan berat yang telah ditentukan, dan total nilainya harus sebesar mungkin.”
1.3 BATASAN MASALAH
Adapun pembatasan masalah dalam penulisan makalah ini adalah sebagai berikut :
- Hanya membahas knapsack 0/1
- Membahas masalah knapsack dengan menggunakan algoritma greedy (Greedy by profit) dan implementasinya dalam bin packing problem.
1.4 TUJUAN
Adapun tujuan dari aplikasi knapsack ini adalah untuk menghasilkan solusi yang optimal pada permasalahan knapsack dengan menggunakan algoritma greedy.
BAB II
PEMBAHASAN
2.1 KNAPSACK 0/1
Knapsack adalah tas atau karung yang digunakan untuk memasukkan sesuatu. Tapi tidak semua barang bisa ditampung kedalam karung tersebut. Karung tersebut hanya dapat menyimpan beberapa objek dengan total ukurannya (weight) lebih kecil atau sama dengan ukuran ka
pasitas karung.
Knapsack problem memiliki tiga jenis persolan, yaitu:
1. Knapsack 0/1
Sesuatu yang dimasukkan kedalam karung dimensinya harus dimasukkan semua atau tidak sama sekali.
2. Knapsack Bounded
Sesuatu yang dimasukkan kedalam karung dimensi
nya bisa dimasukkan sebagaian atau seluruhnya.
3. Knapsack Unbounded
Ada beberapa strategi algoritma yang bisa menghasilkan solusi optimal, diantaranya adalah Brute Force, algotitma genetika, Algoritma greedy. Pada makalah ini masalah knapsack 0/1 akan diselesaikan dengan Greedy Algorithm yaitu solusi yang mencari nilai optimum. Algoritma ini memecahkan permasalahan langkah per langkah, yaitu:
1. Mengambil pilihan terbaik yang bisa diperoleh saat itu juga tanpa memperhatikan konsekuensi kedepan (prinsip “take what you can get now!”).
2. Berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global.
Pada Greedy Algorithm ada beberapa strategi yang digunaka
n untuk memilih objek yang akan dimasukkan kedalam knapsack:
1. 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.
2. 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.
3. Greedy by density.
Pada setiap langkah, knapsack diisi dengan objek yang mempunyai densitas, pi /wi terbesar. Strategi ini mencoba memaksimumkan keuntungan dengan memilih objek yang mempunyai keuntungan per unit berat terbesar.
2.2 MASALAH KNAPSACK
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.
2.3 PENYELESAIAN MASALAH
Berikut adalah beberapa cara 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 2n 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 ith menunjukkan 0 maka item tersebut tidak terpi
lih dan jika 1 maka item tersebut dipilih.
2. Algoritma Genetika
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 diharapkan 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 y
ang 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”.
3. 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. Strategi greedy yang dapat diterapkan pada 0/1 Knapsack Problem :
1. Pilih item yang memiliki nilai maksimum dari item-item
yang tersedia, hal ini akan menambah nilai dari Knapsack secara cepat.
2. Pilih item yang memiliki bobot minimum dari item-item yang ada sehingga kapasitas terisi secara perlahan dan dapat memuat lebih banyak item.
3. Pilih item yang memiliki nilai tinggi untuk bobot/berat
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.
2.4 STUDY KASUS
2.4.1 KNAPSACK 0/1(BIN PACKING)
Diketahui 4 barang yang akan disimpan pada suatu tempat yang memiliki kapasitas maksimal sebesar 16 Kg. Berat masing-masing barang adalah 6 Kg, 5 Kg, 10 Kg, dan 5 Kg dimana setiap barang memiliki profit sebesar masing-masing 12, 15, 50, dan 10. Tentukan barang mana saja yang dapat disimpan ke dalam tempat penyimpanan sehingga diperoleh nilai profit yang maksimal.
2.4.2 PENYELESAIAN
Tinjau persoalan 0/1 Knapsack dengan n = 4.
w1 = 2; p1 = 12
w2 = 5; p1 = 15
w3 = 10; p1 = 50
w4 = 5; p1 = 10
Kapasitas knapsack W = 16
Solusi dengan algoritma greedy:
| Properti objek | Greedy by profitt | |||
| i | wi | pi | pi /wi | |
| 1 | 6 | 12 | 2 | 0 |
| 2 | 5 | 15 | 3 | 1 |
| 3 | 10 | 50 | 5 | 1 |
| 4 | 5 | 10 | 2 | 0 |
| Total bobot | 15 | |||
| Total keuntungan | 65 | |||
Kapasitas m=16 ( w1,w2,w3,w4 = 6,5,10,5 )
( p1,p2,p3,p4 = 12,15,50,10 )
Pilih objek dengan nilai profit terbesar(pi), susun data dengan kriteria:
( p3,p2,p1,p4 = 50,15,12,10)
(w3,w2,w1,w4 = 10,5,6,5)
1. PROCEDURE GREEDY KNAPSACK (P, W, X, n) nama prosedur/prosesà
2. REAL P(1:n), W(1:n), X(1:n), M, isi variabel yang digunakanà
3. INTEGER i, n variabel yang digunakanà
4. X(1:n) = 0
5. isi = M
6. FOR i = 1 TO n DO
7. IF W(i) > isi THEN EXIT ENDIF
8. X(i) = 1
9. isi = isi – W(i)
10. REPEAT
11. IF i ≤ n THEN X(i) = isi/W(i) ENDIF
12. END GREEDY KNAPSACK akhir prosedur/
prosesà Proses kegiatan dimulai dari langkah ke- 4 sampai dengan 11. X(1:4) = 0, artinya X(1)=0, X(2)=0, X(3)=0, X(4)=0
isi = M = 16 Pengulangan untuk i = 1 sampai dengan 4
Untuk i = 1
Apakah W(1) > isi
Apakah 10 > 16, jawabnya tidak, karena tidak maka perintah dibawah IF dikerjakan.
nilai probabilitas untuk objek pada urutan pertama (X1)àX(1) = 1
isi = 16 – 10 = 6
mengulang untuk perulangan FORàREPEAT
Untuk i = 2
Apakah W(2) > isi
Apakah 5 > 6, jawabnya tidak, karena tidak maka perintah dibawah IF dikerjakan.
nilai probabilitas untuk objek pada urutan pertama (X1)àX(1) = 1
Isi=6-5=1
mengulang untuk perulangan FORàREPEAT
Untuk i=3
Apakah W(3)>isi
Apakah 6>1, jawabnya ya. Karena ya maka perintah EXIT dikerjakan yaitu keluar dari perulangan for.
Untuk i=4
Apakah W(4)>isi
Apakah 5>1, jawabnya ya. Karena ya maka perintah EXIT dikerjakan yaitu keluar dari perulangan for.
Hasil dari procedure diatas adalah memilih semua objek yan
g lebih kecil dari isi, yaitu w1 dan w2 yang memiliki bobot masing-masing 10 dan 5 dan yang memiliki profit 50 dan 15.
Jadi, hasilnya adalah 65.
2.5 PROGRAM
2.5.1 LISTING PROGAM
KESIMPULAN
1. Knapsack adalah permasalahan kombinasi yang melibatkan optimasi, dan terdapat variasi masalah dilihat dari jumlah tiap barang i yang ditangani dengan menggunakan Knapsack 0/1.
2. Pemecahan masalah 0-1 Knapsack menggunakan Algoritma Greedy melibatkan kombinatorial dan optimasi.
DAFTAR PUSTAKA
1. http://www.informatika.org/~rinaldi/Stmik/2007-2008/Makalah2008/MakalahIF2251-2008-017.pdf
2. http://www.cs.rpi.edu/~beevek/files/ai-heuristic-search.pdf
4. http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf
5. http://www.informatika.org/~rinaldi/Stmik/Makalah/MakalahStmik16.pdf
6. http://www.scribd.com/doc/30550680/Algoritma-Greedy
