LEMBAR PENGESAHAN PENERAPAN ALGORITMA GENETIK UNTUK

MASALAH KNAPSACK 0/1

dengan ini , saya menyatakan bahwa isi CD-Rom Laporan Penelitian sama dengan hasil Revisi Akhir

Bandung, DESEMBER 2009

Ricky Susanto

NRP: 0572048

Menyetujui,Pembimbing

Pembimbing I Pembimbing II

Dr.Ir Mewati Ayub, MT Peter Hyong Jik Kim, BFA

NIK: 720140 NIK: 710005 Mengetahui

Ketua Jurusan S1 Teknik Informatika

Dr.Ir Mewati Ayub, MT

NIK: 720140

i Universitas Kristen Maranatha

SURAT PERNYATAAN ORISINALITAS KARYA  

Saya yang bertanda tangan di bawah ini:

Nama : Ricky Susanto

NRP : 0572048

Fakultas / Jurusan : Teknologi Informasi / S1 Teknik Informatika

menyatakan bahwa tugas akhir ini merupakan hasil karya saya sendiri dan bukan

duplikasi dari orang lain.

Apabila di kemudian hari diketahui bahwa pernyataan ini tidak benar adanya maka

saya bersedia menerima seluruh sanksi yang diberikan.

Demikian pernyataan ini saya buat.

BANDUNG, DESEMBER 2009

Ricky Susanto

ii Universitas Kristen Maranatha

KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS

Sebagai mahasiswa Universitas Kristen Maranatha Bandung, saya yang

bertanda tangan dibawah ini :

Nama : Ricky Susanto

NRP : 0572048

Demi pengembangan ilmu pengetahuan, menyetujui untuk memberikan

kepada Universitas Kristen Maranatha hak bebas royalti Non‐Eksklusif atas karya

ilmiah saya yang berjudul “PENERAPAN ALGORITMA GENETIK UNTUK

MASALAH KNAPSACK 0/1”.

Dengan hak bebas royalti ini Universitas Maranatha berhak menyimpan,

mengalih formatkan, mendistribusikannya, dan mempublikasikan di berbagai media

untuk kepentingan akademis tanpa perlu meminta izin dari saya selama tetap

mencantumkan nama saya sebagai penulis/pencipta.

Demikian pernyataan ini saya buat dengan sebenar‐benarnya.

BANDUNG, DESEMBER 2009

Ricky Susanto

iii Universitas Kristen Maranatha

KATA PENGANTAR Puji dan syukur penulis panjatkan kepada Tuhan Yesus Kristus yang telah

memberikann bimbingan dan karunia‐Nya selama pengerjaan tugas akhir, hingga

penulis dapat menyelesaikan pelaksanaan tugas akhir dengan judul.

“PENERAPAN ALGORITMA GENETIK UNTUK MASALAH KNAPSACK 0/1”

Tugas akhir merupakan salah satu mata kuliah wajib di jurusan Teknik

Informatika Universitas Kristen Maranatha Fakultas Teknologi Informasi. Selesainya

laporan tugas akhir ini tidak terlepas dari bimbingan dan dukungan dari banyak

pihak. Dukungan ini secara langsung maupun tidak langsung membantu penulis

dalam penyelesaian laporan tugas akhir ini. Pada kesempatan ini, penulis secara

khusus ingin menyampaikan rasa terima kasih yang sedalam-dalamnya serta

penghargaan yang setinggi‐tingginya kepada:

1. Bapak Radiant Victor Imbar, S.Kom, MT, MCP, OCP selaku Dekan Fakultas

Teknologi Informasi.

2. Ibu Dr. Ir. Mewati Ayub, MT. selaku dosen pembimbing dan Ketua Jurusan

S1 Teknik Informatika yang selalu membantu penulis dalam pengerjaan

tugas akhir ini.

3. Bapak Peter Hyong Jik Kim, BFA. selaku dosen pembimbing lapangan

yang telah memberikan masukan-masukan bagi penulis.

4. Papah dan Mamah, yang selalu memberi doa dan dukungan baik secara

moril maupun masukan‐masukan yang membangun bagi penulis.

5. Kalina, BA. yang selalu mendukung dan memberi dorongan dalam

pengerjaan karya tulis ini.

6. Siany Limandinata, Fenny, Marvin Gunardi, Evlin Marcelin, Andre selaku

teman-teman yang selalu mendukung dan memberi dorongan dalam

pengerjaan karya tulis ini.

7. Segenap teman-teman penulis dari jurusan S1 Teknologi Informatika

angkatan 2005 yang memberi saran-saran yang berharga bagi penulis.

iv Universitas Kristen Maranatha

8. Serta berbagai pihak yang telah banyak membantu yang tidak dapat penulis

sebutkan satu.

Penulis telah mengerjakan tugas akhir ini dengan seoptimal mungkin, namun setiap

orang pasti tidak terlepas dari kesalahan. Penulis meminta maaf atas segala

kekurangan dan kesalahan yang dibuat dari laporan ini. Penulis juga mengharapkan

saran yang membangun sehingga bisa menambah pengetahuan dan pengalaman

penulis. Besar harapan penulis agar laporan tugas akhir ini dapat memberikan

manfaat dan pengetahuan bagi semua pihak.

Terima kasih

Bandung, DESEMBER 2009

Ricky Susanto

v Universitas Kristen Maranatha

ABSTRAKSI

Masalah knapsack 0/1 adalah masalah pengemasan barang dengan

batasan-batasan tertentu. Masalah pengemasan barang pada umumnya

dibatasi oleh kapasitas yang disebut knapsack. Banyak cara untuk

menyelesaikan masalah ini salah satunya dengan menggunakan algoritma

genetik.

Aplikasi ini dibangun untuk membuat simulasi yang menghasilkan

solusi untuk mempermudah user dalam melakukan pengemasan barang.

Aplikasi ini mengimplementasikan teknik-tenik yang terdapat pada algoritma

genetik dalam menghasilkan solusi untuk masalah knapsack 0/1. Data

barang yang di-input oleh user direpresentasikan di dalam array sehingga

dapat dengan mudah diolah dengan teknik-teknik algoritma genetik.

Pengujian terhadap aplikasi simulasi membatasi perhitungan hanya

pada dimensi volume dan berat. Hasil pengujian ditujukan untuk mencari

solusi dengan profit tertinggi dengan kombinasi parameter algoritma genetik

yang optimal. Uji kasus juga dilakukan pada kasus nyata dan diharapkan

memberikan solusi yang dapat dipakai pada dunia nyata.

Kata Kunci : knapsack 0/1, algoritma genetik, parameter algoritma genetik,

array.

vi Universitas Kristen Maranatha

ABSTRACT

The problem of knapsack 0/1 is the way of packing of things with some

limitations. The common problem of packing is usually limited by the capacity

called knapsack. There are a lot of ways to solve the problem, one of them by

using the algorithm genetic

This application is made to create a simulation and solution of packing

that eases the user. This application implements the algorithm techniques in

order to create a solution for the knapsack problem. The input from the user,

is represented in an array so it can be easily accessed and processed using

the algorithm genetic.

The application testing is used to limit the calculation that only

depends on the volume and the weight dimension. The test results are used

to create a solution that combines the highest profit with the optimum

algorithm genetic parameter. The real testing is also used for the real case

and is expected to give a best solution that can be used in the real world.

Key Word : knapsack 0/1, genetic algorithm, algorithm genetic parameter.

vii Universitas Kristen Maranatha

2.2.2.2 Urutan Stimulus .......................................................................................... 82.2.2.1 Tujuan ......................................................................................................... 8

Input Knapsack ....................................................................................... 82.2.2 Fitur 2 Input Barang ........................................................................................... 72.2.1 Fitur 1

2.2 Fitur Produk Perangkat Lunak .................................................................................. 7

2.1.4 Antarmuka Komunikasi ...................................................................................... 62.1.3 Antarmuka Perangkat Lunak ............................................................................. 62.1.2 Antarmuka Perangkat Keras.............................................................................. 62.1.1 Antarmuka dengan Pengguna ........................................................................... 6

2.1 Persyaratan Antarmuka Eksternal ............................................................................ 6

BAB 2 SPESIFIKASI PRODUK ......................................................................................... 6

1.2.5 Asumsi dan Ketergantungan.............................................................................. 51.2.4 Batasan - Batasan ............................................................................................. 41.2.3 Karakteristik Pengguna...................................................................................... 41.2.2 Fungsi Produk .................................................................................................... 41.2.1 Perspektif Produk............................................................................................... 4

1.2 Gambaran Keseluruhan............................................................................................ 4

1.1.4 Overview Laporan.............................................................................................. 21.1.3 Definisi, Akronim, dan Singkatan ....................................................................... 21.1.2 Ruang Lingkup Proyek....................................................................................... 21.1.1 Tujuan ................................................................................................................ 1

1.1 Pendahuluan............................................................................................................. 1

BAB 1 PERSYARATAN PRODUK .................................................................................... 1

DAFTAR PROGRAM ....................................................................................................... xv

DAFTAR TABEL .............................................................................................................. xii

DAFTAR GAMBAR ........................................................................................................... xi

DAFTAR ISI ..................................................................................................................... viii

ABSTRACT ...................................................................................................................... vii

ABSTRAKSI ...................................................................................................................... vi

KATA PENGANTAR ......................................................................................................... iv

KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS.................................................... iii

SURAT PERNYATAAN ORISINALITAS KARYA ............................................................. ii

LEMBAR PENGESAHAN ................................................................................................... i

DAFTAR ISI

Universitas Kristen Maranathaviii

ix Universitas Kristen Maranatha

4.2.4 Ulasan Realisasi User Interface Design .......................................................... 554.2.3 Ulasan Realisasi Fungsionalitas ...................................................................... 544.2.2 Error handling................................................................................................... 534.2.1 Top Down Implementasi .................................................................................. 52

4.2 Perjalanan Tahap Implementasi ............................................................................. 52

Class.................................................................................... 424.1.2 Keterkaitan antar Class ............................................................................................. 424.1.1 Pembagian

4.1 Perencanaan Tahap Implementasi ......................................................................... 42

BAB 4 PENGEMBANGAN SISTEM ................................................................................ 42

Class Diagram.................................................................................................. 333.2.3 Activity Diagram ............................................................................................... 273.2.2 Use Case Diagram........................................................................................... 243.2.1

3.2 Desain Perangkat Lunak Secara Keseluruhan....................................................... 24

3.1.5 Penerapan Algoritma Genetika dalam Knapsack Problem ............................. 22Shared Object ........................................................................................... 213.1.4.3

3.1.4.2 Crossover.................................................................................................. 20Roulette Wheel................................................................ 193.1.4.1 Metode Seleksi

3.1.4 Algoritma Genetik ............................................................................................ 18knapsack dengan Greedy..................................................... 143.1.3.1 Pemecahan

Knapsack Problem........................................................................................... 143.1.3 3.1.2 Overview Sistem .............................................................................................. 133.1.1 Identifikasi ........................................................................................................ 13

3.1 Pendahuluan........................................................................................................... 13

BAB 3 DESAIN PERANGKAT LUNAK ........................................................................... 13

2.2.7.3 Persyaratan Fungsional yang berhubungan............................................. 122.2.7.2 Urutan Stimulus ........................................................................................ 112.2.7.1 Tujuan ....................................................................................................... 11

Setting Parameter Algoritma Genetik ............................................ 112.2.7 Fitur 7 2.2.6.3 Persyaratan Fungsional yang berhubungan............................................. 112.2.6.2 Urutan Stimulus..................................................................................... 112.2.6.1Tujuan ........................................................................................................ 10

2.2.6 Fitur 6 Grafik Solusi................................................................................... 102.2.5.3 Persyaratan Fungsional yang berhubungan............................................. 102.2.5.2 Urutan Stimulus ........................................................................................ 102.2.5.1 Tujuan ....................................................................................................... 10

Load ...................................................................................................... 102.2.5 Fitur 5 2.2.4.3 Persyaratan Fungsional yang berhubungan............................................. 102.2.4.2 Urutan Stimulus .......................................................................................... 92.2.4.1 Tujuan ......................................................................................................... 9

Save........................................................................................................ 92.2.4 Fitur 4 2.2.3.3 Persyaratan Fungsional yang berhubungan............................................... 92.2.3.2 Urutan Stimulus .......................................................................................... 82.2.3.1 Tujuan ......................................................................................................... 8

2.2.3 Fitur 3 Pencarian Solusi..................................................................................... 82.2.2.3 Persyaratan Fungsional yang berhubungan............................................... 8

Universitas Kristen Maranathaix

LAMPIRAN DATA PENULIS ............................................................................................IX

DAFTAR PUSTAKA........................................................................................................VIII

6.3 Rencana Perbaikan / Implementasi terhadap Saran yang Diberikan..................... 94

6.2 Keterkaitan antara Saran dengan Hasil Evaluasi ................................................... 93

6.1 Keterkaitan antara Kesimpulan dengan Hasil Evaluasi .......................................... 93

BAB 6 KESIMPULAN DAN SARAN................................................................................ 93

5.3 Ulasan Hasil Evaluasi ............................................................................................ 91

Real.................................................................................................. 895.2.3 Uji Kasus 5.2.2 Uji Algoritma Genetik ....................................................................................... 695.2.1 Black Box ......................................................................................................... 65

5.2 Perjalanan Metodologi Pengujian ........................................................................... 65

5.1.2 Uji Fungsionalitas Modul/Class........................................................................ 645.1.1 Test Case......................................................................................................... 62

5.1 Rencana Pengujian Sistem Terimplementasi......................................................... 62

BAB 5 TESTING DAN EVALUASI SISTEM .................................................................... 62

Universitas Kristen Maranathax

Gambar 4.10 Setting Parameter..................................................................................... 60

Gambar 4.9 Grafik ........................................................................................................... 60

Gambar 4.8 Save Project................................................................................................ 59

Gambar 4.7 Project ......................................................................................................... 58

Gambar 4.6 Load Project................................................................................................ 58

Gambar 4.5 Input Knapsack........................................................................................... 57

Gambar 4.4 Input Barang ............................................................................................... 56

Gambar 4.3 Menu Utama ................................................................................................ 55

Gambar 4.2 Top Down Implementasi ............................................................................ 52

Class...................................................................................... 42Gambar 4.1 Relasi Antar

Gambar 3.11 Class Diagram .......................................................................................... 34

Setting Parameter ....................................................... 33Gambar 3.10 Activity Diagram

Gambar 3.9 Activity Diagram Grafik Solusi.................................................................. 32

Gambar 3.8 Activity Diagram Save................................................................................ 31

Gambar 3.7 Activity Diagram Load ............................................................................... 30

Gambar 3.6 Activity Diagram Pencarian Solusi........................................................... 29

Gambar 3.5 Activity Diagram Memasukan Knapsack ................................................. 28

Gambar 3.4 Activity Diagram Memasukan Barang...................................................... 28

Gambar 3.3 Use Case Diagram...................................................................................... 24

Crossover........................................................................................ 20Gambar 3.2 Varian

Gambar 3.1 Metode Roulette Wheel.............................................................................. 19

DAFTAR GAMBAR

Universitas Kristen Maranathaxi

view grafik ..................................................................................... 64Tabel 5.6 Test Case

Save ............................................................................................... 64Tabel 5.5 Test Case

Load ............................................................................................... 63Tabel 5.4 Test Case

Tabel 5.3 Test Case Pencarian Solusi .......................................................................... 63

Tabel 5.2 Test Case Menginput knapsack.................................................................... 62

Tabel 5.1 Test Case Menginput Barang........................................................................ 62

Tabel 4.1 Realisasi Fungsionalitas................................................................................ 54

Class BukaSO ............................................................................................... 39Tabel 3.15

Class SaveSO ............................................................................................... 38Tabel 3.15

Class Seleksi................................................................................................. 38Tabel 3.14

Class Crossover ........................................................................................... 37Tabel 3.13

Class Mutasi.................................................................................................. 37Tabel 3.12

Class AG........................................................................................................ 36Tabel 3.11

Class Main ..................................................................................................... 34Tabel 3.10

Tabel 3.9 Notasi Use Case View .................................................................................... 27

Tabel 3.8 Notasi Use Case Save.................................................................................... 26

Tabel 3.7 Notasi Use Case Edit Data............................................................................. 26

Tabel 3.6 Notasi Use Case Pencarian Solusi ............................................................... 26

Tabel 3.5 Notasi Use Case Menginput Knapsack........................................................ 25

Tabel 3.4 Notasi Use Case Menginput Barang............................................................. 25

Tabel 3.3 Notasi Use Case Load.................................................................................... 25

Kromosom...................................................................................................... 22Tabel 3.2

Greedy ............................................................................................................ 17Tabel 3.1

Tabel 1.1 Definisi Akronim dan Singkatan ..................................................................... 2

DAFTAR TABEL

Universitas Kristen Maranathaxii

Knapsack Kasus 5........................................................................................ 86Tabel 5.32

Tabel 5.31 Barang Kasus 5 ............................................................................................ 86

Tabel 5.30 Solusi Kasus 4 .............................................................................................. 83

Tabel 5.29 Hasil Uji Kasus 4........................................................................................... 82

Knapsack Kasus 4........................................................................................ 82Tabel 5.28

Tabel 5.27 Barang Kasus 4 ............................................................................................ 82

Tabel 5.26 Solusi Kasus 3 .............................................................................................. 78

Tabel 5.25 Hasil Uji Kasus 3........................................................................................... 77

Knapsack Kasus 3........................................................................................ 77Tabel 5.24

Tabel 5.23 Barang Kasus 3 ............................................................................................ 76

Tabel 5.22 Solusi Kasus 2 .............................................................................................. 74

Tabel 5.21 Hasil Uji Kasus 2........................................................................................... 73

Knapsack Kasus 2........................................................................................ 73Tabel 5.20

Tabel 5.19 Barang Kasus 2 ............................................................................................ 72

Tabel 5.18 Solusi Kasus 1 .............................................................................................. 70

Tabel 5.17 Hasil Uji Kasus 1........................................................................................... 69

Knapsack Kasus 1........................................................................................ 69Tabel 5.16

Tabel 5.15 Barang Kasus 1 ............................................................................................ 69

Edit data ............................................................................. 68Tabel 5.14 Black Box Test

view grafik .......................................................................... 68Tabel 5.13 Black Box Test

Save .................................................................................... 67Tabel 5.12 Black Box Test

Load .................................................................................... 67Tabel 5.11 Black Box Test

Tabel 5.10 Black Box Test Pencarian Solusi................................................................ 66

Tabel 5.9 Black Box Test Menginput knapsack ........................................................... 66

Tabel 5.8 Black Box Test Menginput Barang ............................................................... 65

Edit data ........................................................................................ 64Tabel 5.7 Test Case

Universitas Kristen Maranathaxiii

Tabel 5.39 Hasil Evaluasi ............................................................................................... 91

Real ........................................................................................ 90Tabel 5.38 Solusi Kasus

Real ..................................................................................... 89Tabel 5.37 Hasil Uji Kasus

Knapsack Kasus Real .................................................................................. 89Tabel 5.36

Real....................................................................................... 89Tabel 5.35 Barang Kasus

Tabel 5.34 Solusi Kasus 5 .............................................................................................. 87

Tabel 5.33 Hasil Uji Kasus 5........................................................................................... 86

Universitas Kristen Maranathaxiv

program 4.13 Fungsi SaveFN ........................................................................................ 52

program 4.13 Fungsi Saveso ......................................................................................... 51

program 4.12 Fungsi NamaFile...................................................................................... 50

program 4.12 Fungsi Bukaso......................................................................................... 49

program 4.11 Fungsi Sl .................................................................................................. 49

program 4.10 Fungsi MT ................................................................................................ 48

program 4.9 Fungsi CR .................................................................................................. 47

program 4.8 Fungsi startPerhitungan........................................................................... 47

program 4.7 Fungsi Parameter ...................................................................................... 46

program 4.6 Fungsi Terbaik........................................................................................... 46

program 4.5 Fungsi Fitness ........................................................................................... 45

program 4.4 Fungsi Filter ............................................................................................... 45

program 4.3 Fungsi BuatKromosom ............................................................................ 44

program 4.2 Fungsi Buattabel ....................................................................................... 44

Datagrid ......................................................................................... 43program 4.1 Fungsi

program 3.3 Greedy by Density.................................................................................... 17

program 3.2 Greedy by Weight..................................................................................... 16

program 3.1 Greedy by Profit ....................................................................................... 16

DAFTAR PROGRAM

Universitas Kristen Maranathaxv