Kecerdasan Buatan Suatu Software/Hardware serta Implementasi Metode A* Dalam Menyelesaikan Suatu Masalah
Sebuah software atau hardware disebut cerdas jika memiliki kemampuan untuk Searching, Reasoning, Planning dan Learning.
- Searching
Adalah mekanisme memecahkan suatu masalah dengan teknik pencarian. langkah pertama adalah mendefinisikan ruang masalah, langkah kedua adalah mendefinisikan atauran produksi yang digunakan untuk mengubah suatu state ke state lainnya. langkah terakhir adalah memilih metode pencarian yang tepat sehingga dapat menemukan solusi terbaik dengan usaha minimal. Teknik ini digunakan untuk pencarian rute optimum untuk memandu seseorang di perjalanan.
Contoh : Penggunaan smartphone atau komputer yang dilengkapi Global Positioning System (GPS).
2. Reasoning
Adalah mekanisme penyelesaian masalah dengan cara mereprentasikan masalah ke dalam basis pengetahuan atau knowledge base menggunakan logic atau bahasa formal atau bahasa yang dipahami komputer. Teknik ini digunakan untuk melakukan penalaran terhadap suatu masalah yang dialami manusia.
Contoh : Software yang digunakan dalam dunia kedokteran, MedicWare yang digunakan untuk merekam catatan medis pasien.
3. Planning
Adalah mekanisme menyelesaikan masalah – masalah yang dapat di dekomposisi atau decomposable problems. Teknik ini digunakan untuk melakukan perencanaan terhadap suatu masalah yang hendak diselesaikan.
Contoh : Optimum-AIV adalah suatu planner yang digunakan oleh European Space Agency untuk assembly atau perakitan, integration atau penggabungan dan verification (AIV) pesawat terbang.
4. Learning
Adalah mekanisme yang menggunakan metadata sebagai input dan mengolahnya menggunakan sejumlah lapisan tersembunyi transformasi non liniear dari data masukan untuk menghitung nilai output. Teknik ini digunakan untuk membuat mesin-mesin otomatis melalui proses pembelajaran dan pelatihan sedemikian rupa hingga bisa menjadi cerdas layaknya manusia.
Contoh : Speech to Speech Machine Translation (S2SMT), dengan S2SMT, seseorang bisa berbicara dengan orang lain yang menggunakan bahasa berbeda.
STUDI KASUS
Gambar di bawah ini adalah sebuah graf simetris tak berarah yang menggambarkan kondisi jalan raya di suatu kota. Terdapat 8 simpul yang menyatakan persimpangan jalan dengan posisi – posisi koordinat dua dimensi (x, y). setiap busur memiliki 2 atribut, angka pertama menyatakan Panjang jalan sebenarnya (dalam satuan kilometer), dan angka yang berbeda dalam tanda kurung, menyatakan kecepatan maksimum yang diperbolehkan untuk setiap kendaraan yang melalui jalan tersebut (dalam satuan km/jam). Seorang pimpinan satuan pemadam kebakaran, yang berada di persimpangan S, bermaksud memadamkan api di sebuah Gedung yang terletak di persimpangan G. Dia menggunakan mobil pemadam kebakaran dengan kecepatan maksimum 90km/jam. Bantulah petugas tersebut menemukan rute jalan dengan totoal wakti tercepat dari S ke G dengan menggunakan metode A*.
Menghitung Heuristik
Karena h(n) nya belum diketahui maka kita harus mencari atau menghitung jarak dari dua titik indeks, rumus jarak dua titik adalah sebagai berikut:
Dengan menggunakan rumus di atas, maka perhitungan dari semua titik dapat dilihat sebagai berikut:
| No | Titik Indeks Rute 1 | Hasil |
| 1 | S(1,6) ke A(4,10) | 5 |
| 2 | A(4,10) ke D(16,10) | 12 |
| 3 | D(16,10) ke G(19,6) | 5 |
| 4 | D(16,10) ke E (16,6) | 4 |
| 5 | E(16,6) ke G(19,6) | 3 |
| 6 | E(16,6) ke F(16,2) | 4 |
| 7 | F(16,2) ke G(19,6) | 2,6 |
| 8 | A(4,10) ke B(4,6) | 4 |
| 9 | B(4,6) ke E(16,6) | 12 |
| 10 | E(16,6) ke G(19,6) | 3 |
| 11 | E(16,6) ke D(16,10) | 4 |
| 12 | D(16,10) ke G(19,6) | 5 |
| 13 | E(16,6) ke F(16,2) | 4 |
| 14 | F(16,2) ke G(19,6) | 3 |
| 15 | A(4,10) ke B(4,6) | 4 |
| 16 | B(4,6) ke C(4,2) | 4 |
| 17 | C(4,3) ke F(16,2) | 12 |
| 18 | F(16,2) ke G(19,6) | 2,6 |
| 19 | F(16,2) ke E(16,6) | 4 |
| 20 | E(16,6) ke G(19,6) | 3 |
| 21 | E(16,6) ke D(16,10) | 4 |
| 22 | D(16,10) ke G(19,6) | 5 |
| No | Titik Indeks Rute 2 | Hasil |
| 1 | S(1,6) ke B(4,6) | 3 |
| 2 | B(4,6) ke E(16,6) | 12 |
| 3 | E(16,6) ke G(19,6) | 3 |
| 4 | E(16,6) ke D(16,10) | 4 |
| 5 | D(16,10) ke G(19,6) | 5 |
| 6 | E(16,6) ke F(16,2) | 4 |
| 7 | F(16,2) ke G(19,6) | 2,6 |
| 8 | B(4,6) ke A(4,10) | 4 |
| 9 | A(4,10) ke D(16,10) | 12 |
| 10 | D(16,10) ke G(19,6) | 5 |
| 11 | D(16,10) ke E (16,6) | 4 |
| 12 | E(16,6) ke G(19,6) | 3 |
| 13 | E(16,6) ke F(16,2) | 4 |
| 14 | F(16,2) ke G(19,6) | 2,6 |
| 15 | B(4,6) ke C(4,2) | 4 |
| 16 | C(4,2) ke F(16,2) | 12 |
| 17 | F(16,2) ke G(19,6) | 2,6 |
| 18 | F(16,2) ke E(16,6) | 4 |
| 19 | E(16,6) ke G(19,6) | 3 |
| 20 | E(16,6) ke D(16,10) | 4 |
| 21 | D(16,10) ke G(19,6) | 5 |
| No | Titik Indeks Rute 3 | Hasil |
| 1 | S(1,6) ke C(4,2) | 2,6 |
| 2 | C(4,2) ke F(16,2) | 12 |
| 3 | F(16,2) ke G(19,6) | 2,6 |
| 4 | F(16,2) ke E(16,6) | 4 |
| 5 | E(16,6) ke G(19,6) | 3 |
| 6 | E(16,6) ke D(16,10) | 4 |
| 7 | D(16,10) ke G(19,6) | 5 |
| 8 | C(4,2) ke B(4,6) | 4 |
| 9 | B(4,6) ke E(16,6) | 12 |
| 10 | E(16,6) ke G(19,6) | 3 |
| 11 | E(16,6) ke D(16,10) | 4 |
| 12 | D(16,10) ke G(19,6) | 5 |
| 13 | E(16,6) ke F(16,2) | 4 |
| 14 | F(16,2) ke G(19,6) | 2,6 |
| 15 | C(4,2) ke B(4,6) | 4 |
| 16 | B(4,6) ke A(4,10) | 4 |
| 17 | A(4,10) ke D(16,10) | 12 |
| 18 | D(16,10) ke G(19,6) | 5 |
| 19 | D(16,10) ke E (16,6) | 4 |
| 20 | E(16,6) ke G(19,6) | 3 |
| 21 | E(16,6) ke F(16,2) | 4 |
| 22 | F(16,2) ke G(19,6) | 2,6 |
Langkah pencarian Algoritma A*
Setelah nilai heuristik dari masing – masing node didapat, maka Langkah selanjutnya mencari f(n) menggunakan algoritma A* dengan rumus : f(n) = h(n) + g(n)
Tentukan Starting Point : S
Tentukan nilai f(n) dari setiap suksesor sehingga :
f(A) = 5 + 5 = 10, f(B) = 10 + 3 = 13, f(C) = 5 + 2,6 = 7,6
Dari nilai f(n) pada titik diatas lalu tentukan Best Node yang merupakan jarak terpendek dari graf yang ditemukan, yaitu node C dengan nilai 7,6
Simpan Best Node yang sudah ditemukan dalam Closed List dan simpan node yang lainnya pada Opened List. Sehingga dari langkah pertama didapatkan :
Closed List : [S], Opened List : [A, B, C].
Starting Point : C, karena terpilih sebagai Best Node dan dimasukkan ke Closed List
Bangkitkan Node Suksesor : B dan F
f(B) = jika starting point dari C = SC + CB + h(B) = 5 + 4 + 4 = 13
f(B) sebelumnya saat Starting Point B adalah S yaitu 13 maka sama – sama mendapatkan hasil yang sama.
f(F) = SC + CF + h(F) = 5 + 12 + 12 = 29
Hasil akhir dari tahap 2 yaitu :
Closed List : [S, C], Opened List : [A, B, F].
Cek nilai Opened List yang baru yaitu :
f(A) = 5 + 5 = 10, f(B) = 10 + 3 = 13, f(F) = 29
Best Node adalah node A karena nilai terkecil dari pilihan di atas, sehingga titik A dipilih sebagai Starting Point untuk graf ke 3
Starting Point : A
Bangkitkan Node Suksesor dari A : B dan D
f(B) = jika starting point dari A = SA + AB + h(B) = 5 + 4 + 4 = 13
f(B) sebelumnya saat Starting Point B adalah S yaitu 13 maka sama – sama mendapatkan hasil yang sama.
f(D) = SA + AD + h(D) = 5 + 14 + 12 = 31
Hasil akhir dari tahap 3 yaitu:
Closed List : [S, C, A], Opened List : [B, F, D].
Cek nilai Opened List yang baru yaitu:
f(B) = 10 + 3 = 13, f(F) = 29, f(D) = 31
Best Node adalah node B karena nilai terkecil dari pilihan di atas, sehingga titik B dipilih sebagai Starting Point untuk graf ke 4
Starting Point : B
Bangkitkan Node Suksesor dari B : A, C dan E
Cari nilai f(n) yang belum diketahui yaitu nilai f(E) dan cek kembali nilai f(A) dan f(C) karena nilai B jadi punya 3 parent yaitu S, A, dan C.
E belum pernah ada di open/closed list, maka langsung hitung nilai f(E) = SB + BE + h(E) = 10 + 15 + 12 = 37
Hitung nilai f(A) dan f(C) karena A dan C telah ada di closed list maka perlu dicek terlebih dahulu parent dari B perlu diganti atau tidak.
Ternyata jarak dari S ke B melalui C (S – C – B) adalah (5 + 4 = 9) dan jarak dari S ke B melalui A (S – A – B) adalah (5 + 4 = 9) juga. Karena menghasilkan nilai yang sama, maka dilihat dari kecepatan maksimum yang diperbolehkan untuk setiap kendaraan yang melalui jalan tersebut. Sehingga parent B diganti dari S ke A karena kecepatan maksimum yang diperbolehkan melalu jalan tersebut ialah 90 dan mobil pemadam kebakaran dengan kecepatan maksimum 90km/jam.
A memiliki node suksesor yaitu B dan D, maka nilai f(B) dan f(D) dapat dicek kembali dengan Starting Pointnya dari A yaitu:
f(B) = SA + AB + h(B) = 13
f(D) = SA + AD + h(D) = 5 + 14 + 12 = 31
Closed List : [S, C, A], Opened List : [B, F, D, E].
Maka hasil dari f(n) untuk opened list adalah:
f(B) = 13, f(F) = 29, f(D) = 31, f(E) = 36
Maka yang menjadi best node adalah titik B. Titik B akan menjadi parent untuk langkah selanjutnya dengan menuju titik E.
Dari titik E dengan Node parentnya B maka E memilik suksesor D, F, dan G
f(D) = SB + BE + ED + h(D) = 10 + 15 + 4 + 4 = 33
f(G) = SB + BE + h(G) = 10 + 15 + 3 = 28
f(F) = SB + BE + EF + h(F) = 10 + 15 + 4 + 4 = 33
Maka hasil akhir dari tahap 5 yaitu
Closed List : [S, A, B, C], Opened List : [D, E, F].
Dari hasil akhir didapatkan bahwa jalur terpendek dilalui melalui titik : S > B > E> G dengan nilai 28
Cukup sekian, mohon maaf bila ada kesalahan pengetikkan atau perhitungan rute karena masih dalam proses belajar. Semoga bermanfaat dan terima kasih.
Daftar Pustaka
Kristanto, Andri, 2004, Kecerdasan Buatan, Yogyakarta : Graha Ilmu.
Komentar
Posting Komentar