Sistem Kecerdasan Buatan

Definisi Kecerdasan Buatan

Istilah kecerdasan buatan sebenarnya berasal dari bahasa Inggris: “Artificial Intelligence”. Jika diartikan tiap kata, artificial artinya buatan, sedangkan intelligence adalah kata sifat yang berarti cerdas. Jadi artificial intelligence maksudnya adalah sesuatu buatan atau suatu tiruan yang cerdas. Cerdas di sini kemungkinan maksudnya adalah kepandaian atau ketajaman dalam berpikir, seperti halnya otak manusia dalam menyelesaikan suatu masalah.

Kecerdasan buatan merupakan salah satu cabang bagian ilmu komputer yang membuat agar mesin (komputer) dapat melakukan pekerjaan seperti dan sebaik yang dilakukan oleh manusia, dan dalam merepresentasikan pengetahuan lebih banyak menggunakan bentuk simbol-simbol daripada bilangan dan proses informasi berdasarkan metode heuristic1 atau dengan berdasarkan sejumlah aturan.

Artificial Intelligence (AI) merupakan sub bidang pengetahuan komputer yang khusus ditujukan untuk membuat software dan hardware yang sepenuhnya bisa menirukan beberapa fungsi otak manusia.

Manusia bisa menjadi pandai dalam menyelesaikan segala permasalahan di dunia ini karena manusia mempunyai pengetahuan dan pengalaman Pengetahuan diperoleh dari belajar. Semakin banyak bekal pengetahuan yang dimiliki oleh seseorang tentu saja diharapkan akan lebih mampu dalam menyelesaikan permasalahan. Namu bekal pengetahuan saja tidak cukup, manusia juga diberi akal untuk melakukan penalaran, mengambil kesimpulan berdasarkan pengetahuan dan pengalaman yang mereka miliki. Tanpa memiliki kemampuan untuk menalar dengan baik, manusia dengan segudang pengalaman dan pengetahuan tidak akan dapat menyelesaikan masalah dengan baik. Demikian pula dengan kemampuan menalar yang sangat baik, namun tanpa bekal pengetahuan dan pengalaman yang memadai, manusia juga tidak akan bisa menyelesaikan masalah dengan baik.

Agar komputer bisa bertindak seperti dan sebaik manusia, maka komputer juga harus diberi bekal pengetahuan dan mempunyai kemampuan untuk menalar. Untuk itu AI akan mencoba untuk memberikan beberapa metoda untuk membekali komputer dengan kedua komponen tersebut agar komputer bisa menjadi mesin pintar.

METODE PENCARIAN DAN PELACAKAN

Pelacakan adalah teknik untuk pencarian. Didalam pencarian ada dua kemungkinan hasil yang didapat yaitu menemukan dan tidak menemukan. Sehingga pencarian merupakan teknik yang penting dalam AI. Hal penting dalam menentukan keberhasilan sistem berdasarkan kecerdasan adalah kesuksesan dalam pencarian dan pencocokan. Pencarian adalah suatu proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state place). Ruang keadaan merupakan suatu ruang yang berisi semua keadaan yang mungkin.

Untuk mengukur performansi metode pencarian, terdapat empat kriteria yang dapat digunakan :

• Completeness (Kelengkapan) : apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada ?
• Time compexity (Kekompleksan waktu) : berapa lama waktu yang diperlukan ?
• Space complexity (Kekompleksan ruang) : berapa banyak memori yang di perlukan ?
• Optimality (Optimal) : apakah metode tersebut menjamin menemukan solusi yang terbaik jika beberapa solusi berbeda ?

Searching di dalam AI (Artificial Intelligence) adalah salah satu motode penyelesaian masalah dengan pencarian solusi pada suatu permasalahan yang dihadapi.
Teknik searching sendiri terbagi menjadi dua, yaitu:

1. Blind searching
2. Heuristic searching 

1.      Blind Searching
            Blind Searching adalah model pencarian buta atau pencarian yang tidak memiliki inforamasi awal, model pencarian ini memiliki tiga ciri – ciri utama yaitu:
-          Membangkitkan simpul berdasarkan urutan
-          Kalau ada solusi maka solusi akan ditemukan
-          Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui).

BFS (Breadth-first Search)atau sering disebut juga pencarian melebar
contoh

pada BFS teknik pencarian pesoalannya adalah dengan membuka node (titik) per levelnya.. sehingga pada persoalan diatas penyelesaian pada BFS adalah.

jadi urutan node yang di lalui pada pencarian BFS adalah. a,b,c,d,e,f,g,h

DFS (Depth-first Search)atau sering disebut juga pencarian mendalam
sesuai namanya pencarian mendalam, DFS tidak mencari solusi per level, namun mencari pada kedalaman sebelah kiri terlebih dahulu. masih menggunakan permasalahan di awal, pada DFS akan di dapatkan solusi seperti ini.

jadi solusi node yang di lalui pada DFS adalah a,b,e,h
dfs memiliki beberapa keuntungan,yaitu memori yang di gunakan tidak terlalu banyak karena tidak membuka semua node.

UCS (Uniform cost search) perpaduan antara BFS dan DFS
pada UCS, pencarian nya mempehatikan cost/jarak antara 1 node ke node lain.
contoh nya.

pada permasalahan diatas telah ditentukan jarak antara node. maka pada ucs akan membuka node yang memiliki nilai/cost antar node yang terendah.
pada gambar diatas jika kita buka
c = 10
b = 20
a = 10

karena nilai c dan a sama maka teserah mau buka yang mana lebih dahulu.
seandainya kita mebuka c maka kita teruskan pencariannya, jika kita buka 
d = 10+5 =15
e = 10+40 = 50 (mencapai goal, namun nilai cost nya dirasa masih terlalu besar)

maka kita buka node d, lalu akan didapat
e = 10+5+30 = 45 (nilai pada pencarian ini pun terasa masih terlau besar) maka dari itu kita buka node yang kecil di awal tadi yaitu node a

setelah kita buka node a akan di dapat
e = 10 + 20 = 30 (di dapatkan goal dengan solusi terbaik)

dari kasus diatas dapat kita lihat, ada banyak cara unuk mendapatkan solusi. namun dari berbagai macam penyelesaian kasus, kita dapat mencari solusi yang paling optimal dan ini lah ke unggulan dari UCS

2.     Teknik Pencarian Heuristik (Heuristic Search)

Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness).
Fungsi heuristik digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
Jenis-jenis Heuristic Searching:
– Generate and Test.
– Hill Climbing.
– Best First Search.
– Means-EndAnlysis, Constraint Satisfaction, dll.

PEMBANGKITAN dan PENGUJIAN (Generate and Test)

Metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal.

      Algoritma :

1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu tititk tertentu atau lintasan tertentu dari keadaan awal).
2. Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node terebut atau node akhir dari suatu lintasan yang  dipilih dengan kumpulan tujuan yang diharapkan.
3. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama.


Contoh : “Travelling Salesman Problem (TSP)”


*) Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui ruter terpendek dimana setaip kota hanya  boleh dikkunjungi tepat 1 kali. Misalkan ada 4 kota  dengan jarak antara tiap-tiap kota seperti berikut ini :

Alur pencarian dengan Generate and Test 

Pencarian ke-	Lintasan	Panjang Lintasan	Lintasan terpilih	Panjang Lintasan terpilih
1	ABCD	19	ABCD	19
2	ABDC	18	ABDC	18
3	ACBD	12	ACBD	12
4	ACDB	13	ACBD	12
5	ADBC	16	ACBD	12
Dst…..


 PENDAKIAN BUKIT (Hill Climbing)
• Metode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnyayang mungkin.
• Algoritma:
1. Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
a) Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang : Cari operator yang belum digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
b) Evaluasi keadaan baru tersebut : – Jika keadaan baru merupakan tujuan, keluar – Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang. – Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.
• Contoh: TSP dengan Simple Hill Climbing Disini ruang keadaan berisi semua kemungkinan lintasan yang mungkin. Operator digunakan untuk menukar posisi kota-kota yang bersebelahan. Apabila ada n kota, dan kita ingin mencari kombinasi lintasan dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan sebanyak n!/2!(n-2)! atau sebanyak 6 kombinasi. Fungsi heuristic yang digunakan adalah panjang lintasan yang terjadi.

Refrensi:

https://prezi.com/oekxfwhdazr5/blind-search-and-heuristik/

yuliana.lecturer.pens.ac.id/.../Search%20Algoritma/Praktikum%20-%20Blind%20Sear...

hendrik.staff.gunadarma.ac.id/Downloads/files/23065/teknik-pencarian-heuristik.pdf

cs.unsyiah.ac.id/~irvanizam/ai/INF303-05.pdf

artint.info/html/ArtInt_56.html