BAB 2 LANDASAN TEORI
Pada bab ini akan dijelaskan tentang landasan dari konsep dan teori yang digunakan untuk mendukung pembuatan aplikasi yang dibuat. Landasan teori serta konsep yang akan dijelaskan meliputi penjelasan mengenai grafika komputer, algoritma Steepest Ascent Hill Climbing, WebGL dan Three.js. 2.1. Visualisasi Visualisasi merupakan pengungkapan suatu gagasan atau perasaan dengan menggunakan bentuk gambar, tulisan (kata dan angka), peta, grafik dan lain sebagainya (KBBI, 2012).
2.2. Gudang Menurut Kamus Besar Bahasa Indonesia (KBBI), gudang merupakan sebuah rumah atau bangsal tempat untuk menyimpan barang-barang, baik itu berupa barang-barang kimia, kumpulan surat/arsip-arsip, sesuatu yang mudah dibekukan, tempat menyimpan senjata, dan lain-lain. Menurut Oxford Dictionaries, Warehouse merupakan sebuah bangunan besar tempat penyimpanan bahan-bahan mentah ataupun barang-barang manufaktur yang akan didistribusikan untuk dijual. 2.3. Grafika Komputer Grafika komputer sering dikenal dengan istilah visualisasi data. Grafika komputer merupakan bagian dari ilmu komputer yang berkaitan dengan pembuatan serta manipulasi gambar (visual) secara digital. Awalnya grafika komputer memiliki bentuk yang masih sederhana yaitu dua dimensi (2D), kemudian berkembang menjadi tiga dimensi (3D), pemrosesan citra (image processing) dan pengenalan pola (pattern recognition). Menurut Hudjuli (2012) bagian dari grafika komputer meliputi: (1) Geometri: mempelajari tentang cara menggambarkan permukaan bidang.
Universitas Sumatera Utara
6
(2) Animasi: mempelajari tentang cara menggambarkan dan memanipulasi gerakan. (3) Rendering: mempelajari tentang algoritma untuk menampilkan efek cahaya. (4) Citra (Imaging): mempelajari tentang cara mengambil dan menyunting gambar. 2.3.1. Grafik 3 dimensi (3d) Menurut Basuki dan Nana (2009) objek tiga dimensi (3D) merupakan kumpulan titiktitik 3D (x, y, z) yang kemudian membentuk luasan-luasan (face) yang digabungakan menjadi satu kesatuan. Face merupakan gabungan titik-titik yang membentuk luasan tertentu atau sering dinamakan dengan sisi. 2.4. Penyusunan Barang menggunakan metode Block Stacking Pada aplikasi ini penyusunan barang menggunakan metode block stacking, dimana penyusunan barang mengacu pada penyusunan barang yang ditumpuk ke arah atas dengan ketinggian tertentu (Yahya, 2013). Oleh karena itu penyusunan barang dimulai dari sebelah kiri ruangan kemudian disusun ke atas dengan syarat barang yang disusun di atas memiliki bobot/berat lebih kecil atau sama dengan bobot/berat barang yang berada di bawah serta memiliki panjang dan lebar yang lebih kecil atau sama dengan barang yang berada di bawahnya. Apabila barang yang telah ditumpuk telah mencapai batas maksimal tumpukan (total berat barang yang ditumpuk kecil atau sama dengan barang dibawahnya) maka barang akan disusun ke samping kanan. Jika barang yang telah disusun tidak dimungkinkan lagi untuk disusun ke samping maka barang berikutnya akan disusun di depan barang yang sebelumnya telah disusun, susunan dimulai dari sebelah kiri ruangan dan begitu seterusnya.
2.5. Teori Dasar Algoritma Hill Climbing Algoritma Hill Climbing merupakan salah satu algoritma pencarian lokal. Algoritma hill climbing dimulai dengan memilih sembarang lintasan dan membuat iterasi perubahan kecil pada solusi, setiap langkah mencari solusi yang terbaik, ketika algoritma tidak dapat melihat perbaikan lagi maka berhenti. Pada saat itulah ditemukan solusi tebaik. Kelebihan algoritma hill climbing yaitu algoritma ini dapat menentukan beberapa kemungkinan solusi yang terjadi sehigga dapat dicari kemungkinan solusi yang terbaik dari beberapa kemungkinan tersebut, sedangkan
Universitas Sumatera Utara
7
kelemahannya yaitu algoritma ini membutuhkan waktu yang relatif lama karena harus menghitung kemungkinan solusi yang banyak. Algoritma hill climbing dibedakan menjadi dua, yaitu : algoritma Simple Hill Climbing dan algoritma Steepest Hill Climbing (Mufarricha, 2010).
2.5.1. Algoritma simple hill climbing Algoritma Simple Hill Climbing melakukan proses pengujian dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya sangat bergantung terhadap feedback dari prosedur pengetesan. Proses kerja algoritma simple hill climbing adalah sebagai berikut (Kusumadewi & Purnomo, 2005) : 1. Dimulai dari keadaan awal, dilakukan pengujian. Jika merupakan tujuan maka berhenti, jika tidak maka lanjutkan dengan keadaan sekarang sebagai keadaan awal. 2. Lanjutkan langkah-langkah berikut hingga tujuan tercapai atau hingga iterasi tidak memberikan perubahan pada keadaan sekarang: a. Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan baru. b. Evaluasi keadaan baru tersebut. i. Jika keadaan baru tersebut merupakan tujuan, keluar. ii. Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang. iii. Jika keadaan baru tersebut tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.
2.5.2. Algoritma Steepest Ascent Hill Climbing Algoritma Steppest Ascent Hill Climbing hampir sama dengan algoritma Simple Hill Climbing, perbedaannya terdapat pada pencarian yang dilakukan algoritma Steepest Ascent Hill Climbing tidak dimulai dari posisi paling kiri, melainkan gerakan selanjutnya dicari berdasarkan nilai heuristic terbaik. Dalam hal ini urutan dari penggunaan operator tidak menentukan penemuan solusi. Cara kerja algoritma Steepest Ascent Hill Climbing adalah sebagai berikut sekarang (Kusumadewi & Purnomo. 2005) :
Universitas Sumatera Utara
8
1. Dimulai dari keadaan awal, dilakukan pengujian. Jika merupakan tujuan maka berhenti, jika tidak maka lanjutkan dengan keadaan sekarang sebagai keadaan awal. 2. Lanjutkan langkah-langkah berikut hingga tujuan tercapai atau hingga iterasi tidak memberikan perubahan pada keadaan sekarang: a. Tentukan SUCC sebagai nilai heuristik terbaik dari successorsuccessor. b. Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang. i.
Gunakan operator tersebut dan bentuk keadaan baru.
ii. Evaluasi keadaan baru tersebut. Jika merupakan tujuan maka keluar, jika bukan maka bandingkan nilai heuristiknya dengan SUCC. Jika nilai heuristiknya lebih baik dari nilai SUCC, maka jadikan nilai heuristik tersebut sebagai SUCC, namun jika nilai heuristik tidak lebih baik dari nilai SUCC maka nilai SUCC tidak berubah. c. Jika SUCC lebih baik daripada nilai heuristik keadaan sekarang, ubah node SUCC menjadi keadaan sekarang. Keterangan: SUCC adalah nilai heuristik terbaik dari successorsuccessor. Contoh implementasi Algoritma Steepest Ascent Hill Climbing pada persoalan TSP (Traveling Salesman Problem): Seorang tourist ingin mengunjungi n kota. Jarak antar tiap-tiap kota sudah diketahui. Yang ingin dicari adalah jarak terpendek dimana setiap kota hanya boleh dikunjungi tepat 1 kali. Misalkan terdapat 4 kota dengan jarak tiap-tiap kota sebagai berikut: 9 B
A
4
5
8
6 D
7
C
Gambar 2.1. Graf TSP(Traveling Salesman Problem)
Universitas Sumatera Utara
9
Solusi-solusi yang mungkin dengan menyusun kota-kota dalam urutan abjad, misalkan: A – B – C – D : dengan panjang lintasan = 9+6+7 = 22. B – A – C – D : dengan panjang lintasan = 9+4+7 = 20. C – B – A – D : dengan panjang lintasan = 6+9+8 = 23. D – B – C – A : dengan panjang lintasan = 5+6+4 = 15.
(1) Algoritma Simple Hill Climbing Operator digunakan untuk menukar posisi kota yang bersebelahan. Fungsi heuristik yang digunakan adalah panjang lintasan yang terjadi. Maka penggunaan operator pada lintasan adalah sebagai berikut: Tukar 1,2 tukar urutan posisi kota ke-1 dengan kota ke-2 Tukar 2,3 tukar urutan posisi kota ke-2 dengan kota ke-3 Tukar 3,4 tukar urutan posisi kota ke-3 dengan kota ke-4 Tukar 4,1 tukar urutan posisi kota ke-4 dengan kota ke-1 Tukar 2,4 tukar urutan posisi kota ke-2 dengan kota ke-4 Tukar 1,3 tukar urutan posisi kota ke-1 dengan kota ke-3 Algoritma Steepest Ascent Hill Climbing hampir sama dengan Simple Hill Climbing, hanya saja gerakan pencarian tidak dimulai dari kiri melainkan berdasarkan nilai heuristik terbaik. Keadaan awal lintasan ABCD (22). Tukar 1, 2 BACD = 9 + 4 + 7 = 20. Tukar 2, 3 ACBD = 4 + 6 + 5 = 15. Tukar 3, 4 ABDC = 9 + 5 + 7 = 21. Tukar 4, 1 DBCA = 5 + 6 + 4 = 15. Tukar 2, 4 ADCB = 8 + 7 + 6 = 21. Tukar 1, 3 CBAD = 6 + 9 + 8 = 23. Dipilih nilai terkecil dari graf tersebut. Karena nilai yang terkecil pertama adalah ACBD(15), maka langkah selanjutnya dimulai dari ACBD(15). Tukar 1, 2 CABD = 4 + 9 + 5 = 18. Tukar 2, 3 ABCD = 9 + 6 + 7 = 22. Tukar 3, 4 ACDB = 4 + 7 + 5 = 16. Tukar 4, 1 DCBA = 7 + 6 + 9 = 22.
Universitas Sumatera Utara
10
Tukar 2, 4 ADBC = 8 + 5 + 6 = 19. Tukar 1, 3 BCAD = 6 + 4 + 8 = 18. Karena tidak terdapat nilai yang lebih kecil dari ACBD(15), maka solusi akhir yang di dapat adalah ACBD(15). (Sumber:http://www.slideshare.net/ceezabramovic/metode-pencarian-heuristik). Flowchart algoritma Steepest Ascent Hill Climbing dapat dilihat pada Gambar 2.1. Mulai
Inisialisasi Awal
Tujuan
Ya
Tidak Keadaan Awal -> Keadaan Sekarang
Tentukan SUCC
Bentuk Keadaan Baru
Ya Tujuan Tidak Tidak
Keadaan Baru > SUCC Ya Keadaan Baru -> SUCC
SUCC = SUCC
Tidak
SUCC > Keadaan Sekarang Ya Keadaan Sekarang -> SUCC
Selesai
Gambar 2.2. Flowchart algoritma Steepest Ascent Hill Climbing
Universitas Sumatera Utara
11
2.6. Relevansi Steepest Ascent Hill Climbing Algorithm Pada Pola Penyusunan Barang Algoritma Steepest Ascent Hill Climbing digunakan untuk menyelesaikan permasalahan tata letak penyusunan barang pada ruang tiga dimensi dengan tujuan mendapatkan pola penyusunan barang yang terbaik. Parameter optimal atau tidaknya penyusunan barang pada gudang diukur berdasarkan sisa ruang kosong yang tersisa ketika masih terdapat barang yang tidak dapat lagi dimuat/dimasukkan dalam ruangan tersebut. Semakin sedikit ruang kosong yang terdapat pada suatu pola penyusunan barang maka pola penyusunan tersebut merupakan solusi terbaik. Pada proses penyusunan barang pada gudang 3D (tiga dimensi), salah satu parameter yang menentukan pola penyusunan barang adalah berat barang. Barang yang memiliki berat paling besar akan disusun pertama, kemudian diikuti dengan barang yang memiliki berat lebih kecil dari barang sebelumnya tersebut.
2.7. Teknologi WebGL Beberapa teknologi selain WebGL yang dapat membangun objek 3D (tiga dimensi), yaitu: Unity 3D, Flash Stage 3D, Silverlight 3D, Direct 3D, OpenGL dan OpenGL ES (Boesch, F. 2013). Kelebihan dari WebGL yaitu WebGL dapat berjalan di banyak browser, seperti: Chrome, Firefox, Safari dan Opera. Selain itu untuk dapat membangun sebuah objek 3D (tiga dimensi) pada WebGL, user tidak perlu menginstal plug-in terlebih dahulu. Teknologi WebGL berawal dari pengembangan OpenGL ES 2.0. Beberapa contoh pengembangan OpenGL antara lain berbasis web, real-time rendering yang memungkinkan pembuatan tiga dimensi (3D) di web, visualisasi scientific dan medical imaging. Pembuatan rendering grafik komputer pada WebGL dapat dibuat dengan hanya menggunakan javascript, web browser, serta HTML5 canvas. WebGL merupakan library grafis yang merupakan standar untuk grafik tiga dimensi (3D) di web browser yang memungkinkan browser untuk membuat adegan tiga dimensi (3D). Elemen yang menyusun bagian dari adegan tiga dimensi (3D) didownload dari server, akan tetapi semua proses untuk mendapatkan gambar dilakukan secara lokal menggunakan hardware grafis client. Beberapa komponen aplikasi WebGL yaitu (Wicaksono, 2012):
Universitas Sumatera Utara
12
- Canvas
: tempat komponen objek yang akan diletakkan dan merupakan
elemen standar HTML5 yang dapat diakses menggunakan Document Object Model (DOM) melalui JavaScript. - Object
: entitas 3D yang membentuk bagian dari adegan itu.
- Lights
: pencahayaan dalam 3D.
- Camera
: berfungsi sebagai viewport (untuk melihat dan mengeksplorasi
adegan 3D dalam canvas) Menurut Demeuse, J. (2013), dalam WebGL terdapat : mesh, camera, dan lighting.
2.8. HTML5 HTML5 adalah iterasi dari HTML(HyperText Markup Language). HTML pertama kali distandarisasi tahun 1993 dan digunakan pada World Wide Web. HTML digunakan untuk menentukan isi dari suatu halaman web dengan menggunakan tag “< >”. HTML5 Canvas adalah sebuah area bitmap pada layar yang dapat dimanipulasi menggunakan JavaScript dengan cara me-render pixel pada canvas di layar. Dasar HTML5 Canvas API (Application Program Interface) mencakup konteks 2D (dua dimensi) yang memungkinkan programmer menggambar berbagai bentuk, text render, dan menampilkan gambar langsung ke area tertentu dari jendela browser serta dapat menerapkan warna, rotasi, transparansi alpha, manipulasi pixel dan berbagai jenis garis, kurva, dan kotak untuk mendapatkan bentuk, teks dan gambar yang ditempatkan ke canvas (Fulton, S & Fulton, J. 2011).
2.9. JavaScript JavaScript pertama kali muncul pada tahun 1995. Tujuan utamanya adalah untuk menangani beberapa validasi input yang sebelumnya pernah diserahkan kepada bahasa server-side seperti Pearl. Pada saat itu sebuah round-trip ke server diperlukan untuk menentukan apakah sebuah field yang diperlukan memang berisi kosong atau nilai yang dimasukkan ke dalam field tidak valid. Netscape Navigator berusaha untuk mengubahnya dengan pengenalan JavaSript. Kemampuan untuk mengatasi beberapa validasi dasar pada client merupakan fitur baru yang menarik pada saat penggunaan modem telepon telah meluas. Sejak saat itu JavaScript berkembang menjadi sebuah fitur yang penting dari setiap web browser di market. Tidak hanya terikat untuk
Universitas Sumatera Utara
13
validasi data sederhana, JavaScript saat ini telah berinteraksi dengan hampir semua window browser dan isinya (Zakas, N.C. 2012).
2.9.1. Library Beberapa library yang dapat digunakan pada WebGL yaitu : O3D, GLGE, Three.js, Curve3D, CubicVR, CopperLicht, Kuda, OSGJS, PhiloGL, SceneJS, SpiderGL dan TDL (Diggins, C. 2011). Dari antara beberapa library tersebut, penulis memilih untuk menggunakan Three.js. Three.js adalah sebuah library JavaScript API (Application Program Interface) yang digunakan untuk membuat dan menampilkan animasi komputer grafis tiga dimensi (3D) pada sebuah web browser. Skrip Three.js dapat digunakan bersama dengan HTML5 canvas, SVG atau WebGL.
2.10. Penelitian Terdahulu Beberapa penelitian terdahulu tentang penyusunan barang, yaitu dapat dilihat pada tabel 2.1. Tabel 2.1. Penelitian Terdahulu Peneliti (Tahun)
Judul Penelitian
Keterangan
Gunadi, K.,
Optimasi Pola
Julistiono, I.K. &
Penyusunan
yang optimal pada pola penyusunan
Hariyanto, B.
Barang dalam
barang dalam kontainer dengan input
(2003)
Ruang Tiga
spesifikasi ruang dan barang serta
Dimensi
probabilitas ketiga operator algoritma
menggunakan
genetik (operator reproduksi, pindah
Metode Genetic
silang dan mutasi).
Algorithms
bertujuan untuk mendapatkan solusi
Dalam penelitian ini suatu pola dikatakan optimal ketika semakin sedikit ruang kosong yang tersisa.
Universitas Sumatera Utara
14
Tabel 2.1. Penelitian Terdahulu (lanjutan) Peneliti (Tahun)
Judul Penelitian
Keterangan
Putmawa, F. &
Pengembangan
Santosa, B.
Algoritma Bee
kontainer dalam kapal dengan aturan
(2011)
Swarm Optimization
penyusunan: kontainer yang berat
untuk Penyelesaian
diletakkan di bawah kontainer yang
Container Stowage
ringan dan penyusunan kontainer
Problem
harus sesuai (sama) tipe dan
menyelesaikan masalah penyusunan
ukurannnya dengan mempertimbangkan keseimbangan kapal.
penelitian ini menghasilkan waktu pembongkaran (penyusunan ulang barang) yang lebih minimum.
Angga, C. &
Pengembangan
Munir, R. (2012)
Algoritma Greedy
atau penataan peti kemas pada suatu
untuk Optimalisasi
kapal pengangkut didasari algoritma
Penataan Peti Kemas
greedy agar proses bongkar muat
pada Kapal
dapat dilakukan dengan efisien serta
Pengangkut
tidak mengganggu stabilitas kapal
membantu pembuatan stowage plan
pengangkut. Data yang digunakan merupakan
berat
dan
ukuran
standard peti kemas sesuai dengan stardard
ISO
(International
Organization for Standarization).
output
dari
aplikasi
ini
akan
menampilkan tabel data letak barang serta tujuan barang yang akan dikirim.
Universitas Sumatera Utara
15
Tabel 2.1. Penelitian Terdahulu (lanjutan) Peneliti (Tahun)
Judul Penelitian
Keterangan
Hambali, A.
Sistem Alokasi
(2011)
Penyimpanan
mengalokasikan urutan barang yang
Barang Pada Gudang
masuk ke dalam gudang secara
membuat sebuah sistem yang dapat
optimal sehingga dapat menghemat ruang
dengan
menggunakan
algoritma semut.
menggunakan parameter panjang, lebar, tinggi serta panjang line gudang.
Hasil
dari
penelitian
tersebut berupa blok diagram dengan nilai β = 2 (performa hasil yang terbaik) dan nilai β = 0,5 (performa hasil paling buruk).
Lim, R., Gunadi,
Optimasi
K & Gang, O.W.
Pengambilan dan
menampilkan tata letak barang yang
(2004)
Penataan Ulang
disimpan dalam palet-palet pada rak
Barang di Gudang
di gudang secara 2 dimensi dan 3
dengan Penerapan
dimensi
Stack menggunakan
OpenGL serta algoritma genetik.
Metode Genetic Algorithm
membuat
aplikasi
dengan
untuk
menggunakan
parameter yang digunakan yaitu batas
minimum
dan
maksimum
ukuran gudang, ukuran dan jumlah rak, ukuran dan jumlah palet serta ukuran barang. Hasil uji penelitian tersebut menunjukkan nilai rata-rata fitness cost diatas 90%.
Universitas Sumatera Utara
16
Tabel 2.1. Penelitian Terdahulu (lanjutan) Peneliti (Tahun) Henry (2011)
Judul Penelitian Penerapan Teknologi
Keterangan
membuat web penjualan ikan yang
WebGL pada Virtual
dibuat dalam objek 3D dengan
Aquarium
memanfaatkan animasi.
Berbasis
Tiga Dimensi (3D)
dalam pembuatan aplikasi ini penulis menggunaan HTML5 dan WebGL. Hasil
dari
penelitian
ini
yaitu
menampilkan gambar serta bentuk ikan 3D serta dapat menampilkan format
audio
dan
video
pada
halaman web tanpa menggunakan plug-in. Suhardi, D., et al
Pembuatan Simulasi
(2012)
Pergerakan
Objek
membuat
sebuah
simulasi
pergerakan objek 3D (tiga dimensi)
3D (Tiga Dimensi)
menggunakan
Menggunakan
compile menggunakan C++.
OpenGL.
hasil
dari
OpenGL
aplikasi
ini
yang
di
berupa
simulasi pesawat terbang.
Universitas Sumatera Utara
