BAB 2 LANDASAN TEORI
2.1 2.1.1
Problem Solving dan Algoritma Definisi Problem Solving Istilah problem solving sering digunakan dalam berbagai bidang ilmu dan
memiliki pengertian yang berbeda-beda pula. Tetapi problem solving dalam matematika memiliki kekhasan tersendiri. Secara garis besar terdapat tiga macam interpretasi istilah problem solving dalam pembelajaran matematika, yaitu problem solving sebagai tujuan (as a goal), problem solving sebagai proses (as a process), dan problem solving sebagai keterampilan dasar (as a basic skill). (Branca, N. A. dalam Krulik, S. & Reys, R. E., 1980:3-6). 1.
Problem solving sebagai tujuan
Para pendidik, matematikawan, dan pihak yang menaruh perhatian pada pendidikan matematika seringkali menetapkan problem solving sebagai salah satu tujuan pembelajaran matematika. Bila problem solving ditetapkan atau dianggap sebagai tujuan pengajaran maka ia tidak tergantung pada soal atau masalah yang khusus, prosedur, atau metode, dan juga isi matematika. Anggapan yang penting dalam hal ini adalah bahwa pembelajaran tentang bagaimana menyelesaikan masalah (solve problems) merupakan “alasan utama” (primary reason) belajar matematika.
10
2. Problem solving sebagai proses Pengertian lain tentang problem solving adalah sebagai sebuah proses yang dinamis.
dalam aspek ini, problem solving dapat diartikan sebagai proses
mengaplikasikan segala pengetahuan yang dimiliki pada situasi yang baru dan tidak biasa. Dalam interpretasi ini, yang perlu diperhatikan adalah metode, prosedur, strategi dan heuristik yang digunakan siswa dalam menyelesaikan suatu masalah. Masalah proses ini sangat penting dalam belajar matematika dan yang demikian ini sering menjadi fokus dalam kurikulum matematika. Sebenarnya, bagaimana seseorang melakukan proses problem solving dan bagaimana seseorang mengajarkannya tidak sepenuhnya dapat dimengerti. Tetapi usaha untuk membuat dan menguji beberapa teori tentang pemrosesan informasi atau proses problem solving telah banyak dilakukan. Dan semua ini memberikan beberapa prinsip dasar atau petunjuk dalam belajar problem solving dan aplikasi dalam pengajaran. 3. Problem solving sebagai keterampilan dasar Terakhir, problem solving sebagai keterampilan dasar (basic skill). Pengertian problem solving sebagai keterampilan dasar lebih dari sekedar menjawab tentang pertanyaan: apa itu problem solving? Beberapa yang dikemukakan antara lain keterampilan berhitung, keterampilan aritmetika, keterampilan logika, keterampilan “matematika”, dan lainnya. Satu lagi yang baik secara implisit maupun eksplisit sering diungkapkan adalah keterampilan problem solving.
11
2.1.2
Pengertian Algoritma Algoritma adalah kumpulan urutan perintah yang menentukan operasi-operasi
tertentu yang diperlukan untuk menyelesaikan suatu masalah ataupun mengerjakan suatu tugas tertentu. Algoritma merupakan urutan langkah instruksi yang logis. Setiap langkah instruksi mengerjakan suatu tindakan aksi. Apabila suatu aksi dilaksanakan, maka operasi atau sejumlah operasi yang bersesuaian dengan aksi itu dikerjakan oleh pemroses. Bila data yang digunakan benar, maka algoritma akan selalu berhenti dengan memberikan hasil yang benar pula. Pembuatan algoritma harus selalu dikaitkan dengan : a. kebenaran algoritma, yakni bila program selesai maka hasilnya juga benar b. kompleksitas, lama dan jumlah waktu proses dan penggunaan memori. Ciri dari algoritma: •
tepat sasaran
•
fleksibel dan portable
•
bersih dari kesalahan system ataupun logika
•
murah dan efisien
•
cepat waktu
•
didokumentasikan
12
2.1.3 Definisi Algoritma Beberapa definisi dari kata Algoritma adalah sebagai berikut: a.
Kamus Besar Bahasa Indonesia Algoritma adalah urutan logis pengambilan keputusan untuk pemecahan
masalah. b.
Abu Ja’far Muhammad Ibnu Musa Al-Khwarizmi Algorima adalah langkah - langkah logis penyelesaian masalah yang disusun
secara sistematis dan logis. c.
Goodman Hedetniemi Algoritma adalah urutan-urutan terbatas dari operasi yang terdefinisi dengan
baik, yang masing-masin membutuhkan memory dan waktu yang terbatas untuk menyelesaikan suatu masalah. 2.1.4
Sifat Algoritma Sifat-sifat dari algoritma adalah : Input Sifat ini berarti algoritma harus memiliki kondisi awal sebelum dilaksanakan. Output Sifat ini berarti algoritma menghasilkan suatu keluaran setelah dilaksanakan. Definitif Sifat ini berarti langkah – langkah dari algoritma sudah terdefinisi secara jelas.
13
Finit Sifat ini berarti algoritma melakukan langkah yang terbatas jumlahnya dalam mengolah input menjadi output. Efektif Sifat ini berarti algoritma dapat memberi sebuah solusi sesuai harapan. General Sifat ini berarti algoritma berlaku untuk setiap himpunan input. 2.2
Artificial Intelligince Dewasa ini Artificial Intelligince (AI) banyak menarik minat dan perhatian dari
masyarakat luas. Menurut Kusumadewi (2003, pl), AI adalah salah satu bagian ilmu komputer yang membuat agar komputer dapat melakukan pekerjaan seperti dan sebaik yang dilakukan oleh manusia. Pada awal diciptakannya, komputer hanya dipakai sebagai alat hitung saja. Namun, seiring perkembangan jaman maka peran komputer semakin mendominasi kehidupan umat manusia. Manusia bisa menjadi pandai dalam menyelesaikan suatu persoalan karena manusia mempunyai pengehtahuan dan disertai pengalaman. Pengehtahuan diperoleh dari belajar. Semakin banyak bekal pengehtahuan yang dimiliki seseorang, maka orang tersebuat diharapkan dapat lebih mampu dalam menyelesaikan suatu persoalan. Agar komputer pun dapat bertindah seperti dan sebaik manusia, maka komputer juga harus diberi bekal pengehtahuan dan mempunyai kemampuan untuk berpikir. Pada AI, komputer dibekali beberapa metode yang diharapkan agar komputer dapat menjadi benda yang pintar.
14
2.2.1
Sejarah Artificial Intelligince Program AI pertama yang bekerja ditulis pada 1951, yang saat itu
digunakan untuk menjalankan mesin Ferranti Mark I di University of Manchenster: yaitu sebuah program permainan yang ditulis oleh Christopher Strachey dan program permainan catur yang ditulis oleh Dietrich Prinz. John McCarthy membuat istilah "kecerdasan buatan" pada konferensi pertama yang disediakan untuk pokok persoalan ini pada 1956, John McCarthy juga menemukan bahasa pemrograman Lishp. Sedangkan Alan Turing memperkenalkan "Turing Test" sebagai sebuah cara untuk mengoperasionalkan tes perilaku cerdas. Joseph Weizenbaum membangun ELIZA, sebuah chatterbor yang menerapkan psikoterapi Rogerian. Selama tahun 1960-an dan 1970-an, Joel Moses mendemonstrasikan kekuatan pertimbangan simbolis untuk mengintegrasikan masalah dalam program Macsyma, program berbasis pengehtahuan yang sukses pertama kali dalam bidang matematika. Marvin Minsky dan Seymour Papert menerbitkan Perceptrons, yang mendemonstrasikan batas jaringan syaraf sederhana dan Alain Colmerauer mengembangkan bahasa komputer Prolog. Ted Shortliffe mendemonstrasikan kekuatan sistem berbasis aturan untuk representasi pengehtahuan dan inferensi dalam diagnosa serta terapi medis yang kadang kala disebut sebagai sistem pakar pertama. Hans Moravece mengembangkan kendaraan terkendali komputer pertama yang dapat mengatasi jalan berlintang secara mandiri. Pada tahun 1980-an, jaringan syaraf digunakan secara meluas dengan algoritma pembuatan balik, yang pertaman kali diterangkan oleh Paul John Werbos pada 1974. Di tahun 1990-an sebuah prestasi besar dalam bidang AI ditandai dengan
15
munculnya Deep Blue, sebuah komputer pemain catur yang mengalahkan Garry Kasparov dalam pertandingan enam ronde yang terkenal pada tahun 1997. Perkembangan ini terus berlanjut hingga kini. 2.2.2
Definisi Artificial Intelligence a. Menurut Winston dan Prendergast (1984): "Kecerdasan buatan (Artificial Intelligence) adalah sebuah mesin yang lebih pintar, lebih bermanfaat dan dapat memahami apa itu kecerdasan" b. Menurut H.A.Simon (1987) “Kecerdasan buatan (Artificial Intelligence) merupakan kawasan penelitian, aplikasi dan instruksi yang terkait dengan pemrograman komputer untuk melakukan sesuatu hal yang dalam pandangan manusia adalah cerdas" c. Menurut Rich dan Knight (1991) "Kecerdasan buatan (Artificial Intelligence) merupakan sebuah studi tentang bagaimana membuat komputer melakukan hal - hal yang pada saat ini dapat dilakukan lebih baik oleh manusia" d. Menurut Kusumadewi (2003) "Kecerdasan buatan (Artificial Intelligence) adalah salah satu bagian ilmu komputer yang membuat agar komputer dapat melakukan pekerjaan seperti dan sebaik yang dilakukan oleh manusia"
16
2.2.3
Bidang – Bidang Kecerdasan Buatan a.
Sistem Pakar (Expert System) Sistem pakar adalah program komputer yang didesain untuk berlaku
sebagai seorang ahli dalam suatu bidang khusus. Namun sekarang sistem pakar biasanya hanya digunakan untuk membantu para ahli dalam memecahkan suatu masalah. b.
Natural Language Processing (NLP) Natural Language Processing adalah komputer yang dimaksudkan untuk
mengenal makna dari bentuk kalimat berbeda-beda. Selain mampu mengerti bahasa sehari-hari, NLP juga mencakup kemampuan membentuk kalimat dalam bahasa sehari-hari. c.
Pengenalan Pola Recognition adalah program komputer yang ditujukan untuk mengenali
suatu objek. Contohnya dalam Speech Recognation, komputer dapat mengenali suara, dan sekaligus bias membedakan berbagai macam bentuk sinyal. Contoh lain dalam Character Recognation, komputer dapat mengenali karakter, sekaligus dapat membedakan berbagai macam bentuk karakter. d.
Computer Vision Ilmu pengetahuan dan teknologi komputer yang berkaitan dengan
pengolahan citra komputer seakan dapat melihat benda, terkait dengan teori untuk membangun suatu sistem yang terdiri dari gambar. Contoh yang sering digunakan adalah pendeteksian plat nomor kendaraan.
17
e.
Robotic Mesin
yang
diprogram
untuk
melakukan
tugas-tugas
mekanik,
berintelegensi dan dapat member respon terhadap perubahan lingkungan. Contohnya adalah Asimo dan Aibo. f.
Automatic Programming Komputer yang dapat membuat program sendiri dan menyesuaikan dengan
spesifikasi yang dinginkan oleh pemrogram. g.
Planning and Decission Support Komputer yang memiliki kemampuan khusus untuk membantu manajer
dalam membuat perancanaan dan pengambilan keputusan. h.
Soft Computing Soft Computing adalah koleksi dari beberapa metodologi yang bertujuan
untuk mengeksploitasi adanya toleransi terhadap ketidaktepatan, ketidakpastian dan kebenaran parsial untuk dapat diselesaikan dengan mudah, kuat, dan biaya penyelesaiannya murah. Definisi ini pertama kali diungkapkan oleh Prof. Lofti Zadeh pada tahun 1992. Soft Computing merupakan inovasi baru dalam membangun sistem cerdas. Sistem cerdas ini merupakan sistem yang memiliki keahlian seperti manusia pada domain tertentu, mampu beradaptasi dan belajar agar dapat bekerja lebih baik jika terjadi perubahan lingkungan.
18
2.3
SDLC(System Development Life Cycle) SDLC adalah tahapan-tahapan pekerjaan yang dilakukan oleh analis sistem dan
programmer dalam membangun sistem informasi. Ada beberapa model SDLC. Model yang cukup populer dan banyak digunakan adalah waterfall. Model yang digunakan pada penulisan skripsi ini adalah dengan model waterfall. Model ini adalah model yang muncul pertama kali yaitu sekitar tahun 1970 sehingga sering dianggap kuno, tetapi merupakan model yang paling banyak dipakai didalam Software Engineering (SE). Model ini melakukan pendekatan secara sistematis dan urut mulai dari level kebutuhan sistem lalu menuju ke tahap analisis, desain, coding, testing / verification, dan maintenance. Disebut dengan waterfall karena tahap demi tahap yang dilalui harus menunggu selesainya tahap sebelumnya dan berjalan berurutan. Sebagai contoh tahap desain harus menunggu selesainya tahap sebelumnya yaitu tahap requirement. Secara umum tahapan pada model waterfall dapat dilihat pada gambar 2.1.
Gambar 2. 1 Waterfall - Model
19
Gambar di atas adalah tahapan umum dari waterfall model menurut Roger S. Pressman (1997). Model ini memberikan pendekatan-pendekatan sistematis dan berurutan bagi pengembangan piranti lunak. Berikut adalah penjelasan dari tahap-tahap yang dilakukan di dalam model ini menurut Pressman:
1. System / Information Engineering and Modeling Permodelan ini diawali dengan mencari kebutuhan dari keseluruhan sistem yang akan diaplikasikan ke dalam bentuk software. Hal ini sangat penting, mengingat software harus dapat berinteraksi dengan elemen - elemen yang lain seperti hardware, database, dsb. Tahap ini sering disebut dengan Project Definition. 2. Analisa Kebutuhan Proses pencarian kebutuhan diintensifkan dan difokuskan pada software. Untuk mengetahui sifat dari program yang akan dibuat, maka para software engineer harus mengerti tentang domain informasi dari software, misalnya fungsi yang dibutuhkan, user interface, dsb. Dari 2 aktivitas tersebut (pencarian kebutuhan sistem dan software) harus didokumentasikan dan ditunjukkan kepada pelanggan. 3. Design Proses ini digunakan untuk mengubah kebutuhan-kebutuhan diatas menjadi representasi ke dalam bentuk “blueprint” software sebelum coding dimulai. Desain harus dapat mengimplementasikan kebutuhan yang telah disebutkan pada tahap sebelumnya. Seperti 2 aktivitas sebelumnya, maka proses ini juga harus didokumentasikan sebagai konfigurasi dari software.
20
4. Coding Untuk dapat dimengerti oleh mesin, dalam hal ini adalah komputer, maka desain tadi harus diubah bentuknya menjadi bentuk yang dapat dimengerti oleh mesin, yaitu ke dalam bahasa pemrograman melalui proses coding. Tahap ini merupakan implementasi dari tahap design yang secara teknis nantinya dikerjakan oleh programmer. 5. Testing / Verification Sesuatu yang dibuat haruslah diujicobakan. Demikian juga dengan software. Semua fungsi - fungsi software harus diujicobakan, agar software bebas dari error, dan hasilnya harus benar-benar sesuai dengan kebutuhan yang sudah didefinisikan sebelumnya. 6. Maintenance Pemeliharaan suatu software diperlukan, termasuk di dalamnya adalah pengembangan, karena software yang dibuat tidak selamanya hanya seperti itu. Ketika dijalankan mungkin saja masih ada errors kecil yang tidak ditemukan sebelumnya, atau ada penambahan fitur-fitur yang belum ada pada software tersebut. Pengembangan diperlukan ketika adanya perubahan dari eksternal perusahaan seperti ketika ada pergantian sistem operasi, atau perangkat lainnya. 2.4
Perancangan Basis Data Basis data atau database menurut Connolly (2002,p14) adalah kumpulan data
yang dihubungkan secara bersama-sama, dan gambaran dari data yang dirancang untuk memenuhi kebutuhan informasi dari suatu organisasi. Berbeda dengan sistem file yang
21
menyimpan data secara terpisah, data pada basis data tersimpan secara terintegrasi. Basis data bukan menjadi milik dari suatu departemen tetapi sebagai sumber daya perusahaan yang dapat digunakan bersama. Banyak terdapat aplikasi yang mengatur manajemen basis data, diantaranya SQL dan Micorosft Access. Ada kalanya suatu program aplikasi memerlukan basis data untuk mendukungnya. Basis data diperlukan jika data yang dimiliki terlalu banyak jumlahnya, atau apabila pengguna ingin melakukan fungsi menambahkan, mengubah, atau menghapus data yang akan digunakan dalam menjalankan program aplikasi. 2.5
IMK(Interaksi Manusia dan Komputer) Menurut Shneiderman (2005, p74 – 75), sebuah sistem berbasis komputer selalu
mempunyai elemen manusia yang terkait di dalamnya. Elemen manusia ini berinteraksi langsung dengan perangkat keras dan perangkat lunak melalui perantara sebuah antarmuka (interface). Penggunaan delapan aturan emas berasal dari prinsip – prinsip yang didapatkan dari pengalaman dan direvisi selama lebih dari 2 dekade. Aturan delapan emas yaitu : Berusaha untuk konsisten Urutan aksi yang konsisten diperlukan pada situasi yang sama. Konsistensi juga harus digunakan pada prompt, menu, layar bantu. Warna tampilan, kapitalisasi, huruf dan sebagainya juga harus konsisten. Memungkinkan penggunaan shortcut Menambahkan feature untuk pemakai yang sudah ahli (seperti penjelasan, shortcut) bisa memperkaya desian interface dan meningkatkan kualitas sistem.
22
Memberikan umpan balik yang informatif Untuk setiap tindakan yang dilakukan pemakai, diharapkan adanya respon dari sistem. Untuk tindakan yang sering terjadi dan tidak membutuhkan banyak aksi, respon yang ada bisa dibuat secara sederhana, sedangkan tindakan yang jarang dilakukan dan membutuhkan banyak aksi harus lebih ditonjolkan.
Merancang dialog yang memberikan penutupan Urutan aksi harus disusun ke dalam kelompok awal, tengah, dan akhir. Suatu umpan balik yang informatif pada akhir pekerjaan sebaiknya dibuat untuk mengindikasikan bahwa pekerjaan telah selesai dan siap untuk melanjutkan ke aksi berikutnya. Memberikan pencegahan kesalahan dan penanganan kesalahan sederhana Sebisa mungkin dibuat sistem yang tidak akan menghasilkan kesalahan yang serius jika digunakan oleh pemakai. Jika pemakai membuat kesalahan, sistem tersebut harus dapat mendeteksi kesalahan dan menawarkan instruksi yang sederhana, konstruktif, dan spesifik untuk perbaikan. Memungkinkan pembalikan aksi yang mudah Aksi yang telah dilakukan harus dapat dikembalikan ke keadaan awal. Mendukung pusat kendali internal Menjadikan pemakai sebagai pemberi aksi, bukan sebagai orang yang merespon aksi. Mengurangin beban ingatan jangka pendek
23
Karena keterbatasan manusia dalam pemrosesan informasi pada ingatan jangka pendek, sebaiknya tampilan dibuat sederhana, beberapa halaman dijadikan satu, dan harus ada waktu yang cukup untuk mempelajari kode, singkatan, serta urutan aksi. Informasi seperti singkatan atau kode sebaiknya juga tersedia. 2.6
UML (Unified Modelling Language) Menurut Whitten (2004, p408) UML adalah suatu konvensi pemodelan yang
digunakan untuk menentukan atau menggambarkan sebuah sistem piranti lunak yang terkait dengan objek. UML terdiri dari berbagai tipe diagram, antara lain : (Joseph Schmuller, 1999) •
Flowchart Flowchart merupakan gambar atau bagan yang memperlihatkan urutan dan hubungan antar proses beserta instruksinya. Gambaran ini dinyatakan dengan simbol. Dengan demikian setiap simbol menggambarkan proses tertentu. Sedangkan hubungan antar proses digambarkan dengan garis penghubung. Flowchart ini merupakan langkah awal pembuatan program. Dengan adanya flowchart urutan poses kegiatan menjadi lebih jelas. Setelah flowchart selesai disusun, selanjutnya pemrogram (programmer) menerjemahkannya ke bentuk program dengan bahasa pemrograman. Pada gambar 2.2 dapat dilihat contoh bagan flowchart dari cara peminjaman buku.
24
Gambar 2. 2 Contoh Flowchart Peminjaman buku
• Use Case Diagram Use Case Diagram secara grafis menggambarkan interaksi antara sistem, sistem eksternal dan pangguna. Dengan kata lain, secara grafis mendeskripsikan siapa yang akan menggunakan sistem dan dalam cara apa pengguna mengharapkan interaksi dengan sistem itu. Use case adalah sebuah deskripsi dari
25
tingkah laku sebuah sistem yang dilihat dari sudut pandang user. Bagi para pengembang, ini adalah tool yang sangat berharga : sebuah teknik tried – and – true yang dipakai untuk mengumpulkan persyaratan sebuah sistem yang dilihat dari sudut pandang user. Teknik pengumpulan tersebut penting jika tujuannya adalah untuk membangun sebuah sistem yang bisa digunakan semua orang (bukan hanya orang yang terbiasa dengan komputer) seperti pada contoh gambar 2.3.
Gambar 2. 3 Contoh Use Case Diagram
•
Sequence Diagram Sequence Diagram secara grafis menggambarkan bagaimana objek berinteraksi satu sama lain melalui pesan pada eksekusi sebuah use case atau operasi. Diagram ini mengilustrasikan bagaimana pesan terkirim dan diterima diantara objek dan dalam urutan apa.
26
Sequence Diagram digambarkan sebagai interaksi dari 2 grafik dimensional. Dimensi vertikal merupakan sumbu waktu, yang berjalan makin ke bawah.
Dimensi
horizontal
menggambarkan
peranan
classifier
yang
menampilkan objek individual di dalam kolaborasi. Tiap peranan classifier digambarkan dengan kolom vertikal – sebagai lifeline. Dalam waktu selama objek ada, peranan dari object tersebut digambarkan dengan garis putus – putus. Selama aktivasi prosedur pada sebuah object masih aktif, lifeline digambarkan dengan garis ganda (double line). Pesan ditunjukkan dengan gambar anak panah (arrow) dari lifeline suatu object menuju object yang lainnya. Anak panah tersebut diatur menurun sesuai urutan waktu di dalam diagram. Sequence diagram menunjukkan interaksi yang dinamis berdasarkan waktu. Sebagai contoh terdapat mesin cuci, komponen mesin tersebut meliputi pipa air (untuk masuknya air bersih), sebuah drum (tempat menampung 18 pakaiannya), dan sebuah saluran (untuk membuang air kotor). Itu semua tentu saja merupakan object. Apa yang akan terjadi jika kita menyertakan sebuah use case mesin cuci? Asumsikan “tambah pakaian”, “tambah deterjen”, dan “nyalakan” sudah dioperasikan semua, urutan langkah – langkahnya yang terjadi seperti ini: 1. Air memasuki drum melalui pipa air 2. Drum berputar secara konstan selama lima menit 3. Air berhenti masuk 4. Drum dengan arah kebalikan sebanyak empat kali selama lima belas menit
27
5. Air yang berbusa keluar melalui saluran 6. Air bersih kembali dimasukkan 7. Drum tetap berputar dengan arah kebalikan 8. Air berhenti masuk 9. Air untuk membilas keluar melalui saluran 10. Putaran drum menjadi hanya satu arah dan bertambah cepat selama lima menit 11. Drum berhenti berputar dan cucian sudah selesai Sequence diagram dari cara kerja mesin cuci dapat dilihat pada gambar 2.4.
28
Gambar 2. 4 contoh sequence diagram
2.7
Fast Genetic K-Means Algorithm (FGKA) Fast Genetic K-Means Algorithm adalah penggabungan algoritma Algoritma
Genetik dan Algoritma Clustering Kmeans. Kemunculan algoritma gabungan ini dilakukan oleh Yi Lu, Shiyong Lu, dan Farshad Fotouhi di tahun 2004. Mereka terinspirasi atas Genetik K-Means Algorithm (GKA) diusulkan oleh Krishna dan Murty
29
di tahun 1999. Perbedaan kedua algoritma adalah waktu kecepatan yang dipakai untuk mendapatkan hasil nilai keakuratan perbandingan beberapa gambar. FGKA dimulai dengan fase inisialisasi, yang menghasilkan populasi awal P0. Populasi pada generasi berikutnya Pi +1 diperoleh dengan menerapkan operator genetik berikut berurutan: seleksi, mutasi dan operator K-Means pada Pi populasi saat ini. Evolusi berlangsung sampai kondisi penghentian tercapai. Fase inisialisasi awal secara acak menghasilkan populasi P0 solusi Z yang mungkin berakhir dengan ilegal string. Pada pengecekan pertama string yang ilegal tidak diinginkan. Untuk alasan ini dari algoritma GKA dibuat upaya yang signifikan untuk menghilangkan string ilegal. String ilegal apapun diizinkan di FGKA, tetapi tetap dianggap sebagai solusi yang paling tidak diinginkan, dan oleh TWCVs mereka didefinisikan sebagai + ∞ dan penugasan untuk mereka dengan nilai fitness yang lebih rendah. Fleksibilitas ini yang memungkinkan string ilegal dalam proses evolusi menghindari overhead dari string illegal eliminasi, dan dengan demikian meningkatkan kinerja waktu algoritma. 2.8
Metode Pencarian Gambar Ada tiga tahapan utama dalam pencarian gambar ini, yaitu ekstraksi fitur,
klastering dan matching (pencocokan). Ekstraksi fitur adalah proses pengambilan histogram dan hasil gabor, baik dari gambar database maupun gambar query. Klastering adalah proses untuk mengelompokkan data-data yang mempunyai kemiripan. Sedangkan matching (pencocokan), adalah proses pembandingan antara gambar query dengan gambar dalam database.
30
2.8.1
Ekstrasi Fitur Ekstraksi fitur adalah proses pengambilan histogram (warna) serta nilai mean
dan standard deviasi (untuk fitur tekstur), baik dari gambar database maupun gambar query. Diagram urutan ekstrasi fitur dapat dilihat pada gambar 2.5.
Gambar 2. 5 Diagram Blok Ekstrasi Warna
Tahap ini terdiri dari beberapa sub tahapan, yaitu: a. Pengambilan nilai RGB tiap pixel yang kemudian langsung dikonversi ke HSV. b. Kuantisasi warna dari yang semula berjumlah (360 x 255 x 255) atau 23409000 kemungkinan warna, diubah menjadi (4 x 4 x 4) atau 64 kemungkinan warna. Dengan cara ini, nilai H berkisar antara 0 sampai dengan 3, S berkisar antara 0 sampai dengan 3, dan V berkisar antara 0 sampai dengan 3. c. Normalisasi.
31
d. Pembuatan HSV Histogram. Pada langkah ini juga dilakukan pembuatan Thumbnails yang berguna untuk menampilkan hasil pencarian dalam bentuk icon. 2.8.2
Klastering Tahap ini merupakan implementasi dari algoritma FGKA untuk melakukan
klasterisasi terhadap sejumlah HSV histogram yang di combine dengan nilai hasil filter gabor, sesuai dengan kedekatan jarak (kemiripan) antara gambar-gambar. Langkah – langkah urutan klastering dapat dilihat pada gambar 2.6.
Gambar 2. 6 Diagram Blok FGKA
32
Berikut ini 3 operator genetic yang akan digunakan dalam mencari potongan gambar dari puzzle yang memiliki nilai kecocokan tertinggi. Operator Seleksi Seleksi yang dipakai adalah seleksi yang disebut proporsional untuk seleksi operator yang dimana populasi generasi berikutnya ditentukan oleh Z percobaan acak independen. Setiap percobaan secara acak memilih solusi dari arus populasi {S1, S2, ..., Sz} sesuai dengan distribusi probabilitas. Probabilitas {p1, p2, ..., pz} didefinisikan oleh.
dimana F (Sz) menunjukkan
nilai fitness dari solusi Sz. Dari probabilitas ini, kemudian dilakukan penyeleksian menggunakan Roullete Wheel yaitu kromosom dengan probabilitas yang tinggi akan bertahan untuk ikut diproses dalam operator selanjutnya. (Wulansari,2010) Dan
= Dimana TWCVmax adalah TWCV maksimum yang telah ditemui sampai
generasi sekarang, Fmin adalah nilai string legal dengan fitness terkecil dalam populasi saat ini jika mereka ada, jika tidak ada maka dianggap Fmin = 1. The Mutation Operator Pada operator ini, tiap kromosom dikodekan dengan a1 a2 ... aN dan operator mutasi melakukan mutasi pada suatu gen an (n = 1...N) dengan nilai baru an’ dengan sejumlah 0 < MP < 1 sebagai parameter yang dimasukkan oleh pengguna. Nilai tersebut dinamakan probabilitas mutasi. Mutasi dilakukan dengan
33
an’ yang dipilih secara random dari {1, 2, .. ,K) dengan distribusi (p1, p2, ..., pZ) yang didefinisikan dengan rumus sebagai berikut :
dimana d (Xn, ck) adalah jarak Euclidean antara pola Xn dengan titik pusat ck dari cluster yang ke k, dan dmax(Xn) = max{d(Xn,Ck)}. Jika cluster k kosong, maka d (Xn, ck) didefinisikan sebagai 0. Bias 0.5 diperkenalkan untuk menghindari kesalahan pembagian dengan angka 0. (Wulansari,2010) The K-means Operator Operator K-Means ini digunakan untuk mempercepat konvergensi. Solusi yang ada dikodekan dengan a1 a2 ... aN. Operator ini akan mengganti isi dari gen an (n = 1...N) dengan nilai baru an., dimana nilai yang baru merupakan klaster dengan jarak terpendek dari data an yang dihitung menggunakan rumus Euclidean. 2.8.3
Matching Setelah proses klastering selesai dilakukan, maka tiap klaster tersebut dihitung
nilai gabungan antara histogram dengan nilai gabor rata-ratanya (untuk dijadikan centroid). Nilai centroid - centroid ini kemudian dibandingkan dengan HSV histogram dan nilai gabor gambar query. Centroid yang memiliki jarak paling dekat merupakan solusinya. Cara yang dipakai untuk mengukur jarak antar dua histogram adalah menggunakan Euclidan distance. (Elena Deza, 2009)
34
Rumusnya: d(A,B) =
2.9
Game Game merupakan aktivitas terstruktur yang biasanya bertujuan dalam
mendapatkan kesenangan dan bahkan digunakan sebagai suatu edukasi. Namun, tidak semua permainan bertujuan seperti diatas, adapun permainan yang dijadikan suatu profesi seperti olahraga professional dan lain sebagainya. Jenis game yang ada saat ini sangat banyak, diantaranya adalah olahraga, permainan anak-anak, permainan elektronik, dan lain sebagainya.(Anonim A, 2008). 2.9.1
Computer Game Personal computer game atau biasa dikenal juga dengan computer game.
Computer game adalah game yang dimainkan secara personal dengan menggunakan komputer dan bukan pada mesin console ataupun arcade.(Anonim B, 2008). 2.9.2
Jenis-jenis Game Game biasanya dikelompokan kedalam kategori-kategori berdasarkan gameplay-
nya. Jenis game yang ada saat ini sangat banyak, dan banyak diantaranya memiliki kesamaan namum berbeda genre makan jenis game tidak selalu pasti. Berikut ini adalah jenis – jenis game yang diklasifikasikan secara umum.
35
a.
Action Jenis game yang hampir keseluruhan memerlukan konsentrasi mata dan
tangan. Membutuhkan refleks antara mata dan gerakan tangan. Pada awalnya, game action tidak berfokus pada strategi dan perhitungan dalam aksi, namun game action saat ini telah mengadopsi cerita dan kebutuhan strategi. b.
Strategi Jenis game yang lebih menitikberatkan manajemen dan pengendalian
suatu objek atau banyak objek dibanding respon antara tangan dan mata. Ketangkasan dalam mengatur taktik dan strategi sebelum aksi langsung sangat ditekankan dalam permainan ini dan biasanya dimulai dengan resource yang sedikit. c.
RPG (Role Playing Game) Mirip dengan strategi game, RPG memilik statistik yang banyak dan
biasanya bergantung pada pengembangan karakter. Alur permainan bergantung kepada pilihan sang pemain, begitupun dengan statistik pemain yang perkembangannya berdasarkan pilihan pemain. Pada game jenis ini terdapat banyak quest atau misi-misi yang mengharuskan pemain menjelajahi dunia pada game ini. Biasanya, game jenis ini memiliki dunia fantasi yang besar.
36
d.
Action RPG Merupakan genre terbaru dari jenis-jenis game yang ada. Kombinasi
antara RPG dengan Action, dimana ketajaman mata dan refleks tangan serta manajemen karakter pemain sangat ditekankan. Game jenis ini masih sangat jarang ditemukan, dan game jenis ini membutuhkan hardware requirement besar. Contohnya : Fallout 3, Stalker. e.
Simulation Game yang mensimulasikan sebuah objek atau proses aktivitas pada
dunia nyata. Game ini mengajak user untuk merasakan sebuah aktivitas tertentu tanpa harus melakukannya pada dunia nyata. Realita menjadi kunci utama pada game jenis ini. Contohnya : Flight Simulator, HAWX. f.
Sport Game yang kesuluruhannya mensimulasikan olahraga perseorangan
maupun kelompok. Mirip seperti simulation, game ini juga mementingkan realita. g.
Puzzle atau teka – teki Permainan jenis klasik dibanding jenis - jenis permainan lainnya.
Permainan ini tidak memerlukan kinerja berfikir yang berat. Lebih ditujukan untuk hiburan semata. Contohnya : Puzzle, susun kata dan sebagainya.
37
2.9.3
Game Design Menurut Tom Sloper (anonim10, 2008), perancangan game mempunyai format
seperti dibawah ini : a. Judul Game Judul game ini diisi dengan sebuah nama game. Judul game biasaya dibuat dengan judul yang semenarik mungkin yang bisa mencerminkan game itu. Judul biasa diperoleh dari nama tempat kejadian di permainan itu, nama kejadian, maupun pelakunya, dan lain - lain. b. Game untuk [platform game] Platform game ini diisi dengan perangkat keras yang akan digunakan untuk memainkan game tersebut, misalnya : computer, PS2, Nintendo dan lain – lain. c. Copyright 2008 [nama] Baris diatas menjelaskan tahun pembuatan game tersebut dan nama pembuat game tersebut. Nama bisa berasal dari nama tim, nama perusahaan, maupun nama pribadi. d. Informasi Umum Menjelaskan deskripsi dari permainan yang akan dibuat. Paragraf pertama harus bisa menarik minat pembaca, misalnya dengan memberikan ilustrasi dan gambar, menjelaskan poin dari gameplay.
38
e. Deskripsi Game Secara Detail 1) Konsep Dasar Konsep dasar menceritakan konsep utama dari game tersebut. 2) Latar Belakang Cerita Menceritakan sebuah cerita diawal permainan yang akan semakin berkembang seiring dengan gameplay. Latar belakang cerita idealnya adalah cerita yang menarik, seperti REAL STELL. 3) Objective Menceritakan tujuan dari game tersebut. Jelaskan secara detil untuk mencegah kesalahpahaman. 4) Gameplay Mendeskripsikan bagaimana game itu bekerja dari awal hingga akhir. Ada beberapa pertanyaan yang bisa membantu untuk mengembangkan gameplay. ¾ Bagaimana rancangan antarmuka? ¾ Bagaimana struktur dasar interaktif? ¾ Bagaimana tingkat kesulitan dari game tersebut? ¾ Berapa lama waktu yang diperlukan untuk menyelesaikan game tersebut?
39
f. Aspek Lain dari Design 1) Karakter Urutkan dan jelaskan karakter didalam game itu, jika ada. Tuliskan kepribadian, kemampuan, dan bagaimana aksinya dalam game. 2) Dunia Menjelaskan tempat dimana adegan itu berlangsung. 3) Kontrol Menjelaskan antarmuka pengguna. 4) Grafis Menjelaskan grafik secara umum. Game akan lebih bagus jika ada visualisasi. 5) Suara dan Musik Mendeskripsikan pemakaian dan mendata unsur suara dan musik yang digunakan. Sebaiknya setiap aksi digabung dengan suara yang cocok. 2.10 Jigsaw Puzzle Puzzle adalah suatu masalah dimana dapat membuat orang yang mencoba memecahkannya berpikir. Puzzle digunakan untuk hiburan dan dapat membantu kemampuan logika. Pemain mungkin perlu untuk mengenali pola-pola untuk mengatasinya, sehingga mereka yang memiliki logika yang baik biasanya baik dengan Puzzle. Bermain puzzle dapat mengasah otak kanan para pemainnya. Puzzle terdiri atas Cube Puzzle, Sudoku Puzzle, Jigsaw Puzzle, dan banyak lagi.
40
Kali ini penulis akan membahas Jigsaw Puzzle sebagai topik yang akan digunakan untuk skripsi. Jigsaw Puzzle adalah teka-teki yang mengharuskan pemain untuk memasang kembali potongan – potongan gambar sesuai dengan pola gambar awal. Bila tiap - tiap potongan gambar diletakkan pada posisi yang tepat akan menghasilkan suatu gambar yang utuh dan sempurna. Permainan Jigsaw Puzzle dapat memberikan kontribusi yang cukup besar untuk mengembangkan kecerdasan Anda. Mereka meningkatkan tingkat kecerdasan bahasa, aritmatika dan kemampuan numerik. Permainan puzzle ini tersedia secara online dengan tema yang menarik seperti peta, tempat - tempat terkenal, hewan, alam dan kendaraan. Teka – teki ini diyakini meningkatkan kemampuan intelektual dari orang biasa. Sekarang puzzle online telah dibuat menampilkan grafik warna-warni, gambar menarik dan ikhtisar indah.. Jigsaw Puzzle online populer di kalangan pemain dari segala usia. Tren baru dari game ini di internet termasuk teknik bermain klasik digunakan 300 tahun lalu. 2.11 Visual Basic Bahasa Visual Basic adalah salah satu diantara sekian banyak bahasa pemrograman yang cukup banyak digunakan oleh para programmer. Visual Basic adalah bahasa pemrograman visual dengan dasar pemrograman bahasa Basic. Bahasa BASIC (Beginner's All-purpose Sybolic Instruction Code) dikembangkan pertama kali pada awal 1950-an. Sementara bahasa Visual Basic, yang merupakan pengembangan bahasa basic dikembangkan pertama kali oleh Microsoft pada tahun 1991.
41
Visual Basic merupakan salah satu Development Tool yaitu alat bantu yang dapat digunakan untuk membuat berbagai macam program komputer, khususnya yang berbasis windows. Pembuatan aplikasi dengan menggunakan bahasa Visual Basic dimulai dengan memperkirakan kebutuhan, kemudian merancang tampilan program yang diikuti dengan pembuatan kode program tersebut. Berikuti ini merupakan tampilan langsung dari Visual Basic 2010 seperti pada gambar 2.7.
Gambar 2. 7 Tampilan Lingkungan Visual Basic
Agar bisa menguasai bahasa pemrograman Visual Basic, diharuskan mempelajari dasar - dasarnya dengan lebih baik dan kuat. Beberapa komponen utama dalam bahasa visual yang harus diketahui diantaranya :
42
•
Project Project adalah sekumpulan modul. Jadi project (proyek) adalah program aplikasi itu sendiri. Didalamnya terdapat form beserta code nya. Project ini disimpan dalam file berakhiran .vbp. File ini akan menyimpan seluruh komponen program, termasuk pilihan proyek, pilihan environment, pilihan file EXE dan segala sesuatu yang berhubungan dengan proyek. Pada jendela proyek terdapat tiga icon, yaitu icon View Code, icon View Object dan icon Toggle Folder. Icon View Code dipakai untuk menampilkan jendela editor kode program. Icon View Object dipakai untuk menampilkan bentuk formulir (form) dan icon Toggle Folders berguna untuk menampilkan folder (tempat penyimpanan folder).
•
Form Form adalah object yang dipakai sebagai tempat bekerja program aplikasi. Jadi bisa dikatakan di form inilah kita melakukan aktifitas perancangan program. Biasanya pada saat mendesain Form, terdapat garis titik-titik yang disebut grid. Grid sangat berguna untuk membantu pengaturan tata letak objek yang dimasukkan dalam form, karena gerakan penunjuk mouse akan sesuai (tepat) pada titik-titik grid.
•
Toolbox Toolbox adalah kotak alat yang berisi icon-icon untuk memasukkan objek tertentu ke dalam jendela Form. Kita dapat memodifikasi toolbox, misalnya menambah komponen icon dengan mengklik kanan pada toolbox, lalu memilih Components atau Add Tab.
43
Icon - icon pada toolbox ini seringkali disebut sebagai control. Setiap kontrol memeiliki properti seperti warna, tulisan yang diletakkan pada control dan properti lainnya. Control - control diletakkan pada toolbox untuk dipilih dan digambarkan pada form. •
Properti Properti digunakan untuk menentukan setting suatu objek. Suatu objek biasanya mempunyai beberapa properti yang dapat diatur langsung dari jendela Properties atau lewat kode program. Setting properti akan menentukan cara kerja dari objek yang bersangkutan saat program aplikasi dijalankan, misalnya menentukan warna objek, bingkai objek, pengambilan data dan lain-lain.
•
Kode Program Kode program adalah serangkaian tulisan perintah yang akan dilaksanakan jika suatu Objek dijalankan. Kode program ini akan mengontrol dan menentukan jalannya suatu objek.
•
Event Event adalah peristiwa atau kejadian yang diterima oleh suatu objek, misalnya klik, seret, tunjuk, dan lain-lain. Event yang diterima objek akan memicu MS VB menjalankan kode program yang ada di dalamnya.
44
•
Metoda (Method) Metoda adalah suatu set perintah seperti halnya fungsi dan prosedur, tetapi sudah tersedia di dalam suatu objek. Seperti halnya properti (yang juga terdapat pada suatu objek), suatu metoda dapat dipanggil dengan menyebut nama objek diikuti tanda titik dan nama metodanya.
