kecerdasan buatan

 

 

1. Jadi tekhnik untuk menyelesaikan suatu masalah kecerdasan buatan dengan baik yaitu harus:

1.       Mendefinisikan suatu ruang keadaan masalah dengan tepat

2.       Menganalisis masalah tersebut serta mencari  beberapa tekhnik penyelesaian masalah yang sesuai dan menetapkan satu atau lebih keadaan awal (initial state)

3.       Mempresentasikan pengetahuan untuk menyelesaikan masalah tersebut dan menetapkan satu atau lebih tujuan.

4.       Menetapkan kumpulan aturan dan memilih tekhnik penyelesaian masalah yang terbaik.

2.    A. Blind Search atau Uninformed Search dan Heuristic Search atau Informed Searchmengacu kepada metode pencarian dan perbedaan yang sangat menonjol terletakbahwa Blind Search mengacu kepada pencarian tidak memiliki informasi ataupengetahuan tambahan mengenai kondisi di luar dari yang telah disediakan olehdefinisi masalah sedangkan Heuristic Search mengacu kepada pencarian denganmemiliki informasi atau pengetahuan tambahan mengenai kondisi di luar dari yangtelah disediakan oleh definisi masalah.A.Blind Search ( Uninformed Search)Blind Search atau Uninformed Search secara umum mengartikan bahwa saatproses pencarian kita tidak memiliki clue/hint apakah hasil yang ditemukan. lebih baik daripada yang lainnya, sehingga kita tidak mengetahui apakah hasildari eksplorasi tersebut bermanfaat secara maksimal atau tidak.Search Space(ruang pencarian) dieksplorasi tanpa memanfaatkan apapuun informasi yangmenyangkut pada masalah.

 Contoh dari Blind Search:

1.       Breadth-First Search (BFS)BFS adalah algoritma penelusuran yang memulai penelusuran dari nodeyang ditentukan (source atau node awal) dan proses penelusuran(explore) dilakukan pada tiap tingkat terlebih dahulu. Hal inimemastikan neighbour node (node yang terhubung secara langsungdengan node source) dapat ditemukan. Lalu proses akan dilanjutkan keneighbour node di tingkat selanjutnya.

2.       Uniform-Cost Search(UCS) Bila pada BFS, pencarian dilakukan dengan melakukan ekspansi nodeberdasarkan urutan kedalaman dari root, maka pada uniform costsearch, ekspansi dilakukan berdasarkan cost / biaya dari root. Padasetiap langkah, ekspansi berikutnya ditentukan berdasarkan costterendah atau disebut sebagai fungsi g(n) dimana g(n) merupakanjumlah biaya edge dari root menuju node n. Node-node tersebutdisimpan menggunakan priority queue.

3.       Depth-First SearchAlgoritme DFS adalah algoritma recursion yang memanfaatkanbacktracking. Algoritma ini melakukan pencarian secara mendalampada semua node dengan terus melakukan pencarian ke bawah selamamemungkinkan. Jika tidak memungkinkan, algoritma ini akan beralih

Contoh dari heuristic search :

 

B.            Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness). Fungsi heuristik digunakan untuk mengevaluasi keadaankeadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan. Jenis-jenis Heuristic Searching:

Metode Pencarian Terdapat banyak metode yang telah diusulkan.

Semua metode yang ada dapat dibedakan ke dalam 2 jenis :

1. Pencarian buta / tanpa informasi (blind / un-informed search)

2. Pencarian heuristik / dengan informasi (heuristic atau informed search)

setiap metode mempunyai karakteristik yang berbeda-beda dengan kelebihan dan kekurangan masing-masing. Kriteria mengukur performansi

1. Completeness :

Apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada?

2. Time complexity :

Berapa lama waktu yang diperlukan ?

3. Space complexity :

Berapa banyak memori yang diperlukan ?

4. Optimality :

Apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi yang berbeda ?

4 . Heuristic Searching Sebagai Dasar dari Kecerdasan Buatan

Para peneliti awal kecerdasan buatan menitik beratkan pada penyelesaian masalah yang tidak menggunakan metoda komputasi konvensional.

Hal ini disebabkan metoda pemecahan masalah konvensional tidak dapat lagi digunakan.

Permasalahan pada sistem KB tidak memiliki algoritma tertentu. Kalaupun ada tentulah sangat kompleks.

Karena itu haruslah ditemukan sebuah teknik baru yang mirip dengan cara yang digunakan oleh manusia untuk menyelesaikan masalah dan dapat diimplementasikan pada komputer.

 

5 Salah satu metoda yang cukup terkenal adalah metoda searching.

Searching dalam sebuah struktur data telah menjadi dasar bagi algoritma komputer, tetapi proses searching pada KB memiliki perbedaan.

Metoda searching pada KB merupakan searching terhadap problem space bukan searching data (e.g., angka, karakter, string) tertentu.

6 Proses searching ini berupa jalur yang menggambarkan keadaan awal sebuah masalah menuju kepada penyelesaian masalah yang diinginkan (i.e., the solved problem).

Jalur-jalur ini mengambarkan langkah-langkah penyelesaian masalah.

Melalui proses searching menuju sebuah penyelesaian akan terbentuk sebuah solution space.

 

7 Perhatikan contoh penyelesaian masalah komputer pada Gambar 1.4.

Langkah pertama untuk mengetahui apakah komputer dapat digunakan atau tidak adalah men-switch ON.

Selanjutnya dengan melakukan inspeksi terhadap kondisi lampu indikator kita dapat menentukan langkah berikutnya.

Misalnya kondisi lampu OFF.

Dengan melakukan searching terhadap problem space kita akan tiba pada sebuah penyelesaian masalah agar komputer dapat diaktifkan kembali.

 

9 BLIND / UN-INFORMED SEARCH

Istilah blind atau buta digunakan karena memang tidak ada informasi awal yang digunakan dalam proses pencarian.

3.       Berikut ini, sekilas 6 metode yang tergolong blind search

 

a)      Breadth-First Search (BFS)

b)      Depth-First Search (DFS)

c)       Depth-Limited Search (DLS)

d)      Uniform Cost Search (UCS)

e)      Iterative-Deepening Search (IDS)

f)       Bi-Directional Search (BDS)

 

AA).

a).  Breadth-first Search

Breadth-first search (BFS) melakukan proses searching pada semua node yang berada pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan proses searching pada node di level berikutnya.

Urutan proses searching BFS ditunjukkan dalam Gambar 1.6 adalah: A,B,C,D,E,F,  Breadth-First Search 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 Example: Perjalanan dari Arad ke Bucharest  First Step Second StepThird Step  Keuntungan Tidak akan menemui jalan buntu (solusi lebih optimal)

Jika ada satu solusi, maka breadth-first search akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.

 Kelemahan:

Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon (membutuhkan simpul yam umumnya relatif banyak)

Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level yang ke-(n+1)

b).  Depth-first Search

Depth-first search (DFS) adalah proses searching sistematis buta yang melakukan ekpansi sebuah path (jalur) menuju penyelesaian masalah sebelum melakukan ekplorasi terhadap path yang lain.

Proses searching mengikuti sebuah path tunggal sampai menemukan goal atau dead end.

Apabila proses searching menemukan dead-end, DFS akan melakukan penelusuran balik ke node terakhir untuk melihat apakah node tersebut memiliki path cabang yang belum dieksplorasi.

 Apabila cabang ditemukan, DFS akan melakukan cabang tersebut.

Apabila sudah tidak ada lagi cabang yang dapat dieksplorasi, DFS akan kembali ke node parent dan melakukan proses searching terhadap cabang yang belum dieksplorasi dari node parent sampai menemukan penyelesaian masalah.

Urutan proses searching DFS ditunjukkan dalam Gambar 1.5 adalah: A, B, E, F, G, C, ...

 

 

 Kelebihan DFS adalah:

Pemakaian memori hanya sedikit, berbeda jauh dengan BFS yang harus menyimpan semua node yang pernah dibangkitkan.Jika solusi yang dicari berada pada level yang dalam dan paling kiri,maka DFS akan menemukannya secara cepat.

Kelemahan DFS adalah: Jika pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi (Tidak Complete).

Jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling baik (Tidak Optimal).

c).  Depth-Limited Search (DLS)

Metode ini berusaha mengatasi kelemahan DFS (tidak complete) dengan membatasi kelemahan maksimum dari suatu jalur solusi.Tetapi, sebelum menggunakan DLS, kita harus tahu berapa level maksimum dari suatu solusi.

 Definisi

Algoritma Depth-Limited Search (DLS), adalah salah satu jenis algoritma pencarian solusi. Algoritma ini dijalankan dengan cara membangkitkan pohon pencarian secara dinamis. Pencarian solusi dilakukan secara mendalam.Pada dasarnya, algoritma DLS sama dengan algoritma DFS, hanya saja dalam permasalahan penelusuran graf, sebelumnya ditentukan terlebih dahulu batas maksimum level yang dikunjungi. Algoritma Misalkan terdapat graf/pohon dengan n buah simpul dan v merupakan simpul awal penelusuran maka algoritma DFS adalah sebagai berikut:

Tentukan batas kedalaman pohon yang akan dikunjungi.Kunjungi simpul v.

Kunjungi simpul w yang bertetangga dengan simpul v, yang berada di kedalaman pohon <= batas.

Ulangi DLS mulai dari simpul w.

Ketika mencapai simpul u sedemikian sehingga semua simpul yang bertetangga dengannya telah dikunjungi, pencarian dirunut-balik (backtrack) ke simpul terakhir yang dikunjungi sebelumnya dan mempunyai simpul w yang belum dikunjungi.

Pencarian berakhir bila tidak ada lagi simpul yang belum dikunjungi yang dapat dicapai dari simpul yang telah dikunjungi dalam kedalaman pohon <= batas.

 Kelebihan dan Kekurangan

DLS lahir untuk mengatasi kelemahan DFS(tidak complete) dengan membatasi kedalaman maksimum dari suatu jalur solusi. Tetapi harus diketahui atau ada batasan dari sistem tentang level maksimum. Jika batasan kedalaman terlalu kecil, DLS tidak complete.

Contoh 1 :Bila simpul awal adalah 1 dan batas kedalaman adalah 3 maka urutan dikunjunginya adalah 1, 2, 4, 5, 3, 6,7.

Contoh 2 : Bila simpul awal juga 1 dan batas kedalaman adalah 3 maka urutan dikunjunginya adalah 1, 2, 5, 6, 3, 7, 4

 Definisi

Water Jug problem adalah masalah yang membutuhkan konversi situasi menjadi situasi lain yang diinginkan dengan menggunakan sekumpulan operasi tertentu. Dan masalah ini dapat di selesaikan dengan merepresentasikan semua kemungkinan hasil dalam sebuah pohon. Maka masalah ini dapat dikategorikan sebagai masalah yang membutuhkan penelusuran graf.

Oleh karena itu penulis berpendapat bahwa masalah ini dapat diselesaikan dengan baik dengan menggunakan keempat algoritma tersebut (BFS, DFS, DLS, dan IDS).

Contoh 1 :Kita mempunyai sebuah gelas dengan kapasitas 4 liter dan sebuah gelas yang lain dengan kapasitas (misalkan) 3 liter. Kedua gelas tidak memiliki skala ukuran dan dalam keadaan kosong.

Kita ingin mendapatkan air sebanyak 2 liter dalam gelas yang berkapasitas 4 liter dan tidak boleh mendapatkannya dengan menggunakan prediksi sendiri. Selain itu, kita harus mengikuti suatu operasi-operasi tertentu.

x adalah gelas dengan kapasitas 4 liter

y adalah gelas dengan kapasitas 3 liter

Pencarian Solusi dengan menggunakan algoritma DLS

6 1 2 3 4 5 8 7

Langkah-langkah yang dilakukan dalam pencarian solusi menggunakan algoritma DLS adalah Tentukan kedalaman simpul yang dikunjungi (n), misalkan n=5.Masukkan simpul akar (0, 0) ke dalam antrian q, jika simpul akar adalah simpul tujuan (goal node) maka solusi ditemukan.Stop. Jika S kosong, tidak ada solusi. Stop.Cek apakah sesuai dengan keinginan (2,0).Jika true maka solusi ketemu. Jika false maka bangkitkan simpul tetangga, dan ulang (2), hingga kedalaman simpul yang dikunjungi <= 5.Source Code

d). procedure DLS (input v: Point, level:integer) kamus w: point q: antrian algoritma write(v) dikunjungi[v] ← true {array untuk menampung simpul yang sudah dikunjungi} level  1 while not level > 5 do { kunjungi semua simpul di level 1,panggl algoritma DFS} if A[v,w] = 1 then {simpul v dan simpul w bertetangga} if not dikunjungi[w] then DLS(w, level) endif level  level +1 endwhile

Perbandingan Strategi Pencarian Keterangan  faktor percabangan kedalaman solusi kedalaman maksimum pohon pencarian kedalaman.

 

 

e).  Uniform Cost Search (UCS) Konsepnya hampir sama dengan BFS, bedanya adalah bahwa BFS menggunakan urutan level yang paling rendah sampai yang paling tinggi, sedangkan UCS menggunakan urutan biaya dari yang paling kecil sampai yang terbesar.

UCS berusaha menemukan solusi dengan total biaya terendah yang dihitung berdasarkan biaya dari simpul asal menuju ke simpul tujuan.

f).  Iterative-Deepening Search (IDS)

IDS merupakan metode yang menggabungkan kelebihan BFS (Complete dan Optimal) dengan kelebihan DFS (space complexity rendah atau membutuhkan sedikit memori) Tetapi konsekwensinya adalah time complexitynya menjadi tinggi.

4. kegunaan AI dalam kehidupan sehari hari:

1.       Streaming video/Musik.

2.       Search Engine

3.       Fitur Selfie

4.       4.GPS

5.       5.pemesanan Ojek online.