Logika Orde Pertama (FIRST-ORDER LOGIC)

A. PENGENALAN LOGIKA ORDE PERTAMA (FIRST ORDER LOGIC)

First order logic adalah sebuah bahasa formal yang digunakan di ilmu matematika, philosophy, bahasa dan ilmu computer. Disebut juga kalkulus predikat, merupakan logika yang digunakan untuk merepresentasikan masalah yang tidak dapat direpresentasikan dengan menggunakan proposisi. Logika predikat dapat memberikan representasi fakat-fakta sebagai suatu pernyataan yang mapan (well form). Kalkulus predikat bisa menganalisakan kalimat-kalimat ke dalam subjek dan argumen dalam berbagai cara yang berbeda-beda, yang pada akhirnya kalkulus predikat bisa digunakan untuk memecahkan problem of multiple generality (masalah dalam berbagai keadaan umum) yang telah membingungkan sebagian besar ahli-ahli logika abad pertengahan. Dengan menggunakan logika predikat ini, untuk pertama kalinya, para ahli-ahli logika bisa memberikan quantifier yang cukup umum untuk merepresentasikan semua argumen yang terdapat pada natural language.

Pemanfaatan FOL untuk merepresentasikan fakta adalah salah satu teknik dasar yang sudah sejak lama dipakai untuk dapat mengkodekan bahasa alami ke dalam bentuk formal. Dengan menggunakan FOL, diharapkan fakta (dan juga pertanyaan) dapat direpresentasikan secara tepatke dalam konteksnya masing-masing, sehingga jawaban akhir yang dikembalikan kepada pengguna adalah jawaban yang tingkat kesasihannya (validity, di dalamnya mencakup consistency dan informativeness) sangat tinggi. Jika kita berbicara mengenai logika predikat, maka patut diperhatikan bahwa pada tahun 1879, filsuf berkebangsaan Jerman yang bernama Gottlob Frege menerbitkan sebuah risalat yang luar biasa, yang berjudul the Begriffsschrift (“Concept Script”). Monograp yang brilian ini dianggap sebagai asal muasal dari teori logika modern. Akan tetapi, dalam risalat milik Friege ini masih terdapat banyak kekurangan dalam beberapa bagian dan janggal dalam penotasiannnya. Walaupun demikian, penemuan Frege ini tetap diakui. Selain penemuan dari Frege, formulasi dari logika predikat yang sering digunakan sekarang adalah firstorder logic atau yang biasa dikenal dengan kalkulus predikat yang tercatat dalam Principle of Theorical Logic yang ditulis oleh David Hilbert dan Wilhelm Ackerman pada tahun 1928. First order logic dalam hal ini merupakan dasar pendiri logika matematika modern.

Di sini hanya akan disediakan beberapa poin penting yang membedakan kalkulus predikat dengan logika Aristotle. Beberapa poin tersebut diantaranya:

Di dalam kalkulus predikat didefinisikan bahwa subjek adalah hanya sebuah individu tidak pernah merupakan sekelompok individu. Karena subjek dalam kalkulus predikat ini hanyalah sebuah individu, maka subjek di sini lebih umum untuk disebutkan sebagai individual. Kalkulus predikat memakai banyak simbol-simbol khusus untuk menotasikan sesuatu. Huruf kecil a, b, c, d, …, z digunakan untuk menyatakan individual. Huruf kapital M, N, P, Q, R, … digunakan untuk menyatakan predikat. Jika terdapat notasi seperti Ma, maka dikatakan bahwa a adalah argument untuk M. Selain huruf kecil dan huruf kapital, kalkulus predikat juga menggunakan beberapa simbol khusus untuk menotasikan operator-operator logika. Beberapa simbol khusus itu adalah: ∧ ∨ ~ ⊃ ≡

Sebuah formula adalah ekpresi yang memiliki arti dan dibangun oleh atom-atomnya dan digabungkan dengan menggunakan operatoroperator logika. Kalkulus predikat memiliki kapabilitas yang besar dalam mengekspresikan suatu hal. Banyak pernyataan dalam natural language yang bisa direpresentasikan dengan baik oleh kalkulus predikat. Hal inilah yang kurang dimiliki oleh logika Aristoteles.

Dalam first-order logic yang paling utama adalah bahwa dunia berisi objek-objek yaitu identitas (ciri-ciri individu) dan sifat (properties) yang membedakan mereka dengan objek yang lain. Diantara objek tersebut, akan dibuat bermacam-macam relasi. Beberapa relasi adalah fungsi yaitu hubungan dimana hanya ada satu nilai untuk satu input. Jadi pada first-order logic mengasumsikan “world” memuat :

-Objek : hal-hal yang berhubungan dengan identitas individu, misalnya : manusia, rumah, teori-teori, warna, mobil, dan lain-lain.

-Sifat (properties): sifat benda yang membedakannya dari benda lain, misalnya: merah, bulat, tipis, dan lain-lain

-Relasi : hubungan antara benda yang satu dengan benda yang lainnya, misalnya: lebih besar dari, lebih kecil dari, memiliki, terjadi setelah, dan lain-lain.

-Fungsi (Functions): merupakan subset dari hubungan di mana hanya ada satu “nilai” untuk setiap “input” yang diberikan, misalnya: ayah dari, teman baik, dan lain-lain.

First Order Logic sangat penting dalam ilmu matematika, filsafat, kecerdasan buatan, karena ruang lingkupnya, sebab keberadaan manusia sehari-hari selalu berhubungan dengan obyek dan hubungan antar manusia sendiri. Sehingga kita tidak dapat menyangkal bahwa dunia ini terdiri dari obyek dan hubungan (relasi).

B. SINTAK DAN SEMANTIK LOGIKA ORDE PERTAMA

Model

Sebuah model adalah sebuah situasi yang menjelaskan hal-hal yang menjadi konteks pembicaraan. Untuk membentuk sebuah model, diperlukan adanya kosa-kata (vocabularies), yaitu daftar istilah yang membentuk model tersebut. Sebuah kosa-kata berisikan topik pembicaraan dan bahasa (simbol) yang digunakan dalam pembicaraan. Dalam contoh kalimat‘ayah dan anto makan sepiring nasi’, akan terdapat kosa-kata sebagai berikut: {(ayah,1), (anto,0),(makan,2), (nasi,1)}. Dalam kosa-kata ini akan terlihat bagaimana relasi antara fakta atauvariabel yang satu dengan lainnya di dalam representasi. Perlu dibedakan antara fakta (sebuah konstanta / non-binding variable), dengan variabel yang dapat menampung sebuah fakta (binding variable). Dalam contoh, relasi ‘makan’ menjelaskan bahwa aktivitas tersebut dapat terjadi jika melibatkan dua konstanta (relasi biner yang memiliki arity2). Angka 1 menjelaskan bahwa terjadi relasi tunggal (arity1), yang dapat diisikan (binding) dengan sebuah konstanta. Angka 0 menjelaskan sebuah konstanta, dan bukan merupakan relasi.

• Syntax FOL: Elemen-Elemen Dasar

Elemen-elemen dasar FOL:

Constants : KingJohn, 2, UB, ITS, UI, Malang, Depok , . . .

Predicates : Brother , >, Loves, Membenci , Mengajar , . . .

Functions : Sqrt , LeftLegOf , Ayah, . . .

Variables : x , y , a, b, . . .

Connectives : ∧ ∨ ¬ ⇒ ⇔

Equality :        =

Quantifiers : ∀ ∃

• Syntax FOL : Kalimat Atomic

Definisi atomic sentence : predicate(term1, , termn) atau term1 = term2

Definisi term :

function(term1, , termn) atau constant atau variable

Contoh :

Brother (KingJohn, RichardTheLionheart )

> (Length(LeftLegOf (Richard)), Length(LeftLegOf (KingJohn)))

• Syntax FOL : Kalimat Kompleks

Kalimat kompleks complex sentence terdiri dari sentence yang digabungkan dengan connective.

Definisi complex sentence : ¬S, S1∧ S2, S1∨ S2, S1 ⇒ S2, S1 ⇔ S2

Contoh :

Sibling(KingJohn, Richard ) ⇒ Sibling(Richard , KingJohn)

>(1, 2) ∨ ≤(1, 2)

>(1, 2) ∧ ¬>(1, 2)

Belajar (x , SC) ⇒ Mengerti(x , AI)

• Semantics FOL : Truth & Model

Sama halnya dengan. Proposisi Logic (PL), sebuah kalimat FOL bisa juga dikatakan true terhadap sebuah model.

Namun, sebuah kalimat bisa diinterpretasikan banyak cara dalam sebuah model.

Model berisi :

Objects : elemen-elemen di dalam dunia (domain elements).

Relations : hubungan antara elemen-elemen tersebut.

Sebuah interpretasi mendefinisikan referent (“yang dipetakan”)

Constant symbols → objects

Predicate symbols → relations

Function symbols → functional relations

• Kemungkinan Model & Interpretasi

Entailment , validity , satisfiability , dll. Didefinisikan untuk semua kemungkinan interpretasi dari semua kemungkinan model!

Kalau mau dijabarkan semua kemungkinannya: For each number of domain elements n from 1 to ∞ For each k -ary predicate Pk in the vocabulary For each possible k -ary relation on n objects For each constant symbol C in the vocabulary For each choice of referent for C from n objects . .

Menentukan entailment berdasarkan truth-table? mustahil!

Biasanya ada satu interpretasi yang “dimaksudkan” → intended interpretation.

• Quantifier

Selain penggunaan predikat, First Order Logic juga menawarkan quantifier untuk membuat kalimat logika yang lebih sederhana. Ada 2 jenis quantifier, yaitu universal dan existential. Quatifier ini berlaku terhadap parameter yang muncul di sebuah kalimat masih dalam bentuk variabel. Universal quantifier terhadap sebuah variabel x (disimbolkan dengan ∀x) berarti bahwa kalimat tersebut berlaku untuk setiap obyek x, sedangkan existential quantifier (disimbolkan dengan ∃x) berarti berlaku untuk sebagian obyek saja.

Contoh: Menggunakan definisi untuk p(x), r(x), dan q(x,y), berikut adalah kalimat-kalimat logika dengan menggunakan quantifier dan artinya:

1. ∀x(p(x) Λ r(rabu) → q(x,merah-putih)) : untuk setiap x, jika x adalah seorang siswa kelas II SD dan pada hari Rabu maka x akan mengenakan seragam merah-putih.
2. ∃x(p(x) → ¬q(x,merah-putih)) : ada x, jika x adalah seorang siswa kelas II SD maka x tidak mengenakan seragam merah putih.

• Universal Quantifier

Dalam logika predikat , quantifieri universal merupakan jenis quantifier , sebuah konstanta logis yang ditafsirkan sebagai “diberi” atau “untuk semua”. Ini mengungkapkan bahwa fungsi proposisi dapat dipenuhi oleh setiapanggota dari domain wacana. Dalam istilah lain, itu adalah predikasi dari properti atau hubungan dengan setiap anggota domain. Ini menegaskanbahwa predikat dalam lingkup dari quantifier universal benar dari setiap nilai dari variabel predikat .

Hal ini biasanya dilambangkan dengan berbalik A (∀) operator logika simbol, yang bila digunakan bersama-sama dengan variabel predikat, disebut quantifier universal  (“∀x”, “∀ (x)”, atau kadang-kadang dengan “(x) “saja). Kuantifikasi Universal berbeda dari kuantifikasi eksistensial (“ada ada”), yang menegaskan bahwa properti atau relasi hanya berlaku untuk setidaknya satu anggota dari domain.

Contoh 1 :

(∀x) (x + x = 2x)

“untuk setiap x (dimana x adalah suatu bilangan), kalimat x + x = 2x adalah benar.”

Contoh 2 :

(∀x) (p) (Jika x adalah seekor kelinci -> x adalah binatang).

Kebalikan kalimat “bukan kelinci adalah binatang” ditulis :

(∀x) (p) (Jika x adalah seekor kelinci -> ~x adalah binatang)

dan dibaca :

– “setiap kelinci adalah bukan binatang”

“semua kelinci adalah bukan binantang”

• Existential Quantifier

Dalam logika predikat , suatu quantifier eksistensial adalah jenis quantifier , sebuah konstanta logis yang ditafsirkan sebagai “ada ada,” “ada setidaknya satu,” atau “untuk beberapa.” Ini mengungkapkan bahwa fungsi proposisi dapat dipenuhi oleh setidaknya satu anggota dari domain wacana . Dalam istilah lain, itu adalah predikasi dari properti atau hubungan dengan setidaknya satu anggota dari domain. Ini menegaskan bahwa predikat dalamlingkup dari quantifier eksistensial adalah benar dari setidaknya satu nilai darivariabel predikat .

Hal ini biasanya dilambangkan dengan E berubah (∃) operator logika simbol, yang bila digunakan bersama-sama dengan variabel predikat, disebut quantifier eksistensial (“∃x” atau “∃ (x)”) Kuantifikasi eksistensial.

Contoh 1 :

(∃x) (x . x = 1)

Dibaca : “terdapat x yang bila dikalikan dengan dirinya sendiri hasilnya sama dengan 1.”

Contoh 2 :

(∃x) (panda(x) ∧ nama(Clyde))

Dibaca : “beberapa panda bernama Clyde”.

Contoh 3 :

(∀x) (jerapah(x) -> berkaki empat(x))

Dibaca : “semua jerapah berkaki empat”.

Universal quantifier dapat diekspresikan sebagai konjungsi.

(∃x) (jerapahh(x) ∧ berkaki tiga(x))

Dibaca : “ada jerapah yang berkaki tiga”

Existensial quantifier dapat diekspresikan sebagai disjungsi dari

urutan ai. P(a1) ∨ P(a2) ∨ P(a3) …∨ P(aN)

C. PENGGUNAAN LOGIKA ORDE PERTAMA

1. Assertions and queries in first-order logic.

2. The kinship domain.

3. Numbers, sets, and lists.

D. REKAYASA PENGETAHUAN PADA LOGIKA ORDE PERTAMA

1. Identify the task.

2. Assemble the relevant knowledge.

3. Decide on a vocabulary of predicates, functions, and constants.

4. Encode general knowledge about the domain

5. Encode a description of the specific problem instance.

6. Pose queries to the inference procedure and get answers.

7. Debug the knowledge base.

 E. LOGIKA PROPOSISI VS INFERENSI LOGIKA ORDE PERTAMA

Contoh Permasalahan

Pembuktian Logika Proposisi

Setiap manusia pasti mati. Karena Sayuti adalah manusia, maka dia pastimati.

Secara intuisi kalimattersebut bernilai Benar. Berdasarkan logika proposisi kalimat tersebut dapat

disimbolkan sebagai:

p : Setiap manusia pasti mati

q : Sayuti adalah manusia

r : Sayuti pasti mati

Berdasarkan kerangka berfikir Logika Proposisi bukanlah konsekuensi Logis dari pdan q. Pernyataan

‘Setiap manusia pasti mati’ mengandung pernyataan Himpunan, yaitu Himpunan ‘manusia’, dimana

individu yang merupakan bagian dari himpunan manusia jumlahnya tidak terhingga. Sedangkan

pernyataan ‘Sayuti adalah manusia’ secara implisit menyatakan anggota dari himpunan ‘manusia’/

universal of discourse.

Struktur sepertidiatas tidak dikenali oleh Logika Proposisi, karena apabila ingin membuktikan

kebenaran dari pernyataan ‘Setiap manusiapasti masti’ maka harus dicari nilai kebenaran dari seluruh

elemen himpunan manusia yang jumlahnya tak terhingga. Ini tidak mungkin dilakukan.

Untuk mengatasi permasalahan diatas diperlukan kerangka berfikir lain selain Logika Proposisi yaitu

Logika First-Order (Kalkulus Predikat). Maka dapat didefinisikan bahwa Logika First-Order adalah

perluasan dari konsep Logika Proposisi untuk mengatasi permasalahan yang tidak dapat dipecahkan

melalui kerangka berfikir Logika Proposisi dengan penambahan 3 komponen logika yaitu: Term

(suku), Predicate dan Quantifier.

Pembuktian pada Logika First-Order

Pembuktian Logika First-Order hampir sama dengan pembuktian pada Logika Proposisi. Hanya saja

pada Logika First-Order pembuktian menggunakan Aturan Inferensi lebih mungkin untuk dilakukan.

Contoh:

Buktikan bahwa “Setiap manusia pasti mati. Sayuti adalah manusia, Karenanya Sayuti pasti mati.”

Jawab:

Misal dideklarasikan predikat berikut:

MAN(x)        :x adalah manusia

MORTAL(x) :x pasti mati

Maka pernyataan pada soal menjadi:

P1                  :(x) (MAN(x) MORTAL(x))

P2                  :MAN(Sayuti)

Untuk membuktikan bahwa kesimpulan “Sayuti pasti mati”harus dibuktian bahwa MORTAL(Sayuti)

adalah konsekuensi logis dari P1dan P2. Maka;

Dilakukan pembuktian langsung:

P1P2             : (x) (MAN(x) MORTAL(x)) MAN(Sayuti)

Karena (MAN(x)  MORTAL(x)) bernilai Benar untuk semua x maka;

(MAN(Sayuti)  MORTAL(Sayuti)) juga Benar

(x) (MAN(x)MORTAL(x))

MAN(Sayuti)

(MAN(Sayuti)MORTAL(Sayuti))

MORTAL(Sayuti)

Premis P1

Premis P2

Langkah 1 dan 2

P1: x Sayuti

F. UNIFIKASI DAN LIFTING

Unifikasi adalah usaha untuk mencoba membuat dua ekspresi menjadi identik (mempersatukan keduanya) dengan mencari substitusi-substitusi tertentu untuk mengikuti peubah-peubah dalam ekspresi mereka tersebut. Unifikasi merupakan suatu prosedur sistematik untuk memperoleh peubah-peubah instan dalam wffs. Ketika nilai kebenaran predikat adalah sebuah fungsi dari nilai-nilai yang diasumsikan dengan argumen mereka, keinstanan terkontrol dari nilai-nilai selanjutnya yang menyediakan cara memvalidasi nilai-nilai kebenaran pernyataan yang berisi predikat. Unifikasi merupakan dasar atas kebanyakan strategi inferensi dalam Kecerdasan Buatan. Sedangkan dasar dari unifikasi adalah substitusi.

Suatu substitusi (substitution) adalah suatu himpunan penetapan istilah-istilah kepada peubah, tanpa ada peubah yang ditetapkan lebih dari satu istilah. Sebagai pengetahuan jantung dari eksekusi Prolog, adalah mekanisme unifikasi.

Aturan-aturan unifikasi :

1.     Dua atom (konstanta atau peubah) adalah identik.

2.     Dua daftar identik, atau ekspresi dikonversi ke dalam satu buah daftar.

3.  Sebuah konstanta dan satu peubah terikat dipersatukan, sehingga peubah menjadi terikat kepada konstanta.

4.     Sebuah peubah tak terikat diperssatukan dengan sebuah peubah terikat.

5.  Sebuah peubah terikat dipersatukan dengan sebuah konstanta jika pengikatan pada peubah terikat dengan konstanta tidak ada konflik.

6.   Dua peubah tidak terikat disatukan. Jika peubah yang satu lainnya menjadi terikat dalam upa-urutan langkah unifikasi, yang lainnya juga menjadi terikat ke atom yang sama (peubah atau konstanta).

7.    Dua peubah terikat disatukan jika keduanya terikat (mungkin melalui pengikatan tengah) ke atom yang sama (peubah atau konstanta).

G. FORWARD & BACKWARD CHAINING

• FORWARD CHAINING

Forward chaining merupakan metode inferensi yang melakukan penalaran dari suatu masalah kepada solusinya. Jika klausa premis sesuai dengan situasi (bernilai TRUE), maka proses akan menyatakan konklusi. Forward chaining adalah data-driven karena inferensi dimulai dengan informasi yang tersedia dan baru konklusi diperoleh. Jika suatu aplikasi menghasilkan tree yang lebar dan tidak dalam, maka gunakan forward chaining.

Contoh :

Terdapat 10 aturan yang tersimpan dalam basis pengetahuan yaitu :

R1 : if A and B then C

R2 : if C then D

R3 : if A and E then F

R4 : if A then G

R5 : if F and G then D

R6 : if G and E then H

R7 : if C and H then I

R8 : if I and A then J

R9 : if G then J

R10 : if J then K

Fakta awal yang diberikan hanya A dan E, ingin membuktikan apakah K bernilai benar.

• BACKWARD CHAINING

Menggunakan pendekatan goal-driven, dimulai dari harapan apa yang akan terjadi (hipotesis) dan kemudian mencari bukti yang mendukung (atau berlawanan) dengan harapan kita. Sering hal ini memerlukan perumusan dan pengujian hipotesis sementara. Jika suatu aplikasi menghasilkan tree yang sempit dan cukup dalam, maka gunakan backward chaining.

H. RESOLUSI LOGIKA PREDIKAT

Resolusi pada logika predikat pada dasarnya sama dengan resolusi pada logika proposisi, hanya saja ditambah dengan unifikasi.Pada logika predikat, prosedur untuk membuktikan pernyataan P dengan beberapa pernyataan F yang telah diketahui, dengan menggunakan resolusi, dapat dilakukan melalui algoritma sebagai berikut :

1.     Konversikan semua proposisi F ke bentuk klausa

2.     Negasikan P, dan konversikan hasil negasi tersebut ke bentuk klausa.Tambahkan   kehimpunan klausa yang telah ada pada langkah

3.     Kerjakan hingga terjadi kontradiksi atau proses tidak mengalami kemajuan :

§  Seleksi 2 klausa sebagai klausa parent

§  Bandingkan (resolve) secara bersama-sama. Klausa hasil resolve tersebut  resolvent. Jika ada pasangan literal T dan ¬T2 sedemikian hingga keduanya dapat dilakukan unifikasi, maka salah satu T1 dan T2 disebut sebagai complementary literal. Jika ada lebih dari 1 complementary literal, maka hanya sepasang yang dapat meninggalkan resolvent

§  Jika resolvent berupa klausa kosong, maka ditemukan kontradiksi. Jika tidak, tambahkan ke himpunan klausa yang telah ada

Contoh kasus :

Misalkan terdapat pernyataan-pernyataan sebagai berikut :

1.     Fajar adalah seorang mahasiswa

2.     Fajar masuk Jurusan Elektro

3.     Setiap mahasiswa elektro pasti mahasiswa Teknik

4.     Kalkulus adalah matakuliah yang sulit

5.     Setiap mahasiswa teknik pasti akan suka kalkulus atau akan membencinya

6.     Setiap mahasiswa pasti akan suka terhadap suatu matakuliah

7.     Mahasiswa yang tidak pernah hadir pada kuliah matakuliah sulit, maka mereka pasti tidak   suka terhadap matakuliah tersebut

8.     Fajar tidak pernah hadir kuliah matakuliah kalkulus

Maka harus terlebih dahulu diubah ke dalam bentuk klausa sebagai berikut :

1.     Mahasiswa (Fajar)

2.     Elektro (Fajar)

3.     Elektro (x1) v Teknik (v1)

4.     Sulit (Kalkulus)

5.     Teknik (x2) v suka (x2, Kalkulus) v benci (x2, Kalkulus)

6.     Suka (x3, f1 (x3))

7.     Mahasiswa (x4) v ¬ sulit (y1) v hadir (x4, y1) v ¬ suka (x4, y1)

8.     Hadir (Fajar, Kalkulus)

Sumber:

[Bos, J. 2006], LogAnswer [Furbach, U., et. al. 2009].

Russel, Stuart, Artificial Intelligence : a modern Approach, pearson, 2011.

Ebook Artifical Intelligence A Modern Approach(3rd Edition).

https://ismailakbar12.wordpress.com/2015/06/25/makalah-artifical-intellegent-representasi-pengetahuan/

https://bellavira.blogspot.co.id/2017/10/pertemuan-5-logika-orde-pertama-first.html

http://ulungsatria.webs.com/apps/blog/show/10671951-logika-predikat-

Read More

Pengetahuan dan Penalaran

1.      Pengetahuan Berbasis Agen

AGENT adalah sesuatu yang dapat mengesan ( percieving ) lingkungan (environment) nya  melalui  sensors dan bertindak ( Acting ) terhadap lingkungan tersebut melalui actuators.

Dalam kecerdasan buatan, intelligent agent (IA) adalah sebuah entitas otonom yang mengamati dan bertindak atas lingkungan (yaitu membutuhkan agen) dan mengarahkan aktivitasnya untuk mencapai tujuan  yaitu rasional.Intelligent agen juga dapat belajar atau menggunakan pengetahuan untuk mencapai tujuan mereka. Russell & Norvig (2003) mengartikan Rational Agent  yang mengerjakan segala sesuatu hal dengan benar.

Selanjutnya saya akan membahas tentang PEAS. PEAS adalah singkatan dari Performance Measure, Environment, Actuators, dan Sensor. Dimana harus dispesifikasikan terlebih dahulu mengenai rancangan intelligent agent.

Lalu tipe tipe agent yang terdapat dalam intelegent agent ada 5 tipe, yaitu:

1. Simple Reflex Agents

2. Model Based Reflex Agents

3. Goal-Based Agents

4. Utility-Based Agents

5. Learning Agents

2.      Logika

Logic merupakan jantung dari program, para pemrogram mempunyai keyakinan bahwa sebuah computer dapat dibuat mengerti logika, maka computer dapat dibuat untuk berfikir, karena logika kelihatannya menjadi inti dari kecerdasan.

1. Problem solving agent hanya bisa menyelesaikan masalah yang lingkungannya accessible

2.      Kita membutuhkan agen yang dapat menambah pengetahuan dan menyimpulkan keadaan

3.      Agent yang akan membantu seperti ini kita beri nama knowledge based agent

Knowledge based agent

Komponen utama dari knowledge based agent adalah knowledge basenya. Knowledge base (KB) adalah kumpulan representasi fakta tentang lingkungan atau dunia yang berhubungan atau menjadi daerah bekerjanya agen. Setiap representasi dalam KB disebut sebagai sebuah sentence yang diekspresikan dalam sebuah bahasa yakni knowledge representation language

1.      Representasi Pengetahuan yang bersifat general.

2.       Kemampuan beradaptasi sesuai temuan fakta.

3.       Kemampuan menyimpulkan sesuatu dari pengetahuan yang sudah ada.

Syarat Representasi KB:

1 . Representational    Adequacy

kemampuan merepresentasikan semua pengetahuan yang dibutuhkan dalam domainnya

2.  Inferential        Adequacy

kemampuan memanipulasi struktur pengetahuan untuk membentuk struktur baru dalam menampung pengetahuan baru hasil inferensi

3 . Inferential        Efficiency

kemampuan untuk manambahkan informasi untuk mempercepat pencarian dalam inferensi

4 . Acquisitional  Efficiency

kemampuan untuk menambah informasi baru secara mudah.

Pengetahuan yang dimiliki agent tidak berguna jika ia tidak melakukan apapun Karenanya kita perlu menambahkan aturan agar dia dapat bergerak (complete the knowledge base).

Beberapa tahapan yang dilakukan dalam menyusun knowledge based agent:

·Untuk dapat menyusun sebuah knowledge based agent maka kita harus terlebih dulu bisa menyusun knowledge basenya itu sendiri.

·Untuk menyusun knowledge base kita perlu menentukan bagaimana cara kita merepresentasikan pengetahuan kita (knowledge representation).

Knowledge representation kita harus merupakan bentuk yang mudah disimpan dan digunakan pada komputer. Dalam perkuliahan ini kita menggunakan beberapa macam knowledge representation language.

3.Logika Proposisi

Proposional logic berupa kalimat-kalimat lengkap dari fakta atau kenyataan, atau bisa dikatakan sebuah propositional logic bisa merupakan sebuah proposisi adalah kalimat yang berbentuk dengan sendirinya, apakah kalimat itu bernar atau kalimat itu salah. Propositional logic merupakan operator-operator untuk menghubungkan proposisi-proposisi dalam bentuk, ungkapan dan ekspresi, sebagai kata penyambung logika.

Penggunaan dari propositional logic sebagai langkah atau cara mempresentasikan dari pengetahuan dunia yang diperlukan dari sebuah sistem yang sudah terorganisir (AI). Ekspresi-ekspresi dibentuk menurut semua tata bahasa sederhana, dan ekspresi yang sesuai dengan tata bahasa ini disebut well formed formulae (wffs). Tanda kurung digunakan untuk membuat kelas urutan dari penempatan nilai kebenaran, jika tidak yang lain jelas. Suatu well formed formulae merupakan salah satu proposisi atau akan memiliki salah satu bentuk.

SINTAKS

Seringkali kita mendengar sintak dalam istilah pemrograman. Namun, terkadang kita tidak mengetahui dengan jelas apa arti sintak sebenarnya.

Sintak  sebuah bahasa berhubungan dengan struktur bahasa. Sebagai contoh, untuk membentuk sebuah kalimat yang valid dalam bahasa kita memakai struktur: [subyek] + [kata kerja] + [kata benda]. Dengan memakai struktur ini, kita bisa membentuk kalimat, sebagai contoh: Saya makan nasi. Dalam hubungannya dengan bahasa pemrograman, kita harus memenuhi sintak (baca: aturan struktur bahasa) agar program dapat berjalan atau jika lebih spesifik lagi sintak dapat diartikan aturan-aturan peng-code-an struktur suatu bahasa pemograman, ibarat grammar dalam berbahasa Inggris. Setiap jenis bahasa pemograman mempunyai aturan sintak yang berbeda.

Sintaks berfungsi menyediakan bentuk-bentuk notasi untuk komunikasi antar programmer dan pemroses bahasa pemrograman sehingga dapat mempermudah pembuatan suatu program.

Suatu bahasa pemrograman juga dibangun berdasarkan elemen-elemen syntactic, yang dapat membentuk suatu statement-statement dalam bahasa pemrograman. Elemen-elemen tersebut antara lain :

a. Himpunan karakter

b. Identifier.

c. Simbol untuk operator.

d. Keyword dan reserved word.

e. Noise word.

f. Komentar.

g. Blank.

h. Delimiter dan tanda kurung.

i. Ekspresi.

SEMANTIK

Sintak mendifinisikan suatu bentuk program yang benar dari suatu bahasa. Semantic mendefinisikan arti dari program yang benar secara sintak dari bahasa tersebut. Semantic suatu bahasa membutuhkan semacam ekspresi untuk mengirimkan suatu nilai kebenaran (TRUE, FALSE, NOT atau nilai integer). Dalam banyak kasus, program hanya dapat dieksekusi jika benar, serta mengikuti aturan sintak dan semantic. Semantik suatu bahasa pemrograman mempunyai banyak potensial / keunggulan, beberapa diantara nya adalah :

a. Standarisasi bahasa pemrograman.

b. Referensi untuk user.

c. Pembuktian dari program yang benar.

d. Referensi untuk implementor.

e. Implementasi otomatis.

Jika suatu rumusan semantic sulit untuk di deskripsikan secara formal maka rumusan semantic tersebut juga akan sulit digunakan oleh programmer.

Teknik semantic :

a. Operational semantic

b. Detonational semantic.

c. Axiomatic semantic.

d. Algebraic semantic.

e. Structured operational semantic atau natural semantic.

Inferensi

Inferensi pada logika proposisi dapat dilakukan dengan menggunakan resolusi. Metode inferensi adalah mekanisme berfikir dan pola-pola penalaran yang digunakan oleh sistem untuk mencapai suatu kesimpulan. Metode ini akan menganalisa masalah tertentu dan selanjutnya akan mencari  jawaban atau kesimpulan yang terbaik.

Ekuivalen

Dua atau lebih pernyataan majemuk yang mempunyai nilai kebenaran sama disebut ekuivalensi logika dengan notasi “  dua buah pernyataan majemuk dikatakan ekuivalen, jika kedua pernyataan majemuk itu mempunyai nilai kebenaran yang sama untuk semua kemungkinan nilai kebenaran pernyataan-pernyataan komponen-komponennya, terdapat formula-formula yang memiliki operator logika yang berbeda tetapi nilai kebenaran dari formula tersebut bernilai sama, entah itu bernilai TRUE atau FALSE.

Validitas

adalah suatu ukuran yang menunjukkan tingkat keabsahan atau kesahihan suatu tes atau sejauh mana ketepatan dan kecermatan suatu alat ukur dalam melakukan fungsi ukurnya.

Suatu tes dikatakan valid apabila mengukur apa yang hendak diukur. Tes memiliki validitas yang tinggi apabila hasilnya sesuai dengan kriteria, dalam arti memiliki kesejajaran antara tes dan kriteria.

Jenis-jenis validitas adalah :

·         Validitas isi (Content Validity)

·         Validitas konstruk (Construct Validity)

·         Validitas Ukuran

·         Validitas Sejalan (Concurrent Validity)

Satisfiabilitas

Sebuah proposisi majemuk dikatakan satisfiable jika ada minimal satu nilai tabel kebenarannya yang bernilai TRUE (benar), Jika proposisi majemuk tersebut tidak memiliki nilai TRUE (benar) sama sekali dalam tabel kebenarannya, maka proposisi majemuk tersebut disebut tidak satisfiable.

4.Pola Penalaran (Reasoning Pattern).

            Resolusi

Resolusi adalah suatu aturan untuk melakukan inferensi yang dapat berjalan secara efisien dalam suatu bentuk khusus conjunctive normal form (CNF). Pada logika proposisi, prosedur untuk membuktikan proposisi P dengan beberapa aksioma F yang telah diketahui, dengan menggunakan resolusi.

Algoritma resolusi :

(1) Konversikan semua proposisi F ke bentuk CNF.

(2) Negasikan P, dan konversikan hasil negasi tersebut ke bentuk klausa. Tambahkan ke himpunan klausa yang telah ada pada langkah 1.

(3) Kerjakan hingga terjadi kontradiksi atau proses tidak mengalami kemajuan.

Resolusi merupakan suatu teknik pembuktian yang lebih efisien, sebab fakta-fakta yang akan dioperasikan terlebih dahulu dibawa ke bentuk standar yang sering disebut dengan nama klausa. Pembuktian suatu pernyataan menggunakan resolusi ini dilakukan dengan cara menegasikan pernyataan tersebut, kemudian dicari kontradiksinya dari pernyataan-pernyataan yang sudah ada.

Backward Chaining

Menggunakan pendekatan goal-driven, dimulai dari harapan apa yang akan terjadi (hipotesis) dan kemudian mencari bukti yang mendukung (atau berlawanan) dengan harapan kita. Sering hal ini memerlukan perumusan dan pengujian hipotesis sementara. Jika suatu aplikasi menghasilkan tree yang sempit dan cukup dalam, maka gunakan backward chaining.

Forward Chaining

Forward chaining merupakan metode inferensi yang melakukan penalaran dari suatu masalah kepada solusinya. Jika klausa premis sesuai dengan situasi (bernilai TRUE), maka proses akan menyatakan konklusi. Forward chaining adalah data-driven karena inferensi dimulai dengan informasi yang tersedia dan baru konklusi diperoleh. Jika suatu aplikasi menghasilkan tree yang lebar dan tidak dalam, maka gunakan forward chaining.

5.Inferensi Proposisi yang efektif.

            Backtracking

Algoritma backtracking mempunyai prinsip dasar yang sama seperti brute-force yaitu mencoba segala kemungkinan solusi. Perbedaan utamanya adalah pada ide dasarnya, semua solusi dibuat dalam bentuk pohon solusi (pohon ini tentunya berbentuk abstrak) dan algoritma akan menelusuri pohon tersebut secara DFS (depth field search) sampai ditemukan solusi yang layak. Nama backtrack didapatkan dari sifat algoritma ini yang memanfaat karakteristik himpunan solusinya yang sudah disusun menjadi suatu pohon solusi.

6.Agen Berbasis Logika Proposisi

Agen logika merupakan agen yang memiliki kemampuan bernalar secara logika. Ketika beberapa solusi tidak secara eksplisit diketahui, maka diperlukan suatu agen berbasis logika. Logika sebagai Bahasa Representasi Pengetahuan memiliki kemampuan untuk merepresentasikan fakta sedemikian sehingga dapat menarik kesimpulan (fakta baru, jawaban). Sedangkan pengetahuan merupakan komponen yang penting, sehingga terdapat perbedaan jika diterapkan pada dua agent, yakni problem solving agent dan knowledge-based agent.

Perbedaan dua agent, problem solving agent dan knowledge-based agent. Problem solving agent memilih solusi di antara kemungkinan yang ada. Apa yang ia “ketahui” tentang dunia, pengetahuannya tidak berkembang untuk mencapai problem solution (initial state, successor function, goal test) tetapi jika Knowledge-based agent lebih “pintar”. Ia “mengetahui” hal-hal tentang dunia dan dapat melakukan reasoning (berpikir, bernalar) mengenai Hal-hal yang tidak diketahui sebelumnya (imprefect/ partial information). Tindakan yang paling baik untuk diambil (best action).

SUMBER :

http://zeinrizaldi.blogspot.co.id/2016/10/pengenalan-teknologi-sistem-cerdas.html

https://rinnooberta.wordpress.com/2013/10/18/2-logical-agents/

http://husnulkhatimah16.blogspot.co.id/2016/

https://melkianusbenusu.wordpress.com/category/logika-informatika/

http://yogipratama97.blogspot.co.id/2016/10/pengenalan-logical-agents.html

http://syifaalyan.blogspot.co.id/

http://ctatyasoctavianti.blogspot.co.id/2012/09/matematika-diskrit-logika.html

http://mochblack.blogspot.co.id/

http://raodhotulm.blogspot.co.id/2014/04/logika-dan-penalaran.html

Read More

Pencarian Berbentuk Heuristik Search Dan Eksplorasi

Greedy Best First Search

Salah satu algoritma yang termasuk kedalam kategori informed search adalah Greedy Best First Search yang dikenal juga dengan Greedy Search. Secara harfiah greedy artinya rakus atau tamak, sifat yang berkonotasi negative. Sesuai dengan arti tersebut, prinsip greedy adalah mengambil keputusan yang dianggap terbaik hanya untuk saat itu saja yang diharapkan dapat memberikan solusi terbaik secara keseluruhan. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya.

Greedy Best First Search seperti halnya algoritma yang menggunakan strategi best-first search lainnya mempuyai sebuah fungsi yang menjadi acuan kelayakan sebuah simpul yaitu fungsi evaluasi f(n). padaGreedy Best First Search fungsi evaluasi tidak bergantung pada cost sebelumnya, tetapi hanya bergantung pada fungsi heuristic itu sendiri.jika pada algoritma pencarian yang dilakukan bergantung pada cost sebenarnya dari sebuah simpul yaitu g(n), pada Greedy Best First Search fungsi evaluasi hanya bergantung pada fungsi heuristic h(n) yang mengestimasikan arah yang benar, sehingga pencarian jalur dapat berlangsung dengan sangat secapt. Secara matematis fungsi evaluasi pada greedy search diberikan oleh :

f(n) = h(n)

dengan :

g(n) = estimasi biaya dari simpul n ke simpul tujuan (goal node).

Berikut langkah-langkah pencarian lintasan terpendek yang dilakukan Greedy Best First Search :

•  Masukan simpul awal ke dalam Open List.
• Open berisi simpul awal dan Closed List masih kosong.
•  Masukkan simpul awal ke Closed List dan suksesornya pada Open List.
• Ulangi langkah berikut sampai simpul tujuan ditemukan dan tidak ada lagi simpul yang akan dikembangkan.
• Hitung nilai f simpul-simpul yang ada pada Open List, ambil simpul terbaik (f paling kecil).
• Jika simpul terbesar sama dengan simpul tujuan, maka sukses.
• Jika tidak, masukkan simpul tersebut ke dalam Closed.
• Bangkitkan semua suksesor dari simpul tersebut.

Untuk setiap suksesor kerjakan :

a.    Jika suksesor tersebut belum pernah dibangkitkan, evaluasi suksesor tersebut, tambahkan ke Open dan catat “parent”nya.

b.   Jika suksesor tersebut sudah pernah dibangkitkan, ubah parent-nya jika jalur parent ini lebih baik daripada jalur melalui parent yang sebelumnya. Selanjutnya, perbarui biaya untuk suksesor tersebut.

Algoritma A* (A Star)

Terdapat banyak algoritma pencarian lintasan terpendek, algoritma Dijsktra merupakan salah satu dari algoritma tersebut. Dengan menggunakan fungsi biaya g(n) setiap simpul, algoritma Dijkstra memeriksa kelayakan biaya yang diperlukan untuk mencapai suatu simpul dari sebuah simpul lain. Proses ini dilakukan berulang sampai simpul tujuan diperiksa.

Algoritma Dijkstra memang menjamin didapatkannya jalur optimal, tetapi algoritma ini mempunyai kelemahan. Pemeriksaan simpul akan dilakukan ke segala arah yang dimungkinkan dan pada akhirnya seluruh simpul pada sebuah graf akan diperiksa. Hal ini menyebabkan algoritma ini bekerja dengan lambat, sehingga waktu yang dibutuhkan untuk menemukan solusi akan semakin besar pula.

Algoritma A* adalah algoritma yang menggabungkan Dijkstra dan algoritma Greedy Best First Search. Selain menghitung biaya yang diperlukan untuk berjalan dari simpul satu ke simpul lainnya, algoritma A* juga menggunakan fungsi heuristic untuk memprioritaskan pemeriksaan simpul-simpul pada arah yang benar, sehingga algoritma A* mempunyai efisiensi waktu yang baik dengan tidak mengorbankan perhitungan biaya sebenarnya.

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)

dengan,

g(n) = biaya dari simpul awal (start node) ke simpul n.

h(n) = estimasi biaya dari simpul n ke simpul tujuan (goal node).

Algoritma A* menggunakan dua buah list yaitu Open List dan Closed List. Seperti halnya best-first searchyang lain kedua list mempunyai fungsi yang sama. Pada awalnya Open List hanya berisi satu simpul awal dan Closed List masih kosong. Perlu diperhatikan setiap simpul akan menyimpan petunjuk “parent”nya sehingga stelah pencarian berakhir lintasan juga akan didapatkan. Berikut adalah langkah-langkah algoritma A* (A Star) :

• Masukkan simpul awal ke Open List.
• Ulangi langkah berikut sampai pencarian berakhir.

a.      Cari node n dengan nilai f(n) paling rendah, dalam Open List. Node ini akan menjadi current node.

b.     Keluarkan current node dari Open List dan masukkan ke Closed List.

c.      Untuk setiap suksesor dari current node lakukan langkah berikut :

-  Jika sudah dalam terdapat dalam Closed List, abaikan, jika tidak lanjutkan.

- Jika belum ada pada Open List, masukkan ke Open List. Simpan current node sebagai “parent” dari suksesor ini. Simpan cost masing-masing simpul.

- Jika sudah ada dalam Open List, periksa jika simpul suksesor ini mempunyai nilai lebih disbanding suksesor sebelumnya. Jika lebih kecil, jadikan sebagai current node dang anti “parent” node ini.

d.   Walaupun telah mencapai simpul tujuan, jika masih ada suksesor yang memiliki nilai lebih kecil, maka simpul tersebut akan terus dipilih sampai bobotnya jauh lebih besar atau mencapai simpul akhir dengan bobot yang lebih kecil disbanding dengan simpul sebelumnya yang telah mencapai simpul tujuan.

e.    Pada setiap pemilihan simpul berikutnya, nilai f(n) akan dievaluasi dan jika terdapat nilai f(n) yang sama akan dipilih berdasarkan nilai g(n) terbesar.

Memory-Bounded Heuristic Search

1. Fungsi Heuristik

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

2. Algoritma pencarian lokal dan masalah optimisasi yaitu meliputi :

A) Hill Climbing Search

            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 lainnya yang mungkin. 

B) Simulated Annealing Search

            Simulated Annealing adalah suatu algoritma optimasi yang mensimulasikan proses annealing pada pembuatan materi yang terdiri dari butir kristal atau logam. Algoritma untuk untuk optimisasi yang bersifat generik. Berbasiskan probabilitas dan mekanika statistik, algoritma ini dapat digunakan untuk mencari pendekatan terhadap solusi optimum global dari suatu permasalahan. Masalah yang membutuhkan pendekatan SA adalah masalah-masalah optimisasi kombinatorial, di mana ruang pencarian solusi yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahan itu

            Berikut ini adalah pemetaan dari Physical Annealing ke Simulated Annealing :

Fisika (termodinamika)	Simulated Annealing
Keadaan sistem	Solusi yang mungkin
Energi	Biaya
Perubahan keadaan	Solusi tetangga
Temperatur	Parameter kontrol
Keadaan beku	Solusi heuristik

Annealing adalah satu teknik yang dikenal dalam bidang metalurgi, digunakan dalam mempelajari proses pembentukan kristal dalam suatu materi. Agar dapat terbentuk susunan kristal yang sempurna, diperlukan pemanasan sampai suatu tingkat tertentu, kemudian dilanjutkan dengan pendinginan yang perlahan-lahan dan terkendali dari materi tersebut. Pemanasan materi di awal proses annealing, memberikan kesempatan pada atom-atom dalam materi itu untuk bergerak secara bebas, mengingat tingkat energi dalam kondisi panas ini cukup tinggi. Proses pendinginan yang perlahan-lahan memungkinkan atom-atom yang tadinya bergerak bebas itu, pada akhirnya menemukan tempat yang optimum, di mana energi internal yang dibutuhkan atom itu untuk mempertahankan posisinya adalah minimum.

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

a.   Nilai awal untuk temperatur (T0).

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

b.   Kriteria yang digunakan untuk memutuskan apakah temperatur sistem seharusnya dikurangi.

c.   Berapa besarnya pengurangan temperatur dalam setiap waktu.

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 :

a.  Cari node yang belum pernah digunakan; gunakan node 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 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 untmencari 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 :

a. 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.

b. 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.

c. 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 mtode 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.

Agen pencarian online dan lingkungan yang tidak diketahui.

1. Pencarian buta (uninformed/blind search) : tidak ada informasi awal yang digunakan dalam proses pencarian.

2. Pencarian melebar pertama (Breadth – First Search).

3. Pencarian mendalam pertama (Depth – First Search).

Sumber:

Buku "Perpustakaan Universitas Pendidikan Indonesia". Hal 20-27.

http://fryunfirst.blogspot.co.id/2015/06/pencarian-heuristik-heuristic-search.html

https://bellavira.blogspot.co.id/2017/10/pencarian-berbentuk-heuristic-search.html

http://aditya291296.blogspot.co.id/2017/09/pencarian-berbentuk-dan-eksplorasi.html

Read More