ARTIFICIAL INTELEGENCE - METODE PENCARIAN SIMPLE HILL CLIMBING

METODE PENCARIAN SIMPLE HILL CLIMBING

Metode pencarian & pelacakan 

• Teknik Search menentukan simpul mana yang dibuat lebih dulu dan mana yang kemudian sampai ditemukannya simpul solusi
• Dari proses search dihasilkan diagram tree, sehingga perlu penjelasan beberapa terminologi diagram tree seperti berikut :

Simpul

Level/Cabang

Path

Parent

Child

Root

Leave

Jumlah Ruang Simpul

Langkah solusi (Solusi)

Pencarian Buta (Blind Search)

Breadth-First Search

Depth-First Search

Pencarian Terbimbing (Heuristics Search)

Generate & Test

Hill Climbing

Best-First Search

Tabu Search

Simulated Annealing

Uniformed Cost Search (UCS)

Greedy Algorithm

A/A* Algorithm

Pendakian Bukit (Hill Climbing)

• Metode ini hampir sama dengan metode pembangkitan & pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik. 
• Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. 
• Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin.

Simple Hill Climbing

Algoritma

• Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.
• Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang:
• Cari operator yang belum pernah digunakan; gunakan operator 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 iterasi.

Operator --> Tukar kota ke-i dengan kota ke-j (Tk i,j)

Kasus: TSP

Untuk 4 kota:

Tk 1,2 : tukar kota ke-1 dengan kota ke-2.

Tk 1,3 : tukar kota ke-1 dengan kota ke-3.

Tk 1,4 : tukar kota ke-1 dengan kota ke-4.

Tk 2,3 : tukar kota ke-2 dengan kota ke-3.

Tk 2,4 : tukar kota ke-2 dengan kota ke-4.

Tk 3,4 : tukar kota ke-3 dengan kota ke-4.

Untuk N kota, akan ada operator sebanyak: 

Kasus: Traveling Salesman Problem (TSP). 

Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Ingin diketahui rute terpendek dimana setiap kota hanya boleh dikunjungi tepat 1 kali. 

Apabila hanya digunakan 4 operator saja:

Pada simple hill climbing, ada 3 masalah yang mungkin:

Algoritma akan berhenti kalau mencapai nilai optimum local.

Urutan penggunaan operator akan sangat berprngaruh pada penemuan solusi.

Tidak diijinkan untuk melihat satupun langkah sebelumnya.

ARTIFICIAL INTELEGENCE - PENDAHULUAN II

PENDAHULUAN II

Bagian terpenting AI

• Knowledge base (basis pengetahuan), berisi fakta-fakta, teori, pemikiran dan hubungan antara satu dengan lainnya. 
• Inference engine, yaitu kemampuan menarik kesimpulan berdasarkan pengalaman.

Analogi dengan kecerdasan manusia

Basis Pengetahuan:

Kumpulan pengetahuan & pengalaman yang dimiliki oleh manusia.

Contoh:

Jika saya makan cabe > 5 buah, maka tidak lama kemudian perut saya akan terasa sakit.

Jika kuliah mulai jam 7, dan saya berangkat dari rumah jam 6.45, maka saya akan terlambat.

Jika x=3.75, maka y=100.

Inferensi:

Kemampuan manusia untuk menalar berdasarkan pengetahuan/pengalaman yang dimiliki, apabila muncul suatu fakta.

Contoh:

Pengetahuan: 

Jika saya makan cabe > 5 buah, maka tidak lama kemudian perut saya akan terasa sakit.

Fakta:

Saya baru saja makan cabe 15 buah.

Kesimpulan:

Tidak lama lagi perut saya akan sakit

Bentuk Penalaran

Penalaran Deduktif

Penalaran dimulai dari premis yang bersifat umum, untuk mendapatkan konklusi yang khusus.

Contoh:

Premis1: Jika hari hujan, maka saya tidak datang.

Premis2: Hari ini turun hujan.

Konklusi: Hari ini saya tidak datang.

Penalaran induktif:

Penalaran dimulai dari premis-premis yang bersifat khusus, untuk mendapatkan konklusi yang bersifat umum.

Contoh:

Premis1: Ikan mujaer bernafas dengan insang.

Premis2: Ikan mas koki bernafas dengan insang.

Premis3: Ikan bawal bernafas dengan insang.

Premis4: Ikan kakap bernafas dengan insang.

Konklusi: Ikan adalah hewan yang bernafas dg insang

Konklusi tidak benar !!!

Penalaran induktif sangat rentan terhadap ketidakpastian.

Suatu penalaran dimana adanya penambahan fakta baru mengakibatkan ketidakkonsistenan disebut dengan “Penalaran Non Monotonis”.  

Ciri-ciri dari Penalaran Non Monotonis adalah:

Mengandung ketidakpastian;

Adanya perubahan pada pengetahuan.

Adanya penambahan fakta baru dapat mengubah konklusi yang sudah terbentuk.

Misalkan S adalah konklusi dari D, bisa jadi S tidak dibutuhkan sebagai konklusi D + fakta-fakta baru.

Sedangkan Penalaran Monotonis memiliki ciri-ciri:

Konsisten;

Pengetahuannya lengkap.

Teknik Pemecahan Masalah

Soft Computing

Soft computing adalah koleksi dari beberapa metodologi yang bertujuan untuk mengeksploitasi adanya toleransi terhadap ketidaktepatan, ketidakpastian, dan kebenaran parsial untuk dapat diselesaikan dengan mudah, robustness, dan biaya penyelesaiannya murah. 

Definisi ini pertama kali diungkapkan oleh Prof. Lotfi A. Zadeh pada tahun 1992.

Komponen Soft Computing

Approximate reasoning:

Fuzzy System;

Probabilistic Reasoning;

Functional Approximation/ Randomized Search:

Neural Network (Jaringan Syaraf)

Evolutionary Algorithm (Algoritma evolusioner).

Sistem Fuzzy

Konsepnya menggunakan teori himpunan.

Menggunakan derajat keanggotaan fuzzy untuk menunjukkan seberapa besar suatu nilai masuk dalam suatu himpunan fuzzy.

Bidang kajian:

Fuzzy Inference System

Fuzzy Clustering

Fuzzy Database

Fuzzy Mathematical Programming

Dll.

Jaringan Syaraf Tiruan

Menggunakan algoritma pembelajaran untuk mendapatkan bobot-bobot yang optimum.

Jenis pembelajaran: supervised learning, dan unsupervised learning.

Algoritma pembelajaran yang sudah dikembangkan, dan paling sering diaplikasikan:

Perceptron

Radial Basis

Backpropagation (sederhana & lanjut)

Self Organizing 

Learning Vector Quantization

dll

Algoritma Evolusioner

Menggunakan pendekatan teori evolusi.

Dipelopori oleh algoritma genetika.

Terutama digunakan untuk optimasi.

Algoritma yang sudah dikembangkan:

Algoritma Genetika

Ant System

Fish Schooling

Bird Flocking

Particle Swarm

Probabilistic Reasoning

Mengakomodasi adanya faktor ketidakpastian.

Teori-teori yang berkembang:

Teorema Bayes

Certainty Factor (statistic reasoning)

Teorema Dempster-Shafer (statistic reasoning)

Hybrid Systems

Setiap komponen dalam Soft computing tidak saling ‘berkompetisi’, melainkan justru saling ‘melengkapi’.

Hybrid system merupakan perpaduan antar komponen dalam soft computing.

Beberapa Hybrid Systems

Neuro-fuzzy Systems

Jaringan syaraf digunakan untuk membangkitkan fungsi keanggotaan suatu sistem fuzzy.

Jaringan syaraf digunakan secara serial dengan sistem fuzzy. Jaringan syaraf berperan pada saat preprocessing dan postprocessing.

ANFIS (Adaptive Network-based Fussy Inference System). Jaringan syaraf digunakan untuk mengimplementasikan Fuzzy inference System.

Neural Fuzzy Systems

Digunakan untuk akuisisi pengetahuan dan pembelajaran.

Jaringan syaraf diinisialisasi dengan pengetahuan pakar dalam bentuk simbol, kemudian dilatih berdasarkan input-output sistem nyata.

Pengetahuan dalam bentuk simbol yang diperoleh dari pelatihan tersebut kemudian direpresentasikan dalam logika fuzzy.

Fuzzy Neural Network

Lapisan-lapisan pada jaringan syaraf, melakukan operasi-operasi: fuzzifikasi dan defuzzy, dari input dan output crisp.

Fuzzy Genetic Algorithms

Kemampuan optimasi dari GA digunakan untuk memilih aturan-aturan terbaik untuk fuzzy inference system.

Neuro-genetic Systems

GA digunakan sebagai sarana untuk mengukur performansi pembelajaran dari jaringan syaraf.

ARTIFICIAL INTELEGENCE - PENDAHULUAN I

PENDAHULUAN I

        Kecerdasan buatan atau artificial intelligence merupakan salah satu bagian ilmu komputer yang membuat agar mesin (komputer) dapat melakukan pekerjaan seperti dan sebaik yang dilakukan oleh manusia. Sistem cerdas (intelligent system) adalah sistem yang dibangun dengan menggunakan teknik-teknik artificial intelligence. 

Sudut pandang Kecerdasan 

Sudut pandang kecerdasan 

Kecerdasan Buatan akan membuat mesin menjadi ‘cerdas’ (mampu berbuat seperti apa yang dilakukan oleh manusia) 

Sudut pandang penelitian.

Kecerdasan Buatan adalah suatu studi bagaimana membuat agar komputer dapat melakukan sesuatu sebaik yang dikerjakan oleh manusia 

Sudut pandang bisnis.

Kecerdasan buatan adalah kumpulan peralatan yang sangat powerful dan metodologis dalam menyelesaikan masalah-masalah bisnis.

Sudut pandang pemrograman.

Kecerdasan buatan meliputi studi tentang pemrograman simbolik, penyelesaian masalah (problem solving) dan pencarian (searching).

Tanda Kecerdasan

• belajar atau memahami dari pengalaman 
• menemukan inti dari pesan yang ambigu atau bertentangan 
• merespon dengan cepat dan tepat pada situasi baru 
• menggunakan pertimbangan dalam memecahkan persoalan atau mengarahkan tindakan secara efektif
• menghadapi situasi yang membingungkan 
• memahami dan menyimpulkan dengan cara rasional biasa 
• menerapkan pengetahuan untuk memanipulasi lingkungan 
• berfikir dan mempertimbangkan 

Keuntungan Kecerdasan buatan

• Kecerdasan buatan lebih bersifat permanen 
• Kecerdasan buatan lebih mudah diduplikasi & disebarkan 
• Kecerdasan buatan lebih murah dibanding dengan kecerdasan alami 
• Kecerdasan buatan bersifat konsisten 
• Kecerdasan buatan dapat didokumentasi 
• Kecerdasan buatan dapat mengerjakan pekerjaan lebih cepat dibanding dengan kecerdasan alami 
• Kecerdasan buatan dapat mengerjakan pekerjaan lebih baik dibanding dengan kecerdasan alami 
• Kreatif 
• Kecerdasan alami memungkinkan orang untuk menggunakan pengalaman secara langsung. Sedangkan pada kecerdasan buatan harus bekerja dengan input-input simbolik.
• Pemikiran manusia dapat digunakan secara luas, sedangkan kecerdasan buatan sangat terbatas 

Sejarah AI

     Dimulai dengan uji mesin Turing: AI lulus tes apabila integrator tidak bisa membedakan dialog yang dilakukan oleh komputer – mesin, dengan komputer – manusia. 

Tahun 1943-1956 

Program catur pertama oleh Shanon & Turing (1950)

Deklarasi AI (1956) pada Workshop Dartmouth oleh John McCarthy

Tahun 1956-1966

Logic Theorist (mampu membuktikan teorema-teorema matematika)

Sad Sam, diprogram oleh Robert K. Lindsay (1960). Program ini dapat mengetahui kalimat-kalimat sederhana yang ditulis dalam bahasa Inggris dan mampu memberikan jawaban dari fakta-fakta yang didengar dalam sebuah percakapan.

General Problem Solver

Tahun 1966 – 1979

Program AI hanya bisa melakukan manipulasi simbolik dan hanya bisa memuat sedikit sekali pengetahuan.

Problem AI yang akan dipecahkan tidak mudah ditangani

Sistem berbasis pengetahuan -> terutama untuk sistem pakar:

MYCIN

DENDRAL

PROSPECTOR

XCON & XSEL

FOLIO

DELTA

Tahun 1980-sekarang:

AI telah menjadi komoditi industri:

R1 Sistem Pakar komersial pertama yg dibuat oleh Digital Equipment Corporation (DEC), 1982.

Proyek “Generasi Kelima” , pembuatan komputer cerdas dengan Prolog (Jepang), 1981.

Daya jual produk AI: beberapa juta dolar (1980) – mencapai $2 miliar (1988).

Cabang-cabang AI

Logical AI

Logika (matematis) yang merepresentasikan sekumpulan fakta dan tujuan ---> RUANG KEADAAN:

Graph

Tree

Search

Pencarian keadaan baru dari keadaan sekarang yang akan menentukan pergerakan:

Blind Search

Depth-First Search

Breadth-Firsh Search 

Heuristic Search

Generate & Test

Hill Climbing

Best-First search

Simulated-Annealing

Tabu Search

Algoritma Genetika

Representation

Representasi fakta-fakta (pengetahuan) dalam ruang keadaan:

Logika (proposisi & predikat)

Tree

Jaringan Semantik

Frame

Naskah

Kaidah Produksi

Pattern Recognition

Pengenalan & pencocokan suatu pola terhadap sekumpulan pola.

Pengolahan Bahasa Alami

Jaringan Syaraf Tiruan

Inference

Kemampuan untuk menarik kesimpulan berdasarkan pengetahuan.

Forward Reasoning

Backward Reasoning

Fuzzy Inference System (FIS)

Learning from Experience

Melakukan proses pembelajaran (pelatihan) dari pengetahuan atau pengalaman yang ada pada basis pengetahuan.

Jaringan Syaraf Tiruan

ASSEMBLER - INPUT OUTPUT

INPUT OUTPUT

1.1 Tujuan      
      1. Memahami cara kerja input output pada mikroprosesor
      2. Memahami instruksi input dan output data
      3. Mampu membuat perangkat lunak dengan menggunakan instruksi-instruksi input output dan               mengaplikasikannya.

1.2 Peralatan Yang Digunakan     
      1. 1 set PC atau laptop
      2. Perangkat lunak simulator sms32v50
      3. Buku Kerja

1.3 Teori Dasar
Input Output Mikroprosesor
    Input dan output dalam mikroprosesor atau biasa yang disebut port merupakan sarana untuk berkomunikasi dengan dunia luar dari mikroprosesor tersebut. Dalam simulator ini terdapat 16 port I/O yang beralamat dari 00 – 0F. Dari total alamat tersebut yang terpakai dari 00 – 08 sedangkan pada alamat 09-0F tidak digunakan. Adapun pembagian alamat port I/O beserta perangkat kerasnya ditunjukkan dalam Tabel 5.1.

Tabel 5.1 Port I/O dan alamatnya

Port	Deskripsi	Fungsi
00	Keyboard (pada PC yang digunakan)	Input
01	Traffic Light	Output
02	Seven Segment Display	Output
03	Kontrol the heater dan Sensor thermostat.	Input/Output
04	The snake in the maze.	Output
05	Kontrol motor stepper.	Output
06	Lift	Input/Output

07	Keyboard ASCII code.	Input
08	Keypad (numeric)	Input
09-0F	Tidak digunakan

Sedangkan untuk intruksi yang digunakan ditunjukkan dalam Tabel 5.2

Tabel 5.2 Intruksi I/O

Assembler	Kode Mesin	Keterangan
IN 07	F0 07	Input dari Port 07. F0 adalah opcode. 07 no port I/O
OUT 01	F1 01	Output ke Port 01. F1 adalah opcode. 01 no port I/O

ASSEMBLER - INTERUPSI

INTERUPSI

1.1 Tujuan     
       1. Memahami cara kerja interupsi pada mikroprosesor
       2. Memahami instruksi interups

      3. Mampu membuat perangkat lunak dengan menggunakan instruksi-instruksi yang berhubungan             dengan proses interupsi

1.2 Peralatan Yang Digunakan    
       1. 1 set PC atau laptop
       2. Perangkat lunak simulator sms32v50
       3. Buku Kerja

1.3 Teori Dasar
Interupsi dan Prosedur

       Interupsi adalah suatu permintaan khusus kepada mikroposesor untuk melakukan sesuatu. Bila terjadi interupsi, maka komputer akan menghentikan dahulu apa yang sedang dikerjakannya dan melakukan apa yang diminta oleh yang menginterupsi. Program yang melayani suatu interupsi dinamakan Interrupt Handler. 

     Interupsi adalah fragmen kode pendek yang menyediakan layanan yang berguna yang dapat digunakan oleh program lain. Contoh penanganan rutinitas interupsi adalah penekanan tombol , gerakan mouse dan penekanan tombol , menulis layar , pembancaan dan penulisana disk, dan sebagainya. Interupsi seperti prosedur tapi dengan cara penyebutan yang berbeda . 

     Prosedur ini disebut dengan melompat ke alamat awal prosedur. Alamat ini hanya diketahui program yang memiliki prosedur. Interupsi disebut dengan melihat alamat dari kode interrupt dalam tabel vektor interupsi . Isi tabel ini diterbitkan dan dikenal luas . MS DOS yang menggunakan interupsi untuk semuanya disk, layar , mouse , jaringan, keyboard dan layanan lainnya. 

     Pada Interupsi secara software, permintaan interupsi dipicu bergantung dari program yang berjalan. Sedangkan pada interupsi secara hardware, maka permintaan interupsi dipicu oleh adanya sinyal elektronik ke CPU dari perangkat keras diluar CPU.

Tabel Vektor Interupsi       
      Setiap interrupt akan mengeksekusi interrupt handlernya masing-masing berdasarkan nomornya. Sedangkan alamat dari masing- masing interupt handler tercatat di memori dalam bentuk array yang besar elemennya masing-masing 4 byte. Keempat byte ini dibagi lagi yaitu 2 by te pertama berisi kode offset sedangkan 2 byte berikutnya berisi kode segmen dari alamat interupt handler yang bersangkutan. Pada komputer IBM kompatibel , alamat 0-1024 desimal yang digunakan untuk menyimpan vektor interupsi. Vektor simulator duduk antara alamat 0 dan 15 desimal. 

Tabel 1 Instruksi prosedur/subrutin

Assembler	Machine Code	Explanation
INT 03	CC 03	Instruksi Pointer (IP) diatur ke alamat dari vektor interupsi diambil dari alamat RAM 03. CC adalah instruksi mesin untuk INT. 03 adalah alamat dari vektor interrupt yang digunakan oleh perintah INT.
IRET	CD	Kembali dari interrupt. Mengatur Pointer Instruksi (IP) ke alamat kembali muncul dari tumpukan. CD adalah instruksi mesin untuk IRET.
STI	FC	Mengaktifkan interupsi
CLI	FD	Non aktifkan interupsi
NOP	FF	Tidak ada operasi intruksi dalam satu siklus clock