PENYELESAIAN MASALAH 8 PUZZLE DENGAN ALGORITMA HILL CLIMBING STEPEST ASCENT LOGLIST HEURISTIK BERBASIS JAVA

Seminar Nasional Teknologi Informasi dan Komunikasi 2012 (SENTIKA 2012) Yogyakarta, 10 Maret 2012

ISSN: 2089-9815

PENYELESAIAN MASALAH 8 PUZZLE DENGAN ALGORITMA HILL CLIMBING STEPEST ASCENT LOGLIST HEURISTIK BERBASIS JAVA Azizah Zakiah Teknik Informatika, Politeknik Pos Indonesia Jl. Sariasih 54 Bandung 40151 Telp. (022) 2009570 ext 130 E-mail: [email protected]

ABSTRAKS 8 puzzle merupakan salah satu implementasi dari Artificial Intelegence Dalam proses penyelesaiannya banyak terdapat algoritma-algoritma pencarian yang dapat diterapkan. Solusi 8 puzzle akan lebih cepat diperoleh jika digunakan prinsip array dengan variasi algoritma Steepest-Ascent Hill Climbing (Hill Climbing dengan memilih kemiringan yang paling tajam / curam) dengan parameter heuristik posisi yang benar dan heuristik jarak serta dikombinasikan dengan LogList sebagai penyimpanan state state yang pernah dilalui untuk menanggulangi permasalah pada algoritma hill climbing itu sendiri dan terhindar dari looping state yang pernah dilalui. Metode-metode yang termasuk ke dalam teknik pencarian yang berdasarkan pada fungsi heuristik salah satu diantaranya adalah Hill Climbing, Best First Search, A* (A Bintang). Loglist merupakan tempat penyimpanan setiap kunjungan dari state-state puzzle yang telah dilakukan untuk menghindari looping atau pengulangan terhadap state yang pernah dilalui. Untuk menanggulangi permasalahan pada SteepestAscent Hill Climbing. Kata Kunci: 8Puzzle, heuristik, hill climbing, Steepest-Ascent Hill Climbing , loglist 1. PENDAHULUAN 1.1 Latar Belakang 8 puzzle adalah permainan sliding puzzle ciptaan Sam Loyd yang terdiri dari sebuah bingkai yang berisi kotak kotak angka dalam keadaan teracak dimana sebuah kotak hilang. Karena permainan ini bernama 8 puzzle, maka ukuran bingkai adalah 3 x 3. tujuan dari puzzle ini adalah dengan memakai gerakan geser yang menggunakan ubin kosong untuk mencapai goal state. 8 puzzle merupakan salah satu implementasi dari Artificial Intelegence. Dalam proses penyelesaiannya banyak terdapat algoritmaalgoritma pencarian yang dapat diterapkan. Dalam hal ini penulis memilih algoritma Steepest-Ascent Hill Climbing (Hill Climbing dengan memilih kemiringan yang paling tajam / curam) yang divariasikan dengan fungsi heuristik jarak dan posisi serta loglist sebagai tempat penyimpanan sebagai pembanding terhadap state state yang pernah dilalui untuk menghindari looping atau proses pergeseran ke state yang telah ada sebelumnya. 1.2

Rumusan Masalah Adapun rumusan masalah pada kasus 8 puzzle ini adalah sebagai berikut: a. Bagaimana menyelesaikan permasalahan 8 puzzle b. Algoritma apa yang harus digunakan untuk menyelesaikan permasalahan 8 puzzle c. Bagaimana aturan pergeseran tile yang diperbolehkan. d. Parameter apa yang digunakan sebagai patokan dilakukannya pergeseran

e. Apa yang harus dilakukan apabila terjadi state atau posisi sama yang pernah dilalui oleh puzzle f. Fungsi heuristik apa yang harus digunakan untuk pembanding untuk dilakukan persegeseran state nya. 1.3 a. b. c. d. e. f.

Tujuan Adapun tujuan adalah sebagai berikut: Menyelesaikan permasalahan 8 puzzle Menentukan Algoritma yang harus digunakan untuk menyelesaikan permasalahan 8 puzzle Menentukan aturan pergeseran tile yang diperbolehkan. Memperoleh Parameter apa yang digunakan sebagai patokan dilakukannya pergeseran Menhandle apabila terjadi state atau posisi sama yang pernah dilalui oleh puzzle Menentukan Fungsi heuristik apa yang harus digunakan untuk pembanding untuk dilakukan persegeseran state nya.

2. TINJAUAN PUSTAKA 2.1 Fungsi Heuristic (Heuristic Search) Heuristic berasal dari bahasa Yunani yaitu heuriskein yang berarti “mencari” atau “menemukan”. Di dalam mempelajari metode metode pencarian ini, kata heuristik diartikan sebagai suatu fungsi yang memberikan suatu nilai berupa biaya perkiraan (estimasi) dari suatu solusi. (Suyanto, 2007). Metode-metode yang termasuk ke dalam teknik pencarian yang berdasarkan pada fungsi heuristik salah satu diantaranya adalah: Hill Climbing

158

Seminar Nasional Teknologi Informasi dan Komunikasi 2012 (SENTIKA 2012) Yogyakarta, 10 Maret 2012

Best First Search A* (A Bintang) Terdapat dua jenis fungsi heuristik yang bisa digunakan yaitu: a. H1 = jumlah kotak yang posisinya benar. b. H2 = jarak antara initialstate dan goalstate. Cara menghitungnya yaitu dengan menjumlahkan harga mutlak selisih antara kolom dan baris pada initial state dengan goal state. Total nilai dari h1 dan h2 adalah maksimal 9 yaitu H1 maksimum apabila posisi tile sudah sesuai dengan goalState adalah 9 dan H2 adalah 0 (nol). Heuristik posisi adalah nilai dari pencocokan antara inisialState dengan goalState apabila: a. Jumlah ubin yang menempati posisi yang benar: jumlah yang lebih tinggi adalah yang diharapkan (lebih baik). b. Jumlah ubin yang menempati posisi yang salah: jumlah yang lebih kecil yang diharapkan (lebih baik). Contoh

a. Jumlah Posisi Ubin yang menempati posisi yang benar adalah [1 2 4 5 6 7 8 ] yaitu h1 = 7. b. Jumlah Posisi Ubin yang menempati posisi yang salah adalah [0 3 ] yaitu h1 = 2. Fungsi Heuristik jarak yang diambil adalah yang bernilai 0 (nol) Contoh

a. Heuristik Jarak angka 6 adalah 0 yaitu: Initial state 6: kolom = 0 ; baris = 0 Goal State 6: kolom = 0 ; baris = 0 Maka Jarak |6| adalah |kolom goalState-kolom Initialstate| + |baris goalState-baris Initialstate | = |0-0|+|0-0|  0 b. Heuristik Jarak angka 3 adalah 0 yaitu: Initial state 3: kolom = 0 ; baris = 0 Goal State 3: kolom = 0 ; baris = 1 Maka Jarak |3| = |kolom goalState-kolom Initialstate| + |baris goalState-baris Initialstate | = |0-0|+|1-0|  1

ISSN: 2089-9815

2.2

Hill Climbing Proses Pengujian dilakukan dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristik ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaankeadaan lainnya yang mungkin.(Kusumadewi, 2003) Terdapat dua jenis Hill Climbing yang sedikit berbeda, yakni Simple Hill Climbing (Hill Climbing sederhana) dan Steepest-Ascent Hill Climbing (Hill Climbing dengan memilih kemiringan yang paling tajam / curam). Pada kasus pemecahan masalah 8 puzzle ini penulis memilih Steepest-Ascent Hill Climbing. Steepest-Ascent Hill Climbing sebenarnya hampir sama dengan simple hill climbing. Hanya sajagerakan pencarian tidak dimulai dari posisi paling kiri. Gerakan selanjutnya dicari berdasarkan nilai heuristik terbaik. Dalam hal ini urutan penggunaan operator tidak menentukan penemuan solusi. Algoritma: a. Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti ; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal. b. Kerjakan hingga tujuan tercapai atau hingga iterasi tidak memberikan perubahan pada keadaan sekarang. 1. Tentukan SUCC sebagai niali heuristik terbaik dari successor- successor 2. Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang: 3. Gunakan operator tersebut dan bentuk keadaan baru. 4. Evaluasi keadaan baru tersebut. Jika merupakan tujuan, keluar, Jika bukan, bandingkan nilai heuristiknya dengan SUCC. Jika lebih baik, jadikan nilai heuristic keadaan baru tersebut sebagai SUCC. Namun jika tidak lebih baik, nilai SUCC tidak berubah. 5. Jika SUCC lebih baik daripada nilai heuristik keadaan sekarang, ubah node SUCC menjadi keadaan sekarang. Pada Steepest-Ascent Hill Climbing ini ada 3 masalah yang mungkin yaitu: a. Local optimum keadaan semua tetangga lebih buruk atau sama dengan keadaan dirinya. b. Plateu keadaan semua tetangga sama dengan keadaan dirinya. c. Ridge  local optimum yang lebih disebabkan karena ketidakmampuan untuk menggunakan 2 operator sekaligus. 2.3

Loglist Loglist merupakan tempat penyimpanan setiap kunjungan dari state-state puzzle yang telah 159

Seminar Nasional Teknologi Informasi dan Komunikasi 2012 (SENTIKA 2012) Yogyakarta, 10 Maret 2012

dilakukan untuk menghindari looping atau pengulangan terhadap state yang pernah dilalui. Untuk menanggulangi permasalahan pada SteepestAscent Hill Climbing.

3 1 2 6 4 5 0 7 8 8 ∑(inisialState[i]< initialState[3]) = 2 I=4 5. Hitung jumlah bilangan yang berada di sebelah kanan angka 4 yang lebih kecil tapi bukan 0 (nol). 3 1 2 6 4 5 0 7 8 8 ∑(inisialState[i]< initialState[4]) = 0 I=5 6. Hitung jumlah bilangan yang berada di sebelah kanan angka 5 yang lebih kecil tapi bukan 0 (nol). 3 1 2 6 4 5 0 7 8 8 ∑(inisialState[i]< initialState[5]) = 0 I=6 7. Hitung jumlah bilangan yang berada di sebelah kanan angka 7 yang lebih kecil tapi bukan 0 (nol). 3 1 2 6 4 5 0 7 8 8 ∑(inisialState[i]< initialState[7]) = 0 I=8 Jadi diperoleh jumlah: 2 + 0 + 0 + 2 + 0 + 0 + 0  6, maka goalState yang dipilih adalah goalstate B yaitu [ 0 1 2 3 4 5 6 7 8 ]

3. PEMBAHASAN 3.1 Pemilihan GoalState Sebelum melalukan pencarian state yang harus dipilih. langkah yang harus dilakukan adalah memilih goalState. Dalam 8puzzle terdapat 2 buah goalState yaitu: a. GoalState A adalah goalState yang dipilih apabila jumlah dari perbandingan semua tile dengan tile setelahnya(sebelah kanannya) berjumlah ganjil maka goalStatenya melingkar adalah [1,2,3,8,0,4,7,6,5] b. GoalState B adalah goalState yang dipilih apabila jumlah dari perbandingan semua tile dengan tile setelahnya(sebelah kanannya) berjumlah genap maka goalStatenya berurut adalah [0,1,2,3,4,5,6,7,8] (sumber: www.8puzzle.com) Contohnya: Diketahui InisialState dibawah ini: 3 1 2 6 4 5 0 7 8 Maka goalstate nya adalah 1. Hitung jumlah bilangan yang berada di sebelah kanan angka 3 yang lebih kecil tapi bukan 0 (nol). 3 1 2 6 4 5 0 7 8 8 ∑(inisialState[i]< initialState[0]) = 2 I=1 2. Hitung jumlah bilangan yang berada di sebelah kanan angka 1 yang lebih kecil tapi bukan 0 (nol). 3 1 2 6 4 5 0 7 8 8 ∑(inisialState[i]< initialState[1]) = 0 I=2  3. Hitung jumlah bilangan yang berada di sebelah kanan angka 2 yang lebih kecil tapi bukan 0 (nol). 3 1 2 6 4 5 0 7 8 8 ∑(inisialState[i]< initialState[2]) = 0 I=3  4. Hitung jumlah bilangan yang berada di sebelah kanan angka 6 yang lebih kecil tapi bukan 0 (nol).

ISSN: 2089-9815

3.2

Pemilihan Pergeseran State yang diperbolehkan. State dapat bergerak ke state yang selanjutnya berdasarkan posisi ubin kosong. Operator yang diperbolehkan adalah: 1. Ubin Kosong ke Kanan 2. Ubin Kosong ke Kiri 3. Ubin Kosong ke Atas 4. Ubin Kosong ke Bawah Kemungkinan Posisi ubin kosong pada state adalah: 1. Posisi Ubin Kosong pada index ke 0 atau pojok kiri atas, maka pergesaran yang diperbolehkan adalah bergeser ke kanan atau ke bawah. 2. Posisi Ubin Kosong pada index ke 1 atau tengah atas, maka pergesaran yang diperbolehkan adalah bergeser ke kanan, kiri atau ke bawah. 3. Posisi Ubin Kosong pada index ke 2 atau pojok kanan atas, maka pergesaran yang diperbolehkan adalah bergeser ke kiri atau ke bawah. 4. Posisi Ubin Kosong pada index ke 3 atau tengah 160

Seminar Nasional Teknologi Informasi dan Komunikasi 2012 (SENTIKA 2012) Yogyakarta, 10 Maret 2012

5.

6. 7. 8. 9.

kiri, maka pergesaran yang diperbolehkan adalah bergeser ke kanan, atas atau bawah. Posisi Ubin Kosong pada index ke 4 atau tepat di tengah, maka pergesaran yang diperbolehkan adalah bergeser ke kanan, kiri, atas atau ke bawah. Posisi Ubin Kosong pada index ke 5 atau pojok kiri atas, maka pergesaran yang diperbolehkan adalah bergeser ke kiri, atas atau ke bawah. Posisi Ubin Kosong pada index ke 6 atau pojok kiri atas, maka pergesaran yang diperbolehkan adalah bergeser ke kanan atau ke atas. Posisi Ubin Kosong pada index ke 7 atau pojok kiri atas, maka pergesaran yang diperbolehkan adalah bergeser ke kanan, kiri atau ke atas. Posisi Ubin Kosong pada index ke 8 atau pojok kiri atas, maka pergesaran yang diperbolehkan adalah bergeser ke kiri atau ke atas.

Dari kemungkinan pergeseran-pergeseran yang diperbolehkan dari ubin kosong diatas maka dapat disimpulkan bahwa: 1. Geser Kanan = 1 2. Geser Kiri = -1 3. Geser Atas =-3 4. Geser Bawah = +3 3.3 Algoritma Algoritma Masukkan inisial state Procedure Masukkan Inisial State DEKLARASI initialState:array[1..9]of integer i: integer DESKRIPSI For i  0 to 8 do Read(initialState[i]) Endfor.

Algoritma Pemilihan Goalstate

If (jumlah % 2 == 1) Then For i  0 to 8 do goalState[i]=goalStateA[i] endFor Else For i  0 to 8 do goalState[i]=goalStateB[i] endFor EndIf

Algoritma pemilihan ubin kosong Procedure Pemilihan Langkah ubin kosong (input State: array[1..9] of integer) DEKLARASI i: integer TotalKanan: integer TotalKiri: integer TotalAtas: integer TotalBawah: integer DESKRIPSI For i  0 to 8 do If (State[i]==0) Posisi  i endIf Endfor. Switch(posisi) Case 0: Totalkanan = heuristikPosisi(kanan)+ heuristikJarak(kanan) Totalbawah = heuristikPosisi(bawah)+ heuristikJarak(bawah) If(Totalkanan > Totalbawah) Then Geser(Kanan) Else Geser(Bawah) endIf Break ; Case 1: Totalkanan = heuristikPosisi(kanan)+ heuristikJarak(kanan) Totalbawah = heuristikPosisi(bawah)+ heuristikJarak(bawah) TotalKiri = heuristikPosisi(kiri)+ heuristikJarak(kiri) If(Totalkanan > Totalbawah && TotalKanan > TotalKiri) Then Geser(Kanan) Else If(Totalbawah > Totalkanan && TotalBawah > TotalKiri) Then Geser(Bawah) Else Geser(Kiri) endIf Break ;

Procedure Pemilihan Goal State DEKLARASI initialState: array[1..9] of integer goalStateA: array[1..9] of integer goalStateB: array[1..9] of integer goalState: array[1..9] of integer i , j,jumlah: integer DESKRIPSI goalStateA = {1,2,3,8,0,4,7,6,5} goalStateB = {0,1,2,3,4,5,6,7,8} jumlah =0 { mengecek apakah jumlah dari perbandingan semua tile dengan tile setelahnya (sebelah kanannya) berjumlah ganjil maka goalStatenya melingkar jika tidak goalStateB} For i  0 to 8 do For j  i + 1 to 7 do If (initialState[j]< initialState[i] initialState[j] != 0) then Jumlah++ endIf endFor. Endfor.

ISSN: 2089-9815

&&

Case 2: Totalbawah = heuristikPosisi(bawah)+ heuristikJarak(bawah) TotalKiri = heuristikPosisi(kiri)+ heuristikJarak(kiri) If(TotalKiri> Totalbawah) Then Geser(Kiri) Else Geser(Bawah) endIf Break ; Case 3: TotalAtas = heuristikPosisi(atas)+ heuristikJarak(atas) Totalbawah = heuristikPosisi(bawah)+

161

Seminar Nasional Teknologi Informasi dan Komunikasi 2012 (SENTIKA 2012) Yogyakarta, 10 Maret 2012 heuristikJarak(bawah) TotalKanan = heuristikPosisi(kanan)+ heuristikJarak(kanan) If(Totalkanan > Totalbawah && TotalKanan > TotalAtas) Then Geser(Kanan) Else If(Totalbawah > Totalkanan && TotalBawah > TotalAtas) Then Geser(Bawah) Else Geser(Atas) endIf Break ; Case 4: TotalAtas = heuristikPosisi(atas)+ heuristikJarak(atas) Totalbawah = heuristikPosisi(bawah)+ heuristikJarak(bawah) TotalKanan = heuristikPosisi(kanan)+ heuristikJarak(kanan) TotalKiri = heuristikPosisi(kiri)+ heuristikJarak(kiri) If(Totalkanan > Totalbawah && TotalKanan > TotalAtas && TotalKanan > TotalKiri) Then Geser(Kanan) Else If(TotalKiri > Totalkanan && TotalKiri > TotalAtas &&TotalKiri > TotalBawah) Then Geser(Kiri) Else If(Totalbawah > Totalkanan && TotalBawah > TotalAtas &&TotalBawah > TotalKiri) Then Geser(Bawah) Else Geser(Atas) endIf Break ; Case 5: TotalAtas = heuristikPosisi(atas)+ heuristikJarak(atas) Totalbawah = heuristikPosisi(bawah)+ heuristikJarak(bawah) TotalKiri = heuristikPosisi(kiri)+ heuristikJarak(kiri)

ISSN: 2089-9815

heuristikJarak(kiri) If(TotalKanan > TotalAtas && TotalKanan > TotalKiri) Then Geser(Kanan) Else If(TotalKiri > Totalkanan && TotalKiri > TotalAtas ) Then Geser(Kiri) Else Geser(Atas) endIf Break ; Case 8: TotalAtas = heuristikPosisi(atas)+ heuristikJarak(atas) TotalKiri = heuristikPosisi(kiri)+ heuristikJarak(kiri) If(TotalKiri > TotalAtas ) Then Geser(Kiri) Else Geser(Atas) endIf Break ; endSwitch.

3.4 Program Program masukkan state

Program pemilihan goalstate

If(TotalKiri > TotalAtas &&TotalKiri > TotalBawah) Then Geser(Kiri) Else If(TotalBawah > TotalAtas &&TotalBawah > TotalKiri) Then Geser(Bawah) Else Geser(Atas) endIf Break ; Case 6: TotalAtas = heuristikPosisi(atas)+ heuristikJarak(atas) TotalKanan = heuristikPosisi(kanan)+ heuristikJarak(kanan)

Program penghitungan nilai jarak heuristik

If(TotalKanan > TotalAtas ) Then Geser(Kanan) Else Geser(Atas) endIf Break ; Case 7: TotalAtas = heuristikPosisi(atas)+ heuristikJarak(atas) TotalKanan = heuristikPosisi(kanan)+ heuristikJarak(kanan) TotalKiri = heuristikPosisi(kiri)+

3.5

Antarmuka Adapun antarmuka hasil dari program 8 puzzle ini adalah sebagai berikut: 162

Seminar Nasional Teknologi Informasi dan Komunikasi 2012 (SENTIKA 2012) Yogyakarta, 10 Maret 2012

ISSN: 2089-9815

4.

Gambar 1. Tampilan pertama program 8 puzzle

PENUTUP Kesimpulan pada makalah ini yaitu: 1. Persoalan 8 puzzle dapat diselesaikan dengan menggunakan prinsip array serta algoritma Steepest-Ascent Hill Climbing yang telah divariasikan. 2. Solusi 8 puzzle akan lebih cepat diperoleh jika digunakan prinsip array dengan variasi algoritma Steepest-Ascent Hill Climbing (Hill Climbing dengan memilih kemiringan yang paling tajam / curam) dengan parameter heuristik posisi yang benar dan heuristik jarak serta dikombinasikan dengan LogList sebagai penyimpanan state state yang pernah dilalui untuk menanggulangi permasalah pada algoritma hill climbing itu sendiri.  

Gambar 2. Tampilan inisial state program 8 puzzle

Gambar 3. Tampilan hasil program 8 puzzle Tampilan Pelacakkan Pergeseran:

PUSTAKA HillClimbing. (Online). (http://en.wikipedia.org/ wiki/Hill_climbing diakses pada tanggal 2 April 2010 pukul 20.00 WIB) Kusumadewi, S. (2003). Artificial Intelelligence. Jogyakarta: Graha Ilmu.\ Local search (Constraint satisfication). (Online). (http://en.wikipedia.org/wiki/Local_search_%28 constraint_satisfaction%29#Hill_climbing diakses pada tanggal 2 April 2010 pukul 20.00) Suyanto. (2007). ST.,M.Sc. Dalam A. Intellegence, Searching, Reasoning, Planning and Learning. Bandung: Informatika Bandung. What is 8 puzzle. (Online). (http://www.8puzzle.com diakses pada tanggal 2 April 2010 pukul 20.00 WIB ) Yuval Baror. Visualgo N-puzzle. (Online). (http://yuval.bar-or.org/index.php?item=10 diakses pada tanggal 2 April 2010 pukul 20.00 WIB)

Gambar 4. Tampilan pelacakan pergeseran program 8 puzzle

163