METODE-METODE PENCARIAN DALAM ARTIFICIAL INTELLIGENCE (KECERDASAN BUATAN)

Metode Pencarian/Pelacakan (Search Method) Pada Artificial Intelligence

Pada saat menentukan suatu keberhasilan pada sistem kecerdasan yaitu melalui kesuksesan pencarian  dan pencocokan. Adapun  2 (dua)  teknik pencarian / pelacakan yang dipakai,  yaitu  pencarian  buta  (blind search) dan pencarian terbimbing (heuristic search).

Pencarian Buta / tanpa informasi (Blind Search)

Pada metode pencarian buta (blind search)  umumnya menggunakan 2 metode yang digunakan,  antara lain:

• Pencarian Melebar Pertama (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.
• Pencarian Mendalam Pertama (Depth-First Search) ; 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.

Pencarian Heuristik / dengan informasi (Heuristic Search)

Dalam pencarian  buta tidak dapat sering diterapkan dengan baik, hal  ini dikarenakan dalam waktu aksesnya cukup lama dan besarnya memori yang dipakai. Kelemahan ini dapat diatasi jika memiliki informasi tambahan dari domain yang bersangkutan. Ada 4 metode dalam pencarian heuristik, antara lain:

• Pembangkit dan penggujian (Generate and Test); Metode  ini merupakan  penggabungan  antara  depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju suatu keadaan awal. Nilai Pengujian berupa jawaban baik berupa ‘ya’ atau ‘tidak’. 
• Pendakian bukit (Hill Climbing) ; 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 menunjukan seberapa baiknya nilai perkiraan yang diambil terhadap kondisi-kondisi lainnya yang mungkin terjadi. 
• Pencarian terbaik pertama (Best First Search) ; 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-first search, pencarian dapat mengunjungi node yang ada dilevel yang lebih rendah, jika node pada level yang lebih tinggi memiliki nilai heuristik yang lebih buruk. 
• Simulated Annealing ; Ide dasar terbentuk simulated Annealing yaitu dari pemrosesan logam. Annealing (memanaskan kemudian mendinginkan) dalam pemrosesan logam adalah suatu proses bagaimana  membuat bentuk cair yang sedikit demi sedikit menjadi bentuk yang lebih padat seiring dengan penurunan pada temperatur. Simulated annealing umumnya digunakan dalam penyelesaian masalah yang dimana perubahan keadaan dari suatu kondisi ke kondisi yang lainnya membutuhkan ruang yang sangat besar, misalkan perubahan gerakan dengan menggunakan  permutasi pada masalah Travelling Salesman Problem.

Dibawah ini merupakan  contoh-contoh dari metode pencarian pada kecerdasan buatan (Artificial Intelligence/AI):

• Contoh Breadth-First Search.Dapat dilihat pada contoh ini bahwa gerakan kebawah meproses tingkat demi tingkat hingga tujuannya tercapai. Maka urutan proses seaching Bread-First Search ditunjukkan 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. 

• Contoh Depth-First Search. Contoh ini merupakan depth-first karena hanya satu alternatif dipilih dan didesak pada setiap simpul sampai tujuan tercapai atau simpul tercapai bila gerak yang jauh lebih ke bawah tidak mungkin. Pada saat gerak yang jauh lebih kebawah itu tidak mungkin, maka dalam pencariannya dimulai kembali pada simpul nenek moyang yang terdekat memiliki anak-anak yang tidak diselidiki. Pada urutan proses seaching Depth-First Search ditunjukkan pada gambar adalah dimulai  dari S-A-B-C-E-D-F- dan berakhir di G. 

• Pada gambar ini menunjukkan jarak garis lurus dari tiap-tiap kota ke tujuan.  Sehingga kita dapat mengetahui jarak-jarak antara masing-masing kota dan tujuan. Jika kita harus mencapai tujuan, maka lebih baik berada dalam suatu kota terdekat, tetapi tidak selalu begitu; Kota C lebih dekat dari pada seluruhnya kecuali kota F, tetapi kota C bukanlah tempat yang baik untuk ditempati. 

contoh Hill Climbing. Pada gambar ini menunjukkan apa yang terjadi jika pendakian bukit(hill climbing) digunakan terhadap masalah transversal map dengan menggunakan jarak terbang burung gagak untuk mengatur pilihan. Hill Climbing ini merupakan pencarian depth-first yang memiliki ukuran heurestik yang ,mengatur pilihan-pilihan sebab simpul diperluas. Angka-Angka disamping simpul merupakan jarak garis lurus dari kota yang memiliki terakhir ke kota tujuan. 

• Contoh gambar pohon pencarian yang mempunyai simpul resep ini menunjukkan bagian pohon pencarian yang berawal dari resep dasar untuk telur dadar aprikot. Transformasi-transformasi bahan membentuk pohon; Interestingness heurestics ( heuristik yang menarik)  mengarahkan pencarian best-first pada peluang-peluang yang lebih baik. Pada gambar ini kita dapat menemukan resep telur dadar strawberry dengan mengunakan transformasi subtitusi dasar resep dadar aprikot. Setelah mempunyai dadar strawberry, kita dapat melanjutkan untuk menemukan resep pisang strawberry, dengan menggunakan transformasi tambahan.  Sehingga pengetahuan yang lebih banyak biasanya dapat mengurangi waktu pencarian. 

• Contoh sebuah rute yang dapat dilewati sales tersebut dimana harus melewati setiap perumahan yang tepat sekali. Terdapat 4 Perumahan, dengan jarak  masing-masing kota AB=10, AC=20, AD=25, BC=15, BD=10 CD=30. Tujuannya adalah mencari jarak terpendek bagi sales untuk mengunjungi semua perumahan sekali. Penyelesaian menggunakan generate-test adalah dengan membangkitkan solusi-solusi yang mungkin ada sesuai permasalahan yang dihadapi oleh sales tersebut. Kombinasi abjad sebagai solusi yang mungkin adalah n! = 4! = 24. Tujuannya agar dapat mencari solusii rute terpendek.Rute dikatakan valid apabila jalur yang dilalui tidak berjarak 0. Jika rute valid, maka jarak dihitung kemudian dibandingkan untuk mendapatkan jarak yang sangat optimal.

No Pencarian	Lintasan	Panjang Lintasan	Lintasan yang dipilih	Panjang Lintasan
1	ABCD	45	ABCD	45
2	ABDC	40	ABDC	40
3	ACBD	45	ABDC	40
4	ACDB	50	ABDC	40
5	ADCB	60	ABDC	40
6	ADCB	60	ABDC	40
7	BACD	50	ABDC	40
8	BADC	55	ABDC	40
9	BCAD	60	ABDC	40
10	BCDA	60	ABDC	40
11	BDAC	55	ABDC	40
12	BDCA	50	ABDC	40
13	CABD	45	ABDC	40
14	CADB	55	ABDC	40
15	CBAD	50	ABDC	40
16	CBDA	50	ABDC	40
17	CDAB	55	ABDC	40
18	CDBA	40	ABDC/CDBA	40
19	DABC	50	ABDC/CDBA	40
20	DACB	60	ABDC/CDBA	40
21	DBAC	40	ABDC/CDBA/DBAC	40
22	DBCA	45	ABDC/CDBA/DBAC	40
23	DCAB	50	ABDC/CDBA/DBAC	40
24	DCBA	45	ABDC/CDBA/DBAC	40

Dari tabel diatas, solusi pertama yang dibangkitkan adalah ABCD = 45, solusi kedua ABDC=40. Ternyata solusi kedua menghasilkan jarak yang lebih pendek sehingga dipilih lintasan ABDC=40. Lakukan untuk langkah selanjutnya. Pada tabel didapat solusi terpendek lagi yang sama dengan ABDC yaitu CDBA atau DBAC. Kelemahan dari teknik generate & test ini memerlukan dibangkitkan semua kemungkinan yang ada sehingga jika ditambahkan satu perumahan untuk permasalahan TSP ini yaitu menjadi 5 perumahan akan memerlukan 120 kombinasi lintasan, kecuali diberikan kondisi tertentu misalnya perumahan awal bagi sales telah ditentukan.

REFERENSI :

• Library Binus. BAB II LANDASAN TEORI Pengenalan Kecerdasan Buatan.http://library.binus.ac.id/eColls/eThesisdoc/Bab2HTML/2007300192IFBab2/page10.html(diakses pada tanggal 30 November 2017). 
• D. Suryadi H.S.1995. PENGANTAR INTELIGENSI BUATAN. Jakarta: Universitas Gunadarma. 
• Faizal, Antok. 2015. Search 2 Pertemuan ke Lima.http://slideplayer.info/slide/3111374/(diakses pada tanggal 3 Desember 2017)
• Metode-Algoritma.com. Juni 2013.TSP dengan Algoritma Generate & Test. http://www.metode-algoritma.com/2013/06/tsp-dengan-algoritma-generate-test.html (diakses pada tanggal 5 Desember 2017)