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

Metode Searching

Metode Pencarian/Pelacakan

• Hal penting dalam menentukan keberhasilan sistem AI adalah kesuksesan dalam pencarian solusi.
• Pencarian = suatu proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan/masalah (state space).
• Ruang keadaan/masalah = merupakan suatu ruang yang berisi semua keadaan yang mungkin.

Untuk mengukur kinerja metode pencarian, terdapat empat kriteria yang dapat digunakan :

• Completeness :
  apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada?

• Time complexity :
  berapa lama waktu yang diperlukan?

• Space complexity :
  berapa banyak memori yang diperlukan

• Optimality :
  apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda? 

Langkah-langkah dalam teknik searching :

1. Mendefinisikan RUANG MASALAH/RUANG KEADAAN untuk suatu masalah yg dihadapi.
2. Mendefinisikan aturan produksi yang digunakan untuk mengubah suatu “state” ke “state” lainnya.
3. Memilih metode pencarian yg tepat sehingga dapat menemukan solusi terbaik dengan usaha yang minimal.

Pada dasarnya terdapat 2 teknik pelacakan yang biasa digunakan :

1. Pencarian buta ( blind search )

2. Pencarian Terbimbing ( heuristic search )

Pengertian Teknik Pencarian dalam AI

Pencarian adalah suatu proses mencari solusi dari suatu permasalahn melalui sekumpulan ruang keadaan. Ruang keadaan adalah suatu ruang yang didalamnya berisi semua keadaan yang mungkin.

Kondisi dalam suatu pencarian menggunakan AI :

> Kondisi sekarang / keadaan awal

> Keadaan Tujuan yang merupakan solusi yang dijangkau apakah sudah mencapai sasaran .

> Biaya atau nilai yang diperoleh dari solusi

Solusi merupakan suatu lintasan dari keadaan awal sampai keadaan tujuan.

Uniform Cost Search

Uniform Cost Search adalah algoritma Seach Tree (graph) yang digunakan untuk menyelesaikan beberapa persoalan . Algoritma ini memulai pencarian dari root node, kemudian dilanjutkan ke node-node selanjutnya. Dimana node tersebut dipilih yang memilki harga (cost) terkecil dari root node. Algoritma ini merupakan modifikasi dari Bread First Search (BFS).

Dalam implementasi algoritma ini , melibatkan semua node yang berhubungan dengan root node, dan meletakannya dalam priority queue untuk mencapai node tujuan. Dimana node – node yang dipilih merupakan node yang berharga terkecil.

Depth First Search

Algoritma DFS (Depth First Search) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik.

Algoritma ini mirip dengan Algoritma BFS (Breadth First Search) yang sudah dijelaskan sebelumnya. Jika Algoritma BFS (Breadth First Search) melakukan perhitungan secara terurut dari urutan pertama sampai urutan terakhir, maka algoritma ini melakukan kebalikannya, yaitu melakukan perhitungan secara terurut dari urutan terakhir. Setelah menghabiskan semua kemungkinan dari titik terakhir, barulah mundur ke titik-titik sebelumnya sampai pada titik pertama.

Depth Limited Search

Depth Limited Search Algoritma DLS (Depth Limited Search) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik.

Algoritma ini merupakan variasi dari Algoritma DFS (Depth First Search) yang sudah dijelaskan sebelumnya. Jika Algoritma DFS (Depth First Search) melakukan perhitungan (yang dimulai dengan titik terakhir) dengan cara menghabiskan semua tingkatan / kedalaman dari sebuah titik, maka algoritma ini memiliki batasan dimana perhitungan pada sebuah titik hanya dihitung sampai pada kedalaman tertentu. Setelah semua kemungkinan pada kedalaman itu sudah habis, kemudian akan dilanjutkan pada titik berikutnya.

Pengenalan Teknologi Sistem Cerdas

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 syaraf 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. Di sisi lain, hal yang bagi manusia kelihatannya menuntut sedikit kecerdasan, sampai sekarang masih sulit untuk direalisasikan dalam Informatika. Seperti contoh: Pengenalan Obyek/Muka, bermain sepak bola.

Walaupun AI memiliki konotasi fiksi ilmiah yang kuat, AI membentuk cabang yang sangat penting pada ilmu komputer, berhubungan dengan perilaku, pembelajaran dan adaptasi yang cerdas dalam sebuah mesin. Penelitian dalam AI menyangkut pembuatan mesin untuk mengotomatisasikan tugas-tugas yang membutuhkan perilaku cerdas. Termasuk contohnya adalah pengendalian, perencanaan dan penjadwalan, kemampuan untuk menjawab diagnosa dan pertanyaan pelanggan, serta pengenalan tulisan tangan, suara dan wajah. Hal-hal seperti itu telah menjadi disiplin ilmu tersendiri, yang memusatkan perhatian pada penyediaan solusi masalah kehidupan yang nyata. Sistem AI sekarang ini sering digunakan dalam bidang ekonomi, obat-obatan, teknik dan militer, seperti yang telah dibangun dalam beberapa aplikasi perangkat lunak komputer rumah dan video game.

Beberapa Bidang dalam Kecerdasan Buatan antara lain :

1.Sistem Pakar

2.Algoritma Genetika

3.Logika Fuzzy

4.Jaringan Syaraf Tiruan

5.Robotika

1. Sistem Pakar

Sistem pakar adalah suatu program komputer yang dirancang untuk mengambil keputusan seperti keputusan yang diambil oleh seorang atau beberapa orang pakar. Menurut Marimin (1992), sistem pakar adalah sistem perangkat lunak komputer yang menggunakan ilmu, fakta, dan teknik berpikir dalam pengambilan keputusan untuk menyelesaikan masalah-masalah yang biasanya hanya dapat diselesaikan oleh tenaga ahli dalam bidang yang bersangkutan.

Dalam penyusunannya, sistem pakar mengkombinasikan kaidah-kaidah penarikan kesimpulan (inference rules) dengan basis pengetahuan tertentu yang diberikan oleh satu atau lebih pakar dalam bidang tertentu. Kombinasi dari kedua hal tersebut disimpan dalam komputer, yang selanjutnya digunakan dalam proses pengambilan keputusan untuk penyelesaian masalah tertentu.

Modul Penyusun Sistem Pakar

Suatu sistem pakar disusun oleh tiga modul utama (Staugaard, 1987), yaitu :

Modul Penerimaan Pengetahuan Knowledge Acquisition Mode)

Sistem berada pada modul ini, pada saat ia menerima pengetahuan dari pakar. Proses mengumpulkan pengetahuan-pengetahuan yang akan digunakan untuk pengembangan sistem, dilakukan dengan bantuan knowledge engineer. Peran knowledge engineer adalah sebagai penghubung antara suatu sistem pakar dengan pakarnya

ModulKonsultasi(ConsultationMode)

Pada saat sistem berada pada posisi memberikan jawaban atas permasalahan yang diajukan oleh user, sistem pakar berada dalam modul konsultasi. Pada modul ini, user berinteraksi dengan sistem dengan menjawab pertanyaan-pertanyaan yang diajukan oleh sistem

Modul Penjelasan(Explanation Mode)

Modul ini menjelaskan proses pengambilan keputusan oleh sistem (bagaimana suatu keputusan dapat diperoleh).

Struktur Sistem Pakar

Komponen utama pada struktur sistem pakar (Hu et al, 1987) meliputi:

Basis Pengetahuan (Knowledge Base)

Basis pengetahuan merupakan inti dari suatu sistem pakar, yaitu berupa representasi pengetahuan dari pakar. Basis pengetahuan tersusun atas fakta dan kaidah. Fakta adalah informasi tentang objek, peristiwa, atau situasi. Kaidah adalah cara untuk membangkitkan suatu fakta baru dari fakta yang sudah diketahui. Menurut Gondran (1986) dalam Utami (2002), basis pengetahuan merupakan representasi dari seorang pakar, yang kemudian dapat dimasukkan kedalam bahasa pemrograman khusus untuk kecerdasan buatan (misalnya PROLOG atau LISP) atau shell sistem pakar (misalnya EXSYS, PC-PLUS, CRYSTAL, dsb.

Mesin Inferensi (Inference Engine)

Mesin inferensi berperan sebagai otak dari sistem pakar. Mesin inferensi berfungsi untuk memandu proses penalaran terhadap suatu kondisi, berdasarkan pada basis pengetahuan yang tersedia. Di dalam mesin inferensi terjadi proses untuk memanipulasi dan mengarahkan kaidah, model, dan fakta yang disimpan dalam basis pengetahuan dalam rangka mencapai solusi atau kesimpulan. Dalam prosesnya, mesin inferensi menggunakan strategi penalaran dan strategi pengendalian.

Strategi penalaran terdiri dari strategi penalaran pasti (Exact Reasoning) dan strategi penalaran tak pasti (Inexact Reasoning). Exact reasoning akan dilakukan jika semua data yang dibutuhkan untuk menarik suatu kesimpulan tersedia, sedangkan inexact reasoning dilakukan pada keadaan sebaliknya.

Strategi pengendalian berfungsi sebagai panduan arah dalam melakukan prose penalaran. Terdapat tiga tehnik pengendalian yang sering digunakan, yaitu forward chaining, backward chaining, dan gabungan dari kedua tehnik pengendalian tersebut.

Basis Data (Database)

Basis data terdiri atas semua fakta yang diperlukan, dimana fakta-fakta tersebut digunakan untuk memenuhi kondisi dari kaidah-kaidah dalam sistem. Basis data menyimpan semua fakta, baik fakta awal pada saat sistem mulai beroperasi, maupun fakta-fakta yang diperoleh pada saat proses penarikan kesimpulan sedang dilaksanakan. Basis data digunakan untuk menyimpan data hasil observasi dan data lain yang dibutuhkan selama pemrosesan.

Antarmuka Pemakai (User Interface)

Fasilitas ini digunakan sebagai perantara komunikasi antara pemakai dengan sistem. Hubungan antar komponen penyusun struktur sistem pakar dapat dilihat pada Gambar di bawah ini :

2.Algoritma genetika

Algoritma Genetika adalah suatu algoritma pencarian yang meniru mekanisme dari genetika alam. Algoritma Genetika ini banyak dipakai pada aplikasi bisnis, teknik maupun pada bidang keilmuan.Algoritma ini dapat dipakai untuk mendapatkan solusi yang tepat untuk masalah optimal dari satu variabel atau multi variabel. Sebelum Algoritma ini dijalankan, masalah apa yang ingin dioptimalkan itu harus dinyatakan dalam fungsitujuan, yang dikenal dengan fungsi fitness. Jika nilai fitness semakin besar, maka sistem yang dihasilkan semakin baik. Operasi yang dilakukan adalah reproduksi, crossover, dan mutasi untuk mendapatkan sebuah solusi menurut nilai fitnessnya.

Selanjutnya konstruksi dasar dari Algoritma Genetika adalah sebagai berikut:

• Pendefinisian Chromosome

• Pendefinisian Fungsi Fitness

• Membangkitkan Sebuah Populasi Awal

• Reproduksi

• Crossover

• Mutasi

Contoh: Aplikasi Algoritma Genetika Untuk Merancang Fungsi Keanggotaan Pada Kendali Logika Fuzzy.

3.Logika Fuzzy

Logika Fuzzy ( logika samar ) merupakan logika yang berhadapan langsung dengan konsep kebenaran sebagian, dimana logika klasik menyatakan bahwa segala hal dapat di ekspresikan dalam binary 0 atau 1. logika fuzzy memungkinkan nilai keanggotaan antara 0 dan 1. Karena alasan diatas maka pada penelitian ini akan dibuat perancangan perangkat lunak dan perangkat keras robot avoider dengan mengunakan aplikasi Fuzzy Logic sebagai kendali system.

Perlu diketahui bahwa Teori Himpunan Samar dan Logika Samar sangat berkembang pesat pada saat ini. Banyak sekali masalah-masalah nyata yang lebih tepat diselesaikan menggunakan Teori Himpunan Samar dan Logika Samar. Banyak sekali muncul teori-teori baru pada saat ini misalnya: Topologi Fuzzy, Analisa Fuzzy, Aljabar Fuzzy (Fuzzy Semi Group, Fuzzy Ring, Fuzzy Group, dan sebagainya.

Logika fuzzy telah lama dikenal dan digunakan dalam berbagai bidang oleh para ahli dan insinyur. Penggunaan logika fuzzy pada awalnya digunakan untuk beberapa bidang, seperti sistem diagnosa penyakit (dalam bidang kedokteran); pemodelan sistem pemasaran, riset operasi (dalam bidang ekonomi); kendali kualitas air, prediksi adanya gempa bumi, klasifikasi dan pencocokan pola (dalam bidang teknik). Penggunaan logika fuzzy dalam bidang sistem daya (power system) juga sudah dilakukan, antara lain dalam analisis kemungkinan, prediksi dan pengaturan beban, identifikasi gangguan pada generator dan penjadwalan pemeliharaan generator.

4. Jaringan Syaraf  Tiruan

Jaringan saraf tiruan (JST) (Bahasa Inggris: artificial neural network (ANN), atau juga disebut simulated neural network (SNN), atau umumnya hanya disebut neural network (NN)), adalah jaringan dari sekelompok unit pemroses kecil yang dimodelkan berdasarkan jaringan saraf manusia. JST merupakan sistem adaptif yang dapat mengubah strukturnya untuk memecahkan masalah berdasarkan informasi eksternal maupun internal yang mengalir melalui jaringan tersebut.

Secara sederhana, JST adalah sebuah alat pemodelan data statistik non-linier. JST dapat digunakan untuk memodelkan hubungan yang kompleks antara input dan output untuk menemukan pola-pola pada data.

Sejarah

Saat ini bidang kecerdasan buatan dalam usahanya menirukan intelegensi manusia, belum mengadakan pendekatan dalam bentuk fisiknya melainkan dari sisi yang lain. Pertama-tama diadakan studi mengenai teori dasar mekanisme proses terjadinya intelegensi. Bidang ini disebut ‘Cognitive Science’. Dari teori dasar ini dibuatlah suatu model untuk disimulasikan pada komputer, dan dalam perkembangannya yang lebih lanjut dikenal berbagai sistem kecerdasan buatan yang salah satunya adalah jaringan saraf tiruan. Dibandingkan dengan bidang ilmu yang lain, jaringan saraf tiruan relatif masih baru. Sejumlah literatur menganggap bahwa konsep jaringan saraf tiruan bermula pada makalah Waffen McCulloch dan Walter Pitts pada tahun 1943. Dalam makalah tersebut mereka mencoba untuk memformulasikan model matematis sel-sel otak. Metode yang dikembangkan berdasarkan sistem saraf biologi ini, merupakan suatu langkah maju dalam industri komputer.

Definisi

Suatu jaringan saraf tiruan memproses sejumlah besar informasi secara paralel dan terdistribusi, hal ini terinspirasi oleh model kerja otak biologis. Beberapa definisi tentang jaringan saraf tiruan adalah sebagai berikut di bawah ini.

Hecht-Nielsend (1988) mendefinisikan sistem saraf buatan sebagai berikut:

"Suatu neural network (NN), adalah suatu struktur pemroses informasi yang terdistribusi dan bekerja secara paralel, yang terdiri atas elemen pemroses (yang memiliki memori lokal dan beroperasi dengan informasi lokal) yang diinterkoneksi bersama dengan alur sinyal searah yang disebut koneksi. Setiap elemen pemroses memiliki koneksi keluaran tunggal yang bercabang (fan out) ke sejumlah koneksi kolateral yang diinginkan (setiap koneksi membawa sinyal yang sama dari keluaran elemen pemroses tersebut). Keluaran dari elemen pemroses tersebut dapat merupakan sebarang jenis persamaan matematis yang diinginkan. Seluruh proses yang berlangsung pada setiap elemen pemroses harus benar-benar dilakukan secara lokal, yaitu keluaran hanya bergantung pada nilai masukan pada saat itu yang diperoleh melalui koneksi dan nilai yang tersimpan dalam memori lokal".

Menurut Haykin, S. (1994), Neural Networks: A Comprehensive Foundation, NY, Macmillan, mendefinisikan jaringan saraf sebagai berikut:

“Sebuah jaringan saraf adalah sebuah prosesor yang terdistribusi paralel dan mempuyai kecenderungan untuk menyimpan pengetahuan yang didapatkannya dari pengalaman dan membuatnya tetap tersedia untuk digunakan. Hal ini menyerupai kerja otak dalam dua hal yaitu: 1. Pengetahuan diperoleh oleh jaringan melalui suatu proses belajar. 2. Kekuatan hubungan antar sel saraf yang dikenal dengan bobot sinapsis digunakan untuk menyimpan pengetahuan.

Dan menurut Zurada, J.M. (1992), Introduction To Artificial Neural Systems, Boston: PWS Publishing Company, mendefinisikan sebagai berikut:

“Sistem saraf tiruan atau jaringan saraf tiruan adalah sistem selular fisik yang dapat memperoleh, menyimpan dan menggunakan pengetahuan yang didapatkan dari pengalaman”.

DARPA Neural Network Study (1988, AFCEA International Press, p. 60) mendefinisikan jaringan syaraf buatan sebagai berikut :

Sebuah jaringan syaraf adalah sebuah sistem yang dibentuk dari sejumlah elemen pemroses sederhana yang bekerja secara paralel dimana fungsinya ditentukan oleh stuktur jaringan, kekuatan hubungan, dan pegolahan dilakukan pada komputasi elemen atau nodes.

5. Robotika

Robotika adalah salah satu wacana teknologi untuk menuju peradaban yang lebih maju. Kebanyakan orang selalu beranggapan bahwa robot adalah kemajuan teknologi yang mampu menggeser tingkah laku seseorang untuk melakukan suatu tindakan. Dengan kemajuan yang pesat, maka kebutuhan akan SDM akan merosot tajam. Layaknya revolusi pada bangsa Eropa.

Sangat disayangkan selali bila titik ikon kemajuan teknologi tersebut tidak seiring dengan cepat nya pemahaman masyarakat pada umumnya yang selalu meng-analogikan robot adalah biang kerok hilangnya tenaga buruh untuk memacu pertumbuhan perekonomian.

Hal ini layaknya dua sisi perbedaan yang tidak akan bisa menyatu sama lain. Tapi bisa dicermati kembali, bila orang pelukis ternama akan tergusur karena kemampuan sebuah robot pelukis yang bisa membuat lukisan yang sama. Sebuah robot yang mampu untuk memahat patung yang hampir mirip pula. Seluruh ilustrasi tersebut memang sepintas robot bisa menguasai semua, tapi sangat disayangkan hasil kerja robot adalah tak lebih dari sebuah alat cetak dan seonggok besi aluminium dan komponen elektronika yang dirakit pada papan PCB. Sebuah lukisan dari Afandi tentunya akan bernilai ratusan juta beda ukuran dengan lukisan robot yang paling-paing laku di jual 10 ribuan di pinggir jalan.

Robot Bukanlah Pemegang Kekuasaan

Istilah robot yang dahulu kala berjulukan Robota, tak lain adalah kata lain dari seorang buruh. Lain halnya dengan seorang manusia yang diciptakan se-sempurna mungkin oleh sang Pencipta. Sampai kapanpun robot adalah pembantu manusia. Bila sang teknokrat menciptakan robot untuk menjadi penguasa dunia, semoga saja dia tidak berumur panjang. Namun robot adalah sarana untuk membangun peradaban yang lebh maju dan memberikan kemudahan bagi manusia sebagai penciptanya. Dengan hasil demikian maka seluruh kajian tentang robotika menjadi lebih memasyarakat diseluruh elemen masyarakat. Dan buakan menjadi momok yang harus ditakuti.

Robotika sebagai Ikon dan Kajian Ke-ilmuan

Robot adalah simbol dari kamajuan dari sebuah teknologi, karena didalam nya mencakup seluruh elemen keilmuan. Elektronika, Mekanika, Mekatronika, Kinematika, Dimamika, dan lain sebagainya. Hal ini menjadi suatu alasan yang sangat tepat untuk mengash ilmu didalam nya. Ikon pendidikan akan menjadi semakin termasyur bila selalu mengutamakan teknologi didalam nya. Sebuah ikon ini sangat penting untuk membangun semangat kemajuan, karena hal ini akan menjadi sebuah patokan awal dari sebuah perjuangan untuk selalu dilanjutkan kepada generasi penerus.

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 Lovelace bekerja 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 pondasi untuk jaringan syaraf.

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 syaraf 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 syaraf digunakan secara meluas dengan algoritma 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 syaraf. Para ahli psikologi, David Rumelhart dan Geoff Hinton, melanjutkan penelitian mengenai model jaringan syaraf pada memori. Pada tahun 1985-an sedikitnya empat kelompok riset menemukan kembali algoritma pembelajaran propagansi balik (Back-Propagation learning). Algoritma 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.

Menurut Russel dan Norvig, pengertian agent adalah segala sesuatu yang dapat dipandang menangkap/mengetahui/menangapi lingkunganya melalui sensor dan bertindak terhadap lingkunganya melalui efektor. Sensor merupakan bagian yang merangsang akan merangsang agent (kamera & infra red pada robot) sedangkan efektor merupakan bagian yang digunakan oleh agent untuk menangapi rangsangan yang telah diterimanya sebelumnya(motor pada robot).

Struktur Agent

Sebuah agent diharapkan melakukan tindakan yang benar sesuai dengan tujuan diciptakan agent tersebut. Tindakan yang dilakukan oleh agent tersebut yang akan digunakan sebagai tolak ukur terhadap keberhasilan sebuah agent.

Berikut 4 buah dasar yang dapat digunakan untuk menentukan tolak ukur sebuah agent :

Performance measure (tolak ukur terhadap kesuksesan hasil kerja) yang menyatakan derajat kesuksesan.

Semua imput yang diterima oleh agent, dapat dilacak kembali (imput disimpan dalam serangkaian data/memory).

Segala sesuatu yang diketahui agen terhadap lingkunganya.

Setiap indakan yang akan dilakukan oleh agen.

Pada umumnya sebuah agent terdiri dari dua buah komponen dasar yaitu suatu program dan sebuah piranti perangkat keras (arsitektur/computer). Sebagai ilustrasi terhadap hubungan keduanya, sebuah arsitektur memberikan sebuah percept dari sensor kemudian siap digunakan kedalam program, menjalankan program dan memberikan pilihan-pilihan tindakan program ke efektor.

Dua hal penting dalam proses pembuatan program agent.

Menyatakan mapping (pemetaan) sebagai sebuah fungsi dan urutan precepsi ke tindakan. Program agent hanya menerima sebuah presepsi berdasarkan jangka waktu tertentu. Kemudian menyimpan setiap prepsesi sesuai dengan urutan tertentu kedalam memory .

Tujuan dan performance tidak termaksud kedalam rangka program.

Terdapat 4 hal yang harus diperhatikan dalam merancang sebuah agent. Yaitu Percept, Action, Goal dan Enviroment. Biasa disingkat PAGE. Aget harus menangapi setiap rangsangan (precpt) yang ada disekitarnya, kemudian memberikan tindakan (action) yang tepat terhadap rangsangan tersebut, dan yang pasti setiap tindakan tersebut harus sesuai dengan tujuan (Goal) awal diciptakanya agent tersebut. Selain itu setiap aksi yang dilakukan aleh agent tersebut harus memperhatikan lingkungan (Environment) dimana agent tersebut di tempatkan.

Tipe Program Agent

Simple Reflex Agent

Merupakan agent yang bekerja berdasarkan reflex. Contohnya, sebuah driver agent(supir taxi otomatis), harus memberikan reflex mengerem ketika terdapat mobil yang berhenti didepanya.

2. Agent That Keep Track the World

Merupakan agent yang tetap melakukan pengecekan terhadap keadaan lingkungan, sehingga dapat memberikan respon yang tepat.

3. Goal based agent(Agent berbesis pada tujuan/sasaran)

Merupakan sebuah agent yang mendasarkan setiap tindakannya untuk mencapai tujuan yang telah ditentukan. Setiap agent akan mempertimbangkan setiap kemungkinan yang akan terjadi pada mesa depan berdasarkan tindakan yang akan/telah dilakukanya.

4. Utility Based Agent

Merupakan sebuah fungsi yang memetakan suatu keadaan kedalam bilangan real, yang menggambarkan derajak kesenangan/kepuasan. Sedikit berbeda dengan Goal Based Agent, tipe ini tidak mengutamakan semua tujua, tetapi akan mengutamakan tujuan mana yang mungkin tercapai berdasarkan kondisi tertentu(tujuan kepuasan, kenyamanan, keefisienan).

Environment (Lingkungan)

Lingkungan sangat lah penting dalam proses perancangan sebuah agent. Hal ini dikarenakan setiap tindakan yang akan dilakukan oleh agent harus mempertimbangkan kondisi lingkungan. Terdapat beberapa kriteria pembegian lingkungan.

Accessible (dapat diakses)

Jika sensor agent dapat mendeteksi semua keadaan lingkungan, terutama yang berhubungan dengan pengambilan keputusan.

2. Deterministic

Merupakan suatu lingkungan dimana lingkungan yang akan dating ditentukan oleh keadaan saat ini dan setiap aksi yang dilakukan oleh agen saat ini.

3. Dynamic

Suatu lingkungan yang keadaanya selalu berubah-ubah.

4. Discrete (diskrit)

Keadaan dimana lingkungan saat ini dapat digambarkan dengan pasti, dengan tingkat kesalahan seminimal mungkin.