PENGANTAR KECERDASAN BUATAN (ARTIFICIAL INTELLIGENCE)
Definisi Kecerdasan Buatan
· H. A. Simon [1987] :
“ Kecerdasan buatan (artificial intelligence) merupakan kawasan penelitian, aplikasi dan instruksi yang terkait dengan pemrograman komputer untuk melakukan sesuatu hal yang dalam pandangan manusia adalah- cerdas”Definisi Kecerdasan Buatan
· H. A. Simon [1987] :
· Rich and Knight [1991]:
“Kecerdasan Buatan (AI) merupakan sebuah studi tentang bagaimana membuat komputer melakukan hal-hal yang pada saat ini dapat dilakukan lebih baik oleh manusia.”
· Encyclopedia Britannica:
“Kecerdasan Buatan (AI) merupakan cabang dari ilmu komputer yang
dalam merepresentasi pengetahuan lebih banyak menggunakan bentuk
simbol-simbol daripada bilangan, dan memproses informasi berdasarkan
metode heuristic atau dengan berdasarkan sejumlah aturan”
Tujuan dari kecerdasan buatan menurut Winston dan Prendergast [1984]:
1. Membuat mesin menjadi lebih pintar (tujuan utama)
2. Memahami apa itu kecerdasan (tujuan ilmiah)
3. Membuat mesin lebih bermanfaat (tujuan entrepreneurial)
AI dapat dipandang dalam berbagai perspektif.
· Dari perspektif Kecerdasan (Intelligence)
AI adalah bagaimana membuat mesin yang “cerdas” dan dapat
melakukan hal-hal yang sebelumnya dapat dilakukan oleh manusia
· Dari perspektif bisnis, AI adalah sekelompok alat bantu (tools) yang
berdaya guna, dan metodologi yang menggunakan tool-tool tersebut
guna menyelesaikan masalah-masalah bisnis.
· Dari perspektif pemrograman (Programming), AI termasuk didalamnya
adalah studi tentang pemrograman simbolik, pemecahan masalah,
proses pencarian (search)
n 1970
o “Artificial intelligence” adalah nama pada akar dari studi area.
KONSEP DAN DEFINISI DALAM KECERDASAN BUATAN TURING TEST
Metode Pengujian Kecerdasan
· Turing Test merupakan sebuah metode pengujian kecerdasan yang
dibuat oleh Alan Turing.
· Proses uji ini melibatkan seorang penanya (manusia) dan dua obyek
yang ditanyai. Yang satu adalah seorang manusia dan satunya adalah
sebuah mesin yang akan diuji.
· Penanya tidak bisa melihat langsung kepada obyek yg ditanyai
· Penanya diminta untuk membedakan mana jawaban komputer dan
mana jawaban manusia berdasarkan jawaban kedua obyek tersebut.
· Jika penanya tidak dapat membedakan mana jawaban mesin dan mana
jawaban manusia maka Turing berpendapat bahwa mesin yang diuji
tersebut dapat diasumsikan CERDAS.
Pengantar Kecerdasan Buatan - 4
PEMROSESAN SIMBOLIK
· Komputer semula didisain untuk memproses bilangan/angka-angka
(pemrosesan numerik).
· Sementara manusia dalam berpikir dan menyelesaikan masalah lebih
bersifat simbolik, tidak didasarkan kepada sejumlah rumus atau
melakukan komputasi matematis.
· Sifat penting dari AI adalah bahwa AI merupakan bagian dari ilmu
komputer yang melukan proses secara simbolik dan non-algoritmik
dalam penyelesaian masalah
HEURISTIC
· Istilah Heuristic diambil dari bahasa Yunani yang berarti menemukan
· Heuristic merupakan suatu strategi untuk melakukan proses pencarian
(search) ruang problema secara selektif, yang memandu proses
pencarian yang kita lakukan disepanjang jalur yang memiliki
kemungkinan sukses paling besar.
PENARIKAN KESIMPULAN (INFERENCING)
· AI mecoba membuat mesin memiliki kemampuan berpikir atau
mempertimbangkan (reasoning)
· Kemampuan berpikir (reasoning) termasuk didalamnya proses penarikan
kesimpulan (inferencing) berdasarkan fakta-fakta dan aturan dengan
menggunakan metode heuristik atau metode pencarian lainnya.
PENCOCOKAN POLA (PATTERN MATCHING)
· AI bekerja dengan metode pencocokan pola (pattern matching) yang
berusaha untuk menjelaskan obyek, kejadian (events) atau proses,
dalam hubungan logik atau komputasional.
1. 4 Perbandingan Kecerdasan Buatan dengan Kecerdasan Alamiah
Keuntungan Kecerdasan Buatan dibanding kecerdasan alamiah:
· lebih permanen
· memberikan kemudahan dalam duplikasi dan penyebaran
· relatif lebih murah dari kecerdasan alamiah
· Konsisten dan teliti
· Dapat didokumentasi
· Dapat mengerjakan beberapa task dengan lebih cepat dan lebih baik
dibanding manusia
Keuntungan Kecerdasan Alamiah dibanding kecerdasan buatan
· Bersifat lebih kreatif
· Dapat melakukan proses pembelajaran secara langsung, sementara AI
harus mendapatkan masukan berupa simbol dan representasirepresentasi
Pengantar Kecerdasan Buatan - 5
· Fokus yang luas sebagai referensi untuk pengambilan keputusan
sebaliknya AI menggunakan fokus yang sempit
Komputer dapat digunakan untuk mengumpulkan informasi tentang obyek,
kegiatan (events), proses dan dapat memproses sejumlah besar
informasi dengan lebih efisien dari yang dapat dikerjakan manusia, tetapi
disisi lain manusia –dengan menggunakan insting- dapat melakukan hal yang
sulit untuk diprogram pada komputer, yaitu: manusia dapat mengenali
(recognize) hubungan antara hal-hal tersebut, menilai kualitas dan
menemukan pola yang menjelaskan hubungan tersebut.
Metode Search dalam Kecerdasan Buatan
1.Breadth-first Search
Breadth-first search adalah algoritma yang
melakukan pencarian secara melebar yang
mengunjungi simpul secara preorder yaitu
mengunjungi suatu simpul kemudian mengunjungi
semua simpul yang bertetangga dengan simpul
tersebut terlebih dahulu. Selanjutnya, simpul yang
belum dikunjungi dan bertetangga dengan simpulsimpul
yang tadi dikunjungi , demikian seterusnya.
Jika graf berbentuk pohon berakar, maka semua
simpul pada aras d dikunjungi lebih dahulu
sebelum simpul-simpul pad aras d+1.
Algoritma ini memerluka-n sebuah antrian q untuk
dengannya. Tiap simpul yang telah dikunjungu
masuk ke dalam antrian hanya satu kali.
Algoritma ini juga membutuhkan table Boolean
untuk menyimpan simpul yang te lah dikunjungi
sehingga tidak ada simpul yang dikunjungi lebih
dari satu kali.
Salah satu contoh kakas pencarian yang
menggunakan metode BFS adalah WebCrawler.
WebCrawler adalah suatu kakas yang membuat
indeks isi dari suatu dokumen di Web yang
selanjutnya akan dimanfaatkan oleh mesin pencari.
Terdapat tiga langkah yang dilakukan oleh
WebCrawler ini ketika mengunjungi dokumen,
yaitu menandai bahwa suatu dokumen telah
dikunjungi, mengenali link yang terdapat pada
dokumen tersebut, kemudian isinya didaftarkan
pada daftar indeks.
Pada akhirnya, WebCrawler aakan menampilkan
file yang paling banyak berkaitan dengan kata
kunci.
2.Depth-first Search
Depth-first search (DFS) melakukan pencarian
secara preorder. Mengunjungi anak suatu simpul
sebelum simpul tetangganya. Berkaitan dengan
mesin pencari, DFS ini cenderung mengindeks
dokumen berdasarkan suatu link.Algoritma DFS yang diterapkan pada mesin pencari
dalam melakukan pengindeksan adalah
mengunjungi suatu server kemudian menyimpansemua link yang berhubungan dengan server
tersebut baru kemudian mengunjungi server lain.
Salah satu yang menerapkan algoritma DFS pada
mesin pencarian adalah FTPSearch.
FTPSearch adalah suatu mesin pencari dokumen
yang tersimpan di jaringan ITB. Dapat diakses pada
http://ftpsearch.itb.ac.id.
FTPSearch akan menampilkan daftar hasil
pencarian berdasarkan server. File-file yang
tersimpan pada suatu server akan ditampilkan
terlebih dahulu kemudian baru berpindah pada
server lain. FTPSearch tidak memperhatikan file
mana yang lebih berkaitan dengan kata kunci
karena FTPSearch tidak melakukan observasi
sampai pada isi dokumen tapi hanya melihat judul
dokumen
3.GENERATE AND TEST
· Strategi bangkitkan dan uji (generate and test)
merupakan pendekatan yang paling sederhana
dari semua pendekatan yang akan dibicarakan.
· Pendekatan ini meliputi langkah–langkah
sebagai berikut :
1. Buatlah/bangkitkan sebuah solusi yang
memungkinkan. Untuk sebuah problema hal
ini dapat berarti pembuatan sebuah titik
khusus dalam ruang problema.
2. Lakukan pengujian untuk melihat apakah
solusi yang dibuat benar–benar merupakan
sebuah solusi, dengan cara membandingkan
titik khusus tersebut dengan goal-nya (solusi).
3. Jika telah diperoleh sebuah solusi, langkah–
langkah tersebut dapat dihentikan. Jika belum,
kembalilah ke langkah pertama.
· Jika pembangkitan atau pembuatan solusi–
solusi yang dimungkinkan dapat dilakukan
secara sistematis, maka prosedur ini akan dapat
segera menemukan solusinya, (bila ada).
· Namun, jika ruang problema sangat besar, maka
proses ini akan membutuhkan waktu yang lama.
· Metode generate and test ini kurang efisien
untuk masalah yang besar atau kompleks
4.HILL CLIMBING
· Hill climbing (mendaki bukit) merupakan salah
satu variasi metode buat dan uji (generate and
test) dimana umpan balik yang berasal dari
prosedur uji digunakan untuk memutuskan arah
gerak dalam ruang pencarian (search).
· Dalam prosedur buat dan uji yang murni, respon
fungsi uji hanyalah ya atau tidak.
· Dalam prosedur Hill Climbing, fungsi uji
dikombinasikan dengan fungsi heuristik yang
menyediakan pengukuran kedekatan suatu
keadaan yang diberikan dengan tujuan (goal).
Prosedur Hill Climbing :
1. Buatlah solusi usulan pertama dengan cara yang
sama seperti yang dilakukan dalam prosedur
buat dan uji (generate and test). Periksalah
apakah solusi usulan itu merupakan sebuah
solusi. Jika ya, berhentilah. Jika tidak, kita
lanjutkan ke langkah berikutnya.
Pengantar Inteligensia Buatan – Heuristic Searching 3/8
2.Dari solusi ini, terapkan sejumlah aturan yang
dapat diterapkan untuk membuat sekumpulan
solusi usulan yang baru.
3.Untuk setiap elemen kumpulan solusi tersebut,
lakukanlah hal-hal berikut ini :
1.Kirimkanlah elemen ini ke fungsi uji. Jika
elemen ini merupakan sebuah solusi,
berhentilah.
2.Jika tidak, periksalah apakah elemen ini
merupakan yang terdekat dengan solusi yang
telah diuji sejauh ini. Jika tidak, buanglah.
4.Ambilah elemen terbaik yang ditemukan di atas
dan pakailah sebagai solusi usulan berikutnya.
Langkah ini bersesuaian dengan langkah dalam
ruang problema dengan arah yang muncul
sebagai yang tercepat dalam mencapai tujuan.
5.Kembalilah ke langkah 2.
Masalah-masalah yang mungkin timbul pada
prosedur Hill Climbing :
Pengantar Inteligensia Buatan – Heuristic Searching 4/8
- Maksimum lokal adalah suatu keadaan yang
lebih baik daripada semua tetangganya namun
masih belum lebih baik dari suatu keadaan lain
yang jauh letaknya darinya.
- Daratan (Plateau) adalah suatu daerah datar dari
ruang pencarian (search) dimana semua
himpunan keadaan tetangganya memiliki nilai
yang sama.
- Punggung (Ridge) adalah suatu daerah ruang
pencarian (search) yang lebih tinggi daripada
daerah sekitarnya, namun tidak dapat dibalikkan
oleh langkah–langkah tunggal ke arah manapun.
Solusinya:
- Melakukan langkah balik (backtracking) ke
simpul yang lebih awal dan mencoba bergerak
ke arah yang lain.
- Melakukan lompatan besar ke suatu arah untuk
mencoba bagian ruang pencarian yang baru.
Pengantar Inteligensia Buatan – Heuristic Searching 5/8
- Menerapkan dua atau lebih aturan sebelum
melakukan uji coba. Ini bersesuaian dengan
bergerak ke beberapa arah sekaligus.
5.BEST FIRST SEARCH
· Pencarian terbaik pertama (Best First Search)
merupakan suatu cara yang menggabungkan
keuntungan atau kelebihan dari pencarian
Breadth-First Search dan Depth-First Search.
· Pada setiap langkah proses pencarian terbaik
pertama, kita memilih node-node dengan
menerapkan fungsi heuristik yang memadai
pada setiap node/simpul yang kita pilih dengan
menggunakan aturan-aturan tertentu untuk
menghasilkan penggantinya.
· Fungsi Heuristik yang digunakan merupakan
prakiraan (estimasi) cost dari initial state ke goal
state, yang dinyatakan dengan :
f’ = g + h’
dimana f’ = prakiraan cost dari initial ke goal
g = cost dari initial state ke current state
h’ = prakiraan cost dari current state ke
goal state
“Kecerdasan Buatan (AI) merupakan sebuah studi tentang bagaimana membuat komputer melakukan hal-hal yang pada saat ini dapat dilakukan lebih baik oleh manusia.”
· Encyclopedia Britannica:
“Kecerdasan Buatan (AI) merupakan cabang dari ilmu komputer yang
dalam merepresentasi pengetahuan lebih banyak menggunakan bentuk
simbol-simbol daripada bilangan, dan memproses informasi berdasarkan
metode heuristic atau dengan berdasarkan sejumlah aturan”
Tujuan dari kecerdasan buatan menurut Winston dan Prendergast [1984]:
1. Membuat mesin menjadi lebih pintar (tujuan utama)
2. Memahami apa itu kecerdasan (tujuan ilmiah)
3. Membuat mesin lebih bermanfaat (tujuan entrepreneurial)
AI dapat dipandang dalam berbagai perspektif.
· Dari perspektif Kecerdasan (Intelligence)
AI adalah bagaimana membuat mesin yang “cerdas” dan dapat
melakukan hal-hal yang sebelumnya dapat dilakukan oleh manusia
· Dari perspektif bisnis, AI adalah sekelompok alat bantu (tools) yang
berdaya guna, dan metodologi yang menggunakan tool-tool tersebut
guna menyelesaikan masalah-masalah bisnis.
· Dari perspektif pemrograman (Programming), AI termasuk didalamnya
adalah studi tentang pemrograman simbolik, pemecahan masalah,
proses pencarian (search)
n 1970
o “Artificial intelligence” adalah nama pada akar dari studi area.
KONSEP DAN DEFINISI DALAM KECERDASAN BUATAN TURING TEST
Metode Pengujian Kecerdasan
· Turing Test merupakan sebuah metode pengujian kecerdasan yang
dibuat oleh Alan Turing.
· Proses uji ini melibatkan seorang penanya (manusia) dan dua obyek
yang ditanyai. Yang satu adalah seorang manusia dan satunya adalah
sebuah mesin yang akan diuji.
· Penanya tidak bisa melihat langsung kepada obyek yg ditanyai
· Penanya diminta untuk membedakan mana jawaban komputer dan
mana jawaban manusia berdasarkan jawaban kedua obyek tersebut.
· Jika penanya tidak dapat membedakan mana jawaban mesin dan mana
jawaban manusia maka Turing berpendapat bahwa mesin yang diuji
tersebut dapat diasumsikan CERDAS.
Pengantar Kecerdasan Buatan - 4
PEMROSESAN SIMBOLIK
· Komputer semula didisain untuk memproses bilangan/angka-angka
(pemrosesan numerik).
· Sementara manusia dalam berpikir dan menyelesaikan masalah lebih
bersifat simbolik, tidak didasarkan kepada sejumlah rumus atau
melakukan komputasi matematis.
· Sifat penting dari AI adalah bahwa AI merupakan bagian dari ilmu
komputer yang melukan proses secara simbolik dan non-algoritmik
dalam penyelesaian masalah
HEURISTIC
· Istilah Heuristic diambil dari bahasa Yunani yang berarti menemukan
· Heuristic merupakan suatu strategi untuk melakukan proses pencarian
(search) ruang problema secara selektif, yang memandu proses
pencarian yang kita lakukan disepanjang jalur yang memiliki
kemungkinan sukses paling besar.
PENARIKAN KESIMPULAN (INFERENCING)
· AI mecoba membuat mesin memiliki kemampuan berpikir atau
mempertimbangkan (reasoning)
· Kemampuan berpikir (reasoning) termasuk didalamnya proses penarikan
kesimpulan (inferencing) berdasarkan fakta-fakta dan aturan dengan
menggunakan metode heuristik atau metode pencarian lainnya.
PENCOCOKAN POLA (PATTERN MATCHING)
· AI bekerja dengan metode pencocokan pola (pattern matching) yang
berusaha untuk menjelaskan obyek, kejadian (events) atau proses,
dalam hubungan logik atau komputasional.
1. 4 Perbandingan Kecerdasan Buatan dengan Kecerdasan Alamiah
Keuntungan Kecerdasan Buatan dibanding kecerdasan alamiah:
· lebih permanen
· memberikan kemudahan dalam duplikasi dan penyebaran
· relatif lebih murah dari kecerdasan alamiah
· Konsisten dan teliti
· Dapat didokumentasi
· Dapat mengerjakan beberapa task dengan lebih cepat dan lebih baik
dibanding manusia
Keuntungan Kecerdasan Alamiah dibanding kecerdasan buatan
· Bersifat lebih kreatif
· Dapat melakukan proses pembelajaran secara langsung, sementara AI
harus mendapatkan masukan berupa simbol dan representasirepresentasi
Pengantar Kecerdasan Buatan - 5
· Fokus yang luas sebagai referensi untuk pengambilan keputusan
sebaliknya AI menggunakan fokus yang sempit
Komputer dapat digunakan untuk mengumpulkan informasi tentang obyek,
kegiatan (events), proses dan dapat memproses sejumlah besar
informasi dengan lebih efisien dari yang dapat dikerjakan manusia, tetapi
disisi lain manusia –dengan menggunakan insting- dapat melakukan hal yang
sulit untuk diprogram pada komputer, yaitu: manusia dapat mengenali
(recognize) hubungan antara hal-hal tersebut, menilai kualitas dan
menemukan pola yang menjelaskan hubungan tersebut.
Metode Search dalam Kecerdasan Buatan
1.Breadth-first Search
Breadth-first search adalah algoritma yang
melakukan pencarian secara melebar yang
mengunjungi simpul secara preorder yaitu
mengunjungi suatu simpul kemudian mengunjungi
semua simpul yang bertetangga dengan simpul
tersebut terlebih dahulu. Selanjutnya, simpul yang
belum dikunjungi dan bertetangga dengan simpulsimpul
yang tadi dikunjungi , demikian seterusnya.
Jika graf berbentuk pohon berakar, maka semua
simpul pada aras d dikunjungi lebih dahulu
sebelum simpul-simpul pad aras d+1.
Algoritma ini memerluka-n sebuah antrian q untuk
menyimpan simpul yang telah dikunjungi. Simpul simpul ini diperlukan sebagai acuan untuk
mengunjungi simpul-simpul yang bertetanggaandengannya. Tiap simpul yang telah dikunjungu
masuk ke dalam antrian hanya satu kali.
Algoritma ini juga membutuhkan table Boolean
untuk menyimpan simpul yang te lah dikunjungi
sehingga tidak ada simpul yang dikunjungi lebih
dari satu kali.
Salah satu contoh kakas pencarian yang
menggunakan metode BFS adalah WebCrawler.
WebCrawler adalah suatu kakas yang membuat
indeks isi dari suatu dokumen di Web yang
selanjutnya akan dimanfaatkan oleh mesin pencari.
Terdapat tiga langkah yang dilakukan oleh
WebCrawler ini ketika mengunjungi dokumen,
yaitu menandai bahwa suatu dokumen telah
dikunjungi, mengenali link yang terdapat pada
dokumen tersebut, kemudian isinya didaftarkan
pada daftar indeks.
Pada akhirnya, WebCrawler aakan menampilkan
file yang paling banyak berkaitan dengan kata
kunci.
2.Depth-first Search
Depth-first search (DFS) melakukan pencarian
secara preorder. Mengunjungi anak suatu simpul
sebelum simpul tetangganya. Berkaitan dengan
mesin pencari, DFS ini cenderung mengindeks
dokumen berdasarkan suatu link.Algoritma DFS yang diterapkan pada mesin pencari
dalam melakukan pengindeksan adalah
mengunjungi suatu server kemudian menyimpansemua link yang berhubungan dengan server
tersebut baru kemudian mengunjungi server lain.
Salah satu yang menerapkan algoritma DFS pada
mesin pencarian adalah FTPSearch.
FTPSearch adalah suatu mesin pencari dokumen
yang tersimpan di jaringan ITB. Dapat diakses pada
http://ftpsearch.itb.ac.id.
FTPSearch akan menampilkan daftar hasil
pencarian berdasarkan server. File-file yang
tersimpan pada suatu server akan ditampilkan
terlebih dahulu kemudian baru berpindah pada
server lain. FTPSearch tidak memperhatikan file
mana yang lebih berkaitan dengan kata kunci
karena FTPSearch tidak melakukan observasi
sampai pada isi dokumen tapi hanya melihat judul
dokumen
3.GENERATE AND TEST
· Strategi bangkitkan dan uji (generate and test)
merupakan pendekatan yang paling sederhana
dari semua pendekatan yang akan dibicarakan.
· Pendekatan ini meliputi langkah–langkah
sebagai berikut :
1. Buatlah/bangkitkan sebuah solusi yang
memungkinkan. Untuk sebuah problema hal
ini dapat berarti pembuatan sebuah titik
khusus dalam ruang problema.
2. Lakukan pengujian untuk melihat apakah
solusi yang dibuat benar–benar merupakan
sebuah solusi, dengan cara membandingkan
titik khusus tersebut dengan goal-nya (solusi).
3. Jika telah diperoleh sebuah solusi, langkah–
langkah tersebut dapat dihentikan. Jika belum,
kembalilah ke langkah pertama.
· Jika pembangkitan atau pembuatan solusi–
solusi yang dimungkinkan dapat dilakukan
secara sistematis, maka prosedur ini akan dapat
segera menemukan solusinya, (bila ada).
· Namun, jika ruang problema sangat besar, maka
proses ini akan membutuhkan waktu yang lama.
· Metode generate and test ini kurang efisien
untuk masalah yang besar atau kompleks
4.HILL CLIMBING
· Hill climbing (mendaki bukit) merupakan salah
satu variasi metode buat dan uji (generate and
test) dimana umpan balik yang berasal dari
prosedur uji digunakan untuk memutuskan arah
gerak dalam ruang pencarian (search).
· Dalam prosedur buat dan uji yang murni, respon
fungsi uji hanyalah ya atau tidak.
· Dalam prosedur Hill Climbing, fungsi uji
dikombinasikan dengan fungsi heuristik yang
menyediakan pengukuran kedekatan suatu
keadaan yang diberikan dengan tujuan (goal).
Prosedur Hill Climbing :
1. Buatlah solusi usulan pertama dengan cara yang
sama seperti yang dilakukan dalam prosedur
buat dan uji (generate and test). Periksalah
apakah solusi usulan itu merupakan sebuah
solusi. Jika ya, berhentilah. Jika tidak, kita
lanjutkan ke langkah berikutnya.
Pengantar Inteligensia Buatan – Heuristic Searching 3/8
2.Dari solusi ini, terapkan sejumlah aturan yang
dapat diterapkan untuk membuat sekumpulan
solusi usulan yang baru.
3.Untuk setiap elemen kumpulan solusi tersebut,
lakukanlah hal-hal berikut ini :
1.Kirimkanlah elemen ini ke fungsi uji. Jika
elemen ini merupakan sebuah solusi,
berhentilah.
2.Jika tidak, periksalah apakah elemen ini
merupakan yang terdekat dengan solusi yang
telah diuji sejauh ini. Jika tidak, buanglah.
4.Ambilah elemen terbaik yang ditemukan di atas
dan pakailah sebagai solusi usulan berikutnya.
Langkah ini bersesuaian dengan langkah dalam
ruang problema dengan arah yang muncul
sebagai yang tercepat dalam mencapai tujuan.
5.Kembalilah ke langkah 2.
Masalah-masalah yang mungkin timbul pada
prosedur Hill Climbing :
Pengantar Inteligensia Buatan – Heuristic Searching 4/8
- Maksimum lokal adalah suatu keadaan yang
lebih baik daripada semua tetangganya namun
masih belum lebih baik dari suatu keadaan lain
yang jauh letaknya darinya.
- Daratan (Plateau) adalah suatu daerah datar dari
ruang pencarian (search) dimana semua
himpunan keadaan tetangganya memiliki nilai
yang sama.
- Punggung (Ridge) adalah suatu daerah ruang
pencarian (search) yang lebih tinggi daripada
daerah sekitarnya, namun tidak dapat dibalikkan
oleh langkah–langkah tunggal ke arah manapun.
Solusinya:
- Melakukan langkah balik (backtracking) ke
simpul yang lebih awal dan mencoba bergerak
ke arah yang lain.
- Melakukan lompatan besar ke suatu arah untuk
mencoba bagian ruang pencarian yang baru.
Pengantar Inteligensia Buatan – Heuristic Searching 5/8
- Menerapkan dua atau lebih aturan sebelum
melakukan uji coba. Ini bersesuaian dengan
bergerak ke beberapa arah sekaligus.
5.BEST FIRST SEARCH
· Pencarian terbaik pertama (Best First Search)
merupakan suatu cara yang menggabungkan
keuntungan atau kelebihan dari pencarian
Breadth-First Search dan Depth-First Search.
· Pada setiap langkah proses pencarian terbaik
pertama, kita memilih node-node dengan
menerapkan fungsi heuristik yang memadai
pada setiap node/simpul yang kita pilih dengan
menggunakan aturan-aturan tertentu untuk
menghasilkan penggantinya.
· Fungsi Heuristik yang digunakan merupakan
prakiraan (estimasi) cost dari initial state ke goal
state, yang dinyatakan dengan :
f’ = g + h’
dimana f’ = prakiraan cost dari initial ke goal
g = cost dari initial state ke current state
h’ = prakiraan cost dari current state ke
goal state
Tidak ada komentar:
Posting Komentar