Pengetahuan dan Penalaran Agen Logika (Materi 4)

 1.1. PENGENALAN LOGIC AGENT

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

1.2. PENGETAHUAN BERBASIS AGEN

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.

1.3. LOGIKA PROPORSI / LOGIKA SEDERHANA

a.     SINTAKS

Sintaks merupakan kumpulan aturan yang mendefinisikan suatu bentuk bahasa. Sintaks mendefinisikan bagaimana suatu kalimat dibentuk sebagai barisan/urutan dari pemilihan suatu kata dasar. Kata bukan merupakan sesuatu yang mendasar. Kata dikonstruksikan dengan karakter-karakter alfabet. Dengan menggunakan aturan ini maka suatu kalimat dapat dikatakan legal atau tidak legal. Sebagai contoh, dalam keyword bahasa C (seperti while, do,if, dan else), identifier, angka, operator, dan seterusnya, merupakan kata dalam suatu bahasa.Sintaks dalam bahasa C mengatur cara mengombinasikan kata-kata tersebut ke dalam suatu statement dengan bentuk yang benar sehingga dapat disusun suatu program yang dapat berjalan dengan benar. Sintaks tidak mengerti apapun tentang isi atau arti dari suatu kalimat, aturan semantik yang bisa mengartikannya.

Sintaks dari bahasa pemrograman didefinisikan dengan dua kumpulan aturan, yaitu aturan lexical dan aturan syntactic. Aturan leksikal menspesifikasikan kumpulan karakter yang terdapat dalam alfabet dari bahasa dan cara supaya karakter-karakter tersebut dikombinasikan ke dalam kata-kata yang valid dan dapat diterima. Sebagai contoh adalah bahasa Pascal yang tidak memperhatikan huruf besar dan huruf kecil, sedangkan bahasa C dan Ada memperhatikan dan membedakan hal tersebut.

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 :

§  Himpunan karakter

Himpunan karakter yang sering dijumpai dan digunakan adalah himpunan karakter ASCII, yang berisi dasar karakter-karakter angka dan huruf. Karakter ASCII secara umum dapat langsung digunakan pada kebanyakan perangkat I/O, namun ada bahasa pemrograman yang tidak menggunakan himpunan karakter ASCII, contohnya bahasa APL. APL menggunakan karakter yang tidak dapat digunakan secara langsung pada kebanyakan pernagkat I/O, tidak seperti bahasa C yang menggunakan himpunan karakter ASCII.

§  Identifier

Sintaks dasar dari identifier yang sering digunakan adalah string dari huruf dan angka yang dimulai dengan huruf. Namun, banyak juga variasi dari bahasa pemrograman yang menggunakan suatu identifier dengan tanda “.” Atau “-“. Hal ini akan berpengaruh pada kemudahan dalam pembacaan program.

§  Simbol untuk operator

Kebanyakan bahasa pemrograman menggunakan karakter “+” dan “-“ untuk merepresentasikan dua buah operasi dasar aritmetika, dan menggunaka kombinasi serta memanfaatkan karakter-karakter spesial untuk suatu operator, atau menggunakan string untuk operator seperti pada FORTRAN dengan .EQ. untuk membandingkan kesamaan dan ** untuk perpangkatan.

§  Keyword dan reserved word

Keyword merupakan merupakan suatu identifier yang digunakan sebagai bagian tetap dari sintaks suatu statement, misalnya IF untuk memulai suatu statement kondisi atau DO untuk memulai suatu perulangan dalam bahasa FORTRAN. Keyword merupakan reserved word jika tidak digunakan sebagai identifier yang dipilih oleh programmer. Misalnya dalam bahasa FORTRAN, identifier IF dan DO dapat dipilih sebagai nama variabel oleh programmer sehingga suatu statemen yang dimulai dengan IF belum tentu merupakan

statement kondisi.

§  Noise word

Merupakan kata pilihan yang disisipkan dalam statemen untuk meningkatkan readibility. Sebagai contoh adalah statemen GO TO label. GO merupakan keyword yang harus ada, sedangkan TO merupakan optional yang akan meningkatkan readibility.

§  Komentar

Penambahan komentar dalam suatu program merupakan hal penting dari dokumentasi suatu program. Bahasa pemrograman mengijinkan komentar dalam beberapa bentuk.

· Baris komentar yang terpisah di dalam program seperti pada FORTRAN.

· Penggunaan karakter khusus yang tidak memedulikan baris seperti /* dan */ di bahasa C.

· Dimulai dari sembarang tempat disuatu baris dengan diawali suatu karakter khusus, seperti

“-“ di Ada, “//” di C++ atau “!” di FORTRAN.

§  Blank

Aturan penggunaan spasi pada bahasa pemrograman sangat beragam. Sebagai contoh adalah bahasa C. Biasanya spasi diabaikan, kecuali jika ada simbol “=+” yang merupakan operator tunggal. Bila dipisahkan dengan spasi maka akan terjadi kesalahan sintaks.

§  Delimiter dan tanda kurung

Delimiter merupakan elemen syntactic yang digunakan untuk menandai suatu awalan atau akhiran dari suatu syntactic unit seperti statemen atau ekspresi. Tanda kurung biasanya berpasangan dengan delimiter, misalnya kurung kurawal atau pasangan kata begin … end. Delimiter berguna untuk meningkatkan readability suatu program dan juga dapat menghilangkan ambiguitas suatu statemen karena dapat digunakan secara eksplisit untuk memisahkan statemen-statemen yang mirip.

§  Ekspresi

Merupakan suatu fungsi yang mengakses data dalam suatu program dan mengembalikan suatu nilai. Ekspresi merupakan dasar dari blok syntactic dari statemen yang dibangun.

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

Semantic suatu bahasa pemrograman mempunyai banyak potensial / keunggulan, beberapa diantaranya adalah :

§  Standarisasi bahasa pemrograman.

Banyak usaha yang dilakukan untuk menstandarisasi bahasa pemrograman seperti FORTRAN, COBOL, dan PL/1, untuk lebih memudahkan programmer menggunakannya.

§  Referensi untuk user.

Programmer membutuhkan suatu dokumentasi yang pasti supaya user dapat mengoperasikan program yang dibuat dengan baik.

§  Pembuktian dari program yang benar.

Secara matematis, program tidak mungkin bekerja dan berjalan jika tidak ada semantic.

§  Referensi untuk implementor.

Semantic akan mencegah suatu gaya bahasa yang tidak kompetibel yang diwujudkan dalam suatu implementasi berbeda walaupun dengan bahasa yang sama.

§  Implementasi otomatis.

Suatu tool/alat dapat secara otomatis membuatu translasi bahasa yang melebihi parsing. Hal ini dapat dilakukan jika semantic sudah dirumuskan. f. Pemahaman yang lebih baik dari desain bahasa. Jika suatu rumusan semantic sulit untuk di deskripsikan secara formal maka rumusan semantic tersebut juga akan sulit digunakan oleh programmer.

Teknik semantic :

§  Operational semantic

Pendekatan ini mendefinisikan suatu mesin buatan (abstrak) dengan instruksi-instruksi primitive, tidak perlu realistic, tetapi cukup sederhana supaya tidak muncul kesalahpahaman. Deskripsi semantic dari bahasa pemrograman menentukan suatu translasi ke kode.

§  Detonational semantic.

Pada pendekatan ini, diberikan suatu fungsi yang memetakan program-program computer yang di tunjuk ke dalam bentuk nilai-nilai abstrak secara matematika (angka, nilai kebenaran, fungsi matematika, dsb).

§  Axiomatic semantic.

Pada pendekatan ini di definisikan suatu tindakan program yang di bangun dengan property logika yang menyimpan status computer sebelum dan sesudah dieksekusi.

§  Algebraic semantic.

Pada pendekatan ini dipertimbangkan suatu objek komputasi yang menjadi syarat-syarat dalam aljabar multi stored. Program mengimplementasikan fungsi yang dapat di wujudkan dengan suatu persamaan di antara syarat-syarat tersebut.

§  Structured operational semantic atau natural semantic.

Seperti dalam pengambilan keputusan secara alamiah dengan logika, program di beri suatu arti dari aturan yang diturunkan yang menggambarkan penilaian gagasan suatu bahasa.

Proses analisa sintak dan analisa semantic merupakan 2 proses yang sangat erat kaitannya dan sulit untuk dipisahkan.

Contoh :

A:= (A+B) * (C+D)

Parser hanya akan mengenali symbol-simbol „:=”, “+”, “*”, parser tidak mengetahui makna dari symbol-simbol tersebut. Untuk mengenali makna dari symbol-simbol tersebut maka compiler memanggil routin semantics.

Untuk mengetahui makna, maka routin ini akan memeriksa :

• Apakah variable yang ada telah didefinisikan sebelumnya.

• Apakah variable-variabel terserbut tipenya sama.

• Apakah operand yang akan di operasikan terserbut ada nilainya, dst.

• Menggunakan table symbol.

• Pemeriksaan bisa dilakukan pada table identifier, table display, dan table block.

c.      INFERENSI

Metode inferensi adalah suatu teknik/metode untuk menurunkan kesimpulan berdasarkan hipotesa yang diberikan, tanpa harus menggunakan table kebenaran. Beberapa metode inferensi untuk menentukan validitas adalah sebagai berikut :

§  Modus Ponens

Pada suatu implikasi “jika p maka q” yang diasumsikan bernilai benar, dan apabila juga diketahui bahwa nilai dari anteseden (p) bernilai benar, maka nilai q juga harus benar.

p —> q

p

q

Contoh :

Jika suatu bilangan habis dibagi 2 maka bilangan tersebut adalah bilangan genap.

Suatu bilangan habis dibagi 2.

Bilangan tersebut adalah bilangan genap.

§  Modus Tollens

Suatu implikasi “jika p maka q” akan selalu ekuivalen dengan kontraposisinya, yaitu “jika bukan q maka bukan p”. dengan demikian, hipotesa kedua dan kesimpulan merupakan kontraposisi hipotesa pertama pada modus ponens.

p –> q

~q

~p

Contoh :

Jika hasil jual lebih dari hasil beli maka penjual itu untung.

Penjual itu tidak untung.

Hasil jual tidak lebih dari pembelian.

§  Silogisme

Prinsip Silogisme adalah sifat transitif dari implikasi. Artinya, jika suatu implikasi p à q dan q à r keduanya bernilai benar maka implikasi p à q pasti bernilai benar.

p –> q

q –> r

p –> r

Contoh :

Jika ia belajar dengan baik maka ia akan pandai.

Jika ia pandai maka ia akan lulus dalam ujian.

Jika ia belajar dengan baik ia akan lulus dalam ujian.

d.     VALIDITAS

Menurut Azwar (1986) validitas berasal dari kata validity yang mempunyai arti sejauh mana ketepatan dan kecermatan suatu alat ukur dalam melakukan fungsi ukurnya. Menurut Arikunto (1999) validitas adalah suatu ukuran yang menunjukkan tingkat kesahihan suatu tes. Menurut Nursalam (2003) validitas adalah suatu ukuran yang menunjukkan tingkat kevalidan atau kesahihan suatu instrumen. Berdasarkan beberapa pendapat tentang pengertian validitas di atas, maka dapat diambil kesimpulan bahwa validitas adalah suatu standar ukuran yang menunjukkan ketepatan dan kesahihan suatu instrumen.

Suatu Kalimat logika f bersifat valid jika untuk setiap interpretasinya I for f, f bernilai true.

Contoh :

§  (f and g) if and only if (g and f)

§  f or not f

§  [p and (if r then s)] if only if [(if  r then s ) and p]

§  [p or q) or not (p or q)

§  (if p then not q) if and only if not (p and q)

e.      SATISFIABILITY

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.

Contoh:

Dengan menggunakan table kebenaran, buktikan bahwa : (p ˄ (pq)) adalah satisfiable.

1.4. POLA PENALARAN PADA LOGIKA PROPOSISI

a.     RESOLUSI

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.

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 :

§  Konversikan semua proposisi F ke bentuk CNF.

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

§  Kerjakan hingga terjadi kontradiksi atau proses tidak mengalami kemajuan :

§  Seleksi 2 klausa sebagai klausa parent.

§  Bandingkan (resolve) secara bersama-sama. Klausa hasil resolve tersebut dinamakan resolvent. Jika ada pasangan literal L dan ￢L, eliminir dari resolvent.

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

b.     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. Proses penalaran forward chaining terlihat pada gambar dibawah :

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

Contoh :

Seperti pada contoh forward chining, terdapat 10 aturan yang sama pada basis pengetahuan dan fakta awal yang diberikan hanya A dan E. ingin membuktikan apakah K bernilai benar. Proses penalaran backward chaining terlihat pada gambar berikut :

1.5. INFERENSI PROPOSI YANG EFEKTIF

§  ALGORITMA BACKTRACKING

Algoritma Backtracking mempunyai prinsip dasar yang sama seperti brute-force yaitu mencoba segalakemungkinan solusi. Perbedaan utamanya adalah pada ide dasarnya, semua solusi dibuat dalam bentuk  pohon solusi (pohon ini tentunya berbentuk abstrak) dan algoritma akan menelusuri pohon tersebu secara DFS (depth field search) sampai ditemukansolusi yang layak. Nama backtrack didapatkan dari sifat algoritma iniyang memanfaat karakteristik himpunan solusinya yang sudah disusun menjadi suatu pohon solusi.Agar lebih jelas bisa dilihat pada pohon solusi berikut:

Misalkan pohon diatas menggambarkan solusi darisuatu permasalahan. Untuk mecapai solusi (5), maka jalan yang ditempuh adalah (1,2,5), demikian jugadengan solusi-solusi yang lain. Algoritma backtrack akan memeriksa mulai dari solusi yang pertamayaitu solusi (5). Jika ternyata solusi (5) bukan solusiyang layak maka algoritma akan melanjutkan ke solusi (6). Jalan yang ditempuh ke solusi (5) adalah (1,2,5) dan jalan untuk ke solusi (6) adalah (1,2,6). Kedua solusi ini memiliki jalan awal yang sama yaitu (1,2). Jadi daripada memeriksa ulang dari (1) kemudian (2) maka hasil (1,2) disimpan dan langsung memeriksa solusi (6). Pada pohon yang lebih rumit, cara ini akan jauh lebih efisien daripada brute-force. Pada beberapa kasus, hasil perhitungan sebelumnya harus disimpan, sedangkan pada kasus yang lainnya tidak perlu.

§  KEGUNAAN ALGORITMA BACKTRACKING

Penggunaan terbesar backtrack adalah untuk membuat AI pada board games. Dengan algoritma ini program dapat menghasilkan pohon sampaidengan kedalaman tertentu dari current status dan memilih solusi yang akan membuat langkah-langkah yang dapat dilakukan oleh user akan menghasilkan pohon solusi baru dengan jumlah pilihan langkahterbanyak. Cara ini dipakai sebagai AI yangdigunakan untuk dynamic problem solving. Beberapa kegunaan yang cukup terkenal darialgoritma backtrack dari suatu masalah “statik”adalah untuk memecahkan masalah N Queenproblem dan mazesolver.

N-Queen problem adalah bagaimana carameletakkan bidak Queen catur sebanyak N buah pada papan catur atau pada papan ukuran NxN sedemikian rupa sehingga tidak ada satu bidakpun yang dapat memangsa bidak lainnya dengan 1gerakan [1]. Meskipun mungkin terdapat lebih darisatu solusi untuk masalah ini, tetapi pencarian semuasolusi biasanya tidak terlalu diperlukan, tetapi untuk beberapa kasus tertentu diperlukan pencarian semua solusi sehingga didapatkan solusi yang optimal.

Maze solver adalah bagaimana cara mencari jalankeluar dari suatu maze (labirin) yang diberikan. Pada maze yang sederhana dimana field yang dibentuk dapat direpresentasikan dalam bentuk biner dan pada setiap petak maksimal terdapat 4 kemungkinan: atas, kanan, bawah dan kiri. Untuk masalah ini biasanya solusi pertama yang ditemukan bukanlah solusi yang paling optimal sehingga untuk mendapatkan hasil yang optimal dibutuhkan pencarian terhadap seluruh kemungkinan solusi. Hal ini disebabkan oleh urutan pencarian yang telah ditetapkan dalam program (apakah menyelidiki kemungkinan ke arah atasdahulu atau ke arah lainnya dahulu).

§  IMPLEMENTASI ALGORITMA BACKTRACKING

Algoritma backtrack dapat diimplementasikan dengan mudah pada bahasa-bahasa pemograman yang telah mensupport pemograman rekursif. Bahasa pemograman yang nyaman digunakan adalah Pascal atau Java. Bahasa Pascal dipilih karena bisa diprogram secara rekursif dan mendukung penggunaan pointer. Sedangkan bahasa Java meskipun lebih rumit tetapi dapat bekerja secara rekursif dan sangat mudah dalam membuat dynamic array.

1.6. AGEN BERBASIS LOGIKA PROPOSISI

§  LOGICAL AGENTS

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.

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

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

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

§  LOGIKA PROPOSISI

Logika Proposisi 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.

Contoh:

1 Tanda “^”     artinya “AND”

2 Tanda “v”    artinya “OR”

3. Tanda “   “ artinya “IF THEN”

4. Tanda “    “ artinya “IF and only IF then”

5. Tanda “=”   artinya “assignment”

6. Tanda “   “ artinya “NOT (negation)”

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.

PPT:

Sumber :

https://bellavira.blogspot.com/2017/10/agen-logika.html

Fatichah, Chastine. 2012. Logical Agents. Surabaya.

Astuti,Waniwatining dan Rizani Teguh. 2016. Logika Informatika. Palembang.

Pencarian Berbentuk /heuristik search dan Eksplorasi (MATERI 3)

1. Strategi pencarian berbentuk

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 node. 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 (A-Star Search)

Bentuk dari Best First Search yang paling dikenal adalah algorima pencarian A(Dibaca dengan A-Star). Tidak jauh 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)

• Heuristic Best First Search

Fungsi heuristic h(n) merupakan estimasi cost dari n ke simpul tujuan. Sangat penting untuk memilih fungsi heuristic yang baik. Misalkan h(n) merupakan cost sebenarnya dari simpul n ke simpul tujuan, maka pada algoritma A terdapat beberapa kemungkinan yang terjadi pada pemilihan fungsi heuristic yang digunakan, yaitu (Amit Gaming) :

• Jika h(n) = 0, sehingga hanya g(n) yang terlibat maka A* akan bekerja seperti halnya algoritma Dijkstra.
• Jika h(n) < h*(n), maka A* akan mengembangkan titik dengan nilai paing rendah dan algoritma A* menjamin ditemukannya lintasan terpendek. Nilai h(n) terendah akan membuat algoritma mengembangkan lebih banyak simpul. Jika h(n) < h*(n), maka h(n) dikatakan heuristicyang admissible.
• Jika h(n) = h*(n), maka A* akan mengikuti lintasan terbaik dan tidak akan mengembangkan titik-titik yang lain sehingga akan berjalan cepat. Tetapi hal ini tidak akan terjadi pada semua kasus. Informasi yang baik akan mempercepat kinerja A*.
• Jika h(n) > h*(n), maka A* tidak menjamin pencarian rute terpendek, tetapi berjalan dengan cepat.

Jika h(n) terlalu tinggi relative dengan g(n) sehingga hanya h(n) yang bekerja maka A* berubah jadi Greedy Best First Search.

2. 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 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 :

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.

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

Link PPT:

https://drive.google.com/open?id=1GMj05p3t6NkHAJxjkVWvfOp7QbB6k6rk

Sumber : 

https://adiazep.wordpress.com/2017/11/12/pencarian-berbentuk-heuristik-search-dan-eksplorasi/

https://shabri-prayogi.blogspot.com/2013/08/teknik-pencarian-heuristik-heuristic.html

Penyelesaian Masalah melalui proses Pencarian / Searching

AGEN PEMECAH PERMASALAHAN

Dalam menentukan teknik penyelesaian terbaik dalam AI memang tidak mudah, untuk itu ada beberapa teknik penyelesaian masalah yang perlu kita pahami, antara lain:

1.1 Searching

Teknik penyelesaian masalah yang mempresentasikan masalah kedalam ruang keadaan (state) dan secara sistematis melakukan pembangkitan dan pengujian state-state dari initial state sampai ditemukan suatu goal state.

1.2 Reasoning

Teknik penyelesaian masalah yang mempresentasikan masalah kedalam logic (Mathematical Tools yang digunakan untuk merepresentasikan dan memanipulasi fakta dan aturan)

1.3 Planning

Memecah masalah dalam sub-sub masalah yang lebih kecil, menyelesaikan sub-sub masalah satu demi satu, kemudian menggabungkan solusi-solusi dari sub masalah tersebut menjadi sebuah solusi lengkap.

1.4 Learning

Program komputer yang secara otomatis sanggup belajar dan meningkatkan performancenya  melalui pengalaman

PENCARIAN SEBAGAI SOLUSI PEMECAHAN MASALAH

Searching adalah mekanisme pemecahan masalah yang paling umum di dalam kecerdasan buatan. Di dalam permasalahan-permasalahan kecerdasan buatan, urutan langkah-langkah yang dibutuhkan untuk memperoleh solusi merupakan suatu isu yang penting untuk diformulasikan. Hal ini harus dilakukan dengan mengidentifikasikan proses try and error secara sistematis pada eksplorasi setiap alternatif jalur yang ada.

    STRATEGI PENCARIAN YANG TIDAK BERBENTUK

1.    Depth-First Search

Algoritma Depth First Search (DFS) adalah salah satu algoritma pencarian solusi yang digunakan di dalam kecerdasan buatan. Algoritma ini termasuk salah satu jenis uninformed algorithm yaitu algoritma yang melakukan pencarian dalam urutan tertentu tetapi tidak memiliki informasi apa-apa sebagai dasar pencarian kecuali hanya mengikuti pola yang diberikan.

Di dalam DFS, pencarian dilakukan pada suatu struktur pohon yaitu kumpulan semua kondisi yang mungkin yang diimplementasikan dalam sebuah struktur pohon. Paling atas adalah akar (root) yang berisi kondisi awal pencarian (initial state) dan di bawahnya adalah kondisi-kondisi berikutnya sampai kepada kondisi tujuan (goal state).

Pada prinsipnya, DFS ini menggunakan tumpukan untuk menyimpan seluruh state yang ditemukan atau bisa dikatakan bahwa DFS menggunakan metode LIFO (Last In First Out).

2.    Breadth-First Search

BFS adalah sebuah metode pencarian yang bertujuan untuk memperluas dan memeriksa semua node dari sebuah graf atau kombinasi dari urutan dengan menggunakan semua solusi secara sistematis. dengan kata lain, bfs mencari ke seluruh graf atau urutan secara mendalam tanpa mempertimbangkan tujuannya (goal) sampai tujuan itu tercapai. BFS tidak menggunakan algoritma heuristis.

3.    Uniform Cost Search

Pencarian dengan Breadth First Search 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).

4.    Depth Limited Search

Pencarian menggunakan DFS akan berlanjut terus sampai kedalaman paling terakhir dari tree. Permasalahan yang muncul pada DFS adalah ketika proses pencarian tersebut menemui infinite state space. Hal ini bisa diatasi dengan menginisiasikan batas depth pada level tertentu semenjak awal pencarian. Sehingga node pada level depth tersebut akan diperlakukan seolah-olah mereka tidak memiliki successor.

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

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

Link PPT : https://drive.google.com/open?id=1X0bRdCXQyRIIm-rfYAS2DCMlRIOZyb4U

Sumber :http://furqaanm.blogspot.com/2017/09/penyelesaian-masalah-melalui-proses.html

              http://cakweone.blogspot.com/2017/09/agen-pemecah-permasalahan.html

PENGENALAN AI / KECERDASAN BUATAN (Materi 1)

A. PENGERTIAN KECERDASAN BUATAN

Kecerdasan Buatan atau kecerdasan yang ditambahkan kepada suatu sistem yang bisa diatur dalam konteks ilmiah atau Intelegensi Artifisial (bahasa Inggris: Artificial Intelligence atau hanya disingkat AI) didefinisikan sebagai kecerdasan entitas ilmiah. Sistem seperti ini umumnya dianggap komputer. Kecerdasan diciptakan dan dimasukkan ke dalam suatu mesin (komputer) agar dapat melakukan pekerjaan seperti yang dapat dilakukan manusia. Beberapa macam bidang yang menggunakan kecerdasan buatan antara lain sistem pakar, permainan komputer (games), logika fuzzy, jaringan saraf tiruan dan robotika.

Banyak hal yang kelihatannya sulit untuk kecerdasan manusia, tetapi untuk Informatika relatif tidak bermasalah. Seperti contoh: mentransformasikan persamaan, menyelesaikan persamaan integral, membuat permainan catur atau Backgammon.

B. BIDANG ILMU YANG MENJADI DASAR AI

Penerapan AI meliputi berbagai bidang seperti ditunjukkan pada bagian cabang dari pohon AI pada Gambar 1, sedangkan induk keilmuan AI dapat dilihat pada akar dari pohon AI yang antara lain meliputi: Bahasa/linguistik, Psikologi, Filsafat, Matematik, Teknik Elektro, Ilmu Komputer, dan Ilmu Manajemen.

C. SEJARAH KECERDASAN BUATAN

Pada awal abad 17, René Descartes mengemukakan bahwa tubuh hewan bukanlah apa-apa melainkan hanya mesin-mesin yang rumit. Blaise Pascal menciptakan mesin penghitung digital mekanis pertama pada 1642. Pada 19, Charles Babbage dan Ada Lovelacebekerja pada mesin penghitung mekanis yang dapat diprogram.

Bertrand Russell dan Alfred North Whitehead menerbitkan Principia Mathematica, yang merombak logika formal. Warren McCulloch dan Walter Pitts menerbitkan "Kalkulus Logis Gagasan yang tetap ada dalam Aktivitas " pada 1943 yang meletakkan fondasi untuk jaringan saraf.

Tahun 1950-an adalah periode usaha aktif dalam AI. Program AI pertama yang bekerja ditulis pada 1951 untuk menjalankan mesin Ferranti Mark I di University of Manchester (UK): sebuah program permainan naskah yang ditulis oleh Christopher Strachey dan program permainan catur yang ditulis oleh Dietrich Prinz. John McCarthy membuat istilah "kecerdasan buatan " pada konferensi pertama yang disediakan untuk pokok persoalan ini, pada 1956. Dia juga menemukan bahasa pemrograman Lisp. Alan Turing memperkenalkan "Turing test" sebagai sebuah cara untuk mengoperasionalkan test perilaku cerdas. Joseph Weizenbaum membangun ELIZA, sebuah chatterbot yang menerapkan psikoterapi Rogerian.

Selama tahun 1960-an dan 1970-an, Joel Moses mendemonstrasikan kekuatan pertimbangan simbolis untuk mengintegrasikan masalah di dalam program Macsyma, program berbasis pengetahuan yang sukses pertama kali dalam bidang matematika. Marvin Minsky dan Seymour Papert menerbitkan Perceptrons, yang mendemostrasikan batas jaringan saraf sederhana dan Alain Colmerauer mengembangkan bahasa komputer Prolog. Ted Shortliffe mendemonstrasikan kekuatan sistem berbasis aturan untuk representasi pengetahuan dan inferensi dalam diagnosa dan terapi medis yang kadangkala disebut sebagai sistem pakar pertama. Hans Moravec mengembangkan kendaraan terkendali komputer pertama untuk mengatasi jalan berintang yang kusut secara mandiri.

Pada tahun 1980-an, jaringan saraf digunakan secara meluas dengan algoritme perambatan balik, pertama kali diterangkan oleh Paul John Werbos pada 1974. Pada tahun 1982, para ahli fisika seperti Hopfield menggunakan teknik-teknik statistika untuk menganalisis sifat-sifat penyimpanan dan optimasi pada jaringan saraf. Para ahli psikologi, David Rumelhart dan Geoff Hinton, melanjutkan penelitian mengenai model jaringan saraf pada memori. Pada tahun 1985-an sedikitnya empat kelompok riset menemukan kembali algoritme pembelajaran propagansi balik (Back-Propagation learning). Algoritme ini berhasil diimplementasikan ke dalam ilmu komputer dan psikologi. Tahun 1990-an ditandai perolehan besar dalam berbagai bidang AI dan demonstrasi berbagai macam aplikasi. Lebih khusus Deep Blue, sebuah komputer permainan catur, mengalahkan Garry Kasparov dalam sebuah pertandingan 6 game yang terkenal pada tahun 1997. DARPA menyatakan bahwa biaya yang disimpan melalui penerapan metode AI untuk unit penjadwalan dalam Perang Teluk pertama telah mengganti seluruh investasi dalam penelitian AI sejak tahun 1950 pada pemerintah AS.

Tantangan Hebat DARPA, yang dimulai pada 2004 dan berlanjut hingga hari ini, adalah sebuah pacuan untuk hadiah $2 juta dimana kendaraan dikemudikan sendiri tanpa komunikasi dengan manusia, menggunakan GPS, komputer dan susunan sensor yang canggih, melintasi beberapa ratus mil daerah gurun yang menantang.

D. Jenis – jenis Agent

·         Simple reflex agents : berdasarkan persepsi yang 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 – utility function.

·         Learning agents: belajar dari pengalaman, meningkatkan kinerja.
                              

LINK PPT : https://drive.google.com/open?id=1CnSy2JujbFeJfyB230TZg0lYMFlEJXc4

Sumber : https://id.wikipedia.org/wiki/Kecerdasan_buatan

                http://pbsabn.lecture.ub.ac.id/2012/05/bidang-aplikasi-artificial-intelligence/

                https://evangelinosite.wordpress.com/2017/10/21/agent-konsep-agent-definisi-serta-contoh/