Agen Logika

Agen Logika

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

• KNOWLADGE BASE AGENT

Agen Berbasis Pengetahuan, Knowledge Base (KB) menyatakan apa yang “diketahui” oleh si agent Pendekatan deklaratif membangun agent: “beritahu” informasi yang relevan, simpan dalam KB. Agen dapat ditanya (atau bertanya diri sendiri) apa yang sebaiknya dilakukan berdasarkan KB. Maka sebuah agen berbasis pengetahuan harus bisa mereprentasikan world, state, action, dst. Menerima informasi baru (dan meng-update representasinya). Menyimpulkan pengetahuan lain yang tidak eksplisit (hidden property).  Menyimpulkan action apa yang perlu diambil.

Agen Berbasis Pengetahuan atau Knowledge Base (KB) merupakan Himpunan representasi fakta yang diketahui tentang lingkungannya. Tiap fakta disebut sebagai sentence. Fakta tersebut dinyatakan dalam bahasa formal sehingga bisa diolah, menambahkan sentence baru ke KB. Inference Engine merupakan menentukan fakta baru yang dapat diturunkan dari pengetahuan yang sudah ada dalam KB.

Agen Berbasis Pengetahuan dalam representasi, agent dapat dipandang dari knowledge level. Apa saja informasi yang diketahui? Misal sebuah robot “mengetahui” bahwa gedung B di antara gedung A dan gedung C. Agent dapat dipandang dari implementation level Bagaimana representasi informasi yang diketahuinya? Logical sentence di_antara(gdB, gdA, gdC). Natural language “Gedung B ada di antara gedung A dan gedung C”.

Agen Berbasis Pengetahuan, pilihan representasi berpengaruh terhadap apa yang bisa dilakukan inference engine. Pada pendekatan deklaratif programmer memberitahu agent informasi tentang environment. Kalau informasi kurang, agen bisa melengkapinya sendiri. Jika dibandingkan dengan pendekatan prosedural programmer secara eksplisit memrogram agen untuk bertindak. Sehingga bagaimana jika program tidak benar, maka akan besar kemungkinan menyebabkan kesalahan.

Agen Berbasis Pengetahuan, permasalahannya adalah bagaimana representasi yang tepat, sehingga ada dua hal yang harus diperhatikan expressive bisa menyatakan fakta tentang environment, Tractable bisa mengolah/ memproses inference engine (dengan cepat). Knowledge merupakan power atau kekuatan dari pemrograman secara deklaratif. Representasi dan penalaran membentuk suatu Intelligence.

• WUMPUS WORLD

Aturan main Wumpus :

·Performance measure: emas +1000, mati -1000, gerak -1, panah -10

·Environment: Matriks 4x4 kamar. Initial state [1,1]. Ada gold, wumpus dan pit yang lokasinya dipilih secara acak.

· Percept:
Breeze: kamar di samping lubang jebakan ada hembusan angin
Glitter: kamar di mana ada emas ada kilauan/sinar
Smell: kamar di samping Wumpus berbau busuk

·Action: maju, belok kiri 90◦ , kanan 90◦ , tembak panah (hanya 1!), ambil benda

Sifat Wumpus :

·                     (Fully) observable? Tidak, hanya bisa persepsi local

·                     Deterministic? Ya, hasil tindakan jelas & pasti

·                     Episodic? Tidak, tergantung action sequence

·                     Static? Ya, gold, wumpus, pit tidak bergerak

·                     Discrete? Ya

·                     Single agent? Tidak

• LOGIC IN GENERAL-MODELS AND ENTAILMENT

Logic adalah bahasa formal untuk merepresentasikan informasi sedemikian hingga kesimpulan dapat dibuat dalam pembuatan kesimpulan pasti harus menggunakan bahasa yg benar dalam pembuatan bahasa yang tepat Syntax mendefinisikan kalimat-kalimat pada bahasa kemudian Semantics mendefinisikan arti kalimat; misal, mendefinisikan kebenaran sebuah kalimat

Entailment berarti sesuatu fakta bisa disimpulkan dari (kumpulan) fakta lain Entailment dapat juga berarti sebuah hubungan antar kalimat ( syntax) yang didasarkan pada semantics kemudian Model adalah sebuah “dunia” di mana kebenaran suatu sentence bisa diuji.

Contoh:

Entailment :

KB mengandung sentence “Anto ganteng” dan “Ani cantik”.

KB |= α1: “Anto ganteng dan Ani cantik”

KB 2 α2: “Anto pintar”

x + y = 4 |= 4 = x + y

Contoh :

Model :

M(α) adalah himpunan semua model dari α

KB= Anto ganteng dan Ani cantik.

α = Anto ganteng

Logika Proposisi

Definisi Logika

Ilmu logika lebihmengarah pada bentuk kalimat (sintaks) daripada arti kalimat itu sendiri(semantik). Ilmu logika selalu berhubungan dengan kalimat-kalimat (argument) dan hubungan yang ada diantarakalimat-kalimat tersebut. Argumentasi adalah kumpulan sebuah kesimpulanbeserta fakta-faktanya. Kesimpulan dikatakan benar apabila merupakanakibat dari fakta-fakta yang diajukan. Apabila semua fakta-fakta yang diajukanberikut kesimpulan adalah benar dan terdapat hubungan logis di antarakeduannya, maka argumentasi tersebut adalah benar atau valid. Akan tetapi,terkadang meskipun fakta-fakta yang diajukan tidak diragukan lagi kebenarannya,bisa saja kesimpulan yang diambil menjadi salah akibat dari cara berfikir yangtidak logis dan akhirnya menyebabkan suatu argumentasi menjadi tidak valid. Tujuanmempelajari logika adalah untuk mampu mengidentifikasi valid atau tidaknyasuatu argumentasi.

Dasar Logika Proposisi

-         Proposisi adalah ekspresi yangmengandung variabel (yaitu variableproposisional) berupa pernyataan danoperator (yaitu operator logika) sebagaikonektor.

-         Pernyataan (Statement) adalah kalimatdeklaratif yang memiliki nilai kebenaran (True dan False)

-         Syntactics Rule (AturanSintaktik) adalah aturan yang diperlukan untuk mengkombinasikan antarapropositions dan propositional connectives untuk menghasilkan sentences(kalimat logika). Dapat dibuat alurnya sebagai berikut Propositions + Propositional Connectives à Sentences Propositional connective yang digunakan: Not, And, Or, If-Then,If-Then-Else, dan If-And-Only-If

-         Interpretasi adalah pemberiannilai kebenaran (true atau false) pada setiap symbol proposisi dari suatukalimat logika.

-         Semantic Rule (Aturan Semantik)adalah suatu aturan yang digunakan untuk menentukan “truth value” dari suatusentence.

Logika proposisimemiliki bentuk berupa kalimat deklaratif (atau pernyataan). Proposisididefinisikan sebagai kalimat deklaratif yang memiliki hanya satu nilaikebenaran yaitu benar saja, salah saja, tetapi tidak keduanya, benar sekaligus salah. Pada umumnyabentuk proposisi adalah kalimat berita yang bisa ditentukan nilai kebenarannya(benar/salah).

Contoh:

1.      Soeharto adalah presiden RI ke-2

2.      4 - 2 = 2

3.      2 + 4 = 5

4.      Siapakah namamu?

5.      Lepas alas kaki sebelum masuk!

6.    

Penjelasan:

Kalimat 1 dan 2 adalahkalimat proposisi yang bernilai benar, Kalimat 3 adalah kalimat proposisi yangbernilai salah, Kalimat 4 dan 5 adalah kalimat tanya dan kalimat perintahdimana keduanya tidak memiliki nilai kebenaran jadi tidak bisa disebut kalimatproposisi, sedangkan Kalimat 6 adalah kalimat pernyataan yang bernilai benarsekaligus salah selama nilai x dan y belum ditetapkan. Misalnya ketikanilai x = y, maka pernyataan menjadi benar, selain dari itu pernyataanmenjadi salah. Oleh karenanya kalimat 6 bukan proposisi.

Untuk memudahkanproses manipulasi atau kalkulasi, proposisi dapat dituliskan secara simbolikdengan menggunakan huruf kecil seperti p, q, r, s, dan seterusnya.Sedangkan yang bukan hasil kombinasi dari proposisi-proposisi disebut atom.Pada saat memanipulasi atau mengkombinasi atom, digunakan operator logikaatau operator sambung (connective operator)yang dilambangkan dengan simbol-simbol sebagai berikut:

SIMBOL

ARTI

BENTUK

Not / Tidak / Negasi

tidak …

And / Dan / Konjungsi

… dan …

(Inclusive) Or / Atau / Disjungsi

… atau …

Implies / Maka / Implikasi

jika … maka …

Iff / Jika Hanya Jika / Bi-Implikasi

… jika dan hanya jika …

Exclusive Or / Or Eklusif

… atau …

Hasil kombinasiatom-atom yang terhubung oleh operator logika akan membentuk formula. Formuladapat didefinisikan sebagai berikut:

Atom adalah formula.Jika p adalah formula, maka adalah formula.Jika p dan q adalah formula, maka (), (), (), () adalah formula

Seluruh formuladibentuk dengan menerapkan aturan . Dalam buku referensi mengenai logika proposisi, formuladisebut juga sebagai proposisi majemuk (compoundproposition). Sedangkan penggunaan operator logika  jarang digunakan tapijika digunakan harus memperhatikan konteks atau keterkaitan isi pembicaraan.

Contoh:

1.      “6 adalah bilangan genap dan5 adalah bilangan ganjil”.

2.      “Jika bumi adalah datar, maka”.

3.      “Setelah wisuda, Sayuti akanbekerja di OKTV Jakarta atau di BBC London”.

4.      “Pada istirahat siang, pesertaseminar diperbolehkan makan atau minum”.

5.      “Pak Taka menghidupkan mobil danberangkat ke kantor OKTV”.

Penjelasan:

Kalimat-1: dapat dinotasikan dengan formula, dimana p adalah“6 adalah bilangan genap” dan qadalah “5 adalah bilangan ganjil”.

Kalimat-2: dapat dinotasikan dengan formula, dimana p adalah“Jika bumi adalah datar” dan q adalah“”. Meskipun kedengarannya janggal akibat kesalahan semantikbahasa kalimat tersebut tetap memenuhi pembentukan proposisi.

Kalimat-3: meskipun sangat jelas bahwakalimat tersebut memiliki operator ‘Atau’ tetapi sangat sulit di notasikan,karena operator ‘Atau’ tersebut memiliki makna ganda yaitu Or Inclusive atau Or Exclusiveyang berarti harus memperhatikan konteks atau keterkaitan isi pembicaraan. Padacontoh kalimat diatas lebih merujuk pada OrExclusive karena tidak mungkin Sayuti bekerja di dua tempat sekaligusdimana lokasi keduanya terpisah jauh secara fisik, dengan demikian kalimattersebut dapat dinotasikan dengan formula .

Kalimat-4: penggunaan ‘Atau’ disini merujukpada Or Inclusive, karena pesertaseminar dapat makan saja, minum saja, atau makan dan minum. Kalimat tersebutdapat dinotasikan dengan formula .

Kalimat-5: penggunaan ‘Dan’ disinimengandung arti ‘Kemudian’ sehingga posisi kalimat proposisi tidak bisaditukar. Misalnya “Budi datang bersamaOdah dan Susi” dapat ditukar menjadi “Budidatang bersama Susi dan Odah”. Sedangkan pada kalimat contoh diatas “PakTaka berangkat ke kantor OKTV dan menghidupkan mobil” artinya menjadilain dengan kalimat asal. Pada Logika Proposional ketika menggunakan operatorlogika ‘/Dan/And’ pertukaran formula seperti itu tidakdipermasalahkan, sehingga kalimat pada contoh diatas dapat dinotasikan denganformula .

Kalkulus Proposisi

Kalkulus Proposisiadalah proses kalkulasi penentuan nilai kebenaran dari suatu formula.Pada contoh-contoh sebelumnya proses kalkulasi terjadi pada saat kitamenentukan nilai kebenaran dari suatu kalimat proposisi menjadi notasi denganformula. Nilai kebenaran dalam kalkulus proposisi dapat direpresentasikan/disajikan dalam bentuk-bentuk sebagai berikut:

-         Benar (B) atau True (T) dinotasikan dengan Satu (1).

-         Salah (S) atau False (F) dinotasikan dengan Nol (0).

Nilai kebenaran yangdisebutkan diatas bisa digunakan dengan bentuk B/S, T/F, atau 1/0. Tapi untukkeseragaman, dengan alasan akan digunakan juga pada bahasan Aljabar Boolean dantelah terbiasa, maka nilai kebenaran yang digunakan adalah 1/0. Nilai-nilaikebenaran untuk masing-masing formula dapat dilihat pada tabel kebenaran (Truth Table) dibawah ini:

Negasi

Konjungsi, Disjungsi, Implikasi, Bi-Implikasi, Or Exclusive

Bahasan Khusus: Varian Implikasi

Pada (Implikasi), ketika p= 0  apapun nilai dari q akan selalu bernilai benar. Beberapavarian dari formula Implikasi adalah: Contrapositive,Converse, Inverse.

-         Formula  disebut Contrapositivedari formula

-         Formula  disebut Converse dariformula

-         Formula  disebut Inverse dariformula

Contoh:

Buatlah Contrapositive, Converse, Inverse darikalimat berikut: “Jika Fulan tidak belajar, maka ia tidak akan lulus ujian”.

Jawab: Contrapositive : “Jika Fulan lulus, maka ia belajar”.

Converse         : “Jika Fulan tidak lulus ujian, makaia tidak belajar”.

Inverse                        : “Jika Fulan belajar,maka ia akan lulus ujian”.

Implikasi ini memilikiperan sangat penting dalam penalaran. Implikasi  tidak hanya disebutkansebagai kalimat standar “Jika p Maka q” tetapi juga dapat diekspresikan dalamberbagai cara, antara lain:

Jika p, maka q                         (if p, then q)Jika p, q                                   (if p,q)p mengakibatkan q                  (p implies q)q jika p                                    (q if p)p hanya jika q                          (p only if q)p syarat cukup agar q              (p is sufficient for q)q syarat perlu bagi p                (q is necessary for p)q bilamana p                            (q whenever p)

Bahasan Khusus: Tautologi, Kontradiksi, Ekuivalen

Suatu formuladikatakan Tautologi (Tautology)apabila interpretasi dari formula tersebut selalu benar, apapun nilaiatomnya. Formula dikatakan Kontradiksi (Contradiction) apabila interpretasinya selalu salah. Duaformula p dan q dikatakan Ekivalen secara logika (Logically Equivalent) apabila keduanya memiliki nilai kebenaranyang sama.

Contoh:

1.      Buktikan dengan tabel kebenaranuntuk memperlihatkan bahwa interpretasi formula  adalah tautology.

2.      Buktikan dengan tabel kebenaranuntuk memperlihatkan bahwa inerpretasi formula adalah kontradiksi.

3.      Buktikan dengan tabel kebenaran untukmembuktikan bahwa dan adalah ekivalen secara logika.

4.      Buktikan dengan table kebenaranuntuk membuktikan (Øp Ù Øq)

5.      Selidiki nilai kebenaran dari  (p Ù Øq) ® Ø r

Jawab:

1.    

2.      Tabel kebenaran untuk:

3.      Tabel kebenaran untuk:  dan

4.      Tabel kebenaran untuk: (Øp Ù Øq)

5.      Tabel kebenaran untuk (p Ù Øq) ® Ø r

Validitas dan Inkonsistensi

Pada pembahasan kaliini kita ingin mengetahui kapan suatu formula dikatakan valid pada logikaproposional? Pada penjelasan diatas kita telah dibiasakan dengan formula logikayang berasal dari transformasi kalimat deklaratif. Komposisi atau Kombinasibeberapa kalimat deklaratif yang valid akan menghasilkan formula yang validjuga.

Suatu formuladikatakan Valid jika dan hanya jika formula tersebut Tautologi. Dan formuladisebut Invalid jika dan hanya jika tidak valid.

Suatu formula disebut Inkonsistenjika dan hanya jika formula tersebut kontradiksi. Dan formula disebut Konsistenjika dan hanya jika tidak Inkonsisten.

Pernyataan berikut iniadalah implikasi dari definisi diatas:

Formula adalah Valid jika dan hanya jika Negasinya InkonsistenFormula adalah Inkonsisten jika dan hanya jika Negasinya ValidFormula adalah Invalid jika dan hanya jika ada interpretasi yang menyebabkannya salah.Formula adalah Konsisten jika dan hanya jika ada interpretasi yang menyebabkannya benarJika formula adalah Valid, maka formula tersebut Konsisten tetapi tidak sebaliknyaJika formula adalah Inkonsisten, maka formula tersebut Invalid, tetapi tidak untuk sebaliknya.

Contoh:

      Dengan menggunakan tabel kebenarn, kitadapat menyimpulkan bahwa:

1.      Formula adalah inkonsisten, yang juga invalid

2.      Formula adalah valid, yang juga konsisten

3.      Formula adalah invalid, yang juga konsisten

5.5            Bentuk Normal Formula

Seperti yang kita ketahuibahwa suatu logika proposisi dibentuk dari suatu formula dengan kombinasi darioperator . Formula yang hanya menggunakan kombinasi operator   disebut formulabentuk normal.  Ada dua macam Bentuk Normal Formula yaitu:

Bentuk Normal Konjungsi:Formula F dikatakanberbentuk Normal Konjungsi jika dan hanya jika F berbentuk  dimana  dan  himpunan bilanganbulat.

Contoh:

Jika diketahui p, q,dan r. Maka formula adalah berbentuk normal konjungsi dimana , dan , .

Bentuk Normal DisjungsiFormula F dikatakanberbentuk Normal Disjungsi jika dan hanya jika F berbentuk  dimana  dan  himpunan bilanganbulat.

Contoh:

Jika diketahui p, q,dan r. Maka formula adalah berbentuk normal konjungsi dimana , dan , .

Pada saat mengubahbentuk formula menjadi bentuk normal, tabel ekuivalensi logis dapat digunakansebagai alat bantu. Berikut prosedur transformasinya:

Contoh:

Ubahlah formula  kedalam bentuk normal konjungsiJawab:

Maka bentuk normalkonjungsi untuk formula

 adalah

Ubahlah formula kedalam bentuk normal disjungsiJawab:

Maka bentuk normalkonjungsi untuk formula

 adalah

Metode-Metode Inferensi

Metode Inferensiadalah teknik untuk menurunkan kesimpulan berdasarkan hipotesa yang ada, tanpaharus menggunakan tabel kebenaran. Konklusi disimbolkan sebagai ‘’ dibaca ‘jadi’ atau ‘karena itu’. Beberapa metode inferensiuntuk menentukan ke-Valid-an suatu kesimpulan adalah sebagai berikut: (LihatTabel aturan inferensi)

Modus Ponen

Bentuk(implikasi) diasumsikan bernilai benar. Apabila selanjutnya diketahui bahwa anteseden p (hipotesa) juga bernilai benar, agar konklusi bernilai benar, maka q (konklusi) juga harus bernilai benar.

Contoh:

Misalkan implikasi “Jika 20 habis dibagi 2, maka 20 adalah bilangan genap” dan hipotesa “20 habis dibagi 2” keduanya bernilai benar. Maka metode inferensi modus ponen dinyatakan dalam bentuk:

“Jika 20 habis dibagi 2, maka 20 adalah bilangan genap. 20 habis dibagi 2. Karena itu, 20 adalah bilangan genap.”

Bernilai benar dan dapat ditulis juga sebagai:

Contoh lainnya:

Modus Tollen

Bentuk Modus Tollen mirip dengan Modus Ponen, hanya saja Hipotesa kedua dan Konklusi merupakan kontraposisi hipotesa pertama modus ponen, karena suatu implikasi selalu ekuivalen dengan kontraposisi.

Contoh:

Misalkan implikasi “Jika Zeus seorang manusia, maka ia dapat mati” dan hipotesa “Zeus tidak dapat mati” keduanya bernilai benar. Maka metode inferensi modus ponens dinyatakan dalam bentuk:

“Jika Zeus seorang manusia, maka ia dapat mati. Zeus tidak dapat mati. Karena itu, Zeus bukan seorang manusia.”

Bernilai benar dan dapat ditulis juga sebagai:

Disjungtif

dan

Inferensi penambahan Disjungtif didasarkan atas fakta bahwa suatu kalimat dapat digeneralisasikan dengan penghubung ‘’. Alasannya adalah karena penghubung ‘’ bernilai benar jika salah satu komponennya bernilai benar.

Contoh:

Konjungtif

dan

Inferensi penyederhanaan konjungtif merupakan kebalikan dari inferensi Disjungtif. Jika kalimat dihubungkan dengan ‘’, kalimat tersebut dapat diambil salah satunya secara khusus.

Contoh:

Penghubung ‘dan’ dalam kalimat diatas berarti bahwa Taka menguasai bahasa Inggris sekaligus menguasai bahasa Jepang. Secara khusus dapat dikatakan bahwa Taka menguasai bahasa Inggris.

SilogismeDisjugtif

 dan

Silogisme Disjungtif didasari pada fakta kehidupan sehari-hari bahwa apabila dihadapkan satu diantara 2 pilihan (A atau B), sedangkan kita tidak memilih A, maka satu-satunya pilihan yang mungkin adalah B.

Contoh:

SilogismeHipotesis

Silogisme Hipotesis adalah implikasi yang bersifat transitif. Jika implikasi  dan  keduanya bernilai benar, maka implikasi juga bernilai benar.

Contoh:

Konjungsi

Jika ada dua kalimat yang masing-masing bernilai benar maka gabungan kedua kalimat tersebut yang dihubungkan dengan operator ‘’ juga bernilai benar.

Contoh:

Dilema

Dalam kalimat yang dihubungkan dengan dengan penghubung ‘’, masing-masing kalimat dapat mengimplikasikan sesuatu yang sama.

Contoh:

Contoh Metode Inferensi

Contoh berikut iniadalah persoalan mengenai penggunaan metode inferensi berdasarkan fakta-faktayang actual, dimana setiap nilai kebenaran yang dihasilkan suatu fakta akanmenghasilkan nilai kebenaran bagi fakta lainnya:

“Pada suatu hari, Anda hendak pergi kuliah dan baru sadar bahwa andatidak memakai kacamata. Setelah diingat-ingat, ada beberapa fakta yang Andayakini benar yaitu:”

1.      Jika kacamataku ada di meja dapur,aku pasti sudah melihatnya ketika mengambil makanan kecil.

2.      Aku membaca buku pemrograman diruang tamu atau aku membacanya di dapur.

3.      Jika aku membaca buku pemrogramandi ruang tamu, maka pastilah kacamata kuletakkan dimeja tamu.

4.      Aku tidak melihat kacamatakuketika aku mengambil makanan kecil.

5.      Jika aku membaca majalah diranjang, maka kacamataku kuletakkan dimeja samping ranjang.

6.      Jika aku membaca buku pemrogramandi dapur, maka kacamata ada di meja dapur.

Berdasarkanfakta-fakta tersebut, tentukan dimana letak kacamataku?

Jawab:

Pernyataan dalambentuk simbol logika:

§  p : Kacamata ada di meja dapur.

§  q : Aku melihat kacamataku ketika mengambilmakanan kecil.

§  r : Aku membaca buku pemrograman di ruangtamu.

§  s : Aku membaca buku pemrograman di dapur.

§  t : Kacamata kuletakkan di meja tamu.

§  u : Aku membaca buku majalah di ranjang.

§  w : Kacamata kuletakkan di mejasamping ranjang.

Fakta dapat ditulis:

1.    

2.    

3.    

4.    

5.    

6.    

Inferensi yang dapatdilakukan:

    1.   Tolens

2.   Tolens

3.   Silogisme Disj.

4.   Ponens

Kesimpulan:

Kacamata ada di Meja Tamu

Pencarian Heuristik

Pengenalan

Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness). Fungsi heuristik digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan. Jenis-jenis Heuristic Searching:

• Generate and Test

• Metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal.
• 
  
• Algoritma :
1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu tititk tertentu atau lintasan tertentu dari keadaan awal).
2. Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node terebut atau node akhir dari suatu lintasan yang  dipilih dengan kumpulan tujuan yang diharapkan.
3. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama.

• HillClimbing

• Metode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnyayang mungkin.
• 
  
• Algoritma:
1. Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
a) Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang : Cari operator yang belum digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
b) Evaluasi keadaan baru tersebut : – Jika keadaan baru merupakan tujuan, keluar – Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang. – Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.

• Best First Search

• Metode ini merupakan kombinasi dari metode depthfirst search dan breadth-first search. Pada metode best-first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node pada level yang lebih tinggi ternyata memiliki nilai heuristic yang lebih buruk.
• Fungsi Heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal state, yang dinyatakan dengan : 
f’(n) = g(n) + h’(n)
• f’ = Fungsi evaluasi
• g = cost dari initial state ke current state
• h’ = prakiraan cost dari current state ke goal state

• Alpha  Beta  Prunning,Means-End-Anlysis,Constraint Satisfaction, Simulated Anealing, dll

SMA * Search (Simplified Memory-Bounded) A*

Simplified Memory-Bounded A* atau biasa disebut SMA* merupakan algoritma pencarian yang dapat menggunakan semua memori yang tersedia untuk melakukan pencarian. Menggunakan lebih banyak memori hanya dapat meningkatkan efisiensi pencarian, salah satunya bisa selalu mengabaikan ruang tambahan, tetapi biasanya lebih baik untuk mengingat node daripada harus membuatnya kembali bila diperlukan.

SMA* memiliki gambaran berikut :

• Dia akan memanfaatkan memori apa pun yang tersedia untuk nya.
• Dia menghindari pernyataan berulang sejauh memori memungkinkan.
• Dia selesai jika memori yang tersedia cukup untuk menyimpan jalur solusi dangkal.
• Dia optimal jika tersedia cukup memori untuk menyimpan jalur solusi dangkal optimal. Jika tidak, dia mengembalikan solusi terbaik yang dapat dicapai, dengan memori yang tersedia.

 Algoritma SMA* ini merupakan sebuah algoritma yang dikembangkan dari algoritma A* (A Star). Algoritma A* sendiri adalah variasi dari algoritma Branch and Bound. Jadi secara tidak langsung, algoritma SMA* itu sendiri merupakan salah satu variasi pengembangan dari algoritma Branch and Bound. Menggunakan algoritma SMA* berarti kita memperhitungkan biaya sebenarnya ditambah dengan biaya perkiraan. Biaya sebenarnya dinotasikan dengan g(n). Sedangkan biaya perkiraan dinotasikan dengan h(n). Jadi kita memperhitungkan g(n) + h(n).

Algoritma A*

Algoritma A* adalah algoritma pencarian yang merupakan pengembangan dari kelas algoritma Greedy. Seperti halnya pada Greedy, untuk menemukan solusi, A* juga dilakukan oleh fungsi heuristik, yang menentukan urutan titik mana yang akan dikunjungi terlebih dahulu. Heuristik merupakan penilai yang memberi harga pada tiap verteks yang memandu A* mendapatkan solusi yang diinginkan. Algoritma A* menyelesaikan masalah yang menggunakan graph

untuk perluasan ruang statusnya. 

Dengan kata lain digunakan untuk menyelesaikan permasalah yang bisa direpresentasikan dengan graph. Algoritma A* adalah sebuah algoritma yang telah dikembangkan. Dengan menerapkan fungsi heuristik, algoritma ini membuang langkah-langkah yang tidak perlu dengan pertimbangan bahwa langkah-langkah yang dibuang sudah pasti merupakan langkah yang tidak akan mencapai solusi yang diinginkan. Secara informal, algoritma bekerja dalam banyak cara yang sama seperti pada algoritma Dijkstra. Daripada selalu mempertimbangkan verteks terbuka dengan nilai terendah, lebih baik memilih verteks yang paling mungkin untuk mengarahkan  pencarian ke arah tujuan dengan nilai terkecil. Semuanya dikendalikan oleh sebuah fungsi heuristik. Jika fungsi tersebut akurat, maka algoritma akan efisien dan rute terpendek akan segera ditemukan jika memang ada.

Fungsi Heuristik

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

Simulated annealing

Simulated annealing (SA) adalah salah satu 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. Publikasi tentang pendekatan ini pertama kali dilakukan oleh S. Kirkpatrick, C. D. Gelatt dan M. P. Vecchi, diaplikasikan pada desain optimal hardware komputer, dan juga pada salah satu masalah klasik ilmu komputer yaitu Traveling Salesman Problem.

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.

Simulated Annealing berjalan berdasarkan analogi dengan proses annealing yang telah dijelaskan di atas. Pada awal proses SA, dipilih suatu solusi awal, yang merepresentasikan kondisi materi sebelum proses dimulai. Gerakan bebas dari atom-atom pada materi, direpresentasikan dalam bentuk modifikasi terhadap solusi awal/solusi sementara. Pada awal proses SA, saat parameter suhu (T) diatur tinggi, solusi sementara yang sudah ada diperbolehkan untuk mengalami modifikasi secara bebas.

Kebebasan ini secara relatif diukur berdasarkan nilai fungsi tertentu yang mengevaluasi seberapa optimal solusi sementara yang telah diperoleh. Bila nilai fungsi evaluasi hasil modifikasi ini membaik (dalam masalah optimisasi yang berusaha mencari minimum berarti nilainya lebih kecil/downhill) solusi hasil modifikasi ini akan digunakan sebagai solusi selanjutnya. Bila nilai fungsi evaluasi hasil modifikasi ini memburuk, pada saat temperatur annealing masih tinggi, solusi yang lebih buruk (uphill) ini masih mungkin diterima, sedangkan pada saat temperatur annealing sudah relatif rendah, solusi hasil modifikasi yang lebih buruk ini mungkin tidak dapat diterima. Dalam tahapan selanjutnya saat temperatur sedikit demi sedikit dikurangi, maka kemungkinan untuk menerima langkah modifikasi yang tidak memperbaiki nilai fungsi evaluasi semakin berkurang. Sehingga kebebasan untuk memodifikasi solusi semakin menyempit, sampai akhirnya diharapkan dapat diperoleh solusi yang mendekati solusi optimal. Pada temperatur rendah ini, SA biasanya menggunakan konsep Hill-Climbing.

Genetic Algorithm

Genetic Algorithm(atau 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.

GA diimplementasikan sebagai proses simulasi yang dijabarkan sebagai berikut: Populasi dari representasi abstrak (disebut kromosom, genotip, atau genom) dari candidate solution (disebut individual, atau fenotip) dari optimasi yang berevolusi ke solusi yang lebih baik. Biasanya solusi direpresentasikan ke dalam string biner. Evolusi dimulai dari populasi dari individu yang dihasulkan secara random dan terjadi dalam generasi. Di setiap generasi, fitness dari setiap individu dalam populasi dievaluasi, beberapa individu dipilih secara stokastik(berdasarkan fitness) dan dimodifikasi(crossover dan kemungkinan mutasi) untuk membentuk populasi baru. Populasi baru lalu dimanfaatkan untuk iterasi selanjutnya. Secara umum, algoritma selesai jika telah menghasilkan generasi maksimum atau hasil dalam populasi dirasa memuaskan (berdasarkan berbagai parameter).

Dalam GA biasanya ada 2 hal yang harus didefinisikan:

1. Representasi genetis dari domain solusi
2. Fungsi fitness untuk mengevaluasi solusi domain.

Representasi standar dari solusi adalah array of bits, karena memudahkan operasi crossover. Fungsi fitness didefinisikan dari representasi genetis dan kualitas dari representasi solusi. Setelah keduanya didefinisikan, GA berlanjut ke inisialisasi populasi dari solusi secara acak, lalu berkembang lewat perulangan aplikasi mutasi, crossover dan seleksi.

Inisialisasi

Awalnya, beberapa solusi individual dihasilkan secara acak untuk membentuk populasi awal yang ukurannya tergantung sifat dari masalah.

Seleksi

Dalam setiap generasi baru, proporsi dari populasi yang ada dipilih untuk menghasilkan generasi selanjutnya. Solusi individual dipilih lewat proses fitness, dimana solusi yang lebih baik (diukur dari fungsi fitness) lebih mungkin dipilih. Metode seleksi yang umum dipakai adalah roulette wheel dan tournament.

Reproduksi

Langkah selanjutnya adalah menghasilkan generasi selanjutnya dari populasi solusi dari hasil seleksi lewat operasi genetik crossover (atau rekombinasi) dan/atau mutasi

Terminasi

Proses ini diulang sampai tercapai kondisi akhir. Kondisi akhir yang umum antara lain:

• Solusi yang ditemukan memenuhi kriteria minimum
• Jumlah generasi tertentu telah tercapai
• Telah mencapai waktu komputasi tertentu
• Tidak dapat dihasilkan hasil yang lebih baik
• Inspeksi manual
• Kombinasi dari kondisi di atas.

Pseudo-code

1. Pilih populasi awal

2. Evaluasi fitness dari tiap individu dalam populasi

3. Iterasi:

• Pilih individu terbaik untuk reproduksi
• Hasilkan generasi baru lewat crossover dan mutasi dan menghasilkan anak
• Evaluasi fitness dari setiap individu anak
• Ganti bagian populasi terburuk dengan anak

4. Sampai kondisi akhir tercapai