Selasa, 03 Agustus 2010

Algoritma Genetik

Sekilas Sejarah tentang Algoritma Genetik

Landasan teory Algoritma genetik ini diajukan
oleh John Holland dalam bukunya yang berjudul
"Adaption in Natural and Artificial Systems" pada tahun
1975, yang kemudian dikembangkan lebih lanjut oleh
muridnya David Goldberg.
Proses genetika dari organisme-organisme biologi yang
berdasar pada teori evolusi Charles Drawin

Taukah anda "Algoritma Genetik"?
 
Algoritma genetik adalah suatu metoda pencarian
acak yang didasarkan atas prinsip evolusi yang terjadi di alam.
Dalam proses evolusi, individu secara terusmenerus
mengalami perubahan gen untuk menyesuaikan dengan
lingkungan hidupnya. Hanya individu yang kuat yang mampu
bertahan, sehingga dalam proses evolusi dapat diharapkan
diperoleh individu yang terbaik. Proses seleksi alamiah ini
melibatkan perubahan gen yang terjadi pada individu melalui
proses perkembangbiakan
untuk mendapatkan keturunan
yang lebih baik.

Apa "Genetik" itu sendiri?

Genetik itu Cabang biologi yang mempelajari tentang keturunan dan variasi
mahluk hidup
Informasi genetik manusia tesimpan dalam sel tepatnya di
kromosom.
Dalam sel manusia kromosom bentuknya berpasangan dan
terdapat 23 pasang
Kromosom ini terbentuk dari bagian-bagian yang disebut gen
Gen inilah yang mengatur properti dan karateristik suatu individu
contoh: Warna mata, jenis rambut

Dasar Algoritma Genetik

-Populasi-
-Individu-


Populasi adalah kumpulan kromosom (chromosome).
Kromosom ini dibentuk dari komponen-komponen
penyusun yang disebut sebagai gen dan nilainya dapat
berupa bilangan numerik, biner, simbol ataupun
karakter tergantung dari permasalahan yang ingin
diselesaikan.

Individu merupakan kumpulan gen dalam sistem
algoritma genetik bisa dikatakan sama dengan
kromosom. Gen ini bisa biner, float, dan kombinatorial.
Individu dalam algoritma genetik dapat juga
menyatakan salah satu kemungkinan solusi yang dicari.
Misalkan dalam travel salesman problem individu dapat
menyatakan suatu jalur terpendek yang akan ditempuh.
Prinsip Kerja Prinsip Kerja



Prinsip Kerja dalam Algorima Genetik

Evaluasi solusi, Proses ini akan mengevaluasi setiap populasi
dengan menghitung nilai fitness setiap kromosom dan
mengevaluasinya sampai terpenuhi kriteria berhenti. Bila kriteria
berhenti belum terpenuhi maka akan dibentuk lagi generasi baru
dengan mengulangi langkah 2.
Beberapa kriteria berhenti yang sering digunakan antara lain:
Berhenti setelah dalam beberapa generasi berturut-turut
didapatkan nilai fitness tertinggi tidak berubah.
Berhenti bila dalam n generasi berikut tidak didapatkan nilai
fitness yang lebih tinggi.
Contoh
Algoritma Genetik Untuk Mencari Kata Secara Acak
Sebuah kata ditentukan sebagai target, misalnya:
‘BASUKI’. Bila setiap huruf diberi nilai dengan nilai urut
alfabet, maka targetnya bisa dinyatakan sebagai besaran
numerik :
Target=[2 1 19 21 11 9]
Komputer akan membangkitkan kata dengan jumlah huruf
yang sama dengan target secara acak, terus-menerus
hingga diperoleh kata yang sama dengan kata target.

Definisi Individu Dan Fitness

Individu adalah satu kata yang muncul dari proses acak tersebut,
misalnya : AGHSQE atau [1 7 8 19 17 5]
Satu individu mempunyai n gen integer yang setiap gennya
menyatakan no urut alfabet.
Nilai fitness adalah inversi dari perbedaan antara nilai kata yang
muncul (individu) dan target yang ditentukan. Misalnya kata yang
muncul : AGHSQE dan targetnya BASUKI maka, nilai perbedaannya:
E = |1-2| + |7-1| + |8-18| + |19-21| + |17-11| + |5-9|
= 1+6+10+2+6+4 = 29
Fitness = (26)(6) - 29 = 156-29 = 127


Pembangkitan Populasi  Awal

Populasi awal dibangkitkan dengan cara
membangkitkan semua huruf dalam sejumlah kata
(individu) yang dibangkitkan.
Pembangkitan Populasi
Awal

Seleksi, Cross-Over & Mutasi
 
Seleksi dilakukan dengan menggunakan roulette-wheel.
Cross-over, dilakukan dengan menukar gen-gen terpilih
antar dua induk
Mutasi dilakukan dengan mengacak kembali nilai 1-26
dari gen yang dimutasikan.

Part 4 Pencarian

Pencarian Heuristik

• Ada 4 metode pencarian heuristik
– Pembangkit & Pengujian (Generate and Test)
– Pendakian Bukit (Hill Climbing)
– Pencarian Terbaik Pertama (Best First Search)
– Simulated Annealing

Pencarian Terbaik Pertama
(Best First Search)

• Metode best-first search ini merupakan kombinasi dari
metode depth-first search dan metode breadth-first search
dengan mengambil kelebihan dari kedua metode tersebut.
• Apabila pada pencarian dengan metode hill climbing tidak
diperbolehkan untuk kembali ke node pada level yang
lebih rendah meskipun node pada level yang lebih rendah
tersebut memiliki nilai heuristik yang lebih baik, lain halnya
dengan metode best-first search ini.
• Pada metode best-first search, pencarian diperbolehkan
mengunjungi node yang ada di level yang lebih rendah,
jika ternyata node pada lebih yang lebih tinggi ternyata
memiliki nilai heuristik yang lebih buruk.

Pencarian Terbaik Pertama
(Best First Search)
• Metode best-first search ini merupakan kombinasi dari
metode depth-first search dan metode breadth-first search
dengan mengambil kelebihan dari kedua metode tersebut.
• Apabila pada pencarian dengan metode hill climbing tidak
diperbolehkan untuk kembali ke node pada level yang
lebih rendah meskipun node pada level yang lebih rendah
tersebut memiliki nilai heuristik yang lebih baik, lain halnya
dengan metode best-first search ini.
• Pada metode best-first search, pencarian diperbolehkan
mengunjungi node yang ada di level yang lebih rendah,
jika ternyata node pada lebih yang lebih tinggi ternyata
memiliki nilai heuristik yang lebih buruk.

Pencarian Terbaik Pertama
(Best First Search)

• Penentuan node berikutnya adalah node yang terbaik
yang pernah dibangkitkan
• Menggunakan informasi
– biaya perkiraan
– biaya sebenarnya
• Terdapat 2 jenis
– Greedy Best First Search
• biaya perkiraan f(n) = h(n)
– A*
• biaya perkiraan + biaya sebenarnya
• f(n) = g(n) + h(n) 

Pencarian Terbaik Pertama
(Best First Search)
• Untuk mengimplementasikan metode ini menggunakan
graph keadaan, dibutuhkan 2 antrian yang berisi node-
node, yaitu:
– OPEN, berisi node,node yang sudah dibangkitkan,
namun belum diuji. Umumnya berupa antrian
berprioritas yang berisi elemen-elemen dengan nilai
heuristik tertinggi.
– CLOSED berisi node-node yang sudah diuji.

Pencarian Terbaik Pertama
(Best First Search)

• Algoritma:
– Tempatkan node awal A pada antrian OPEN.
– Kerjakan langkah-langkah berikut hingga tujuan
ditemukan atau antrian OPEN sudah kosong:
– Ambil node terbaik dari OPEN;
– Bangkitkan semua successornya;
– Untuk tiap-tiap successor kerjakan:
– Jika node tersebut belum pernah dibangkitkan
sebelumnya, evaluasi node tersebut dan masukkan ke
OPEN;
– Jika node tersebut sudah pernah dibangkitkan
sebelumnya, ubah parent jika lintasan baru lebih
menjanjikan. Hapus node tersebut dari antrian OPEN.

METODE PENCARIAN DAN PELACAKAN

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

• Untuk mengukur perfomansi 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?

• Dua teknik pencarian dan pelacakan
– Pencarian buta (blind search)
• Pencarian melebar pertama (Breadth – First
Search)
• Pencarian mendalam pertama (Depth – First
Search)
– Pencarian terbimbing (heuristic search)
• Pendakian Bukit (Hill Climbing)
• Pencarian Terbaik Pertama (Best First Search)

Pencarian Melebar Pertama
(Breadth-First Search)

• Semua node pada level n akan dikunjungi
terlebih dahulu sebelum level n+1
• Mulai dari akar terus ke level 1 dari kiri ke
kanan
• Kemudian ke level selanjutnya hingga solusi
ditemukan

Pencarian Melebar Pertama
(Breadth-First Search)

• Keuntungan
– Tidak akan menemui jalan buntu
– Menjamin ditemukannya solusi (jika solusinya
memang ada) dan solusi yang ditemukan pasti
yang paling baik
– Jika ada satu solusi maka bread-first search akan
menemukannya
• Kelemahannya
– Membutuhkan memori yang cukup banyak
– Membutuhkan waktu yang cukup lama

Pencarian mendalam pertama
(Depth-First Search)

• Proses pencarian dilakukan pada semua
anaknya sebelum dilakukan pencarian ke
node-node yang selevel
• Keuntungan
– Memori yang relatif kecil
– Secara kebetulan, akan menemukan
solusi tanpa harus menguji lebih banyak
lagi

Pencarian Heuristik
• Pencarian buta tidak selalu dapat diterapkan dengan baik
– Waktu aksesnya yang cukup lama
– Besarnya memori yang diperlukan
• Metode heuristic search diharapkan bisa menyelesaikan
permasalahan yang lebih besar.
• Metode heuristic search menggunakan suatu fungsi yang
menghitung biaya perkiraan (estimasi) dari suatu simpul
tertentu menuju ke simpul tujuan ➔ disebut fungsi
heuristic
• Aplikasi yang menggunakan fungsi heuristic : Google,
Deep Blue Chess Machine

Pencarian Heuristik
• Contoh pada masalah 8 puzzle
1 2 3
7 8 4
6 5
1 2 3
8
6
4
7 5
Keadaan Awal Tujuan

Pencarian Heuristik
• Operator
– Ubin kosong geser ke kanan
– Ubin kosong geser ke kiri
– Ubin kosong geser ke atas
– Ubin kosong geser ke bawah

Pencarian Heuristik
• Langkah Awal
1 2 3
8 4
7 6 5
1 2 3
7 4
6 5
8
1 2 3
7 4
6 5
8
1 2 3
7 4
6 5
8
1 2 3
7 4
6 8 5
Tujuan
kanan
kiri atas

Pencarian Heuristik
• Langkah Awal hanya 3 operator yang bisa
digunakan
– Ubin kosong digeser ke kiri, ke kanan dan ke
atas.
• Jika menggunakan pencarian buta, tidak perlu
mengetahui operasi apa yang akan dikerjakan
(sembarang)
• Pada pencarian heuristik perlu diberikan
informasi khusus dalam domain tersebut

Informasi yang bisa
diberikan
• Untuk jumlah ubin yang menempati posisi yang benar
jumlah yang lebih tinggi adalah yang lebih diharapkan (lebih
baik)
1 2 3
8 4
7 6 5
1 2 3
7 4
6 5
8
1 2 3
7 4
6 5
8
1 2 3
7 4
6 5
8
1 2 3
7 4
6 8 5
Tujuan
kanan
kiri atas
h=6 h=4 h=5

Informasi yang bisa
diberikan
• Untuk jumlah ubin yang menempati posisi yang salah jumlah
yang lebih kecil adalah yang diharapkan (lebih baik).
1 2 3
8 4
7 6 5
1 2 3
7 4
6 5
8
1 2 3
7 4
6 5
8
1 2 3
7 4
6 5
8
1 2 3
7 4
6 8 5
Tujuan
kanan
kiri atas
h=2 h=4 h=3

Informasi yang bisa
diberikan
• Menghitung total gerakan yang diperlukan untuk mencapai
tujuan jumlah yang lebih kecil adalah yang diharapkan (lebih
baik).
1 2 3
8 4
7 6 5
1 2 3
7 4
6 5
8
1 2 3
7 4
6 5
8
1 2 3
7 4
6 5
8
1 2 3
7 4
6 8 5
Tujuan
kanan
kiri atas
h=2 h=4 h=4

Pencarian Heuristik
• Ada 4 metode pencarian heuristik
– Pembangkit & Pengujian (Generate and Test)
– Pendakian Bukit (Hill Climbing)
– Pencarian Terbaik Pertama (Best First Search)
– Simulated Annealing

Pembangkit & Pengujian
(Generate and Test)

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

Contoh
Traveling Salesman Problem (TSP)
• Seorang salesman ingin mengunjungi n kota. Jarak antara tiaptiap
kota sudah diketahui. Ingin diketahui rute terpendek dimana
setiap kota hanya boleh dikunjungi tepat 1 kali.
A B
D C
8
6
7 5
3 4

Contoh
Traveling Salesman Problem (TSP)
• Generate & test akan membangkitkan semua solusi yang
mungkin:
– A – B – C – D
– A – B – D – C
– A – C – B – D
– A – C – D – B, dll
A B C D
B C D
C D B D C B
D C D B B C

Lintasan
Pencarian
ke- Lintasan
Panjang
Lintasan Lintasan terpilih
Panjang
Lintasan
terpilih
1. ABCD 19 ABCD 19
2. ABDC 18 ABDC 18
3. ACBD 12 ACBD 12
4. ACDB 13 ACBD 12
5. ADBC 16 ACBD 12
6. ADCB 18 ACBD 12
7. BACD 17 ACBD 12
8. BADC 21 ACBD 12
9. BCAD 15 ACBD 12
10. BCDA 18 ACBD 12
11. BDAC 14 ACBD 12
12. BDCA 13 ACBD 12

Pencarian
ke- Lintasan
Panjang
Lintasan Lintasan terpilih
Panjang
Lintasan
terpilih


Pembangkit & Pengujian
(Generate and Test)

• Kelemahan
– Perlu membangkitkan semua kemungkinan
sebelum dilakukan pengujian
– Membutuhkan waktu yang cukup lama dalam
pencariannya

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.



Steepest Ascent Hill
Climbing

• Steepest-ascent hill climbing sebenarnya
hampir sama dengan simple hill climbing,
hanya saja gerakan pencarian tidak dimulai
dari posisi paling kiri.
• Gerakan selanjutnya dicari berdasarkan
nilai heuristik terbaik.
• Dalam hal ini urutan penggunaan operator
tidak menentukan penemuan solusi.

Steepest Ascent Hill
Climbing

• Steepest-ascent hill climbing sebenarnya
hampir sama dengan simple hill climbing,
hanya saja gerakan pencarian tidak dimulai
dari posisi paling kiri.
• Gerakan selanjutnya dicari berdasarkan
nilai heuristik terbaik.
• Dalam hal ini urutan penggunaan operator
tidak menentukan penemuan solusi.

Algoritma
• Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan,
maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang
sebagai keadaan awal.
• Kerjakan hingga tujuan tercapai atau hingga iterasi tidak memberikan
perubahan pada keadaan sekarang.
• Tentukan SUCC sebagai nilai heuristic terbaik dari successorsuccessor.
• Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang:
• Gunakan operator tersebut dan bentuk keadaan baru.
• Evaluasi keadaan baru tersebut. Jika merupakan tujuan, keluar. Jika
bukan, bandingkan nilai heuristiknya dengan SUCC. Jika lebih baik,
jadikan nilai heuristic keadaan baru tersebut sebagai SUCC. Namun
jika tidak lebih baik, nilai SUCC tidak berubah.

Part 2

MASALAH, RUANG KEADAAN, PENCARIAN

Pembahasan kaping setunggal membahas suatu problem/Masalah
yaitu:
Dalam pembangunan sistem masalah yang perlu kita pertimbangkan ada 4 hal, yaitu:
* Penjabaran dan pendefinisian masalah dengan tepat:
• Spesifikasi yang tepat mengenai keadaan awal
• Solusi yang diharapkan
*Penganalisisan masalah dengan tepat
*teknik penyelesaian masalah yang sesuai
– Merepresentasikan pengetahuan yang perlu untuk menyelesaikan masalah
– Memilih teknik penyelesaian masalah yang terbaik

Masalah Sebagai Ruang Keadaan
• Misalkan permasalahan yang dihadapi adalah Permainan Catur
• Maka harus ditentukan :
– Posisi awal pada papan catur
– Aturan-aturan untuk melakukan gerakan secara legal
– Tujuan (goal)

Posisi awal pada papan catur
• Posisi awal selalu sama

Aturan-aturan untuk melakukan gerakan secara legal
• Aturan-aturan sangat berguna untuk menentukan gerakan suatu bidak
• Untuk mempermudah
– huruf (a,b,c,d,e,f,g,h) horizontal
– angka (1,2,3,4,5,6,7,8) vertikal
• Contoh
– bidak (e,2) ke (e,4)
IF Bidak putih pada Kotak(e,2),
AND Kotak(e,3) Kosong,
AND Kotak(e,4) Kosong
Then Gerakkan bidak dari (e,2) ke (e,4)
Aturan-aturan untuk melakukan gerakan secara legal
• Aturan-aturan sangat berguna untuk menentukan gerakan suatu bidak
• Untuk mempermudah
– huruf (a,b,c,d,e,f,g,h) horizontal
– angka (1,2,3,4,5,6,7,8) vertikal
• Contoh
– bidak (e,2) ke (e,4)
IF Bidak putih pada Kotak(e,2),
AND Kotak(e,3) Kosong,
AND Kotak(e,4) Kosong
Then Gerakkan bidak dari (e,2) ke (e,4)

Aturan-aturan untuk melakukan gerakan secara legal

Tujuan (goal)
• Tujuan yang ingin dicapai adalah posisi pada papan catur yang menunjukkan kemenangan seseorang  terhadap lawannya
• Ditandai dengan posisi Raja yang sudah tidak dapat bergerak lagi
Tujuan (goal)
• Tujuan yang ingin dicapai adalah posisi pada papan catur yang menunjukkan kemenangan seseorang terhadap lawannya
• Ditandai dengan posisi Raja yang sudah tidak dapat bergerak lagi

Ruang Keadaan(State Space)
• Suatu ruang yang berisi semua keadaan yang mungkin
• Sehingga secara umum, untuk mendeskripsikan masalah dengan baik, harus:
– Mendefinisikan suatu ruang keadaan
– Menetapkan satu atau lebih keadaan awal
– Menetapkan satu atau lebih tujuan
– Menetapkan kupulan aturan
• Ada beberapa cara untuk merepresentasikan
Ruang Keadaan
Ruang Keadaan(State Space)
• Suatu ruang yang berisi semua keadaan yang mungkin
• Sehingga secara umum, untuk mendeskripsikan masalah dengan baik, harus:
– Mendefinisikan suatu ruang keadaan
– Menetapkan satu atau lebih keadaan awal
– Menetapkan satu atau lebih tujuan
– Menetapkan kupulan aturan
• Ada beberapa cara untuk merepresentasikan
Ruang Keadaan

Graph Keadaan
• Terdiri dari node-node yang menunjukkan keadaan yaitu keadaan awal dan keadaan
baru yang akan dicapai dengan menggunakan operator
• Node-node saling dihubungkan dengan menggunakan arc (busur) yang diberi panah
untuk menunjukkan arah
Graph Keadaan
• Terdiri dari node-node yang menunjukkan keadaan yaitu keadaan awal dan keadaan
baru yang akan dicapai dengan menggunakan operator
• Node-node saling dihubungkan dengan menggunakan arc (busur) yang diberi panah
untuk menunjukkan arah

Penyelesaian masalah secara umum
• Mendefinisikan suatu ruang keadaan;
• Menetapkan satu atau lebih keadaan awal;
• Menetapkan satu atau lebih tujuan;
• Menetapkan kumpulan aturan.

Penyelesaian
• Identifikasi ruang keadaan
– Permasalahan ini dapat dilambangkan dengan
(JumlahKambing, JumlahSerigala, JumlahSayuran,
JumlahBoat).
– Sebagai contoh: Daerah asal (0,1,1,1) berarti pada daerah
asal tidak ada kambing, ada serigala, ada sayuran, dan ada
boat.
• Keadaan Awal
– Daerah asal: (1,1,1,1)
– Daerah seberang: (0,0,0,0)
– Tujuan
– Daerah asal: (0,0,0,0)
– Daerah seberang: (1,1,1,1)
Penyelesaian
• Identifikasi ruang keadaan
– Permasalahan ini dapat dilambangkan dengan
(JumlahKambing, JumlahSerigala, JumlahSayuran,
JumlahBoat).
– Sebagai contoh: Daerah asal (0,1,1,1) berarti pada daerah
asal tidak ada kambing, ada serigala, ada sayuran, dan ada
boat.
• Keadaan Awal
– Daerah asal: (1,1,1,1)
– Daerah seberang: (0,0,0,0)
– Tujuan
– Daerah asal: (0,0,0,0)
– Daerah seberang: (1,1,1,1)

Aturan-aturan


Aturan
ke-
Aturan
1. Kambing menyeberang
2. Sayuran menyeberang
3. Serigala menyeberang
4. Kambing kembali
5. Sayuran kembali
6. Serigala kembali
7. Boat kembali

Penyelesaian


Daerah
Seberang
Daerah Asal
Aturan yang
dipakai
(1,1,1,1) (0,0,0,0) 1
(0,1,1,0) (1,0,0,1) 7
(0,1,1,1) (1,0,0,0) 3
(0,0,1,0) (1,1,0,1) 4
(1,0,1,1) (0,1,0,0) 2
(1,0,0,0) (0,1,1,1) 7
(1,0,0,1) (0,1,1,0) 1
(0,0,0,0) (1,1,1,1) solusi


Metode Pencarian dan
Pelacakan



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

Metode Pencarian dan
Pelacakan




Untuk mengukur perfomansi 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?

Metode Pencarian dan
Pelacakan



• Dua teknik pencarian dan pelacakan
– Pencarian buta (blind search)
• Pencarian melebar pertama (Breadth – First
Search)
• Pencarian mendalam pertama (Depth – First
Search)
– Pencarian terbimbing (heuristic search)
• Pendakian Bukit (Hill Climbing)
• Pencarian Terbaik Pertama (Best First Search)

Pencarian Melebar Pertama
(Breadth-First Search)
• Semua node pada level n akan dikunjungi
terlebih dahulu sebelum level n+1
• Mulai dari akar terus ke level 1 dari kiri ke
kanan
• Kemudian ke level selanjutnya hingga solusi
ditemukan
Pencarian Melebar Pertama
(Breadth-First Search)
• Semua node pada level n akan dikunjungi
terlebih dahulu sebelum level n+1
• Mulai dari akar terus ke level 1 dari kiri ke
kanan
• Kemudian ke level selanjutnya hingga solusi
ditemukan

Pencarian Melebar Pertama
(Breadth-First Search)
• Keuntungan
– Tidak akan menemui jalan buntu
– Menjamin ditemukannya solusi (jika solusinya
memang ada) dan solusi yang ditemukan pasti
yang paling baik
– Jika ada satu solusi maka bread-first search akan
menemukannya
• Kelemahannya
– Membutuhkan memori yang cukup banyak
– Membutuhkan waktu yang cukup lama
Pencarian Melebar Pertama
(Breadth-First Search)
• Keuntungan
– Tidak akan menemui jalan buntu
– Menjamin ditemukannya solusi (jika solusinya
memang ada) dan solusi yang ditemukan pasti
yang paling baik
– Jika ada satu solusi maka bread-first search akan
menemukannya
• Kelemahannya
– Membutuhkan memori yang cukup banyak
– Membutuhkan waktu yang cukup lama

Pencarian mendalam pertama
(Depth-First Search)
• Proses pencarian dilakukan pada semua
anaknya sebelum dilakukan pencarian ke
node-node yang selevel
• Keuntungan
– Memori yang relatif kecil
– Secara kebetulan, akan menemukan
solusi tanpa harus menguji lebih banyak
lagi
Pencarian mendalam pertama
(Depth-First Search)
• Proses pencarian dilakukan pada semua
anaknya sebelum dilakukan pencarian ke
node-node yang selevel
• Keuntungan
– Memori yang relatif kecil
– Secara kebetulan, akan menemukan
solusi tanpa harus menguji lebih banyak
lagi

Pencarian buta
(blind search)
• Kekurangan
– Memungkinkan tidak ditemukannya
tujuan yang diharapkan
– Hanya akan mendapatkan 1 solusi pada
setiap pencarian
Pencarian buta
(blind search)
• Kekurangan
– Memungkinkan tidak ditemukannya
tujuan yang diharapkan
– Hanya akan mendapatkan 1 solusi pada
setiap pencarian

Kecerdasan Buatan Part. 01

Artifical Intelegence bagian Siji


Kecerdasan buatan iku adalah suatu .......... aduh,mbuh ah lali.... sek tak lihat catatanku dulu,hehehe.....

Menurut apa yang saya pelajari pada kuliah minggu kemarin alias pertemuan pertama yaiku suatu ilmu yang mempelajari mesin komputer yang bisa mengerjakan pekerjaan manusia dan bisa mengerjakan sesuatu lebih baik dari apa yang dapat dilakukan oleh manusia bahkan lebih baik lagi dan lagi.

Menurut uncle John McCharty pada tahun 1956 ( zaman pak Karno masih suka tongkrong ma anak-anak vespa dan pake vespa berkepala bulat seperti yang biasa dinamakan dengan ENDGOG di daerah kemayoran baru, hehehehehe.... ) yaitu ilmu untuk mengetahui dan memodelkan proses-proses berpikir manusia & mendesain mesin agar dapat menirukan perilaku manusia.

Kelebihan AI antara lain =
-mempunyai sifat yang permanen
-Lebih cheaper than the others
-seperti yang biasa kita kenali, yaitu bisa didokumentasikan
-Lebih cepat lebih baik (seperti slogan salah satu PARPOL)
-Mudah di publikasikan

Kelebihan kecerdasan alami =
-Kreatif
-Daya Pemikiran yang luas
-Live Knowledge

Sekarang kita perbincangkan tentang sejarah AI

rikala jaman semono durung ono sego, Seorang ilmuwan bernama Alan Turing melakukan poercobaan pada sebuah komputer melalu terminalnya ditempatkan pada jarak yang jauh, lalu dengan eksperimennya itu Turing mengambil kesimpulan bahwa mesin juga bisa cerdas melebihi manusia, bahkan lebih cerdas lagi.

Ing ngisor iki tuladha2 ne bidang2 AI:
-Language Translator/penerjemah bahasa( seperti pada Google Translate )
-Text Summarization
-Pengenalan ucapan( Speech recognition )
-Pengolahan bahasa alami

Soft computing,
merupakan inovasi baru dalam membangun sistem cerdas.
Metodologi pada soft computing adalah yaitu
-Logika Fuzzy
-Jaringan Syaraf
-Probabilistic Reasuming
-Algoritma Genetika

Demikian blog ini saya buat dengan kesadaran dan tanpa paksaan apapun dari pihak lain. Thank you.
salam belajar dan jangan ngaku kaya kalau belum naek vespa!!!!
piss..