1. Searching bisa dimaknai sebagai proses pencarian data dari sekian banyaknya data yang tersedia di suatu mesin pencari. Searching didalam AI (artificial Intelegence) adalah salah satu metode penyelesaian masalah dengan pencarian solusi pada suatu permasalahan yang dihadapi. Metode searching pada kecerdasan buatan merupakan searching teerhadap problem space bukan searching data (e, g, angka, karakter, string) tertentu. Ada dua teknik pencarian yang dipakai, yaitu blind search (pencarian buta) dan heuristic search (pencarian terbimbing).
A. Blind Search (pencarian buta)
Pada metode blind search umumnya menggunakan 2 metode yang digunakan, antara lain:
(a) Breadth-First Search (Pencarian Melebar Pertama)
Pada metode Breadth-First Search, semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai dari node akar terus ke level ke-1 dari kiri ke kanan. Kemudian berpindah ke level berikutnya demikian pula dari kiri ke kanan hingga ditemukannya solusi.
(b) Depth-First Search (Pencarian Mendalam Pertama)
Metode Depth-First Search ini akan dilakukan pada proses pencarian semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi. Proses ini akan terus diulangi hingga mendapatkan solusi.
B. Heuristic Search (pencarian terbimbing)
Pada metode ini terdapat 4 metode dalam pencarian heuristic, antara lain:
(a) Generate and Test (Pembangkit dan Pengujian)
Ini merupakan penggabungan antara depth-first search dengan backtracking (pelacakan mundur), yaitu bergerak ke belakang menuju suatu keadaan awal. Nilai pengujian berupa jawaban baik ‘ya’ atau ‘tidak’
(b) Hill Climbing (Pendakian Bukit)
Pada metode ini hampir sama seperti metode pembangkitan dan pengujian, namun proses pengujian ini dilakukan dengan fungsi heuristik. Pembangkitan kondisi yang berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes fungsi heuristik akan menunjukkan seberapa baiknya nilai perkiraan yang diambil terhadap kondisi-kondisi lainnya yang mungkin terjadi.
(c) Best First Search (Pencarian Terbaik Pertama)
Metode best-first search merupakan metode yang mengambil kelebihan dari kedua metode kombinasi dari metode depth-first search dengan metode breadth-first search. Apabila ada pencarian dengan metode hill climbing tidak dapat untuk balik ke node pada level yang lebih rendah walaupun node pada level yang lebih rendah tersebut memiliki nilai heuristik yang lebih baik, lain halnya dengan metode best-first search ini. Pada metode best-fisrt search, pencarian dapat mengunjungi node-node pada level yang lebih tinggi memilki nilai heuristic yang lebih buruk.
(d) Simulated Annealing
Ide dasar terbentuk simulated annealing yaitu dari pemrosesan logam. Annealing (memanaskan kemudian mendinginkan) dalam pemrosesam logam adalah sutau proses bagaimana membuat bentuk cair yang sedikti demi sedikit menjadi bentuk yang lebih padat seiring dengan penurunan pada temperatur. Simulated annealing umumnya digunakan dalam penyelesaian masalah yang dimana perubahan dari suatu kondisi ke kondisi yang lainnya membutuhkan ruang yang sangat besar, misalkan perubahan gerakan dengan menggunakan permutasi pada masalah Travelling Salesman Problem.
• Contoh Breadth-First Search
Dapat dilihat pada contoh dibawah ini bahwa gerakan ke bawah meproses tingkat demi tingkat hinggga tujuannya tercapai. Maka urutan proses searching Braedth-First Search ditunjukan pada gambar adalah dimulai dari S-A-D-B-D-A-E-C-E-E-B-B-F-D-F-B-F-D-E-A-C dan berakhir pada G.
Dibawah ini merupakan contoh depth-first search dimana hanya satu alternatif dipilih dan didesak pada setiap simpul sampai tujuan tercapai atau simpul tercapai bila gerak yang jauh kebawah tidak memungkinkan. Pada saat gerak yang jauh lebih kebawah itu tidak mungkin, maka dalam pencariannya dimulai kembali pada simpul nenek moyang yang terdekat memilki anak-anak yang tidak diselidiki. Pada urutan proses searching depth-first seasrch ditunjukkan pada gambar adalah dimulai dari S-A-B-C-E-D-F- dan berakhir di G.
2. Reasoning (penalaran) yang merupakan teknik penyelesaian masalah dengan cara merepresentasikan masalah kedalam basis pengetahuan (knowledge base) menggunakan logic atau bahasa formal (bahasa yang dipahami computer). Contohnya yaitu apel adalah buah-buahan. Itu merupakan fakta yang benar dan nyata.
Semantic network adalah bentuk link yang memilki arah atau representasi garis deklaratif yang dapat digunakan baik untuk mewakili pengetahuan atau pendukung penalaran pengetahuan sistem otomatis.
Contoh dari analogi sematic network yaitu ada seorang petani, srigala, ayam dan padi. Petani tersebut ingin pindah dengan membawa seekor srigala, ayam dan padi untuk menyebrangi sungai. Sayangnya perahunya terbatas. Yang dapat petani lakukan yaitu dengan membawa 1 objek. Petani tersebut tidak bisa meninggalkan ayam dan srigala dalam satu tempat karena ayam tersebut akan dimakan oleh srigala. Demikian pula petani tidak bisa meninggalkan ayam dan padi dalam satu tempat karena padi akan dihabiskan oleh ayam. Dari permasalahan tersebut kita dapat menggunakan semantic network untuk mempresentasikannya.
Contoh hasil dari implementasi pembuatan app seperti pada permasalahan diatas yaitu:
Kesimpulannya reasoning merupakan fakta yang benar dan nyata sedangkan semantic network merupakan representasi garis deklaratif sebagai pendukung sistem otomatis.
3. Planning (perencanaan) adalah proses yang mendefinisikan tujuan dari organisasi, membuat strategi yang digunakan untuk mencapai tujuan dari organisasi, serta mengembangkan rencana aktivitas kerja organisasi. Perencanaan merupakan proses-proses yang penting dari semua fungsi manajemen sebab tanpa perencanaan (planning) fungsi perorganisasian, pengontrolan maupun pengaarahan tidak akan dapat berjalan. Dalam AI (Artificial Intelegence) sendiri planning mempunyai arti suatu metode penyelesaian masalah dengan cara memecah masalah ke dalam sub-sub masalah yang lebih kecil, menyelesaikan sub-sub masalah satu demi satu, kemudian menggabungkan solusi-solusi dari sub-sub masalah tersebut menjadi sebuah solusi lengkap dengan tetap mengingat dan menangani interaksi yang terdapat pada sub-sub masalah tersebut.
4. Learning adalah bagian dari ilmu kecerdasan buatan atau dikenal juga sebagai AI (Artificial Intelligenci). Konsep dari learning ini adalah pada pengembangan sistem yang dapat belajar “sendiri” tanpa perlu di program oleh manusia berulang kali. Saat ini ilmu pembelajaran mesin sendiri telah menjadi salah satu bagian penting dalam industri bagian di bidang lainnya. Terdapat banyak sekali metode yang terdapat dalam teknik learning dengan berbagai variasinya yang telah diusulkan dan diimplementasikan diantaranya yaitu : decision tree learning, jaringan saraf tiruan, dan algoritma genetika.
Sebagai contoh, perhatikan data penerimaan pegawai pada table di bawah ini. Terdapat 11 orang pelamar kerja dengan 3 paramater / atribut penilaian : IPK (Indeks Prestasi Kumulatif), hasil tes psikologi, dan hasil tes wawancara. IPK dikelompokkan dalam tiga kategori (Bagus, Cukup, Kurang). Hasil tes psikologi dikelompokkan dalam tiga kategori (Tinggi, Sedang, Rendah). Hasil tes wawancara dalam dua kategori (Baik dan Buruk). Untuk data yang lengkap, seharusnya 3 × 3 × 2 = 18 kombinasi sampel data.Tetapi pada tabel tersebut hanya terdapat 11 sampel data. Artinya, masih ada 7sampel data lainnya yang tidak kita ketahui. Misalnya, untuk sampel data : [ IPK = ‘Kurang’, Psikologi = ‘Tinggi’, Wawancara = ‘Buruk’ ], kita tidak memiliki pengetahuan untuk memutusakan: Diterima = ‘Ya’ atau ‘Tidak’.
Ada satu pertanyaan menarik, pada masalah penerimaan pegawai diatas, bisakah kita membuat aturan yang benar dan lengkap seandainya kita mengetahui 18 kombinasi data secara lengkap?
Tentu saja secara manual kita bisa dengan mudah menemukan aturan yang benar dan lengkap karena hanya terdapat 3 atribut dengan 18 kombinasi data, Jika kita mengetahui data secara lengkap, system yang kita bangun tentu saja mampu memberikan keputusan yang 100% akurat. Tetapi, jika parameter yang diperhitungkan lebih dari 3, misalnya 30 atribut dan masing-masing atibut memilki 3 nilai berbeda, maka terdapat 205.891.132.094.649 kombinasi data. Dari kombinasi data yang sangat banyak (lebih dari 200 triliun) seperti ini, bisakah kita menemukan aturan yang benar dan lengkap secara manual? Tentu saja hal ini akan sangat sulit atau bahkan tidak mungkin dilakukan.
Bisakah kita membuat suatu program komputer yang secara otomatis bisa menemukan aturan-aturan yang kita harapkan? Jawabnya adalah bisa. Tetapi untuk kasus dimana kombinasi datanya tidak lengkap, maka kita tidak bisa berharap program komputer akan menemukan aturan yang benar dan lengkap, maka kita tidak bisa berharap program komputer akan menemukan aturan yang benar dan lengkap. Bagaimanapun, program komputer yang sanggup belajar seperti ini akan sangat membantu, meskipun akurasinya tidak 100%. Tetapi, kita bisa membuat program komputer yang juga bisa mempelajari data-data baru (sebagai pengalaman) sehingga membuatnya semakin “pintar” (performansinya menigkat). Secara luas, definisi untuk program komputer yang sanggup meningkatkan performasinya melalui pengalaman (experience).
Contoh Dari Studi Kasus
Dibawah ini terdapat studi kasus dimana sebuah graf simetris tak berarah yang menggambarkan kondisi jalan raya disuatu 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 berada dalam 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 90 km/jam. Bantulah petugas tersebut menemukan rute jalan dengan total waktu 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 diatas maka perhitungan dari semua titik dapat dilihat sebagai berikut :
Table rute 1
| 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 |
Table rute 2
| 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 E (19,6) | 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 |
Table rute 3
| 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 algoritma A* Heuristic
Langkah selanjutnya mencari nilai f(n) menggunakan algoritma A* dengan rumus : f(n) = h(n) + g(n)
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 Clossed 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
Tidak ada komentar:
Posting Komentar