Pelita Informatika Budi Darma, Volume : IV, Nomor: 3, Agustus 2013
ISSN : 2301-9425
PENERAPAN ALGORITMA A* PADA PERMASALAHAN OPTIMALISASI PENCARIAN SOLUSI DYNAMIC WATER JUG Firman Harianja (0911519) Mahasiswa Program Studi Teknik Informatika STMIK Budidarma Medan Jl. Sisingamangaraja No. 338 Simpang Limun Medan www.stmik-budidarma.ac.id // Email :
[email protected] ABSTRAK Pada penilisan skripsi ini penulis merancang Penerapan Algoritma A* pada Permasalahan Optimalisasi Pencarian Solusi Dynamic Water Jug dimana Optimalisasi itu sendiri adalah sebuah proses memodifikasi sistem untuk membuat beberapa aspek agar bekerja lebih efisien atau menggunakan resource (sumber) lebih sedikit. Sebuah program komputer di optimalisasi sehingga bisa menjalankan tugasnya lebih dengan cepat, atau mampu untuk beropersai dalam pengurangan sejumlah memory storage. Dalam optimalisasi permasalahan water jug dengan kemungkinan-kemungkinan terbaik dilakukan, optimalisasi bisa berarti permasalahan maksimalisasi, memaksimalkan pencapaian nilai terbaik atau permasalahan minimalisasi, meminimalkan biaya,waktu dan sebagainya. Dalam hal ini penulis menerapkan Algoritma A* sebagai salah satu Algoritma pencarian yang Complit dan Optimal yang dapat diterapkan dalam penyelesaian Optimalisasi pencarian solusi Water Jug. Kata Kunci : Solusi, Optimalisasi, Water Jug, Algoritma A*.
1. Pendahuluan 1.1 Latar Belakang Algoritma A*, Algoritma ini merupakan algoritma Best First Search yang menggabungkan Uniform Cost Search dan Greedy Best-First Search. Dimana Harga yang dipertimbangkan f(n) didapat dari harga sesungguhnya g(n) ditambah dengan harga perkiraan h(n). Dalam notasi matematika dituliskan: f(n) = g(n) + h(n). Masalah utama dalam membangun sistem berbasis AI adalah bagaimana mengkonversi situasi yang diberikan ke dalam situasi lain yang diinginkan menggunakan sekumpulan operasi tertentu Masalah water jug / wadah air adalah salah satu masalah yang membutuhkan konversi dari satu situasi menjadi situasi yang diinginkan dengan menggunakan sekumpulan operasi. Dari pendahuluan diatas maka masalah water jug ini dapat diselesaikan dengan algoritma penelusuran graf / node. Oleh karena itu untuk mencari solusi masalah ini dengan optimal dan komplit, penulis menerapkan algoritma A* (Star). 1.1. Tujuan 1. Menyelesaikan masalah Optimalisasi Dynamic Water Jug dengan algoritma penelusuran A* (Star). 2. Menerapkan algoritma A* (Star) sebagai alternatif penyelesaian permasalahan Optimalisasi Dynamic Water Jug.
3. Merancang sebuah Penerapan Algoritma A*(Star) Pada Optimalisasi Pencarian Solusi Dynamic Water Jug. 1.2. Identifikasi Masalah 1. Bagaimana Permasalahan Optimalisasi Dynamic Water Jug ? 2. Bagaimana Penyelesaian Optimalisasi Solusi Dynamic Water Jug ? 3. Bagaimana menerapkan algoritma A* (Star) untuk menyelesaikan permasalahan Optimalisasi Pencarian Solusi Dynamic Water Jug ? 4. Bagaimana merancang sebuah Penerapan Algoritma A*(Star) Pada Permasalahan Optimalisasi Pencarian Solusi Dynamic Water Jug ? 1.3. Metode Penelitian 1. Studi kepustakaan (Library Research) 2. Studi literatur (Literature Research) 3. Tahapan Penulisan Skripsi 4. Tahapan Perancangan 5. Tahapan Implementasi 2. Algoritma Dibawah ini adalah penjelasan singkat tentang algoritma A* yang digunakan untuk penyelesaian optimalisasi solusi dynamic water jug.
Penerapan Algoritma A* Pada Permasalahan Optimalisasi Pencarian Solusi Dynamic Water Jug. Oleh : Firman Harianja
48
Pelita Informatika Budi Darma, Volume : IV, Nomor: 3, Agustus 2013
2.1. A* (Star) Sama dengan algortima dasar Best First Search, algoritma A* ini juga menggunakan dua senarai : OPEN dan CLOSED. Terdapat tiga kondisi bagi setiap suksesor yang dibangkitkan, yaitu: sudah berada di OPEN, sudah berada di CLOSED, dan tidak berada di OPEN maupun CLOSED. Pada ketiga kondisi tersebut diberikan penanganan yang berbeda-beda.[1] Jika suksesor sudah pernah berada di OPEN, maka dilakukan pengecekan apakah perlu pengubahan parent atau tidak tergantung pada nilai g-nya melalui parent lama atau parent baru. Jika melalui parent baru memberikan nilai g yang lebih kecil, maka dilakukan pengubahan parent. Jika pengubahan parent dilakukan, maka dilakukan juga perbaruan (update) nilai g dan f pada suksesor tersebut. Untuk terpilih sebagai simpul terbaik (best node).[1] Jika suksesor sudah pernah berada di CLOSED, maka dilakukan pengecekan apakah perlu pengubahan parent atau tidak. Jika ya, maka dilakukan perbaruan nilai g dan f pada suksesor tersebut serta semua “ anak cucunya” yang sudah pernah berda di OPEN. Dengan perbaruan ini, maka semua anak cucunya tersebut memiliki kesempatan lebih besar untuk terpilih sebagai simpul terbaik (best node). Jika suksesor tidak berada di OPEN maupun di CLOSED, maka suksesor tersebut dimasukkan ke dalam OPEN. Tambahkan suksesor tersebut sebagai suksesornya best node. Hitung biaya suksesor tersebut dangan rumus f’ = g + h’. Contoh Penelusuran A* :
ISSN : 2301-9425
Maka node A tersebut dimasukkan ke list OPEN sebagai best node, Pada gambar (b) hasil penelusuran dari node A terdapat tiga buah hasil node baru yaitu node B,C dan D, sehingga node A dipindahkan ke CLOSED sebagai tanda bahwa node A sudah pernah ditelusuri, dari ketiga node ini setelah dihitung nilai yang dipertimbangkan [f(n)] paling minim terpilih node C sebagai node terkecil dengan nilai 2 yang selanjutnya untuk ditelusuri. Kemudian semua suksesor C dibangkitkan hingga menghasilkan node E dan F dapat dilihat pada gambar 2.1 (c). Maka graf yang ditelusuri dari gambar diatas adalah A-C-F (Dalam hal ini bila pada node F telah ditemukan tujuan atau goal akhir). Dengan penggunaan f(n), maka algoritma A* adalah Complete dan Optimal. Heuristik adalah nilai yang memberi harga pada tiap simpul yang memandu A* mendapatkan solusi yang diinginkan. Dengan heuristik, maka A* pasti akan mendapatkan solusi (jika memang ada solusinya). Dengan kata lain, heuristik masih merupakan estimasi / perkiraan biasa saja. Sama sekali tidak ada rumus khususnya. Artinya,setiap kasus memiliki fungsi heuristik yang berbeda-beda. Algoritma A* menyelesaikan masalah yang menggunakan graf untuk perluasan ruang statusnya. Dengan kata lain digunakan untuk menyelesaikan permasalahan yang bisa di representasikan dengan graf. Algoritma A* adalah sebuah algoritma yang telah diperkaya, dengan menerapkan suatu heuristik, algoritma ini membuang langkah-langkah yang tidak perlu dengan pertimbangan bahwa langkah-langkah yang dibuang sudah pasti merupakan langkah yang tidak akan mencapai solusi yang diinginkan. Algoritma A* membangkitkan simpul yang paling kecil. Simpul ini kemudian disimpan suksesornya ke dalam list sesuai dengan urutan yang paling mendekati solusi terbaik. Kemudian, simpul pertama pada list diambil, dibangkitkan suksesornya dan kemudian suksesor ini disimpan ke dalam list sesuai dengan urutan yang terbaik untuk solusi. List simpul ini disebut dengan simpul terbuka(open node). 2.2 Fungsi Heuristik
(a)
(b)
(c)
Gambar 1 : Pohon penelusuran A* Awal graf pada gambar 2.1 (a) adalah sebagai node Awal yang selanjutnya untuk ditelusuri.
Heuristik yang paling umum digunakan adalah jarak Manhattan. Fungsi heuristik ini hanya akan menjumlahkan selisih nilai x dan nilai y dari dua buah titik. Perhitungannya dapat ditulis sebagai berikut: h(n) = abs(n.x-tujuan.x) + abs(n.y-tujuan.y) Rumus diatas adalah rumus untuk mencari garis lurus antara dua verteks, yaitu verteks a dan verteks b. 3. Analisa Masalah Formulasi Masalah merupakan suatu langkah yang sangat penting dalam perancangan model
Penerapan Algoritma A* Pada Permasalahan Optimalisasi Pencarian Solusi Dynamic Water Jug. Oleh : Firman Harianja
49
ISSN : 2301-9425
Pelita Informatika Budi Darma, Volume : IV, Nomor: 3, Agustus 2013
simulasi. Formulasi masalah yang tidak tepat tidak akan mungkin menghasilkan model yang tepat (akurat). Formulasi masalah merupakan suatu kegiatan untuk memilih satu permasalahan yang dianggap paling penting untuk diselesaikan saat itu dari sekian banyak permasalahan. Berikut ini adalah formulasi contoh kasus masalah water jug yang akan di selesaikan. 1. Terdapat 2 wadah, yaitu wadah A dan B, masingmasing memiliki kapasitas 8 liter dan 6 liter serta sebuah keran air. 2. Awalnya di asumsikan semua wadah kosong. 3. Diminta untuk mengisikan air ke wadah A sebanyak 4 liter secara tepat penuh dengan memanfaatkan ke dua wadah tersebut. 4. Diasumsikan sumber air dari keran tidak terbatas. Contoh :
Operasi yang mengubah suatu state ke state lainnya disebut sebagai aturan produksi. Penelusuran dilakukan sampai didapatkan semua aturan produksi yang mungkin. Pertanyaan yang muncul adalah bagaimana kita tahu bahwa aturan produksi yang kita defenisikan tersebut sudah lengkap atau belum? Suatu solusi mungkin tidak dapat ditemukan jika aturan produksinya tidak terdefenisi secara lengkap. Aturan-aturan produksi yang lengkap dapat digunakan untuk memecahkan masalah water jug ditunjukkan pada tabel 3.1 dibawah ini. Tabel 1 : Tabel Aturan Produksi Jika
Keterangan
1 (x,y), x < 8 2 (x,y), y < 6 3 (x,y), x > 0
4
Gambar 2 : Contoh Kasus Water jug 3.1. Penyelesaian Pada tahapan ini, sebelum melakukan percobaan simulasi terlebih dahulu lakukan langkah-langkah berikut ini: 1. Defenisikan ruang masalah, initial state dan goal state Ruang masalah untuk masalah water jug di atas dapat di gambarkan sebagai himpunan pasangan bilangan bulat (x,y) yang terurut, sedemikian hingga x = 0,1,2,3,4,5,6,7 atau 8 dan y = 0,1,2,3,4,5, atau 6. x menyatakan jumlah air dalam wadah berukuran 8 liter, dan y menyatakan jumlah air dalam wadah ukuran 6 liter. Dengan demikian, keadaan awal (initial state) dimana kedua wadah masih kosong dinyatakan sebagai (0,0). Karena tujuannya adalah mendapatkan tepat 4 liter air tanpa mempedulikan jumlah air diwadah lain, maka goal state dapat dipresentasikan sebagai (4,n) untuk setiap nilai n. 2. Defenisikan aturan produksi Aturan produksi dapat di defenisikan dengan menggambarkan struktur pohon dari keadaankeadaan yang telah didefenisikan di atas. Dengan mempresentasikan initial state (0,0) sebagai simpul akar (root) dari sebuah pohon, maka kita dapat menelusuri simpul-simpul (keadaan-keadaan) berikutnya yang mungkin terjadi.
5
6
7
8
(8,y). Isi wadah A. (x,6). Isi wadah B. (0,y). Kosongkan wadah A dengan membuang airnya. (x,y), y > 0 (x,0). Kosongkan wadah B dengan membuang airnya. (x,y), x + y (8, y-(8-x)). Tuangkan air dari wadah B ke wadah 8 dan y > 0 A sampai wadah A penuh. (x,y), x + y (x-(6-y),y).Tuangkan air dari wadah A ke wadah 6 dan x > 0 B sampai wadah B penuh. (x,y), x + y (x+y,0). Tuangkan seluruh air dari wadah B ke 8 dan y > 0 wadah A. (x,y), x + y (0,x+y). Tuangkan seluruh air dari wadah A ke 6 dan x > 0 wadah B.
Ket : X = jumlah air diwadah A Y = jumlah air diwadah B
3. Algoritma A* Permasalahan Wadah Air merupakan salah satu permasalahan klasik dalam Artificial Intelligence (AI). Terdapat berbagai macam algoritma yang dapat digunakan untuk menyelesaikan masalah ini. Sebagaimana yang sudah dijelaskan dalam latar belakang masalah sebelumnya, bahwa algoritma yang sudah pernah di lakukan untuk menyelesaikan masalah water jug ini adalah menggunakan algoritma BFS,DFS,DLS dan IDS [2]. Namun hal ini saya menggunakan Algoritma A*. Masalah ini dapat diselesaikan dengan menggunakan bantuan struktur graf / pohon biner Algoritma A*. Dimana satu keadaan (node) mewakili satu keadaan wadah Penerapan Algoritma A* Pada Permasalahan Optimalisasi Pencarian Solusi Dynamic 50 Water Jug. Oleh : Firman Harianja
Pelita Informatika Budi Darma, Volume : IV, Nomor: 3, Agustus 2013
. Prosedur kerja untuk mencari solusi yang mungkin dari suatu keadaan dengan menggunakan bantuan struktur pohon biner algoritma A* sebagai berikut :
Gambar 3 : Graf /node penelusuran A* Dari penyelesaian diatas nilai yang paling minimal yang menjadi optimalisasi solusi dinamis terpilih penyelesaian water jug adalah jalur pertama yaitu : Jalur alternative (A,C,D,G,H) [(0-0),(06),(6-0),(6-6),(8-4)] dalam hal ini dibutuhkan 4 langkah optimal meyelesaikan water jug diatas. Sebagaimana ditunjukkan gambar pohon pencarian A* dibawah ini (jalur merah/solusi ke- 1) : Tabel 2 : Hasil Optimalisasi Solusi Dinamis Jlh Air diwadah A
Jlh Air diwadah B
(X-Y)
Aturan Produksi
0
0
0
0-0
0
1
0
6
0-6
2
2
6
0
6-0
7
3
6
6
6-6
2
4
8
4
8-4
5
4.
ISSN : 2301-9425
Kompleksitas dari suatu algoritma merupakan ukuran seberapa banyak komputasi yang dibutuhkan algoritma tersebut untuk menyelesaikan masalah. Secara informal, algoritma yang dapat menyelesaikan suatu permasalahan dalam waktu yang singkat memiliki kompleksitas yang rendah, sementara algoritma yang membutuhkan waktu lama untuk menyelesaikan masalahnya mempunyai kompleksitas yang tinggi. Algoritma untuk simulasi implementasi algoritma A* pada permasalahan optimalisasi dinamis water jug terbagi menjadi 2 (dua) bagian, yaitu : 1. Algoritma pencarian A*. 4.1 Algoritma A* OPEN = node asal CLOSE array = 0 g=0 f’ = h’ Ulangi sampai node tujuan ditemukan If {OPEN = 0} Then Gagal Else BestNode = node yang ada di OPEN dengan f’ minimal Pindahkan node terbaik tersebut dari OPEN ke CLOSE If {BestNode = Goal } Then Sukses Else Bangkitkan semua suksesor BestNode tapi jangan buat pointer Untuk setiap suksesor kerjakan : Hitung g(suksesor) = g(BestNode) + actual cost (dari BestNode ke suksesor) {Proses Periksa Suksesor} If {suksesor ada di OPEN} Then {sudah pernah dibangkitkan tapi belum diproses} OLD = isi OPEN tersebut Tambahkan OLD ke BestNode Bandingkan nilai g(OLD) dengan g(isi OPEN) If {g(OLD) lebih baik} Then Ubah parent isi OPEN ke BestNode Ubah nilai g dan f’ pada isi OPEN End Else If {suksesor ada di CLOSE} Then {sudah pernah dibangkitkan dan sudah diproses} OLD = isi CLOSE Tambahkan OLD sebagai suksesor BestNode Bandingkan nilai g(OLD) dengan g(isi CLOSE) If {g(OLD) lebih baik} Then Ubah parent isi CLOSE ke BestNod
Algoritma Algoritma dapat dikatakan sebagai urutan langkah-langkah logis yang sistematis dalam mencari suatu solusi dari suatu permasalahan yang ada. Pada program komputer, algoritma terdiri dari sekumpulan langkah-langkah untuk mencapai suatu tujuan, seperti logika If -Then-Else maupun pengulangan suatu tindakan atau langkah dengan loop. Penerapan Algoritma A* Pada Permasalahan Optimalisasi Pencarian Solusi Dynamic Water Jug. Oleh : Firman Harianja
51
Pelita Informatika Budi Darma, Volume : IV, Nomor: 3, Agustus 2013
Ubah nilai g dan f’ pada isi CLOSE Propogasi untuk semua suksesor OLD dengan penelusuran DFS dengan algoritma : Ulangi sampai node suksesor tidak ada di OPEN atau tidak punya suksesor If {suksesor ada di OPEN} Then Propogasi diteruskan Else If {nilai g via suksesor lebih baik} Then Propogasi diteruskan Else Propogasi diteruskan End End End Else {suksesor tidak ada di OPEN maupun CLOSE} Masukkan suksesor ke OPEN Tambahkan suksesor tersebut sebagai suksesor BestNode Hitung f’ = g(suksesor) + h’(suksesor) End End End End 4.2 Implementasi 4.2.1 Form Menu Instruksi
ISSN : 2301-9425
water jug tersebut. Menu kedua merupakan menu penyelesaian masalah yang akan dibangun oleh user sendiri. 4.2.2 Form Menu Penyelesaian
Gambar 5 : Penyelesaian Keterangan Gambar : 1. Pilihan Tipe Masalah 2. Pilihan Kasus Wadah 3. Input Nilai wadah, Awal masalah dan Goal Tujuan 4. Tombol Tampil wadah 5. Gamabar wadah 6. Tombol proses 7. Hasil proses 8. Hasil aksi 9. Tombol Undo 4.2.3 Form penyelesaian 2
Gambar 4 : Instruksi Dalam program water jug di atas terdapat dua menu sebagai berikut: 1. Menu Instruksi 2. Menu Penyelesaian Dimana menu pertama adalah menu instruksi yang berisi tentang peraturan penggunaan program Penerapan Algoritma A* Pada Permasalahan Optimalisasi Pencarian Solusi Dynamic Water Jug. Oleh : Firman Harianja
52
Pelita Informatika Budi Darma, Volume : IV, Nomor: 3, Agustus 2013
ISSN : 2301-9425
memanfaatkan pemrograman Borlan Delphi 7.0 sebagai tools pemrogramannya. Daftar Pustaka [1]. ST, MSc, Suyanto, 2011, Artificial Inteligence. [2]. Jurnal, Pertiwi, N., Dewi Lubis, E.H., Taufik, L. (2006), Penerapan Algoritma BFS, DFS, DLS, dan IDS dalam Pencarian Solusi Water Jug Problem [3]. Jurnal SAINTIKOM, Dahria, M. 2008, Kecerdasan Buatan (Artificial Inteligence). [4]. Jurnal, Putradi,E. 2009, Penerapan Algoritma A* Sebagai Pencari Jalan Dalam Game. [5]. Wahana Komputer, 2009, Aplikasi Cerdas Menggunakan Delphi.
Gambar 6 : Hasil optimalisasi Dengan data : 1. Kasus 2 wadah 2. Kapasitas wadah 1 dan 2 (8-6), Start (Keadaan Awal) 0-0, Goal/Tujuan (4-0). 3. Hasil Komputer Solusi 6 (langkah) : a. Fill#2 (6) 0-6 => Isi Wadah 2 (6) Keadaan 0-6. b. From#2 to #1 (6) 6-0 => Tuang dari wadah 2 ke wadah 1 keadaan 6-0. c. Fill#2 (6) 6-6 => Isi penuh wadah 2 keadaan baru 6-6. d. From#2 to #1 (2) 8-4 => Tuang dari wadah 2 ke wadah 1 sampai wadah 1 penuh (8-4). 4. Kotak Informasi yang menunjukkan bahwa simulasi telah berhasil. 5. Kesimpulan Dari hasil penjelasan bab-bab sebelumnya tentang permasalahan wadah air, dapat ditarik kesimpulan sebagai berikut : 1. Permasalahan optimalisasi dynamic water jug adalah bagaimana mengoptimalkan penyelesaian sebuah permasalahan water jug atau mencari sebuah solusi paling optimal dalam meyelesaikan sebuah kasus wadah air. 2. Untuk dapat mencari optimalisasi solusi dynamic water jug perlu sebuah langkah peyelesaian dengan menerapkan algoritma A* mencari solusi optimal. 3. Algoritma A* merupakan perbaikan dari algoritma Uniform Cost Search dengan meminimalisasi jumlah node yang diekspansi dalam tree-search, serta mampu memberikan solusi optimal terhadap masalah water jug sebelumnya dengan 4 langkah. 4. Perangkat lunak dapat mencari solusi terpendek dan complit karena menggunakan metode pencarian heuristik (Algoritma A*) dengan Penerapan Algoritma A* Pada Permasalahan Optimalisasi Pencarian Solusi Dynamic Water Jug. Oleh : Firman Harianja
53
