UNIVERSITAS BINA NUSANTARA Program Ganda Teknik Informatika – Matematika Skripsi Sarjana Program Ganda Sementer Ganjil 2005/2006
Willy Rahardja NIM : 0500584311
Abstrak
Dalam kehidupan nyata, banyak sekali kejadian-kejadian yang mengharuskan kita meletakan beberapa pola (pattern) pada suatu bidang yang terbatas, sebagai contoh antara lain dalam industri pembuatan baju, kerajinan kayu, serta logam. Kondisi tersebut mengharuskan kita menempatkan pola-pola (pattern) dalam posisi yang optimal sehingga bidang yang digunakan menjadi minimum. Saai ini masih banyak yang melakukannya dengan perkiraan, namun hal tersebut akan sulit jika pola-pola (pattern) mempunyai bentuk yang tidak teratur. Dengan menggunakan metode Tabu search, untuk mencari posisi yang optimal dan menggunakan komputer sebagai alat penghitungnya, diharapkan dapat mengatasi kendala tersebut. Tujuan skripsi ini adalah untuk merancang dan membangun sebuah sistem pencarian posisi yang optimal dari peletakan pola-pola (pattern) tersebut terhadap suatu bidang dengan menggunakan metode pencarian Tabu search. Dalam skripsi ini dibuat program pencarian posisi yang optimal yang dimulai dari input berupa gambar pola (pattern), mengubah gambar pola (pattern) tersebut menjadi objek pola (pattern) yang digunakan dalam program, memproses objek pola-pola (pattern) tersebut hingga menghasilkan keluaran berupa gambar gabungan dari pola-pola (pattern) tersebut. Pengujian dengan menggunakan input dari sebuah pola (pattern) yang dibagi menjadi tiga bagian, diperoleh hasil analisis bahwa sistem dapat mencari posisi yang optimal dari ketiga pola (pattern) tersebut. Namun ada hal yang harus diperhatikan yaitu penggunaan gambar dengan format windows bitmap dapat menghilangkan ketelitian dari gambar akibat dari melakukan efek penghalusan terhadap grafik yang dibuat. Kata kunci : Tabu search, pattern, windows bitmap
iv
PRAKATA
Puji dan syukur kepada Tuhan Yang Maha Esa yang telah membimbing penulis dalam menyelesaikan skripsi yang berjudul “Perancangan Program Aplikasi Optimasi Peletakan Pola Pada Bidang Dengan Metode Tabu Search”. Skripsi ini disusun untuk memenuhi syarat gelar penyelesaian studi Teknik Informatika dan Matematika S1 di Universitas Bina Nusantara. Dalam penyusunan skripsi ini penulis banyak mendapatkan bantuan serta dukungan moral dari berbagai pihak. Oleh karena itu, pada kesempatan ini penulis ingin menyampaikan terima kasih kepada : 1. Bapak Prof. Dr. Gerardus Polla, M. App. Sc. selaku Rektor Universitas Bina Nusantara 2. Bapak Wikaria Gazali, S.Si, M.T., selaku Dekan Fakultas MIPA dan dosen pembimbing yang telah banyak menyediakan waktu, memberikan kepercayaan, kesempatan dan membimbing penulis dalam menyelesaikan skripsi ini. 3. Bapak Ngarap Imanuel Manik, Drs., M.Kom. selaku Ketua Jurusan Matematika yang telah memberikan kesempatan, kepercayaan dan semangat serta dukungan bagi penulis dalam penyusunan skripsi ini. 4. Bapak Dr. Ir. Haryono Soeparno, M.Sc., selaku dosen pembimbing yang telah banyak menyediakan waktu, membantu, memberikan sumbangan pemikiran dan membimbing penulis dalam menyelesaikan masalah-masalah yang ditemui selama penulis menyusun skripsi ini. 5. Keluarga dari penulis yang memberikan dukungan baik secara moral maupun finansial untuk menyelesaikan skripsi ini. 6. Rekan-rekan mahasiswa yang secara langsung maupun tidak langsung telah memberikan dukungan kepada penulis. v
7. Teman teman lain yang tidak dapat penulis sebutkan satu persatu yang telah memberikan bantuan tidak ternilai selama penyusunan skripsi ini. Penulis juga menyadari bahwa skripsi ini masih belum sempurna, oleh karena itu dengan segala kerendahan hati, penulis sangat mengharapkan saran dan kritik untuk membangun skripsi ini. Akhir kata, penulis berharap agar skripsi ini dapat memberikan manfaat bagi semua pembaca dan semua pihak yang berkepentingan. Terima kasih.
Jakarta, 29 Januari 2006 Penulis
Willy Rahardja 0500584311
vi
DAFTAR ISI Halaman Halaman Judul ...................................................................................................................i Halaman Pengesahan Softcover .......................................................................................iii Abstrak ............................................................................................................................iv Prakata ..............................................................................................................................v Daftar Isi .........................................................................................................................vii Daftar Tabel......................................................................................................................ix Daftar Gambar ..................................................................................................................x Daftar Lampiran ..............................................................................................................xi BAB 1 PENDAHULUAN ................................................................................................1 1.1 Latar Belakang Masalah..................................................................................1 1.2 Rumusan Rancangan .......................................................................................3 1.3 Spesifikasi Rancangan.....................................................................................3 1.4 Ruang Lingkup Masalah .................................................................................3 1.5 Tujuan dan Manfaat ........................................................................................4 1.6 Metodologi Penelitian .....................................................................................4 1.7 Sistematika Penulisan......................................................................................5 BAB 2 LANDASAN TEORI............................................................................................9 2.1 Tabu Search.....................................................................................................9 2.1.1 Latar Belakang Tabu search ..................................................................9 2.1.2 Kegunaan Memory...............................................................................10 2.1.3 Intensifikasi dan Diversifikasi..............................................................11 2.1.4 Prinsip Tabu search dan Memori Jangka Pendek ................................12 2.1.5 Memori dan Klasifikasi Tabu...............................................................14 2.1.6 Recency-based Memory........................................................................15 2.1.7 Komponen-komponen Tabu search .....................................................15 2.1.8 Algoritma Tabu search.........................................................................16 2.2 Computer Graphics .......................................................................................17 2.2.1 Bentuk Dasar ........................................................................................17 2.2.2 Resolusi ................................................................................................18 2.2.3 Teknik Manipulasi Image Processing..................................................19 2.2.4 Manajemen Warna ...............................................................................21 2.2.5 Warna RGB(Red, Green & Blue), CMYK (Cyan, Magenta, Yellow, Black), dan HSL (Hue, Saturation, Luminosity) .....................................................21 2.2.6 Manajemen Warna RGB ......................................................................23 2.2.7 Dokumen Bitmap (.bmp)......................................................................24 2.3 Transformasi Dua Dimensi ...........................................................................27 2.3.1 Sistem Koordinat Kartesian Dua Dimensi ........................................... 28 2.3.2 Matriks .................................................................................................28 2.3.3 Boundary ..............................................................................................30 2.3.4 Tranformasi Geometri ..........................................................................31 2.4 Bubble Sort ...................................................................................................32 2.5 Microsoft C#.NET.........................................................................................33 vii
BAB 3 PERANCANGAN ..............................................................................................34 3.1 Spesifikasi Rumusan Rancangan ..................................................................34 3.1.1 Proses Input ..........................................................................................36 3.1.2 Proses Tabu search...............................................................................41 3.1.3 Proses Output .......................................................................................44 3.2 Perancangan Program ...................................................................................46 3.2.1 Modul Input..........................................................................................46 3.2.2 Modul Proses........................................................................................48 3.2.3 Modul Output .......................................................................................49 3.2.4 Class GambarMatrix ............................................................................50 3.2.5 Class Hasil............................................................................................51 3.2.6 Class Map.............................................................................................52 3.2.7 Class Pattern.........................................................................................52 3.2.8 Struct Position ......................................................................................53 3.3 Flowchart Program .......................................................................................54 3.3.1 Flowchart Konversi Gambar Menjadi Objek Pattern..........................54 3.3.2 Flowchart Proses Searching.................................................................55 3.3.3 Flowchart Konversi Hasil Menjadi Gambar........................................ 56 3.4 Rancangan Layar Program ............................................................................57 3.4.1 Rancangan Layar Menu Utama............................................................57 3.4.2 Rancangan Layar Form Input ..............................................................58 3.4.3 Rancangan Layar Form Proses ............................................................59 3.4.4 Rancangan Layar Form Output............................................................60 3.4.5 Rancangan Layar Form About .............................................................61 BAB 4 IMPLEMENTASI DAN HASIL PENELITIAN ................................................62 4.1 Spesifikasi Hardware dan Software..............................................................62 4.2 Persiapan Data...............................................................................................63 4.3 Proses Implementasi......................................................................................65 4.4 Hasil Penelitian .............................................................................................68 BAB 5 KESIMPULAN DAN SARAN...........................................................................73 5.1 Kesimpulan....................................................................................................73 5.2 Saran..............................................................................................................74 DAFTAR PUSTAKA ..................................................................................................... 76 RIWAYAT HIDUP......................................................................................................... 78 LAMPIRAN ................................................................................................................... L1
viii
DAFTAR TABEL
Tabel 2.1 Tabel 3.1 Tabel 3.2 Tabel 3.3 Tabel 4.1
Jenis kompresi pada dokumen bitmap ..........................................................26 Bentuk Matriks Dari Gambar........................................................................40 Representasi Gambar Lengkap Dengan ‘Isi’ dan ‘Samping’........................ 41 Map Dari Hasil Proses Tabu search..............................................................45 Spesifikasi pattern input................................................................................65
ix
DAFTAR GAMBAR Halaman Gambar 1.1 Gambar 2.1 Gambar 2.2 Gambar 2.3 Gambar 2.4 Gambar 2.5 Gambar 3.1 Gambar 3.2 Gambar 3.3 Gambar 3.4 Gambar 3.5 Gambar 3.6 Gambar 3.7 Gambar 3.8 Gambar 3.9 Gambar 3.10 Gambar 3.11 Gambar 3.12 Gambar 4.1 Gambar 4.2 Gambar 4.3 Gambar 4.4 Gambar 4.5 Gambar 4.6 Gambar 4.7 Gambar 4.8
Contoh pola baju .......................................................................................2 Empat Prinsip Dasar Memory Dalam Tabu search ................................11 Warna dalam RGB dan CMY .................................................................23 HSL Color Wheel ....................................................................................23 Struktur Dokumen Bitmap ......................................................................25 Grafik Efisiensi Bubble Sort ...................................................................33 Objek Pattern ..........................................................................................37 Objek Pattern Dengan Batasnya .............................................................38 Objek Pattern Setelah Dibagi-bagi .........................................................39 Kombinasi Gambar Asli Dengan Hasil Output.......................................45 Flowchart Konversi Gambar Menjadi Objek Pattern.............................54 Flowchart Proses Searching....................................................................55 Flowchart Konversi Hasil Menjadi Gambar ...........................................56 Rancangan Layar Form Menu Utama.....................................................57 Rancangan Layar Input ...........................................................................58 Rancangan Layar Proses .........................................................................59 Rancangan Layar Output.........................................................................60 Rancangan Layar About ..........................................................................61 Pembagian pattern awal menjadi tiga bagian .........................................64 Langkah Pada Form Input.......................................................................66 Langkah Pada Form Proses ....................................................................66 Hasil terbaik dari proses..........................................................................68 Hasil Posisi Terbaik ................................................................................69 Perubahan Bentuk Pattern Yang Berwarna Hijau ..................................70 Pattern Biru Yang Tertutup Oleh Pattern Hijau ......................................70 Perpotongan image pada format windows bitmap...................................71
x
LAMPIRAN Halaman LAMPIRAN 1 Listing Program .................................................................................. L.1 1.1 Form About ............................................................................... L.1 1.2 Form Input................................................................................. L.6 1.3 Form Menu.............................................................................. L.14 1.4 Form Output............................................................................ L.17 1.5 Form Proses............................................................................. L.24 1.6 Class GambarMatrix ............................................................... L.38 1.7 Class GambarPattern............................................................... L.41 1.8 Class Hasil............................................................................... L.43 1.9 Class Map................................................................................ L.45 1.10 Class Pattern............................................................................ L.47 1.11 Class Position.......................................................................... L.50
xi
