Pencarian Berbentuk (Heuristik search dan Eksplorasi)

Pencarian Berbentuk (Heuristik search dan Eksplorasi)

Metode Pencarian Heuristic

Kata Heuristic berasal dari sebuah kata kerja Yunani, heuriskein, yang berarti “mencari” atau “menemukan”. Dalam dunia pemrograman, sebagian orang  menggunakan kata heuristic sebagai lawan kata dari algoritmik, di mana kata heuristic ini diartikan sebagai suatu proses yang mungkin dapat menyelesaikan  suatu masalah tetapi tidak ada jaminan bahwa solusi yang dicari selalu dapat
ditemukan. 

Heuristic memperbaiki proses pencarian solusi walaupun tidak harus sampai mengatasi kasus terburuk (worst case scenario). Heuristik ini mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness). Algoritma ini biasanya mencari solusi yang dekat dengan solusi terbaik dan proses pencariannya cepat dan mudah. Terkadang algoritma ini dapat menjadi akurat dan menemukan solusi terbaik, tetapi algoritma ini tetap disebut heuristic hingga solusi terbaik itu terbukti untuk menjadi yang terbaik. 

Fungsi heuristic h(n) adalah perkiraan biaya termurah dari node n ke node tujuan. Fungsi heuristic melambangkan cost yang akan dikeluarkan agent jika memilih node tertentu.

1. STRATEGI PENCARIAN BENTUK

Dengan menggunakan Uninformed Search Algorithm, beberapa permasalahan dapat dipecahkan, namun tidak semua algoritma dapat menyelesaikan permasalahan dengan efektif serta efisien.

Informed Search Algorithm, disebut juga dengan Heuristic Search. Pencarian dengan algoritma ini menggunakan pengetahuan yang spesifik kepada permasalahan yang dihadapi selain dari definisi masalahnya itu sendiri.

Pada pencarian dengan metode UCS(Salah satu bagian dai Uninformed Search Algorithm), kita membandingkan nilai pada path yang ada lalu kemudian melakukan ekspansi pertama kali pada path dengan nilai yang terkecil. Nilai path ini biasanya dilambangkan dengan g(n). lebih lanjut lagi, dari metode pencarian tsb, pada Informed Search Algorithm, kita akan mengenal nilai estimasi(prediksi) dari satu node ke node yang lainnya. Nilai estimasi ini biasanya dilambangkan dengan h(n). Jika n adalah goal node, maka nilai h(n) adalah nol.

Metode metode pada Informed Search Algorithm :

• .      Greedy Best First Search

Metode pencarian ini melakukan ekspansi node yang memiliki jarak terdekat dengan goal. Namun, ekspansi yang dilakukan pada metode ini menggunakan evaluasi node hanya dengan melihat kepada fungsi heuristiknya. Dengan kata lain, yang dibandingkan untuk penentuan ekspansi node adalah nilai estimasi/prediksinya saja. 

f(n) = h(n)

• .      A* Search

Bentuk dari Best First Search yang paling dikenal adalah algoritma pencarian A* (dibaca dengan “A-star”). Sedikit berbeda dengan Greedy yang hanya melihat kepada nilai h(n), pencarian dengan A* melihat kepada kombinasi nilai dari pathnya yaitu g(n) dengan nilai estimasi yaitu h(n).

f(n) = g(n) + h(n)

• .      SMA* atau Simplified Memory Bounded A*

SMA* atau Simplified Memory Bounded A* adalah algoritma pencarian jalur terpendek berdasarkan dari algoritma A*. Keuntungan utama dari algo SMA* adalah dia menggunakan bounded memory, sementara algo A* mungkin membutuhkan memori exponensial. Semua karakteristik di algo SMA* diturunkan dari A*.

Seperti A *, algoritma SMA* memperluas cabang yang paling menjanjikan menurut heuristik. Apa yang membuat SMA * terpisah adalah SMA* memangkas simpul yang ekspansinya telah diungkapkan kurang menjanjikan dari yang diharapkan. Pendekatan ini memungkinkan algoritma untuk mengeksplorasi cabang dan backtrack untuk mengeksplorasi cabang lain.
Ekspansi dan pemangkasan simpul didorong karena SMA* menjaga dua nilai f untuk setiap simpul. Simpul x menyimpan nilai f(x) yang memperkirakan biaya mencapai tujuan dengan mengambil jalan melalui simpul tersebut. Semakin rendah nilai, semakin tinggi prioritas. Seperti di A * nilai ini diinisialisasi dengan h (x) + g (x), tetapi kemudian akan diperbarui untuk mencerminkan perubahan estimasi ketika anak-anaknya diperluas. Sebuah simpul yang sudah diperluas sepenuhnya akan memiliki nilai f setidaknya setinggi dari suksesornya. Selain itu, simpul menyimpan nilai f dari suksesor terbaik yang telah dilupakan. Nilai ini dikembalikan jika suksesor yang telah dilupakan itu dinyatakan sebagai suksesor paling menjanjikan.
SMA* merupakan algoritma yang:

1.      Bekerja dengan heuristic, seperti A*

2.      Selesai jika memori yang diperbolehkan cukup tinggi untuk menyimpan solusi terdangkal

3.      Optimal jika memori yang diperbolehkan cukup tinggi untuk menyimpan solusi optimal terdangkal, jika tidak dia akan mengembalikan solusi terbaik yang ada di memori

4.      Menjauhi pernyataan yang diulang-ulang selama batas memori memperbolehkannya

5.      Menggunakan semua memori yang ada

6.      Memperbesar batas memori dari algoritma hanya akan mempercepat perhitungan

7.      Ketika memori cukup ada untuk memuat seluruh pohon pencarian, maka perhitungan mempunyai kecepatan yang optimal 

2. FUNGSI HEURISTIK

Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian (pencarian yang lebih simple). Namun kemungkinan juga dapat mengngorbankan kelengkapan (complateness). Fungsi Heuristic digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan

3. ALGORITMA PENCARIAN LOKAL DAN MASALAH OPTIMISASI

·         Metode Hill Climbing Search

Metode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristik ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin(Sri Kusumadewi 2003, h. 34).

Ada dua macam metode Hill

·         Climbing Search, yaitu Simple Hill Climbing ,

·         Steepest-ascent Hill Climbing (Sri Kusumadewi 2003, h. 39).

Algoritma untuk Hill Climbing Search adalah sebagai berikut :

1.      Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.

2.      Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada node baru yang akan diaplikasikan pada keadaan sekarang :

·         Cari node yang belum pernah digunakan; gunakan node ini untuk mendapatkan keadaan yang baru.

·         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 pencarian.

·         Simulated Annealing Search

Merupakan ialah suatu algoritma optimasi yang mensimulasikan proses annealing pada pembuatan materi yang terdiri dari butir keristal/logam. Algoritma unt untuk optimalisasi yang bersifat generic. Berbasiskan probabilitas dan mekanika statistic, algoritma ini dapat dipakai untuk mencari pendekatan terhadap solusi optimum global dari suatu permasalahn. Masalah yang membutuhkan pendekatan simulated annealing ialah masalah-masalah optimisasi kombinatorial, dimana ruang pencarian solusi yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahn itu.

Secara umum ada 3 hal pokok pada simulated annealing, yaitu:

1.      Nilai awal : Unt temperature (T0). Nilai T0 biasanya ditetapkan cukup besar (tidak mendekati 0), karena jika T mendekati 0 maka gerakan simulated annealing akan sama dengan hill climbing. Biasanya temperature awal ini ditetapkan sebesar 2 kali panjang suatu jalur yang dipilih secara acak.

2.      Kriteria : Yang dipakai unt memutuskan apakah temperature sistem seharusnya dikurangi.

3.      Berapa besarnya pengurangan temperature dalam setiap waktu.

·         Local Beam Search

Local beam search adalah algoritma pencarian heuristik yangmerupakan optimasi dari pencarian best-first search yang mengurangikebutuhan memorinya. Dalam Beam Search, hanya jumlah solusiparsial terbaik yang telah ditetapkan yang disimpan sebagai kandidat.

Beam Search membutuhkan tiga komponen sebagai inputnya, yaitu :

1.      Masalah yang akan di selesaikan : Biasanya di tampilkan dalam bentuk grafik dan berisi kumpulan node yang tiap satu atau lebih node mengarah ke goal/hasil.

2.      Kumpulan aturan-aturan heuristik untuk pemangkasan : Adalah aturan-aturan spesifik yang mengarah ke ruang masalah dan memangkas node yang tidak menguntungkan dari memori yang berhubungan dengan ruang masalah.

3.      Memori dengan kapasitas yang terbatas adalah memori tempat menyimpan beam, dimana ketika memori dalam keadaan penuh dan node akan di tambahkan ke beam, maka node yang nilainya paling besar yang dihapus, jadi  tidak  akan melebihi memori yang tersedia.

Beam Search memiliki keuntungan yang berpotensi mengurangi perhitungan dan waktu pencarian. Selain itu, pemakaian memori daripencarian ini jauh lebih sedikit daripada metode yang mendasari metode pencarian ini.  Kelemahan utama Beam Search adalah metode pencarian ini mungkin  tidak dapat mencapai tujuan/hasil yang optimaldan bahkan mungkin tidak mencapai tujuan sama sekali. Padakenyataannya, algoritma beam search berakhir untuk dua kasus:  nodetujuan yang diperlukan tercapai, atau node tujuan tidak tercapai dantidak ada node tersisa untuk dieksplorasi.

·         Genetic Algorithm

Genetic Algorithm (GA) adalah teknik pencarian dalam bidang komputasi untuk menemukan solusi benar atau pendekatan untuk masalah optimasi dan pencarian. Teknik dalam GA didasarkan pada biologi evolusioner seperti pewarisan, mutasi, seleksi dan crossover.

Dalam GA biasanya ada 2 hal yang harus didefinisikan:

1.      Representasi genetis dari domain solusi

2.      Fungsi fitness untuk mengevaluasi solusi domain.

Hal-hal yang harus dilakukan untuk menggunakan algoritma genetika:

1.      Mendefinisikan individu, dimana individu menyatakan salah satu solusi (penyelesaian) yang mungkin dari permasalahan yang diangkat.

2.      Mendefinisikan nilai fitness, yang merupakan ukuran baik tidaknya sebuah individu atau baik tidaknya solusi yang didapatkan.

3.      Menentukan proses pembangkitan solusi awal. Hal ini biasanya dilakukan dengan menggunakan pembangkitan acak seperti random walk.

4.      Menentukan proses seleksi yang akan digunakan.

5.      Menentukan proses perkawinan silang (cross over) dan mutasi gen yang akan digunakan.

4. AGEN PENCARIAN ONLINE DAN  LINGKUNGAN YANG TIDAK DIKETAHUI 

     Agen yang berupa perangkat lunak, atau bisa disebut agen cerdas, adalah perangkat lunak yang dapat bertindak seperti orang yang mampu berinteraksi dengan lingkungan. Contoh:

1.      Agen sistem operasi digunakan untuk membantu penggunaan sistem operasi digunakan untuk membantu penggunaan sistem operasi. Contoh, microsoft memiliki sejumlah agen yang dinamakan wizard pada sistem operasi yang di buatnya; misalnya Windows NT. Agen ini digunakan antara lain untuk menambah nama pemakai, mengelola grup pemakai, dan manajemen berkas.

2.      Agen spreadsheet digunakan untuk membuat program spreadsheet menjadi lebih mudah digunakan oleh pemakai. Contoh, Office Assistant pada excel dapat “mengamati” pemakaidan jika terjadi sesuatu yang perlu untuk dibantu, agen cerdas akan memberikan saran. 

3.      Agen untuk perdagangan elektronis digunakan untuk membantu pemakai yang akan melakukan belanja secara online.Metode Pencarian Heuristic

Kata Heuristic berasal dari sebuah kata kerja Yunani, heuriskein, yang berarti “mencari” atau “menemukan”. Dalam dunia pemrograman, sebagian orang  menggunakan kata heuristic sebagai lawan kata dari algoritmik, di mana kata heuristic ini diartikan sebagai suatu proses yang mungkin dapat menyelesaikan  suatu masalah tetapi tidak ada jaminan bahwa solusi yang dicari selalu dapat
ditemukan. 

Heuristic memperbaiki proses pencarian solusi walaupun tidak harus sampai mengatasi kasus terburuk (worst case scenario). Heuristik ini mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness). Algoritma ini biasanya mencari solusi yang dekat dengan solusi terbaik dan proses pencariannya cepat dan mudah. Terkadang algoritma ini dapat menjadi akurat dan menemukan solusi terbaik, tetapi algoritma ini tetap disebut heuristic hingga solusi terbaik itu terbukti untuk menjadi yang terbaik. 

Fungsi heuristic h(n) adalah perkiraan biaya termurah dari node n ke node tujuan. Fungsi heuristic melambangkan cost yang akan dikeluarkan agent jika memilih node tertentu.

1. STRATEGI PENCARIAN BENTUK

Dengan menggunakan Uninformed Search Algorithm, beberapa permasalahan dapat dipecahkan, namun tidak semua algoritma dapat menyelesaikan permasalahan dengan efektif serta efisien.

Informed Search Algorithm, disebut juga dengan Heuristic Search. Pencarian dengan algoritma ini menggunakan pengetahuan yang spesifik kepada permasalahan yang dihadapi selain dari definisi masalahnya itu sendiri.

Pada pencarian dengan metode UCS(Salah satu bagian dai Uninformed Search Algorithm), kita membandingkan nilai pada path yang ada lalu kemudian melakukan ekspansi pertama kali pada path dengan nilai yang terkecil. Nilai path ini biasanya dilambangkan dengan g(n). lebih lanjut lagi, dari metode pencarian tsb, pada Informed Search Algorithm, kita akan mengenal nilai estimasi(prediksi) dari satu node ke node yang lainnya. Nilai estimasi ini biasanya dilambangkan dengan h(n). Jika n adalah goal node, maka nilai h(n) adalah nol.

Metode metode pada Informed Search Algorithm :

• .      Greedy Best First Search

Metode pencarian ini melakukan ekspansi node yang memiliki jarak terdekat dengan goal. Namun, ekspansi yang dilakukan pada metode ini menggunakan evaluasi node hanya dengan melihat kepada fungsi heuristiknya. Dengan kata lain, yang dibandingkan untuk penentuan ekspansi node adalah nilai estimasi/prediksinya saja. 

f(n) = h(n)

• .      A* Search

Bentuk dari Best First Search yang paling dikenal adalah algoritma pencarian A* (dibaca dengan “A-star”). Sedikit berbeda dengan Greedy yang hanya melihat kepada nilai h(n), pencarian dengan A* melihat kepada kombinasi nilai dari pathnya yaitu g(n) dengan nilai estimasi yaitu h(n).

f(n) = g(n) + h(n)

• .      SMA* atau Simplified Memory Bounded A*

SMA* atau Simplified Memory Bounded A* adalah algoritma pencarian jalur terpendek berdasarkan dari algoritma A*. Keuntungan utama dari algo SMA* adalah dia menggunakan bounded memory, sementara algo A* mungkin membutuhkan memori exponensial. Semua karakteristik di algo SMA* diturunkan dari A*.

Seperti A *, algoritma SMA* memperluas cabang yang paling menjanjikan menurut heuristik. Apa yang membuat SMA * terpisah adalah SMA* memangkas simpul yang ekspansinya telah diungkapkan kurang menjanjikan dari yang diharapkan. Pendekatan ini memungkinkan algoritma untuk mengeksplorasi cabang dan backtrack untuk mengeksplorasi cabang lain.
Ekspansi dan pemangkasan simpul didorong karena SMA* menjaga dua nilai f untuk setiap simpul. Simpul x menyimpan nilai f(x) yang memperkirakan biaya mencapai tujuan dengan mengambil jalan melalui simpul tersebut. Semakin rendah nilai, semakin tinggi prioritas. Seperti di A * nilai ini diinisialisasi dengan h (x) + g (x), tetapi kemudian akan diperbarui untuk mencerminkan perubahan estimasi ketika anak-anaknya diperluas. Sebuah simpul yang sudah diperluas sepenuhnya akan memiliki nilai f setidaknya setinggi dari suksesornya. Selain itu, simpul menyimpan nilai f dari suksesor terbaik yang telah dilupakan. Nilai ini dikembalikan jika suksesor yang telah dilupakan itu dinyatakan sebagai suksesor paling menjanjikan.
SMA* merupakan algoritma yang:

1.      Bekerja dengan heuristic, seperti A*

2.      Selesai jika memori yang diperbolehkan cukup tinggi untuk menyimpan solusi terdangkal

3.      Optimal jika memori yang diperbolehkan cukup tinggi untuk menyimpan solusi optimal terdangkal, jika tidak dia akan mengembalikan solusi terbaik yang ada di memori

4.      Menjauhi pernyataan yang diulang-ulang selama batas memori memperbolehkannya

5.      Menggunakan semua memori yang ada

6.      Memperbesar batas memori dari algoritma hanya akan mempercepat perhitungan

7.      Ketika memori cukup ada untuk memuat seluruh pohon pencarian, maka perhitungan mempunyai kecepatan yang optimal 

2. FUNGSI HEURISTIK

Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian (pencarian yang lebih simple). Namun kemungkinan juga dapat mengngorbankan kelengkapan (complateness). Fungsi Heuristic digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan

3. ALGORITMA PENCARIAN LOKAL DAN MASALAH OPTIMISASI

·         Metode Hill Climbing Search

Metode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristik ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin(Sri Kusumadewi 2003, h. 34).

Ada dua macam metode Hill

·         Climbing Search, yaitu Simple Hill Climbing ,

·         Steepest-ascent Hill Climbing (Sri Kusumadewi 2003, h. 39).

Algoritma untuk Hill Climbing Search adalah sebagai berikut :

1.      Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.

2.      Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada node baru yang akan diaplikasikan pada keadaan sekarang :

·         Cari node yang belum pernah digunakan; gunakan node ini untuk mendapatkan keadaan yang baru.

·         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 pencarian.

·         Simulated Annealing Search

Merupakan ialah suatu algoritma optimasi yang mensimulasikan proses annealing pada pembuatan materi yang terdiri dari butir keristal/logam. Algoritma unt untuk optimalisasi yang bersifat generic. Berbasiskan probabilitas dan mekanika statistic, algoritma ini dapat dipakai untuk mencari pendekatan terhadap solusi optimum global dari suatu permasalahn. Masalah yang membutuhkan pendekatan simulated annealing ialah masalah-masalah optimisasi kombinatorial, dimana ruang pencarian solusi yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahn itu.

Secara umum ada 3 hal pokok pada simulated annealing, yaitu:

1.      Nilai awal : Unt temperature (T0). Nilai T0 biasanya ditetapkan cukup besar (tidak mendekati 0), karena jika T mendekati 0 maka gerakan simulated annealing akan sama dengan hill climbing. Biasanya temperature awal ini ditetapkan sebesar 2 kali panjang suatu jalur yang dipilih secara acak.

2.      Kriteria : Yang dipakai unt memutuskan apakah temperature sistem seharusnya dikurangi.

3.      Berapa besarnya pengurangan temperature dalam setiap waktu.

·         Local Beam Search

Local beam search adalah algoritma pencarian heuristik yangmerupakan optimasi dari pencarian best-first search yang mengurangikebutuhan memorinya. Dalam Beam Search, hanya jumlah solusiparsial terbaik yang telah ditetapkan yang disimpan sebagai kandidat.

Beam Search membutuhkan tiga komponen sebagai inputnya, yaitu :

1.      Masalah yang akan di selesaikan : Biasanya di tampilkan dalam bentuk grafik dan berisi kumpulan node yang tiap satu atau lebih node mengarah ke goal/hasil.

2.      Kumpulan aturan-aturan heuristik untuk pemangkasan : Adalah aturan-aturan spesifik yang mengarah ke ruang masalah dan memangkas node yang tidak menguntungkan dari memori yang berhubungan dengan ruang masalah.

3.      Memori dengan kapasitas yang terbatas adalah memori tempat menyimpan beam, dimana ketika memori dalam keadaan penuh dan node akan di tambahkan ke beam, maka node yang nilainya paling besar yang dihapus, jadi  tidak  akan melebihi memori yang tersedia.

Beam Search memiliki keuntungan yang berpotensi mengurangi perhitungan dan waktu pencarian. Selain itu, pemakaian memori daripencarian ini jauh lebih sedikit daripada metode yang mendasari metode pencarian ini.  Kelemahan utama Beam Search adalah metode pencarian ini mungkin  tidak dapat mencapai tujuan/hasil yang optimaldan bahkan mungkin tidak mencapai tujuan sama sekali. Padakenyataannya, algoritma beam search berakhir untuk dua kasus:  nodetujuan yang diperlukan tercapai, atau node tujuan tidak tercapai dantidak ada node tersisa untuk dieksplorasi.

·         Genetic Algorithm

Genetic Algorithm (GA) adalah teknik pencarian dalam bidang komputasi untuk menemukan solusi benar atau pendekatan untuk masalah optimasi dan pencarian. Teknik dalam GA didasarkan pada biologi evolusioner seperti pewarisan, mutasi, seleksi dan crossover.

Dalam GA biasanya ada 2 hal yang harus didefinisikan:

1.      Representasi genetis dari domain solusi

2.      Fungsi fitness untuk mengevaluasi solusi domain.

Hal-hal yang harus dilakukan untuk menggunakan algoritma genetika:

1.      Mendefinisikan individu, dimana individu menyatakan salah satu solusi (penyelesaian) yang mungkin dari permasalahan yang diangkat.

2.      Mendefinisikan nilai fitness, yang merupakan ukuran baik tidaknya sebuah individu atau baik tidaknya solusi yang didapatkan.

3.      Menentukan proses pembangkitan solusi awal. Hal ini biasanya dilakukan dengan menggunakan pembangkitan acak seperti random walk.

4.      Menentukan proses seleksi yang akan digunakan.

5.      Menentukan proses perkawinan silang (cross over) dan mutasi gen yang akan digunakan.

4. AGEN PENCARIAN ONLINE DAN  LINGKUNGAN YANG TIDAK DIKETAHUI 

     Agen yang berupa perangkat lunak, atau bisa disebut agen cerdas, adalah perangkat lunak yang dapat bertindak seperti orang yang mampu berinteraksi dengan lingkungan. Contoh:

1.      Agen sistem operasi digunakan untuk membantu penggunaan sistem operasi digunakan untuk membantu penggunaan sistem operasi. Contoh, microsoft memiliki sejumlah agen yang dinamakan wizard pada sistem operasi yang di buatnya; misalnya Windows NT. Agen ini digunakan antara lain untuk menambah nama pemakai, mengelola grup pemakai, dan manajemen berkas.

2.      Agen spreadsheet digunakan untuk membuat program spreadsheet menjadi lebih mudah digunakan oleh pemakai. Contoh, Office Assistant pada excel dapat “mengamati” pemakaidan jika terjadi sesuatu yang perlu untuk dibantu, agen cerdas akan memberikan saran. 

3.      Agen untuk perdagangan elektronis digunakan untuk membantu pemakai yang akan melakukan belanja secara online.

Penyelesaian Masalah melalui proses Pencarian / Searching

Penyelesaian Masalah melalui proses Pencarian / Searching

1.  Agen Pemecahan Permasalahan

·         Simple reflex agents: berdasarkan persepsi yg terakhir.

·         Model-based reflex agents: memiliki representasi internal tentang keadaan sekitar.

·         Goal-based agents: memiliki informasi tentang tujuan, memilih tindakan yang mencapai tujuan.

·         Utility-based agents: melakukan penilaian kuantitatif terhadap suatu keadaan lingkungan.

·         Learning agents: belajar dari pengalaman, meningkatkan kinerja.

2. Pencarian sebagai solusi pemecahan masalah

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:

·         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).

Blind Searching sendiri dibagi menjadi tiga macam yaitu :

1.      BFS (Breadth First Search)

2.      DFS (Depth-first Search)

3.      UCS (Uniform Cost Search).

·         Heuristic Searching

Heuristic Search merupakan metode pencarian yang memperhatikan nilai heuristik (nilai perkiraan).Teknik pencarian heuristik (heuristic searching) merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan (state space) suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan di sepanjang jalur yang memiliki kemungkinan sukses paling besar, dan mengesampingkan usaha yang bodoh dan memboroskan waktu.

Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness).Heuristic Search memperkirakan jarak menuju Goal (yang disebut dengan fungsi heuristik).

Fungsi heuristik ini digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

Jenis-jenis Heuristic Searching :

1.      Generate and Test

2.      Hill Climbing

3.      Best First Search

4.      Alpha Beta Prunning

5.      Means-End-Anlysis

6.      Constraint Satisfaction

3. Strategi Pencarian yang tidak berbentuk

Algoritma ini tidak memberikan informasi apapun tentang permasalah yang ada, tetapi hanya berfokus memberikan informasi tentang algorima tersebut. Algoritma ini juga disebut Blind Search. Istilah Blind Search berpedoman bahwa, teknik pencarian ini tidak memiliki informasi tambahan lain selain dari yang disediakan.

Yang dilakukan oleh algorima ini adalah melakukan generate dari successor dan membedakan goal state dari non-goal state. Pencarian ini dilakukan berdasarkan pada urutan mana saja node yang hendak di-expand.

Macam-macam Uninformed Search Algorithm :

·         Breadth First Search(BFS)

Pencarian dengan metode ini menggunakan teknik dimana langkah pertama yang harus dilakukan adalah root node di-ekspansi, setelah itu dilanjutkan semua successor dari root node juga di-expand. Hal ini terus dilakukan berulang-ulang hingga leaf(node pada level paling bawah yang sudah tidak memiliki successor lagi).

·         Uniform Cost Search(UCS)

Pencarian dengan BFS akan menjadi optimal ketika nilai pada semua path adalah sama. Dengan sedikit perluasan, dapat ditemukan sebuah algoritma yang optimal dengan melihat kepada nilai tiap path di antara node-node yang ada.

Selain menjalankan fungsi algoritma BFS, Uniform Cost Search melakukan ekspansi node dengan nilai path yang paling kecil. Hal ini bisa dilakukan dengan membuat antrian pada successor yang ada berdasar kepada nilai path-nya (node disimpan dalam bentuk priority queue).

·         Depth First Search (DFS)

Teknik pencarian dengan metode ini adalah dengan melakukan ekspansi menuju node yang paling dalam pada tree. Node paling dalam dicirikan dengan tidak adanya successor dari node itu. Setelah node selesai di ekspansi, maka node tersebut akan ditinggalkan dan dilakukan ke node paling dalam lainnya yang masih memiliki successor yang belum di ekspansi.

·         Depth Limited Search

Pencarian menggunakan DFS akan berlanjut sampai kedalam paling terakhir dari sebuah tree. Misalkan yang muncul pada DFS adalah ketikda proses pencarian tersebut menemui infinite state space. Hal ini bisa diatasi dengan mengisiasikan batas depth pada level tertentu semenjak awal pencarian. Sehingga node pada level depth tersebut akan diperlakukan seolah-olah mereka sudah tidak memiliki successor.

·         Iterative Deepening Depth First Search

Iterative deepening search merupakan sebuah strategi umum yang biasanya dikombinasikan dengan depth first tree search, yang akan menemukan berapa depth limit terbaik untuk digunakan. Hal ini dilakukan dengan secara menambah limit secara bertahap, mulai dari 0,1, 2, dan seterusnya sampai goal sudah ditemukan.

·         Bidirectional Search

Pencarian dengan metode bidirectional search adalah dengan menjalankan dua pencarian secara simultan, yang satu dikerjakan secara forward dari initial state menuju ke goal, sedangkan yang satu lagi dikerjakan secara backward mulai dari goal ke initial state. Yang kemudian diharapkan bahwa kedua pencarian itu akan bertemu di tengah-tengah.